Updating Rare Term Vector Replacement

International Joint Conference on Natural Language Processing, pages 1002–1006, Nagoya, Japan, 14-18 October 2013. Updating Rare Term Vector Replacement Tobias Berka† †Department of Computer Sciences University of Salzburg {tberka,marian}@cosy.sbg.ac.at Marian Vajterˇsic†‡ ‡Department of Informatics Mathematical Institute Slovak Academy of Sciences Abstract Rare term vector replacement (RTVR) is a novel technique for dimensionality reduc- tion. In this paper, we introduce an up- dating algorithm for RTVR. It is capable of updating both the projection matrix for the reduction and the reduced corpus ma- trix directly, without having to recompute the expensive projection operation. We in- troduce an effective batch updating algo- rithm, and present performance measure- ments on a subset of the Reuters newswire corpus that show that a 12.5% to 50% split of the documents into corpus and update vectors leads to a three to four fold speed- up over a complete rebuild. Thus, we have enabled optimized updating for rare term vector replacement. 1 Introduction Rare term vector replacement (RTVR) is a re- cently developed linear dimensionality reduction technique for term frequency vectors (Berka and Vajterˇsic, 2011). It is easily and rapidly computed, patent-free, and produces a semantically meaning- ful multivariate space with a significantly reduced dimensionality. Furthermore, the method has been parallelized for data and task parallelism (Berka and Vajterˇsic, 2013). The construction of this representation is based on document-scope term cooccurrences. Rare terms that occur only in δ documents or fewer are eliminated by replacing them with the average vectors of the documents that contain them. The replacement vectors of the rare terms are added to the original document vectors. Then, all rows for rare terms are dropped from all vectors. Only the common terms remain of the original term frequency vector space. By Zipf’s law (Powers, 1998), we know that this operation will eliminate a high number of terms and lead to a highly con- densed representation. The performance of the re- placement now depends on the applicability of the cluster hypothesis (Raiber and Kurland, 2012; Ri- jsbergen, 1979), i.e., that documents in close prox- imity are semantically related. If the cluster hy- pothesis holds, then the centroid of the containing documents will act as a succint representation of all documents containing the replacement term. The most prominent techniques for dimension- ality reduction of text data in published litera- ture are latent semantic indexing (LSI), see (Deer- wester et al., 1990) and the related COV ap- proach (Kobayashi et al., 2002). These two methods are applications of a principal compo- nent analysis to text using unbiased and biased correlation measures. Factor analysis based on the SVD applied to automated indexing has been reported as probabilistic latent semantic analy- sis (PLSA) (Hofmann, 1999). Updating opera- tions for LSI are well understood (Zha and Si- mon, 1999), and are also being developed for PLSA (Bassiou and Kotropoulos, 2011), or other dimensionality reduction methods such as the ker- nel PCA (Mastronardi et al., 2010). Through the connection between PLSA and La- tent Dirichlet Allocation (LDA) (Girolami and Kab´an, 2003), …

Content truncated to 500 words