In recent years there has been an increasing research interest in novelty/diversity detection in Information Retrieval and in Recommendation Systems. We propose a model that increases the novelty of recommendations using a context user pro le that was created automatically using self-organizing maps. Our system was evaluated on the Reuters Corpus Volume 1 and our experiments show that ltering the recommended items using a novelty score derived from the contextbased user pro le provides better search results in terms of novel information that is presented to the user.
This work was supported by the Ministerio de Educacion y Ciencia under the grant N. TIN2011-28538-C02, Novelty, diversity, context and time: newdimensions in next-generation information retrieval and recommender systems. doesn't know whether the user wants to know something about the neighborood in New York, about the cocktail, or about the Indian tribe: the query has several possible interpretation, and whoever formulated the query is interested in general in only one of them. Without further speci cation, the safest bet for the server is to provide a diverse result set, that is, one that covers all these topics, possibly in an amount proportional to the estimated a priori user interest (one can assume, for instance, that more people are interested in New York than in the Indian tribe). Even if the query is not ambiguous and the results are about what the user really meant (say, the neighborhood in new york), the user would want every document to be novel, that is, to provide information that is not present in other documents. A highly informative text about the history and the human landscape of Manhattan is probably a very good rst result, but another document almost identical to the rst is not an equally desirable second result: the information that it contains has already been seen. That is, every interpretation of a query contains several aspects, and the person who formulated it will be interested, to some degree, in all of them. These considerations highlight an important di erence between diversity and novelty. Diversity is something that the user wouldn't really want: the person interested in the manhattan cocktail would be very happy to receive results only about the cocktail. Diversity is needed mainly by the server, which doesn't know enough about the user true intentions. Novelty, on the other hand, is something the user wants, since she will be interested in all the aspects of her query. Novelty is a way to avoid redundancy, while diversity is a way to deal with the server's ignorance.
If we have access to a model of the user's interests, then it is possible to reduce ambiguity and, therefore, to reduce the need for diversity, concentrating only on increasing novelty. We present a method for increasing novelty that relies on a context model built on texts previously seen by the user. The scenario that we use here to exemplify the working of our method is that of the recommendation of news, and the context is composed of past news that the user has considered interesting. This is just one possible way in which context can be gathered. Our model is very general and can be used to represent text or multimedia data. In past work, we have used, for example, the contents of the user's hard disk to represent his main interests [7]. In this paper we show and evaluate a modi cation to our model with the purpose of increasing the context coverage of the recommendations, that is, the fraction of the user context that the items lter 6 context model short time update
marker irreversible update recommended items will cover, trying to avoid items that refer to parts of the context already covered by previously seen items.
One important distinction between this work and others on novelty and diversity in recommendation is that we are dealing with a stream of news, that is, with a continuous{ potentially in nite{interaction, while typical recommendation systems work based on sessions: the user chooses an item or requests a recommendation, and a nite set of results is shown. This operation may be repeated several times, as the user selects several items and receives correspondingly changing recommendations. No work, to the best of our knowledge, has considered novelty in a session-less situation, in which a countable stream of items arrive and a system has to decide whether they are relevant for the user at that moment. Note that, di erently from the case of a closed session, we don't have access to the whole data base of items that can be recommended. We don't even have access to the items that have already been shown, since in a stream their number is unbound. All we can do, at any given time, is take a decision only considering how the past history of items has modi ed the user context. The system is shown schematically in gure 1. We have a stream of items (news, in our test scenario) that arrive continuously to the user. The user is described by the context model C (the details of this representation will be given in the next section) and each news is compared with the context and assigned a score. Whenever the score is above a certain threshold (or a prede ned criterion is met) the item is presented to the user. At the same time, the context undergoes a rst kind of change, which we call a short term change. This change (used to improve the novelty of the recommended items) is characterized by a time constant . After a time, depending on , the change provoked by any individual item disappears. This is one important di erence between our model and the session based ones. Let us assume that a person is interested in politics. News about the election of the new French president will undoubtedly be of interest to her. However, she will probably not be interested in receiving many similar news about the election one after the other. The e ect of the short term change will be do \deactivate", for a time, the part of the context that deals with this kind of news, so that further news about the French elections will not, c teris paribus, be considered as interesting. However, this situation should not be permanent: after a while (a few hours, a day,...), further news about the French President will again be considered interesting, and should be recommended.
In addition to this short term change, the context evolves in a permanent and irreversible way, again under the in uence of the documents read (as well as, possibly, based on other elements such as the documents that the user creates on her computer, or the emails that she writes). A number of strategies can be used for this evolution: the user can be asked to mark certain documents of special interest, the system can present only a summary, and all the documents whose complete text is accessed are permanently entered into the context, etc. We have considered the evolution of the context based on documents of interest elsewhere [7], and we shall not consider it here. From the point of view of this paper, therefore, the context, de ned as in the following section, is xed, and only the short term changes, needed to increase novelty, are considered.
There is convincing evidence that a user model can help attain a higher precision in information retrieval and recommendation systems [1, 6]. In this paper, we are interested in using such a model to achieve novelty, that is, to obtain recommendations that span the whole gamut of the user's interests. The context model that we use was presented (without the extension to enforce novelty that we present here0 in [7], to which the reader is referred for details; here we shall only give a brief description. The basis of the model is a set of documents, which can be composed of the documents on which the user is working at the time or, in our case, by news items marked in the past. The model doesn't change depending on the source of the documents. In the following, in order to make the tests self-contained, we shall always assume that the context is based on a set of news items that supposedly the user has seen in the past and that he has found relevant.
All the documents in the contexts are considered as a single \macro-document" and processed consequently. On this macro-document we perform stop-word removal and stemming. Each term t is assigned a weight wt using tf-idf weighting [1]. We use the standard vector model representation of information retrieval in which each di erent term corresponds to an axis in the word space. We consider n-grams, constituted of n consecutive terms that appear in the document. If the n-gram pk is composed of the terms tu1 ; : : : ; tun , with weights wu1 ; : : : ; wun , then its representation in the word space is given by the point
(: : : ; wu1 ; : : : ; ww2 ; : : : ; wun ; : : :) pk =
1 pPn
i=1 wu2i in the T -dimensional term space. Note that all points are normalized, so they are in reality points in the manifold ST 1 (the unit sphere in RT ). A context is represented by a set of these n-gram representations, what we call a point cloud representation. That is, a context is a nite set of points C ST 1.
In the word space, we lay a self-organizing map, using a
modi cation of WEBSOM [3]. The map is a grid of elements
called neurons, each one of which is a point in the word space
and is identi ed by two integer indices, that is, a neuron is
given as:
[ ] = ([ ]1; : : : ; [ ]T )0 1
(
[ ]
the neuron [ ] and all its neighbors are shifted towards p.
The amount of this shift depends on the learning parameter
and on the distance from [ ] on the map:
8[ ] [ ]
[ ] + (t)h(t; ([ ]; [ ])) (p
[ ]) (
[ ] pPi[ ]i2
If we don't consider novelty, we can lter the news items as they arrive simply by representing them as a point u 2 ST 1 (considering it as a document and using the same information retrieval techniques that we have used to represent the 1The map can be k dimensional; however, maps with k > 4 are rarely used because of the combinatorial explosion in the number of neuron which would lead to over- tting most training sets. We have used mostly maps with k = 2, and we shall consider only this case here, mainly because it avoid notational complexities.
In this schema, we only reduce the interest factor of the neuron [ ]. In our tests, we also tried another schema, in which we reduce (by a progressively smaller amount) the interest factor of neurons in the neighborhood of the winner using the same function h that we have used in the training algorithm. In this case, the update of the interest factor is context), and determining the maximal similarity between u and the neurons of the map r = max s([ ]; u)
[ ]
the items that yield a value of r below a certain threshold are
considered interesting and presented to the user. As we have
mentioned in the introduction, the problem with this simple
solution is that very similar news items can have high score
because they are similar to the same neuron (that is: to the
same part of the user context), although the presentation
of more than one adds little to the information content of
the rst one. To increase the diversity of the results, we
rewrite (
if [ ] = [ ]
g otherwise
with 0 < < 1 and > 0. According to this equation, the
interest of the neuron closest to a recommended news item
is reduced by a factor , reducing its contribution to (
log log(1 + ) If we want to achieve e ective diversity, this time should be of the order of magnitude of the number of neurons in the network, but not greater, as if neurons win too often their interest factor will decrease, on average, as a function of time. A reasonable choice is to set tr 1K0 , where K is the number of neurons. Expressing, say as a function of and tr, we obtain so, for the desired recovery span, we have = =
1 1 tr 1
We consider two measures. The rst one is the standard
precision (the fraction of recommended documents that are
relevant). Given a context and a set of recommendations,
we expect that the use of novelty will somewhat decrease
precision (if there are two very relevant documents that are
almost identical, a system that considers novelty will
recommend only one of them). So, this measure is a sort of
quality control: we do accept a certain reduction of
precision, but we want to keep it under control, to avoid losing
too much result quality. The second measure is a
determination of novelty. We measure, for a given number of
recommended items, the number of neurons that win. If D
is the number of documents recommended and, during the
recommendation of these documents, nw di erent neurons
are winners (i.e. they are the neurons that achieve the
maximum in eq. (
No IDF, (M11,M13,MCAT)
To validate the proposed approach, we conducted some experiments using 2.5 gigabytes of uncompressed news stories from Reuters Corpus Volume 1 (RCV1-v1) [4]. The Reuters's is a collection of 806,791 news stories, each one associated with some metadata. In our experiments, we used the text and the topics categories each news document belongs to. The RCV1-v1 test collection contains 117 topics in a three-level hierarchy with, at the top, four categories: CCAT (Corporate/Industrial), ECAT (Economics), GCAT (Government/Social), MCAT (Market). Fourteen of these categories contain no document, and in our experiments we used only the 103 that do.
No IDF, (M11,M13,MCAT) 1000 100 10 1 0 100 200 300 400
500
We began by creating a context. To this end, we used
5% of the news items contained in the sub-categories (of
MCAT) M11 (EQUITY MARKETS) and M13 (MONEY
MARKETS), for a total of about 5000 documents. Once
the context is in place, we create a stream of news with all
the elements in the Reuters data base and use our method
for recommending items that are close to the context. As a
ground truth, we consider as relevant all the items that are
in the context categories (M11 and M13) and in their parent
category (MCAT), but not those that are in the sibling
categories of M11 and M13. We stop the stream when 500 items
have ben recommended (this is necessary in order to get
signi cant coverage values, as we mentioned before). Each item
is analyzed and represented as a point u 2 ST 1 (see
section 4). The weights of the terms that compose each item
are determined according to two di erent schemas:
Simple weighting (without an inverse document frequency (idf)
term; the weight of a word is calculated using the normalized
term frequency (tf ), and tf-idf (the normalized frequency of
a word is divided by the logarithm of its frequency in the
British National Corpus (BNC) word frequency list2).
Figures 2{5 show the results of our tests. Each gure contains
three curves: the rst is obtained by ltering the items
without taking into account novelty (having the interest factor of
each neuron always equal to 1). For the second, we used the
adaptation of (
1 0.8 0.6 We must also remark that the MCAT category is quite difcult to lter, as many of the signi cant terms that appear in it are part of the economics jargon, and appear in other categories as well, such as ECAT. This explains the relatively low values of precision that we obtain, independently IDF, (M11,M13,MCAT)
novelty: no update winner only neighborhood of the use of the method for increasing novelty. This might also explain why in some cases the novelty system attains a higher precision than the one based only on relevance: there are probably parts of the context more ambiguous than others sine they are sensitive to words that appear in categories other than MCAT. With the novelty system, once an item has activated these part, they become \desensitized," and cease to produce irrelevant results.
In this paper, we have presented a method for increasing the novelty of a recommendation system that receives a stream, as opposed to the session-based recommender systems common in the literature. We have shown that a model of the user context can be useful to increase the novelty of the recommended results without having to receive results irrelevant for the user. The fact that we receive a potentially in nite stream of items poses new challenges for novelty increasing systems, as redundancy, which is taken to be a constant in session based system, \fades away" in the case of stream: a result very similar to one already received will be considered redundant in the short term, but may become interesting again in the long term. To deal with this problem, we have introduced an interest factor in our model that is reduced when a certain area of the context is activated but that, if the area is no longer activated, recovers in a time that can be controlled by design.