next up previous
Next: Term Selection and Weighting Up: A Competitive Term Selection Previous: A Competitive Term Selection


Vector Space Model (VSM) was proposed by Salton [15] in the 1970's. This model states a simple way to represent documents of a collection by using vectors with weights according to the terms appearing in each document. Even though several other approaches have been tried, such as representative pairs [10] or documents tokens, terms vector representation remains a topic of interest. Main attraction stills on VSM because it provides a framework for several applications of Natural Language Processing (NLP) such as text categorization, clustering, summarization and so on. Particularly, in Information Retrieval (IR), several experiments have shown a sucessful use of VSM. In this model, each document is represented as a vector whose entries are weights of the vocabulary terms obtained from a text collection. Specifically, given a text collection $ \{D_1,\ldots,D_M\}$ with vocabulary $ V=\{w_1,\ldots,w_n\}$, the vector $ \overrightarrow{D_i}$ of dimension $ n$, corresponding to the document $ D_i$, has entries $ d_{ij}$ representing the weight of the term $ w_j$ in $ D_i$:

$\displaystyle d_{ij}=tf_{ij}\cdot idf_j,$ (1)

where $ tf_{ij}$ is the frequency of term $ w_j$ in document $ D_i$, $ idf_j=\log_2(\frac{2M}{df_j})$, and $ df_j$ is the number of documents in which $ w_j$ appears. In collections of hundreds of documents, the dimension of the vector space can be of tens of thousands. Therefore, a key element in text representation consists basically of the adequate selection of important terms, i.e., those that do not affect the retrieval, clustering, or categorization process, implicit in the application. Besides, a reduction of the vocabulary dimensionality without affecting the effectiveness is expected. It is important, from the reason just explained, to explore new mechanisms to represent texts, with the minimal number of terms and, the maximum tradeoff of precision and recall.

In [17] , for instance, R. Urbizagástegui used the Transition Point (TP) to show its usefulness in text indexing. TP is a frequency value that splits the vocabulary of a text into two sets of terms (low and high frequency). This technique is based on the Zipf Law of Word Ocurrences [19] and also on the refined studies of Booth [2]. These studies are meant to demonstrate that mid-frequency terms are closely related to the conceptual content of a document. Therefore, it is possible to hypothesize that terms closer to TP can be used as index terms of a document. A typical formula used to obtain this value is: $ TP = \frac{-1 + \sqrt{8*I_1+1}}{2},$ where $ I_1$ represents the number of words with frequency equal to $ 1$ (see [17]). Alternatively, TP can be found as the first frequency that is not repeated from a non-increasing frequency-sorted vocabulary; since a feature of low frequencies is that they tend to repeat [2]. Particularly, in the experiments we have carried out, we used this approach. Additionaly, the Transition Point technique has shown a good performance in term selection for text categorization [9] and clustering [12].

TP is derived from items underlying in the form layer, because of its intrinsic property of statistical regularity in the texts. By using ontologies, dictionaries and other lexical resources, it is possible to affect the signifier substance [4]. Thus, TP can be used to affect form and substance by using terms related to it. However, the use of some lexical resources, such as WordNet, would not be factible because of its wide domain, carrying out to discard several terms belonging to the specific application domain. Regarding the usefulness of the later remark, the set of terms selected by TP may be increased with related terms, namely TP enriched approach [14].

On the other hand, M. A. Montemurro [6] did a statistical analysis of some set of words without knowledge of the grammatical structure of the documents analized. He used the entropy concept for sorting sets of words, based on the role that these words play in a set of documents from the literature domain. Entropy measures the amount of information contained in a system [3]. So, given a system $ S$ with $ s_1,\ldots,s_n$ states, the entropy of $ S$ is $ H(S)=-\sum_i p_i \log(p_i),$ being $ p_i=\Pr(s_i).$ This means that a deterministic system lacks of information if $ H(S)=0$, since $ p_i=1$ (the same argument is valid if $ p_i=0$). On the other hand, a system whose states have the same probability ($ p_i=1/n$) will have the maximum of information $ H(S)=\log n$. We must not confuse the information that a system has with the information that can be extracted from it; in other words, the less information we have from a system, the bigger amount of information the system will have; the information of a system is a measurement of our ignorance. In a text collection we can consider a) the words, $ w$, that have high probability to appear in all the documents ( $ \Pr(w)\approx 1$); b) words that are not uniformly distributed in the collection of texts, i.e., those which are concentrated in some document; and, c) those words that are uniformly distributed in a corpus. The last one has a high value of significance in terms of information, compared with the two former and may be used to represent the text.

This work explores an alternative to the classic representation based on the VSM for IR. Entropy was used in [5] for IR processes on a small text collection, but results were not conclusive. TP has been also used in this context [13], obtaining good results: reducing dimensionality and outperforming classical representation. In [14] an enrichment of the term selected by TP for cross-lingual information retrieval was presented, but results were not indicative of better performance due to the noisy terms in multilingual collections. Our contribution here consists in clarify the uselfulness of each of these methods by using the TREC-5 standard collection as a common reference. Besides, we have tried to enhance the obtained results by providing a combination of such approaches.

Following sections present the term selection and weighting schemata, experiments done by using the TREC-5 collection, results, and a discussion with conclusions.

next up previous
Next: Term Selection and Weighting Up: A Competitive Term Selection Previous: A Competitive Term Selection
David Pinto 2007-05-08