nips nips2013 nips2013-301 knowledge-graph by maker-knowledge-mining

301 nips-2013-Sparse Additive Text Models with Low Rank Background

Source: pdf

Author: Lei Shi

Abstract: The sparse additive model for text modeling involves the sum-of-exp computing, whose cost is consuming for large scales. Moreover, the assumption of equal background across all classes/topics may be too strong. This paper extends to propose sparse additive model with low rank background (SAM-LRB) and obtains simple yet efﬁcient estimation. Particularly, employing a double majorization bound, we approximate log-likelihood into a quadratic lower-bound without the log-sumexp terms. The constraints of low rank and sparsity are then simply embodied by nuclear norm and ℓ1 -norm regularizers. Interestingly, we ﬁnd that the optimization task of SAM-LRB can be transformed into the same form as in Robust PCA. Consequently, parameters of supervised SAM-LRB can be efﬁciently learned using an existing algorithm for Robust PCA based on accelerated proximal gradient. Besides the supervised case, we extend SAM-LRB to favor unsupervised and multifaceted scenarios. Experiments on three real data demonstrate the effectiveness and efﬁciency of SAM-LRB, compared with a few state-of-the-art models. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 om Abstract The sparse additive model for text modeling involves the sum-of-exp computing, whose cost is consuming for large scales. [sent-6, score-0.257]

2 Moreover, the assumption of equal background across all classes/topics may be too strong. [sent-7, score-0.154]

3 This paper extends to propose sparse additive model with low rank background (SAM-LRB) and obtains simple yet efﬁcient estimation. [sent-8, score-0.48]

4 Particularly, employing a double majorization bound, we approximate log-likelihood into a quadratic lower-bound without the log-sumexp terms. [sent-9, score-0.332]

5 The constraints of low rank and sparsity are then simply embodied by nuclear norm and ℓ1 -norm regularizers. [sent-10, score-0.269]

6 Consequently, parameters of supervised SAM-LRB can be efﬁciently learned using an existing algorithm for Robust PCA based on accelerated proximal gradient. [sent-12, score-0.316]

7 Besides the supervised case, we extend SAM-LRB to favor unsupervised and multifaceted scenarios. [sent-13, score-0.46]

8 Several efforts emerged to seek alternative formulations, taking the correlated topic models [13, 19] for instance. [sent-18, score-0.234]

9 Its core idea is that the lexical distribution in log-space comes by adding the background distribution with sparse deviation vectors. [sent-21, score-0.308]

10 Successfully applying SAGE, effort [14] discovers geographical topics in the twitter stream, and paper [25] detects communities in computational linguistics. [sent-22, score-0.202]

11 Second, SAGE assumes one single background vector across all classes/topics, or equivalently, there is one background vector for each class/topic but all background vectors are constrained to be equal. [sent-25, score-0.507]

12 Motivated to solve the second problem, we are propose to use a low rank constrained background. [sent-29, score-0.188]

13 However, directly assigning the low rank assumption to the log-space is difﬁcult. [sent-30, score-0.169]

14 We turn to approximate the data log-likelihood of sparse additive model by a quadratic lower-bound based on the 1 double majorization bound in [6], so that the costly log-sum-exponential computation, i. [sent-31, score-0.473]

15 Main contributions of this paper can be summarized into four-fold as below: • Propose to use low rank background to extend the equally constrained setting in SAGE. [sent-35, score-0.342]

16 • Approximate the data log-likelihood of sparse additive model by a quadratic lower-bound based on the double majorization bound in [6], so that the costly log-sum-exponential computation is avoided. [sent-36, score-0.473]

17 Consequently, SAM-LRB can be efﬁciently learned by employing the accelerated proximal gradient algorithm for Robust PCA [20]. [sent-38, score-0.245]

18 • Extend SAM-LRB to favor supervised classiﬁcation, unsupervised topic model and multifaceted model; conduct experimental comparisons on real data to validate SAM-LRB. [sent-39, score-0.664]

19 1 Supervised Sparse Additive Model Same as in SAGE [10], the core idea of our model is that the lexical distribution in log-space comes from adding the background distribution with additional vectors. [sent-41, score-0.2]

20 Particularly, we are given documents D documents over M words. [sent-42, score-0.12]

21 For each document d ∈ [1, D], let yd ∈ [1, K] represent the class label in the current supervised scenario, cd ∈ RM denote the vector of term counts, + and Cd = w cdw be the total term count. [sent-43, score-0.597]

22 We assume each class k ∈ [1, K] has two vectors bk , sk ∈ RM , denoting the background and additive distributions in log-space, respectively. [sent-44, score-0.58]

23 Then the generative distribution for each word w in a document d with label yd is a soft-max form: exp(byd w + syd w ) p(w|yd ) = p(w|yd , byd , syd ) = M . [sent-45, score-0.59]

24 , sK ], the log-likelihood of data X is: M K L(d, k), L = log p(X |Θ) = L(d, k) = c⊤ (bk + sk ) − Cd log d k=1 d:yd =k exp(bki + ski ). [sent-52, score-0.247]

25 ˆ ˆ In SAGE [10], the authors further assumed that the background vectors across all classes are the same, i. [sent-54, score-0.154]

26 , bk = b for ∀k, and each additive vector sk is sparse. [sent-56, score-0.426]

27 Although intuitive, the background equality assumption may be too strong for real applications. [sent-57, score-0.197]

28 In this case, SAGE would tend to include these terms as the sparse additive part, instead of as the background. [sent-59, score-0.183]

29 1 as an illustrative example, the log-space distribution (left) is the sum of the low-rank background B (middle) and the sparse S (right). [sent-61, score-0.259]

30 Applying SAGE to this type of data, the equality constrained background B would fail to capture the low-rank structure, and/or the additive part S would be not sparse, so that there may be risks of over-ﬁtting or under-ﬁtting. [sent-62, score-0.345]

31 2 Supervised Sparse Additive Model with Low Rank Background Motivated to avoid the inefﬁcient computing due to sum-of-exp, we adopt the double majorization lower-bound of L [6], so that it is well approximated and quadratic w. [sent-73, score-0.29]

32 Further based on this lower-bound, we proceed to assume the background B across classes is low-rank, in contrast to the equality constraint in SAGE. [sent-77, score-0.232]

33 An optimization algorithm is proposed based on proximal gradient. [sent-78, score-0.122]

34 (2): K Llb ⊤ −(bk + sk )⊤ Ak (bk + sk ) − βk (bk + sk ) − γk , = k=1 ˜ with γk = Ck αk − 1 2 M 2 2 αk + ξki + f (ξki )(αk − ξki ) + 2 log(exp(ξki ) + 1) i=1 ˜ Ak = Ck diag [f (ξk )] , ˜ 1 βk = Ck ( − αk f (ξk )) − 2 cd , d:yd =k ˜ Ck = , Cd . [sent-88, score-0.51]

35 (4) d:yd =k For each class k, the two variational variables, αk ∈ R and ξk ∈ RM , can be updated iteratively as + below for a better approximated lower-bound. [sent-89, score-0.13]

36 αk = M 1 M (bki + ski )f (ξki ) , −1+ M 2 i=1 f (ξki ) i=1 ξk = abs(bk + sk − αk ). [sent-91, score-0.187]

37 (4), which is convenient for further assigning the low-rank constraint on B and the sparsity constraint on S. [sent-102, score-0.129]

38 (6) Concerning the two constraints, we call the above as supervised Sparse Additive Model with LowRank Background, or supervised SAM-LRB for short. [sent-113, score-0.29]

39 In the literature, there have been several efforts considering both low rank and sparse constraints similar to Eq. [sent-115, score-0.253]

40 (6), most of which take the use of proximal gradient [2, 7]. [sent-116, score-0.154]

41 Papers [20, 28] studied the problems under the name of Robust Principal Component Analysis (RPCA), aiming to decouple an observed matrix as the sum of a low rank matrix and a sparse matrix. [sent-117, score-0.223]

42 In [24], the authors proposed an efﬁcient algorithm for problems that constrain a matrix to be both low rank and sparse simultaneously. [sent-120, score-0.223]

43 Following these existing works, we adopt the nuclear norm to implement the low rank constraint, and ℓ1 -norm for the sparsity constraint, respectively. [sent-121, score-0.269]

44 λk = (bk + sk ) 1 of Llb equal to zero, the maximum of Llb can be achieved at λ∗ = − 2 A−1 βk . [sent-125, score-0.143]

45 k Simultaneously considering the equality λk = (bk + sk ), the low rank on B and the sparsity on S, one can rewritten Eq. [sent-127, score-0.362]

46 Lagrange multipliers µ and ν control the strengths of low rank constraint and sparsity constraint, respectively. [sent-133, score-0.211]

47 Paper [20] proposed an algorithm for RPCA based on accelerated proximal gradient (APG-RPCA), showing its advantages of efﬁciency and stability over (plain) proximal gradient. [sent-136, score-0.325]

48 Data: Term counts and labels {cd , Cd , yd }D of D docs and K classes, sparse thres. [sent-143, score-0.312]

49 05 d=1 Result: Log-space distributions: low-rank B and sparse S Initialization: randomly initialize parameters {B, S}, and variational variables {αk , ξk }k ; while not converge do if optimize variational variables then iteratively update {αk , ξk }k according to Eq. [sent-145, score-0.294]

50 , λ∗ ]; 1 K end Algorithm 1: Supervised SAM-LRB learning algorithm Consequently, the supervised SAM-LRB algorithm is speciﬁed in Algorithm 1. [sent-153, score-0.145]

51 Compared with the supervised SAGE learning algorithm in Sec. [sent-156, score-0.145]

52 3 of [10], our supervised SAM-LRB algorithm not only does not need to compute the sum of exponentials so that computing cost is saved, but also is optimized simply and efﬁciently by proximal gradient instead of using Newton updating as in SAGE. [sent-157, score-0.36]

53 , the low rank background assumption and the convex relaxation, we ﬁnd that adopting the convex relaxation also helps SAGE during optimization. [sent-161, score-0.297]

54 3 Extensions Analogous to [10], our SAM-LRB formulation can be also extended to unsupervised topic modeling scenario with latent variables, and the scenario with multifaceted class labels. [sent-162, score-0.685]

55 1 Extension 1: Unsupervised Latent Variable Model We consider how to incorporate SAM-LRB in a latent variable model of unsupervised text modelling. [sent-164, score-0.137]

56 Following topic models, there is one latent vector of topic proportions per document and one latent discrete variable per term. [sent-165, score-0.642]

57 That is, each document d is endowed with a vector of topic proportions θd ∼ Dirichlet(ρ), and each term w in this document is associated with a latent topic (d) label zw ∼ Multinomial(θd ). [sent-166, score-0.985]

58 Then the probability distribution for w is (d) p(w|zw , B, S) ∝ exp bz(d) w + sz(d) w , w (8) w (d) which only replaces the known class label yd in Eq. [sent-167, score-0.295]

59 We can combine the mean ﬁeld variational inference for latent Dirichlet allocation (LDA) [4] with the lower-bound treatment in Eq. [sent-169, score-0.171]

60 the expected count of term w in topic ˜ ˜ k, and Ck = w ckw is the topic’s expected total count throughout all words. [sent-172, score-0.248]

61 ˜ This unsupervised SAM-LRB model formulates a topic model with low rank background and sparse (d) deviation, which is learned via EM iterations. [sent-173, score-0.654]

62 Once {Ak , βk } are computed as above, the M-step to update {B, S} and variational variables {αk , ξk }k remains the same as the supervised case in Algorithm 1. [sent-175, score-0.252]

63 e, combining per-word latent topics and document labels and pursuing a structural view of labels and topics. [sent-178, score-0.273]

64 In the literature, multifaceted generative models have been studied in [1, 21, 23], and they incorporated latent switching variables that determine whether each term is generated from a topic or from a document label. [sent-179, score-0.656]

65 In [10], SAGE needs no switching variables and shows advantageous of model sparsity on multifaceted modeling. [sent-182, score-0.275]

66 More recently, paper [14] employs SAGE and discovers meaningful geographical topics in the twitter streams. [sent-183, score-0.202]

67 Applying SAM-LRB to the multifaceted scenario, we still assume the multifaceted variations are composed of low rank background and sparse deviation. [sent-184, score-0.861]

68 The log-likelihood’s lower-bound involves the sum through all topic-label pairs: J K Llb ⊤ −λ⊤ Akj λkj − βkj λkj − γkj kj = k=1 j=1 + d with λkj (d) (d) log p(zw |θd ) − log Q(zw ) [ log p(θd |ρ) − log Q(θd ) ] + (T ) bk (T ) + sk (L) + bj (L) + sj + d (I) skj . [sent-194, score-0.615]

69 , weighted by both the observed labels and posteriors of latent topics. [sent-199, score-0.132]

70 Put Λ∗(T ) into Algorithm 1 to update B (T ) and S (T ) ; • With (B (T ) , S (T ) , B (L) , S (L) ) ﬁxed, update S (I) by proximal gradient. [sent-205, score-0.122]

71 4 Experimental Results In order to test SAM-LRB in different scenarios, this section considers experiments under three tasks, namely supervised document classiﬁcation, unsupervised topic modeling, and multi-faceted modeling and classiﬁcation, respectively. [sent-206, score-0.531]

72 1 Document Classiﬁcation We ﬁrst test our SAM-LRB model in the supervised document modeling scenario and evaluate the classiﬁcation accuracy. [sent-208, score-0.291]

73 Particularly, the supervised SAM-LRB is compared with the DirichletMultinomial model and SAGE. [sent-209, score-0.145]

74 Concerning the variational variables {αi , ξi }i in the quadratic lower-bound of SAM-LRB, both cases of ﬁxing them and updating them are considered. [sent-212, score-0.189]

75 Moreover, with random and ﬁxed variational variables, the SAM-LRB model performs further better or at least comparably well. [sent-224, score-0.133]

76 If the variational variables are updated to tighten the lower-bound, the performance of SAM-LRB is substantially the best, with a 10%∼20% relative improvement over SAGE. [sent-225, score-0.13]

77 We can see that, by avoiding the log-sum-exp calculation, SAM-LRB (ﬁxed) performs more than 7 times faster than SAGE, while SAM-LRB (optimized) pays for updating the variational variables. [sent-227, score-0.133]

78 Following the same preprocessing and evaluation as in [10, 26], we have a training set of 1986 documents with 237,691 terms, and a testing set of 498 documents with 57,427 terms. [sent-234, score-0.12]

79 For all these unsupervised models, the number of latent topics is varied from 10 to 25 and then to 50. [sent-236, score-0.213]

80 With one exception happens when the topic number equals 50, SAM-LRB (ﬁxed) performs slightly worse than SAGE, mainly caused by inappropriate ﬁxed values of variational variables. [sent-243, score-0.374]

81 3 Multifaceted Modeling We then proceed to test the multifaceted modeling by SAM-LRB. [sent-246, score-0.27]

82 Same as [10], we choose a publicly-available dataset of political blogs describing the 2008 U. [sent-247, score-0.124]

83 Also, support vector machine provides a comparable accuracy of 69%, while supervised LDA [3] performs undesirably on this task. [sent-256, score-0.145]

84 In [10], SAGE is repeated 5 times for each of multiple topic numbers, and achieves its best median 2 3 http://www. [sent-257, score-0.204]

85 Using SAM-LRB (optimized), the median results out of 5 runs for each topic number are shown in Table 2. [sent-267, score-0.204]

86 The different preferences on topic numbers between SAGE and SAM-LRB may mainly come from their different assumptions on background lexical distributions. [sent-269, score-0.436]

87 Table 2: Classiﬁcation accuracy on political blogs data by SAM-LRB (optimized). [sent-270, score-0.124]

88 # topic (K) 10 20 30 40 50 accuracy (%) median out of 5 runs 67. [sent-271, score-0.204]

89 1 5 Concluding Remarks This paper studies the sparse additive model for document modeling. [sent-276, score-0.264]

90 By employing the double majorization technique, we approximate the log-sum-exponential term involved in data log-likelihood into a quadratic lower-bound. [sent-277, score-0.332]

91 With the help of this lower-bound, we are able to conveniently relax the equality constraint on background log-space distribution of SAGE [10], into a low-rank constraint, leading to our SAM-LRB model. [sent-278, score-0.232]

92 Then, after the constrained optimization is transformed into the form of RPCA’s objective function, an algorithm based on accelerated proximal gradient is adopted during learning SAM-LRB. [sent-279, score-0.248]

93 Besides the supervised version, extensions of SAM-LRB to unsupervised and multifaceted scenarios are investigated. [sent-281, score-0.46]

94 First, the accelerated proximal gradient updating needs to compute SVD decompositions, which are probably consuming for very large scale data. [sent-284, score-0.275]

95 Moreover, we may also adopt nonconjugate priors and employ nonconjugate variational inference in [27]. [sent-287, score-0.199]

96 Since nonzero elements of sparse S in SAM-LRB can be also regarded as selected feature, one may design to include them into the discriminative features, rather than only topical distributions [3]. [sent-289, score-0.139]

97 Additionally, the augmented Lagrangian and alternating direction methods [9, 29] could be also considered as alternatives to the proximal gradient optimization. [sent-290, score-0.214]

98 Staying informed: supervised and semi-supervised multi-view topical analysis of ideological pespective. [sent-295, score-0.215]

99 Smoothing proximal gradient method for general structured sparse regression. [sent-337, score-0.234]

100 Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization. [sent-494, score-0.153]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('sage', 0.543), ('zw', 0.286), ('multifaceted', 0.242), ('yd', 0.206), ('topic', 0.204), ('bk', 0.18), ('llb', 0.176), ('background', 0.154), ('majorization', 0.154), ('supervised', 0.145), ('sk', 0.143), ('proximal', 0.122), ('ki', 0.11), ('rpca', 0.107), ('variational', 0.107), ('additive', 0.103), ('kj', 0.097), ('ck', 0.093), ('rank', 0.091), ('cd', 0.081), ('document', 0.081), ('sparse', 0.08), ('double', 0.08), ('topics', 0.076), ('unsupervised', 0.073), ('blogs', 0.071), ('ak', 0.068), ('ahmed', 0.067), ('byd', 0.066), ('syd', 0.066), ('generative', 0.065), ('latent', 0.064), ('lda', 0.064), ('documents', 0.06), ('nuclear', 0.058), ('lagrangian', 0.057), ('quadratic', 0.056), ('political', 0.053), ('low', 0.052), ('twitter', 0.05), ('geographical', 0.05), ('exp', 0.049), ('accelerated', 0.049), ('dirichlet', 0.046), ('consuming', 0.046), ('lexical', 0.046), ('nonconjugate', 0.046), ('constrained', 0.045), ('bki', 0.044), ('cdw', 0.044), ('ckw', 0.044), ('ski', 0.044), ('skj', 0.044), ('equality', 0.043), ('employing', 0.042), ('posteriors', 0.042), ('label', 0.04), ('abs', 0.039), ('akj', 0.039), ('jeffreys', 0.039), ('vocabulary', 0.039), ('discovering', 0.038), ('scenario', 0.037), ('facets', 0.036), ('eisenstein', 0.036), ('ideological', 0.036), ('optimized', 0.035), ('constraint', 0.035), ('norm', 0.035), ('topical', 0.034), ('decoupling', 0.034), ('sparsity', 0.033), ('robust', 0.033), ('augmented', 0.032), ('ganesh', 0.032), ('gradient', 0.032), ('mainly', 0.032), ('bj', 0.031), ('inappropriate', 0.031), ('efforts', 0.03), ('log', 0.03), ('modeling', 0.028), ('www', 0.028), ('classi', 0.028), ('alternating', 0.028), ('deviation', 0.028), ('perplexity', 0.028), ('sparseness', 0.027), ('labels', 0.026), ('assigning', 0.026), ('discovers', 0.026), ('comparably', 0.026), ('updating', 0.026), ('proportions', 0.025), ('illustrative', 0.025), ('discriminative', 0.025), ('xi', 0.024), ('updated', 0.023), ('wright', 0.023), ('newton', 0.023)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999994 301 nips-2013-Sparse Additive Text Models with Low Rank Background

Author: Lei Shi

2 0.18417074 174 nips-2013-Lexical and Hierarchical Topic Regression

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

Abstract: Inspired by a two-level theory from political science that uniﬁes agenda setting and ideological framing, we propose supervised hierarchical latent Dirichlet allocation (S H L DA), which jointly captures documents’ multi-level topic structure and their polar response variables. Our model extends the nested Chinese restaurant processes to discover tree-structured topic hierarchies and uses both per-topic hierarchical and per-word lexical regression parameters to model response variables. S H L DA improves prediction on political afﬁliation and sentiment tasks in addition to providing insight into how topics under discussion are framed. 1 Introduction: Agenda Setting and Framing in Hierarchical Models How do liberal-leaning bloggers talk about immigration in the US? What do conservative politicians have to say about education? How do Fox News and MSNBC differ in their language about the gun debate? Such questions concern not only what, but how things are talked about. In political communication, the question of “what” falls under the heading of agenda setting theory, which concerns the issues introduced into political discourse (e.g., by the mass media) and their inﬂuence over public priorities [1]. The question of “how” concerns framing: the way the presentation of an issue reﬂects or encourages a particular perspective or interpretation [2]. For example, the rise of the “innocence frame” in the death penalty debate, emphasizing the irreversible consequence of mistaken convictions, has led to a sharp decline in the use of capital punishment in the US [3]. In its concern with the subjects or issues under discussion in political discourse, agenda setting maps neatly to topic modeling [4] as a means of discovering and characterizing those issues [5]. Interestingly, one line of communication theory seeks to unify agenda setting and framing by viewing frames as a second-level kind of agenda [1]: just as agenda setting is about which objects of discussion are salient, framing is about the salience of attributes of those objects. The key is that what communications theorists consider an attribute in a discussion can itself be an object, as well. For example, “mistaken convictions” is one attribute of the death penalty discussion, but it can also be viewed as an object of discussion in its own right. This two-level view leads naturally to the idea of using a hierarchical topic model to formalize both agendas and frames within a uniform setting. In this paper, we introduce a new model to do exactly that. The model is predictive: it represents the idea of alternative or competing perspectives via a continuous-valued response variable. Although inspired by the study of political discourse, associating texts with “perspectives” is more general and has been studied in sentiment analysis, discovery of regional variation, and value-sensitive design. We show experimentally that the model’s hierarchical structure improves prediction of perspective in both a political domain and on sentiment analysis tasks, and we argue that the topic hierarchies exposed by the model are indeed capturing structure in line with the theory that motivated the work. 1 ߨ ݉ ߠௗ ߙ ߰ௗ ߛ ‫ݐ‬ௗ௦ ‫ݖ‬ௗ௦௡ ‫ݓ‬ௗ௦௡ ܿௗ௧ ܰௗ௦ ∞ ߩ ܵௗ ‫ݕ‬ௗ ‫ܦ‬ ߱ ߟ௞ ߬௩ ܸ 1. For each node k ∈ [1, ∞) in the tree (a) Draw topic φk ∼ Dir(βk ) (b) Draw regression parameter ηk ∼ N (µ, σ) 2. For each word v ∈ [1, V ], draw τv ∼ Laplace(0, ω) 3. For each document d ∈ [1, D] (a) Draw level distribution θd ∼ GEM(m, π) (b) Draw table distribution ψd ∼ GEM(α) (c) For each table t ∈ [1, ∞), draw a path cd,t ∼ nCRP(γ) (d) For each sentence s ∈ [1, Sd ], draw a table indicator td,s ∼ Mult(ψd ) i. For each token n ∈ [1, Nd,s ] A. Draw level zd,s,n ∼ Mult(θd ) B. Draw word wd,s,n ∼ Mult(φcd,td,s ,zd,s,n ) ¯ ¯ (e) Draw response yd ∼ N (η T zd + τ T wd , ρ): ߶௞ ∞ ߤ i. zd,k = ¯ ߪ ߚ ii. wd,v = ¯ 1 Nd,· 1 Nd,· Sd s=1 Sd s=1 Nd,s n=1 I [kd,s,n = k] Nd,s n=1 I [wd,s,n = v] Figure 1: S H L DA’s generative process and plate diagram. Words w are explained by topic hierarchy φ, and response variables y are explained by per-topic regression coefﬁcients η and global lexical coefﬁcients τ . 2 S H L DA: Combining Supervision and Hierarchical Topic Structure Jointly capturing supervision and hierarchical topic structure falls under a class of models called supervised hierarchical latent Dirichlet allocation. These models take as input a set of D documents, each of which is associated with a response variable yd , and output a hierarchy of topics which is informed by yd . Zhang et al. [6] introduce the S H L DA family, focusing on a categorical response. In contrast, our novel model (which we call S H L DA for brevity), uses continuous responses. At its core, S H L DA’s document generative process resembles a combination of hierarchical latent Dirichlet allocation [7, HLDA] and the hierarchical Dirichlet process [8, HDP]. HLDA uses the nested Chinese restaurant process (nCRP(γ)), combined with an appropriate base distribution, to induce an unbounded tree-structured hierarchy of topics: general topics at the top, speciﬁc at the bottom. A document is generated by traversing this tree, at each level creating a new child (hence a new path) with probability proportional to γ or otherwise respecting the “rich-get-richer” property of a CRP. A drawback of HLDA, however, is that each document is restricted to only a single path in the tree. Recent work relaxes this restriction through different priors: nested HDP [9], nested Chinese franchises [10] or recursive CRPs [11]. In this paper, we address this problem by allowing documents to have multiple paths through the tree by leveraging information at the sentence level using the twolevel structure used in HDP. More speciﬁcally, in the HDP’s Chinese restaurant franchise metaphor, customers (i.e., tokens) are grouped by sitting at tables and each table takes a dish (i.e., topic) from a ﬂat global menu. In our S H L DA, dishes are organized in a tree-structured global menu by using the nCRP as prior. Each path in the tree is a collection of L dishes (one for each level) and is called a combo. S H L DA groups sentences of a document by assigning them to tables and associates each table with a combo, and thus, models each document as a distribution over combos.1 In S H L DA’s metaphor, customers come in a restaurant and sit at a table in groups, where each group is a sentence. A sentence wd,s enters restaurant d and selects a table t (and its associated combo) with probability proportional to the number of sentences Sd,t at that table; or, it sits at a new table with probability proportional to α. After choosing the table (indexed by td,s ), if the table is new, the group will select a combo of dishes (i.e., a path, indexed by cd,t ) from the tree menu. Once a combo is in place, each token in the sentence chooses a “level” (indexed by zd,s,n ) in the combo, which speciﬁes the topic (φkd,s,n ≡ φcd,td,s ,zd,s,n ) producing the associated observation (Figure 2). S H L DA also draws on supervised LDA [12, SLDA] associating each document d with an observable continuous response variable yd that represents the author’s perspective toward a topic, e.g., positive vs. negative sentiment, conservative vs. liberal ideology, etc. This lets us infer a multi-level topic structure informed by how topics are “framed” with respect to positions along the yd continuum. 1 We emphasize that, unlike in HDP where each table is assigned to a single dish, each table in our metaphor is associated with a combo–a collection of L dishes. We also use combo and path interchangeably. 2 Sd Sd,t ߶ଵ ߟଵ dish ߶ଵଵ ߟଵଵ ߶ଵଶ ߟଵଶ ߶ଵଵଵ ߟଵଵଵ ߶ଵଵଶ ߟଵଵଶ ߶ଵଶଵ ߟଵଶଵ ߶ଵଶଶ ߟଵଶଶ table ܿௗ௧ ‫1=ݐ‬ ‫2=ݐ‬ ‫1=ݐ‬ ‫2=ݐ‬ ‫3=ݐ‬ ‫1=ݐ‬ ‫2=ݐ‬ ‫ݐ‬ௗ௦ ‫2=ݏ 1=ݏ‬ ‫ܵ = ݏ‬ଵ ‫3=ݏ 2=ݏ 1=ݏ‬ ݀=1 ݇ௗ௦௡ ‫ܵ = ݏ‬ଶ ‫ܵ = ݏ‬஽ ݀=2 ߶ଵ ߟଵ ݀=‫ܦ‬ customer group (token) (sentence) restaurant (document) ߶ଵଵ ߟଵଵ ݀=1 ‫1=ݏ‬ ߶ଵଵଵ ߟଵଵଵ combo (path) Nd,s Nd,·,l Nd,·,>l Nd,·,≥l Mc,l Cc,l,v Cd,x,l,v φk ηk τv cd,t td,s zd,s,n kd,s,n L C+ Figure 2: S H L DA’s restaurant franchise metaphor. # sentences in document d # groups (i.e. sentences) sitting at table t in restaurant d # tokens wd,s # tokens in wd assigned to level l # tokens in wd assigned to level > l ≡ Nd,·,l + Nd,·,>l # tables at level l on path c # word type v assigned to level l on path c # word type v in vd,x assigned to level l Topic at node k Regression parameter at node k Regression parameter of word type v Path assignment for table t in restaurant d Table assignment for group wd,s Level assignment for wd,s,n Node assignment for wd,s,n (i.e., node at level zd,s,n on path cd,td,s ) Height of the tree Set of all possible paths (including new ones) of the tree Table 1: Notation used in this paper Unlike SLDA, we model the response variables using a normal linear regression that contains both pertopic hierarchical and per-word lexical regression parameters. The hierarchical regression parameters are just like topics’ regression parameters in SLDA: each topic k (here, a tree node) has a parameter ηk , and the model uses the empirical distribution over the nodes that generated a document as the regressors. However, the hierarchy in S H L DA makes it possible to discover relationships between topics and the response variable that SLDA’s simple latent space obscures. Consider, for example, a topic model trained on Congressional debates. Vanilla LDA would likely discover a healthcare category. SLDA [12] could discover a pro-Obamacare topic and an anti-Obamacare topic. S H L DA could do that and capture the fact that there are alternative perspectives, i.e., that the healthcare issue is being discussed from two ideological perspectives, along with characterizing how the higher level topic is discussed by those on both sides of that ideological debate. Sometimes, of course, words are strongly associated with extremes on the response variable continuum regardless of underlying topic structure. Therefore, in addition to hierarchical regression parameters, we include global lexical regression parameters to model the interaction between speciﬁc words and response variables. We denote the regression parameter associated with a word type v in the vocabulary as τv , and use the normalized frequency of v in the documents to be its regressor. Including both hierarchical and lexical parameters is important. For detecting ideology in the US, “liberty” is an effective indicator of conservative speakers regardless of context; however, “cost” is a conservative-leaning indicator in discussions about environmental policy but liberal-leaning in debates about foreign policy. For sentiment, “wonderful” is globally a positive word; however, “unexpected” is a positive descriptor of books but a negative one of a car’s steering. S H L DA captures these properties in a single model. 3 Posterior Inference and Optimization Given documents with observed words w = {wd,s,n } and response variables y = {yd }, the inference task is to ﬁnd the posterior distribution over: the tree structure including topic φk and regression parameter ηk for each node k, combo assignment cd,t for each table t in document d, table assignment td,s for each sentence s in a document d, and level assignment zd,s,n for each token wd,s,n . We approximate S H L DA’s posterior using stochastic EM, which alternates between a Gibbs sampling E-step and an optimization M-step. More speciﬁcally, in the E-step, we integrate out ψ, θ and φ to construct a Markov chain over (t, c, z) and alternate sampling each of them from their conditional distributions. In the M-step, we optimize the regression parameters η and τ using L-BFGS [13]. Before describing each step in detail, let us deﬁne the following probabilities. For more thorough derivations, please see the supplement. 3 • First, deﬁne vd,x as a set of tokens (e.g., a token, a sentence or a set of sentences) in document d. The conditional density of vd,x being assigned to path c given all other assignments is −d,x Γ(Cc,l,· + V βl ) L −d,x fc (vd,x ) = l=1 −d,x Γ(Cc,l,v + Cd,x,l,v + βl ) V −d,x Γ(Cc,l,· + Cd,x,l,· + V βl ) (1) −d,x Γ(Cc,l,v + βl ) v=1 where superscript −d,x denotes the same count excluding assignments of vd,x ; marginal counts −d,x are represented by ·’s. For a new path cnew , if the node does not exist, Ccnew ,l,v = 0 for all word types v. • Second, deﬁne the conditional density of the response variable yd of document d given vd,x being −d,x assigned to path c and all other assignments as gc (yd ) =  1 N Nd,· ηc,l · Cd,x,l,· + ηcd,td,s ,zd,s,n + wd,s,n ∈{wd \vd,x }  Sd Nd,s L τwd,s,n , ρ (2) s=1 n=1 l=1 where Nd,· is the total number of tokens in document d. For a new node at level l on a new path cnew , we integrate over all possible values of ηcnew ,l . Sampling t: For each group wd,s we need to sample a table td,s . The conditional distribution of a table t given wd,s and other assignments is proportional to the number of sentences sitting at t times the probability of wd,s and yd being observed under this assignment. This is P (td,s = t | rest) ∝ P (td,s = t | t−s ) · P (wd,s , yd | td,s = t, w−d,s , t−d,s , z, c, η) d ∝ −d,s −d,s −d,s Sd,t · fcd,t (wd,s ) · gcd,t (yd ), for existing table t; (3) −d,s −d,s α · c∈C + P (cd,tnew = c | c−d,s ) · fc (wd,s ) · gc (yd ), for new table tnew . For a new table tnew , we need to sum over all possible paths C + of the tree, including new ones. For example, the set C + for the tree shown in Figure 2 consists of four existing paths (ending at one of the four leaf nodes) and three possible new paths (a new leaf off of one of the three internal nodes). The prior probability of path c is: P (cd,tnew = c | c−d,s ) ∝       L l=2 −d,s Mc,l −d,s Mc,l−1 + γl−1  γl∗    −d,s M ∗ cnew ,l∗ + γl , l∗ l=2 for an existing path c; (4) −d,s Mcnew ,l , for a new path cnew which consists of an existing path −d,s Mcnew ,l−1 + γl−1 from the root to a node at level l∗ and a new node. Sampling z: After assigning a sentence wd,s to a table, we assign each token wd,s,n to a level to choose a dish from the combo. The probability of assigning wd,s,n to level l is −s,n P (zd,s,n = l | rest) ∝ P (zd,s,n = l | zd )P (wd,s,n , yd | zd,s,n = l, w−d,s,n , z −d,s,n , t, c, η) (5) The ﬁrst factor captures the probability that a customer in restaurant d is assigned to level l, conditioned on the level assignments of all other customers in restaurant d, and is equal to P (zd,s,n = −s,n l | zd ) = −d,s,n mπ + Nd,·,l −d,s,n π + Nd,·,≥l l−1 −d,s,n (1 − m)π + Nd,·,>j −d,s,n π + Nd,·,≥j j=1 , The second factor is the probability of observing wd,s,n and yd , given that wd,s,n is assigned to level −d,s,n −d,s,n l: P (wd,s,n , yd | zd,s,n = l, w−d,s,n , z −d,s,n , t, c, η) = fcd,t (wd,s,n ) · gcd,t (yd ). d,s d,s Sampling c: After assigning customers to tables and levels, we also sample path assignments for all tables. This is important since it can change the assignments of all customers sitting at a table, which leads to a well-mixed Markov chain and faster convergence. The probability of assigning table t in restaurant d to a path c is P (cd,t = c | rest) ∝ P (cd,t = c | c−d,t ) · P (wd,t , yd | cd,t = c, w−d,t , c−d,t , t, z, η) (6) where we slightly abuse the notation by using wd,t ≡ ∪{s|td,s =t} wd,s to denote the set of customers in all the groups sitting at table t in restaurant d. The ﬁrst factor is the prior probability of a path given all tables’ path assignments c−d,t , excluding table t in restaurant d and is given in Equation 4. The second factor in Equation 6 is the probability of observing wd,t and yd given the new path −d,t −d,t assignments, P (wd,t , yd | cd,t = c, w−d,t , c−d,t , t, z, η) = fc (wd,t ) · gc (yd ). 4 Optimizing η and τ : We optimize the regression parameters η and τ via the likelihood, 1 L(η, τ ) = − 2ρ D 1 ¯ ¯ (yd − η zd − τ wd ) − 2σ T d=1 T K+ 2 (ηk − µ)2 − k=1 1 ω V |τv |, (7) v=1 where K + is the number of nodes in the tree.2 This maximization is performed using L-BFGS [13]. 4 Data: Congress, Products, Films We conduct our experiments using three datasets: Congressional ﬂoor debates, Amazon product reviews, and movie reviews. For all datasets, we remove stopwords, add bigrams to the vocabulary, and ﬁlter the vocabulary using tf-idf.3 • U.S Congressional ﬂoor debates: We downloaded debates of the 109th US Congress from GovTrack4 and preprocessed them as in Thomas et al. [14]. To remove uninterestingly non-polarized debates, we ignore bills with less than 20% “Yea” votes or less than 20% “Nay” votes. Each document d is a turn (a continuous utterance by a single speaker, i.e. speech segment [14]), and its response variable yd is the ﬁrst dimension of the speaker’s DW- NOMINATE score [15], which captures the traditional left-right political distinction.5 After processing, our corpus contains 5,201 turns in the House, 3,060 turns in the Senate, and 5,000 words in the vocabulary.6 • Amazon product reviews: From a set of Amazon reviews of manufactured products such as computers, MP 3 players, GPS devices, etc. [16], we focused on the 50 most frequently reviewed products. After ﬁltering, this corpus contains 37,191 reviews with a vocabulary of 5,000 words. We use the rating associated with each review as the response variable yd .7 • Movie reviews: Our third corpus is a set of 5,006 reviews of movies [17], again using review ratings as the response variable yd , although in this corpus the ratings are normalized to the range from 0 to 1. After preprocessing, the vocabulary contains 5,000 words. 5 Evaluating Prediction S H L DA’s response variable predictions provide a formally rigorous way to assess whether it is an improvement over prior methods. We evaluate effectiveness in predicting values of the response variables for unseen documents in the three datasets. For comparison we consider these baselines: • Multiple linear regression (MLR) models the response variable as a linear function of multiple features (or regressors). Here, we consider two types of features: topic-based features and lexicallybased features. Topic-based MLR, denoted by MLR - LDA, uses the topic distributions learned by vanilla LDA as features [12], while lexically-based MLR, denoted by MLR - VOC, uses the frequencies of words in the vocabulary as features. MLR - LDA - VOC uses both features. • Support vector regression (SVM) is a discriminative method [18] that uses LDA topic distributions (SVM - LDA), word frequencies (SVM - VOC), and both (SVM - LDA - VOC) as features.8 • Supervised topic model (SLDA): we implemented SLDA using Gibbs sampling. The version of SLDA we use is slightly different from the original SLDA described in [12], in that we place a Gaussian prior N (0, 1) over the regression parameters to perform L2-norm regularization.9 For parametric models (LDA and SLDA), which require the number of topics K to be speciﬁed beforehand, we use K ∈ {10, 30, 50}. We use symmetric Dirichlet priors in both LDA and SLDA, initialize The superscript + is to denote that this number is unbounded and varies during the sampling process. To ﬁnd bigrams, we begin with bigram candidates that occur at least 10 times in the corpus and use Pearson’s χ2 -test to ﬁlter out those that have χ2 -value less than 5, which corresponds to a signiﬁcance level of 0.025. We then treat selected bigrams as single word types and add them to the vocabulary. 2 3 4 http://www.govtrack.us/data/us/109/ 5 Scores were downloaded from http://voteview.com/dwnomin_joint_house_and_senate.htm 6 Data will be available after blind review. 7 The ratings can range from 1 to 5, but skew positive. 8 9 http://svmlight.joachims.org/ This performs better than unregularized SLDA in our experiments. 5 Floor Debates House-Senate Senate-House PCC ↑ MSE ↓ PCC ↑ MSE ↓ Amazon Reviews PCC ↑ MSE ↓ Movie Reviews PCC ↑ MSE ↓ SVM - LDA 10 SVM - LDA 30 SVM - LDA 50 SVM - VOC SVM - LDA - VOC 0.173 0.172 0.169 0.336 0.256 0.861 0.840 0.832 1.549 0.784 0.08 0.155 0.215 0.131 0.246 1.247 1.183 1.135 1.467 1.101 0.157 0.277 0.245 0.373 0.371 1.241 1.091 1.130 0.972 0.965 0.327 0.365 0.395 0.584 0.585 0.970 0.938 0.906 0.681 0.678 MLR - LDA 10 MLR - LDA 30 MLR - LDA 50 MLR - VOC MLR - LDA - VOC 0.163 0.160 0.150 0.322 0.319 0.735 0.737 0.741 0.889 0.873 0.068 0.162 0.248 0.191 0.194 1.151 1.125 1.081 1.124 1.120 0.143 0.258 0.234 0.408 0.410 1.034 1.065 1.114 0.869 0.860 0.328 0.367 0.389 0.568 0.581 0.957 0.936 0.914 0.721 0.702 SLDA 10 SLDA 30 SLDA 50 0.154 0.174 0.254 0.729 0.793 0.897 0.090 0.128 0.245 1.145 1.188 1.184 0.270 0.357 0.241 1.113 1.146 1.939 0.383 0.433 0.503 0.953 0.852 0.772 S H L DA 0.356 0.753 0.303 1.076 0.413 0.891 0.597 0.673 Models Table 2: Regression results for Pearson’s correlation coefﬁcient (PCC, higher is better (↑)) and mean squared error (MSE, lower is better (↓)). Results on Amazon product reviews and movie reviews are averaged over 5 folds. Subscripts denote the number of topics for parametric models. For SVM - LDA - VOC and MLR - LDA - VOC, only best results across K ∈ {10, 30, 50} are reported. Best results are in bold. the Dirichlet hyperparameters to 0.5, and use slice sampling [19] for updating hyperparameters. For SLDA , the variance of the regression is set to 0.5. For S H L DA , we use trees with maximum depth of three. We slice sample m, π, β and γ, and ﬁx µ = 0, σ = 0.5, ω = 0.5 and ρ = 0.5. We found that the following set of initial hyperparameters works reasonably well for all the datasets in our experiments: m = 0.5, π = 100, β = (1.0, 0.5, 0.25), γ = (1, 1), α = 1. We also set the regression parameter of the root node to zero, which speeds inference (since it is associated with every document) and because it is reasonable to assume that it would not change the response variable. To compare the performance of different methods, we compute Pearson’s correlation coefﬁcient (PCC) and mean squared error (MSE) between the true and predicted values of the response variables and average over 5 folds. For the Congressional debate corpus, following Yu et al. [20], we use documents in the House to train and test on documents in the Senate and vice versa. Results and analysis Table 2 shows the performance of all models on our three datasets. Methods that only use topic-based features such as SVM - LDA and MLR - LDA do poorly. Methods only based on lexical features like SVM - VOC and MLR - VOC outperform methods that are based only on topic features signiﬁcantly for the two review datasets, but are comparable or worse on congressional debates. This suggests that reviews have more highly discriminative words than political speeches (Table 3). Combining topic-based and lexically-based features improves performance, which supports our choice of incorporating both per-topic and per-word regression parameters in S H L DA. In all cases, S H L DA achieves strong performance results. For the two cases where S H L DA was second best in MSE score (Amazon reviews and House-Senate), it outperforms other methods in PCC. Doing well in PCC for these two datasets is important since achieving low MSE is relatively easier due to the response variables’ bimodal distribution in the ﬂoor debates and positively-skewed distribution in Amazon reviews. For the ﬂoor debate dataset, the results of the House-Senate experiment are generally better than those of the Senate-House experiment, which is consistent with previous results [20] and is explained by the greater number of debates in the House. 6 Qualitative Analysis: Agendas and Framing/Perspective Although a formal coherence evaluation [21] remains a goal for future work, a qualitative look at the topic hierarchy uncovered by the model suggests that it is indeed capturing agenda/framing structure as discussed in Section 1. In Figure 3, a portion of the topic hierarchy induced from the Congressional debate corpus, Nodes A and B illustrate agendas—issues introduced into political discourse—associated with a particular ideology: Node A focuses on the hardships of the poorer victims of hurricane Katrina and is associated with Democrats, and text associated with Node E discusses a proposed constitutional amendment to ban ﬂag burning and is associated with Republicans. Nodes C and D, children of a neutral “tax” topic, reveal how parties frame taxes as gains in terms of new social services (Democrats) and losses for job creators (Republicans). 6 E ﬂag constitution freedom supreme_court elections rights continuity american_ﬂag constitutional_amendm ent gses credit_rating fannie_mae regulator freddie_mac market ﬁnancial_services agencies competition investors fannie bill speaker time amendment chairman people gentleman legislation congress support R:1.1 R:0 A minimum_wage commission independent_commissio n investigate hurricane_katrina increase investigation R:1.0 B percent tax economy estate_tax capital_gains money taxes businesses families tax_cuts pay tax_relief social_security affordable_housing housing manager fund activities funds organizations voter_registration faithbased nonproﬁts R:0.4 D:1.7 C death_tax jobs businesses business family_businesses equipment productivity repeal_permanency employees capital farms D REPUBLICAN billion budget children cuts debt tax_cuts child_support deﬁcit education students health_care republicans national_debt R:4.3 D:2.2 DEMOCRAT D:4.5 Figure 3: Topics discovered from Congressional ﬂoor debates. Many ﬁrst-level topics are bipartisan (purple), while lower level topics are associated with speciﬁc ideologies (Democrats blue, Republicans red). For example, the “tax” topic (B) is bipartisan, but its Democratic-leaning child (D) focuses on social goals supported by taxes (“children”, “education”, “health care”), while its Republican-leaning child (C) focuses on business implications (“death tax”, “jobs”, “businesses”). The number below each topic denotes the magnitude of the learned regression parameter associated with that topic. Colors and the numbers beneath each topic show the regression parameter η associated with the topic. Figure 4 shows the topic structure discovered by S H L DA in the review corpus. Nodes at higher levels are relatively neutral, with relatively small regression parameters.10 These nodes have general topics with no speciﬁc polarity. However, the bottom level clearly illustrates polarized positive/negative perspective. For example, Node A concerns washbasins for infants, and has two polarized children nodes: reviewers take a positive perspective when their children enjoy the product (Node B: “loves”, “splash”, “play”) but have negative reactions when it leaks (Node C: “leak(s/ed/ing)”). transmitter ipod car frequency iriver product transmitters live station presets itrip iriver_aft charges international_mode driving P:6.6 tried waste batteries tunecast rabbit_ears weak terrible antenna hear returned refund returning item junk return A D router setup network expander set signal wireless connect linksys connection house wireless_router laptop computer wre54g N:2.2 N:1.0 tivo adapter series adapters phone_line tivo_wireless transfer plugged wireless_adapter tivos plug dvr tivo_series tivo_box tivo_unit P:5.1 tub baby water bath sling son daughter sit bathtub sink newborn months bath_tub bathe bottom N:8.0 months loves hammock splash love baby drain eurobath hot ﬁts wash play infant secure slip P:7.5 NEGATIVE N:0 N:2.7 B POSITIVE time bought product easy buy love using price lot able set found purchased money months transmitter car static ipod radio mp3_player signal station sound music sound_quality volume stations frequency frequencies C leaks leaked leak leaking hard waste snap suction_cups lock tabs difﬁcult bottom tub_leaks properly ring N:8.9 monitor radio weather_radio night baby range alerts sound sony house interference channels receiver static alarm N:1.7 hear feature static monitors set live warning volume counties noise outside alert breathing rechargeable_battery alerts P:6.2 version hours phone F ﬁrmware told spent linksys tech_support technical_supportcusto mer_service range_expander support return N:10.6 E router ﬁrmware ddwrt wrt54gl version wrt54g tomato linksys linux routers ﬂash versions browser dlink stable P:4.8 z22 palm pda palm_z22 calendar software screen contacts computer device sync information outlook data programs N:1.9 headphones sound pair bass headset sound_quality ear ears cord earbuds comfortable hear head earphones ﬁt N:1.3 appointments organized phone lists handheld organizer photos etc pictures memos track bells books purse whistles P:5.8 noise_canceling noise sony exposed noise_cancellation stopped wires warranty noise_cancelling bud pay white_noise disappointed N:7.6 bottles bottle baby leak nipples nipple avent avent_bottles leaking son daughter formula leaks gas milk comfortable sound phones sennheiser bass px100 px100s phone headset highs portapros portapro price wear koss N:2.0 leak formula bottles_leak feeding leaked brown frustrating started clothes waste newborn playtex_ventaire soaked matter N:7.9 P:5.7 nipple breast nipples dishwasher ring sippy_cups tried breastfeed screwed breastfeeding nipple_confusion avent_system bottle P:6.4 Figure 4: Topics discovered from Amazon reviews. Higher topics are general, while lower topics are more speciﬁc. The polarity of the review is encoded in the color: red (negative) to blue (positive). Many of the ﬁrstlevel topics have no speciﬁc polarity and are associated with a broad class of products such as “routers” (Node D). However, the lowest topics in the hierarchy are often polarized; one child topic of “router” focuses on upgradable ﬁrmware such as “tomato” and “ddwrt” (Node E, positive) while another focuses on poor “tech support” and “customer service” (Node F, negative). The number below each topic is the regression parameter learned with that topic. In addition to the per-topic regression parameters, S H L DA also associates each word with a lexical regression parameter τ . Table 3 shows the top ten words with highest and lowest τ . The results are unsuprising, although the lexical regression for the Congressional debates is less clear-cut than other 10 All of the nodes at the second level have slightly negative values for the regression parameters mainly due to the very skewed distribution of the review ratings in Amazon. 7 datasets. As we saw in Section 5, for similar datasets, S H L DA’s context-speciﬁc regression is more useful when global lexical weights do not readily differentiate documents. Dataset Floor Debates Amazon Reviews Movie Reviews Top 10 words with positive weights bringing, private property, illegally, tax relief, regulation, mandates, constitutional, committee report, illegal alien highly recommend, pleased, love, loves, perfect, easy, excellent, amazing, glad, happy hilarious, fast, schindler, excellent, motion pictures, academy award, perfect, journey, fortunately, ability Top 10 words with negative weights bush administration, strong opposition, ranking, republicans, republican leadership, secret, discriminate, majority, undermine waste, returned, return, stopped, leak, junk, useless, returning, refund, terrible bad, unfortunately, supposed, waste, mess, worst, acceptable, awful, suppose, boring Table 3: Top words based on the global lexical regression coefﬁcient, τ . For the ﬂoor debates, positive τ ’s are Republican-leaning while negative τ ’s are Democrat-leaning. 7 Related Work S H L DA joins a family of LDA extensions that introduce hierarchical topics, supervision, or both. Owing to limited space, we focus here on related work that combines the two. Petinot et al. [22] propose hierarchical Labeled LDA (hLLDA), which leverages an observed document ontology to learn topics in a tree structure; however, hLLDA assumes that the underlying tree structure is known a priori. SSHLDA [23] generalizes hLLDA by allowing the document hierarchy labels to be partially observed, with unobserved labels and topic tree structure then inferred from the data. Boyd-Graber and Resnik [24] used hierarchical distributions within topics to learn topics across languages. In addition to these “upstream” models [25], Perotte et al. [26] propose a “downstream” model called HSLDA , which jointly models documents’ hierarchy of labels and topics. HSLDA ’s topic structure is ﬂat, however, and the response variable is a hierarchy of labels associated with each document, unlike S H L DA’s continuous response variable. Finally, another body related body of work includes models that jointly capture topics and other facets such as ideologies/perspectives [27, 28] and sentiments/opinions [29], albeit with discrete rather than continuously valued responses. Computational modeling of sentiment polarity is a voluminous ﬁeld [30], and many computational political science models describe agendas [5] and ideology [31]. Looking at framing or bias at the sentence level, Greene and Resnik [32] investigate the role of syntactic structure in framing, Yano et al. [33] look at lexical indications of sentence-level bias, and Recasens et al. [34] develop linguistically informed sentence-level features for identifying bias-inducing words. 8 Conclusion We have introduced S H L DA, a model that associates a continuously valued response variable with hierarchical topics to capture both the issues under discussion and alternative perspectives on those issues. The two-level structure improves predictive performance over existing models on multiple datasets, while also adding potentially insightful hierarchical structure to the topic analysis. Based on a preliminary qualitative analysis, the topic hierarchy exposed by the model plausibly captures the idea of agenda setting, which is related to the issues that get discussed, and framing, which is related to authors’ perspectives on those issues. We plan to analyze the topic structure produced by S H L DA with political science collaborators and more generally to study how S H L DA and related models can help analyze and discover useful insights from political discourse. Acknowledgments This research was supported in part by NSF under grant #1211153 (Resnik) and #1018625 (BoydGraber and Resnik). Any opinions, ﬁndings, conclusions, or recommendations expressed here are those of the authors and do not necessarily reﬂect the view of the sponsor. 8 References [1] McCombs, M. The agenda-setting role of the mass media in the shaping of public opinion. North, 2009(05-12):21, 2002. [2] McCombs, M., S. Ghanem. The convergence of agenda setting and framing. In Framing public life. 2001. [3] Baumgartner, F. R., S. L. De Boef, A. E. Boydstun. The decline of the death penalty and the discovery of innocence. Cambridge University Press, 2008. [4] Blei, D. M., A. Ng, M. Jordan. Latent Dirichlet allocation. JMLR, 3, 2003. [5] Grimmer, J. A Bayesian hierarchical topic model for political texts: Measuring expressed agendas in Senate press releases. Political Analysis, 18(1):1–35, 2010. [6] Zhang, J. Explore objects and categories in unexplored environments based on multimodal data. Ph.D. thesis, University of Hamburg, 2012. [7] Blei, D. M., T. L. Grifﬁths, M. I. Jordan. The nested Chinese restaurant process and Bayesian nonparametric inference of topic hierarchies. J. ACM, 57(2), 2010. [8] Teh, Y. W., M. I. Jordan, M. J. Beal, et al. Hierarchical Dirichlet processes. JASA, 101(476), 2006. [9] Paisley, J. W., C. Wang, D. M. Blei, et al. Nested hierarchical Dirichlet processes. arXiv:1210.6738, 2012. [10] Ahmed, A., L. Hong, A. Smola. The nested Chinese restaurant franchise process: User tracking and document modeling. In ICML. 2013. [11] Kim, J. H., D. Kim, S. Kim, et al. Modeling topic hierarchies with the recursive Chinese restaurant process. In CIKM, pages 783–792. 2012. [12] Blei, D. M., J. D. McAuliffe. Supervised topic models. In NIPS. 2007. [13] Liu, D., J. Nocedal. On the limited memory BFGS method for large scale optimization. Math. Prog., 1989. [14] Thomas, M., B. Pang, L. Lee. Get out the vote: Determining support or opposition from Congressional ﬂoor-debate transcripts. In EMNLP. 2006. [15] Lewis, J. B., K. T. Poole. Measuring bias and uncertainty in ideal point estimates via the parametric bootstrap. Political Analysis, 12(2), 2004. [16] Jindal, N., B. Liu. Opinion spam and analysis. In WSDM. 2008. [17] Pang, B., L. Lee. Seeing stars: Exploiting class relationships for sentiment categorization with respect to rating scales. In ACL. 2005. [18] Joachims, T. Making large-scale SVM learning practical. In Adv. in Kernel Methods - SVM. 1999. [19] Neal, R. M. Slice sampling. Annals of Statistics, 31:705–767, 2003. [20] Yu, B., D. Diermeier, S. Kaufmann. Classifying party afﬁliation from political speech. JITP, 2008. [21] Chang, J., J. Boyd-Graber, C. Wang, et al. Reading tea leaves: How humans interpret topic models. In NIPS. 2009. [22] Petinot, Y., K. McKeown, K. Thadani. A hierarchical model of web summaries. In HLT. 2011. [23] Mao, X., Z. Ming, T.-S. Chua, et al. SSHLDA: A semi-supervised hierarchical topic model. In EMNLP. 2012. [24] Boyd-Graber, J., P. Resnik. Holistic sentiment analysis across languages: Multilingual supervised latent Dirichlet allocation. In EMNLP. 2010. [25] Mimno, D. M., A. McCallum. Topic models conditioned on arbitrary features with Dirichlet-multinomial regression. In UAI. 2008. [26] Perotte, A. J., F. Wood, N. Elhadad, et al. Hierarchically supervised latent Dirichlet allocation. In NIPS. 2011. [27] Ahmed, A., E. P. Xing. Staying informed: Supervised and semi-supervised multi-view topical analysis of ideological perspective. In EMNLP. 2010. [28] Eisenstein, J., A. Ahmed, E. P. Xing. Sparse additive generative models of text. In ICML. 2011. [29] Jo, Y., A. H. Oh. Aspect and sentiment uniﬁcation model for online review analysis. In WSDM. 2011. [30] Pang, B., L. Lee. Opinion Mining and Sentiment Analysis. Now Publishers Inc, 2008. [31] Monroe, B. L., M. P. Colaresi, K. M. Quinn. Fightin’words: Lexical feature selection and evaluation for identifying the content of political conﬂict. Political Analysis, 16(4):372–403, 2008. [32] Greene, S., P. Resnik. More than words: Syntactic packaging and implicit sentiment. In NAACL. 2009. [33] Yano, T., P. Resnik, N. A. Smith. Shedding (a thousand points of) light on biased language. In NAACL-HLT Workshop on Creating Speech and Language Data with Amazon’s Mechanical Turk. 2010. [34] Recasens, M., C. Danescu-Niculescu-Mizil, D. Jurafsky. Linguistic models for analyzing and detecting biased language. In ACL. 2013. 9

3 0.11742663 70 nips-2013-Contrastive Learning Using Spectral Methods

Author: James Y. Zou, Daniel Hsu, David C. Parkes, Ryan P. Adams

Abstract: In many natural settings, the analysis goal is not to characterize a single data set in isolation, but rather to understand the difference between one set of observations and another. For example, given a background corpus of news articles together with writings of a particular author, one may want a topic model that explains word patterns and themes speciﬁc to the author. Another example comes from genomics, in which biological signals may be collected from different regions of a genome, and one wants a model that captures the differential statistics observed in these regions. This paper formalizes this notion of contrastive learning for mixture models, and develops spectral algorithms for inferring mixture components speciﬁc to a foreground data set when contrasted with a background data set. The method builds on recent moment-based estimators and tensor decompositions for latent variable models, and has the intuitive feature of using background data statistics to appropriately modify moments estimated from foreground data. A key advantage of the method is that the background data need only be coarsely modeled, which is important when the background is too complex, noisy, or not of interest. The method is demonstrated on applications in contrastive topic modeling and genomic sequence analysis. 1

4 0.11608213 287 nips-2013-Scalable Inference for Logistic-Normal Topic Models

Author: Jianfei Chen, June Zhu, Zi Wang, Xun Zheng, Bo Zhang

Abstract: Logistic-normal topic models can effectively discover correlation structures among latent topics. However, their inference remains a challenge because of the non-conjugacy between the logistic-normal prior and multinomial topic mixing proportions. Existing algorithms either make restricting mean-ﬁeld assumptions or are not scalable to large-scale applications. This paper presents a partially collapsed Gibbs sampling algorithm that approaches the provably correct distribution by exploring the ideas of data augmentation. To improve time efﬁciency, we further present a parallel implementation that can deal with large-scale applications and learn the correlation structures of thousands of topics from millions of documents. Extensive empirical results demonstrate the promise. 1

5 0.1160157 353 nips-2013-When are Overcomplete Topic Models Identifiable? Uniqueness of Tensor Tucker Decompositions with Structured Sparsity

Author: Anima Anandkumar, Daniel Hsu, Majid Janzamin, Sham M. Kakade

Abstract: Overcomplete latent representations have been very popular for unsupervised feature learning in recent years. In this paper, we specify which overcomplete models can be identiﬁed given observable moments of a certain order. We consider probabilistic admixture or topic models in the overcomplete regime, where the number of latent topics can greatly exceed the size of the observed word vocabulary. While general overcomplete topic models are not identiﬁable, we establish generic identiﬁability under a constraint, referred to as topic persistence. Our sufﬁcient conditions for identiﬁability involve a novel set of “higher order” expansion conditions on the topic-word matrix or the population structure of the model. This set of higher-order expansion conditions allow for overcomplete models, and require the existence of a perfect matching from latent topics to higher order observed words. We establish that random structured topic models are identiﬁable w.h.p. in the overcomplete regime. Our identiﬁability results allow for general (non-degenerate) distributions for modeling the topic proportions, and thus, we can handle arbitrarily correlated topics in our framework. Our identiﬁability results imply uniqueness of a class of tensor decompositions with structured sparsity which is contained in the class of Tucker decompositions, but is more general than the Candecomp/Parafac (CP) decomposition. Keywords: Overcomplete representation, admixture models, generic identiﬁability, tensor decomposition.

6 0.1126247 274 nips-2013-Relevance Topic Model for Unstructured Social Group Activity Recognition

7 0.10505725 345 nips-2013-Variance Reduction for Stochastic Gradient Optimization

8 0.10366781 88 nips-2013-Designed Measurements for Vector Count Data

9 0.10195021 229 nips-2013-Online Learning of Nonparametric Mixture Models via Sequential Variational Approximation

10 0.096338421 56 nips-2013-Better Approximation and Faster Algorithm Using the Proximal Average

11 0.092122033 10 nips-2013-A Latent Source Model for Nonparametric Time Series Classification

12 0.090859599 75 nips-2013-Convex Two-Layer Modeling

13 0.087234676 285 nips-2013-Robust Transfer Principal Component Analysis with Rank Constraints

14 0.084707506 233 nips-2013-Online Robust PCA via Stochastic Optimization

15 0.081907868 232 nips-2013-Online PCA for Contaminated Data

16 0.080805466 318 nips-2013-Structured Learning via Logistic Regression

17 0.075905472 312 nips-2013-Stochastic Gradient Riemannian Langevin Dynamics on the Probability Simplex

18 0.075737 321 nips-2013-Supervised Sparse Analysis and Synthesis Operators

19 0.074409321 98 nips-2013-Documents as multiple overlapping windows into grids of counts

20 0.070754379 65 nips-2013-Compressive Feature Learning

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.179), (1, 0.083), (2, -0.008), (3, 0.04), (4, 0.055), (5, 0.003), (6, 0.031), (7, 0.066), (8, 0.105), (9, -0.052), (10, -0.036), (11, 0.148), (12, 0.0), (13, 0.026), (14, -0.013), (15, -0.119), (16, 0.168), (17, 0.005), (18, 0.034), (19, -0.108), (20, -0.044), (21, -0.052), (22, 0.099), (23, 0.065), (24, 0.073), (25, -0.194), (26, 0.13), (27, -0.009), (28, -0.046), (29, 0.085), (30, 0.025), (31, 0.04), (32, -0.053), (33, -0.007), (34, 0.013), (35, -0.088), (36, 0.012), (37, 0.057), (38, -0.016), (39, -0.072), (40, -0.021), (41, -0.029), (42, -0.028), (43, -0.022), (44, 0.028), (45, 0.029), (46, 0.093), (47, 0.017), (48, 0.113), (49, -0.006)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.93668139 301 nips-2013-Sparse Additive Text Models with Low Rank Background

Author: Lei Shi

2 0.75075847 287 nips-2013-Scalable Inference for Logistic-Normal Topic Models

Author: Jianfei Chen, June Zhu, Zi Wang, Xun Zheng, Bo Zhang

3 0.74637961 174 nips-2013-Lexical and Hierarchical Topic Regression

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

4 0.71139145 274 nips-2013-Relevance Topic Model for Unstructured Social Group Activity Recognition

Author: Fang Zhao, Yongzhen Huang, Liang Wang, Tieniu Tan

Abstract: Unstructured social group activity recognition in web videos is a challenging task due to 1) the semantic gap between class labels and low-level visual features and 2) the lack of labeled training data. To tackle this problem, we propose a “relevance topic model” for jointly learning meaningful mid-level representations upon bagof-words (BoW) video representations and a classiﬁer with sparse weights. In our approach, sparse Bayesian learning is incorporated into an undirected topic model (i.e., Replicated Softmax) to discover topics which are relevant to video classes and suitable for prediction. Rectiﬁed linear units are utilized to increase the expressive power of topics so as to explain better video data containing complex contents and make variational inference tractable for the proposed model. An efﬁcient variational EM algorithm is presented for model parameter estimation and inference. Experimental results on the Unstructured Social Activity Attribute dataset show that our model achieves state of the art performance and outperforms other supervised topic model in terms of classiﬁcation accuracy, particularly in the case of a very small number of labeled training videos. 1

5 0.68219191 70 nips-2013-Contrastive Learning Using Spectral Methods

Author: James Y. Zou, Daniel Hsu, David C. Parkes, Ryan P. Adams

6 0.63917691 345 nips-2013-Variance Reduction for Stochastic Gradient Optimization

7 0.63362557 312 nips-2013-Stochastic Gradient Riemannian Langevin Dynamics on the Probability Simplex

8 0.62574649 353 nips-2013-When are Overcomplete Topic Models Identifiable? Uniqueness of Tensor Tucker Decompositions with Structured Sparsity

9 0.61616606 98 nips-2013-Documents as multiple overlapping windows into grids of counts

10 0.55937117 317 nips-2013-Streaming Variational Bayes

11 0.52959269 88 nips-2013-Designed Measurements for Vector Count Data

12 0.51818448 294 nips-2013-Similarity Component Analysis

13 0.46394947 10 nips-2013-A Latent Source Model for Nonparametric Time Series Classification

14 0.43201748 229 nips-2013-Online Learning of Nonparametric Mixture Models via Sequential Variational Approximation

15 0.4139156 115 nips-2013-Factorized Asymptotic Bayesian Inference for Latent Feature Models

16 0.4096539 249 nips-2013-Polar Operators for Structured Sparse Estimation

17 0.40457991 65 nips-2013-Compressive Feature Learning

18 0.40323371 75 nips-2013-Convex Two-Layer Modeling

19 0.40244266 13 nips-2013-A Scalable Approach to Probabilistic Latent Space Inference of Large-Scale Networks

20 0.39946869 187 nips-2013-Memoized Online Variational Inference for Dirichlet Process Mixture Models

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(16, 0.034), (33, 0.135), (34, 0.109), (41, 0.06), (49, 0.084), (55, 0.227), (56, 0.088), (70, 0.043), (85, 0.035), (89, 0.032), (93, 0.071)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.94230181 174 nips-2013-Lexical and Hierarchical Topic Regression

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

2 0.82655746 59 nips-2013-Blind Calibration in Compressed Sensing using Message Passing Algorithms

Author: Christophe Schulke, Francesco Caltagirone, Florent Krzakala, Lenka Zdeborova

Abstract: Compressed sensing (CS) is a concept that allows to acquire compressible signals with a small number of measurements. As such it is very attractive for hardware implementations. Therefore, correct calibration of the hardware is a central issue. In this paper we study the so-called blind calibration, i.e. when the training signals that are available to perform the calibration are sparse but unknown. We extend the approximate message passing (AMP) algorithm used in CS to the case of blind calibration. In the calibration-AMP, both the gains on the sensors and the elements of the signals are treated as unknowns. Our algorithm is also applicable to settings in which the sensors distort the measurements in other ways than multiplication by a gain, unlike previously suggested blind calibration algorithms based on convex relaxations. We study numerically the phase diagram of the blind calibration problem, and show that even in cases where convex relaxation is possible, our algorithm requires a smaller number of measurements and/or signals in order to perform well. 1

same-paper 3 0.79181713 301 nips-2013-Sparse Additive Text Models with Low Rank Background

Author: Lei Shi

4 0.73325759 298 nips-2013-Small-Variance Asymptotics for Hidden Markov Models

Author: Anirban Roychowdhury, Ke Jiang, Brian Kulis

Abstract: Small-variance asymptotics provide an emerging technique for obtaining scalable combinatorial algorithms from rich probabilistic models. We present a smallvariance asymptotic analysis of the Hidden Markov Model and its inﬁnite-state Bayesian nonparametric extension. Starting with the standard HMM, we ﬁrst derive a “hard” inference algorithm analogous to k-means that arises when particular variances in the model tend to zero. This analysis is then extended to the Bayesian nonparametric case, yielding a simple, scalable, and ﬂexible algorithm for discrete-state sequence data with a non-ﬁxed number of states. We also derive the corresponding combinatorial objective functions arising from our analysis, which involve a k-means-like term along with penalties based on state transitions and the number of states. A key property of such algorithms is that— particularly in the nonparametric setting—standard probabilistic inference algorithms lack scalability and are heavily dependent on good initialization. A number of results on synthetic and real data sets demonstrate the advantages of the proposed framework. 1

5 0.69684923 121 nips-2013-Firing rate predictions in optimal balanced networks

Author: David G. Barrett, Sophie Denève, Christian K. Machens

Abstract: How are ﬁring rates in a spiking network related to neural input, connectivity and network function? This is an important problem because ﬁring rates are a key measure of network activity, in both the study of neural computation and neural network dynamics. However, it is a difﬁcult problem, because the spiking mechanism of individual neurons is highly non-linear, and these individual neurons interact strongly through connectivity. We develop a new technique for calculating ﬁring rates in optimal balanced networks. These are particularly interesting networks because they provide an optimal spike-based signal representation while producing cortex-like spiking activity through a dynamic balance of excitation and inhibition. We can calculate ﬁring rates by treating balanced network dynamics as an algorithm for optimising signal representation. We identify this algorithm and then calculate ﬁring rates by ﬁnding the solution to the algorithm. Our ﬁring rate calculation relates network ﬁring rates directly to network input, connectivity and function. This allows us to explain the function and underlying mechanism of tuning curves in a variety of systems. 1

6 0.69169563 22 nips-2013-Action is in the Eye of the Beholder: Eye-gaze Driven Model for Spatio-Temporal Action Localization

7 0.69132411 303 nips-2013-Sparse Overlapping Sets Lasso for Multitask Learning and its Application to fMRI Analysis

8 0.68907458 64 nips-2013-Compete to Compute

9 0.68676174 262 nips-2013-Real-Time Inference for a Gamma Process Model of Neural Spiking

10 0.6854468 77 nips-2013-Correlations strike back (again): the case of associative memory retrieval

11 0.68449271 236 nips-2013-Optimal Neural Population Codes for High-dimensional Stimulus Variables

12 0.68331665 141 nips-2013-Inferring neural population dynamics from multiple partial recordings of the same neural circuit

13 0.68270808 5 nips-2013-A Deep Architecture for Matching Short Texts

14 0.68160844 345 nips-2013-Variance Reduction for Stochastic Gradient Optimization

15 0.67931724 221 nips-2013-On the Expressive Power of Restricted Boltzmann Machines

16 0.67882991 114 nips-2013-Extracting regions of interest from biological images with convolutional sparse block coding

17 0.67668438 287 nips-2013-Scalable Inference for Logistic-Normal Topic Models

18 0.6752845 49 nips-2013-Bayesian Inference and Online Experimental Design for Mapping Neural Microcircuits

19 0.67509806 99 nips-2013-Dropout Training as Adaptive Regularization

20 0.67417479 183 nips-2013-Mapping paradigm ontologies to and from the brain