linear separability
In plain wordsWhen two groups of points can be perfectly divided by a single straight line or, in more dimensions, a flat surface. Many simple learning methods only fully succeed in this case.
The condition that two classes of points can be split by a single hyperplane (a line in two dimensions, a plane in three) with each class lying strictly on its own side; geometrically, it holds exactly when the convex hulls of the two classes (the smallest convex regions containing them) have no point in common. If training data are linearly separable, the perceptronperceptron, n.: One of the first learning machines: a single artificial neuron that sorts inputs into two groups by drawing a straight dividing line, nudging its weights whenever it guesses wrong. learning rule is guaranteed to find a separating hyperplane in a finite number of steps (Novikoff's theorem), and a hard-margin support vector machinesupport vector machine, n.: A classic method that separates two groups of examples with the widest possible gap — like laying the broadest possible road between them. A mathematical shortcut lets it draw curved boundaries too. finds the one with maximum marginmargin, n.: How far, and on which side, an example lies from a classifier's dividing line. A wide gap between the line and the nearest examples suggests the classifier will handle new data well.. The XOR pattern is the classic non-separable case: no line separates (0,0) and (1,1) from (0,1) and (1,0). Cover's theorem shows that a random two-class labeling of n points in general position in d dimensions is very likely separable when n is well below 2d, which is why mapping data into a higher-dimensional space — through a hidden layer or the kernel trickkernel trick, n.: A mathematical shortcut that lets simple straight-line methods find curved patterns, by computing similarities between examples as if the data had been mapped into a far richer space — without ever building that space. — can make classes separable.
After the kernel mapping the two classes became linearly separable, so the hard-margin SVM converged.
Origin
The concept comes from threshold logic and late-1950s–1960s perceptron research: Albert Novikoff proved perceptron convergence for separable data in 1962, Thomas Cover counted separable dichotomies in 1965, and Marvin Minsky and Seymour Papert's 'Perceptrons' (1969) highlighted single-layer networks' inability to learn non-separable functions such as XOR.
Usage note
Real datasets are rarely exactly separable, so soft-margin methods and logistic regressionlogistic regression, n.: A simple, widely used method for yes-or-no predictions that outputs a probability — say, a 70% chance a customer cancels — by passing a weighted sum of inputs through an S-shaped curve. tolerate overlap. Without regularization, logistic regression's weights grow without bound on perfectly separable data.
Related
- perceptronperceptron, n.: One of the first learning machines: a single artificial neuron that sorts inputs into two groups by drawing a straight dividing line, nudging its weights whenever it guesses wrong.
- support vector machinesupport vector machine, n.: A classic method that separates two groups of examples with the widest possible gap — like laying the broadest possible road between them. A mathematical shortcut lets it draw curved boundaries too.
- kernel trickkernel trick, n.: A mathematical shortcut that lets simple straight-line methods find curved patterns, by computing similarities between examples as if the data had been mapped into a far richer space — without ever building that space.
- decision boundarydecision boundary, n.: The dividing line, or surface, where a classifier switches from predicting one category to another. Simple models draw straight lines; flexible ones draw curves.
- Perceptrons (book)Perceptrons (book), prop. n.: A 1969 book by Marvin Minsky and Seymour Papert proving that simple one-layer neural networks cannot learn certain patterns. It is widely blamed for a decade-long slump in neural-network research.
- multilayer perceptronmultilayer perceptron, n.: A neural network made of several layers of artificial neurons, each connected to every neuron in the next layer. It is the simplest kind of deep network and a component of almost every modern model.
Sources
- Cover, T. M. (1965). Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition. IEEE Transactions on Electronic Computers, EC-14(3), 326–334.
- Minsky, M. & Papert, S. (1969). Perceptrons: An Introduction to Computational Geometry. MIT Press.
Mentioned in
decision boundarydecision boundary, n.: The dividing line, or surface, where a classifier switches from predicting one category to another. Simple models draw straight lines; flexible ones draw curves., Frank RosenblattFrank Rosenblatt, prop. n.: An American psychologist who invented the perceptron, the first neural network that learned from examples, and built a machine that learned to recognize simple images., kernel trickkernel trick, n.: A mathematical shortcut that lets simple straight-line methods find curved patterns, by computing similarities between examples as if the data had been mapped into a far richer space — without ever building that space., marginmargin, n.: How far, and on which side, an example lies from a classifier's dividing line. A wide gap between the line and the nearest examples suggests the classifier will handle new data well., perceptronperceptron, n.: One of the first learning machines: a single artificial neuron that sorts inputs into two groups by drawing a straight dividing line, nudging its weights whenever it guesses wrong., support vector machinesupport vector machine, n.: A classic method that separates two groups of examples with the widest possible gap — like laying the broadest possible road between them. A mathematical shortcut lets it draw curved boundaries too., XOR problemXOR problem, n.: The classic puzzle of teaching a single artificial neuron the 'one or the other but not both' rule. It cannot be done with one straight dividing line, which showed why networks need hidden layers.