Support-vector networks
Cortes and Vapnik let the method be wrong on some examples, and it began working on real, non-separable data.
Why it matters
The method went from theory to working tool and for a decade was the first thing tried on a new problem.
The soft margin adds a penalty for each example on the wrong side of the boundary, and the penalty parameter governs the trade-off between margin width and number of errors. The authors showed handwritten digit results competitive with the Bell Labs networks. The theoretical support is Vapnik-Chervonenkis theory, which ties the complexity of a class to the amount of data required.