Combining Learning and Word Sense Disambiguation for Intelligent User Profiling

1 Introduction

Personalized systems adapt their behavior to individual users by learning their preferences during the interaction in order to construct a user profile, that can be later exploited in the search process. Traditional keyword-based approaches are primarily driven by a string-matching operation: If a string, or some morphological variant, is found in both the profile and the document, a match occurs and the document is considered relevant. String matching suffers from problems of polysemy, the presence of multiple meanings for one word, and synonymy, multiple words having the same meaning. The result is that, due to synonymy, relevant information can be missed if the profile does not contain the exact keywords in the documents, while, due to polysemy, wrong documents could be deemed relevant. These problems call for alternative methods to learn more accurate profiles that capture concepts expressing user interests from relevant documents. These semantic profiles should contain references to concepts defined in lexicons or ontologies. This paper describes an approach in which user profiles are obtained by machine learning techniques integrated with a word sense disambiguation (WSD) strategy based on the WordNet lexical database [Miller, 1990; Fellbaum, 1998]. The paper is organized as follows: After a brief discussion about the main works related to our research, in Section 3 the WSD strategy proposed to represent documents by using WordNet is described. Section 4 presents the na¨ıve Bayes text categorization method we adopted to build WordNet-based user profiles. This method is implemented by the content-based profiling system ITem Recommender (ITR). An experimental sessions has been carried out in order to evaluate the proposed approach in a movie recommending scenario. The main results are presented in Section 5. Conclusions and future work are discussed in Section 6.

∗This research was partially funded by the European Commission under the 6th Framework Programme IST Integrated Project VIKEF, Priority 2.3.1.7 Semantic-based Knowledge Systems.

2 RelatedWork

Our research was mainly inspired by the following works. Syskill & Webert [Pazzani and Billsus, 1997] learns user profiles as Bayesian classifiers able to recommend web pages, but it represents documents using keywords. LIBRA [Mooney and Roy, 2000] adopts a Bayesian classifier to produce content-based book recommendations by exploiting product descriptions obtained from the web pages of the Amazon online digital store. Documents are represented by using keywords and are subdivided into slots, each one corresponding to a specific section of the document. Like Syskill & Webert, the main limitation of this work is that keywords are used to represent documents. Conversely, SiteIF [Magnini and Strapparava, 2001] exploits a sense-based document representation to build a user profile as a semantic network whose nodes represent senses of the words in documents requested by the user. The semantic network is built by assigning each node with a score that is inversely proportional to its frequency over all the corpus. Thus, the score is higher for less frequent senses, and this prevents very common meanings from becoming too prevailing in the user model. In our approach, a probability distribution of the senses, found in the corpus of the documents rated by the user, is learned. OntoSeek [Guarino et al., 1999] is a system designed for content-based information retrieval from online yellow pages and product catalogs, which explored the role of linguistic ontologies in knowledge-retrieval systems. That approach has shown that structured content representations, coupled with linguistic ontologies, can increase both recall and precision of content-based retrieval systems. By taking into account the lessons learned by the aforementioned works, ITR has been conceived as a text classifier able: 1) To deal with a sense-based document representation obtained by exploiting a linguistic ontology; 2) To learn a Bayesian profile from documents subdivided into slots. The strategy we devise in order to shift from a keyword-based document representation to a sense-based one, is to integrate lexical knowledge in the indexing step of training documents. Several methods have been proposed to accomplish this task. Scott and Matwin [1998] included WordNet information at the feature level by expanding each word in the training set with all its synonyms in WordNet in order to avoid a WSD process. This approach has shown a decrease of effectiveness in the obtained classifier, mostly due to the word ambiguity problem. Therefore, it suggests that some kind of disambiguation is required. Bloedhorn and Hotho [2004] experiment with various settings for mapping words to senses: No WSD, most frequent sense as provided by WordNet, WSD based on context. They found positive results on the Reuters 25178 1 , the OHSUMED 2 and the FAODOC 3 corpora. None of the previous approaches for embedding WSD in classification has taken into account the fact that WordNet is a hierarchical thesaurus. A distinctive feature of our work is the adoption of a similarity measure that takes into account the hierarchical structure of WordNet.

3 UsingWordNet to Represent Documents

We consider the problem of learning user profiles as a binary text categorization task: Each document has to be classified as interesting or not with respect to the user preferences. The set of categories is C = {c+, c-}, where c+ is the positive class (user-likes) and c- the negative one (user-dislikes). There are several ways in which content can be represented in order to be used as a basis for the learning component and there exists a variety of machine learning methods that could be exploited for inferring user profiles. We propose a strategy to learn sense-based profiles that consists of two steps. This section describes the first one, that is, a WSD technique that exploits the word senses in WordNet to represent documents.

1 http://about.reuters.com/researchandstandards/corpus/

2 http://www.ltg.ed.ac.uk/disp/resources/

3 http://www4.fao.org/faobib/index.html

In the second step, described in Section 4, a na¨ıve Bayes approach learns sense-based user profiles as binary text classifiers (user-likes and user-dislikes) from disambiguated documents. A thorough experimental evaluation of that idea in the context of a hybrid (content-based / collaborative) recommender system has been carried out in [Degemmis et al., 2007].

3.1 The JIGSAWAlgorithm for Word Sense Disambiguation

Textual documents cannot be directly interpreted by learning algorithms. An indexing procedure that maps a document di into a compact representation of its content must be applied. A typical choice for document indexing is the classical bag-of-words (BOW) approach, where each document is represented as a feature vector counting the number of occurrences of different words as features [Sebastiani, 2002]. We extend the BOW model to a model in which each document is represented by the senses corresponding to the words in its content and their respective occurrences. This sense-based document representation is exploited by the learning algorithm to build semantic user profiles. Here, "sense" is used as a synonym of "meaning". Any implementation of sensebased document indexing must solve the problem that, while words occur in a document, meanings do not, since they are often hidden in the context. Therefore, a procedure is needed for assigning senses to words. This task, known as word sense disambiguation, consists in determining which of the senses of an ambiguous word is invoked in a particular use of that word [Manning and Sch¨utze, 1999].

The goal of a WSD algorithm is to associate a word wi occurring in a document d with its appropriate meaning or sense s, by exploiting the context C in which wi is found, commonly defined as a set of words that precede and follow wi. The sense s is selected from a predefined set of possibilities, usually known as sense inventory. In the proposed algorithm, the sense inventory is obtained fromWordNet (version 1.7.1). WordNet was designed to establish connections between four types of Parts of Speech (POS): Noun, verb, adjective, and adverb. The basic building block for WordNet is the SYNSET (SYNonym SET), which represents a specific meaning of a word. The specific meaning of one word under one type of POS is called a sense. Synsets are equivalent to senses, which are structures containing sets of words with synonymous meanings. Each synset has a gloss, a short textual description that defines the concept represented by the synset. For example, the words night, nighttime and dark constitute a single synset that has the following gloss: "the time after sunset and before sunrise while it is dark outside". Synsets are connected through a series of relations: Antonymy (opposites), hyponymy/hypernymy (IS-A), meronymy (PART-OF), etc. JIGSAW is a WSD algorithm based on the idea of combining three different strategies to disambiguate nouns, verbs, adjectives and adverbs. The motivation behind our approach is that the effectiveness of the WSD algorithms is strongly influenced by the POS tag of the target word. An adaptation of Lesk dictionary-based WSD algorithm has been used to disambiguate adjectives and adverbs [Banerjee and Pedersen, 2002], an adaptation of the Resnik algorithm has been used to disambiguate nouns [Resnik, 1995], while the algorithm we developed for disambiguating verbs exploits the nouns in the context of the verb as well as the nouns both in the glosses and in the phrases that WordNet utilizes to describe the usage of the verb. The algorithm disambiguates only words which belong to at least one synset. JIGSAW takes as input a document d = {w1, w2, . . . , wh} and will output a list of WordNet synsets X = {s1, s2, . . . , sk} (k ≤ h) in which each element si is obtained by disambiguating the target word wi based on the information obtained fromWordNet about a few immediately surrounding words. We define the context C of the target word to be a window of n words to the left and another n words to the right, for a total of 2n surrounding words. The algorithm is based on three different procedures for nouns, verbs, adverbs and adjectives, called JIGSAWnouns, JIGSAWverbs, JIGSAWothers, respectively. The POS tag of each word is computed by the HMMbased tagger ACOPOST t3 4 . JIGSAW proceeds in several iterations by using the disambiguation results of the previous iteration to reduce the complexity of the next one. First, JIGSAW performs the JIGSAWnouns procedure. Then, verbs are disambiguated by JIGSAWverbs by exploiting the words already disambiguated by JIGSAWnouns. Finally, the JIGSAWothers procedure is executed. More details for each one of the above mentioned procedures follow.

The algorithm assigns to wi the most appropriate synset sih among the sense inventory Wi for wi. It computes the similarity between each sik in the sense inventory and the context for wi. The method differs from the original algorithm by Resnik [1995] in the use of the similarity measure. We adopted the Leacock-Chodorow measure [1998], which is based on the length of the path between concepts in an ISA hierarchy. The idea behind this measure is that similarity between synsets a and b is inversely proportional to their distance in the WordNet IS-A hierarchy. The distance is computed by counting the number of nodes in the shortest path joining a with b (by passing through their most specific subsumer). The similarity function is: SinSim(a, b) =

- log(Np/2D), where Np is the number of nodes in the shortest path p from a to b, and D is the maximum depth of the taxonomy (D = 16, in WordNet 1.7.1). The procedure starts by defining the context C of wi as the set of words having the same POS tag and found in the same sentence as wi. Next, the algorithm identifies both the sense inventory for wi and the sense inventory Wj, for each word wj in C. The sense inventory T for the whole context C is given by the union of all Wj. JIGSAWnouns measures the similarity between each candidate sense sik ∈ Wi and each sense sh ∈ T . The sense assigned to wi is the one with the highest similarity score.

JIGSAWverbs

Before describing the JIGSAWverbs procedure, the description of a synset must be defined. It is the string obtained by concatenating the gloss and the sentences that WordNet uses to explain the usage of a word. For example, the gloss for the synset corresponding to the sense n.2 of the verb look ({look, appear, seem}) is "give a certain impression or have a certain outward aspect", while some examples of usage of the verb are: "She seems to be sleeping"; "This appears to be a very difficult problem". The description of the synset is "give a certain impression or have a certain outward aspect She seems to be sleeping This appears to be a very difficult problem". First, the JIGSAWverbs includes in the context C for the target verb wi all the nouns in the window of 2n words surrounding wi. For each candidate synset sik of wi, the algorithm computes nouns(i, k), that is the set of nouns in the description for sik. In the above example, nouns(look, 2)={impression, aspect, problem}. Then, for each wj in C and each synset sik, the following value is computed:

4 http://acopost.sourceforge.net/

In other words, maxjk is the highest similarity value for wj, with respect to the nouns related to the k-th sense for wi. Finally, a score for each sik is computed:

where R(k) is the ranking of sik (synsets in WordNet are ranked according to their frequency of usage) and G(posj ) is a gaussian factor related to the position of wj with respect to wi in the original text that gives a higher weight to words near the target word. The synset assigned to wi is the one with the highest ϕ value.

This procedure is based on the WSD algorithm proposed in [Banerjee and Pedersen, 2002]. The idea is to compare the glosses of each candidate sense for the target word to the glosses of all the words in its context. Let Wi be the sense inventory for the target word wi. For each sik ∈ Wi, JIGSAWothers computes the string targetGlossik that contains the words in the gloss of sik. Then, the procedure computes the string contextGlossi, which contains the words in the glosses of all the synsets corresponding to each word in the context for wi. Finally, the procedure computes the overlap between contextGlossi and targetGlossik, and assigns the synset with the highest overlap score to wi. This score is computed by counting the words that occur both in targetGlossik and in contextGlossi. The JIGSAW algorithm was evaluated according to the parameters of the Senseval initiative 5 , that provides a forum where the WSD systems are assessed against disambiguated datasets. In order to measure the capability of disambiguating a complete text, the "All Words Task" for English was chosen. JIGSAW reaches the fourth position in that task, by achieving precision and recall equal to 50%. This result assures that our WSD algorithm can be configured to have high precision, and thus would add very little noise in the training set. Due to space limitations, the details of the experiments are not reported.

5 http://www.senseval.org.

3.2 Keyword-based and Synset-based Document Representation

The WSD procedure described in the previous section is adopted to obtain a synset-based vector space representation that we called bag-of-synsets (BOS). In this model, a synset vector instead of a word vector represents a document. Another key feature of the approach is that each document is represented by a set of M slots, where each slot is a textual field corresponding to a specific feature of the document, in an attempt to take also into account the document structure. According to the BOS model, the text in each slot is represented by counting separately the occurrences of a synset in the slots in which it occurs. More formally, assume that we have a collection of N documents. Let m be the index of the slot, for n = 1, 2, . . . , N, the n-th document dn is reduced to M bags of synsets, one for each slot:

where tmnk is the k-th synset in slot sm of document dn and Dnm is the total number of synsets appearing in the m-th slot of document dn. For all n, k and m, tmnk ∈ Vm, which is the vocabulary for the slot sm (the set of all different synsets found in slot sm). Document dn is finally represented in the vector space by M synset-frequency vectors:

where wm nk is the weight of the synset tk in the slot sm of document dn, and can be computed in different ways: It can be simply the number of times synset tk appears in slot sm, as we used in our experiments, or a more complex TF-IDF score. Our hypothesis is that the proposed document representation helps to obtain profiles able to recommend documents semantically closer to the user interests. The difference with respect to keyword-based profiles is that synset unique identifiers replace words.

4 ANa¨ıve Bayes Method for User Profiling

ITem Recommender (ITR) uses a Na¨ıve Bayes text categorization algorithm to build profiles as binary classifiers (userlikes vs user-dislikes). The induced probabilistic model estimates the a posteriori probability, P(cj|di), of document di belonging to class cj as follows:

where N(di, tk) is the number of times token tk occurs in document di. In ITR, each document is encoded as a vector of BOS in the synset-based representation, or as a vector of BOW in the keyword-based representation, one BOS (or BOW) for each slot. Therefore, equation (3) becomes:

where S= {s1, s2, . . . , s|S|} is the set of slots, bim is the BOS or the BOW in the slot sm of di, nkim is the number of occurrences of token tk in bim. When the system is trained on BOW-represented documents, tokens tk in bim are words, and the induced categorization model relies on word frequencies. Conversely, when training is performed on BOS-represented documents, tokens are synsets, and the induced model relies on synset frequencies. To calculate (4), the system has to estimate P(cj) and P(tk|cj, sm) in the training phase. The documents used to train the system are rated on a discrete scale from 1 to MAX, where MAX is the maximum rating that can be assigned to a document. According to an idea proposed in [Mooney and Roy, 2000], each training document di is labeled with two scores, a "user-likes" score wi+ and a "userdislikes" score wi-, obtained from the original rating r:

The scores in (5) are exploited for weighting the occurrences of tokens in the documents and to estimate their probabilities from the training set TR. The prior probabilities of the classes are computed according to the following equation:

Witten-Bell smoothing [1991] is adopted to compute P(tk|cj, sm), by taking into account that documents are structured into slots and that token occurrences are weighted using scores in equation (5):

where N(tk, cj, sm) is the count of the weighted occurrences of token tk in the slot sm in the training data for class cj, Vcj is the total number of unique tokens in class cj, and V is the total number of unique tokens across all classes. N(tk, cj, sm) is computed as follows:

In (8), nkim is the number of occurrences of token tk in slot sm of document di. The sum of all N(tk, cj, sm) in the denominator of equation (7) denotes the total weighted length of the slot sm in class cj. In other words, ˆ P(tk|cj, sm) is estimated as the ratio between the weighted occurrences of tk in slot sm of class cj and the total weighted length of the slot. The final outcome of the learning process is a probabilistic model used to classify a new document in the class c+ or c-. This model is the user profile, which includes those tokens that turn out to be most indicative of the user preferences, according to the value of the conditional probabilities in (7).

5 Experimental Evaluation

The goal of the experiments was to compare the performance of synset-based user profiles to that of keyword-based profiles. Experiments were carried out on a content-based extension of the EachMovie dataset 6 , a collection of 1, 628 textual descriptions of movies rated by 72, 916 users on a 6-point scale (1-6). The content information for each movie was collected from the Internet Movie Database 7 by using a crawler that gathered the Title, the Director, the Genre, that is the category of the movie, the Keywords, the Summary and the Cast. Movies are subdivided into different genres: Action, Animation, Classic, Art Foreign, Comedy, Drama, Family, Horror, Romance, Thriller. For each genre or category, a set of 100 users was randomly selected among users that rated n items, 30 ≤ n ≤ 100 in that movie category (only for genre 'Animation', the number of users that rated n movies was 33, due to the low number of movies in that genre). In this way, for each category, a dataset of at least 3, 000 triples (user, movie, rating) was obtained (at least 990 for 'Animation'). Table 1 summarizes the data used for the experiments.

Tokenization, stopword elimination and stemming have been applied to index the documents according to the BOW model. The content of slots title, director and cast was only tokenized because the elimination of the stopwords produced some unexpected results. For example, slots containing exclusively stopwords, such as "It" or "E.T.", became empty. Moreover, it does not make sense to apply stemming and stopword elimination on proper names. Documents have been processed by the JIGSAW algorithm and indexed according to the BOS model, obtaining a 38% feature reduction. This is mainly due to the fact that synonymwords are represented by the same synset. Keyword-based profiles were inferred by learning from BOW-represented documents, whilst synset-based profiles were obtained from BOS-represented documents. As ITR is conceived as a text classifier, its effectiveness is evaluated by the well-known classification accuracy measures precision and recall [Sebastiani, 2002]. Also used is F1 measure, a combination of precision and recall. We adopted the Normalized Distance-based Performance Measure (NDPM) [Yao, 1995] to measure the distance between the ranking imposed on documents by the user ratings and the ranking predicted by ITR, that ranks documents accord-

6 EachMovie dataset no longer available for download, see the GroupLens home page for a new version named MovieLens, originally based on this dataset: http://www.cs.umn.edu/Research/GroupLens/

7 IMDb, http://www.imdb.com

ing to the a-posteriori probability of the class likes. Values range from 0 (agreement) to 1 (disagreement). The adoption of both classification accuracy and rank accuracy metrics gives us the possibility of evaluating both whether the system is able to recommend relevant documents and how these documents are ranked. In all the experiments, a movie description di is considered relevant by a user if the rating is greater or equal to 4, while ITR considers a description relevant if P(c+|di) > 0.5, computed as in equation (4). We executed one run of the experiment for each user in the dataset. Each run consisted in: 1) Selecting the documents and the corresponding ratings given by the user; 2) Splitting the selected data into a training set Tr and a test set Ts; 3) Using Tr for learning the corresponding user profile; 4) Evaluating the predictive accuracy of the induced profile on Ts, using the aforementioned measures. The methodology adopted for obtaining Tr and Ts was the 5-fold cross validation. Table 2 shows the results reported over all 10 genres by ITR.

A significant improvement of BOS over BOW both in precision (+8%) and recall (+10%) can be noticed. The BOS model outperforms the BOW model specifically on datasets 5 (+11% of precision, +14% of recall), 7 (+15% of precision, +16% of recall), 8 (+19% of precision, +24% of recall). Only on dataset 4 no improvement can be observed, probably because precision and recall are already very high. It could be noticed from the NDPM values that the relevant / not relevant classification accuracy is increased without improving the ranking. This result can be explained by the example in Table 3, in which each column reports the ratings or scores of the items and the corresponding positions in the ranking.

Let Ru be the ranking imposed by the user u on a set of 10 items, RA the ranking computed by A, and RB the ranking computed by method B (ratings ranging between 1 and 6 - classification scores ranging between 0 and 1). An item is considered relevant if the rating r > 3 (symmetrically, if the ranking score s ≥ 0.5). Method A has a better classification accuracy compared to method B (Recall=4/5, Precision=4/5 vs. Recall=3/5, Precision=3/4). NDPM is almost the same for both methods because the two rankings RA and RB are very similar. The difference is that I4 is ranked above I6 in RA, whilst I6 is ranked above I4 in RB. The general conclusion is that method A (BOS model) has improved the classification of items whose score (and ratings) are close to the relevant / not relevant threshold (items for which the classification is highly uncertain). A Wilcoxon signed ranked test (p < 0.05) has been performed to validate the results. Each genre dataset has been considered as a single trial for the test. Results confirmed that there is a statistically significant difference in favor of the BOS model compared to the BOWmodel as regards precision, recall and F1-measure. Conversely, the two models are equivalent in defining the ranking of the preferred movies according to the score for the class "likes".

6 Conclusions and Future Work

We presented a system that exploits a Bayesian learning method to induce semantic user profiles from documents represented by WordNet synsets suggested by the WSD algorithm JIGSAW. Our hypothesis is that, replacing words with synsets in the indexing phase, produces a more effective document representation, which can help learning algorithms to infer more accurate user profiles. Our approach has been evaluated in a movie recommending scenario. Results showed that the integration of the WordNet linguistic knowledge in the learning process improves the classification of those documents for which the classification is highly uncertain. As a future work, we plan to exploit not only the WordNet hierarchy, but also domain ontologies in order to realize a more powerful document indexing.