Back

Support Vector Machine Active Learning with Applications to Text Classification

Simon TongD. Koller

article2001JMLR3,523 citations

Develops a principled active learning framework for Support Vector Machines based on version space reduction that drastically cuts the number of labeled examples needed for text classification across inductive and transductive settings.

Listen

The research addresses the high cost of labeling data for training classifiers in domains such as text categorization, where large amounts of unlabeled text are readily available but expert labeling is expensive. The authors developed and tested three pool-based active learning algorithms for support vector machines that select the most informative unlabeled instances to label next, rather than relying on random selection.

They motivated the approach theoretically by showing that queries which halve the version space—the set of hypotheses consistent with the labeled data—minimize the expected size of that space after each query. Three practical approximations were introduced: the Simple Margin method, which selects the instance closest to the current SVM hyperplane; the MaxMin Margin method, which chooses the instance expected to produce the largest minimum margin after labeling; and the Ratio Margin method, which balances the relative margins under both possible labels. Experiments were run on the Reuters-21578 and Newsgroups collections using pools of 500–1000 documents, with performance measured by test-set accuracy and precision-recall breakeven points, and results averaged over multiple random pools and repeated trials.

The three active methods performed similarly to one another and consistently outperformed random sampling, often reaching the accuracy level obtained from the entire pool after seeing only a small fraction of the data. In several Reuters categories, passive learning required more than six times as many labeled examples to match the active methods. Active learning also provided greater gains than switching from inductive to transductive SVMs. Larger unlabeled pools further improved results, and a hybrid strategy that applied the more expensive methods only for the first few queries preserved stability while keeping computation low.

These outcomes indicate that targeted querying can reduce labeling effort by an order of magnitude in practical text-classification tasks without sacrificing accuracy. The main limitations are that the Simple method occasionally performed poorly on certain topics and that the MaxMin and Ratio methods become computationally expensive as the labeled set grows. Further work on incremental SVM updates and multiple simultaneous queries would help scale the stronger methods to larger problems.

Stanford Universityactive learningsupport vectortext classificationActive LearningSupport Vector MachineVersion Space
Tong et al (2001).pdf
  • Paper: A training algorithm for optimal margin classifiers, B. Boser et al. (1992). Reading this foundational paper on optimal margin classifiers is essential for understanding the underlying quadratic programming framework and support vector mechanics that the source paper adapts for active learning.
  • Paper: Support-vector networks, Corinna Cortes et al. (1995). This seminal work on support-vector networks provides the core classification algorithms and optimization decomposition techniques upon which the source paper builds its pool-based active learning approach.
Cover for Support Vector Machine Active Learning with Applications to Text Classification

Abstract

Support vector machines have met with significant success in numerous real-world learning tasks. However, like most machine learning algorithms, they are generally applied using a randomly selected training set classified in advance. In many settings, we also have the option of using pool-based active learning. Instead of using a randomly selected training set, the learner has access to a pool of unlabeled instances and can request the labels for some number of them. We introduce a new algorithm for performing active learning with support vector machines, i.e., an algorithm for choosing which instances to request next. We provide a theoretical motivation for the algorithm using the notion of a version space. We present experimental results showing that employing our active learning method can significantly reduce the need for labeled training instances in both the standard inductive and transductive settings.

Topics

active learningsupport vectortext classificationtraining samplesvm

Keywords

Active LearningSupport Vector MachineVersion SpaceText ClassificationPool-Based SamplingSimple MarginMaxMin MarginRatio MarginTransductive SVMReuters-21578

Table of Contents

  • 1. Introduction
  • 2. Support Vector Machines
  • 2.1 SVMs for Induction
  • 2.2 SVMs for Transduction
  • 3. Version Space
  • 4. Active Learning
  • 5. Experiments
  • 5.1 Reuters Data Collection Experiments
  • 5.2 Newsgroups Experiments
  • 6. Related Work
  • 7. Conclusions and Future Work
  • Acknowledgments
  • References

Knowls

  1. Knowl 1 — Simple Margin Active Learning for Support Vector Machines

    algorithm

    The Simple Margin active learning algorithm selects the next query from an unlabeled pool by choosing the instance whose mapped feature vector is closest to the current SVM decision boundary. Under the duality between feature space F\mathcal{F} and parameter space W\mathcal{W}, an SVM unit weight vector wiw_i represents the center of the largest sphere fitting in the current version space Vi\mathcal{V}_i. The distance ∣wi⋅Φ(x)∣|w_i \cdot \Phi(x)| in feature space equals the distance in parameter space from wiw_i to the hyperplane defined by xx. Minimizing this distance selects the hyperplane that comes closest to centrally bisecting the current version space.

    Input: Initial labeled training set L = {(x_1, y_1), ..., (x_n, y_n)} where y_i in {-1, +1}
    Input: Unlabeled pool U = {x_1, ..., x_u}
    Input: Kernel operator K(u, v) = Phi(u) . Phi(v)
    Input: Total number of active queries T
    for t = 1 to T do
        Train an SVM on labeled set L with kernel K to obtain normal vector w_t
        x* = argmin_{x in U} |w_t . Phi(x)|
        Query oracle for true label y* of x*
        L = L union {(x*, y*)}
        U = U \ {x*}
    end for
    Train final SVM on L and return resulting classifier

    When evaluating ∣wt⋅Φ(x)∣|w_t \cdot \Phi(x)|, the value is computed using the dual SVM expansion ∣∑j=1∣L∣αjyjK(xj,x)∣\left|\sum_{j=1}^{|L|} \alpha_j y_j K(x_j, x)\right|. For batch querying of size kk, the algorithm selects the kk unlabeled instances with the smallest absolute values.

  2. Knowl 2 — MaxMin Margin and Ratio Margin Active Learning Algorithms

    algorithm

    When the version space V\mathcal{V} is asymmetric or elongated, the SVM center wiw_i does not necessarily lie in the geometric center of V\mathcal{V}, and a candidate hyperplane close to wiw_i may split V\mathcal{V} unevenly. The MaxMin Margin and Ratio Margin methods explicitly estimate the sizes of the two resulting version spaces V−\mathcal{V}^- (if candidate xx has label −1-1) and V+\mathcal{V}^+ (if candidate xx has label +1+1) using the resulting SVM margins m−(x)m^-(x) and m+(x)m^+(x) as proxies for version space radius.

    Input: Labeled training set L = {(x_1, y_1), ..., (x_n, y_n)}
    Input: Unlabeled pool U = {x_1, ..., x_u}
    Input: Query selection criterion Method in {MaxMin, Ratio}
    Input: Number of queries T
    for t = 1 to T do
        for each candidate instance x in U do
            Train SVM on L union {(x, -1)} and record its margin m^-(x)
            Train SVM on L union {(x, +1)} and record its margin m^+(x)
            if Method == MaxMin then
                Score(x) = min(m^-(x), m^+(x))
            else if Method == Ratio then
                Score(x) = min(m^-(x) / m^+(x), m^+(x) / m^-(x))
            end if
        end for
        x* = argmax_{x in U} Score(x)
        Query oracle for true label y* of x*
        L = L union {(x*, y*)}
        U = U \ {x*}
    end for
    Train final SVM on L and return resulting classifier

    MaxMin Margin maximizes min⁡(m−(x),m+(x))\min(m^-(x), m^+(x)) to avoid small version space cuts, while Ratio Margin maximizes min⁡(m−(x)m+(x),m+(x)m−(x))\min\left(\frac{m^-(x)}{m^+(x)}, \frac{m^+(x)}{m^-(x)}\right) to enforce an even split regardless of global version space elongation. For an unlabeled pool of size ss, each query step requires training 2s2s SVMs.

  3. Knowl 3 — Duality of Version Space and the Support Vector Machine Center

    theoretical result

    Let X⊆Rd\mathcal{X} \subseteq \mathbb{R}^d be an input space and F\mathcal{F} be the feature space induced by a Mercer kernel K(u,v)=Φ(u)⋅Φ(v)K(u,v) = \Phi(u) \cdot \Phi(v). Assume all feature vectors have constant norm ∥Φ(x)∥=λ\|\Phi(x)\| = \lambda. The hypothesis space is parameterized by unit vectors in W=F\mathcal{W} = \mathcal{F}:

    H={f | f(x)=w⋅Φ(x)∥w∥, w∈W}\mathcal{H} = \left\{ f \,\middle|\, f(x) = \frac{w \cdot \Phi(x)}{\|w\|}, \, w \in \mathcal{W} \right\}

    Given labeled instances {(x1,y1),…,(xn,yn)}\{(x_1, y_1), \dots, (x_n, y_n)\} with yi∈{−1,+1}y_i \in \{-1, +1\}, the version space V\mathcal{V} is the set of consistent hypotheses:

    V={w∈W∣∥w∥=1, yi(w⋅Φ(xi))>0, i=1,…,n}\mathcal{V} = \{w \in \mathcal{W} \mid \|w\| = 1, \, y_i (w \cdot \Phi(x_i)) > 0, \, i = 1, \dots, n\}

    Under duality between F\mathcal{F} and W\mathcal{W}, each training point Φ(xi)\Phi(x_i) defines a bounding hyperplane w⋅Φ(xi)=0w \cdot \Phi(x_i) = 0 on the unit sphere in W\mathcal{W} with normal vector Φ(xi)/λ\Phi(x_i)/\lambda. The maximal margin SVM solution w∗=arg⁡max⁡w∈Vmin⁡iyi(w⋅Φ(xi))w^* = \arg\max_{w \in \mathcal{V}} \min_i y_i (w \cdot \Phi(x_i)) corresponds exactly to the center of the largest radius hypersphere that can be inscribed in V\mathcal{V} without intersecting its bounding hyperplanes. The radius of this inscribed sphere is equal to m/λm / \lambda, where mm is the margin of the SVM in feature space F\mathcal{F}, and the bounding hyperplanes touched by the sphere correspond to the support vectors.

  4. Knowl 4 — Optimality of Version Space Halving under Worst-Case Label Distributions

    theoretical result

    Let Area(V)\text{Area}(\mathcal{V}) denote the surface area occupied by version space V\mathcal{V} on the unit hypersphere ∥w∥=1\|w\| = 1 in a finite rr-dimensional parameter space W\mathcal{W}. For an active learner after ii queries, let Vi−\mathcal{V}_i^- and Vi+\mathcal{V}_i^+ denote the version spaces resulting from assigning label −1-1 and +1+1 to query xi+1x_{i+1}, respectively.

    Let P\mathcal{P} denote the set of all conditional distributions P(y∣x)P(y \mid x) of labels given instances. If an active learner ℓ∗\ell^* always selects queries whose corresponding hyperplanes in W\mathcal{W} halve the surface area of the current version space (such that Area(Vi+1∗)=12Area(Vi∗)\text{Area}(\mathcal{V}_{i+1}^*) = \frac{1}{2} \text{Area}(\mathcal{V}_i^*) for every query), and ℓ\ell is any other active learner, then for all query counts i∈N+i \in \mathbb{N}^+:

    sup⁡P∈PEP[Area(Vi∗)]≤sup⁡P∈PEP[Area(Vi)]\sup_{P \in \mathcal{P}} \mathbb{E}_P[\text{Area}(\mathcal{V}_i^*)] \le \sup_{P \in \mathcal{P}} \mathbb{E}_P[\text{Area}(\mathcal{V}_i)]

    Strict inequality holds whenever there exists a query step j∈{1,…,i}j \in \{1, \dots, i\} at which ℓ\ell selects an instance that fails to bisect Vj−1\mathcal{V}_{j-1}.

  5. Knowl 5 — Hybrid Margin Active Learning Strategy

    model/method

    The Hybrid Margin active learning method combines the exploration properties of the Ratio (or MaxMin) Margin method with the computational efficiency of the Simple Margin method.

    During early query rounds (e.g., the first 10 queries), when the labeled training set is very small and the risk of the Simple Margin getting stuck in local regions or missing disconnected clusters is highest, the learner executes the Ratio Margin algorithm. Because the labeled set is small, solving 2s2s SVM optimization problems per step is fast (taking a few seconds for a pool of s=500s=500).

    Once the version space has been broadly bounded and initial cluster representatives have been identified (after 10 queries), the learner switches to the Simple Margin algorithm for all subsequent queries. Because Simple Margin only evaluates the distance ∣w⋅Φ(x)∣|w \cdot \Phi(x)| without retraining SVMs across the pool, per-query computation remains under a fraction of a second even as the labeled dataset grows.

  6. Knowl 6 — Sample Complexity Reduction on Reuters-21578 Text Classification

    empirical result

    On the Reuters-21578 text collection (using the ModApte split, top 10 categories, TFIDF word vectors of dimension ≈10000\approx 10000, and a linear kernel), active SVM learning dramatically outperforms passive random sampling.

    When initialized with 1 positive and 1 negative document and allowed 8 active queries (total 10 labeled documents), active learning achieves classification accuracy and precision/recall breakeven points that require substantially more randomly sampled documents:

    • On the top 10 categories, passive learning requires an average of over 6 times as much labeled data to reach the performance achieved by the Ratio active method.
    • For infrequent topics (e.g., Acq, Crude, Trade, Interest, Ship, Wheat), passive sampling requires >100>100 labeled documents to match the precision/recall breakeven score achieved by active learning with only 10 labeled documents.
    • Performance gains of active sampling are not caused by class balance alone: an artificial baseline ('BalancedRandom') that randomly draws equal numbers of positive and negative documents achieves significantly worse initial accuracy (<50%<50\%) and lower precision/recall curves than the active SVM methods.

  7. Knowl 7 — Simple Margin Instability and Cluster Miss Vulnerability

    limitation

    The Simple Margin active learning heuristic assumes that the version space V\mathcal{V} is symmetric and that the SVM weight vector wiw_i is placed at its geometric center. When the unlabeled data contain isolated clusters in feature space, the current hyperplane may lie far from an unrepresented cluster, assigning high confidence (∣wi⋅Φ(x)∣≫0|w_i \cdot \Phi(x)| \gg 0) to all its points.

    In experiments on the 20 Newsgroups dataset (comp.* subcategories with pool size 500), this behavior causes failure modes:

    • In 10% to 15% of experimental runs on categories comp.sys.ibm.pc.hardware and comp.os.ms-windows.misc, the Simple Margin method was misled by failing to explore unlabeled clusters, yielding test set accuracy as low as 25% after 50 labeled examples (worse than random guessing).
    • In contrast, the MaxMin and Ratio Margin methods avoid this trap by testing both hypothetical labels for every candidate point, which forces immediate querying of separate clusters where neither label produces a viable large-margin SVM.

  8. Knowl 8 — Computational Run Times of Active SVM Query Strategies

    data/table

    Empirical runtime benchmarks illustrate the scalability trade-off between Simple, MaxMin, Ratio, and Hybrid active learning methods. Measurements were recorded on a Sun Ultra 60 450 MHz workstation evaluating a pool of 500 text documents from the 20 Newsgroups corpus.

    Query Number Simple (s) MaxMin (s) Ratio (s) Hybrid (s)
    1 0.008 3.7 3.7 3.7
    5 0.018 4.1 5.2 5.2
    10 0.025 12.5 8.5 8.5
    20 0.045 13.6 19.9 0.045
    30 0.068 22.5 23.9 0.073
    50 0.110 23.2 23.3 0.115
    100 0.188 42.8 43.2 0.200

    Simple Margin scales efficiently across queries because candidate evaluation requires only inner products ∣w⋅Φ(x)∣|w \cdot \Phi(x)|. MaxMin and Ratio become computationally expensive as labeled set size grows, requiring over 40 seconds per query at 100 queries due to 2s=10002s = 1000 SVM retrainings. The Hybrid strategy (Ratio for queries 1–10, Simple thereafter) achieves the low per-query runtime of Simple Margin while preserving the classification stability of Ratio Margin.

  9. Knowl 9 — Active Querying versus Transductive SVM Inference

    empirical result

    In a transductive setting on the Reuters-21578 dataset where performance is measured directly on the remaining unlabeled pool of 1000 documents, active querying provides a substantially larger performance improvement than transductive inference alone:

    • Incorporating unlabeled data via a Transductive SVM (TSVM) improves precision/recall breakeven performance over standard inductive SVMs under both passive and active selection.
    • However, an active inductive SVM querying 20 labeled instances achieves a precision/recall breakeven point of approximately 70%70\%, matching the performance of a transductive SVM trained on over 100 randomly sampled instances.
    • Combining active learning with transductive inference (Transductive Active) achieves the highest overall breakeven performance, exceeding 85%85\% with 50 queries and over 90%90\% with 100 queries.

  10. Knowl 10 — Superiority of Active SVM over Committee-Based Active Learning

    empirical result

    When evaluated on the Reuters-21578 corpus under identical experimental setups, active learning with SVMs outperforms established probabilistic and committee-based active learning algorithms:

    • Compared to the Query-by-Committee with Naive Bayes (MN-algorithm of McCallum and Nigam, 1998) querying batches of 5 instances on categories Corn, Trade, and Acq, the SVM Simple Active method achieves consistently higher precision/recall breakeven points across all query counts (e.g., reaching >75%>75\% breakeven at 100 documents versus ≈60%\approx 60\% for the MN-algorithm).
    • Compared to the Query-by-Committee with Winnow classifiers (LT-algorithm of Liere and Tadepalli, 1997) initialized with 150 random instances, the SVM Simple Active method achieves substantially higher classification accuracy across the top 10 categories (reaching >95%>95\% accuracy at 300 instances compared to ≈75%\approx 75\% for the Winnow active method).

Coverage note — None omitted; all primary theoretical motivations (version space duality, halving optimality), algorithms (Simple, MaxMin, Ratio, Hybrid), and empirical evaluations (inductive, transductive, newsgroups stability, and committee baselines) are covered.

References

  1. 1.C. J.C. Burges. A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 2:121–167, 1998.
  2. 2.C. Campbell, N. Cristianini, and A. Smola. Query learning with large margin classifiers. In Proceedings of the Seventeenth International Conference on Machine Learning, 2000.
  3. 3.G Cauwenberghs and T. Poggio. Incremental and decremental support vector machine learning. In Advances in Neural Information Processing Systems, volume 13, 2001.
  4. 4.C. Cortes and V. Vapnik. Support vector networks. Machine Learning, 20:1–25, 1995.
  5. 5.I. Dagan and S. Engelson. Committee-based sampling for training probabilistic classifiers. In Proceedings of the Twelfth International Conference on Machine Learning, pages 150–157. Morgan Kaufmann, 1995.
  6. 6.S.T. Dumais, J. Platt, D. Heckerman, and M. Sahami. Inductive learning algorithms and representations for text categorization. In Proceedings of the Seventh International Conference on Information and Knowledge Management. ACM Press, 1998.
  7. 7.Y. Freund, H. Seung, E. Shamir, and N. Tishby. Selective sampling using the query by committee algorithm. Machine Learning, 28:133–168, 1997.
  8. 8.D. Heckerman, J. Breese, and K. Rommelse. Troubleshooting Under Uncertainty. Technical Report MSR-TR-94-07, Microsoft Research, 1994.
  9. 9.R. Herbrich, T. Graepel, and C. Campbell. Bayes point machines. Journal of Machine Learning Research, pages 245–279, 2001.
  10. 10.E. Horvitz and G. Rutledge. Time dependent utility and action under uncertainty. In Proceedings of the Seventh Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann, 1991.
  11. 11.T. Joachims. Text categorization with support vector machines. In Proceedings of the European Conference on Machine Learning. Springer-Verlag, 1998.
  12. 12.T. Joachims. Making large-scale svm learning practical. In B. Schölkopf, C. Burges, and A. Smola, editors, Advances in Kernel Methods - Support Vector Learning. MIT Press, 1999a.
  13. 13.T. Joachims. Transductive inference for text classification using support vector machines. In Proceedings of the Sixteenth International Conference on Machine Learning, pages 200–209. Morgan Kaufmann, 1999b.
  14. 14.K. Lang. Newsweeder: Learning to filter netnews. In International Conference on Machine Learning, pages 331–339, 1995.
  15. 15.Jean-Claude Latombe. Robot Motion Planning. Kluwer Academic Publishers, 1991.
  16. 16.D. Lewis and J. Catlett. Heterogeneous uncertainty sampling for supervised learning. In Proceedings of the Eleventh International Conference on Machine Learning, pages 148–156. Morgan Kaufmann, 1994.
  17. 17.D. Lewis and W. Gale. A sequential algorithm for training text classifiers. In Proceedings of the Seventeenth Annual International ACM-SIGIR Conference on Research and Development in Information Retrieval, pages 3–12. Springer-Verlag, 1994.
  18. 18.D. McAllester. PAC-Bayesian model averaging. In Proceedings of the Twelfth Annual Conference on Computational Learning Theory, 1999.
  19. 19.A. McCallum. Bow: A toolkit for statistical language modeling, text retrieval, classification and clustering. www.cs.cmu.edu/~mccallum/bow, 1996.
  20. 20.A. McCallum and K. Nigam. Employing EM in pool-based active learning for text classification. In Proceedings of the Fifteenth International Conference on Machine Learning. Morgan Kaufmann, 1998.
  21. 21.T. Mitchell. Generalization as search. Artificial Intelligence, 28:203–226, 1982.
  22. 22.J. Rocchio. Relevance feedback in information retrieval. In G. Salton, editor, The SMART retrieval system: Experiments in automatic document processing. Prentice-Hall, 1971.
  23. 23.G. Schohn and D. Cohn. Less is more: Active learning with support vector machines. In Proceedings of the Seventeenth International Conference on Machine Learning, 2000.
  24. 24.Fabrizio Sebastiani. Machine learning in automated text categorisation. Technical Report IEI-B4-31-1999, Istituto di Elaborazione dell’Informazione, 2001.
  25. 25.H.S. Seung, M. Opper, and H. Sompolinsky. Query by committee. In Proceedings of Computational Learning Theory, pages 287–294, 1992.
  26. 26.J. Shawe-Taylor and N. Cristianini. Further results on the margin distribution. In Proceedings of the Twelfth Annual Conference on Computational Learning Theory, pages 278–285, 1999.
  27. 27.V. Vapnik. Estimation of Dependences Based on Empirical Data. Springer Verlag, 1982.
  28. 28.V. Vapnik. Statistical Learning Theory. Wiley, 1998.

Citation

MLA
Tong, S., and D. Koller. “Support Vector Machine Active Learning with Applications to Text Classification”. Journal of Machine Learning Research, vol. 2, no. Nov, 2001, pp. 45–66, https://www.jmlr.org/papers/v2/tong01a.html.
APA
Tong, S., & Koller, D. (2001). Support Vector Machine Active Learning with Applications to Text Classification. Journal of Machine Learning Research, 2(Nov), 45–66. https://www.jmlr.org/papers/v2/tong01a.html
Chicago
Tong, S., and D. Koller. 2001. “Support Vector Machine Active Learning with Applications to Text Classification”. Journal of Machine Learning Research 2 (Nov): 45–66. https://www.jmlr.org/papers/v2/tong01a.html.
Harvard
Tong, S. and Koller, D. (2001) “Support Vector Machine Active Learning with Applications to Text Classification”, Journal of Machine Learning Research, 2(Nov), pp. 45–66. Available at: https://www.jmlr.org/papers/v2/tong01a.html.
Vancouver
1. Tong S, Koller D (2001) Support Vector Machine Active Learning with Applications to Text Classification. Journal of Machine Learning Research 2:45–66

BibTeX

@article{tong2001support,
  title = {Support Vector Machine Active Learning with Applications to Text Classification},
  author = {Tong, Simon and Koller, Daphne},
  year = {2001},
  journal = {Journal of Machine Learning Research},
  volume = {2},
  number = {Nov},
  pages = {45-66},
  url = {https://www.jmlr.org/papers/v2/tong01a.html}
}
Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF