\chapter{Introduction}

%% What's in this chapter


\section{The need for intelligent information filtering}
% Brief (half a page)

Group communication systems are spreading increasingly fast as they
become part of the infrastructure in educational, commercial and
governmental organizations. Modern information technology provides
efficient means for fast coordination, dissemination and retrieval of
information. As with all media they have specific advantages, but
with increased popularity a number of disadvantages also emerge, such
as information overload and a low ratio of quality to quantity.

When users must spend more time on the processing of incoming messages
they are usually faced with two alternatives. Some may be able to cut
down the flow by deselecting a source, eg by cancelling subscriptions
on Internet mailing-lists and newsgroups. Others who do not have this
option need help. This help can be an additional worker or a computer
program. Even if the message processing task is out of reach of the
most modern artificial intelligence\footnote{AI systems can be, and
are being built that perform quite well in narrow domains
(\cite{church95a,bratko95a,langley95a}). Outside these domains the
systems perform poorly, if at all.}, the choice may still be in favour
of the computer because software cost less than people.

The user of a filtering program is, inially at least, under pressure
to both continue normal processing and provide instructions for the
filter. For this reason the interface between the user and the program
should be as simple as possible. Current products for the filtering
of electronic mail and Usenet News employ everything from explicit
programming to a simple selection of characteristic examples.

A filtering program is not required to go all the way and perform at
the level of the human user. Usually it will be sufficient if the filter
is able to recognize what is routine and do a gross selection. As with
most tools, a specialized skill is more useful than just being able to
nibble at this and that.

When electronic messages such as email and Usenet News are
to be filtered by a computer program many users and participants
hesitate at the concept of allowing the computer to remove
potentially important information or otherwise censor the information
directed at them. But there is no need to reject or hide anything; a
simple rearrangement of the order in which new items are presented
is usually adequate. 

Human beings adapt very well to their environment, be it an arctic
tundra or an information super-highway. We form our own concepts and
make decisions on the basis of the information available. We create
inferential rules that govern our behaviour based on small cues. Most
of the time we are not aware of these cues and form our decisions
unconsciously. Therefore the task of an information filtering program
is not only to do basic categorization, but to provide cues for the
human eyes and ears which empowers the mind and allows fast, correct
and intuitive decisions with a minimum of cognitive effort.

The preferred properties of a message filtering system outlined so far
can be summarized as:
\begin{itemize}
\item small but competent
\item easy to configure
\item messages are sorted, not rejected
\item it provides the user with clear perceptual cues
\end{itemize}

\section{The purpose of the IntFilter project}

% Very brief (quarter page)
The purpose of the IntFilter project was to investigate techniques
applicable to the filtering of electronic messages.

While the goal includes all form of computer-mediated communication,
it was early decided to restrict the project's attention to
messages from Internet Usenet News, a global bulletin board
system. It was expected that many subscribers of Usenet News share
their opinions on a considerable subset of the messages, something
which appears unlikely for email. Usenet News is also a formidable
source of electronic messages (approximately 20 Mbytes each day) and
it is trivial to create a situation where the amount of input exceeds
the capacity of any human. As opposed to email, most subscribers
feel that they can afford to miss News. A lot of people desist from
reading News at all, simply because there is too much of it.


%% \section{Goals}

% Very brief (quarter page)


\section{Background}

This section presents a number of areas and techniques relevant for
message filtering. One particular interesting distinction is that
between information retrieval and message management. The two concepts
overlap in several places but are distinctly different in some
important properties.

% (Long: if too long, make a separate chapter)
% Scientific interests:
%% Behavioural science (Eva)
%% Computer Science (IR)
%% Artificial Intelligence
%% Cognitive Science and Psychology
% Information retrieval
% The relation between information retrieval and filtering
% Message processing by a human
% The individual and the organization?
% Differences between News, mailing-lists and mail
% Approaches to filtering
%% Retrieval
\subsection{Retrieval}

The nature of computer-mediated communication is that messages are
created, copied to their destination and stored there until the
receiver explicitly deletes them. This abundant storing of copies
creates an accumulation of messages in whatever message system is
used. For example articles in Usenet News are stored in thousands of
copies across all News servers; email is sometimes stored by the
sender and by all recipients; systems for group communication
maintain central or distributed databases of the messages.

With all these messages being stored in a multitude of places it
appears possible to view daily message processing as performing a
set of operations on the result of a database query. In its simplest
form the query can be informally specified as
\begin{quotation}
 {\em `Select all messages not marked as read from my subscription
set, order by arrival time.'}
\end{quotation}

The qualifier {\em from my subscription set} is, in the context of
Usenet News, the set of newsgroups the user subscribes to. Without
this restriction the hypothetical query would be directed at all
unread messages in the News system, an unwieldy amount. The qualifier
can henceforth be assumed.

Actually, the whole issue of message filtering can be captured in the
expressiveness and semantics of the two verbs {\em `select'} and
{\em `order by'}. We would like to be able to say:
\begin{quotation}
{\em `Select all {\em interesting} messages not marked as read, 
order by {\em importance}.'}
\end{quotation}

Naturally we are forced to yield a definition of {\em interesting} and
{\em importance} in terms which the computer can understand. The most
common technique to define {\em interesting} today is in the form of a
list of keywords or phrases, while the term {\em importance} is defined
as the number of matching keywords in a message\footnote{Keywords are
usually weighed by discriminative power to avoid words present in all
or most texts.}.

Information retrieval is among other things also associated with a
purposeful search for information rather than the routine
dissemination of recent developments. The difference is for all
practical purposes the same as the separate uses one has for a morning
paper and an encyclopedia. In the former case, articles have structure
in the form of threads of discussion, immediate and important
information or regular briefings. The articles in an encyclopedia,
however, are reference material. The content of each article is
carefully prepared and relations between articles are not those of
debate but of topical proximity and historical succession. This
distinction is in a way inherited from the work in the information
retrieval community which aim at finding encyclopedically prepared
articles (scientific papers, books, WWW-pages) in huge databases. The
legacy is sometimes a burden, when systems are applied to retrieve
news articles or mail and are unable to properly preserve the temporal
and threaded relations between the articles.

While the selection mechanism (eg keywords) works just as well for
news clippings as for books, the impediment of the information
retrieval view is that it prefers to see the result of a query simply as a
set of documents. This view does not work well for messages
which are part of on-going discussions, already arranged in newsgroups
and often short (25--50 lines).

%% Incremental retrieval
\subsection{Incremental Retrieval}

Anyone who is the receiver of a message flow will have to deal with
the messages periodically or they will overflow the
receptable. Returning to the imaginary query in the previous section,
an information retrieval system could be configured to continously
match all submissions to the database against the standing
query. Matching articles are added to a temporary result which is
fetched by or sent to the user at a convenient time.

Incremental queries allows the user to have an immediate response at
the expense of extra storage in the database. Systems like \SIFT\
\cite{yan95} and \BORGES\footnote{http://borges.compapp.dcu.ie\/}
perform in this way; \SIFT\
sends a regular result to its subscriber via email and \BORGES\
prepares a \WWW-page.

%% Selection of rejected messages
\subsection{Selecting Rejected Messages}

Some simpler filtering systems work by identifying messages to
delete. Rules, keywords or whatever matching mechanism is used, serve
only to pick out unwanted material. The rest is assumed to be
readable. While censoring the user's messages this technique has been
common in News clients for a long time under the name of {\em
`killfiles'}. The point is of course that the user in one way or
another specifies how the filter can recognize unwanted messages.

Since the filter prevents messages from reaching the user it can be
hard to detect classification errors. On the other hand, messages that
are not covered by the undesirability definition will be presented and
this allows for serendipitious discoveries, ie finding out about
something you didn't know you were interested in.

%% Selection of preferred messages
\subsection{Selecting Preferred Messages}

In this filtering technique, rules, keywords, or whatever is used to
pick out articles which are predicted to be of interest to the
user. Messages not selected are deleted.

This strategy may be useful if one is monitoring a specific set of
topics. Since non-matching articles are deleted serendipitous
discoveries are less likely to occur. Misclassifications may also be
difficult to identify.

%% Sorting in order of relevance
\subsection{Order by Importance}

%% place on a scale. threshold for hiding. dubious semantics of a number.

The next step up from systems that perform a binary classification, ie
if the message is allowed {\em `to be or not to be'} read by the
user, is to place each message on a scale.  The user expresses an
opinion about the article in the form of a rating. The rating is often
a point on a discrete scale ranging from bad to good with a few
intermediate steps. Working from the examples rated by the user, the
filter then tries to predict which rating the user will give to the
unread articles.  The prediction is usually a real number which
makes it easy to sort the unread articles in order of
predicted interest. Some systems allow the user to place a
threshold against the list and hide the articles that fall below the
threshold.

While this mechanism has been pursued in some systems (GroupLens
\cite{resnick94a}, Browse \cite{higuchi95}, NewsWeeder
\cite{lang94a,lang95a}, and Newt \cite{sheth94}) a strong argument
against it is that there is no general meaning attached to a point on a
scale. Using a single dimension of interest may be simplifying things
too far; what if the topic of an article is fascinating, but the text
is technical, difficult or poorly written? How to value a text
on a subject which lacks all appeal but is written by one of the
favourite authors? Using a single dimension forces a collapse of
properties which may be in conflict. Once a single point has been
choosen it cannot reveal if this was an all mediocre text or a case
where interests clashed. Information is lost.

Although most proponents feel that there is a noticable distinction
between {\em `good'} and {\em `bad'}, using a single scale for
entering a user's rating makes the filter's job much harder. The
filter is given no clue to the features in the message that makes it
good or bad in the eyes of the user. The features must be induced from
the examples, a process which, if it is to be even moderately
successful, requires a substantial collection of carefully choosen
examples.

In favour of the single dimension approach is that ordinary people
reads what they read one text at a time. So, if the goal of the
filtering system is to arrange the texts in the order believed to be
the most preferred reading order, then there is no escape from
resolving conflicts between properties.

%% Categorization
\subsection{Order by Category}

Rather than working with discrete or continous points on a scale,
categorization of messages follows closely the way we normally archive
information. A label is affixed to the message making it a member of a
class of messages. The classes are weakly disjoint; a message may be a
member of several classes but should in general be in only one class.
This is the approach taken in the \PEFNA\ News filtering system
developed by us.

The \PEFNA\ system allows the user to create a list of
class names. If the user comes across a particularly good example of a
class the user assigns a class label to the article and continues
with the reading. The article is stored on disk.

Before the next Usenet News session, a filtering agent is run to
assign distances between each unread article and each user defined
class. This is done using a standard information retrieval function,
the Cosine measure \cite{salton83}. The measurements are stored in
the user's personal database.

As the user reads News once again, the newsreader (also developed by
us) sorts the unread threads in each newsgroup according to three
values:
\begin{itemize}
\item The major class label of the thread.
\item The average proximity between the thread and the major class.
\item The estimated uniqeness of the major class.
\end{itemize}
Note that the reader sorts {\em article threads} rather than articles. The
reason is of course that threads represent ongoing discussions and
these should be followed in temporal order.

The order of the unread threads follows the order in which the user has
arranged the class labels. There is no inherent assumption of good or
bad in the system, the user must make this distinction (if so
inclined) by creating the appropriate classes.

Our approach to the information filtering problem is similar to the
information retrieval process, where the user has a number of
long-term queries. Each query corresponds to a class the user has
created. The document collection at any time, is the stream of
unread messages provided by the subscribed newsgroups. This view has
earlier been presented by Belkin and Croft \cite{belkin92}.

Our work is similar to that of Sheth \cite{sheth94}, Morita and Shinoda
\cite{morita94}, and Yan and Garcia-Molina \cite{yan93}. Like them, we
have decided to use a simple statistical similarity measure for
queries and documents.


%% Collaborative filtering
\subsection{Collaborative Filtering}

Studies by Malone et al \cite{malone87} present three aspects of
filtering performed by humans, {\em cognitive, economic} and {\em
social}.

Cognitive filtering is content filtering, ie the human reader understands
the contents of the document and makes that understanding the basis
for decisions of further reading.

Economic filtering evaluates the document in terms of the resources it
will consume and occupy when read. For instance, the user's time will
be consumed, attention will be occupied and disk space may be
allocated to store the document for future reference.

Social, or collaborative filtering is when the user values or is
influenced by the opinions of other people. These other people may be
editors and moderators, (un)popular authors or simply fellow
readers. The idea behind computer-mediated social filtering is that a
group of users submit their opinions about articles to a
database. The computer, in turn, perform what in its simplest form can
be described as compu-dating, ie matching people with similar
interests in the assumption that people who have agreed on articles in
the past will agree in the future.

The computer's role in collaborative filtering is to collect opinions
from many readers, allow users to take advantage of these opinions and
to use the correlations to provide ratings for unread articles.

For the cynic, efficient collaborative filtering resides upon two
assumptions; that others have rated the message already and that it
works better the more you conform to the majority.

Obviously, someone must be the first person to rate a
message. Subsequent readers may add ratings of their own, but as the
message gets older the incentive to rate it decreases. Rating the
message for the benefit of others is meaningless for the last
reader. In general, fast and early readers will have to do a lot of
rating while receiving little or no support themselves. It follows
that these persons either will refrain from submitting ratings or that
their input will guide the selection of the majority of the subsequent
readers.

The reason why collaborative filtering is feasible in spite of the
cynic's view is that with a {\em sufficiently large group} there will
be enough variation in who reads a particular message first to give
everyone support over time. There will also be enough participants to
enable almost everyone to recognize a subgroup matching their own
taste.

A possible compromise between pure collaborative filtering and
personal filter systems is to allow for the exchange of user
profiles. That way the individual still receives filtering support
from a personalized service, but is given the opportunity to import
queries or profiles from other users. This removes the frailty of the
first assumption (someone else has already rated the message) since
the first reader will always be the computer. It also moves the
altruistic nature implicit in collaborative filtering from articles to
generalizations of articles.  Conformity is also less of an issue,
since each profile is shaped after its user. Software can perform the
matching and brokering of profiles without having the user feel guilty
for not providing enough feedback to the community.

%% JP-addendum begin

However, collective filtering need not be based on majority decisions
among all who have seen a message. Filtering for one person may be
based on the ratings made by other people with similar values, views
and knowledge. The computer might automatically find people with
similar views, or its users may join groups of users with similar
views who help each other with collective filtering. Collective
filtering need neither be based on majority decisions, several other
decision models are possible. Note that collective filtering is the
basis for newspapers, magazines, journals and radio and TV
broadcasting, and is thus already widely used in society. Computers
can, however, open new options for collective filtering, by removing
the disadvantage with non-computer collective filtering that the
filtering is controlled by a few journalists and editors.

The need for other people to read a message before you read it can be
handled by built-in delays in reading, where in each peer group some
people read message immediately and rate them, and other people in the
peer group read the messages with intentional delays so that they can
be helped by the rating results.

%% JP-addendum end

\subsection{User Input Stress}

%% providing examples increases stress on user. reading time not a
%% good cue. user should be given minimal and optional extra effort.

Work on filtering systems invariably runs into the requirement that
the user provides some form of feedback to the filter. This feedback
demands extra cognitive effort from the user and since the goal of the
effort is to reduce workload, this feedback should be kept as simple
as possible. The problem influences the way that user interfaces are
created; when the user needs to communicate with the filter the
process should be expedient and intuitive.

%% Glass box model; Kias Phd.
Kristina \HOOK\ at the Swedish Institute of Computer Science has
addressed the problem of how to present an intuitive and workable user
interface to the complex interiors of a software system
in {\em ``A Glass Box Approach to Adaptive Hypermedia''}
\cite{glassbox94a,hook96a}. Metaphorically, the glass box is the
transparent user interface which presents and allows the manipulation
of simple concepts and structures. The system's internal complexity
and actual machinery is hidden from the user in a black box. 

The real issue is of course how far the simplification can be
stretched and still provide a valid signal for the filter. A
completely automated filter must rely on inference and
assumption. Assuming too much, however, will reduce the user's
confidence in the filter, perhaps to such a degree that the filter is
no longer used. At the other extreme the user must explicitly
program each and every condition on which the filter is allowed to
act. This does not ease the burden of the user, and despite the
inability to blame misclassifications on the filter (or perhaps,
precisely for that reason) the filter may be left unused.

The need for simplicity explains in part why the discrete rating
approach is so popular: the user only has to press one of five
buttons. Other workers (eg Morita et al \cite{morita94}) have
attempted to infer the user's interest from the time spent examining
an article. While it may be possible to detect that some articles
suffered an early rejection (the user did not scroll through the
entire article, only 25 \% of the lines were on the screen long enough
to be read) this is a risky business. The filter can never be sure
that an exposed article is actually being read since there is an
infinite number of reasons why the user {\em is not} currently reading
the article.

%%It is instructive to ponder the amount of information needed to
%%communicate ones own preferences just to another human. Even though
%%one has access to the full social and psychological interface of
%%speech, gestures, and facial expressions there may still be special
%%terms in need of definition, vague emotional states, indecisions and
%%so on. Conveying the same information to a computer, accurately
%%model it and keep the model up to date is indeed a formidable task.
