A Learning System for Selective Dissemination of Information

1 Introduction

Information overload is an increasing problem in many domains . New information services (e.g. news services, electronic mail , libraries and databanks) deliver to the user an increasing volume of digital information. Often the information delivered to the user does not match the user interest and it ends up overloading the user, who will have to manually select the interesting information from the "noise" . It is true that the user could switch off such automatic delivery of information, but in that case she will have to go after the information herself. In such a dynamic environment it is also difficult for the user , equipped with only conventional search capabilities, to keep up with the fast pace of information generation. Instead of making the user go after the information or having to go through the large amount of incoming in­ formation, information should more selectively flow to the interested user . Traditionally, libraries and data­ banks, provide such kind of service to user. A user is asked to provide a description of the classes of docu­ ment in which she is interested. Such descriptions are then used as static queries that are submitted to a sys­ tem that send to a passive user the documents matching Flavio Ubaldini Fondazione U go Bordoni B. Castiglione, 59 I-00142 Rome, Italy the queries. Such systems are becoming increasingly im­ portant and will form an indispensable tool for global information systems.

·Previously at Dipartimento di Elettronica e Informatica, Universita di Padova, Padova, Italy.

In this paper we present an system called ProFile that learns by interacting with the user what is the user inter­ est . ProFile constructs and adaptively tunes a represen­ tation of the classes of user's interests using a learning algorithm that is derived from the generalised probabilis­ tic model of IR presented in [Amati and van Rijsbergen, 1995]. ProFile selectively distributes documents from a continuous stream to multiple users with several classes of interests. The fast learning and adapting capabilities of ProFile enables it to effectively perform information filtering and dissemination .

2 Selective Dissemination of Information

Document filtering, also known as selective dissemina­ tion of information, has a long history, most of it based on the unranked Boolean retrieval model of information retrieval (IR) [van Rijsbergen, 1979] . Most of the recent research on document filtering is based on the assump­ tion that effective IR techniques are also effective doc­ ument filtering techniques. The TREC conference (see [Harman, 1996] for the last TREC conference) is a good example of this practice.

Recently, the term information filt ering (IF) has started being used in place of the old style document filtering , to emphasise the possibility of selectively dis­ tributing multimedia information. In the context of this paper we will use this term too, since the technique here presented can also be used to perform multimedia doc­ ument filtering and dissemination.

In IF there is the twofold problem of determining what information is relevant to any user and how this decision can be automatically taken by the information system. Parametric and qualitative descriptions of what informa­ tion is of her interest must be generated. These factors constitute on the whole what is generally referred to as the user profile, but what is needed for expressing them may be difficult to circumscribe. The user profile may consist of a set of keywords, that represent the topics of user's interest , similar to the one generated by the indexing process in IR. However this representation may result insufficient because the user could also need to know some additional modalities to which information is related, such as its novelty, urgency or purpose. There­ fore it is not clear what factors are important for pre­ dicting the relevance of information to user's interests. However some limiting hypotheses on the type of user and/or data sources should be done to present a work­ able model of information filtering. Users may range from casual to specific ones and data types may vary from unstructured (images or "textual" data) to struc­ tured ones (such as relational tables). In the following we assume that the system is able to process the data and to provide them with precise (quantitative) descrip­ tors of their contents, that is with a derivative structured information. Such data are called of semi-structured type [Belkin and Croft, 1992]. This is what typically happens with the indexing of textual data in IR: by using differ­ ent techniques it is possible to assign sets of keywords to the data items. These sets are then organised into a ma­ trix made out of vectors of weighted descriptors: weights are computed on the basis of a statistical analysis of the occurrences of words.

A second assumption upon which our work is based is that the user is casual, that is her profile is not pre­ defined by some specific keywords chosen by the user in a controlled language , that is among a set of possible terms. On the contrary, we assume that the system does not necessarily know any initial definition of the user's profile. Rather, this is long-term defined. The underly­ ing idea is that the system is trained by the user herself and that her profile "converges" to a stable description as soon as the number of the interactions with the informa­ tion sources has become "large enough". This require­ ment for the user model makes a non-trivial difference with IR where the system is concerned with a single ses­ sion at a time. Differently from IF, IR does not depend on time , though user's relevance feedback introduces an implicit temporal factor. Indeed, by adapting a variant of van Rijsbergen's model of IR to IF, as described in [Amati and van Rijsbergen, 1995], we are able to define a new model of information filtering. In particular we will show that the profile of a casual user consists of a vector whose descriptors are in the set of uncontrolled terms of the sources data.

3 Some Considerations about Related Work

Before considering the crux of the IF , we would like to make some remarks on how statistics may influence an IF model. Useful theoretical tools, that range from ele­ mentary probability theory to decision theory and statis­ tical methods, are generally used to draw inferences for processing language and analysing linguistic structures. An example of stochastic model for indexing in IR is that based on the expected mutual information measure (EMIM) of van Rijsbergen's [van Rijsbergen, 1979], de­ rived from Shannon's theory of information . This model was used to find out the word associations in the En­ glish language for the last edition of the Collins' dictio­ nary [Church and Hanks, 1989]. Here a word is inter­ preted as a "message" which carries a measure of un­ certainty (entropy) defined in accord to the probability laws. This entropy is maximum when the message is unclear while is null when the message is "free" from any noise. An alternative approach is vector space model (VSM) by Salton [Salton and McGill, 1983] based on the Zipf's rank-frequencies law. In [Amati and van Rijsber­ gen, 1995] we have explored the connection of our model with both the EMIM and the VSM. In this paper we will outline the connections of our IF model with IR models rather than arguing how statistics can be better applied to IF. For the purpose of this paper, which is merely concerned with the modelling user's behaviour in IF, we will not focus on whether information theory or rank-frequencies is the best representation of the docu­ ment content. Indeed, we assume the system to have the "best" statistical method for drawing linguistic knowl­ edge from a sample of data. Our model is predictive of the behaviour of the user rather than explicative of the content of documents in the sample.

A large number of systems have been currently devel­ oped to filter information, and special efforts are devoted to filter the Internet messages. Despite of this explotion, results concerning the evaluation of these systems are rarely available. The evaluation is generally left to the end users. As an example the NewsWeeder [Lang, 1995] has been evaluated by monitoring for a year two users which used a very large amounts of training data. Only two precision values w.r .t. the set of selected documents are given ( 44% and 59%) and the relative recall values are not available. Hence, very little knowledge is avail­ able on whether and how fast the end users experience the filter.

4 The ProFile System

The ProFile (PRObabilistic FILtEring) system has been developed at Fondazione U go Bordoni in Rome (Italy) in 1996 and has been in used since then by many researchers of that institution for filtering the Usenet News [Amati et al., 1995]. Despite being born with the purpose of filtering news, ProFile can be adapted to filter any in­ coming stream of information, like email, newswires, or newspaper articles.

4.1 The ProFile Architecture

In ProFile each user may define a number of concep­ tual classes to classify the filtered documents: each class has its own profile. IF systems have two ways for as­ signing a document to a conceptual class. The first one consists in ranking documents according to a similarity values between the profiles of conceptual classes. A doc­ ument is then assigned to the conceptual class with the highest level of similarity. This technique is appropri­ ate when conceptual classes cover the set of all possible documents. Differently, another technique consists in defining a relation to be satisfied by each couple class­ document. If the document satisfy the relation, then it is classified into that class, otherwise it is discarded. If a document satisfy relations with more than one class, then it is either classify into all classes or one is chosed (an arbitrary one or the one with the strongest rela­ tion, if that can be quantified). The model used by ProFile follows this second approach by exploiting se­ mantic information theory [Bar-Hillel and Carnap, 1953; Hintikka, 1970] and decision theory [Jeffrey, 1965] . Pro­ File operates according to the following procedure:

Definition of the conceptual classes. The user defines a set of conceptual classes in which he wants to filter and classify the incoming stream of documents. ProFile requires from the user a set of keywords for an approxi­ mate description of each conceptual class.

Training phase. The initial description of the user in­ terests is utilised as a query by the FIFT service (Fub Information Filtering Tool) [Amati et al., 1995], a cus­ tomised version of SIFT, a filtering system developed at Stanford (see Section 3). FIFT filters out of the docu­ ment collection a set of documents that will be used as the "training set". The user go through the documents of the training set and assigns them relevance values with respect to each conceptual class. The relevance values are chosen from a scale of eleven values of interests (from 0 to 10) . The user does not need to go through all the documents retrieved. The number of documents used in the training phase constitutes the training data. Pro­ File's relevance feedback process uses the probabilistic learning model that will be describe in detail in Section 4.2. The pre-filtering phase can go on as long as the user requires, with as many retrieval runs (performed by FIFT) and user relevance feedback as the user chooses.

Filtering phase. The user decides to activate the fil­ tering phase when he believes that the definition of the conceptual classes built by FIFT using relevance feed­ back are accurate enough. The filtering phase is made up of two sub-phases:

1. Filtering. ProFile filters the documents and deliv­ ers to the appropriate user's conceptual class. The user can see the filtered documents classified into his personal conceptual classes.
2. Tuning. The user can either accept the result of the filtering and let ProFile keep working with the current profiles or otherwise he can modify the pro­ files providing additional information. This can be achieved by giving relevance values to the filtered documents in the same way it is done in the train­ ing phase. The additional information enables Pro­ File to tune to the user perception of relevance and adapt the profiles of the conceptual classes. This phase can be repeated as many times as the user wants.

It should be noticed that the initial training phase is very important for the effectiveness of the filter . Indeed, in the limit case of no relevant document in the training set (i.e. no document has been marked as relevant by the user before starting the filtering phase) the system will not retrieve any document and the user will not have any chance for correcting his profile with the tuning phase. We observed that the best training set is obtained by balancing the number of relevant and non-relevant doc­ uments present in the training set (see Section 5). Our way of training the system can be assimilated to the un­ certainty sampling. In [Lewis and Gale , 1994], Lewis and Gale observed a better performance in using uncertainty sampling instead of relevance sampling [Ghosh, 1991] when the sample size is small in comparison with the number of positive examples in the set of non-evaluated data. This is an important feature of ProFile, because the first set of evaluated document in the training set is very small. Typically, a user wants to activate the filtering phase after only 20 or 30 documents have been examined.

4.2 The Information Filtering Model

In this section we describe in detail our probabilistic learning model. The model is derived from the gener­ alised probabilistic model of IR presented in [Amati and van Rijsbergen, 1995] .

Learning theory

At the abstract level IF can be seen as a process dealing with a repetitive event: a document is delivered to the user or not according to his current profile. A profile is a description of what the user is interested at . We as­ sume that the document is represented by a set of terms (phrases, indexes, words or lexical units). The seman­ tic relations between terms in the set T are implicitly explained by means of the set Sl( T) of documents which have been examined by the filter up to the current in­ stant of time T. In statistics this set can be considered as a sample of the population. Relations between terms are often expressed using frequency values. The user relevance assessments also provide a way of expressing semantic relations between terms.

A learning theory for IF is a triple < n, A, P >. n depends on a temporal parameter T , 0( T) being the set of all documents processed before the time T. Here we assume that n is the set of documents which have con­ stituted the data stream up to the current moment , so that T can be omitted. A is the power set of n, namely the set of all subsets of n. Pis defined by the user start­ ing from the mutually exclusive elementary events, that is the elements d of n. This function is lifted from the elementary events to all the events e; of the space A by using the additivity axiom.

In a. finite space, a probability can be then obtained by conditioning. The conditioning of P is defined, provided P(e2) > 0 as:

Functions defined from n to the set of real numbers are called random variables. In our model a random variable is associated to each term t E T. With a lit­ tle abuse of language we denote this random variable with t itself. Given a document d E D, the value t(d) of the random variable t is the statistics on the term t in the document d, for example the tf weighting (the relative frequency of t in d), or the idf weighting (de­ fined as idf(t) = -log(n/N), where n is the number of documents in which t occurs and N is the number of documents in the collection) [Salton and McGill, 1983]. In ProFile we use tf since idf needs a complete informa­ tion on the set of incoming data which is unrealistic in filtering or require a high expensive processing.

In other words if we denote by (af)dEO,tET the matrix (t(d))dEO,tET, then a row associated to dis the vector (t)t(d)ET made out of the statistics of the set of terms in the document d, while the random variables t E T are obtained by the columns of the matrix. In IR the matrix (t( d) )dEfl,tET is called the inverted file oft he collection fl . We can define the conditioning expectation of a discrete random variable t with respect to the measure P as:

Note that if 0 S: t(d) S: 1 then 0 S: Ep(t) S: 1.

In [Amati and van Rijsbergen, 1995], an IR model is introduced as follows . P corresponds to a subjective measureR of relevance on the event space n, its form is a scale of relevance weights R(d), with 0 S: R(d) S: 1, arbi­ trarily generated by the user. In ProFile, for example, we used a scale of 11 degree of relevance that are naturally mapped to the real numbers in the interval [0, 1], but the whole continuous interval could be used. {R( d))dEO may be defined as a subjectively held vector and can be seen as a person's belief at the current instant of time. The dual measure of non-relevance, -.R( d) = 1 - R( d), can be also defined. (-.R(d))dEO can be seen as a person's disbelief on n.

As already pointed out, a random variable t takes the values t( d) by means of statistics. Since t( d) is related to frequencies we may suppose that 0 S: t S: 1. ER(t) can be considered as a relevance\frequency weight of the term t , while E..,R(t) as a non-relevance\frequency weight of the term t.

When the system must decide whether a term is rel­ evant or not on the basis of the expected measures of relevance and non-relevance of documents, an error can occur and then a loss is produced. To make this deci­ sion the system computes the expected monetary value of decision theory [Amati and van Rijsbergen, 1995], that tS:

where At is the "gain" when t is relevant to the user, while A2 is the "loss" when t is not relevant to the user. The event "t is relevant" produces a benefit whenever EMV(t) > 0.

EMV can be equivalently given by the formula:

Decision theory and semantic information

Let us assume that the user has to decide whether to use the term t or not. t has the "a priori" relevance value ER(t) . Suppose also that t is relevant to the informa­ tion need of the user. At would be then the "award" if he takes t while A2 would be the "cost" if he discards t (with a priori probability E..,R(t)). If "t is relevan­ t" , then the user will gain the amount of information of non-relevance oft: let us denote it by Inf..,R(t). On the other hand, the loss A2 can be quantified by the amount of information of relevance oft, that is InfR(t). In both information theories (semantic and frequency- based) the amount of information is taken to be inversely propor­ tional to probability, that is I nfp (e) = -log P( e) or by the similar entropy expression. They share the principle that a sentence is more informative if it excludes more alternatives, that is, if it has a low probability (in par­ ticular tautologies are not informative at all because no alternatives can be excluded) . Hintikka [Hintikka, 1970] suggests to use as a measure of information of a sen­ tence the relative number of alternatives that the sen­ tence excluded, more generally this can be formalised as inf(e) = 1- P(e). In our case we have to assign the amount of information to random variables instead to sentences , that is, we may define the amount of in­ formation as Infp(t) =de f 1 - Ep(t). Let us define -.t = 1-t, then: lnf..,R(t) = 1- E..,R(t) = E..,R(-.t) and InfR(t) = 1- ER(t) = ER(-.t) Substituting the values of the A 's into (3) , we have the absolute relevance of the term, which must satisfy the constraint:

The above model derives the probabilistic model of IR [Robertson and Sparck Jones, 1976; van Rijsbergen, 1979]

under the hypothesis that: (a) R is the counting mea­ sure for the relevance of documents i.e. R takes a value R( d) = 0 or R( d) = 1 for every document according to the user relevance feedback; (b) a~ is the counting document-term matrix, that is: af = 1, if the i-th term occurs in d, and af = 0 otherwise.

In the formula nR denotes the cardinality of the rel­ evant set of documents, N the cardinality of n, ri the cardinality of the set of relevant documents in which the term t; occurs, n .,iR the cardinality of the set of non rel­ evant documents in which the term t; occurs, and finally ni the cardinality of the set of documents in which the term t; occurs.

More generally, w(t) can be used as a weight of rel­ evance of the term t for the user: greater is the value of Wt, higher is the degree of relevance oft. The vector (wt)tfiT in ProFile can be thus considered as a weighted description of the user's profile.

Let us now define ProFile's learning model.

The expected probability of relevance for IR can be easily adapted to define a filtering function. Let us as­ sume that n conceptual classes C1 , C2, ... Cn are asso­ ciated to a single user. These conceptual classes can possibly be reduced to two: the user's class of relevant documents and the set of uncertain documents. Let us examine one document x = (xt)t y, on the set T of terms, at a time from a stream of documents. Then the probabilistic model < n, A, Re >, as described above, can be applied to each class by using the weights:

To summarise, ProFile works in the following way:

1. For each incoming document and for each concep­ tual class C the user provides a relevance measure Re, 0 ::; Re ::; 1.

2. By applying the decision theory we are able to provide a term t with a weighting formula we(t) (see equation (6)).

3. When a new document y = (Yt)teT is evaluated, the weighting formulas we(t) are easily updated.

4. Finally,the vector space similarity function SIM is applied to the vectors x = (xt)teT and we = (we(t))teT to compute a real number value for the mem­ bership of x to C. The conceptual classes containing the document x are such that: SIM(x, wei)> se where se is a threshold value. From a theoretical point of view se must be equal to 0. However, this threshold is experi­ mentally greater than 0. Note also that if the user always gives the maximum uncertain value ~ to each document in the stream of documents then we is the null vector.

5 Evaluation Framework and Results

In the context of the work reported in this paper we intended to evaluate the performance of our IF learning model, in particular when little training data is provided. The collection we used is the TREC-5 B [Harman, 1996] a subset of the collection used in the experiments done in 1996 in the context of the TREC 5 initiative. The collec­ tion is made of 3 years (1990-92) of selected full text arti­ cles of the Wall Street Journal. The total number of doc­ uments (articles) in the collection is about 75.000. Each document is, on average, about 550 words in length. The size of the collection is about 260M byte. This is quite a large collection for IF and IR standards. We also used a set of 50 already prepared queries (or topics, as they are called in TREC) with the corresponding set of relevant documents that were used for the training and for the evaluation. The topics are complex and long and they can be regarded as almost complete description of the information need of a user. We regarded these topics as examples of relevant documents.

The evaluation was performed in true IR style, since this is the current practice for IF systems (see the eval­ uation methodology used in the ·various TREC confer­ ences). The main retrieval effectiveness measures used in IR are Recall and Precision. Recall (R) is the propor­ tion of all documents in the collections that are relevant to a query and that are actually retrieved. Precision (P) is the proportion of the retrieved set of documents that is also relevant to the query. Experimentally these measures have proved to be related in such a way that high precision brings low recall and viceversa. In or­ der to give a measure of the learning performance of the filtering algorithm, R and P have been evaluated with different dimension of the set of training examples.

At each run we trained the system with only very few documents. The training data of each run was a subset of up to 32 relevant and 32 non relevant documents, ran­ domly chosen. The filtering runs shown in Tables 1, 2, 3 and 4 are thus incremental. We did not exploit the idf weighting function which would have required the pro­ cessing of the whole collection in advance. Moreover, we only used a stop list without the stemming. We therefore used a minimum amount of information about the text collection at each run. This is the normal situation in which many filters work, e.g. filtering systems for the net news. We made the hypothesis that the system cannot process in advance the incoming data.

We divided the possible users into three categories: user A demands a high precision performance from the system and is happy with low recall performance (a recall value 0.3, that is 30% of the total number of relevant documents in the collection), the user B requires average levels of recall and precision (a recall of 0.5), and the user C who wants to retrieve most of the relevant information stored in the collection (a recall value of at least 0.7) .

Table 2 and Table 3 show that the learning must be restricted to only high frequent terms in the training data. They also shows that if the information need of an end user is stable in the long-term, learning is in general no faster using only positive documents compared with a balanced training set; negative examples are neither harmful nor useless when combined with positive infor­ mation (notice the better behavior respectively of the runs 8R-8N and 16R-16N-AT with respect to the runs 8R and 16R, which have the same number of relevant documents) .

Table 4 shows that a training set made up of only negative examples do not contribute significantly in the tuning phase. The initial improvement with respect the base run does not growth by increasing the size of the training data. Notice that the performance of the run which does not add extra term to the base run profile (denoted by 32N-TT), is equal to the performance of the run (32N-AT) in which also the terms occurring in the training are weighted. This result shows that neg­ ative counterexamples contribute to eliminate the noise brought about by non-discriminant terms of the topic, but new negative terms do not help to discriminate the relevant documents.

Even though the topics were long and complex, the results show that few training documents improve sub­ stantially the performance of.the system, hence a short tuning phase is indeed necessary especially when the doc­ ument sources are different and not known in advance. Nevertheless, results shown that a relatively small subset of the relevance judgments works quite well with respect to the full set.

6 Conclusions and Future Work

We presented a learning algorithm to perform effective information dissemination and filtering. Our future work will be devoted to further experimentation in order to determine the best possible learning strategy among the many that can be performed using the proposed model.