acl acl2012 acl2012-79 knowledge-graph by maker-knowledge-mining

79 acl-2012-Efficient Tree-Based Topic Modeling

Source: pdf

Author: Yuening Hu ; Jordan Boyd-Graber

Abstract: Topic modeling with a tree-based prior has been used for a variety of applications because it can encode correlations between words that traditional topic modeling cannot. However, its expressive power comes at the cost of more complicated inference. We extend the SPARSELDA (Yao et al., 2009) inference scheme for latent Dirichlet allocation (LDA) to tree-based topic models. This sampling scheme computes the exact conditional distribution for Gibbs sampling much more quickly than enumerating all possible latent variable assignments. We further improve performance by iteratively refining the sampling distribution only when needed. Experiments show that the proposed techniques dramatically improve the computation time.

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract Topic modeling with a tree-based prior has been used for a variety of applications because it can encode correlations between words that traditional topic modeling cannot. [sent-3, score-0.521]

2 , 2009) inference scheme for latent Dirichlet allocation (LDA) to tree-based topic models. [sent-6, score-0.392]

3 This sampling scheme computes the exact conditional distribution for Gibbs sampling much more quickly than enumerating all possible latent variable assignments. [sent-7, score-0.554]

4 We further improve performance by iteratively refining the sampling distribution only when needed. [sent-8, score-0.215]

5 Experiments show that the proposed techniques dramatically improve the computation time. [sent-9, score-0.048]

6 1 Introduction Topic models, exemplified by latent Dirichlet allocation (LDA) (Blei et al. [sent-10, score-0.063]

7 “Topics” discovered by topic models are multinomial probability distributions over words that evince thematic coherence. [sent-12, score-0.374]

8 One of LDA’s virtues is that it is a simple model that assumes a symmetric Dirichlet prior over its word distributions. [sent-14, score-0.04]

9 Recent work argues for structured distributions that constrain clusters (Andrzejewski et al. [sent-15, score-0.055]

10 , 2011) to improve the quality and flexibility of topic modeling. [sent-17, score-0.281]

11 These models all use different tree-based prior distributions (Section 2). [sent-18, score-0.095]

12 These approaches are appealing because they preserve conjugacy, making inference using Gibbs sampling (Heinrich, 2004) straightforward. [sent-19, score-0.233]

13 , 2009) is an efficient Gibbs sampling algorithm for LDA based on a refactorization of the conditional topic distribution (reviewed in Section 3). [sent-26, score-0.566]

14 In Section 4, we provide a factorization for tree-based models within a broadly applicable inference framework that empirically improves the efficiency of inference (Section 5). [sent-28, score-0.096]

15 Abney and Light (1999) used treestructured multinomials to model selectional restrictions, which was later put into a Bayesian context for topic modeling (Boyd-Graber et al. [sent-30, score-0.281]

16 In both cases, the tree came from WordNet (Miller, 1990), but the tree could also come from domain experts (Andrzejewski et al. [sent-32, score-0.064]

17 Organizing words in this way induces correlations that are mathematically impossible to represent with a symmetric Dirichlet prior. [sent-34, score-0.158]

18 To see how correlations can occur, consider the generative process. [sent-35, score-0.158]

19 Start with a rooted tree structure that contains internal nodes and leaf nodes. [sent-36, score-0.11]

20 This skeleton is a prior that generates K topics. [sent-37, score-0.04]

21 Like vanilla LDA, these topics are distributions over words. [sent-38, score-0.26]

22 Internal nodes have a distribution πk,i over children, where πk,i comes from per-node Dirichlet parameterized by βi. [sent-40, score-0.03]

23 1 Each leaf node is associated with a word, and each word must appear in at least (possibly more than) one leaf node. [sent-41, score-0.156]

24 To generate a word from topic k, start at the root. [sent-42, score-0.281]

25 Select a child x0 ∼ Mult(πk,ROOT), and traverse the tree until reaching a lt(eπaf node. [sent-43, score-0.032]

26 This walk replaces the draw from a topic’s multinomial distribution over words. [sent-45, score-0.068]

27 , positive or negative) and strength of correlations that appear. [sent-48, score-0.158]

28 c so2c0ia1t2io Ans fso rc Ciatoiomnp fuotart Cio nmaplu Ltiantgiounisatlic Lsi,n pgaugiestsi2c 7s5–279, The rest of the generative process for LDA remains the same, with θ, the per-document topic multinomial, and z, the topic assignment. [sent-51, score-0.562]

29 The closer types are in the tree, the more correlated they are. [sent-53, score-0.038]

30 Because types can appear in multiple leaf nodes, this encodes polysemy. [sent-54, score-0.078]

31 The path that generates a token is an additional latent variable we must sample. [sent-55, score-0.322]

32 Gibbs sampling is straightforward because the treebased prior maintains conjugacy (Andrzejewski et al. [sent-56, score-0.336]

33 We integrate the per-document topic distributions θ and the transition distributions π. [sent-58, score-0.391]

34 The complexity of computing the sampling distri- bution is O(KLS) for models with K topics, paths at most L nodes long, and at most S paths per word type. [sent-60, score-0.547]

35 In contrast, for vanilla LDA the analogous conditional sampling distribution requires O(K). [sent-61, score-0.341]

36 A bucket is the total probability mass marginaliPzing over latent variable assignments (i. [sent-64, score-0.69]

37 The Pthree buckets are a smoothing only bucket βVα +kβn·|k, 2For clarity, we omit indicators that ensure λ ends at wd,n. [sent-67, score-0.683]

38 3To ease notation we drop the subscript for z and w in this and future equations. [sent-68, score-0.04]

39 d,n 276 sLDA, document topic bucket rLDA, and topic word bucket qLDA (we use the “LDA” subscript to contrast with our method, for which we use the same bucket names without subscripts). [sent-69, score-2.064]

40 Caching the buckets’ total mass speeds the computation of the sampling distribution. [sent-70, score-0.349]

41 Bucket sLDA is shared by all tokens, and bucket rLDA is shared by a document’s tokens. [sent-71, score-0.538]

42 To sample from the conditional distribution, first sample which bucket you need and then (and only then) select a topic within that bucket. [sent-74, score-0.972]

43 Because the topic-term bucket qLDA often has the largest mass and has few non-zero terms, this speeds inference. [sent-75, score-0.588]

44 4 Efficient Inference in Tree-Based Models In this section, we extend the sampling techniques for SPARSELDA to tree-based topic modeling. [sent-76, score-0.466]

45 Henceforth we call Nk,λ the normalizer for path λ in topic k, Sλ the smoothing factor for path λ, and Ok,λ the observation for path λ in topic k, which are Nk,λ = Y X(βi→j0 + ni→j0|k) (i→Yj) ∈λ Xj0 Sλ = Y βi→j (4) (i→Yj) ∈λ Ok,λ = Y (βi→j + ni→j|k) (i→Yj) ∈λ − Y βi→j. [sent-78, score-1.359]

46 (i→Yj) ∈λ Equation 3 can be rearranged in the same way as Equation 5, yielding buckets analogous to SPARSELDA’s, p(z = k,l = λ|Z− , L−, w) (5) ∝αNkkS,λλ+nNk|kdS,λλ+(αk+N nkk,|λd)Ok,λ. [sent-79, score-0.212]

47 T{hze samp}ling process is much the same as for SPARSELDA: select which bucket and then select a topic / path combination within the bucket (for a slightly more complex example, see Algorithm 1). [sent-81, score-1.453]

48 Recall that one of the benefits of SPARSELDA was that s was shared across tokens. [sent-82, score-0.081]

49 This is no longer possible, as Nk,λ is distinct for each path in treebased LDA. [sent-83, score-0.287]

50 Moreover, Nk,λ is coupled; changing ni→j|k in one path changes the normalizers of all cousin paths (paths that share some node i). [sent-84, score-0.546]

51 This negates the benefit of caching s, but we recover some of the benefits by splitting the normalizer to two parts: the “root” normalizer from the root node (shared by all paths) and the “downstream” normalizer. [sent-85, score-0.321]

52 We precompute which paths share downstream normalizers; all paths are partitioned into cousin sets, defined as sets for which changing the count of one member of the set changes the downstream normalizer of other paths in the set. [sent-86, score-0.856]

53 Thus, when updating the counts for path l, we only recompute Nk,l0 for all l0 in the cousin set. [sent-87, score-0.306]

54 SPARSELDA’s computation of q, the topic-word bucket, benefits from topics with unobserved (i. [sent-88, score-0.235]

55 In our case, any non-zero path, a path with any non-zero edge, contributes. [sent-91, score-0.228]

56 4 To quickly determine whether a path contributes, we introduce an edge-masked count (EMC) for each path. [sent-92, score-0.309]

57 Higher order bits encode whether edges have been observed and lower order bits encode the number of times the path has been observed. [sent-93, score-0.438]

58 For example, if a path of length three only has its first two edges observed, its EMC is 11000000. [sent-94, score-0.26]

59 If the same path were observed seven times, its EMC is 11100111. [sent-95, score-0.228]

60 With this formulation we can ignore any paths with a zero EMC. [sent-96, score-0.218]

61 Efficient sampling with refined bucket While caching the sampling equation as described in the previous section improved the efficiency, the smoothing only bucket s is small, but computing the associated mass is costly because it requires us to consider all topics and paths. [sent-97, score-1.703]

62 This is not a problem for SparseLDA because s is shared across all tokens. [sent-98, score-0.033]

63 (6) A sampling QalgorithmP can take advantage of this by not explicitly calculating s. [sent-100, score-0.185]

64 277 as proxy, and only compute the exact s if we hit the bucket s0 (Algorithm 1). [sent-104, score-0.472]

65 Here we propose two techniques to consider latent variable assignments in decreasing order of probability mass. [sent-107, score-0.204]

66 By considering fewer possible assignments, we can speed sampling at the cost of the overhead of maintaining sorted data structures. [sent-108, score-0.185]

67 We sort topics’ prominence within a document (SD) and sort the topics and paths of a word (SW). [sent-109, score-0.495]

68 Sorting topics’ prominence within a document (SD) can improve sampling from r and q; when we need to sample within a bucket, we consider paths in decreasing order of nk|d. [sent-110, score-0.623]

69 Sorting path prominence for a word (SW) can improve our ability to sample from q. [sent-111, score-0.394]

70 The edge-masked count (EMC), as described above, serves as a proxy for the probability of a path and topic. [sent-112, score-0.318]

71 If, when sampling a topic and path from q, we sample based on the decreasing EMC, which roughly correlates with path probability. [sent-113, score-1.095]

72 5 Experiments In this section, we compare the running time5 of our sampling algorithm (FAST) and our algorithm with the refined bucket (RB) against the unfactored Gibbs sampler (NAI¨VE) and examine the effect of sorting. [sent-114, score-0.7]

73 Experiments begin with 100 topics, 100 correlations, vocab size 10000 and then vary one dimension: number of topics (top), vocabulary size (middle), and number of correlations (bottom). [sent-117, score-0.339]

74 6 Since we are interested in varying vocabulary size, we rank types by average tf-idf and choose the top V. [sent-119, score-0.042]

75 For each synset in WordNet, we generate a subtree with all types in the synset— that are also in our vocabulary—as leaves connected to a common parent. [sent-122, score-0.048]

76 This subtree’s common parent is then attached to the root node. [sent-123, score-0.029]

77 We compared the FAST and FAST-RB against NA¨IVE (Table 1) on different numbers of topics, various vocabulary sizes and different numbers of correlations. [sent-124, score-0.042]

78 Their benefits are clearer as distributions become sparse (e. [sent-126, score-0.103]

79 Gains accumulate as the topic number increases, but decrease a little with the vocabulary size. [sent-129, score-0.323]

80 While both sorting strategies reduce time, sorting topics and paths for a word (SW) helps more than sorting topics in a document (SD), and combining the 613284 documents, 41554 types, and 2714634 tokens. [sent-130, score-0.811]

81 278 Figure 1: The average running time per iteration against the average number of senses per correlated words. [sent-131, score-0.038]

82 As more correlations are added, NA¨IVE’s time increases while that of FAST-RB decreases. [sent-133, score-0.158]

83 This is because the number of non-zero paths for uncorrelated words decreases as more correlations are added to the model. [sent-134, score-0.391]

84 Since our techniques save computation for every zero path, the overall computation decreases as correlations push uncorrelated words to a limited number of topics (Figure 1). [sent-135, score-0.482]

85 Qualitatively, when the synset with “king” and “baron” is added to a model, it is associated with “drug, inmate, colombia, waterfront, baron” in a topic; when “king” is correlated with “queen”, the associated topic has “king, parade, museum, queen, jackson” as its most probable words. [sent-136, score-0.367]

86 In contrast to previous approaches, inference speeds up as topics become more semantically coherent (BoydGraber et al. [sent-138, score-0.244]

87 6 Conclusion We demonstrated efficient inference techniques for topic models with tree-based priors. [sent-140, score-0.37]

88 These methods scale well, allowing for faster exploration of models that use semantics to encode correlations without sacrificing accuracy. [sent-141, score-0.2]

89 Improved scalability for such algorithms, especially in distributed environments (Smola and Narayanamurthy, 2010), could improve applications such as cross-language information retrieval, unsupervised word sense disambiguation, and knowledge discovery via interactive topic modeling. [sent-142, score-0.313]

90 Incorporating domain knowledge into topic modeling via Dirichlet forest priors. [sent-152, score-0.281]

91 Efficient methods for topic model inference on streaming document collections. [sent-192, score-0.375]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('bucket', 0.472), ('topic', 0.281), ('sparselda', 0.267), ('path', 0.228), ('nk', 0.198), ('sampling', 0.185), ('buckets', 0.181), ('paths', 0.181), ('correlations', 0.158), ('emc', 0.148), ('topics', 0.139), ('lda', 0.129), ('sorting', 0.102), ('sample', 0.095), ('andrzejewski', 0.094), ('ldza', 0.089), ('qlda', 0.089), ('slda', 0.089), ('normalizer', 0.083), ('ok', 0.083), ('yj', 0.082), ('leaf', 0.078), ('cousin', 0.078), ('caching', 0.078), ('dirichlet', 0.077), ('ni', 0.072), ('prominence', 0.071), ('yao', 0.068), ('vanilla', 0.066), ('ive', 0.066), ('assignments', 0.065), ('latent', 0.063), ('king', 0.062), ('jagarlamudi', 0.059), ('normalizers', 0.059), ('queen', 0.059), ('rlda', 0.059), ('samp', 0.059), ('sifa', 0.059), ('treebased', 0.059), ('yuening', 0.059), ('mass', 0.059), ('speeds', 0.057), ('distributions', 0.055), ('conjugacy', 0.052), ('uncorrelated', 0.052), ('baron', 0.052), ('hu', 0.052), ('downstream', 0.051), ('count', 0.05), ('gibbs', 0.05), ('inference', 0.048), ('computation', 0.048), ('synset', 0.048), ('benefits', 0.048), ('bits', 0.047), ('xiaojin', 0.047), ('sd', 0.047), ('document', 0.046), ('decreasing', 0.045), ('refined', 0.043), ('wordnet', 0.043), ('vocabulary', 0.042), ('encode', 0.042), ('mimno', 0.042), ('efficient', 0.041), ('jordan', 0.04), ('prior', 0.04), ('equation', 0.04), ('subscript', 0.04), ('smola', 0.04), ('daume', 0.04), ('proxy', 0.04), ('sw', 0.04), ('na', 0.039), ('multinomial', 0.038), ('correlated', 0.038), ('zero', 0.037), ('blei', 0.037), ('park', 0.036), ('maryland', 0.035), ('college', 0.034), ('edge', 0.034), ('shared', 0.033), ('sampled', 0.033), ('correlates', 0.033), ('abney', 0.033), ('edges', 0.032), ('tree', 0.032), ('interactive', 0.032), ('fast', 0.031), ('analogous', 0.031), ('variable', 0.031), ('quickly', 0.031), ('smoothing', 0.03), ('distribution', 0.03), ('xk', 0.03), ('root', 0.029), ('sort', 0.029), ('conditional', 0.029)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999946 79 acl-2012-Efficient Tree-Based Topic Modeling

Author: Yuening Hu ; Jordan Boyd-Graber

2 0.26089311 22 acl-2012-A Topic Similarity Model for Hierarchical Phrase-based Translation

Author: Xinyan Xiao ; Deyi Xiong ; Min Zhang ; Qun Liu ; Shouxun Lin

Abstract: Previous work using topic model for statistical machine translation (SMT) explore topic information at the word level. However, SMT has been advanced from word-based paradigm to phrase/rule-based paradigm. We therefore propose a topic similarity model to exploit topic information at the synchronous rule level for hierarchical phrase-based translation. We associate each synchronous rule with a topic distribution, and select desirable rules according to the similarity of their topic distributions with given documents. We show that our model significantly improves the translation performance over the baseline on NIST Chinese-to-English translation experiments. Our model also achieves a better performance and a faster speed than previous approaches that work at the word level.

3 0.21213469 171 acl-2012-SITS: A Hierarchical Nonparametric Model using Speaker Identity for Topic Segmentation in Multiparty Conversations

Author: Viet-An Nguyen ; Jordan Boyd-Graber ; Philip Resnik

Abstract: One of the key tasks for analyzing conversational data is segmenting it into coherent topic segments. However, most models of topic segmentation ignore the social aspect of conversations, focusing only on the words used. We introduce a hierarchical Bayesian nonparametric model, Speaker Identity for Topic Segmentation (SITS), that discovers (1) the topics used in a conversation, (2) how these topics are shared across conversations, (3) when these topics shift, and (4) a person-specific tendency to introduce new topics. We evaluate against current unsupervised segmentation models to show that including personspecific information improves segmentation performance on meeting corpora and on political debates. Moreover, we provide evidence that SITS captures an individual’s tendency to introduce new topics in political contexts, via analysis of the 2008 US presidential debates and the television program Crossfire. 1 Topic Segmentation as a Social Process Conversation, interactive discussion between two or more people, is one of the most essential and common forms of communication. Whether in an informal situation or in more formal settings such as a political debate or business meeting, a conversation is often not about just one thing: topics evolve and are replaced as the conversation unfolds. Discovering this hidden structure in conversations is a key problem for conversational assistants (Tur et al., 2010) and tools that summarize (Murray et al., 2005) and display (Ehlen et al., 2007) conversational data. Topic segmentation also can illuminate individuals’ agendas (Boydstun et al., 2011), patterns of agree- ment and disagreement (Hawes et al., 2009; Abbott 78 Jordan Boyd-Graber iSchool and UMIACS University of Maryland College Park, MD jbg@ umiac s .umd .edu Philip Resnik Department of Linguistics and UMIACS University of Maryland College Park, MD re snik @ umd .edu al., 2011), and relationships among conversational participants (Ireland et al., 2011). One of the most natural ways to capture conversational structure is topic segmentation (Reynar, 1998; Purver, 2011). Topic segmentation approaches range from simple heuristic methods based on lexical similarity (Morris and Hirst, 1991 ; Hearst, 1997) to more intricate generative models and supervised methods (Georgescul et al., 2006; Purver et al., 2006; Gruber et al., 2007; Eisenstein and Barzilay, 2008), which have been shown to outperform the established heuristics. However, previous computational work on conversational structure, particularly in topic discovery and topic segmentation, focuses primarily on conet tent, ignoring the speakers. We argue that, because conversation is a social process, we can understand conversational phenomena better by explicitly modeling behaviors of conversational participants. In Section 2, we incorporate participant identity in a new model we call Speaker Identity for Topic Segmentation (SITS), which discovers topical structure in conversation while jointly incorporating a participantlevel social component. Specifically, we explicitly model an individual’s tendency to introduce a topic. After outlining inference in Section 3 and introducing data in Section 4, we use SITS to improve state-ofthe-art-topic segmentation and topic identification models in Section 5. In addition, in Section 6, we also show that the per-speaker model is able to discover individuals who shape and influence the course of a conversation. Finally, we discuss related work and conclude the paper in Section 7. 2 Modeling Multiparty Discussions Data Properties We are interested in turn-taking, multiparty discussion. This is a broad category, inProce Jedijung, sR oefpu thbeli c50 othf K Aonrneua,a8l -M14e Jtiunlgy o 2f0 t1h2e. A ?c s 2o0c1ia2ti Aosns fo cria Ctio nm fpourta Ctoiomnpault Laitniognuaislt Licisn,g puaigsteiscs 78–87, cluding political debates, business meetings, and online chats. More formally, such datasets contain C conversations. A conversation c has Tc turns, each of which is a maximal uninterrupted utterance by one speaker.1 In each turn t ∈ [1, Tc], a speaker ac,t utters N words {wc,t,n}. Eatch ∈ w [1o,rTd is from a vocabulary of size V , {awnd th}ere are M distinct speakers. Modeling Approaches The key insight of topic segmentation is that segments evince lexical cohesion (Galley et al., 2003; Olney and Cai, 2005). Words within a segment will look more like their neighbors than other words. This insight has been used to tune supervised methods (Hsueh et al., 2006) and inspire unsupervised models of lexical cohesion using bags of words (Purver et al., 2006) and language models (Eisenstein and Barzilay, 2008). We too take the unsupervised statistical approach. It requires few resources and is applicable in many domains without extensive training. Like previous approaches, we consider each turn to be a bag of words generated from an admixture of topics. Topics—after the topic modeling literature (Blei and Lafferty, 2009)—are multinomial distributions over terms. These topics are part of a generative model posited to have produced a corpus. However, topic models alone cannot model the dynamics of a conversation. Topic models typically do not model the temporal dynamics of individual documents, and those that do (Wang et al., 2008; Gerrish and Blei, 2010) are designed for larger documents and are not applicable here because they assume that most topics appear in every time slice. Instead, we endow each turn with a binary latent variable lc,t, called the topic shift. This latent variable signifies whether the speaker changed the topic of the conversation. To capture the topic-controlling behavior of the speakers across different conversations, we further associate each speaker m with a latent topic shift tendency, πm. Informally, this variable is intended to capture the propensity of a speaker to effect a topic shift. Formally, it represents the probability that the speaker m will change the topic (distribution) of a conversation. We take a Bayesian nonparametric approach (M¨uller and Quintana, 2004). Unlike 1Note the distinction with phonetic definition are bounded by silence. utterances, which by 79 parametric models, which a priori fix the number of topics, nonparametric models use a flexible number of topics to better represent data. Nonparametric distributions such as the Dirichlet process (Ferguson, 1973) share statistical strength among conversations using a hierarchical model, such as the hierarchical Dirichlet process (HDP) (Teh et al., 2006). 2.1 Generative Process In this section, we develop SITS, a generative model of multiparty discourse that jointly discovers topics and speaker-specific topic shifts from an unannotated corpus (Figure 1a). As in the hierarchical Dirichlet process (Teh et al., 2006), we allow an unbounded number of topics to be shared among the turns of the corpus. Topics are drawn from a base distribution H over multinomial distributions over the vocabulary, a finite Dirichlet with symmetric prior λ. Unlike the HDP, where every document (here, every turn) draws a new multinomial distribution from a Dirichlet process, the social and temporal dynamics of a conversation, as specified by the binary topic shift indicator lc,t, determine when new draws happen. The full generative process is as follows: 1. For speaker m ∈ [1, M], draw speaker shift probability πm ∼ Beta(γ) 2. Draw∼ global probability measure G0 ∼ DP(α, H) 3. For each conversation c ∈ [1, C] (a) Draw conversation distribution Gc ∼ DP(α0 , G0) (b) For each turn t ∈ [1, Tc] with speaker ac,t i. If t = 1, set the topic shift lc,t = 1. Otherwise, draw lc,t ∼ Bernoulli(πac,t ). ii. If lc,t = 1∼, d Breawrn Gc,t ∼ DP(αc, Gc). Otherwise, set Gc,t ≡ Gc,t−1 . iii. For each word ≡ind Gex n ∈ [1, Nc,t] • Draw ψc,t,n ∼ Gc,t • DDrraaww wc,t,n ∼ Multinomial(ψc,t,n) The hierarchy of Dirichlet processes allows statistical strength to be shared across contexts; within a conversation and across conversations. The perspeaker topic shift tendency πm allows speaker identity to influence the evolution of topics. To make notation concrete and aligned with the topic segmentation, we introduce notation for segments in a conversation. A segment s of conversation c is a sequence of turns [τ, τ0] such that lc,τ = lc,τ0+1 = 1and lc,t = 0, ∀t ∈ (τ, τ0] . When lc,t = 0, Gc,t is the same =Gc 0,t,−∀1t a ∈nd ( aτ,llτ τtopics (i.e. multinomial distributions over words) {ψc,t,n} that generate words in turn t and the topics{ ψ{ψc,t}−1,n} that generate words in turn t −1 come from{ψ ψthc,et −s1a,mn}e as Figure 1: Graphical model representations of our proposed models: (a) the nonparametric version; (b) the parametric version. Nodes represent random variables (shaded ones are observed), lines are probabilistic dependencies. Plates represent repetition. The innermost plates are turns, grouped in conversations. distribution. Thus all topics used in a segment s are drawn from a single distribution, Gc,s, , , , Gc,s | lc,1 lc,2 · · · lc,Tc , αc, Gc ∼ DP(αc, Gc) (1) For notational convenience, Sc denotes the number of segments in conversation c, and st denotes the segment index of turn t. We emphasize that all segment-related notations are derived from the posterior over the topic shifts land not part of the model itself. Parametric Version SITS is a generalization of a parametric model (Figure 1b) where each turn has a multinomial distribution over K topics. In the parametric case, the number of topics K is fixed. Each topic, as before, is a multinomial distribution φ1 . . . φK. In the parametric case, each turn t in conversation c has an explicit multinomial distribution over K topics θc,t, identical for turns within a segment. A new topic distribution θ is drawn from a Dirichlet distribution parameterized by α when the topic shift indicator lis 1. The parametric version does not share strength within or across conversations, unlike SITS. When applied on a single conversation without speaker identity (all speakers are identical) it is equivalent to (Purver et al., 2006). In our experiments (Section 5), we compare against both. 80 3 Inference To find the latent variables that best explain observed data, we use Gibbs sampling, a widely used Markov chain Monte Carlo inference technique (Neal, 2000; Resnik and Hardisty, 2010). The state space is latent variables for topic indices assigned to all tokens z = {zc,t,n} and topic shifts assigned to turns l= {lc,t}. {Wze marginalize over all other latent variablle =s. Here, we only present the conditional sampling equations; for more details, see our supplement.2 3.1 Sampling Topic Assignments To sample zc,t,n, the index of the shared topic assigned to token n of turn t in conversation c, we need to sample the path assigning each word token to a segment-specific topic, each segment-specific topic to a conversational topic and each conversational topic to a shared topic. For efficiency, we make use of the minimal path assumption (Wallach, 2008) to generate these assignments.3 Under the minimal path assumption, an observation is assumed to have been generated by using a new distribution if and only if there is no existing distribution with the same value. 2 http://www.cs.umd.edu/∼vietan/topicshift/appendix.pdf 3We also investigated using the maximal assumption and fully sampling assignments. We found the minimal path assumption worked as well as explicitly sampling seating assignments and that the maximal path assumption worked less well. We use Nc,s,k to denote the number of tokens in segment s in conversation c assigned topic k; Nc,k denotes the total number of segment-specific topics in conversation c assigned topic k and Nk denotes the number of conversational topics assigned topic k. TWk,w denotes the number of times the shared topic k is assigned to word w in the vocabulary. Marginal counts are represented with · and ∗ represents all hyperparameters. The condit·ional d∗istribution for zc,t,n is P(zc,t,n = k | wc,t,n = w, z−c,t,n, w−c,t,n, l, ∗) ∝ Nc−,sct ,kn+αNc −c,s−ct,kct·,n Nn+c −,·αc ,t0cnN +k−· αc,t0 ,n + αK ×  VT1 W k−, ·c,wctk, n e+w V.λ( 2), Here V is the size of the vocabulary, K is the current number of shared topics and the superscript −c,t,n denotes counts without considering wc,t,n. In Equation 2, the first factor is proportional to the probability of sampling a path according to the minimal path assumption; the second factor is proportional to the likelihood of observing w given the sampled topic. Since an uninformed prior is used, when a new topic is sampled, all tokens are equiprobable. 3.2 Sampling Topic Shifts Sampling the topic shift variable lc,t requires us to consider merging or splitting segments. We use kc,t to denote the shared topic indices of all tokens in turn t of conversation c; Sac,t,x to denote the number of times speaker ac,t is assigned the topic shift with value x ∈ {0, 1}; Jcx,s to denote the number of topics in segment s 1o}f conversation c if lc,t = x and Ncx,s,j to denote the number of tokens assigned to the segment-specific topic j when lc,t = x.4 Again, the superscript −c,t is used to denote exclusion of turn t of conversation c in the corresponding counts. Recall that the topic shift is a binary variable. We use 0 to represent the case that the topic distribution is identical to the previous turn. We sample this assignment P(lc,t = 0 | l−c,t, w, k, a, ∗) ∝ SSa−a−cc,c,ct,t , t·,0++ 2 γγ×αcJ0c,sNtx=Qc01,sjJt=c,0·,1s(tx(N −c0 1,s +t,j α−c) 1)!. (3) 4Deterministically knowQing the path assignments is the primary efficiency motivation for using the minimal path assumption. The alternative is to explicitly sample the path assignments, which is more complicated (for both notation and computation). This option is spelled in full detail in the supplementary material. 81 In Equation 3, the first factor is proportional to the probability of assigning a topic shift of value 0 to speaker ac,t and the second factor is proportional to the joint probability of all topics in segment st of conversation c when lc,t = 0. The other alternative is for the topic shift to be 1, which represents the introduction of a new distri- bution over topics inside an existing segment. We sample this as P(lc,t = 1 | l−c,t, w, k, a, ∗) ∝ S −a −c ,c t, t, t, ·1+ 2 γ ×αcJc1,(st−1x)NQ=c1,1(jJs=ct1−,1(s1t)−,·1()x(N −c1 1,( +st− α1c) ,j− 1)! αcJcQ1,sNxt=c1Q1,stJj,c=1·,(s1xt( −N 1c1, +stj α−c) 1)!. (4) As above, the first faQctor in Equation 4 is proportional to the probability of assigning a topic shift of value 1to speaker ac,t; the second factor in the big bracket is proportional to the joint distribution of the topics in segments st − 1 and st. In this case lc,t = 1 means splitting the current segment, which results in two joint probabilities for two segments. 4 Datasets This section introduces the three corpora we use. We preprocess the data to remove stopwords and remove turns containing fewer than five tokens. The ICSI Meeting Corpus: The ICSI Meeting Corpus (Janin et al., 2003) is 75 transcribed meetings. For evaluation, we used a standard set of reference segmentations (Galley et al., 2003) of 25 meetings. Segmentations are binary, i.e., each point of the document is either a segment boundary or not, and on average each meeting has 8 segment boundaries. After preprocessing, there are 60 unique speakers and the vocabulary contains 3346 non-stopword tokens. The 2008 Presidential Election Debates Our second dataset contains three annotated presidential debates (Boydstun et al., 2011) between Barack Obama and John McCain and a vice presidential debate between Joe Biden and Sarah Palin. Each turn is one of two types: questions (Q) from the moderator or responses (R) from a candidate. Each clause in a turn is coded with a Question Topic (TQ) and a Response Topic (TR). Thus, a turn has a list of TQ’s and TR’s both of length equal to the number of clauses in the turn. Topics are from the Policy Agendas Topics SpeakerTypeTurn clausesTQTR BrokawQbSeenfo.r Oeib ta gmeat,s [b.e.t.t]er A arned yo thuey sa oyuingght [. to. b]e th parte tphaere Adm foerri tchaant? economy is going to get much worse1N/A ObamaR[hN.o .m,.]e Is B a,um mtac mokenofs itdu iermenpt o ahrabt oaun th tel yt ,h we c Aaen’rm epea gryoic ithnangei e trco bo hinlaosvm e[.y t. o. h]elp ordinary familes be able to stay in their1 1 4 BrokawQSen. McCain, in all candor, do you think the economy is going to get worse before it gets better?1N/A McCainR[Iom.ftwho.trie]n Ikiegrtofih oeicwonumkteiv aegfn wdlyt.ebri[ua.dyc otuf]petfh ec tserivo bnlayd,islmfoaw nes,d staobptihelcaziteplt ihoneptlrheoscuatsni hgflauvmean rckne itnw– WmhoaisrcthgiaIngbetoalnitevshoe w ne wca vna,l ucet1 240 Table 1: Example turns from the annotated 2008 election debates. The topics (TQ and TR) are from the Policy Agendas Topics Codebook which contains the following codes of topic: Macroeconomics Community Development (14), Government Operations (20). (1), Housing & Codebook, a manual inventory of 19 major topics and 225 subtopics.5 Table 1 shows an example annotation. To get reference segmentations, we assign each turn a real value from 0 to 1indicating how much a turn changes the topic. For a question-typed turn, the score is the fraction of clause topics not appearing in the previous turn; for response-typed turns, the score is the fraction of clause topics that do not appear in the corresponding question. This results in a set of non-binary reference segmentations. For evaluation metrics that require binary segmentations, we create a binary segmentation by setting a turn as a segment boundary if the computed score is 1. This threshold is chosen to include only true segment boundaries. CNN’s Crossfire Crossfire was a weekly U.S. television “talking heads” program engineered to incite heated arguments (hence the name). Each episode features two recurring hosts, two guests, and clips from the week’s news. Our Crossfire dataset contains 1134 transcribed episodes aired between 2000 and 2004.6 There are 2567 unique speakers. Unlike the previous two datasets, Crossfire does not have explicit topic segmentations, so we use it to explore speaker-specific characteristics (Section 6). 5 Topic Segmentation Experiments In this section, we examine how well SITS can replicate annotations of when new topics are introduced. 5 http://www.policyagendas.org/page/topic-codebook 6 http://www.cs.umd.edu/∼vietan/topicshift/crossfire.zip 82 We discuss metrics for evaluating an algorithm’s segmentation against a gold annotation, describe our experimental setup, and report those results. Evaluation Metrics To evaluate segmentations, we use Pk (Beeferman et al., 1999) and WindowDiff (WD) (Pevzner and Hearst, 2002). Both metrics measure the probability that two points in a document will be incorrectly separated by a segment boundary. Both techniques consider all spans of length k in the document and count whether the two endpoints of the window are (im)properly segmented against the gold segmentation. However, these metrics have drawbacks. First, they require both hypothesized and reference segmentations to be binary. Many algorithms (e.g., probabilistic approaches) give non-binary segmentations where candidate boundaries have real-valued scores (e.g., probability or confidence). Thus, evaluation requires arbitrary thresholding to binarize soft scores. To be fair, thresholds are set so the number of segments are equal to a predefined value (Purver et al., 2006; Galley et al., 2003). To overcome these limitations, we also use Earth Mover’s Distance (EMD) (Rubner et al., 2000), a metric that measures the distance between two distributions. The EMD is the minimal cost to transform one distribution into the other. Each segmentation can be considered a multi-dimensional distribution where each candidate boundary is a dimension. In EMD, a distance function across features allows partial credit for “near miss” segment boundaries. In addition, because EMD operates on distributions, we can compute the distance between non-binary hypothesized segmentations with binary or real-valued reference segmentations. We use the FastEMD implementation (Pele and Werman, 2009). Experimental Methods We applied the following methods to discover topic segmentations in a document: • TextTiling (Hearst, 1997) is one of the earliest generalpurpose topic segmentation algorithms, sliding a fixedwidth window to detect major changes in lexical similarity. • P-NoSpeaker-S: parametric version without speaker identity run on keaerc-hS conversation (Purver et al., 2006) • P-NoSpeaker-M: parametric version without speaker identity run on Mall conversations • P-SITS: the parametric version of SITS with speaker identity run on all conversations • NP-HMM: the HMM-based nonparametric model which a single topic per turn. This model can be considered a Sticky HDP-HMM (Fox et al., 2008) with speaker identity. • NP-SITS: the nonparametric version of SITS with speaker identity run on all conversations. Parameter Settings and Implementations experiment, all parameters same as in (Hearst, 1997). of TextTiling In our are the For statistical models, Gibbs sampling with 10 randomly initialized chains is used. Initial hyperparameter values are sampled from U(0, 1) to favor sparsity; statistics are collected after 500 burn-in iterations with a lag of 25 iterations over a total of 5000 iterations; and slice sampling (Neal, 2003) optimizes hyperparameters. Results and Analysis Table 2 shows the perfor- mance of various models on the topic segmentation problem, using the ICSI corpus and the 2008 debates. Consistent with previous results, probabilistic models outperform TextTiling. In addition, among the probabilistic models, the models that had access to speaker information consistently segment better than those lacking such information, supporting our assertion that there is benefit to modeling conversation as a social process. Furthermore, NP-SITS outperforms NP-HMM in both experiments, suggesting that using a distribution over topics to turns is better than using a single topic. This is consistent with parametric results reported in (Purver et al., 2006). The contribution of speaker identity seems more valuable in the debate setting. Debates are characterized by strong rewards for setting the agenda; dodging a question or moving the debate toward an oppo83 nent’s weakness can be useful strategies (Boydstun et al., 2011). In contrast, meetings (particularly lowstakes ICSI meetings) are characterized by pragmatic rather than strategic topic shifts. Second, agendasetting roles are clearer in formal debates; a modera- tor is tasked with setting the agenda and ensuring the conversation does not wander too much. The nonparametric model does best on the smaller debate dataset. We suspect that an evaluation that directly accessed the topic quality, either via prediction (Teh et al., 2006) or interpretability (Chang et al., 2009) would favor the nonparametric model more. 6 Evaluating Topic Shift Tendency In this section, we focus on the ability of SITS to capture speaker-level attributes. Recall that SITS associates with each speaker a topic shift tendency π that represents the probability of asserting a new topic in the conversation. While topic segmentation is a well studied problem, there are no established quantitative measurements of an individual’s ability to control a conversation. To evaluate whether the tendency is capturing meaningful characteristics of speakers, we compare our inferred tendencies against insights from political science. 2008 Elections To obtain a posterior estimate of π (Figure 3) we create 10 chains with hyperparameters sampled from the uniform distribution U(0, 1) and averaged π over 10 chains (as described in Section 5). In these debates, Ifill is the moderator of the debate between Biden and Palin; Brokaw, Lehrer and Schieffer are the three moderators of three debates between Obama and McCain. Here “Question” denotes questions from audiences in “town hall” debate. The role of this “speaker” can be considered equivalent to the debate moderator. The topic shift tendencies of moderators are much higher than for candidates. In the three debates between Obama and McCain, the moderators— Brokaw, Lehrer and Schieffer—have significantly higher scores than both candidates. This is a useful reality check, since in a debate the moderators are the ones asking questions and literally controlling the topical focus. Interestingly, in the vice-presidential debate, the score of moderator Ifill is only slightly higher than those of Palin and Biden; this is consistent with media commentary characterizing her as a size of the metrics Pk and WindowDiff chosen to replicate previous results. weak moderator.7 Similarly, the “Question” speaker had a relatively high variance, consistent with an amalgamation of many distinct speakers. These topic shift tendencies suggest that all candidates manage to succeed at some points in setting and controlling the debate topics. Our model gives Obama a slightly higher score than McCain, consistent with social science claims (Boydstun et al., 2011) that Obama had the lead in setting the agenda over McCain. Table 4 shows of SITS-detected topic shifts. Crossfire Crossfire, unlike the debates, has many speakers. This allows us to examine more closely what we can learn about speakers’ topic shift tendency. We verified that SITS can segment topics, and assuming that changing the topic is useful for a speaker, how can we characterize who does so effectively? We examine the relationship between topic shift tendency, social roles, and political ideology. To focus on frequent speakers, we filter out speakers with fewer than 30 turns. Most speakers have relatively small π, with the mode around 0.3. There are, however, speakers with very high topic shift tendencies. Table 5 shows the speakers having the highest values according to SITS. We find that there are three general patterns for who influences the course of a conversation in Crossfire. First, there are structural “speakers” the show uses to frame and propose new topics. These are 7 http://harpers.org/archive/2008/10/hbc-90003659 84 2008 Presidential Election Debates (larger means greater tendency) audience questions, news clips (e.g. many of Gore’s and Bush’s turns from 2000), and voice overs. That SITS is able to recover these is reassuring. Second, the stable of regular hosts receives high topic shift tendencies, which is reasonable given their experience with the format and ostensible moderation roles (in practice they also stoke lively discussion). The remaining class is more interesting. The remaining non-hosts with high topic shift tendency are relative moderates on the political spectrum: • John Kasich, one of few Republicans to support the assault weapons ban and now governor of Ohio, a swing state • Christine Todd Whitman, former Republican governor of CNehrwis Jersey, a very iDtmemano,c froartmice srt Ratee • John McCain, who before 2008 was known as a “maverick” for working with Democrats (e.g. Russ Feingold) This suggests that, despite Crossfire’s tendency to create highly partisan debates, those who are able to work across the political spectrum may best be able to influence the topic under discussion in highly polarized contexts. Table 4 shows detected topic shifts from these speakers; two of these examples (McCain and Whitman) show disagreement of Republicans with President Bush. In the other, Kasich is defending a Republican plan (school vouchers) popular with traditional Democratic constituencies. 7 Related and Future Work In the realm of statistical models, a number of techniques incorporate social connections and identity to explain content in social networks (Chang and Blei, atsbDePMmwphIncFiAoasCrtuLleycnNdAg:irIs’SatYphyo,weumckItGrasy’.qoheivfnuIakgrsdt?heo vna,dtbpJ.omslrheyivcaBnwdspeur[.ihodqtef]nuar,slihmetdnyuaopi’s-SbeI[hBn.FCtDvHLcr]ligEemIhysNoa:nFbvWidxeAltEsghnmRboad:eics[yr.,fmtuwleinha][go.,dLYftweur]–’lhsdaitngxerkbIfoat.hqeslkOufinrmbtyoeha,rit[n.geholyasc]rdi,wteoaxylpm’sburneItaopfkvicsqr.,n[BYoOtafebxruli.,mcEksGgatvn]roOebpyitmlnorcd.ea[sfviPYtr]lgoandyu., Previous turnTurn detected as shifting topic examples of those with high topic shift tendency 238947156FPAGNQMreouna.mlvsWea†‡kt.iluBonrcseh‡.7586 41702 4863150FBCKWMealchgrsitCvA lamuhoin†efr.5 2473509 π. RankSpeakerπRankSpeakerπ Table 5: Top speakers by topic shift tendencies. We mark hosts (†) and “speakers” who often (but not always) appeared in clips (‡). Apart from those groups, speakers with the highest tendency were political moderates. 2009) and scientific corpora (Rosen-Zvi et al., 2004). However, these models ignore the temporal evolution of content, treating documents as static. Models that do investigate the evolution of topics over time typically ignore the identify of the speaker. For example: models having sticky topics over ngrams (Johnson, 2010), sticky HDP-HMM (Fox et al., 2008); models that are an amalgam of sequential models and topic models (Griffiths et al., 2005; Wal85 lach, 2006; Gruber et al., 2007; Ahmed and Xing, 2008; Boyd-Graber and Blei, 2008; Du et al., 2010); or explicit models of time or other relevant features as a distinct latent variable (Wang and McCallum, 2006; Eisenstein et al., 2010). In contrast, SITS jointly models topic and individuals’ tendency to control a conversation. Not only does SITS outperform other models using standard computational linguistics baselines, but it also pro- poses intriguing hypotheses for social scientists. Associating each speaker with a scalar that models their tendency to change the topic does improve performance on standard tasks, but it’s inadequate to fully describe an individual. Modeling individuals’ perspective (Paul and Girju, 2010), “side” (Thomas et al., 2006), or personal preferences for topics (Grimmer, 2009) would enrich the model and better illuminate the interaction of influence and topic. Statistical analysis of political discourse can help discover patterns that political scientists, who often work via a “close reading,” might otherwise miss. We plan to work with social scientists to validate our implicit hypothesis that our topic shift tendency correlates well with intuitive measures of “influence.” Acknowledgements This research was funded in part by the Army Research Laboratory through ARL Cooperative Agreement W91 1NF-09-2-0072 and by the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA), through the Army Research Laboratory. Jordan Boyd-Graber and Philip Resnik are also supported by US National Science Foundation Grant NSF grant #1018625. Any opinions, findings, conclusions, or recommendations expressed are the authors’ and do not necessarily reflect those of the sponsors. References [Abbott et al., 2011] Abbott, R., Walker, M., Anand, P., Fox Tree, J. E., Bowmani, R., and King, J. (201 1). How can you say such things?!?: Recognizing disagreement in informal political argument. In Proceedings of the Workshop on Language in Social Media (LSM 2011), pages 2–1 1. [Ahmed and Xing, 2008] Ahmed, A. and Xing, E. P. (2008). Dynamic non-parametric mixture models and the recurrent Chinese restaurant process: with applications to evolutionary clustering. In SDM, pages 219– 230. [Beeferman et al., 1999] Beeferman, D., Berger, A., and Lafferty, J. (1999). Statistical models for text segmentation. Mach. Learn., 34: 177–210. [Blei and Lafferty, 2009] Blei, D. M. and Lafferty, J. (2009). Text Mining: Theory and Applications, chapter Topic Models. Taylor and Francis, London. [Boyd-Graber and Blei, 2008] Boyd-Graber, J. and Blei, D. M. (2008). Syntactic topic models. In Proceedings of Advances in Neural Information Processing Systems. [Boydstun et al., 2011] Boydstun, A. E., Phillips, C., and Glazier, R. A. (201 1). It’s the economy again, stupid: Agenda control in the 2008 presidential debates. Forthcoming. [Chang and Blei, 2009] Chang, J. and Blei, D. M. (2009). Relational topic models for document networks. In Proceedings of Artificial Intelligence and Statistics. [Chang et al., 2009] Chang, J., Boyd-Graber, J., Wang, C., Gerrish, S., and Blei, D. M. (2009). Reading tea leaves: How humans interpret topic models. In Neural Information Processing Systems. [Du et al., 2010] Du, L., Buntine, W., and Jin, H. (2010). Sequential latent dirichlet allocation: Discover underlying topic structures within a document. In Data Mining (ICDM), 2010 IEEE 10th International Conference on, pages 148 –157. 86 [Ehlen et al., 2007] Ehlen, P., Purver, M., and Niekrasz, J. (2007). A meeting browser that learns. In In: Proceedings of the AAAI Spring Symposium on Interaction Challenges for Intelligent Assistants. [Eisenstein and Barzilay, 2008] Eisenstein, J. and Barzilay, R. (2008). Bayesian unsupervised topic segmentation. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, Proceedings of Emperical Methods in Natural Language Processing. [Eisenstein et al., 2010] Eisenstein, J., O’Connor, B., Smith, N. A., and Xing, E. P. (2010). A latent variable model for geographic lexical variation. In EMNLP’10, pages 1277–1287. [Ferguson, 1973] Ferguson, T. S. (1973). A Bayesian analysis of some nonparametric problems. The Annals of Statistics, 1(2):209–230. [Fox et al., 2008] Fox, E. B., Sudderth, E. B., Jordan, M. I., and Willsky, A. S. (2008). An hdp-hmm for systems with state persistence. In Proceedings of International Conference of Machine Learning. [Galley et al., 2003] Galley, M., McKeown, K., FoslerLussier, E., and Jing, H. (2003). Discourse segmentation of multi-party conversation. In Proceedings of the Association for Computational Linguistics. [Georgescul et al., 2006] Georgescul, M., Clark, A., and Armstrong, S. (2006). Word distributions for thematic segmentation in a support vector machine approach. In Conference on Computational Natural Language Learning. [Gerrish and Blei, 2010] Gerrish, S. and Blei, D. M. (2010). A language-based approach to measuring scholarly impact. In Proceedings of International Conference of Machine Learning. [Griffiths et al., 2005] Griffiths, T. L., Steyvers, M., Blei, D. M., and Tenenbaum, J. B. (2005). Integrating topics and syntax. In Proceedings of Advances in Neural Information Processing Systems. [Grimmer, 2009] Grimmer, J. (2009). A Bayesian Hierarchical Topic Model for Political Texts: Measuring Expressed Agendas in Senate Press Releases. Political Analysis, 18: 1–35. [Gruber et al., 2007] Gruber, A., Rosen-Zvi, M., and Weiss, Y. (2007). Hidden topic Markov models. In Artificial Intelligence and Statistics. [Hawes et al., 2009] Hawes, T., Lin, J., and Resnik, P. (2009). Elements of a computational model for multiparty discourse: The turn-taking behavior of Supreme Court justices. Journal of the American Society for Information Science and Technology, 60(8): 1607–1615. [Hearst, 1997] Hearst, M. A. (1997). TextTiling: Segmenting text into multi-paragraph subtopic passages. Computational Linguistics, 23(1):33–64. [Hsueh et al., 2006] Hsueh, P.-y., Moore, J. D., and Renals, S. (2006). Automatic segmentation of multiparty dialogue. In Proceedings of the European Chapter of the Association for Computational Linguistics. [Ireland et al., 2011] Ireland, M. E., Slatcher, R. B., Eastwick, P. W., Scissors, L. E., Finkel, E. J., and Pennebaker, J. W. (201 1). Language style matching predicts relationship initiation and stability. Psychological Science, 22(1):39–44. [Janin et al., 2003] Janin, A., Baron, D., Edwards, J., Ellis, D., Gelbart, D., Morgan, N., Peskin, B., Pfau, T., Shriberg, E., Stolcke, A., and Wooters, C. (2003). The ICSI meeting corpus. In IEEE International Confer- ence on Acoustics, Speech, and Signal Processing. [Johnson, 2010] Johnson, M. (2010). PCFGs, topic models, adaptor grammars and learning topical collocations and the structure of proper names. In Proceedings of the Association for Computational Linguistics. [Morris and Hirst, 1991] Morris, J. and Hirst, G. (1991). Lexical cohesion computed by thesaural relations as an indicator of the structure of text. Computational Linguistics, 17:21–48. [M¨ uller and Quintana, 2004] Mu¨ller, P. and Quintana, F. A. (2004). Nonparametric Bayesian data analysis. Statistical Science, 19(1):95–1 10. [Murray et al., 2005] Murray, G., Renals, S., and Carletta, J. (2005). Extractive summarization of meeting recordings. In European Conference on Speech Communication and Technology. [Neal, 2000] Neal, R. M. (2000). Markov chain sampling methods for Dirichlet process mixture models. Journal of Computational and Graphical Statistics, 9(2):249– 265. [Neal, 2003] Neal, R. M. (2003). Slice sampling. Annals of Statistics, 31:705–767. [Olney and Cai, 2005] Olney, A. and Cai, Z. (2005). An orthonormal basis for topic segmentation in tutorial dialogue. In Proceedings of the Human Language Technology Conference. [Paul and Girju, 2010] Paul, M. and Girju, R. (2010). A two-dimensional topic-aspect model for discovering multi-faceted topics. In Association for the Advancement of Artificial Intelligence. [Pele and Werman, 2009] Pele, O. and Werman, M. (2009). Fast and robust earth mover’s distances. In International Conference on Computer Vision. [Pevzner and Hearst, 2002] Pevzner, L. and Hearst, M. A. (2002). A critique and improvement of an evaluation metric for text segmentation. Computational Linguistics, 28. [Purver, 2011] Purver, M. (201 1). Topic segmentation. In Tur, G. and de Mori, R., editors, Spoken Language Understanding: Systems for Extracting Semantic Information from Speech, pages 291–3 17. Wiley. 87 [Purver et al., 2006] Purver, M., Ko¨rding, K., Griffiths, T. L., and Tenenbaum, J. (2006). Unsupervised topic modelling for multi-party spoken discourse. In Proceedings of the Association for Computational Linguistics. [Resnik and Hardisty, 2010] Resnik, P. and Hardisty, E. (2010). Gibbs sampling for the uninitiated. Technical Report UMIACS-TR-2010-04, University of Maryland. http://www.lib.umd.edu/drum/handle/1903/10058. [Reynar, 1998] Reynar, J. C. (1998). Topic Segmentation: Algorithms and Applications. PhD thesis, University of Pennsylvania. [Rosen-Zvi et al., 2004] Rosen-Zvi, M., Griffiths, T. L., Steyvers, M., and Smyth, P. (2004). The author-topic model for authors and documents. In Proceedings of Uncertainty in Artificial Intelligence. [Rubner et al., 2000] Rubner, Y., Tomasi, C., and Guibas, L. J. (2000). The earth mover’s distance as a metric for image retrieval. International Journal of Computer Vision, 40:99–121 . [Teh et al., 2006] Teh, Y. W., Jordan, M. I., Beal, M. J., and Blei, D. M. (2006). Hierarchical Dirichlet processes. Journal of the American Statistical Association, 101(476): 1566–1581. [Thomas et al., 2006] Thomas, M., Pang, B., and Lee, L. (2006). Get out the vote: Determining support or opposition from Congressional floor-debate transcripts. In Proceedings of Emperical Methods in Natural Language Processing. [Tur et al., 2010] Tur, G., Stolcke, A., Voss, L., Peters, S., Hakkani-Tu¨r, D., Dowding, J., Favre, B., Ferna´ndez, R., Frampton, M., Frandsen, M., Frederickson, C., Graciarena, M., Kintzing, D., Leveque, K., Mason, S., Niekrasz, J., Purver, M., Riedhammer, K., Shriberg, E., Tien, J., Vergyri, D., and Yang, F. (2010). The CALO meeting assistant system. Trans. Audio, Speech and Lang. Proc., 18: 1601–161 1. [Wallach, 2006] Wallach, H. M. (2006). Topic modeling: Beyond bag-of-words. In Proceedings of International Conference of Machine Learning. [Wallach, 2008] Wallach, H. M. (2008). Structured Topic Models for Language. PhD thesis, University of Cambridge. [Wang et al., 2008] Wang, C., Blei, D. M., and Heckerman, D. (2008). Continuous time dynamic topic models. In Proceedings of Uncertainty in Artificial Intelligence. [Wang and McCallum, 2006] Wang, X. and McCallum, A. (2006). Topics over time: a non-Markov continuoustime model of topical trends. In Knowledge Discovery and Data Mining, Knowledge Discovery and Data Mining.

4 0.19406505 199 acl-2012-Topic Models for Dynamic Translation Model Adaptation

Author: Vladimir Eidelman ; Jordan Boyd-Graber ; Philip Resnik

Abstract: We propose an approach that biases machine translation systems toward relevant translations based on topic-specific contexts, where topics are induced in an unsupervised way using topic models; this can be thought of as inducing subcorpora for adaptation without any human annotation. We use these topic distributions to compute topic-dependent lex- ical weighting probabilities and directly incorporate them into our translation model as features. Conditioning lexical probabilities on the topic biases translations toward topicrelevant output, resulting in significant improvements of up to 1 BLEU and 3 TER on Chinese to English translation over a strong baseline.

5 0.16992338 208 acl-2012-Unsupervised Relation Discovery with Sense Disambiguation

Author: Limin Yao ; Sebastian Riedel ; Andrew McCallum

Abstract: To discover relation types from text, most methods cluster shallow or syntactic patterns of relation mentions, but consider only one possible sense per pattern. In practice this assumption is often violated. In this paper we overcome this issue by inducing clusters of pattern senses from feature representations of patterns. In particular, we employ a topic model to partition entity pairs associated with patterns into sense clusters using local and global features. We merge these sense clusters into semantic relations using hierarchical agglomerative clustering. We compare against several baselines: a generative latent-variable model, a clustering method that does not disambiguate between path senses, and our own approach but with only local features. Experimental results show our proposed approach discovers dramatically more accurate clusters than models without sense disambiguation, and that incorporating global features, such as the document theme, is crucial.

6 0.14259252 98 acl-2012-Finding Bursty Topics from Microblogs

7 0.13389973 86 acl-2012-Exploiting Latent Information to Predict Diffusions of Novel Topics on Social Networks

8 0.12295389 31 acl-2012-Authorship Attribution with Author-aware Topic Models

9 0.11049394 198 acl-2012-Topic Models, Latent Space Models, Sparse Coding, and All That: A Systematic Understanding of Probabilistic Semantic Extraction in Large Corpus

10 0.10256618 203 acl-2012-Translation Model Adaptation for Statistical Machine Translation with Monolingual Topic Information

11 0.098267995 61 acl-2012-Cross-Domain Co-Extraction of Sentiment and Topic Lexicons

12 0.094939202 144 acl-2012-Modeling Review Comments

13 0.091355309 88 acl-2012-Exploiting Social Information in Grounded Language Learning via Grammatical Reduction

14 0.085324235 110 acl-2012-Historical Analysis of Legal Opinions with a Sparse Mixed-Effects Latent Variable Model

15 0.082672119 14 acl-2012-A Joint Model for Discovery of Aspects in Utterances

16 0.080749094 159 acl-2012-Pattern Learning for Relation Extraction with a Hierarchical Topic Model

17 0.080245152 145 acl-2012-Modeling Sentences in the Latent Space

18 0.078654654 28 acl-2012-Aspect Extraction through Semi-Supervised Modeling

19 0.059616152 18 acl-2012-A Probabilistic Model for Canonicalizing Named Entity Mentions

20 0.054635692 102 acl-2012-Genre Independent Subgroup Detection in Online Discussion Threads: A Study of Implicit Attitude using Textual Latent Semantics

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.178), (1, 0.11), (2, 0.189), (3, 0.044), (4, -0.36), (5, 0.05), (6, -0.08), (7, -0.041), (8, 0.074), (9, 0.011), (10, 0.058), (11, 0.0), (12, 0.048), (13, -0.051), (14, 0.029), (15, 0.009), (16, -0.024), (17, -0.008), (18, -0.0), (19, 0.022), (20, 0.014), (21, -0.051), (22, -0.024), (23, 0.004), (24, -0.009), (25, 0.005), (26, 0.008), (27, 0.017), (28, -0.008), (29, -0.02), (30, -0.094), (31, 0.098), (32, -0.07), (33, -0.057), (34, -0.018), (35, -0.028), (36, -0.053), (37, 0.112), (38, -0.01), (39, 0.023), (40, -0.056), (41, -0.027), (42, 0.048), (43, 0.084), (44, -0.054), (45, 0.031), (46, 0.016), (47, 0.063), (48, -0.046), (49, 0.033)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.97829556 79 acl-2012-Efficient Tree-Based Topic Modeling

Author: Yuening Hu ; Jordan Boyd-Graber

2 0.8660444 171 acl-2012-SITS: A Hierarchical Nonparametric Model using Speaker Identity for Topic Segmentation in Multiparty Conversations

Author: Viet-An Nguyen ; Jordan Boyd-Graber ; Philip Resnik

3 0.78411388 31 acl-2012-Authorship Attribution with Author-aware Topic Models

Author: Yanir Seroussi ; Fabian Bohnert ; Ingrid Zukerman

Abstract: Authorship attribution deals with identifying the authors of anonymous texts. Building on our earlier finding that the Latent Dirichlet Allocation (LDA) topic model can be used to improve authorship attribution accuracy, we show that employing a previously-suggested Author-Topic (AT) model outperforms LDA when applied to scenarios with many authors. In addition, we define a model that combines LDA and AT by representing authors and documents over two disjoint topic sets, and show that our model outperforms LDA, AT and support vector machines on datasets with many authors.

4 0.7672286 22 acl-2012-A Topic Similarity Model for Hierarchical Phrase-based Translation

Author: Xinyan Xiao ; Deyi Xiong ; Min Zhang ; Qun Liu ; Shouxun Lin

5 0.69995612 110 acl-2012-Historical Analysis of Legal Opinions with a Sparse Mixed-Effects Latent Variable Model

Author: William Yang Wang ; Elijah Mayfield ; Suresh Naidu ; Jeremiah Dittmar

Abstract: We propose a latent variable model to enhance historical analysis of large corpora. This work extends prior work in topic modelling by incorporating metadata, and the interactions between the components in metadata, in a general way. To test this, we collect a corpus of slavery-related United States property law judgements sampled from the years 1730 to 1866. We study the language use in these legal cases, with a special focus on shifts in opinions on controversial topics across different regions. Because this is a longitudinal data set, we are also interested in understanding how these opinions change over the course of decades. We show that the joint learning scheme of our sparse mixed-effects model improves on other state-of-the-art generative and discriminative models on the region and time period identification tasks. Experiments show that our sparse mixed-effects model is more accurate quantitatively and qualitatively interesting, and that these improvements are robust across different parameter settings.

6 0.68512011 98 acl-2012-Finding Bursty Topics from Microblogs

7 0.67013049 86 acl-2012-Exploiting Latent Information to Predict Diffusions of Novel Topics on Social Networks

8 0.65763676 198 acl-2012-Topic Models, Latent Space Models, Sparse Coding, and All That: A Systematic Understanding of Probabilistic Semantic Extraction in Large Corpus

9 0.65242386 199 acl-2012-Topic Models for Dynamic Translation Model Adaptation

10 0.5170114 88 acl-2012-Exploiting Social Information in Grounded Language Learning via Grammatical Reduction

11 0.50243175 14 acl-2012-A Joint Model for Discovery of Aspects in Utterances

12 0.4999305 208 acl-2012-Unsupervised Relation Discovery with Sense Disambiguation

13 0.44853219 203 acl-2012-Translation Model Adaptation for Statistical Machine Translation with Monolingual Topic Information

14 0.42399329 61 acl-2012-Cross-Domain Co-Extraction of Sentiment and Topic Lexicons

15 0.40125492 144 acl-2012-Modeling Review Comments

16 0.3591902 28 acl-2012-Aspect Extraction through Semi-Supervised Modeling

17 0.35283729 159 acl-2012-Pattern Learning for Relation Extraction with a Hierarchical Topic Model

18 0.3336986 18 acl-2012-A Probabilistic Model for Canonicalizing Named Entity Mentions

19 0.32257116 145 acl-2012-Modeling Sentences in the Latent Space

20 0.31706861 29 acl-2012-Assessing the Effect of Inconsistent Assessors on Summarization Evaluation

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(26, 0.017), (28, 0.056), (30, 0.026), (37, 0.02), (39, 0.484), (59, 0.011), (74, 0.011), (82, 0.013), (84, 0.013), (85, 0.021), (90, 0.059), (92, 0.14), (94, 0.015), (99, 0.038)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.94350499 180 acl-2012-Social Event Radar: A Bilingual Context Mining and Sentiment Analysis Summarization System

Author: Wen-Tai Hsieh ; Chen-Ming Wu ; Tsun Ku ; Seng-cho T. Chou

Abstract: Social Event Radar is a new social networking-based service platform, that aim to alert as well as monitor any merchandise flaws, food-safety related issues, unexpected eruption of diseases or campaign issues towards to the Government, enterprises of any kind or election parties, through keyword expansion detection module, using bilingual sentiment opinion analysis tool kit to conclude the specific event social dashboard and deliver the outcome helping authorities to plan “risk control” strategy. With the rapid development of social network, people can now easily publish their opinions on the Internet. On the other hand, people can also obtain various opinions from others in a few seconds even though they do not know each other. A typical approach to obtain required information is to use a search engine with some relevant keywords. We thus take the social media and forum as our major data source and aim at collecting specific issues efficiently and effectively in this work. 163 Chen-Ming Wu Institute for Information Industry cmwu@ i i i .org .tw Seng-cho T. Chou Department of IM, National Taiwan University chou @ im .ntu .edu .tw 1

same-paper 2 0.92438018 79 acl-2012-Efficient Tree-Based Topic Modeling

Author: Yuening Hu ; Jordan Boyd-Graber

3 0.88863885 186 acl-2012-Structuring E-Commerce Inventory

Author: Karin Mauge ; Khash Rohanimanesh ; Jean-David Ruvini

Abstract: Large e-commerce enterprises feature millions of items entered daily by a large variety of sellers. While some sellers provide rich, structured descriptions of their items, a vast majority of them provide unstructured natural language descriptions. In the paper we present a 2 steps method for structuring items into descriptive properties. The first step consists in unsupervised property discovery and extraction. The second step involves supervised property synonym discovery using a maximum entropy based clustering algorithm. We evaluate our method on a year worth of ecommerce data and show that it achieves excellent precision with good recall.

4 0.88564181 7 acl-2012-A Computational Approach to the Automation of Creative Naming

Author: Gozde Ozbal ; Carlo Strapparava

Abstract: In this paper, we propose a computational approach to generate neologisms consisting of homophonic puns and metaphors based on the category of the service to be named and the properties to be underlined. We describe all the linguistic resources and natural language processing techniques that we have exploited for this task. Then, we analyze the performance of the system that we have developed. The empirical results show that our approach is generally effective and it constitutes a solid starting point for the automation ofthe naming process.

5 0.86324078 133 acl-2012-Learning to "Read Between the Lines" using Bayesian Logic Programs

Author: Sindhu Raghavan ; Raymond Mooney ; Hyeonseo Ku

Abstract: Most information extraction (IE) systems identify facts that are explicitly stated in text. However, in natural language, some facts are implicit, and identifying them requires “reading between the lines”. Human readers naturally use common sense knowledge to infer such implicit information from the explicitly stated facts. We propose an approach that uses Bayesian Logic Programs (BLPs), a statistical relational model combining firstorder logic and Bayesian networks, to infer additional implicit information from extracted facts. It involves learning uncertain commonsense knowledge (in the form of probabilistic first-order rules) from natural language text by mining a large corpus of automatically extracted facts. These rules are then used to derive additional facts from extracted information using BLP inference. Experimental evaluation on a benchmark data set for machine reading demonstrates the efficacy of our approach.

6 0.58520865 21 acl-2012-A System for Real-time Twitter Sentiment Analysis of 2012 U.S. Presidential Election Cycle

7 0.54000109 198 acl-2012-Topic Models, Latent Space Models, Sparse Coding, and All That: A Systematic Understanding of Probabilistic Semantic Extraction in Large Corpus

8 0.53056866 206 acl-2012-UWN: A Large Multilingual Lexical Knowledge Base

9 0.51079041 161 acl-2012-Polarity Consistency Checking for Sentiment Dictionaries

10 0.50660431 28 acl-2012-Aspect Extraction through Semi-Supervised Modeling

11 0.50646609 151 acl-2012-Multilingual Subjectivity and Sentiment Analysis

12 0.50642383 102 acl-2012-Genre Independent Subgroup Detection in Online Discussion Threads: A Study of Implicit Attitude using Textual Latent Semantics

13 0.50598389 88 acl-2012-Exploiting Social Information in Grounded Language Learning via Grammatical Reduction

14 0.50460505 36 acl-2012-BIUTEE: A Modular Open-Source System for Recognizing Textual Entailment

15 0.5040524 38 acl-2012-Bayesian Symbol-Refined Tree Substitution Grammars for Syntactic Parsing

16 0.50340891 132 acl-2012-Learning the Latent Semantics of a Concept from its Definition

17 0.50080901 6 acl-2012-A Comprehensive Gold Standard for the Enron Organizational Hierarchy

18 0.49484777 80 acl-2012-Efficient Tree-based Approximation for Entailment Graph Learning

19 0.4862597 174 acl-2012-Semantic Parsing with Bayesian Tree Transducers

20 0.48477331 70 acl-2012-Demonstration of IlluMe: Creating Ambient According to Instant Message Logs