nips nips2010 nips2010-151 nips2010-151-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jie Luo, Francesco Orabona
Abstract: In many real world applications we do not have access to fully-labeled training data, but only to a list of possible labels. This is the case, e.g., when learning visual classifiers from images downloaded from the web, using just their text captions or tags as learning oracles. In general, these problems can be very difficult. However most of the time there exist different implicit sources of information, coming from the relations between instances and labels, which are usually dismissed. In this paper, we propose a semi-supervised framework to model this kind of problems. Each training sample is a bag containing multi-instances, associated with a set of candidate labeling vectors. Each labeling vector encodes the possible labels for the instances in the bag, with only one being fully correct. The use of the labeling vectors provides a principled way not to exclude any information. We propose a large margin discriminative formulation, and an efficient algorithm to solve it. Experiments conducted on artificial datasets and a real-world images and captions dataset show that our approach achieves performance comparable to an SVM trained with the ground-truth labels, and outperforms other baselines.
[1] S. Andrews, I. Tsochantaridis, and T. Hofmann. Support vector machines for multiple-instance learning. In Proc. NIPS, 2003.
[2] K. Barnard, P. Duygulu, D. Forsyth, N. de Freitas, D. Blei, and M. Jordan. Matching words and pictures. JMLR, 3:1107–1135, 2003.
[3] T. Berg, A. Berg, J. Edwards, and D. Forsyth. Who’s in the picture? In Proc. NIPS, 2004.
[4] D. P. Bertsekas. Convex Analysis and Optimization. Athena Scientific, 2003.
[5] R. C. Bunescu and R. J. Mooney. Multiple instance learning for sparse positive bags. In Proc. ICML, 2007.
[6] C. C. Chang and C. J. Lin. LIBSVM: A Library for Support Vector Machines, 2001. Software available at http://www.csie.ntu.edu.tw/˜cjlin/libsvm.
[7] O. Chapelle, A. Zien, and B. Sch¨ lkopf (Eds.). Semi-supervised Learning. MIT Press, 2006. o
[8] T. Cour, B. Sapp, C. Jordan, and B. Taskar. Learning from ambiguously labeled images. In Proc. CVPR, 2009.
[9] K. Crammer and Y. Singer. On the algorithmic implementation of multiclass kernel-based vector machines. JMLR, 2:265–292, 2001.
[10] T. G. Dietterich, R. H. Lathrop, T. Lozano-Perez, and A. Pharmaceutical. Solving the multipleinstance problem with axis-parallel rectangles. Artificial Intelligence, 39:31–71, 1997.
[11] R.-E. Fan, K.-W. Chang, C.-J. Lin, S. S. Keerthi, and S. Sundarajan. LIBLINEAR: A library for large linear classification. JMLR, 9:1871–1874, 2008.
[12] Y. Grandvalet. Logistic regression for partial labels. In Proc. IPMU, 2002.
[13] M. Guillaumin, J. Verbeek, and C. Schmid. Multiple instance metric learning from automatically labeled bags of faces. In Proc. ECCV, 2010.
[14] A. Gupta and L. Davis. Beyond nouns: Exploiting prepositions and comparative adjectives for learning visual classifiers. In Proc. ECCV, 2008.
[15] E. H¨ llermeier and J. Beringe. Learning from ambiguously labelled example. Intelligent Data u Analysis, 10:419–439, 2006.
[16] L. Jie, B. Caputo, and V. Ferrari. Who’s doing what: Joint modeling of names and verbs for simultaneous face and pose annotation. In Proc. NIPS, 2009.
[17] R. Jin and Z. Ghahramani. Learning with multiple labels. In Proc. NIPS, 2002.
[18] S. Shalev-Shwartz, Y. Singer, and N. Srebro. Pegasos: Primal Estimated sub-GrAdient SOlver for SVM. In Proc. ICML, 2007.
[19] A. J. Smola, S. V. N. Vishwanathan, and T. Hofmann. Kernel methods for missing variables. In Proc. AISTAT, 2005.
[20] I. Tsochantaridis, T. Joachims, T. Hofmann, and Y. Altun. Large margin methods for structured and interdependent output variables. JMLR, 6:1453–1484, 2005.
[21] E.P Xing, A.Y. Ng, M.I. Jordan, and S. Russell. Distance metric learning with application to clustering with side-information. In Proc. NIPS, 2002.
[22] C.-N. Yu and T. Joachims. Learning structural svms with latent variables. In Proc. ICML, 2009.
[23] A. Yuille and A. Rangarajan. The concave-convex procedure. Neural Computation, 15:915– 936, 2003.
[24] M.-L. Zhang and Z.-H. Zhou. M3 MIML: A maximum margin method for multi-instance multilabel learning. In Proc. ICDM, 2008.
[25] Z.-H. Zhou and M.-L. Zhang. Multi-instance multi-label learning with application to scene classification. In Proc. NIPS, 2006.
[26] X. Zhu. Semi-supervised learning literature survey. Technical Report 1530, Computer Sciences, University of Wisconsin-Madison, 2005. 9