Agents for personalized information filtering and browsing assistance

Dateline: 09/23/97

There is a growing availability of information sources in today's world, and the World Wide Web is the largest one of them . As it is becoming more and more difficult for users to cope with such an amount of information, new tools like agents are devised to assist with information overload. In order for the agents to be of real help, they have to learn user's interests and habits using machine learning techniques, maintain their competence by adapting to the changing interests and exploring new domains that may be of interests to the user. This week we'll learn about techniques and products that help us understand and develop intelligent agents for personalized information filtering.

Behind the stage

There is a large number of learning algorithms used for agents to "understand" user's preferences. Most often, learning algorithms require a set of positive examples of some concepts (such as web pages one is interested in) and negative examples (such as web pages one is not interested in). Most learning programs require that the examples be represented as a set of feature vectors. Each feature usually has a Boolean value that indicates whether a particular word is present (at least once) or absent in a particular web page. The frequency of of the word in the document can also be used. The text is passed through a stemmer, which removes the suffix of the words and keeps only their roots (both "proposing" and "proposal" will become "propos"), thus reducing the number of different words significantly. Stop list is used to remove commonly used words that don't describe the content of a document.

TF-IDF is one of the most successful and well-tested techniques in Information Retrieval (IR). A document is represented as a vector of weighted terms. The computation of the weights reflects empirical observations regarding text. Terms that appear frequently in one document (TF stands for term-frequency), but rarely on the outside (IDF stands for inverse-document-frequency), are more likely to be relevant to the topic of the document. Therefore, the TF-IDF weight of a term in one document is the product of its term-frequency (TF) and the inverse of its document frequency (IDF). In addition, to prevent longer documents from having a better chance of retrieval, the weighted term vectors are usually normalized to unit length. Standard information retrieval weighting mechanism:

where W is a weight of word in a document, Hc is a header constant, Tf is a frequency of the word in the current document and idfk is defined as:

where N is the total number of documents that have been already retrieved by the system and dfk is the document frequency of the k-th term. Header constant is used to give more weight to the words in the title of the document, or any other part of the text we think is important.

The Bayesian classifier is a probabilistic method for classification. It can be used to determine the probability that an example j belongs to class Ci given values of attributes of the example. To determine the most likely class of an example, the probability of each class is computed. An example is assigned to the class with the highest probability. The nearest neighbor algorithm operates by storing all examples in the training set. To classify an unseen instance, it assigns it to the class of the most similar example. Decision tree learners such as ID3 build a decision tree by recursively partitioning examples into subgroups until those subgroups contain examples of a single class. A partition is formed by a test on some attribute (e.g., is the feature database equal to 0). ID3 selects the test that provides the highest gain in information content. Neural networks and genetic algorithms are standard Artificial Intelligence techniques used in information retrieval. Typically, agents traverse the Web and find new documents. Any traversal incurs an energy cost. The amount of energy an agent receives by finding an document is determined by its relevance, which in turn is estimated by standard techniques from IR theory. Each agent can decide to present any document to the user hoping to get bonus energy. This decision uses state information (the current level of energy) along with document relevance. The user's feedback increases or decreases the agent's energy. When energy exceeds a fixed threshold, the agent produces an offspring by cloning or sexual reproduction with random weight mutations; when energy is reduced below zero, the agent dies.

Projects

There are many research projects in this particular area, and I'll briefly describe just a few of them. Armstrong et al. developed WebWatcher, a system that assists user in locating information on the Web by taking keywords from the user, suggesting hyperlinks and receiving evaluation. It learns by observing a user on her way through the Web and suggests interesting hyperlinks whenever it is confident enough. Unlike WebWatcher, Personal WebWatcher (Mladenic) is structured to specialize for a particular user, modeling only her interests. It learns user interests from the pages requested by him by "watching over its shoulder", and doesn't requests any keywords or user opinions.
Balabanovic et al. developed Learning Information Retrieval Agents, a system which learns to browse the Internet on behalf of a user. It searches the Web taking bounded amount of time, select the best pages and receives an evaluation from the user. This evaluation is used to update the search and selection heuristics. Lira has been superseded by Fab (Notice: The Fab system is no longer active. Publications about Fab and subsequent systems can be found at Marko's new home page).
Mitchell et al. developed a system connected to the user's electronic calender that generates sets of rules capturing the user's scheduling preferences, using them to provide advice for new, unscheduled meetings.
Sheth developed Newt, a personalized information filtering system for the Usenet newsgroups that uses genetic algorithms and relevance feedback to learn about user's interests.
Moukas proposed Amalthaea, a co-evolution model of information filtering agents that adapt to the various user's interests and information agents that monitor and adapt to the various on-line information.
Henry Lieberman developed Letizia: as the user operates a conventional Web browser, the agent tracks user behavior and attempts to anticipate items of interest by doing concurrent, autonomous exploration of links from the user's current position. The agent automates a browsing strategy consisting of a best-first search augmented by heuristics inferring user interest from browsing behavior.
Menczer et al. proposed a model for a population of IR agents that are competing for energy from environment and user feedback, thus robustly adapting to their environment.
Pazzani et al. developed Syskill & Webert, a software agent that learns to rate pages on the World Wide Web (WWW), deciding what pages might interest a user. The user rates explored pages on a three point scale, and Syskill & Webert learns a user profile by analyzing the information on each page.