Following constructivist models of contextual learning, knowledge acquisition goes beyond mere absorption of isolated facts, and, instead is enabled, stimulated and supported by related existing knowledge and experiences. In this paper, we discuss a range of query expansion and result list reranking techniques aiming to preserve contextual dependencies among retrieved documents and, thereby, enhancing the performance of learning-centric search engines. Our empirical evaluation is based on a snapshot of Wikipedia and suggests signi cantly increased usability during an interactive user study.
The Internet connects vast numbers of knowledge resources
that are assumed to contain the necessary information to
answer most general questions occurring to common users [
Despite the wide acceptance and demonstrated success of constructivist methods in pedagogics, common retrieval models do not support any notion of contextual learning. Document relevance is largely judged in isolation and listwide ranking considerations rarely go beyond diversi cation e orts. Consequently, state-of-the-art search engines cannot be considered ideal learning environments.
We believe that this shortcoming is manifested in threefold form: (1) Raw textual documents may not be the ideal retrieval unit. Due to high variance in length and an often non-uniform distribution of relevant factoids across documents, learning may be better supported by a ner granularThe copyright for this paper remains with its authors.
Copying permitted for private and academic purposes. ity. (2) The user's learning intent by de nition characterizes a degree of unfamiliarity with the desired information. To account for this fact, query formulation should be guided not just by user-speci ed terms but also by connections and dependencies dictated by the studied subject matter. (3) The probability ranking principle is based on point estimates of relevance. While this approach ensures maximum relevance at early result list ranks, it ignores important causal dependencies between documents, potentially resulting in a chaotic and didactically dissatisfying ordering of material.
While paragraph retrieval, query expansion and result list re-ranking are known techniques, this work aims to use and combine them to optimally support the goal of contextual learning in Web search. We believe that as such, this overview, along with the results of an empirical user study, will be of interest to the community.
The remainder of this paper is structured as follows: Section 2 gives a necessarily brief introduction into the concepts of contextual learning as well as domain expertise upon which this work builds. Section 3 formally describes three concrete techniques that address the previously enumerated shortcomings of state-of-the-art retrieval models. Section 4 puts these methods to use in a real-world learning-centric search scenario. Finally, Section 5 concludes with a brief discussion of our ndings as well as an outlook on future directions in this domain. 2.
This section gives a brief overview of related work dedicated to two directions. Beginning with a brief discussion of formal constructivist theories, we proceed to a more applied line of work dedicated to estimating user domain expertise during Web search.
Jean Piaget rst proposed the theory of \Cognitive
Development" that considers knowledge to be an actively
constructed complex system of experience, stage of cognitive
development, cultural background and personal history [
Over the past years, the study of user's existing
domainspeci c knowledge has led to a wide number of innovations
in user understanding. White et al. [
In this section, we formally describe three techniques supporting contextual learning during search. Beginning with a paragraph retrieval model, we move on to pseudo-relevance feedback-based query-expansion as well as a method for dependency-based result list re-ranking. 3.1
At the core of our method, we rely on a standard tf-idf model scoring documents d in response to a query q according to the frequency at which query term t occurs in d. While this score tft;d, is higher for documents that contain more query terms it has the drawback of treating all terms as equally important. To apply a non-uniform term weighting, de ned by the speci city of a term throughout the collection, we further introduce the notion of t's document frequency dft as the number of unique documents containing t. With both components in place, our retrieval model score s is given by s(q; d) =
X tft;d t2q log
N dft wt (1) where N denotes the total number of documents in the collection and wt is an additional term weight that is uniformly set to 1 for all original query terms. In the following section we will discuss a query expansion scheme that may add new terms at a wt 6= 1.
In this work, we attempt to better contextualise search results by considering documents of varying granularity. Depending on the concrete model, d can either be a complete document or a single paragraph extracted from a longer text. We assume that there are reliable techniques for breaking up documents into paragraphs. Section 4 will introduce the concrete paragraph extraction scheme that was applied in our experimental setup. 3.2
Formulating e ective queries has been shown to be a hard
task that requires intimate familiarity with the subject
domain as well as the underlying document collection [
To address this issue, we introduce a pseudo relevance
feedback (PRF) step. Instead of following the established
approach by Rocchio [
We formally capture this intuition by collecting the set of top-k most highly scoring documents Dq;k according to the original query q. For each document in this set, we follow outgoing hyperlinks and collect the bag of words Tnew of all terms appearing in the titles of linked-to documents. Intuitively, Tnew represents a description of the required reading for the original selection of highly relevant documents. To account for the relative importance of the newly added terms, we normalize the contribution of each term by jTnewj, the size of the bag of words. In this way, terms that occur in multiple titles or titles that are linked to frequently are weighted more prominently than singleton occurrences.
At this point, due to our normalization scheme, the sum of all newly added terms amounts to the same cumulative weight as a single original query term. In order to control the relative importance of original and newly added terms, the parameter wadd determines the \number" of virtual terms to be added.
wt = (1;
for t 2 q wadd count(t;Tnew) ; otherwise
jTnewj
Finally, the expanded query q0 is given by the original query q as well as the linked title terms Tnew, which are added with their respective importance weights wt.
q0 = q [ Tnew 3.3
Web search-based learning can result in jumping back and forth between documents. This may happen because a document covers material that possibly requires previous knowledge from another source indicated by a reference. This induces a dependency structure over the documents. As motivated in Section 2, the order of material can have significant implications on learning rate and knowledge retention. As consequence, we would like to present documents in an ordering that respects this referral structure.
We again consider Dq;k, the top-k retrieved documents and compute the number of times each document is referred to from within Dq;k. Let us call this quantity the document's link count c(d). (2) (3) where is a scaling weight to boost the resulting link score l(d) into the regime of s(q; d). Our nal dependencyaware retrieval model score s0(q; d) is given by a weighted mixture of the original score s as well as l(d), the document's importance in the context of Dq;k.
s0(q; d) = s(q; d) + (1 )l(d) (5)
Our empirical investigation of the practical usefulness of the presented methods is based on a recent snapshot of Wikipedia. The platform represents a popular knowledge resource and is consulted at high frequency every day. We provide a basic retrieval system implemented in the Apache Lucene framework1 and index either full articles or paragraphs as the atomic retrieval unit. Due to Wikipedia's article structure, paragraph splitting is a straight-forward process guided by the original article's sections (identi ed by \==" and \===" delimiters). To ensure realistic and informative document titles, paragraphs concatenate their parent article's title with their own section heading.
We study the following 23 = 8 combinations of experimental conditions:
To evaluate these conditions, we select 10% (11 out of
107) of the INEX 2010 Ad Hoc queries [
Each question is scored according to the number of correct answers divided by the total number of choices, where \correct" refers to either the selection of a correct answer choice or the leaving blank of a wrong option. To further penalize random guessing, we subtract points for wrong answers, bounding the score per question in [0; 1].
score = max (#correct #wrong; 0) #correct + #wrong (6)
With this scoring scheme in place, workers, topics and experimental conditions can be evaluated by averaging across all scores of the respective selection. 4.1
For each of the 8 experimental conditions and 11 topics we collect answers from 5 individual workers, leading to a total of 440 experiment submissions.
Table 1 shows the scores per experimental condition. Topic numbers are denoted in columns. The experimental conditions are encoded according to the respective components used. \A" and \P" refer to full article vs. paragraph retrieval. \E" indicates the use of query expansion and \R" the dependency based re-ranking. The right-most column details each system's mean score across topics. Similarly, the bottom-most row contains mean scores per topic across all systems, capturing the di culty of each topic and the corresponding questions.
The correctness scores range from 35.25% to 73.33% with the overall mean score being 57.77% (median 59.37%). At a glance, we note a considerable variance in the di culty of individual topics, while the performance of the compared systems is more closely tied. For greater ease of inspection, in the following, we provide a number of detailed views extracted from the overall data.
Let us begin by evaluating the e ect of document granularity. Table 2 shows the performance di erence observed when switching from retrieving full documents to paragraphs in otherwise identical experimental conditions. The scores show that for most experiment conditions, performance scores are signi cantly greater when retrieving paragraphs instead of full articles. Only the re-ranked and expanded condition (AER vs. PER) performs better when retrieving articles. On average, switching to paragraph retrieval introduced a 4.99% increase in scores. We suspect that the reason for this tendency may lie in the di erent document lengths of articles and paragraphs. Highly ranked paragraphs provide a high density of relevant information whereas full articles can contain lengthy stretches of unrelated content.
Table 3 highlights the e ect of adding query expansion or
result list re-ranking to a reference system. The rst column
indicates the reference system, to which we add either query
expansion (E) or result list re-ranking (R), while keeping all
other conditions stable. We can observe that
dependencybased re-ranking has a mild positive e ect on the users'
correctness scores while query expansion, in the vast majority
of investigated conditions, shows a negative e ect. We
suggest that the query expansion mechanism as implemented,
cannot e ectively address the wide variety of query subjects
and lengths. It can conceivably bene t from an interactive
implementation, where a user can take in uence on the term
selection and determine the impact upon its level of expertise
as elaborated by Vakkari [
In this paper, we present initial results of an ongoing investigation into the suitability of established retrieval techniques as well as variants thereof, for the task of contextual learning in Web search. Inspired by constructivist theories of learning and knowledge formation, we propose a paragraph retrieval model, a document title based query expansion scheme as well as a result list re-ranking method that aims to preserve order dependencies in the material.
We conducted a learning-centric user study on the basis of the Wikipedia corpus during which participants used varying combinations of the above components to help their search sessions. The experiment showed a strong positive e ect of using paragraphs instead of full documents as retrieval units. While the query expansion approach turned out to result in an overall negative e ect, dependency based re-ranking resulted in an increased performance score on average. While this study is limited in both the size of the user base as well as the diversity of information needs, it shows promising potential and highlights the importance of explicitly accounting for contextual learning during the retrieval process.
There are several exciting directions of future inquiry. To ensure comparability between limited-scale results, the present study relies on xed queries and only incorporates real users as result list consumers. While this paradigm showed good results, it would be interesting to study the proposed techniques in a truly interactive search setting in which the users themselves formulate their queries. In such a setting, one can imagine a wide range of interesting controls that enable the user to specify the exact amount (e.g., in terms of number of pages or minutes worth of reading) of material to retrieve as well as its topical focus. Further, a user could interactively adjust a wide range of parameters for the search engine presented in Section 3 or interactively select additional query terms to obtain better search results. According to Piaget's \Cognitive Development" theory, the contextual learning e ect can increases with the possibility to actively participate in the learning step, e.g., the searching step for learning-based search engines.
Additionally, the present study focuses on point estimates of factual knowledge acquisition. In the future it would be interesting to conduct more longitudinal investigations of learning rates and knowledge retention in the true constructivist spirit.
Finally, the task of contextual learning in Web search is an exciting environment for user modelling and personalization e orts in which notions such as domain expertise or preferred reading levels will play a key role.