acl acl2013 acl2013-190 knowledge-graph by maker-knowledge-mining

190 acl-2013-Implicatures and Nested Beliefs in Approximate Decentralized-POMDPs


Source: pdf

Author: Adam Vogel ; Christopher Potts ; Dan Jurafsky

Abstract: Conversational implicatures involve reasoning about multiply nested belief structures. This complexity poses significant challenges for computational models of conversation and cognition. We show that agents in the multi-agent DecentralizedPOMDP reach implicature-rich interpretations simply as a by-product of the way they reason about each other to maximize joint utility. Our simulations involve a reference game of the sort studied in psychology and linguistics as well as a dynamic, interactional scenario involving implemented artificial agents.

Reference: text


Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 Implicatures and Nested Beliefs in Approximate Decentralized-POMDPs Adam Vogel, Christopher Potts, and Dan Jurafsky Stanford University Stanford, CA, USA , {acvoge l cgpott s Abstract Conversational implicatures involve reasoning about multiply nested belief structures. [sent-1, score-0.51]

2 We show that agents in the multi-agent DecentralizedPOMDP reach implicature-rich interpretations simply as a by-product of the way they reason about each other to maximize joint utility. [sent-3, score-0.302]

3 Our simulations involve a reference game of the sort studied in psychology and linguistics as well as a dynamic, interactional scenario involving implemented artificial agents. [sent-4, score-0.278]

4 1 Introduction , Gricean conversational implicatures (Grice, 1975) are inferences that listeners make in order to reconcile the speaker’s linguistic behavior with the assumption that the speaker is cooperative. [sent-5, score-0.561]

5 As Grice conceived of them, implicatures crucially involve reasoning about multiply-nested belief structures: roughly, for p to count as an implicature, the speaker must believe that the listener will infer that the speaker believes p. [sent-6, score-1.466]

6 This complexity makes implicatures an important testing ground for models of conversation and cognition. [sent-7, score-0.221]

7 Many implicature patterns can be embedded in these games using specific combinations of potential referents and message sets. [sent-9, score-0.385]

8 , 2012) but also for studying children’s pragmatic abilities without implicitly assuming they have mastered challenging linguistic structures (Stiller et al. [sent-14, score-0.064]

9 In this paper, we extend these results beyond simple reference games to full decision-problems in which the agents reason about language and action together over time. [sent-16, score-0.326]

10 To do this, we use the Decentralized Partially Observable Markov Decision Process (Dec-POMDP) to implement agents that are capable of manipulating the multiply-nested belief structures required for implicature calculation. [sent-17, score-0.571]

11 We show that agents in the Dec-POMDP reach implicature-rich interpretations simply as a byproduct of the way they reason about each other to maximize joint utility. [sent-20, score-0.302]

12 Our simulations involve a reference game and a dynamic, interactional scenario involving implemented artificial agents. [sent-21, score-0.278]

13 , 2002) is a multi-agent generalization of the POMDP, where agents act to maximize a shared utility function. [sent-23, score-0.2]

14 S is a finite set of states, A is the set of actions, O is the set of observations, and T(s0|a1 , a2, s) is the transition distribution which dete|ramines what effect the joint action (a1, a2) has on the state of the world. [sent-25, score-0.177]

15 The true state s ∈ S is not observable to twheo agents, ew trhuoe m stautset u sti ∈lize S o isbs neorvta otibosners o ∈ O to, wthehic agh are ,e wmhitote md asftte urt eliazceh o abcsteiorvna according Oto, the observation distribution Ω(o1 , o2 |s0, a). [sent-26, score-0.131]

16 Lastly, b0 ∈ ∆(S) is the initial belief state and 74 Proce dinSgosfi oa,f tB huel 5g1arsita, An Anu gauls Mt 4e-e9ti n2g01 o3f. [sent-28, score-0.232]

17 I wn single-agent POMDPs, agents maintain a belief state b(s) ∈ ∆(S), which aisg a ndtsismt riabiunttiaoinn over sietfat setsa. [sent-32, score-0.432]

18 Agents acting i,n w DheicchPOMDPs must take into account not only their beliefs about the state of the world, but also the beliefs of their partners, leading to nested belief states. [sent-33, score-0.752]

19 In the model presented here, our agent models the other agent’s beliefs about the state of the world, and assumes that the other agent does not take into account our own beliefs, a common approach (Gmytrasiewicz and Doshi, 2005). [sent-34, score-0.458]

20 Agents make decisions according to a policy πi : ∆(S) → A which maximizes the discounted expected reward Pt∞=0γtE[R(st, at1, at2)|b0,π1,π2]. [sent-35, score-0.101]

21 Using tPhe assumption that the )o|tbher agent tracks one less lPevel of belief, we can solve for the other agent’s policy π¯, which allows us to estimate his actions and beliefs over time. [sent-36, score-0.434]

22 Even tracking just one level of nested beliefs quickly leads to a combinatorial explosion in the × number of belief states the other agent might have. [sent-38, score-0.534]

23 To form this single-agent POMDP, we augment the state space to be S S, where the asuecgomnden set oef s tsattaete s pvaacrieab toles b ea Sllow ×s us to mreo tdheel the other agent’s beliefs. [sent-43, score-0.064]

24 We maintain a point estimate b¯ of the other agent’s beliefs, which is formed by summing out observations O that the other player might have received. [sent-44, score-0.114]

25 To accomplish this, we factor the transition distribution into two terms: T((s0, s0) |a, π¯( s¯) , (s, s)) = T¯( s¯0|s0, a, π¯( s¯), (s, s))T(s0|a, π¯( s¯), (s, s)). [sent-45, score-0.073]

26 nto the transition distribution T¯( s¯0|s0, a, π¯( s¯) , (s, s)) : T¯( s¯0| s0, a, π¯( s¯), (s, s)) = Pr( s¯0|s0, a, π¯( s¯), (s, s)) =X? [sent-47, score-0.073]

27 (1) Communication is treated as another type of observation, with messages coming from a finite set M. [sent-49, score-0.078]

28 Each message m ∈ M has the semantics Pr(s|m), hw mhiecshs represents t hMe probability mthaant ttihces wPor(rlsd|m mis) i,n w state s ∈ eSse given eth parto m bisi true. [sent-50, score-0.179]

29 A literal listener, denoted L, interprets messages according to this semantics, without taking into account the beliefs of the speaker. [sent-53, score-0.63]

30 L assumes that the perceptual observations and messages are conditionally independent given the state of the world. [sent-54, score-0.183]

31 Using Bayes’ rule, the literal listener’sjoint observation/message distribution is Pr((o, m) |s, s0, a) = Ω(o|s0, a) Pr(m|s) = Ω(o|s0,a)Pm0Pr(sP|mr(s)|Pmr0()mP)r(m0) (2) The Pr(m) prior ovPer messages can be estimated from corpus data, but we use a uniform prior for simplicity. [sent-55, score-0.357]

32 A literal speaker, denoted S, produces messages according to the most descriptive term: πS(s) = argmaxp(s|m). [sent-56, score-0.328]

33 (3) The literal speaker does not model the beliefs of the listener. [sent-57, score-0.758]

34 To interpret implicatures, a level-one listener, denoted L(S), models the beliefs a literal speaker must have had to produce an utterance: Pr(m|s) = 1 ¯πS(s) = m], where π¯S is the level[ one mlis|ste)n =er’ s1 [e¯ πstimate of the speaker’s policy. [sent-58, score-0.758]

35 Instead, when he solves for the literal speaker’s policy ¯π S, the meaning of a message is the set of beliefs that would lead the literal speaker to produce the utterance. [sent-60, score-1.144]

36 A level-one speaker, S(L), produces utterances to influence a literal listener, and a level-two listener, L(S(L)), uses two levels of belief nesting to interpret utterances as the beliefs that a level-one speaker might have to produce that utterance. [sent-61, score-1.096]

37 Message moustache glasses hat r1 r2 r3 21 21 0 21 21 0 1 0 0 (b) Literal interpretations. [sent-63, score-0.438]

38 Message r1 r3 1 0 0 moustache glasses hat r2 0 1 0 0 0 1 (c) Implicature-rich interpretations. [sent-64, score-0.438]

39 , 2013), augmenting the state space with another copy of the underlying world state space, where the new copy represents the next level ofbelief. [sent-67, score-0.168]

40 For instance, the L(S(L)) agent will make decisions in the S S S space. [sent-68, score-0.08]

41 )F aogre an L(S(L)) es dtaetec (s, s, s), s i sS ×theS t×ruSe state of the world, s is the speaker’s belief of the state of the world, and is the speaker’s belief of the listener’s beliefs. [sent-69, score-0.464]

42 In the next two sections we show how a level-one and level-two listener infer implicatures. [sent-70, score-0.46]

43 1a is the scenario for a reference game of the sort pioneered by Rosenberg and Cohen (1964) and Dale and Reiter (1995). [sent-72, score-0.171]

44 The speaker is assigned a referent ri (hidden from the listener) and produces a message on that basis. [sent-75, score-0.451]

45 The speaker and listener share the goal of having the listener identify the speaker’s intended referent ri. [sent-76, score-1.264]

46 However, the language and scenario facilitate scalar implicature (Horn, 1972; Harnish, 1979; Gazdar, 1979). [sent-81, score-0.347]

47 Briefly, the scalar implicature pattern is that a speaker who is knowledgeable about the relevant domain will choose a communicatively weak utterance U over a communicatively stronger utterance U0 iff U0 is false (assuming U and U0 are relevant). [sent-82, score-0.788]

48 The required sense of communicative strength encompasses logical entailments as well as more particularized pragmatic partial orders (Hirschberg, 1985). [sent-83, score-0.097]

49 In our scenario, ‘hat’ is stronger than ‘glasses’ : the referents wearing a hat are a proper subset of those wearing glasses. [sent-84, score-0.273]

50 Thus, given the players’ goal, if the speaker says ‘glasses’, the listener should draw the scalar implicature that ‘hat’ is false. [sent-85, score-1.044]

51 Similarly, though ‘moustache’ and ‘glasses’ do not literally stand in the specific–general relationship needed for scalar implicature, they do with ‘glasses’ pragmatically associated with r2 (Fig. [sent-88, score-0.107]

52 The state space S encodes the attributes of the referents (e. [sent-91, score-0.125]

53 , hat(r2) = T, glasses(r1) = F) and includes a target variable t identifying the speaker’s referent (hidden from the listener). [sent-93, score-0.07]

54 The speaker has three speech actions, identified with the three messages. [sent-94, score-0.274]

55 The listener has four actions: ‘listen’ plus a ‘choose’ action ci for each referent ri. [sent-95, score-0.57]

56 The set of observations O is just the set of messages (construed as utterances). [sent-96, score-0.119]

57 The agents receive a positive reward iff the listener action ci corresponds to the speaker’s target t. [sent-97, score-0.737]

58 Because this is a one-step reference game, the transition distribution T is the identity distribution. [sent-98, score-0.11]

59 The literal listener L interprets utterances as a truth-conditional speaker would produce them (Fig. [sent-99, score-1.122]

60 The level-one speaker S(L) augments the state space with a variable ‘listener target’ and models L’s beliefs b¯ using the approximate methods of Sec. [sent-101, score-0.572]

61 Crucially, the optimal speaker policy πS(L) is such that πS(L) (t=r3) = ‘hat’ and πS(L)(t=r1) = ‘moustache’ . [sent-103, score-0.338]

62 The level-two listener L(S(L)) models S(L) via an estimate of the ‘listener target’ variable. [sent-104, score-0.46]

63 , 2004; Franke, 2009), and a ‘soft-max’ view of the listener (Frank et al. [sent-111, score-0.46]

64 The world is a simple maze in which a deck of cards has been distributed. [sent-114, score-0.193]

65 The state space S is composed of the location of each player and the location of the card. [sent-124, score-0.233]

66 The transition distribution T(s0 |s, a1, a2) encodes the outcome of movement actio|nss,. [sent-125, score-0.073]

67 The players are rewarded when they are both located on the card. [sent-127, score-0.058]

68 Each player begins knowing his own location, but not the location of the other player nor of the card. [sent-128, score-0.194]

69 The players have four movement actions (‘up’, ‘down’, ‘left’, ‘right’) and nine speech actions in- terpreted as identifying card locations. [sent-129, score-0.216]

70 2 depicts these utterances as a partial order determined by entailment. [sent-131, score-0.07]

71 net top right top left bottom right bottom left , \ ,\ , SS S S ! [sent-134, score-0.57]

72 " top right left bottom middle Figure 2: Cards world utterance actions. [sent-142, score-0.439]

73 42) Figure 3: Literal interpretations derived from the Cards corpus. [sent-152, score-0.102]

74 Each term is estimated from all tokens that contain it, which washes out implicature-rich usage, thereby providing our model with an empirically-grounded literal start. [sent-154, score-0.292]

75 ships show that the language can support scalar conversational implicatures. [sent-155, score-0.136]

76 To model this vagueness, we analyze each message m as denoting a conditional distribution Pr(x|m) over grid squares x idnit itohnea gameboard. [sent-161, score-0.101]

77 Of course, there is a tension here: our model assumes that we begin with literal interpretations, but human–human data will reflect pragmaticallyenriched usage. [sent-163, score-0.25]

78 To get around this, we approximate literal interpretations by deriving each term’s distribution from all the corpus tokens that contain it. [sent-164, score-0.381]

79 For example, the distribution for ‘top’ is 2Our agents cannot produce modified versions of ‘middle’ like ‘middle right’ . [sent-165, score-0.229]

80 04) Figure 4: Implicature-rich interpretations, derived using the level-one listener L(S). [sent-177, score-0.46]

81 The denotation for ‘top right’ excludes simple ‘top’ and ‘right’ utterances but includes expressions like ‘very top right’ . [sent-179, score-0.134]

82 This semantics washes out any implicature patterns, thereby giving us a proper literal starting point. [sent-180, score-0.538]

83 To show how the Dec-POMDP model delivers implicatures, we begin with a literal speaker S who does not consider the location of the other player and instead searches the board until he finds the card. [sent-186, score-0.645]

84 After finding it, he communicates the referring expression with highest literal probability for his location, using the distributions from Fig. [sent-187, score-0.293]

85 The level-one listener L(S) tracks an estimate of S’s location and beliefs about the card location. [sent-190, score-0.788]

86 2, L(S) interprets an utterance m as Pr(m|s) = 1π¯S (s) = m] . [sent-192, score-0.133]

87 [ Thus, nth uet meaning aofs Pear(cmh m i=s 1th[¯e π set of beliefs that S might have to produce this utterance. [sent-193, score-0.234]

88 44) Figure 5: Distributions reflecting human speakers’ aggregate referential intentions . [sent-208, score-0.107]

89 listener interpretations to align with speaker intentions, and we can gain insight into (aggregate) speaker intentions using our method for grounding referential terms. [sent-210, score-1.217]

90 Whereas the literal interpretation for message m is obtained from all the tokens that contain it (Fig. [sent-211, score-0.322]

91 Thus, the L(S) model correctly infers the pragmatic meaning of referring expressions as used by human speakers, albeit in an idealized manner. [sent-217, score-0.141]

92 5 Future Work We showed that implicatures arise in cooperative contexts from nested belief models. [sent-218, score-0.441]

93 Our listenercentric implicatures must be combined with ratio- nal speaker behavior (Vogel et al. [sent-219, score-0.495]

94 The computational complexity of Dec-POMDPs is prohibitive, and our approximations can be problematic for deep belief nesting. [sent-221, score-0.168]

95 Future work will explore samplingbased approaches to belief update and decision making (Doshi and Gmytrasiewicz, 2009) to overcome these problems. [sent-222, score-0.206]

96 These steps will move us closer to a computationally effective, unified theory of pragmatic enrichment and decision making. [sent-223, score-0.102]

97 That’s what she (could have) said: How alternative utterances affect language use. [sent-228, score-0.07]

98 The complexity of decentralized control of Markov decision processes. [sent-233, score-0.093]

99 Computational interpretations of the Gricean maxims in the generation of referring expressions. [sent-253, score-0.182]

100 Using speakers’ referential intentions to model early cross-situational word learning. [sent-283, score-0.107]


similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('listener', 0.46), ('speaker', 0.274), ('literal', 0.25), ('beliefs', 0.234), ('implicatures', 0.221), ('implicature', 0.203), ('agents', 0.2), ('glasses', 0.185), ('belief', 0.168), ('cards', 0.153), ('hat', 0.128), ('moustache', 0.125), ('scalar', 0.107), ('interpretations', 0.102), ('game', 0.097), ('pr', 0.093), ('bottom', 0.089), ('vogel', 0.082), ('right', 0.081), ('agent', 0.08), ('messages', 0.078), ('player', 0.073), ('message', 0.072), ('referent', 0.07), ('utterances', 0.07), ('goodman', 0.068), ('interprets', 0.068), ('utterance', 0.065), ('state', 0.064), ('pragmatic', 0.064), ('policy', 0.064), ('top', 0.064), ('ager', 0.063), ('doshi', 0.063), ('franke', 0.063), ('gmytrasiewicz', 0.063), ('gricean', 0.063), ('maienborn', 0.063), ('referents', 0.061), ('players', 0.058), ('actions', 0.056), ('stiller', 0.055), ('rosenberg', 0.055), ('decentralized', 0.055), ('pomdp', 0.055), ('frank', 0.055), ('intentions', 0.054), ('referential', 0.053), ('nested', 0.052), ('bernstein', 0.051), ('left', 0.051), ('middle', 0.049), ('games', 0.049), ('location', 0.048), ('card', 0.046), ('transition', 0.044), ('semantics', 0.043), ('referring', 0.043), ('camerer', 0.042), ('degen', 0.042), ('golland', 0.042), ('interactional', 0.042), ('nexp', 0.042), ('prashant', 0.042), ('spaan', 0.042), ('washes', 0.042), ('wearing', 0.042), ('observations', 0.041), ('action', 0.04), ('pragmatics', 0.04), ('world', 0.04), ('observable', 0.038), ('reasoning', 0.038), ('decision', 0.038), ('scenario', 0.037), ('krahmer', 0.037), ('grice', 0.037), ('maxims', 0.037), ('communicatively', 0.037), ('rohde', 0.037), ('devault', 0.037), ('listeners', 0.037), ('perseus', 0.037), ('piotr', 0.037), ('reference', 0.037), ('reward', 0.037), ('speakers', 0.035), ('ri', 0.035), ('simulations', 0.034), ('bergen', 0.034), ('denotations', 0.034), ('idealized', 0.034), ('dale', 0.034), ('gerhard', 0.033), ('logical', 0.033), ('involve', 0.031), ('nesting', 0.03), ('distribution', 0.029), ('noah', 0.029), ('conversational', 0.029)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0 190 acl-2013-Implicatures and Nested Beliefs in Approximate Decentralized-POMDPs

Author: Adam Vogel ; Christopher Potts ; Dan Jurafsky

Abstract: Conversational implicatures involve reasoning about multiply nested belief structures. This complexity poses significant challenges for computational models of conversation and cognition. We show that agents in the multi-agent DecentralizedPOMDP reach implicature-rich interpretations simply as a by-product of the way they reason about each other to maximize joint utility. Our simulations involve a reference game of the sort studied in psychology and linguistics as well as a dynamic, interactional scenario involving implemented artificial agents.

2 0.20898114 184 acl-2013-Identification of Speakers in Novels

Author: Hua He ; Denilson Barbosa ; Grzegorz Kondrak

Abstract: Speaker identification is the task of at- tributing utterances to characters in a literary narrative. It is challenging to auto- mate because the speakers of the majority ofutterances are not explicitly identified in novels. In this paper, we present a supervised machine learning approach for the task that incorporates several novel features. The experimental results show that our method is more accurate and general than previous approaches to the problem.

3 0.090875879 116 acl-2013-Detecting Metaphor by Contextual Analogy

Author: Eirini Florou

Abstract: As one of the most challenging issues in NLP, metaphor identification and its interpretation have seen many models and methods proposed. This paper presents a study on metaphor identification based on the semantic similarity between literal and non literal meanings of words that can appear at the same context.

4 0.069315307 382 acl-2013-Variational Inference for Structured NLP Models

Author: David Burkett ; Dan Klein

Abstract: unkown-abstract

5 0.067366235 118 acl-2013-Development and Analysis of NLP Pipelines in Argo

Author: Rafal Rak ; Andrew Rowley ; Jacob Carter ; Sophia Ananiadou

Abstract: Developing sophisticated NLP pipelines composed of multiple processing tools and components available through different providers may pose a challenge in terms of their interoperability. The Unstructured Information Management Architecture (UIMA) is an industry standard whose aim is to ensure such interoperability by defining common data structures and interfaces. The architecture has been gaining attention from industry and academia alike, resulting in a large volume ofUIMA-compliant processing components. In this paper, we demonstrate Argo, a Web-based workbench for the development and processing of NLP pipelines/workflows. The workbench is based upon UIMA, and thus has the potential of using many of the existing UIMA resources. We present features, and show examples, offacilitating the distributed development of components and the analysis of processing results. The latter includes annotation visualisers and editors, as well as serialisation to RDF format, which enables flexible querying in addition to data manipulation thanks to the semantic query language SPARQL. The distributed development feature allows users to seamlessly connect their tools to workflows running in Argo, and thus take advantage of both the available library of components (without the need of installing them locally) and the analytical tools.

6 0.067186996 53 acl-2013-Annotation of regular polysemy and underspecification

7 0.05279173 86 acl-2013-Combining Referring Expression Generation and Surface Realization: A Corpus-Based Investigation of Architectures

8 0.052438311 238 acl-2013-Measuring semantic content in distributional vectors

9 0.049643371 49 acl-2013-An annotated corpus of quoted opinions in news articles

10 0.04773796 282 acl-2013-Predicting and Eliciting Addressee's Emotion in Online Dialogue

11 0.047159422 239 acl-2013-Meet EDGAR, a tutoring agent at MONSERRATE

12 0.044367235 197 acl-2013-Incremental Topic-Based Translation Model Adaptation for Conversational Spoken Language Translation

13 0.044106495 230 acl-2013-Lightly Supervised Learning of Procedural Dialog Systems

14 0.043549977 379 acl-2013-Utterance-Level Multimodal Sentiment Analysis

15 0.042166963 124 acl-2013-Discriminative state tracking for spoken dialog systems

16 0.039968602 155 acl-2013-Fast and Accurate Shift-Reduce Constituent Parsing

17 0.039880771 240 acl-2013-Microblogs as Parallel Corpora

18 0.039431699 90 acl-2013-Conditional Random Fields for Responsive Surface Realisation using Global Features

19 0.03889136 121 acl-2013-Discovering User Interactions in Ideological Discussions

20 0.038851924 212 acl-2013-Language-Independent Discriminative Parsing of Temporal Expressions


similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.105), (1, 0.024), (2, -0.019), (3, -0.027), (4, -0.032), (5, -0.025), (6, 0.047), (7, 0.002), (8, 0.008), (9, 0.019), (10, -0.066), (11, 0.017), (12, -0.041), (13, -0.031), (14, -0.011), (15, -0.049), (16, -0.049), (17, 0.064), (18, 0.032), (19, -0.073), (20, -0.108), (21, -0.102), (22, 0.073), (23, -0.013), (24, 0.009), (25, 0.034), (26, -0.005), (27, 0.044), (28, 0.045), (29, 0.013), (30, 0.054), (31, -0.058), (32, 0.005), (33, 0.035), (34, 0.005), (35, 0.042), (36, 0.097), (37, 0.017), (38, -0.006), (39, 0.085), (40, -0.002), (41, 0.046), (42, 0.015), (43, 0.063), (44, 0.035), (45, 0.083), (46, 0.121), (47, -0.036), (48, 0.011), (49, -0.16)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.95281196 190 acl-2013-Implicatures and Nested Beliefs in Approximate Decentralized-POMDPs

Author: Adam Vogel ; Christopher Potts ; Dan Jurafsky

Abstract: Conversational implicatures involve reasoning about multiply nested belief structures. This complexity poses significant challenges for computational models of conversation and cognition. We show that agents in the multi-agent DecentralizedPOMDP reach implicature-rich interpretations simply as a by-product of the way they reason about each other to maximize joint utility. Our simulations involve a reference game of the sort studied in psychology and linguistics as well as a dynamic, interactional scenario involving implemented artificial agents.

2 0.78551197 184 acl-2013-Identification of Speakers in Novels

Author: Hua He ; Denilson Barbosa ; Grzegorz Kondrak

Abstract: Speaker identification is the task of at- tributing utterances to characters in a literary narrative. It is challenging to auto- mate because the speakers of the majority ofutterances are not explicitly identified in novels. In this paper, we present a supervised machine learning approach for the task that incorporates several novel features. The experimental results show that our method is more accurate and general than previous approaches to the problem.

3 0.6014834 90 acl-2013-Conditional Random Fields for Responsive Surface Realisation using Global Features

Author: Nina Dethlefs ; Helen Hastie ; Heriberto Cuayahuitl ; Oliver Lemon

Abstract: Surface realisers in spoken dialogue systems need to be more responsive than conventional surface realisers. They need to be sensitive to the utterance context as well as robust to partial or changing generator inputs. We formulate surface realisation as a sequence labelling task and combine the use of conditional random fields (CRFs) with semantic trees. Due to their extended notion of context, CRFs are able to take the global utterance context into account and are less constrained by local features than other realisers. This leads to more natural and less repetitive surface realisation. It also allows generation from partial and modified inputs and is therefore applicable to incremental surface realisation. Results from a human rating study confirm that users are sensitive to this extended notion of context and assign ratings that are significantly higher (up to 14%) than those for taking only local context into account.

4 0.60125929 203 acl-2013-Is word-to-phone mapping better than phone-phone mapping for handling English words?

Author: Naresh Kumar Elluru ; Anandaswarup Vadapalli ; Raghavendra Elluru ; Hema Murthy ; Kishore Prahallad

Abstract: In this paper, we relook at the problem of pronunciation of English words using native phone set. Specifically, we investigate methods of pronouncing English words using Telugu phoneset in the con- text of Telugu Text-to-Speech. We compare phone-phone substitution and wordphone mapping for pronunciation of English words using Telugu phones. We are not considering other than native language phoneset in all our experiments. This differentiates our approach from other works in polyglot speech synthesis.

5 0.53094715 239 acl-2013-Meet EDGAR, a tutoring agent at MONSERRATE

Author: Pedro Fialho ; Luisa Coheur ; Sergio Curto ; Pedro Claudio ; Angela Costa ; Alberto Abad ; Hugo Meinedo ; Isabel Trancoso

Abstract: In this paper we describe a platform for embodied conversational agents with tutoring goals, which takes as input written and spoken questions and outputs answers in both forms. The platform is developed within a game environment, and currently allows speech recognition and synthesis in Portuguese, English and Spanish. In this paper we focus on its understanding component that supports in-domain interactions, and also small talk. Most indomain interactions are answered using different similarity metrics, which compare the perceived utterances with questions/sentences in the agent’s knowledge base; small-talk capabilities are mainly due to AIML, a language largely used by the chatbots’ community. In this paper we also introduce EDGAR, the butler of MONSERRATE, which was developed in the aforementioned platform, and that answers tourists’ questions about MONSERRATE.

6 0.50897276 141 acl-2013-Evaluating a City Exploration Dialogue System with Integrated Question-Answering and Pedestrian Navigation

7 0.49208701 337 acl-2013-Tag2Blog: Narrative Generation from Satellite Tag Data

8 0.48853889 30 acl-2013-A computational approach to politeness with application to social factors

9 0.46961093 86 acl-2013-Combining Referring Expression Generation and Surface Realization: A Corpus-Based Investigation of Architectures

10 0.45732906 36 acl-2013-Adapting Discriminative Reranking to Grounded Language Learning

11 0.45137033 321 acl-2013-Sign Language Lexical Recognition With Propositional Dynamic Logic

12 0.43210736 311 acl-2013-Semantic Neighborhoods as Hypergraphs

13 0.43010795 282 acl-2013-Predicting and Eliciting Addressee's Emotion in Online Dialogue

14 0.42625439 302 acl-2013-Robust Automated Natural Language Processing with Multiword Expressions and Collocations

15 0.42568186 364 acl-2013-Typesetting for Improved Readability using Lexical and Syntactic Information

16 0.39365643 382 acl-2013-Variational Inference for Structured NLP Models

17 0.38765806 175 acl-2013-Grounded Language Learning from Video Described with Sentences

18 0.38189697 63 acl-2013-Automatic detection of deception in child-produced speech using syntactic complexity features

19 0.37836313 161 acl-2013-Fluid Construction Grammar for Historical and Evolutionary Linguistics

20 0.37500179 1 acl-2013-"Let Everything Turn Well in Your Wife": Generation of Adult Humor Using Lexical Constraints


similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.049), (6, 0.04), (11, 0.064), (15, 0.026), (24, 0.067), (26, 0.039), (35, 0.062), (42, 0.05), (48, 0.035), (56, 0.342), (64, 0.016), (70, 0.045), (88, 0.033), (90, 0.023), (95, 0.036)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.83237714 108 acl-2013-Decipherment

Author: Kevin Knight

Abstract: The first natural language processing systems had a straightforward goal: decipher coded messages sent by the enemy. This tutorial explores connections between early decipherment research and today’s NLP work. We cover classic military and diplomatic ciphers, automatic decipherment algorithms, unsolved ciphers, language translation as decipherment, and analyzing ancient writing as decipherment. 1 Tutorial Overview The first natural language processing systems had a straightforward goal: decipher coded messages sent by the enemy. Sixty years later, we have many more applications, including web search, question answering, summarization, speech recognition, and language translation. This tutorial explores connections between early decipherment research and today’s NLP work. We find that many ideas from the earlier era have become core to the field, while others still remain to be picked up and developed. We first cover classic military and diplomatic cipher types, including complex substitution ciphers implemented in the first electro-mechanical encryption machines. We look at mathematical tools (language recognition, frequency counting, smoothing) developed to decrypt such ciphers on proto-computers. We show algorithms and extensive empirical results for solving different types of ciphers, and we show the role of algorithms in recent decipherments of historical documents. We then look at how foreign language can be viewed as a code for English, a concept developed by Alan Turing and Warren Weaver. We describe recently published work on building automatic translation systems from non-parallel data. We also demonstrate how some of the same algorithmic tools can be applied to natural language tasks like part-of-speech tagging and word alignment. Turning back to historical ciphers, we explore a number of unsolved ciphers, giving results of initial computer experiments on several of them. Finally, we look briefly at writing as a way to encipher phoneme sequences, covering ancient scripts and modern applications. 2 Outline 1. Classical military/diplomatic ciphers (15 minutes) • 60 cipher types (ACA) • Ciphers vs. codes • Enigma cipher: the mother of natural language processing computer analysis of text language recognition Good-Turing smoothing – – – 2. Foreign language as a code (10 minutes) • • Alan Turing’s ”Thinking Machines” Warren Weaver’s Memorandum 3. Automatic decipherment (55 minutes) • Cipher type detection • Substitution ciphers (simple, homophonic, polyalphabetic, etc) plaintext language recognition ∗ how much plaintext knowledge is – nheowede mdu 3 Proce diSnogfsia, of B thuleg5a r1iast, A Anungu aslt M4-9e t2in01g3 o.f ? tc he20 A1s3so Acsiasoticoinat fio rn C fo rm Cpoumtaptuiotantaioln Lainlg Luinisgtuicis ,tpi casges 3–4, – ∗ index of coincidence, unicity distance, oanf dc oointhceidr measures navigating a difficult search space ∗ frequencies of letters and words ∗ pattern words and cribs ∗ pElMin,g ILP, Bayesian models, sam– recent decipherments ∗ Jefferson cipher, Copiale cipher, cJievfifle war ciphers, n Caovaplia Enigma • • • • Application to part-of-speech tagging, Awopprdli alignment Application to machine translation withoAuptp parallel t teoxtm Parallel development of cryptography aPnarda ltrleanls dlaetvioenlo Recently released NSA internal nReewcselnettlyter (1974-1997) 4. *** Break *** (30 minutes) 5. Unsolved ciphers (40 minutes) • Zodiac 340 (1969), including computatZioodnaial cw 3o4r0k • Voynich Manuscript (early 1400s), including computational ewarolyrk • Beale (1885) • Dorabella (1897) • Taman Shud (1948) • Kryptos (1990), including computatKiorynaplt owsor (k1 • McCormick (1999) • Shoeboxes in attics: DuPonceau jour- nal, Finnerana, SYP, Mopse, diptych 6. Writing as a code (20 minutes) • Does writing encode ideas, or does it encDoodees phonemes? • Ancient script decipherment Egyptian hieroglyphs Linear B Mayan glyphs – – – – wUgoarkritic, including computational Chinese N ¨ushu, including computational work • Automatic phonetic decipherment • Application to transliteration 7. Undeciphered writing systems (15 minutes) • Indus Valley Script (3300BC) • Linear A (1900BC) • Phaistos disc (1700BC?) • Rongorongo (1800s?) – 8. Conclusion and further questions (15 minutes) 3 About the Presenter Kevin Knight is a Senior Research Scientist and Fellow at the Information Sciences Institute of the University of Southern California (USC), and a Research Professor in USC’s Computer Science Department. He received a PhD in computer science from Carnegie Mellon University and a bachelor’s degree from Harvard University. Professor Knight’s research interests include natural language processing, machine translation, automata theory, and decipherment. In 2001, he co-founded Language Weaver, Inc., and in 2011, he served as President of the Association for Computational Linguistics. Dr. Knight has taught computer science courses at USC for more than fifteen years and co-authored the widely adopted textbook Artificial Intelligence. 4

same-paper 2 0.83048356 190 acl-2013-Implicatures and Nested Beliefs in Approximate Decentralized-POMDPs

Author: Adam Vogel ; Christopher Potts ; Dan Jurafsky

Abstract: Conversational implicatures involve reasoning about multiply nested belief structures. This complexity poses significant challenges for computational models of conversation and cognition. We show that agents in the multi-agent DecentralizedPOMDP reach implicature-rich interpretations simply as a by-product of the way they reason about each other to maximize joint utility. Our simulations involve a reference game of the sort studied in psychology and linguistics as well as a dynamic, interactional scenario involving implemented artificial agents.

3 0.69102931 65 acl-2013-BRAINSUP: Brainstorming Support for Creative Sentence Generation

Author: Gozde Ozbal ; Daniele Pighin ; Carlo Strapparava

Abstract: Daniele Pighin Google Inc. Z ¨urich, Switzerland danie le . pighin@ gmai l com . Carlo Strapparava FBK-irst Trento, Italy st rappa@ fbk . eu you”. As another scenario, creative sentence genWe present BRAINSUP, an extensible framework for the generation of creative sentences in which users are able to force several words to appear in the sentences and to control the generation process across several semantic dimensions, namely emotions, colors, domain relatedness and phonetic properties. We evaluate its performance on a creative sentence generation task, showing its capability of generating well-formed, catchy and effective sentences that have all the good qualities of slogans produced by human copywriters.

4 0.65822816 178 acl-2013-HEADY: News headline abstraction through event pattern clustering

Author: Enrique Alfonseca ; Daniele Pighin ; Guillermo Garrido

Abstract: This paper presents HEADY: a novel, abstractive approach for headline generation from news collections. From a web-scale corpus of English news, we mine syntactic patterns that a Noisy-OR model generalizes into event descriptions. At inference time, we query the model with the patterns observed in an unseen news collection, identify the event that better captures the gist of the collection and retrieve the most appropriate pattern to generate a headline. HEADY improves over a state-of-theart open-domain title abstraction method, bridging half of the gap that separates it from extractive methods using humangenerated titles in manual evaluations, and performs comparably to human-generated headlines as evaluated with ROUGE.

5 0.63306791 258 acl-2013-Neighbors Help: Bilingual Unsupervised WSD Using Context

Author: Sudha Bhingardive ; Samiulla Shaikh ; Pushpak Bhattacharyya

Abstract: Word Sense Disambiguation (WSD) is one of the toughest problems in NLP, and in WSD, verb disambiguation has proved to be extremely difficult, because of high degree of polysemy, too fine grained senses, absence of deep verb hierarchy and low inter annotator agreement in verb sense annotation. Unsupervised WSD has received widespread attention, but has performed poorly, specially on verbs. Recently an unsupervised bilingual EM based algorithm has been proposed, which makes use only of the raw counts of the translations in comparable corpora (Marathi and Hindi). But the performance of this approach is poor on verbs with accuracy level at 25-38%. We suggest a modifica- tion to this mentioned formulation, using context and semantic relatedness of neighboring words. An improvement of 17% 35% in the accuracy of verb WSD is obtained compared to the existing EM based approach. On a general note, the work can be looked upon as contributing to the framework of unsupervised WSD through context aware expectation maximization.

6 0.41154268 83 acl-2013-Collective Annotation of Linguistic Resources: Basic Principles and a Formal Model

7 0.41018716 318 acl-2013-Sentiment Relevance

8 0.40761468 85 acl-2013-Combining Intra- and Multi-sentential Rhetorical Parsing for Document-level Discourse Analysis

9 0.40526021 99 acl-2013-Crowd Prefers the Middle Path: A New IAA Metric for Crowdsourcing Reveals Turker Biases in Query Segmentation

10 0.40503296 169 acl-2013-Generating Synthetic Comparable Questions for News Articles

11 0.40408722 123 acl-2013-Discriminative Learning with Natural Annotations: Word Segmentation as a Case Study

12 0.40361866 2 acl-2013-A Bayesian Model for Joint Unsupervised Induction of Sentiment, Aspect and Discourse Representations

13 0.40268308 225 acl-2013-Learning to Order Natural Language Texts

14 0.40262946 185 acl-2013-Identifying Bad Semantic Neighbors for Improving Distributional Thesauri

15 0.40104842 82 acl-2013-Co-regularizing character-based and word-based models for semi-supervised Chinese word segmentation

16 0.40018392 224 acl-2013-Learning to Extract International Relations from Political Context

17 0.39969179 183 acl-2013-ICARUS - An Extensible Graphical Search Tool for Dependency Treebanks

18 0.39932895 272 acl-2013-Paraphrase-Driven Learning for Open Question Answering

19 0.39926514 56 acl-2013-Argument Inference from Relevant Event Mentions in Chinese Argument Extraction

20 0.39850524 367 acl-2013-Universal Conceptual Cognitive Annotation (UCCA)