Abstract
Machine Learning today offers a broad repertoire of methods for classification and regression. But what if we need to predict complex objects like trees, orderings, or alignments? Such problems arise naturally in natural language processing, search engines, and bioinformatics. The following explores a generalization of Support Vector Machines (SVMs) for such complex prediction problems.
- Baeza-Yates, R., Ribeiro-Neto, B. Modern Information Retrieval. Addison-Wesley-Longman, Harlow, UK (May 1999). Google ScholarDigital Library
- Cai, L., Hofmann, T. Hierarchical document categorization with support vector machines. In Proceedings of the ACM Conference on Information and Knowledge Management (CIKM) (2004). Google ScholarDigital Library
- Chakrabarti, S., Khanna, R., Sawant, U., Battacharyya, C. Structured learning for non-smooth ranking losses. In ACM Conference on Knowledge Discovery and Data Mining (KDD) (2008). Google ScholarDigital Library
- Chapelle, O., Le, Q., Smola, A. Large margin optimization of ranking measures. In NIPS Workshop on Machine Learning for Web Search (2007).Google Scholar
- Collins, M. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Empirical Methods in Natural Language Processing (EMNLP) (2002), 1--8. Google ScholarDigital Library
- Crammer, K., Singer, Y. On the algorithmic implementation of multiclass kernel-based vector machines. J. Mach. Learn. Res. (JMLR) 2 (2001), 265--292. Google ScholarDigital Library
- Finley, T., Joachims, T. Supervised clustering with support vector machines. In International Conference on Machine Learning (ICML) (2005), 217--224. Google ScholarDigital Library
- Finley, T., Joachims, T. Training structural SVMs when exact inference is intractable. In International Conference on Machine Learning (ICML) (2008), 304--311. Google ScholarDigital Library
- Hastie, T., Tibshirani, R., Friedman, J. The Elements of Statistical Learning. Springer (2001).Google Scholar
- Hofmann, T., Schölkopf, B., Smola A.J. Kernel methods in machine learning. Ann. Stat. 36, 3 (2008), 1171--1220.Google ScholarCross Ref
- Joachims, T. Learning to Classify Text Using Support Vector Machines - Methods, Theory, and Algorithms. Kluwer/Springer (2002). Google ScholarDigital Library
- Joachims, T. A support vector method for mulivariate performance measures. In International Conference on Machine Learning (ICML) (2005), 377--384. Google ScholarDigital Library
- Joachims, T. Training linear SVMs in linear time. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) (2006), 217--226. Google ScholarDigital Library
- Joachims, T., Finley, T., Yu, C.-N. Cutting-plane training of structural svms. Machine Learning Journal (2009) DOI 10.1007/S 10994-009-5108-8 Google ScholarDigital Library
- Khuller, S., Moss, A., Naor, J. The budgeted maximum coverage problem. Inform. Process. Lett. 70, 1 (1997), 39--45. Google ScholarDigital Library
- Lafferty, J., McCallum, A., Pereira, F. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In International Conference on Machine Learning (ICML) (2001). Google ScholarDigital Library
- LeCun, Y., Bottou, L., Bengio, Y., Haffner, P. Gradient-based learning applied to document recognition. Proc. IEEE 86, 11 (1998), 2278--2324, November.Google ScholarCross Ref
- McCallum, A., Freitag, D., Pereira, F. Maximum entropy Markov models for information extraction and segmentation. In International Conference on Machine Learning (ICML) (2000), 591--598. Google ScholarDigital Library
- Meller, J., Elber, R. Linear programming optimization and a double statistical filter for protein threading protocols. Proteins Struct. Funct. Genet. 45 (2001), 241--261.Google ScholarCross Ref
- Qiu, J., Elber, R. SSALN: an alignment algorithm using structure-dependent substitution matrices and gap penalties learned from structurally aligned protein pairs. Proteins 62 (2006), 881--91.Google ScholarCross Ref
- Robertson, S., Walker, S., Jones, S., Hancock-Beaulieu, M., Gatford, M. Okapi at TREC-3. In Proceedings of TREC-3 (1994).Google Scholar
- Sha, F., Pereira, F. Shallow parsing with conditional random fields. In NAACL'03: Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology (Morristown, NJ, USA, 2003), 134--141. Association for Computational Linguistics. Google ScholarDigital Library
- Shindyalov, I.N., Bourne, P.E. Protein structure alignment by incremental combinatorial extension(CE) of the optimal path. Protein Eng. 11 (1998), 739--747.Google ScholarCross Ref
- Swaminathan, A., Mathew, C., Kirovski, D. Essential pages. Technical Report MSR-TR-2008--015, Microsoft Research (2008).Google Scholar
- Taskar, B., Guestrin, C., Koller, D. Maximum-margin markov networks. In Advances in Neural Information Processing Systems (NIPS) (2003).Google Scholar
- Tsochantaridis, I., Hofmann, T., Joachims, T., Altun, Y. Support vector machine learning for interdependent and structured output spaces. In International Conference on Machine Learning (ICML) (2004), 104--112. Google ScholarDigital Library
- Tsochantaridis, I., Joachims, T., Hofmann, T., Altun, Y. Large margin methods for structured and interdependent output variables. J. Mach. Learn. Res. (JMLR), 6 (September 2005), 1453--1484. Google ScholarDigital Library
- Yu, C.-N.J., Joachims, T. Training structural svms with kernels using sampled cuts. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) (2008), 794--802. Google ScholarDigital Library
- Yu, C.-N.J., Joachims, T., Elber, R., Pillardy, J. Support vector training of protein alignment models. J. Comput. Biol. 15, 7 (September 2008), 867--880.Google ScholarCross Ref
- Yue, Y., Finley, T., Radlinski, F., Joachims, T. A support vctor method for optimizing average precision. In ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) (2007), 271--278. Google ScholarDigital Library
- Yue, Y., Joachims, T. Predicting diverse subsets using structural SVMs. In International Conference on Machine Learning (ICML) (2008), 271--278. Google ScholarDigital Library
- Zhai, C., Cohen, W.W., Lafferty, J. Beyond independent relevance: Methods and evaluation metrics for subtopic retrieval. In Proceedings of the ACM Conference on Research and Development in Information Retrieval (SIGIR) (2003). Google ScholarDigital Library
- Zhang, Y., Skolnick, J. TM-align: A protein structure alignment algorithm based on TM-score. Nucleic Acids Res. 33 (2005), 2302--2309.Google ScholarCross Ref
Index Terms
- Predicting structured objects with support vector machines
Recommendations
Wavelet twin support vector machines based on glowworm swarm optimization
Twin support vector machine is a machine learning algorithm developing from standard support vector machine. The performance of twin support vector machine is always better than support vector machine on datasets that have cross regions. Recently ...
PAC-Bayes bounds for twin support vector machines
Twin support vector machines are regarded as a milestone in the development of support vector machines. Compared to standard support vector machines, they learn two nonparallel hyperplanes rather than one as in standard support vector machines for ...
Multitask centroid twin support vector machines
Twin support vector machines are a recently proposed learning method for binary classification. They learn two hyperplanes rather than one as in conventional support vector machines and often bring performance improvements. However, an inherent shortage ...
Comments