Introduction to Machine Learning

This class has a website [3]. Everything is there.
Overview of most significant machine learning techniques.
The textbook has everything. Read it!
Requirements: Algorithms, Math, Programming.
Goal: Understand how all the popular machine learning algorithms work. Be able to implement them. Understand the tradeoffs among them.

2 Outline

Why Machine Learning?
What is a well-defined learning problem?
An example: learning to play checkers
What questions should we ask about Machine Learning?

3 Why Machine Learning

Machine learning techniques have reached maturity (but, still limited).
Growing flood of electronic data: Internet and private databases.
Computational power is available.
Budding industry.

Three niches for machine learning:

Data mining : using historical data to improve decisions.
- Retailers: wal-mart to Amazon.
- The government.
- Bioinformatics: a large problem domain.
medical records → medical knowledge.
Software applications we can't program by hand:
- autonomous driving,
- speech recognition,
- self-customizing programs,
- robots,
- browsers that learn user interests.

3.1 Bioinformatics Example

A Gene-Expression Signature as a Predictor of Survival in Breast Cancer [4], The New England Journal of Medicine, 347 (25), 2002.

4 Relevant Disciplines

Artificial intelligence
Bayesian methods
Computational complexity theory
Control theory
Information theory
Philosophy
Psychology and neurobiology
Statistics
...

5 What is the Learning Problem?

Learning means improving with experience at some task.
Specifically, we want to improve over task $T$, with respect to performance measure $P$, based on experience $E$.
A computer program is said to learn from experience $E$ with respect to some class of tasks $T$ and performance measure $P$, if its performance at tasks in $T$, as measured by $P$, improves with experience $E$.

5.1 Learning to Play Checkers

$T$: Play checkers.
$P$: Percentage of games won in world tournament.
$E$: opportunity to play against self.

We must ask:

What experience?
What exactly should be learned?
How shall it be represented?
What specific algorithm to learn it?

5.2 Learning Handwriting Recognition

$T$: recognize and classify handwritten words within images.
$P$: percent of words correctly classified.
$E$: a database of handwritten words with their classification.

We must ask the same questions:

What experience?
What exactly should be learned?
How shall it be represented?
What specific algorithm to learn it?

6 Choosing the Training Experience

Direct information (or training examples) consists of individual checkerboard states and their correct moves.
Indirect information consist of a move sequences and the final outcomes (win or lose).
When using indirect information we are faced with the credit assignment problem: determining how much credit each move should receive for the final outcome.
Decide whether the learner chooses its own examples or they are presented to it by a teacher.
Make the distribution of training examples representative of those used by the performance metric.
In the checker's example we could choose $E$ to be games played against itself.

7 Choose the Target Function

The obvious thing to learn seems to be a function that tells us what move M to take in each board B.
ChooseMove: B → M.
This will turn out to be very hard to learn. An easier function is one that assigns a score (value) to every board state.
$V: B \rightarrow \mathbb{R}$

7.1 Possible Definition for Target Function

if $b$ is a final board state that is won, then $V(b) = 100$
if $b$ is a final board state that is lost, then $V(b) = -100$
if $b$ is a final board state that is drawn, then $V(b) = 0$
if $b$ is a not a final state in the game, then $V(b) = V(b')$, where $b'$ is the best final board state that can be achieved starting from $b$ and playing optimally until the end of the game.

This gives correct values, but its nonoperational because of case 4. That is, it is not efficiently computable.
In general, it is very difficult to perfectly learn $V$. We will approximate it.

8 Choose Representation for Target Function

a table?
a collection of rules?
a neural network ?
a polynomial function of board features?

8.1 A Representation for the Target Function

Our approximation of $V$ is given by $\hat{V}$: \[ \hat{V}(b) = w_{0} + w_{1}\cdot bp(b) + w_{2}\cdot rp(b) + w_{3}\cdot bk(b) + w_{4}\cdot rk(b) + w_{5}\cdot bt(b) + w_{6}\cdot rt(b) \]
$bp(b)$: number of black pieces on board $b$.
$rp(b)$: number of red pieces on $b$.
$bk(b)$: number of black kings on $b$.
$rk(b)$: number of red kings on $b$.
$bt(b)$: number of red pieces threatened by black (i.e., which can be taken on black's next turn).
$rt(b)$: number of black pieces threatened by red.

9 Training Examples

$V(b)$: the true target function
$\hat{V}(b)$ : the learned function
Calculating $\hat{V}$ will require training examples. An example looks like: \[ \langle \langle bp = 2, rp = 4, bk = 1, rk=0, bt=0, rt=0\rangle, +100\rangle \]
$V_{train}(b)$ is the training value for $b$, for example: \[ V_{train}(\langle bp = 2, rp = 4, bk = 1, rk=0, bt=0, rt=0\rangle) = 100 \]
Its easy to assign values to final board states. For intermediate boards we can use \[ V_{train}(b) \leftarrow \hat{V}(Successor(b)) \]
$Successor(b)$ gives the next board state following $b$ for which it is again the program's turn to move.

10 Choose Weight Tuning Rule

We need to update the weights in $\hat{V}$ so that it matches the examples.
One algorithm is the Least Mean Squares rule:
LMS Weight update rule:

Select a training example $b$ at random
Compute $error(b)$: \[error(b) = V_{train}(b) - \hat{V}(b)\]
For each board feature $f_{i}$, update weight $w_{i}$: \[w_{i} \leftarrow w_{i} + c \cdot f_{i} \cdot error(b) \] where, $c$ is some small constant, say 0.1, to moderate the rate of learning.
Goto 1

11 Final Design

The performance system uses the learned function and plays a game.
The critic takes a trace of this game and produces a series of training examples. In our case, $V_{train}$.
The generalizer takes the training examples and produces a new estimate of the target function. LMS in our example.
The experiment generator takes as input the current learned function and outputs a new problem. In our example we always output the same problem: the start board state.

12 Design Choices

The steps involved in designing a learning program are:

Determine the type of training experience: games against experts, table of correct moves, games against self, etc.
Determine target function ($V$): Board → move, Board → value, etc.
Determine representation of learned function ($\hat{V}$): polynomial, artificial neural network, linear function of six features, etc.
Determine learning algorithm: linear programming, gradient descent, etc.

13 Some Issues in Machine Learning

What algorithms can approximate functions well (and when)?
How does number of training examples influence accuracy?
How does complexity of hypothesis representation impact it?
How does noisy data influence accuracy?
What are the theoretical limits of learnability?
How can prior knowledge of learner help?
What clues can we get from biological learning systems?
How can systems alter their own representations?