<!DOCTYPE html>
<html>
<head>
<meta charset=utf-8>
<title>82 nips-2009-Entropic Graph Regularization in Non-Parametric Semi-Supervised Classification</title>
</head>

<body>
<p><a title="nips" href="../nips_home.html">nips</a> <a title="nips-2009" href="../home/nips2009_home.html">nips2009</a> <a title="nips-2009-82" href="../nips2009/nips-2009-Entropic_Graph_Regularization_in_Non-Parametric_Semi-Supervised_Classification.html">nips2009-82</a> <a title="nips-2009-82-reference" href="#">nips2009-82-reference</a> knowledge-graph by maker-knowledge-mining</p><script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
<!-- maker adsense -->
<ins class="adsbygoogle"
     style="display:inline-block;width:728px;height:90px"
     data-ad-client="ca-pub-5027806277543591"
     data-ad-slot="4192012269"></ins>
<script>
(adsbygoogle = window.adsbygoogle || []).push({});
</script>
<h1>82 nips-2009-Entropic Graph Regularization in Non-Parametric Semi-Supervised Classification</h1>
<br/><p>Source: <a title="nips-2009-82-pdf" href="http://papers.nips.cc/paper/3739-entropic-graph-regularization-in-non-parametric-semi-supervised-classification.pdf">pdf</a></p><p>Author: Amarnag Subramanya, Jeff A. Bilmes</p><p>Abstract: We prove certain theoretical properties of a graph-regularized transductive learning objective that is based on minimizing a Kullback-Leibler divergence based loss. These include showing that the iterative alternating minimization procedure used to minimize the objective converges to the correct solution and deriving a test for convergence. We also propose a graph node ordering algorithm that is cache cognizant and leads to a linear speedup in parallel computations. This ensures that the algorithm scales to large data sets. By making use of empirical evaluation on the TIMIT and Switchboard I corpora, we show this approach is able to outperform other state-of-the-art SSL approaches. In one instance, we solve a problem on a 120 million node graph. 1</p><br/>
<h2>reference text</h2><p>[1] O. Chapelle, B. Scholkopf, and A. Zien, Semi-Supervised Learning. MIT Press, 2007.</p>
<p>[2] X. Zhu, “Semi-supervised learning literature survey,” tech. rep., Computer Sciences, University of Wisconsin-Madison, 2005.</p>
<p>[3] M. Szummer and T. Jaakkola, “Partially labeled classiﬁcation with Markov random walks,” in Advances in Neural Information Processing Systems, vol. 14, 2001.</p>
<p>[4] X. Zhu and Z. Ghahramani, “Learning from labeled and unlabeled data with label propagation,” tech. rep., Carnegie Mellon University, 2002.</p>
<p>[5] X. Zhu, Z. Ghahramani, and J. Lafferty, “Semi-supervised learning using gaussian ﬁelds and harmonic functions,” in Proc. of the International Conference on Machine Learning (ICML), 2003.</p>
<p>[6] T. Joachims, “Transductive learning via spectral graph partitioning,” in Proc. of the International Conference on Machine Learning (ICML), 2003.</p>
<p>[7] A. Corduneanu and T. Jaakkola, “On information regularization,” in Uncertainty in Artiﬁcial Intelligence, 2003.</p>
<p>[8] K. Tsuda, “Propagating distributions on a hypergraph by dual information regularization,” in Proceedings of the 22nd International Conference on Machine Learning, 2005.</p>
<p>[9] M. Belkin, P. Niyogi, and V. Sindhwani, “On manifold regularization,” in Proc. of the Conference on Artiﬁcial Intelligence and Statistics (AISTATS), 2005.</p>
<p>[10] C. Bishop, ed., Neural Networks for Pattern Recognition. Oxford University Press, 1995.  8</p>
<p>[11] A. Subramanya and J. Bilmes, “Soft-supervised text classiﬁcation,” in EMNLP, 2008.</p>
<p>[12] R. Collobert, F. Sinz, J. Weston, L. Bottou, and T. Joachims, “Large scale transductive svms,” Journal of Machine Learning Research, 2006.</p>
<p>[13] V. Sindhwani and S. S. Keerthi, “Large scale semi-supervised linear svms,” in SIGIR ’06: Proceedings of the 29th annual international ACM SIGIR, 2006.</p>
<p>[14] O. Delalleau, Y. Bengio, and N. L. Roux, “Efﬁcient non-parametric function induction in semi-supervised learning,” in Proc. of the Conference on Artiﬁcial Intelligence and Statistics (AISTATS), 2005.</p>
<p>[15] M. Karlen, J. Weston, A. Erkan, and R. Collobert, “Large scale manifold transduction,” in International Conference on Machine Learning, ICML, 2008.</p>
<p>[16] I. W. Tsang and J. T. Kwok, “Large-scale sparsiﬁed manifold regularization,” in Advances in Neural Information Processing Systems (NIPS) 19, 2006.</p>
<p>[17] A. Tomkins, “Keynote speech.” CIKM Workshop on Search and Social Media, 2008.</p>
<p>[18] A. Jansen and P. Niyogi, “Semi-supervised learning of speech sounds,” in Interspeech, 2007.</p>
<p>[19] T. M. Cover and J. A. Thomas, Elements of Information Theory. Wiley Series in Telecommunications, New York: Wiley, 1991.</p>
<p>[20] Y. Bengio, O. Delalleau, and N. L. Roux, Semi-Supervised Learning, ch. Label Propogation and Quadratic Criterion. MIT Press, 2007.</p>
<p>[21] Dempster, Laird, and Rubin, “Maximum likelihood from incomplete data via the em algorithm,” Journal of the Royal Statistical Society, Series B, vol. 39, no. 1, pp. 1–38, 1977.</p>
<p>[22] T. Abatzoglou and B. O. Donnell, “Minimization by coordinate descent,” Journal of Optimization Theory and Applications, 1982.</p>
<p>[23] W. Zangwill, Nonlinear Programming: a Uniﬁed Approach. Englewood Cliffs: N.J.: Prentice-Hall International Series in Management, 1969.</p>
<p>[24] C. F. J. Wu, “On the convergence properties of the EM algorithm,” The Annals of Statistics, vol. 11, no. 1, pp. 95–103, 1983.</p>
<p>[25] I. Csiszar and G. Tusnady, “Information Geometry and Alternating Minimization Procedures,” Statistics and Decisions, 1984.</p>
<p>[26] A. K. Halberstadt and J. R. Glass, “Heterogeneous acoustic measurements for phonetic classiﬁcation,” in Proc. Eurospeech ’97, (Rhodes, Greece), pp. 401–404, 1997.</p>
<p>[27] K. F. Lee and H. Hon, “Speaker independant phone recognition using hidden markov models,” IEEE Transactions on Acoustics, Speech and Signal Processing, vol. 37, no. 11, 1989.</p>
<p>[28] J. Godfrey, E. Holliman, and J. McDaniel, “Switchboard: Telephone speech corpus for research and development,” in Proceedings of ICASSP, vol. 1, (San Francisco, California), pp. 517–520, March 1992.</p>
<p>[29] N. Deshmukh, A. Ganapathiraju, A. Gleeson, J. Hamaker, and J. Picone, “Resegmentation of switchboard,” in Proceedings of ICSLP, (Sydney, Australia), pp. 1543–1546, November 1998.</p>
<p>[30] S. Greenberg, “The Switchboard transcription project,” tech. rep., The Johns Hopkins University (CLSP) Summer Research Workshop, 1995.</p>
<p>[31] J. Friedman, J. Bentley, and R. Finkel, “An algorithm for ﬁnding best matches in logarithmic expected time,” ACM Transaction on Mathematical Software, vol. 3, 1977.</p>
<p>[32] S. Arya and D. M. Mount, “Approximate nearest neighbor queries in ﬁxed dimensions,” in ACM-SIAM Symp. on Discrete Algorithms (SODA), 1993.  9</p>
<br/>
<br/><br/><br/>

<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');

ga('create', 'UA-48522588-1', 'makerhacker.github.io');
ga('send', 'pageview');
</script>

</body>
</html>

{'avg_line_length': 109.91044776119404, 'max_line_length': 1006, 'alphanum_fraction': 0.7403585008147746, 'licenses': ['MIT'], 'repository_name': 'makerhacker/makerhacker.github.io', 'path': 'paper-mining/nips/nips2009_reference/nips-2009-Entropic_Graph_Regularization_in_Non-Parametric_Semi-Supervised_Classification_reference.html', 'size': 7510, 'lang': 'HTML'}