Topic Detection and Tracking using idf-Weighted Cosine Coefficient

The goal of TDT Topic Detection and Tracking is to develop aut omatic methods of identifying topically related stories wit hin a stream of news media. We describe approaches for both detection and tr cking based on the well-known idf -weighted cosine coefficient similarity metric. The surprising outcome of this research is th at we achieved very competitive results for tracking using a very simple method of feature selection, without word stemming and with ou a score normalization scheme. The detection task results wer e not as encouraging though we attribute this more to the clustering algorithm than the underlying similarity metric. 1. The Tracking Task The goal of the topic tracking task for TDT2 is to identify new s stories on a particular event defined by a small number ( Nt) of positive training examples and a greater number of negative examples . All stories in the news stream subsequent to the final positive ex ample are to be classified as on-topic if they pertain to the event or off-topic if they do not. Although the task is similar to IR routing and fi ltering tasks, the definition of event leads to at least one significan t difference. An event is defined as an occurrence at a given place and t ime covered by the news media. Stories are on-topic if they cover th event itself or any outcome (strictly-defined in ) of the e vent. By this definition, all stories prior to the occurrence are offt pic, which contrary to the IR tasks mentioned, theoretically provides for unlimited off-topic training material (assuming retrospective corpora are available). We expected to be able to take advantage of these unlimited negative examples but in our final implementation did so only to the extent that we used a retrospective corpus to improve t erm statistics of our database. 1.1. idf-Weighted Cosine Coefficient As the basis for our approach we used the idf -weighted cosine coefficient described in  often referred to as tf idf . Using this metric, the tracking task becomes two-fold. Firstly, choosing an op timal set of features to represent topics, i.e. feature selection. Th e approach must choose features from a single story as well as from multi ple stories (forNt > 1). Secondly, determining a threshold (potentially one per topic) which optimizes the miss and false alarm proba bilities for a particular cost function, effectively normalizing th e similarity scores across topics. The cosine coefficient is a document similarity metric which has been investigated extensively. Here documents (and querie s) ar represented as vectors in an n-dimensional space, where n is the number of unique terms in the database. The coefficients of th e vector for a given document are the term frequencies ( tf ) for that dimension. The resulting vectors are extremely sparse and t ypically high frequency words (mostly closed class) are ignored. The cosine of the angle between two vectors is an indication of vector si milarity and is equal to the dot-product of the vectors normalized by the product of the vector lengths. cos( ) = ~ A ~ B k ~ Akk ~ Bk tf idf (term frequency times inverse document frequency) weighting is an ad-hoc modification to the cosine coefficient calcul tion which weights words according to their usefulness in discriminating documents. Words that appear in few documents are more usefu l than words that appear in many documents. This is captured in the equation for the inverse document frequency of a word: idf(w) = log10 N df(w) Wheredf(w) is the number of documents in a collection which contain wordw andN is the total number of documents in the collection. For our implementation we weighted only the topic vector by idf and left the story vector under test unchanged. This allows u s to calculate and fix anidf -scaled topic vector immediately after training on the last positive example story for a topic. The resulting calculation for the similarity measure becomes: sim(a; b) = Pnw=1 tfa(w) tfb(w) idf(w) pPnw=1 tf2 a (w) pPnw=1 tf2 b (w) 1.2. UPENN System Attributes To facilitate testing, the stories were loaded into a simple document processing system. Once in the system, stories are proc ssed in chronological order testing all topics simultaneously w ith a single pass over the data 1 at a rate of approximately 6000 stories per minute on a Pentium 266 MHz machine. The system tokenizer delimits on white space and punctuation (and discards it), col lapses case, but provides no stemming. A list of 179 stop words consi sti g almost entirely of close classed words was also employed. In order to improve word statistics, particularly for the beginning of the test set, we prepended a retrospective corpus (the TDT Pilot ) of approximately 16 thousand stories. 1In accordance with the evaluation specification for this pro ject  no information is shared across topics. 1.3. Feature Selection Thechoice as well asnumber of features (words) used to represent a topic has a direct effect on the trade-off between miss and f lse alarm probabilities. We investigated four methods of produ cing lists of features sorted by their effectiveness in discriminatin g a topic. This then allowed us to easily vary the number of those featur s for the topic vectors 2. 1. Keep all features except those words belonging to the stop word list. 2. Relative to training stories, sort words by document coun t, keepn most frequent. This approach has the advantage of finding those words which are common across training stories, an d therefore are more general to the topic area, but has the disa dvantage of extending poorly from the Nt = 16 case to the Nt = 1 case. 3. For each story, sort by word count ( tf ), keepn most frequent. While this approach tends to ignore low count words which occur in multiple training documents, it generalizes well f rom theNt = 16 to theNt = 1 case. 4. As a variant on the previous method we tried adding to the initial n features using a simple greedy algorithm. Against a database containing all stories up to and including the Nt-th training story, we queried the database with the n f atures plus the next most frequent term. If the separation of on-topic an d off-topic stories increased, we kept the term, if not we igno red it and tested the next term in the list. We defined separation as the difference between the average on-topic scores and th e average of the 20 highest scoring off-topic documents. Of the feature selection methods we tried the forth one yield ed the best results across varying values of Nt, although only slightly better than the much simpler third method. Occam’s Razor prompt ed us to omit this complication from the algorithm. The DET curves 3 in Figure 1. show the effect of varying the number of features (o btained from method 3) on the miss and false alarm probabilities. The upper right most curve results from choosing the single most fr equent feature. Downward to the left, in order are the curves for 5, 1 0, 50, 150 and 300 features. After examining similar plots from the pilot, training4, and development-test data sets, we set the number of features for our system to 50. It can be seen that there is limited benefit in adding features after this point.  Since each topic is r epresented by its own unique vector it cannot be expected that the same threshold value will be optimal across all topics unless the scores are normalized. We tried two approaches for normalizing the topic similarity scores. For the first approach we calculated the similarity of a rando m sample of several hundred off-topic documents in order to estim a e an 2We did not employ feature selection on the story under test bu t used the text in entirety. 3See  for detailed description of DET curves. 4The first two month period of TDT2 data is called the training s et, not to be confused with training data. 1 2 5 10 20 40 60 80 90 .01 .02 .05 .1 .2 .5 1 2 5 10 20 40 60 80 90 M is s pr ob ab ili ty ( in % ) False Alarms probability (in %) random performance num_features=1 num_features=5 num_features=10 num_features=50 num_features=150 num_features=300  DET curve for varying number of features. (Nt=4, TD T2 evaluation data set, newswire and ASR transcripts) average off-topic score relative to the topic vector. The no rmalized score is then a function of the average on-topic 5 and off-topic scores and the off-topic standard deviation 6. The second approach looked at only thehighest scoringoff-topic stories returned from a query of the topic vector against a retrospective database with th e score normalized in a similar fashion to the first approach. Both attempts reduced the story-weighted miss probability by approximately 10 percent at low false alarm probability relat ive. However, this results was achieved at the expense of higher miss probability at higher false alarm probability, and a higher cost a t the operating point defined by the cost function for the task 7. Ctrack = Cmiss P (miss) Ptopic +Cfa P (fa) (1 Ptopic) where Cmiss = 1: (the cost of a miss) Cfa = 1: (the cost of a false alarm) Ptopic = 0:02: (thea priori probability of a story being on a given topic was chosen based on the TDT2 training topics and traini ng corpus.) Because of the less optimal trade-off between error probabi lities at the point defined by the cost function, we choose to ignore nor malization and look directly at cost as a function of a single thr es old value across all topics. We plotted tf idf score against story and topic-weighted cost for the training and development-test data sets. As our global threshold we averaged the scores at which story and topic-weighted cost were minimized. This is depicted in figu re 2. Figure 3 shows the same curves for the evaluation data set. Th e threshold resulting from the traini