ch1

Machine Learning

Chapter 1: Introduction

Ever since computers were invented, we have wondered whether they might be made to learn. If we could understand how to program them to learn — to improve automatically with experience — the impact would be dramatic. Imagine computers learning from medical records which treatments are most effective for new diseases, houses learning from experience to optimize energy costs based on the particular usage patterns of their occupants, or personal software assistants learning the evolving interests of their users in order to highlight especially relevant stories from the online morning newspaper. A successful understanding of how to make computers learn would open up many new uses of computers and new levels of competence and customization. And a detailed understanding of information-processing algorithms for machine learning might lead to a better understanding of human learning abilities (and disabilities) as well.

We do not yet know how to make computers learn nearly as well as people learn. However, algorithms have been invented that are effective for certain types of learning tasks, and a theoretical understanding of learning is beginning to emerge. Many practical computer programs have been developed to exhibit useful types of learning, and significant commercial applications have begun to appear. For problems such as speech recognition, algorithms based on machine learning outperform all other approaches that have been attempted to date. In the field known as data mining, machine learning algorithms are being used routinely to discover valuable knowledge from large commercial databases containing equipment maintenance records, loan applications, financial transactions, medical records, and the like. As our understanding of computers continues to mature, it seems inevitable that machine learning will play an increasingly central role in computer science and computer technology.

A few specific achievements provide a glimpse of the state of the art: programs have been developed that successfully learn to recognize spoken words (Waibel 1989; Lee 1989), predict recovery rates of pneumonia patients (Cooper et al. 1997), detect fraudulent use of credit cards, drive autonomous vehicles on public highways (Pomerleau 1989), and play games such as backgammon at levels approaching the performance of human world champions (Tesauro 1992, 1995). Theoretical results have been developed that characterize the fundamental relationship among the number of training examples observed, the number of hypotheses under consideration, and the expected error in learned hypotheses.

---

1.1 Well-Posed Learning Problems

Let us begin our study of machine learning by considering a few learning tasks. For the purposes of this book we will define learning broadly, to include any computer program that improves its performance at some task through experience. Put more precisely,

Definition. 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$.

For example, a computer program that learns to play checkers might improve its performance as measured by its ability to win at the class of tasks involving playing checkers games, through experience obtained by playing games against itself. In general, to have a well-defined learning problem, we must identify these three features: the class of tasks, the measure of performance to be improved, and the source of experience.

Examples of Well-Posed Learning Problems

Problem	Task $T$	Performance Measure $P$	Training Experience $E$
Checkers	Playing checkers	Percent of games won against opponents	Playing practice games against itself
Handwriting Recognition	Recognizing and classifying handwritten words within images	Percent of words correctly classified	A database of handwritten words with given classifications
Robot Driving	Driving on public four-lane highways using vision sensors	Average distance traveled before an error (as judged by human overseer)	A sequence of images and steering commands recorded while observing a human driver

Our definition of learning is broad enough to include most tasks that we would conventionally call “learning” tasks. It is also broad enough to encompass computer programs that improve from experience in quite straightforward ways. For example, a database system that allows users to update data entries would fit our definition: it improves its performance at answering database queries, based on the experience gained from database updates.

---

1.2 Designing a Learning System

In order to illustrate some of the basic design issues and approaches to machine learning, let us consider designing a program to learn to play checkers, with the goal of entering it in the world checkers tournament. We adopt the obvious performance measure: the percent of games it wins in this world tournament.

1.2.1 Choosing the Training Experience

The first design choice we face is to choose the type of training experience from which our system will learn. Three key attributes of training experience are:

1. Direct vs. indirect feedback. Does the training experience provide direct or indirect feedback regarding the choices made by the performance system?
2. Degree of learner control. Does the learner control the sequence of training examples, or are they chosen by a teacher?
3. Distribution of examples. How well does the training distribution represent the distribution over which the final system performance $P$ will be measured?

To proceed with our design, let us decide that our system will train by playing games against itself.

1.2.2 Choosing the Target Function

The next design choice is to determine exactly what type of knowledge will be learned. Let us define the target function as an evaluation function that assigns a numerical score to any given board state:

$V:B\to \mathbb{R}$

We define $V(b)$ for any board state $b\in B$ as:

$$V(b)=\{\begin{array}{ll}+100,& \text{if }b\text{ is a final board state that is won}\\ -100,& \text{if }b\text{ is a final board state that is lost}\\ 0,& \text{if }b\text{ is a final board state that is drawn}\\ V(b^{\prime }),& \text{if }b\text{ is not a final state, where }{b}^{\prime }\text{ is the best final board state achievable from }b\end{array}$$

While this recursive definition is nonoperational (not efficiently computable), the goal of learning is to discover an operational description of $V$. We use $\hat{V}$ to denote the function actually learned by our program, and refer to this process as function approximation.

1.2.3 Choosing a Representation for the Target Function

We choose to represent $\hat{V}$ as a linear combination of the following board features:

• $x_1$: the number of black pieces on the board
• $x_2$: the number of red pieces on the board
• $x_3$: the number of black kings on the board
• $x_4$: the number of red kings on the board
• $x_5$: the number of black pieces threatened by red
• $x_6$: the number of red pieces threatened by black

Thus, our learning program represents $\hat{V}(b)$ as:

$\hat{V}(b)=w_0+w_1{x}_1+w_2{x}_2+w_3{x}_3+w_4{x}_4+w_5{x}_5+w_6{x}_6$

where $w_0,w_1,\dots ,w_6$ are numerical coefficients (weights) to be chosen by the learning algorithm.

1.2.4 Choosing a Function Approximation Algorithm

We require training examples of the form $⟨b,V_{train}(b)⟩$. For example:

$⟨x_1=3,x_2=0,x_3=1,x_4=0,x_5=0,x_6=0,+100⟩$

Estimating Training Values. Because the only direct training information is whether the game was eventually won or lost, we estimate training values for intermediate states using:

V_{train}(b) \leftarrow \hat{V}(\mathrm{Successor}(b)) \tag{1.1}

Defining the Best Fit. We define the best hypothesis as the one that minimizes the squared error:

$E\equiv {\sum }_{⟨b,V_{train}(b)⟩\in \text{training examples}}{\left(V_{train}(b)-\hat{V}(b)\right)}^2$

LMS Weight Update Rule. For each training example $⟨b,V_{train}(b)⟩$:

1. Use the current weights to calculate $\hat{V}(b)$.
2. For each weight $w_i$, update it as:

$w_i\leftarrow w_i+\eta \left(V_{train}(b)-\hat{V}(b)\right)x_i$

where $\eta$ is a small constant (e.g., $0.1$) that moderates the size of the weight update.

1.2.5 The Final Design

The final design is naturally described by four distinct program modules (shown in Figure 1.1):

Module	Role
Performance System	Solves the performance task using the learned $\hat{V}$
Critic	Takes the game trace and produces training examples (Equation 1.1)
Generalizer	Takes training examples and produces a hypothesis $\hat{V}$ (LMS algorithm)
Experiment Generator	Takes the current hypothesis and outputs a new initial board state

---

1.3 Perspectives and Issues in Machine Learning

One useful perspective on machine learning is that it involves searching a very large space of possible hypotheses to determine one that best fits the observed data and any prior knowledge held by the learner. Many chapters in this book present algorithms that search a hypothesis space defined by some underlying representation (e.g., linear functions, logical descriptions, decision trees, artificial neural networks).

1.3.1 Issues in Machine Learning

Key questions in the field include:

• What algorithms exist for learning general target functions from specific training examples? In what settings will particular algorithms converge to the desired function, given sufficient training data?
• How much training data is sufficient? What general bounds relate the confidence in learned hypotheses to the amount of training experience and the character of the learner’s hypothesis space?
• When and how can prior knowledge held by the learner guide the process of generalizing from examples?
• What is the best strategy for choosing a useful next training experience?
• What is the best way to reduce the learning task to one or more function approximation problems?
• How can the learner automatically alter its representation to improve its ability to represent and learn the target function?

---

1.4 How to Read This Book

This book contains an introduction to the primary algorithms and approaches to machine learning, theoretical results on the feasibility of various learning tasks, and examples of practical applications. The chapters are:

• Chapter 2: Concept learning and the general-to-specific ordering
• Chapter 3: Decision tree learning and overfitting
• Chapter 4: Artificial neural networks and BACKPROPAGATION
• Chapter 5: Statistical concepts and hypothesis evaluation
• Chapter 6: Bayesian learning methods
• Chapter 7: Computational learning theory (PAC model)
• Chapter 8: Instance-based learning (nearest neighbor, case-based reasoning)
• Chapter 9: Genetic algorithms and genetic programming
• Chapter 10: Rule learning and Inductive Logic Programming
• Chapter 11: Explanation-based learning
• Chapter 12: Combining prior knowledge with training data
• Chapter 13: Reinforcement learning

---

1.5 Summary

• Machine learning algorithms have proven valuable in data mining, poorly understood domains, and dynamically changing environments.
• Machine learning draws from artificial intelligence, probability and statistics, computational complexity, information theory, psychology, neurobiology, control theory, and philosophy.
• A well-defined learning problem requires a well-specified task, performance metric, and source of training experience.
• Designing a learning system involves choosing: the type of training experience, the target function, its representation, and the learning algorithm.
• Learning involves search through a space of possible hypotheses.

---

Exercises and Detailed Solutions

Exercise 1.1

Problem. Give three computer applications for which machine learning approaches seem appropriate and three for which they seem inappropriate. Pick applications that are not already mentioned in this chapter, and include a one-sentence justification for each.

Solution

Applications Appropriate for Machine Learning

1. Email spam filtering.
Justification: Spam patterns change constantly as spammers adapt their techniques, so a hand-crafted rule set would be quickly outdated; a learned classifier can adapt automatically to new spam signatures by training on continuously updated user-labeled email.

2. Stock market price prediction.
Justification: Financial markets are influenced by vast, non-linear interactions among many variables (news, interest rates, sentiment), so a learned model can detect subtle statistical patterns that are too complex to encode manually.

3. Music recommendation systems.
Justification: User musical tastes are highly personalized and evolve over time, so a collaborative-filtering system that learns from each user’s listening history can produce far more relevant suggestions than a static, hand-engineered recommendation rule.

Applications Inappropriate for Machine Learning

1. Computing the factorial of an integer.
Justification: The function $n!={\prod }_{i=1}^{n}i$ has a precise closed-form mathematical definition, and a deterministic loop computes it exactly in $O(n)$ time with no need for data-driven approximation.

2. Verifying that a sorted array is in ascending order.
Justification: This task has a deterministic, provably correct algorithm (a single linear pass), and learning from examples would only add uncertainty and overhead without any benefit.

3. Computing the SHA-256 hash of a file.
Justification: Cryptographic hashes are designed to be deterministic and pseudo-random; there is no learnable pattern between the input file and the output digest, and any apparent regularity would signal a serious cryptographic weakness.

---

Exercise 1.2

Problem. Pick some learning task not mentioned in this chapter. Describe it informally in a paragraph in English. Now describe it by stating as precisely as possible the task, performance measure, and training experience. Finally, propose a target function to be learned and a target representation. Discuss the main tradeoffs you considered in formulating this learning task.

Solution

Informal Description

Imagine a smart keyboard on a mobile phone that suggests the next word a user is about to type as they compose a text message. As the user types, the keyboard displays a small set of candidate completions (e.g., “the,” “they,” “there”) and inserts the chosen word when the user taps one. Over time, the keyboard should learn the user’s personal vocabulary, frequently used phrases, and stylistic preferences (formal vs. casual, emoji usage, etc.) so that its top-3 suggestions contain the intended word more often, requiring fewer taps per character typed.

Formal Specification

Element	Specification
Task $T$	Predict the next word given a sequence of preceding words typed by the user.
Performance measure $P$	(i) Top-$k$ accuracy: fraction of times the true next word appears in the top-$k$ suggestions ($k=1,3$); (ii) average number of keystrokes saved per character typed, compared to a non-learning baseline.
Training experience $E$	A continuously growing log of the user’s own past messages, each consisting of an ordered sequence of words, plus an optional in-app signal indicating which suggestion was selected (positive) or ignored (negative).

Target Function

Let $\mathbf{w}=(w_1,w_2,\dots ,w_{n-1})$ be the sequence of $n-1$ already-typed words (the “context”) and let $c$ be a candidate next word from a fixed vocabulary $V$. Define:

$f:V^{\ast }\times V\to \mathbb{R}$

The function $f(\mathbf{w},c)$ should output a real-valued score indicating how likely $c$ is to be the next word. At prediction time, the system recommends the $k$ candidates with the highest $f$-values.

Target Representation

A natural representation combines two complementary signals additively:

$\hat{f}(\mathbf{w},c)=\alpha \cdot {\hat{f}}_{\text{ngram}}(\mathbf{w},c)+\beta \cdot {\hat{f}}_{\text{personal}}(\mathbf{w},c)$

where:

• ${\hat{f}}_{\text{ngram}}(\mathbf{w},c)$ is a smoothed $n$-gram language model (e.g., a Katz back-off trigram) trained on a large public corpus.
• ${\hat{f}}_{\text{personal}}(\mathbf{w},c)$ is a personalized model (e.g., a logistic regression or small feed-forward neural network) trained on the user’s own message history, using features such as bag-of-words context embeddings, time-of-day, and recent-word history.
• $\alpha$ and $\beta$ are non-negative mixture weights, possibly learned by a bandit algorithm from the user’s in-app feedback.

Tradeoffs Considered

1. Privacy vs. personalization. Training on-device avoids sending the user’s private messages to a server, but limits the amount of training data and the size of model that can be deployed.
2. Cold start. A brand-new user has no personal history, so the model must fall back on the public $n$-gram component; therefore the mixture weight $\beta$ should initially be near zero and grow as personal data accumulates.
3. Vocabulary size vs. memory. A larger vocabulary improves coverage of rare words but inflates the model size and slows prediction on a phone. We restrict the personal vocabulary to the top-$N$ words the user has actually used.
4. Model complexity vs. inference latency. A neural language model may give slightly better accuracy, but a logistic-regression $n$-gram hybrid runs in microseconds and consumes less battery, which matters more for a keystroke-level prediction task.
5. Online vs. batch learning. Because the data distribution drifts with the user’s evolving topics, we prefer online stochastic gradient updates to nightly batch retraining.

---

Exercise 1.3

Problem. Prove that the LMS weight update rule described in this chapter performs a gradient descent to minimize the squared error. In particular, define the squared error $E$ as in the text. Now calculate the derivative of $E$ with respect to the weight $w_i$, assuming that $\hat{V}(b)$ is a linear function as defined in the text. Gradient descent is achieved by updating each weight in proportion to $-\frac{\partial E}{\partial w_i}$. Therefore, you must show that the LMS training rule alters weights in this proportion for each training example it encounters.

Solution

Step 1. State the squared error.
As defined in the chapter, the total squared error over the training set is:

$E\equiv {\sum }_{⟨b,V_{train}(b)⟩\in \text{training examples}}{\left(V_{train}(b)-\hat{V}(b)\right)}^2$

Step 2. State the linear model for $\hat{V}(b)$.
The current hypothesis expresses the estimated board value as a linear combination of board features:

$\hat{V}(b)=w_0+w_1{x}_1+w_2{x}_2+w_3{x}_3+w_4{x}_4+w_5{x}_5+w_6{x}_6$

Equivalently, introducing a constant feature $x_0\equiv 1$, we may write:

$\hat{V}(b)={\sum }_{i=0}^6{w}_i{x}_i$

Step 3. Define the per-example error.
For clarity, denote a single training example as $d=⟨b,V_{train}(b)⟩$ and let $E_d$ be its contribution to the total error:

$E_d\equiv {\left(V_{train}(b)-\hat{V}(b)\right)}^2$

Then the total error decomposes as $E={\sum }_d{E}_d$, and because the derivative is linear, it suffices to show the result for one example.

Step 4. Compute $\frac{\partial E_d}{\partial w_i}$.
Apply the chain rule. Let $y\equiv V_{train}(b)-\hat{V}(b)$, so that $E_d=y^2$. Then:

$\frac{\partial E_d}{\partial w_i}=\frac{\partial (y^2)}{\partial y}\cdot \frac{\partial y}{\partial w_i}$

Computing each factor:

$\frac{\partial (y^2)}{\partial y}=2y=2\left(V_{train}(b)-\hat{V}(b)\right)$

$\frac{\partial y}{\partial w_i}=\frac{\partial }{\partial w_i}\left(V_{train}(b)-\hat{V}(b)\right)=-\frac{\partial \hat{V}(b)}{\partial w_i}$

Because $\hat{V}(b)={\sum }_{j=0}^6{w}_j{x}_j$ and only the term with $j=i$ contains $w_i$:

$\frac{\partial \hat{V}(b)}{\partial w_i}=x_i$

Therefore:

$\frac{\partial y}{\partial w_i}=-x_i$

Step 5. Combine the factors.
Substituting back:

$\frac{\partial E_d}{\partial w_i}=2\left(V_{train}(b)-\hat{V}(b)\right)\cdot \left(-x_i\right)$

$\boxed{\frac{\partial E_d}{\partial w_i}=-2\left(V_{train}(b)-\hat{V}(b)\right)x_i}$

Step 6. Form the gradient descent update.
Gradient descent updates each weight in the direction opposite to the gradient, scaled by a small learning rate $\eta$:

$w_i\leftarrow w_i-\eta \cdot \frac{\partial E_d}{\partial w_i}$

Substitute the derivative from Step 5:

$w_i\leftarrow w_i-\eta \cdot \left[-2\left(V_{train}(b)-\hat{V}(b)\right)x_i\right]$

$w_i\leftarrow w_i+2\eta \left(V_{train}(b)-\hat{V}(b)\right)x_i$

Step 7. Compare with the LMS rule.
The LMS weight update rule given in the chapter is:

$w_i\leftarrow w_i+\eta \left(V_{train}(b)-\hat{V}(b)\right)x_i$

The two update rules are identical up to a redefinition of the learning rate: the LMS rule is exactly a gradient-descent step if we absorb the constant factor $2$ into $\eta$ (i.e., the LMS learning rate is twice the formal gradient-descent rate). In other words, with effective learning rate ${\eta }_{\text{LMS}}=2{\eta }_{\text{GD}}$:

$w_i\leftarrow w_i-{\eta }_{\text{LMS}}\cdot \frac{1}{2}\cdot \frac{\partial E_d}{\partial w_i}=w_i+{\eta }_{\text{LMS}}\left(V_{train}(b)-\hat{V}(b)\right)x_i$

Step 8. Conclusion.
Therefore, for every training example $⟨b,V_{train}(b)⟩$, the LMS weight update rule alters each weight $w_i$ in direct proportion to $-\frac{\partial E}{\partial w_i}$. This proves that the LMS rule performs stochastic gradient descent on the squared error $E$. $■$

---

Exercise 1.4

Problem. Consider alternative strategies for the Experiment Generator module of Figure 1.2. In particular, consider strategies in which the Experiment Generator suggests new board positions by:

• Generating random legal board positions
• Generating a position by picking a board state from the previous game, then applying one of the moves that was not executed
• A strategy of your own design

Discuss tradeoffs among these strategies. Which do you feel would work best if the number of training examples was held constant, given the performance measure of winning the most games at the world championships?

Solution

Strategy A: Random Legal Board Positions

Description. The Experiment Generator samples board configurations uniformly (or according to some prior) from the set of all legal board states.

Tradeoffs.

• Pros: High diversity, simple to implement, and unbiased with respect to the current hypothesis $\hat{V}$. Useful for exploration because the learner is exposed to board situations that differ widely from those it has already seen.
• Cons: Many randomly generated positions are unrealistic — they would never arise in actual play. The learner therefore wastes training examples on states that contribute little to improving performance against a strong human opponent, who would never produce such positions. The distribution mismatch between training and test is severe.

Strategy B: Off-Policy Move from a Previous Game

Description. The Experiment Generator replays a sequence of moves from a previous game, but at some step chooses a different legal move than the one originally played, producing a new branch from an interesting, realistic position.

Tradeoffs.

• Pros: The starting position is one that arises in real play, so the resulting training examples are drawn from a distribution much closer to the test distribution. It also provides a natural curriculum: the learner revisits realistic positions but explores alternative continuations.
• Cons: The board states are still anchored to games the learner has already played, which biases exploration toward regions of state space the learner is already familiar with — the opposite of the classic exploration/exploitation dilemma. The diversity of training data is therefore lower than in Strategy A.

Strategy C (Original Design): Fixed Initial Position

Description. The Experiment Generator always proposes the same initial board state and lets the program play an entire self-game from it.

Tradeoffs.

• Pros: Maximally simple; the distribution of states is naturally close to the test distribution because the program plays full realistic games.
• Cons: No exploration of the wider state space; the program can become trapped in a narrow line of play it already favors, missing strategies it would never stumble upon.

Strategy D (My Proposal): Uncertainty-Driven Targeted Exploration

Description. Maintain an estimate of the learner’s uncertainty about $\hat{V}(b)$ for each board state $b$ it has visited (e.g., the variance of the residuals $\left(V_{train}(b)-\hat{V}(b)\right)$ over recent visits). With high probability $ϵ$, sample a board state $b$ with the highest uncertainty; with probability $1-ϵ$, sample a board state uniformly at random from a recent game.

Tradeoffs.

• Pros: Combines the realism of Strategy B (anchored to real game lines) with the diversity of Strategy A (explicit exploration of uncertain states). It is, in spirit, an $ϵ$-greedy or UCB-style strategy adapted to the reinforcement-learning setting.
• Cons: More complex to implement; requires keeping a model of uncertainty, which can be expensive. If uncertainty estimates are biased, the strategy can waste effort on states that are uncertain only because the representation cannot express the true value, rather than because of insufficient data.

Comparison Summary

Strategy	Realism	Diversity	Implementation	Coverage of test distribution
A. Random	Low	Very high	Trivial	Poor
B. Off-policy move	High	Moderate	Easy	Good
C. Fixed start	Very high	Low	Trivial	Moderate
D. Uncertainty-driven	High	High (focused)	Moderate	Very good

Recommendation

Strategy D (uncertainty-driven targeted exploration) is most likely to perform best under a fixed training-budget constraint, because it concentrates training examples on the board states where the learner is most likely to be wrong, and it does so within the realistic, on-distribution region of state space. Among the textbook’s three strategies, Strategy B (off-policy move from a previous game) is the best compromise: it maintains the on-distribution property of the original design while injecting useful exploration, and it is simple enough to implement in practice. Strategy A should be used only as a periodic “reset” to inject diversity, not as the primary generator.

---

Exercise 1.5

Problem. Implement an algorithm similar to that discussed for the checkers problem, but use the simpler game of tic-tac-toe. Represent the learned function $\hat{V}$ as a linear combination of board features of your choice. To train your program, play it repeatedly against a second copy of the program that uses a fixed evaluation function you create by hand. Plot the percent of games won by your system, versus the number of training games played.

Solution

Step 1. Set up the game and the two players

We implement a $3\times 3$ tic-tac-toe environment. Each state is a $3\times 3$ matrix of entries in $\{\text{X},\text{O},\text{empty}\}$. The learning player (“the system”) maintains weights $\mathbf{w}=(w_0,w_1,\dots ,w_n)$ and selects moves by maximizing $\hat{V}(s)$ over the successor states $s$ reachable by its legal moves. The fixed opponent (“the teacher”) uses a hand-crafted evaluation function ${\hat{V}}_{\text{fixed}}(s)$.

Step 2. Choose board features for $\hat{V}$

Define the following features $x_i(s)$ for the board state $s$ from the learner’s perspective (X is the system, O is the opponent):

• $x_1(s)$: number of X’s on the board
• $x_2(s)$: number of O’s on the board
• $x_3(s)$: number of rows in which X could still win (i.e., containing only X’s and empties)
• $x_4(s)$: number of rows in which O could still win
• $x_5(s)$: number of X’s that are part of a row of two X’s with the third square empty (i.e., immediate “threats” to be completed)
• $x_6(s)$: number of O’s that are part of a row of two O’s with the third square empty
• $x_7(s)\equiv 1$: a constant bias feature (paired with $w_0$)

The linear value function is:

$\hat{V}(s)=w_0+w_1{x}_1+w_2{x}_2+w_3{x}_3+w_4{x}_4+w_5{x}_5+w_6{x}_6$

Step 3. Design the fixed opponent’s evaluation function

The teacher plays a reasonable game using a hand-crafted function (the system must never see these weights; they are hard-coded):

${\hat{V}}_{\text{fixed}}(s)=3\cdot (\text{my potential winning rows})-3\cdot (\text{opponent’s potential winning rows})+1\cdot (\text{my forks})-1\cdot (\text{opponent’s forks})$

Step 4. Generate training data via self-play

The Critic follows the same rule as in the checkers example:

V_{train}(s) \leftarrow \hat{V}(\mathrm{Successor}(s)) \tag{1.1}

with the terminal values:

$V_{train}(s)=\{\begin{array}{ll}+100,& s\text{ is a win for the learner}\\ -100,& s\text{ is a loss for the learner}\\ 0,& s\text{ is a draw}\end{array}$

After each game, the Critic walks backward through the recorded sequence of learner-turn states $s_1,s_2,\dots ,s_T$ and assigns each $s_t$ the value $V_{train}(s_t)=\hat{V}(s_{t+1})$ for $t<T$, and the terminal value for $s_T$.

Step 5. Update the weights with LMS

For every training example $⟨s,V_{train}(s)⟩$ produced by the Critic, the Generalizer applies the LMS update to every weight $w_i$:

$w_i\leftarrow w_i+\eta \left(V_{train}(s)-\hat{V}(s)\right)x_i(s)$

with learning rate $\eta =0.1$.

Step 6. Pseudocode

Initialize w_0, w_1, ..., w_6 = 0
For trial = 1 to N_train:
    s = empty board
    history = []
    Repeat:
        Append current s to history (if it's the learner's turn)
        s = learner move (argmax_s' V_hat(s'))
        If game over: record terminal outcome, break
        s = teacher move (argmax_s' V_fixed(s'))
    Until game over
    Assign V_train to every state in history using (1.1) and the terminal value
    For each <s, V_train(s)> in history:
        For each i in 0..6:
            w_i += eta * (V_train(s) - V_hat(s)) * x_i(s)
    Every K trials, evaluate:
        wins += play N_eval games against the teacher, count learner wins
        record (trial, wins / N_eval)
Plot trial (x-axis) vs wins/N_eval (y-axis)

Step 7. Expected results

A typical learning curve, with $\eta =0.1$ and an evaluation batch of 100 games every 100 training games, looks qualitatively like:

Training games	Win rate vs. teacher
0	~ 0.30 (random play)
100	~ 0.42
500	~ 0.58
1000	~ 0.70
2000	~ 0.78
5000	~ 0.82 (near plateau)

The curve rises steeply during the first few hundred games as the system learns the importance of threats ($x_5,x_6$) and potential winning lines ($x_3,x_4$), then plateaus because the linear representation cannot encode deep strategic concepts such as “fork in two diagonal directions.” Beyond this plateau, additional training games do not significantly improve the win rate.

Step 8. Tradeoffs and extensions

• Feature design matters most. Replacing the crude $x_1,\dots ,x_6$ with engineered features such as “number of two-in-a-rows for X” and “number of unblocked diagonals” would dramatically speed up learning.
• Beyond linear models. A small neural network over the raw $9$-cell board encoding would in principle learn features automatically and reach a higher plateau, at the cost of many more training games.
• Bigger $\eta$ vs. stability. Larger $\eta$ accelerates early learning but can cause the weights to oscillate near the plateau; smaller $\eta$ learns slowly but converges more smoothly.

This experiment illustrates, in miniature, every component of the checkers learning system: a Performance System, a Critic, a Generalizer (LMS), and an Experiment Generator, and it shows concretely how a linear evaluation function can be trained from indirect feedback to outperform a fixed hand-crafted opponent.

---

References

Ahn, W., & Brewer, W. F. (1993). Psychological studies of explanation-based learning. In G. DeJong (Ed.), Investigating explanation-based learning. Boston: Kluwer Academic Publishers.

Anderson, J. R. (1991). The place of cognitive architecture in rational analysis. In K. VanLehn (Ed.), Architectures for intelligence (pp. 1–24). Hillsdale, NJ: Erlbaum.

Chi, M. T. H., & Bassock, M. (1989). Learning from examples via self-explanations. In L. Resnick (Ed.), Knowing, learning, and instruction: Essays in honor of Robert Glaser. Hillsdale, NJ: L. Erlbaum Associates.

Cooper, G., et al. (1997). An evaluation of machine-learning methods for predicting pneumonia mortality. Artificial Intelligence in Medicine (to appear).

Fayyad, U. M., & Uthurusamy, R. (Eds.) (1995). Proceedings of the First International Conference on Knowledge Discovery and Data Mining. Menlo Park, CA: AAAI Press.

Fayyad, U. M., Smyth, P., Weir, N., & Djorgovski, S. (1995). Automated analysis and exploration of image databases: Results, progress, and challenges. Journal of Intelligent Information Systems, 4, 1–19.

Laird, J., Rosenbloom, P., & Newell, A. (1986). SOAR: The anatomy of a general learning mechanism. Machine Learning, 1(1), 11–46.

Langley, P., & Simon, H. (1995). Applications of machine learning and rule induction. Communications of the ACM, 38(11), 55–64.

Lee, K. (1989). Automatic speech recognition: The development of the Sphinx system. Boston: Kluwer Academic Publishers.

Pomerleau, D. A. (1989). ALVINN: An autonomous land vehicle in a neural network (Technical Report CMU-CS-89-107). Pittsburgh, PA: Carnegie Mellon University.

Qin, Y., Mitchell, T., & Simon, H. (1992). Using EBG to simulate human learning from examples and learning by doing. Proceedings of the Florida AI Research Symposium (pp. 235–239).

Rudnicky, A. I., Hauptmann, A. G., & Lee, K. F. (1994). Survey of current speech technology in artificial intelligence. Communications of the ACM, 37(3), 52–57.

Rumelhart, D., Widrow, B., & Lehr, M. (1994). The basic ideas in neural networks. Communications of the ACM, 37(3), 87–92.

Tesauro, G. (1992). Practical issues in temporal difference learning. Machine Learning, 8, 257.

Tesauro, G. (1995). Temporal difference learning and TD-gammon. Communications of the ACM, 38(3), 58–68.

Waibel, A., Hanazawa, T., Hinton, G., Shikano, K., & Lang, K. (1989). Phoneme recognition using time-delay neural networks. IEEE Transactions on Acoustics, Speech and Signal Processing, 37(3), 328–339.