Hal Daume - US grants

This project considers the problem of simultaneously solving multiple
component-level natural language processing problems. Such
component-level tasks are necessary as building blocks for large-scale
applications (eg., automatic document summarization, machine
translation, etc.), but are typically solved independently. These
independent solutions ignore the natural connections that relate the
output of one problem to the output of the other. This research
explores the ability to exploit such output correspondences to aid
machine learning algorithms, termed "Cross-Task Learning." These
output correspondences provide strong prior information about the
relationship between the desired outputs of multiple problems. This
prior knowledge can potentially serve to improve task-level
performance, even when large amounts of training data are unavailable.
The research exploits such prior knowledge using a k-best methodology
so as to maximize the applicability of these techniques. It also
develops new techniques for semi-supervised learning based on the idea
of output correspondences in order to capitalize on the vast amounts
of unannotated data that are available. In addition, the proposed techniques
are analyzed in the context of computational learning theory. The outcome
will be a set of techniques for learning across multiple natural language processing
tasks. This technology will be empirically evaluated in the context
of low-level tasks such as shallow parsing and named entity
recognition, as well as the high-level tasks of discourse analysis and
automatic document summarization.

Objectives of the Project
We propose a workshop for brainstorming and planning for the Computational Thinking Olympiad (CTO). The goal of this olympiad is to increase the awareness of Computational Thinking at the high school level.
The proposed workshop will be focused on deciding on the desired content of the Olympiad. We have generated (though an NSF-sponsored REU supplemental grant) a private Wiki that contains lists of example problems from related programs, such as COMAP, ACM Programming Contest, ICPC and IOI. The Wiki contains over 40 example problems. In this proposed workshop, we will
discuss these related programs, determine the niche into which the CTO would t, and determine what sorts of problems t best therein.
At the conclusion of the workshop, our aim is to have de ned the sort of problem to be solved at the CTO, decided the roll of programming projects in the CTO, and placed ourselves within the context of other, related, Olympiads.

This project considers the unification of two view of language: that
from natural language processing and that from linguistic typology.
Our view is that typological information is both useful for solving
real-world natural language processing thats and automatically
derivable from language data. This research first explores how to use
typological knowledge to improve performance on problems such as
dependency parsing and machine translation for low density langauges.
Intuitively, our statistical models waste time exploring a hypothesis
space that is too big: the space of realistic grammars is much smaller
than the space of all grammars. The second part of this research
considers the automatic acquisition and boostrapping of typological
knowledge from raw text. The outcome of this research is: (a)
improved statistical models for hard natural language processing
problems; and (b) a larger library of typological universals that have
been derived automatically from data. Our outcomes are empirically
evaluated on the raw language processing tasks and in terms of the
quality of the universal implications mined from data, but comparing
them with known repositories of universals.

Our results will impact the fields of natural language processing and linguistics. From the research side, this research will find applications in a wider variety of problems than the ones we intend to study; in particular, the use of linguistic universals in natural language processing technology
will fundamentally change the way multilinguality is addressed in this
field. From a linguistics perspective, the goal of this project is to
shed new light on linguistic universals. This should impact not only
the area of typology, but also the study and preservation of
endangered languages. By automatically identifying typological
features and implications from data, the process of documenting
endangered languages could be made more efficient: leading to a
smaller loss of knowledge of these languages.

This project focuses on developing the infrastructure for a self-sustaining organization that can manage, grow, and evangelize olympiads that involve young students (middle and junior high) in computational thinking. A large component is the creation of pilot olympiads in a select few cities in the United States. Specific goals of this project include: (1) identifying a set of foundational skills that underlie computational thinking that can be taught before college and high school; (2) identifying a style of problems and scenarios that engage a wide variety of students; and (3) implementing a curriculum of training sessions and contest questions that exemplify those foundational skills.

There are two broad reasons for creating a Computational Thinking Olympiad. First, to expose the fundamentals of computational thinking to a broad audience of potential researchers and practitioners in the field, thus increasing participation and diversity in computing. Second, to ensure long-lasting impact beyond of this project.

The success of the Computational Thinking Olympiad will have a significant impact on our society by introducing middle school students to computational thinking in its breadth and depth: (1) encouraging students to have fun with the computational thinking in an arena that is both cooperative and competitive; (2) encouraging students to pursue education in computing; (3) introducing the unplugged parts of computing to those who have not had access to the plugged-in parts; and (4) showing that computational thinking is not ``just'' programming.

This project uses machine learning to accelerate the execution of a class of computer programs relevant to AI. Given a program and a class of inputs, the new methods automatically seek execution strategies that are fast while still achieving a high level of accuracy.

The project focuses on the main inference algorithms that underlie statistical AI: dynamic programming, belief propagation, Markov chain Monte Carlo, and backtracking search. Each of these inference algorithms faces an enormous search space, iteratively extending or refining its picture of this space. Each algorithm must continually choose which computational step to take next.

The opportunity is to learn a strategy for making these choices. Some choices are on the "critical path" and help the system find an accurate output, while others lead mainly to wasted work. The learned strategy for evaluating choices in context may itself be computationally intensive, so the method learns to speed that up as well, within the same framework.

The project will disseminate software and will have broader impact on several fields. The targeted algorithms are central to natural language processing, speech processing, machine vision, computational biology, health informatics and music processing. Their ability to form a coherent global analysis of a set of observations is a hallmark of intelligence, and will enable artificial systems that aid human understanding and performance. Speeding them up is critical as researchers develop increasingly sophisticated statistical models.
Furthermore, the learning methodologies developed will be useful in other settings that attempt to learn computational or behavioral strategies.

The project supports graduate student participation in the 28th International Conference on Machine Learning (ICML 2011). Specifically, the project supports travel to the conference for those who might not otherwise be able to attend for financial reasons, and organizes a student poster-presentation program that will facilitate one-on-one discussions and other mentoring with the world's leading researchers in machine learning. Students are exposed to state-of-the-art work by other researchers and have the opportunity to attend tutorials on material that is not taught at their home institutions. Participating students receive feedback from senior researchers beyond their institutional and national boundaries. Furthermore, participation in the poster session and conference helps to integrate these students into the research community and represents a natural integration of research and education.

To apply machine learning to problems in the physical world, one needs models/algorithms that are faithful to physics. We consider understanding how the anatomical structure of the body and ears leads to the remarkable ability to localize a sound source in a complex and noisy environment that is innate in most animals and humans. The cues used in localization arise from the process of the acoustic wave scattering off the complex-shaped listener's body and ears. Numerically, these changes in the sound spectrum are characterized by the head-related transfer function (HRTF). Every person's body is unique, and the HRTF is highly individual. It is possible to measure the HRTF; however, the measurement requires specialized hardware and is tedious. There has been considerable interest in convenient methods to obtaining the HRTF. We propose to develop a framework to perform machine learning to establish a relationship between the anatomy and HRTF. An HRTF database with 100 subjects, along with their anthropometric measurements, is available. A novel LMA (Learning of Multiple Attributes) algorithm will be developed. The key properties of this algorithm are that it can incorporate physical constraints into the learning and predict complex structured outputs in continuous spaces. The algorithm will find the low-dimensional manifold in high-dimensional HRTF space and to map the manifold structure to anatomical parameters.

The research will create novel machine learning algorithms that are able to incorporate physics based constraints, and these will find application in other problems. HRTF generation from simple body measurements will allow introduction of personalized spatial audio into fields such as human-computer interaction, consumer electronics, auditory assistive devices for the vision-impaired, robotics, entertainment, education, and surveillance. Training of K-16 and graduate students in the proposed research will add to the nations talent pool.

There is an urgent need for models of financial ecosystems that are driven and informed by data. Unfortunately, current financial cyberinfrastructures severely restrict the availability of data to market participants, regulators and researchers. There are constraints on the data collection authority of regulators that are exacerbated by the lack of ontologies and standards. Beyond these limitations is the inherent challenge of dealing with the complexity of financial information and meeting the diverse and sophisticated analyses required to model heterogeneous ecosystems.

For computer scientists to get engaged, a central requirement is the availability of data -- as exemplar and for testing and benchmarking. While some types of data are easily available, many other important types of financial data are proprietary and generally unavailable to the computing research community. The creation of a community infrastructure can go a long way toward meeting this need and hence enabling computer science research in a new domain of data science for finance.

The impact of the next generation of community financial cyberinfrastructure and a framework of data science for finance will be significant. There will be increasing synergy from applying computational technology, BIGDATA and Linked Data, and social media, to address difficult modeling and monitoring problems. This may result in improved tools for regulators, as well as fundamentally new designs of market mechanisms, recommendations, ratings, etc. On the educational frontier, data science for finance should nurture a new generation of multi-disciplinary scholars who will blend computational solutions with theories, models and methodologies from finance, economics, mathematics and statistics.

Machine learning algorithms cannot "think on their feet". When applied in practice, most approaches developed using traditional machine learning techniques wait for an entire input to arrive before they are able to provide an answer or react. While sufficient for some tasks, this is inappropriate for a large class of problems that require more immediate or incremental responses. This project develops new algorithms to address machine learning problems that require an algorithm to "think on its feet". These algorithms combine guesses about what input is likely appear in the future with actions that the algorithm should take now to provide useful, effective output in a timely fashion.

One application of these new methods is simultaneous translation. This is the problem of taking problem of "observing" a sentence one word at a time in a foreign language, such as German, and providing a real-time running translation in a target language (like English). This is particularly difficult for language pairs that have significant syntactic divergences, such as object-verb order differences between foreign languages like German or Japanese (verb final) and target languages like English (verb medial). Like human simultaneous translators, machine learning algorithms must learn to predict the words that will appear at the end of a sentence. The project facilitates this prediction using a framework that combined word prediction and machine translation system.

The project also uses the newly developed algorithms in academic settings to provide significant outreach to high school students and undergraduates, particularly in underrepresented communities.

Algorithms that can understand human language must be able to recognize the underlying structure (e.g., subject-verb-object) of that language. Computational approaches developed in the natural language processing community typically have build ad hoc, one-off algorithms for solving the hard, combinatorial optimization problems that arise in such tasks. Most large-scale systems are built using complex combinations of heuristics applied to try to make approximate search techniques better. Concurrently, the algorithms community has developed scalable exact algorithms and approximation algorithms for solving many of these hard combinatorial optimization problems. This EArly Grant for Exploratory Research investigates the connection between these two extremes: the language processing community with the hard problems they need solved, and the algorithms community with the provably correct algorithms for solving such hard problems. The biggest technical challenge this exploration addresses is how to couple the statistical learning algorithms necessary to build effective language applications with the types of abstractions that make efficient algorithms possible. In particular, this project explores the application of "inverse optimization" to machine learning. For example, if one has access to an efficient algorithm for solving a particular discrete optimization problem, how can one learn parameters that make that particular algorithm as high accuracy as possible? Success in this project will give rise to theoretically principled, efficient algorithms for learning to solve complex linguistic tasks, which can transform to downstream applications like machine translation, automatic question answering and information retrieval.

This project's main technical innovation is the coupling of "inverse optimization" problems with online learning techniques. For instance, suppose that the end goal is to find some particular structure. The search for this structure can often be cast as a particular form of dynamic programming problem, which in turn often becomes a shortest path problem in a hypergraph. The machine learning challenge then is to learn a model under which the solution to this shortest path search is actually the desired structure. From an algorithmic perspective, this requires finding a set of inputs under which a given structure is optimal: inverse optimization. However, it is not enough for a given structure to be optimal: it must also beat all other (non-optimal) structures by some given margin. This project will develop a combination of online learning algorithms and inverse optimization formulations that enable such advances.

Language learning, in humans and machines, has far-reaching relevance to global technology, commerce, education, health, and national security. This National Science Foundation Research Traineeship (NRT) award prepares doctoral students at the University of Maryland, College Park with tools to advance language technology and language learning. The program provides trainees with an interdisciplinary understanding of learning models from cross-training in linguistics, computer science, and psychological and neural sciences, and with the tools to work with multi-scale language data. The training program contributes to the public understanding of science through a policy internship program that engages trainees with federal agencies and Washington-area professional organizations. Moreover, by contributing to the development of a free public digital linguistic tool, Langscape, it will provide a valuable resource for researchers, the public, the government, and nongovernmental agencies to discover geographical and linguistic information about languages of the world.

Flexible and efficient language learning, in humans and machines, is the research focus of this NRT program. The research hypothesis is that improvements in learning in machines and in humans will come from the ability to use training data more efficiently at multiple scales. Through interdisciplinary team approaches, trainees will explore efficient use of language data, with a focus on the informativity of data to human and machine learning. Through a suite of training activities that includes intensive summer research workshops, engagement with undergraduates and K-12 schools, and policy internships, trainees will become flexible communicators in writing and speaking and also learn to apply their research to diverse contexts.

This project studies novel algorithms for building artificial intelligence (AI) systems that can learn to improve their performance with a human in the loop. Many recent AI successes are driven by large, expensive and difficult-to-collect datasets. This yields systems that are deep, but narrow. The goal of this project is to build technology that will allow AI systems to learn from their interactions with people. The project focuses on key applications related to natural language understanding: building technology to understand the meanings of individual sentences, and integrate those meanings into the meaning of a discourse or dialog. One specific application pursued herein relates to extracting biomedical knowledge from text, which will pave the way to helping biomedical researchers develop novel hypotheses. The work will fund students from underrepresented groups in STEM, and encourage cross-disciplinary education at the graduate and undergraduate levels. Finally, the work will be communicated to the public not just with scientific papers, but internationally through social media and locally through visits to middle schools and high schools.

Natural language processing (and other fields of artificial intelligence) have had enormous success by training supervised learning systems on large labeled datasets ("corpora"). Unfortunately, curating such corpora is infeasible except for very specific problems. This happens either because it is too expensive, or it is too difficult to get human labelers to agree on an annotation standard. Instead of relying solely on human labeled data, this project develops algorithms that can learn from human interaction. These systems can continually improve their performance based on downstream performance supervision, often with a human in the loop. This work leverages recent developments on the structured contextual bandits learning framework which provides a theoretically grounded and computationally efficient way in which to develop novel approaches to distant supervision. This resulting learning techniques will push advances in natural language understanding: semantic parsing and discourse interpretation. Furthermore, the underlying imitation learning technology is broadly applicable, including novel applications to recurrent neural network models. To aid adoption by the research community, code and data from this project will be released open source.

Interpretation, the task of translating speech from one language to another, is an important tool in facilitating communication in multi-lingual settings such as international meetings, travel, or diplomacy. However, simultaneous interpretation, during which the results must be produced as the speaker is speaking, is an extremely difficult task requiring a high level of experience and training. In particular, simultaneous interpreters often find certain content such as technical terms, names of people and organizations, and numbers particularly hard to translate correctly. This Early Grant for Exploratory Research project aims to create automatic interpretation assistants that will help interpreters with this difficult-to-translate content by recognizing this content in the original language, and displaying translations on a heads-up display (similar to teleprompter) for interpreters to use if they wish. This will make simultaneous interpretation more effective and accessible, making conversations across languages and cultures more natural, more common, and more effective and joining communities and cultures across the world in trade, cooperation, and friendship.

Creating these systems is a technically challenging problem and has not previously been attempted. One challenge is that simultaneous interpretation is already a cognitively taxing task, and any interface must not unduly increase the cognitive load on the interpreter by being too intrusive. Reducing this cognitive load requires an interface that can decide when to provide translation suggestions and when to refrain from doing so. To achieve this goal, this project will develop methods that are robust to speech recognition errors, and learn what to display by observing the interpreters' interpretation results. The utility of the proposed framework will be evaluated with respect to how much it improves the ability of interpreters to produce fluent, accurate interpretation results, as well as the cognitive load the additional interface imposes on them.

Online platforms bring out the best and worst of free speech: while they help us make connections and share ideas, they can also facilitate hate speech and extremism. Content moderators work to enforce community rules designed to mitigate these negative behaviors, but face a high burden from repeated exposure to toxic content. In principle, automated tools that use natural language processing (NLP) and machine learning (ML) techniques could ease this burden. However, current NLP and ML techniques can be circumvented by determined posters through the use of subtle and coded language, and the moderation tools that use them are often hard for moderators to configure for their community's norms, policies, and moderation practices. This project leverages the fact that communities already make and enforce diverse speech policies online to 1) teach software to learn nuance from the decisions moderators make in existing communities; 2) support moderators by not only flagging content, but also suggesting decisions and providing explanations for those decisions; and 3) provide auditing tools that help community members know that moderators are acting in accordance with norms and policies. In doing this research, the team will develop tools to support healthier online communities, particularly volunteer-led communities, by strengthening policy enforcement, enabling better working conditions for online moderators (who are often from marginalized communities), creating more flexible software responses to community policies, and supporting adaptability to future regulation of content moderation.

To achieve these goals, the cross-disciplinary project team is conducting cycles the involve empirical needs-finding studies with moderators, development of NLP and ML-based tools, evaluation, and iterative improvement of those tools. The project's empirical studies will advance knowledge of how ``machine-in-the-loop'' moderation (where automated tools make or support moderation decisions) impacts moderator working conditions and online participant experiences, as well as informing evaluation mechanisms for measuring the success of the ML tools at respecting online community policies and identifying unwritten community norms. The project's design process will make fundamental progress in ML algorithms that learn from few labels using justifications provided by moderators, as well as improving explanations for machine decisions based on human rationales. Together, these advances produce new design methods for ML tools that adapt to complex written policies and identify unwritten social norms, serving multiple stakeholders accountably and transparently.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.