New Unsupervised Learning Functions

Amir Azadi, Wolfram Research

Join the Conversation #WolframTechConf

Overview

New unsupervised learning functions in V12: AnomalyDetection, FindAnomalies, DeleteAnomalies and SynthesizeMissingValues

Purely unsupervised approach to detect anomalies and fill in missing parts of the data by learning the underlying probability density of the input.

Practical guide for how to use these functions will be discussed.

I. FindAnomalies & AnomalyDetection

{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,} -> {,}

II. SynthesizeMissingValues

{,,,,,,} -> {,,,,,,}

Introduction

FindAnomalies & AnomalyDetection

Goal:

Given a list of examples, {ex1, ex2, ...}, find the examples that are anomalous.

Numerical data:

{1,2,3,4, 5,6,100}

Nominal data:

{{"A", "Alice"},{"A", "Alice"},{"B","Bob"},{"B","Bob"},{"A","Bob"}}

Images:

{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,} -> {,}

Applications in fraud detection, monitoring servers for suspicious activities/attacks, data cleaning.....

Anomalous example = example different from others.

Also called outliers.

In WL V.12, we introduce:

AnomalyDetection

AnomalyDetectorFunction

FindAnomalies

DeleteAnomalies

Examples

Find anomalous examples in data:

Using FindAnomalies directly:

FindAnomalies[{1,2,3,4, 5,6,100}]

Using FindAnomalies with different properties:

FindAnomalies[{1,2,3,4, 5,6,100},"AnomalyPositions"]

FindAnomalies[{1,2,3,4, 5,6,100},"AnomalyCount"]

FindAnomalies in the list of colors:

FindAnomalies[{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,}]

Eliminating anomalous examples:

DeleteAnomalies[{1,2,3,4, 5,6,100}]

Training an AnomalyDetectorFunction[...] using AnomalyDetection[...]:

AnomalyDetection[...] -> AnomalyDetectorFunction[...]

Using AnomalyDetection on a 2D numerical vector:

ad=AnomalyDetection[RandomReal[1, {20, 2}]]

Use the trained AnomalyDetectorFunction to find anomalies in new examples:

ad[{{5, 0.6}, {0.3, 0.5}, {0.1,0.2}}]

Use FindAnomalies with the trained AnomalyDetectorFunction to find anomalies in new examples:

FindAnomalies[ad, {{5, 0.6}, {0.3, 0.5}, {0.1,0.2}}]

Note: we are not dealing with finding anomalies in a give example (e.g. find anomalies in a time series, or in a image).

Will be in future versions....

What is an anomalous example?

Wikipedia: “Rare items which raise suspicions by differing significantly from the majority of the data”.

“Example being different from the others”.

If anomalies are frequent and not too diverse, we can have a supervised learning approach:

Classify[{(Subscript[example, 1])->False,(Subscript[example, 2])->True,…}]

Here we are focusing on problems where:

Anomalies are rare

Anomalies are diverse (broad range of possible anomalies)

In this setting, supervised approaches will fail (little data, and large space)

We can formalize this type of problems using probabilistic models

We can only model the non-anomalous data and figure out how “extreme” an example is

Pure Unsupervised function

Our formalization

Let’s assume we know the distribution of non-anomalous data

Anomalies are examples that are considered “out-of-distribution”

“Out-of-distribution” example is defined by the probability to generate samples with a lower pdf than the example, for a given distribution.

We call this RarerProbability

rarerProbability[dist_, x_]:=NProbability[PDF[dist,y]<PDF[dist,x],Distributed[y,dist]]

rarerProbability[NormalDistribution[0,1], 4]

**This number is telling what is the total probability to generate samples with pdf lower than pdf of “4”

Can be seen as an extension of two-tailed P-Value for multivariate non-normal distribution

We introduce RarerProbability in V.12

N@RarerProbability[NormalDistribution[0,1], 4]

Examples are considered anomalous when their RarerProbability is below a given AcceptanceThreshold.

RarerProbability is not the anomaly probability!

We can ask for the “RarerProbability” using AnomalyDetector Function

AnomalyDetectorFunction[...][{ex,...}, "RarerProbability"]

ad=AnomalyDetection[RandomReal[1, {20, 2}]]

ad[{{5, 0.6}, {0.3, 0.5}, {0.1,0.2}},"RarerProbability"]

ad[{{5, 0.6}, {0.3, 0.5}, {0.1,0.2}}]

AcceptanceThreshold option

RarerProbability threshold to consider an example anomalous

The default values is 0.001, (one in thousand examples)

Example:

Create a random 3D vectors with anomalies:

ndata=RandomReal[1, {1000, 3}];
adata=RandomReal[{-2,-.5}, {5, 3}];
data = Join[ndata, adata];

ListPointPlot3D[{ndata, adata}, ]

Find anomalous examples with the default  AcceptanceThreshold:

ListPointPlot3D[{ndata, FindAnomalies[data]},]

Change the anomaly detection false-positive rate by specifying the AcceptanceThreshold:

ListPointPlot3D[{ndata, FindAnomalies[data, AcceptanceThreshold -> 0.2 ]}, ]

if data comes from the same distribution as the training for the detector, AcceptanceThreshold corresponds to the anomaly detection false-positive rate.

How to compute the distribution?

The distribution is modelled using LearnDistribution

Ideal case: If training data is non-anomalous data

If training data contains anomalies, chicken and egg problem:

we need distribution to find anomalies

but we need non-anomalous data to model distribution...

Method 1: cross validation

We train on some examples and evaluate on other examples to isolate anomalies

Once we have removed anomalies, we train a distribution on the non-anomalous data

If there are no anomaly (near) duplicates, this works great

Method 2: clustering approach

Start with a seed of examples with largest probabilities, then grow the seed by adding more non-anomalous examples and retrain the distribution.

Heuristic-type approach such as Computationally-efficient Outlier Nominators (BACON): fragile once the growth process stops early

Robust to anomaly (near) duplicates

For V12, we only use Method 1

Future:

More methods will be added (BACON, Isolation Forest,...)

It will work with anomalous elements in an example like rare events in time series, texts and images....

It will work with texts, audio

Built-in pre-trained AnomalyDetectorFunction will be available

Using FindAnomalies and AnomalyDetection

FindAnomalies properties

In FindAnomalies[…,props], possible properties include:

“Anomalies”: examples that are considered anomalous

“AnomalyCount”:  number of examples that are considered anomalous

“AnomalyBooleanList”: Boolean values indicating whether examples are anomalous

“AnomalyPositions”: list of anomaly positions

“NonAnomalies”: examples that are considered non-anomalous

“RarerProbabilities”: probability to generate a sample with lower PDF

ad=AnomalyDetection[RandomReal[1, {20, 2}]]

FindAnomalies[ad, {{0.8,0.7},{5, 0.6}, {0.3, 0.5}, {0.1,0.2}, {1, 7}}, {"Anomalies","AnomalyPositions", "NonAnomalies", "AnomalyBooleanList", "RarerProbabilities"}]

Application: Anomalies in images

Finding “out-of-distribution” images

train=RandomSample[ResourceData["MNIST", "TrainingData"][[All, 1]], 30000];
test=RandomSample[ResourceData["MNIST", "TestData"][[All, 1]], 40];

RandomSample[train, 10]

Add anomalous examples to the test set:

antest=Join[{,}, test]

Train an anomaly detector on the training set:

You can specify the method for learning the distribution (same as LearnDistribution methods)

admnist=AnomalyDetection[train, Method -> "Multinormal", PerformanceGoal->"Speed"]

Find anomalous examples in the test set:

FindAnomalies[admnist, antest, AcceptanceThreshold->0.0001]

Obtain information about the trained AnomalyDetectorFunction:

Information[admnist]

SynthesizeMissingValues

Goal:

Fill in missing values in each example by generated values.

By default, Missing[…] and Indeterminate values are considered missing.

SynthesizeMissingValues[{{1,1.2},{Missing[],2},{Indeterminate,4},{4,1},{2,6}}]

Our formalism

Train a distribution on examples

Condition the distribution on known variable:

{Missing[],2}

P(x) = P (x | y = 2)

Sample from the conditioned distribution.

It can be a random sample or the mode of the conditioned distribution

It can be used directly on the data with missing values:

SynthesizeMissingValues[{{1,1.2},{Missing[],2},{Indeterminate,4},{4,1},{2,6}}]

Or it can be given a trained distribution:

Train a distribution on a two-dimensional dataset:

ld=LearnDistribution[{{1.1,1.4},{2.3,3.1},{4.4,5.4},{8.7,7.5}}]

SynthesizeMissingValues[ld,{4.2,Missing[]}]

Synthesizing values from the distribution

dn1=MultinormalDistribution[{2,1},{{2,1/3},{1/3,2/3}}];
dn2=MultinormalDistribution[{-3,-2},{{2,-1/3},{-1/3,2/3}}];
dataN=RandomVariate[MixtureDistribution[{1,1},{dn1,dn2}],700];
ld=LearnDistribution[dataN, Method-> "KernelDensityEstimation"];
cp=ContourPlot[PDF[ld, {x,y}], {x, -7,6}, {y, -5,4}, Contours->7];
pts=ListPlot[dataN,  PlotStyle->Directive[Opacity[0.5], PointSize[0.01], Red]];
Show[cp,pts]

Random samples from the distribution as candidates for the missing value:

synthpts1=ListPlot[Table[SynthesizeMissingValues[ld,{-4, Missing[]}], 20], ];
Show[cp,pts, synthpts1]

Specifying the “ModeFinding” Method to obtain the missing value candidates with largest probability:

synthpts4=ListPlot[Table[SynthesizeMissingValues[ld,{-4, Missing[]}, Method -> "ModeFinding"], 10], ];

Show[cp,pts, synthpts1,synthpts4]

Methods

“LearningMethod” sets the method for learning the probability distribution

“EvaluationStrategy” how to synthesize from the distribution

It can be a random sample (“RandomSampling”) or the mode of the conditioned distribution (“ModeFinding”)

SynthesizeMissingValues[{{1,2.2},{2,3.2},{3,Missing[]},{5, 6.2},{6, 7}},Method -> <|"LearningMethod"-> "Multinormal", "EvaluationStrategy" -> "ModeFinding"|>]

SynthesizeMissingValues[ld,{-4, Missing[]}]

Specifying missing values

By default, Missing[…] and Indeterminate values are considered missing.

SynthesizeMissingValues[{{1,1.2},{Missing[],2},{Indeterminate,4},{4,1},{2,6}}]

MissingValuePattern option can be used to specify which elements are considered missing.

SynthesizeMissingValues[{{1,1.2},{Missing[],2},{3,4},{4,1},{2,6}},MissingValuePattern -> 4]

SynthesizeMissingValues[{{1.1,3},{2,4.2},{3,4},{4.4,5},{5,6}, {7,8.3}, {9,10}}, MissingValuePattern -> x_/;x<3]

Application

Fill in missing pixels of images

datamnist=RandomSample[ResourceData["MNIST", "TrainingData"][[All, 1]], 10000];

RandomSample[datamnist, 10]

ldmnist=LearnDistribution[ImageData/@datamnist, Method-> "Multinormal"]

synthdata=SynthesizeMissingValues[ldmnist,ImageData/@ {,},MissingValuePattern -> 0.5, Method -> "ModeFinding"];

Image[#]&/@synthdata

Future:

It will work with other data types such as texts, time series...

Built-in pre-trained Synthesizers will be available

The representation of missing values will be generalized for different data types (missing representation in images)