Motivation
An inference engine applies rules already supplied to it. A learning system instead uses examples to adjust a representation or its parameters. This distinction is useful but not absolute: a learned decision tree can later function as a rule system, and a neural network can supply features to a separate reasoning procedure. In either case, a prediction is constrained by the information retained in the representation.
Suppose a message classifier records whether certain words occur. It can learn correlations between those indicators and labels, but it cannot distinguish two messages mapped to the same indicator vector. If word order changes the meaning, a bag of words has already discarded relevant information before optimization begins. Better fitting cannot reconstruct information absent from its input. Representation and learning rule must therefore be examined together.
This unit derives two basic learning updates from explicit models and studies one decision-tree splitting criterion. The mathematical guarantees are intentionally narrow. A perceptron bound assumes a separating margin; a gradient is a local derivative, not a promise of global optimization; entropy reduction on a training sample is not a guarantee of future accuracy.
Definitions
Definition 3.1.1
(Labeled example and linear score)
A binary labeled example is , where is a feature vector and is a label. A linear score is . A bias can be included by replacing with and giving the extra coordinate its own weight. All norm and margin assumptions below then concern these augmented vectors. A prediction convention at zero must be stated; for the update rule we treat as a mistake or boundary violation.
Concept lensStructural
A feature map creates equivalence classes
For any deterministic feature map , all predictors of the form give the same output to inputs with the same . Thus partitions inputs into indistinguishable classes. If a task assigns different required labels within one class, no choice of can fit both. This explains a limitation of bag-of-words language representations without attributing it to a particular optimizer. For example, “dog bites person” and “person bites dog” have the same word-count vector but different role assignments, so any predictor that sees only the word counts must treat them alike.
Token counts retain useful evidence for some classification tasks while discarding syntax. A broader natural-language system must specify tokenization, ambiguity handling, compositional structure and its evaluation task. Merely using a large vector does not establish that these issues have been resolved.
Definition 3.1.2
(The perceptron update)
The perceptron starts with . On a violating example, it updates ; otherwise it leaves the weight unchanged. The update increases that example's signed score by , since . It can nevertheless reduce another example's signed score, so progress on one example does not establish monotone decrease of the number of errors.
Definition 3.1.3
(Squared loss, gradient step and the one-hidden-layer network)
For a differentiable model and target , a squared loss is . Gradient descent uses with a specified step size . For a one-hidden-layer scalar-output network, write
The hidden activation is differentiable at the values under consideration, and the output here is linear. Other output activations and losses produce different derivatives. For sigmoid, and . A rectified linear activation is not differentiable at zero, where an algorithm needs a stated subgradient or other convention.
Definition 3.1.4
(Entropy, conditional entropy and information gain)
For a finite labeled sample, let a randomly selected training item have class variable . If class proportions are , its empirical entropy in bits is
using by continuity. A candidate attribute partitions the sample into values , with proportions . The conditional entropy is , and information gain is . A decision-tree learner may greedily choose a split of largest gain. It still needs stopping, tie and pruning rules.
Theorem/Proposition
Theorem 3.1.5
(Perceptron mistake bound under a positive margin)
Suppose every presented example satisfies , and one fixed unit vector satisfies for every example. Starting at zero and updating on , the perceptron makes at most updates, regardless of presentation order. This bounds updates, not the number of correctly classified examples that may be presented between them.
Proposition 3.1.6
(Backpropagation for the stated network)
For the differentiable scalar-output network above and , let . At the current parameter values,
For a batch-average loss, average these per-example derivatives before the simultaneous update.
These claims address different questions. The first establishes finite progress under a strong geometric assumption. The second computes the exact local sensitivity of a specified function. It contains no assertion that the loss surface is convex or that repeated updates reach the best parameters.
Proposition 3.1.7
(Information gain is nonnegative)
For a partition of one nonempty labeled sample by an attribute , the conditional entropy satisfies . Hence the information gain is at least zero.
Proof sketch or proof idea
Proof
(Alignment grows linearly, the norm only as a square root)
Index only actual perceptron updates, writing after of them. Each update increases alignment with the separator by at least , so induction gives . For the norm, an update on satisfies
Thus . Cauchy–Schwarz and now give . If , divide by and square to obtain the bound. For it holds directly. Cycling through a finite separable sample must eventually complete a pass with no updates, because an infinite sequence of mistaken passes would contradict the finite update bound.
Proof X-ray
Why both inequalities are necessary
The separator supplies linear growth of alignment in the number of mistakes. Updating only on nonpositive signed scores supplies at most square-root growth of the norm. Their incompatibility for large mistake counts proves termination. Without a common positive margin, the first inequality disappears. Without the mistake condition, the cross term in the squared norm need not be nonpositive. The proof therefore cannot be transferred unchanged to arbitrary gradient updates or contradictory labels.
Proof
(The chain rule through each parameter group)
For backpropagation, start from . Since and , the output derivatives follow immediately. Along the path from to , the chain rule multiplies , the output weight , the activation derivative and the input vector . Replacing the final derivative by gives the bias derivative. This calculation also explains the organization of reverse-mode differentiation: reuse a shared downstream sensitivity rather than recomputing each full composition.
For a scalar differentiable loss and a nonzero gradient, differentiability gives as , so sufficiently small steps decrease the loss locally. This does not make every fixed positive step safe, nor does it ensure generalization.
Proof
(Concavity of the entropy function)
The function is concave on , with the endpoint defined by continuity. The parent class-proportion vector is the weighted average of the children's vectors. Applying concavity coordinatewise and adding gives . Hence information gain is nonnegative for a genuine partition of one sample.
The argument says nothing about whether the split reflects a stable population relationship; a unique identifier can make every child pure while memorizing the sample.
On inseparable data the perceptron loop never completes a clean pass.
A natural next question
What if no separating vector exists?
On inseparable data the perceptron loop never completes a clean pass.
The bound assumes a margin. If no gives every signed score , the loop cannot end, because a complete pass with no update would itself be such a . For example, two copies of with labels and send from to and back to , repeatedly. Whether another rule can still find a good classifier is a separate question that this theorem does not answer.
Worked examples
Worked example 3.1.8
(Tracing a biased perceptron)
Use augmented examples and . Starting at zero, the first example violates the boundary and yields . For the second, , so its signed score is and no update occurs. The resulting classifier has boundary in the original one-dimensional input. A separator has margins and , so and give a bound of five updates. This is an upper bound, not the observed count or a prediction that exactly five updates are needed.
Worked example 3.1.9
(One fully specified neural step)
Take one input , one sigmoid hidden unit, parameters , target , and step . Then , and . The gradients are , , and . A simultaneous step gives . The new hidden input is , the new output is approximately , and the loss falls from to approximately . Recomputing the forward pass checks both the signs and the interpretation of the derivative.
Worked example 3.1.10
(Information gain can prefer memorization)
Eight items have four positive and four negative labels, so the parent entropy is one bit. Attribute A makes two equally sized children, with class counts and . Each child has entropy , so gain is approximately bits. An identifier attribute makes eight singleton children and has gain one bit. Its larger training gain does not imply better predictions for a new identifier: no learned branch may apply. A split criterion must be interpreted together with representation, regularization and evaluation on unseen data.
Common mistakes
Counterexample mode
Linear features cannot express XOR
Label and positive, and and negative. If an affine score strictly separated them, adding the two positive-score inequalities would give . Adding the two negative-score inequalities would give , a contradiction. Adding the feature solves this representation problem: its sign equals the label. A failure to find a linear separator here is not evidence that the perceptron step size is too small.
Common mistake
(Mixing old and new parameters inside one gradient step)
All derivatives in one gradient step must be evaluated at the same old parameter vector. Updating first and then using its new value in the formula for defines a different procedure, and the result is no longer the gradient step of the stated loss. In the one-unit example, uses the old , not the updated .
Common mistake
(Reading zero information gain as irrelevance)
For the XOR table with rows , splitting on or on alone leaves each child with one row of each label, so both gains are zero. Yet the two attributes together determine the label exactly. A zero gain says only that this single split does not change the label proportions.
Common mistake
(Treating a learned association as a rule and a score as a probability)
An expert system also needs more than an inference engine. Knowledge acquisition must identify domain rules, their conditions and exceptions; explanation should expose which rules fired; maintenance must detect conflicting or outdated rules. A learned association is not automatically a logically valid implication. Likewise, a neural score is not a calibrated probability without an appropriate model, training objective and calibration check. Keep classification error, training loss and confidence as distinct quantities.
Summary
Learning combines a representation, an objective or update rule, and assumptions about the examples. A positive margin yields a perceptron mistake bound. The chain rule yields neural gradients, but not a global-optimum or generalization theorem. Entropy gain measures sample label reduction and can reward memorization. Before changing an optimizer, test whether the chosen representation can distinguish the cases the task requires.
Exercises
Exercise 3.1.11
(Starting from zero, cycle through and using the perceptron update on nonpositive signed scores. Give the first two updates and a unit separator with a positive margin, and compute the theorem's update bound.)
Core
Solution(3)
- 1
Run the first two updates
At the first example has signed score , so . The second example has , so its signed score is zero and it updates: . A further pass gives positive signed scores and , so no more updates occur.
- 2
Choose a separator and read off the margin
Key step
Take . Both signed margins equal , so , and .
Because: The theorem needs one fixed unit vector with every signed score at least .
- 3
Apply the bound
. Two updates occur, so the bound is attained for this order and zero-boundary convention.
Exercise 3.1.12
(For the neural example above, recompute the gradients when the target is . Give the simultaneous parameter update for step and explain the direction of change of the output bias.)
Core
Solution(3)
- 1
Recompute the forward values and the error
The forward values remain , , , but now .
- 2
Compute the gradients at the old parameters
, , and .
Because: Every derivative uses the old value .
- 3
Apply the simultaneous step
With step : , , , . The positive derivative means that increasing the output bias increases the loss locally; subtracting the gradient lowers the bias and moves the output toward the target zero.
Exercise 3.1.13
(A parent sample has six positive and two negative items. A binary attribute makes children with class counts and . Compute its information gain and explain why it is zero although neither child is pure.)
Foundation
Solution(2)
- 1
Compute the entropies
The parent and both children have positive proportion , so all three entropies equal bits.
- 2
Compute the weighted child entropy and the gain
The two children each carry weight one half, so the weighted child entropy is bits, equal to the parent entropy, and the gain is zero. A split can reorganize records without changing the label proportions. Zero gain is not a statement that the labels themselves are deterministic or that the attribute can never matter jointly with another attribute.
Exercise 3.1.14
(Prove the indistinguishability statement for a deterministic feature map. Apply it to the two reversed-role sentences above, then propose one explicit additional feature that distinguishes those two inputs without claiming to solve general language understanding.)
SynthesisProof
Solution(3)
- 1
Use that is a function of the feature vector
Let be a deterministic feature map, let be any function, and suppose .
- 2
Compare the outputs
Key step
Applying the same function to both sides gives . If the task requires opposite labels for and , the predictor is wrong on at least one of them.
- 3
Apply to the sentence pair and add a feature
The two sentences have the same word-count features, so no predictor of those features separates them. The feature “does the ordered adjacent pair dog-bites occur?” equals one in the first sentence and zero in the second under the specified tokenization, so it distinguishes this pair. Negation, paraphrases, longer dependencies and ambiguous grammar remain separate problems; the added feature gives no general semantic completeness claim.
Because: The two sentences have the same word-count vector.
∎