Search Results

This chapter reports on research showing that it may be a universal structural property of human languages that they fall into a class of languages defined by mildly context-sensitive grammars. It also investigates the issue of whether there are properties of language that are needed to guarantee that it is learnable. It suggests that languages are learnable if they have a finite Vapnik-Chervonenkis (VC) dimension (where the VC dimension provides a combinatorial measure of complexity for a set of languages). Informally, a finite VC dimension requires that there be restrictions on the set of languages to be learned such that they do not differ from one another in arbitrary ways. These restrictions can be construed as universals that are required for language to be learnable (given formal language learnability theory). The chapter concludes by pointing out that formalizations of the semantic contribution (e.g., compositionality) to language learning might yield further insight into language universals.

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 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 discusses the transductive learning setting proposed by Vapnik where predictions are made only at a fixed number of known test points. Transductive support vector machines (TSVMs) implement the idea of transductive learning by including test points in the computation of the margin. This chapter provides some examples for why the margin on the test examples can provide useful prior information for learning, in particular for the problem of text classification. The resulting optimization problems, however, are difficult to solve. The chapter reviews exact and approximate optimization methods and discusses their properties. Finally, the chapter discusses connections to other related semi-supervised learning approaches such as co-training and methods based on graph cuts, which can be seen as solving variants of the TSVM optimization problem.