Maximum Entropy & SVMs in NLP (1996) › Support Vector Machines: Optimal Boundaries

Support Vector Machines provided a complementary approach to the feature integration challenge. Developed by Vladimir Vapnik and colleagues starting in the 1960s and refined in the 1990s, SVMs found optimal decision boundaries separating different classes in high-dimensional feature spaces. Rather than modeling probability distributions, SVMs learned deterministic classifiers that made hard decisions about class membership. This perspective proved particularly effective for tasks like text classification and, with appropriate encoding, sequence labeling.

The core idea was finding the maximum-margin hyperplane, the decision boundary that maximized the distance to the nearest training examples from each class. This maximum-margin principle led to good generalization: the classifier was positioned as far as possible from ambiguous cases, making it reliable to small variations in input. SVMs could handle high-dimensional feature spaces naturally through the kernel trick, mapping inputs to even higher-dimensional spaces where linear separation became possible. For NLP, where feature spaces were naturally high-dimensional and sparse, this property was central.

Applying SVMs to NLP tasks required encoding problems appropriately. For text classification, determining whether a document was about sports, politics, science, etc., documents could be represented as high-dimensional vectors where each dimension corresponded to a word or feature, with values indicating presence or frequency. SVMs learned hyperplanes in this space separating documents of different classes. For sequence labeling tasks like tagging, researchers developed encoding schemes representing tagging decisions as classification problems: predict the tag for word $i$ given features derived from the sentence context. Structured prediction techniques extended SVMs to handle sequences directly, learning to score entire tag sequences rather than individual tags.

SVMs showed remarkable performance on text classification benchmarks. In experiments comparing different machine learning algorithms, SVMs consistently achieved among the highest accuracies and generalized well to unseen data. The approach's success stemmed from several factors. The maximum-margin principle led to good generalization even with limited training data. The kernel trick enabled capturing complex feature interactions implicitly, without explicitly constructing high-order feature combinations. The optimization framework was well-understood, with efficient algorithms available. SVMs avoided the overfitting problems that plagued some other approaches, finding stable, generalizable decision boundaries.

For sequence labeling, SVMs required more sophisticated encoding. The standard approach represented tagging as a sequence of classification decisions, with features for each decision including the current word, surrounding words, word shapes, morphological properties, and previous tag predictions. Structured SVMs extended this further, learning to score complete tag sequences by considering dependencies between tags. These extensions, while computationally more expensive than simple classification, captured important sequential structure while retaining SVM's generalization properties.

The feature representation for SVMs in NLP was typically sparse and high-dimensional. A sentence might be represented using thousands of binary features: indicators for specific words, word pairs, word shapes, morphological patterns, positional properties, and contextual configurations. SVMs handled this sparsity naturally. They only needed to consider support vectors, the training examples closest to the decision boundary, making learning efficient even with large feature sets. This property made SVMs particularly well-suited for NLP, where feature spaces were naturally sparse but high-dimensional.