view release on metacpan or  search on metacpan

lib/Algorithm/AM/algorithm.pod  view on Meta::CPAN

package Algorithm::AM::algorithm;
use strict;
use warnings;
# ABSTRACT: How the Analogical Modeling algorithm works
# VERSION

1;

__END__

=pod

=encoding UTF-8

=head1 NAME

Algorithm::AM::algorithm - How the Analogical Modeling algorithm works

=head1 VERSION

version 3.13

=head1 DESCRIPTION

First, the user must create a set of data items, with their outcomes,
and some test items.  All of these items are represented by I<feature
vectors>.  These feature vectors are I<not> created by the AM
algorithm; they could be generated by hand or script, it matters not
to AM.  All the feature vectors must be of the same length, call it
I<n>.

=head2 The supracontextual lattice

AM requires the construction of a I<supracontextual lattice>.  It is
merely a complete distributive lattice of sets called
I<supracontexts>, each one labeled with an integer in the range 0
to S<2^I<n> - 1>.  If I<a> and I<b> are labels of two supracontexts,
then I<a> & I<b> = I<b> (that's bitwise AND) iff the supracontext
labeled by I<a> is a superset of the supracontext labeled by I<b>.

The supracontextual lattice starts out with every element being the
empty set.  The AM algorithm adds I<subcontexts> to them one at a
time.

=head2 Subcontexts

Subcontexts are also sets, and they are also labeled with an integer
in the range 0 to S<2^I<n> - 1>.  The elements of the subcontexts are
data items.

=over 4

=item Example

Suppose that the test item has feature vector

('S', 'O', '0', 'S', 'R', '0', 'T', 'A')

and a data item has the feature vector

('P', 'Y', 'V', 'S', 'R', '0', 'T', 'a').

Compare the corresponding features, using a 1 for different and 0 for
same.  Then the binary number

0b11100001

is the label of the subcontext to which the data item belongs.

=back

=head2 Filling the supracontextual lattice

The elements of the supracontexts are the subcontexts.  If a
subcontext has label I<a>, then it will be an element of any
supracontext whose label I<b> satisfies I<b> & I<a> = I<a>.

Thus, the subcontext labeled by 0b11100001 will belong to 16 different
supracontexts.  The labels of these supracontexts are found by
replacing the 0s by 1s in all possible ways; the original 1s are left
untouched.

=head2 Homogeneity and Heterogeneity

A supracontext is I<heterogeneous> if the following two conditions
hold:

=over 4

=item 1

The supracontext contains two or more subcontexts.

=item 2

The data items contained in these subcontexts do not share a common
outcome.

=back

Otherwise, the supracontext is I<homogeneous>.  Only homogeneous