Detection of Topic and its Extrinsic Evaluation Through Multi-Document Summarization

LDA presented by [4] models each document as a mixture of topics (we call it lda_topic to discriminate our $topic$ candidates), and generates a discrete probability distribution over words for each lda_topic. The generative process for LDA can be described as follows:

1. 1.

   For each topic $k$ = 1, $\mathrm{\cdots }$, $K$, generate ${\varphi }_k$, multinomial distribution of words specific to the topic $k$ from a Dirichlet distribution with parameter $\beta$;

2. 2.

   For each document $d$ = 1, $\mathrm{\cdots }$, $D$, generate ${\theta }_d$, multinomial distribution of topics specific to the document $d$ from a Dirichlet distribution with parameter $\alpha$;

3. 3.

   For each word $n$ = 1, $\mathrm{\cdots }$, $N_d$ in document $d$;

   1. (a)

      Generate a topic $z_{dn}$ of the $n^{th}$ word in the document $d$ from the multinomial distribution ${\theta }_d$

   2. (b)

      Generate a word $w_{dn}$, the word associated with the $n^{th}$ word in document $d$ from multinomial ${\varphi }_{zdn}$

Like much previous work on LDA, we used Gibbs sampling to estimate $\varphi$ and $\theta$. The sampling probability for topic $z_i$ in document $d$ is given by:

$z_{\backslash i}$ refers to a topic set $Z$, not including the current assignment $z_i$. $n_{\backslash i,j}^v$ is the count of word $v$ in topic $j$ that does not include the current assignment $z_i$, and $n_{\backslash i,j}^{\cdot }$ indicates a summation over that dimension. $W$ refers to a set of documents, and $T$ denotes the total number of unique topics. After a sufficient number of sampling iterations, the approximated posterior can be used to estimate $\varphi$ and $\theta$ by examining the counts of word assignments to topics and topic occurrences in documents. The approximated probability of topic $k$ in the document $d$, $\widehat{{\theta }_d^k}$, and the assignments word $w$ to topic $k$, $\widehat{{\varphi }_k^w}$ are given by:

We used documents prepared by summarization tasks, NTCIR and DUC data as each task consists of series of documents with the same topic. We applied LDA to the set consisting of all documents in the summarization tasks and documents from the corpus. We need to estimate the appropriate number of lda_topic.

Let $k^{\prime }$ be the number of lda_topics and $d^{\prime }$ be the number of topmost $d^{\prime }$ documents assigned to each lda_topic. We note that the result obtained by LDA can be regarded as the two types of clustering result shown in Figure 1: (i) each cluster corresponds to each lda_topic (topic id0, topic id1 $\mathrm{\cdots }$ in Figure 1), and each element of the clusters is the document in the summarization tasks (task1, task2, $\mathrm{\cdots }$ in Figure 1) or from the corpus (doc in Figure 1), and (ii) each cluster corresponds to the summarization task and each element of the clusters is the document in the summarization tasks or the document from the corpus assigned topic id. For example, DUC2005 consists of 50 tasks. Therefore the number of different clusters is 50. We call the former lda_topic cluster and the latter task cluster. We estimated $k^{\prime }$ and $d^{\prime }$ by using Entropy measure given by:

$l$ refers to the number of clusters. $P\left(A_i,C_j\right)$ is a probability that the elements of the cluster $C_j$ assigned to the correct class $A_i$. $N$ denotes the total number of elements and $N_j$ shows the total number of elements assigned to the cluster $C_j$. The value of $E$ ranges from 0 to 1, and the smaller value of $E$ indicates better result. Let $E_{topic}$ and $E_{task}$ are entropy value of lda_topic cluster and task cluster, respectively. We chose the parameters $k^{\prime }$ and $d^{\prime }$ whose value of the summation of $E_{topic}$ and $E_{task}$ is smallest. For each lda_topic, we extracted words whose probabilities are larger than zero, and regarded these as topic candidates.

The proposed method does not simply use MACD to find bursts, but instead determines topic words in series of documents. Unlike Dynamic Topic Models [3], it does not assume Gaussian distribution so that it is a natural way to analyze bursts which depend on the data. We applied it to extract topic words in series of documents. MACD histogram defined by Eq. (6) shows a difference between the MACD and its moving average. MACD of a variable $x_t$ is defined by the difference of $n_1$-day and $n_2$-day moving averages, MACD($n_1$,$n_2$) = EMA($n_1$) - EMA($n_2$). Here, EMA($n_i$) refers to $n_i$-day Exponential Moving Average (EMA). For a variable $x$ = $x\left(t\right)$ which has a corresponding discrete time series x = {$x_t$ $\mid$ $t$ = 0,1,$\mathrm{\cdots }$}, the $n$-day EMA is defined by Eq. (5).

$\alpha$ refers to a smoothing factor and it is often taken to be $\frac{2}{\left(n+1\right)}$. MACD histogram shows a difference between the MACD and its moving average¹¹In the experiment, we set $n_1$, $n_2$, and $n_3$ to 4, 8 and 5, respectively [11]..

The procedure for topic detection with MACD is illustrated in Figure 2. Let $A$ be a series of documents and $w$ be one of the topic candidates obtained by LDA. Each document in $A$ is sorted in chronological order. We set $A$ to the documents from the summarization task. Whether or not a word $w$ is a topic word is judged as follows:

1. 1.

   Create document-based MACD histogram where X-axis refers to $T$, i.e., a period of time (numbered from day 1 to 365). Y-axis is the document count in $A$ per day. Hereafter, referred to as correct histogram.

2. 2.

   Create term-based MACD histogram where X-axis refers to $T$, and Y-axis denotes bursts of word $w$ in $A$. Hereafter, referred to as bursts histogram.

3. 3.

   We assume that if a term $w$ is informative for summarizing a particular documents in a collection, its burstiness approximates the burstiness of documents in the collection. Because $w$ is a representative word of each document in the task. Based on this assumption, we computed similarity between correct and word histograms by using KL-distance²²We tested KL-distance, histogram intersection and Bhattacharyya distance to obtain similarities. We reported only the result obtained by KL-distance as it was the best results among them.. Let $P$ and $Q$ be a normalized distance of correct histogram, and bursts histogram, respectively. KL-distance is defined by $D(P\mid \mid Q)$ = ${\sum }_{i=1}P\left(x_i\right)\log \frac{P\left(x_i\right)}{Q\left(x_i\right)}$ where $x_i$ refers bursts in time $i$. If the value of $D(P\mid \mid Q)$ is smaller than a certain threshold value, $w$ is regarded as a topic word.

An event word is something that occurs at a specific place and time associated with some specific actions [2, 1]. It refers to notions of who(person), where(place), when(time) including what, why and how in a document. Therefore, we can assume that named entities(NE) are linguistic features for event detection. An event word refers to the $theme$ of the document itself, and frequently appears in the document but not frequently appear in other documents. Therefore, we first applied NE recognition to the target documents to be summarized, and then calculated tf$\ast$idf to the results of NE recognition. We extracted words whose tf$\ast$idf values are larger than a certain threshold value, and regarded these as event words.

We recall that our hypothesis about key sentences in multiple documents is that they include topic and event words. Each sentence in the documents is represented using a vector of frequency weighted words that can be event or topic words.

Like much previous work on extractive summarization [7, 18, 25], we used Markov Random Walk (MRW) model to compute the rank scores for the sentences. Given a set of documents to be summarized, $G$ = ($S$, $E$) is a graph reflecting the relationships between two sentences. $S$ is a set of vertices, and each vertex $s_i$ in $S$ is a sentence. $E$ is a set of edges, and each edge $e_{ij}$ in $E$ is associated with an affinity weight $f(i\to j)$ between sentences $s_i$ and $s_j$ ($i$ $\ne$ $j$). The affinity weight is computed using cosine measure between the two sentences, $s_i$ and $s_j$. Two vertices are connected if their affinity weight is larger than 0 and we let $f(i\to i)$= 0 to avoid self transition. The transition probability from $s_i$ to $s_j$ is then defined as follows:

We used the row-normalized matrix $U_{ij}$ = ${\left(U_{ij}\right)}_{\mid S\mid \times \mid S\mid }$ to describe $G$ with each entry corresponding to the transition probability, where $U_{ij}$ = $p(i\to j)$. To make $U$ a stochastic matrix, the rows with all zero elements are replaced by a smoothing vector with all elements set to $\frac{1}{\mid S\mid }$. The final transition matrix is given by formula (8), and each score of the sentence is obtained by the principal eigenvector of the matrix $M$.

We selected a certain number of sentences according to rank score into the summary.

We applied the results of topic detection to extractive multi-document summarization task, and examined how the results of topic detection affect the overall performance of the salient sentence selection. We used two tasks, Japanese and English summarization tasks, NTCIR-3³³http://research.nii.ac.jp/ntcir/ SUMM Japanese and DUC⁴⁴http://duc.nist.gov/pubs.html English data. The baselines are (i) MRW model (MRW): The method applies the MRW model only to the sentences consisted of noun words, (ii) Event detection (Event): The method applies the MRW model to the result of event detection, (iii) Topic Detection by LDA (LDA): MRW is applied to the result of topic candidates detection by LDA and (iv) Topic Detection by LDA and MACD (LDA & MACD): MRW is applied to the result of topic detection by LDA and MACD only, i.e., the method does not include event detection.

The data used in the NTCIR-3 multi-document summarization task is selected from 1998 to 1999 of Mainichi Japanese Newspaper documents. The gold standard data provided to human judges consists of FBFREE DryRun and FormalRun. Each data consists of 30 tasks. There are two types of correct summary according to the character length, “long” and “short”, All series of documents were tagged by CaboCha [14]. We used person name, organization, place and proper name extracted from NE recognition [14] for event detection, and noun words including named entities for topic detection. FBFREE DryRun data is used to tuning parameters, i.e., the number of extracted words according to the tf$\ast$idf value, and the threshold value of KL-distance. The size that optimized the average Rouge-1(R-1) score across 30 tasks was chosen. As a result, we set tf$\ast$idf and KL-distance to 100 and 0.104, respectively.

We used FormalRun as a test data, and another set consisted of 218,724 documents from 1998 to 1999 of Mainichi newspaper as a corpus used in LDA and MACD. We estimated the number of $k^{\prime }$ and $d^{\prime }$ in LDA, i.e., we searched $k^{\prime }$ and $d^{\prime }$ in steps of 100 from 200 to 900. Figure 3 illustrates entropy value against the number of topics $k^{\prime }$ and documents $d^{\prime }$ using 30 tasks of FormalRun data. Each plot shows that at least one of the documents for each summarization task is included in the cluster. We can see from Figure 3 that the value of entropy depends on the number of documents rather than the number of topics. From the result shown in Figure 3, the minimum entropy value was 0.025 and the number of topics and documents were 400 and 300, respectively. We used them in the experiment. The summarization results are shown in Table 1.

Table 1 shows that our approach, “Event & Topic” outperforms other baselines, regardless of the summary type (long/short). Topic candidates include surplus words that are not related to the topic because the results obtained by “LDA” were worse than those obtained by “LDA & MACD”, and even worse than “Event” in both short and long summary. This shows that integration of LDA and MACD is effective for topic detection.

We used DUC2005 consisted of 50 tasks for training, and 50 tasks of DUC2006 data for testing in order to estimate parameters. We set tf$\ast$idf and KL-distance to 80 and 0.9. The minimum entropy value was 0.050 and the number of topics and documents were 500 and 600, respectively. 45 tasks from DUC2007 were used to evaluate the performance of the method. All documents were tagged by Tree Tagger [21] and Stanford Named Entity Tagger ⁵⁵http://nlp.stanford.edu/software/CRF-NER.shtml [8]. We used person name, organization and location for event detection, and noun words including named entities for topic detection. AQUAINT corpus⁶⁶http://catalog.ldc.upenn.edu/LDC2002T31 which consists of 1,033,461 documents are used as a corpus in LDA and MACD. Table 2 shows Rouge-1 against unigrams.

We can see from Table 2 that Rouge-1 obtained by our approach was also the best compared to the baselines. Table 2 also shows the performance of other research sites reported by [5]. The top site was “HybHSum” by [5]. However, the method is a semi-supervised technique that needs a tagged training data. Our approach achieves performance approaching the top-performing unsupervised method, “TTM” [6], and is competitive to “PYTHY” [24] and “hPAM” [16]. Prior work including “TTM” has demonstrated the usefulness of semantic concepts for extracting salient sentences. For future work, we should be able to obtain further advantages in efficacy in our topic detection and summarization approach by disambiguating topic senses.