Adaptive Personal Information Filtering System that Organizes Personal Profiles Automatically

1 Introduction

Wi t h t he increasing availability of information , it be­ comes more important to provide methods of filtering in­ format ion to reflect the user's needs. There are many dif­ fi culties in determining what information the user wants to see. The difficulties are based on the following facts: the words people use do not always clearly reflect the topi c or content. A single word has more than one mean­ ing in 111a.ny documents[Foltz and Dumais , 1992]. Fur­ thermore, not only the user's interest but also the value of the words used to retrieve items change, i.e. "inter­ net" was a useful key word a few years ago. However , it is no longer useful today.

Many studies have been performed in an attempt to overcome the ambiguity of words. Latent Semantic In­ dexing is a methods that takes account of the ambiguity for document profiles[Foltz, 1990] . Information Tapestry is a method used to overcome it by means of collabora­ tive filtering[Goldberg et a/. , 1992].

Furthermore, adaptive learning is discussed as an approach to overcome changes in the user's interest[Asakura et a/., 1995]. Unfortunately, the dis­ cussed adaptive learning algorithm has many heuristic parameters and its effects are not shown.

In this paper, we present an adaptive personal infor­ mation filtering system with which users do not need to direct ly manipulate their profile. The system gives them items sorted in order of interest (priority). We call the present system "information filtering system sorting items in order of user 's priority" or simply "IN SOP" . INSOP has only 2 parameters: one is a parameter to limit the size of user profile and the other is a. parameter to control the method of manipulation of rare keywords. In Section 2, we derive an adaptive learning algorithm based on the statistical consideration - what key words are useful for retrieving the items in which only one user is interested. In Section 3, we demonstrate the effects of INSOP. We show that INSOP is a good information filtering system. In Section 4, we show the architecture and browser of the current INSOP system used 111 our fi eld test.

2 Adaptive Learning Algorithm

In th is section , we show the adaptive learning algorithm of INSOP. First , we consider which key words are useful for retrieving items in which the user is interested. Next , we give an adaptive learning algorithm for an ideal case and refine the algorithm for application to actual cases.

2.1 Classification of Key Words

If our subj ect is to supply a set of key words which are useful for retrieving items in which only one user is inter­ ested , then the intrinsic value of each key word depends on whether the key word reflects his or her interest or not. The semantics of each key word is not important in t his context. Using this viewpoint , we classify key words (including Boolean combinations of key words) into 3 groups . The first group includes those whereby if one of t hem appears in an item, then the user has an interest in the item. We call such key words "positive key words" . T he second group is that whereby if one of the key words appears in an item, then the user dose not have an in­ terest in the item. We call such key words "negative key words" . The third group includes those which are not useful in determining whether that the user has an in­ terest in t he items with the key word or not. We call such key words "neutral key words" .

2.2 Ideal Case

ln order to explain the principal idea of INSOP clearly, we consider an ideal case in which we can manipulate items , keywords , and user's inputs by statistical meth­ ods.

Here we define notations as follows: Wj is the j-th key word , p* is the true probability that an item is one in which the user has an interest , and q* ( wi ) is the true probability that an item with the j -th key word is one in which the user has an interest.

The positive (negative) key words satisfy q* ( Wj) > p* ( q* ( Wj ) < p*) , and the neutral key words satisfy q* ( Wj) ,...., p* .

In an ideal case , we can define a statistical quantity to classify key words into the 3 groups as :

SI< C(-) is the "Statistical Key word Classifier" . When the Statistical Key word Classifier receives one of pos­ itive, or negative, or neutral key words as an input , it outputs a positive, or negative value, or the value close to 0, respectively. The Statistical Key word Classifier is similar to Kullback-divergence, which is used to measure the "distance" between 2 distributions in statistics ,

but the sign of its second term is different from that of t he Kullback-divergence.

In addition , we define the "Statistical Item Classifier" as

where itema is t he a-th item, na is the number of the key words of the a-th item, and wj is the j-th key word of them. When t he a-th item has many positive (negative) key words , the output of the Statistical Item Classifier is a large positive (negative) value.

The Stat istical Key word Class ifier and the Statist ical Item Classifier work well as tools for classifying items in which a user is interested or not , in the ideal case.

As a result , a system which sorts items in order of the output of the Statist ical Item Class ifier works as an informat ion filtering system. T his is t he principal idea of INSOP.

2.3 Actual Case

If we apply the Stat istical Key word Class ifier and t he Statist ical Item Class ifier to an actual informat ion fil ­ tering system, we must est imate the probabili ty that an item with the j -th key word is of in terest based on sam­ ple items. The estimated probability, q( Wj) , is not equal to the true probability, q* ( Wj) , in actual cases. T he ac­ curacy of the est imated probabili ty depends on the num­ ber of sample data. Accordingly, the following prob lems must be solved: (1) how to t reat key words which are too rare to be manipulated by stat istical met hods, (2) how to initialize the system, (3) how to adapt user's interests and their modifications, ( 4) how to treat items whi ch have both posit ive and negative key words . In this sec­ tion, we provide the solu t ions to these problems by ex­ tending the Statistical Key word Classifier to the "Key word Classifier" for the treatment of both frequent and rare key words and by introducing an adapt ive learning algorithm.

First , we extend the Statistical Key word Classifier in order to solve the first problem. T he rare key word problem is that the probability estimated on the basis of a small mount of sample data is different from the true value. We consider a typical case where the r-th key word , which is a rare key word whose t rue probabili ty, q*(wr) , satisfies 0 « q*(wr) « 1, appears just once wit h an interest item. Note that a case in which a new key word , either is rare or not , appears is equivalent to t his case. In the real world , there are many such cases . Then, the probability q( Wr ) is est imated as

As a result , the Statistical Key word Class ifier input with the rare (new) r·-th key word outputs a large bu t unreli­ able value. Here, we remember that the Statistical Key word Class ifier input wi th one of the neut ral key words, which are useless to estimate user 's interest , outpu ts the value close to 0. Therefore, if we interpret "unreliab le" as "useless" , we are able to int roduce the following "Key word Classifier" to treat frequent and rare key words ,

where p i is the appearance count of interest ing items, p u is the appearance coun t of uninteresting items, Qj is the appearance count of interesting items with the j-th key word, Q'/ is the appearance count of uninteresting items with the j-th key word , and a is the parameter , called the "rarity parameter", which controls the manip­ ulation of rare key words . Accordingly, we define "Item Classifier" as:

The Key word Classifier outputs a value close to 0 when it receives a key word whose appearance count is less than the rarity parameter a. Namely, the Key word Classifier classifies the key word as a useless key word. Consequently, the unfavorable influence of the rare key words to the output of the Item Classifier is small corn­ pared with that to the Statistical Key word Classifier . As a result, the Key word Classifier and the Item Clas­ sifier work well as tools for classifying the interesting, neutral, or uninteresting items in actual cases.

This is one solution to the first problem of rare key words.

The definitions of the Key word Classifier and the Item Classifier require that the personal profile of IN­ SOP must be in the form given in Table 1.

Accordingly, the adaptive learning algorithm of the per­ sonal profile is given as follows.

1. A user reads an item, itema, with key words, wf, ... 'w~a.
2. If the user inputs "interesting" to INSOP, then
3. 2-1) pi .-.pi+ 1 and
4. 2-2) search user 's personal profile for the same key word as wf;, k = 1, · · · , na .
5. 2-3) If there is a key word which satisfies Wj = wf; , then Qj <- Qj + 1.
6. 2-4) Otherwise, add wf; into user's personal profile as the (I(+ 1)-th key word and set Qi""+l = 1, Q'K+l = o.
7. If the user inputs "uninteresting" to INSOP, then
8. 3-1) pu <- P" + 1 and
9. 3-2) search user 's personal profile for the same key word as wf;, k = 1, · · · , na.
10. 3-3) If there is the key word which satisfies Wj = wf;, then Qj .-. Qj + l.
11. 3-4) Otherwise, add wf; into user 's personal profile as the (I<+ 1 )-th key word and set Qk+l = o, Q'K+l = 1.

Note that we do not need to embed the user's interest into the personal profile initially. INSOP can be started an empty profile. This is an advantage of INSOP and is also the solution to the second problem (how to initialize the system). There is , however , a disadvantage of the algorithm as follows: the algorithm contiimally increases the number of key words in the user's personal profile.

We overcome this disadvantage by adding an algo­ rithm which selects the key words which give the "best" finite personal profile of INSOP. In INSOP, positive and negative key words are useful but neutral key words are useless. We introduce a function which outputs a large positive value for positive or negative key words but which outputs a value close to 0 for neutral key words in order to construct INSOP which selects a finite number of useful key words. Such a function is given by

We call KCH(-) the "Key word Checker". When we design the INSOP system, we must give the limit of the number of key words in the personal profile, N. In order to make the "best" personal profile of INSOP under the limit , we select N key words which give large outputs of the Key word Checker compared to other key words.

Next, we show that the rarity parameter a is related to the adaptive speed of INSOP. The properties of the Key word Checker are summarized in Table 2.

The outputs of the Key word Checker following input of rare or new key words depend on the rarity parameter . If we give the rarity parameter a value close to 0, then the outputs become very large and INSOP manipulates rare and/or new key words as useful key words com­ pared to positive and negative key words. As a result , INSOP retains new or rare key words whose appearance counts are small and releases old key words - positive or negative key words - whose appearance counts are large. As the rarity parameter increases , rare and new key words become useless and are easily released but positive and negative key words are held fast in INSOP. This shows that we can control the adaptive speed of INSOP according to our requirements using the rarity parameter. This is the solution to the third problem (how to adapt the user 's interests and their modifica­ tions) and also that of the first problem (how to treat rare key words).

The remaining problem is how to treat items which have both positive and negative key words. We can de­ termine the characteristic of such items but we have no direct solution for this problem yet. The characteristic is that the output of the Item Classifier is close to 0 but the sum of the outputs of the Key word Checker is large when we input such an item. Accordingly, we designed the current INSOP system which displays the output of the Item Classifier as "needs" and the sum of the Key word Checker outputs as "reliance" in order to help users to identify such items .

3 Performance of INSOP

In this section, we demonstrate the performance of IN­ SOP based on experiments conducted in collaboration with several researchers who cooperated as testees . All of them are highly experienced in patent retrieval. We set the limit of the number of key words in the personal profile to N = 750 in this experiment.

We obtained test sequences of items which were head­ lines of Japanese newspapers provided by information providers and the Boolean combination of key words for retrieving to the items in which each testee had interest as follows.

1. The tester requested each testee to mark the items in which they had interests and executed the inter­ face program which displays one item without key words and receives the testee's input - "interesting" or "uninteresting".
2. The testee read 600 items and input his answers.
3. After the testee had input all the answers , the tester stopped the program and requested the testee to produce the Boolean combination of key words to ret rieve the items which he marked "interesting" .

In order to simulate a case where each user received three sets of items, we divided each test sequence into 3 short test sequences including 200 items.

In Figure 1, we show typical results of the experiments to evaluate the performance of INSOP. The horizontal axis indicates the number of items which the testees read. We refer to the number as m. The vertical axis indicates the number of interesting items including the read items . Three sequences of items are shown in Figure 1. The first sequence corresponding to a solid line is the test se­ quence. The second sequence corresponding to a dashed line is that of items ret rieved by the key word matching method using the Boolean combination of key words set by the testee. The third sequence corresponding to a dotted line is that of items sorted by INSOP.

The solid line shows that the dist ribution of the marked items in the short test sequence is approximately uniform.

The dashed line stops to increase at m = 36, 238 and 421. This shows that the key word matching method retrieves 10%,.._, 20% items. About 60% marked items are included in the retrieved items. Consequently, t he density of the marked items in the items retrieved using the key word matching method is about 3 times as high as that in the short test sequences. T his rate is consis­ tent with the value of 1.5 ""' 2.5 reported by ref.[Foltz and Dumais, 1992]. Note that the key word matching method misses several of the marked items (about 40%). Namely, it is difficult to create a Boolean combination of key words that includes all our personal interests , whi ch are indefinite, even if we have much experience in infor­ mation retrieval. This result suggests that the key word matching method is not useful for retrieving the marked items in this test task.

However, based on this result , we are not suggest­ ing that the key word matching method is useless for all types of information retrieval or filtering. In gen­ eral, retrieval methods , into whi ch the key word match­ ing method is classified, in which personal profiles are directly manipulated by users , are still useful in cases where users understand the exact subjects to retrieve, i.e. patent retrieval.

The dotted line shows the performance of INSOP. In the experiment, adaptive learning of the personal profile is executed at m = 50, 100, 250, 300 , 450 and 500. The order of the first 50 items presented by an IN SOP system whose personal profile is empty is the same as the order of the test sequence. At m = 50, INSOP executes the first adaptive learning of the personal profile and sorts the remaining 150 items into the first short sequence in the order of the testee's degree of interest est imated us­ ing the learned personal profile. As a result, the dotted line begins to go upward and deviates from the solid line at m = 50. This indicates that INSOP moves inter­ est ing items forward and uninteresting items backward. INSOP executes the second learning and sorting of the remaining items in the first short sequence at m = 100. At m = 200, INSOP sorts all the items in the second short sequence and executes the adapt ive learning and sorting of the remaining items in the short sequence at m = 250.

The density of interesting items at the head of the sorted sequence is as high as that in the retrieved items using the key word matching method. The number of interesting items including in the head is large r than the number including in the retrieved items.

These graphs show that INSOP is a. good informat ion filtering system which sorts items in order of interesting, neutral and uninterest ing items compared to the key word matching method.

4 INSOP in Field Test

In this sect ion , we demonstrate the current INSOP sys­ tem in our field test. First , we explain the architecture of the current INSOP system. Next , we show how to use the INSOP browser to receive the INSOP service, and we present the results of the field test .

4.1 Architecture

Figure 2 shows the flow of items through the following major architectural components of the current INSOP system.

• It em store. Provides storage for items sent by infor­ mation providers.
• Personal profile store. Provides storage of a per­ sonal profile.
• INSOP filt erer. Sorts items in order of user 's inter­ est.
• INSOP browser. Provides the user with an interface for accessing INSOP services. This includes facili­ t ies for displaying items and receiving user inputs.
• INSOP adapter. Organizes user's personal profile according to the adaptive learning algorithm de­ scribed in the previous section.

The current INSOP system uses a client /server model. The client(INSOP browser) is installed into over 50 per­ sonal computers (PCs) and operates as an application software on each PC whose OS is Windows95. The server

(INSOP filterer/adapter) operates as a daemon process on several UNIX machines . The clients and the servers send data (sorted items, user 's input etc.) to each other according to our original protocol based on the TCP / IP.

4.2 Browser

If we execute the INSOP browser , the browser requests for us to input a server name , our user IDs , and our passwords . After receiving them, the browser opens the window in which there are 4 areas as shown in Figure 3. In area ( 1) , the name of the opened file or the folder is shown. In area (2), the trees of the files and folders are shown according to the same format as Microsoft Explore. In area (3), accessible files or folders are shown. Area ( 4) displays items with the two values, "needs" and "reliance", defined at the end of Section 2.

We open an item folder and select a file using a PC mouse in the same manner as with Explore. The items included in the file are displayed in area (4) (we show a copy of the browser at Figure 4 where Japanese items are displayed) . The bold frame indicates the item to which we should respond using the mouse buttons - its left button for "interesting" and its right button for "un­ interesting" and is moved using the mouse. If we mark an item with "interesting" or "uninteresting", then the color of the left block in area ( 4) where "needs" and "re­ liance" are displayed changes from white to dark or light gray, respectively. If we attempt to open a new file after marking items using the buttons, the INSOP browser sends the set of our inputs and the key words wit h the items to the INSOP adapter. The INSOP adapter or­ ganizes our personal profiles according to the adaptive learning algorithm. Then, the INSOP filterer, based on our personal profiles , sorts the items of the new file and sends the sorted items to the INSOP browser. The INSOP browser displays them in area (4).

The calculation time from the start of the adaptive learning to the sorting items is less than ls in the cases where the number of items is 100. The actual waiting time , depending on the load levels of the network and the server, is 1"'5s on the local area network (LAN) of Matsushita Research Institute, Tokyo Inc. (MRIT) .

4.3 Field Test

We executed the field test of the current INSOP sys­ tem on the LAN. The purpose of the test was to en­ sure that INSOP responds to the various interests of many users. The items used in the test were headlines of Japanese newspapers which were supplied by infor­ mation providers at a rate of about 600 per day. Over 50 users participated in the test including not only re­ searchers and engineers in material, mechatronics, image processing, speech technology and mobile communica­ tion but also staff members.

We asked a set of questions to the users regarding their impression of INSOP and the sorting ability 3 times : when the INSOP filterer was operating (case 1), when the we stopped the INSOP filterer (case 2), and when the INSOP filterer was operating again (case 3).

Table 3 shows the result of a questionnaire on the cur­ rent INSOP system.

Furthermore, over 90% of users answered, "INSOP is useful reading the headlines of Japanese newspapers.".

5 Conclusion

In this paper, we presented an adaptive personal infor­ mation filtering system, IN SOP, whose personal profile is automatically organized from an empty profile by means of user-system interaction. The IN SOP system is a good information filtering system which sorts items in order of interesting, neutral, and uninteresting items. The resul ts of the experiment and field test suggest that INSOP can be put to practical use.

Acknowledgments

We thank Electric Library Co. which allows us to demonstrate the INSOP system using the head lines of Japanese newspapers , Mr. N atsuki Oka, Mr. Seiji Kishi­ moto and Mr. Tatsuro Itoh for their useful comments, and the members of MRIT who cooperated with us as testees .