Eugene Charniak

AAAI Conference 2014 Conference Paper

Identifying Differences in Physician Communication Styles with a Log-Linear Transition Component Model

• Byron Wallace
• Issa Dahabreh
• Thomas Trikalinos
• Michael Barton Laws
• Ira Wilson
• Eugene Charniak

We consider the task of grouping doctors with respect to communication patterns exhibited in outpatient visits. We propose a novel approach toward this end in which we model speech act transitions in conversations via a log-linear model incorporating physician specific components. We train this model over transcripts of outpatient visits annotated with speech act codes and then cluster physicians in (a transformation of) this parameter space. We find significant correlations between the induced groupings and patient survey response data comprising ratings of physician communication. Furthermore, the novel sequential component model we leverage to induce this clustering allows us to explore differences across these groups. This work demonstrates how statistical AI might be used to better understand (and ultimately improve) physician communication.

AAAI Conference 1997 Conference Paper

Statistical Parsing with a Context-Free Grammar and Word Statistics

• Eugene Charniak

AIJ Journal 1996 Journal Article

Taggers for parsers

• Eugene Charniak
• Glenn Carroll
• John Adcock
• Anthony Cassandra
• Yoshihiko Gotoh
• Jeremy Katz
• Michael Littman
• John McCann

We consider what tagging models are most appropriate as front ends for probabilistic context-free grammar parsers. In particular, we ask if using a “multiple tagger”, a tagger that returns more than one tag, improves parsing performance. Our conclusion is somewhat surprising: single-tag Markov-model taggers are quite adequate for the task. First of all, parsing accuracy, as measured by the correct assignment of parts of speech to words, does not increase significantly when parsers select the tags themselves. In addition, the work required to parse a sentence goes up with increasing tag ambiguity, though not as much as one might expect. Thus, for the moment, single taggers are the best taggers.

AAAI Conference 1996 Conference Paper

Tree-Bank Grammars

• Eugene Charniak

By a “ tree-bank grammar” we mean a context-free grammar created by reading the production rules directly from hand-parsed sentences in a tree bank. Common wisdom has it that such grammars do not perform we& though we know of no published data on the issue. The primary purpose of this paper is to show that the common wisdom is wrong. In particular, we present results on a tree-bank grammar based on the Penn WaII Street Journal tree bank. To the best of our knowledge, this grammar outperforms ah other non-word-based statistical parsers/grammars on this corpus. That is, it outperforms parsers that consider the input as a string of tags and ignore the actual words of the corpus.

AAAI Conference 1994 Conference Paper

Context-Sensitive Statisticsfor Improved Grammatical Language Models

• Eugene Charniak

We develop a language model using probabilistic context-free grammars (PCFGs) that is “pseudo context-sensitive” in that the probability that a nonterminal N expands using a rule T depends on N’ s parent. We give the equations for estimating the necessary probabilities using a variant of the inside-outside algorithm. We give experimental results showing that, beginning with a high-performance PCFG, one can develop a pseudo PCSG that yields significant performance gains. Analysis shows that the benefits from the context-sensitive statistics are localized, suggesting that we can use them to extend the original PCFG. Experimental results confirm that this is both feasible and the resulting grammar retains the performance gains. This implies that our scheme may be useful as a novel method for PCFG induction.

AIJ Journal 1994 Journal Article

Cost-based abduction and MAP explanation

• Eugene Charniak
• Solomon Eyal Shimony

Cost-based abduction attempts to find the best explanation for a set of facts by finding a minimal cost proof for the facts. The costs are computed by summing the costs of the assumptions necessary for the proof plus the cost of the rules. We examine existing methods for constructing explanations (proofs), as a minimization problem on a DAG (directed acyclic graph). We then define a probabilistic semantics for the costs, and prove the equivalence of the cost minimization problem to the Bayesian network MAP (maximum a posteriori probability) solution of the system. A simple best-first algorithm for finding least-cost proofs is presented, and possible improvements are suggested. The semantics of cost-based abduction for complete models are then generalized to handle negation. This, in turn, allows us to apply the best-first search algorithm as a novel way of computing MAP assignments to belief networks that can enumerate assignments in order of decreasing probability. An important point is that improvement results for the best-first search algorithm carry over to the computation of MAPs.

AIJ Journal 1993 Journal Article

A Bayesian model of plan recognition

• Eugene Charniak
• Robert P. Goldman

We argue that the problem of plan recognition, inferring an agent's plan from observations, is largely a problem of inference under conditions of uncertainty. We present an approach to the plan recognition problem that is based on Bayesian probability theory. In attempting to solve a plan recognition problem we first retrieve candidate explanations. These explanations (sometimes only the most promising ones) are assembled into a plan recognition Bayesian network, which is a representation of a probability distribution over the set of possible explanations. We perform Bayesian updating to choose the most likely interpretation for the set of observed actions. This approach has been implemented in the Wimp3 system for natural language story understanding.

AAAI Conference 1993 Conference Paper

Equations for Part-of-Speech Tagging

• Eugene Charniak
• Neil Jacobson

We derive from first principles the basic equations for a few of the basic hidden-Markov-model word taggers as well as equations for other models which may be novel (the descriptions in previous papers being too spare to be sure). We give performance results for all of the models. The results from our best model (96. 45% on an unused test sample from the Brown corpus with 181 distinct tags) is on the upper edge of reported results. We also hope these results clear up some confusion in the literature about the best equations to use. However, the major purpose of this paper is to show how the equations for a variety of models may be derived and thus encourage future authors to give the equations for their model and the derivations thereof.

AAAI Conference 1992 Conference Paper

Dynamic MAP Calculations for Abduction

• Eugene Charniak

We present a dynamic algorithm for MAP calculations. The algorithm is based upon Santos’ s technique (Santos 1991b) of transforming minimal-cost-proof problems into linearprogramming problems. The algorithm is dynamic in the sense that it is able to use the results from an earlier, near by, problem to lessen its search time. Results are presented which clearly suggest that this is a powerful technique for dynamic abduction problems.

AAAI Conference 1991 Conference Paper

A New Admissible Heuristic for Minimal-Cost Proofs

• Eugene Charniak

Finding best explanations is often formalized in AI in terms of minimal-cost proofs. Finding such proofs is naturally characterized as a best-first search of the proof-tree (actually a proof dag). Unfortunately the only known search heuristic for this task is quite poor. In this paper we present a new heuristic, a proof that it is admissible (for certain successor functions), and some experimental results suggesting that it is a significant improvement over the currently used heuristic.

UAI Conference 1991 Conference Paper

A Probabilistic Analysis of Marker-Passing Techniques for Plan-Recognition

• Glenn Carroll
• Eugene Charniak

Useless paths are a chronic problem for marker-passing techniques. We use a probabilistic analysis to justify a method for quickly identifying and rejecting useless paths. Using the same analysis, we identify key conditions and assumptions necessary for marker-passing to perform well.

AAAI Conference 1991 Conference Paper

A Probabilistic Model of Plan Recognition

• Eugene Charniak

Plan-recognition requires the construction of possible plans which could explain a set of observed actions, and then selecting one or more of them as providing the best explanation. In this paper we present a formal model of the latter process based upon probability theory. Our model consists of a knowledge-base of facts about the world expressed in a first-order language, and rules for using that knowledge-base to construct a Bayesian network. The network is then evaluated to find the plans with the highest probability.

UAI Conference 1990 Conference Paper

A new algorithm for finding MAP assignments to belief networks

• Solomon Eyal Shimony
• Eugene Charniak

We present a new algorithm for finding maximum a-posterior) (MAP) assignments of values to belief networks. The belief network is compiled into a network consisting only of nodes with boolean (i.e. only 0 or 1) conditional probabilities. The MAP assignment is then found using a best-first search on the resulting network. We argue that, as one would anticipate, the algorithm is exponential for the general case, but only linear in the size of the network for poly trees.

UAI Conference 1990 Conference Paper

Dynamic construction of belief networks

• Robert P. Goldman
• Eugene Charniak

We describe a method for incrementally constructing belief networks. We have developed a network-construction language similar to a forward-chaining language using data dependencies, but with additional features for specifying distributions. Using this language, we can define parameterized classes of probabilistic models. These parameterized models make it possible to apply probabilistic reasoning to problems for which it is impractical to have a single large static model.

AAAI Conference 1990 Conference Paper

Probabilistic Semantics for Cost Based Abduction

• Eugene Charniak

Cost-based abduction attempts to find the best explanation for a set of facts by finding a minimal cost proof for the facts. The costs are computed by summing the costs of the assumptions necessary for the proof plus the cost of the rules. We examine existing methods for constructing explanations (proofs), as a minimization problem on a DAG. We then define a probabilistic semantics for the costs, and prove the equivalence of the cost minimization problem to the Bayesian network MAP solution of the system.

IJCAI Conference 1989 Conference Paper

A Semantics for Probabilistic Quantifier-Free First-Order Languages, with ParticularApplication to Story Understanding

• Eugene Charniak
• Robert Goldman

We present a semantics for interpreting probabilistic statements expressed in a first-order quantifier-free language. We show how this semantics places constraints on the probabilities which can be associated with such statements. We then consider its use in the area of story understanding. We show that for at least simple models of stories (equivalent to the script/plan models) there arc ways to specify reasonably good probabilities. Lastly, we show that while the semantics dictates seemingly implausibly low prior probabilities for equality statements, once they are conditioned by an assumption of spatio-temporal locality of observation the probabilities become "reasonable. "

UAI Conference 1989 Conference Paper

Plan Recognition in Stories and in Life

• Eugene Charniak
• Robert P. Goldman

Plan recognition does not work the same way in stories and in "real life" (people tend to jump to conclusions more in stories). We present a theory of this, for the particular case of how objects in stories (or in life) influence plan recognition decisions. We provide a Bayesian network formalization of a simple first-order theory of plans, and show how a particular network parameter seems to govern the difference between "life-like" and "story-like" response. We then show why this parameter would be influenced (in the desired way) by a model of speaker (or author) topic selection which assumes that facts in stories are typically "relevant".

AIJ Journal 1988 Journal Article

Motivation analysis, abductive unification, and nonmonotonic equality

• Eugene Charniak

Motivation analysis in story comprehension requires matching an action mentioned in the story against actions which might be predicted by possible explanatory motivations. This requires matching constants from the story against Skolem functions in the possible motivations (assuming a normal first-order representation of stories, plans, etc.). We will show that extending unification to allow for unifying two things if they are nonmonotonically equal does exactly what is needed in such cases. We also show that such a procedure allows for a clean method of noun-phrase reference determination. The work described here has all been implemented.

AAAI Conference 1986 Conference Paper

A Neat Theory of Marker Passing

• Eugene Charniak

We describe here the theory behind the language comprehension program Wimp. Wimp understands by first, finding paths between the open-class words in a sentence using a marker passing, or spreading-activation, technique. This paper is primarily concerned with the “ meaning” (or interpretation) of such paths. We argue that they are best thought of as backbones of proofs that the terms (words) at, either end of the paths exist in the story and show how viewing paths in this way naturally leads to the kinds of inferences which are normally thought to characterize “ understanding. ” In a companion paper we show how this interpretation also accomplishes much of the work normally expected in the parsing of language (noun-phrase reference, word-sense disambiguation, etc) so we only briefly touch on this topic here. Wimp has been implemented and works on all of the examples herein.

AAAI Conference 1983 Conference Paper

The Bayesian Basis of Common Sense Medical Diagnosis

• Eugene Charniak

In the paper, we show that the objections most frequently related against the use of Bayesian statistics within the AI-in-Medicine community do not seem to hold. In particular, we will show that the independence assumptions required to make Bayesian statistics computationally feasiable are not nearly as damaging as has been claimed. We will also argue that Bayesian statistics is perfectly compatible with heuristic solu-tions to the multiple disease problem.

AIJ Journal 1981 Journal Article

A common representation for problem-solving and language-comprehension information

• Eugene Charniak

Many in Artificial Intelligence have noted the common concerns of problem-solving and language-comprehension research. Both must represent large bodies of real world knowledge, and both must use such knowledge to infer new facts from old. Despite this the two subdisciplines have, with minor exceptions, kept arm's length. So, for example, many in language comprehension have adopted some form of ‘frame’ representation, while problem-solving people have tended to use predicate calculus. In this paper I will first show that this is not merely idiosyncratic behavior, but rather stems from the different issues stressed by the two areas, problem solvers being primarily concerned with deep inferences in narrow domains, while language comprehenders being more concerned with shallow inference in broader areas. I will then suggest a compromise position which will use both frames and predicate calculus, and then show how this representation has features desired by both camps.

AIJ Journal 1978 Journal Article

On the use of framed knowledge in language comprehension

• Eugene Charniak

Notions like “frames”, “scripts” etc. are now being used in programs to understand connected discourse. We will describe a program in this vein which understands simple stories about painting. (Jack was painting a chair. He dipped a brush into some paint. Q: Why?) In particular, problems of matching, read time inference, and undoing false conclusions will be stressed. The program makes heavy use of real world knowledge, and there is an extensive discussion of various issues in knowledge representation and how they affect frame representations: modularity, the need for problem solving, worldly vs control knowledge, and cleanliness. The paper concludes with an extensive discussion of the program's shortcomings.

IJCAI Conference 1969 Conference Paper

Computer Solution of Calculus Word Problems.

• Eugene Charniak