In this proposal, we describe challenges encountered by phrase-based and syntax-based machine translation (MT) systems today, and present an in-depth, quantitative comparison of both models. Then, we describe a novel model for statistical MT which addresses these challenges using a Synchronous Tree Adjoining Grammar. We introduce a method of converting these grammars to a weakly equivalent tree transducer for decoding. And we present a method for learning the rules and associated probabilities of this grammar from aligned tree/string training data.

Finally, our initial results show that adjoining already delivers an end-to-end improvement of +0.8 BLEU over a baseline statistical syntax-based MT model on a medium-scale Arabic/English MT task. Furthermore, we demonstrate it is a competitive entry in the Urdu-English track of the 2009 NIST MT evaluation. We then propose improvements to the model, decoding, and extraction that promise to allow this new, linguistically-motivated MT model to surpass its syntax-based and phrase-based cousins in a wide range of scenarios and language pairs.

About the Speaker:

--

Brief Bio: Nanda Kambhatla has nearly 17 years of research experience in the areas of Natural Language Processing (NLP), text mining, information extraction, dialog systems, and machine learning. He holds 6 U.S patents and has authored over 30 publications in books, journals, and conferences in these areas. Nanda holds a B.Tech in Computer Science and Engineering from the Institute of Technology, Benaras Hindu University, India, and a Ph.D in Computer Science and Engineering from the Oregon Graduate Institute of Science & Technology, Oregon, USA.

Currently, Nanda is the manager of the Data Analytics Group at IBM's India Research Lab (IRL), Bangalore. The group is focused on research on machine translation, Natural Language Processing, text analysis and machine learning techniques for developing analytics solutions to help IBM's services divisions. Most recently, Nanda was the manager of the Statistical Text Analytics Group at IBM's T.J. Watson Research Center, the Watson co-chair of the Natural Language Processing PIC, and the task PI for the Language Exploitation Environment (LEE) subtask for the DARPA GALE project. He has been leading the development of information extraction tools/products and his team has achieved top tier results in successive Automatic Content Extraction (ACE) evaluations conducted by NIST for extracting entities, events and relations from text from multiple sources, in multiple languages and genres.

Earlier in his career, Nanda has worked on natural language web-based and spoken dialog systems at IBM. Before joining IBM, he has worked on information retrieval and filtering algorithms as a senior research scientist at WiseWire Corporation, Pittsburgh and on image compression algorithms while working as a postdoctoral fellow under Prof. Simon Haykin at McMaster University, Canada.

It will NOT cover Hadoop, MPI, real workflow management tools like Condor.

Machine translation systems typically rely on some form alignment as a preprocessing step. Typically, these alignments take the form of word-to-word alignments. In this talk, we will introduce several models aimed at aligning foreign words to either English words or nodes in the English parse tree. Such word-to-node alignments offer several potential advantages over traditional word-to-word alignments. Firstly, since the extraction process for some syntactic systems explicitly considers the English trees, we expect that also considering the trees at alignment time will produce alignments that will better suit the extraction process. Secondly, aligning foreign function words to English tree nodes can admits highly desirable syntactic transfer rules which cannot be directly as word-to-word alignments. Finally, word-to-node alignments can effectively model many-to-one alignments. We present four models of increasing complexity and show preliminary results for each model.

Title: A Statistical Foray into Poetry

Abstract: Although the analysis and generation of poetry is often considered an exclusively human task, we have taken some initial steps to automate the process. We build a series of finite state transducers to analyze poetic meter and train them on a handmade corpus of poetry. We then use these trained transducers to generate poetry. Specifically, we focus on generating sonnets and limericks.

------------------------------------------

TALK 2: Paramveer Dhillon

Title: Learning to simplify target language for MT + Unsupervised log-linear models for Word Alignment

Abstract: We consider the Machine Translation task for the language pair (Chinese and English), where English is the target language. There are lots of redundancies in English language, e.g. It has capitalization, i.e. the first word of each sentence is capitalized, and it has different morphology i.e. it has noun and verb endings; none of which are present in Chinese. In a way, due to these redundancies, we are learning that a single Chinese word "tamen" translates to "They" and "they" and another Chinese word translates to "run", "runs" and "running". We present generative models which learn to "cluster" the target language vocabulary, by removing the above redundancies, namely (Capitalization and Different morphology). We show results on how this "clustering" affects the translation quality in end-to-end MT experiments.

A wide variety of problems in NLP require parallel data to train supervised models to perform different tasks. For example, in machine translation (where the task is to translate between two languages automatically) parallel data containing source/target language sentence pairs is required to train various models which can then be used to translate new sentences or documents. The dependency on parallel data for many of these NLP tasks limits their applications to specific domains, or language pairs for which a lot of training data is readily available. On the other hand, collecting parallel data for new domains, language pairs, etc. is a costly as well as time-intensive operation. For such tasks, the development of novel unsupervised approaches which require only {\em non-parallel} data for training can enable their application to new domains and potentially broaden the impact and benefits of NLP research to wider areas.

A similar problem has been tackled by cryptographers and archaeologists in a different context---for "decipherment" purposes. During the 1940's and 1950's, mathematicians and scientists worked on code-breaking operations, which spurred the development of many research ideas for modern computer science. For such problems, it is highly unlikely to assume the availability of parallel data relating the ciphertext and plaintext, yet cryptographers and archaeologists have attempted to solve such tasks using various decipherment techniques along with other non-parallel sources of information.

A* parsing makes 1-best search efficient by suppressing unlikely 1-best items. Existing k- best extraction methods can efficiently search for top derivations, but only after an exhaus- tive 1-best pass. We present a unified algo- rithm for k-best A* parsing which preserves the efficiency of k-best extraction while giv- ing the speed-ups of A* methods. Our algo- rithm produces optimal k-best parses under the same conditions required for optimality in a 1-best A* parser. Empirically, optimal k-best lists can be extracted significantly faster than with other approaches, over a range of gram- mar types.

------------------------------------------

Improved Word Alignment with Statistics and Linguistic Heuristics (Ulf Hermjakob)

We present a method to align words in a bitext that combines elements of a traditional statistical approach with linguistic knowledge. We demonstrate this approach for Arabic-English, using an alignment lexicon produced by a statistical word aligner, as well as linguistic resources ranging from an English parser to heuristic alignment rules for function words. These linguistic heuristics have been generalized from a development corpus of 100 parallel sentences. Our aligner, UALIGN, outperforms both the commonly used GIZA++ aligner and the state-of-the-art LEAF aligner on F-measure and produces superior scores in end-to-end statistical machine translation, +1.3 BLEU points over GIZA++, and +0.7 over LEAF.

About the speaker:

Yang Liu is an Assistant Researcher at Institute of Computing Technology (ICT), Chinese Academy of Sciences. He received his PhD degree in Computer Science from ICT in 2007. His major research interests include statistical machine translation and Chinese information processing. He has been working on syntax-based modeling, word alignment, and system combination. His paper on tree-to-string translation won the Meritorious Asian NLP Paper Award of COLING/ACL 2006. He served as Reviewers for TALIP, TSLP, JNLE, ACL, EMNLP, AMTA, and SSST.

About the speaker:

Yang Liu is an Assistant Researcher at Institute of Computing Technology (ICT), Chinese Academy of Sciences. He received his PhD degree in Computer Science from ICT in 2007. His major research interests include statistical machine translation and Chinese information processing. He has been working on syntax-based modeling, word alignment, and system combination. His paper on tree-to-string translation won the Meritorious Asian NLP Paper Award of COLING/ACL 2006. He served as Reviewers for TALIP, TSLP, JNLE, ACL, EMNLP, AMTA, and SSST.

Combining the 1-best output of multiple parsers via parse selection or parse hybridization improves f-score over the best individual parser (Henderson and Brill, 1999; Sagae and Lavie, 2006). We propose three ways to improve upon existing methods for parser combination.

---------------------------------------------------------

Disambiguation of Preposition Sense Using Linguistically Motivated Features (Dirk Hovy: 3:30pm -- 4:00pm)

We present a method for performing machine transliteration without any parallel resources. We frame the transliteration task as a decipherment problem and show that it is possible to learn cross-language phoneme mapping tables using only monolingual resources. We compare various methods and evaluate their accuracies on a standard name transliteration task.

This is joint work with Kevin Knight.

----------------------------------------------------

Talk-2: A New Objective Function for Word Alignment

We develop a new objective function for word alignment that measures the size of the bilingual dictionary induced by an alignment. A word alignment that results in a small dictionary is preferred over one that results in a large dictionary. In order to search for the alignment that minimizes this objective, we cast the problem as one of integer linear programming. We then extend our objective function to align corpora at the sub-word level, which we demonstrate on a small Turkish-English corpus.

This is joint work with Tugba Bodrumlu and Kevin Knight.

In this talk, I report on new experimental evidence in support of a coherence-driven analysis, and describe how the analysis can accommodate a range of previous findings suggestive of conflicting preferences and biases. Case studies of four commonly-cited preferences are described, specifically (i) the parallel grammatical role preference (e.g., Smyth 1994), (ii) thematic role preferences (e.g., Stevenson et al. 1994), (iii) implicit causality biases (e.g., Caramazza et al. 1977), and (iv) the subject assignment strategy (e.g., Crawley et al. 1990). In each case, the experimental results offer an explanation of what the underlying source of the bias is, and predicts in what contexts evidence for it will surface.

These results suggest that pronoun interpretation is incrementally influenced in part by the probabilistic expectations that hearers have about how the discourse will be coherently continued. They are also argued to leave various myths by the roadside, e.g., that pronoun interpretation can be profitably thought of as a 'search and match' procedure, and that coherence relations need not be controlled for in experimental stimuli.

This talk includes joint work with Laura Kertz, Hannah Rohde, and Jeffrey Elman.

Noting that the real world uses far more quasi-paraphrases than the logically equivalent ones, we first present a general typology of quasi-paraphrases together with their relative frequencies. To our knowledge the first one ever. We then present a method for automatically learning the contexts in which quasi-paraphrases obtained from a corpus are mutually replaceable. Knowing that quasi-paraphrases are often inexact because they contain semantic implications which can be directional, we present an algorithm called LEDIR to learn the directionality of quasi-paraphrases. Since semantic classes play a crucial role in our work, we also investigate the use of a semi-supervised clustering algorithm for learning semantic classes.

We next investigate the task of learning surface paraphrases, i.e., paraphrases that do not require the use of any syntactic interpretation. Since one would need a very large corpus to find enough surface variations, we use a really large but unprocessed corpus of 150GB (25 billion words) obtained from Google News to do this learning. We show that these paraphrases can be used to learn surface patterns for relation extraction. Finally, we use paraphrases to learn patterns for domain-specific information extraction.

Thus, in this thesis we define quasi-paraphrases, present methods to learn them from a corpus, and show that quasi-paraphrases are useful for information extraction.

Additionally, we describe analysis of human expressive behavior that can be afforded by such audio-visual data. We describe an analysis of the interrelation between facial gestures and speech using a multimodal approach. Using a controlled setting, motion capture technology was used to simultaneously acquire speech and detailed facial information. Our results indicate that the verbal and non-verbal channels of human communication are internally and intricately connected. The interplay is observed across the different communication channels such as various aspects of speech, facial expressions, and movements of the hands, head and body, and is greatly affected by the linguistic and emotional content of the message being communicated. As a result of the analysis, applications in automatic emotion recognition and synthesis of expressive communication are presented.

[This research was supported in part by funds from the NSF, NIH, and the Department of the Army]

In this talk I will first introduce a tree-based (aka syntax-directed) paradigm for machine translation, inspired by both human translators and compilers. In this paradigm, a source language sentence is first parsed into a syntactic tree, which is then recursively converted into a target language sentence via tree-to-string transformation rules. Since the translation process is driven by the syntax, this approach resembles the classical "syntax-directed translation" method in compiling theory.

However, natural languages are crucially different from programming languages in that they are fundamentally ambiguous. So we don't (and will probably never) have perfect parsers, and parsing errors adversely affect translation quality. To alleviate this problem, an obvious idea is to use the top-k parses, rather than a single 1-best, but this only helps a little bit due to the limited scope of the k-best list. We instead propose a "forest-based approach", which translates a packed forest encoding *exponentially* many parses in a compact (polynomial) space by sharing common subtrees. Large-scale experiments showed very significant improvements (over the 1-best baseline) in terms of translation quality, which outperforms the best reported systems to date. More interestingly, translating a forest of millions of trees is even faster than translating on top-30 individual trees thanks to dynamic programming.

This talk includes joint work with Kevin Knight and Aravind Joshi (first part), and with Haitao Mi and Qun Liu (second/third parts).

Short Bio:

Liang Huang recently completed his PhD study at the University of Pennsylvania, co-supervised by Aravind Joshi and Kevin Knight (USC/ISI). He is mainly interested in the theoretical aspects of computational linguistics, in particular, efficient algorithms in parsing and machine translation, generic dynamic programming, and formal properties of synchronous grammars. His thesis develops a set of "forest-based methods" that have been applied to many problems in NLP including k-best parsing, forest rescoring and reranking, and forest-based translation. His awards include an Outstanding Paper Award at ACL 2008, and a University Teaching Award at Penn in 2005.

- the most important contributions in the fields of speech recognition, language modeling, and machine translation;

- past ideas that failed to lead to substantial improvements;

- and contributions that are most likely to have a material impact in the future.

Errors in English parse trees impact the quality of syntax-based MT systems trained using those parses. Frequent sources of error for English parsers include PP-attachment ambiguity, NP-bracketing ambiguity, and coordination ambiguity. Not all ambiguities are preserved across languages. We examine a common type of ambiguity in English that is not preserved in Chinese: given a sequenc "VP NP PP", should the PP be attached to the main verb, or to the object noun phrase? We present a discriminative method for exploiting bilingual Chinese-English word alignments to resolve this ambiguity in English. On a heldout test set of Chinese-English parallel sentences, our method achieves 86.3% accuracy on this PP-attachment disambiguation task, an improvement of 4% over the accuracy of the baseline Collins parser (82.3%).

Online Large-Margin Training of Syntactic and Structural Translation Features (practice talk for EMNLP)

Minimum-error-rate training (MERT) is a bottleneck for current development in statistical machine translation because it is limited in the number of weights it can reliably optimize. Building on the work of Watanabe et al., we explore the use of the MIRA algorithm of Crammer et al. as an alternative to MERT. We first show that by parallel processing and exploiting more of the parse forest, we can obtain results using MIRA that match or surpass MERT in terms of both translation quality and computational cost. We then test the method on two classes of features that address deficiencies in the Hiero hierarchical phrase based model: first, we simultaneously train a large number of Marton and ResnikÂ’s soft syntactic constraints, and, second, we introduce a novel structural distortion model. In both cases we obtain significant improvements in translation performance. Optimizing them in combination, for a total of 56 feature weights, we improve performance by 2.6 Bleu on a subset of the NIST 2006 Arabic-English evaluation data.

(Joint work with Yuval Marton and Philip Resnik)

Statistical parsers have become increasingly accurate, to the point where they are useful in many natural language applications. However, estimating parsing accuracy on a wide variety of domains and genres is still a challenge in the absence of gold-standard parse trees.

We propose a technique that automatically takes into account certain characteristics of the domains of interest, and accurately predicts parser performance on data from these new domains. As a result, we have a cheap (no annotation involved) and effective recipe for measuring the performance of a statistical parser on any given domain. (Joint work with Kevin Knight and Radu Soricut)

Overcoming Vocabulary Sparsity in MT Using Lattices (practice talk for AMTA)

Source languages with complex word formation rules present a challenge for statistical machine translation (SMT). In this paper, we take on three facets of this challenge: (1) common stems are fragmented into many different forms in training data, (2) rare and unknown words are frequent in test data, and (3) spelling variation creates additional sparseness problems. We present a novel, lightweight technique for dealing with this fragmentation, based on bilingual data, and we also present a combination of linguistic and statistical techniques for dealing with rare and unknown words. Taking these techniques together, we demonstrate +1.3 and +1.6 BLEU increases on top of strong baselines for Arabic-English machine translation. (Joint work with Ulf Hermjakob and Kevin Knight)

About the Speaker:

Eugene Charniak is Professor of Computer Science. and Cognitive Science at Brown University. He received an A.B. degree in Physics from University of Chicago and a Ph.D. from M.I.T. in Computer Science. He has published four books: Computational Semantics, with Yorick Wilks (1976); Artificial Intelligence Programming (now in a second edition) with Chris Riesbeck, Drew McDermott, and James Meehan (1980, 1987); Introduction to Artificial Intelligence with Drew McDermott (1985); and Statistical Language Learning (1993). He is a Fellow of the American Association of Artificial Intelligence and was previously a Councilor of the organization. His research has always been in the area of language understanding or technologies which relate to it, such as knowledge representation, reasoning under uncertainty, and learning. Over the last few years he has been interested in statistical techniques for language understanding. His research in this area has included work in the subareas of part-of-speech tagging, probabilistic context-free grammar induction, and, more recently, syntactic disambiguation through word statistics, efficient syntactic parsing, and lexical resource acquisition through statistical means.

Various techniques have been developed to estimate the parameters of CD-HMMs. In particular, discriminative techniques such as conditional maximum likelihood and minimum classification error have attracted significant research attention. When carefully and skillfully implemented, they often lead to lower error rates (in speech recognition) than traditional techniques of maximum likelihood estimation.

In this talk, I will describe a new discriminative technique that is based on the principle of large margin, a key framework in many machine learning algorithms including support vector machines and boosting. The new technique differs from previous discriminative methods for ASR in the goal of margin maximization. In particular, in our large margin training of CD-HMMs, model parameters are optimized to maximize the gap (or the margin) between correct and incorrect classifications. I will present an extensive empirical evaluation of our approach on two benchmark problems in speech recognition: phonetic classification and recognition on the TIMIT speech database. In both tasks, large margin systems obtain significantly better performance than systems trained by maximum likelihood estimation or competing discriminative frameworks. An in-depth analysis also reveals some interesting features of our approach, which contribute to the superior performance.

Towards the end of the talk, I will discuss briefly the connection of our work to the structured prediction problems in the machine learning community. I will also discuss the future direction of this line of work and other application potentials.

First, I'll talk about how to cast phrase alignment search as an integer linear programming (ILP) problem and find the optimal alignment reliably and quickly with off-the-shelf ILP software. Some applications of this technique include training phrase alignment models and interpreting the output of word alignment models.

Second, we'll look at how to estimate translation probabilities under a phrase alignment model using a Gibbs sampling procedure. The sampler has some nice asymptotic convergence properties and also seems to produce good results in practice. I'll walk through the different models we've trained and how they performed.

The goal of MITCH is to turn the field logs and registration books into a populated semantic network, in which concepts such as animal specimens are related to all other concepts that define them: where, when, under which circumstances and by whom were they found, who described them first in the academic literature, who prepared them for storage in the Naturalis depot, which registration number was assigned to them, etc. This means that all textual descriptions of a specimen need to be parsed into exactly these concepts and their relations. All of this needs to be done at a scale that goes far beyond the human capacity, as tens of thousands of digitized but unanalysed textual records are waiting for semantic analysis. This necessitates the use of state-of-the-art machine learning methods that learn from examples automatically.

- Ward Rounds Information Systems (WRIS) & Handovers - The WRIS is designed to support the work of all clinical staff in their ward rounds activities. The system, when activated, automatically populates from the resident clinical database a pro forma report with the most recent relevant data about the patient, such as vital signs, pathology reports, and other diagnostic measurements, presented as a web page. The clinical staff then write their progress notes into the web page which converts the text to SNOMED CT codes and other relevant concepts and entities. The clinician is given the opportunity to change any analyses done by the processor. This clinician approved data is loaded to the patient record. The essential elements of this system, that is computing an extract of the patient record, accepting narrative input, and analysing the text for coding, is a productivity gain of itself, but more importantly, also constitutes the beginning of a hospital wide Handovers System for use throughout each step in the patient journey. This system is being tested at the RPAH ICU in readiness for ward usage. The impact of this system in improving the quality and safety of handovers has the potential to be very significant.

- Clinical Data Analytics Language (CDAL) - General purpose access to data from clinical information systems, beyond retrieval for point of care work, is needed for many aspects of the hospital's work particularly for clinical research, logistics & operational planning, and auditing patient safety. Most current clinical systems only provide access to data identified in standard reports with no flexibility to make ad hoc enquiries or to pursue new directions of enquiry. The clinical data analytics language developed enables the expression of any question that can be answered from the data in the database in a restricted natural language. A prototype of the language has been developed for the CareVue information system used in the ICU at the Royal Prince Alfred Hospital. It provides for the use of local medical dialects, SNOMED CT terminology including all forms of collective expressions in SNOMED (e.g. infectious diseases), specification of patient groups, a variety of statistical functions, and constraints over any medical variable, Time, and Location. CDAL is general in that it can be bolted on to any clinical information system and is applicable to any clinical specialisation.

N-gram language models are fundamental to speech recognition and machine translation. Unfortunately, the n-gram parameter space grows exponentially with the dimension of the feature vector. I will describe how randomization can be used to remove the space-dependency of such models on the a priori parameter space.

The novel extensions of the Bloom filter that I will present are able to take advantage of the entropy of the distribution of values assigned to feature vectors to save space in a discrete statistical model. I will review some results applying these models to language modeling in machine translation and relate their space-requirements to a novel lower bound on the general problem of querying a map of key/value pairs.

No prior knowledge of randomized data structures will be assumed.

Since finite state (string) transducers are not expressive enough for many NLP applications, computational linguistics started to investigate tree transducers for the task of machine translation, for example. Quite some successful work has been done on generalizing results from string transducers to tree transducers. But when it comes to composition results are not satisfying because generally tree transducers are not closed under composition. Still we think that most of the tree transducers used in NLP are composable and that is why we defined the problem of the composition for two individual transducers instead of the whole class. During the summer we started with linear nondeleting tree transducers with epsilon rules and approached an algorithm to decide for two such transducers whether their composition is again in the same class.

Using the Perceptron Algorithm to Tune Large Numbers of Feature Weights for Syntax-Based Statistical Machine Translation

The language models used in statistical machine translation are often quite large, requiring significant memory and sometimes pre-processing in order to be utilized effectively. It would be desirable to have a more compact representations of language models while minimizing the impact on translation quality. Various quantization methods and lossy storage of language models will be presented.

Context for Syntax-Based Translation Rules

The rules that a translation system employs should be applicable in many contexts. This ensures that a rich language is expressible with a minimum number of rules. However, when rules that are applicable in too many contexts are combined, they result in nonsensical translations. How can we keep rules general but constrain the context of their use? This summer we explored the approach of constraining the context by conditioning on various neighboring elements of each rule.

The yield of ATGs is exactly the set of Tree-Adjoining Languages. Just like RTGs are stronger than CFGs, ATGs are stronger than TAGs. In addition we will show that the ATG notation simplifies many of the foundational proofs for TAGs including proofs of the closure properties. In particular, ATLs do not use adjunction constraints, and thus are much easier to understand than TAGs.

We compare ATGs with previously proposed simplifications of CFTGs, called monadic simple CFTGs, which also have been shown to be weakly equivalent to TAG (i.e. they generate the same set of string languages). We consider the question of whether these two weakly equivalent formalisms are strongly equivalent (i.e. generate exactly the same set of tree languages).

Finally, we will show that the standard definition used for probabilistic TAG is (surprisingly) very different from the natural definition of probabilistic ATL. Using an example of PP-attachment ambiguity we show that the two probabilistic models are different from each other.

About the speaker:

Anoop Sarkar is an assistant professor in the Department of Computing Science at Simon Fraser University. He received his PhD in 2002 from the Department of Computer and Information Science at the University of Pennsylvania, with Prof. Aravind Joshi as his advisor. His research work is on machine learning, especially semi-supervised learning, applied to the processing of natural language and stochastic formal grammars.

About the speaker:

Liang-Chih Yu (http://www.isi.edu/~liangchi) is now a visiting student in the Information Sciences Institute (ISI) of University of Southern California (USC). My host advisor is Dr. Eduard Hovy. I am also a PhD candidate in the Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan, Taiwan. My advisor is Dr. Chung-Hsien Wu. My research interests include natural language processing, text mining, information retrieval, ontology construction, spoken dialogue system.

The project aimed to address the problems encountered when trying to match available employees to open job positions, based on skill matches. Currently, job search applications, like IBM's Professional Marketplace, only find exact matches. A skill affinity computation is desired to allow searches to be expanded to related/similar skills, and return more potential matches.

In this talk, I will explore the problem of computing text similarity between verb phrases describing skilled human behavior for the purpose of finding approximate matches. Four parsers (Charniak's parser, Stanford's parser, IBM XSG slot grammar parser, and Lin's MINIPAR) are evaluated on a corpus of skill statements extracted from an enterprise-wide expertise taxonomy. A similarity measure utilizing common semantic role features extracted from parse trees was found superior to an information-theoretic measure of similarity and comparable to the level of human agreement.

About the speaker:

About the speaker:

Christopher Collins is a PhD candidate in information visualization and computational linguistics at the University of Toronto. He works with Prof. Gerald Penn and Prof. Sheelagh Carpendale (University of Calgary).

About the speaker:

About the speaker:

Prof. Helbig is head of the chair Intelligent Information and Communication Systems at the University of Hagen, Germany. His main research areas are Knowledge Representation, Semantic Natural Language Processing, and Question-Answering.

- is expressive enough to capture how natural language works

- permits tractable inference

- admits learning algorithms for automatic knowledge acquisition

- leads to modular system construction

This talk will look at knowledge representation for capturing natural language transformations. A lot of what we do falls into this category. Examples of transformations include language translation (French to English), question answering (Question to Answer), transliteration (foreign script to Roman alphabet), summarization (long text to short text), parsing (string to tree), language generation (meaning to string), etc.

I'll show various knowledge formats (starting with simple finite-state transducers) and show how they stack up on the 4 criteria above, using theorems and examples. We'll see that different types of tree and string automata lead to good behavior on various subsets of the 4 criteria, but getting 4 out of 4 is still elusive.

I will briefly describe an experiment with readers aimed at providing reliable data for a computational investigation of lexical cohesion. We then discuss a number of informative features for cohesion detection, drawing on sources like WordNet, distributional information, free associations, and the structure of information in the text itself. Finally, I report experiments with supervised learning of lexical cohesion.

About the speaker:

Bio:

Interestingly, these techniques can be applied to speed up bilexical parsing as well, where the (bi-) lexical probabilities can be viewed as n-gram probabilities that causes non-monotonicity. This method fits naturally into the coarse-to-fine grained multi-pass parsing schemes.

To push this direction even further, we can generalize cube and lazy cube pruning as generic tools for reducing complicated search spaces, as alternatives to the well-known A* and annealing techniques.

Joint work with Matthew Stone, Rutgers and Rich Thomason, Michigan

About the Speaker:

o the slides from roughly page 40 - The Schwartzian Transform - Dissecting a program o What to do, if you do need popen or backticks? o OO Perl - a start o C embedding - definitely only a "start here" o Useful recipes, e.g. interpolating variables in configuration scripts from Perl values.

We then present a novel parsing approach that avoids language model context intersection during parsing in favor of language model driven n-best list extraction.Ê The parsing step produces aÊ sentence spanning parse forest which is explored in left-to-right target order by the N-Best extraction method.

This method avoids lossy pruning during the parsing process, searching a much larger effective parse space than practically possible in the full intersection scenario, and has the important benefit of allowing integration of a high order language within the N-Best search process, rather than only in parse re-scoring.

We demonstrate the impact of this parsing approach using the SPCFG approach described in Zollmann, Venugopal, Vogel 06, which is similar to Galley et al., 04 and compare performance against full intersection.

This is joint work with Andreas Zollmann

About the Speaker:

Ashish Venugopal is a Ph.D candidate at the Language Technologies Institute at Carnegie Mellon University, and holds B.S (SCS, Univ. Honors), M.S degrees from the same institution. He is a Seibel Scholar and has received the annual Graduate Student Teaching Award at Carnegie Mellon. His research focus is on syntax augmented machine translation.

1. How does one obtain a balanced corpus to annotate? What is a balanced corpus?

2. How does one decide which aspects to annotate? How does one adequately express the theory behind the phenomena in simple annotation steps?

3. Which annotators does one hire? How does one ensure that they are adequately trained?

4. How does one establish a simple, fast, and trustworthy annotation procedure? What interfaces does one build? How does one ensure that the interfaces do not affect the annotation results?

5. How does evaluate the results? What are the appropriate agreement measures? At which cutoff points should one re-do the annotations? How does one ensure improvement?

6. How should one formulate and store the results? How does one ensure compatibility with other existing resources? How does one make results available for best impact?

7. How does one report the annotation effort and results? How does one actually get a paper on this work published at an important conference? What should the paper contain?

We present an unsupervised algorithm for identifying and removing "bad" links using GHKM syntax-based rule extraction. We show that we can improve upon the precision of GIZA union (measured against a gold standard set of manually aligned Chinese-English sentence pairs), while only decreasing recall slightly.

In this talk, the Textual Entailment framework will be introduced. I'll then present an algorithm for large-scale Web-based acquisition of entailment rules, a type of knowledge needed for robust inference. Finally, I will present an unsupervised Relation Extraction approach based on the Textual Entailment framework.

About the speaker:

Idan Szpektor is a PhD student under the supervision of Dr. Ido Dagan at Bar Ilan University, Israel. His current research activity is in acquisition of knowledge for textual entailment.

An important problem in the area of homeland security and fraud detection is to identify abnormal entities in large datasets. Although there are methods from knowledge discovery and data mining focusing on finding anomalies in numerical datasets, there has been little work aimed at discovering abnormal or suspicious instances in large and complex semantic graphs whose nodes are richly connected with many different types of links. In this talk, I will describe a novel, domain-independent and unsupervised framework to identify such instances. Besides discovering suspicious instances, we believe that to complete the discovery process and to deal with the "curse of false positives", a system has to convince the users by providing explanations for its findings. Therefore, in the second part of the talk I will describe an explanation mechanism to automatically generate human-understandable explanations for the discovered results. Experimental results show that our discovery system outperforms state-of-the-art unsupervised network algorithms used to analyze the 9/11 terrorist network by a large margin. Additionally, a human study we conducted demonstrates that our explanation system, which provides natural language explanations for its findings, allowed human subjects to perform complex data analysis in a much more efficient and accurate manner

Here is the link for the paper: http://www.cs.ualberta.ca/~wqin/papers/depar_margin_conll06.pdf

About the speaker:

We present a novel method for extracting parallel sub-sentential fragments from comparable bilingual corpora. Currently, the state of the art in comparable corpus mining is only able to extract full sentence pairs which are judged to be parallel. We advance the state of the art by showing how to obtain useful data even from not-fully-parallel sentences. By analyzing sentence pairs using a signal-processing-inspired approach, we detect which segments of the source sentence are translated into segments of the target sentence, and which are not. We evaluate the quality of the extracted data by showing that it improves the performance of a state-of-othe-art machine translation system.

Advances in Discriminative Parsing Joseph Turian

Once upon a time, synchronous grammars and tree transducers were esoteric topics in formal language theory, far removed from the practice of building real, large-scale natural language systems. However, these tools are now rapidly becoming essential for modeling machine translation and other complex language transformations. It has therefore become practical and important to understand the basic properties of tree transformation systems, which we cover in this tutorial.

--------------------------------------------------------------------------

NATURAL LANGUAGE GENERATION FOR TEXT-TO-TEXT APPLICATIONS USING AN INFORMATION-SLIM REPRESENTATION

Radu Soricut

In this talk, I describe a new natural language generation paradigm, based on direct transformation of textual information into well-formed textual output. I support this language generation paradigm with theoretical contributions in the field of formal languages, new algorithms, empirical results, and software implementations. At the core of this work is a novel representation formalism for probability distributions over finite languages. Due to its convenient representation and computational properties, this formalism supports a wide range of language generation needs, from sentence realization to text planning.

Based on this formalism, I describe, implement, and analyze theoretically a family of algorithms that perform language generation using direct transformations of text. These algorithms use stochastic models of language to drive the generation process. I perform extensive empirical evaluations using my implementation of these algorithms. These evaluations show state-of-the-art performance in automatic translation, and significant improvements in state-of-the-art performance in abstractive headline generation and coherent discourse generation.

--------------------------------------------------------------------------

PRACTICAL STRUCTURED LEARNING FOR NATURAL LANGUAGE PROCESSING

Hal Daume III

----------------------------------------------------------------------

Expectation Maximization (EM) has proved to be a great and useful technique for unsupervised learning problems in speech and language processing. Unfortunately, its range of applications is limited either by intractable E- or M-steps, or by its reliance on the maximum likelihood estimator. The natural language processing community typically resorts to ad-hoc approximation methods to get (some reduced form of) EM to apply to NLP tasks. However, many of the problems that plague EM can be solved with Bayesian methods, which are theoretically more well justified. In this tutorial, I discuss Bayesian methods as they can be used in natural language processing. The two primary foci of this tutorial are specifying prior distributions and performing the necessary computations to perform inference in Bayesian models. I focus on unsupervised techniques (for which EM is the obvious choice), but discuss supervised and discriminative techniques at the conclusion with pointers to relevant literature.

Depending on one's inference technique of choice, the math required to build Bayesian learning models can be difficult. Compounding this problem is the fact that current written tutorials on Bayesian techniques tend to focus on continuous-valued problems, a poor match for the high-dimension discrete world of text. This combination makes the cost of entrance to the Bayesian learning literature often too high. The goal of this tutorial is to provide sufficient motivation, intuition and vocabulary mapping so that one can easily understand recent papers in Bayesian learning that are published at conferences like NIPS, and increasingly at ACL. In addition to the standard tutorial materials (slides), this tutorial is accompanied by a technical report that spells out all the mathematic derivations in great detail, for those who wish to start research projects in this fields.

----------------------------------------------------------------------------- FIRST TALK:

The traditional approach to diagnosing learner speech errors in Computer Aided Language Learning is to create a linguistic profile of the learner/user. We, however, propose that work must also be done to model the linguistic profile of a typcial native listener.

Not all errors in second langage learner speech are created equal. Different errors sound more "severe" or "harsh" to native speaker ears and should therefore be treated with more emphasis in pedagogical interaction.

The Tactical Language Training System (TLTS) is a speech-enabled virtual-reality based computer learning environment designed to teach Arabic spoken communication to American English speakers. This talk addresses the ways the TLTS contextualizes non-native speech errors, and how this contextualization fits in the corrective exchanges between a non-native learner and a pedagogical agent built to model a native listener.

The pedagogical system used in TLTS includes:

  * Automatic Speech Recognition (ASR) models which are built on a combination of both annnotated and unannotated non-native speech with native speech data.

  * A stochastic generative model for errors in learner speech that creates mispronunciation grammars for the ASR

  * Reweighting of system-perceived mispronunciation severity based on aggregate native speaker judgements of quality pronunciation and intelligiblity.

  * Contextualization of feedback based on lexical and phonetic inventories of the native and non-native languages.

----------------------------------------------------------------------------- SECOND TALK:

We present a novel feature-enriched approach that learns to detect the conversation focus of threaded discussions by combining NLP analysis and IR techniques. Using the graph-based algorithm HITS, we integrate different features such as lexical similarity, poster trustworthiness, and speech act analysis of human conversations with featureoriented link generation functions. It is the first quantitative study to analyze human conversation focus in the context of online discussions that takes into account heterogeneous sources of evidence. Experimental results using a threaded discussion corpus from an undergraduate class show that it achieves significant performance improvements compared with the baseline system.

In the talk, I will first present our work on constructing an annotated corpus for extracting information about the typical durations of events from texts, including the annotation guidelines, the event classes we categorized, the way we use normal distributions to model such vague and implicit temporal information, and how we evaluate inter-annotator agreement. I will then show that machine learning techniques applied to this data yield coarse-grained event duration information, considerably outperforming a baseline and approaching human performance.

At the beginning of the talk, I will also give a brief overview of the time ontology (OWL-Time, formerly DAML-Time) we have developed, which is represented in both first-order logic and the OWL web ontology language.

One way to alleviate this lack of parallel data is to exploit a much richer and more diverse resource: comparable corpora, texts which are not strictly parallel but related. The prototypical example of comparable texts are two news articles in different languages which report on the same event. I will present methods for automatic extraction of parallel data from such corpora. I will show how to detect parallel data at various levels of granularity: parallel documents, parallel sentences, and even parallel sub-sentence fragments. The parallel corpora obtained using these methods help improve translation performance for both resource-scarce language pairs (such as Romanian-English) and resource-rich ones (such as Arabic-English).

We present a novel extension of syntax-directed translation for statistical MT. Formally speaking, our model is based on tree-to- string transducers that recursively convert a parse-tree in the source-language into a string in the target-language. These transduction rules have multi-level trees on the source-side, giving this system more transformational power due to the extended domain of locality. We also present efficient algorithms for decoding based on dynamic programming. Initial experiments on English-to-Chinese translation show promising results in both speed and the translation quality.

Joint work with Kevin Knight and Aravind Joshi.

Bio:

Rambow et al. Parsing Arabic Dialects: Final Report. Johns Hopkins University Center for Language and Speech Processing Workshop 2005. http://www.clsp.jhu.edu/ws2005/groups/arabic/documents/finalreport.pdf

Chiang et al. Parsing Arabic Dialects. To appear in Proc. EACL 2006.

I will also provide a brief overview of some of my other work on training and search for word alignment.

About the Speaker:

John M. Conroy received a B.S. in Mathematics from Saint Joseph's University in 1980 and a Ph.D. in Applied Mathematics from the University of Maryland in 1986. Since then he has been a research staff member for the IDA Center for Computing Sciences in Bowie, MD. His research interest is applications of numerical linear algebra and statistics. He is a member of the Society for Industrial and Applied Mathematics, Institute of Electrical and Electronics Engineers (IEEE), and the Association for Computational Linguistics.

Full paper:

http://www.isi.edu/~timc/papers/IUI06-grainpile-chkl.pdf

This paper investigates some computational problems associated with probabilistic translation models that have recently been adopted in the literature on machine translation. These models can be viewed as pairs of probabilistic context-free grammars working in a `synchronous' way. Two hardness results for the class NP are reported, along with an exponential time lower-bound for certain classes of algorithms that are currently used in the literature.

(3:00 sharp) My 7-10 min bit for panel discussion on "Manual vs. Automated Knowledge Acquisition"

Will touch on web extraction vs. learning from volunteers -- strengths and weaknesses, new thoughts on synergies

(3:15) Designing Intelligent Acquisition Interfaces for Collecting World Knowledge from Web Contributors (paper by Timothy Chklovski, Yolanda Gil)

State-of-the-art statistical machine translation systems use lexical phrases as the basic unit of translation. Phrase-based systems can capture those aspects of translation that are sensitive to local context. Syntax-based systems, on the other hand, make use of linguistically motivated syntactic structure, can capture long-distance dependencies and reorderings, and offer greater generalization in translation rules. However, their performance lags that of phrase-based systems.

Hierarchical phrase-based translation, introduced by [Chiang 05], provides an elegant framework for exploring the continuum between phrase-based and syntax-based translation. This system combines the "formal machinery" of syntax-based systems without any "linguistic commitment" to a particular syntactic structure [Chiang 05].

I will present results from my re-implementation of Chiang's hierarchical phrase-based system, and (if time permits) compare those results with the following systems on Chinese-English translation: ISI's phrase-based system, and ISI's syntax-based system. Between now and December 2005, I plan to incrementally explore the space between phrase-based and syntax-based systems by augmenting these hierarchical phrase-based rules with richer syntactic annotation.

3:30pm Liang Huang (Penn) and Hao Zhang (Rochester) Efficient Integration of n-gram Language Models with Syntax-based Decoding

We first give an overview of the ISI syntax-based MT system which is based on tree-to-string (xRs) translation rules. The biggest problem at this stage is the inefficiency of the integration of n-gram models. Without n-gram models, the xRs translation rules can be easily binarized with respect to the foreign language to ensure cubic-time decoding. With n-gram models, however, binarization without considering both languages will lead to exponential complexity.

There exist a wide variety of competing formalisms for representing a language of ordered tree pairs. These include (bottom-up and top-down) tree transducers, synchronous tree-substitution grammars (STSGs), synchronous tree-adjoining grammars (STAGs), and inversion transduction grammars (ITGs). Since these formalisms have all developed independently of one another, it is difficult to compare their respective representational power. This work seeks to make this task simpler by viewing these formalisms as instances of a general unifying formalism, which we call tree sequence automata (TSA). By casting these different formalisms in a single framework, we can compare them directly by studying the specific subclass of TSA that they fall into.

4:00pm Jason Riesa (Johns Hopkins) A case study in building a cost-effective speech-to-speech machine translation system with sparse resources: English - Iraqi Arabic

The Arabic spoken dialect of Iraq is a language deprived of the vast resources that researchers enjoy when working with its written counterpart, Modern Standard Arabic (MSA). The Iraqi Arabic lexicon and grammar are also sufficiently distinct so that the use of existing tools or corpora for MSA yield little or no positive effect on machine translation output quality. One can see that building a machine translation system normally dependent on a large parallel corpus is a particularly difficult task when given just a 37,000 line translated parallel text based on transcribed speech. This talk will explore the constraints involved in working with this type of data, how we endeavored to mitigate such problems as a non-standard orthography and a highly inflected grammar, and propose a cost- effective way for dealing with such projects in the future.

4:30pm Preslav Nakov (UC Berkeley) Multilingual Word Alignment

About the speaker:

This thesis proposal is about meeting the demand for natural language generation in the context of text-to-text applications. I introduce a new representation formalism (WIDL-expressions), propose generation algorithms that operate on representations specific to this formalism, and discuss a generic sentence realization framework for text-to-text applications. The generation mechanism is based on algorithms for intersecting WIDL-expressions with probabilistic language models. I present both theoretical and empirical results concerning the correctness and efficiency of these algorithms. I also discuss the practical aspects arising from implementing this generation mechanism.

In a concrete application of the proposed generation mechanisms, I present an end-to-end Machine Translation application. I also discuss another possible application for Automated Summarization, namely automated headline generation.

1. There is no well defined theoretical motivation for such feature model. Structural properties may not fit in any flat feature representation.

2. To define effective flat features, a deep knowledge about the linguistic phenomenon is required.

Kernel methods for Natural Language Processing aim to solve both the above problems as kernel functions can be used to define similarities between linguistic objects without explicitly defining the target feature space. In this way, a linguistic phenomenon can be modeled at a more abstract level where the modeling is easier. Such property is extremely useful when the representation of linguistic phenomena is still not well understood. For example, the feature design of semantic role labeling appear to be quite complex since several and non-definitive feature sets have been proposed.

As a viable alternative to manual feature design, kernel methods propose two steps: (1) they generate all substructures of the target syntactic/semantic structures and (2) they let the learning algorithm (e.g. Support Vector Machines) to select the most relevant substructures. In this talk, we (1) introduce the PropBank and FrameNet predicate argument structures, (2) present the standard approaches to the automatic labeling of semantic roles and (3) show advanced semantic role labeling models based on kernel methods.

About the speaker:

Alessandro Moschitti is a researcher at the Computer Science Department of the University of Rome ^ÓTor Vergata^Ô. In 1998 he took his master degree in Computer Science at the University of Rome ^ÓLa Sapienza^Ô. In 2003 he finished his PhD in Computer Science at ^ÓTor Vergata^Ô University. Between 2002 and 2004 he worked as an associate researcher in the University of Texas at Dallas. His research interests concern machine learning approaches for Natural Language Processing and Information Retrieval. His deep expertise relates to automated text categorization and semantic role labeling. Recently, he has devised new kernels which enable Support Vector and other kernel-based machines to carry out advanced semantic processing.

The goal of our research is to support cooperative work performed by stakeholders sitting around a table. To support such cooperation, various table-based systems with a shared electronic display on the tabletop have been developed. These systems, however, suffer the common problem of not recognizing shared information such as text and images equally because the orientation of their view angle is not favorable. To solve this problem, we propose the Lumisight Table. This is a system capable of displaying personalized information to each required direction on one horizontal screen simultaneously by multiplexing them and of capturing stakeholders' gestures to manipulate the information.

About the Speaker:

Mitsunori Matsushita is a research scientist of NTT Communication Science Labs., Nippon Telegraph and Telephone Corporation (NTT). He received B.E., M.E., and Dr.E. degrees from Osaka University, in 1993, 1995 and 2003 respectively. In 1995, he joined NTT, and has been engaged in researches on natural language understanding, information visualization, and interaction design.

In this tutorial, I will discuss Bayesian methods as they can be used in natural language processing. The first half will be background (some of which you probably won't have seen, some of which you probably will have seen, but which will probably be presented in a different way that you're used to) including graphical models, EM, priors and pro- (and con-) Bayesian arguments. The second half of the tutorial will focus on solving complex inference problems, essentially building on what we've seen from EM. I'll cover MAP (*not* Bayesian -- if you can't tell me why, then you should come to the tutorial!), summing, Monte Carlo, MCMC, Laplace, variational and expectation propagation. Time permitting, I will briefly discuss Bayesian discriminative models (basically what a Bayesian uses instead of SVMs), non-parametric (infinite) models and Bayesian decision theory, all of which make use of the inference techniques we will have already covered.

This tutorial is intended to be largely self contained, though I will expect that you know what probabilities are, what distributions are and the standard manipulations of conditional/joint distributions. Familiarity with EM would be helpful, but I'll cover this topic in some depth since it will be important for understanding the rest of the tutorial. I hope -- though this never really seems to come to fruition -- that this will be a semi-interactive talk and I will attempt to adjust according to what people are interested in and what is putting people to sleep.

(see http://www.isi.edu/~hdaume/bayesnlp/ for more information)

The Story Generator Algorithms project at the University of Hamburg evaluated several existing Story Generators with respect to their discursive abilities. It became obvious that most Story Generators concentrate on creating a coherent and chronological abstract Story, which is directly mapped onto natural language. This results in a predominance of 1:1 relations between Story and surface, and in most cases corresponds to a default or zero instantiation of Discourse parameters. As a consequence, Story Generator outputs tend to be very explicit and straightforward, and are likely to be perceived as uniform and boring.

Narratological expert knowledge might be useful to future enhanced Story Generators and to Natural Language Generation systems dealing with narrative. One of the aims of Computational Narratology is to model that expert knowledge. Ideally, narratological knowledge will be integrated into a Narratological Structurer, as a processing component of an advanced system that creates narratives. In such a system, the Narratological Structurer will be the interface between a Story Generator and subsequent Natural Language Generation modules. The talk also presents examples of the knowledge that is being modelled.

About the Speaker:

Birte Lönneker graduated from the University of Hamburg, Germany, with a degree in French with Finno-Ugristics (Finnish) and Business Administration. Since then, her main fields of publication are Cognitive Linguistics and electronic resources for Natural Language Processing, with special focus on frames and metaphors, as well as electronic dictionaries, corpora, and recently part-of-speech tagging. Her PhD on Concept Frames and Relations, also published as a book in 2003, was co-supervised at the Institute for Romance Languages and at the Department of Informatics in Hamburg. For her Slovenian-German online dictionary, Birte Lönneker was twice awarded the EURALEX Laurence Urdang Award. From 2002 to 2004, she received various research grants for Slovenia, where she was working in the Corpus Laboratory of the Institute of Slovenian Language.

Since 2004, Birte Lönneker carries out research on Story Generator Algorithms within the Narratology Research Group Hamburg. She is also a board member of the German Cognitive Linguistics Association.

I will talk about the ideas underlying the project, the current implementation of NeuroScholar, developments from collaboration with the natural language group at ISI and possible collaborations for the future.

In this talk, I will demonstrate the convergence of several popular parsing formalisms (weighted deduction, shared forest, semiring) under the powerful hypergraph formalism. If time permits, I will also show how generic Dynamic Programming can be formalised as hypergraph searching.

Joint work with David Chiang (University of Maryland)

Please bring a pen or pencil and some paper; there is a small exercise!

About the speaker:

Yutaka Sasaki received his Ph.D. in Engineering from the University of Tsukuba, Japan in 2000 for his work on generating Information Extraction rules with hierarchically sored Inductive Logic Programming. He joined NTT Laboratories in 1988. Since then, he was involved in research in rule-based CAI, inductive logic programming, Information Extraction, and Question Answering. From 1995 to 1996, he spent one year at Simon Fraser University, Canada as a visiting researcher. From 1999, he led a subgroup to develop the first practical Japanese Question Answering System SAIQA. Then, he applied SVMs to automatically construct the QA system SAIQA-II from QA and NE data. In June 2004, he moved to ATR Spoken Language Translation Research Laboratories. Currently, he is the head of Department of Natural Language Processing. He is also an organizer of the NTCIR 5 Cross-Lingual Question Answering Task.

Additionally, I will show how word confidence measures can be applied in an interactive SMT system. This system predicts translations, taking parts of the sentence into account that have already been accepted or typed by the user. Through the use of confidence measures, the performance of the prediction engine can be improved.

About the Speaker:

Nicola Ueffing is a graduate research assistant at the group for "Human Language Technology and Pattern Recognition" (Lehrstuhl fuer Informatik VI) at RWTH Aachen University. She received her diploma in mathematics from RWTH Aachen University in 2000. Her research topic is statistical machine translation, focusing on confidence measures for SMT. In 2003, she was a member of the team working on "Confidence Estimation for SMT" at the CLSP workshop at JHU.

In a pedagogical context, speech recognition is a hard thing we're trying to recover signal from noisy language-learner speech--with all of its mispronunciations, disfluencies, and grammatical errors . Language understanding is hopeless unless you have a good approximation of what kinds of mistakes learners make, and you can build a system to anticipate them.

Suppose an English language learner says "Water". Is he asking you for water? Is he telling you there's a puddle in front of you? Is he saying his name is "Walter", but with horrible pronunciation? There's a lot of ambiguity involved. In order to disambiguate, we need to look at the speech signal itself, the utterance's context, the learner's past language performance, and details about the learner's mother language as it relates to English, etc., etc... Only then can we hope to guess what the learner is actually trying to say.

And then, of course, once we've made a good guess at the learner's speech intentions, what do we do about it? How do we correct him? How do we balance the consideration of inherent qualities of learner motivation, language errors, learning objectives, and possibly low-confidence speech recognition, as we generate good pedagogical feedback?

This is NLP (primarily statistical) with a bit of pedagogy theory and linguistic (SLA and phonology) theory sprinkled in.

I will discuss several current projects at Michigan related to text mining from a variety of genres. Depending on the amount of time, I will talk about (a) lexical centrality for multidocument summarization, (b) syntax-based sentence alignment, (c) graph-based classification,(d) lexical models of Web growth, and (e) mining protein interactions from scientific papers. As it turns out, the right representations, when complemented with traditional NLP and IR techniques, turn many of these into instances of better studied problems in areas such as social networks, statistical mechanics, sequence analysis, and computational phylogenetics.

About the Speaker:

Dragomir R. Radev is Assistant Professor of Information, Electrical Engineering and Computer Science, and Linguistics at the University of Michigan, Ann Arbor. He leads the CLAIR (Computational Lingusitics And Information Retrieval) group which currently includes 12 undergraduate and graduate students. Dragomir holds a Ph.D. in Computer Science from Columbia University. Before joining Michigan, he was a Research Staff Member at IBM's TJ Watson Research Center in Hawthorne, NY. He is the author of more than 45 papers on information retrieval, text summarization, graph models of the Web, question answering, machine translation, text generation, and information extraction. Dr. Radev's current research on probabilistic and link-based methods for exploiting very large textual repositories, representing and acquiring knowledge of genome regulation, and semantic entity and relation extraction from Web-scale text document collections is supported by NSF and NIH. Dragomir serves on the HLT-NAACL advisory committee, was recently reelected as treasurer of NAACL, is a member of the editorial boards of JAIR and Information Retrieval, and is a four-time finalist at the ACM international programming finals (as contestant in 1993 and as coach in 1995-1997). Dragomir received a graduate teaching award at Columbia and recently, the U. of Michigan award for Outstanding Research Mentorship (UROP).

Our current work focuses on what are generally referred to as "short text answers" as contrasted to "essays". However we prefer to contrast "factual" with "discursive" answers, and speculate that the former may be amenable to simple statistical techniques, while the latter require more sophisticated natural language analysis. I will show some examples of real exam data and the techniques we are using and developing to handle them.

One might think that "now" simply expresses a temporal property of an event. But in fact in almost every instance, it is used to point up a contrast -- "This is true now. Something else was true then." It is thus more of a relation than a property. I will describe several categories of such relations. Another question of interest about "now" is "How long a period is the word "now" describing in its various uses?": "I'm typing an abstract now" vs. "We travel by automobile now." I suggest some categories of knowledge that need to be encoded to answer this question.

When we successfully understand "A is like B", we have figured out some property that A and B have in common. How can we find that property computationally? In the data I looked at, in 80% of the instances, the property is explicit in the nearby text, and I will talk about how we can identify it. For the remainder I examine the knowledge we would need in order to infer the common property.

I will talk about the importance of randomized algorithms and their potential in speeding up some NLP algorithms. This talk will be a survey of some recent advances in Theoretical Computer Science/Math seen with an NLP point-of-view. I am not going to present any results. But I am hoping that this talk will clarify my thinking process, get feedback from people and help me colloborate with others.

Many current designs for automatic parsers learn probabilities for the relative frequencies of parts-of-speech and syntactic rules, and this has proven to be generally reliable. In spite of the ubiquity of probabilistic techniques for parsing, however, little attention has been given to the linguistic significance of the probabilistic data and what it might say about human performance.

Hawkins proposes a general theory of grammaticalization based on the minimization of syntactic domains. Given that a sentence of any language will contain at least one noun phrase, one verb, and possibly additional noun phrases and prepositional phrases, "minimize domains" suggests that these phrases will order themselves according to whichever pattern requires the least effort to recognize the higher syntactic structure of the sentence. These effects are directly measurable through corpus statistics, and can be interpreted as potential heuristics for probabilistic parsers. In this study, we examine Japanese data from the Kyoto Treebank and test Hawkins' predictions for noun phrase ordering by noun phrase weight as well as by generic semantic types. The discussion will focus primarily on how accurately Hawkins' predictions are reflected in the corpus statistics, and will conclude with observations about how they might be applied to the decision mechanisms of probabilistic parsers.

--------------------------------------------------------------------------

Hai Huang: TBA

--------------------------------------------------------------------------

Jens Stephan: Evaluation and Visualization of a Dialogue System

Evaluations have become a necessary standard to almost any type of research. However, there are many areas where there is no common agreement on how to evaluate, which is the case for complex problem of evaluating dialogue systems. The evaluation of the multi party multi modal dialogue system MRE(1) provides a good example of what questions are important for such an evaluation, how to actually do the evaluation and finally how to how make special problems of the system visible to use the evaluation results to improve the systems performance.

After a brief introduction of the MRE domain and architecture, I will break the task town to a set of general evaluation questions. From there I will explain what kinds of metrics and visualizations are suited to answer those questions and what kind of data is needed, as well as how that data was obtained. Along the road, examples of actual system problems and performances will be presented. The topics of data formatting and visualization will receive some special attention by introducing the MRE Evaluation Toolkit as well as the corpus it operates on.

--------------------------------------------------------------------------

Chen-kang Yang: Using the Omega Ontology to Determine Selectional Restrictions for Word Sense Disambiguation

Experimental results on a large-scale TREC collection show that the proposed approach to improve retrieval effectiveness is successful, while most of the previous work failed to improve performances even on small text collection. The proposed method also shows promising results when is combined with pseudo relevance feedback and state-of-the-art retrieval function such as BM25.

One approach we have been successful with is phrase classification, i.e., classifying a noisy speech-recognized utterance into one of many meaning categories. Phrase classification is computationally cheap and can provide high quality translations for in domain utterances almost instantaneously. Speed is important for speech translation, where processing delay is a great concern.

In this talk, different aspects of building a classification-based speech translator are discussed. Following an overview of automatic speech-to-speech translation and its challenges, a comparison of different classification methods is presented and data collection techniques for that application are introduced.

Bio:

Marcello Federico has been a permanent researcher at ITC-irst since 1991. During 1998-2003, he led the "Multilingual natural speech technologies" (MUNST) research line at ITC-irst. Since 2004, he is head of the "Cross-language information processing" (Hermes) research line. His interests include automatic speech recognition, statistical language modeling, information retrieval, and machine translation.

Bio: Philipp Koehn is the author of papers on natural language processing, machine translation, and machine learning. He received his PhD from the University of Southern California in 2003 (advisor: Kevin Knight), and is currently employed as a postdoc at the Massachusetts Institute of Technology, working with Michael Collins. He has worked at AT&T Laboratories on text-to-speech systems, and at WhizBang! Labs on text categorization.

Natural Language Understanding (NLU) is an essential module of a good dialogue system. To achieve satisfactory performance levels, real time dialogue systems need the NLU module to be both fast and accurate. Finite State Model (FSM) based systems are fast and accurate but lack robustness and flexibility. The Statistical Learning Model (SLM) based systems are robust and flexible but lack accuracy and are at most times slow.

In this talk, I am going to talk about an SLM based NLU approach for dialogue utterances that is both accurate and fast. The system has high accuracy and produces frames in real time.

A Community of Words: Understanding Social Relationships from E-mail

A corpus of e-mail messages presents a number of challenges for NLP techniques, with its nearly unconstrained structure and vocabulary, mistyped words and ungrammatical sentences, and extensive contextual information that is never explicitly stated. Yet, the intrinsically social nature of such communication provides an opportunity to study not just a bag of words, but also the relationships, competencies, and activities behind them.

This talk presents work with Eduard Hovy as part of the MKIDS project.

How does one put this theory to practice and build real summarization systems? How do the systems built based on this idea perform?

In this talk, I will present an innovative method for automatic extraction of conceptual graphs as a means to represent text meaning.  The method relies on a novel adaptation of graph-based ranking algorithms - traditionally (and successfully) used in citation analysis, Web page ranking, and social networks. I will show how such algorithms can be adapted to semantic networks, resulting in an efficient unsupervised method for resolving the semantic ambiguity of all words in open text, and identifying relations between entities in the text. I will also outline a number of applications that are enabled by this representation, including keyphrase extraction, domain classification, and extractive summarization.

(Preview of an HLT/NAACL-2004 Invited Speaker Presentation)

Jill Burstein Educational Testing Service Princeton, NJ

Bio:

Stephan Vogel is a researcher at the Language Technologies Institute, Carnegie Mellon University, where he heads the statistical machine translation team. He received a Diploma in Physics from Philips University Marburg, Germany, and a Masters of Philosophy from the University of Cambridge, England. After working for a number of years on the history of science, he turned to computer science, especially natural language processing. Before coming to CMU, he worked for several years at the Technical Univerity of Aachen on statistical machine translation, and also in the Interactive Systems Lab at the University of Karlsruhe.

Shlomo Argamon is an associate professor at the Illinois Institute of Technology Chicago.

The first phase of the project has been completed and a working system, known as ScamAlert installed at the Australian Securities and Investment Commission (ASIC). The independent audit of the performance of the system proved satisfactory with a result for precision of .75, recall .43, and F=. 54, along with identification of 4 scams misclassified by the client. Significant improvement in recall is foreshadowed in the 2nd phase of the project. The results are satisfying in the context of the structure of the data where the density of scam documents is about 1.8% of the total corpus.

The good performance of the operational system is ascribed to the combination of using a strong linguistic model of language (Systemic Functional Linguistics) to define the scam documents in parallel with a rich statistical analysis of the structure of non-scam documents and scam look-alikes. A large amount of the experimental program has concentrated on understanding and exploiting the interaction between the linguistically described aspects of the documents and the statistical properties. Each type of data has been used to inform and modify the usage of the other.

The operational aspects of the project have proven to be as challenging as the research objectives. The project has a budget of $2.2M over 15 months. It has been managed so as to create a balance in resources between the needs of both the research objectives and the engineering objectives. Software development has concentrated on three aspects. Firstly, to produce an environment for the strong directive management of computational linguistics experiments, secondly, in the aid of the linguists to create tools to support their manual analysis, and thirdly the best practice of software engineering principles to ensure a clean automated rollout of the production system for ASIC.

The results and experimental setups developed in connection with summarization will be extended to the machine translation. I will review possible reasons why metrics such a bleu have experienced significantly more success in machine translation than in summarization. I will also connect the evaluation criterea developed in the context of summarization to machine translation, and discuss the automation of these methods.

In short: I'll talk about why I've been doing so much data elicitaiton recently.

This will be a highly informal seminar and participation is highly encouraged.

(joint work with Michel Galley, Kevin Knight, and Daniel Marcu)

Natural-language engineers the world over are coming to a consensus that a degree of semantic knowledge is a necessary addition to purely structural representations of language. This talk describes the Propbank project at Penn, which provides a complete shallow semantic parse of the Treebank II corpus.

Inducing a Chronology of the Pali Canon:

Works such as Kroch (1989), Taylor (1994) and Han (2000) have demonstrated that syntactic change can be described mathematically as the competition between innovating and archaic formations. This paper demonstrates how this same mathematical description can be turned around to predict the date of a historical text. The Middle Indic period showed dramatic change in the morphological system, such as the collapse of the past-tense verbal system. Whereas Sanskrit had three competing formations, each with multiple possible morphological realizations, Pali (a Middle Indo-Aryan language) had only a single formation, based mostly on the sigmatic aorist although many archaic nonsigmatic aorists are also attested. The proportions of the archaic and innovative forms can be easily calculated for each text in the Pali Canon and these proportions used to assign an approximate date for each text. The accuracy of the method can be assessed qualitatively by comparing the derived chronology to chronologies based on various non-linguistic criteria, or quantitatively by comparing the derived chronology to a known dating scheme. For the latter it is necessary to turn to a different dataset, such as that describing the rise of do-support in Early Modern English, as described in Ellegard (1953) and Kroch (1989).

Bio:

Paul Kingsbury graduated summa cum laude in linguistics from Ohio State University in 1993 with a thesis on "Some sources for L-words in Sanskrit". He subsequently entered the University of Pennsylvania to study historical linguistics and Sanskrit, but (like most historical students) was diverted to computational issues. He joined the Propbank project in 2000 and soon thereafter engineered a major rethinking of the methods and goals of the project, in order to make the annotation linguistically meaningful. He completed his doctorate in 2002 with a thesis entitled 'The Chronology of the Pali Canon: the case of the aorist'.

Bio:

Hang Li is a researcher at the Natural Language Computing Group of Microsoft Research in Beijing, China. He is also adjunct professor of Xian Jiaotong University. Hang Li obtained a B.S. in Electrical Engineering from Kyoto University (Japan) in 1988 and a M.S. in Computer Science from Kyoto University in 1990. He earned his Ph.D. in Computer Science from the University of Tokyo in 1998. >From 1990 to 2001, Hang Li worked at the Research Laboratories of NEC Corporation in Kawasaki, Japan. He joined Microsoft Research in 2001.  His research interest includes statistical learning, natural language processing, data mining, and information retrieval. Hang Li's web site: http://research.microsoft.com/users/hangli/

In this talk, we will present an overview of Question Answering Challenge(QAC), which is the question answering task of the NTCIR Workshop. QAC-1 (the first evaluation of QAC) was carried out at NTCIR Workshop 3 in October 2002, and QAC-2 will be at NTCIR Workshop 4 in December 2003. In the QAC, systems to be evaluated are expected to return exact answers consisting of a noun or noun compound denoting, for example, the names of persons, organizations, or various artifacts or numerical expressions such as money, size, or date. Those basically range over the Named Entity (NE) elements of MUC and IREX but is not limited to them. QAC consists of three kinds of subtasks: Task 1, where the systems are allowed to return ranked five possible answers; Task 2, where the systems are required to return a complete list of answers; and Task 3, the systems are required to answer series of questions, that have anaphora and zero-anaphora. We will present the results of QAC-1, and vision and prospect of QAC-2.

NTCIR -- the Way Ahead Noriko Kando

Dr. Noriko Kando is the leader of NTCIR(Test Collections and Evaluation of IR, Text Summarization, Q&A, etc) project, and an associate professor of National Institute of Informatics (NII). She got her Ph. D in 1995 from Keio University. Her research interest includes evaluation of information retrieval systems, technologies to "Make Information Usable for Users", cross-lingual information retrieval, and analysis of text structure, genre, citation & link She is a member of editorial boards of International Journal on Information Processing and Management, ACM-Transaction on Asian Language Information Processing, etc.

Jun'ichi Fukumoto and Tsuneaki Kato are task organizers of QAC. Dr. Jun'ichi Fukumoto is an associate professor of Ritsumeikan University. He got his Ph. D in 1999 from University of Manchester Institute of Science and Technology. His research interest includes Q&A, automatic summarization, and dialogue processing. Dr. Tsuneaki Kato is an associate professor of the University of Tokyo. He got his Dr. of Engineering in 1995 from Tokyo Institute of Technology. His research interests includes multimodal dialogue processing, multimodal presentation generation and domain independent question and answering. He is a member of editorial committee of transaction on information and systems of The Institute of Electronics, Information and Communication Engineers.

In this talk, I will outline some different ideas that we have been pursuing. I will connect stochastic parsing with finding shortest paths in hypergraphs, and show how this approach naturally provides a chart parser for arbitrary probabilistic context-free grammars (finding shortest paths in a hypergraph is easy; the central problem of parsing is that the hypergraph has to be constructed on the fly). From this viewpoint, a natural approach is to use the A* algorithm to cut down the work in finding the best parse. On unlexicalized grammars, this can reduce the parsing work done dramatically, by at least 97%. This approach is competitive with methods standardly used in statistical parsers, while ensuring optimality, unlike most heuristic approaches to best-first parsing.

Finally, I will present a novel modular generative model in which semantic (lexical dependency) and syntactic structures are scored separately. This factored model is conceptually simple, linguistically interesting, admits exact inferenence with an extremely effective A* algorithm, and provides straightforward opportunities for separately improving the component models. In particular, I will mention some of the work we have done focusing on the PCFG component to produce a very high accuracy unlexicalized grammar.

This is joint work with Dan Klein.

About the Speaker:

Christopher Manning is an Assistant Professor of Computer Science and Linguistics at Stanford University. He received his Ph.D. from Stanford University in 1995, and served on the faculty of the Computational Linguistics Program at Carnegie Mellon University (1994-1996) and the University of Sydney Linguistics Department (1996-1999) before returning to Stanford. His research interests include probabilistic models of language, natural language parsing, constraint-based linguistic theories, syntactic typology, information extraction and text mining, and computational lexicography. He is the author of three books, including Foundations of Statistical Natural Language Processing (MIT Press, 1999, with Hinrich Schuetze).

I will review the state of the art in statistical machine translation (SMT), present my dissertation work, and sketch out the research challenges of syntactically structured statistical machine translation.

The currently best methods in SMT build on the translation of phrases (any sequences of words) instead of single words. Phrase translation pairs are automatically learned from parallel corpora. While SMT systems generate translation output that often conveys a lot of the meaning of the original text, it is frequently ungrammatical and incoherent.

The research challenge at this point is to introduce syntactic knowledge to the state of the art in order to improve translation quality. My approach breaks up the translation process along linguistic lines. I will present my thesis work on noun phrase translation and ideas about clause structure.

This is joint work with Daniel Marcu and Kevin Knight.

I discuss practical and theoretical motivations for the task, evaluations of our model, increases in performance achieved over the summer, and directions for future research.

This work was done in collaboration with Kevin Knight, Daniel Marcu, Jonathan Graehl and Nick Mote.

We will describe a large effort to extend a high-performing phrase-based MT system as baseline by adding new features representing syntactic knowledge that deal with specific problems of the underlying baseline. We investigate a broad range of possible feature functions, from very simple binary features to sophisticated tree-to-tree translation models. Simple feature functions test if a certain constituent occurs in the source and the target language parse tree. More sophisticated features will be derived from an alignment model where whole sub-trees in source and target can be aligned node by node. We present results on the Chinese-English large data track of the recent TIDES MT evaluations.

This is joint work with the other workshop team members: Daniel Gildea, Anoop Sarkar, Sanjeev Khudanpur, Kenji Yamada, Libin Shen, Shankar Kumar, David Smith, Viran Jain, Katherine Eng, Jin Zhen and Dragomir Radev.

See http://www.clsp.jhu.edu/ws03/groups/translate/ for more.

2) Headlines are useful for users who only need information on the main topics of a story. We present a headline summarization system that is built at ISI for this purpose and is a top performer for DUC2003's task 1, generating very short summaries (10 words or less).

http://guir.berkeley.edu/oral-history/

In this talk, I will discuss my recent work at applying a stochastic generator, HALogen, and its newswire language model to a dialogue system, TRIPS. I'll describe the difficulties in mapping the TRIPS semantic form into HALogen's representation, the critical differences between newswire and dialogue, and the possibility of using HALogen and a large newswire model as a domain independent generator.

We will introduce the Open Archival Information Systems (OAIS) model, and then focus on two key processes: ingestion and access. Our focus in ingestion is on support for review and redaction, which we believe will be key enablers to acquisition and near-term access. For access, we will address both browsing based on provenance (original order) and user-guided reorganization based on search and visualization. Along the way, we will identify potentially productive opportunities to apply natural language processing technologies such as topic segmentation, link detection, and summarization. We will then describe two test collections, and demonstrate a system that we have developed to explore user-guided reorganization through visualization for one of those collections. We will conclude the talk by sketching out a research agenda. At that point, we will expect suggestions and comments from the audience. Knowing this audience, it is unlikely that we will need to wait that long :-).