Review of Unsupervised Learning in the Wolfram Language

Amir Azadi, Wolfram Research

WTC 2019

Overview of Unsupervised Learning

Unsupervised Learning: Learning previously unknown patterns in the data without pre-existing labels which can be used for various tasks.

Tasks of Unsupervised Learning

I. Clustering

Looking for patterns in the data

->

II. DimensionReduction

Analyzing and visualizing high dimensional data

->

III. LearnDistribution

Finding the underlying statistical distribution of the data (density estimation)

->

IV. FindAnomalies

Finding outliers ("out-of-distrubution" examples)

V. SynthesizeMissingValues

Fill-in missing values

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

Clustering

Goal: Partitioning data into clusters of similar elements (based on a distance or dissimilarity function)

->

Clustering Functions in the Wolfram Language

FindClusters[data]
ClusterClassify[data]

Works on a variety of data types, including numerical, textual, and image, dates and times

Find clusters of nearby numerical values:

FindClusters[{1,2,10,12,3,1,13,25, 100, 150}]

FindClusters[{1,2,10,12,3,1,13,25, 100, 150},2]

c=ClusterClassify[{1,2,10,12,3,1,13,25, 100, 150}]

c[{1,2,10,12,3,1,13,25, 100, 150}]

Create a ClassifierFunction from a list of images and classify examples:

flowers={,,,,,,,,,,,,,,,,,,};

c=ClusterClassify[flowers,3]

Find the cluster assignments and gather the elements by their corresponding clusters:

c[flowers]

GatherBy[flowers,c]

Clustering Methods

The (RefLink[Method, paclet:ref/Method]) option can be used to specify the clustering algorithm: 
	"KMeans", "KMedoids", "DBSCAN", "JarvisPatrick", "MeanShift", "SpanningTree", "NeighborhoodContraction", "GaussianMixture", "Agglomerate", "Spectral"

FindClusters[{,,,,,,,,,,,,,,},Method->"Spectral"]

FindClusters[{,,,,,,,,,,,,,,},Method->"DBSCAN"]

The method’s performance depends on cluster shapes, sizes and densities and level of noise in the data.

Finding clusters in the complex data patterns is not a trivial and a not well defined.

No good universal metric to find clusters and compare the results of different methods:

All methods are documented so users can explore in details what method is suitable for their data.

Clustering Applications

Finding outliers using “DBSCAN” method

"DBSCAN" (density-based spatial clustering of applications with noise)

density is estimated using a neighbor-based approach.

"DBSCAN" defines clusters as connected high-density regions.

In ClusterClassify, noise points are labeled as (RefLink[Missing["Anomalies"], paclet:ref/CriterionFunction]). (V.12.1)

nccdata= {1000,1,2,3,1.1,2,9,8,7,6,4,1,.5,152,153, 150,145, -1000};
cc=ClusterClassify[nccdata, Method->"DBSCAN"]
cc[nccdata]

cc=ClusterClassify[nccdata, Method->{"DBSCAN", "DropAnomalousValues"-> True}]
cc[nccdata]

Dimensionality Reduction

Goal: Projects the data in the high-dimensional space to a space of fewer dimensions.

Dimensionality Reduction Functions in the Wolfram Language

DimensionReduction[data]
DimensionReduce[data]

Works for a variety of data types, including numerical, textual, and image, as well as dates and times.

Reduce the dimension of vectors:

vectors={{1,2,3},{2,3,5},{3,5,8},{4,5,8.5}};

DimensionReduce[vectors]

Specify that the target dimension should be 1:

DimensionReduce[vectors,1]

Generate a dimension reducer from a list of vectors:

dr=DimensionReduction[{{1,2,3},{2,3,5},{3,5,8},{4,5,8.5}}]

Use this reducer on a new vector:

dr[{6,7,14}]

Linear & Non-Linear Dimension Reduction

Methods

Based on the selected method the projection can be linear or Non-linear

DimensionReduce[{{1,2,3},{2,3,5},{3,5,8},{4,5,8.5}}, Method->"Linear"]

Linear Reduction

Linear Methods (Automatic): Principal component analysis, LowRankMatrixFactorization...

The projection of numerical vectors from FisherIris dataset using the Linear method:

iris=ExampleData[{"MachineLearning","FisherIris"}, "Data"];

RandomSample[iris,5]

Generate a reducer function using the linear method:

diris=DimensionReduction[iris[[All,1]], 2]

Group the examples by their species, reduce the dimension of the features and visualize the reduced dataset:

byspecies=GroupBy[iris,Last->First];
byspecies=diris/@byspecies;
ListPlot[Values[byspecies],]

Non-Linear Reduction

Non-Linear methods:

"Isomap" (Isometric mapping), preserves the geodesic distances between points.

"LLE" (locally linear embedding), a neighborhood-preserving projection on linear patches of the manifold

"TSNE", t-distributed Stochastic Neighbor Embedding

Examples of Non-Linear Embeddings

Data lies on an embedded non-linear manifold in the space. Like “Swiss roll” toy dataset:

SeedRandom[11]
data=Table[Insert[AngleVector[1+{2,8}*RandomReal[]],RandomReal[],2],1000];
ListPointPlot3D[data,]

Failure of linear methods:

reducedpts=DimensionReduce[data, Method->"Linear"];
ListPlot[Style[#,Hue[First[#]/2]] & /@ reducedpts, AspectRatio->1,PlotStyle->Directive[PointSize->Medium]]

Train a nonlinear dimension reducer using "LLE" on the dataset to map to two-dimensional space:

reducer=DimensionReduction[data,2,Method->"LLE"]

"LLE" (locally linear embedding), a neighborhood-preserving projection on linear patches of the manifold

Find the data coordinates in the reduced space:

reducedpts=reducer[data];
ListPlot[Style[#,Hue[First[#]/2]] & /@ reducedpts,]

Visualize the dataset in the original space, with each point colored according to its reduced variable:

ListPointPlot3D[Style[#,Hue[First[reducer[#]]/2]] & /@ data,]

Recover Head Poses by Non-Linear Mapping

Generate a dataset of different head poses from 3D geometry data with random viewpoints:

cc=RandomPoint[Circle[{0, 0}, 0.8, {Pi, 2Pi}], 50];
pp=Flatten[Table[{cc[[i,1]], cc[[i,2]], j},{i, 1, Length@cc}, {j, -0.8, 0.8, 0.2}], 1];
vp=RandomSample[pp, 60];
obj = ExampleData[{"Geometry3D", "Beethoven"}];
poses=Table[Show[obj, ViewPoint->vp[[i]]], {i, 1, Length@vp}];
imgs=Table[Rasterize[poses[[i]], ImageResolution->8, Background->None],{i, 1, Length@poses}];
RandomSample[imgs, 10]

"Isomap" (Isometric mapping), preserves the geodesic distances between points.

Visualize the original images in the reduced space, in which the up-down and front-side poses are disentangled:

red=DimensionReduce[imgs,2,Method->{"Isomap","NeighborsNumber"->10}];
Graphics[MapThread[Inset[#1,#2,{0,0},15,Background->None]&,{imgs,red}],ImageSize->200,ImagePadding->20,Frame->False,AspectRatio->1]

Examples of DimensionReduciton using NeuralNetworks

Reduce the dimension of images using the auto-encoder neural network method:

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

SeedRandom[11];
{trainmnist, testmnist}=TakeDrop[datamnist, 24700];
RandomSample[trainmnist, 10]

dr = DimensionReduction[trainmnist, 2, Method->"AutoEncoder"]

red=dr[testmnist];

Graphics[{MapThread[Inset[#1,#2,{0,0},1.5,Background->None]&,{testmnist,red}],ImageSize->1000,ImagePadding->5,AspectRatio->2/3}]

dr[[1]]

Find words representation in a lower dimensional space using Net models as feature extractor

animals={"Alligator","Ant","Bear","Bee","Bird","Camel","Cat","Cheetah","Chicken","Chimpanzee","Cow","Crocodile","Deer","Dog","Dolphin","Duck","Eagle","Elephant","Fish","Fly"};

fruits={"Apple","Apricot","Avocado","Banana","Blackberry","Blueberry","Cherry","Coconut","Cranberry","Grape","Turnip","Mango","Melon","Papaya","Peach","Pineapple","Raspberry","Strawberry","Ribes","Fig"};

words=Join[animals,fruits];
drw=DimensionReduce[words,FeatureExtractor->NetModel["GloVe 100-Dimensional Word Vectors Trained on Wikipedia and Gigaword 5 Data"]]

Graphics[{MapThread[Inset[#1,#2,{0,0},2.5,Background->None]&,{words,drw}],ImageSize->1000,ImagePadding->5}]

Learning the Data Distribution

Learning a probability distribution from data

A central application of unsupervised learning

Various types of data, including numerical, nominal and images.

Numeric variable

{1.3,2.7,1.5...}->

Numeric vectors

Nominal variable

{"A","A","B", ...} -> <|"A"->0.66, "B"->0.33|>

Numeric and nominal variables

(CopyTag)

Images

{,,,,...,,,,,}

LearnDistribution

Applications of LearnDistribution

Generating new examples: RandomVariate

Probability queries, compute the PDF of new examples: PDF[LearnedDistribution[...],{(Subscript[example, 1]),(Subscript[example, 2]),…}]

Find Anomalies: FindAnomalies

Fill-in missing values using conditioned distribution on known values : SynthesizeMissingValues

Predict any variable as function of others

Denoising / Error correction

LearnDistribution and Derivative Functions in the Wolfram Language

(RefLink[LearnDistribution, paclet:ref/LearnDistribution])[{(Subscript[example, 1]),(Subscript[example, 2]),…}]

Returns a (RefLink[LearnedDistribution, paclet:ref/LearnedDistribution])[…] attempts to represent an distribution for the the examples given

ldn=LearnDistribution[{1.2,2.5,3.2,4.6, 5,6,7}]

(RefLink[LearnDistribution, paclet:ref/LearnDistribution])[examples] yields a (RefLink[LearnedDistribution, paclet:ref/LearnedDistribution])[…], dist on which the following functions can be used:

(RefLink[PDF, paclet:ref/PDF])[dist,…] : probability or probability density for data

PDF[ldn,3.4]

(RefLink[RandomVariate, paclet:ref/RandomVariate])[dist]: random samples generated from the distribution

RandomVariate[ldn]

Automation and Method Selection

colors=RandomColor[20]
ldn=LearnDistribution[colors, Method->"Multinormal"]

ldn=LearnDistribution[RandomColor[3000]]

Methods: Multinormal, GaussianMixture, ContingencyTable, KernelDensityEstimation, DecisionTree, RealNVP(Reversible Networks)

Loss function: cross-entropy (log likelihood) on test sets

Procedure:

Start with a set of configurations

Train configurations on a small dataset (“experiments”)

Predict how well the configurations would perform on the full dataset

Give more data to promising configurations

Problems:

More brittle than supervised learning

repeated elements

mix of discrete and continuous values

...

Some models cannot compute PDF (GAN, energy based model, ...)

Learning Distribution of Numeric Data

Load Fisher’s Irises dataset and select "PetalLength" and "SepalWidth" attributes.

GIT[ML]

irisdata=ResourceData["Sample Data: Fisher's Irises"][[All, {"PetalLength", "SepalWidth"}]]

ptsplt=ListPlot[{irisdata},PlotStyle->Directive[Opacity[0.6`],PointSize[0.02`], Red],Frame->True,FrameLabel->{"PetalLength","SepalWidth"},AspectRatio->1, PlotRange->{{0,8},{1.5,5}}]

ld=LearnDistribution[irisdata]

RandomVariate[ld,5]

cplot=ContourPlot[PDF[ld,{x,y}*(Quantity[1, "cm", centimeter, "Centimeters"])],{x,0,8},{y,1.5,5},];
Show[{cplot, ptsplt}]

PDF[ld, {8,5}(Quantity[1, "cm", centimeter, "Centimeters"])]

Perhaps an outlier!

Anomalies & RarerProbability

What is an anomalous example?

“Example being different from the others”.

Here we are focusing on problems where:

Anomalies are rare

Anomalies are diverse (broad range of possible anomalies)

Assumption: the data distribution is known

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

“Out-of-distribution” example is defined by RarerProbability.

(RefLink[RarerProbability, paclet:ref/RarerProbability])[dist,example] computes the probability for the distribution  dist to generate samples with PDF lower than the example.

Formally, (RefLink[RarerProbability, paclet:ref/RarerProbability]) computes (RefLink[Probability, paclet:ref/Probability])[(RefLink[PDF, paclet:ref/PDF])[dist,y]<(RefLink[PDF, paclet:ref/PDF])[dist,x],y\[Distributed]dist]:

ld=LearnDistribution[{1.2,2.5,3.2,4.6, 5,6,7}]
RarerProbability[ld, {3,100}]

**This number is the total probability to generate samples with pdf lower than pdf of “3” and “100”

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

AcceptanceThreshold option

RarerProbability threshold to consider an example anomalous

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

Using FindAnomalies with learned distribution

Given the trained distribution on a training set, FindAnomalies uses the learned distribution to find anomalies in the test set:

FindAnomalies[LearnedDistribution[...],{(Subscript[example, 1]),(Subscript[example, 2]),…}]

ldn=LearnDistribution[{1.1,2,3,4,5,6,7,8,9.5}]

FindAnomalies[ldn, {1,100,1.4,3.4,4,5.5,6.8,7.9,8,9,10,12, -1000}]

FindAnomalies[ldn, {1,100,1.4,3.4,4,5.5,6.8,7.9,8,9,10,12, -1000}, AcceptanceThreshold->.1]

Separate Anomalies & Non-Anomalies

The distribution is modelled using LearnDistribution

Ideal case: If training data is non-anomalous data

Trivial case: using a trained distribution on non-anomalous data, but not always possible

FindAnomalies[LearnedDistribution[...],{(Subscript[example, 1]),(Subscript[example, 2]),…}]

If training data contains anomalies, chicken and egg problem:

we need distribution to find anomalies

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

Cross validation

Finding anomalies directly on data which contains anomalies:

FindAnomalies[{(Subscript[example, 1]),(Subscript[example, 2]),…}]

We train a distribution 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

Using FindAnomalies

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

ld=LearnDistribution[RandomReal[1, {20, 2}]]

FindAnomalies[ld, {{0.8,0.7},{5, 0.6}, {0.3, 0.5}, {0.1,0.2}, {1, 7}}]

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

Application: Finding anomalous images

Learn a distribution on dataset of images:

SeedRandom[1234]
cifar=ResourceData["CIFAR-10"];
cifar= RandomSample[cifar];
sample=Keys@RandomSample[cifar, 5000];
{cifartest, cifartrain}=TakeDrop[sample, 1000];
cifartest=Flatten[Join[Table[RandomImage[1, {12,12}], 10],cifartest ], 1];
cifartest[[;;100]]

ldi=LearnDistribution[cifartrain, "ComputedPropertiesMinSampleNumber"->500]

FindAnomalies[ldi,cifartest]

imgs={,,,,,};
corupted=ImageEffect[#,{"Jitter", 6}]&/@imgs
newtest=Join[imgs, corupted]

FindAnomalies[ldi,newtest, AcceptanceThreshold->.1]

Synthesizing Missing Values

Goal: Replaces missing values in each example by generated values

SynthesizeMissingValues[LearnedDistribution[...],{(Subscript[example, 1]),(Subscript[example, 2]),…}]
SynthesizeMissingValues[{(Subscript[example, 1]),(Subscript[example, 2]),…}]

Our formalism

Train a distribution on examples

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

Condition the distribution on known variable:

{Missing[], 4.5}

P(x) = P (x | y = 4.5)

Sample from the conditioned distribution.

Expected Maximization (EM): iterates between training the distribution and imputing missing values with samples from the distribution and retraining the distribution ....

Fill in Missing values :

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

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

SynthesizeMissingValues[{{1,2.2},{2,3.2},{3,Missing[]},{5, 6.2},{6, 7}}]

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"|>]

Example

data=ExampleData[{"MachineLearning","FisherIris"},"Data"][[All,1,{1,3}]];
ListPlot[data]

ld=LearnDistribution[data]

Plot the probability density of the distribution, along with the training data.

pdf=ContourPlot[PDF[ld,{x,y}],{x,4,8},{y,0.5,7},];
Show[{pdf,ListPlot[data,]}]

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

By default, the imputation is done by sampling from the conditioned distribution. Obtain other possible imputations.

imputed=Table[SynthesizeMissingValues[ld,{5.5,Missing[]}],1000];

RandomSample[imputed,10]

Show[{pdf,ListPlot[RandomSample[imputed,20],]}]

Visualize the distribution of imputed values.

Histogram[Last/@imputed,50,Frame->True,ImageSize->Medium]

Impute a missing value by specifying the “ModeFinding” Method to obtain the missing value candidates with largest probability:

mode=SynthesizeMissingValues[ld,{5.5,Missing[]},Method->"ModeFinding"]
Show[{pdf,ListPlot[{mode},]}]

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: Training an “In-Painter”

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

Generative Adversarial networks (GANs) will be added

It will work sequences such as texts, time series...

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

Definitions & extra examples

Notebook function definition

(*move to notebook funcs.*)

(*"anisotropic"*)
generateNormalClusterdata[ns_, random_]:=Module[
{p1,p2,p3},
(*ns=600;*)
(*SeedRandom[1234];*)
	SeedRandom[random];
	p1=With[{ρ=.5},RandomVariate[MultinormalDistribution[{1,2}, {{.1,ρ },{ρ ,3}}], ns]];
	p2=With[{ρ=.5},RandomVariate[MultinormalDistribution[{2.9  ,3}, {{.1,ρ },{ρ ,3}}], ns]];
	p3=With[{ρ=.4},RandomVariate[MultinormalDistribution[{-1.2,-2}, {{.1,ρ },{ρ ,2}}], ns]];
	Join[p1,p2,p3]
]
compltoptfull[data_]:=(Sequence@@{
PlotStyle->Directive[PointSize[0.011],Opacity[0.4]],
Frame->True, Axes->False,FrameTicks->None, AspectRatio->1, PlotRange-> pltRange[data]});

dbscancompltoptfull[data_]:=Sequence@@{
PlotStyle->Directive[(*PointSize[0.021]*)PointSize[0.035], Gray,Opacity[0.85]],
Frame->True, Axes->False,FrameTicks->None, AspectRatio->1, PlotRange-> pltRange[data]};

pltRange[data_, edg_:0.3]:= {
{Min@data[[All, 1]]- edg,Max@data[[All, 1]]+edg},
{Min@data[[All, 2]]-edg,Max@data[[All, 2]]+edg}
}
showDBPlot[cl_, ccdata_]:=Module[{decision, rancls, regcls},
decision=cl[ccdata];
regcls= Select[DeleteDuplicates[decision],(#>0 )&];
Show[{ListPlot[Pick[ccdata,Replace[decision,Missing["Anomalies"]-> -1,All],#]&/@regcls,compltoptfull[ccdata]], 
ListPlot[Pick[ccdata,decision,Missing["Anomalies"]],dbscancompltoptfull[ccdata]]}]
]