nips nips2011 nips2011-181 nips2011-181-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Dan Zhang, Yan Liu, Luo Si, Jian Zhang, Richard D. Lawrence
Abstract: Most existing Multiple-Instance Learning (MIL) algorithms assume data instances and/or data bags are independently and identically distributed. But there often exists rich additional dependency/structure information between instances/bags within many applications of MIL. Ignoring this structure information limits the performance of existing MIL algorithms. This paper explores the research problem as multiple instance learning on structured data (MILSD) and formulates a novel framework that considers additional structure information. In particular, an effective and efficient optimization algorithm has been proposed to solve the original non-convex optimization problem by using a combination of ConcaveConvex Constraint Programming (CCCP) method and an adapted Cutting Plane method, which deals with two sets of constraints caused by learning on instances within individual bags and learning on structured data. Our method has the nice convergence property, with specified precision on each set of constraints. Experimental results on three different applications, i.e., webpage classification, market targeting, and protein fold identification, clearly demonstrate the advantages of the proposed method over state-of-the-art methods. 1
[1] S. Andrews, I. Tsochantaridis, and T. Hofmann. Support vector machines for multiple-instance learning. In NIPS, 2003.
[2] S.P. Boyd and L. Vandenberghe. Convex optimization. Cambridge Univ Press, 2004.
[3] B.Scholkopf and A.Smola. Learning with Kernels. MITPress, Cambridge, MA, 2002.
[4] T. G. Dietterich, R. H. Lathrop, and T. Lozano-Perez. Solving the multiple instance problem with axis-parallel rectangles. In Artificial Intelligence, 1998.
[5] T. G¨ rtner, P.A. Flach, A. Kowalczyk, and A.J. Smola. Multi–instance kernels. In ICML, 2002. a
[6] T. Joachims. Training linear SVMs in linear time. In KDD, 2006.
[7] T. Joachims, T. Finley, and C.N.J. Yu. Cutting-plane training of structural SVMs. Machine Learning, 2009.
[8] JE Kelley Jr. The cutting-plane method for solving convex programs. JSIAM, 1960.
[9] Krzysztof C. Kiwiel. Proximity control in bundle methods for convex nondifferentiable minimization. Math. Program., 46:105–122, 1990.
[10] Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schtze. Introduction to Information Retrieval. Cambridge University Press, 2008.
[11] Amy McGovern and David Jensen. Identifying predictive structures in relational data using multiple instance learning. In ICML, 2003.
[12] G.J. Qi, X.S. Hua, Y. Rui, T. Mei, J. Tang, and H.J. Zhang. Concurrent multiple instance learning for image categorization. In CVPR, 2007.
[13] R. Rahmani and S.A. Goldman. MISSL: Multiple-instance semi-supervised learning. In ICML, 2006.
[14] A.J. Smola, SVN Vishwanathan, and T. Hofmann. Kernel methods for missing variables. In AISTATS, 2005.
[15] Qingping Tao, Stephen D. Scott, N. V. Vinodchandran, and Thomas Takeo Osugi. Svm-based generalized multiple-instance learning via approximate box counting. In ICML, 2004.
[16] Benjamin Taskar, Carlos Guestrin, and Daphne Koller. Max-margin markov networks. In NIPS, 2003.
[17] I. Tsochantaridis, T. Joachims, T. Hofmann, and Y. Altun. Large margin methods for structured and interdependent output variables. JMLR, 2006.
[18] Chun-Nam John Yu and T. Joachims. Learning structural svms with latent variables. In ICML, 2009.
[19] A. Yuille and A. Rangarajan. The concave-convex procedure. Neural Computation, 2003.
[20] D. Zhou, J. Huang, and B. Scholkopf. Learning from labeled and unlabeled data on a directed graph. In ICML, 2005.
[21] Z-H Zhou, Y-Y Sun, and Y-F Li. Multi-instance learning by treating instances as non i.i.d. samples. In ICML, 2009.
[22] S-H Zhu, K. Yu, Y. Chi, and Y-H Gong. Combining content and link classification using matrix factorization. In SIGIR, 2007. 9