Current Projects

Active Learning for Machine Translation
Statistical machine translation methods rely on large quantities of training data to learn various models. We are investigating applications of active learning to both minimize the amount of training data required (for example when moving to new domains or in languages where large amounts of text is not available) as well as integrating a human in the training process to help answer difficult questions, such as translations of phrases, that will help improve the overall translations.

Phrasal Improvement of Machine Translation
Given a machine translation function and bilingual data, we can generate an aligned Enlish/English data set by translating the foreign sentences with the translation function. Differences between these sentences point to possible mistakes in the translation function. We are investigating various same language alignment methods on this data. Given these alignments, phrase correction rules can be learned. Initial investigation shows major improvements in commercial translation functions and some improvement on phrase based systems.

Unsupervised Pronoun Resolution
Research with Andy Kehler and Lara Taylor

Most data driven pronoun resolution techniques rely on labeled data for training. Recently, there has been some work showing that unlabeled data can be used to train these pronoun/antecedent models. Using a large corpus of text, unambiguous pronouns are identified and used to bootstrap a model. Using this model, new pronouns are labeled and the process is continued until convergence. The advantage of these unsupervised methods is that they have much larger data sets available than for supervised. We are investigating an expanded set of features for pronoun resolution that leverage this increased amount of data.

Binarizing Translation Rules
Research with Kevin Knight and Daniel Marcu at ISI

Recent translation models for statistical machine translation involve syntactically motivated translation rules (Galley et. al). Empirically and qualitatively this type of translation approach seems to be a good way to integrate syntax into the translation process while still maintaining many of the advantages of current state of the art phrase based systems. Decoding with these rules is similar to parsing with additional complications. CKY style, bottom up type parsing methods appear to be a good approach for this model.

One of the complications for many bottom up algorithms is that the grammar must be binary (i.e. at most two elements on the right hand side). Binarization of PCFG rules is fairly straightforward. Binarization for translation rules is an interesting area of research since the rules are more complicated (i.e. left hand side consists of a tree, not just a non-terminal) and because other models are used during decoding such as the language models. The binarization process can be biased so that partial hypothesis and future cost estimation are more accurate.

Hierarchical Clustering with Bregman Distances
Research with Sanjoy Dasgupta and Anjum Gupta

In 2003, we introduced an iterative hierarchical clustering method. The problem with previous approaches is that they are greedy. Once a decision is made in constructing the hierarchy, this decision can never be undone. The iterative approach we presented searches the space of hierarchical clusterings and therefore does not have that problem.

The iterative approach attempts to minimize a criterion function based on the current clustering. In our initial paper, we used a squared Euclidean cost function similar to that of K-means. Euclidean distance is just one of a family of distance metrics called Bregman distances. We are examining how these distances can be integrated with our iterative method. The hope is that these new distance metrics will fit more naturally for a variety of different data sets where Euclidean distance is not appropriate.

Previous (Unpublished) Projects

Searching Research Papers
Research with Vibhu Mittal at Google

Information retrieval of research papers provides a number of interesting problems that are different than traditional information retrieval. First, extracting information from non-text files is non-trivial and information such as authors, titles and references must be extracted from research articles before further processing. This can be difficult due to the wide variation of formatting and conventions. Once this information has been extracted, the citation graph of research papers provides a very interesting search structure that is much more reliable than traditional web link structure.

Reinforcement Learning for Traffic Navigation
Preliminary paper available

In this paper we examine reinforcement learning problems which consist of a set of homogeneous entities. 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 related problems.

Vision Techniques for Audio Processing
Preliminary paper available

In this paper we discuss the problem of audio retrieval. We examine artist recognition/retrieval as a problem instead of the traditional genre classification. This problem has the motivating benefit that there is a known, uncontroversial ground truth. Second, and more importantly, we suggest borrowing research from the image retrieval community. We provide results from one image retrieval technique ported over to audio retrieval. This technique consists of taking the discrete wavelet transform of the audio, histogramming the results and using statistical histogram comparison metrics to compare similarity. The results are not outstanding, but we do show that this sort of research can be done fairly easily and productively.

Dynamic Resource Allocation in Heterogeneous Computing Environments

The increasing power of modern personal computers is making clusters, which are built up from desktop components increasingly popular. However, these clusters do have their drawbacks. When clusters are updated, the whole cluster may not be upgraded all at once. This will lead to an environment where there are some nodes that are faster than others. This irregular environment can occur more simply in the case where jobs are running on some of the nodes. These nodes will tend to run slower than the free nodes. There are a number of problems such as RedBlack3D that have highly regular rectangular partitioning schemes. Unfortunately, if these static partitions are used in the environment just described, idle waiting can occur when faster nodes have that have finished their iteration early and are stuck waiting at a synchronization point for slower processors to finish. We investigate a load balancer that can adaptively tailor per-node workloads to node speed to help reduce this inefficiency.