jmlr jmlr2013 jmlr2013-55 jmlr2013-55-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Mark Vere Culp, Kenneth Joseph Ryan
Abstract: The cluster assumption had a significant impact on the reasoning behind semi-supervised classification methods in graph-based learning. The literature includes numerous applications where harmonic functions provided estimates that conformed to data satisfying this well-known assumption, but the relationship between this assumption and harmonic functions is not as well-understood theoretically. We investigate these matters from the perspective of supervised kernel classification and provide concrete answers to two fundamental questions. (i) Under what conditions do semisupervised harmonic approaches satisfy this assumption? (ii) If such an assumption is satisfied then why precisely would an observation sacrifice its own supervised estimate in favor of the cluster? First, a harmonic function is guaranteed to assign labels to data in harmony with the cluster assumption if a specific condition on the boundary of the harmonic function is satisfied. Second, it is shown that any harmonic function estimate within the interior is a probability weighted average of supervised estimates, where the weight is focused on supervised kernel estimates near labeled cases. We demonstrate that the uniqueness criterion for harmonic estimators is sensitive when the graph is sparse or the size of the boundary is relatively small. This sets the stage for a third contribution, a new regularized joint harmonic function for semi-supervised learning based on a joint optimization criterion. Mathematical properties of this estimator, such as its uniqueness even when the graph is sparse or the size of the boundary is relatively small, are proven. A main selling point is its ability to operate in circumstances where the cluster assumption may not be fully satisfied on real data by compromising between the purely harmonic and purely supervised estimators. The competitive stature of the new regularized joint harmonic approach is established. Keywords: harmonic function, joint training, cluster assumption, s
S Abney. Semisupervised Learning for Computational Linguistics. Chapman and Hall, CRC, 2008. A Aswani, P Bickel, and C Tomlin. Regression on manifolds: estimation of the exterior derivative. Annals of Statistics, 39(1):48–81, 2010. M Azizyan, A Singh, and L Wasserman. Density-sensitive semisupervised inference. Annals of Statistics, 41(2):751–771, 2013. 3750 J OINT H ARMONIC F UNCTIONS M Belkin, P Niyogi, and V Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 7:2399–2434, 2006. M Bredel and E Jacoby. Chemogenomics: An emerging strategy for rapid target and drug discovery. Nature Reviews Genetics, 5(4):262–275, April 2004. M Carreira-Perpi˜ an and R Zemel. Proximity graphs for clustering and manifold learning. In n´ Advances in NIPs 18, pages 225–232, 2005. O Chapelle, M Chi, and A Zien. A continuation method for semi-supervised SVMs. In International Conference on Machine Learning, 2006a. O Chapelle, B Sch¨ lkopf, and A Zien. Semi-Supervised Learning. MIT Press, Cambridge, MA, o 2006b. URL http://www.kyb.tuebingen.mpg.de/ssl-book. C Cortes, M Mohri, D Pechyony, and A Rastogi. Stability of transductive regression algorithms. In International Conference of Machine Learning, 2008. M Culp. On the semi-supervised joint trained elastic net. Journal of Computational Graphics and Statistics, 22(2):300–318, 2013. M Culp, G Michailidis, and K Johnson. On multi-view learning with additive models. Annals of Applied Statistics, 3(1):545–571, 2009. P Doyle and J Snell. Random walks and electrical networks. Mathematical Association of America, 1984. A Frank and A Asuncion. UCI machine learning repository, http://archive.ics.uci.edu/ml. 2010. URL T Hastie, R Tibshirani, and J Friedman. The Elements of Statistical Learning (Data Mining, Inference and Prediction). Springer Verlag, 2001. M Hein, J Audibert, and U von Luxburg. From graphs to manifolds–weak and strong pointwise consistency of graph Laplacians. In Conference on Learning Theory, pages 470–485, 2005. A Izenman. Modern Multivariate Statistical Techniques: Regression, Classification, and Manifold Learning. Springer Verlag, 2008. T Jebara, J Wang, and S Chang. Graph construction and b-matching for semi-supervised learning. In International Conference of Machine Learning, 2009. I Koprinska, J Poon, J Clark, and J Chan. Learning to classify e-mail. Information Science, 177 (10):2167–2187, 2007. ISSN 0020-0255. M Kui, K Zhang, S Mehta, T Chen, and F Sun. Prediction of protein function using protein-protein interaction data. Journal of Computational Biology, 10:947–960, 2002. J Lafferty and L Wasserman. Statistical analysis of semi-supervised regression. In Advances in NIPS, pages 801–808. MIT Press, 2007. 3751 C ULP AND RYAN R Lundblad. Chemical Reagents for Protein Modification. CRC Press Inc., 2004. ISBN 084931983-8. A McCallum, K Nigam, J Rennie, and K Seymore. Automating the construction of internet portals with machine learning. Information Retrieval Journal, 3:127–163, 2000. D Meyer, E Dimitriadou, K Hornik, A Weingessel, and F Leisch. e1071: Functions of the Department of Statistics (e1071), TU Wien, 2012. http://CRAN.R-project.org/package=e1071. R package version 1.6-1. Misc URL B Nadler, N Srebro, and X Zhou. Statistical analysis of semi-supervised learning: The limit of infinite unlabelled data. In Advances in NIPs 22, pages 1330–1338. MIT Press, 2009. R Core Team. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, 2012. P Rigollet. Generalization error bounds in semi-supervised classification under the cluster assumption. Journal of Machine Learning Research, 8:1369–1392, 2007. A Singh, R Nowak, and X Zhu. Unlabeled data: Now it helps, now it doesn’t. In Advanced in NIPS, pages 1513–1520, 2008. A Subramanya and J Bilmes. Semi-supervised learning with measure propagation. Journal of Machine Learning Research, 12:3311–3370, 2011. U von Luxburg, A Radl, and M Hein. Hitting times, commute distances and the spectral gap for large random geometric graphs. Computing Research Repository, abs/1003.1266, 2010. J Wang and X Shen. Large margin semi-supervised learning. Journal of Machine Learning Research, 8:1867–1897, 2007. Y Yamanishi, J Vert, and M Kanehisa. Protein network inference from multiple genomic data: A supervised approach. Bioinformatics, 20:363–370, 2004. X Zhu. Semi-supervised learning literature survey. Technical report, Computer Sciences, University of Wisconsin-Madison, 2008. X Zhu and A Goldberg. Introduction to Semi-Supervised Learning. Morgan and Claypool Publishers, 2009. X Zhu, Z Ghahramani, and J Lafferty. Semi-supervised learning using Gaussian fields and harmonic functions. In International Conference on Machine Learning, pages 912–919, 2003. 3752