Swedish is a compounding language, and therefore it is important to split compound words so that useful word constituents can be found. One of the problems is that it is difficult to find constituents that express a concept similar to that expressed by the compound. The approach taken in this paper is to look at how the leading constituent of the compound word can be used to expand a search query. The constituent was added to the original query, while still keeping the compound. Every word was then truncated so as to increase recall by hopefully finding other compounds with the leading constituent as prefix. Since this approach increase recall in a rather uncontrolled way, we also used a Boolean quorum-level type of query combination so that documents were ranked according to both the tf-idf factor but also to the number of matching Boolean combinations. The Boolean combinations performed relatively well, taken into consideration that the queries were very short (maximum five search terms). Also included in this paper are the results of two other methods we are currently working on in our lab; one for re-ranking search results on the basis of stylistic analysis of documents, and one for dimensionality reduction using Random Indexing.
of the problems of compound splitting is that it is difficult to find constituents that express a concept 1 that is similar to that expressed by the compound.
For example, the word “Diamantgruva” is important to split so that the content-bearing words “Diamant” and “Gruva” can be found. These two words are good query terms, since they are not ambiguous and express the two separate concepts diamond and mine. On the other hand, if the word “Domstol” (Court) is split into “Dom” (Judgement) and “Stol” (Chair), some errors are introduced. “Stol” is not a good search term in this context, and “Dom” is ambiguous; it also means “Them” in spoken Swedish. Splitting “Domstol” thus make more harm than keeping the compound form.
Another problem that may occur can be exemplified by splitting the compound “Riksdagshus” (Parliament building). The lemmatizer that we used in our experiments split this into the three constituents “Riks”, “Dags” and “Hus”. It did not find the word “Riksdag” (Parliament) which is an important word in this context. Furthermore, the words “Riks” and “Dags” should not have been extracted as constituents, since “Riksdag(s)” is a not a compound. Moreover, it seems that the lemmatizer does not make a morphological analysis of the constituents. This has the effect that sometimes a joining ’s’ is left at the end of words that should not have it.
In summary, some of the problems with using constituents from compound splitting are that they • may not express a concept similar to that expressed by the compound • may be ambiguous • may not always be valid words 2
Since compound splitting may not always yield constituents that improve a query, it is desirable to have a method for selecting only a subset of the constituents. Since compounds are often very specific words, one way to improve the query is to find constituents that boost the recall. In our case, we chose to select only the leading constituent for expanding the query.
The leading constituent is sometimes a modifier to the last constituent, i.e. it determines something about the last constituent. For instance, the leading constituent “Ozon” (Ozone) in “Ozonlager” (Ozone layer) determines that the layer mentioned is the ozone layer. The word “Ozon” is useful as a search term, since documents about ozone layers probably also contain the separate word “Ozon”. Such documents might also contain other compounds that begin with “Ozon” such as “Ozonhalt” (Ozone amount) and “Ozonh˚al” (Ozone hole), so finding these words might also help improve the query.
By expanding a query with the leading constituent of a compound search word will effectively increase the recall, and hopefully in such a way that the new documents that are found are related to the concept expressed by the compound. And if we also expand the query with all words that begin with the leading constituent, we will find new words that again, hopefully, are related as well. But we will also find words that are not related to the concept at all, so there must be some way of narrowing the query as well.
Our general approach in runs sicsSVtad and sicsSVtmd was to expand the queries with leading constituent. These were added as search words while also keeping the original compound. Each search word was then truncated, i.e. we found all other indexed words that had the search word as prefix. All search words were truncated, not only the leading compounds. For instance, the truncation of “Diamant” found “Diamantexport” (Diamond export), “Diamantf¨oretag” (Diamond corporation) and also “Diamantgruva” mentioned earlier.
We decided to do the compounds splitting at query time, so that we could elaborate with how to select good constituents for improving the queries.
1By concept, we mean search term 2.1
The underlying retrieval engine we used is an experimental system developed at SICS. It currently
supports Boolean, Vector Space and structured queries. It is designed to handle a large amount
of documents and queries, using algorithms described in [
The Swedish document collection was parsed and normalized using a lemmatizer, but we did not use any compound splitting at indexing time. Also, we used a list of 285 stop words.
For scoring documents, we used pivoted cosine normalization, or Lnu in Smart notation [
We used two different approaches to query formulation. For the first run, sicsSVtad, we used the selective compound splitting on the Title field only. In the second run, sicsSVtmd, we again used the Title words, but also added some words from the Desc field (those with lowest document frequency) so that there was a maximum of 5 words in the query. Each such base word was then truncated, and we performed a ranked Boolean AND between the base words and a ranked Boolean OR between the words found by truncating the base words. In the case where there were less than 1000 documents in a result list, we appended the results of a standard vector space query using all words from the Desc field.
To illustrate the Boolean combination procedure, let a, b and c be three query terms, and let a1, . . . , an be the expanded words from the truncation of a (and b1, . . . , bm, c1, . . . , cr for b and c). For each possible Boolean combination of the query terms, we constructed one query. In total this makes 7 queries, displayed in Figure 1.
(a1 ∨ . . . ∨ an) ∧ (b1 ∨ . . . ∨ bm) ∧ (c1 ∨ . . . ∨ cr)
(a1 ∨ . . . ∨ an) ∧ (b1 ∨ . . . ∨ bm)
(a1 ∨ . . . ∨ an) ∧ (c1 ∨ . . . ∨ cr)
(b1 ∨ . . . ∨ bm) ∧ (c1 ∨ . . . ∨ cr)
(a1 ∨ . . . ∨ an)
(b1 ∨ . . . ∨ bm)
(c1 ∨ . . . ∨ cr)
In general, the number of such Boolean query combinations is Pik=1 ki , where k is the number
of terms in the query. This type of Boolean combination is sometimes called quorum level search
[
Since each Boolean combination was a single query, we simply set the RSV for each document to the sum of the RSV values from all queries in that combination. This has the desirable property that documents are not only ranked according to the tf-idf model, but also to the number of combinations of the search words that are spotted in the document. For instance, a document where all search words are found would be at the top of the list, since that document would get positive RSV values from all queries in the combination. 3
Since the Boolean combinations of truncated terms is designed to increase recall, it is important to make sure that we do not add too much noise in this process. One way of doing this is to use stylistic filtering of the retrieved documents to boost news items with animate agents. 3.1
As the text corpus was composed of news service items with longer more textual pieces, short one-paragraph or one-sentence passages, as well as tables of sports or stock results, a filter to boost the rank of items more likely to be relevant to the textually oriented materials requested for CLEF was designed. The basic assumption of the filter was that items more likely to be relevant would contain more animate agents than others: texts with the personal agents present and with descriptions of actions taken by people or organizations or other animate entities were assumed to be of a higher information value than texts with completely impersonal and non-active constructions.
The style filter was constructed in a multi-step process. First, a set of prototypical animate agents was drawn up. The list used as a seed set can be seen in Table 1. Second, all verbs in the corpus were tabulated by their occurrence with a subject from the seed set of animate agents. Verbs which occurred at least once with one of the prototypically animate agents were noted to be personal verbs - comprising a set of over 2200 verbs.
Third, for each textual item, the number of personal verbs was tabulated. This statistic was used as an animacy score for the text item.
Fourth, the output from other retrieval runs was then reranked using the animacy score as a key. The reranking was done in one pass through the list. If an item has a low animacy score, operationalized as less than 75 per cent of the average animacy score of any text in the retrieved set, and the item just below it has a higher animacy score, their position is swapped. This method avoids large scale movement of items through the ranked list but shifts adjacent items from position to position.
han hon man kvinna he she man / impersonal “one” woman barn ungdom pojke flicka child youth boy girl
Unfortunately, we could see no effect of the reranking in our results, and are currently investigating why this was the case. 3.2
Dimensionality reduction is often important in information retrieval tasks, since the dimensionality of the search space induces constraints on the performance of the retrieval engine; very highdimensional data will require large amounts of memory and processing time, and will severely limit the efficiency of the system. This is especially important in real-world settings, where the user expects both accurate and, sometimes even more important, fast results. A common approach to reduce the dimensionality of the data in information retrieval systems is by using various forms of word filtering techniques, such as stop lists, frequency thresholding and morphological normalization.
An alternative method for dimensionality reduction in the Vector Space Model (VSM) [
In one of our CLEF 2003 runs (sicsSVind), we used the Random Indexing approach [
The retrieval was then performed by simply calculating the vector similarity between each query vector and all the document vectors. The documents with highest similarity score were ranked as most relevant to the query. As similarity measure, we used the cosine of the angles between the vectors, given by: dcos(x, y) =
~x · ~y | ~x || ~y | =
Pin=1 xiyi pPin=1 xi2pPn i=1 yi2
The results are somewhat disappointing; only 2 queries are above the median results, 3 are on the median, and 48 below. It is not clear at this point whether the results are an artefact of the dimensionality reduction, or if they depend on the simple and naive query formulation process used in these runs. Future experiments will investigate this matter more fully. 4
A summary of the results of the runs using the Boolean combination queries is displayed in Table 2. The Table shows the number of queries that were above, on, or below the median result as well as the number queries that obtained the maximum or minimum score.
Run sicsSVtad sicsSVtmd
The overall results are encouraging but there are also many missed queries. Since we use a maximum of 5 search terms for each query, the misses are easily attributed to the small amount of query terms. However, we believe that it is interesting to evaluate what type of results that can be achieved when using few query terms, since it is well known that many users (especially search engine users) typically use only three or four words to express their query.
There is an interesting difference between the two runs; the number of queries above the median result and the number of queries that obtained the lowest score. Recall that in sicsSVtad, only terms from the Title field were used. When we added some terms from the Desc field in sicsSVtmd we got fewer (3) queries that obtained lowest score but also fewer queries (2) above the median.
The fewer number of queries that got lowest score is due to the fact that we added more search terms to the query in the sicsSVtmd. For instance, the average precision of query 165 was improved from 0.3333 to 1.000. The query in sicsSVtad was “GOLDEN GLOBE” whereas in sicsSVtmd it was expanded to “GOLDEN GLOBE KATEGORI DRAMA FILM”.
We noted that for the queries that were above median in sicsSVtad and then below median in sicsSVtmd, the difference was very small in terms of average precision. For instance, the average precision of query 147 was changed from 0.0673 to 0.0619, and the median was 0.0639.
2We used a stop list based on document frequencies together with ordinary word frequency thresholds (excluding low (< 3 occurrences) and high (> 12000 occurrences) frequency words). For a compounding language such as Swedish, it is important to find methods that can effectively manage compound words in information retrieval systems. The approach taken in this paper is to look at how the leading constituent of a compound word can be used to expand the query. The query terms were then truncated to increase recall. To strike a balance between high recall and high precision, we used a Boolean quorum-level type of combination where documents were ranked according to both the tf-idf factor but also according to how many of the Boolean combinations that matched.
The Boolean combinations performed relatively well, taken into consideration that the queries were very short. This was our first attempt to tackle the problem of using compound word splitting for query expansion, and we will continue to pursue this line of research. What we would like to do to next is to use co-occurrence statistics and perhaps also clustering methods to find words that are related to the compound, so that we can have a more principled way of checking the relation between the concept expressed by the constituent and that expressed by the compound. Acknowledgements The work reported here is partially funded by the European Commission under contracts IST-2000-29452 (DUMAS) and IST-2000-25310 (CLARITY) which is hereby gratefully acknowledged. We thank Tidningarnas Telegrambyr˚aAB, Stockholm, for providing us with the Swedish text collection.