nips nips2010 nips2010-236 nips2010-236-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Umar Syed, Ben Taskar
Abstract: We address the problem of semi-supervised learning in an adversarial setting. Instead of assuming that labels are missing at random, we analyze a less favorable scenario where the label information can be missing partially and arbitrarily, which is motivated by several practical examples. We present nearly matching upper and lower generalization bounds for learning in this setting under reasonable assumptions about available label information. Motivated by the analysis, we formulate a convex optimization problem for parameter estimation, derive an efficient algorithm, and analyze its convergence. We provide experimental results on several standard data sets showing the robustness of our algorithm to the pattern of missing label information, outperforming several strong baselines. 1
[1] Olivier Chapelle, Bernhard Sch¨ lkopf, and Alexander Zien, editors. Semi-Supervised Learning. MIT o Press, Cambridge, MA, 2006.
[2] Thomas G. Dietterich, Richard H. Lathrop, and Tom´ s Lozano-P´ rez. Solving the multiple instance a e problem with axis-parallel rectangles. Artificial Intelligence, 89(1-2):31–71, 1997.
[3] Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 7:2399–2434, 2006.
[4] Gregory Druck, Gideon Mann, and Andrew McCallum. Learning from labeled features using generalized expectation criteria. In Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 595–602, 2008.
[5] Michael Kearns and Ming Li. Learning in the presence of malicious errors. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 267–280, New York, NY, USA, 1988. ACM.
[6] Adam T. Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio. Agnostically learning halfspaces. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pages 11–20, 2005.
[7] Adam R. Klivans, Philip M. Long, and Rocco A. Servedio. Learning halfspaces with malicious noise. Journal of Machine Learning Research, 10:2715–2740, 2009.
[8] Maria-Florina Balcan and Avrim Blum. A PAC-style model for learning from labeled and unlabeled data. In Proceedings of the 18th Annual Conference on Learning Theory, pages 111–126, 2005.
[9] Rong Jin and Zoubin Ghahramani. Learning with multiple labels. In Advances in Neural Information Processing Systems 16, 2003.
[10] Timothee Cour, Ben Sapp, Chris Jordan, and Ben Taskar. Learning from ambiguously labeled images. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2009.
[11] Kuzman Ganchev, Jo˜ o Graca, Jennifer Gillenwater, and Ben Taskar. Posterior regularization for struca ¸ tured latent variable models. Journal of Machine Learning Research, 11:2001–2049, 2010.
[12] Percy Liang, Michael I. Jordan, and Dan Klein. Learning from measurements in exponential families. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 641–648, 2009.
[13] Rie Johnson and Tong Zhang. On the effectiveness of laplacian normalization for graph semi-supervised learning. Journal of Machine Learning Research, 8:1489–1517, December 2007.
[14] Philippe Rigollet. Generalization error bounds in semi-supervised classification under the cluster assumption. Journal of Machine Learning Research, 8:1369–1392, December 2007.
[15] Michael Collins, Amir Globerson, Terry Koo, Xavier Carreras, and Peter L. Bartlett. Exponentiated gradient algorithms for conditional random fields and max-margin markov networks. Journal of Machine Learning Research, 9:1775–1822, 2008.
[16] Jyrki Kivinen and Manfred K. Warmuth. Exponentiated gradient versus gradient descent for linear predictors. Inf. Comput., 132(1):1–63, 1997.
[17] Sameer A. Nene, Shree K. Nayar, and Hiroshi Murase. Columbia object image library (COIL-100). Technical Report CUCS-006-96, Columbia University, 1996.
[18] Thomas Navin Lal, Thilo Hinterberger, Guido Widman, Michael Schr¨ der, N. Jeremy Hill, Wolfgang o Rosenstiel, Christian Erich Elger, Bernhard Sch¨ lkopf, and Niels Birbaumer. Methods towards invasive o human brain computer interfaces. In Advances in Neural Information Processing Systems 17, 2004.
[19] Thorsten Joachims. Transductive inference for text classification using support vector machines. In Proceedings of the 16th International Conference on Machine Learning, pages 200–209, 1999.
[20] Gary B. Huang, Manu Ramesh, Tamara Berg, and Erik Learned-Miller. Labeled faces in the wild: A database for studying face recognition in unconstrained environments.
[21] Ben Taskar, Carlos Guestrin, and Daphne Koller. Max-margin markov networks. In Advances in Neural Information Processing Systems 16, 2004. 9