MRIM research group has participated in two tasks (ad-hoc image-based retrieval and case-based retrieval) of the ImageCLEF2012 Medical Retrieval track. In our contribution, we study the frequency shift problem that happens when using concepts instead of words as indexing terms. The main goal of our experiments is to check the validity of our new counting strategy of concepts (Relative Count), which is proposed as a solution to the frequency shift problem. In order to validate our new counting strategy, we compare the retrieval performance (represented by MAP) of some classical IR models using the classical counting strategy (count each concept as 1) with their performance using the new strategy. The results are promising, and using the new counting strategy shows a considerable gain in performance. We use in our experiments two supplementary resources: MetaMap as a text-to-concepts mapping tool, and UMLS as an external resource containing concepts.
We present in this paper the contribution of the MRIM1 research group in the ImageCLEF20122 Medical Image Retrieval task3.
The main goal of our experiments and contribution is to study the side-e ects of moving from the word-space to the concept-space on the classical Information Retrieval (IR) models. In other words, to study the side-e ects of using concepts instead of words as indexing terms on the classical IR models. Concepts are entry IDs in a speci c external resource, and each concept is associated to a set of strings that describe it.
However, in order to build a concept-based IR system, another component,
for mapping documents and queries text into concepts, is needed. These mapping
tools, e.g. MetaMap4 [
Therefore and as classical IR models directly or indirectly depend on the
shared terms d \ q between a document d and a query q in order to compute the
Relevance Status Value RSV (d; q) [
One solution to this problem is the supplementary disambiguation step that
is actually achieved alongside the mapping process [
The goal is to nally satisfy the following condition for a piece of text TXT : jTXT j =
X c2map(TXT) count c (1) where, jTXT j is the number of words in TXT , map(TXT ) is the set of all candidate concepts of TXT , and count c 2 R + is the new relative count of the concept c and we will explain in the following sections the algorithm of computing it.
This year, ImageCLEF2012 contains four main tracks: 1) Medical Image Classi cation and Retrieval, 2) Photo Annotation and Retrieval, 3) Plant Identi cation, and 4) Robot Vision. Medical Image Classi cation and Retrieval track contains three tasks: 1) modality classi cation, 2) ad-hoc image-based retrieval which is an image retrieval task using textual, image or mixed queries, and 3) case-based retrieval: in this task the documents are journal articles extracted from PubMed6 and the queries are case descriptions. We participated in the last two tasks: ad-hoc image-based retrieval and case-based retrieval. Table 1 shows some statistics on the data collections of the two tasks that we participated in. We only use the textual data.
This paper is structured as follows: Section 2 describes in details the problem that occurs when moving from the word-space to the concept-space, and it also 5 Uni ed Medical Language System (http://www.nlm.nih.gov/research/umls/) 6 http://www.ncbi.nlm.nih.gov/pubmed/ presents our proposed solution. Section 3 presents all technical details of applying our proposed solution to ImageCLEF2012 test collections. It also shows our formal runs and the obtained results. We conclude in section 4. 2
Computing Relative Concept Count
Our algorithm depends on the output of MetaMap as a mapping tool and on the
UMLS as an external resource containing the concepts. However, the algorithm
could be easily generalized because most mapping tools [
For a textual document d or a query q, mapping tools (e.g. MetaMap) extract noun-phrases from the text and try to map them into one or more candidate concepts of a speci c external resource (e.g. UMLS).
However, for a noun-phrase np, it is sometimes di cult to nd concepts
corresponding to the whole noun-phrase. Moreover, even if there are concepts
corresponding to the whole noun-phrase np, it is useful to return some concepts
corresponding to parts of np, because restricting our attention to the concepts
that only correspond to the whole phrase could lead to miss some related
concepts, or in other words, it could lead to lose in recall. Therefore, most mapping
tools do not only depend on the exact match to nd candidate concepts, but
they also generate some variants7 of the original noun-phrase [
In this study, we regroup all variants that correspond to the same part of the original noun-phrase into only one variant. Therefore, Table 2 become Table 3. 7 spelling variants, abbreviations, acronyms, synonyms, in ectional and derivational variants, or meaningful combinations of these. Our algorithm locally works at the level of noun-phrases not at the level of documents.
Each noun-phrase np is a sequence of words or a set of 2-tuples, where each tuple (w; i) contains a word w 2 W and the position i 2 N of w in np. Any variant v of np is also supposed to be a noun-phrase. By this way, it is possible to attach to each noun-phrase np, a set Vnp:
Vnp = fnpg [ fv1; : : : ; vjg where, fv1; : : : ; vjg are the variants of np that are generated by the mapping tool.
We de ne the function wrd that returns the set of word-position tuples of a speci c variant.
wrd : Vnp ! 2W N For example, suppose the variant v ="pneumonia x-ray" of the phrase "lobar pneumonia x-ray", then: wrd (v) = f(pneumonia; 2); (x ray; 3)g We also de ne for any variant v 2 Vnp, jvj = jwrd (v)j the number of words in v.
We de ne the function map that returns the candidate concepts of a variant v 2 Vnp. where C is a set of concepts. For example, suppose the variant v ="pneumonia x-ray" of the phrase "lobar pneumonia x-ray ", then:
map : Vnp ! 2C map(v) = fC0581647g
We will remove from Vnp all members v that do not have any candidate concepts map(v) = . For example, in the case of "lobar pneumonia x-ray" noun-phrase, we will remove the noun-phrase itself because it is not mapped into any concept. Finally, Vnp becomes: Vnp=f"lobar pneumonia", "pneumonia x-ray", "pneumonia", "lobar ", "x-ray"g It is possible to de ne a partial order < relation on the set Vnp as follow: 8v1; v2 2 Vnp; v1 < v2 i wrd (v1) wrd (v2) 8v1; v2 2 Vnp [ fRg, Therefore, it is possible to de ne a hierarchy HRnp on Vnp [ fRg, where: { v 2 Vnp [ fRg are the nodes. { R is an abstract root satisfying: 8v 2 Vnp; v < R. Moreover, jRj = 0. { The direct children ch(v) of any node v 2 Vnp [ fRg is de ned as follow: v1 2 ch(v2) i v1 < v2 and 6 9v3 2 Vnp; v1 < v3 < v2 { The direct parents pr (v) of any node v 2 Vnp [ fRg is de ned as follow: 8v1; v2 2 Vnp [ fRg; v1 2 pr (v2) i v2 2 ch(v1) For example, Fig. 1 shows the hierarchy of the noun-phrase "lobar pneumonia x-ray". 2.2
The main goal of the algorithm is to compute the relative count of candidate concepts, as follow: for a noun-phrase np, distributing the number of words jnpj of this noun-phrase on the candidate concepts of np and its variants. The algorithm respects two hypothesis: { the relative count of a concept is directly proportional to the number of words in the corresponding variant. { the relative count of a concept is inversely proportional to the ambiguity level of the corresponding variant. The variant that is mapped into a larger number of concepts is more ambiguous.
The input is the set Vnp that contains all variants of np, and the number of words jnpj in np. The output will be a set CC np of 2-tuples, and each tuple contains one of the candidate concepts and its associated relative count. The detailed algorithm is shown in Algorithm 1. 2.3
Assume np is the noun-phrase "lobar pneumonia x-ray ". The list of variant Vnp is: Vnp = fv1; v2; v3; v4; v5g (see Fig. 1). Figure 1 also shows the hierarchy HRnp of the set Vnp [ fRg. Initially, we have R = jnpj = 3 and 8v 2 Vnp; v = 0. We scan the nodes in breadth- rst order, that means, nodes will be scanned in the following order < R; v1; v2; v3; v4; v5 >.
By following the Algorithm 1, Table 4 shows the output set CC np. By consulting Table 4, we can see: P(c;countc)2CC np count c = jnpj = 3. 3
The main goal of our experiments is to show the validity of our new way of counting. We check this validity through comparing the retrieval performance of some classical IR models using classical concept counting method, to their performance using our new way of counting.
We use the Mean Average Precision (MAP) metric as an indicator to the retrieval performance of IR models. 3.1
In order to check the validity of our new way of counting, we use several classical IR models:
Algorithm 1: RelativeCount input : Vnp, jnpj output: CC np
C
R + 1 CC np = fg; 2 construct the hierarchy HRnp of the set Vnp [ fRg; 3 attach to each node n0 in HRnp a value n0 , where n0 is the total amount that is received from pr (n0) and should be distributed on the candidate concepts of n0 and its children ch(n0), starting by n0 = 0; 4 n is the current node, starting by n = R; 5 set R = jnpj; 6 scan HRnp in a breadth- rst way, starting from the current node n = R; 7 begin 8 for each child n0i 2 ch(n) do 9 compute the amount n0i that should be transferred from n to n0i: n0i = n0i + jnj+Pnn0j2jcnh(0inj) jn0jj ; end if n 6= R then compute the amount an that should be distributed on the candidate concepts map(n) of the current node n: an = jnj+Pnn0j2cjhn(jn) jn0jj ;
CC np = CC np [ f(ci; count cnip)g; for each candidate concept ci 2 map(n) do
compute the relative count: count cnip = jmaapn(n)j ;
end
end
change n to the next node according to the breadth- rst scan order;
go to line 7;
{ from probabilistic framework: we choose BM25 (2) [
s, k1, b, k3, , and are all parameters. They usually have the following
values: s = 0:2 [8]. k1 = 1:2, b = 0:75, and k3 = 1000 [
s) + s ajvddjl RSV (d; q) = jd \ qj
X tf t;q t2d\q
tf t;q tf t;d
d tf t;d + ajvdjl ln
N + 1
nt N nt
There are two di erent views for documents and queries. The rst one is the classical view, where both documents and queries are bags of indexing terms (e.g. words or concepts). The classical way of counting (count each concept or word as 1) is compatible with this view, and the previous de nitions of IR model components correspond to this classical view. We will present the second view, which is convenient to the relative count of concepts. In this view, some components of IR models should be rede ned.
Most mapping tools extract noun-phrases from the text of documents and queries. Therefore, any document d or query q is a sequence of noun-phrases: d =< np1; : : : ; npnd > q =< np1; : : : ; npnq > We rede ne the set CC np on the level of documents and queries instead of the noun-phrase level:
CC d = [ CC npi
CC q = [ CC npi According to our way of counting (Relative Count), the components of the IR models become: tf c;d =
X (c;ri)2CC d
ri jdj =
X (ci;ri)2CC d ri tf c;q =
jqj = jd \ qj =
X (c;ri)2CC q
X
X (ci;ri)2CC q ri ri ri (ci;ri)2CC d\q tf c;D =
X tf c;di di2D jDj = X
jdij di2D 3.2
We only use the textual part of the data collections of ad-hoc image-based retrieval and case-based retrieval tasks of the ImageCLEF 2012 Medical Image Classi cation and Retrieval track. Table 1 shows some statistics about these two data collections.
We use two types of indexing terms: { words (W): we eliminate the stop words and stem the remaining words using Porter algorithm to nally get the list of words that indexes documents and queries. { concepts (C): we use MetaMap for mapping the documents and queries text content into UMLS concepts. 3.3
The initial of our runs in the formal campaign is "LIG MRIM xxx". However, Tables 5 and 6 show the name and the description of our runs. The best MAP in the ad-hoc image-based retrieval task (only text) is 0.2182, and the best MAP in the case-based retrieval task (text only) is 0.1690. 3.4
In this section we show the validity of our new method of concept counting (RelativeCount), through comparing the retrieval performance of IR models with or without using the relative count. The only type of indexing terms that is used in this section is concepts. We count concepts in two ways: the classical count (count each concept as 1) and the relative count (Algorithm 1).
Table 7 shows the results of applying IR models to the image2012 collection (see Teble 1).
Table 8 shows the results of applying IR models to the case2012 collection (see Teble 1). We only map the title and the abstract parts of documents into concepts Tables 7 and 8 show that we have a considerable gain in retrieval performance when using the relative count instead of the classical one. The gain is clearer in the case of short documents and queries (image2012) than the case of long documents and queries (case2012).
Tables 5 and 6 show that using words as indexing terms is still more e ective (from the retrieval performance point of view) than using concepts.
Concerning our formal contribution in the ad-hoc image-based retrieval task, we got a middle-rank. We still far from the best formal run. However, our contribution in the case-based retrieval task was more encouraging. We are ranked the second in the nal list. We made a late fusion between two result set: 1- one resulting from applying DIR model to the case2012 corpus using words as indexing terms, and 2- another one resulting from applying DIR model to case2012 corpus using concepts as indexing terms. We present in this paper the contribution of the MRIM research group in the ImageCLEF2012 Medical Image Retrieval task. We describe the frequency shift problem that happens when moving from the word-space to the concept-space. The source of this problem is the heterogeneous change in the frequency of indexing terms when moving from the word-space to the concept-space.
We propose a solution to the frequency shift through a new counting strategy. Our counting strategy (Algorithm 1) depends on the hierarchy that could be built from the output of mapping tools. It also depends on the following two hypotheses: { the relative count of a concept is directly proportional to the number of words in the corresponding text. { the relative count of a concept is inversely proportional to the ambiguity level of the corresponding text.
For validating the e ectiveness (from the retrieval performance point of view) of our new counting strategy, we participated in the ImageCLEF2012 campaign, more precisely, in the ad-hoc image-based retrieval and case-based retrieval tasks. Our experiments only depend on the textual data. For mapping text into concepts, we use MetaMap as a mapping tool and UMLS as an external resource containing concepts. In the case-based retrieval task, we only map the title and abstract of each document (we do not map the fulltext ).
In the ad-hoc image-based retrieval task, we got a middle-rank. We still far from the best formal run. However, our contribution in the case-based retrieval task was more encouraging. We are ranked the second in the nal list.
Moreover, the supplementary results that we present in this paper show a considerable gain in retrieval performance when applying our counting strategy (Algorithm 1) comparing to the classical counting strategy (count each concept as 1). 8. Amit Singhal, Chris Buckley, and Mandar Mitra. Pivoted document length normalization. In Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, SIGIR '96, pages 21{29, New York, NY, USA, 1996. ACM. 9. Chengxiang Zhai and John La erty. A study of smoothing methods for language models applied to ad hoc information retrieval. In Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, SIGIR '01, pages 334{342, New York, NY, USA, 2001. ACM.