Background

Regular expressions come from the mathematics of automata: Stephen Kleene described “regular events” in 1956, and Ken Thompson turned them into a practical search tool in 1968, building them into the text editors that later gave Unix its grep command. This page uses JavaScript’s regular expressions, which add conveniences such as \d and lookahead to that original notation.

In practice

Hand-written patterns are still widely used in clinical and research NLP for well-formed items such as doses, dates, lab values and trial IDs. They are transparent and need no training data, but brittle: every variation (a missing space, “mcg” instead of “µg”, a new date format) needs another rule, and they match form rather than meaning, as the dose example shows.

References

1. Kleene, S. C. (1956). Representation of events in nerve nets and finite automata. In C. E. Shannon & J. McCarthy (Eds.), Automata Studies (pp. 3–41). Princeton University Press. doi.org/10.1515/9781400882618-002
2. Thompson, K. (1968). Regular expression search algorithm. Communications of the ACM, 11(6), 419–422. doi.org/10.1145/363347.363387
3. MDN Web Docs. Regular expressions (JavaScript guide). developer.mozilla.org

Why it matters

Weizenbaum was troubled by how readily people confided in the program, even when they knew how it worked. The tendency to read understanding into a system's output is now called the ELIZA effect. He later argued that some decisions, including in medicine and psychotherapy, should not be handed over to computers at all. Today's clinical chatbots are far more fluent, but they raise the same questions.

This is the original program's behaviour running Weizenbaum's own DOCTOR script, exactly as printed in the appendix of the 1966 paper. The engine is Anthony Hay's faithful recreation, which reproduces the conversation printed in the paper word for word. Both the recreation and the original code and script are in the public domain (CC0), the latter with the permission of Weizenbaum's estate. Like the original, ELIZA replies in capitals, keeps only the first clause that contains a keyword, and swaps pronouns across the whole sentence before matching any pattern.

References

1. Weizenbaum, J. (1966). ELIZA — a computer program for the study of natural language communication between man and machine. Communications of the ACM, 9(1), 36–45. doi.org/10.1145/365153.365168
2. Weizenbaum, J. (1976). Computer Power and Human Reason: From Judgment to Calculation. San Francisco: W. H. Freeman.
3. Hay, A. ELIZA: a recreation of Weizenbaum's 1966 ELIZA and DOCTOR script (CC0). github.com/anthay/ELIZA
4. ELIZAGEN: the original ELIZA code, found in Weizenbaum's archive at MIT. elizagen.org

How stemming works

Porter’s stemmer (1980) strips suffixes in five steps of rules, each applied only if enough of the word remains. It is fast and needs no dictionary, but its stems are not always real words (“this” → thi, “sample” → sampl), it misses irregular forms (“ran” and “run” stay apart), and it was written for American spelling: “randomised” becomes randomis but “randomized” becomes random. Lemmatisation, which maps words to their dictionary form, is the more linguistic alternative.

In practice

Every choice here changes what later steps see. “Not” and “no” are on the stopword list, so “not significant” loses the word that matters most. Medical text is full of tokens that simple rules handle unevenly: this tokenizer keeps “67-year-old”, “COVID-19” and “HbA1c” whole but splits “7.2%” into 7 and 2. Modern language models skip stemming and stopwords altogether and split text into subword pieces instead.

References

1. Porter, M. F. (1980). An algorithm for suffix stripping. Program, 14(3), 130–137. doi.org/10.1108/eb046814
2. Manning, C. D., Raghavan, P., & Schütze, H. (2008). Introduction to Information Retrieval. Cambridge University Press. Chapter 2: The term vocabulary and postings lists. Free online: nlp.stanford.edu/IR-book

Background

The idea that a word is informative in proportion to how few documents contain it was introduced by Karen Spärck Jones in 1972 as “term specificity”, now called inverse document frequency. Combined with term frequency, it became the standard way to weight words in search engines, and remains a strong baseline for searching, comparing and clustering documents.

Variants

There are many versions of the formula: counts may be log-scaled, idf smoothed so that words in every document keep some weight, and each document’s scores normalised to a vector of length 1. This panel uses the simplest textbook form: raw term frequency divided by document length, times ln(N / df).

References

1. Spärck Jones, K. (1972). A statistical interpretation of term specificity and its application in retrieval. Journal of Documentation, 28(1), 11–21. doi.org/10.1108/eb026526
2. Salton, G., & Buckley, C. (1988). Term-weighting approaches in automatic text retrieval. Information Processing & Management, 24(5), 513–523. doi.org/10.1016/0306-4573(88)90021-0
3. Manning, C. D., Raghavan, P., & Schütze, H. (2008). Introduction to Information Retrieval. Cambridge University Press. Chapter 6: Scoring, term weighting and the vector space model. Free online: nlp.stanford.edu/IR-book

Background

BM25 (“Best Matching 25”) was developed by Stephen Robertson, Karen Spärck Jones and colleagues for the Okapi search system, and presented in its now-standard form at the TREC-3 evaluation in 1994. It follows from a probabilistic model of relevance, and remains the default ranking in the Lucene search library (and Elasticsearch, which is built on it) as well as a standard baseline in retrieval research.

The formula

For each query word: idf × f·(k1 + 1) / (f + k1·(1 − b + b·|d| / avgdl)), summed over the query, where f is how often the word occurs in the document, |d| is the document’s length and avgdl the average length. Typical settings are k1 between 1.2 and 2 and b = 0.75.

References

1. Robertson, S. E., Walker, S., Jones, S., Hancock-Beaulieu, M. M., & Gatford, M. (1995). Okapi at TREC-3. In Overview of the Third Text REtrieval Conference (TREC-3) (pp. 109–126). NIST.
2. Robertson, S., & Zaragoza, H. (2009). The probabilistic relevance framework: BM25 and beyond. Foundations and Trends in Information Retrieval, 3(4), 333–389. doi.org/10.1561/1500000019
3. Apache Lucene. BM25Similarity (documentation of the idf variant used here). lucene.apache.org

Why “naive”

The model assumes that every word is independent of the others once the class is known, which is plainly false (“randomised” and “placebo” tend to appear together). Yet it classifies text surprisingly well, trains in a single pass over the data and shows exactly why it made each decision, which is why it has long been a standard first model for tasks such as spam filtering and document classification. Whether it is good enough for a task is judged on examples it has not seen, with the measures shown in evaluating classifiers.

Smoothing

Without smoothing, a single word never seen with a class would make that class impossible, because its probability would be zero. Adding α to every count (Laplace smoothing when α = 1) avoids this; move the slider to see how a larger α flattens the evidence.

References

1. Maron, M. E. (1961). Automatic indexing: an experimental inquiry. Journal of the ACM, 8(3), 404–417. doi.org/10.1145/321075.321084
2. McCallum, A., & Nigam, K. (1998). A comparison of event models for naive Bayes text classification. In AAAI-98 Workshop on Learning for Text Categorization (pp. 41–48). aaai.org
3. Manning, C. D., Raghavan, P., & Schütze, H. (2008). Introduction to Information Retrieval. Cambridge University Press. Chapter 13: Text classification and Naive Bayes. Free online: nlp.stanford.edu/IR-book

SVMs and text

Before deep learning, support vector machines were among the most accurate text classifiers: Joachims (1998) showed that they cope well with the thousands of word features in a TF-IDF representation. This demo uses two dimensions so that the boundary can be drawn; with text, every word is a dimension and the boundary is a flat hyperplane in that space.

How it is trained

The widest-margin boundary is the solution of an optimisation problem. This page solves it with sequential minimal optimisation (SMO), which repeatedly adjusts just two points at a time, each time choosing the pair that most violates the optimality conditions. It is the approach used by the widely used LIBSVM library, and gives the same results on test data.

References

1. Boser, B. E., Guyon, I. M., & Vapnik, V. N. (1992). A training algorithm for optimal margin classifiers. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory (pp. 144–152). doi.org/10.1145/130385.130401
2. Cortes, C., & Vapnik, V. (1995). Support-vector networks. Machine Learning, 20(3), 273–297. doi.org/10.1007/BF00994018
3. Joachims, T. (1998). Text categorization with support vector machines: learning with many relevant features. In Machine Learning: ECML-98, LNCS 1398 (pp. 137–142). Springer. doi.org/10.1007/BFb0026683
4. Platt, J. (1998). Sequential minimal optimization: a fast algorithm for training support vector machines (Technical Report MSR-TR-98-14). Microsoft Research.
5. Keerthi, S. S., Shevade, S. K., Bhattacharyya, C., & Murthy, K. R. K. (2001). Improvements to Platt’s SMO algorithm for SVM classifier design. Neural Computation, 13(3), 637–649. doi.org/10.1162/089976601300014493
6. Chang, C.-C., & Lin, C.-J. (2011). LIBSVM: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2(3), 27. doi.org/10.1145/1961189.1961199

The distributional hypothesis

The idea that words used in similar contexts have similar meanings goes back to Zellig Harris (1954) and J. R. Firth, who wrote in 1957 that “you shall know a word by the company it keeps”. It underlies every method on this page and the next, up to today’s language models.

Raw counts or PPMI

Raw counts are dominated by frequent words that appear everywhere. Pointwise mutual information (Church & Hanks, 1990) asks instead whether two words occur together more often than chance would predict; keeping only the positive values (PPMI) gives cleaner vectors. Compare the two with the weighting menu.

Limits

With 28 sentences the vectors are sparse and noisy; research systems count over millions of sentences. Such count-based vectors are closely related to word2vec on the next page: Levy & Goldberg (2014) showed that word2vec implicitly factorises a matrix of shifted PMI values.

References

1. Harris, Z. S. (1954). Distributional structure. Word, 10(2–3), 146–162. doi.org/10.1080/00437956.1954.11659520
2. Firth, J. R. (1957). A synopsis of linguistic theory, 1930–1955. In Studies in Linguistic Analysis (pp. 1–32). Oxford: Philological Society.
3. Church, K. W., & Hanks, P. (1990). Word association norms, mutual information, and lexicography. Computational Linguistics, 16(1), 22–29. aclanthology.org/J90-1003
4. Turney, P. D., & Pantel, P. (2010). From frequency to meaning: vector space models of semantics. Journal of Artificial Intelligence Research, 37, 141–188. arxiv.org/abs/1003.1141
5. Levy, O., & Goldberg, Y. (2014). Neural word embedding as implicit matrix factorization. Advances in Neural Information Processing Systems 27. papers.nips.cc

Why squares?

Squaring the errors makes them all positive and punishes large misses more than small ones, and it gives a unique best line that can be computed directly, without trial and error. Adrien-Marie Legendre published the method in 1805 to fit the orbits of comets. The price is sensitivity to outliers: one extreme point carries the square of its distance, so it can tilt the whole line. Try the outlier example, then drag that point around.

Overfitting and the test set

A higher-degree curve can always get closer to the training points, so training error alone keeps improving. What matters is how well the model predicts points it has not seen. With a test set held out, the training error falls as the degree rises while the test error eventually climbs again: the curve has started fitting noise. Ridge regression (Hoerl & Kennard, 1970) adds a penalty λ on the size of the coefficients, trading a little bias for a smoother, more stable curve.

Where the name comes from

Francis Galton noticed in 1886 that children of unusually tall parents tend to be less extreme than their parents, and called it “regression towards mediocrity”. Regression to the mean turns up wherever something is measured twice: a team after a record season, a pupil after an unusually good exam, or a patient enrolled in a trial because a reading was unusually high will, on average, do less extremely next time, whether or not anything changed.

References

1. Legendre, A.-M. (1805). Nouvelles méthodes pour la détermination des orbites des comètes. Paris. (Appendix: the method of least squares.)
2. Galton, F. (1886). Regression towards mediocrity in hereditary stature. Journal of the Anthropological Institute of Great Britain and Ireland, 15, 246–263.
3. Hoerl, A. E., & Kennard, R. W. (1970). Ridge regression: biased estimation for nonorthogonal problems. Technometrics, 12(1), 55–67. doi.org/10.1080/00401706.1970.10488634
4. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed.), chapters 3 and 7. Springer. doi.org/10.1007/978-0-387-84858-7 · free online: hastie.su.domains/ElemStatLearn

The learning rate

Each step moves the parameters by the learning rate times the gradient. Too small and the walk takes forever; too large and each step overshoots the bottom of the valley and lands higher up the opposite wall, so the error grows instead of shrinking. Try raising the learning rate step by step: with standardised age the walk overshoots and zigzags above 0.5 and diverges above 1; with age in years it zigzags across the valley just below 3.2 × 10⁻⁴ and diverges just above.

Why scaling matters

With age in years (25 to 80), a small change in the slope moves the line far more than the same change in the intercept, so the error landscape is a long, narrow valley: steep across, almost flat along. A learning rate small enough not to overshoot across the valley crawls along it: the path snaps sideways to the valley floor within a few steps and then barely moves, because it is now heading almost straight up a nearly flat slope. Plain gradient descent needs about 156,000 steps to arrive, momentum about 44,000. Standardising age (subtracting the mean and dividing by the standard deviation) turns the valley into a round bowl, and the same method arrives in under a hundred steps. The condition number in the table, the ratio of the steepest to the flattest curvature, measures the problem: about 27,000 in years, exactly 1 when standardised. This is why features are usually standardised before training.

Momentum, Adam and mini-batches

Momentum (Polyak, 1964) lets each step keep 90% of the previous one, so the zigzags across the valley cancel out while progress along it builds up speed. Adam (Kingma & Ba, 2015) also keeps a running average of the size of each parameter's gradient and divides by it, so every parameter moves at a similar pace whatever its scale. With large datasets, computing the gradient over every point for every step is too slow, so each step uses a small random mini-batch instead: stochastic gradient descent, going back to Robbins and Monro (1951). The path becomes noisy but much cheaper per step; set the batch to 1 or 5 to see it. Neural networks, including large language models, are trained with variants of these same methods. For this line there is also an exact formula (the regression demo uses it), which makes it easy to check that every method ends up in the same place.

References

1. Cauchy, A. (1847). Méthode générale pour la résolution des systèmes d'équations simultanées. Comptes rendus hebdomadaires des séances de l'Académie des sciences, 25, 536–538.
2. Robbins, H., & Monro, S. (1951). A stochastic approximation method. The Annals of Mathematical Statistics, 22(3), 400–407. doi.org/10.1214/aoms/1177729586
3. Polyak, B. T. (1964). Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5), 1–17. doi.org/10.1016/0041-5553(64)90137-5
4. Kingma, D. P., & Ba, J. (2015). Adam: a method for stochastic optimization. 3rd International Conference on Learning Representations (ICLR), San Diego. arxiv.org/abs/1412.6980

Probabilities, odds and the S-curve

A probability must stay between 0 and 1, so a straight line cannot predict one. Logistic regression instead models the log-odds, log(p / (1 − p)), as a straight line in the predictors; turning the log-odds back into a probability gives the S-curve. The slope β is the change in log-odds per unit of the predictor, so e^β is the odds ratio: in the heart disease example, each 10 years of age multiplies the odds of disease by about e^10β. With several predictors each coefficient is adjusted for the others, which is why logistic regression is the standard way to report risk factors.

Fitting by maximum likelihood

There is no squared error to minimise here. Instead the fit chooses the coefficients that make the observed outcomes most probable (maximum likelihood), which is the same as minimising the log-loss: the average of −log(p) for the people who had the outcome and −log(1 − p) for those who did not. Confident wrong predictions are punished hard. Unlike least squares there is no direct formula; the demo uses Newton's method, the standard approach, which converges in a handful of steps. Gradient descent would reach the same answer more slowly.

Boundaries and their limits

With two predictors, the 50% line is where the log-odds are zero, which is a straight line: logistic regression is a linear classifier. The electrolytes example has a round normal range, which a straight line cannot capture; adding the squared terms lets the boundary curve into an ellipse, the same trick as adding x² inputs in the neural network demo. When the classes do not overlap at all (try “no overlap”), the likelihood keeps rising as the curve steepens, the coefficients run off to infinity, and the software must stop somewhere; a penalty such as ridge, or Firth's correction, fixes this.

References

1. Berkson, J. (1944). Application of the logistic function to bio-assay. Journal of the American Statistical Association, 39(227), 357–365. doi.org/10.1080/01621459.1944.10500699
2. Cox, D. R. (1958). The regression analysis of binary sequences. Journal of the Royal Statistical Society, Series B, 20(2), 215–232 (with discussion, 232–242). doi.org/10.1111/j.2517-6161.1958.tb00292.x
3. Firth, D. (1993). Bias reduction of maximum likelihood estimates. Biometrika, 80(1), 27–38. doi.org/10.1093/biomet/80.1.27
4. Hosmer, D. W., Lemeshow, S., & Sturdivant, R. X. (2013). Applied Logistic Regression (3rd ed.). Wiley. doi.org/10.1002/9781118548387

Choosing k

With k = 1 every training point decides its own small territory, so the boundary is jagged and follows every quirk and mislabelled case: training accuracy is a perfect 100% because each point is its own nearest neighbour. Larger k smooths the boundary by averaging over more cases, until with k close to the number of points the majority class wins everywhere. Training accuracy is therefore no guide. The chart also shows leave-one-out accuracy, where each training point is classified by the others with itself left out, and accuracy on a held-out test set: both usually peak at a moderate k. Weighting votes by 1 / distance lets the closest cases count for more.

Distances need comparable units

“Nearest” depends on how distance is measured. Glucose varies over a few mmol/L while BMI varies over tens of kg/m², so in raw units a difference of 1 in either counts the same, and BMI dominates: on the diabetes data the dashed neighbourhood is a wide, flat ellipse on the plot, stretching across most of the glucose range while covering only a narrow band of BMI. Turning on feature scaling standardises each feature (subtracts its mean and divides by its standard deviation) so that both count equally, and the neighbourhood becomes round in proportion to the spread of the data. Which choice is right is a judgment about the problem, but it should always be a deliberate one.

Strengths and limits

Fix and Hodges described the method in 1951 in a report for the US Air Force School of Aviation Medicine; Cover and Hart (1967) proved that, with enough data, the error of the single nearest neighbour is at most twice the lowest error any classifier could achieve. Nearest neighbours needs no assumptions about the shape of the boundary and adapts to any number of classes, but it must keep and search the whole training set for every prediction, and in many dimensions all points end up roughly equally far apart, so “nearest” loses its meaning.

References

1. Fix, E., & Hodges, J. L. (1951). Discriminatory analysis. Nonparametric discrimination: consistency properties. Report No. 4, Project 21-49-004. USAF School of Aviation Medicine, Randolph Field, Texas. Reprinted in International Statistical Review (1989), 57(3), 238–247, with a commentary by B. W. Silverman & M. C. Jones.
2. Cover, T. M., & Hart, P. E. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1), 21–27. doi.org/10.1109/TIT.1967.1053964
3. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed.), chapters 2.3 and 13. Springer. doi.org/10.1007/978-0-387-84858-7

How a split is chosen

At each node the tree tries every possible threshold on every feature and keeps the one that makes the two groups purest. Purity is measured by Gini impurity (the chance that two points drawn at random from the node belong to different classes) or by entropy; both are zero when a node holds only one class. The search is greedy, one question at a time, and every question compares a single feature with a threshold, so the regions are always rectangles. That is why the diagonal example needs a staircase of many splits to follow a boundary that one sloped line would describe.

Depth and overfitting

A deep enough tree can put every training point in a leaf of its own and score 100% on the training data, while carving out small boxes around noise that do not hold for new patients. Limiting the depth or the size of a leaf, or pruning the tree back afterwards, keeps it general. The electrolytes example shows this best: its normal range is round and its classes overlap at the edge, so the tree keeps splitting all the way to depth 8. Hold out a test set and raise the depth step by step: training accuracy climbs towards 100% while test accuracy peaks at a moderate depth and then falls. Random forests, which average many trees grown on resampled data, are a common way to keep the accuracy while losing some of the noise.

References

1. Breiman, L., Friedman, J. H., Olshen, R. A., & Stone, C. J. (1984). Classification and Regression Trees. Belmont, CA: Wadsworth.
2. Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1(1), 81–106. doi.org/10.1007/BF00116251
3. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed.), chapter 9.2. Springer. doi.org/10.1007/978-0-387-84858-7

Two kinds of randomness

Each tree is grown on a bootstrap sample: as many points as the training set, drawn with replacement, so some points appear several times and about a third (1/e ≈ 37%) are left out. This is bagging (bootstrap aggregating; Breiman, 1996). On its own it still gives similar trees, because they all choose the same strong first splits, so at each split a random forest also considers only a random subset of the features (Ho, 1995; Breiman, 2001). With two features that means one, picked at random, and the trees become genuinely different. Averaging many trees that are each accurate but err in different places reduces the variance without adding much bias.

Out-of-bag accuracy

Because every tree misses about a third of the points, each point can be classified by just the trees that never saw it. The resulting out-of-bag accuracy behaves like accuracy on a test set, without setting any data aside. In the chart it rises quickly over the first few trees and then levels off: adding more trees never makes a forest overfit, it only stops helping. The cost is interpretability: a forest of a hundred trees can no longer be read like a single flowchart.

References

1. Breiman, L. (2001). Random forests. Machine Learning, 45(1), 5–32. doi.org/10.1023/A:1010933404324
2. Breiman, L. (1996). Bagging predictors. Machine Learning, 24(2), 123–140. doi.org/10.1007/BF00058655
3. Ho, T. K. (1995). Random decision forests. In Proceedings of the 3rd International Conference on Document Analysis and Recognition, Montreal (Vol. 1, pp. 278–282). IEEE. doi.org/10.1109/ICDAR.1995.598994
4. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed.), chapters 8.7 and 15. Springer. doi.org/10.1007/978-0-387-84858-7

Why “gradient”?

For squared error, the residuals are exactly the direction in which each prediction should move to reduce the loss: the negative gradient. Friedman (2001) saw that boosting is gradient descent, carried out not on a handful of parameters but on the predictions themselves, with each tree as one step. Swapping in a different loss gives boosting for other tasks: log-loss for classification (fitting probabilities, as logistic regression does), or absolute error for data with outliers. Earlier boosting methods such as AdaBoost (Freund & Schapire, 1997) reweighted the misclassified points instead.

Learning rate, depth and when to stop

Adding only a fraction of each tree (the learning rate, or shrinkage) makes progress slower but smoother, and usually ends more accurate: with a learning rate of 1 the model chases the noise within a few trees. Deeper trees capture interactions between features but overfit sooner. Unlike a random forest, boosting can overfit if it runs too long, since each tree fits a little more of the remaining noise: hold out a test set and watch the test error flatten and then creep up while the training error keeps falling. In practice the number of trees is chosen by stopping when the error on held-out data stops improving.

References

1. Friedman, J. H. (2001). Greedy function approximation: a gradient boosting machine. The Annals of Statistics, 29(5), 1189–1232. doi.org/10.1214/aos/1013203451
2. Freund, Y., & Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1), 119–139. doi.org/10.1006/jcss.1997.1504
3. Chen, T., & Guestrin, C. (2016). XGBoost: a scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 785–794). doi.org/10.1145/2939672.2939785

What the neurons learn

Each neuron in the first hidden layer splits the plane along one straight line, soft-edged by its activation function: hover over them to see. The next layer combines these half-planes into corners, bands and patches, and the output combines those into the final boundary. Two neurons cannot surround a circle; three or four can. The checkerboard needs neurons that pick out the diagonals, and the spiral needs several layers or extra inputs. Adding x², y² or xy as inputs hands the network curved features ready-made: with x² and y² a circle can be separated by a single output neuron with no hidden layer at all.

Training and its pitfalls

A training run that starts from different random weights can end somewhere different: if the loss stops falling at a poor value, press reset to try new starting weights. Too high a learning rate makes the loss jump about; too low and nothing seems to happen. With noisy data and a large network, the training loss keeps falling while the test loss starts to rise as the network bends its boundary around individual noisy points: overfitting, as in the regression demo. The L2 penalty (weight decay) discourages large weights and so keeps the boundary smoother. ReLU, max(0, z), is the usual choice in modern networks because it trains quickly in deep stacks; tanh and the sigmoid were the classic choices.

From perceptrons to deep learning

Rosenblatt's perceptron (1958) was a single layer of trainable weights. Multilayer networks were known to be more powerful, but there was no practical way to train their hidden layers until backpropagation was popularised by Rumelhart, Hinton and Williams (1986). Cybenko (1989) proved that one hidden layer with enough neurons can approximate any continuous function, although “enough” may be very many; in practice, deeper networks need far fewer neurons. Today's deep networks for images, speech and language are, at heart, much larger versions of this one. The layout of this demo follows the TensorFlow Playground (Smilkov et al., 2017).

References

1. Rosenblatt, F. (1958). The perceptron: a probabilistic model for information storage and organization in the brain. Psychological Review, 65(6), 386–408. doi.org/10.1037/h0042519
2. Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1986). Learning representations by back-propagating errors. Nature, 323, 533–536. doi.org/10.1038/323533a0
3. Cybenko, G. (1989). Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2(4), 303–314. doi.org/10.1007/BF02551274
4. Kingma, D. P., & Ba, J. (2015). Adam: a method for stochastic optimization. ICLR 2015. arxiv.org/abs/1412.6980
5. Smilkov, D., Carter, S., Sculley, D., Viégas, F. B., & Wattenberg, M. (2017). Direct-manipulation visualization of deep networks. arxiv.org/abs/1708.03788 · playground.tensorflow.org

Sensitivity, specificity and the threshold

Sensitivity is the share of diseased people the test calls positive; specificity is the share of healthy people it calls negative. Yerushalmy (1947) popularised both terms while comparing how radiologists read chest X-rays. Lowering the threshold catches more disease but alarms more healthy people, and raising it does the reverse. Where to put it depends on the cost of each mistake: a screening test, where a missed case is costly and a false alarm only leads to a second test, favours sensitivity; a confirmatory test before a risky treatment favours specificity.

The ROC curve and AUC

The ROC curve, a term borrowed from radar engineering, plots sensitivity against the false positive rate (1 − specificity) for every possible threshold at once, so it describes the test itself rather than one choice of threshold. The area under it, the AUC, is the probability that a randomly chosen diseased person scores higher than a randomly chosen healthy one (counting ties as half; Hanley & McNeil, 1982): 0.5 is no better than chance, 1 is perfect separation. Move the separation slider to see the curve bow out towards the top-left corner as the groups pull apart.

Prevalence and predictive values

Sensitivity and specificity do not depend on how common the disease is, but what a positive result means does. The positive predictive value (PPV) is the chance that someone who tests positive really has the disease, and it falls steeply as the disease gets rarer, because the few true positives are swamped by false positives from the large healthy majority. Set the prevalence to 1% to see a test that is right most of the time produce mostly false alarms. This is why screening programmes for rare conditions follow a positive result with a more specific test, and why accuracy alone is misleading when the classes are unbalanced.

Cross-validation

Judging a model on the data it was trained on rewards memorising: the deepest tree scores best on its own training data. A single held-out test set avoids that but wastes data, and with small datasets the result depends on which points happened to land in it. k-fold cross-validation splits the data into k parts, trains on k − 1 of them and tests on the remaining one, k times over, so every point is used for testing exactly once (Stone, 1974). The average estimates performance on new data, and the spread across folds shows how uncertain that estimate is. Choosing the depth with the best cross-validated accuracy, as here, is how settings are usually tuned; a final, untouched test set then gives an honest score for the chosen model.

References

1. Yerushalmy, J. (1947). Statistical problems in assessing methods of medical diagnosis, with special reference to X-ray techniques. Public Health Reports, 62(40), 1432–1449. doi.org/10.2307/4586294
2. Hanley, J. A., & McNeil, B. J. (1982). The meaning and use of the area under a receiver operating characteristic (ROC) curve. Radiology, 143(1), 29–36. doi.org/10.1148/radiology.143.1.7063747
3. Altman, D. G., & Bland, J. M. (1994). Diagnostic tests 1: sensitivity and specificity. BMJ, 308(6943), 1552. doi.org/10.1136/bmj.308.6943.1552
4. Altman, D. G., & Bland, J. M. (1994). Diagnostic tests 2: predictive values. BMJ, 309(6947), 102. doi.org/10.1136/bmj.309.6947.102
5. Fawcett, T. (2006). An introduction to ROC analysis. Pattern Recognition Letters, 27(8), 861–874. doi.org/10.1016/j.patrec.2005.10.010
6. Stone, M. (1974). Cross-validatory choice and assessment of statistical predictions. Journal of the Royal Statistical Society, Series B, 36(2), 111–133 (with discussion, 133–147). doi.org/10.1111/j.2517-6161.1974.tb00994.x

Local optima and starting points

Every assign and every update can only lower the inertia, so k-means always stops, but it stops at the first arrangement it cannot improve, which need not be the best one. With random starting points, two centroids sometimes begin in the same blob and one real blob is left to share a centroid with its neighbour: press “new start” a few times with four blobs to see it happen. k-means++ (Arthur & Vassilvitskii, 2007) picks each new starting centroid with probability proportional to its squared distance from those already chosen, which spreads them out and makes poor starts rare. Software usually also runs k-means several times and keeps the result with the lowest inertia.

Choosing k

Inertia always falls as k grows, reaching zero when every point is its own cluster, so the lowest inertia cannot pick k. The elbow plot shows the best inertia found for each k: on clear data the curve drops steeply until k reaches the true number of groups and then flattens, and that bend, the “elbow”, suggests k (Thorndike, 1953). On the data with no clusters there is no elbow, yet k-means still returns k tidy-looking groups: it always finds clusters, whether or not they are there.

What k-means assumes

Because each point goes to its nearest centroid, k-means draws straight borders halfway between centroids and favours round clusters of similar size. The unequal example shows the cost: the borders cut into the wide cluster to give the tight ones a fair share of space. The two moons are two clear groups, but not round ones, so k-means splits them across the middle. Methods such as Gaussian mixtures, DBSCAN or hierarchical clustering make different assumptions. Stuart Lloyd devised the algorithm at Bell Labs in 1957 for quantising signals; it was published only in 1982.

References

1. Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137. (Bell Laboratories manuscript, 1957.) doi.org/10.1109/TIT.1982.1056489
2. Arthur, D., & Vassilvitskii, S. (2007). k-means++: the advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 1027–1035). SIAM.
3. Thorndike, R. L. (1953). Who belongs in the family? Psychometrika, 18(4), 267–276. doi.org/10.1007/BF02289263

What the components are

PCA centres the data and looks for the line through the middle along which the points are most spread out: PC1. It is also the line that the points are, on average, closest to, which is how Karl Pearson framed it in 1901. PC2 is the direction of greatest remaining spread at right angles to PC1, and so on. Mathematically the components are the eigenvectors of the covariance matrix and each eigenvalue is the variance along its component; the rotation they define keeps all the information, and dropping the last components throws away only the variance along them. Height and weight are strongly correlated, so PC1 (roughly “overall size”) carries most of the variance, and keeping only PC1 loses little.

Reading a biplot, and why to standardise

In the lab panel, each arrow shows how one measurement lines up with the two components on screen: measurements whose arrows point the same way rise and fall together, and patients lie towards the arrows of their high values. With standardisation, PC1 picks up the metabolic measurements (weight, waist, glucose and triglycerides up, HDL down) and separates the metabolic-syndrome group, while PC2 combines body size and kidney function. Turn standardisation off and PC1 becomes almost pure creatinine, with over 90% of the variance, simply because creatinine is measured in µmol/L and its numbers are the largest. Without standardising, PCA ranks features by their units, not by what they tell you, so features on different scales are almost always standardised first.

Limits

PCA only finds straight directions, and the direction of greatest variance is not necessarily the most useful one: here the kidney-disease group differs from the healthy group mainly along PC2 and PC3 (show PC2 against PC3), which together carry less than 40% of the variance. Components are mixtures of every feature, which can make them hard to name. Methods such as t-SNE and UMAP draw curved, local structure better, but distort distances in ways that are easy to over-read; PCA remains the usual first look at a new dataset; the word2vec demo uses it to draw 300-dimensional word vectors in three.

References

1. Pearson, K. (1901). On lines and planes of closest fit to systems of points in space. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 2(11), 559–572. doi.org/10.1080/14786440109462720
2. Hotelling, H. (1933). Analysis of a complex of statistical variables into principal components. Journal of Educational Psychology, 24(6), 417–441, and 24(7), 498–520. doi.org/10.1037/h0071325
3. Jolliffe, I. T., & Cadima, J. (2016). Principal component analysis: a review and recent developments. Philosophical Transactions of the Royal Society A, 374(2065), 20150202. doi.org/10.1098/rsta.2015.0202

Reading the map

In the colours example each unit's weights are a colour, so the map can be painted directly: after training, similar colours sit together and blend into each other. For 2D data, the units are coloured by their position in the input space, so the same colours in both views belong together. The U-matrix (Ultsch & Siemon, 1990) shows the distance from each unit to its neighbours: orange ridges are gaps in the data, the borders between clusters. The hits view shows how many samples each unit represents.

Measuring quality

The quantisation error is the average distance from each sample to its best-matching unit: how faithfully the map represents the data. The topographic error is the share of samples whose two closest units are not neighbours on the grid: how well the map keeps things that are close in the data close on the grid. A tangled map, as at the start, has a high topographic error. Shrinking the neighbourhood too fast leaves knots that never untangle; try a short training length on the square.

Where SOMs are used

Teuvo Kohonen developed the method in the early 1980s, partly as a model of the orderly maps found in the brain's sensory cortex. SOMs have since been used to organise large collections of documents, sounds and images, to monitor industrial processes, and in biology to group genes by their expression patterns (Tamayo et al., 1999). Their advantage over plain clustering is the picture: the map shows how groups relate to each other, not only which group each item belongs to.

References

1. Kohonen, T. (1982). Self-organized formation of topologically correct feature maps. Biological Cybernetics, 43(1), 59–69. doi.org/10.1007/BF00337288
2. Kohonen, T. (1990). The self-organizing map. Proceedings of the IEEE, 78(9), 1464–1480. doi.org/10.1109/5.58325
3. Ultsch, A., & Siemon, H. P. (1990). Kohonen's self organizing feature maps for exploratory data analysis. In Proceedings of the International Neural Network Conference (INNC-90), Paris (Vol. 1, pp. 305–308). Kluwer.
4. Tamayo, P., Slonim, D., Mesirov, J., et al. (1999). Interpreting patterns of gene expression with self-organizing maps: methods and application to hematopoietic differentiation. Proceedings of the National Academy of Sciences, 96(6), 2907–2912. doi.org/10.1073/pnas.96.6.2907