AI-MaxEntropy
view release on metacpan or search on metacpan
AI-MaxEntropy.xs view on Meta::CPAN
int y_num;
int** lambda_idx;
};
/**************************************************************************
* EXPORTED XSUBS
**************************************************************************/
MODULE = AI::MaxEntropy PACKAGE = AI::MaxEntropy
void
_neg_log_likelihood(lambda_in, step, self, OUTLIST SV* f, OUTLIST SV* g)
AV* lambda_in
SV* step
SV* self
PREINIT:
dTRACE("_neg_log_likelihood");
/* fetch the pre-cached samples and f_map */
SV* _c = *hvref_fetch(self, "_c");
struct samples_t* samples =
INT2PTR(struct samples_t*, SvIV(*hvref_fetch(_c, "samples")));
struct f_map_t* f_map =
INT2PTR(struct f_map_t*, SvIV(*hvref_fetch(_c, "f_map")));
int** lambda_idx = f_map->lambda_idx;
/* fetch other useful data */
SV* smoother = *hvref_fetch(self, "smoother");
int x_num = SvIV(*hvref_fetch(self, "x_num"));
int y_num = SvIV(*hvref_fetch(self, "y_num"));
int f_num = SvIV(*hvref_fetch(self, "f_num"));
/* intermediate variables */
AV* av_d_log_lh;
char* smoother_type;
int i, j, x, y, lambda_i;
double log_lh, sum_exp_lambda_f, sigma, fxy;
double* lambda_f = (double*)malloc(sizeof(double) * y_num);
double* exp_lambda_f = (double*)malloc(sizeof(double) * y_num);
double* d_log_lh = (double*)malloc(sizeof(double) * f_num);
double* lambda = (double*)malloc(sizeof(double) * f_num);
CODE:
/* initialize */
TRACE("enter");
for (i = 0; i < f_num; i++)
lambda[i] = SvNV(*av_fetch(lambda_in, i, 0));
log_lh = 0;
for (i = 0; i < f_num; i++) d_log_lh[i] = 0;
TRACE("finish initializing");
/* calculate log likelihood and its gradient */
for (i = 0; i < samples->s_num; i++) {
/* log likelihood */
for (sum_exp_lambda_f = 0, y = 0; y < y_num; y++) {
for (lambda_f[y] = 0, j = 0; j < samples->x_len[i]; j++) {
lambda_i = lambda_idx[y][samples->x[i][j]];
if (lambda_i != -1) lambda_f[y] += lambda[lambda_i];
}
sum_exp_lambda_f += (exp_lambda_f[y] = exp(lambda_f[y]));
}
log_lh += samples->w[i] *
(lambda_f[samples->y[i]] - log(sum_exp_lambda_f));
/* gradient */
for (y = 0; y < y_num; y++) {
fxy = (y == samples->y[i] ? 1.0 : 0.0);
for (j = 0; j < samples->x_len[i]; j++) {
lambda_i = lambda_idx[y][samples->x[i][j]];
if (lambda_i != -1)
d_log_lh[lambda_i] += samples->w[i] *
(fxy - exp_lambda_f[y] / sum_exp_lambda_f);
}
}
}
TRACE("finish log likelihood and gradient");
/* smoothing */
if (SvOK(smoother) && hvref_exists(smoother, "type")) {
smoother_type = SvPV_nolen(*hvref_fetch(smoother, "type"));
if (strcmp(smoother_type, "gaussian") == 0) {
sigma = SvOK(*hvref_fetch(smoother, "sigma")) ?
SvNV(*hvref_fetch(smoother, "sigma")) : 1.0;
for (i = 0; i < f_num; i++) {
log_lh -= (lambda[i] * lambda[i]) / (2 * sigma * sigma);
d_log_lh[i] -= lambda[i] / (sigma * sigma);
}
}
}
TRACE("finish smoothing");
/* negate the value and finish */
log_lh = -log_lh;
av_d_log_lh = newAV();
av_extend(av_d_log_lh, f_num - 1);
for (i = 0; i < f_num; i++)
av_store(av_d_log_lh, i, newSVnv(-d_log_lh[i]));
f = sv_2mortal(newSVnv(log_lh));
g = sv_2mortal(newRV_noinc((SV*)av_d_log_lh));
TRACE("leave");
CLEANUP:
free(lambda_f);
free(exp_lambda_f);
free(d_log_lh);
free(lambda);
SV*
_apply_gis(self, progress_cb, epsilon)
SV* self
SV* progress_cb
double epsilon
PREINIT:
dSP;
dTRACE("_apply_gis");
AI-MaxEntropy.xs view on Meta::CPAN
lambda_i = lambda_idx[y][samples->x[i][j]];
if (lambda_i != -1)
p1_f[lambda_i] += pxy * samples->w[i];
}
}
}
/* lambda = lambda + d_lambda */
d_lambda_norm = 0;
lambda_norm = 0;
for (i = 0; i < f_num; i++) {
d_lambda[i] = (1.0 / af_num) * log(p_f[i] / p1_f[i]);
lambda[i] += d_lambda[i];
d_lambda_norm += d_lambda[i] * d_lambda[i];
lambda_norm += lambda[i] * lambda[i];
}
d_lambda_norm = sqrt(d_lambda_norm);
lambda_norm = sqrt(lambda_norm);
/* call progress_cb if defined */
if (SvOK(progress_cb) && SvROK(progress_cb) &&
SvTYPE(SvRV(progress_cb)) == SVt_PVCV) {
TRACE("call progress_cb");
the concept 'feature'
0.11 Sat Feb 16 17:27:00 2008
- Optimize the XS code, now the the function 'learn' should run
at least twice faster than 0.10 version
- New functions in AI::MaxEntropy::Util, which allows the client
program manipulate samples more flexibly
- Replace Test::Differences with is_deeply in Test::More
0.10 Wed Feb 13 16:56:00 2008
- rewrite the log likelihood evaluation and smoothing by C, now
the ME learner should run more than 10 times faster than the
previous version
- add a new module AI::MaxEntropy::Util, which provides some
utilities for doing experiments with ME learners
- AI::MaxEntropy::see now accepts attribute-value style samples
- include Algorithm::Diff in the distribution for testing
0.02 Thu Feb 7 11:26:00 2008
- some tiny corrections :-P
If ommited, 'lbfgs' is used by default.
progress_cb
The entry "progress_cb => ..." specifies the progress callback
subroutine which is used to trace the process of the algorithm. The
specified callback routine will be called at each iteration of the
algorithm.
For L-BFGS, "progress_cb" will be directly passed to "fmin" in
Algorithm::LBFGS. f(x) is the negative log-likelihood of current lambda
vector.
For GIS, the "progress_cb" is supposed to have a prototype like
progress_cb(i, lambda, d_lambda, lambda_norm, d_lambda_norm)
"i" is the number of the iterations, "lambda" is an array ref containing
the current lambda vector, "d_lambda" is an array ref containing the
delta of the lambda vector in current iteration, "lambda_norm" and
"d_lambda_norm" are Euclid norms of "lambda" and "d_lambda"
inc/Test/Builder.pm view on Meta::CPAN
my $self = shift;
my($file_or_fh) = shift;
my $fh;
if( $self->is_fh($file_or_fh) ) {
$fh = $file_or_fh;
}
else {
$fh = do { local *FH };
open $fh, ">$file_or_fh" or
$self->croak("Can't open test output log $file_or_fh: $!");
_autoflush($fh);
}
return $fh;
}
sub _autoflush {
my($fh) = shift;
my $old_fh = select $fh;
lib/AI/MaxEntropy.pm view on Meta::CPAN
my $self = shift;
# cut 0 for default
$self->cut(0) if $self->{last_cut} == -1;
# initialize
$self->{lambda} = [map { 0 } (1 .. $self->{f_num})];
$self->_cache;
# optimize
my $type = $self->{algorithm}->{type} || 'lbfgs';
if ($type eq 'lbfgs') {
my $o = Algorithm::LBFGS->new(%{$self->{algorithm}});
$o->fmin(\&_neg_log_likelihood, $self->{lambda},
$self->{algorithm}->{progress_cb}, $self);
}
elsif ($type eq 'gis') {
die 'GIS is not applicable'
if $self->{af_num} == -1 or $self->{last_cut} != 0;
my $progress_cb = $self->{algorithm}->{progress_cb};
$progress_cb = sub {
print "$_[0]: |lambda| = $_[3], |d_lambda| = $_[4]\n"; 0;
} if defined($progress_cb) and $progress_cb eq 'verbose';
my $epsilon = $self->{algorithm}->{epsilon} || 1e-3;
lib/AI/MaxEntropy.pm view on Meta::CPAN
If ommited, C<'lbfgs'> is used by default.
=head3 progress_cb
The entry C<progress_cb =E<gt> ...> specifies the progress callback
subroutine which is used to trace the process of the algorithm.
The specified callback routine will be called at each iteration of the
algorithm.
For L-BFGS, C<progress_cb> will be directly passed to
L<Algorithm::LBFGS/fmin>. C<f(x)> is the negative log-likelihood of current
lambda vector.
For GIS, the C<progress_cb> is supposed to have a prototype like
progress_cb(i, lambda, d_lambda, lambda_norm, d_lambda_norm)
C<i> is the number of the iterations, C<lambda> is an array ref containing
the current lambda vector, C<d_lambda> is an array ref containing the
delta of the lambda vector in current iteration, C<lambda_norm> and
C<d_lambda_norm> are Euclid norms of C<lambda> and C<d_lambda> respectively.
=item 2.
This file.
=item 3.
The name and version of the module you were trying to build.
=item 4.
A full log of the build that failed.
=item 5.
Any other information that you think could be relevant.
=back
For the latest version of this code, please get the C<Devel::PPPort>
module from CPAN.
newSVuv|5.006000||p
newSV|||
newUNOP|||
newWHILEOP||5.009003|
newXSproto||5.006000|
newXS||5.006000|
new_collate||5.006000|
new_constant|||
new_ctype||5.006000|
new_he|||
new_logop|||
new_numeric||5.006000|
new_stackinfo||5.005000|
new_version||5.009000|
next_symbol|||
nextargv|||
nextchar|||
ninstr|||
no_bareword_allowed|||
no_fh_allowed|||
no_op|||
t/02-learn_by_lbfgs.t view on Meta::CPAN
NAME 'Load the module';
BEGIN { use_ok 'AI::MaxEntropy' }
my $me = AI::MaxEntropy->new(smoother => {});
$me->see(['round', 'smooth', 'red'] => 'apple' => 2);
$me->see(['long', 'smooth', 'yellow'] => 'banana' => 3);
$me->cut(0);
$me->_cache;
###
NAME 'Negative log likelihood calculation (lambda = all 0)';
my ($f, $g) = AI::MaxEntropy::_neg_log_likelihood(
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], undef, $me
);
delta_ok
[
$f,
$g
],
[
- (2 * log(0.5) + 3 * log(0.5)),
[
- ((1 - 0.5) * 2 + 0 * 3),
- ((1 - 0.5) * 2 + (0 - 0.5) * 3),
- ((1 - 0.5) * 2 + 0 * 3),
- (0 * 2 + (0 - 0.5) * 3),
- (0 * 2 + (0 - 0.5) * 3),
- ((0 - 0.5) * 2 + 0 * 3),
- ((0 - 0.5) * 2 + (1 -0.5) * 3),
- ((0 - 0.5) * 2 + 0 * 3),
- (0 * 2 + (1 - 0.5) * 3),
- (0 * 2 + (1 - 0.5) * 3)
]
],
$__;
###
NAME 'Negative log likelihood calculation (lambda = random .1 and 0)';
($f, $g) = AI::MaxEntropy::_neg_log_likelihood(
[.1, .1, 0, 0, 0, .1, .1, 0, 0, .1], undef, $me
);
delta_ok
[
$f,
$g
],
[
- (log(exp(.1) / (2 * exp(.1))) * 2 +
log(exp(.2) / (exp(.1) + exp(.2))) * 3),
[
- ((1 - exp(.1) / (2 * exp(.1))) * 2 + 0 * 3),
- ((1 - exp(.1) / (2 * exp(.1))) * 2 +
(0 - exp(.1) / (exp(.1) + exp(.2))) * 3),
- ((1 - exp(.1) / (2 * exp(.1))) * 2 + 0 * 3),
- (0 * 2 + (0 - exp(.1) / (exp(.1) + exp(.2))) * 3),
- (0 * 2 + (0 - exp(.1) / (exp(.1) + exp(.2))) * 3),
- ((0 - exp(.1) / (2 * exp(.1))) * 2 + 0 * 3),
- ((0 - exp(.1) / (2 * exp(.1))) * 2 +
(1 - exp(.2) / (exp(.1) + exp(.2))) * 3),
- ((0 - exp(.1) / (2 * exp(.1))) * 2 + 0 * 3),
- (0 * 2 + (1 - exp(.2) / (exp(.1) + exp(.2))) * 3),
- (0 * 2 + (1 - exp(.2) / (exp(.1) + exp(.2))) * 3)
]
],
$__;
###
NAME 'Negative log likelihood calculation (with Gaussian smoother)';
$me->{smoother} = { type => 'gaussian', sigma => .5 };
($f, $g) = AI::MaxEntropy::_neg_log_likelihood(
[0, 0, .1, .1, 0, 0, 0, .1, .1, .1], undef, $me
);
delta_ok
[
$f,
$g
],
[
- (log(exp(.1) / (2 * exp(.1))) * 2 +
log(exp(.2) / (exp(.1) + exp(.2))) * 3 -
(5 * .1 ** 2) / (2 * .5 ** 2)),
[
- ((1 - exp(.1) / (2 * exp(.1))) * 2 + 0 * 3 - 0 / .5 ** 2),
- ((1 - exp(.1) / (2 * exp(.1))) * 2 +
(0 - exp(.1) / (exp(.1) + exp(.2))) * 3 - 0 / .5 ** 2),
- ((1 - exp(.1) / (2 * exp(.1))) * 2 + 0 * 3 - .1 / .5 ** 2),
- (0 * 2 + (0 - exp(.1) / (exp(.1) + exp(.2))) * 3 - .1 / .5 ** 2),
- (0 * 2 + (0 - exp(.1) / (exp(.1) + exp(.2))) * 3 - 0 / .5 ** 2),
- ((0 - exp(.1) / (2 * exp(.1))) * 2 + 0 * 3 - 0 / .5 ** 2),
- ((0 - exp(.1) / (2 * exp(.1))) * 2 +
t/03-learn_by_gis.t view on Meta::CPAN
3 * (exp(0) / (exp(0) + exp(0))),
3 * (exp(0) / (exp(0) + exp(0)))
];
delta_ok
[
$lambda,
$d_lambda
],
[
[
(1.0 / 3) * log(2 / $p1_f->[0]),
(1.0 / 3) * log(2 / $p1_f->[1]),
(1.0 / 3) * log(2 / $p1_f->[2]),
(1.0 / 3) * log($zero / $p1_f->[3]),
(1.0 / 3) * log($zero / $p1_f->[4]),
(1.0 / 3) * log($zero / $p1_f->[5]),
(1.0 / 3) * log(3 / $p1_f->[6]),
(1.0 / 3) * log($zero / $p1_f->[7]),
(1.0 / 3) * log(3 / $p1_f->[8]),
(1.0 / 3) * log(3 / $p1_f->[9])
],
[
(1.0 / 3) * log(2 / $p1_f->[0]),
(1.0 / 3) * log(2 / $p1_f->[1]),
(1.0 / 3) * log(2 / $p1_f->[2]),
(1.0 / 3) * log($zero / $p1_f->[3]),
(1.0 / 3) * log($zero / $p1_f->[4]),
(1.0 / 3) * log($zero / $p1_f->[5]),
(1.0 / 3) * log(3 / $p1_f->[6]),
(1.0 / 3) * log($zero / $p1_f->[7]),
(1.0 / 3) * log(3 / $p1_f->[8]),
(1.0 / 3) * log(3 / $p1_f->[9])
]
],
$__;
###
NAME 'The second iteration';
my @l = @$lambda;
$me->{algorithm}->{progress_cb} =
sub { ($lambda, $d_lambda) = ($_[1], $_[2]); $n++; $n >= 2 ? 1 : 0 };
$me->learn;
t/03-learn_by_gis.t view on Meta::CPAN
3 * $p1_1,
3 * $p1_1
];
delta_ok
[
$lambda,
$d_lambda
],
[
[
$l[0] + (1.0 / 3) * log(2 / $p1_f->[0]),
$l[1] + (1.0 / 3) * log(2 / $p1_f->[1]),
$l[2] + (1.0 / 3) * log(2 / $p1_f->[2]),
$l[3] + (1.0 / 3) * log($zero / $p1_f->[3]),
$l[4] + (1.0 / 3) * log($zero / $p1_f->[4]),
$l[5] + (1.0 / 3) * log($zero / $p1_f->[5]),
$l[6] + (1.0 / 3) * log(3 / $p1_f->[6]),
$l[7] + (1.0 / 3) * log($zero / $p1_f->[7]),
$l[8] + (1.0 / 3) * log(3 / $p1_f->[8]),
$l[9] + (1.0 / 3) * log(3 / $p1_f->[9])
],
[
(1.0 / 3) * log(2 / $p1_f->[0]),
(1.0 / 3) * log(2 / $p1_f->[1]),
(1.0 / 3) * log(2 / $p1_f->[2]),
(1.0 / 3) * log($zero / $p1_f->[3]),
(1.0 / 3) * log($zero / $p1_f->[4]),
(1.0 / 3) * log($zero / $p1_f->[5]),
(1.0 / 3) * log(3 / $p1_f->[6]),
(1.0 / 3) * log($zero / $p1_f->[7]),
(1.0 / 3) * log(3 / $p1_f->[8]),
(1.0 / 3) * log(3 / $p1_f->[9])
]
],
$__;
( run in 1.985 second using v1.01-cache-2.11-cpan-49f99fa48dc )