Search Results

This chapter first presents definitions of supervised and unsupervised learning in order to understand the nature of semi-supervised learning (SSL). SSL is halfway between supervised and unsupervised learning. In addition to unlabeled data, the algorithm is provided with some supervision information—but not necessarily for all examples. Often, this information will be the targets associated with some of the examples. Other forms of partial supervision are possible. For example, there may be constraints such as “these points have (or do not have) the same target.” The different setting corresponds to a different view of semi-supervised learning: In succeeding chapters, SSL is seen as unsupervised learning guided by constraints. A problem related to SSL was introduced by Vapnik several decades ago—transductive learning. In this setting, a labeled training set and an unlabeled test set are provided. The idea of transduction is to perform predictions only for the test points.

This chapter presents a fictitious discussion inspired by real discussions between the editors of this book and a number of people, including Vladimir Vapnik. It involves three researchers; for simplicity, called here A, B, and C, without implying any one-to-one mapping to real persons. The topic of the discussion is: What is the Difference between Semi-Supervised Learning and Transductive Learning?

This chapter provides an introduction to covariate shift adaptation toward machine learning in a non-stationary environment. It begins by discussing cover machine learning under covariate shift. It then describes the core idea of covariate shift adaptation, using an illustrative example. Next, it formulates the supervised learning problem, which includes regression and classification. It pays particular attention to covariate shift and model misspecification. An overview of the subsequent chapters is also presented.

This chapter shows how the different graph-based algorithms for semi-supervised learning can be cast into a common framework where one minimizes a quadratic cost criterion whose closed-form solution is found by solving a linear system of size n (total number of data points). The cost criterion naturally leads to an extension of such algorithms to the inductive setting, where one obtains test samples one at a time: the derived induction formula can be evaluated in O(n) time, which is much more efficient than solving again exactly the linear system (which in general costs O(kn²) time for a sparse graph where each data point has k neighbors). This inductive formula is also used to show that when the similarity between points satisfies a locality property, then the algorithms are plagued by the curse of dimensionality, with respect to the dimensionality of an underlying manifold.

This chapter presents a number of conclusions. Firstly, labeled and unlabeled data contribute to a reduction in variance in semi-supervised learning under maximum-likelihood estimation. Secondly, when the model is “correct,” maximum-likelihood methods are asymptotically unbiased both with labeled and unlabeled data. Thirdly, when the model is “incorrect,” there may be different asymptotic biases for different values of λ. Asymptotic classification error may also vary with λ—an increase in the number of unlabeled samples may lead to a larger estimation asymptotic bias and to a larger classification error. If the performance obtained from a given set of labeled data is better than the performance with infinitely many unlabeled samples, then at some point the addition of unlabeled data must decrease performance.

This chapter discusses the explicit relationship that must be asserted between labeled and unlabeled data, which is a requirement of semi-supervised learning methods. Semi-supervised model selection and regularization methods are presented here that instead require only that the labeled and unlabeled data are drawn from the same distribution. From this assumption, a metric can be constructed over hypotheses based on their predictions for unlabeled data. This metric can then be used to detect untrustworthy training error estimates, leading to model selection strategies that select the richest hypothesis class while providing theoretical guarantees against overfitting. This general approach is then adapted to regularization for supervised regression and supervised classification with probabilistic classifiers. The regularization adapts not only to the hypothesis class but also to the specific data sample provided, allowing for better performance than regularizers that account only for class complexity.

This chapter discusses basic concepts from control theory and machine learning to facilitate a formal understanding of animal learning and motor control. It first distinguishes between feedback and feed-forward control strategies, and later introduces the classification of machine learning applications into supervised, unsupervised, and reinforcement learning problems. Next, it links these concepts with their counterparts in the domain of the psychology of animal learning, highlighting the analogies between supervised learning and classical conditioning, reinforcement learning and operant conditioning, and between unsupervised and perceptual learning. Additionally, it interprets innate and acquired actions from the standpoint of feedback vs anticipatory and adaptive control. Finally, it argues how this framework of translating knowledge between formal and biological disciplines can serve us to not only structure and advance our understanding of brain function but also enrich engineering solutions at the level of robot learning and control with insights coming from biology.

This chapter explores the use of generative models for semi-supervised learning with labeled and unlabeled data in domains of text classification. The widely used naive Bayes classifier for supervised learning defines a mixture of multinomials mixture models. In some domains, model likelihood and classification accuracy are strongly correlated, despite the overly simplified generative model. Here, expectation-maximization finds more likely models and improved classification accuracy. In other domains, likelihood and accuracy are not well correlated with the naive Bayes model. Here, we can use a more expressive generative model that allows for multiple mixture components per class. This helps restore a moderate correlation between model likelihood and classification accuracy, and again, EM finds more accurate models. Finally, even with a well-correlated generative model, local maxima are a significant hindrance with EM. Here, the approach of deterministic annealing does provide much higher likelihood models, but often loses the correspondence with the class labels. When class label correspondence is easily corrected, high accuracy models result.

This chapter describes an experimental study of large-scale semi-supervised learning for the problem of protein classification. The protein classification problem, a central problem in computational biology, is to predict the structural class of a protein given its amino acid sequence. Such a classification helps biologists to understand the function of a protein. Building an accurate protein classification system, as with many tasks, depends critically upon choosing a good representation of the input sequences of amino acids. Early work using string kernels with support vector machines (SVMs) for protein classification achieved state-of-the-art classification performance. However, such representations are based only on labeled data—examples with known three-dimensional (3D) structures, organized into structural classes-while in practice, unlabeled data are far more plentiful.

This chapter discusses the difference between transductive inference and semi-supervised learning. It argues that transductive inference captures the intrinsic properties of the mechanism for extracting additional information from the unlabeled data. It also shows an important role of transduction for creating noninductive models of inference. In transductive inference the goal is to classify the given u test vectors of interest while in semi-supervised learning the goal is to find the function that minimizes the functional. Semi-supervised learning can be seen as being related to a particular setting of transductive learning. From a conceptual point of view, transductive inference contains important elements of a new philosophy of inference and this is the subject of this discussion.

This chapter discusses density-based metrics induced by Riemannian manifold structures. It presents asymptotically consistent methods to estimate and compute these metrics and present upper and lower bounds on their estimation and computation errors. Finally, it is discussed how these metrics can be used for semi-supervised learning and present experimental results. Learning algorithms use a notion of similarity between data points to make inferences. Semi-supervised algorithms assume that two points are similar to each other if they are connected by a high-density region of the unlabeled data. Apart from semi-supervised learning, such density-based distance metrics also have applications in clustering and nonlinear interpolation.

This chapter describes an augmented version of the PAC model, designed with semi-supervised learning in mind, that can be used to help think about the problem of learning from labeled and unlabeled data and many of the different approaches taken. The model provides a unified framework for analyzing when and why unlabeled data can help, in which one can discuss both sample-complexity and algorithmic issues. The model described here can be viewed as an extension of the standard PAC model, where a compatibility function is also proposed—a type of compatibility that one believes the target concept should have with the underlying distribution of data. Unlabeled data are potentially helpful in this setting because they allow one to estimate compatibility over the space of hypotheses.

This chapter describes an algorithm to assign weights to multiple graphs within graph-based semi-supervised learning. Both predicting class labels and searching for weights for combining multiple graphs are formulated into one convex optimization problem. The graph-combining method is applied to functional class prediction of yeast proteins. When compared with individual graphs, the combined graph with optimized weights performs significantly better than any single graph. When compared with the semi-definite programming-based support vector machine (SDP/SVM), it shows comparable accuracy in a remarkably short time. Compared with a combined graph with equal-valued weights, this method could select important graphs without loss of accuracy, which implies the desirable property of integration with selectivity.

This chapter assesses the strengths and weaknesses of different semi-supervised learning (SSL) algorithms through inviting the authors of each chapter in this book to apply their algorithms to eight benchmark data sets. These data sets encompass both artificial and real-world problems. Details are provided on how the algorithms were applied, especially how hyperparameters were chosen given the few labeled points. Finally, the chapter concludes by presenting and discussing the empirical performance.

This chapter analyzes Bayesian supervised learning with extensions to semisupervised learning, and learning with covariate or dataset shift. The main result is an expression for the generalization optimal Bayesian procedure. The resulting “Bayesian transduction” average is optimal for a realizable model. For semisupervised learning, this implies that all available data, including unlabeled data, should be used in the likelihood, hence in forming the parameter posterior. In the case of covariate or dataset shift, the situation is contingent on the parameterization.

Marr proposed that complex information processing systems be analysed at three different levels, those of computation, algorithm and implementation. Applying this framework to current research on the cerebellum suggests that two different kinds of computational problem are involved. The first, solved by the cerebellar cortical microcircuit, involves the learning of input-output mappings. The second makes use of this ability in a wide variety of contexts that are determined by the unique connections of different cortical microzones. This dichotomy is captured by the metaphor of the cerebellar chip. A powerful algorithm for learning input-output mappings uses the Least Mean Square rule, so a crucial implementational question is whether microcircuit synaptic plasticity is consistent with this rule. A number of experimental findings suggest consistency, but uncertainty persists both because the relevant sites of plasticity have yet to be localised, and because synaptic plasticity in vivo is not simply related to the forms of synaptic plasticity characterised in vitro. A number of algorithms have been proposed for the external circuitry. One solves the reafference problem by removing from sensory inputs interference generated by the organism’s own movement. Some features of the circuitry described for eyeblink conditioning appear consistent with this algorithm, in particular the apparent presence of a comparator in the inferior olive that subtracts cerebellar output from sensory input. A second algorithm solves the problem of compensating for a changing body when producing accurate movements. A number of findings from studies of the VOR adaptation circuit appear consistent with the algorithm. However, in both cases the actual neural circuits are more complex than the algorithms would seem to require. This problem is becoming more acute as experiments reveal an ever-increasing wealth of implementational detail. A powerful feature of Marr’s framework is its use of computational and algorithmic constraints to help interpret this otherwise overwhelming complexity.

In this chapter we define the problem space and describe the core components of automatic facial expression recognition systems. In particular, we discuss the most prominent methods of face segmentation, face registration, feature extraction, classification, and temporal integration. We then present several practical applications of expression recognition technology. Finally, we comment on the core future challenges to the field, including generalization to multiple poses and ethnicities, collection of better training data, evaluation infrastructure, and commercialization.

The cerebellar cortex appears to be involved in predictive feedforward control to generate smooth movements. There is a beautiful network architecture which suggests that the granule cells perform expansion recoding of the inputs; that these connect to the Purkinje cells via an architecture that ensures regular sampling; and that each Purkinje cell has a single teacher, the climbing fibre, which produces associative long-term synaptic depression as part of perceptron-like learning.

Using archival, textual information from Federal Open Market Committee (FOMC) transcript data as well as FOMC policy statements, chapter 4 demonstrates that when the chair and median member have opposing inflation preferences, the FOMC communicates with greater precision than when the chair and median member have aligned inflation preferences. The author finds this is true, however, when computing the median members able to cast a public vote. The chapter also provides supportive evidence that when committee members are more dissimilar, the number of textual changes to the policy announcement is higher than otherwise. Theoretically, the chapter shows that a combination of members’ preferences and voting rights matter for the level of uncertainty words used in the official policy statement. Methodologically, the chapter demonstrates the innovative use of supervised and unsupervised learning techniques to construct quantitative measures from text as data, applied to central bank committees.