Modeling Relational Events via Latent Classes

Citation

Christopher DuBois, Padhraic Smyth. Modeling Relational Events via Latent Classes. KDD 2010

Online version

download here

Summary

Many social network activities can be described as a series of dyadic events. An event in this paper is defined as a triple of (sender, receiver, event_type). Authors assume that such events are generated by some latent class and in the paper they proposed a graphical model to identify the latent class as well as dyadic events with the inference implementation of Gibbs sampling and Expectation-Maximization methods.

Methodology

It's assumed that relational events are generated by following process:

• Draw the class distribution ${\bar {\pi }}$ ~ Dirichlet(${\bar {a}}$)
• Draw distributions:

$\theta _{c}$ ~ Dirichlet($\beta$)

$\phi _{c}$ ~ Dirichlet($\gamma$)

$\psi _{c}$ ~ Dirichlet($\delta$)

for all c in {1...C}

• For each event

(a) Draw $c$ ~ Multinomial(${\bar {\pi }}$), the event’s class

(b) Draw $s|c$ ~ Multinomial(${\bar {\theta _{c}}}$), the event’s sender

(c) Draw $r|c$ ~ Multinomial(${\bar {\phi _{c}}}$), the event’s receiver

(d) Draw $a|c$ ~ Multinomial(${\bar {\psi _{c}}}$), the event’s typ

LDA does not explicitly model the temporal relationship. There are two other common ways to capture the temporal information: the Dynamic Topic Model (Blei and Lafferty, 2006), representing each years' documents as generated from a normal distribution centroid over topics, with the following year's centroid generated from the preceding year's; the Topics over Time Model (Wang and McCallum, 2006), assuming that each document chooses its own time stamp based on a topic-specific beta distribution. But both of these models impose constraints on the time periods: the Dynamic Topic Model penalizes large changes from year to year while the beta distribution in Topics over Time Model are relatively inflexible.

So in this paper the authors first apply the LDA (implemented in Gibbs Sampling) at each year. Then they perform post hoc calculations based on the observed probability of each topic given the current year. Define ${\hat {p}}(z|y)$ as the empirical probability that an arbitrary paper $d$ written in year $y$ was about topic $z$:

${\hat {p}}(z|y)={\frac {1}{C}}\sum _{d:t_{d}=y}\sum _{z'_{i}\in d}I(z'_{i}=z)$

where $I$ is the indicator function, $t_{d}$ is the data document $d$ was written, ${\hat {p}}(z|y)$ is set to a constant $1/C$.

Define ${\hat {p}}(z|c)$ as the empirical distribution of a topic $z$ at a conference $c$:

${\hat {p}}(z|c)={\frac {1}{C}}\sum _{d:c_{d}=c}\sum _{z'_{i}\in d}I(z'_{i}=z)$.

Define topic entropy to measure the breadth of a conference:

$H(z|c,y)=-\sum _{i=1}^{K}{\hat {p}}(z_{i}|c,y)log{\hat {p}}(z_{i}|c,y)$.

Finally use Jensen-Shannon divergence(JS divergence) to investigate whether or not the topic distributions of the conferences are converging:

$D_{JS}(P||Q)={\frac {1}{2}}D_{KL}(P||R)+{\frac {1}{2}}D_{KL}(Q||R)$

$R={\frac {1}{2}}(P+Q)$

Data

ACL Antology

Experimental Result

• Historical Trends in Computational Linguistics

To visualize some trend, they show the probability mass asscociated with various topics over time, plotted as (a smoothed version of) ${\hat {p}}(z|y)$. The topics becoming more prominent are such as classification, probabilistic models, stat. parsing, stat. MT and lex. sem, while the topics declined are computational semantics, conceptual semantics and plan-based dialogue and discourse.

• Is Computational Linguistics Becoming More Applied?

Look at trends over time for some applications such as Machine Translation, Spelling Correction, Dialogue Systems etc and found there is a clear trend toward an increase in applications over time.

• Differences and Similarities Among COLING, ACL and EMNLP

Inferred from the topic entropy, COLING has been historically the broadest of the three conferences; ACL started with a fairly narrow focus, became nearly as broad as COLING during the 1990's but become more narrow again in recent years; EMNLP shows being its status as a "special interest" conference.

From the JS divergence, they showed all of the three conferences are converging to their topics.

Related papers

Blei and Lafferty, ICML2006: David Blei and John D. Lafferty. 2006. Dynamic topic models. ICML.

Wang and McCallum, KDD2006: Xuerui Wang and Andrew McCallum. 2006. Topics over time: a non-Markov continuous-time model of topical trends. In KDD, pages 424–433, New York, NY, USA. ACM.