\chapter{Contributions}

% what's in this chapter


\section{Comparisons of two document similarity metrics}

This section is a summary of \cite{kilander94a}.

In order to estimate the similarity between a query and a collection
of documents in a database, a number of metrics have been applied and
tried in the area of information retrieval. The metrics are easily
adapted to provide a numerical distance between an unread message and
a set of long-term queries.

For the purpose of developing a message filter application, two
particular metrics were empirically evaluated.  They were the the
cosine measure by Salton et al \cite{salton83} and sub-string indexing
by Morita and Shinoda \cite{morita94}.

The cosine measure has received its name from a trigonometrical
analogy: the angle between two vectors in N-dimensional space is
always measurable across a 2-D plane. When the vectors point in the
same direction the angle between them is $\phi = 0$.  When they are
perpendicular to each other the angle between them is $\phi = \pi /
2$. Taking the cosine of the angle normalizes the range between the
extremes into
\[
	\{\cos(\phi = \pi / 2) = 0 \ldots \cos(\phi=0)=1 \}\,.
\]

In this {\em vector-space} model, the desired result is directly
available by taking the cross product of the vectors. For texts, each
document or query is represented by a vector of weighted terms:
\[
	V = \{wt_{0},wt_{1},\ldots,wt_{n}\}
\]
where each $wt_{i}$ consists of two parts, the numerical weight and
the term. The term is some component feature of the document, usually
a string containing a word or a phrase, e\ g `computer' or
`concept graphs'. In addition, the term may be any boolean
feature of the document.

Given a candidate document $d$ and a stored document $q$, the cosine
similarity was computed in the following way:
\[
	sim_{q,d}=\frac{\sum_{t} w_{q,t} \cdot w_{d,t}}
{\sqrt{\sum_{t} w_{q,t}^{2}} \cdot \sqrt{\sum_{t} w_{d,t}^{2}}}
\]
where $w_{x,t}$ was the number of times term $t$ occurred in document
$x$. The resulting term, $sim_{q,d}$ would be $1.0$ for identical
documents and $0.0$ for documents with no common terms.

When the frequencies of isolated words are used to
describe a document, no memory of ordering remains. For example, a
document like
\begin{quote}
`A horse is better than a car.'
\end{quote}
is regarded as identical to
\begin{quote}
`A car is better than a horse.'
\end{quote}
although they say different things. Additionally, the sentences
\begin{quote}
`Take off your shoes.'
\end{quote}
and
\begin{quote}
`Remove thy footwear.'
\end{quote}
are regarded as completely dissimilar. In summary, the cosine measure
is a {\em statistical} comparison which draws its strength from the
style and vocabulary commonly shared by texts on a particular topic.

Using phrases instead of single words reduce the chance that words
from different contexts support a match but also requires in a higher
degree that similar documents actually share wording. The first
example above will still yield a high similarity since both sentences
share the two-word phrases
\begin{quote}
`a horse', `is better', `better than', `than a', `a car'.
\end{quote}

Comparing phrases rather than single words will do nothing for the
third and fourth examples which requires semantic knowledge to judge
similarity. The analysis is quite complex. Not only must the single
word `remove' be matched against the phrase `take off', but it
must also be inferred that `take off' is used in a context where it
means exactly that, rather than `depart' or `aeronautic
manouver'. The words `shoes' and `footwear' do not have any
simple equality either; while the imperative in the two sentences
collapses the generalization to the particular situation of the
utterance, `shoes' can be seen as an instance of `footwear' and
may be equally replacable by `sandals', `boots' or `ankle
chains'.

The sub-string indexing similarity measure is simply the proportion of
terms shared by two documents:
\[
	sim = \frac{2 \mid V_{q} \cap V_{d} \mid}
		{\mid V_{q} \mid + \mid V_{d} \mid }\,.
\]

\subsection{Experiments}

A sample of articles consisting of 101 articles was taken in
non-sequential order from a newsgroup with a number of ongoing threads
and heterogeneous postings (alt.games.doom). One article was selected
to act as the query. All articles in the sample (including the query
itself) were then compared against the query and their similarity
registered. The message headers were included in the comparison.

\begin{table}
\centering
\begin{tabular}{|l|r|c|c|}
\hline
	& Words	&	Case		&	No case		\\
\hline
Cosine	&  1	&  0.264948 (0.115154)	& 0.307219 (0.117363)	\\
\cline{2-4}
	&  2	&  0.073103 (0.114970)	& 0.073977 (0.115743)	\\
\hline
Substring & 1	&  0.259642 (0.086204)	& 0.282888 (0.084398)	\\
\cline{2-4}
	  & 2	&  0.073875 (0.098067)	& 0.077426 (0.097920)	\\
\hline
\end{tabular}
\caption{\label{stats}Average similarities (and standard deviation).}
\end{table}

Two dimensions were tested for each similarity measure: document
feature and letter case significance. Document features were terms,
constructed from single words or two-word phrases created by combining
adjacent pairs of words.  Table \ref{stats} summarizes the average
measurements for the eight test combinations. The cosine measure on
single word features gave the highest average similarity while the
sub-string indexing metric had a steeper similarity slope than the
cosine measure as documents separated.


\section{A survey of filtering systems}

This is a summary of \cite{kilander96b}.

A number of workers are providing or researching mechanisms to filter
Internet messages. The most common target of these efforts are
directed at Usenet News. Inspired by a compilation of references to
message filtering systems provided by Doug
Oard\footnote{http://www.glue.umd.edu/enee/medlab/filter/filter.html,
oard@glue.umd.edu} eleven systems differing in approach and ambition
were compared.

%% The following terms were used to describe the systems:
%% \begin{itemize}
%% \item {\em Model}---The general filtering model: does it retrieve or rate.
%% \item {\em Adaptation}---How the filter is adapted to the individual needs
%% of the user.
%% \item {\em Classification}---How the filter performs its classification.
%% \item {\em Motivation}---How the filter shows or defends its
%% classification of a particular article.
%% \item {\em Operation}---How and when the filter operates.
%% \item {\em Implementation}---How the filter is implemented.
%% \item {\em Results}---What are the results (if any).
%% \end{itemize}

\subsection{Summary of examined systems}

\subsubsection{SIFT}

The Stanford Information Filtering Tool (\SIFT) \cite{yan95} is a
service provided over the World Wide Web (\WWW). Users access the
filter by submitting one or more {\em subscription profiles} to the
service using a \WWW-browser with forms capability. Each profile
specifies a number of keywords using two alternative matching
strategies; a boolean conjunction of (optionally negated) terms, or, a
set of keywords and a weight threshold. The profiles are matched
against the entire news-feed received at Stanford. Matching articles
are sent to the user by email.

\subsubsection{NewsWeeder}

NewsWeeder \cite{lang94a,lang95a} is a system in experimental use
at Carnegie Mellon University. A special \WWW-browser serves as
user interface. The user visits each newsgroup of interest in turn. For
each group, the user rates interesting articles using a number in the
range 1--5.

The system collects the rating information and presents the
overall rating averaged across all other NewsWeeder users. As such the
systems provides collaborative filtering. NewsWeeder can also
provide a {\em prediction} of the score, computed with machine
learning techniques from the user's profile of past ratings.

\subsubsection{Browse}

Browse \cite{higuchi95} is a reader for Usenet News with a neural
network model of the user's interests. Each message presented to the
user is classified as either being accepted (read) or rejected (not
read). The first 300 words of the message (filtered by stop list of
common words) are used to represent the features of the message.

Browser rates articles and can be used in one of three modes: {\em all
articles, selected ranked articles} and {\em augmented keyword
search}. The {\em all} mode simply shows all articles in chronological
order. The {\em search} mode employs the neural network model to rank
each article and filter them against a threshold value (settable on
the \GUI).  In the augmented keyword search mode the user can type in
keywords that increase the acceptance or rejection of an article.

\subsubsection{NewsClip}

NewsClip\footnote{ http://www.clarinet.com/newsclip.html\/} is a
programming language focussed on Usenet News filtering. The compiled filter
operates offline by comparing the user's {\em .newsrc} file with the
contents of the news server. It applies its rules to all unread
messages and rewrites the {\em .newsrc} file in such a way that messages
that are filtered out are marked as already read. As a result, the 
user is free to employ any conventional newsreader.

\subsubsection{Lurker}

Lurker is a personal retrieval program written in Perl by Vince
Taluskie\footnote{taluskie@utpapa.ph.utexas.edu}. In short, it can be
seen as a way to periodically perform {\em grep} on a Usenet News
server and have the selected articles stored on disk or sent to the
user as email. Lurker is similar to \SIFT\ in spirit.

\subsubsection{SMART}

\SMART\ \cite{buckley85a} is an old and ambitious software package. It
is basically an information retrieval system, with its functions being
open to specialized applications. The general system can be used with
the newsfeed as the message store, or its routines can be built into a
special-purpose browser.

\subsubsection{GroupLens}

GroupLens by Resnick et al \cite{resnick94a} is a system for
distributed, collaborative filtering of Usenet News. Unlike most other
systems who regards the News systems as an opaque message store,
GroupLens ties deeply into the infrastructure of News and exploits its
mechanisms for its own purpose. Briefly, GroupLens allows users to
rate articles as they are read. The ratings from each user is then
stored in a rating server, a {\em Better Bit Bureau}. Just as in the
News system, there can be many servers across the Internet and users
subscribe to the server nearest to them. The rating servers use
a distinguished newsgroup in the ordinary news system to exchange
ratings.

The synergy achieved by having articles rated by many readers is that
the rating servers can correlate users with similar preferences. This
allows the rating server to hypothesize the rating a user will give to
an unread article.

\subsubsection{Borges}

The \BORGES\ project\footnote{http://borges.compapp.dcu.ie\/} is a
European effort to build a News and \WWW\ filtering system using a
\WWW-browser as the client and the \SMART\ system as the retrieval
engine.

\BORGES\ consists of a \WWW-server interfacing a \SMART\ database. The
database stores (or can access) user profiles and News articles. The
user submits standing queries (as with \SIFT) and then retrieves the
result in the form a \WWW-page updated each day.

The interface for query submission allows the interactive refinement
of keywords and phrases based on polysemous words. That simply means
that the interface highlights words and phrases that may have multiple
meanings, like the word {\em `bank'} which may refer to a financial
institution, a subset of a computer's memory or the sloping sides of a
riverbed.


\subsubsection{InfoScan}

InfoScan\footnote{http://www.machinasapiens.qc.ca/english/infoscanang.html\/}
is a commercial system which in essence presents a two-dimensional view of
how a number of locally stored texts relate to a particular query.

The texts (which must be files on the local file system) are arranged
into what InfoScan calls {\em sources}. These sources are then further
aggregated into {\em collections}. The user maintains a set of {\em
filters} where each filter is a set of keywords. When a filter is
combined with a collection the result is a query, and infoscan
graphically visualizes the relation between the filter and the texts
found in the collection.

\subsubsection{RAMA}

\RAMA\ \cite{binkley96a} is a retrieval system where a query server
accepts queries via email. It then searches through a collection of
News, FTP and \WWW\ sources it knows about and returns the result via
email. The user may have standing queries. The server keeps track of
users, queries and the time answers were reported to avoid serving the
same answer twice. The matching algorithm uses the Cosine measure and
simple pattern matching (agrep).

\subsubsection{Pefna}

\PEFNA\ is a rating system, developed by Kilander, \FAAR, Lantz and
Palme in the IntFilter 
project\footnote{http://www.dsv.su.se/\~{
}fk/if\_Doc/IntFilter.html\/} at the department of computer and 
systems sciences (DSV) at Stockholm University.

\PEFNA\ consists of a Usenet News client and a classifier agent.  The
user runs the client to read Usenet News from a standard news
server. The client allows the user to create and maintain an ordered
list of freely named categories. An article which is judged by the
user to be a good example of a particular category is saved under the
name of the category. Over time, the user accumulates a number of
categories and one or more example articles in each.

The agent compares the user's {\em .newsrc} file with the contents of
the news server and retrieves any new articles. Each article is then
compared against the examples in each category and a list of Cosine distances
is built and saved. 

When the user launches the client the next time, it examines the
article ratings provided by the agent. In each thread, one category is
selected as the most representative for the thread. The list of
threads presented to the user is then sorted to follow the sequence
in which the user has arranged the categories.


\subsection{Classification}

The purpose of the classification mechanism is to assign each article
to a class, or more generally to a point on a scale of
attractiveness. Methods that use boolean expressions commonly reach a
point where a binary decision is made; the article is either
interesting enough to be recommended or it is not. Other
classification schemes allow a softer gradation, allowing the user to
modify the cutoff threshold at will.

\begin{table}
\centering
\begin{tabular}{|c|c|c|c|c|}\hline
Boolean 	& Cosine 	& MDL		& Neural  & User 	\\
expression	& measure	&		& network & correlation	\\
\hline
NewsClip	& NewsWeeder	& NewsWeeder	& Browse  & GroupLens	\\
\SIFT		& \SIFT		& 		&	&	\\
Lurker		& \SMART	&		&	&	\\
		& \RAMA		&		&	&	\\
		& InfoScan	&		&	&	\\
		& \BORGES	&		&	&	\\
		& \PEFNA	&		&	&	\\
\hline
\end{tabular}
\caption{\label{classif}Filter systems categorized by classification method.}
\end{table}

Five different types of classification schemes are represented among
the examined filters:
\begin{itemize}
\item Boolean expressions.
\item The Cosine measure.
\item Minimum description length ({\sc mdl}).
\item Neural network modelling.
\item Correlation of user profiles.
\end{itemize}
Table \ref{classif} shows the 11 systems and their method of
classification.

%======================================================================
% User studies (Ann)

\section{Criterias for filtering}

Ann Lantz performed two studies \cite{lantz94} to investigate how
readers of Usenet News evaluate and classify an article. The first
study used four subjects who were subjected to monitored reading
sessions and interviews. The work resulted in a number of message
properties which were submitted to a larger audience in the second
study in the form of a questionnaire. Twenty subjects responded.

\begin{table}
\centering
\begin{tabular}{|l|l|}
\hline
Percentage	& Alternative	\\
\hline
80\%		& Subject line (what I thought the article was about)	\\
40\%		& The genre the text belongs to				\\
30\%		& Where the article is placed in the thread		\\
25\%		& (Articles are read) in the presented order		\\
\hline
\end{tabular}
\caption{\label{altwo}How subjects choosed an article to read.}
\end{table}

When asked how they choosed an article to read, 80 percent answered
that they looked at the subject line (table \ref{altwo}). Many also
regarded the genre, or style, of the text as a factor in the decision.

\begin{table}
\centering
\begin{tabular}{|l|l|}
\hline
Percentage	& Alternative	\\
\hline
80\%		& Subject line	\\
35\%		& The length of the article	\\
30\%		& The amount of quoted text in the article	\\
25\%		& The author of the article	\\
25\%		& If the article was well written and structured \\
25\%		& The genre the text belonged to	\\
\hline
\end{tabular}
\caption{\label{althree}How subjects choosed an article to avoid.}
\end{table}

To avoid an article, more factors came into play (table
\ref{althree}). Again the subject line was rated as most important by
80 percent, followed by a fairly even distribution (25--35 percent)
between such properties as the length, the genre, the amount of cited
text, the author, and the structure or the article.

Nearly all subjects (95 percent) felt that there was a need to filter
information in Usenet News. The subjects were asked what they could
accept in order to accomplish mechanical filtering. The responses were
that
\begin{itemize}
\item 65\% accepted selection rules
\item 45\% accepted keyword search in the subject line
\item 45\% accepted that the system had access to their user profile
\item 35\% were willing to supply a binary rating
\item 15\% were willing to supply a rating on a scale of ten steps.
\end{itemize}

Only 5 percent preferred that an automatic filtering systems worked
without intervention, while 55 percent wanted to have an active
dialogue with the filter.


%======================================================================
% Methods and properties to filter mail by students.

\section{Message properties as perceived by users}

This is a summary of \cite{kilander96a}.

Students at the Department of Computer and Systems Sciencs (\DSV) were
given the task of writing a short essay on the problem of using
machine learning to classify electronic texts and messages such as
electronic mail (email), Usenet News postings or World Wide Web (\WWW)
pages. The purpose was to collect information from real users on what
they perceive to be important properties in electronic messages. For
the more than one-hundred students the essay was a small part of a
wider examination. Fifty-four of them elected to adress the issue.

The authors of the essays were all students at \DSV, at the time
halfway through their second year of a four year curriculum. With all
likelyhood, all of them used \WWW\ and email at \DSV, some of them
also Usenet News. A non-neglible fraction indicated in their essays
experiences from working in other environments where email played an
important role. The majority of the authors were 20--30 years
old. Female authors provided nine of the essays.


\begin{table}
\centering
\begin{tabular}{|l|r|} \hline
Property		& Count	\\
\hline
Keywords		&	40	\\
Sender			&	37	\\
Subject			&	30	\\
Length			&	21	\\
Date and time		&	21	\\
Categories of senders	&	13	\\
Recipients		&	11	\\
Relations to other texts &	9	\\
Semantic text analysis	&	6	\\
Readability analysis	&	6	\\
Keyword synonyms	&	5	\\
Attachments		&	5	\\
Language		&	4	\\
Priority		&	3	\\
Newsgroup		&	3	\\
Layout			&	2	\\
Negative keywords	&	2	\\
Author's keywords	&	1	\\
Nof readers		&	1	\\
History of sender	&	1	\\
\hline
\end{tabular}
\caption{\label{summary}Message properties suggested as important}
\end{table}

Table \ref{summary} shows a summary of the properties suggested by the
students. Most of them had approached the task with email in mind and listed
the sender first, followed by the subject. This likely reflects the
way most people peruse their mail. Many also noted keywords in the
body of the message as an important property, but as an afterthought
or after having spent time thinking further about the problem.
The appreciation of length appeared to be a very individual issue:
some authors apparently used length in conjunction with the sender to
hypothesize the contents of the message (again, mostly for mail).
Time was also an important factor for many; essentially the discussion
revolved around deadlines, events and the time a message was allowed
to be stored but not read.

\subsection{Sender}

\subsection{Senders and recipients}

Several authors indicated that senders should be categorized for
easier processing and developed the concept in several ways:
\begin{itemize}
\item Senders can be persons, organizations or mechanisms.
\item Senders have properties.
\item Senders can be categorized.
\end{itemize}

Senders that are persons are usually known to the user. If not known
personally, the social and organizational relation between the sender
and the user is often already established: supervisor, co-worker,
employee, client, customer etc. Some authors recognized that
categories could overlap (your boss can also be your friend) in which
case other mechanisms would have to be employed in order to determine
which {\em role} the sender is having in the message.

A number of authors felt that knowing the group of recipients of a
message was important. Knowing that others have recieved a message
may influence decisions related to the message.

\subsection{Subject}

Many authors felt that the subject line was very important and
argued that it would be searched for keywords or phrases. Some authors
recognized that subject lines can be useful, but also devastating if
their import is overly emphasized. Writing a good subject or title is
difficult and sometimes willfully abused.

\subsection{Length}

Length was quoted by many authors as important for categorization but
the opinions on its interpretation varied, apparently from their
personal experiences. The basic evaluation of a message's length was that
a longer message would take more time to read (economic
filtering). Some authors argued that short messages usually were the
result of errors or test and could therefore mostly be ignored, while
others felt that the sender and subject determined the importance of
short messages.

None of the authors suggested that the proportion between cited and
original text was an important property, but neither did any one
specify explicitly that length should be counted only as original
content.

\subsection{Date and time}

Information about dates and times were considered to be important by
many authors. Several suggested that important time information could
be embedded within the message and should be identified and
extracted. Surprisingly enough, some were apparently ready to discard
messages about events past without reading them. At least one author
suggested that unread email should be subject to aging, ie receive
higher priority with time.

\subsection{Comments}

A number of authors suggested that a combination of techniques and
properties should be used for classification. Considering that many of
the authors wrote with their personal experience in mind, it should be
safe to say that people use whatever information they have at hand and
form heuristics around that.

On a more general level, the attention given to email by the authors
appears guided by two things, the commitment expected of them and
crucial time information, ie deadlines. Commitment is not easily
quantified, but many cite a letter from their `boss' as an example
of something which is given the highest priority.



\section{User studies}
%% Till�gg till "Intelligent Information Filtering" 
%% 96-12-20

%% 3.5 User studies

%% 3.5.1 Think-aloud-study
\subsection{Think-aloud-study}


In 1993 and 1994 Ann Lantz conducted two studies with the aim to se
how experienced users of the Usenet News choose the information to read 
\cite{lantz93,lantz94}. In the first study she let the users think
aloud while they were searching for the contributions they wanted to
read. In the other study, Lantz sent an electronic inquiry to members
in Swedish speaking news groups.  The results show that the users
usually made their choice on keywords in the subject line.


%% 3.5.2 Field investigation
\subsection{Field investigation}

During 1995 and 1996 Eva \FAAR\ conducted a user study \cite{faar96a}
to find out the user�s opinion about the \PEFNA\ filtering system and
to search for possible improvements. At the same time the study
produced a sample of classified texts to use as test material in the
experiments with the filtering system.
 
The study was conducted as a field investigation. Three users used the 
\PEFNA\ prototype to read Usenet News and placed the contributions in 
different categories or `baskets', depending on content and user's interest.

The behaviour of the users and the result of their manual filtering were 
studied through interviews and then analyzed by inductive methods, based 
on Grounded Theory \cite{strauss90}.
%% (Strauss & Corbin, 1990).

The goal was not to formulate a theory as such, but to try to get new ideas 
about how to support users in search of interesting texts.

The analysis lead to the following formulation of the core of the
studied task:
 
The main story seems to be about how a user, by just glancing on a
part of a text, surveys it and decides what it is about and if it is
worth reading, now or later and if so under what circumstances.  The
decision is also whether to read more before deciding what to do.

This formulation can be translated into a more abstract level:

Perception of elements in a contribution give, if they are recognized,
an association that results in a text classification which decides
whether the text is saved for later use.

%% 3.5.3 Generated ideas
\subsection{Generated ideas}

Grounded on these core categories and inspired of ideas born during
the interviews and meetings we formulate how the computer could
support the reader.

The perception can be supported by the system presenting the elements
in the contribution more clearly. The subject line and the keywords
can be displayed brighter, in bold font or in different
colours. Questions and answers can be shown together and perhaps in a
different colour or font.  Connections between contributions in a
chain can also be shown graphically. By showing the complete
contribution in a smaller scale, the system can quickly give an
impression of the contribution's outline, format and size.  These
measures will make it easier for the reader to observe recognisable
elements valuable for the classification.

To support the association the system could show the readers' baskets
next to the contribution. The readers shall also be able to look into
a basket and see the contributions already put there, reminding of the
chosen strategy of classification.

Saving the contribution can be made simpler by direct manipulation,
i.e.  the user can click and drag the contribution over the screen and
drop it in the basket.


%% 3.5.4 Conclusions
\subsection{Conclusions}

The results from the field investigation confirm the conclusions
drawn by Ann Lantz \cite{lantz94}, i.e. that keywords in the subject line
are very important as to how the users judge the contributions, and
completes it with a more detailed image of how the users act.

Through this study we have received support for the assumption that
the computer should be used to present the contributions in a clear
way and that different readers have different wishes and needs. There
are differences between different readers and the same reader on
different occasions.

We have not got any support for the theory that even a {\em rather} good
sorting of the contributions can be of great help. The study lasted
too short a time to make the users really able to use the prototype
efficiently.

The study does not give any reason to reject the filtering technique
chosen but the users say they questioned the possibility to `teach' the
computer what is interesting or not interesting. Instead they suggested
some criteria to use.

Filters can very well be used by groups in co-operation, by letting
different categories of contributions be guided to different
individuals watching different areas for one another. The idea of
letting readers put a judgement on contributions, that others can
benefit from (so called social filtering) is not supported in this
study.



\section{The PEFNA prototype}

The Private Filtering News Agent (\PEFNA) is a prototype system for
filtering Usenet News. \PEFNA\ consists of two pieces of software, a
Usenet News browser (\PFCLIENT) and a classifier (\PFAGENT). The user
runs the client to read news from a standard news server. The client
allows the user to create and maintain an ordered list of freely named
categories. An article which is judged by the user to be a good
example of a particular category is saved under the name of the
category. Over time, the user accumulates a number of categories and
one or more example articles in each.

The agent runs as a batch program, preferrably in the morning
hours. It compares the user's {\em .newsrc}-file with the contents of
the news server and retrieves any new articles. Each article is then
compared against the examples in each category and a list of distances
is built using Salton and McGill's cosine measure \cite{salton83}.
The list is stored in a database in the user's home directory.

When the user launches the client the next time and visits a
newsgroup, the client builds a list of threads for unread articles in
the group. It also examines the user's database for the ratings
provided by the agent. In each thread, a single category is selected
and used to label the thread. The list of threads presented to the
user is then sorted to correspond to the sequence in which the user
has arranged the list of categories.

For example, if the user has placed the category 'Call for papers' at
the top, then all threads closest to that category are sorted to the
top of the list.


\subsection{The article database} 

Practically all information needed by \PEFNA\ is stored in a
subdirectory in the user's home directory. This directory contains the
article classification database, a log over the classification runs,
the names and sequence of the user's preferred categories and a
subdirectory tree holding articles which were selected by the user as
good examples of each category.

The database is a formatted {\sc ascii} file. For each article
information pertaining to the identity of the article is stored, along
with other properties detected in the message. Of particular interest
to \PFCLIENT, the Usenet News browser, is the list if distances
between the article and the user's categories.


\subsection{The classification agent}

The classification agent \PFAGENT\ is written in C and covers
approximately 7600 lines of code. It opens the user's {\em
.newsrc}-file\footnote{Actually, the file is called {\tt .xnewsrc} to
separate it from the test subject's ordinary news reader.} and
compares the read articles in the subscribed groups with the contents
of the \NNTP-server. Each unread and unmeasured article is fetched,
and its similarity to each of the existing categories is examined.

The conceptual architecture of \PFAGENT\ is that of a central message
fetching engine and a collection of measurement routines. The message
engine visits each of the newgroups to which the user is a subscriber
and retrieves the article number (not the article itself) of each
available article. It then passes the newsgroup name and article
number to each of the measurement routines. Each routine may
independently decide if it needs to retrieve the text of the article
or not.



\subsection{The presentation sequence}

When the user commands \PFCLIENT\ to visit a newsgroup, the subject,
references and message-id fields are fetched from the server. The
message-id is used to lookup the article's entry in the article
database prepared by \PFAGENT. The references and subject fields are
used to tie together the articles in threads.

Within each thread the articles are ordered temporally, there's really
no other convenient way if one wants to follow a discussion over
time. Therefore, the filtering task boils down to arranging the
threads. Since the user's categories are viewed and available from top
to bottom in a menu, the threads are sorted to conform to that order.

Since many threads consists of a single article, these are very simple
to assign. The thread's category is simply the category the article is
most similar to. For longer threads the method of choosing a winning
category is not that obvious so a simple voting scheme was used. Each
article in the thread adds its similarity counts to each category and
the category with the highest sum is choosen to represent the thread.


\subsection{Experiments with term weights}

While the cosine measure works quite well, it does lead to
misclassifications. In order to evaluate the accuracy of the
similarity measure, the core of \PFAGENT\ was modified to select a
number of testcases from a user's set of examples, and assign them to
the most similar category.

Three classes of term weighing measures were evaluated, as
represented by a total of 12 different weighing methods. The base
case was to assign the weight of a word from its occurrence count, ie
the more it appears in a category the more important it must be. The
first alternate case was the inverse document frequency, which
estimates that the word frequency should be divided by the number of
categories in which the word appears, but without further regard for
how often it is represented in each category. The final, and most
successful weighing measure was discriminative informativity, a
measure adapted from the machine learning community. This measure
penalizes words that tend to be evenly distributed across several
catagories while favouring words which are good indicators of category
membership.

In quantitative terms, the best case achieved when using the
informativity measure was an average classification accuracy $7.6$
times better than assigning the article to a category randomly.
