MACHINE LEARNING

Learning has many faces, not all of them part of traditional ML. Most
of this part of AI has to do with an agent acquiring or enhancing an
ability via a training regimen of some sort. Over time, with repeated
interaction with many items or trials of some general type, the system
comes to have a way of distinguishing "favorable" ones from the others
with a success rate better than chance (and hopefully a lot better).

This leaves out a good many ways in which we often learn; for
instance:

 - it does not include the kind of learning we refer to in
   saying "Today in class I learned that...
         ...Napoleon was defeated at Waterloo"
   or 
         ...an alpha particle is the same thing as a helium nucleus"
   namely learning a fact by reading or being told. 

 - it excludes learning by simple observation: I learned that Marge
   can run really fast (I saw her do it).

 - it also leaves out learning by inference, as in: "In my boredom I was
   doodling with numbers, and I just learned (figured out, discovered)
   that the sum of the first four primes is the same as my age." 
   Discovery is certainly one major way to learn things; it can happen by
   complete accident, or by keeping an eye out for something in a general
   way, and so on. Scientific discovery -- like detective work -- often
   involves having a hunch that examining something or other might reveal
   an insight; one does not know just what if anything will be found, but
   there may be indications of good places to look. And the result, when
   there is one, is something learned. Yet this kind of learning
   (purposeful discovery) is not usually included in what is called ML,
   and in fact automated scientific discovery is its own subarea of AI,
   with a very cognitive or KB style.  [Thought-Question: is this simply
   heuristic search and/or constraint satisfaction?]

Nevertheless, ML does deal with a number of important methods by which
learning can occur.  It is somewhat traditional to divide ML into the
following types:

CLASSIFICATION LEARNING: Here the aim is to learn divide a space of items
into two (or more) classes. There are at least three types:

1. Supervised Learning 

Here the system may be provided with positive and negative examples
and told which are which. The system tries to come up with a method
that distinguishes the two sorts, and then refines that method as more
examples are provided. This means that a human has already decided on
the classification and in effect is teaching it to (or hinting at it
for) the system. A famous example is that of learning the notion of an
arch (from either logically or visually-provided examples of
arches). One might ask why not just give a definition, but -- shades
of the qualification problem! -- very many natural categories (cup,
chair, and bird are good examples) defy precise definition.

There are many different algorithms for supervised learning, each with
advantages and disadvantages. A famous theorem (The No Free Lunch
Theorem) says that there is no one algorithm that works best on all
supervised learning problems. Among standard such algorithms are ones
based on neural networks (themselves based loosely on models of the
brain), support vector machines (which analyze data in terms of
features taken as dimensions in a vector space, and look for regions
in that space that ideally hold all and only positive cases), decision
trees, and so-called naive Bayes' classifiers (which use conditional
probabilities to determine features that make it likely that a given
case is one of the positive ones).


2. Unsupervised Learning

Sometimes there is no previous human classification for a given type
of data, and the aim is to find interesting classifications. [This is
similar to scientific discovery. But frequently in the latter case the
discoverers tend to have an idea of what they are looking for, based
on an existing understanding of some of the underlying phenomenon. An
exception was early biological classifications based largely on little
more than the visible forms of the bodies of organisms.] A robot on
Mars might be instructed to collect samples of different sorts of
things -- but if we don't know what sort of things might be there
(which is why we send the robot!) then we can't tell it what to look
for or how to tell if two things are the same or different. So it will
have to come up with its own classification of things based on what it
finds. 

Some supervised learning methods (such as neural networks) can also be
used for unsupervised learning.  Statistical methods (eg, multivariate
analysis) also provide powerful tools here.

3. Semi-Supervised Learning

Sometimes the two classification styles above are combined, with some
"labeled" data ( as positive and negative items) and (typically a much
larger set of) unlabeled data. A reason to do this is that it can be
very time-consuming for humans to label data. An example is that of
identifying handwritten text. The variation in how people write a
given letter is enormous. A human can specify, say, 50 versions of
each letter, and then provide many thousands more that have not been
classified yet. Under certain assumptions, the 50 labelled cases of
each letter might provide a kind of preliminary classification that
the additional unlabelled cases can then actually help crystallize into
a more refined classification. It can be tricky, and does not always
work. But sometimes it is very powerful.

Here is an oversimplified but intuitive example: Consider three
leaves, one green, one yellow, and one red, all labeled as such. But
colors come in many shades. Now suppose that 1000 more leaves are
provided, and not labelled. If it happens that they naturally fall
into five color types (say dark green, pale green, yellow, orange, and
red) then an algorithm that had learned the initial three colors would
have trouble with in-between cases. So it could, for instance,
classify leaves into:

definite green
uncertain between green and yellow
definite yellow
uncertain between yellow and red
definite red

and this then would be -- in the case just described -- a far more
informative classification scheme.


ACTION-SUCCESS LEARNING

Here the aim is for the system to learn about an unfamiliar
environment, and in particular to learn about "good" and "bad" states
of it (their "location" rather than their distinguishing features).
Again, there are many algorithms that can do this.  One family of such
algorithms goes by the name of Reinforcement Learning.

This is based on the idea from behaviorist psychology of reinforcing
or rewarding "good" behaviors so as to encourage more of the same. The
idea is that an agent has various actions available to it in any given
state of its world, and some actions produce more reward than
others. An agent then might operate by learning from experience over
time which actions in which states tend to produce the greatest
reward.

But an agent that always chooses the immediately largest-reward action
(instant gratification!)  might have a total reward that is smaller
than that of an agent that pays attention to rate of reward
accumulation over time (short-term pain for long-term gain!) than
simply reward now.  A common scenario for this is exploration of
unknown territory, where good (or bad or neutral) things can be
found. 

For some reinforcement learning algorithms there are convergence
theorems guaranteeing that -- given enough time -- the algorithm will
converge to an optimal set of action choices, i.e., ones that
guarantee the maximum possible rate of reward for a given environment.

One such algorithm is called Q-learning. Here is an example (based on
work in my lab) of what can happen when it is applied to a
2-dimensional grid with a reward structure that stays fixed for many
trials, and then suddenly changes to a new fixed structure.


Chippy gets hungry:

 - hunts about, seeing when up-down-left-right are effective.
 - learns in about 1000 turns a very good action-policy
 - then at turn 10,000 the rewards structure is drastically altered:
	nuts now on the ground, not in trees.
 - has no concept of its policy being bad; just continues to refine it
	little by little, having to gradually unlearn things in the
	same slow way it learned them in the first place, but taking
	even longer since the learned policy has by then many
	subtleties that reinforcement learning is not equipped to
	shake off.
 - in the end, it takes far more than twice as long to adapt to the
	new reward structure.

So, what to do? Real chipmunks do not continue hunting in trees for
nuts that are not there. They quickly realize their policy is not
working, and give it up altogether.

We built a small “metacognitive” unit on top of the Q-learning
algorithm, that simply threw out the learned policy if the reward rate
dropped and stayed low for more than a small number of turns. And it
had the obvious result: after turn 10,000, it again took only about
1000 turns to learn a new policy that was honed to the new rewards.