Adaptive Information Filtering with Minimal Instruction



Progress Report: July 1, 2002óDecember 31, 2002


Tommi S. Jaakkola and Tomaso Poggio




Project Overview


This project concerns with automated methods for finding a few pieces of relevant information (such as research articles) within a large dataset of predominantly incomplete and superficially similar information (such as technical report archives). While many such information filtering tasks vary considerably depending on the context, the primary challenges associated with automated techniques are often shared across different tasks. In this project, we develop the foundations for adaptive information retrieval tools with the ability to function accurately with minimal instruction of what is relevant, learn from related filtering problems, and make use of any optional feed-back automatically queried from the user


Progress Through December 2002


We have made progress on several fronts and outline here three areas in particular: 1) classification with unlabeled examples, 2) collaborative filtering, and 3) feature induction for text classification.


Classification with unlabeled examples. We have developed a new principle for combing unlabeled and labeled examples for the purpose of accurate classification of documents. The key motivation for this work is that the labels or relevance assessments that one is interested in learning to predict are often largely missing in the available data. Standard statistical methods are therefore not effective in this context as they have been developed primarily under the assumption that the key information is missing in only a small fraction of the available cases. Our principle is the first to articulate in probabilistic terms how the conditional distribution of labels given documents -- quantity needed for classification -- should in general relate to the marginal distribution of documents or the large number of unannoted documents. The principle is cast in terms of regularization theory and penalizes information about the labels that is introduced beyond the few available labeled examples. This ensures that the classification decisions for unlabeled documents are based firmly on the available information. Effectively, the regularization principle states how the conditional probabilities should be interpolated over the unlabeled points on the basis of the few labeled examples. More generally, the principle is formulated in terms of Tikhonov regularization theory.


(While information regularization was already mentioned in an earlier report, the idea has been extended considerably in the last six months.)


We are actively developing efficient algorithms for exploiting this principle in practical applications. We currently have two publications pertaining to early versions of the information regularization work:


                  Ph.D. thesis by Martin Szummer (jointly advised by T. Jaakkola and T. Poggio):

                  Final version of the paper presented at the NIPS conference:


Other material currently in preparation will be distributed as they are completed.


Collaborative filtering. Collaborative filtering provides a simple and efficient way of exploiting what is common to groups of decision makers. A typical collaborative filtering approach involves finding a low rank factorization of the data matrix containing user identities and their preference decisions. The low rank factorization that should capture shared features across users is, however, often estimated by assuming a simple squared loss between the data matrix and the predictions. This error measure is mathematically convenient but rarely reflects the structure of the problem. More appropriate error measures such as those based on probabilistic classification methods make the low rank factorization problem somewhat more challenging from a computational perspective. In particular, we can no longer obtain the solution in closed form and have to find the underlying low rank representation with iterative algorithms. We have developed several new algorithms for finding low rank matrix factorizations in the more general contexts relevant for collaborative filtering. The simplest such algorithms cast the  iterative steps of the estimation process in terms of incomplete data estimation and formulate an EM algorithm for finding the low rank matrix factorizations. The mathematical foundation of these ideas can be found in the following technical report


                  N. Srebro and T. Jaakkola, "Generalized Low-Rank Approximations", AI Memo 2003-001.


The paper detailing an application of these ideas to collaborative filtering is under preparation and will be made available shortly.


Feature induction for text classification. An important problem in document classification is to find the set of text features that are useful for classification, both in general and in the context of a specific classification task. We cast the problem in terms of data compression and systematically search for features in the documents so as to best compress the labels (or summaries) that one is interested in predicting. The features come in two forms: those that are common to a number of classification tasks, and those that are useful only within a single task. Generic features that are useful across tasks are much less costly to introduce (they need to be encoded only once) but may not suffice for the specific task at hand.


A brief and preliminary description of some of these ideas can be found in:


                  J. Rennie and T. Jaakkola, ìFeature induction for text classificationî, AI Abstract 2003,


Research Plan for the Next Six Months


Our plan for the next six months consists primarily of the following tasks:


Developing and testing efficient algorithms for exploiting information regularization principle in large scale applied problems. Specifically, we hope to solve the regularization problem within a constrained class of conditional probabilities.  


More extensive adaptation of generalized low rank estimation algorithms to collaborative filtering tasks.

Formulating and testing active learning methods in combination with the information regularization framework. This approach would not only make an appropriate use of the available unlabeled documents but would also exploit resulting classification decisions to iteratively find the most informative new documents to label.


We seek to extend the overall active learning framework to efficiently annotate documents in large databases with multiple topic labels. This would be done in collaboration with Dr. Naonori Ueda.