See here for project reports from June 2001.

Kristin Branson, Label-preserving dimensionality reduction.

Abstract:  Many tasks, such as face recognition, require learning a classifier from a small number of high dimensional training samples.  These tasks suffer from the curse of dimensionality: the number of training samples required to accurately  learn a classifier increases exponentially with the dimensionality of  the data.  One solution to this problem is dimensionality reduction.   Common methods for dimensionality reduction such as Principal Component  Analysis (PCA) and Fisher's Linear Discriminant Analysis (LDA) have  undesirable properties.  PCA is an unsupervised algorithm, while LDA cam only produce a small number of components and assumes the data is normally distributed.   A new algorithm framework proposed in this paper, Structured Principal Component Analysis (SPCA), does not have these undesirable properties.  SPCA structures the data in a supervised way, then applies PCA to each structure.  SPCA first clusters together similar features of the data, using a supervised  similarity measure that makes small, reasonable assumptions about the data.   From each cluster of similar features, a small number of components are chosen to represent that cluster.   The instantiation of SPCA employed in this paper uses the normalized cut  criterion to cluster the features.  The similarity measure used is the same-class Chi-squared distance between each feature over all the training data.  Finally, PCA is used to extract a small number of components from  each cluster.  This algorithm was tested on two face recognition databases, with encouraging results.

Abstract:  We discuss a reinforcement learning framework where learners observe experts interacting with the environment. Our approach is to construct from these observations exploratory policies which favor selection of actions the expert has taken. This imitation strategy can be applied at any stage of learning, and requires neither that information regarding reinforcement be conveyed from the expert to the learner nor that the learner have any explicit knowledge of its reinforcement structure. We show that learning with an imitative policy can be much faster than learning in isolation. We also show that our approach is robust to sub-optimal experts.

Abstract:  Random projection is a technique for dimensionality reduction technique that has recently been successfully incorporated into the learning of mixtures of Gaussians with the EM algorithm.  In this work we examine how to use random projection to learn other mixture models.  We use random projection in conjunction with EM for mixtures of Gaussians to learn a high dimensional probabilistic graphical model.  In our experiments we find that while the model learned by the method that incorporates random projection learns a less accurate model than the one which does not, the models learned are qualitatively and structurally very similar.

Abstract:  In data clustering with k-means, the choice of the number of clusters k reflects prior knowledge about the structure of the dataset to be clustered.  However,  choosing k is not always easy or obvious, and learning should discover k as well as the parameters for each cluster. In this paper we develop a new way of choosing k based on a statistical hypothesis test.  The basic idea is that two centers should not be used to represent a cluster that is in fact Gaussian.  Our test builds on the x-means framework of Pelleg and Moore, but is more flexible test and produces better results.  We present synthetic and real-world experiments illustrating the success of our algorithm.

Abstract:  We examine reinforcement learning problems which involve a set of homogeneous agents.  These problems tend to have extremely large state spaces making standard approaches unattractive.  We study lane change selection in a car traffic control problem as an example of such a problem.   We show how a single agent problem can be translated into an approximating multi-agent problem.  We provide learning results in a traffic simulator using this multi-agent approximation with Q-learning and R-learning.  Learning in the multi-agent problem proceeds quickly and outperforms heuristic methods.  Experimental results show that learned methods perform better than heuristic methods as traffic densities increase towards rush hour conditions.  We summarize the translation method used from a single agent problem to a related multi-agent problem for car traffic control and propose this as a starting place for solving related problems.

Abstract:  We show how to apply a new probabilistic modeling framework, Maximum Entropy Markov Models, to the protein secondary structure prediction problem.  As in previous domains, such as the task of segmenting a body of text, to which MEMM was applied, the protein secondary structure prediction problem requires labeling an observation sequence.  This paper is an exploratory effort that attempts to establish the feasibility of using the new framework on this long-standing problem.  Our initial results produced with a rather simple MEMM model show promise (over 58% accuracy) and suggest directions for further improvements.

Abstract:  We investigate feature extraction and selection in the framework of automatically classifying forestry images according to their esthetic beauty. We experimentally evaluate three recent advances in feature selection: a wrapper method proposed by A. Ng that is robust when the number of irrelevant features is large compared to the number of relevant ones, and filter methods based on boosting and support vector machines (SVMs). As a baseline, we use 65 features chosen according to human expertise, which lead to 18.9% of error when the classifier is an SVM. A data-driven method proposed by K. Tieu and P. Viola is used to obtain 46,875 alternative features.  Feature selection methods are tested using these data-driven features.  The SVM-based filter method achieved 18.9% of misclassification rate using 10,000 features, and a wrapper method with an SVM classifier led to 21.4% using only 4 features.  We also discuss why, in practice, it is more convenient to use a filter method to pre-select features for wrappers than to use Ng's wrapper method with all features.