Stochastic scheduling of active support vector learning algorithms

ABSTRACT

Active learning is a generic approach to accelerate training of classifiers in order to achieve a higher accuracy with a small number of training examples. In the past, simple active learning algorithms like random learning and query learning have been proposed for the design of support vector machine (SVM) classifiers. In random learning, examples are chosen randomly, while in query learning examples closer to the current separating hyperplane are chosen at each learning step. However, it is observed that a better scheme would be to use random learning in the initial stages (more exploration) and query learning in the final stages (more exploitation) of learning. Here we present two novel active SV learning algorithms which use adaptive mixtures of random and query learning. One of the proposed algorithms is inspired by online decision problems, and involves a hard choice among the pure strategies at each step. The other extends this to soft choices using a mixture of instances recommended by the individual pure strategies. Both strategies handle the exploration-exploitation trade-off in an efficient manner. The efficacy of the algorithms is demonstrated by experiments on benchmark datasets.

REFERENCES

• 1: Yoram Baram , Ran El-Yaniv , Kobi Luz, Online Choice of Active Learning Algorithms, The Journal of Machine Learning Research, 5, p.255-291, 12/1/2004
• 2: C. L. Blake and C. J. Merz. UCI repository of machine learning databases, 1998.
• 3: K. Brinker. Incorporating diversity in active learning with support vector machines. In ICML, 2003.
• 4: Christopher J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, v.2 n.2, p.121-167, June 1998 [doi>10.1023/A:1009715923555]
• 5: Colin Campbell , Nello Cristianini , Alex J. Smola, Query Learning with Large Margin Classifiers, Proceedings of the Seventeenth International Conference on Machine Learning, p.111-118, June 29-July 02, 2000
• 6: David Cohn , Les Atlas , Richard Ladner, Improving Generalization with Active Learning, Machine Learning, v.15 n.2, p.201-221, May 1994 [doi>10.1023/A:1022673506211]
• 7: J. C. Gittins. Multi-armed Bandit Allocation Indices. John Wiley, 1989.
• 8: A. Kalai and S. Vempala. Efficient algorithms for the online decision problem. In COLT, 2003.
• 9: Nadeem Ahmed Syed , Huan Liu , Kah Kay Sung, A study of support vectors on model independent example selection, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.272-276, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312245]
• 10: R. Schapire, Y. Freund, P. Bartlett, and W. S. Lee. Boosting the margin: A new explanation for the effectiveness of voting methods. Annals of Statistics, 26:1651--1686, 1998.
• 11: Greg Schohn , David Cohn, Less is More: Active Learning with Support Vector Machines, Proceedings of the Seventeenth International Conference on Machine Learning, p.839-846, June 29-July 02, 2000
• 12: Simon Tong , Daphne Koller, Support vector machine active learning with applications to text classification, The Journal of Machine Learning Research, 2, p.45-66, 3/1/2002 [doi>10.1162/153244302760185243]
• 13: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995

INDEX TERMS

Keywords:
SVM, multi-arm bandit problem, pool based active learning, stochastic scheduling