NSF-ITR / IM PROJECT : 2003 Abstracts From Bits to Information : Statistical Learning Technologies for Digital Information Management Search

The problem of text classification is to predict the labels of documents based on their content. When learning a classifier using training data, one must balance two aspects: (1) specificity to the training set, and (2) generalization to unseen data. A natural framework for this problem is compression. In compressing a set of document labels, we can either transmit the labels directly, or specify aspects of the documents that predict the labels. This imposes a natural trade-off: it is advantageous to use features from the documents only if they allow more efficient encoding of the labels. Important in bridging the gap between theory and practice is efficiently encoding features and weights. We develop techniques for this by taking advantage of prior information. The compression framework also naturally extends to incorporating unlabeled data, making use of similar classification problems, and taking advantage of hierarchical structure. We describe these extensions and provide examples on real-world data sets.  Generalized Low-Rank Approximations PI: T. Jaakkola Participants: Nathan Srebro and Tommi Jaakkola Abstract: We study the frequent problem of approximating a target matrix with a matrix of lower rank. We provide a simple and efficient (EM) algorithm for solving /weighted/ low-rank approximation problems, which, unlike simple matrix factorization problems, do not admit a closed form solution in general. We analyze, in addition, the nature of locally optimal solutions that arise in this context, demonstrate the utility of accommodating the weights in reconstructing the underlying low rank representation, and extend the formulation to non-Gaussiannoise models such as logistic models. We apply the methods developed to a collaborative filtering task. We study the frequent problem of approximating a target matrix with a matrix of lower rank. We provide a simple and efficient (EM) algorithm for solving /weighted/ low-rank approximation problems, which, unlike simple matrix factorization problems, do not admit a closed form solution in general. We analyze, in addition, the nature of locally optimal solutions that arise in this context, demonstrate the utility of accommodating the weights in reconstructing the underlying low rank representation, and extend the formulation to non-Gaussiannoise models such as logistic models. We apply the methods developed to a collaborative filtering task.  Information Regularization with Partially Labeled Data PI: T. Jaakkola Participants: Martin Szummer (CBCL, MIT AI Lab) and Tommi Jaakkola (MIT AI Lab)  Classification with partially labeled data requires using a large number of unlabeled examples, or $P(\xb)$, to further constrain the conditional $P(y|\xb)$ beyond a few available labeled examples. We formulate here a regularization approach to linking the marginal and the conditional in a general way. T he regularization penalty measures the information that is implied about the labels at the chosen resolution over {\em covering} regions. No parametric assumptions are required and the approach remains tractable even for continuous marginal densities $P(\xb)$. We develop algorithms for solving the regularization problem for finite covers, establish a limiting differential equation, and exemplify the behavior of the new regularization approach in simple cases.  On Information Regularization PI: T. Jaakkola Participants: Adrian Corduneanu and Tommi Jaakkola Abstract: We formulate a principle for classification with the knowledge of the marginal distribution over the data points (unlabeled data). The principle is cast in terms of Tikhonov style regularization where the regularization penalty articulates the way in which the marginal density should constrain otherwise unrestricted conditional distributions. Specifically, the regularization penalty penalizes any information introduced between the examples and labels beyond what is provided by the available labeled examples. The project extends the work of Szummer and Jaakkola (2002) to multiple dimensions, providing a regularizer independent of the covering of the space used in the derivation. We illustrate the regularization principle in practice by restricting the class of conditional distributions to be logistic regression models and constructing the regularization penalty from a finite set of unlabeled examples.  Component-based Face Detection PI: T. Poggio Participants: Bernd Heisele and Thomas Serre  We present a component-based, trainable system for detecting frontal and near-frontal views of faces in still gray images. The system consists of a two-level hierarchy of Support Vector Machine (SVM) classifiers. On the first level, component experts independently detect components of a face. On the second level, a single classifier checks if the geometrical configuration of the detected components in the image matches a geometrical model of a face. We propose a method for automatically learning components by using 3-D head models. This approach has the advantage that no manual interaction is required for choosing and extracting components. Experiments show that the component-based system is significantly more robust against rotations in depth than a comparable system trained on whole face patterns.  Classification of Yahoo News from Images and Captions PI: T. Poggio Participants: Alexandros Kyriakides and Giorgos Zacharia Abstract: Classification of images obtained from news articles. Our goal is to find the best suitable image for a news story. We use the captions of the images in order to classify the images and perform the selection. Our current approach tries to predict which words in a news story are likely to be in the caption of the image. In essence we are selecting the most important words from a news story that will help us select the correct image. We can currently predict with 75%-80% accuracy if a word in a news story is also in the caption of the image. The confusion matrix below shows how well one of our predictors performs. Words, which are both in the news story and the caption, are termed "yes" words. Words, which are in the news story but not in the caption, are termed "no" words. The rows indicate the actual class. The columns indicate the predicted class. No Yes no 120618 32040 yes 4771 8764 Correctly Classified Instances: 129382 (77.8505 %) Project Title: Stability is necessary and sufficient for consistency of Empirical Risk Minimization Participants: Sayan Mukherjee and Tomaso Poggio PI: T. Poggio  Solutions of learning problems by Empirical Risk Minimization (ERM) -and almost-ERM in general when the minimizer does not exist -need to be consistent, so that they may be predictive. They also need to be well-posed, so that they might be used robustly. We propose a statistical form of well-posedness, defined in terms of the property of cross-validation leave-one-out cv stability. Our main observation implies that for bounded loss classes, cv stability of ERM is necessary and sufficient for consistency of ERM. We conclude that cv stability is the weakest form of stability which is sufficient for convergence in probability of the empirical error to the expected error for general learning algorithms while being necessary and sufficient for ERM. We discuss stronger forms of stability and their relations with small uGC hypothesis spaces, such as VC-classes and balls in a Sobolev or a RKHS space.  Rademacher Averages as Complexity Measures PI: T. Poggio Participant: Alex Rakhlin  We study measures of complexity other than VC or V-gamma dimensions. In many applications, the Rademacher Averages appear to be an easier tool than the usual metric entropy approaches. In particular, we show that using recent developments in Empirical Process theory, we get fast convergence rates for estimating densities from very rich classes of infinite convex combinations of parametrized densities. Project title: Information Regularization with Partially Labeled Data PI: T. Poggio Participants: Martin Szummer and Tommi Jaakkola Abstract: Classification with partially labeled data involves learning from a few labeled examples as well as a large number of unlabeled examples, and represents a blend of supervised and unsupervised learning. We formulate a regularization approach to linking the marginal density (estimated from unlabeled data) to the conditional (estimated from labeled data) in a general way. The regularization penalty measures the information that is implied about the labels over covering regions. No parametric assumptions are required and the approach remains tractable even for continuous marginal densities P(x). We develop algorithms for solving the regularization problem for finite covers, establish a limiting differential equation, and exemplify the behavior of the new regularization approach. Classification with partially labeled data involves learning from a few labeled examples as well as a large number of unlabeled examples, and represents a blend of supervised and unsupervised learning. We formulate a regularization approach to linking the marginal density (estimated from unlabeled data) to the conditional (estimated from labeled data) in a general way. The regularization penalty measures the information that is implied about the labels over covering regions. No parametric assumptions are required and the approach remains tractable even for continuous marginal densities P(x). We develop algorithms for solving the regularization problem for finite covers, establish a limiting differential equation, and exemplify the behavior of the new regularization approach.  Generalized Robust Conjoint Estimation PI: T. Poggio Participants: Giorgos Zacharia, Constantinos Boussios, Theodoros Evgeniou Abstract: We present a framework within which models of preferences that are robust to noise and can