Polyrepresentative Clustering: A Study of Simulated User Strategies and Representations

Abstract

The principle of polyrepresentation and document clustering are two established methods for Interactive Information Retrieval, which have been used separately so far. In this paper we discuss a cluster based polyrepresentation approach for information need and document based representations. In our work we simulate and evaluate two possible cluster browsing strategies a user could apply to explore the polyrepresentative clusters. In our evaluation we apply information need and bibliographic features on the iSearch collection. Our results suggest that polyrepresentative cluster browsing may be more e ective than exploring a ranked list.

Introduction

Interactive Information Retrieval (IIR) systems are supposed to support users to satisfy their information need beyond typing in queries. Unlike traditional rank based retrieval, interactive systems improve the user's search experience by providing extended means for user interactions in the overall search process. To this end, polyrepresentation has been identi ed as an important principle in IR [ 1 ]. The principle suggests that if multiple cognitively di erent (coming from di erent users) representations (i.e., reviews, ratings etc.) and functionally (coming from the same user for di erent purpose) di erent representations (i.e., title, abstract, references etc.) point to an information object then it is likely to be relevant to the user's information need. This situation is depicted in Figure 1. Let us assume R represents the relevance of a representation, hence R1 denotes the documents relevant to representation 1, R2 to representation 2 and so on, so the documents in R1; R2 and R3 are only relevant to these individual representations. The intersection of the two representations, i.e. R12 R13 and R23 holds the documents relevant to the two respective representations, and the intersection of all three representation, R123 is the total cognitive overlap, the set of documents relevant w.r.t. all representations. R0 the set of documents not relevant to any representation at all. According to the principle of polyrepresentation this set is supposed to hold the most relevant documents as evaluated in [ 2 ]. This notion is shown in Figure 1. The principle of polyrepresentation has been evaluated so far in ad hoc retrieval and is used to create a ranked list. The actual challenge lies in modelling and re ecting user preferences in the context of R3

R13

R12 R123

R23

R0

R2

Total Cognitive Overlap the principle of polyrepresentation. A system may be able to combine di erent representations, but the system initially does not know whether and to what degree the user prefers some of these representations { for instance, is a user interested in the title but not references? A binary overlap computation found in most of the literature is not su cient to cover such a varying importance of the representations. One approach to mitigate this is to let the user decide about their preference during the search session. To this end we propose to combine document clustering and polyrepresentation. From this we can derive a \polyrepresentation cluster hypothesis"{ documents relevant to the same representations should appear in the same cluster [ 3 ]. Thus, we argue that instead of a ranked list, users may be presented with the clusters which represent the overlap shown in Fig. 1. By browsing the clusters and thus determining the sequence of visited clusters, the user got stronger means at hand to explore the results according to their interests. In this study an attempt is made to explore the potential and limitations of cluster-based polyrepresentation as an alternative to a result list organised in a single sequential list.

In Section 2 the cluster-based polyrepresentation is highlighted and in Section 3 our evaluation. A discussion and conclusion in given in Section 5. 2

Polyrepresentation and Document Clustering

The document clustering techniques in IR are proven e ective for enhancing the overall search process [ 4 ]. They drive their justi cation from the well-known cluster hypothesis [ 5 ]. It is argued in the literature that clustering helps users in interactive information retrieval when it is di cult for them to specify information needs [ 6 ]. In contrast to the traditional heuristic clustering approaches, an Optimum Clustering Framework (OCF) has been proposed [ 6 ], with a sound theoretical justi cation for probabilistic document clustering. The framework utilizes so-called query sets, by following the cluster hypothesis in a reversed order: documents relevant to same queries should appear in the same cluster. In a nutshell, OCF-based clustering represents each document d as a vector (d) = (P (Rjd; q1); : : : ; P (Rjd; qn)) of the probability of relevance of the document with respect to each query in the query set. Traditional clustering algorithms can then be applied to this representation. This notion goes along with polyrepresentation based document clustering as described in [ 3 ], which states that the polyrepresentative overlaps as described in Figure 1 could be generated with the help of document clustering. In order to implement documentbased polyrepresentation clustering, we employ the OCF-based notion of query sets. Thus for our polyrepresentation based clustering approach we intend to discover the possible clusters for the polyrepresentative sets R by estimating the degree of overlap, in this case the probability of relevance of each representation to the overlap. The vectors for information need based representations ri 2 REPin for document d become in(d) = (P (Rjd; r1); : : : ; P (d; rn)) : Similarly, the vector for document-based representation rdi 2 REPdoc becomes doc(d) = (P (Rjrd1; q); : : : ; P (Rjrdm; q)). In previous work we evaluated the effectiveness of polyrepresentative clustering using in and doc separately [ 7 ]. One of the contributions of this work is to evaluate the concatenation of both vectors to a vector (in doc) 2 Rn+m with

(in doc)(d) = (P (Rjd; r1); : : : ; P (d; rn); P (Rjrd1; q); : : : ; P (Rjrdm; q)) : This way we combine document and information need polyrepresentation, which to our knowledge has not been tried before, the motivation to combining REPin and REPdoc was to explore whether such a combination contribute in improving retrieval. The vectors can then be used to cluster the documents with a suitable clustering function. Furthermore the single probabilities of relevance can be combined to create a within-cluster ranking that the user can explore. The evaluation of a cluster-based polyrepresentation approach poses many challenges, among them are nding the total cognitive overlap cluster, cluster order and the number of picked document from each cluster.

In [ 3 ] it is identi ed that cluster ranking methods are helpful in identifying the candidate cluster for the total cognitive overlap, further in [ 7 ] the initial evaluation of the polyrepresentative clustering approach is presented for information need based polyrepresentation and document based polyrepresentation. In this work we explore the e ects of cluster based polyrepresentation approach on the combination of both the information need and document based representations, as expressed in the document vector (in doc) and a further combination method described in the next section. This should give us an idea if a richer representation is bene cial for our approach. In Section 3.3 we present strategies to simulate the user behaviour, i.e. some naive and basic browsing strategies. Here the goal is to demonstrate that o ering cluster-based interaction means in a polyrepresentative environment can indeed lead to a more e ective search.

Evaluation

3.1

Collection

The goal of our evaluation is to demonstrate if a richer representation, including both information need and document polyrepresentation, leads to further improvements. We also look at applying di erent user-based exploration strategies. To conduct our experiments, the PF part of the iSearch [ 8 ] collection is used. This sub-collection contains full text physics articles. The collection comprises 65 search tasks, where each search task is expressed in ve information need (IN) representations, i.e., Search Terms (st), Work Task (wt), Current Information Need (cn), Ideal Answer (ia) and Background Knowledge (bk). These ve representations build the REPin part of the experiments. For document based polyrepresentation; Title (ti), Abstract (ab), Body Text (bt), References (re) representations were extracted from full text articles. An additional context representation has been built based on the citation data available in the collection as described in [ 7 ]. All these representations constitute the REPdoc part of the experiment collection. We report the results for the concatenation of the REPin and REPdoc (referred to as REPconc). Furthermore, as previous experiments in polyrepresentation suggest not all representations may be equally e ective, we look at pairwise combinations of individual representations comprised in REPin and REPdoc, respectively. We refer to this as REPcomb. For example, (ti ab) denotes the combination of title and abstract, (ct re) means context combined with references. In order to estimate the P (Rjd; ri) and P (Rjdri; q) in absence of actual relevance judgements for each representation, the BM25 based documents weights have been computed for every information need representation REPini and each document representation REPdoci , respectively, using the Terrier IR platform [ 9 ]. These weights constitute the document vectors for clustering, as described in Section 2. To cluster the document vectors we used a standard kmeans implementation in Matlab2011 with 'cityblock' distance while setting k to 2jREP j (the motivation for computing 2jREP j clusters was to match the number of possible overlaps as shown in Fig. 1 for k = 3). The k for REPconcwas set to 210 and for REPcomb to 22 (as we only look at representation pairs. As a baseline for REPconc we created a ranked list from the actual BM25 document weights for all 10 representations fused together using the CombSum fusion method [ 10 ]. Similarly, for REPcomb the BM25 weights for the two representations in the pair were combined together using CombSum to create the respective BM25 baseline. The same strategy was applied to create a within-cluster ranking of documents belonging to a cluster. In our experiments we used graded scale relevance for computing N DCG@k; for P @k the 4-point graded scale was reduced to binary values, i.e., rel = 0 was mapped to non relevant and rel > 0 was mapped to relevant. We map n-tier relevance values to binary ones as one of the user strategies below assumes that a binary judgement is made. 0 http://itlab.dbit.dk/~isearch/ 3.2

Cluster Ranking

To simulate the user behaviour regarding the possible sequence in which clusters could be picked by the user or presented to the user, we ranked clusters using di erent criteria. The motivation of choice of such criteria was to use only information available in the cluster without relying on some external cluster quality measure. The two of such criteria were arithmetic mean and geometric mean as described in [ 11 ]. The arithmetic mean of a cluster C was computed as: arith(C) = jC1 j Pd2C Pin=1 P r(Rnjd;ri) , while the geometric mean of a cluster C was computed over the summed scores of the documents in the cluster as geom(C) = Qd2C Pin=1 P r(Rnjd;ri) jC1 j . Besides these the OCF based (expected F-measure (eF))[ 6 ] was derived as follows. For a cluster C in the clustering C let (C) = jCj1 1 P(dl;dm)2Ci Ci (dl)T (dm)(l 6= m) if jCj > 1; and 0 otherwise. Then the expected pairwise precision of C is dened as (C) = jCj (C). Likewise, the expected recall is de ned as (C) = jCij(jCij 1) (Ci). Based on these the expected F-measure is computed as: eF = (1C) +2 (1C) . Besides these measures we used the sparsity density, which is computed over the document representation matrix which constitutes the cluster. For example, if a cluster C holds jCj documents having jREP j representations then this makes a jCj jREP j matrix Mc where P (Rjd; ri) becomes an element of matrix Mc. Thus, the sparsity of the Mc becomes the number of non-zero values in the matrix i.e., P (Rjd; ri) > 0 , which could be denoted as jMc > 0j. We then divided it with the total number of elements in the cluster matrix jMcj to indicate the Sparsity Density as: SD(C) = jMc>0j . jMcj 3.3

Cluster Browsing Strategies

In order to evaluate the polyrepresentation based document clustering approach we use a simulated user methodology [ 12 ]. The rst strategy strategy-1 is described in [ 7 ], where for each query q the user is assumed to look at top l documents from each cluster. The sequence of clusters the user is visiting and the l documents in each within-cluster ranked list examined by the user create an arti cial ranked list made of the documents and their sequence the user is assumed to be visiting them when exploring the polyrepresentative clusters. To simulate this, the clusters need to be ranked on the basis of some cluster quality criteria. The rst cluster to be presented to the user is supposed to represent the total cognitive overlap as it is assumed to contain documents relevant to all representations involved. To check if a cluster browsing strategy is more e ective than browsing a single ranked list, the resulting arti cial cluster based ranked list is re-ranked and is evaluated against the actual BM25 ranking (our baseline as discussed above).

The second simulated user strategy, strategy-2 , is as follows: we apply cluster ranking to simulate the sequence of clusters the user is visiting. We also create a ranked list of documents in each cluster as described above. The rst cluster will be presented to the user; from its ranked list the user examines the rst document and looks at the second document only if the previously visited document would be relevant (hence the binary relevance judgements described above). This procedure continues until the user comes across a non-relevant document in the cluster. When user encounters a non-relevant document, user moves on to the next cluster in the cluster rank. For each cluster this procedure is repeated { the user is assumed to examine the documents in the within-cluster ranking until a non-relevant document is reached and proceeds to the next cluster. In any case the rst document of each cluster is added to the ranked list. Again we can create an arti cial ranked list from the visited documents re-rank them and evaluate them against the BM25 baseline. 4

Results and Discussion

For strategy-1 and REPconc we compared the created cluster based ranked list against their BM25 baseline, in Table 1 and 2, the entries in bold show the average performance improvement. The entries marked with ( ) are statistically signi cant based on two tailed paired sample t-test at 95% con dence intervals. The performance improvement for strategy-1 regarding REP concatenated to some extent con rms that the multiple representations of functionally and cognitively di erent nature could be useful for the performance bene t. But we can also observe a rather negative e ect on the overall performance when we concatenate IN and document representations { the results for REPconc lie between the values for separate document and IN polyrepresentation that were reported in [ 7 ]. Given the lower overall results for IN based polyrepresentation, this could have been expected. However, it should be noted that for REPconc we were able to beat the respective BM25 baseline signi cantly for NDCG@30 and P@30, although these values are still below the ones for individual document polyrepresentation.

BM25 arithMean eF

geomMean SD 0.0769 0.0769 0.0462 0.0477 0.0359 0.0390 0.0323 0.0354 0.0256 0.0313 0.0769 0.0769 0.0477 0.0477 0.039 0.0390 0.0354 0.0354 0.0313 0.0313 0.0769 0.0477 0.0390 0.0354 0.0313

The evaluation results for strategy-2 , described in Section 3.3 are given in Table 3 for both P @k and N DCG@k. Performance of strategy-2 remains better than the baseline on average, but the overall improvement is not statistically signi cant. The actual set back for our strategy-2 of user interaction is the very strict assumption that the user moves to a di erent cluster after observing the rst non-relevant document. But even if the top-ranked document is not relevant, those appearing at second and third position in the cluster document rank could 0.0399 0.0430 p@10 0.0462 0.0477 0.0433 0.0499 p@15 0.0359 0.0390 ment based representations has been explored along with the cluster browsing strategies for simulating the user interaction in context. The concatenations and combinations of various representations were compared against respective BM25 document rankings. The evaluation results con rm ndings in previous studies that cluster-based polyrepresentation has potential bene ts in interactive IR. However, a concatenation of IN and document based polyrepresentation does not seem to be useful as results are somewhat between those for IN and document polyrepresentation alone. Moreover the ndings reveal that di erent combinations of fewer individual representations do improve performance and a cluster-based approach seems promising here as well. The cluster browsing strategy-2 appears useful, however need to be adapted further as it turns out to be too strict. In our future work we will re ne and apply di erent cluster browsing strategies, based on strategy-1 and strategy-2 discussed here. We will also look at a di erent strategy to combine IN and document based polyrepresentation, where each IN representation is matched against each document representation.

References

1. Ingwersen , P. , Jarvelin, K. : The Turn: Integration of Information Seeking and Retrieval in Context. Springer-Verlag New York, Inc., Secaucus, NJ, USA ( 2005 )

2. Skov , M. , Larsen , B. , Ingwersen , P. : Inter and intra-document contexts applied in polyrepresentation for best match IR . Information Processing & Management 44 ( 5 ) ( 2008 ) 1673 { 1683

3. Frommholz , I. , Abbasi , M. : On clustering and polyrepresentation . In: Proceedings ECIR2014 . ( 2014 ) 618 { 623

4. Tombros , A. , Villa , R., Van Rijsbergen, C. : The e ectiveness of query-speci c hierarchic clustering in information retrieval . Information Processing & Management 38 ( 4 ) ( 2002 ) 559 { 582

5. van Rijsbergen, C.J.: Information Retrieval. Butterworths , London ( 1979 )

6. Fuhr , N. , Lechtenfeld , M. , Stein , B. , Gollub , T. : The Optimum Clustering Framework: Implementing the Cluster Hypothesis . Information Retrieval 15 ( 2 ) ( 2011 ) 93 { 115

7. Abbasi , M.K. , Frommholz , I. : Exploiting Information Needs and Bibliographics for Polyrepresentative Document Clustering . In: Proceedings of the First Workshop on Bibliometric-enhanced Information Retrieval . ( 2014 ) 21 { 28

8. Lykke , M. , Larsen , B. , Lund , H. , Ingwersen , P. : Developing a test collection for the evaluation of integrated search . In: Advances in Information Retrieval . Springer ( 2010 ) 627 { 630

9. Ounis , I. , Amati , G. , Plachouras , V. , He , B. , Macdonald , C. , Lioma , C. : Terrier: A High Performance and Scalable Information Retrieval Platform . In: Proceedings of ACM SIGIR'06 Workshop on Open Source Information Retrieval (OSIR 2006 )

10. Wu , S. : Data Fusion in Information Retrieval. Springer, Heidelberg ( 2012 )

11. Kurland , O. , Raiber , F. , Shtok , A. : Query-Performance Prediction and Cluster Ranking: Two Sides of the Same Coin . In: Proceedings of the 21st ACM international Conference on Information and Knowledge Management - CIKM ' 12 . ( 2012 ) 2459 { 2462

12. Azzopardi , L. : The economics in interactive information retrieval . In: Proceedings of the 34th international ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2011 ), New York, New York, USA, ACM Press ( 2011 ) 15 { 24