A taxonomy of Recommender Agents on the Internet


Download 490.08 Kb.

bet1/4
Sana30.03.2018
Hajmi490.08 Kb.
  1   2   3   4

Artificial Intelligence Review 19: 285–330, 2003.

© 2003 Kluwer Academic Publishers. Printed in the Netherlands.

285

A Taxonomy of Recommender Agents on the Internet

MIQUEL MONTANER, BEATRIZ LÓPEZ and JOSEP LLUÍS DE LA

ROSA

Agents Research Laboratory, Institut d’Informàtica i Aplicacions, Universitat de Girona,

Campus Montilivi, 17071 Girona, Spain. E-mails: mmontane@eia.udg.es;

blopez@eia.udg.es; peplluis@eia.udg.es

Abstract. Recently, Artificial Intelligence techniques have proved useful in helping users

to handle the large amount of information on the Internet. The idea of personalized search

engines, intelligent software agents, and recommender systems has been widely accepted

among users who require assistance in searching, sorting, classifying, filtering and sharing

this vast quantity of information. In this paper, we present a state-of-the-art taxonomy of

intelligent recommender agents on the Internet. We have analyzed 37 different systems and

their references and have sorted them into a list of 8 basic dimensions. These dimensions are

then used to establish a taxonomy under which the systems analyzed are classified. Finally,

we conclude this paper with a cross-dimensional analysis with the aim of providing a starting

point for researchers to construct their own recommender system.



Keywords: agents, information filtering, personalization, profile exploitation, profile genera-

tion, profile maintenance, recommender systems, taxonomy, user modelling



1. Introduction

The development of the Internet has resulted in a global information society

with a growing number of users around the world. Yet, because of this

avalanche of information at our doors, there is a rapidly increasing diffi-

culty in finding what we want when we need it and in a manner which best

meets our requirements. Users are constantly confronted with situations in

which they have too many options to choose from, where they need help

to explore and to filter out their preferences from the myriad possibilities.

Internet Search Engines, designed originally to be helpful, now commonly

find many thousands of potentially relevant sites, thus losing their usefulness.

Recently, in the Artificial Intelligence community, there has been a great

deal of work on how AI can help to solve this problem. The idea of person-

alized search engines, intelligent software agents, and recommender systems

has been widely accepted among users who require assistance in searching,

sorting, classifying, filtering and sharing the vast amount of information

now available on the Web. A combination of modelling the preferences



286

MIQUEL MONTANER ET AL.

of particular users, building content models, and modelling social patterns

in intelligent agents (Maes 1994) would provide users with a means for

managing information in a rational way, thus helping them to overcome the

information overload.

The kind of personalized agent which develops will depend on the require-

ments of the application. It is therefore essential that we identify different

design possibilities and investigate their properties. In this paper, we carry out

a comprehensive and systematic study of recommender agents. Analyzing the

different systems, we have identified a list of 8 dimensions in which recom-

mender agents can differ and possible values for these dimensions, therefore

providing a taxonomy.

The intention of this paper is to present state-of-the-art elements orga-

nized into a simple classification, explain the methods used and describe their

advantages and disadvantages. Thus, the main purpose is to provide a starting

point for researchers to construct their own recommender agents.

This paper is organized as follows. First, we present the dimensions

that constitute the taxonomy, which we group in two blocks: dimensions

regarding profile generation and maintenance and dimensions related to

profile exploitation. In Sections 3 and 4 we provide the classification of

the systems according to dimensions of profile generation and maintenance

and profile exploitation respectively. We continue by performing a cross-

dimensional analysis in Section 5 and end with Section 6 in which several

conclusions are presented.

2. The Taxonomy

In a relatively short time, several recommender agents have been developed

and there is a wide variety of such systems, all of which take advantage of a

particular set of AI techniques. We have followed two main approaches in this

study of recommender agents: spatial and functional. The spatial approach

produces a classification of agents according to the application domain (see

Table 1 for the domains of the various systems analyzed). The functional

approach produces a classification based on the different task-achievement

techniques used in the system. This latter approach allows us to study the

systems systematically and consequently, we have spent more time on it.

Consistently, when analyzing how a personal agent makes recommen-

dations or assesses a user, the key issue is the user profile. User profile

generation and maintenance requires five design decisions which constitute

the first five dimensions of our taxonomy: the profile representation tech-

nique, the technique used to generate the initial profile, the source of the

relevance feedback which represents the user interests, the profile learning



A TAXONOMY OF RECOMMENDER AGENTS ON THE INTERNET

287


Table 1. Domain of the analyzed systems

NAME


REFERENCES

DOMAIN


ACR News

Mobasher et al. 2000

Netnews filtering

Amazon


Amazon 2001

E-commerce

Amalthaea

Moukas 1997

Web recommender

Anatagonomy

Skagami et al. 1997

Personalized newspaper

Beehive

Huberman and Kaminsky 1996



Sharing news

Bellcore Video Recom

Hill 1995

Movie recommender

Casmir

Berney and Ferneley 1999



Document recommender

CDNow


CDnow

E-commerce

Fab

Balabanovic and Shokam 1997



Web recommender

GroupLens

Resnick et al. 1994

Netnews recommender

ifWeb

Minio and Tasso 1996; Asnicar



Web recommender

and Tasso 1997

InfoFinder

Krulwich and Burkey 1995, 1996

Information recommender

INFOrmer


Riordan and Sorensen 1995;

Netnews filtering

Sorensen et al. 1997

Krakatoa Chronicle

Kamba et al. 1995

Personalized newspaper

LaboUr

Schwab et al. 2001



Document recommender

Let’s Browse

Lieberman et al. 1999

Web recommender

Letizia

Lieberman et al. 1995



Web recommender

LifeStyle Finder

Krulwich 1997

Purchase, travel and store

recommender

MovieLens

Good et al. 1999

Movie recommender

News Dude

Billsus and Pazzani 1999

Netnews recommender

NewsWeeder

Lang 1995

Netnews recommender

NewT

Sheth and Maes 1993



Netnews filtering

Personal WebWatcher

Mladenic 1996

Web recommender

PSUN

Sorensen and McElligot 1995



Netnews recommender

Re:Agent


Boone 1998

E-mail filtering

Recommender

Basu et al. 1998

Movie recommender

Ringo/FireFly

Shardanand 1994; Shardanand

Music recommender

and Maes 1995

SIFT Netnews

Yan and Garcia-Molina 1995

Netnews filtering

SiteIF

Stefani and Strappavara 1998



Web recommender

Smart Radio

Hayes and Cunningham 1999, 2000

Music lists recommender

Syskill & Webert

Pazzani et al. 1996; Pazzani and

Web recommender

Billsus 1997

Tapestry

Goldberg 1992

E-mail filtering

Webmate


Chen and Sycara 1998

Web recommender

WebSail

Chen et al. 2000



Web search filtering

WebSell


Cunningham et al. 2001

Purchase recommender

Websift

Cooley 1999



Web recommender

WebWatcher

Armstrong et al. 1995; Joachims

Web recommender

et al. 1997


288

MIQUEL MONTANER ET AL.



Figure 1. Profile generation and maintenance.

technique and the profile adaptation technique. Figure 1 shows the relation-

ships between these techniques in the generation and maintenance of user

profiles.


The profile representation is the first step to take into account in a recom-

mender agent since the other techniques depend on it. Once this step is

decided, the other techniques can be defined. A recommender agent cannot

begin to function until the user profile has been created. Furthermore, the

system needs to know as much as possible from the user in order to provide

him/her with satisfactory results from the very beginning. Therefore, systems

need to use a suitable technique in order to generate an accurate initial profile.

To generate and maintain the user profile, the system needs relevant infor-

mation about the user’s interests. When users interact with a computer, they

provide a great deal of information about themselves. Successful interpreta-

tion of these data streams is necessary for computers to tailor themselves to

each individual’s behavior, habits and knowledge. As for the interaction of

the user with these applications, the system can gather relevance feedback to

learn his tastes, interests and preferences. Relevance feedback is then a main

dimension for recommender agents. Typically, the feedback, given explicitly

or implicitly by the user, has no sense in itself. Therefore, there is a need

for a profile learning technique which extracts the relevant information and

structures this information depending on the representation of the profile.



A TAXONOMY OF RECOMMENDER AGENTS ON THE INTERNET

289


Figure 2. Profile exploitation for recommendation.

User tastes usually change as time goes on. Therefore, the user profile

should also be changed in order to retain the desired accuracy in its exploita-

tion. Hence, the need for a technique to adapt the user profile to new interests

and to forget old ones.

Once there is a user profile available, personal agents exploit it to recom-

mend either products or actions to a user. Intelligent agents make decisions

according to the information available. Such information includes data about

items as well as different profiles of other agents on the web. Since there is

so much information, a fundamental issue is to select the most appropriate

information with which to make decisions. In other words, an information

filtering method is essential. There are three information filtering approaches

for making recommendations: demographic filtering, content-based filtering

and collaborative filtering. Demographic filtering uses descriptions of people

to learn the relationship between a particular item and the type of people who

like it. Content-based filtering uses descriptions of the content of the items to

learn the relationship between a single user and the description of the items.

Several user profile-item matching methods can be used in order to compare

the user’s interests and the items. Collaborative filtering uses the feedback

from a set of people concerning a set of items in order to make recommen-

dations, but ignores the content of the items. Various methods are used by the

systems to match user profiles and find users with similar interests.



290

MIQUEL MONTANER ET AL.



Table 2. Dimensions of the taxonomy

TAXONOMY OF RECOMMENDER AGENTS

Profile generation and maintenance

Profile exploitation

User profile representation

Information filtering method

Initial profile generation

User profile-item matching technique

Profile learning technique

User profile matching technique

Relevance feedback

Profile adaptation technique

In terms of profile exploitation, then, three main dimensions characterize

intelligent recommender agents: the information filtering method (demo-

graphic, content-based and collaborative), the item-profile matching (when

content-based) and the user profile matching techniques (when collaborative).

See Figure 2 for a general view.

All in all, we have identified, from a functional viewpoint, 8 classification

dimensions for recommender agents, 5 in terms of profile generation and

maintenance and 3 in terms of profile exploitation (see Table 2). We will

now go on to discuss these in further detail.

3. Profile Generation and Maintenance

Five design decisions should be taken to generate and maintain a user profile:

the representation, the technique to generate the initial profile, the source of

the relevance feedback which represents the user interest, the profile learning

technique and the profile adaptation technique (see Figure 1).

3.1. User profile representation

Constructing accurate profiles is a key task since the system’s success will

depend, to a large extent, on the ability to represent the user’s current interests.

Accurate profiles are vital for both the content-based component (to insure

recommendations are appropriate) and the collaborative component (to insure

that users with similar profiles are indeed similar).

Several approaches have been taken to represent user profiles, such as a

history of purchases, web navigation or e-mails, an indexed vector of features,

a n-gram, a semantic network, an associative network, a classifier including

neural networks, decision trees, inducted rules or Bayesian networks, a matrix

of ratings and a set of demographic features. Table 3 shows the user profile

representation techniques used by the different systems analyzed.


A TAXONOMY OF RECOMMENDER AGENTS ON THE INTERNET

291


Table 3. Profile representation technique of the systems

NAME


TECHNIQUE

ACR News


Frequent itemsets, URL clusters

Amazon


Purchase history with ratings

Amalthaea

Weighted feature vector

Anatagonomy

Weighted feature vector

Beehive


Clusters (weighted feature vector)

Bellcore Video Recom

User-item ratings matrix

Casmir


Weighted feature and document network

CDNow


Purchase history with ratings

Fab


Weighted feature vector

GroupLens

User-item ratings matrix

ifWeb


Multivalued weighted attributes, weighted semantic network

InfoFinder

Decision tree

INFOrmer


Weighted associative network

Krakatoa Chronicle

Weighted feature vector

LaboUr


Probabilistic feature vector, boolean feature vector

Let’s Browse

Weighted reature vector

Letizia


Weighted freature vector

LifeStyle Finder

Demographic features

MovieLens

Weighted feature vector, inducted rules

News Dude

Short-term: weighted, long-term: boolean feature vector

NewsWeeder

Weighted feature vector

NewT


Weighted feature vector

Personal WebWatcher

Probabilistic feature vector

PSUN


Weighted n-grams

Re:Agent


Weighted feature vector, neural network

Recommender

Inducted rules

Ringo/FireFly

User-item ratings matrix

SIFT Netnews

Boolean feature vector, weighted feature vector, decision tree

SiteIF


Weighted semantic networks

Smart Radio

User-item ratings matrix

Syskill & Webert

Probabilistic feature vector, boolean feature vector, decision

tree, weighted feature vector

Tapestry

Indexed messages and annotations

Webmate

Weighted feature vector



WebSail

Boolean feature vector

WebSell

Interesting/not interesting products



Websift

Inducted rules, patterns, statistics

WebWatcher

Boolean feature vector



292

MIQUEL MONTANER ET AL.

3.1.1. History-based model

Some systems keep a list of purchases, the navigation history in WWW or the

content of e-mail boxes as a user profile. Additionally, it is also common to

keep the relevant feedback of the user associated with each item in the history.

A historical approach is most commonly used in e-commerce, in which

systems keep a list of purchased products and user ratings, as a user profile.

This is the case in the two most popular state-of-the-art recommender systems

in e-commerce: Amazon.com (Amazon 2001) and CDNow.com (CDNow

2001). A similar approach is used in WebSell (Cunningham et al. 2001), in

which the profile is defined by using two lists, one with purchased products

rated as interesting and another with uninteresting ones. Another approach is

implemented in Tapestry (Goldberg et al. 1992), an e-mail filtering system

which builds a profile while keeping track of messages and annotations given

by the user.

3.1.2. Vector space model

In the vector space model, items are represented with a vector of features,

usually words or concepts, with an associated value. This value can be a

Boolean or a real number. The Boolean value represents the presence of the

value of the feature, and the real number represents the frequency, relevance

or probability of the feature, which is calculated using information indexing

techniques (see Section 3.3.2).

For example, Webmate (Chen and Sycara 1998) utilizes a multiple feature

vectors representation. The basic idea is to represent each document as a

vector in a vector space so that documents with similar content have similar

vectors. Each dimension of the vector space represents a word and its weight,

calculated as a combination of the statistics term frequency (see Section

3.3.2).

3.1.3. Weighted n-grams



In weighted n-grams, items are represented with a net of words with weights

in the nodes and edges. For example, PSUN (Sorensen and McElligot 1995),

based on the assumption that words tend to occur one after another a

significantly high number of times, extracts fixed length consecutive series

of characters and organizes them with weighted links representing the

co-occurrence of different words. Therefore, the structure achieves a context

representation of the words.

3.1.4. Weighted semantic networks

Semantic networks (Potter and Trueblood 1988) are able to store the mean-

ings of words, so the human-like use of these meanings is possible. Minio

and Tasso, in the ifWeb system (Minio and Tasso 1996), implement such


A TAXONOMY OF RECOMMENDER AGENTS ON THE INTERNET

293


an approach. In IfWeb, a semantic network base contains a collection of

semantic networks describing a typical pattern of topics of interest to the

user. The Stefani and Strapparava approach in the SiteIF system (Stefani

and Strappavara 1998) represents every node as a word or an interesting

concept and the arcs between nodes are the co-occurrence relation between

two words; every node and every arc has a weight representing a different

level of interests to the user.

3.1.5. Weighted associative networks

An associative network consists of a set of nodes which represent primary

terms, concepts or words, in which a user is interested. A set of weighted

links establishes the organization of these terms into relevant phrases. Associ-

ative networks differ from the semantic networks because semantic networks

have different generic link types such as synonymy, superclass-subclass, and

also possibly disjunctive and conjunctive sets of links. In contrast, associative

networks have only a single link type, a weighted edge, the semantics being

implicit in the structure of the network and the parameters associated with the

processing (Riordan and Sorensen 1995).

3.1.6. Classifier-based models

Systems using a classifier as a user profile learning technique retain the struc-

ture of the classifier as a profile. This is the case in neural networks, decision

trees, inducted rules and Bayesian networks.

A neural network is a network of input and output cells, based upon neuron

functions in the brain. Neural networks create a compact representation that

responds to queries quickly. However, they can be slow to train. For example,

Re:Agent (Boone 1998) filter e-mails through a neural network previously

trained with feature vectors of past messages.

A decision tree is another way to classify data. It consists of a set of

nodes and a set of directed edges that connect the nodes (tree structure).

The internal nodes represent questions about the parameters, and the edges

represent answers to those questions, i.e. values for the parameters. The

leaf nodes represent a final decision. For example, InfoFinder (Krulwich and

Burkey 1996) recommends documents based on a decision tree.

Association rules have been used for many years in merchandizing, both to

analyze patterns of preference across products, and to recommend products to

consumers based on other products they have selected. Association rules can

form a compact representation of preference data which improve efficiency

of storage as well as performance. For example, an association rule expresses

the relationship that a certain movie is often purchased along with others

(Basu et al. 1998).


294

MIQUEL MONTANER ET AL.

A Bayesian network is a directed acyclic graph in which nodes represent

propositional variables and arcs represent dependencies (Jensen 1996). A

node’s value is a function of the values of the nodes it depends upon. Leaf

nodes represent propositions, which can be determined by observation. The

resulting model is very small, very fast and essentially as accurate as nearest

neighbors methods (Breese et al. 1998).

3.1.7. User-item ratings matrix

Some collaborative filtering systems maintain a user-item ratings matrix as

a user profile. The user-item ratings matrix contains historical user ratings

on items. Each cell (u,i) of the matrix contains a rating representing the

evaluation of the user to the item i, and an empty value if there is no

evaluation.

These systems do not use any learning profile technique (see Section 3.3.1)

but bring together all the processes in the user profile matching techniques

(see Section 4.3).

3.1.8. Demographic features

Demographic filtering systems create a user profile through stereotypes.

Therefore, the user profile representation is a list of demographic features

which represent the kind of user. None of these systems use any learning

profile technique (see Section 3.3.1) but they bring together all the processes

in stereotype reasoning (Kobsa et al. 2001).

3.2. Initial profile generation

It is desirable to learn as much as possible from the user so that the recom-

mender agents provide satisfactory results from the very beginning. However,

the user is not usually willing to spend much time in defining his interests to

create his profile. Moreover, users’ interests may change over time, making

the profiles difficult to maintain. For these reasons, starting up and main-

taining user profiles is a difficult aspect in the design and development of

intelligent agent systems. The degree of automation in the acquisition of

user profiles can range from manual input, to semi-automatic procedures

(stereotyping and training sets), to the automatic recognition by the agents

themselves. Table 4 shows the initial profile generation techniques used by

the different systems analyzed.

3.2.1. Empty

Some systems do not bother with the initial profile and start with an empty

profile structure (e.g., Chen and Sycara 1998; Balabanovic and Shoham



A TAXONOMY OF RECOMMENDER AGENTS ON THE INTERNET

295


Table 4. Initial profile generation technique of the systems

NAME


TECHNIQUE

ACR News


Training set

Amalthaea

Manual

Amazon


Empty

Anatagonomy

Empty

Beehive


Empty

Bellcore Video Recom

Training set

Casmir


Unknown

CDNow


Empty

Fab


Empty

GroupLens

Empty

ifWeb


Training set, stereotyping

InfoFinder

Training set

INFOrmer


Training set

Krakatoa Chronicle

Empty

LaboUr


Training set

Let’s Browse

Training set

Letizia


Empty

LifeStyle Finder

Stereotyping

MovieLens

Training set

News Dude

Training set

NewsWeeder

Training set

NewT


Training set

Personal WebWatcher

Manual

PSUN


Training set

Re:Agent


Manual, training set

Recommender

Training set

Ringo/FireFly

Training set

SIFT Netnews

Training set

SiteIF


Empty

Smart Radio

Training set

Syskill & Webert

Manual, stereotyping

Tapestry


Empty

Webmate


Empty

WebSail


Empty

WebSell


Empty

Websift


Training set

WebWatcher

Manual


296

MIQUEL MONTANER ET AL.

1997; Cunningham et al. 2001). There is no initial phase, the profile struc-

ture is filled through an automatic recognition method when the user begins

interaction with the system.

3.2.2. Manual

A manual system asks users to register their interests in the form of keywords,

topics and so on. One of the advantages of this method is the transparency of

the system behavior. When items have been delivered to a user, he/she can

usually easily guess why each item was delivered. One problem with this

method though, is that it requires much effort on the part of the user. Another

problem is that people cannot necessarily specify what they are interested in,

because their interests are sometimes still unknown.

3.2.3. Stereotyping

Stereotyping is based on the fact that creating an initial model is, in a sense,

a classification problem, aimed at generating initial predictions about the

user (Kobsa et al. 2001). The user model is initiated by classifying users in

stereotypical descriptions (Rich 1979), representing the features of classes of

users. The use of stereotypes in computer systems for maintaining models of

their users was introduced by Rich with the Grundy system. Typically, the

data used in the classification is demographic and the user is asked to fill out

a registration form: record data (name, address, etc.), geographic data (area

code, city, etc), user characteristics (age, sex, etc.), psychographic data (e.g.,

lifestyle), etc.

An example is the method implemented by Krulwich in the LifeStyle

Finder (Krulwich 1997) which uses a commercially available database of

demographic data which encompasses the interests of people nationwide.

The main shortcoming of this technique is the difficulty of acquiring

personal data from the users. Internet users normally avoid engaging in a

relationship with Internet sites. This is mostly due to a lack of faith in the

privacy policy of today’s web sites. Normally, users either withhold personal

data or provide false data.

3.2.4. Training set

The training set is a collection of user interaction examples which is used to

infer the initial user profile. One practical way to establish the training set

is to ask the user to rate some concrete examples as relevant or irrelevant to

their interests (e.g., Sorensen and McElligot 1995; Boone 1998). A similar

approach is to ask the user to rate a set of predefined examples (e.g., Good et

al. 1999; Shardanand 1994). In both cases, once the user has given the appro-

priate information, the system processes the data with one of the learning

techniques explained in Section 3.3.


A TAXONOMY OF RECOMMENDER AGENTS ON THE INTERNET

297


This mode has the advantage of simplified handling. It has the disadvan-

tage, and the danger, that someone has to select the examples which are

not always representative and the results are less precise. Some of the

systems using this technique are ACR News (Mobasher et al. 2000); FireFly

(Shardanand and Maes 1995) and LaboUr (Schwab et al. 2001).

3.3. Profile learning techniques

The previous section described sources of information potentially represen-

tative of user interests, mainly the training sets. Profile learning techniques

build a user profile through these data. These techniques can be seen as a

preliminary step in representing a user profile.

It is important to note that when the learning data is composed of

text without structure, it is necessary to pre-process the information in

order to get structured, relevant information. Some systems simply use an

information indexing technique to build a profile and represent it as a struc-

ture of indexed words, although information indexing techniques cannot be

considered artificial intelligence techniques.

Some systems have an off-line phase during which they learn a model of

a user behavior, and then an online phase during which they apply the model

in real time. Most systems, however, use a lazy learning approach (online),

in that they build and update the model while making recommendations in

real time. Offline learning methods may prove practical for environments in

which knowledge of consumer preferences changes slowly with respect to the

time needed to build the model, but they are not suitable for environments in

which consumer preference models must be updated rapidly or frequently.

In this section, we will first briefly explain some typical systems for which

profile learning techniques are not necessary. Then, we summarize the infor-

mation retrieval techniques used to preprocess information. Finally, we look

at the most commonly used profile learning techniques are reviewed: cluster-

ing and classifiers. Table 5 shows the profile learning techniques used by the

different systems analyzed.

3.3.1. Not necessary

Some systems keep information directly acquired from the system as a user

profile, therefore, they do not need a profile learning technique. There are

three main kinds of systems do not need a profile learning method:

− Systems which acquire user profile information from a database. For

instance, electronic commerce systems (Amazon 2001; CDNow 2001;

Cunningham et al. 2001) which extract the information from a database

of products and keep a purchase list as a profile (see Section 3.1.1).



298

MIQUEL MONTANER ET AL.



Table 5. Profile learning technique of the systems

NAME


TECHNIQUE

ACR News


Induction rule learning, clustering

Amazon


Not necessary

Amalthaea

Feature selection (stemming), information indexing (TF-IDF)

Anatagonomy

Information indexing (TF-IDF)

Beehive


Clustering

Bellcore Video Recom Not necessary

Casmir

Simple positive reinforcement, simple positive reinforcement with query



keyword overriding, positive and negative reinforcement, positive and

negative reinforcement with query keyword overriding

CDNow

Not necessary



Fab

Information indexing (TF-IDF)

GroupLens

Not necessary

ifWeb

Feature selection (stop-words, stemming, . . .)



InfoFinder

Feature selection (heuristics), decision tree (ID3)

INFOrmer

Feature selection (stop-words, stemming, . . .)

Krakatoa Chronicle

Information indexing (TF-IDF)

LaboUr

Information indexing (Boolean)



Let’s Browse

Information indexing (TF-IDF)

Letizia

Information indexing (TF-IDF)



LifeStyle Finder

Not necessary

MovieLens

Information indexing (TF-IDF), induction rule learning (Ripper)

News Dude

Short-term: information indexing (TF-IDF), information indexing (Boolean)

NewsWeeder

Information indexing (TF-IDF), MDL

NewT

Feature selection (stop-words, stemming), information indexing (TF-IDF)



Personal WebWatcher

Information indexing (TF-IDF)

PSUN

Feature selection (stemming), n-gram induction



Re:Agent

Feature selection (stop-words), information indexing (TF-IDF), clustering,

neural network

Recommender

Induction rule learning (Ripper)

Ringo/FireFly

Not necessary

SIFT Netnews

Information indexing (Boolean), information indexing (TF-IDF)

SiteIF


Feature selection (stop-words, stemming, . . .)

Smart Radio

Not necessary

Syskill & Webert

Feature selection (stop-words), information

indexing (Boolean), information indexing (TF-IDF), decision tree (ID3)

Tapestry

Not necessary

Webmate

Information indexing (TF-IDF)



WebSail

Information indexing (TF-IDF)

WebSell

Not necessary



Websift

Induction rule learning

WebWatcher

Information indexing (TF-IDF), Winnow, WordStat, random



A TAXONOMY OF RECOMMENDER AGENTS ON THE INTERNET

299


− Collaborative filtering systems (Goldberg et al. 1992; Resnick et al.

1994; Shardanand and Maes 1995) which keep a matrix with the

user-item ratings as a profile (see Section 3.1.7).

− Systems which create an initial profile through stereotyping (see Section

3.2.3) and do not modify it (Krulwich 1997). This is the case in

demographic filtering systems (see Section 4.1.1).

Systems that do not need a profile learning technique concentrate infor-

mation filtering tasks on the profile-item (see Section 4.2) or profile-profile

(see Section 4.3) matching techniques.

3.3.2. Structured information retrieval techniques

When information has no structure (e.g. text), some kind of pre-processing

step is needed to extract structured relevant information. Typically, this

process comprises two main steps: feature selection and information

indexing.

Feature selection can be achieved through different approaches which

reduce the number of words: stop-words, pruning, stemming, etc (see Salton

and McGill 1983).

Information indexing uses the frequency word occurrence to calculate the

potential relevance of an item. TF-IDF is one of the most successful and best-

tested techniques. A document is represented as a vector of weighted terms

(see Section 3.1.2). The computation of the weights reflects empirical obser-

vations regarding text. Terms frequently appearing in a document (TF = term-

frequency), but rarely on the outside (IDF = inverse-document-frequency),

are more likely to be relevant to the topic of the document.

TF-IDF has two popular variants: the boolean method and the probabil-

istic method. The boolean method is a simplistic approach where the profile

is represented as a vector of words with a boolean value indicating their

presence in the text. The probabilistic method is a generalization of the

exact match technique. In this method, documents are ranked by the proba-

bility that they satisfy the information need rather than by making a shape

decision. Bayesian inference networks have proven to be a useful technique

for computing this probability (see Section 3.3.4).

3.3.3. Clustering

The basic idea of this technique is clustering similar user information

into groups based on data. Then, these clusters are matched against actual

information to conclude whether it is interesting or not.

For example, in ACR News (Mobasher et al. 2000) user transactions

are mapped into a multi-dimensional space as vectors of URL references.

This space is partitioned into clusters (usage clusters) representing a group

of transactions that are similar, based on co-occurrence patterns of URL



300

MIQUEL MONTANER ET AL.

references. Finally, clusters are matched against an active user session to

recommend interesting URLs.

Traditional collaborative filtering techniques are often based on matching

the current user profile against clusters of similar profiles obtained by the

system over time from other users (see Section 4.3.1.2).

3.3.4. Classifiers

Classifiers are general computational models for assigning a category to an

input. To build a recommender system using a classifier means using infor-

mation about the item and the user profile as input, and having the output

category represent how strongly to recommend an item to the user. Classi-

fiers may be implemented using many different machine learning strategies

including neural networks, decision trees, association rules and Bayesian

networks.

Learning in neural networks is achieved by training the network with a

set of data. Each input pattern is propagated forward through the network

and active output cells represent the interest of the user. When an error is

detected, it is propagated backward adjusting the cell parameters to reduce the

error, thus achieving learning. For instance, Jennings and Higuchi employed a

neural network for constructing a user’s profile (Jennings and Higuchi 1993).

Decision tree learning is a method for approximating discrete-valued

target functions, in which the learned function is represented by a decision

tree. The learned trees can also be represented as a set of if-then rules.

Decision tree learners build a decision tree by recursively partitioning

examples into subgroups, obtaining source classes of items which can be

classified, for example, into interesting and not interesting (Krulwich and

Kurkey 1995). The most widely-used decision tree learner applied to profiling

is the ID3 (Quinlan 1983).

The discovery of association rules by inductive learning (Mobasher et

al. 2000) is one of the best-known classifier examples. The association rule

discovery methods initially find groups of items occurring frequently together

in many transactions. Such groups of items are referred to as frequent item

sets. Association rules capture the relationships among these items based

on their patterns of co-occurrence across transactions. Association rules can

form a very compact representation of preference data which may improve

efficiency of storage as well as performance. Some examples of inductive

learning techniques are Ripper (Cohen 1995b), Slipper (Cohen and Singer

1999), CN2 (Clark and Niblett 1989) and C4.5rules (Quinlan 1994).

A Bayesian network learner algorithm is applied to a set of training data,

searching over various model structures in terms of dependencies for each

item. In the resulting network, each item will have a set of parent items that

are the best predictors of its votes. The model can be built off-line in a matter

of hours. Thus, this technique may prove practical for environments in which



A TAXONOMY OF RECOMMENDER AGENTS ON THE INTERNET

301


knowledge of consumer preferences changes slowly with respect to the time

needed to build the model.

3.4. Relevance feedback

Human interests change as time passes. For example, a new father may

be interested in infant care just after childbirth, but this interest gradually

decreases over time. Therefore, the recommender agent needs up-to-date

information to update the user profile automatically. In this section, several

ways to obtain this information, which we call relevance feedback, are

presented. Then, in Section 3.5 we will see how to use this information to

update user profiles.

Typically, it is possible to distinguish two kinds of relevance feedback:

positive information (items liked by the user) and negative information (i.e.,

inferring features which the user is not interested in (Holte and Yan 1996)).

The authors claim that negative information produces a dramatic improve-

ment in the system’s performance. However, there are a few systems which

cannot take into account negative information because the system’s accuracy

is likely to decrease (e.g., Schwab et al. 2000). So, it all depends on the

system.


The two most common ways to obtain relevance feedback is to use infor-

mation given explicitly or to get information observed implicitly from the

user’s interaction. Moreover, some systems propose implicit/explicit hybrid

approaches. Table 6 shows the relevance of feedback techniques used by the

different systems analyzed.

3.4.1. No feedback

Some systems do not update the user profile automatically and, therefore, they

do not need relevance feedback. For example, all the systems which update

the user profile manually (see Section 3.5.1). Of course, systems which never

modify the profile do not need relevance feedback either.

For instance, SIFT Netnews (Yan and Garcia-Molina 1995) creates an

initial profile of the user and does not update it automatically over time.

However, the user can modify his profile manually.

3.4.2. Explicit feedback

In several systems, users are required to explicitly evaluate items. These

evaluations indicate how relevant or interesting an item is to the user, or how

relevant or interesting the user thinks an item is to other users (Rich 1979).

There are three main approaches to get explicit relevance feedback:

like/dislike (e.g., Chen et al. 2000; Billsus and Pazzani 1999), ratings (e.g.,

Shardanand and Maes 1995; Moukas 1997) and text comments (e.g., Resnick

et al. 1994; Goldberg 1992). In like/dislike systems, users are required to


302

MIQUEL MONTANER ET AL.



Table 6. Relevance feedback technique of the systems

NAME


TECHNIQUE

ACR News


Implicit (navigation history)

Amazon


Explicit (ratings), implicit (purchase history)

Amalthaea

Explicit (ratings)

Anatagonomy

Explicit (ratings), implicit (scrolling, enlarging)

Beehive


Implicit (mail history)

Bellcore Video Recom

Explicit (ratings)

Casmir


Explicit (ratings)

CDNow


Explicit (ratings), Implicit (purchase history)

Fab


Explicit (ratings)

GroupLens

Explicit (ratings, text comments), implicit (time spent)

ifWeb


Explicit (ratings)

InfoFinder

Explicit (ratings)

INFOrmer


Explicit (ratings)

Krakatoa Chronicle

Explicit (ratings), implicit (saving, scrolling, time spent,

maximizing, resizing, peeking)

LaboUr

Implicit (links, time spent)



Let’s Browse

Implicit (links, time spent)

Letizia

Implicit (links, time spent)



LifeStyle Finder

Explicit (ratings), implicit (purchase history)

MovieLens

Explicit (ratings)

News Dude

Explicit (like/dislike, I already know this, tell me more)

NewsWeeder

Explicit (ratings)

NewT

Explicit (like/dislike)



Personal WebWatcher

Implicit (links)

PSUN

Explicit (ratings)



Re:Agent

No feedback

Recommender

Explicit (ratings)

Ringo/FireFly

Explicit (ratings)

SIFT Netnews

Explicit (like/dislike)

SiteIF

Implicit (links)



Smart Radio

Explicit (ratings), implicit (saving)

Syskill & Webert

Explicit (ratings)

Tapestry

Explicit (like/dislike, text comments), implicit (forwarding)

Webmate

Explicit (like/dislike)



WebSail

Explicit (like/dislike)

WebSell

Explicit (unknown)



Websift

Implicit (navigation history)

WebWatcher

Explicit (goal reached), implicit (links)



A TAXONOMY OF RECOMMENDER AGENTS ON THE INTERNET

303


explicitly judge items on a binary scale, i.e., classify an object as “interesting

or “not interesting”, as “relevant” or “not relevant” or as “like” or “hate”. The

ratings approach requires users to provide a judgement on a discrete scale.

The rating scale is typically numeric (e.g., the web bookstore Amazon.com

offered users the opportunity of rating books in various categories on a 5-

point scale) or symbolic with mapping to a numeric scale (e.g., in Syskill

& Webert (Pazzani et al. 1996) users have the possibility of rating a Web

page as “hot”, “lukewarm”, or “cold”). Finally, several sites encourage textual

comments from their users (e.g., Grouplens (Resnick et al. 1994) and Tapestry

(Goldberg et al. 1992)). Systems gather comments about a single item and

present them to the users as a means of facilitating the decision-making

process. While textual comments are helpful, they require a fair amount of

processing by the targeted user. Users must read text and interpret to what

degree it is positive or negative.

Explicit feedback has the advantage of simplicity. Several papers have

demonstrated the high performance of systems using explicit relevance feed-

back (Salton and Buckley 1990; Buckley and Salton 1995). However, in

practical applications, explicit feedback has three serious drawbacks:

− First, the relevance of information is always relative to the changing

information need of a user, and information relevance judgements of

individual items are typically assumed to be independent when, in fact,

they are not (e.g., the third article presented on the same topic may

simply be rated lower because the first two items satisfied information

need and the user is judging incremental relevance at this point).

− Another problem is that numeric scales may not be adequate for

describing the reactions humans have to items.

− The last problem is that computer users do not supply enough feedback,

particularly negative feedback. Pazzani et al. report that only 15% of

users would supply feedback even though they were encouraged to do so

(Pazzani and Billsus 1997). Users are generally very reluctant to perform

actions not directed towards their immediate goals if they do not receive

immediate benefits, even when they would profit in the long run (Carroll

1987).

3.4.3. Implicit feedback



Implicit feedback means that the system automatically infers the user’s

preferences passively by monitoring the user’s actions. Chatterjee et al. prove

empirically in 1998 that the user’s interests can be inferred from his behavior.

Their results are important because motivating web consumers to provide

personal data in an explicit way is proving very difficult. Conclusions about

the user’s interests should therefore not rely on user explicit feedback very



304

MIQUEL MONTANER ET AL.

much, but rather take passive observations about users into account as far as

possible.

Implicit feedback was defined some years ago by Rich (1979), and the first

system was implemented by Mitchell et al. (1985). Since then, many systems

have implemented implicit user feedback in their approaches (e.g., Stefani

and Strappavara 1998; Schwab et al. 2001) and some systems have even

combined it with explicit feedback (see hybrid approach in Section 3.4.4).

Most implicit methods obtain relevance feedback by analyzing the links

followed by the user (e.g., Lieberman 1995; Mladenic 1996), by a history

of purchases (e.g., Amazon 2001; CDNow 2001; Krulwich 1997), by the

navigation history (e.g., Cooley et al. 1999; Mobasher et al. 2000), by e-

mail boxes (e.g., Huberman and Kaminsky 1996) and by the time spent on

a particular web page (e.g., Morita and Shinoda 1994; Konstan et al. 1997;

Kobsa et al. 2001; Sakagami et al. 1997).

There are many other examples of confirmatory actions. For documents

like Web pages, news articles or e-mail messages, it is interesting to find out

if the user takes any further processing action, such as saving a document

(Kamba et al. 1995), printing a document, bookmarking a Web page, deleting

a document, replying to or forwarding an e-mail (Goldberg et al. 1992), or

scrolling, maximizing, minimizing or resizing the window containing the

document or the Web page (Kamba et al. 1995; Sakagami et al. 1997). Since

these actions are performed under the control of the application, they can be

registered and evaluated to learn the user’s profile.

However, Kobsa et al. (2001) do not recommend a universal logging of

usage data on the micro-interaction level, such as the tracking of mouse

movements within applets, unless the purpose of the login has already been

specified (e.g., for determining user’s interest in page segments (Sakagami

et al. 1997)). The amount of data collected is very large, the computation

needed to derive recommendations for adaptations is extensive, and the confi-

dence in the suitability of these adaptations is likely to be relatively low.

However, experimentation with such data in smaller, laboratory contexts to

drive the development of new methods in the area of implicit feedback seems

promising.

3.4.4. Hybrid approach

The limited evidence available on implicit feedback suggests that it has great

potential but its effectiveness remains unproven. As is common in many tech-

nologies, the best performing system results in combining several existing

technologies. In this field, implicit feedback can be combined with explicit

feedback systems in a hybrid system. Providing implicit feedback greatly

decreases the user’s efforts, whereas providing explicit feedback helps the

system to infer user preferences accurately.


A TAXONOMY OF RECOMMENDER AGENTS ON THE INTERNET

305


One approach with this combination involves using implicit data as a

check on explicit ratings (Nichols 1997). For instance, if a user is explicitly

rating an item, then there should be some implicit data to confirm that he has

actually examined it. If there is no evidence to suggest this, then perhaps its

rating should be ignored or reduced in importance. Conversely, an evaluation

with a relatively long “examine time” may be increased in importance.

A different case is Anatagonomy (Sakagami et al. 1997). Giving explicit

feedback is optional and should only be used when users wish to show explicit

interest. WebWatcher (Joachims et al. 1997), LifeStyle Finder (Krulwich

1997), Krakatoa Chronicle (Kamba et al. 1995), GroupLens (Resnick et al.

1994), CDNow (CDNow 2001) and Amazon (Amazon 2001) also use hybrid

relevance feedback.

3.5. Profile adaptation techniques

Since recommender agents typically involve interaction over long periods of

time, user interests cannot be assumed to stay constant. This normally means

that the most recent observations gathered through what we have called rele-

vance feedback represent the user’s current interests better than older ones.

Therefore, there is a need for a technique that will adapt the user profile to

new interests and forget old ones.

There are several approaches to this: manually (simply adding the new

information), with a time window, aging examples, combining a short-term

and a long-term model, a gradual forgetting function or the natural selection

for ecosystems of agents. Table 7 shows the profile adaptation techniques

used by the different systems analyzed.

3.5.1. Manual

In some systems, the user has to change the profile when he/she is interested

in updating it. For instance, in Sift Netnews (Yan and Garcia-Molina 1995),

when the user wants to include/exclude one of the interests contained in his

profile, he has to modify it manually.

As in manual initial profile generation (see Section 3.2.2), this approach

has two important problems: it requires much effort on the part of the user and

people cannot necessarily specify what they are interested in because their

interests are sometimes still unknown. Therefore, manual updating turns out

to be difficult when requirements change quickly.

3.5.2. Add new information

This approach is the most commonly used in current systems. The idea is

to update the user profile adding new information extracted from the user


306

MIQUEL MONTANER ET AL.



Table 7. Profile adaptation technique of the systems

NAME


TECHNIQUE

ACR News


Add new information

Amalthaea

Natural selection, gradual forgetting

Amazon


Add new information

Anatagonomy

Add new information

Beehive


Add new information

Bellcore Video Recommender

Add new information

Casmir


Add new information

CDNow


Add new information

Fab


Natural selection

GroupLens

Add new information

ifWeb


Gradual forgetting

InfoFinder

Add new information

INFOrmer


Add new information

Krakatoa Chronicle

Add new information

LaboUr


Gradual forgetting

Let’s Browse

Add new information

Letizia


Add new information

LifeStyle Finder

Add new information

MovieLens

Add new information

News Dude

Short-term and long-term models

NewsWeeder

Add new information

NewT


Natural selection

Personal WebWatcher

Add new information

PSUN


Natural selection

Re:Agent


Manual

Recommender

Add new information

Ringo/FireFly

Add new information

SIFT Netnews

Manual

SiteIF


Gradual forgetting

Smart Radio

Add new information

Syskill & Webert

Add new information

Tapestry


Add new information

Webmate


Add new information

WebSail


Add new information

WebSell


Add new information

Websift


Add new information

WebWatcher

Add new information


A TAXONOMY OF RECOMMENDER AGENTS ON THE INTERNET

307


relevance feedback. Thus, the profile is adapted to the new user’s interests.

The main drawback, however, is that old interests are not forgotten.

3.5.3. Gradual forgetting function

The concept of gradual forgetting was introduced by Webb and Kuzmycz in

1996 with the main idea being that natural forgetting is a gradual process.

Therefore, a gradual forgetting function can be defined. It should produce a

weight for each observation according to its location in the course of time.

Webb and Kuzmycz suggest a data aging mechanism which places an initial

weight of 1 on each observation. A set proportion discounts the weight of

every observation each time another relevant observation is incorporated into

the model. Thus, the most recent observations become more “important”,

assuming they better represent the current users’ interests than the older ones.

Hence, the system becomes more noise resistant without losing its sensitivity

to real changes in interest (Schwab et al. 2001).

Koychev proposes a linear gradual forgetting function (Koychev 2000),

but it can be approximated with any function (e.g., logarithmic or exponen-

tial).

A particular case of the gradual forgetting function is the time window



approach. It is the most frequently-used approach in dealing with the problem

of forgetting old interests. It consists of learning the description of the user’s

interests from only the latest observations. The training examples are selected

from a so-called time window, i.e. only the last examples are used for

training (Mitchell et al. 1994). An improvement on this approach is the use of

heuristics to adjust the size of the window according to the current predictive

accuracy of the learning algorithm (Widmer and Kubat 1996).

Maloof and Michalski implemented a variation of the time window

approach (Maloof and Michalski 2000). Instances older than a certain given

age are deleted from the partial memory. Like the time window, the system

only takes into account the last examples. However, this approach does forget

observations outside the given window or older than a certain age.

3.5.4. Natural selection

The natural selection approach is associated with systems implementing an

ecosystem architecture of agents based on genetic algorithms. An ecosystem

of specialized agents competing in parallel, gives recommendations to the

user. The ecosystem evolves in the following way: agents producing the best

results are reproduced with the crossover and mutation operators and others

are destroyed. Amalthaea (Moukas 1997), Fab (Balabanovic and Shoham

1997), NewT (Sheth and Maes 1993) and PSUN (Sorensen and McElligot

1995) use this approach.


308

MIQUEL MONTANER ET AL.




Do'stlaringiz bilan baham:
  1   2   3   4


Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2017
ma'muriyatiga murojaat qiling