This paper describes participation of Dokuz Eylül University to WikipediaMM task at ImageCLEF2009. This year we concentrated on two main topics: First is about expansion of native document, term phrase selection and query expansion processes which is based on WordNet, WSD and WordNet similarity functions. The second is a new reranking approach with Boolean retrieval and C3M based clustering. Experimentation shows that reranking generated the best MAP and precision results among all participants in WikipediaMM 2009 task. This paper presents details of our participation to the WikipediaMM task of ImageCLEF 2009. This is our first year in WikipediaMM task, and we participated both retrieval experiment and relevance assessment steps. We propose expansion and reranking approaches. Reranking is used to re-order the initial retrieved documents for better results by increasing the precision. Reranking is recently most popular research subject for Information Retrieval. We also used expansion techniques for both dataset and queries. Although there are numerous works on query expansion, document expansion is one of the major proposed novel approaches. Expansion phase is implemented using WordNet [1] (WSD, WN Similarity Functions). During the baseline retrieval, expanded and original datasets are combined with the form of Pivoted Unique Normalization [9]. The main focus of this work is to improve search results by two phased reranking. The set of initial retrieved documents are re-ordered for better results by increasing the precision. The first phase comprises reranking and reordering with the Boolean retrieval approach. The main objective of the second step is reranking with the clustering algorithm. C3M [23] clustering algorithm is executed on the new result sets and the similarity score of each document with its related query is calculated with C matrix ( ). Final ranking score is calculated by using Boolean ranking score ( ) and query-document similarity score ). Experimental results show that, phased reranking approach improves results over the baseline and over expansion results. Rest of the paper is organized as follows: Sections 2 gives the details of our retrieval system. In Section 3, we present, Document and Query expansion methods, we have tested, by using WordNet system. Section 4 gives our two phased reranking approaches based on Boolean retrieval and C3M clustering. Section 5 concludes the paper, discusses the results we obtained and gives a look at the future studies on this subject.
Figure 1 shows the retrieval system framework and our experimentations. First of all, preprocessing step is done; dataset is expanded using WordNet (WSD, WN Similarity Functions) and term phrases are selected. Both the original and the expanded form of dataset are used and converted to document vectors before baseline retrieval. Queries can also be expanded using TPS and/or WordNet for experimental purposes. During the baseline retrieval, expanded and original datasets are combined with the form of Pivoted Unique Normalization (Pivoted VSM). Each baseline query resultset is kept (new Pivoted VSMs) and two phased reranking steps start. The first phase aims reranking and reordering with the boolean retrieval approach. The resultsets of each query and the base ranking scores are again saved for the next reranking step. The main objective of the second step is reranking with the clustering algorithm. Final ranking score is calculated using boolean ranking score ( ) from the first step and query-document similarity score ) from the second step. The two phased reranking process is completed and final ranked resultsets are generated. Term weighting is an important aspect of modern text retrieval systems [10]. There are three major parts that affects the importance of a term in a text, which are the term frequency factor ( ), the inverse document frequency factor ( ), and document length normalization. Cosine normalization is the mostly used normalization technique in the vector space model [8]. Normalization factor is computed as in the formula (1), DE phase, Pivoted Unique Normalization affects the retrieval performance positively by increasing recall. This work purposes to improve search results by reranking. If the recall level of the retrieval process is not high, reranking becomes non-effective.
# $%&
) '() 1 "
* 1 +,+11-* " $%& . where dtf is the number of times the term appears in the document, sumdtf is the sum of (log(dtf)+1)'s for all terms in the same document, N is the total number of documents, nf is the number of documents that contain the term, U is the number of unique terms in the document. The uniqueness means that the measure of document length is based on the unique terms in the document. In this work, 0.0118 is used as the pivot value.
When retrieving, the rank is the product of the weight and the frequency of the term in the query.
In our work, document expansion (DE), term phrase selection (TPS) and query expansion (QE) phases are
realized by using WordNet [
The first stage of preprocessing is the expansion stage. Although only query expansion is mostly common in the text retrieval, in this work, both the documents and queries are expanded using the same approaches. Namely, the word “expansion”, is used for both the document expansion (DE) and query expansion (QE).
Expansion is realized with Word sense disambiguation (WSD), so that the terms are expanded, with the most
appropriate sense, based on the context in which they occur. Word sense disambiguation (WSD) is the process of
finding out the most appropriate sense of a word based on the context in which it occurs. The Lesk algorithm [
Before the expansion stage, both the documents and queries are processed through some phases. The first phase is stop-words elimination. The stop words in the documents and queries are eliminated by controlling each term’s existence in the stop-words dictionary. The second phase is lemmatizing. Lemmatization is the process of reducing an inflected spelling to its lexical root or lemma form. The lemma form is the base form or head word form that can be found in the WordNet dictionary. The combination of the lemma form with its POS is called the lexeme.
Although it is commonly argued that language semantics are mostly captured by nouns and noun termphrases, in this work, both noun and adjective representations (POS) are used in the documents and queries. After all of these phases the documents and queries are available for the expansion process. To emphasize that in the expansion stage, the new terms are also processed through these phases. If they pass successfully through them, then they are added to the documents and queries.
In general, the documents in the datasets are domain-specific. On the other hand, Wiki has a heterogeneous structure [11][12]. It contains nearly 150.000 documents, created by the different users for different aims. However queries are more target focused and they are created by the users according to their needs without knowing the documents. The aim of expanding both documents in the dataset and the queries is, to assimilate the queries to the documents, and documents to queries. Expanding the poorly defined documents and adding new terms or term-phrases, results in higher ranking performance, or similarly expanding the queries and widening the search terms, increase the quality of ranking by bringing relevant documents not matching literally with the original user query.
As an example; the document, related with the query “blue flower”, includes the term “sea lavender”. Without expansion, they are not matching literally and they seem irrelevant. However, as we expand “sea lavender” with WordNet, the new terms “blue flower” are added to the document. So both the query and the document include the same terms and their ranking score increases.
WSD and WordNet similarity functions decrease the risk of creating exhaustive documents and queries. Especially, the documents contains numerous terms and expanding all of these terms can cause creating exhaustive documents and can also affect ranked results negatively. For this reason, only in DE stage, the original forms of documents are also kept to compensate the ranking weight score during the retrieval process. An example of document expansion and matching the document literally with the query, is given above. And the query expansion stage is illustrated in Figure 2.
For each expanded term in the query or document, similarity score is calculated. Different methods have been
proposed in the literature for determining the semantic similarity between terms [
TPS phase goes parallel with the expansion phase. While the documents and the queries are being expanded, each twosome terms are controlled in WordNet for existence. If the twosome terms exist in WordNet as a nounphrase, they are accepted as term-phrases. These terms are added to the both dictionary and the expanded document or query as a new term. In this work, 6,808 term-phrases are generated and added into dictionary for Wiki dataset. For example, a document or a query contains “hunting”, “dog” terms sequentially, these two successive tokens are searched as “hunting dog” in WordNet. If this phrase exists in WordNet, the document or query is expanded with the term “hunting-dog”. And finally the term phrase is added to the term phrase dictionary. TPS idea is showed in the equation (5);
1; PQ # R+; iS iS
T UVWSXSiY W%rdNet Z
T d%es Y%t UVWSXSiY W%rdNet where, and
T represents two successive terms.
The equations of final query selection and ranking score calculation with the original and expanded datasets are given below; 5 \ 1]^ # b ` a `_5 i= \ l\p lq \ jk l l ;
5 i= \ jk l l ; 5 p lq \ jk l l ; 5 ; c d ef g 1]^ 5(dfh ' ('d c d ef g 1]^ 5(dfh ' dmn]1 d c d ef g 1]^ 5(dfh ' dmn]1 d c PQo c r/ c d ef g 1]^ 5(dfh ' dmn]1 d c r/ ]1 PQo
Z 6) Where, qf_finali is the number of times the term appears in the final query which can be the original query or expanded using WSD and/or TPS . 5) 7) -) 9) Reranking is a methodical technique to reorder the initial retrieved documents for better results by increasing the precision. Basically, relevant documents that have low ranking weights are reweighted and reordered in a retrieved resultset. According to the literature several methods can be used for reranking, such as unsupervised document clustering, semi-supervised document categorization, relevance feedback, probabilistic weighting, collaborative filtering or a combination of them.
Some researchers proposes methods based on clustering, inter document similarity or user supported relevance data for document reranking [16][17][20]. Some has proposed a modification in weighting scheme proposed [13][14][15][18]. Most of the researcher studied on text retrieval. Similarly, an application of Lee’s method is performed on image dataset by Park et al. [19]. Image features used in proposed method are color histogram in HSV color space, Gray-scale co-occurrence matrixes and edge histograms.
In our work, we propose a new reranking approach in two phases. After the base retrieval results are generated, the result sets of each query and the base ranking scores ( ) are saved for the reranking phases. The first phase comprises reranking and reordering with the Boolean retrieval approach. The result sets of each query and the base ranking scores ( ) are again saved for the next step after the Boolean retrieval is performed. The main objective of the second step is reranking with the clustering algorithm. Firstly, expanded forms of relevant queries are appended to the end of the Boolean ranked result sets. After that, C3M clustering algorithm is executed on the new result sets and the similarity score of each document with its related query is calculated with C matrix ( ). Finally, new reranking score is combined with Boolean ranking score ( ) from the first step and with the query-document similarity score ) from the second step. The two phased reranking process is completed after the documents are ranked according to this score.
Boolean retrieval is the first phase for reranking. The Boolean retrieval is a model for information retrieval in which any query can be formulized in the form of a Boolean expression of terms. Query terms are combined with the classical Boolean operators AND, OR, and NOT [24]. In this work, each query’s terms are searched for the exact match by keeping the orders. It can be considered as the relational database query operators’, LIKE or CONTAINS functionality. Basic Boolean approach is showed in (11); Definite calculation for the reranking score is showed in (11)
1; # R+; l # R iSd%cxmeYt yzNX{WNS|xer} terms ~ith the e€ct %rder Z iSd%cxmeYt d%es Y%t yzNX{WNS|xer} terms ~ith the e€ct %rder " u1) > +Z „ + 1+) 11) 12)
By considering document , D matrix can be represented with respect to the two-stage probability model. Each element of C matrix, , (the probability of selecting a term of from ) can be founded by summing the probabilities of individual path from to where is the baseline retrieval score using WordNet (DE, WSD, WNSimScore) and QE, ‚@ is the new pivoted normalization ranking score after the retrieval process on the new resultset, is boolean ranking score using boolean retrieval (1 or 0), and l is the calculated ranking score for boolean retrieval phase. µ1, v1and β are constant parameters. In this work, their values are set as 0.8, 1, and 4 respectively for experimental results. 4.2 Reranking with C3M Clustering Clustering is a method for grouping a set of documents into clusters. The algorithms’ goal is to create clusters that are relevant internally, but clearly different from each other. In other words, documents within a cluster should be as similar as possible and documents in one cluster should be as dissimilar as possible from documents in other clusters [24].
Cover Coefficient-based Clustering Methodology (C3M) is originally proposed by Can and Ozkarahan [23] to cluster text documents. The base concept of the algorithm, the cover coefficient (CC), provides a means of estimating the number of clusters within a document database and relates indexing and clustering analytically. The CC concept is used also to identify the cluster seeds and to form clusters with these seeds. The retrieval experiments show that the information retrieval effectiveness of the algorithm is compatible with a very demanding complete linkage clustering method that is known to have good retrieval performance.
In their paper Can and Ozkarahan they showed that the complexity of C3M is better than most other clustering algorithms, whose complexities range from O(m2) to O(m3). Also their experiments show that C3M is time efficient and suitable for very large databases. Its low complexity is experimentally validated. C3M has all the desirable properties of a good clustering algorithm. C3M is a seed-based partitioning type clustering scheme. Basically, it consists of two different steps that are cluster seed selection and the cluster construction. D matrix is the input for C3M, which represents documents and their terms. It is assumed that each document contains n terms and database consists of m documents. The need is to construct C matrix, in order to employ cluster seeds for C3M. C, is a document-by-document matrix whose entries (1 < i, j < m) indicate the probability of selecting any term of from . In other words, the C matrix indicates the relationship between documents based on a two-stage probability experiment. The experiment randomly selects terms from documents in two stages. The first stage randomly chooses a term of document ; then the second stage chooses the selected term from document . For the calculation of C matrix, , one must first select an arbitrary term of , say, , and use this term to try to select document from this term, that is, to check if contains . Each row of the C matrix summarizes the results of this two-stage experiment.
Let ' indicate the event of selecting from at the first stage, and let '′ indicate the event of selecting , from at the second stage. In this experiment, the probability of the simple event “' and '′ ” that is, P(' , '′ ) can be represented as P(' )× P('′ ) . To simplify the notation, ' and '′ can be used respectively, for P(' ) and P('′ ), where; ' #
l…† ‡ˆ‰Š‹ l…ˆ) ; €Yd 'Œ #
l† ‡ˆŽŠ‹ lˆ†)
; ~here 1 ≤ i ; j ≤ m ; 1 ≤ k ≤ Y # 4
' ’ " '”“’) #1 this can be written as; ( # • ‡’1#1 " –’ " ), ~here 1 ≤ i ; j ≤ m) 13) 14) 15) 16)
In our work, we used C3M clustering algorithm during final reranking phase. For each query, the boolean reranking resultsets are utilized as inputs for clustering process. Expanded forms of queries are also appended into these resultsets. For each resultset, C3M algorithm is run and C matrix is constructed. C matrix includes similarity scores by keeping a document-by-document matrix. Since, the expanded form of query is appended as a document, query-by-document similarity scores ( ) are also generated for each query and document.
Both l and are used for final ranking score calculation. Since the calculation and results of these two values are different, these values should be approximated and compensated to each other mathematically. Formally, # “ " )]m—ee^ ]1’d o efd " ' )o efd˜ d
) 1++ " )]m™š] f mo efd) where, )]m—ee^ ]1’d o efd is the maximum boolean ranking score for the query resultset, ' )o efd˜ d specifies the percentage of ranking score effect for experiment, )]m™š] f mo efd is the maximum query-bydocument similarity score for the query. Final C3M ranking score equation is showed in (16) # l " u2) " v2)
Where, l is the Boolean retrieval score, is the compensated query-document ranking score and is the final ranking score. µ2 and v2 are constant parameters. In this work, their values are set as 0.9 and 1 respectively for experimental results. 5
WikipediaMM task provides a test bed for the system-oriented evaluation of visual information retrieval from a collection of Wikipedia images. The aim is to investigate retrieval approaches in the context of a larger scale and heterogeneous collection of images (similar to those encountered on the Web) that are searched for by users with diverse information needs. It contains 151,519 images that cover diverse topics of interest. These images are associated with unstructured and noisy textual annotations in English. WikipediaMM dataset includes 45 queries in 2009 sub-track [11].
The main focus of this work is to improve search results by two phased reranking. The set of initial retrieved documents are re-ordered for better results by increasing the precision. It is obvious that two phased reranking approach improves results over the baseline and over expansion results. The baseline retrieval, expansion and reranking methods are realized on Wiki 2009 sub-track [11]. We have participated in Wiki 2009 with 6 runs and 4 of our runs ranked the best MAP values.
In all of the runs, pivoted unique normalization is used. The documents are expanded with WSD and only noun and adjective representations (POS) are used. The original forms of documents are also kept to calculate the ranking weight score as a combination of original and expanded dataset weights.
The differences between the runs are based on the different techniques of query expansion and reranking. In the first run (200); the original forms of the queries are used in the retrieval process. In the second run (201); term phrases are selected and added to the queries. And the documents are retrieved with the expanded queries. In the third run (202); the expanded queries from the second run are used. In addition to this; the one-length queries are expanded with WSD. Starting from the fourth run, in the next three runs, different re-ranking methods are applied to the retrieved result set from the third (201) run. In the fourth run (203); Boolean retrieval is applied to the retrieved result set and the resultset is re-ranked according to this. The difference between the fifth run (204) and the fourth run is that only the documents in the result set above a threshold value are taken for the Boolean retrieval process. Finally in the sixth run (205), the resultset of the fourth run is saved and C3M clustering is applied to this result set.
In conclusion, expanding the query with WSD and term-phrase selection increases the quality of the retrieved result set and, reranking the retrieved result set improves precision values. The increase of precision values by reranking is represented in Figure 3 for Wiki 2009. As it can be seen from the MAP values in Table 1 for Wiki 2009, the best result obtained from the sixth run, in which the result set is re-ranked with C3M clustering. And the second best result obtained by reranking with Boolean retrieval. Our experimentation shows that reranking generated the best results among all participants (205 and 204).
ID 200 201 202 203 204 205 90,00 80,00 70,00 60,00 n io 50,00 s i ec 40,00 r P 30,00 20,00 10,00 0,00
MAP
This work is supported by Turkish National Science Foundation (TÜBTĐAK) under project number 107E217. [7] A. Tversky, Features of Similarity. Psychological Review, 84(4):327–352, 1977. [8] Gerard Salton, A.Wong, and C.S. Yang. A vector space model for information retrieval. Journal of the
American Society for Information Science, 18(11):613-620,November 1975. [9] E. Garcia. Implementation and application of term weights in mysql environment, 10 2006. [10] Chris Buckley. The importance of proper weighting methods. In M. Bates, editor. Human Language
Technology. Morgan Kaufman, 1993. [11] Theodora Tsikrika and Jana Kludas. Overview of the wikipediaMM task at ImageCLEF 2009, CLEF working notes 2009, Corfu, Greece, 2009 [12] Theodora Tsikrika and Jana Kludas. Overview of the wikipediaMM task at ImageCLEF 2008. In Evaluating Systems for Multilingual and Multimodal Information Access, Proceedings of the 9th Workshop of the Cross-Language Evaluation Forum, Lecture Notes in Computer Science, vol. 5709, pp. 539-550, Springer 2009. [13] Lingpeng Yang, Donghong Ji, Guodong Zhou, Yu Nie, Guozheng Xiao, “Document re-ranking using cluster validation and label propagation” Proceedings of the 15th ACM international conference on Information and knowledge management CIKM '06, pp. 690 – 697. [14] Jaime Carbonell and Jade Goldstein. The use of mmr, diversity-based reranking for reordering documents and producing summaries. In SIGIR ’98 Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, pages 335 336, New York, NY, USA, 1998. ACM. [15] Lingpeng Yang, Donghong Ji, Guodong Zhou and Yu Nie. Improving retrieval effectiveness by using key terms in top retrieved documents. Advances in Information Retrieval, pages 169 184, 2005. [16] Jaroslaw Balanski and Czeslaw Danilowicz. Re-ranking method based on inter-document distances.
Information Processing & Management, 41(4):759 775, 2005. [17] James Allan, Anton Leuski, Russel Swan, and Donald Byrd. Evaluating combinations of ranked lists and visualizations of inter-document similarity. Information Processing & Management, 37(3):435 458, 2001. [18] James Callan, W. Bruce Croft, and Stephen M. Harding. The inquery retrieval system. In Proceedings of the Third International Conference on Database and Expert Systems Applications, pages 78 83. SpringerVerlag, 1992. [19] Guhnan Park, Yunju Beak, and Heung-Kyu Lee. Re-ranking algorithm using post retrieval clustering for content-based image retrieval. Information Processing & Management, 41(2):177 194, 2005. [20] Kyung-Soon Lee, Young-Chan Park, and Key-Sun Choi. Re-ranking model based on document clusters.
Information Processing & Management, 37(1):1 14, 2001. [21] B. Chidlovskii, N. Glance, and A. Grasso. Collaborative reranking of search results. In Proc. AAAI-2000
Workshop on AI for Web Search., 2000. [22] K. Sugiyama, K. Hatano, and M. Yoshikawa. Adaptive web search based on user profile constructed without any effort from users. In Proceedings of WWW 2004, pages 675 – 684, 2004. [23] Can, F., Ozkarahan. E.A. [1990]. “Concepts and Effectiveness of the Cover Coefficient Based Clustering
Methodology for Text Databases”, ACM Transactions on Database Systems, Vol. 15, No. 4. [24] Manning D. Chirstopher, Raghavan Prabhakar and Schütze Hinrich. An Introduction to Information Retrieval, Cambridge University Press, 2009.