19.1 Forms of Learning
Supervised learning uses labeled examples; unsupervised learning finds structure without labels; reinforcement learning learns from reward signals.
AI · MACHINE LEARNING
19 · Learning from Examples
Machine learning improves a task by extracting patterns from data. A useful system must generalize to examples it has not seen, not merely memorize its training set.
19.2 Supervised Learning
A learner uses input–output pairs to estimate a function, evaluating performance on data kept separate from training.
19.3 Learning Decision Trees
Decision trees recursively split examples by feature tests. Information gain measures how much a split reduces label uncertainty.
19.4 Model Selection and Optimization
Optimization fits model parameters; validation data helps select complexity and reduce overfitting. Regularization trades fit against complexity.
19.5 The Theory of Learning
Learning theory relates sample size, hypothesis complexity, and generalization error, clarifying when observed accuracy is trustworthy.
19.6 Linear Regression and Classification
Linear models combine features with weights; regression predicts numeric values, while classification maps scores to categories.
19.7 Nonparametric Models
Nonparametric methods let model complexity grow with available data, as in nearest-neighbor prediction and kernel methods.
19.8 Ensemble Learning
Ensembles combine predictors; bagging reduces variance, boosting focuses on errors, and random forests average diverse trees.
19.9 Developing Machine Learning Systems
A practical workflow includes data collection, representative evaluation, error analysis, deployment monitoring, and attention to bias and drift.
Key terms and a split-selection trace
- Supervised learning
- Fit a predictor from feature vectors paired with labels. Keep a separate validation/test set for an honest estimate on unseen cases.
- Entropy and information gain
- For binary labels with positive fraction p, H = −p log₂p − (1−p)log₂(1−p). A split's gain is parent entropy minus the child entropies weighted by child size.
- Decision stump
- A depth-one tree tests one feature against one threshold; each side predicts its majority class. This demo is not a fully grown tree.
- Generalization / overfitting
- A high training score may reflect memorization. The displayed accuracy is training accuracy only; it is not evidence of test performance.
Training trace
For each feature (x and y), sort distinct observed values and test midpoints between neighbors. For every candidate, partition the points, compute weighted child entropy, and retain the largest gain. Then each child predicts its majority label. For example, a midpoint that sends mostly class-0 points left and class-1 points right can sharply reduce entropy; the exact winner is calculated from the current sample set.
New demo examples are synthetically labeled by x+y>1, so this generated rule is known to the toy data source and may not resemble a real task.
Interactive supervised learning
Train a one-split decision tree
Choose the feature and threshold with the greatest information gain, then evaluate the resulting stump on these labeled points.
No split trained.
Examples: 12
Train the tree to compare candidate splits.
Demo performance
Let n be the number of examples and d the number of features tested (d=2 here). There are at most d(n−1) thresholds. The implementation filters and recomputes child entropy by scanning examples for each threshold, and also computes training accuracy with repeated majority-count scans: worst-case O(dn²) time (the value-sorting term O(dn log n) is no larger for n≥2). Temporary candidate/group arrays use O(n+d) auxiliary space; stored examples and the SVG plot each use O(n) space. With two fixed features, training is O(n²), not linear.