Reasoning With Text

February 18-19, 2011

USC Institute for Creative Technologies

Los Angeles, CA

Intelligent robots of the future are going to need to know a lot of stuff. They are going to need to know how a power outage will affect my plans for a holiday party. They need to know what to do if the dishwasher floods my apartment while I am away on a business trip. They need to know to stay off the carpet if my son pours wet paint all over them. How are we ever going to be able to teach all of this stuff to these robots?

Maybe the answer is to give them a lot to read. There are millions of personal stories in Internet weblogs that have a lot of this knowledge in them. There are millions of how-to articles on the web that give step-by-step instructions for a lot of stuff. There are dedicated websites that collect and catalog millions of people's plans and goals; maybe these can be put to good use. But how?

Natural language understanding is hard work. If we require deep understanding in order to put this text to use, then we've simply exchanged one impossible problem for another. Instead, we should be looking for just the right text corpus, and just the right mix of natural language processing necessary to support the reasoning task at hand. If we can figure out exactly what class of reasoning problems we are trying to solve, and how that relates to the structure of the text in a particular corpus, then deep understanding may not be required.

Tucked away deep in the bowels of research labs all across the planet, creative PhD students and junior researchers are working on this problem. They share a common desire to harness natural language processing technologies and the web in order to tackle long-standing artificial intelligence problems. However, they are largely unaware of each other, or even that there is a community of more-senior researchers that care deeply about what they are doing. Now would be a good time to gather all of these people together.

How about a workshop? It would be a great way to bring together junior and senior researchers, where former can share their new ideas and the latter can help foster a healthy research community. Los Angeles is nice, even in the middle of winter. The University of Southern California's Institute for Creative Technologies (ICT) has a fancy new building that would work perfectly, so we've booked the facilities for February 18 and 19. ICT workshops are well organized and always a lot of fun. We've secured some funding to ensure that all be well fed and entertained, and that some of the airfare and hotel expenses can be reimbursed. Let's do it!

Schedule

 

Friday February 18th

9:00 am - 10:30 am

Commonsense causal reasoning using millions of personal stories

Andrew Gordon, University of Southern California, Institute for Creative Technologies

Cause-Effect Relation Learning using the Web as a Corpus

Zornitsa Kozareva, USC ISI

Toward a new semantics: Integrating propositional and distributional information (SLIDES)

Eduard Hovy, University of Southern California, Information Science Institute

11:00 am - 12:00 noon

Reasoning with (Not Quite) Text (SLIDES)

Henry Lieberman, MIT

1:00 pm - 3:00 pm

Activity-based Human Experience Mining

Sung-Hyon Myaeng, KAIST

Extracting Action Ingredients from Non-imperative Sentences in How-to Instructions (SLIDES)

Jihee Ryu, KAIST

Daily life is revealed by the stories people tell in weblogs

Christopher Wienberg, USC ICT

Open-domain interactive storytelling with SayAnything

Reid Swanson, Disney Research

3:30 pm - 5:00 pm

Building a memory by telling stories

Larry Birnbaum, Northwestern University

What Can Machines Learn by Reading Tweets?

Alan Ritter, University of Washington

Using Social Streams for Knowledge Acquisition

Markus Strohmaier, Technical University Graz

 

 

Saturday February 19th

9:00 am - 10:30 am

Reading the Second Book

Peter Clark, Vulcan Inc.

Applications and Discovery of Granularity in Natural Language Discourse

Rutu Mulkar-Mehta, USC ISI

Why can we extract generic knowledge from text?

Benjamin Van Durme, Johns Hopkins University

11:00 am - 12:30 pm

Analogical Dialogue Acts: Supporting Learning by Reading Analogies

David Barbella, Northwestern University

Learning and evaluating conversational dialogue policies using text examples

Kenji Sagae, USC ICT

From Text to Rules (SLIDES)

Jerry Hobbs, USC ISI

1:30 pm - 3:00 pm

Learning from text: It takes an architecture

Kenneth D. Forbus, Northwestern University

Towards Learning World Knowledge Suitable for Inference (SLIDES)

Jonathan Gordon, University of Rochester

An Activity Knowledge Base from Multiple Resources: Construction and Utilization (SLIDES)

Yuchul Jung, KAIST and ETRI

3:30 pm - 5:00 pm

Is General Knowledge about Events and Narratives Useful?

Nate Chambers, Stanford University

How to mine an event network (SLIDES)

Dustin Smith, MIT

Learning to predict events and induce event schemas from personal stories

Cosmin "Adi" Bejan, USC ICT

Information for invited participants

  • Location information: here
  • Nearby hotels: here
  • Area attractions: here

Abstracts of talks

Toward a new semantics: Integrating propositional and distributional information

Eduard Hovy, University of Southern California, Information Science Institute

This talk argues for a new kind of semantics that 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. Combining the two views of semantics opens many fascinating questions that invite study. I show how to define such a lexicon, how to build and format it, and how to use it for various tasks.

 

Commonsense causal reasoning using millions of personal stories

Andrew Gordon, University of Southern California, Institute for Creative Technologies

The personal stories that people tell in their weblogs reveal an enormous amount of information about causality in the everyday world. In this talk I will review our efforts to capture and utilize this information on a massive scale.

 

Open-domain interactive storytelling with SayAnything

Reid Swanson, Disney Research

The dichotomy between literal truth and personalized interpretation is a reoccurring theme, arising in Frege's study of semantics, Propp's study of narrotology and Barthe's study of photography. The majority of computational approaches that model meaning, and storytelling in particular, have focused most of their effort on one side of this dichotomy, what Propp would call the fabula, or the literal events of the story. Although there are many reasons for this, one of the primary explanations is the incredible difficulty in hand authoring the breadth and depth of human emotions, relationships, desires and goals. However, without these key ingredients woven into the narration, the resulting stories are flat and lack the emotional and cultural connections that make narratives meaningful and compelling to people. Fortunately, the rise of the social web has changed this equation. Instead of trying to enumerate all of the goals, activities and emotions we can leverage the vast amount knowledge implicitly available in the millions of personal stories shared on individual's weblogs that are posted every month. In this talk I will discuss how my storytelling application, Say Anything, is able to learn from this natural language text in order to produce, not just plausible event sequences, but is also able to generate content that feels more natural because of its rich embedding of human emotion, culture and local color.

 

What Can Machines Learn by Reading Tweets?

Alan Ritter, University of Washington

Social Media websites (such as Facebook and Twitter) offer a promising source of real-time and social information not available elsewhere on the web.  This stream of raw un-edited data presents severe challenges, however, as large numbers of irrelevant status messages can easily lead to information overload.  If a person could read all 50 million tweets produced each day, they would find many timely bits of important information, however this is well beyond human capabilities.  Computers, on the other hand, are well adept at processing and aggregating information at this scale, but their understanding of natural language is currently far from human-level.  Complicating the problem is the noisy nature of Twitter; unlike newswire or biomedical text, tweets contain frequent misspellings, inconsistent capitalization, etc... rendering off-the-shelf NLP tools nearly useless.  Recognizing named entities in text is a key step towards enabling machines to derive structured information suitable for reasoning.  This talk will describe our initial efforts towards machine-understanding of status messages; in particular it will focus on recognizing entities in this informal text using domain-adaptation and semi-supervised techniques to address challenges such as those listed above.  In addition it will present preliminary results on applications made possible by accurate NE tagging over millions of Tweets.

Relevant Paper: Unsupervised modeling of Twitter conversations, with Colin Cherry and Bill Dolan, NAACL-2010

 

Applications and Discovery of Granularity in Natural Language Discourse

Rutu Mulkar-Mehta, USC ISI

Granularity is the concept of breaking down an event into smaller parts or granules such that each individual granule plays a part in the higher level event. For example, the activity of driving to the grocery store involves some fine-grained events like opening the car door, starting the engine, planning the route, and driving to the destination. Each of these may in turn be decomposed further into finer levels of granularity. For instance, planning the route might involve entering an address into GPS and following directions. The phenomenon of granularity is observed in various domains, including scientific literature, game reports, and political descriptions. In scientific literature, the process of photosynthesis on closer examination is made up of smaller individual fine-grained processes such as the light dependent reaction and the light independent reaction.

This talk is about the phenomenon of granularity in natural language. Humans can seamlessly shift their granularity perspective while reading or understanding a text. To emulate this mechanism, I will describe a set of features that identify the levels of granularity in text, and the empirical experiment conducted to verify this feature set using a human annotation study for granularity identification. This theory is the foundation for any system that can learn the (global) behavior of event descriptions from (local) behavior descriptions. This is the first research initiative, for identifying granularity shifts in natural language descriptions.

 

How to mine an event network

Dustin Smith, MIT

Over a million procedural descriptions for common activities such as 'buy a house' and 'kick a soccer ball', are available on websites like eHow.com and wikiHow.com, but they are represented as ordered trees of English imperatives. Is it possible to convert these instructions into a machine interpretable network of goals and actions? What should such a network contain? This talk will address the motivation behind this project and some of the problems and modeling decisions it entails. In particular, I will focus on the problems of (1) mapping English imperatives to their corresponding action representation, and (2) computing similarity between actions and plans.

 

Towards Learning World Knowledge Suitable for Inference

Jonathan Gordon, University of Rochester

To enable human-level artificial intelligence, we want machines to have access to the same kind of commonsense knowledge about the world people have. This knowledge needs to be available in large volumes, at high quality, and in a form that supports reasoning. While the Web offers a vast quantity of text with a breadth of topics, it also presents the problem of dealing with casual, unedited writing, which can lead to low-quality knowledge. Ongoing work with the KNEXT system identifies good commonsense factoids from the bad and sharpens them into stronger, quantified claims to be used in the Epilog reasoning engine. This talk presents the state of the knowledge base produced by this large-scale automatic extraction and sharpening.

 

Learning from text: It takes an architecture

Kenneth D. Forbus, Northwestern University

Text by itself is ambiguous: We understand it via context, provided by our interactions with others and with the world. The Companions cognitive architecture we are building is intended to be a software social organism, working with, and learning from, human partners over extended periods of time. Most cognitive architecture can potentially provide valuable aspects of context, because language is integrated with reasoning and behavior. We believe Companions are especially suitable for learning and reasoning from text because analogical processing is central. Analogical processing provides mechanisms for re-using experience directly in new situations, and refining multiple experiences into probabilistic generalizations. This talk will describe how we are exploring these ideas in two efforts. The first is our second-generation learning by reading system, which is focusing on learning large bodies of conceptual knowledge from text and sketches. The second is an exploration of what it takes to achieve interactive learning via multimodal interaction, over extended periods of time, using a strategy game as a simulated environment.

 

Analogical Dialogue Acts: Supporting Learning by Reading Analogies

David Barbella, Northwestern University

Analogy is heavily used in written explanations, particularly in instructional texts. We introduce the concept of analogical dialogue acts, the roles utterances play in instructional analogies. We describe a catalog of such acts, based on ideas from structure-mapping theory. We focus on the operations that these acts lead to while understanding instructional texts, using the Structure-Mapping Engine and dynamic case construction in a computational model. We test this model on a small corpus of instructional analogies, expressed in simplified English, which were understood via a semi-automatic natural language system using analogical dialogue acts. The model allowed for improved question-answering performance on comprehension questions and further improved performance by incorporating existing knowledge into the analogy to aid in structuring it.

 

Is General Knowledge about Events and Narratives Useful?

Nate Chambers, Stanford University

Recent work in learning general knowledge without human intervention has focused on richer structures for events and participants. One particular representation is the narrative schema. While knowledge of this type is scientifically interesting, examples of how it can be usefully used in NLP applications are not always satisfying. I will discuss one particular application that may yield fruit: extracting slot fillers for information extraction (IE). IE often relies on human annotators to inject examples of the desired relations and slots into supervised (or weakly-supervised) extraction systems. Only recently does work like Open-IE attempt to remove the human dependency, but these are mostly limited to learning atomic binary relations. I will show how richer event structure can be learned and applied to an IE application.

 

Using Social Streams for Knowledge Acquisition

Markus Strohmaier, Technical University Graz

The acquisition of knowledge about common human goals represents a major challenge. In this talk, I will investigate a novel resource for this task: The utilization of social streams of data, in particular search query logs. By relating goals contained in search query logs with goals contained in existing commonsense knowledge bases such as ConceptNet, we aim to shed light on the usefulness of social streams for capturing knowledge about common human goals. The talk sketches ways how goals from search query logs could be used to address the goal acquisition and goal coverage problem related to commonsense knowledge bases.

Related paper: Studying Databases of Intentions: Do Search Query Logs Capture Knowledge about Common Human Goals?

 

An Activity Knowledge Base from Multiple Resources: Construction and Utilization

Yuchul Jung, KAIST and ETRI

Active user participations and interactive communications among users in the Web 2.0 era have made it possible to elicit a vast amount of user activity information from the Web resources. At the same time, they call for a more advanced technology that enables a correct understanding of individual and/or group activities, situations, and intents of the users in various domains. There is no doubt that the vast amount of information on human experiences involving activities is going to help understanding human activities of various sorts. Our research centers around the question of how to turn the vast amount of activity-related information into a form that can be utilized for various intelligence-enabled applications. Focusing on human activity information, we introduce a new approach to knowledge base construction by exploring and integrating structured, semi-structured and unstructured forms of activity knowledge. More specifically, we start with a manually constructed knowledge base consisting of a small number of commonsense activity frames and augment them automatically with how-to articles containing step-by-step instructions and blog posts in a free text form.
In this talk, I will introduce the key idea of the proposed approach with overall architecture and implemented modules with real examples. A set of preliminary experimental results will be also presented. Finally, I will illustrate potential applications of the enriched activity knowledge in different domains.

Related paper: Automatic construction of a large-scale situation ontology by mining how-to instructions from the web

 

Activity-based Human Experience Mining

Sung-Hyon Myaeng, KAIST

The Web can be seen as a massive memory for human activities and experiences. Not only do online news papers report on various events the public would be interested in but also personal and social media such as blog posts and twits reflect various personal activities and experiences that could be gathered and utilized for various decision making purposes. We have embarked on projects whose common goal is to utilize the vast amount of information on human experiences involving activities. In this talk, I will introduce our ongoing efforts to automatically capture and represent activity-based human experiences from the Web. With the aid of huge activity or situation ontology constructed automatically, mined human experiences can be utilized for various applications including query-free search and "decision-on-the-go", primary capabilities to be realized in a mobile/smart phone environment.

Related papers: Personal Information Access Using Proactive Search and Mobile Hypertext ; Detecting Experiences from Weblogs ; Automatic construction of a large-scale situation ontology by mining how-to instructions from the web

Extracting Action Ingredients from Non-imperative Sentences in How-to Instructions
Jihee Ryu, KAIST

A how-to article in ehow.com contains a description of a goal to achieve and specific action steps to carry out. Once translated into a situation ontology form, the how-to instructions in such a large-scale resource would be valuable for detecting an activity a system user is currently engaged in or a document like blog text describes as part of user experiences. However, extracting actions and associated ingredients from manually generated how-to instructions on the Web is non-trivial because they vary in writing styles include implicit expressions for actions to be taken. In this research, we attempt to determine whether a non-imperative sentence is in fact actionable and label the action verb and associated ingredients. Based on an observation that actionable sentences have certain dominant linguistic and stylistic characteristics, we formulate the task of detecting actionable sentence and the knowledge components as a classification problem. Features include sentence types, intent types, activity revealing clues, semantic classes of major verbs, etc. This work expands and complements our previous work on automatic knowledge base construction for situation ontology.

Relevant Papers: Automatic Extraction of Human Activity Knowledge from Method-Describing Web Articles (2010, AKBC) Automatic construction of a large-scale situation ontology by mining how-to instructions from the web (2010, Journal of Web Semantics)

 

Building a memory by telling stories

Larry Birnbaum, Northwestern University

Providing machines with organized memories of events seems like a good idea. Over the past year + we've been working on systems to automatically generate narratives from data. Doing that well requires figuring out the critical features of the data and what they mean thematically. We've recently started thinking about building a memory of stories generated and how it could be used to enrich the analysis and narrative generation process. This talk will describe both our results in narrative generation and our more speculative thinking about how to build and use a memory of narratives.

 

Reading the Second Book

Peter Clark, Vulcan Inc.

In 2003, Ed Feigenbaum suggested the following Grand Challenge: Given a formal encoding of a textbook, have the computer "read" the next text in the field, augmenting its existing knowledge base as it reads (with some level of human interaction allowed). In our work on Project Halo, we are building a large, (manually built) knowledge base that partially encodes a sizable part of a biology textbook, and thus in principle will soon be in a position to explore this challenge (although we have not yet decided on this route). In this talk I will assess the opportunities and difficulties in addressing this task, in particular how and why a large knowledge base can substantially address some of the otherwise daunting challenges for machine reading, and what problems still remain.
Relevant papers: Machine Reading as a Process of Partial Question Answering

 

Learning and evaluating conversational dialogue policies using text examples

Kenji Sagae, USC ICT

Most task-oriented conversational dialogue systems use dialogue policies to decide what to say next in response to a user utterance. These dialogue policies are usually modeled using system-specific representations of knowledge, dialogue acts, system objectives, etc, which are coupled with linguistic knowledge and human intuition about conversations in formal machinery such as rules, deduction systems, or state transition networks. In this talk I will present ongoing work that approaches dialogue policy creation and evaluation from a data-driven standpoint, where knowledge and intuition are represented as natural language examples, minimizing the need for formal modeling and technical expertise.

 

Personal stories in weblogs are a source of information about daily life

Christopher Wienberg, USC ICT

The rise of weblogging has created new opportunities to study the behavior of people on a large scale. In this paper we explore the potential of one genre of weblog posts, the personal stories that people write about their everyday lives. We describe our efforts to collect every English-language personal story posted in weblogs in 2010. Using supervised machine-learning techniques, we developed an accurate story classifier, and used it to filter a daily stream of posts provided to us by a commercial weblog aggregator. The resulting corpus, consisting of over 10 million personal stories, provides a unique opportunity to examine the daily lives of millions of people. We compare this resource to other sources of information about human behavior, including search query logs and micro-blogging, by tracking the use of certain words and phrases of the course of a year. We demonstrate that personal stories are similar to micro-blogs in that they document the everyday experiences of people, but provide greater depth of content through the use of the narrative form.

 

Learning to predict events and induce event schemas from personal stories

Cosmin "Adi" Bejan, USC ICT

Information about events is continuously streaming through news and social media, and, as a result, textual documents describing events are available in unprecedented number. In text documents, events are not described in isolation, but rather in the context of scenarios where an event can interact with other events. In our efforts to capture some of these relations, we focus on studying how can we predict what event is most likely to happen if we already know what sequence of events already happened. Or, more generally, we would like to know what are the most probable scenarios that can happen, given the fact that we know that some events already happened or are going to happen. I this talk, I will present some preliminary experiments for answering to these questions by building Markov models from chains of story events.

 

Why can we extract generic knowledge from text?

Bejamin Van Durme, Johns Hopkins University

Researchers have been opening papers with talk of addressing the "knowledge acquisition bottleneck" for years. These introductions invariably jump into the details of one or another (semi-)automatic method for bulk, text-based extraction of semi-structured material that the authors assure us will be useful, someday. Rather than discuss my own methods or datasets, I'll give a non-technical argument of why this has been partially successful, from a linguistic-pragmatic view. I'll then suggest a distinction between mining knowledge about the world, versus knowledge about what one tends to find expressed in text. This distinction, owing to "reporting bias", means we may not be doing quite what we have been claiming as our research goal. This point is speculative, and meant to provoke discussion.
Portions of this talk are based on the following, and references therein: Van Durme, B. "Extracting Implicit Knowledge from Text". PhD Thesis. University of Rochester. 2010.

 

 

Reasoning with (Not Quite) Text

Henry Lieberman, MIT

Many projects in machine reading or textual analysis try to abstract logical propositions from English text. Others try to do reasoning directly from textual statements using statistical or Bayesian methods. A few brave projects have taken a stab at trying to integrate these two approaches.

This talk will present new representation and reasoning methods that work with an intermediate form with an (adjustable) granularity midway between raw text and full logic. Starting from the text, it is minimally processed with well-known transformations such as stemming and tagging. Pattern matching looks for a limited (but extensible) set of fairly general relations. The result looks something like conventional logical assertions, but the terms can be full noun phrases or verb phrases (e.g. "eat a sandwich"), and there is no assumption of uniqueness or exactness.

Conventional logical reasoning proceeds by inferring new assertions, one by one, by means of inference rules. In contrast, reasoning with this representation proceeds by putting all the knowledge "in a box", and transforming the whole box at once to produce a knowledge space. The box is represented by a concept-versus-feature matrix and inference proceeds by computing the principal components of this matrix. This "fills in gaps" in the knowledge space, and self-organizes it along salient dimensions like "good vs. bad" or "cheap vs. expensive". We argue that this representation holds promise for working with Commonsense knowledge; vaguely expressed knowledge; less tangible concepts like affect or overall "sense"; and possibly inconsistent bodies of knowledge.

 

 

Cause-Effect Relation Learning using the Web as a Corpus

Zornitsa Kozareva, USC ISI

A challenging problem in open information extraction and text mining is the learning of the selectional restrictions of semantic relations. I will present a minimally supervised bootstrapping algorithm that uses a single seed and a recursive lexico-syntactic pattern to learn the arguments and supertypes of cause-effect relation from the Web. Finally, I will show how the harvested knowledge can be used to generate new paraphrases expressing cause-effect relation between pairs of nominals.

 

From Text to Rules

Jerry Hobbs, USC ISI

Natural language descriptions of procedures and other collections of rules are rarely close to the format needed for computational purposes. Complex inference is needed to bridge the gap. In this talk I will present an analysis of a short but difficult text, with a discussion of how it could be translated, in an abduction framework, into a formal ontology and I will point out some problems associated with doing so.

 

Participants

David Barbella, Northwestern University
Cosmin "Adi" Bejan, USC ICT
Larry Birnbaum, Northwestern University
Peter Clark, Vulcan Inc.
Nate Chambers, Stanford University
Yuchul Jung, KAIST and ETRI
Kenneth D. Forbus, Northwestern University
Andrew Gordon, USC ICT
Jonathan Gordon, University of Rochester
Jerry Hobbs, USC ISI
Eduard Hovy, USC ISI
Zornitsa Kozareva, USC ISI
Henry Lieberman, MIT
Niloofar Montazeri, USC ISI
Rutu Mulkar-Mehta, USC ISI
Sung-Hyon Myaeng, KAIST
Sara Owsley Sood, Pomona College
Alan Ritter, University of Washington
Jihee Ryu, KAIST
Kenji Sagae, USC ICT
Dustin Smith, MIT
Markus Strohmaier, Technical University Graz
Reid Swanson, Disney Research
Benjamin Van Durme, Johns Hopkins University
Christopher Wienberg, USC ICT