\newcommand\CMCS{{\sc cmcs}}
\documentstyle{article}

\title{Message Classification and Filtering}

\author{Fredrik Kilander \\
fk@dsv.su.se \\
http://www.dsv.su.se/\~{ }fk
}

\begin{document}
\maketitle

\begin{center}
{\sc IntFilter} \\
{\sc k2lab} --- Laboratory for Knowledge Engineering and Communication \\
Department  of Computer and Systems Sciences \\
Stockholm University and the Royal Institute of technology \\
Electrum 230, S-164 40 KISTA \\
Sweden \\
\end{center}


\section{Introduction}

This document is a proposal of how to implement classification and
filtering of messages in a computer mediated communication system
(\CMCS).  The particular \CMCS\ we have in mind ({\sc kom}) consists of
two basic components, a {\em client} and a {\em server}. The client is
the user interface through which the user exchanges messages with the
server and updates personal information. The server acts as a central
repository and database for both messages and information about users.
In addition to its communication with the clients, the server also
exchanges information with other servers. These other servers may be
other \CMCS\ servers or servers for Usenet News or electronic mail.

From the user's point of view, the \CMCS\ system collects messages from
several sources: the \CMCS\ itself, Usenet News, mailing lists, and
email, and presents them in a coherent form. The \CMCS\ client enables
the user to process messages from or to these sources through a single
interface.


\section{Messages Sequenced by Multiple Sources}

In a traditional setup where the user has to execute email, Usenet
News and computer conferencing as separate tasks, each such task is a
discrete and easily identified piece of work. It appears intuitive to
expect that people schedules these tasks in order of importance; say,
email as most important and done first, computer conferencing as
second most important and performed as the second task, while
Usenet News is done last if time so allows.

Within each of these discrete messages sources (email, Usenet News
and computer conferences) messages have internal priority. For
instance, mailing-lists are commonly recieved through email, and their
contents is probably not as highly valued as a letter addressed
directly to the user. Likewise, a computer conference system usually
contains its own mechanism for personal messages. Such messages are
equal in status to the email letter, while most users probably rate
the discussion groups mediated by the conference system with different
levels of interestingness. Finally, Usenet News may in turn contain
newsgroups which the user pays undivided attention, while others
receive only cursory interest.

The use of a single interface such as the \CMCS\ client has both
advantages as well as caveats.  While the user only has to learn a
single interface, the amount of information made available through
that interface is increased, as everything is funneled through the
client. It is technically possible, but pointless, to artificially
recreate in the \CMCS\ the division between email, the \CMCS\ and
Usenet News. It is probably more meaningful to the user to process a
sequence of messages where the most important ones comes first and the
least important messages are presented last. This implies that (given the
preferences already assumed) the sequence begins with personally
addressed letters, either from within the \CMCS\ or from
an outside email source. Next follows a mixture of mailing lists and
computer conferences generic to the \CMCS\ or imported from Usenet News.

%% KOLLA HUR MAILINGLISTOR HANTERAS!

Many \CMCS\ conceptually distinguishes between two types of message
origins, personal mail and conferences. External sources such as
mailing lists and Usenet News newsgroups are coerced into the form of
conferences. The default message sequencing in \CMCS\ consists of
personal mail followed by a list of conferences with unread
submissions. The sequence of conference presentations depends on the
order in which the user subscribes to the conferences. The user may
alter the sequence of conference presentations by moving a conference
to the top of the list, but if left intact the sequence will remain
the same between sessions. This has the effect of offering the user a
sequence of conferences similar in appearence, but of hetergeneous
origin.


\section{Message Sequencing within a Conference}

Within a particular conference or newsgroup there are basically two
types of messages; {\em original} messages and {\em followups},
although the distinction at times can be hard to make. Original
messages are commonly presented to the readers of the conference as
questions, information, advertisements or opinions. Followups usually
refer to the text of an original message or other followups.
Together, the original message and the comments form a {\em thread} of
discussion. It is not uncommon that threads only contain the original
message.

Threads in Usenet News are maintained by two fields in
the header of a Usenet News message:
\begin{itemize}
\item {\tt Message-ID} and
\item {\tt References}.
\end{itemize}

The {\tt Message-ID} field gives the message a uniqe identity.  When a
message is a followup to another message, the last item of the {\tt
References} field is the message ID of the followup'ed message. The
field is not restricted to a single message ID, it may be a list of
several message ID's, copied from the {\tt References} field of the
followup'ed message. However, the standard \cite{rfc1036} allows for
this list to be truncated if the list becomes too long for local
software to handle.  As a consequence, the last item on the list is
the only required link to the referenced message, and a message can
only be a followup to one message, not several.

%% Threads in generic \CMCS\ conferences are strictly maintained by the
%% \CMCS\ server and have therefore a well-defined ordering and reference
%% graph. A difference between \CMCS\ and Usenet News is that the {\tt
%% References:} field of news message may contain a list of several
%% messages being referenced, while a \CMCS\ message always refers to a
%% single message, restricting the reference graph to a tree.

\begin{figure}
\centering
\input{NewsThread.latex}
\caption{\label{NewsThread}An example of a thread in a newsgroup.}
\end{figure}

Figure \ref{NewsThread} shows the structure of a chain of followups.
Bold arrows indicate the main reference (the last item in the {\tt
References} field) while thin arrows represent references inherited
from the followup'ed messages. Message $a.1$ is the original message,
$a.2$ is a followup to $a.1$, $a.3$ is a followup to $a.2$, $a.4$ is a
followup to $a.3$ and $a.5$ is a followup to $a.4$. Message $a.5$ has
truncated its list of message ID's and has only one prior reference.

\begin{figure}
\centering
\input{LogicNewsThread.latex}
\caption{\label{LogicNewsThread}A example of a logical thread tree.}
\end{figure}

Figure \ref{LogicNewsThread} illustrates the structure that emerges
when only the last item of the {\tt References} field is considered
and there are several followups to the same message. In the example,
messages $a.3$ and $a.4$ both are subroots of independent followup
chains.

\begin{figure}
\centering
\input{KomThread.latex}
\caption{\label{CMCSThread}An example of a conference with three
threads.}
\end{figure}

Figure \ref{CMCSThread} shows a conference with three threads. The
threads are labelled $a$, $b$ and $c$. The structure is a combination
of temporal ordering (thin arrows, pointing towards the future) and
reference relations (bold arrows, pointing towards the message
referred to). In essence, the contents of a conference can be viewed
as a temporally ordered lists of threads.

The presentation sequence offered by most news readers and \CMCS\ is
the result of a scan over the threads (major ordering) and within each
thread a depth-first traversal of the graph (minor ordering). In
addition, the interface commonly ensures that each message is shown to
the user only once.

Most news readers allow random access to messages but usually the
sequence governed by newsgroup, thread and depth-first traversal of
the thread prevails. This is technically very convenient and usually
compatible with the user's needs. Since text is inherently a
sequential form of communication, it is up to the interface to convey
to the user why a certain message is shown at a particular time.


\section{Message Classification and Filtering}

The purpose of classification and filtering of messages is to {\em
increase the amount of relevant information} that reaches the user.
This is done by increasing the weight of interesting messages and
decreasing the weight of uninteresting messages. The criteria for what
is regarded as interesting, lies entirely with the user. A
computerized message classificiation process must therefore address
two fundamental issues:
\begin{itemize}
\item modelling the user's interest in the computer
\item classifying each message according to the user model.
\end{itemize}

\begin{figure}
\center
\input{SmallCFpipe.latex}
\caption{\label{SmallCFpipe}Schematic view of the classification and
filtering process.}
\end{figure}

Once the classification process is complete, the filtering, or
weighting of each message takes place. The simplest result of the
filtering is to rearrange the message sequence so that the most
interesting messages are presented before the ones classified as less
interesting. Indeed, it may be the case that the user trusts the
system to completely delete the most uninteresting messages. Figure
\ref{SmallCFpipe} shows a schematic view of the classification and
filtering process.

One of the reasons to separate classification and filtering is that 
classification can be very {\sc cpu}-intensive. Each message must be
scrutinized, potentially for each user. Filtering, on the other hand,
collapses into a summation of weights and subsequent sorting (message
reordering). This invites an architecture where classification is
performed off-line or in the background and the filter component
in the interactive interface performs a minimum of computation.


\subsection{Human Message Classification}

Categories of messages are in their simplest form only two,
interesting and not interesting. Elaboration may provide more classes,
or a continuous range between extremes. 

However, in the assimilation of a message stream the user (with
varying degrees of conciousness) sees in each message a set of {\em
perceived properties}, for instance {\em subject, origin, temporal
persistence} and {\em comprehensibility}. Many such properties are
imaginable.

For each message, the collection of perceived properties is balanced
to form the final judgement of interestingness. The properties may be
in conflict with each other.

\begin{figure}
\centering
\input{Reading.latex}
\caption{\label{Reading}Message reading state diagram.}
\end{figure}

As the user reads on, the property assignment and classification
process continues as more and more information is obtained from the
message. As a particular newsgroup is visited, the nature of the
newsgroup itself creates a set of expectations, or context in the mind
of the reader. Messages are judged in relation to this context. As a
message appears, the first fragments of information (the contents of
the subject, the layout of the text, the first lines of the message)
adds to the set of expectations.

Figure \ref{Reading} shows a hypothetical state diagram of message
reading. Actually reading the text is a cognitive effort. It takes
time and energy. Scanning is much easier and does not require
understanding. The reader glances across the text and stops if a
familiar pattern of characters (such as well-known acronym or name) is
seen.

A switch from reading to scanning signifies that the reader is
uncertain of the proper classification and hopes to be able to satisfy
expectations of interestingness further down. Depending on which
expectations that are denied or fulfilled, the reader may switch
between reading and scanning until the message finally is abandonded.

The message is always abandoned in some stage. It may be abandoned
before the reader has seen or read all text. It can be saved to a file
or a printer for future reference or when the reader reaches the end
of the message. At this point the user either knows that the message
indeed was interesting and the reading a meaningful experience. The
remaining case is a disappointment in that the whole message had to be
exposed or read before the reader knew that the reading was effort
wasted. 

The last case is quite common for short messages simply because they
fit in whole on a computer terminal and contain a comparatively small
amount of information.  In order to know if this information is
interesting or not one has to read it.

The presence of key words or phrases in the subject and text greatly
aid the classification process since the keywords release specific
sets of expectations in the reader.

The identification of perceived properties in the user and their
mapping to machine-readable properties in messages appears central to
the success of an automatic message classification process.


\subsection{Mapping the User Model}

The coupling between the user's intermediate categories and a particular
message can be viewed as the projection of properties onto the message
in the mind of the user. This is a very difficult task, for two
reasons:
\begin{itemize}
\item The set of perceived properties a message invokes in a human
reader varies between different individuals. The set of properties is
difficult to capture and model accurately in a general way.
\item The mapping from the machine-readable and physical properties of
a message correspond very loosely to concepts that are familiar and
important to the reader.
\end{itemize}
In order to perceive the same properties as the user, the computer
must be able to read and understand the message in the same way as
the human. This is currently not within reach. To even get close, and
establish at least a fundemental understanding requires expensive
computations for natural language processing, domain knowledge and
psychological competence.

The prevailing strategy is to force the user to provide the mapping by
restricting the user model to those message properties that are
immediately available or inferrable from unexpensive computation.  By
restricting the language, the user is forced to formulate the
preferences in terms that the machine can understand and manipulate:
the length of a message, the author, the conference, an answer to a
question etc. This is probably the reason why keywords so often are
choosen as a simple and fairly effective classification aid: the
keywords are characteristic symbols for well-defined concepts in the
user's mind. It is not necessary to understand the text in order to
scan for keywords and it is a task well suited to a computer.


\subsubsection{Machine-readable Message Properties}

Machine-readable properties are computed from the message itself. Some
of the properties are absolute, like the number of lines or the
contents of the header fields. Other properties are inferred by
computation. Inferred properties are guided by a model. In some cases
the model is considered universal and in other cases provided by the
user.  An example of a universal model is genre classification, while
a keyword search is an example of a user-specific inference model.

Obviously, absolute and universally inferred properties only has to be
established once for each message. Properties inferred from user
models must be done for each user and message\footnote{Each message in
the user's default presentation sequence.}.

\begin{table}
\centering
\begin{tabular}[t]{|l|ccc|c|}
\hline
Property 			& Abs. 	& Univ. & User	& Cost \\
\hline
Message header			& X	& 	&	& low \\
Position in subject thread	& X	&	&	& low \\
Wordcount			&	& X	&	& low \\
Other reader's evaluations	& X	&	&	& low \\
Percentage of quoted text	& 	& X	&	& low \\
Quoting depth			&	& X	&	& low--medium \\
Language			&	& X	&	& medium--high \\
Keyword search			&	&	& X	& medium--high \\
Pattern search			&	&	& X	& medium--high \\
Layout analysis			&	& X	&	& medium--high \\
Spelling			&	& X	&	& high \\
Genre analysis			&	& X	&	& high \\
\hline
\end{tabular}
\caption{\label{machprops}Machine-readable message properties.}
\end{table}

Table \ref{machprops} lists a number of message properties suitable for
computer processing. For each property, the table indicates if
the property is absolute, inferred according to a universal model or a
model which must be complemented for each user. In each case, the
value of each property is compared to the user model if the model
requests it.


\subsubsection{The Message Header}

\begin{table}
\centering
\begin{tabular}{|l|l|}
\hline
Field			& Required \\
\hline
From			& yes \\
Date			& yes \\
Newsgroups		& yes \\
Subject			& yes \\
Message-ID		& yes \\
Path			& yes \\
Reply-To		& no \\
Sender			& depends on the From field \\
Followup-To		& no \\
Expires			& no \\
References		& iff the message is a followup \\
Control			& no \\
Distribution		& no \\
Organization		& no \\
Keywords		& no \\
Summary			& no \\
Approved		& in a moderated newsgroup \\
Lines			& no \\
Xref			& no \\
\hline
\end{tabular}
\caption{\label{headerfields}Standard header fields in a Usenet message.}
\end{table}

Some of the fields in the message header have already been discussed.
Their description is repeated in this section.  The most common header
fields are shown in table \ref{headerfields}. In addition to the
required and optional fields, any valid mail-header field is
allowed. Furthermore, unrecognized fields are to be left unmolested
\cite{rfc1036}.

The {\tt From} field contains the name and email address of the person
or entity posting the message. The {\tt Sender} field should also be
specified when the user edits the {\tt From} field rather than using
the supplied default. This may happen when someone is sending a
message from a username used by several people.

The {\tt Date} field contains the date and time when the message
entered the news system (was posted). If a finer resolution than 24
hours is required time-zones must be understood. The standard
recommends that universal time (GMT) is used and translated to local
time whenever necessary. Unfortunately, the {\tt Date} field does not
prevent messages from occasionally being presented in the wrong order;
clocks are not globally synchronized and transportation delays may
cause an answer to reach the local news server {\em before} the
question.

The {\tt Newsgroups} field is a list of newsgroups to which the
message is posted. The storage and presentation software uses this to
arrange the messages in newsgroups. In particular, messages directed
to groups not subscribed to can be erased at once by the news server.

The {\tt Subject} field is for humans. According to \cite{rfc1036}:
\begin{quote}
``It should be suggestive enough of the contents of the message to
enable a reader to make a decision whether to read the message based
on the subject alone.''
\end{quote}
Messages with identical {\tt Subject} fields usually belong to the
same thread. However, it is common practice for the software (and
sometimes the users themselves) to prepend the string {\em Re:} to the
original subject string when submitting a followup.
%%The string {\em ``Re: ''} is usually prepended to the contents of the
%%{\tt Subject} field when posting a followup.

The {\tt Message-ID} field gives the message a uniqe identity. The
standard recommends that a message ID is uniqe for at least two years.
With some restrictions, it is up to the sending software to compose
the ID, using a counter or some transformation of the local date and
time.

The {\tt Path} field is for the benefit of the distribution software.
As the message is passed from one host to the next, each one prepends
its own name to the contents of this field. The information is used
for diagnostics and to avoid sending messages to hosts who already has
received them.

The {\tt Reply-To} field is specified if mailed replies to the author
of the message should go to some other address than the one specified
in the {\tt From} field.

The {\tt Followup-To} field is used to redirect followups to the
message to other newsgroups than those specified by the {\tt
Newsgroups} field.

The {\tt Expires} field suggests an expiration date for the message.
This field should be used with deliberation since practically all news
servers have their own expiration policy, based on storage resources
and volume.

The {\tt References} field is a list of message ID's, if the message
is a followup to those messages. The field is not allowed for original
messages. The structure that is created by the list of messages is
slightly peculiar in that each followup inherits the list of
referenced messages from the message it is a followup to. It then adds
the message ID of the referenced message to the end of the list. In
theory, the {\tt References} field of each message which is a followup
to another message, contains the entire list of messages preceeding
it. However, the standard allows for this list to be truncated if the
list becomes too long for local software to handle.  As a consequence,
the last item on the list is the only required link to the referenced
message, and any other references before the last link are bonus
information.

The {\tt Control} field is for internal administration of the News
system and not aimed at any human user (with the possible exception of
the system administrators).

The {\tt Distribution} field controls how far the message is spread.
The intended use of this field is to {\em reduce} distribution; i.e.\
limit distribution to a smaller area. The contents of the field form a
conjunction with the {\tt Newsgroups} field which must be satisfied
for the message to be transmitted and received.

The {\tt Organization} field is for humans. It is intended to contain
a short phrase which helps to identify the person or machine which
sent the message.

The {\tt Keywords} field is intended for
\begin{quote}
``a few well-selected keywords identifying the message$\ldots$ This is
used as an aid in determining if this message is interesting to the reader.''
\end{quote}
One wonders how many news-readers that encourage their users to submit
keywords when posting a message.

The {\tt Summary} field 
\begin{quote}
``should contain a brief summary of the message. It is usually used as
part of a follow-up to another message. Again, it is very useful
to the reader in determining whether to read the message.''
\end{quote}
Since almost all users of Usenet News appears top cite other messages
in their own text, it appears that this field is largely unused.

The {\tt Approved} field is used in moderated newsgroups. It could be
seen as the moderator's signature.

The {\tt Lines} field simply is the number of lines in body of the
message.

The {\tt Xref} field is provided by the local system. The information
links the message to the files that store it.


\subsubsection{Position in Subject Thread}

This information is extracted from the {\tt References} field in the
header. Its usefulness is related to such concepts as {\em answers to
questions}, {\em original} messages and, of course, followups.


\subsubsection{Wordcount}

The number of words in the body of the message provides complimentary
information to the number of lines obtainable from the header.
Although a limit of 80 characters per line often is assumed, both
longer and shorter lines are common. The algorithm performing the
wordcount is quite affected by which language the message is written
in. For instance, the '{\tt \{}' character is not regarded as part of
a word in an english message, but is very likely to represent 
'{\tt \"a}' in a swedish language message.


\subsubsection{Other Reader's Evaluations}

This is an interesting topic and it assumes that the conference system
is able to collect and store reader's assessments of a message. In its
simplest form, the assesments is represented as a point in an
$N$-dimensional space, for example in terms of {\em accuracy, quality,
novelty} and {\em contribution}.

There are two major problems with reader assessments. The first is
that user's may be unwilling to provide good assessments simply
because it takes too much of their time and adds a cognitive
strain to the regular reading process. This problem has no obvious
solution---the users must be motivated, either by altruism or
recognition of the synergetic benefit.

The second problem is that an assessment always is made in some
context; for instance personal satisfaction or recognition of the
needs of a working group. The recorded assessment must somehow be able
to reflect this context or the stored value will be meaningless.

Perhaps the most general solution to both problems is that each user
so inclined reviews messages for personal reasons only, and that other
users {\em prefer} the assessments made by people they feel share
their own views.


\subsubsection{Percentage of Quoted Text}

Many messages include large portions of text cut and pasted from
other documents. Usually, these quoted sections are indicated by
indentation and prefixation by a special character, for instance '{\tt
>}', '{\tt :}', '{\tt ]}' or '{\tt !}'. A simple, yet quite effective
heuristic, is to regard lines that begin with a printing,
non-alphabetic character as cited text (excluding blank lines and
initial white-space).


\subsubsection{Quoting depth}

The analysis of quoted text can be extended to indicate different
levels of quotation and assigning probability estimates to the status
of each line. The percentage of quoted text and quoting depth is
related to questions and answers, followups short in original content
and layout analysis.


\subsubsection{Language}

With the dominant languge being english, readers may be expected to
pay little attention to deviant languages other than those in national
groups. Other classification routines, for instance the wordcount,
work better if the language of the message (or paragraph, or line) is
known.


\subsubsection{Keyword Search}

Keywords are very effective (if choosen correctly) to cull those messages
that are of a particular class. The search and matching process is
subject to a great deal of variation and sophistication. Keywords
found in a message have different status depending of where they are
found; in the {\em Keywords} or {\em Subject} fields, in original or
quoted text.


\subsubsection{Pattern Search}

Pattern searches in a message aim at finding special constructs that
occur in specific contexts. Examples of such constructs are email
addresses, URL's for World Wide Web, portions of source-code from
programming languages or text-encoded binaries.


\subsubsection{Layout Analysis}

The idea behind layout analysis is to model or mimick the impression
the reader gets when scanning the message. It reflects the structure
of the message, not the content. Typical patterns that reflect
different messages are long, original documents with no quoted text
and justified text (call for papers, short stories); followups with
much quoted text and few lines of original content at the end (``me
too''); snippets of source code with regular text between (tutorials,
examples). The layout analysis needs to classify each line according
to some criteria, such as quoted text or programming language.


\subsubsection{Spelling}

Checking the spelling of the text gives information if the text was
written in haste or carefully prepared. Spelling control of course
relies on language classification.


\subsubsection{Genre Analysis}

The genre analysis attempts to classify the message in general terms,
for instance {\em religion, skills and hobbies, general fiction} or
{\em humor}. While this has proven to be possible, these general
genres appears to be subsumed by the specialization of the conferences.
It may be a valuable tool to classify conferences and newsgroups.


\subsection{Classification Mechanisms}

Message properties and the their relation to the classification model
must be encoded in some data structure convenient for processing. The
classification mechanism applies the data structure to each message
and arrives at a classification. Conceptually, the model maps a
specified pattern of properties to a classification. Data structures
and classification engines are available in several guises:
rule systems, decision trees, neural network models and probabilistic
classifiers.


\subsubsection{Rule Systems}

A rule system consists of a set of rules and a production engine. Each
rule is of the format:
\begin{quote}
{\tt IF} {\em condition} {\tt THEN} {\em assertion}.
\end{quote}

The {\em condition} of the rule is a boolean expression. For each
message it will be either true or false. The basic terms of the
condition can be almost anything which can be decided to be either
true or false. For instance {\em keyword '{\tt computerization}'
appears more than three times} or {\em quoted text more than 50
percent}.

The {\em assertion} of the rule specifies what happens when the
condition is true. In the simplest case, the assertion is a
classification. Alternatively, the assertion is either a
classification or a new property, inferred by the rule. The decision
to allow rules to infer properties which other rules may act upon is
one of implementation. The idea with inferred properties is that
recurring combinations of conditions doesn't have to be repeated in
each rule that use that condition:
\[
\begin{array}{rcl}
	P \wedge Q \wedge R & \rightarrow & Z	\\
	Z \wedge S & \rightarrow & W		\\
	Z \wedge T & \rightarrow & X		\\
	Z \wedge U & \rightarrow & Y
\end{array}
\]
is much more convenient than
\[
\begin{array}{rcl}
	P \wedge Q \wedge R \wedge S & \rightarrow & W	\\
	P \wedge Q \wedge R \wedge T & \rightarrow & X	\\
	P \wedge Q \wedge R \wedge U & \rightarrow & Y\,.
\end{array}
\]

Problems that must be addressed with rule systems can be summarized
like this:
\begin{itemize}
\item who writes the rules?
\item which basic terms are to be used for the conditions?
\item what happens when more than one rule has a true condition and
the assertions are mutually exclusive?
\item should one allow the condition of one rule to subsume another?
\end{itemize}

Among the good points with a rule system are that they are fairly easy
to read and understand, and allows for a compact and powerful
representation.


\subsubsection{Decision Trees}

Decision trees are similar to rules in that a decision tree can be
rewritten as a rule system. A decision tree typically consists of a
recursive structure in which each node contains a test on a basic
term. Depending on the outcome of the test, a branch leading to a
subtree is selected where another test is found. Eventually a leaf is
reached and instead of a test, the leaf contains the assertion. The
path from the root to the leaf can be seen as a rule, with a condition
formed by the conjunction of the tests on the basic terms.

\begin{figure}
\centering
\input{DecisionTree.latex}
\caption{\label{DecisionTree}A simple decision tree.}
\end{figure}

Figure \ref{DecisionTree} shows the symbolic rules presented above as
a binary decision tree. Note that two leafs are marked {\em '?'},
indicating that there is no known assertion at that leaf.

Problems with decision trees are that they handle disjunctions
uneconomically, in that each disjunction generates extra subtrees.
They can also become quite large and therefore a bit unwieldy to
inspect. A naive translation into rules presents them with long
and complicated conditions.

Positive aspects of decision trees are that there are good techniques
to generate them automatically from pre-classified examples and that
they are efficient in use.


\subsubsection{Neural Network Models}

Neural network models, or NN for short, has been studied and used for
many years in classification. From an operational point of view they
can be viewed as black boxes that after training perform a certain
classification task. In the classification of messages, the user is
required to supply the NN machinery with a set of accurately
classified training examples.

The NN models do not easily reveal their internal structure. It is
distributed and is for all practical reasons, opaque. This makes it
difficult to provide the user with motivations for a particular
classification. Erroneous classifications can only be removed by
retraining, and then it may be difficult to pinpoint the training
examples that should be removed from the training set.


\subsubsection{Probabilistic Classifiers}

Probabilistic classifiers use various statistical techniques, mostly
based on Bayesian probability. From a set of given features, they
calculate the set of probable classes and their respective
probability. Their are quite robust and not that complicated in their
basic appearence. They have problems with the assumed independence
between selected features and certain pathological sitations involving
mututally exclusive features. These problems have solutions, but the
solutions typically are research issues.

Just as with neural network models, it may be difficult to structure
an explanation for a classification in intuitive terms; the mapping
from features to class is a matter of frequency and likelihood.


\subsection{Machine Learning Techniques}

Three machine learning techniques are considered. They are not
mutually exclusive and hybrid solutions are possible. With one
exception, the learning technique relates very closely to the
classifier it creates.


\subsubsection{Induction of Decision Trees}

This technique constructs a decision tree by recursive subdivision of
a set of training examples. The result can be used either as is, or
reformulated as rules for a rule system. Originating from the CART
algorithm by Breiman et al and ID3 by Quinlan, modern decision tree
builders are more robust and capable than their predecessors: C4.5 by
Quinlan; Assistant by Bratko et al; ID5 by ??? and IDL are some of the
modern algorithms.

\subsubsection{Neural Network Models}

Many different variants exists here both in architecture and
algorithm. Among the commonly used variants are found a three-layered
net trained by backpropagation; Kohonen networks and Hopfield nets.


\subsubsection{Probabilistic Classifiers}

The Recursive Bayesian Classifier by Langley, LMDT by Utgoff and
Brodley. 

\subsubsection{Genetic Programming}

Also known as genetic algorithms, and the slightly confusing term {\em
``classifier systems''} this technique is applicable to each of the
above machine learning techiques. It is a strategy for parallel
hill-climbing in the space of solutions. To be used, it requires a
function that provides a numerical distance between two alternate
solutions. The solutions themselves, may be almost anything: rules,
decision trees, networks or probabilities.

One particular filtering system has been built with the aid of genetic
programming; the Newt system by Sheth. It uses a vector-based approach
to model messages and profiles.


\subsection{Message Filtering}


The conference sequence structure presupposes that users prefer to
assimilate all messages in each conference before moving on to the
next. While this appears perfectly reasonable both from a cognitive
and technical point of view, it conflicts with the possibility of
reading a message classified as important ahead of the conference
sequence. One viable solution is to allow the classification process
to {\em rearrange} the conference sequence, based on some measure of
importance for the conference as a whole.

Within each conference, a similar substructure is displayed by the
thread abstraction, and again the solution appears to be to form a
measure of the importance of the thread as a whole and
rearrange the sequence of threads to reflect this importance.

In essence, the filter assigns each message a weight. The weight of
individual messages propagate to their thread, and the weight of the
threads propagate to the conference. This retains the the conference
and thread structure, but does not rearrange interesting messages
within a thread. Weights can of course be both positive and negative.

\begin{figure}
\centering
\input{InterestOne.latex}
\caption{\label{InterestOne}Hypothetical message weight over the
standard presentation sequence.}
\end{figure}

There are two problems with this approach. Unless signalled for each
message, the user has little chance of knowing when an important
message (in the opinion of the automatic system) is presented. The
interestingness of messages will be similar to the curve in figure
\ref{InterestOne}. The valleys in the curve are created by messages
with less weight but presented with the more important ones because
they are bound together by the same thread.

The second problem is how to formulate a proper summation function for
a thread or a conference. Is a one-message thread with a message of
weight $1.0$ equally important to multi-message thread where only one
message has the same weight?

In conjunction with the regular presentation sequence it may be
advantageous to offer a separate list of interesting messages, sorted
by weight.

\section{Requirements on the Classification and Filtering Module}

The requirements are divided into three groups:
\begin{itemize}
\item user interface
\item application interface
\item operation.
\end{itemize}

\subsection{User Interface}

\begin{enumerate}

\item The user must be able to see and understand the classification
and filtering condition.

\begin{enumerate}
\item The most recent classification and filtering decision made for a user
must be stored.
\item The decision must be time-stamped as it may become
outdated by learning or editing of the classifier and filter.
\item The decision can be removed when the message is erased
from the conference system (implies erasure notification).
\end{enumerate}


\item The user must be able to modify the filtering conditions.

\begin{enumerate}
\item The user must be able to label messages, or part of messages,
as positive or negative instances of a class, and to maintain these as
a current set of interests. This implies deletions and additions to
the set.

\item The user must be able to confirm or disapprove of the automatic
classification. (What bias can be expected from messages lost to
erroneously assigned low weights? The user will see and judge most of
the messages classified as interesting, but runs the risk of not being
able to correct hidden messages.)

\item The ability to specify priority conditions (rules that override
the automatic classification) is, while desirable, not critical to the
automatic classification task per se.
\end{enumerate}

\end{enumerate}

\subsection{Application Interface}

In the context of the CMCS system, the classification module is
perceived as a piece of software cooperating and communicating with
the CMCS server. 

Messages in the direction CMCS $\rightarrow$ classifier:
\begin{enumerate}
\item Message $M$ may be presented to users $\{U_{1}
\ldots U_{n}\}$.
\item Message $M$ has been deleted.
\end{enumerate}

\subsection{Operation}


\subsection{User Profile Maintenance}

The computer's model of a user's interests is kept in a user {\em
profile} or {\em model}. A factor that tends to complicate the
maintenance of the profile is that the importance of the intermedaite
categories change over time and sometimes are dependant on every-day
context.

In order to capture long-term change in the user's interests, it is
necessary to provide continuous feedback from the user to the computer
on its performance. For this several mechanisms are plausible. In the
simplest case, the user reformulates, or edits the interest profile as
if it was issued for the first time. More elaborate methods rely on
confirmation from the user as a signal for incremental change.

Every-day contexts appears difficult to capture and formalize without
the user explicitly communication the context to the computer. One
solution may be to arrange a set of pre-arranged names, to which the
user has associated recurring contexts, like {\em extremely busy},
{\em calling remote}, {\em cracker attack} or {\em feeling lazy}. In
each of these contexts, the relative importance of the intermediate
categories is altered, to better reflect the needs of the current
context.





%%Filtering - message properties
%%filter specification, user's role, learning, maintenance, explanation,
%%interface,
%% Serendipity: discoveries made by chance. A separately
%% compiled hotlist with pointers to the best messages found.
%%
%% ``...to test, please ignore my previous claim...''

\end{document}
