Part I

Here at HN I'm trying to be anonymous but
on anomaly detection make a contribution.

The basic idea of my research is for
positive integer k, use k-nearest
neighbors or, really, any of a wide
variety of such measures, metrics,
functions, windows however want to
regard them.

So, right, are on the way to some
approaches to multi-dimensional
probability density estimation.

The main contribution of my research is
the applied probability derivations to
show how to calculate, adjust, set, etc.
the false alarm rate. In practice, false
alarm rate unknown, out'a control, often
too high is a biggie problem -- e.g., can
cause staff just to ignore too many
alarms. E.g., see the movie Tora, Tora,
Tora about the 12/7/1941 attack on Pearl
Harbor where the US actually had just what
the heck it needed for early detection,
early enough to get fighter airplanes in
the air, maybe early enough to get the
ships out of the harbor, etc. -- radar on
top of a hill. And the radar operators
DID get the detection and DID report it,
but the chain of command assumed that the
detection was a false alarm. Big, huge,
gigantic bummer. The US came within the
thickness of an onion skin of getting the
US airplanes and ships out of harm's way,
shooting down much of the attacking
airplanes, and having the US carriers,
already at sea, attacking the attacking
carriers when all their airplanes were off
over Hawaii. The US could have sustained
little damage and sunk all six of the
attacking carriers.

Having a good anomaly detector and
ignoring it can be a bummer.

But if know what the false alarm rate is
and know that it's low, then maybe the
chain of command will take a detection
more seriously and, then, take the next
step -- diagnosis.

Sometimes the spook business, say, Soviets
in England, would watch the comings,
goings, lights on late, etc. at British
military HQs and try to detect anomalies
that would indicate war. Sure, for such
detection need both distribution-free and
multi-dimensional with good control over
false alarm rate and good evidence of a
relatively high detection rate. So, sure,
the US CIA should want my work. I wrote
them -- never heard back.

Once I did give a talk on my work at the
Institute for Defense Analysis (IDA),
think tank resource for the Joint Chiefs.
Some in the audience mentioned credit card
fraud detection. Okay. But there should
also be national security applications.

Once gave a talk on the work at the Johns
Hopkins University Applied Physics Lab
(JHU/APL) -- I might as well have talked
about a recipe for pancakes.

Once I gave a talk on the work at the
NASDAQ site in Trumbull, CT. I got a nice
tour, a nice lunch, and a nice tote bag.

I gave some talks on this work to my
management chain at IBM's Watson lab --
the suits were afraid I might have some
good work they didn't understand, couldn't
control, and couldn't throttle. They were
PISSED.

I presented my work to some IBM people
outside of Watson Research -- they liked
the work, but Watson Research was PISSED.

For the applied probability stuff in my
research, for a detection of an anomaly
can also report the lowest false alarm
rate at which the data would still be a
detection. Then right along can graph
these lowest rates and use them as a
heuristic about detection seriousness.
Net, getting a handle, knob to turn,
knowledge of, etc. false alarm rate is
important.

The applied probability stuff is based on
some cute symmetry in the calculations.
The symmetry, then, gives some measure
preserving transformations
(transformations that don't change the
probability distribution). So, end up
with a finite algebraic group of such
transformations. Then sum over the group
and, presto, bingo, get what need to know
false alarm rate.

To adjust the false alarm rate, adjust the
diameter, cut-off, whatever, of the k
nearest neighbors or other metric,
convolution window, etc. Of course all of
this is conditional probabilities
conditioned on the historical data used
where assume that the system being
monitored when the historical data was
collected was healthy. How to confirm
healthy? Let the data age and see if
there are any other, later symptoms of
problems from other means, e.g., angry
customer complaints, malware, attacks and
intrusions, etc.

So, have a case of, essentially, being
brief here, the conditional expectation
E[Y|X] where Y is the random variable of
detections and X is the historical data.
Then of course E[E[Y|X]] = E[Y] which says
that have set false alarm rate "exactly"
in the long-run or, if you will,
conditionally exactly in the short run.

A result is that the naive way to evaluate
false alarm rate from the historical data
does, for lots of data, converge to the
right answer. Proving that, however, was
a bit tricky.

Achieving the Neyman-Pearson best result
needs lots of data from both healthy and
sick systems, and in practice the second
is in short supply.

The Neyman-Pearson result is intuitive,
like investing in real estate: Buy plots
of real estate that give the best return
per dollar invested until have invested
all the available money.

Well, suppose the data observed is, for
the set of real numbers R and some
positive integer n, in R^n. Then
partition R^n into little patches. Then
in each little patch, assume that data in
that patch would raise an alarm, and,
then, from the data (need lots of data,
especially as n grows) get the ratio of
the detection rate over the false alarm
rate. Then false alarm rate is really
like the money you have to invest, and
detection rate is your return on that
investment. So, sure, you buy the
patches with the highest ratio until you
have spent, invested, all your false
alarm rate, money.

Can find proofs in terms of freshman
calculus. I wrote out a quite general
proof in terms of the Hahn decomposition
from the Radon-Nikodym theorem in measure
theory.

So, right, if have only finitely many
patches in R^n, then have essentially a
knapsack problem, IIRC, in NP-complete
(although likely not a concern in
practice).

Can write out a little derivation, mostly
just Fubini's theorem (the measure theory
version of the calculus interchange order
of integration) to show in a cute sense of
the distribution of sick systems being
translation invariant (right, a bit much
to assume -- but here I'm typing quickly
from memory of what I did 20+ years ago)
then my techniques give, for the assumed
false alarm rate, the highest detection
rate possible. So, this is a simple,
quick and dirty, data-free, crude approach
to the full Neyman-Pearson result of best
detection.