Intelligent Systems Lecture Notes

11 November 2011 • Advanced Learning

Outline

Neural networks.
Ensemble learning.
Case-based learning.

Neural Networks

Inspired by biology.
Artificial neurons, or units, have inputs and an output.
The unit output is a parameterized function of the inputs.
Learning occurs by adjusting parameters to fit the data.
Neural networks can approximate any function.

Why Neural Networks?

Modeling biological systems.
- Neurological systems are complex.
Cargo-cult science.
- The bad old AI.
Biologically-inspired systems.
A simple but effective learning model.
- The Japanese Fifth Generation Project.

Feed-Forward Neural Networks

A feed-forward neural network is a directed acyclic graph.
Each hidden unit is a squashed linear function.

Neural-Network Example.

neural-network example

pval(e, Likes) =

f(w₀ + w₁val(e, H1) + w₂val(e, H2))

Neural-Network Example..

val(e, H1) =
	f(w₃ + w₄val(e, Culture) + w₅val(e, Fly)
	+ w₆val(e, Hot) + w₇val(e, Music)
	+ w₈val(e, Nature))

val(e, H2) =
	f(w₉ + w₁₀val(e, Culture) + w₁₁val(e, Fly)
	+ w₁₂val(e, Hot) + w₁₃val(e, Music)
	+ w₁₄val(e, Nature))

Neural-Network Example...

Feature domains are real numbers.
The weights w₀, …, w₁₄ are real numbers.
Features H1 and H2 are hidden-unit values.
The hypothesis space is a 15-dimensional real space.
Each point in the hypothesis space is a weight vector.

Prediction Error

Given a weight vector w₀, …, w_k = w and example set E, the sum-of-squares error is
Error_E(w) = \(\sum\)_{e \(\in\) E}(p_e^w - o_e)²
- p_e^w is the predicted output.
- o_e is the observed output for example e.
Learn weights to minimize the error.

Back Propagation

Back-propagation learning uses gradient descent to find the weight vector.
For each example in the training set:
1. Work the example forward through the neural network.
2. Compute the error from the predicted and actual values.
3. Work the error back through the network, proportionally adjusting weights.
Repeat until satisfied.

Gradient Descent

At each iteration, update the parameter w_i
w_i \(\leftarrow\) w_i - \(\eta\) \(\partial\)error(w_i)/\(\partial\)w_i
Partial derivatives can be computed
- Numerically: for small \(\Delta\)
  (error(w_i + \(\Delta\)) - error(w_i))/\(\Delta\)
- Analytically:
  f '(x) = f(x)(1 - f(x)) + chain rule

Representation Problems

logic representations

w₀		w₁		w₂		Logic
-15		10		10		and
-5		10		10		or
5		-10		-10		nor

Output is f(w₀ + w₁\(I\)₁ + w₂\(I\)₂)
A single unit can't represent xor.

Bias

A neural network can recognize “at least two inputs are true”.
(w₀, w₁, \(\ldots\), w_k) = (-15, 10, \(\ldots\), 10)
This is a large decision tree.
Consider the conditional “if c then a else b”.
- A simple decision tree.
- Neural network represents (a \(\wedge\) b) \(\vee\) (\(\neg\)c \(\wedge\) b).

Logic

Attach meaning to the input and output units.
No prior meaning associated with hidden units.
The hidden units represent something that's learned.

E Pluribus Unum

combining linear classifiers

Ensemble Learning

Ensemble Learning takes a set of base-level algorithms for learning and combines them into a new learner.
As usual, balancing complimentary strengths and weaknesses is a good reason for combining algorithms.
In addition, approximations improve with a diversity of opinions.
- Find trends, gauge consensus, smooth results.

Diversity Training

A set of identical base-level algorithms can be trained on different subsets of the training data.
- Usually randomly generated subsets.
The resulting predictions could be averaged or otherwise smoothed if numeric.
- Or subject to a majority if classifications.
Different base-level algorithms could be serially cascaded.

Stability

A stable learning algorithm produces the same results with different subsets of the training data.
- Decision trees and neural networks are unstable.
- Linear classifiers are stable.
Stable learning algorithms are less helpful than unstable algorithms in an ensemble.
- Stability dampens diversity.

Bagging

Bootstrap aggregating (bagging) trains an ensemble of identical algorithms.
Each algorithm is trained on a subset that's n% of the training set.
- Each subset is drawn from the full training set.
The final prediction is some smoothing of the constituent predictions.
- Usually the majority (the mode).

Lean on Failure

boosting illustrated

Weighted linear combination of predictions with w_i size proportional to weight.

Boosting

Boosting feeds forward the errors from one base-level algorithms into the training of the next.
The example sets are weighted, with troublesome examples in the last training session weighed more heavily in the next.
- The next training session contains the examples incorrectly predicted in the previous training session.
Variations on boosting are many.

More Diversity

There are may other sources of diversity.
Each base-level algorithm trains on a subset of the input feature set.
Adding randomness is always a good way to mix things up.
- Perturb neural network weights, or even the input feature values.

Using Examples

Learning algorithms are pain.
- You have to pick the right one.
- You have to train it.
- You have to keep watch over it.
- The path to the prediction is often incomprehensible.
Why not chuck all that and work from the training examples directly?

Reasoning From Examples

Case-Based Reasoning reasons directly from examples.
- Examples are represented in a structure-preserving way.
Given a new input set,
- Find the closest matching example,
- predict from the matching examples.
New predictions are added to the collection of prior predictions.
- That's the learning part.

Reasoning Illustrated

cased-based reasoning

Matching

Matches can be exact or approximate.
Exact matches provide the best predictions.
- But there may often be no exact matches.
- Most caching schemes are exact case-based reasoners.
Approximate matches complement exact matches: inexact predictors, and lots of them.

Predicting

Given a set of approximate matches:
- Statistically reduce the predictions.
- Select a best of the inexact prediction.
- These choices may be conditioned on set size.
The opposite problem: no matches.
- Give up, or fall back to other learning algorithms.

k-Nearest Neighbors

Use a distance metric between examples.
Given a new input set, find the k nearest neighbors.
Predict classification by using the mode, median, or interpolating between the neighbors.
Often want k > 1 because there can be errors in the case base.

Euclidean Distance

Define a metric for each dimension (convert the values to a numerical scale).
The Euclidean distance between examples x and y is:
d(x, y) = (\(\sum\)_A w_A(x_A - y_A)²)^0.5
- x_A is the value for feature A from example x.
- w_A is a non-negative real-valued weight specifying the relative weight of feature A.

kd-Tree

A k-way decision tree with examples stored at the leaves.
- k = 4, quad trees; k = 8, oct trees.
Build a balanced tree so searches take O(log n) work.
Leaves may match examples imperfectly.
Examples missing on one attribute can be found in O(log² n) time.

Summary

Neural networks are simple, versatile learning algorithms.
When life gives you a bunch of basic learning algorithms, ensemble them.
- Create and exploit diversity to improve results.
Eliminate the middle representations.
- Reason about features by directly contemplating related examples from the training set.

References

Learning in IS (Chapter 16) in Intelligent Systems by Robert Schalkoff, Jones and Bartlett, 2011.
Knowledge in Learning (Chapter 19) in Artifical Intelligence, third edition, by Stuart Russell and Peter Norvig, Prentice Hall, 2010.
Cargo Cult Science by Richard Feynman, Engineering and Science, June, 1974.

This page last modified on 2011 November 9.