\chapter{The history of the IntFilter project}

% what's in this chapter

\begin{figure}
\centering
\input{workersgant.latex}
\caption{\label{wgant}Workers in the IntFilter project 1993--1996.}
\end{figure}

\section{Formation of the project}

% Gathering workers
A number of workers has been involved in, or associated with the
IntFilter project. A rough sketch of their involvement is shown in
figure~\ref{wgant} on page~\pageref{wgant}.
%% Solid lines indicate
%% continuous involvement, dashed lines a less active association.

% Jacob, Jussi, Daniel, Ann, Olle
Several people took part from the outset, and a core group consisting
of Daniel Pargman, Jussi Karlgren, Ann Lantz, Olle Palmgren and Kia
H\"{o}\"{o}k set about gathering related research and discussing the problems
involved in filtering.

\section{Ghosts}
Background research continued and during the fall of 1993 Palmgren and
Pargman started to build a prototype system they called \GHOSTS. This
was a system based on the newsreader \NN\ and the design featured several
components: a filtering news client, an email filter, a rule editor
and a newsgroup editor. It was implemented in C and C++ and slowly
grew larger and larger.

\GHOSTS\ was taken to the level of carefully guided demonstration in
the first months of 1994. At this time both Palmgren and Pargman were
compelled to direct their attention elsewhere in order to complete
their exams before the end of the spring semester. Pargman continued
in close association with the IntFilter project but lacked the
resources necessary to continue coding. The development of
\GHOSTS\ ceased.

\section{Discussion}

% Speculation and discussion
% Olle leaving, Fredrik entering.

While Kilander completed his dissertation in May 1994, debate ensued
within the core group. Conflicting interests drew in different
directions while there was still hope that Palmgren would be able to
complete \GHOSTS\ to a level sufficient for user testing.

The group agreed upon a number of key factors of the filtering
problem and a filtering software tool. The tool would have to
operate in close cooperation with the user, raising a requirement for
a well developed user interface. The user should also be given 
enough information from the filter to be able to understand how the
filter had operated on a particular message.

However, the working group had not resolved the issue of how articles
were to be measured by the filter, ie which machine-readable features
that should be the atomic functions on the filter's decisive
expressions. Everyone understood clearly that there were many possible
measurements, eg the number of words, the proportion of cited text,
genre classification or the presence of selected keywords, but there
was no good understanding how these related to human judgement.  Lantz
was already underway to tackle this problem from a psychological and
behavioural view but the results so far were inconclusive.

\section{Ghosts reevaluated}
% Reevaluation of the Ghosts program, criticism.

By August 1994 Kilander began to take active part in the
project. His first task was to examine the \GHOSTS\ system in the
expectation that he would be able to continue development.  As it
turned out \GHOSTS\ was a remarkable piece of software, but not very
well suited for research purposes. Documentation was scarce and mostly
missing. The package required non-standard libraries and tools (read
{\em hacks\/}) to compile and relied on the presence of a complex
newsreading system (\NN) which was not installed on the available host
computer.

Furthermore, the basic filtering mechanism in \GHOSTS\ was a forward
chaining production system with dubious properties. The rules would
fire indeterministically, ie the conflict resolution strategy was
random selection. Rule antecedents could contain both classification
operations and destructive message handling. The combination made it
very difficult to ensure that a rule set did not accidentally remove a
message. To create and maintain a developing set of rules under these
circumstances was unappealing and the decision was made to abandon
\GHOSTS.

% The scripts hack.

\section{Scripts}

In order to examine the efficiency of naive filtering, Kilander wrote
a small system called \SCRIPTS. It used unix shell-scripts, standard
unix utilities {\em (sed, grep, wc, comm, awk, sort)} to fetch
articles from a news server and compare the number of words common to
a set of stored example texts. Only words five characters or longer
were counted and the number of lines of original text was weighed into
the final result. The output consisted of a \HTML-page listing article
references in order of descending weight.

From this simple system a number of important points were
learned. First, it worked! It was not terribly accurate but for the
only newsgroup and topic selected in the short trials the most
relevant articles were usually found in the top ten percent
of the output list. Another point which was established was that the
five character limit was too narrow. It did not allow for acronyms
which on most occasions are very related to the target topic. Finally,
the system was unwieldy and inefficient; there would be no cheap victories
won by slow programs\footnote{Applying system programs like awk, sed
etc from a shell script requires that separate processes are created
for each. To measure a single article usually required 10--15
processes run and the delays quickly added up.}.

\section{Ellemtell}
% Initial contacts with Ellemtell

In late 1994 Lantz and Kilander approached Hans
\"{O}hrvall on Ellemtell to inquire into the possibilities to do a field
study at their site of a filtering system yet to be developed. While
the needs of Ellemtell did not exactly correspond to the interests of
the IntFilter project it was agreed that techniques and concepts could
be tested, when available.

The members of the core group, now consisting of Lantz, Kilander,
Karlgren and Pargman, continued to debate the possible features and
mechanisms in a filter. Kilander's \SCRIPTS\ system had demonstrated
that simple systems could provide a benefit and as frustration over
the lack of a proper prototype system accumulated, the group reached the
firm understanding that it was not necessary to have a totally
competent filter; a little help would be a lot more than none at all.

\section{Lantz's user studies}
% Ann studies project members on grounds for classification.
Lantz undertook two studies in which she interviewed subjects on
how they decided to read or not to read a news article. The first
study was performed in late 1993 \cite{lantz93}, the second, complemented
by a questionnaire, in 1994 \cite{lantz94}.

Essentially, she found that the main features of the articles used
by the subjects to form their decision was
\begin{itemize}
\item keywords in the header's subject line
\item keywords in the body
\item genre
\item author
\item length
\item thread position, and
\item a body inconsistent with the subject line.
\end{itemize}
In addition, almost all subjects felt that filtering would be useful
in Usenet News.

\section{Algorithmic studies}

% Comparing algorithms
Meanwhile (late 1994) Kilander had started a search for algorithms
which could be used to compare News articles against keywords or
prototypical texts. The results are presented in \cite{kilander94a}
and the conclusions were that the established Cosine measure
(Salton and McGill \cite{salton83}) was preferred over any ad hoc
solution. Lang reported \cite{lang94a,lang95a} slightly better results
using {\em Minimum Description Length} ({\sc mdl}), an information
theoretic measure, but {\sc mdl} was not choosen because it is
complicated and difficult to thoroughly understand.

\section{A new prototype}
% Committment to produce a solid prototype

As the pressure to produce a working prototype increased, Kilander
pursued the search for algorithms no further and began designing a
filter system. Two major issues influenced the design. The filter should
have a modern graphical user interface and the processing of articles
should be efficient. Other considerations involved how the filter tied
in to the normal reading of Usenet News. Proxy news servers (as had
been the case in \GHOSTS), modified readers and even servers were
contemplated. 

In the end, the design settled on a two-component system. A News client
was to be written using the Tcl/Tk scripting environment. The client
would offer simple news reading operations and provide the user
interface to the filter component. The filter was implemented as a
stand\-alone (batch) program, written in C. The communication between
the filter and the News client was in the form of a database where the
filter stored information about measured articles. When the user read
News, the client consulted the database to order the articles in a
presentation sequence.

The separation of the filter from the client relieved the client from
the burden and delay of filter processing. It also relieved the filter
of an unneccesary portion of user interface routines, which in the
case of the X Windows System is quite substantial. As it turned out,
this was the correct choice, since the filter needed that runtime
memory to store many lists of words.

Writing the client in Tcl/Tk enabled rapid prototyping of a modern
{\sc gui}. In addition, the lowlevel {\sc nntp} routines could be
borrowed from the arTCLs News client written by Mike
Hoegeman\footnote{mh@awds.imsd.contel.com}.


\section{Dissipation}
% Daniel and Jussi gradually disengaging.
% Ann leaving, Ellemtell cooperation breaking down.

In early 1995 the core group of IntFilter workers had already begun to
dissolve. Pargman had been accepted to Link\"{o}ping University in
August 1994 and while attending meetings his association with the
IntFilter project gradually weakened. In Febrary 1995, Lantz was given
a position at the department of Psychology at Stockholm University and
took the opportunity to pursue her dissertation. Karlgren was involved
in various other projects and finally left for New York in the summer
of 1995.

Discussion continued in the administrative group consisting of Jacob
Palme, Yvonne Waern and Kilander. Lantz and Pargman attended these
meetings during the first half of 1995.


\section{The prototype emerges}

The prototype filtering system was given the name \PEFNA {\em (Private
Filtering News Agent}). Originally scheduled for July 1995, the
prototype was not ready to be given to users until December that
year. The reason was that changes in the way user feedback was to be
given required portions of the code to be rewritten several times.

The first design specified that the user classified articles with a point
on scale of attractiveness. Five buttons labelled -2, -1, 0, +1 and +2
were placed beneath the text. If the user felt inclined to rate the
article a button was pushed using the terminal's pointing device. The
article was then saved under a corresponding label where the filter
component could get at it.

The filter was then supposed to compare unread articles to the rated
examples using the Cosine measure. It would then weigh the distance
with the label and the client could use the weight to sort the
presentation sequence accordingly.

However, this did not work very well. The lack of rigid semantics in
the numeric scale made it difficult to judge why a certain article was
given a specific rating. Since rating was performed by the filter
agent, a separate program, the client could not easily motivate the
decision. The filter could possibly store motivations with each
article but that would require massive amounts of disk space,
something which could not be accepted for regular users. While a
Cosine distance metric is a simple number, the filter was designed to
be able to include more complex measurements.
%%In terms of document similarities, the interesting information is
%%the set of matching words.

\section{A new member}
% Eva joins the project.
% PEFNA's categories no longer global but specialized per group.


By September 1995 Eva \FAAR\ joined the project to pick up the
work on psychological and behavioural research previously done by
Lantz. As \FAAR\ familiarized herself with the ongoing work she
suggested that the discrete rating numbers in \PEFNA\ should be
replaced by arbitrary labels. In the following discussion Kilander and
\FAAR\ realized that there was no need even to distinguish these labels in
terms of weight. Articles were simply assigned to their closest label
and the user could arrange and rearrange the order of the labels at
any time.

As a result, the discrete number buttons were removed and replaced by a
tear-off menu. The user reads an article and if the article is a good
example of a category of texts the user assigns a label to the
article. Labels are essentially names for user-defined categories. The
categories are defined by the example texts placed in them. The filter
does not weigh the categories, but simply measures the distance
between each unread article and the categories. The measurements are
stored in the database and the News client sorts the presentation
sequence in the same way as the user has arranged the labels.

\section{First user trial}
% Eva asks subjects to classify messages with PEFNA.

In December 1995 \PEFNA\ was placed into the hands of three
users. The subjects were asked to consistenly create categories
(labels) and categorize articles. The subjects did not at this time
use the filtering component.

%% The purpose of the experiment was to collect a large number of texts
%% categorized by real users in a real reading situation. Close to 1000
%% articles were collected in this way.

The purpose of the study was:
\begin{enumerate}
\item To collect a large number of texts
categorized by real users in a real situation. Close to 1000 articles
were collected in this way.

\item To augment the understanding of how
users spontaneously filter their information.
\end{enumerate}

Three subjects used the \PEFNA\ prototype to read and classifie texts in
categories of their own choice. After the reading the subjects were
interviewed about how they choose what to read and how to classify
the texts. For a detailed description of this part of the study, see
\cite{faar96a}.


% Students are asked about perceived properties for filtering (mail)

\section{Prototype refinements}
% Comparison enhancements are tested.

Working against the collections provided by four users of the \PEFNA\
system, Kilander examined various techniques to improve the
classification of unread articles. The idea was that certain words
were unique in almost every category and therefore should be given
higher weight than words present in several categories. Using the
information entropy measure
\[
\sum_{i=1}^{i=N} P(w|C_{i}) log_{2}(P(w|C_{i}))
\]
the discriminative power of each word was established. Several
combinations of reweighing the words with this information before
applying the Cosine measure were tried, but the results were initially
contradictory since no single variant gave a consistently higher
accuracy for all users. Further examination \cite{kilander96c}
revealed that term weighing based on information entropy provides
more accuracate classification than just term frequency counts.

The experiments reinforced the confidence in the Cosine measure since
with it, the probability of an unread article being assigned to the
correct category were several times higher
\footnote{In this particular case, 5--7 times higher.} 
than if a category had been choosen randomly.


\section{Second user trial}

In june 1996 the subjects in the first trial were approached again and
asked to use the \PEFNA\ system once more. This time they were to
recreate categories important to them but only store relevant and
typical examples. They were also to use the filter component.

At this point \PEFNA\ had seen further revisions and
refinements. The categories to be used for article labelling could now be
selected for each newsgroup. This enabled a more focussed presentation
and avoided the confusion that arose from articles being assigned to a
category only relevant in another newsgroup.


