Semisupervised learning

Semi-supervised learningAdaptive Computation and Machine LearningThomas Dietterich, editorChristopher Bishop, David Heckerman, Michael Jordan, and Michael Kearns, Associate editorsBioinformatics: The Machine Learning Approach, Pierre Baldi and Soren BrunakReinforcement Learning: An Introduction, Richard s Sutton and Andrew G. BartoGraphical Models for Machine learning and Digital Communication, Brendan JFLearning in graphical Models, Michael I. JordanCausation, Prediction, and Search, second edition, Peter Spirtes, Clark glymourand richard ScheinesPrinciples of Data Mining, David Hand, Heikki Mannila, and Padhraic SmythBioinformatics: The Machine Learning Approach, second edition, Pierre Baldi andSoren brunakLearning Kernel Classifiers: Theory and algorithms, Ralf HerbrichLearning with Kernels: Support vector Machines, Regularization, Optimization, andBeyond, Bernhard Scholkopf and Alexander J SmolaIntroduction to Machine Learning, Ethem AlpaydinGaussian Processes for Machine Learning, Carl Edward Rasmussen and Christopher K.I. WilliamsSemi-Supervised Learning, Olivier Chapelle, Bernhard Scholkopf, and AlexanderZienSemi-Supervised LearningOlivier ChapelleBernhard scholkopfAlexander zienThe mit PressCambridge, MassachusettsLondon. englandC2006 Massachusetts Institute of TechnologyAll rights reserved. No part of this book may be reproduced in any form by any electronicor mechanical means(including photocopying, recording, or information storage and retrieval)without permission in writing from the publisherTypeset by the authors using IATEX 2aPrinted and bound in the United States of americaLibrary of Congress Cataloging-in-Publication DataSemi-supervised learning/ edited by Olivier Chapelle, Bernhard Scholkopf, Alexander Zienp cm-(Adaptive computation and machine learningIncludes bibliographical referencesISBN978-0-26203358-9(alk. paper)Supervised learning(Machine learning) I Chapelle, Olivier. II. Scholkopf, Bernhard. III. ZienAlexander Iv. SQ32575S422006006.31-dc22200604444810987654321ContentsSeries forewordPrefaceX111 Introduction to Semi-Supervised Learning11. 1 Supervised, Unsupervised, and Semi-Supervised learning1.2 When Can Semi-Supervised Learning Work?41. 3 Classes of Algorithms and Organization of This BookGenerative Models132 A Taxonomy for Semi-Supervised Learning Methods15Matthias seeger2.1 The Semi-Supervised Learning problem152.2 Paradigms for Semi-Supervised Learning172.3 Examples222. 4 Conclusions313 Semi-Supervised Text Classification Using EM33Kamal Nigam, Andrew Mccallum, Tom Mitchell3.1 Introduction333.2 A Generative Model for Text353.3 Experimental Results with Basic EM413.4 USing a More Expressive Generative Model433.5 Overcoming the Challenges of Local Maxima.493.6 Conclusions and Summary544 Risks of Semi-Supervised Learning57Fabio cozman. ra Cohen4.1 Do Unlabeled Data Improve or Degrade Classification Performance? 574.2 Understanding Unlabeled Data: Asymptotic Bias594.3 The Asymptotic Analysis of Generative Semi-Supervised Learning 634.4 The value of labeled and unlabeled data4.5 Finite Sample effectsContents4.6 Model search and robustness704.7 Conclusion.715 Probabilistic Semi-Supervised Clustering with Constraints73Sugato basu, Mikhail bilenko, Arindam Banerjee, raymond Mooney5.1 Introduction5.2 HMRF Model for Semi-Supervised Clustering745.3 HMRF-KMEANS Algorithm815.4 Active Learning for Constraint Acquisition935.5 Experimental results5.6 Related Work1005.7 Conclusions101Low-Density Separation1036 Transductive Support vector Machines105Thorsten oachims6.1 Introduction1056.2 Transductive Support Vector Machines1086.3 Why Use Margin on the Test Set?6.4 Experiments and applications of Tsvms.1126.5 Solving the tsVM Optimization Problem1146.6 Connection to Related Approaches1166.7 Summary and Conclusions1167 Semi-Supervised Learning Using Semi-Definite Programming 119Tijl De Bie, Nello Cristianin7.1 Relaxing SvM transduction.1197.2 An Approximation for Speedup1267.3 General Semi-Supervised Learning Settings1287.4 Empirical results127.5 Summary and Outlook.133Appendix: The Extended Schur Complement Lemma1348 Gaussian Processes and the null-Category noise model137Neil D. lawrence. Michael l. ordan8.1 Introduction1378.2 The noise model1418.3 Process Model and Effect of the Null-Category.1438.4 Posterior inference and prediction1458.5 Results1478.6 Discussion1499 Entropy regularization151ContentsYves grandvalet, Yoshua Bengio9. 1 Introduction1519.2 Derivation of the Criterion29.3 Optimization Algorithms1559. 4 Related methods1589.5 Experiments1609. 6 Conclusion166Appendix: Proof of Theorem 9.116610 Data-Dependent regularization169Adrian Corduneanu, Tommi Jaakkola10.1 Introduction16910.2 Information Regularization on Metric Spaces17410.3 Information Regularization and Relational Data18210.4 Discussion189Ii Graph-Based Methods19111 Label Propagation and Quadratic Criterion193Yoshua Bengio, Olivier Delalleau, Nicolas Le rour11. 1 Introduction19311.2 Label Propagation on a Similarity graph19411.3 Quadratic Cost Criterion19811. 4 From transduction to induction20511.5 Incorporating Class Prior Knowledge11.6 Curse of Dimensionality for Semi-Supervised Learning11. 7 Discussion.21512 The Geometric Basis of Semi-Supervised Learning217Vikas sindhwani, Misha Belkin, Partha Niyogi12. 1 Introduction12.2 Incorporating Geometry in Regularization22012.3 Algorithms22412.4 Data-Dependent Kernels for Semi-Supervised Learning22912.5 Linear Methods for Large-Scale Semi-Supervised Learning23112.6 Connections to Other Algorithms and Related Work2312. 7 Future Directions23413 Discrete regularization237Denggong Zhou, Bernhard Scholkopf13.1 Introduction.23713.2 Discrete analysis13.3 Discrete Regularization24513.4 Conclusion249Contents14 Semi-Supervised Learning with Conditional Harmonic Mixing 251Christopher C. Burges, John C. Platt14.1 Introduction25114.2 Conditional Harmonic mixing25514.3 Learning in CHM Models25614.4 Incorporating Prior Knowledge26114.5 Learning the Conditionals26114.6 Model averaging26214.7 Experiments26314.8 ConclusionsV Change of Representation27515 Graph Kernels by Spectral Transforms277Xiaojin Zhu, Jaz Kandola, John Lafferty, Zoubin ghahramani15.1 The Graph Laplacian27815.2 Kernels by Spectral Transforms28015.3 Kernel Alignment28115.4 Optimizing Alignment Using QcQp for Semi-Supervised Learning 28215.5 Semi-Supervised Kernels with Order Constraints28315.6 Experimental results15.7 Conclusion28916 Spectral Methods for DimensionalityReduction293Lawrence k. saul, Kilian Q. Weinberger, Fei Sha, Jihun Ham, Daniel D. Lee16. 1 Introduction29316.2 Linear methods16.3 Graph-Based Methods29716.4 Kernel Methods30316.5 Discussion.30617 Modifying Distances309Sajama, Alon Orlitsky17.1 Introduction30917.2 Estimating DBD Metrics31217.3 Computing DBD Metrics32117.4 Semi-Supervised Learning Using Density-Based Metrics32717.5 Conclusions and Future Work329V Semi-Supervised Learning in Practice33118 Large-Scale Algorithms333ContentsOlivier Delalleau, Yoshua Bengio, Nicolas Le rour18.1 Introduction33318.2 Cost Approximations33418.3 Subset Selection33718.4 Discussion34019 Semi-Supervised Protein ClassificationUsing Cluster Kernels343Jason weston, Christina leslie, Eugene le, William stafford noble19.1 Introduction34319.2 Representations and Kernels for Protein Sequences34519.3 Semi-Supervised Kernels for Protein Sequences34819.4 Experiments35219.5 Discussion35820 Prediction of protein function fromNetworks361Hyunjung Shin, Koji tsuda20.1 Introduction20.2 Graph-Based Semi-Supervised Learning36420.3 Combining Multiple graphs20.4 Experiments on Function Prediction of Proteins.36920.5 Conclusion and Outlook37421 Analysis of Benchmarks37721.1 The benchmark37721.2 Application of SsL Methods21.3 Results and discussion390ⅵ I Perspectives39522 An Augmented PAC Model for Semi-Supervised Learning397Maria-Florina balcan. avrim blum22.1 Introduction.39822. A Formal Framework40022.3 Sample complexity Results40322.4 Algorithmic Results41222.5 Related models and discussion..41623 Metric-Based Approaches for SemiSupervised Regression and Classification421Dale schuurmans, Finnegan Southey, Dana Wilkinson, Yuhong guo23.1 Introduction42123.2 Metric Structure of Supervised Learning423