A Benchmark for Streaming Anomaly Detection
Okay, I used to work in <i>anomaly
detection</i>, right, for more important
server farms and networks, in particular
for real-time, <i>zero day</i> detection, that
is, detecting problems, <i>anomalies</i>, never
seen before.<p>The OP has 6 &quot;ideal characteristics of a
real-time anomaly detection algorithm&quot;.
My work seems to do relatively well on the
criteria.<p>A challenging criterion is the 6th one:<p>&quot;The algorithm should minimize false
positives and false negatives.&quot;<p>So, no false positives and no false
negatives would be a <i>perfect</i> detector,
and in practice they are rarely possible.<p>A more realistic formulation of the
criterion is that for a given rate of
false positives (false alarms) achieve the
lowest rate possible for false negatives
(missed detections of actual anomalies).<p>How to do this is in the now classic
Neyman-Pearson result.  Right, in some
cases the computations are a knapsack
problem where that problem is, IIRC, in
NP-complete.<p>Really, another important criterion is to
have the false alarm rate adjustable, that
is, can set the false alarm rate in
advance and get that rate exactly in
practice.<p>Yup, that&#x27;s possible.<p>Why?  Really, anomaly detection is nearly
necessarily some continuously
(continually) applied statistical
hypothesis tests where the <i>null
hypothesis</i> is that the system being
monitored, that is, the source of the
data, is <i>healthy</i> and the data <i>normal</i>
and not an anomaly or a symptom of a
problem.<p>So, we are into statistical hypothesis
testing, and that is the context of the
classic Neyman-Pearson result.<p>The literature on statistical hypothesis
testing goes back to at least the
Neyman-Pearson result before 1950; the
field is old with a lot known.<p>In that field, it is usual to be able to
set the rate of false alarms (<i>type I
error</i>) in advance and get that rate
exactly in practice.<p>For monitoring server farms and networks,
there are two additional criteria that are
just crucial -- right, in particular for
getting a low rate of missed detections
(false negatives, <i>type II errors</i>) for a
given rate of false positives:<p>(1) Distribution-free.<p>The easy way to be able to do the
calculations of an hypothesis test is to
assume that know the probability
distribution of the input data when the
null hypothesis holds.  There, sure, the
most common distribution assumed is the
Gaussian.<p>But there are also statistical hypothesis
tests that are <i>distribution-free</i> (also
<i>non-parametric</i>, e.g., not using the
<i>parameters</i> of the Gaussian distribution)
that is, that make no assumptions about
the probability distribution of the data
when the null hypothesis holds.<p>For monitoring server farms and networks,
too often should be using
distribution-free tests.<p>(2) Multi-dimensional<p>The data readily available from monitoring
server farms and networks is horrendously
large, like flowing oceans of data.<p>So, it&#x27;s easy to get data on each of
dozens of variables at rates from one
<i>point</i> each few seconds up to hundreds of
points a second.<p>Treating such <i>jointly</i> multi-dimensional
data one variable at a time must typically
throw away a huge fraction of the relevant
information.  So, the data should be
handled <i>jointly</i>.  So, need statistical
hypothesis tests that are
multi-dimensional, and those are not so
easy to find in the literature.<p>So, the work I did for detecting zero-day
problems in server farms and networks was
to create a large collection of
statistical hypothesis tests that are both
distribution-free and multi-dimensional.<p>E.g., if the data consists of a time
series of points on a checkerboard and
<i>normal</i> data is on the red squares, then
my work will detect, with known and
adjustable false alarm rate achieved
exactly in practice, points on black
squares.  In this case, treating the data
on each of two perpendicular edges (axes)
of the checkerboard separately yields
exactly nothing.  So, this example
illustrates the extra <i>power</i> of being
multi-dimensional.  Also the distribution
of the data when the null hypothesis holds
is just the red squares, that is, far from
anything common in statistics.<p>Moreover, can argue that there are some
good <i>qualitative</i> reasons to believe
that, really, a good detector for zero-day
problems in server farms and networks
should be able to <i>know</i> when it is in a
fractal such as the Mandelbrot set and when
not.  Yes my work does that.<p>But, I have to say, I did my work -- at
IBM&#x27;s Watson lab to improve on our
approaches via AI -- and published it
decades ago, and since then I&#x27;ve seen
essentially no interest at all in the
work.<p>For more, for years I jerked the chains of
a huge fraction of all the venture capital
firms in the US with essentially no
interest.<p>My conclusion is good work in anomaly
detection and a dime won&#x27;t cover a ten
cent cup of coffee.<p>But, if by now anyone really is
interested, then the remarks here should
help.