This paper reports the work of Middlesex University for the CLEF bilingual task. We have carried out experiments using Portuguese queries to retrieve documents in English. The approach used was Latent Semantic Indexing, which is an automatic method not requiring dictionaries or thesauri. We describe the methods used along with an analysis of the results obtained. Middlesex University is participating in CLEF for the first time. We have submitted runs for the bilingual task, using Portuguese queries to retrieve English documents. The approach adopted was Latent Semantic Indexing (LSI), which has achieved some promising results in previous experiments using other languages [5,10] and has the great advantage of not requiring expensive resources such as thesauri. This paper is organised as follows: Section 2 presents some reasons for choosing Portuguese; Section 3 describes LSI and how it can be applied to CLIR; Section 4 reports our experiments and Section 5 analyses our results.
900 800 700 s 600 n lio 500 il 400 n 300 M I 200 100 0 363 341 322 176 170 167 150 125 100 77 andarin M
i Hind nglish E
ortuguese P engali B
Arabic
Japanese erman G
French
Figure 1– languages in number of native speakers [3] On the other hand, according to the Internet Software Consortium [4], less than 1% of all web hosts are in Portuguese. In addition, only a small percentage of this population is competent in English, the vast majority (including university students) are not able to present good queries (in English) to a search engine like Google, Altavista, Lycos, etc. As a consequence, sources of information for the 8 million Portuguese speakers accessing the Internet are extremely limited compared to the immense amount of information available to the English speaking population. Moreover, no CLIR research has been done using Portuguese. For all those reasons we decided to put Portuguese in the picture, by using it in our experiments. 3
Latent Semantic Indexing [1] is a technique developed in 1990 by Dumais, Derweester, Landauer, Furnas and Harshman. The main goal is to retrieve on the basis of conceptual content rather than the actual terms used in the query. There are several ways of expressing a concept and the terms used in the query may not match the terms used in the documents.
LSI seeks to tackle synonymy and polysemy as they are the main problems with keyword matching. Synonymy is the fact that there are many ways to refer to the same object. And polysemy refers to the fact that many words have more than one distinct meaning. Attempts to solve the synonymy problem have been addressed by query expansion, which works by looking up a thesaurus and augmenting the query with related terms. The polysemy problem is considerably more difficult. Attempts to solve it include research done on word sense disambiguation.
The main goal of using LSI for CLIR is to provide a method for matching text segments in one language with text segments of similar meaning in another language without needing to translate either, by creating a languageindependent representation of the words. This means that words are given an abstract description that does not depend on the original language.
A B Água
LSI is initially applied to a matrix of terms by documents (see Figure 2). Therefore, the first step is to build such a matrix based on a set of dual-language documents1. The matrix contains the number of occurrences (or weights) of each term in each document. In a ideal situation the pattern of occurrence of a term in language A should be identical to the pattern of occurrence of its match in language B. The resulting matrix tends to be very sparse, since most terms do not occur in every document.
This matrix is then factorised by singular value decomposition2 (SVD). SVD reduces the number of dimensions, throwing away the small sources of variability in term usage. The k most important dimensions are kept. Roughly speaking, these dimensions (or factors) may be thought as artificial concepts; they represent extracted common meaning components of many different words and documents. Each term or document is then 1 Dual-language documents are composed by the document in the original language together with its translation in another language.
2 Mathematics are presented in detail in [1]. characterised by a vector of weights indicating its strength of association with each of these underlying concepts. Since the number of factors or dimensions is much smaller than the number of unique terms, words will not be independent. For example, if two terms are used in similar documents, they will have similar vectors in the reduced-dimension representation.
It is possible to reconstruct the original term by document matrix from its factor weights with reasonable accuracy. However, it t not advisable to reconstruct it with perfect accuracy, as the original matrix contains noise, which can be eliminated through dimension reduction. LSI implements the vector-space model, in which terms, documents and queries are represented as vectors in a k-dimensional semantic space. The SVD of a sparse matrix A is given by:
A = UΣV T Where U and V are orthogonal matrices and Σ is the diagonal matrix of singular values. The columns of U and V contain the left and right singular vectors, respectively. The m × n matrix Ak, which is constructed from the klargest single triplets of A, is the closest rank-k matrix to A. Ak = Best rank-k approximation to A m = number of terms U = Left singular vectors (term vectors) n = number of documents Σ = Singular values k = rank (number of dimensions)
V = Right singular vectors (document vectors) r = number of dimensions of A After deriving the semantic space with an initial sample of documents, new documents can be added (folded in), those are placed at the average of its corresponding terms. Queries are treated as pseudo-documents and placed at the weighted sum of its component term vectors. The similarity between query and documents is measured using the cosine between their vectors.
SVD causes synonyms to be represented by similar vectors (since they would have many co-occurrences), which allows relevant documents to be retrieved even if they do not share any terms with the query. This is what makes LSI suitable for CLIR, given that a term in one language will be treated as a synonym to its match in the other language. The main advantages of using LSI for CLIR are: • • • • • •
In order to use LSI for a bilingual experiment we needed an initial sample of parallel documents, i.e. the original documents and their translations, to derive the concept space. However, the collection we used, the Los Angeles Times, was in English only. Therefore we used Systran [8] to translate 20% (approximately 22000 documents) of the collection into Portuguese. Figure 4 shows a sample dual-language document used in the experiment. The translation is far from perfect, and many times the incorrect sense of a word was used, e.g. “branch” was translated to “filial” (shop branch), when the correct sense was “ramo” (tree branch). When the system did not have a translation for a term, it remained in the original language. Nevertheless, we did not perform any corrections or modifications on the resulting translations.
<DOCNO> LA012394-0072 </DOCNO> TIME TO CARE FOR ROSES Give attention to roses at this time. Prune them before spraying to reduce the total area that needs to be sprayed at this time.
Remember to drench the branches and trunk until the material runs off the branches.
<DOCNO> LA012394-0072 </DOCNO> A HORA DE IMPORTAR-SE COM ROSAS dá a atenção às rosas neste tempo.Pode-os antes de pulverizar para reduzir a área total que necessita ser pulverizada neste tempo. Recorde drench as filiais e o tronco até o material funciona for a das filiais. We used the Porter stemmer [7] to stem the English documents, and our own stemmer [6] to stem the Portuguese translations. Stop words were also removed. Next step was to run the SVD on the 22,000 dual-language documents. We used a binary version of LSI provided by Telcordia Technologies [9]. An important aspect is the choice of the number of dimensions that will compose the concept space. We chose 700 dimensions since this is the number which gave best performance, within reasonable indexing time, when using last year’s query topics.
The entries in the term by document matrix were the local weight (frequency of a term in a document) multiplied by the global weight of the term (number of occurrences of a term across the entire collection). The weighting scheme used was “log-entropy” which is given by the formula below. A term whose appearance tends to be equally likely among the documents is given a low weight and a term whose appearance is concentrated in a few documents is given a higher weight. The elements of our matrix will be of the form: L( i , j ) * G( i ) Local Weighting: L( i , j ) = log(tfij +1) Global Weighting: G( i ) = 1 − ∑ Nj=1 pij log( pij ) where pij =
log N where: tfij gfi tfij = frequency of term i in document j gfi = total number of times term i occurs in the entire collection
N = number of documents in the collection The next step was to “fold in” the remaining 91,000 English-only documents into that semantic space, which means that vector representations were calculated for those remaining documents. The resulting index had 70,000 unique terms, covering both languages. We did not index terms which were less than 3 characters long. We did not use phrases or multiword recognition, syntactic or semantic parsing, word sense disambiguation, heuristic association, spelling checking or correction, proper noun identification, a controlled vocabulary, a thesaurus, or any manual indexing.
All terms and documents from both languages are represented in the same concept space. Therefore a query in one language may retrieve documents in any languages. This situation benefits from cross-linguistic homonyms, i.e. words that have the same spelling and meaning in both languages; e.g. “singular” is represented by one vector only, accounting for both languages. On the other hand, it suffers with “false friends”, i.e. words that have the same spelling across languages but different meanings; e.g. “data” in Portuguese means “date” instead of “information”. The problem in this case is that false friends are wrongly represented by only one point in space, placed at the average of all meanings. The ideal scenario would be taking advantage from cross-linguistic homonyms and at the same time avoiding false friends. We are still looking for a way to do that automatically.
In and ideal situation the similarity between a term and its translation should be very high (close to 100%). In order to evaluate how accurately LSI represents the correspondence between terms, we calculated the similarities between some English words and their counterparts in Portuguese. Table 1 shows the results for this experiment. The scores are generally quite high. However, when cross-linguistic polysemy is present, the similarity decreases significantly (see second column). This happens because term co-occurrences decrease in the presence of polysemy and results in a term and its translation being placed further apart in the concept space. baby
bebê
Chipre carro correr encontrar Analysing the sets of documents retrieved for each query, we observed that most highly ranked but irrelevant documents were generally on the query topic, but did not specifically meet the requirements. As an example, for query 121 – “Successes of Ayrton Senna”, the documents retrieved were about him, but sometimes did not mention his sporting achievements. We also did not score well in queries 97, 98 and 131 for which there was only one relevant document. We believe that happened because we did not index words that occurred in one document only, and “Kaurismäkis”, for example, was one of them.
In comparison to the other groups, we have achieved the best score in four topics: 126,130, 137 (MDXman) and 106 (MDXtd). Also in four topics we achieved the worst result: 91, 98, 134 (MDXtpc) and 108 (MDXtd). For MDXman, 22 topics were at or above the median and 20 topics were below the median. LSI outperforms keyword based searching in the cases where the words used in the query do not match the terms used in the relevant documents. This was the case of topic 137 – “international beauty contests”, both relevant documents did not contain the keywords present in the topic. It had, however, related terms such as “miss world” and “miss universe”. Our superior performance in those cases confirms that LSI can efficiently tackle the synonymy problem, modelling relationships between related terms and placing them close together in the vector-space. Future work will include further analysis of those results in order to establish methods for improvement. We are also interested in finding automatic ways to minimise the effects of polysemy. 2 3 4 5 6
Analysis. Journal of the American Society for Information Science, 41(6):1-13, 1990.
Semantic Indexing. In: Proceedings of the Sixth Annual Conference of the UW Centre for the New Oxford
SPIRE’2001 Symposium on String Processing and Information Retrieval, Laguna de San Raphael, Chile,