A central question is: where do the types and relations come from?

The subfield of NLP concerned with this is relation extraction, which comprises two main tasks: 1. identifying and extracting relation instances from text 2. determining the types of their predicates and arguments The first task is difficult for several reasons. Relations can express their predicate explicitly or implicitly. Furthermore, their elements can be far part, with unrelated words intervening. In this thesis, we restrict ourselves to relations that are explicitly expressed between syntactically related words. We harvest the relation instances from dependency parses. The second task is the central focus of this thesis. Specifically, we will address these three problems: 1) determining argument types 2) determining predicate types 3) determining argument and predicate types. For each task, we model predicate and argument types as latent variables in a hidden Markov models. Depending on the type system available for each of these tasks, our approaches range from unsupervised to semi-supervised to fully supervised training methods.

We have also studied bigger picture questions such as how much weight tweets by Big Bird (or someone pretending to be Big Bird) should be allocated in reporting the results of sentiment analysis. Question about the role of humor and sarcasm in social media lead to some skepticism of naive applications of sentiment analysis but present interesting examples of content that influences social media user behavior and spills over into traditional media.

Recent advances in unsupervised algorithms have demonstrated promising results on several NLP tasks without using any labeled data. But despite their utility, scalable unsupervised algorithms rarely provide probabilistic representations of the data which can be useful for predicting on unseen data or integrated as components with a larger model or pipeline. In addition, these methods often favor simple model descriptions (e.g., k-means algorithm for clustering) in exchange for rich statistical models. This leads to the problem of rapidly diminishing returns when applying these methods on increasing amounts of data. Instead, we need to design algorithms that can scale elegantly to large data as well as complex models.

In this work, I will present our recent work on scalable probabilistic learning with Bayesian inference. We show a novel algorithm for fitting mixtures of exponential families, which generalizes several models that are typically used in NLP and other areas. A major contribution of our work is a novel sampling method that uses locality sensitive hashing to achieve high throughput in generating proposals during sampling. Using "clustering" as an example application, I will describe our approach and show that it scales elegantly to large numbers of clusters achieving a speedup of several orders of magnitude over existing toolkits, while maintaining high clustering quality. In addition, we also prove probabilistic error guarantees for the new sampling algorithm. This is joint work with Amr Ahmed and Alex Smola. Lastly, I will briefly mention some ongoing work on large-scale unsupervised learning for other NLP applications such as machine translation.

Bio: Sujith Ravi is a Research Scientist at Google. He completed his PhD at University of Southern California/Information Sciences Institute and joined Yahoo! Research, Santa Clara as a Research Scientist before joining Google, Mountain View in 2012. His main research interests span various problems and theory related to the fields of Natural Language Processing (NLP) and Machine Learning. He is specifically interested in large-scale unsupervised and semi-supervised methods and their applications to structured prediction problems in NLP, information extraction, user modeling in social media, graph optimization algorithms for summarizing noisy data, computational decipherment and computational advertising. His work has been reported in several magazines such as New Scientist, ACM TechNews, etc. For more information, you can visit his personal page (http://www.sravi.org).

In this talk, I will present some of our recent work modeling multiple aspects of human communication dynamics, including behavioral dynamic, multimodal dynamic and interpersonal dynamic. I will describe the different computational models specifically designed model these dynamics, including the Latent-Dynamic Conditional Random Fields, Multi-view Hidden Conditional Random Fields and the Latent Mixture of Discriminative Experts. I will show how these technologies can be applied to real-world problems such as negotiation outcome prediction, YouTube opinion mining, group learning analytics and psychological distress indicators. Finally, I will summarize our recent progress in integrating these sensing technologies with a virtual human for healthcare application.

Bio:

This talk will focus on three important problems which contribute towards a unified computational framework for ensembles of diverse experts. The first problem deals with "modeling" a diverse ensemble. I will present our proposed Globally-Variant Locally-Constant (GVLC) model as a statistical framework for answering this question. The second question is about "analysis", where I will address the link between ensemble diversity and performance using statistical learning theory. The final segment of my talk will focus on "designing" an ensemble of diverse linear classifiers, specifically conditional maximum entropy models. Practical applications throughout the talk will include emotion classification from speech, text classification, and crowd-sourcing for automatic speech recognition.

This talk will describe our ongoing efforts on Behavioral Signal Processing (BSP)--technology and algorithms for quantitatively and objectively understanding typical, atypical and distressed human behavior--with a specific focus on communicative, affective and social behavior. Using examples drawn from different application domains, the talk will also illustrate Behavioral Informatics applications of these processing techniques that contribute to quantifying higher-level, often subjectively described, human behavior in a domain-sensitive fashion. [Work supported by NIH, NSF, DARPA, and ONR].

Biography of the Speaker: Shrikanth (Shri) Narayanan is Andrew J. Viterbi Professor of Engineering at USC, where he is Professor of Electrical Engineering, and, jointly in, Computer Science, Linguistics and Psychology. Prior to USC he was with AT&T Bell Labs and AT&T Research. His research focuses on human-centered information processing and communication technologies. He is a Fellow of the Acoustical Society of America, IEEE, and the American Association for the Advancement of Science (AAAS). Shri Narayanan is an Editor for the Computer, Speech and Language Journal and an Associate Editor for the IEEE Transactions on Multimedia, the IEEE Transactions on Affective Computing and the Journal of Acoustical Society of America having previously served an Associate Editor for the IEEE Transactions of Speech and Audio Processing (2000-2004) and the IEEE Signal Processing Magazine (2005-2008). He is a recipient of several honors including the 2005 and 2009 Best Paper awards from the IEEE Signal Processing Society and serving as its Distinguished Lecturer for 2010-11. With his students, he has received a number of best paper awards including winning the Interspeech Challenges in 2009 (Emotion classification), 2011 (Speaker state classification) and in 2012 (Speaker trait classification). He has published over 500 papers and has 13 U.S. patents.

We support our thesis using theoretical, experimental, computational results. The theoretical arguments use Russell's notion of definite descriptions, Carnap's notion of theoretical entities, and the question-asking period in child language acquisition. The experimental data we collected include dialogs between humans and computers and web-based surveys, both using crowd-sourcing on Amazon Mechanical Turk. The computational models include a dialog agent based on sequential Bayesian belief update within a generalized pushdown automaton, as well as a fuzzy logic model of similarity and subsethood between emotion terms.

For future work, we propose a research agenda that includes a continuation of work on the emotion domain as well as new work on other domains where subjective descriptions are established through natural language communication.

Short Bio: Abe Kazemzadeh is a PhD candidate at the USC Computer Science Dept and a research assistant at the the Signal Analysis and Interpretation Laboratory (SAIL). His interests include natural language, logic, emotions, games, and algebra. He is currently the chief technology officer at the USC Annenberg Innovation Laboratory (AIL).

I will give a demo of our web-based AMR Editor, which is used by dozens of annotators at LDC, SDL/LanguageWeaver (Cluj) and other places. Finally, I will give an overview of our initial end-to-end prototype, with rule extraction (own work), decoding from source language to AMR (work by Yinggong Zhao) and AMR to target language generation (Yang Gao).

This talk describes the application of Semantic Web formalisms, RDF, OWL/DL and SPARQL, to facilitate the interoperability of linguistic corpora and linguistic annotations. Interoperability of linguistic corpora involves two aspects: Structural interoperability (annotations of different origin are represented using the same formalism) and conceptual interoperability (annotations of different origin are linked to a common vocabulary). I will describe ontology-based approaches for both aspects, the POWLA ontology that defines a data model for annotated corpora, and the Ontologies of Linguistic Annotation (OLiA) that provide definitions for linguistic categories and properties (Chiarcos 2012). As compared to state-of-the-art approaches based on standoff XML, e.g., the recently published ISO standard for an Linguistic Annotation Framework, key advantages of this approach include the existence of a rich technological ecosystem developed around RDF and OWL, including standardized query languages for directed acyclic (multi-) graphs (SPARQL), APIs, data base implementations, as well as the availability of OWL reasoners that can be applied to validate the consistency of linguistic corpora and their annotations and to infer additional information that is relevant, for example, for their appropriate visualization.

Naturally, representing corpora in OWL and RDF also allows to interlink resources freely, e.g., different annotation layers of a multi-layer corpus, translated texts in parallel corpora, or linguistic corpora and lexical-semantic resources. Modeled in this way, corpora can be fully integrated in a Linked Open Data (sub-)cloud of linguistic resources, along with lexical-semantic resources and knowledge bases of information about languages and linguistic terminology. The second part of my talk will introduce recent efforts to create a Linked Open Data sub-cloud of linguistic resources, the Linguistic Linked Open Data cloud (Chiarcos et al. 2012, cf. http://linguistics.okfn.org).

References

Christian Chiarcos, Sebastian Hellmann, Sebastian Nordhoff, et al. (2012), The Open Linguistics Working Group, Proceedings of the 8th International Conference on Language Resources and Evaluation (LREC-2012). Istanbul, Turkey, May 2012. [http://www.lrec-conf.org/proceedings/lrec2012/pdf/912_Paper.pdf]

Christian Chiarcos (2012), Interoperability of Corpora and Annotations, In: Christian Chiarcos, Sebastian Nordhoff, and Sebastian Hellmann (eds.) Linked Data in Linguistics. Representing and Connecting Language Data and Language Metadata. Springer, Heidelberg. [http://www.springer.com/computer/ai/book/978-3-642-28248-5]

Bio

About the Speaker:

The central idea of my dissertation is to learn low-dimensional subspaces (or interlingual representations) that are effective for various multilingual and monolingual NLP tasks. First, I demonstrate the effectiveness of interlingual representations in mining bilingual word translations for machine translation, and then proceed to developing models for diverse situations that often arise in NLP tasks. In particular, I design models for 1) bridge setting -- when there are more than two views but we only have training data from a single pivot view into each of the remaining views 2) reranking setting -- when an object from one view is associated with a ranked list of objects from another view, and finally 3) when the underlying objects have rich structure, such as a tree.

A previous study (Frank and Bod, 2011) compared unlexicalized sequential and hierarchical models of human sentence processing, and found that sequential models explain observed human behavior (e.g. eye movements) during sentence processing better than hierarchical models. The authors concluded that the human sentence processing mechanism is insensitive to hierarchical syntactic structure.

We investigate this claim, and find a picture that is more complicated than the one presented by the previous study. First, we show that lexicalized syntactic models explain observed human behavior during sentence processing better than unlexicalized syntactic models. Second, we consider a broader set of sequential and hierarchical models, and show that the findings of (Frank and Bod, 2011) do not generalize to this broader set. Finally, we show why, even within the set of models considered by (Frank and Bod, 2011), their findings are not entirely conclusive. Our results indicate that the claim that the human sentence processing mechanism is insensitive to hierarchical syntactic structure is premature.

We aim to exploit this property of deep learning to transfer knowledge from resource-rich to resource-poor domains. We facilitate the transfer of knowledge by constraining the learned embeddings of both domains to share as much structural similarity as possible. I will discuss preliminary results for noisy text normalization in Twitter, where the task is to transfer the correct clean words from English to the noisy Twitter domain, and review the main deep learning models for NLP (Bengio et al. (2003, Mnih and Hinton (2007), Collobert and Weston (2008), Mikolov et al. (2010), and Socher et al. (2011)).

Bio:

This is a practice talk for ACL.

Bio:

This is joint work with Mark Johnson and Sharon Goldwater to be presented at this year’s ACL

Bio:

Bio:

The large number of relations makes relation extraction challenging; given a sentence, many possible relations can be extracted. If we can specify the relations we are interested in beforehand, we can annotate data to train supervised systems. Often though, definition beforehand is impossible, and we have to find all possible relations that hold in a text. In those cases, we must rely on unsupervised approaches. A second problem is rapid adaptation to new domains and topics. Relations extracted from one domain may not be relevant to another. A third problem is variation in the ways relations are expressed in text. Often, intervening words and phrases between predicates and arguments cause fixed-window pattern matching approaches to fail.

Most previous relation extraction approaches have either relied on annotated data or (semi-) structured sources of information. These approaches require pre-defined relations and manually annotated data. Furthermore, many of these approaches rely on pattern matching over surface strings, which is not robust to variations. If previous approaches used unsupervised training methods, they largely focused on clustering, effectively ignoring sequential structure in the data.

The future of QA will require us to quickly adapt to new domains and topics with little annotated data. Only if we can discover and disambiguate relations automatically can we build systems capable of open-ended QA. I present several techniques for discovering relations from text. I show how to use unsupervised sequential models to discover relations from raw text. These methods do not require any existing resources, manual annotation, or pre-defined relations, and can be applied to any domain. I use dependency parse structures as inputs to these methods, making these approaches more robust to surface variations. I show improvements over state-of-the-art systems as well as novel approaches to fully exploit the structure contained in the data.

* to interpret, to translate and to generate pronouns, definite and indefinite NPs correctly,

* to translate non-canonical constructions (e.g., passive),

* to generate the correct word order (e.g., when translating into a free-word order language),

* to insert or to drop discourse markers and conjunctions, or

* to choose the appropriate type of syntactic embedding in complex sentences.

In other branches of NLP, different aspects of discourse are important, e.g., relations between utterances (machine reading), the hierarchical organization of discourse (text summarization) and the sequential organization of utterances in a text (text structuring/natural language generation).

Numerous models of different aspects of discourse have been proposed, including discourse structure (the hierarchical organization of utterances in discourse), discourse relations (relations between independent utterances in discourse), information structure (the functional structure of utterances in context), and information status (accessibility of antecedents of pronouns, definite descriptions and elliptic constructions). These approaches range from relatively abstract models from cognitive and functional linguistics (e.g., Givon 1983), over elaborate formal models developed in formal semantics (e.g., Asher 1993), to "parameterized", rule-based models in AI (e.g., Grosz et al. 1995).

Since the mid-1990s, this traditional, "theory-centered" line of research has been complemented with an "annotation-centered" methodology, i.e., the development and the use of annotated corpora to test predictions and to develop statistical classifiers. In the first part of the talk, I describe selected activities of the applied computational linguistics group at the University of Potsdam/Germany in this direction, which include

* the annotation of discourse structure, coreference, information structure and information status (Stede 2004, Krasavina and Chiarcos 2007, Ritz et al. 2008)

* the development of generic multi-layer architectures capable to represent and to access these annotations along with other types of annotation applied to the same stretch of data (Chiarcos et al. 2008), e.g., annotations for constituent syntax, dependency syntax, or frame semantics, and

* the application of machine learning techniques to predict discourse features from less abstract annotation layers (Ritz 2007, Chiarcos 2011).

The primary drawback of annotation-centered models are the immense cognitive (and thus, financial) efforts necessary to produce reliable discourse annotations. One way to address this problem is to make use of corpora without discourse annotations to test predictions of candidate models, and to develop unsupervised or weakly supervised approaches to support or to replace manual annotation.

In the second part of my talk, this "data-centered" approach on discourse will be illustrated for the example of discourse relations, one of the main topics of my work at ISI. I describe a pilot study that shows that significant, reproducible and interpretable insights about the discourse relation (that is likely to be) connecting a pair of events can be achieved from a sufficiently large corpus with syntax annotations only. Further, possible lines for subsequent research will be sketched.

Nicholas Asher (1993). Reference to Abstract Objects in Discourse. Kluwer, Dordrecht, 1993.

Christian Chiarcos (2011). Evaluating salience metrics for the context-adequate realization of discourse referents. In: Proceedings of the 13th European Workshop on Natural Language Generation (ENLG 2011). Association of Computational Linguistics, Nancy, France, Sep 2011, 32-43.

Christian Chiarcos, Stefanie Dipper, Michael Gotze, Ulf Leser, Anke Lüdeling, Julia Ritz, and Manfred Stede (2008). A Flexible Framework for Integrating Annotations from Different Tools and Tagsets. TAL (Traitement automatique des langues) 49 (2): 218-248.

Talmy Givon (ed., 1983). Topic Continuity in Discourse: A Quantitative Cross-Language Study. John Benjamins, Amsterdam and Philadelphia.

Barbara J. Grosz, Aravind K. Joshi, and Scott Weinstein (1995). Centering: A framework for modelling the local coherence of discourse. Computational Linguistics, 21(2):203–225.

Olga Krasavina and Christian Chiarcos (2007). PoCoS - Potsdam Coreference Scheme. In Proceedings of the Linguistic Annotation Workshop. Held in Conjunction with the ACL-2007, Prague, Czech Republic, pages 156–163.

Julia Ritz, Svetlana Petrova, Michael Götze, and Stefanie Dipper (2007). Automatic Identification of Information Structure in Small Corpora of Modern and Old High German. GLDV-Fruhjahrstagung 2007, Tubingen, Germany.

Julia Ritz, Stefanie Dipper, und Michael Götze (2008). Annotation of Information Structure: An Evaluation Across Different Types of Texts. In Proceedings of the the 6th LREC conference. Marrakech, Morocco.

Manfred Stede (2004). The Potsdam Commentary Corpus. In Bonnie Webber and Donna K. Byron, editors, Proceedings of the ACL-2004 Workshop on Discourse Annotation, Barcelona, pages 96–102.

Biography:

Christian Chiarcos, born 1977, studied Computer Science (MSc, 2002) and General Linguistics (MA, 2004) at the Technical University Berlin, Germany. From 2002 to 2003, he received a scholarship in the context of the project "Collocations in Dictionary" at the Berlin-Brandenburg Academy of Science under the auspicion of Christiane Fellbaum (Princeton). From 2003 to 2005, he participated in the graduate school "Economy and Complexity in Language" at the Humboldt-Unversity at Berlin and the University of Potsdam, Germany, where he developed a corpus-based approach to predict syntactic alternations for Natural Language Generation. This research formed the basis for his PhD thesis "Mental Salience and Grammatical Form" (University of Potsdam, 2010).

What is in common between translating from English into Chinese and compiling C++ into machine code? And yet what are the differences that make the former so much harder for computers? How can computers learn from human translators?

This talk sketches an efficient (linear-time) "understanding + rewriting" paradigm for machine translation inspired by both human translators as well as 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 rewriting rules. In both "understanding" and "rewriting" stages, this paradigm closely resembles the efficiency and incrementality of both human processing and compiling. We will discuss these two stages in turn.

First, for the "understanding" part, we present a linear-time approximate dynamic programming algorithm for incremental parsing that is as accurate as those much slower (cubic-time) chart parsers, while being as fast as those fast but lossy greedy parsers, thus getting the advantages of both worlds for the first time, achieving state-of-the-art speed and accuracy. But how do we efficiently learn such a parsing model with approximate inference from huge amounts of data? We propose a general framework for structured prediction based on the structured perceptron that is guaranteed to succeed with inexact search and works well in practice.

Clinical documentation forms an abundant source to extract valuable information that can be used for this purpose, however clinical corpora contain protected health information and must be kept in a safe way. Today only in Sweden (with a population of 10 million) 4-10 million pages of patient records are produced each year.

We have studied the Stockholm EPR Corpus, a huge clinical document collection written in Swedish, containing over one million patient records. The document collection is distributed over 900 clinics from the Stockholm area encompassing three years 2006-2008. We have used this clinical corpus as a knowledge base to develop a set of tools that can work as basic building blocks for the future tools for health engineering. We have been assisted by physicians that have interpreted the content in the clinical text to us, they have annotated the clinical text and they have also set requirements on these tools together with their colleagues. We have identified four groups of users in the health domain: physicians, clinical researchers, hospital management and patients. We will show examples on these tools and the benefits they will give to health care.

1) For physicians: Automatic ICD-10 assignment 2) For clinical researchers: Comorbidity networks 3) For hospital management: ICD-10 validation and adverse event detection, and finally 4) For patients: automatic text summarization.

Brief Bio:

Dr. Hercules Dalianis, Professor, born 20 July 1959

Dalianis is a professor in Computer and Systems Sciences at Stockholm University. Dalianis received his Ph.D in 1996. Dalianis was a postdoc researcher at University of Southern California/ISI in Los Angeles in 1997. Dalianis was also postdoc researcher (forskarassistent) at KTH-Royal Institute of Technology in Stockholm, 1999-2003. Dalianis held a three year guest professorship at CST, University of Copenhagen during 2002-2005, founded by the Norfa, the Nordic council. Dalianis works in the interface between industry and university and with the aim to make research results useful for society. Dalianis has specialized in the area of human language technology, to make computers understand and process human language text, but also to make computers produce text automatically. Currently Dalianis is working in the area of clinical text mining with the aim to improve health care in form of better electronic patient record systems, presentation of the patient records and extraction of valuable information for clinical researchers as well as for the patients.

To verify the usefulness of the feature-based approach, I discuss the performance two models: first, a lexical translation model evaluated by the word alignments it learns. Unlike previous unsupervised alignment models, the new model utilizes features that capture diverse lexical and alignment relationships, including morphological relatedness, orthographic similarity, and conventional co-occurrence statistics. Results from typologically diverse language pairs demonstrate that the generate-and-test model provides substantial performance benefits compared to state-of-the-art generative baselines. Second, I discuss the results of an end-to-end translation model in which lexical, configurational, and wellformedness constraints are modeled independently. Because of the independence assumptions, the model is substantially more compact than state-of-the-art translation models, but still performs significantly better on languages where source-target word order differences are substantial.

Biography: Gael Dias is full professor at the University of Caen Basse-Normandie (France). His research interests include unsupervised methodologies for text mining, information retrieval and text summarization. His recent research focuses on Sentiment Analysis, Ontology Learning, Lexical Semantics, Web Personalization and Collaboration, Temporal Information Retrieval, and Paraphrase Extraction and Identification. He has served on program committees of international conferences and workshops such as ACL/HLT 2011, COLING 2010, IJCNLP/ACL 2009, ACL 2007, HLT-NAACL 2007, COLING/ACL 2006 as well as is/was a reviewer for Information Processing and Management, IEEE Transactions on Audio, Speech and Language Processing, Natural Language Engineering Journal, Journal of Language Resources and Evaluation, Journal of Computer Speech and Language and ACM Transactions on Speech and Language Processing.

First, we motivate our work by providing compelling empirical evidence that n-gram LMs are not sufficient for ASR task and why we need to incorporate non-local features such as syntax. The development of language models with such long-span (non-local) features is underway, but is not addressed in this talk. We instead address how such models should be trained discriminatively and applied effectively. Specifically, we describe a new approach for rescoring speech lattices with such models (acoustic or language) that does not entail computationally intensive lattice expansion or limited rescoring of only an N -best list.

We view the set of word-sequences in a lattice as a discrete space and develop a hill climbing technique to start with, say, the 1-best hypothesis under the lattice-generating model(s) and iteratively improve it using the new model. We demonstrate empirically that to achieve the same reduction in error rate using a better estimated, higher order LM, our technique evaluates fewer hypotheses than conventional N-best rescoring by up to two orders of magnitude.

We also propose to integrate the idea of hill climbing into the training of discriminative language models with non-local sentence level features. Discriminative models provide the flexibility to include both local n-gram features and arbitrary sentence level features. However, unlike generative LMs with long-span dependencies where one has to resort to N-best lists only during decoding (rescoring), discriminative models force the use of N-best lists even for LM training. We demonstrate significant computational saving during training as well as error-rate reduction over N-best training methods.

Bio:

Ariya Rastrow is a Ph.D. candidate at Johns Hopkins University, working with Sanjeev Khudanpur and Mark Dredze. He was initially advised by Fred Jelinek. The focus of his PhD research is to advance speech recognition systems to efficiently incorporate linguistically motivated non-local features into language models. In his recent work, he has developed an efficient hill-climbing algorithm to apply non-local complex models for the speech recognition task. He has also worked on out-of-vocabulary (OOV) detection, spoken term detection and semi-supervised adaptation techniques for speech recognition.

The three main types of the existing knowledge sources are lexical-semantic dictionaries, distributional resources, and ontologies. After comparing these types of resources and outlining their differences, I will present an integrative knowledge base combining lexical-semantic, ontological, and distributional knowledge in a modular way.

I will then talk about reasoning procedures able to make use of the large scale knowledge base. In particular, I will compare two main forms of logical inferences applied to NLU: deduction and abduction.

Much MT research focuses on types of the patterns and features to include in a translation model. Recent statistical MT models have used syntax trees to enforce grammaticality, but the currently popular tree substitution models only memorize sequences of words or constituents, specifying exactly what phrases to use and exactly what trees are grammatical, which does not generalize well. Adding the operation of tree-adjoining provides the freedom to splice additional information into an existing grammatical tree. An adjoining translation model allows general, linguistically-motivated translation patterns to be learned without the clutter of endless variations of optional material. The appropriate modifiers, such as adjectives, adverbs, and prepositional phrases, can be grafted into these core patterns as needed to translate details. We show that the increased generalization power provided by adjoining, when used carefully, improves MT quality without becoming computationally intractable.

We exploit this by trying to establish relations between events (such as ``bombing'' or ``election'') and temporal expressions that can be resolved to a timestamp, i.e., an expression like ``last Tuesday'' to an absolute value like 20110802. This enables a number of interesting applications, such as generation of absolute timelines, cross-document event coreference, and resolution of logical discrepancies.

However, in text editors for programmers ww find so-called language-aware editing functions. These functions operate on the elements and structures of a programming or mark-up language and help to avoid errors, as language-aware functions make revising and editing less tedious and error-prone.

We argue that the concept of language awareness can be transferred to writing natural language texts using word processors. We propose functions that take the structures of natural languages into consideration. We distinguish information functions, movement functions, and operations to support revising and editing. The design is based on current findings from writing research.

Language-aware editing functions rely on the recognition and categorization of relevant elements and structures with respect to a certain language. We use methods and resources from computational linguistics for morphological analysis and generation, and for part-of-speech tagging. When evaluating respective resources we face a rather disappointing situation: NLP resources for German are less suitable than assumed and less applicable for real-world applications than usually claimed in the literature.

The meaning of phrases and sentences is determined by the meanings of its words and the rules of compositionality. We introduce a recursive neural network (RNN) for syntactic parsing which can learn vector representations that capture both syntactic and semantic information of phrases and sentences. For instance, the phrases "declined to comment" and "would not disclose" have similar representations. Since our RNN does not depend on specific assumptions for language, it can also be used to find hierarchical structure in complex scene images. This algorithm obtains state-of-the-art performance for semantic scene segmentation on the Stanford Background and the MSRC datasets and outperforms Gist descriptors for scene classification by 4%.

The ability to identify sentiments about personal experiences, products, movies etc. is crucial to understand user generated content in social networks, blogs or product reviews. The second architecture I will talk about is based on semi-supervised recursive autoencoders (RAE). RAEs learn vector representations for phrases sufficiently well as to outperform other traditional supervised sentiment classification methods on several standard datasets. Lastly, I describe an alternative unsupervised RAE model that can learn features which outperform previous approaches for paraphrase detection on the Microsoft Research Paraphrase corpus.

This talk presents joint work with Andrew Ng and Chris Manning.

Bio: Richard Socher is a Computer Science PhD student at Stanford, co-advised by Chris Manning and Andrew Ng. Most recently, he won the Yahoo! Key Scientific Challenges Program Award and the Distinguished Application Paper Award at ICML, 2011 for his work on recursive deep learning.

The first contribution of this thesis is to advance the theoretical foundations for the interpretation of three ambiguous linguistic phenomena in English that have significant overlap in terms of the relations expressed: noun compounds, possessive constructions, and prepositions. For these, I define inventories of relations based upon extensive annotation by myself, previous work by others, and inter-annotator agreement studies. In the case of prepositions, the relations are created by refining an existing resource whereas the other two are created from scratch. In addition to mappings to prior work, mappings are provided across the different inventories in order to create a unified set of relations.

Second, I produce large datasets annotated according to the aforementioned sense inventories. Such data is vital for training most automatic tools and also provides exemplars for the theory embodied in the inventories. Some of these datasets are created from scratch, including a collection of over 17,500 noun compounds and a collection of over 21,900 possessive construction examples. In the case of prepositions, an existing resource including over 24,000 annotated examples is refined.

The final contribution is a suite of tools that can construct semantically-enriched parse trees. The suite is designed to work in a sequential, pipeline-like fashion and can be thought of as consisting of two subsections. The first part reconstructs the grammatical structure of the text using a dependency parser that extends the non-directional easy-first algorithm developed by Goldberg and Elhadad (2010) in order to support non-projective trees and is trained using my improved dependency tree conversion of the Penn Treebank. Second is a semantic annotation module that adds shallow semantic annotation for noun compounds, preposition senses, and possessives. Combined, these tools produce semantically-enriched parse trees that include both grammatical structure and shallow semantics. The core parser itself achieves state-of-the-art accuracy and can process over 75 sentences per second, which is substantially faster than most of the accurate parsers available today.

In conclusion, this thesis work provides significant contributions to computational linguistics, both in terms of theory and resources. It advances our understanding of the relations expressed by three semantically-ambiguous linguistic phenomena, creates large annotated datasets useful for machine learning, and produces a fast, accurate, and informative system for semantically-enriched parsing.

I will give an overview of the three primary tasks that are the current focus of our research. The first is urgency detection, which involves detecting important chat messages within a dynamic chat stream. The second is summarization, which involves summarizing chat conversations and temporally summarizing sets of chat messages. The third is human-subject studies, which involves simulating a watchstander environment and testing whether our urgency detection and summarization ideas, along with 3D-audio cueing, can aid a watchstander in conducting their duties.

Short Bio: Deniz Yuret is an assistant professor in Computer Engineering at Koc University in Istanbul. Previously he was at the MIT AI Lab and later co-founded Inquira, Inc. His research is on lexical semantics and unsupervised approaches to parsing and disambiguation. Currently he is one of the organizers of the SemEval3 semantic evaluation exercise, co-chair for the ACL 2011 semantics area, and an editor for the Computational Linguistics Journal.

The first part of the talk concentrates on interpreting answers to yes/no questions which do not straightforwardly convey a 'yes' or 'no' answer. I focus on questions involving scalar modifiers (Was it acceptable? It was unprecedented.) and numerical answers (Are you kids little? I have a 10 year-old and a 7 year-old.). I exploit the availability of large amount of text to learn meanings from words and sentences in real context. I show that we can ground scalar modifier meaning based on large unstructured databases, and that such meanings can drive pragmatic inference.

The second part of the talk targets veridicality -- whether a speaker intends to convey that the events described are actual, non-actual or uncertain -- which is central to language understanding, but little used in relation and event extraction systems. What do people infer from a sentence such as FBI agents alleged in court documents today that Zazi had admitted receiving weapons and explosives training from al Qaeda operatives? Did Zazi received weapons and explosives training? I show that not only lexical semantic properties but context and world knowledge shape veridicality judgments. Since such judgments are not always categorical, I suggest they should be modeled as distributions, and propose a classifier to do so. The classifier features provide a nuanced picture of the diverse factors that affect veridicality.

Short Bio: Thomas Schoenemann was born and grew up in Germany. He studied Computer Science at RWTH Aachen, Germany, where he got a diploma in 2005, having written his diploma thesis on the topic of confidence measures in machine translation in the group of Hermann Ney. Afterwards he went to the University of Bonn, Germany, to do his Ph.D. thesis in computer vision in the years 2006-2008. Up to a month ago he was a postdoc in the vision group at Lund University, Sweden, where he also resumed his work on translation. Currently he is taking a time off to explore other fields and broaden his scope.

First, I will describe a generalization of the hierarchical Dirichlet process model to account for additional properties associated with observable objects. In addition, to overcome some of the limitations of this new model, I will then describe a new hybrid model which combines an infinite latent class model with a discrete time series model. The main advantages of this hybrid model are the abilities to represent a potentially infinite number of features associated with observable objects and to perform an automatic selection of the most salient features. Furthermore, all the models described in this talk are designed to account for a potential number of categorical outcomes. The evaluation performed for solving both within- and cross document event coreference shows significant improvements of the models when compared against three baselines for this task.

Short Bio: Cosmin Adrian Bejan is a postdoctoral researcher at the USC Institute for Creative Technologies, where he is currently working on applications that involve extraction and analysis of commonsense knowledge from large collections of text documents. His research interests include event semantics, semantic parsing, commonsense causal reasoning, unsupervised learning, and nonparametric Bayesian methods.

In this talk, we describe challenges encountered by phrase-based and syntax-based 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. Then we present a method for learning the rules and associated probabilities of this grammar from aligned tree/string training data.

Finally, our results show that adjoining delivers a consistent improvement over a baseline statistical syntax-based MT model on both medium and large-scale MT tasks using several language pairs.

First, I will describe efforts towards Information Extraction from status messages. Because statuses can be posted quickly and are widely disseminated, they often provide the most up-to-date source of information on current events around the world and locally. This dynamically changing source of realtime information is already being processed using keyword extraction techniques, for example the "trends" displayed on Twitter's website provide a list of phrases which are frequent in the current stream of messages. In order to move beyond a flat list of phrases, we have been investigating the feasibility of applying Information Extraction techniques to produce more structured representations of events. A key challenge is the noisy nature of this data; unlike newswire, or biomedical text, status messages contain frequent misspellings and abbreviations, inconsistent capitalization, unique grammar, etc... To deal with these issues, we have been annotating a corpus of Twitter Posts with POS tags and Named Entities, then using these annotations to train Twitter-specific NLP tools. As a demonstration of their utility, the resulting tools are combined to produce a calendar of popular events occurring in the future.

In addition, I will discuss work which exploits a corpus of roughly 1.3 million naturally occurring conversations collected from Twitter for building models of human conversation. Three data-driven approaches to generating responses to Twitter status posts are considered, based on either information retrieval or phrase-based statistical machine translation. Although there are many challenges to overcome in adapting phrase-based SMT to dialogue, we show that it is a promising approach to this problem. We compare these approaches in a human evaluation, using annotators from Amazon's Mechanical Turk service. Furthermore, we measure agreement between human evaluators and the BLEU automatic MT evaluation metric. As far as we are aware, this is the first work to investigate the application of phrase-based SMT to dialogue generation.

Vector space models have become a standard way of representing word meaning that can be learned in an unsupervised way. The problem of polysemy, however, has only recently been addressed within this framework. Several approaches to derive vector representations of words in specific sentential contexts have been proposed. I will present recent work on extending such contextualization operations to vector models incorporating rich syntactic structure, achieving significant improvements in context-dependent lexical substitution tasks.

Going beyond the meaning of single words, I will then turn to work on semantic role labeling. Here, a key obstacle is the annotation effort required for the training of high quality role labeling systems. I will present a semi-supervised approach to semantic role labeling, based on generalizing semantic annotations from manually labeled seed sentences to unlabeled sentences via structural alignments, yielding significant improvements in role labeling performance.

I will conclude my talk with an outlook onto how the search for adequate models of semantics may profit from formulation in task-specific ways. In particular, I will sketch some ideas on structured semantic models for statistical machine translation.

In this talk I'll briefly discuss a novel use of spreading activation (SA) techniques (primarily from cognitive science) for computing semantic relatedness between words and/or documents. This is done by modelling the article hyperlink structure of Wikipedia as an associative network structure for knowledge representation. The SA technique is adapted and several problems are addressed for it to function over the derived Wikipedia hyperlink graph. We evaluate these approaches over standard document similarity datasets and by user evaluation experiments, and achieve results which compare favourably with state of the art methods.

The presented dissertation work tackles the problem of inflectional morphology with a novel, unified statistical approach. We present a generative probability model that can be used to learn from plain text how the words of a language are inflected, given some minimal supervision. In other words, we discover the inflectional paradigms that are implicit, or hidden, in a large unannotated text corpus.

This model consists of several components: a hierarchical Dirichlet process clusters word tokens of the corpus into lexemes and their inflections, and graphical models over strings -- a novel graphical-model variant -- model the interactions of multiple morphologically related type spellings, using weighted finite-state transducers as potential functions.

We present the components of this model, from (1) weighted finite-state transducers parameterized as log-linear models, to (2) graphical models over multiple strings, to (3) the final Bayesian non-parametric model over a corpus, its lexemes, inflections, and paradigms. These three components of the model correspond to the combined use of (1) dynamic programming, (2) belief propagation and (3) MCMC for inference.

We show experimental results for several tasks along the way, including a lemmatization task in multiple languages and, to demonstrate that parts of our model are applicable outside of morphology as well, a transliteration task. Finally, we show that learning from large unannotated text corpora under our non-parametric model significantly improves the quality of predicted word inflections.

Twenty years ago, the research area of machine translation was beginning to make use of the increasing availability and speed of computing resources demanded by the ideas of a previous generation, notably Weaver (1949). The IBM translation models -- statistical models for automatic word-to-word translation (Brown et al., 1990; Brown et al., 1993) - spurred a flurry of new statistical and empirical research in this area. They have become ubiquitous in the field and are easy to train in an unsupervised fashion; Al-Onaizan et al. (1999) and Och and Ney (2003) have given us open-source toolkits for this purpose.

In this talk I argue for a new kind of semantics, which is combines traditional symbolic logic-based proposition-style semantics of the kind used in older NLP with (computation-based) statistical word distribution information (what is being called Distributional Semantics in modern NLP). The core resource is a single lexico-semantic 'lexicon' that can be used for a variety of tasks provided it is reformulated appropriately. I show how to define such a lexicon, how to build and format it, and how to use it for various tasks. The talk pulls together a wide range of related topics, including Pantel-style resources like DIRT, inferences / expectations such as those used in Schank-style expectation-based parsing and expectation-driven NLU, PropBank-style word valence lexical items, and the treatment of negation and modalities.

The first part introduces dual decomposition as a framework for deriving inference algorithms for NLP problems. The approach relies on standard dynamic-programming algorithms as oracle solvers for sub-problems, together with a simple method for forcing agreement between the different oracles. The approach provably solves a linear programming (LP) relaxation of the global inference problem. It leads to algorithms that are simple, in that they use existing decoding algorithms; efficient, in that they avoid exact algorithms for the full model; and often exact, in that empirically they often recover the correct solution in spite of using an LP relaxation.

The second part presents an application of dual decomposition to non-projective parsing . We focus on parsing algorithms for non-projective head automata, a generalization of head-automata models to non-projective structures. The dual decomposition algorithms are simple and efficient, relying on standard dynamic programming and minimum spanning tree algorithms. They provably solve an LP relaxation of the non-projective parsing problem. Empirically the LP relaxation is very often tight: for many languages, exact solutions are achieved on over 98% of test sentences.The accuracy of our models is higher than previous work on a broad range of datasets.

Bio: William Yang Wang is a graduate student at Columbia University, and he is currently visiting the NL Dialog Group at USC/ICT, working on phonetically aware natural language understanding and speech synthesis. In 2008-2009, he was with the Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences.

(This talk will present joint work with Steve Abney.)

Brief Bio:

Steven Bird is Associate Professor in the Department of Computer Science and Software Engineering at the University of Melbourne, and also Senior Research Associate at the Linguistic Data Consortium. In 2009 he served as president of the Association for Computational Linguistics, and he completed a textbook on Natural Language Processing, published by O'Reilly. Steven studies scalable, semi-automatic methods for analyzing spoken and written language, and for preserving endangered languages. This involves a mixture of computational modelling and linguistic fieldwork. For further details and online publications, please visit http://stevenbird.me/

Joint work with Tom Griffiths (Berkeley) and Sharon Goldwater (Edinburgh)

Speaker Bio:

Mark Johnson is a Professor of Language Science (CORE) in the Department of Computing at Macquarie University. He was awarded a BSc (Hons) in 1979 from the University of Sydney, an MA in 1984 from the University of California, San Diego and a PhD in 1987 from Stanford University. He held a postdoctoral fellowship at MIT from 1987 until 1988, and has been a visiting researcher at the University of Stuttgart, the Xerox Research Centre in Grenoble, CSAIL at MIT and the Natural Language group at Microsoft Research. He has worked on a wide range of topics in computational linguistics, but his main research area is parsing and its applications to text and speech processing. He was President of the Association for Computational Linguistics in 2003, and was a professor from 1989 until 2009 in the Departments of Cognitive and Linguistic Sciences and Computer Science at Brown University.

Bio:

Walter Daelemans (PhD in Computational Linguistics, University of Leuven, 1987). Trained as a linguist and psycholinguist at the Universities of Antwerpen and Leuven, he specialised in computational linguistics and held research posts at the University of Nijmegen and the AI Lab of the University of Brussels before becoming a lecturer in Computational Linguistics and Artificial Intelligence at Tilburg University where he founded an early research group on machine learning of language (ILK). Since 1999 he is full-time professor at the University of Antwerp where he also heads the computational linguistics group within the CLiPS research centre. His main research interests are in machine learning of language (especially memory-based learning), text analytics, and computational psycholinguistics. He co-founded ACL's Special Interest Group on Natural Language Learning (SIGNLL) and its associated conference and shared task series (CoNLL).

I will also explain the need of linguistic knowledge and introduce some weakly supervised learning methods. I will show a demo of the ngram search engine, which extracts ngrams and sentences which match to a query with arbitrary wildcard.

Also, I will give a brief introduction about the Web People Search. It is a task to disambiguate search results of people name and people attribute extraction task. We organized WePS1 and 2, and currently started the third evaluation, which includes 2 tasks: 1) the combined task of people disambiguation and attribute extraction and 2) organization disambiguation from twitter messages.

Brief Bio:

Satoshi Sekine is an Research Associate Professor at New York University. He received his MSc at UMIST, UK in 1992 and his PhD in 1998 at NYU. He has been working on various topics, including parsing, NE, Information Extraction and minimally supervised knowledge discovery. He edited a book about NE from John Benjamins, organized a JHU summer workshop 2009, WePS task, NSF symposium on Semantic Knowledge Discovery, Organization and Use in 2008, workshop on Textual Entailment and Parsing 2007 and so on.

Your participation in order to critique the tutorial is appreciated!

In order to alleviate this problem, we use compact structures such as lattices and forests instead of single-best results in each module, and then integrate both lattice and forest into a single tree-to-string system. We explore the algorithms of lattice parsing, lattice-forest-based rule extraction and decoding. Experiments show a statistically significant improvement over a start-of-the-art forest-based baseline. More interestingly, we observe a significant reduction in rule-set size when extracting with a lattice, which implies better generalizability (with a smaller model).

About the speaker:

Haitao Mi is an Assistant Researcher in the Institute of Computing Technology, Chinese Academy of Sciences (CAS/ICT). He received his Ph.D. from CAS/ICT in 2009. His main research interests include syntax-based machine translation and statistical parsing. Additional information about him and his group can be found at http://nlp.ict.ac.cn/~mihaitao/

There are two problems with existing approaches to automatic word alignment and parsing for syntax-based machine translation. First, these processes are noisy and introduce errors which impact translation quality. Second, these processes are typically performed independently of one another. Since each process produces constraints that can be used to guide the other, by more closely integrating them, we can expect to improve the accuracy of each process. In this thesis, we address these two problems as follows: first, we improve upon the accuracy of a state-of-the-art parser; second, we use word alignments to improve parse accuracy; third, we use parses to improve word alignment accuracy; and fourth, we optimize parses and word alignments simultaneously. We examine the impact of each of these methods upon parse quality, alignment quality, and translation quality in a downstream syntax-based machine translation system. Our results demonstrate that more closely integrating word alignment and syntactic parsing can indeed improve the accuracy of each process, and in some cases leads to an improvement in translation quality relative to a state-of-the-art syntax-based statistical machine translation system.

Brief bio:

Parsing is the task of finding the most probable interpretation for a given sentence, and is a central problem in NLP because it serves as the basis of many downstream applications such as machine translation, summarization, paraphrasing, and question answering. Improving parsing efficiency and accuracy will greatly improve the applicability of those applications.

However, unlike human parsing which is amazingly efficient by scanning the sentence incrementally, current state-of-the-art parsers are either extremely slow (standard algorithms like CKY scale cubically with sentence length), or purely greedy in the search algorithm that only touches a tiny fraction of the (exponentially) large search space. We instead propose a dynamic programming algorithm that does incremental parsing and ambiguity packing along the way, such that the running time is (almost) linear, and yet searches over exponentially many trees. Empirical results are very good, but further details withheld -- come to the talk!

The central activities include developing techniques and tools for: - converting texts into representations of the particular events and entities they refer to, - identifying relations between these entity and event instances such as shared participants, temporal and spatial juxtapositions, causal connections, entailments, and so on, thereby constructing representations of complex scenarios, - inducing from sets of like entity, event and scenario instances, representations of entity, event and scenario types, - using these entity, event and scenario types as background knowledge to support approximate inferencing (e.g., statistical inference rules such as poisoning probably entails death) within important interactive tasks such as Information Retrieval and web search.

Speaker Bio:

In basic text analysis, we have been developed Japanese morphological analyzer and parser, which are widely used in research community. Case frames, which describe the relation between a verb and its case components, are automatically constructed from a large Web corpus. Synonym and is-a relations are automatically extracted from a dictionary and Web corpus.

In Information Retrieval, we are running a search engine infrastructure called TSUBAKI. The features of TSUBAKI are (i) the sentence structure (dependency relation) is considered in the document ranking, and (ii) the expression divergence between a query and a document is assimilated. We are also running a search result clustering system based on TSUBAKI.

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.

Jointly parsing two languages has been shown to improve accuracies on either or both sides. However, its search space is much bigger than the monolingual case, forcing existing approaches to employ complicated modeling and crude approximations. Here we propose a much simpler alternative, bilingually-constrained monolingual parsing, where a source-language parser learns to exploit reorderings as additional observation, but not bothering to build the target-side tree as well. We show specifically how to enhance a shift-reduce dependency parser to use alignment features to resolve shift-reduce conflicts. Experiments on the bilingual portion of Chinese Treebank show that, with just 3 bilingual features, we can improve parsing accuracies by 0.6% for both English and Chinese, with negligible (~6%) efficiency overhead, thus much faster than biparsing.

K-Best A* Parsing (Adam Pauls)

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:

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.

WIDL-expressions represent compactly probability distributions over finite sets of candidate realizations, and have optimal algorithms for text realization via interpolation with language model probability distributions. We show the effectiveness of our WIDL-based NLG engine for both sentence realization and document realization tasks. By employing language models that capture sentence-level properties, we perform Machine Translation and Headline Generation at state-of-the-art levels or better. By employing language models that capture document-level properties such as text coherence, we synthesize output for Multi-document Summarization that displays both high content selection performance and increased coherence.

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.

The topics & approximate start times:

(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 :-).