Active Learning
(ActiveClassification & ActivePrediction)
(available in 11.1 release)
 functions may work only in the latest version

Piyush Kumar
           Oct. 19, 2016

Introduction

Two basic tasks of “Supervised” Machine Learning -- Classification and Prediction

In WL, have nice functions: Classify[{ex1-> class1, ex2->class2,...}]  and  Predict[{ex1-> val1, ex2-> val2}]

Works in the following manner:

User provides entire training dataset with inputs (examples) and their classes (real values).

Algorithm chooses a particular method of Classification/Prediction and returns a ClassifierFunction/PredictorFunction.

Classify

trainingset1 = {1->"A",2->"A",3.5->"B",4->"B"};
c=Classify[trainingset1]

c[2.5]

testset1 = {2.2->"A",2.7->"A",4.5->"B",1.4->"B"};
cm = ClassifierMeasurements[c, testset1]["LogLikelihood"]

In general, however :

Unlabeled data much easier to obtain than labeled data.

Labeled data typically much harder - expensive or time-consuming. Examples:

Classifying documents on the basis of topics : Building ground truth entails labeling each document as belonging to -- Sports, Politics, Entertainment, etc. Requires effort.

Data requiring domain-expertise: E.g Annotating gene markers in a biological dataset. Requires scientific experts.

So, good to have a method in which the data to be labeled is selectively chosen and then queried to be labeled.

If choose data smartly, then hope to learn good Classifier/Predictor Model with (much) fewer labeled instances.

Active Learning -- Basic Idea

Settles 2010

(Unlabeled) data assumed to be sampled from some underlying input distribution

Query Strategies

Optimal Strategy : Markov Decision Process (MDP) --> construct an appropriate Value Function (V)

Value function depends on some kind of “reward” one gets at each step of the MDP.

Recursive Bellman Equation  for the Value Function ---> Computationally Intractable

Heuristic Strategies:

Randomized Sampling: select data to query randomly  -- from the same input distribution

Uncertainty Sampling: select data to query which has the least information/maximum uncertainty (entropy) according to current model (θ):

(Subscript[x, H])* = (Subscript[argmax, x]) (- Sum[(Subscript[P, θ])((Subscript[y, i])|x)Log[(Subscript[P, θ])((Subscript[y, i])|x)], {i, 1, n}]);  n = number of classes

Issues: i) Assumes that classifier model only needs to be modified near boundaries 					--- Not true in many cases.
	ii) Querying distribution very different from underlying data distribution 	
		--- Sampling bias
Solution: Use Importance Weights to correct the sampling bias.

More advanced (computationally intensive) strategies:

E.g. Information-based Sampling: select unlabeled data x⋆ to query by maximizing immediate expected information gain from the query x⋆.

Design and Implementation

ActiveClassification[f, spacespec], ActivePrediction[f, spacespec]
	: find best classification/prediction model obtained by using f to determine classes/values for configurations in spacespec

Input

spacespec : defines domain of the function. Domain of four types:

List of configurations {(Subscript[conf, 1]), (Subscript[conf, 2]), ...}

Geometric region reg : ConstantRegionQ[reg] must yield True

Configuration generator sampler:

sampler[] must output a configuration so that f can be applied to it.

Initial configuration(s)  {(Subscript[conf, 1]), (Subscript[conf, 2]), ...} together with a neighborhood configuration generator neighborsampler:  {(Subscript[conf, 1]), (Subscript[conf, 2]), ...}  -> neighborsampler								neighborsampler[(Subscript[conf, i])] must output a configuration so that f can be applied to it.

Configurations conf can be of any type accepted by Classify/Predict: numerical, nominal (categorical), text, sound, images, etc.

function f : arbitrary function -- explicit or blackbox.

Requirement -- i) ActivePrediction: f [conf] must yield a real number; ii) ActiveClassification: f [conf]  interpreted as a class/label.

No symbolic evaluation of f

ActivePrediction[x^2-3*x, Interval[{0,1}]]

Output

Output in the form of an “object” that has lots of information.

Can query the object for many properties prop.

ActiveClassificationObject[...][prop], ActivePredictionObject[...][prop]

Simple Examples

Classification-- Figuring out whether a particular person in the Titanic “died” or “survived”

PacletDirectoryAdd["~/git/ARG/MachineLearning"]
Get["MachineLearning`"]

Construct a “Titanic Oracle” that tells you whether a given person died or survived

titanicdataset = RandomSample[ExampleData[{"MachineLearning", "Titanic"}, "TrainingData"]]; 
titanicOracle[configuration_]:= Module[
	{testpos, result},
	testpos = First @ Flatten[Position[titanicdataset[[All, 1]], configuration]];
	result = titanicdataset[[testpos, 2]];
	result
];

Set the domain of the OracleFunction via a configuration generator:

samplertitanic[]:= RandomChoice[titanicdataset][[1]];

titanicOracle[samplertitanic[]]

Use ActiveClassification to construct a Classifier:

acTitanic= ActiveClassification[titanicOracle,samplertitanic]

Properties of the ActiveClassification Object obtained:

Properties

acTitanic["Properties"]

Training History

acTitanic["TrainingHistory"]

ClassifierFunction

acT= acTitanic["ClassifierFunction"]

Learning Curve

acTitanic["LearningCurve"]

Construct a Test set and check the ConfusionMatrixPlot of the resulting Classifier:

titanicTestset = RandomSample[ExampleData[{"MachineLearning", "Titanic"}, "TestData"], 100];
acM= ClassifierMeasurements[acT, titanicTestset];
acM["ConfusionMatrixPlot"]

Another Example -- Choosing between two DistanceFunctions that is faster

Define two distance functions between two elements:

prog1[l1_,l2_]:=Outer[ManhattanDistance,l1,l2,1];
prog2[l1_,l2_]:=Transpose[(Total/@Transpose[Abs[Transpose[l1]-#]])&/@l2];

Define a “DistanceChoice Oracle” that selects the distance function that is faster for a given configuration:

distanceChoiceOracle[{n1_, n2_, d_}]:= Module[
	{list1,list2},
	list1=RandomReal[1,{Round[Exp[n1]],Round[Exp[d]]}];
	list2=RandomReal[1,{Round[Exp[n2]],Round[Exp[d]]}];
	If[ First[AbsoluteTiming[prog1[list1,list2]]]> First[AbsoluteTiming[prog2[list1,list2]]], "Program2", "Program1"]
];

distanceChoiceOracle[parametersampler[]]

parametersampler[]

Set the domain of the OracleFunction via a configuration generator:

parametersampler[]:={RandomReal[{0,Log[1000.]}],RandomReal[{0,Log[1000.]}],RandomReal[{0,Log[1000.]}]};

Use ActiveClassification to construct a Classifier that chooses between the two functions:

(* can be stopped early if needed *)

acDistanceChoice= ActiveClassification[distanceChoiceOracle, parametersampler]

Properties of the ActiveClassification Object obtained:

Training History

acDistanceChoice["TrainingHistory"]

ClassifierFunction

acD = acDistanceChoice["ClassifierFunction"]

Learning Curve

acDistanceChoice["LearningCurve"]

Construct a Test set and check the Accuracy and ConfusionMatrixPlot of the resulting Classifier:

distanceChoiceTestset = Module[{r},
	r = Table[parametersampler[], {i, 1, 100}];
	#-> distanceChoiceOracle[#] &/@ r
];
acDM= ClassifierMeasurements[acD, distanceChoiceTestset];
acDM["Accuracy", "Uncertainty"-> True] 
acDM["ConfusionMatrixPlot"]

Prediction:

Construct an OracleFunction that gives the value of the Branin function for a given configuration:

fBranin[{x1_, x2_}]:= Module[
	{x1bar, x2bar, y},
	x1bar = 15.*x1-5.;
	x2bar = 15.*x2;
	y = 1/(51.95) *((((x2bar - 5.1((x1bar^2)/(4(π^2))) + 5(x1bar/π)-6))^2)+(10.-10./(8π))*Cos[x1bar] - 44.81);
	y
];

Set the domain of the function via a Configuration Generator:

samplertest[]:=RandomPoint[Rectangle[{0,0},{1.,1.}]];

Use ActivePrediction to construct a Predictor for the Branin function:

apBranin=ActivePrediction[fBranin, samplertest]

Properties of the Output object:

pBranin=apBranin["PredictorFunction"]

apBranin["PredictorMeasurementsObject"]

apBranin["TrainingHistory"]

apBranin["LearningCurve"]

Examine the quality of the predictor by plotting it together with the original function:

Plot3D[{fBranin[{x,y}], pBranin[{x,y}]}, {x,0,1},{y,0,1}, Exclusions-> False, PlotLegends-> {"Original Function", "Predictor Function"}]

Future Directions

Automated Machine Learning. Goal:

Fully automatic version of Classify/Predict. At present uses rudimentary heuristics.

Can use ActiveClassification inside Classify!

use it to choose between different methods as well as choose hyperparameters for different methods

also need appropriate version of hyperparameter optimization: BayesianOptimization

How Active Learning fits in the Big Picture:

Belongs to general class of “Sequential Decision Problems” / “Adaptive Control Processes”

Mathematical formulation : MDPs (fully observed, partially observed)

Idea : i) Query function and get “Reward” ii) Construct probabalistic model (reasoning); 		iii) Take actions/decisions to maximize Value function(V) that depends on the Reward.

Various branches of Machine Learning:

Active Learning: Reward = -H(f | (Subscript[D, 1: t]))

Bayesian Optimization : Here, reward is just the value of the function at the final ((T^th)) step  -- Reward = (Subscript[f, T]) (In WL, have BayesianMinimization and BayesianMaximization)

Multi-arm Bandits : Here, reward is the sum of the values of the functions at all intermediate steps --  Reward = ((Subscript[Σ, t=1])^T) (Subscript[f, t])

Reinforcement Learning : Most general case. Here, actions influence a “State” as well, which can keep changing.

Now, Value function (V) depends on: i) initial state distribution : P((Subscript[s, 0]))

ii) transition probabilities : P(s’| s, a)

iii) reward probabilities : P(r| s, a)

iv) policy: P(a | s)

RL : parameters for transition and reward probabilities not known in general.