Jaime Carbonell - US grants

This project provides partial funding for a symposium on Artificial Intelligence, jointly sponsored by NSF and the Japanese Institute for New Generation Computer Technology (ICOT). The purpose of the joint symposium is to provide a venue for the interchange of new scientific ideas, methods and approaches between the researchers from the U.S. and Japan. The main focus of the symposium is on artificial intelligence architectures, foundational aspects of artificial intelligence, artificial languages and methodologies, natural language processing and learning, and machine learning and knowledge acquisition. The 3- day symposium will be held in Tokyo, Japan, with a fourth day scheduled for a visit/tour of the ICOT facility.

This is the first year of a three year continuing award. To plan in complex, large-scale tasks requires elaborate and costly knowledge engineering and programming to design and implement task-specific planners. General planning methods, on the other hand, apply only to small constrained tasks because of the inherent combinatiorial search. Although some worthy inroads have been made by modern planners, such as SIPE, to combine general planning methods with hand-crafted domain heuristic, This research considers a different alternative: focused machine learning of control knowledge to guide search. In particular, the fully-implemented PRODIGY planner presents the ideal substrate on which to investigate multiple learning methods. Previously explanation-based learning was successfully integrated in PRODIGY. This research addresses automated acquisition of abstraction spaces for hierarchical planning, case-based learning with derivational analogy, and their synergistic integration. Proper abstractions in partially-decomposable domains provide major performance improvements, and automated abstraction eliminates the bottleneck of laborious hand-coded abstraction. Derivational analogy provides and extremely flexible case-based replay mechanism, falling back to general planning when solution to subgoals do not transfer. Together, both methods should prove even more effective, with abstraction providing the key indices for case-based memory search (those features that cannot abstracted away, such as bottleneck points or roots of dependency networks), and derivational analogy speeding up search within abstraction spaces. Through this automated acquisition of control knowledge, planners will be able to solve increasingly complex planning domains.

The Machine Translation Summit is the third international meeting for exchange of scientific, technological and user-oriented information on machine translation. It is being held for the first time in the U.S. where there is increasing research interest in the area. Further stimulation to the research area will be achieved by including partial support for student participation through scholarships. This meeting is jointly funded by the DARPA Speech and Language effort.

9314959 Cole This is the first year of a continuing award in the NSF/ARPA Human Language Technology initiative involving cooperation between the Oregon Graduate Institute and the International Computer Science Institute. The proposed project considers research on: a) signal representation methodologies that would combat environmental noise and non-linearities which detract from automatic speech recognition, b) speaker variability which is a source of uncertainty also in recognition, and is to be tackled from a probabilistic point of view from collected (telephone) speech corpus, and, c) dialogue enhancement methodologies and strategies, including recovery, in order to increase the probability of correct recognition. Each of these three areas comprise major deterrents to robust recognition that will be investigated. The overall objective of the project is to consider integrated approaches to spoken-language system robustness. 9314946 Flanagan This is the first year of a continuing award in the NSF/ARPA Human Language Technology for cooperation between researchers at Rutgers University's Center for Computer Aids for Industrial Productivity (CAIP), AT&T Bell Laboratories and General Dynamics Electric Boat Division. The research to be conducted concerns the generation of speech signals in terms of (a) an articulatory description of the vocal system, and (b) a fluid dynamic solution to the generation, propagation, and radiation of audible sound produced by the acoustic system. This includes the computation of the speech signal from first principles, using the Navier- Stokes description of fluid flow, already demonstrated feasible. Anticipated results include a potentially significant improvement in the quality of synthesized speech and fundamentally new and more robust designs of speech recognizers stemming from a better understanding of the speech phenomena and how it can be made more immune to interference. Also it is expected that t his research influence improvements in the coding of speech at lower bit rates. 9314967 Price This is the first year of a continuing award in the NSF/ARPA Human Language Technology initiative involving cooperation between researchers at SRI International, Stanford University and the Massachusetts Institute of Technology. The proposed project considers research on the hypothesis that disfluencies in spontaneous speech - pauses, repeated words, repairs, filled pauses, word fragments, and elongated segments - are far from random and that knowledge about their regularity would shed light on aspects of human cognition and provide principled methods for dealing with them in spontaneous speech processing. Several relevant disciplines are involved in this effort such as human- computer interaction, linguistics, psycho-linguistics, computational linguistics, prosody, and speech technology. The multi-disciplinary approach includes investigating the forms and distribution of disfluencies across many corpora, conducting perceptual experiments to assess the saliency of specific cues in the signal, and developing and evaluating new methods for automatic processing of speech. 9314955 Pustejovsky This is the first year of a continuing award in the NSF/ARPA Human Language Technology initiative involving cooperation between researchers at Brandeis University and at Apple Computer. The research involves the building of a generative lexical engine at the core which aids in the determination of word sense following lexical properties considered composable in a given phrasal context. The project instantiates a lexical semantic segment of a substantial fragment of English by constructing such core lexical engine with the following components: a semantic typing system, relational structures for all categories, and generative mechanisms enabling extension and identification of word sense in context. The project is complementary to other initiatives to develop linguistic infrastructure resources on a large scale, such as COMLEX and WordNet. The project develops mechanisms that carry out the specialized lexical inferences that result, through composition of lexical types, in word sense determination. 9314969 Sleator This is the first year of a continuing award in the NSF/ARPA Human Language Technology initiative involving cooperation between researchers from Carnegie Mellon University and International Business Machines. This project intends takes advantage of the simplicity of the classical statistical trigram model of language while augmenting it with the syntactic and semantic aspects which constrain the use of the new grammatical trigram model to advantage over the purely stochastic model. The concepts of probabilistic link grammars are used in this research, incorporating trigrams into a unified framework for modeling long-distance grammatical dependencies in computationally efficient ways. The methods proposed are expected to have greater predictive power over current methods from the point of view of entropy measurements, and to integrate finite-state automata models and new statistical estimation algorithms with modern powerful machines resulting in improved speech recognition, translation, and understanding systems. 9314961 Thomason This is the first year of a continuing award in the NSF/ARPA Human Language Technology initiative involving cooperation between the University of Pittsburgh and the Stanford Research Institute. This project involves research on integrating the intentional and informational perspectives in architectures for interpretation and generation of interactive discourse. Particular problems investigated include the recognition by the listener of the speaker s plan, a formalization of the notion of conversational record, discourse structure from a computational point of view, and analysis of implicatures involving quantity and similar phenomena involvin g interactions between the processes of generation and interpretation. Bases for the research are the use of abductive inference in finite-state approximation methods and in knowledge-based systems, accommodation processes in interactive discourse, generation of coherent text, use of defeasible reasoning in plan recognition, and utterance planning to achieve communicative goals. 9314992 Young This is the first year of a continuing award in the NSF/ARPA Human Language Technology initiative involving cooperation between Carnegie Mellon University and the SRA Corporation. This project involves the investigation of methodologies for the extraction of information from text and its summarization in structured data records for subsequent automatic processing. The approach includes merging, fusing and consolidating multiple texts that address the same topic at one or more points in time and use of the results in the augmentation of existing knowledge bases, as well as in the detection of potential trends in the data. The basic issues investigated involve metrics to assess information consistency and redundancy, the probabilistic unification of multiple co-referential texts, methods for unifying representations of texts describing events that evolve over time, and constrained structural induction for predicting trends. The project uses pre-extracted representations of texts from the ARPA TIPSTER project, known to be noisy by containing errors of omission and commission, so as to increase the tractability of the project in an information rich description of events at single or evolving points in time, and in order to develop robust methods in the presence of inconsistencies and partial information.

This is a three-year standard award. The ultimate goal of the Universal Information Access project is the full democratization of information and knowledge access, by removing -- or greatly lowering -- educational, linguistic and socio-economic barriers to effective information access and use. Progress towards this goal requires us to address the following challenges: (1) Translingual information retrieval, in order to access documents across language barriers, and across same-language jargon barriers, (2) Multi-level summarization, customized to the user's profile and information needs, (3) Automated hierarchical categorization, via high-dimensionality statistical learning methods, (4) Detection and tracking, of new topics and events of interest to each user as they unfold, and (5) Information validation as a function of source reliability and inter-source consistency. These capabilities will be integrated seamlessly into an information navigator's workstation, using a common underlying object model and a user-centric interface for visualization and management of information. These methods will be evaluated both with respect to quantitative metrics and with respect to user feedback from realistic tasks. Universal information access requires more than search engines and web browsing. For instance, much useful information may exist in languages other than English, or may come from sources of unknown reliability. Moreover, rapid analysis of information requires customized summarization, anti-redundancy filters, and hierarchical organization. Advances in these areas are beneficial to all disciplines which must cope with large volumes of rapidly growing information, such as scientific research, crisis management, international business, and improving our educational infrastructure. The proposed research, in addition to its clear impact on democratizing information access, should provide significant advances in: Information Retrieval, Machine Learning, Digital Libraries, and user-centered Information Management.

This project will extend the state of the art in high performance multilingual information access, both in terms of underlying science and its technological realization via a functional prototype for English and German in the biomedical domain. Heretofore, Cross-Lingual Information Retrieval (CLIR) was founded upon dictionary-based query translation methods or corpus-based statistical learning of vocabulary mappings, combined with various IR methods. The existence of large, well accepted ontological resources in biomedicine (e.g., MeSH and UMLS) enables a new interlingual approach wherein both queries and documents are mapped into multiple taxonomic categories automatically, permitting direct conceptual matching. This research will compare existing techniques (dictionarybased and corpus-based) with the new interlingual methods on various evaluative dimensions, such as I I-point average precision, computational tractability, and end-to-end user acceptability. To judge the latter, a full prototype system will be developed; that is the main focus of the European side of the project. In addition to developing and evaluating these new CLIR methods, and producing and evaluating a usable prototype application, this project will provide other benefits beyond CLIR proper improving IR precision via automated corpus-based word sense disambiguation; developing statistical methods for the creation of multilingual lexical and phrasal resources; providing automated on-demand summarization of retrieved documents using the Maximal Marginal Relevance method; and improving multilingual information access and management systems forthe biomedical domain.

Our primary research goal is to develop a prototype voice-enabled
translating communicator which will deliver information services across
the linguistic divide for minority languages in order allow remote
linguistically-diverse users to communicate directly with Internet
content and databases, and more importantly to communicate with others
speaking a different language from their own. The latter will enable
information, education, and, for example, health services, to reach
remote minority-language communities. Achieving this goal requires
major advances in machine learning for translation and in cross-language
speech-recognition adaptability to wider language phenomena.

Traditional transfer-rule-based MT requires up to a person-century
to build and perfect a new language pair. Statistical and
Example-Based MT replaces human coding effort by vast amounts of
bilingual training data, which are virtually unobtainable for most
minority languages. Without a radical advance, leading to an
over-an-order-of-magnitude improvement in development time, the
only commercially justifiable MT applications involve the major
European languages, Japanese, Chinese, Korean, Arabic and perhaps a
couple more relatively-popular languages. The vast majority of human
languages are currently relegated to the proverbial MT dust heap.

We propose new MT approaches based on extended and new machine
learning methods. The first approach consists of statistical MT
methods that learn from orders of magnitude less training data,
and that can more effectively incorporate prior linguistic information
(including dictionaries, word classes, and known linguistic
rule classes or constraints) by using the joint source-channel
modeling approach combined with exponential (maximum entropy) models.
The second approach is a new method for acquiring high-quality MT
transfer rules from native informants which decreases dependence on
human experts and reduces development time. Semantically-conditioned
transfer rules are generalized via a new locally-constrained
Seeded Version-Space method based on a controlled bilingual corpus
and interactive tools to elicit information from native informants.
The third method builds general phone models across multiple language
families for speech recognition and adapts the recognizer to new
languages with minimal new- language training data. All of these
methods are based on new and existing machine learning algorithms
that combine prior knowledge with limited amounts of new data in
order to converge quickly on working machine translation and speech
recognition and synthesis systems.

The primary societal impact will be a significant contribution
to the global democratization of informa- tion, a process that
requires bridging current linguistic barriers, especially for
low-density or economically- disadvantaged languages. Additionally,
preservation and teaching of endangered languages will be directly
enabled by the new linguistic and acoustic knowledge coupled with
existing tutorial software. If successful, Avenue (Adaptable Voice-Enabled
Natural-translator for Universal Empowerment) will be the prototype
of an MT system that will empower world-wide access to multilingual
information.

EIA-0225656
Reddy, Raj
Carnegie Mellon University

Title: Computational Learning and Discovery in Biological Sequence, Structure and Function Mapping

Computer scientists, together with biological chemists will collaborate using statistical and computational tools and methods that the computer scientists have been developing for dealing with human language to better understand the function of proteins. Proteins are major players in the functioning of human and all other living cells.
As in languages, where sequences of letters determine patterns of words and sentences, sequences of amino acids in proteins determine protein structure, dynamics and function. Such sequences and their constituents can be thought of as syllables or words that have particular properties. Given these sequences, scientists want to be able to predict their geometrical structure and dynamics, and hence their function. A deeper understanding of the relationship between these is required so that the information hidden in the DNA sequences of genes can be used to develop drugs to fight disease. In particular, there is great societal demand to understand and treat degenerative diseases, many of which are based on defective triggers for protein shape and interactions. Work toward these goals requires deep knowledge both in computer science and in biological chemistry, and must therefore be collaborative in nature. Carnegie Mellon computer scientists will therefore be partnering with colleagues with expertise in Biological Chemistry at the University of Pittsburgh, the Massachusetts Institute of Technology (MIT), Boston University and the National Research Council of Canada. Industry collaborators include Mathworks, Inc., and medical bioinformatics company, Medstory, Inc.
Using tools like statistical language modeling, machine learning methods and high-level language processing for understanding how proteins work inside cells is a relatively new field called computational biolinguistics. At this point, the researchers have been able to detect protein fragment signatures from pathogens by application of statistical language modeling technologies to genome sequences, promising novel strategies in identifying and targeting such pathogens.
.

The LETRAS project investigates novel approaches to development of Machine
Translation (MT) technology, with the goal of establishing a general framework
that supports building MT prototype systems for languages for which only
limited amounts of data and resources in electronic form are available. The
research focus of the project is on automatic learning of translation
transfer-rules from limited amounts of elicited bilingual data. A new run-time
translation "engine" maps source language sentences to their target language
equivalents, by building a large structure of possible partial translations
and then applying effective search techniques for recovering the best
translation. In the last stage, an automatic rule refinement module helps the
system learn how to correct and improve its imperfect translation rules, based
on feedback on translation errors provided by users. MT prototype systems for
several language pairs are being constructed as an integral part of the
project and in collaboration with external research groups. The prototypes
guide our research and test out our new ideas. At the same time, our
collaborations with local researchers and native communities promote the
development of information technology for native languages and educate local
researchers with our state-of-the-art MT research. The prototypes include a
Hebrew-to-English MT system (with University of Haifa, Israel); an
Inupiaq-to-English MT system (with University of Alaska, Fairbanks, and the
Inupiat Heritage Center in Barrow, Alaska); and a Karitiana-to-Portuguese MT
system (with University of Sao Paulo, Brazil). Support for the Alaska
collaboration is being provided by NSF's Office of Polar Programs (OPP), and
support for the collaborations with Israel and Brazil is being provided by
NSF's Office for International Science and Engineering (OISE). OISE is also
providing funding for a planning trip to Bolivia to explore a possible
Aymara-to-Spanish project. The potential long-term impact of the project
is profound - enabling the development of Machine Translation for many
languages of the world, which in turn opens the door for active participation
of native and minority communities in the information-rich activities of the
21st century.

This subproject is one of many research subprojects utilizing the resources provided by a Center grant funded by NIH/NCRR. The subproject and investigator (PI) may have received primary funding from another NIH source, and thus could be represented in other CRISP entries. The institution listed is for the Center, which is not necessarily the institution for the investigator. Given a Multiple Sequence Alignment (MSA) of a family of proteins we want to find evolutionarily conserved and covarying residues, which we believe would be functionally and structurally important. Specifically we propose to elicit the structure of a Markov Random Field from the MSA, and study this structure in terms of it's ability to discriminate sequences of this family from others and also to generate new sequences which are functionally and structurally identical to ones in the family.

Machine learning (ML) has witnessed tremendous success both in establishing firm theoretical foundations and reaching out to major applications ranging from the scientific (e.g. computational biology) to the practical (e.g. financial fraud detection, spam detection). However the reach of machine learning has been hampered by an underlying inductive framework that largely has not evolved from using only labeled instances of concepts (e.g. emails and yes/no labels on whether they are spam) and its overly simple view of the role of the user or subject matter expert (SME) as a mere provider of the labels for the training instances. However, when instructing humans, teachers provide richer information: Why is an instance of a concept a good positive example? What are key differences between instances belonging to different classes? Which properties are transient and which are invariant? Where should the learner focus attention? What does the current learning task have in common with previously acquired concepts or processes? Answers to such questions not only enrich the learning process, but they also can effectively reduce the hypothesis space and provide significant speed ups in learning than can be achieved with use of class membership feedback only.

The aim of this project is to bring this kind of richer interaction into the realm of machine learning by developing frameworks as well as machine learning methods that can take advantage of fuller mixed-initiative communication. In particular, this project aims to develop ML algorithms that can exploit information from SME's such as (1) identification of landmark instances; (2) proposing rules of thumb; (3) providing feedback on similarity of instances; and (4) transfer of similarity measures themselves. This project brings to bear four streams of research: (1) algorithms based on similarity functions and landmark instances; (2) active and "pro-active" learning; (3) Bayesian active transfer learning; and (4) learning to cope with temporal evolution in the underlying data distribution. In order to reach practical results, this project focuses on challenges where these new methods are both most needed and likely to prove most effective, such as learning in dynamic environments with concept drift, and where potential for long-term transfer learning is present. Broader impacts include more effective learning by incorporating scientific domain knowledge in eScience, for instance in computational proteomics. Educational and research-community outreach includes participation of graduates and undergraduates from Howard University, for instance in yearly research gatherings involving all students on the project, and reusable open-source methods and data sets.

With massive quantities of educational materials freely available on the web, the vision of personalized and readily accessible education appears within our grasp. General-purpose search engines are insufficient as they do not focus on educational materials, objectives, pre-requisite relations, etc., nor do they stitch together multiple sources to create customized curricula for students' goals and current knowledge. This exploratory project focuses on establishing fundamental results in: (1) extracting educational units from diverse web sites and representing them in a large directed graph, whose nodes are content descriptors and whose edges encode pre-requisite and other relations; (2) conducting multi-field topic inference via a new family of graphical models to infer relations among educational units; and (3) automated curricular planning, focusing on providing sequences of lessons, courses, exercises and other education units for a student to achieve his or her educational goals, conditioned on current skills. The objective is to develop a data-driven course/curriculum planner on demand, based on a graph traversal that is enriched with alternate paths, reinforcement options, and conditional branches to match the learner's needs.

The broader impact of this research is two-fold: (1) developing methods for mining and traversing web-based educational materials in general, later generalizing to multi-media lessons and courses; and (2) individualized curricular planning, so any student anywhere can be provided with guidance on how to navigate and exploit the vast ocean of massive open online course (MOOC) materials and other educational texts, exercises, etc. in a manner customized to the student's learning objective, capabilities and skills. The resulting system, named TEACHER, can be applied to learning specific job skills, to reinforce classroom instructions, or as stand-alone academic support to address, for instance, the huge percentage of students who attempt taking MOOCs but never complete them due to lack of requisite skills and lack of guidance on how to acquire them. Project web site (http://nyc.lti.cs.cmu.edu/teacher/) will be used to disseminate results.

Whom do you ask when you don't know whom to ask? That may be considered a rhetorical question in some contexts, but it is the "raison d'être" for referral networks. If a person must address a problem, but lacks the knowledge of how to solve it, he or she asks someone who may either provide a solution, or may know someone else who might provide the solution. Referral networks are very useful for professional success, such as in consulting companies, health-care organizations (e.g. referral of patients to medical specialists) or interdisciplinary research endeavors. The advent of AI-based intelligent agents, who typically have narrow expertise, enables the creation of agent-based or mixed human-and-agent referral networks, but adds complexity to the referral process. In order to tame this complexity, the new research addresses learning to refer in a distributed setting. Each expert learns to better estimate the expertise of other experts in the network, whether human or AI-based agents, and thus overall network refers with increasing accuracy. The learning-to-refer methods are robust with respect to gradual expertise change (e.g. experts learn to perform better) or changes in the network (e.g. an experienced expert retires and/or one or more new but less experienced experts join).

The research starts by modifying methods from reinforcement learning, such as the successful interval-estimation learning approach, extending them to the distributed referral-network setting. Preliminary results show that distributed interval threshold learning is effective in improving the accuracy of referrals with accrued experienced, and performs better than other approaches such as Q-learning or greedy selection of best-known expert. The research will address issues of robustness to changes in the referral network topology, benefits of informative priors and proactive skill advertisement by individual experts to their peers, and other related aspects relaxing the initial restrictive assumptions in order to address real referral-network scenarios. In addition to establishing this new line of distributed learning, this EAGER will generate data sets useful for further research in the area of expertise-network learning and make them available.