### SSL Tutorial at ACL 2008

### Jerry Zhu's excellent SSL Tutorial (covers non-graph SSL as well)

### SSL Book edited by Olivier Chapelle, Bernhard Schölkopf, and Alexander Zien

# Software

### Junto Label Propagation Toolkit

This toolkit consists of implementations of various graph-based semi-supervised learning (SSL) algorithms. Currently, three algorithms are implemented: Gaussian Random Fields (GRF), Adsorption, and Modified Adsorption (MAD). Starting with v1.2.0, Junto also contains Hadoop-based implementations of these three algorithms.

# References

[1] A. Alexandrescu and K. Kirchhoff. Data-driven graph construction for semi-supervised graph-based learning in nlp. In NAACL HLT, 2007.

[2] Y. Altun, D. McAllester, and M. Belkin. Maximum margin semi-supervised learn- ing for structured variables. NIPS, 2006.

[2b] B. Krishnapuram, D. Williams, Y. Xue, A. Hartemink, L. Carin, M. A. T. Figueiredo. On Semi-Supervised Classiﬁcation. In NIPS 2004.

[3] S. Baluja, R. Seth, D. Sivakumar, Y. Jing, J. Yagnik, S. Kumar, D. Ravichandran, and M. Aly. Video suggestion and discovery for youtube: taking random walks through the view graph. In WWW, 2008.

[4] R. Bekkerman, R. El-Yaniv, N. Tishby, and Y. Winter. Distributional word clusters vs. words for text categorization. J. Mach. Learn. Res., 3:1183–1208, 2003.

[5] 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.

[6] Y. Bengio, O. Delalleau, and N. Le Roux. Label propagation and quadratic criterion. Semi-supervised learning, 2006.

[7] T. Berg-Kirkpatrick, A. Bouchard-Coˆt ́e, J. DeNero, and D. Klein. Painless unsupervised learning with features. In HLT-NAACL, 2010.

[8] J. Bilmes and A. Subramanya. Scaling up Machine Learning: Parallel and Distributed Approaches, chapter Parallel Graph-Based Semi-Supervised Learning. 2011.

[9] S. Blair-goldensohn, T. Neylon, K. Hannan, G. A. Reis, R. Mcdonald, and J. Reynar. Building a sentiment summarizer for local service reviews. In In NLP in the Information Explosion Era, 2008.

[10] M. Cafarella, A. Halevy, D. Wang, E. Wu, and Y. Zhang. Webtables: exploring the power of tables on the web. VLDB, 2008.

[11] O. Chapelle, B. Scho ̈lkopf, A. Zien, et al. Semi-supervised learning. MIT press Cambridge, MA:, 2006.

[12] Y. Choi and C. Cardie. Adapting a polarity lexicon using integer linear program- ming for domain specific sentiment classification. In EMNLP, 2009.

[13] S. Daitch, J. Kelner, and D. Spielman. Fitting a graph to vector data. In ICML, 2009.

[14] D. Das and S. Petrov. Unsupervised part-of-speech tagging with bilingual graph- based projections. In ACL, 2011.

[15] D. Das, N. Schneider, D. Chen, and N. A. Smith. Probabilistic frame-semantic parsing. In NAACL-HLT, 2010.

[16] D. Das and N. Smith. Graph-based lexicon expansion with sparsity-inducing penalties. NAACL-HLT, 2012.

[17] D. Das and N. A. Smith. Semi-supervised frame-semantic parsing for unknown predicates. In ACL, 2011.

[18] J. Davis, B. Kulis, P. Jain, S. Sra, and I. Dhillon. Information-theoretic metric learning. In ICML, 2007.

[19] O. Delalleau, Y. Bengio, and N. L. Roux. Efficient non-parametric function induction in semi-supervised learning. In AISTATS, 2005.

[20] P. Dhillon, P. Talukdar, and K. Crammer. Inference-driven metric learning for graph construction. Technical report, MS-CIS-10-18, University of Pennsylvania, 2010.

[21] S. Dumais, J. Platt, D. Heckerman, and M. Sahami. Inductive learning algorithms and representations for text categorization. In CIKM, 1998.

[22] J. Friedman, J. Bentley, and R. Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Transaction on Mathematical Software, 3, 1977.

[23] J. Garcke and M. Griebel. Data mining with sparse grids using simplicial basis functions. In KDD, 2001.

[24] A. Goldberg and X. Zhu. Seeing stars when there aren’t many stars: graph-based semi-supervised learning for sentiment categorization. In Proceedings of the First Workshop on Graph Based Methods for Natural Language Processing, 2006.

[25] A. Goldberg, X. Zhu, and S. Wright. Dissimilarity in graph-based semi-supervised classification. AISTATS, 2007.

[26] M. Hu and B. Liu. Mining and summarizing customer reviews. In KDD, 2004.

[27] T. Jebara, J. Wang, and S. Chang. Graph construction and b-matching for semi-supervised learning. In ICML, 2009.

[28] T. Joachims. Transductive inference for text classification using support vector machines. In ICML, 1999.

[29] T. Joachims. Transductive learning via spectral graph partitioning. In ICML, 2003.

[30] M. Karlen, J. Weston, A. Erkan, and R. Collobert. Large scale manifold transduction. In ICML, 2008.

[31] S.-M. Kim and E. Hovy. Determining the sentiment of opinions. In Proceedings of the 20th International conference on Computational Linguistics, 2004.

[32] F. Kschischang, B. Frey, and H. Loeliger. Factor graphs and the sum-product algorithm. Information Theory, IEEE Transactions on, 47(2):498–519, 2001.

[33] K. Lerman, S. Blair-Goldensohn, and R. McDonald. Sentiment summarization: evaluating and learning user preferences. In EACL, 2009.

[34] D.Lewisetal.Reuters-21578.http://www.daviddlewis.com/resources/testcollections/reuters21578, 1987.

[35] J. Malkin, A. Subramanya, and J. Bilmes. On the semi-supervised learning of multi-layered perceptrons. In InterSpeech, 2009.

[36] B. Pang, L. Lee, and S. Vaithyanathan. Thumbs up?: sentiment classification using machine learning techniques. In EMNLP, 2002. [37] D. Rao and D. Ravichandran. Semi-supervised polarity lexicon induction. In EACL, 2009.

[38] A. Subramanya and J. Bilmes. Soft-supervised learning for text classification. In EMNLP, 2008.

[39] A. Subramanya and J. Bilmes. Entropic graph regularization in non-parametric semi-supervised classification. NIPS, 2009.

[40] A. Subramanya and J. Bilmes. Semi-supervised learning with measure propagation. JMLR, 2011.

[41] A. Subramanya, S. Petrov, and F. Pereira. Efficient graph-based semi-supervised learning of structured tagging models. In EMNLP, 2010.

[42] P. Talukdar. Topics in graph construction for semi-supervised learning. Technical report, MS-CIS-09-13, University of Pennsylvania, 2009.

[43] P. Talukdar and K. Crammer. New regularized algorithms for transductive learn- ing. ECML, 2009.

[44] P. Talukdar and F. Pereira. Experiments in graph-based semi-supervised learning methods for class-instance acquisition. In ACL, 2010.

[45] P. Talukdar, J. Reisinger, M. Pa ̧sca, D. Ravichandran, R. Bhagat, and F. Pereira. Weakly-supervised acquisition of labeled class instances using graph random walks. In EMNLP, 2008.

[46] B. Van Durme and M. Pasca. Finding cars, goddesses and enzymes: Parametriz- able acquisition of labeled instances for open-domain information extraction. In AAAI, 2008.

[47] L. Velikovich, S. Blair-Goldensohn, K. Hannan, and R. McDonald. The viability of web-derived polarity lexicons. In HLT-NAACL, 2010.

[48] F. Wang and C. Zhang. Label propagation through linear neighborhoods. In ICML, 2006.

[49] J. Wang, T. Jebara, and S. Chang. Graph transduction via alternating minimiza- tion. In ICML, 2008.

[50] R. Wang and W. Cohen. Language-independent set expansion of named entities using the web. In ICDM, 2007.

[51] K. Weinberger and L. Saul. Distance metric learning for large margin nearest neighbor classification. The Journal of Machine Learning Research, 10:207–244, 2009.

[52] T. Wilson, J. Wiebe, and P. Hoffmann. Recognizing contextual polarity in phrase- level sentiment analysis. In HLT-EMNLP, 2005.

[53] D. Zhou, O. Bousquet, T. Lal, J. Weston, and B. Scho ̈lkopf. Learning with local and global consistency. NIPS, 2004.

[54] D. Zhou, J. Huang, and B. Scho ̈lkopf. Learning from labeled and un- labeled data on a directed graph. In ICML, 2005.

[55] D. Zhou, B. Scho ̈lkopf, and T. Hofmann. Semi-supervised learning on directed graphs. In NIPS, 2005.

[56] X. Zhu and Z. Ghahramani. Learning from labeled and unlabeled data with label propagation. Technical report, CMU-CALD-02-107, Carnegie Mellon University, 2002.

[57] X. Zhu and Z. Ghahramani. Learning from labeled and unlabeled data with label propagation. Technical report, Carnegie Mellon University, 2002.

[58] X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In ICML, 2003.

[59] X. Zhu and J. Lafferty. Harmonic mixtures: combining mixture models and graph- based methods for inductive and scalable semi-supervised learning. In ICML, 2005.