Redundancy Reduction and Pattern Recognition
============================================

<img align=left width=150
src="http://www.weareatheism.com/wp-content/uploads/2014/02/Richard-Dawkins-The-Selfish-Genes.jpg">
From Richard Dawkins : Evolutionary Biologist;
Emeritus Professor of the Public Understanding of
Science, Oxford; Author, The Greatest Show on Earth,
The Magic of Reality

<br clear=all>

Deep, elegant, beautiful? Part of what makes a
theory elegant is its power to explain much while
assuming little. Here, Darwin's natural selection
wins hands down. The ratio of the huge amount that
it explains (everything about life: its complexity,
diversity and illusion of crafted design) divided by
the little that it needs to postulate (non-random
survival of randomly varying genes through
geological time) is gigantic. Never in the field of
human comprehension were so many facts explained by
assuming so few. Elegant then, and deep—its depths
hidden from everybody until as late as the
nineteenth century. On the other hand, for some
tastes natural selection is too destructive, too
wasteful, too cruel to count as beautiful. In any
case, coming late to the party as ever, I can count
on somebody else choosing Darwin. I'll take his
great grandson instead, and come back to Darwin at
the end.

Horace Barlow FRS is the youngest grandchild of Sir
Horace Darwin, Charles Darwin's youngest child. Now
a very active ninety, Barlow is a member of a
distinguished lineage of Cambridge
neurobiologists. I want to talk about an idea that
he published in two papers in 1961, on redundancy
reduction and pattern recognition. It is an idea
whose ramifications and significance have inspired
me throughout my career.

The folklore of neurobiology includes a mythical
'grandmother neurone', which fires only when a very
particular image, the face of Jerry Lettvin's
grandmother, falls on the retina (Lettvin was a
distinguished American neurobiologist who, like
Barlow, worked on the frog retina). The point is
that Lettvin's grandmother is only one of countless
images that a brain is capable of recognising. If
there were a specific neurone for everything we can
recognise—not just Lettvin's grandmother but lots of
other faces, objects, letters of the alphabet,
flowers, each one seen from many angles and
distances, we would have a combinatorial
explosion. If sensory recognition worked on the
'grandmother principle', the number of specific
recognition neurones for all possible combinations
of nerve impulses would exceed the number of atoms
in the universe. Independently, the American
psychologist Fred Attneave had calculated that the
volume of the brain would have to be measured in
cubic light years. Barlow and Attneave independently
proposed redundancy reduction as the answer.

Claude Shannon, inventor of Information Theory,
coined 'redundancy' as a kind of inverse of
information. In English, 'q' is always followed by
'u', so the 'u' can be omitted without loss of
information. It is redundant. Wherever redundancy
occurs in a message (which is wherever there is
nonrandomness), the message can be more economically
recoded without loss of information (although with
some loss in capacity to correct errors). Barlow
suggested that, at every stage in sensory pathways,
there are mechanisms tuned to eliminate massive
redundancy.

The world at time t is not greatly different from
the world at time t-1. Therefore it is not necessary
for sensory systems continuously to report the state
of the world. They need only signal changes, leaving
the brain to assume that everything not reported
remains the same. Sensory adaptation is a well-known
feature of sensory systems, which does precisely as
Barlow prescribed. If a neurone is signalling
temperature, for example, the rate of firing is not,
as one might naively suppose, proportional to the
temperature. Instead, firing rate increases only
when there is a change in temperature. It then dies
away to a low resting frequency. The same is true of
neurones signalling brightness, loudness, pressure
and so on. Sensory adaptation achieves huge
economies by exploiting the non-randomness in
temporal sequence of states of the world.

What sensory adaptation achieves in the temporal
domain, the well-established phenomenon of lateral
inhibition does in the spatial domain. If a scene in
the world falls on a pixellated screen, such as the
back of a digital camera or the retina of an eye,
most pixels see the same as their immediate
neighbours. The exceptions are those pixels which
lie on edges, boundaries. If every retinal cell
faithfully reported its light value to the brain,
the brain would be bombarded with a massively
redundant message. Huge economies can be achieved if
most of the impulses reaching the brain come from
pixel cells lying along edges in the scene. The
brain then assumes uniformity in the spaces between
edges.

As Barlow pointed out, this is exactly what lateral
inhibition achieves. In the frog retina, for
example, every ganglion cell sends signals to the
brain, reporting on the light intensity in its
particular location on the surface of the
retina. But it simultaneously sends inhibitory
signals to its immediate neighbours. This means that
the only ganglion cells to send strong signals to
the brain are those that lie on an edge. Ganglion
cells lying in uniform fields of colour (the
majority) send few if any impulses to the brain
because they, unlike cells on edges, are inhibited
by all their neighbours. The spatial redundancy in
the signal is eliminated.

The Barlow analysis can be extended to most of what
is now known about sensory neurobiology, including
Hubel and Wiesel's famous horizontal and vertical
line detector neurones in cats (straight lines are
redundant, reconstructable from their ends), and in
the movement ('bug') detectors in the frog retina,
discovered by the same Jerry Lettvin and his
colleagues. Movement represents a non-redundant
change in the frog's world. But even movement is
redundant if it persists in the same direction at
the same speed. Sure enough, Lettvin and colleagues
discovered a 'strangeness' neurone in their frogs,
which fires only when a moving object does something
unexpected, such as speeding up, slowing down, or
changing direction. The strangeness neurone is tuned
to filter out redundancy of a very high order.

Barlow pointed out that a survey of the sensory
filters of a given animal could, in theory, give us
a read-out of the redundancies present in the
animal's world. They would constitute a kind of
description of the statistical properties of that
world. Which reminds me, I said I'd return to
Darwin. In Unweaving the Rainbow, I suggested that
the gene pool of a species is a 'Genetic Book of the
Dead', a coded description of the ancestral worlds
in which the genes of the species have survived
through geological time. Natural selection is an
averaging computer, detecting redundancies—repeat
patterns—in successive worlds (successive through
millions of generations) in which the species has
survived (averaged over all members of the sexually
reproducing species). Could we take what Barlow did
for neurones in sensory systems, and do a parallel
analysis for genes in naturally selected gene pools?
Now that would be deep, elegant and beautiful.


## From Neurons to High-Level rules

From _Data Mining for Very Busy People_ 2003 by Tim Menzies and Ying Hu IEEE
Computer, [http://menzies.us/pdf/03tar2.pdf](http://menzies.us/pdf/03tar2.pdf)

For 21st-century businesses, the problem is not
accessing data but ignoring irrelevant data. Most
modern businesses can electronically access
mountains of data such as transactions for the past
two years or the state of their assembly line. The
trick is effectively using the available data. In
practice, this means summarizing large data sets to
find the "pearls in the dust"- that is, the data that
really matters.

In the data mining community, "learning the least"
is an uncommon goal. Most data miners are zealous
hunters seeking detailed summaries and generating
extensive and lengthy descriptions. The "Data Mining
Treatment Learning" sidebar discusses some work in
this area. Here, we take a different approach and
assume that busy people don't need- or can't
use- complex models. Rather, they want only the data
they need to achieve the most benefits.

Instead of finding extensive descriptions of things,
the TAR2 "treatment learner" is a data mining tool
that hunts for a minimal difference set between
things. A list of essential differences is easier to
read and understand than detailed
descriptions. Overly elaborate models can
complicate, not clarify, a situation. Cognitive
scientists and researchers studying human decision
making note that humans often use simple models
rather than intricate ones. Because it learns much
smaller models, TAR2 provides better support for
real-world decision making than standard data
miners.

### What is Different About TAR2?

TAR2 is a different kind of data miner.
Standard data miners produce classifiers that can *categorize* a new
example into some class.

A *treatment learner* finds rules that *change* the expected class
distribution (compare to some baseline).

Classifiers are used for *recognition* tasks; e.g. find what toys to
remove from the assembly line because they are defective.

Treatment learners are used for *planning* some minimal action to
improve the odds that something will be later be recognized as belonging
to some class. A treatment learner could be used to make repairs to the
defective toys rejected from the assembly line.

Treatment learners are all about minimality that is, what is the *least*
you need to do to *most* effect something.

Classifiers are all about representational accuracy. If the target
complex is complex then the resulting tree can be complex.

### Example

For example, here's WEKA's J4.8. learning from 506 examples of low,
medlow, medhigh, high quality house from Boston:

     LSTAT <= 14.98
     |   RM <= 6.54
     |   |   DIS <= 1.6102
     |   |   |   DIS <= 1.358: high (4.0/1.0)
     |   |   |   DIS > 1.358
     |   |   |   |   LSTAT <= 12.67: low (2.0)
     |   |   |   |   LSTAT > 12.67: medlow (2.0)
     |   |   DIS > 1.6102
     |   |   |   TAX <= 222
     |   |   |   |   CRIM <= 0.06888: medhigh (3.0)
     |   |   |   |   CRIM > 0.06888: medlow (4.0)
     |   |   |   TAX > 222: medlow (199.0/9.0)
     |   RM > 6.54
     |   |   RM <= 7.42
     |   |   |   DIS <= 1.8773: high (4.0/1.0)
     |   |   |   DIS > 1.8773
     |   |   |   |   PTRATIO <= 19.2
     |   |   |   |   |   RM <= 7.007
     |   |   |   |   |   |   LSTAT <= 5.39
     |   |   |   |   |   |   |   INDUS <= 6.41: medhigh (25.0/1.0)
     |   |   |   |   |   |   |   INDUS > 6.41: medlow (2.0)
     |   |   |   |   |   |   LSTAT > 5.39
     |   |   |   |   |   |   |   DIS <= 3.9454
     |   |   |   |   |   |   |   |   RM <= 6.861
     |   |   |   |   |   |   |   |   |   INDUS <= 7.87: medhigh (9.0)
     |   |   |   |   |   |   |   |   |   INDUS > 7.87: medlow (3.0/1.0)
     |   |   |   |   |   |   |   |   RM > 6.861: medlow (3.0)
     |   |   |   |   |   |   |   DIS > 3.9454: medlow (14.0/1.0)
     |   |   |   |   |   RM > 7.007: medhigh (29.0)
     |   |   |   |   PTRATIO > 19.2: medlow (11.0/1.0)
     |   |   RM > 7.42
     |   |   |   PTRATIO <= 17.9: high (25.0/1.0)
     |   |   |   PTRATIO > 17.9
     |   |   |   |   AGE <= 43.7: high (2.0)
     |   |   |   |   AGE > 43.7: medhigh (3.0/1.0)
     LSTAT > 14.98
     |   CRIM <= 0.63796
     |   |   INDUS <= 25.65
     |   |   |   DIS <= 1.7984: low (5.0/1.0)
     |   |   |   DIS > 1.7984: medlow (37.0/2.0)
     |   |   INDUS > 25.65: low (4.0)
     |   CRIM > 0.63796
     |   |   RAD <= 4: low (13.0)
     |   |   RAD > 4
     |   |   |   NOX <= 0.655
     |   |   |   |   AGE <= 97.5
     |   |   |   |   |   DIS <= 2.2222: low (8.0)
     |   |   |   |   |   DIS > 2.2222: medlow (6.0/1.0)
     |   |   |   |   AGE > 97.5: medlow (5.0)
     |   |   |   NOX > 0.655
     |   |   |   |   CHAS = 0: low (80.0/8.0)
     |   |   |   |   CHAS = 1
     |   |   |   |   |   DIS <= 1.7455: low (2.0)
     |   |   |   |   |   DIS > 1.7455: medlow (2.0)

Treatment learners generate more succinct output. First, it tells us the
*baseline distribution* of the classes:

                 low:~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  [   133 - 29%] 
              medlow:~~~~~~~~~~~~~~~~~~~~~~~~~~~~~   [   131 - 29%] 
             medhigh:~~~~~~~~~~~~~~~~~~~~~           [    97 - 21%] 
                high:~~~~~~~~~~~~~~~~~~~~~           [    94 - 21%]

Next, it tells us the best *treatment*; i.e. some constraint which when
applied to the dataset selects examples with a better distribution:

     Treatment:[PTRATIO=[12.6..16)
                RM=[6.7..9.78)]

It then shows a prediction of what happens when this constraint is
applied to the data:

                low:                                [     0 -  0%]
             medlow:                                [     0 -  0%]
            medhigh:                                [     1 -  3%]
               high:~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  [    38 - 97%]

In this case, the learner is saying that if we focus only one houses
with 7 to 9 rooms in suburbs where the parent teacher ration between
12.6 to 16, then we we only find good houses.

Note that the treatment is much smaller than the classifier. One reason to use
    treatment learning is that it usually generates succinct theories
    that are easy to read and understand.

### Key Concepts


_Lift:_
Treatment learners assess their theories by comparing a weighted sum of
the classes in the baseline to the a weighted sum of the classes in the
prediction. The sum is normalized so the baseline distribution is said
to have a lift of 1. FYI, the above predicted distribution has a
lift of 2.34.

Note that different treatment learners call lift by a variety of
names; e.g. worth, etc. Whatever- its all really lift.

_Best Support:_
Ideally, treatments have large lift and this can be achieved by making
the treatment more specific; i.e. adding in more conjunctions.

However, the larger the conjunction, the less likely that any particular
example in the current data set will satisfy the treatment. That is, the
*higher* the lift, the *less* evidence will be available that that
treatment actually achieves that lift. This threatens the external
validity of the learnt treatment.

In order to remove this over-fitting bias, treatment learners use *best
support*; i.e. the percentage of the best classes seen in the proposed
treatment. Treatments are rejected that do not satisfy the *minimal best
support*.

_The Small Treatment Effect:_
Minimal best support is also known as **BestClass**. Increasing
**BestClass** increases the external validity but tend also to reduce
the lift (since the larger the treatment, the less likely a member of
the best class will fall into the treatment).

A consequence of using **BestClass**/minimal best support is that
treatments are very small (typically, conjunctions of size four or
less). Small treatments are useful when (e.g.) explaining a theory to a
human or (e.g.) designing some device that will use the learnt theory.
In both cases, the *fewer* the attributes in the learnt theory, the
*less* we need to (e.g.) understand or (e.g.) add sensors to a
house-hunting robot or (e.g.) write queries into some database.

### Insider the TAR3 Treatment Learner


Definitions

+ Classes have weights
+ Baseline best = number of highest weighted instances
+ Yield = sum of class frequency*weight
+ Baseline = yield of all data
+ Treatment = RX = {Attribute=value}+
+ Selected = subset of data consistent with RX
+ Lift = yield (selected) / baseline
     -   Lift over 1 means _better_.
     -   Lift below 1 means _worse_.
+ Rx learning= seek smallest treatment
     -   With the most lift (the controller: what to do)
     -   With the least lift (the monitor: what we most fear)
     -   With enough support (minimum best support e.g. 20% * baseline best)

Sort the ranges as follows:

+ Randomly select N- the size of the treatment. Pick this at random from 1
to some user specified parameter **MaxSize**.
+ Randomly select N promising ranges as follows. First calculate the lift
of each individual attribute value then search through combinations of
the highly scoring values. Usually, there are some outstandingly high
scoring values. For example, the red bars below show the lift scores for
16 different attribute values score in the iris domain (don't worry
about the negative numbers, there just artifacts of quirks of the lift
calculation).

![image](http://unbox.org/open/trunk/472/14/spring/doc/img/iris.png)

Note that of the 16 values, two score outstandingly high (9 and 10).
That is, in this domain, treatments can be very small since there exist
a very small number of very powerful _lifting_ values.

Try combining the promising treatments as follows:

-   Convert the individual value scores are converted into a cumulative
    probability distribution (see the green line, above).
-   Select values at random from this distribution (so low-scoring
    ranges have a very low probability of being selected).
-   To build one treatment, repeat the above N times (where N is picked
    at random from 1 to some **MaxSize** parameter supplied by the
    user).
-   To score one treatment, run over the data and extract all the
    examples that don't contradict the treatment. The weighted class
    distribution of those extracted examples is then calculated to find
    the lift for that treatment. Ignore the treatment if it has less
    that the minimum best support.
-   Build **RandomTrials** number of treatments. Score them. Delete all
    but the best **MaxNumber** of them.
-   Repeat the above till after a **FutileTrials** number of times, we
    don't see any new treatments in the top **MaxNumber** of treatments.

### And the results?

Lots of tiny models:

![image](http://unbox.org/open/trunk/472/14/spring/doc/img/tar2.png)
