Synthesis Lectures on Artificial Intelligence and Machine Learning Editors Ronald j Brachman, Yahoo Research Thomas Dietterich, Oregon State University Introduction to Semi-Supervised learning 200oJin Zhu and Andrew B. Goldberg 009 Action Programming languages Michael thielscher 2008 Representation Discovery using Harmonic Analysis Sridhar mahadevan 2008 Essentials of Game Theory: A Concise Multidisciplinary Introduction Kevin Leyton-Brown, Yoav Shoham 2008 A Concise Introduction to Multiagent Systems and Distributed Artificial Intelligence Nikos vlassis 2007 Intelligent Autonomous Robotics: A Robot Soccer Case Study 2007 Copyright@ 2009 by Morgan Claypool All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any mcansclcctronic, mcchanical, photocopy, rccording, or any other except for bricf quotations in printed reviews, without the prior permission of the publisher Introduction to Semi-Supervised Learning Xiaojin Zhu and Andrew B. Goldberg www.morganclaypool.com ISBN:9781598295474 paperback ISBN:9781598295481 DOl10.2200/S00196ED1Vo1Y200906AIM006 A Publication in the Morgan Claypool Publishers series SYNTHESIS LECTURES ON ARTIFICIAL INTELLIGENCE AND MACHINE LEARNING Lecture #6 Scrics Editors: Ronald J Brachman, Yaboo. Research Thomas Dietterich, Oregon State University Series issn Synthesis Lectures on Artificial Intelligence and Machine Learning Print 1939-4608 Electronic 1939-4616 Introduction to Semi-Supervised Learning Xiaojin Zhu and Andrew B. goldberg University of Wisconsin, Madison SYNTHESIS LECTURES ON ARTIFICLAL INTELLIGENCE AND MACHINE LEARNING #6 MORGaN &CLAYPOOL PUbLiSherS ABSTRACT Semi-supcrviscd learning is a learning paradigm concerned with the study of how computers and natural systems such as humans learn in the presence ofboth labeled and unlabeled data. Traditionally learning has been studied either in the unsupervised paradigm(e.g, clustering, outlier detection where all the data is unlabeled, or in the supervised paradigm (e. g, classification, regression )where ill the data is labeled. The goal of semi-supervised learning is to understand how combining labeled and unlabeled data may change the learning behavior, and design algorithms that take advantage of such a combination Semi-supervised learning is of great interest in machine learning and data mining because it can use readily available unlabeled data to improve supervised learning tasks when the labeled data is scarce or expensive. Semi-supervised learning also shows potential as a quantitativ tool to understand hunan category learning, where inost of the input is self-evidently unlabeled In this introductory book, we present some popular semi-supervised learning models, including elf-training, mixture models, co-training and multiview learning, graph-based methods, and sem supervised support vector machines. For each model, we discuss its basic mathematical formulation The success of semi-supervised learning depends critically on some underlying assumptions. We emphasize the assumptions made by each model and give counterexamples when appropriate to demonstrate the limitations of the different models. In addition, we discuss semi-supervised learning for cognitive psychology. Finally, we give a computational learning theoretic perspective on semi- supervised learning, and we conclude the book with a brief discussion of open questions in the field KEYWORDS semi-supervised learning, transductive learning, self-training, Gaussian mixture model expectation maximization (EM), cluster-then-label, co-training, multiview learning, mincut, harmonic function, label propagation, manifold regularization, semi-supervised support vector machines(S3 VM), transductive support vector machines(TSVM),en tropy regularization, human semi-supervised learning our parents uan Susan and Steven goldberg with much love and gratitude Contents Preface 1 Introduction to Statistical Machine Learning 1.1 The data 1.2 Unsupervised learning 1.3 Supervised Learning 2 Overview of Semi-Supervised Learning 2.1 Learning from Both Labeled and Unlabeled Data 2.2 How is Semi-Supervised Learning Possible 11 23 Inductive vs. Transductive Semi-Supervised Learning.........∴........................12 2.4 Caveats 13 2.5 Self-Training Models 3 Mixture Models and EM 3.1 ture Models for Supervised classification 21 3.2 Mixture Models for Semi-Supervised classification ..25 3.3 Optimization with the EM Algorithm"* 3.4 The Assumptions of Mixture models ..···· 28 3.5 Other Issues in Generative Models 3.6 Cluster-then-Label Methods 4 Co-Training 35 4.1 Two Views of an instance 35 4.2C o- raining∴ ∴..36 4.3 The Assumptions of Co-Training 37 4.4 Multiview l earnin 38 X CONTENTS 5 Graph- Based semi- Supervised Learning.................. 43 5.1 Unlabeled Data as Stepping Stones.......... 面看着 5.2 The Graph .43 5.3 Mincut 45 5.4 Harmonic Function 5.5 Manifold Regularization .50 5.6 The Assumption of graph-Based Methods* upervised Support Vector Machines 6.1 Support Vector Machines 6.2 Semi-Supervised Support Vector Machines 61 6.3 Entropy regularization ...63 6.4 The Assumption of S3 VMs and Entropy Regularization 7 Human semi- Supervised Learning............ 7.1 From Machine learning to Cognitive Science 69 7.2 Study One: Humans Learn from Unlabeled Test Data 70 7.3 Study Two: Presence of Human Semi-Supervised Learning in a Simple Task. ...72 7. 4 Study Three: Absence of Human Semi-Supervised Learning in a Complex Task 7.5 Discussions / 8 Theory and Outlook 79 8.1 A Simple Pac Bound for Supervised learning...................79 8. 2 A Simple PAC Bound for Semi-Supervised Learning 8.3 Future Directions of Semi-Supervised Learning 83 a Basic Mathematical ro 85 b Semi-Supervised Learning Software................ .89 93 1ograp 113