\begin{wrapfigure}{r}{2in}
\begin{center}
\includegraphics[width=2in]{data/lhs.pdf}
\end{center}
\caption{Monitoring average maximum liklihood over 50 eras.}\label{fig:lhs}
\end{wrapfigure}


\begin{figure*}
\begin{center}
\begin{minipage}{.6\linewidth}
\begin{center}
{\scriptsize
\begin{tabular}{l@{~}r|@{~}l|l@{}c@{~}l@{~}c@{~}l@{}c@{}lc@{}r|}\cline{3-9}
\multicolumn{2}{c}{}& \multicolumn{1}{|c|}{incremental} &\multicolumn{6}{c|}{batch}\\\cline{3-9}
data set & \#instances & SAWTOOTH & NB & & nbk&&j48\\\hline
\input{data/10way.dat}
\end{tabular}}
\end{center}
\end{minipage}\hfill
\begin{minipage}{.35\linewidth}
\begin{center}
\includegraphics[width=2in]{data/10way.pdf}
~\\
~\\~\\~\\
{\scriptsize
\begin{tabular}{|c|c|c|c|c|c|c|} \hline
learner & win - loss & win & loss & ties \\ \hline
J48        &     10 &     25 &     15 & 20 \\
nbk        &      8 &     17 &      9  & 34\\
SAWTOOTH        &     -6 &     12 &     18 & 30\\
NB        &    -12 &      9 &     21 & 30 \\
\hline
\end{tabular}
%~\newline~\newline
}\end{center}
\end{minipage}
\end{center}
\caption{$mean \pm standard\; deviations$
seen in 10*10-way cross validation
experiments on UCI Irvine data sets.
``NB'' and ``nbk'' denote  N\aive Bayes
classifiers that use gaussians 
model continuous attributes.  ``NB'' uses a single
gaussian while ``nbk'' uses a sum of gaussians in the method
recommended by John and Langley~\cite{john95}.
The plot top-right sorts the differences in the accuracies
found by SAWTOOTH and all the other learners.
Some of those differences  aren't statistically significant:
the  {\upp} or {\downn} symbols in the left-hand-side table denote 
mean differences that are significantly more or less (respectively) 
to SAWTOOTH 
at the $\alpha=0.05$ level.
The significant differences between
all the learners are shown in
the win-loss statistics of the bottom-right table.
 }\label{fig:uci}
\end{figure*}




One drawback with Bayes classifiers is their handling of continuous distributions.
Bayes classifiers handle numeric attributes via {\em
kernal esitmation} or {\em discretization}.
In kernel estimation, new arrived numeric data is mapped into some underlying
distribution. A standard Bayes classifiers assumes a single gaussian~\cite{witten99} while
more sophisticated methods assume that the distribution is a sum of a sequence
of gaussians. 

Simplistic assumptions about the distribution of  numeric attribute 
often can be modeled
as a  simple gaussian often perform sub-optimially. 

 process
subsets sequentially
or correnctlym then combine
the results.
** use a relational representations: avoids the memory
explosion assocaited with joining denormalization of data


Hulten and Domingos
discuss general principles for scaling up any method
that, at any time, selects a new ``best'' model
from  multiple competing models and their case
studies is learning a directed acyclic  Bayes net;
i.e. not the simpler Bayes classifiers studied here.







XXX windowing.


sequetnail learning ~\cite[p22]{provost99survey}
usually performs {\em worse} that learning from the total
set.  We have not foudn that to be case. Our incremetnatl
naive bayes classifer works as wll or better than a batch baive
baues estiamtor with kernel estiamtion. why tjhis is so ithe subject
of our on-going research. at this stage, we just comment that
we use a dynamic widow size policy,and the disabling of the learner
over periods where new information adds nothing to the existing
frequencies, may remove some of the
problems seen in prior multi-set stdies.

Much of the sequential partitioning research 
discussed in provost is either based on rule learners
or decision tree classifiers. To our surprise,
with few exceptions,
we cannot find in the literature any discussion of incremental
Bayesian classifiers. Incremental decision tree learning
is widely discussed but not incremental Bayes.
Exception: 


pazzini's~\cite{pazzani97learning}
data set very small (50 examples, max) compared a
standard naive bayes classier to several
other methods and naive bayes was not demonstrably inferior.
that performance was improved when a user profile of interesting
terms was incrementally modified.



 
Provost et.al. discuss some of the
issues associated with selecting a good
subset size and we highlight
one of their comments: the best
policy may be dependent on the data set.
Therefore, we finding a good
size $w$ it is important so study more
than the learning algorithm. Rather,
it may be necessary to study the behavior
of the learner on the current data set.

\section{Levering Bayes}


Adaptive systems can adjust their own internal logic at runtime.
Such systems have the benefit that the software can
fix itself.  For example, a planning system might
find a new method to generate better plans in less time.  The problem with
adaptive systems is that the adaption might render obsolete any
pre-adaption certification.

We therefore seek a method for monitoring an adaptive system
to determine when a learner is no longer trustworthy. In the general case, this is
a complex problem.
This is a well-studied problem with
many sophisticated solutions. For example, Cukic and XXX used support vector machines to
identify {\em mode changes} in the environment of a jet fighter being controlled by a neural
net. Such mode changes arise in many situations Many time series data sets experience {\em mode changes}.
For example, a plane in stable flight might start ascending at which point the distributions
of the attributes also change. After such a mode change, old theories may need
to be discarded and new theories learned. 


determine a n-dimensional boundary around the space of instances seen so far~\cite{xxx}. If new
instances arrive that are outside that boundary, then the learner can offer a caution that
any conclusions it makes may not be relevant to the current problem.

In one particular case, a much simpler method can suffice.  
determining when a learner has moved {\em out of bounds} and
can no longer be trusted. One situation where this 


Mode changes are a concern when using data miners for safety critical systems. If a learner
is certified, then the underlying domain distributions change, then that certification may be

In domains where the frequency of mode changes is high, many sophisticated temporal
learning schemes have been devised and successfully applied. 
When the frequency of model changes is low, a very simple incremental scheme called
SAWTOOH can suffice.

The key to SAWTOOH is that the learner's performance can see enough instances
to reach peak performance {\em before} the next mode change. In many data sets,
such peak performances can be reached by many learners after learning from
just a few hundred (or less)
instances.  

befoIn a surpising number cases, many learners 
exhibit an {\em early plateau} in their performance. That is,
when learninf from $10\%,20\%,30\%...100\%$ of the availabe data,
peak performance is often achieved after seeing just a small percentage
of the available data. Assuming early plateaus, a very simple batch-learning
scheme called SAWTOOTH can scale to very large data sets. 

SAWTOOTH processes incoming data in chunks of $I$ instances, called
{\em eras}.  The data in each era is passed to a learner.  If the
performance of the learner has not changed after e.g.  $E$ eras, the
learning is said to have {\em plateaued}.  Learning is then disabled
so the theory learnt up till the plateau is now {\em stable}.  New
eras are then processed using the stable theory.  Meanwhile, SAWTOOTH
maintains a cache of the all the instances seen in the last $Past$
number of eras.  Learning is reactived if the performance seen in one
era is significantly different to the prior era. On reactivation, a
new theory is learned from the cache and the algorithm continues.

The resulting behaviour looks like a sawtooth curve. Learning performance rises
sharply during the first few eras, plateaus, then can drop
sharply. One reason for such a drop is a {\em mode change}  in the source of the instances.

epstopdf plateaumsm5.pdf
epstopdf plateaumslsr.pdf
epstopdf plateauktnbk.pdf
epstopdf plateauktj48.pdf


If the goal of learning is to generate models that
have some useful future validity, then the learned theory should be
tested on data not used to build it\footnote{ Failing to do so can
result in a excessive over-estimate of the learned model- for example,
Srinivasan and Fisher report an 0.82 correlation between the
predictions generated by their learned decision tree and the actual
software development effort seen in their training
set~\cite{srinivasan95}. However, when that data was applied to data
from another project, that correlation fell to under 0.25. The
conclusion from their work is that a learned model that works fine in
one domain may not apply to another.}.
One standard meta-assessment method a N-way cross validation study where, the
data is sorted into a random order M times. For each order, the data
is divided into N buckets and the theory learned on N-1 buckets is
tested on the remaining bucket.  This procedure allows a prediction on
how well the learner will perform on new data.

\begin{figure}
{\footnotesize
M times the data ordering is randomized
and then:
\bi
\item The first L examples are 
divided into
N buckets. The class distribution within the N buckets
is selected to be similar to the class distribution in the original
data set.
\item
$\frac{X}{N}*L$ of
the data for $X\in\{1,2,\ldots N-1\}$ is used for training
a\item
The remaining
$\frac{N-X}{N}*L$ of the data is used for testing.
\ei
The 
sequence stops at $N-1$ since training
on $\frac{N}{N}$ of the data would leave nothing for the test
suite ($1-\frac{N}{N}=0$).
}
\caption{An LMNX study.}\label{fig:lmno}
\end{figure}


{\bf LMNX STUDIES:}
In a commercial setting, accessing
data is difficult. 
Data miners need to know
how {\em little} data they need to achieve good results. 
Hence, we modify
the M*N procedure
to explore how the learner's performance changes as 
{\em less
and less  data} is available.

\fig{lmno} defines an L*M*N*X study.
In summary, the procedure picks up to L items from a data set
(selected at random), divides those items into N buckets, then records
the performance of a learner as an increasing number of the buckets is
used for training.  This process is repeated M-times.  The ``L'' in
the LMNX study is very important since this it the upper
\underline{l}imit on the number of examples processed M*N*X
times. Such upper limits are required when processing very large data
sets (e.g. the JM1 data set in \fig{datasets} which has 10885
examples).


\fig{summ} shows the results from a LMNX study where 
{\em $<$L=150,M=N=10,X=1\ldots 9$>$} on the IRIS data set from the UCI
repository~\cite{Blake+Merz:1998}. The plot on the left shows the mean
classifier accuracy improving as more and more of the data is used to
train two classifiers from the WEKA toolkit~\cite{witten99} (J48 and a
N\aive Bayes classifier with kernel estimation).

The error bars in \fig{summ} show ${\pm}1$ standard deviations for the
accuracies seen in the $M$ repeats.  Those standard deviation values
can be used in t-tests to generate the right-hand-side {\em LMNX
summary plot} of \fig{summ}.  In a LMNX summary plot, the display of
the mean accuracy of a classifier only changes if it is statistically
difference (at the 95\% level) to the last seen change (otherwise the
displayed mean value is the same as the value seen at the last
change).  The summary plot shows that there was little significant
improvement in classification accuracy of N\aive Bayes or J4.8 after
using 20\% of the data. Further, there was no significant improvement
in either method after using 60\% of the data.


\begin{figure}
\begin{center}
\includegraphics[width=1.7in]{graphs/iris_ALL_accuracy.png}
\includegraphics[width=1.7in]{graphs/iris_ALL_accuracy_changes.png}
\end{center}
\caption{Learning curves (left); summarized (right).}\label{fig:summ}
\end{figure}



\begin{figure}[!t]
\centerline{
\subfigure[Data sets]{\begin{scriptsize}
\begin{tabular}{l|lrrrr}
\multicolumn{3}{c}{}&\multicolumn{2}{c}{\# attributes}&\\\cline{4-5}
 id & data set & \# instances & discrete & numeric& \# classes\\\hline
 A &heart-c   &    303& 7&   6& 5    \\ 
 B &zoo        &   101& 16&  1 & 7    \\
 C &vote       &   435& 16 & 0& 2     \\
 D &heart-statlog &270& 0 &  13& 2    \\
 E &lymph        & 148& 15& 3&   4    \\
 F &autos        & 205& 10&  15& 7    \\
 G &ionosphere   & 351& 0 & 34& 2     \\
 H &diabetes     & 768& 0 &  8& 2     \\
 I &balance-scale& 625& 0 &  4& 3     \\
 J &soybean      & 683& 35&  0& 19    \\\hline
 K &bodyfat      & 252& 0& 14& numeric  \\   
 L &cloud        & 108& 2& 4 & numeric    \\ 
 M &fishcatch    & 158& 2& 5 & numeric     \\
 N &sensory      & 576& 11& 0& numeric     \\
 O &pwLinear     & 200& 0& 10& numeric     \\
 P &cleveland    & 303& 7 & 6& numeric     \\
 Q &strike       & 625& 1 & 5& numeric     \\
 R &pbc          & 418& 8& 10& numeric     \\
 S &autoMpg      & 398& 3&  6& numeric     \\
 T &housing      & 506& 1& 12& numeric     \\
\end{tabular}
\end{scriptsize}
}}
\label{fig_datasets}
\centerline{
\subfigure[Bayes (+kernel estimation)]{\includegraphics[width=1.6in]{plateauktnbk.pdf}
\label{fig_first_case}}
\hfil
\subfigure[M5: model tress]{\includegraphics[width=1.6in]{plateaumsm5.pdf}
\label{fig_second_case}}}
\centerline{
\subfigure[J48 (decision trees)]{\includegraphics[width=1.6in]{plateauktj48.pdf}
\label{fig_first_case}}
\hfil
\subfigure[LSR: linear regression]{\includegraphics[width=1.6in]{plateaumslsr.pdf}
\label{fig_second_case}}}
\caption{Simulation results}
\label{fig:sim}
\end{figure}

On top of a LMNX summary plot is a comparison of the performance of
the two learners at each $X$ value.  One learner {\em wins} over the
other if it is {\em both} statistically different (using a t-test at
the 95\% level) {\em and} the mean performance of one learner is
larger than the the other.  In the case of this study with the IRIS
data set, N\aive Bayes won over J48 four times; and J48 never won; and
both learners tied four times.


% An example of a floating table. Note that, for IEEE style tables, the 
% \caption command should come BEFORE the table. Table text will default to
% \footnotesize as IEEE normally uses this smaller font for tables.
% The \label must come after \caption as always.
%
%\begin{table}
%% increase table row spacing, adjust to taste
%\renewcommand{\arraystretch}{1.3}
%\caption{An Example of a Table}
%\label{table_example}
%\centering
%% The array package and the MDW tools package offers better commands
%% for making tables than plain LaTeX2e's tabular which is used here.
%\begin{tabular}{|c||c|}
%\hline
%One & Two\\
%\hline
%Three & Four\\
%\hline
%\end{tabular}
%\end{table}

\begin{figure}
\centerline{\subfigure[Large data sets from UCI]{
\begin{scriptsize}
\begin{tabular}{l|lrrrr}
\multicolumn{3}{c}{}
& \multicolumn{2}{c}{\# attributes}\\\cline{4-5}
id& data set&Atts&Num&Disc&\# classes\\\hline
U& letter& 20000 & 16& 0& 26\\
V& waveform-5000& 5000 & 40& 0& 3\\
W& hypothyroid& 3772 & 7 &22& 4\\
X& segment& 2310 & 19& 0& 7\\
Y& kr-vs-kp& 3196 & 0& 36& 2\\
Z& anneal& 898& 38 & 32& 5\\
AA& vehicle& 846&  18& 0& 4\\
\end{tabular}
\end{scriptsize}}}
\centerline{\subfigure[SAWTOOTH, 10*10-way cross validation
results.]{\includegraphics[width=3.2in]{bigguns.jpg}}}
\centerline{
\subfigure[Win/loss tables]{
\begin{scriptsize}
\begin{tabular}{l|rrr}
Algorithm& wins-loses&wins &loses\\\hline
J4.8& 18& 21& 3\\
ST& 0& 9& 9\\
NBK& -3& 7& 10\\
NBC& -15& 2& 17
\end{tabular}\end{scriptsize}}
}
\caption{SAWTOOTH and large data sets.}\label{fig:large}
\end{figure}


\begin{figure}
\begin{center}
\includegraphics[width=3.2in]{s1.pdf}
\end{center}
\caption{SAWTOOTH learning in a low frequency domain.
Each black dot shows the accuracy seen after processing a new era.
Mode changes occured at x-axis points labelled ``1'', ``2'', ``3'', ``4'', ``5''.
A nominal mode changed to one of five different error modes, for the duration
of two eras. 
}\label{fig:simulator}
\end{figure}



letter: 51 bins
max num of bins: XXX

kdd cup results.


Our goal is a data miner
that satisfies a data mining
desiderata adapated from several 
sources~\cite{bradley98scaling,hulten03,widmer96learning}
\bi
\item[D1]
\label{dfast}
{\em FAST}: requires small
constant time per record, lest the learner
falls behind newly arriving data;
\item[D2]
\label{dsmall}
{\em SMALL}: uses a fixed amount of main memory,
irrespective of the total
number of records it has seen;
\item[D3]
\label{d1pass}
{\em ONE SCAN}: 
require one scan of the data and early
termination of that one scan (if appropriate) is highly desirable;
\item[D4]
\label{donline}
{\em ON-LINE}:
on-line suspendable,
resumable inference that offers, at anytime
  a current ``best'' answer plus status information about progress
(e.g. expected remaining
time);
\item[D5]
\label{dincremental}
{\em CAN FORGET}:
old theories should be discarded or updated
 if the 
data-generating phenomenon changes; i.e. when concept
drift is present;
\item[D6]
\label{dremembers}
{\em CAN RECALL}: if the learner should
adapt faster whenever it arrives again at a previously visited
context.
\item[D7]
\label{dcompentent}
{\em COMPETENT:}
produces a  theory that is (nearly) equivalent 
 to one obtained  without the above
constraints.
\ei

XXX widmer and kubat hd to addat their FLORA2 system to FLORA3 to
handle recurring contexts. We do it with no modification.

\section{future work}

future work. more data.

====

Widmer and Kubat
distinguish between
concept drift and 
increased noise.
In the former, the learner
should incorporate
the new information
while in the latter,
the learner should ignore
the data. To date, we have
not tested SAWTOOTH for
noise.

XXX andreas. \& missing data in sawtoodh

\section{Inside SAWTOOTH}

Internally, SAWTOOTH has three compents: a N\aive Bayes {\em classifer}
that processes one era's worth of data; a {\em monitor} that controls
the classifier and maintains a cache of prior examples; and a one-pass
incremental discretizer called SPADE~\cite{orrego04}.

When dealing with very long streams of data, itSAWTOOTH uses  a N\aive Bayes classifier.
Such classifiers read instances one at a time, then update summary
tables with how often different attribute ranges appear in different classes.
These learners can be quite memory effecient
(only need memory for some {\em
summary tables} plus a
buffer just large enough to hold a single instance. 

XXX bayesian. fast incremental adaptation

batch learning within an era or when loading in the cache.
monitor: summary statistics on the batch at the end of earch er

Large databaes often exhibit concept
drift. Over the months of years of their
existing, data collection process can change
as can the phenomenum being studied.
(e.g. a retail organization could focus
less on face-to-face sales than on web-based
marketing). 

We face the concept drift problem in our target domain: heuristic
search for violations to temporal properties.  In our approach,
properties are converted into a Buchi automoma and some piece of code
is exercised. The automan is like a road map showing how to reach
violations. As a device is executed via a Monte Carlo simulation,
output from the device change trigger transistions in the automona.
Our learner seeks to learn changes to the distributions of input
variables that favors a greater percent coverage of the automna (such
choices increase the odds of finding some violation). Consider a
repeated cycle of some simulation followed by some learning followed
by changes to the input distributions.  As input variable changes,
concept drift would occur if the Monte Carlo simulations may execute
different parts of the device.

Traditional learners have previously been applied to the concept drift
problem. Catlett reports a {\em peep hole} method
where only a subset of the new arrived
examples are used to update a decision tree.

SPRINT: paralled clssifiers.

after 
tradingsize for accuracy is probelmatics. ideally,
seek soultuions that perofmr as well or better
on large
data sets than batch processing.
What is the growth rate of the algorithm;s run
time as the number of examples increase. irrelevant
due to forgetting.


baseline system.



Gama~\cite{gama00}: frequncy counts in summary adjusted according to how successful
was the last round of learning. Hill
climbing search for parameter
esitmation. but we have seen before dicussions of using naive bayes,
withoug modification, on data sets.

Most of what we can find was in text mining or user modeling.
priors updated. chai updates priors via feedback
from the examples seen to date. 
No reference to the concept drift problem~\cite{chai02bayesian}

further work: the gama adaptive methods could improve SAWTOOTH.

must read: domingos1996b
also, kearns 1993: checking hypothesis against
all the data is not necessary. keeps statistics.



Our results may be too small-
further increases deeper.
Provost et,al comment  
Catlett and Harris-Jones and Haines 
note that learning does improve as many more
examples are added, but the rate of improvement
decreceases dramatically (e.g. 
in Catlett's study  the difference
in error rate in theories learned from
2000 or 5000 randomly
selected examples were usually most often
within 1\%)

linear relationnship c4.5 tree size 
and number of examples.
catlett991

previsou reslut seen 
with c4.5 and five differet
prinring methods

cohen
incremental cross-valdtion
repeat M times:
randomized order of data
divide data into $N$ disjoint sets
for i=1 to N-1
 train on sets 1..i;
 score[M,i]=test on sets i+1..N

Their study took longer than
ours to reach a plateau point. 
Note that their values come from a study of C4.5, not N\aive Bayes
and it possible that  that Bayes classifiers reach peak performance earlier
than C4.5. One concern with this hypothesis is that N\aive Bayes
may be reaching its plateau {\em earlier} since it is reaching a
{\em lower} plateau. Hence, in the subsequent experiments, we take
care to compare Naive Bayes with C4.5. 

A second explanation for the difference between our results and
those of Oates and Jensen is that we use t-tests to compare
performance scores seen in theories learned from $M$ or $N$ examples.
Oates and Jensen, other the hand, scan the accuracies
learned from $M,N,O,etc$ examples ($M<N<O$) looking for three
consecutive scores that are within 1\% of the score
gained from a theory using all the availabe data. That is,
we measure different things. Oates and Jensen assess when
a theory starts {\em decreasing} from the maximum value while
we assess when a theory stops {\em increasing} from past
values. Also, our t-tests
takes into account means {\em and} standard deviations.

our method takes into account the means and standard deviation

is with 1
decide
if the classification accuracy after seeing N examples is significantly
different to the last significant chage seen in theories learned
from tatistically
different to the last sign

\{10\%,
20\%,
20\%,
20\%,
25\%,
30\%,
40\%,
40\%,
45\%,
45\%,
50\%,
50\%,
75\%,
85\%,
85\%,
85\%,
100\%,
100\%,
100\%\}

we compute W dynmaiclayy: w=n*eras. also, we freeze learning. most of
the time, our learners are deactivated.


differences: 
These experiments have all been in a Bayesian
framework. An alernative method
might be to repalce the Bayes classifier
within SAWTOOTH with a decision tree learner.  We have not done
this for this study since Bayes classifiers are very easy
to incrementally update (just add the attribute ranges seen in the
latest example to the frequency counts in the summary tables). If
we were to move to decision trees, we might (XXX incremetanl dt.

use a decision tree learner whtCVFDFT: incremental decision tree work.

Concept drift implies that what has le
make the same assumptions
as widmern and kubat~\cite{widmer96learning}:
rate of context  change is rather low (ie.. that therea re phases of stability between periods of change), but on the other hand weill allow coencpt
changes of alarge exit (i.e.
successive versions of the target cocnept may be very
different). Under those two assumptions, there exists a class of
data for which learning from very long streams can be achieved
using very simple learners. That class of data are those
that exhibit {\em  early platueas}; i.e. learners achieve peak
performance after seeing just a few hundred (or less)
training examples. We have some evidence that that class if very common.
All of the UCI Irvine data sets
we have studied belong to  that class as does data 
we have collected from flight simulator experiments. 

windowing:

Therefore,
we have some confidence that our approach is widely applicable.
Further, our toolkit comes with a test for from 

Formally, these
summary tables are $P(H\given E_i)$; i.e. the probability of the evidence $E_i$
(attribute range $i$) given some hypothesis $H$ (the class).
N\aive Bayes
classifiers tune past knowledge to this evidence using Bayes' Theorem:
\[
P(H\given E)=\frac{P(H)}{P(E)}\prod_iP(E_i\given H)
\]
Given fragments of evidence $E_i$ and a prior probability for
a class $P(H)$, a posterior probability $P(H\given E)$ is calculated
for the hypothesis given the evidence. The Bayes classifier returns
the class with highest probability.  Many studies
(e.g.~\cite{hall03,dou95}) have reported that, in many domains, this
simple Bayes classification scheme exhibits excellent performance
compared to other learners.  This is a surprising result.
Such classifiers are
called {\em {n\aive}}~\cite{witten99}, since they assume that
the frequencies of different attributes are independent.  In
practice~\cite{webb00a}, the absolute values of the classification
probabilities computed by Bayes classifiers are often inaccurate.
However, the relative ranking of classification probabilities is
adequate for the purposes of classification.
 
Bayes classifiers can be extended to numeric attributes
using {\em kernel estimation} methods. 
The standard estimator assumes the central limit theorem and models each
numeric attribute using a single gaussian. 
Other methods don't assume a single
gaussian. John and Langley's gaussian  kernel
estimator models distributions of any shape as the sum of multiple gaussians.
Other, more
sophisticated methods are well-established~\cite{john95,FayIra93Multi},
but several studies report that even simple {\em discretization methods} suffice for
adapting Bayes classifiers to numeric
variables~\cite{dou95,YanWeb02Comparative}. 

Many discretization methods
are inappropriate for infinite long streams of instances. For example, 
Dougherty et.al.'s {\em straw man} discretization method~\cite{dou95} 
is {\em 10 bins} which divides attribute $a_i$ into bins of size $\frac{MAX(a_i)-MIN(a_i)}{10}$.
If MAX and MIN are calcuated incrementally along  a stream of data, then instance data
may have to be cached and re-discretized if the bin sizes change. 
An alternative is to calcuate MAX and MIN after seeing {\em all} the data.
Both cases require two passes through the data (with the second pass doing the actual
binning). Many  other discretization methods (e.g. all the methods
discussed by Dougherty et.al. and 
Yang and Webb~\cite{YanWeb02Comparative}) suffer from this two-pass problem.

Another advantage of  Bayes
classifiers is that they are
simpler to implement, and therefore easier to experiment with,
than  generators of decision trees or
classification rules; e.g.  the {\tt update} method
of \fig{class} is much simpler that the method used in FLORA.
Yet much of the scale up research focuses on rule or tree
generators~\cite{provost99survey}.  


SAWTOOTH is simpler than FLORA in several other respects.
FLORA's theories are {\em description items}; i.e.
negation free conjunctions of attibute
values that shrink (generalize) or grow (specialize) according
to feedback from newly arrive data. Several sets of descriptions are
maintained: the description items of the positive/negative examples;
and a seperate set of potential descriptors that match both positive
and negative examples. Literals are shuffled between these sets when
new examples arrive and the theory is updated or when the the window
is full and examples are forgotten.  

SAWTOOTH, on the other hand,
maintains a single theory: just the frequency counts of a single N\aive
Bayes classifier.  These counts update when new examples arrive and
our original plan was to {\em decrement} those counts
when the window was full and we discarded examples.
A programming mistake  disabled this feature.
Our results (see below) suggest that such decrements are not essential. 

Provost and Kolluri
distinguish three  main scale-up methods.
Firstly, there are {\em relational representation}
methods that reject the assumption that we should
learn  from a single memory-resident table. 
Secondly, there are {\em faster algorithms}
Such tables
can be built by joining and denormalizing other tables.
Denormalization echos that the same datum in multiple location
so the joined tables can be must larger than the original
tables. For example,  
joining and denormalizing
three tables of data expanded changed the storage
requirements from  100MB to 2.5GB files~\cite[p25]{provost99survey}.
Various relational representation learning methods exist such as hierarchical
structure learners; inductive logic programming; or methods
that take more advantage of the DBMS that gathers together the data
for the learner.

Returning to the single-table approach,
another class of scale-up methods are those
based on {\em faster algorithms}
that (e.g.)
exploits {\em parallelism};
or that  target some 
{\em restricted representations}
such as a decision tree of limited
depth;
or that {\em optimize search} by, say, combining 
greedy search for extensions to
the current theory with a fast pruning
strategy.

A third class of scale-up methods
perform  {\em data partitioning} methods to
learn  from (e.g.)  
some {\em subset of the attributes} such as those selected 
 via attribute
relevance studies;
or from {\em subsets of the instances}
selected via, say:
\bi
\item
Duplicate compaction or 
\item
Stratified sampling method where minority class(es) are selected with
greater frequency and most of the majority class if ignored.
\item
A {\em windowing} scheme where newly arrived examples are pushed into
the start of sliding window of size $W$ while the same number of older
examples are popped from the end. Windowing is used in many systems
including FLORA1$\ldots$FLORA4~\cite{widmer96learning} and our
SAWTOOTH system.
\ei

Large databaes often exhibit concept
drift. Over the months of years of their
existing, data collection process can change
as can the phenomenum being studied.
(e.g. a retail organization could focus
less on face-to-face sales than on web-based
marketing). 

We face the concept drift problem in our target domain: heuristic
search for violations to temporal properties.  In our approach,
properties are converted into a Buchi automoma and some piece of code
is exercised. The automan is like a road map showing how to reach
violations. As a device is executed via a Monte Carlo simulation,
output from the device change trigger transistions in the automona.
Our learner seeks to learn changes to the distributions of input
variables that favors a greater percent coverage of the automna (such
choices increase the odds of finding some violation). Consider a
repeated cycle of some simulation followed by some learning followed
by changes to the input distributions.  As input variable changes,
concept drift would occur if the Monte Carlo simulations may execute
different parts of the device.


\centerline{
\subfigure[Data sets]{\begin{scriptsize}
\begin{tabular}{l|lrrrr}
\multicolumn{3}{c}{}&\multicolumn{2}{c}{\# attributes}&\\\cline{4-5}
 id & data set & \# instances & discrete & numeric& \# classes\\\hline
 A &heart-c   &    303& 7&   6& 5    \\ 
 B &zoo        &   101& 16&  1 & 7    \\
 C &vote       &   435& 16 & 0& 2     \\
 D &heart-statlog &270& 0 &  13& 2    \\
 E &lymph        & 148& 15& 3&   4    \\
 F &autos        & 205& 10&  15& 7    \\
 G &ionosphere   & 351& 0 & 34& 2     \\
 H &diabetes     & 768& 0 &  8& 2     \\
 I &balance-scale& 625& 0 &  4& 3     \\
 J &soybean      & 683& 35&  0& 19    \\\hline
 K &bodyfat      & 252& 0& 14& numeric  \\   
 L &cloud        & 108& 2& 4 & numeric    \\ 
 M &fishcatch    & 158& 2& 5 & numeric     \\
 N &sensory      & 576& 11& 0& numeric     \\
 O &pwLinear     & 200& 0& 10& numeric     \\
 P &cleveland    & 303& 7 & 6& numeric     \\
 Q &strike       & 625& 1 & 5& numeric     \\
 R &pbc          & 418& 8& 10& numeric     \\
 S &autoMpg      & 398& 3&  6& numeric     \\
 T &housing      & 506& 1& 12& numeric     \\
\end{tabular}
\end{scriptsize}
}}
\label{fig_datasets}