[PDF] Mondrian Forests Mondrian Forests. Randomization mechanism. Online

View - Download Mondrian Forests

Previous PDF

Next PDF

Mondrian Forests

Balaji Lakshminarayanan

Gatsby Unit, University College London

Joint work with Daniel M. Roy and Yee Whye Teh

1

Outline

Motivation and Background

Mondrian Forests

Randomization mechanism

Online training

Prediction and Hierarchical smoothing

Classification Experiments: online vs batch

Regression Experiments: evaluating uncertainty estimates

Conclusion

2

Motivation

Typical converation:

I have a fasterABC DEF sampler for a fancy

non-parametric Bayesian model XYZ

Bayesian: cool!

Others: Isn"t the

non-Ba yesianpar ametric v ersion,lik e100 times faster? Why should I care?Lots of neat ideas in Bayesian non-parametrics; can we use these in a non-Bayesian context?3

Motivation

Typical converation:

I have a fasterABC DEF sampler for a fancy

non-parametric Bayesian model XYZ

Bayesian: cool!

Others: Isn"t the

non-Ba yesianpar ametric v ersion,lik e100 times faster? Why should I care?Lots of neat ideas in Bayesian non-parametrics; can we use these in a non-Bayesian context?3

Motivation

Typical converation:

I have a fasterABC DEF sampler for a fancy

non-parametric Bayesian model XYZ

Bayesian: cool!

Others: Isn"t the

non-Ba yesianpar ametric v ersion,lik e100 times faster? Why should I care?Lots of neat ideas in Bayesian non-parametrics; can we use these in a non-Bayesian context?3

Motivation

Typical converation:

I have a fasterABC DEF sampler for a fancy

non-parametric Bayesian model XYZ

Bayesian: cool!

Others: Isn"t the

non-Ba yesianpar ametric v ersion,lik e100 times faster? Why should I care?Lots of neat ideas in Bayesian non-parametrics; can we use these in a non-Bayesian context?3

Problem setup

Input: attributesX=fxngNn=1, labelsY=fyngNn=1(i.i.d) xn2 X(we assumeX= [0;1]Dbut could be more general) yn2 f1;:::;Kg(classification) oryn2R(regression)

Goal: Predictyfor test datax

Recipe for prediction: Use ar andomf orest

Ensemb leof r andomizeddecision trees

Stat e-of-the-artf orlots of real w orldprediction tasks -Do we Need Hundreds of Classifiers to Solve Real World Classification Problems?[Fern´andez-Delgado et al., 2014]

What is a decision tree?4

Problem setup

Input: attributesX=fxngNn=1, labelsY=fyngNn=1(i.i.d) xn2 X(we assumeX= [0;1]Dbut could be more general) yn2 f1;:::;Kg(classification) oryn2R(regression)

Goal: Predictyfor test datax

Recipe for prediction: Use ar andomf orest

Ensemb leof r andomizeddecision trees

Stat e-of-the-artf orlots of real w orldprediction tasks -Do we Need Hundreds of Classifiers to Solve Real World Classification Problems?[Fern´andez-Delgado et al., 2014]

What is a decision tree?4

Problem setup

Input: attributesX=fxngNn=1, labelsY=fyngNn=1(i.i.d) xn2 X(we assumeX= [0;1]Dbut could be more general) yn2 f1;:::;Kg(classification) oryn2R(regression)

Goal: Predictyfor test datax

Recipe for prediction: Use ar andomf orest

Ensemb leof r andomizeddecision trees

Stat e-of-the-artf orlots of real w orldprediction tasks -Do we Need Hundreds of Classifiers to Solve Real World Classification Problems?[Fern´andez-Delgado et al., 2014]

What is a decision tree?4

Example: Classification tree

Hierarchical axis-aligned binary partitioning of input space

Rule for predicting label within each blockx

1>0:37x

2>0:5 , ,F,F?

??x 2x101 1B jT: list of nodes, feature-id + location of splits for internal nodes : Multinomial parameters at leaf nodes 5

Prediction using decision tree

Example

Multi- classclassification: = [r;b;g]

Predict ion= smoothed empir icalhistog ramin node j

Label counts in left node [nr=2;nb=0;ng=0]

- Dirichlet(=3;=3;=3)

Predict ion= P osteriormean of =2+=32+;=32+;=32+?

??x 2x101 1B j6

Prediction using decision tree

Example

Multi- classclassification: = [r;b;g]

Predict ion= smoothed empir icalhistog ramin node j

Label counts in left node [nr=2;nb=0;ng=0]

- Dirichlet(=3;=3;=3)

Predict ion= P osteriormean of =2+=32+;=32+;=32+

Likelihood fornthdata point=p(ynjj)assumingxnlies in leaf nodejofT

Prior overj: independent orhier archical

Prediction forxfalling inj=EjjT;X;Yp(yjj), where

p(jjT;X;Y)/p(jj:::)|{z} priorY n2N(j)p(ynjj) |{z} likelihood of data points in node j

Smoothing is done independently for each tree6

From decision trees to Random forests (RF)

Generate

r andomized trees fTmgM1

Prediction forx:

p(yjx) =1M X mp(yjx;Tm)

Model combination

and not Ba yesianmodel a veraging

Advantages of RF

Excellent predictiv eperf ormance(test accur acy)

F astto tr ain(in batch setting) and test

T reescan be tr ainedin par allel7

From decision trees to Random forests (RF)

Generate

r andomized trees fTmgM1

Prediction forx:

p(yjx) =1M X mp(yjx;Tm)

Model combination

and not Ba yesianmodel a veraging

Advantages of RF

Excellent predictiv eperf ormance(test accur acy)

F astto tr ain(in batch setting) and test

T reescan be tr ainedin par allel7

Disadvantages of RF

Not possible to train incrementally

Re-tr ainingbatch v ersionper iodicallyis slo wO(N2logN)

Existin gonline RF v ariants

Saffari et al., 2009

Denil et al., 2013

] require lots of memor y/ computation or need lots of tr ainingdata bef orethe ycan deliv ergood test accuracy ( data inefficient Random forests do not give useful uncertainty estimates

Predict ionsoutside r angeof tr ainingdata can be

overconfident Uncer taintyestimates are cr ucialin applications such as Bayesian optimization, Just-in-time learning, reinforcement learning, etc.8

Disadvantages of RF

Not possible to train incrementally

Re-tr ainingbatch v ersionper iodicallyis slo wO(N2logN)

Existin gonline RF v ariants

Saffari et al., 2009

Denil et al., 2013

] require lots of memor y/ computation or need lots of tr ainingdata bef orethe ycan deliv ergood test accuracy ( data inefficient Random forests do not give useful uncertainty estimates

Predict ionsoutside r angeof tr ainingdata can be

overconfident Uncer taintyestimates are cr ucialin applications such as Bayesian optimization, Just-in-time learning, reinforcement learning, etc.8

Mondrian Forests

Mondrian forests= Mondrian process + Random forests

Can operate in either batch mode or online mode

Online speedO(NlogN)

Data efficient

(predictiv eperf ormanceof online mode equals that of batch mode!)

Better uncertainty estimate than random forests

Predictions outside range of training data exhibit higher uncertainty and shrink to prior as you move farther away9

Mondrian Forests

Mondrian forests= Mondrian process + Random forests

Can operate in either batch mode or online mode

Online speedO(NlogN)

Data efficient

(predictiv eperf ormanceof online mode equals that of batch mode!)

Better uncertainty estimate than random forests

Predictions outside range of training data exhibit higher uncertainty and shrink to prior as you move farther away9

Outline

Motivation and Background

Mondrian Forests

Randomization mechanism

Online training

Prediction and Hierarchical smoothing

Classification Experiments: online vs batch

Regression Experiments: evaluating uncertainty estimates

Conclusion

10

Popular batch RF variants

How to generate individual trees in RF?

Breiman-RF[Breiman, 2001]: Bagging + Randomly

subsample features and choose best location amongst subsampled features

Extremely Randomized Trees[Geurts et al., 2006]

(ERT-k): Randomly samplek(feature-id, location) pairs and choose the best split amongst this subset no b agging

ER T-1does not use labels Yto guide splits!11

Popular batch RF variants

How to generate individual trees in RF?

Breiman-RF[Breiman, 2001]: Bagging + Randomly

subsample features and choose best location amongst subsampled features

Extremely Randomized Trees[Geurts et al., 2006]

(ERT-k): Randomly samplek(feature-id, location) pairs and choose the best split amongst this subset no b agging

ER T-1does not use labels Yto guide splits!11

Mondrian process [Roy and Teh, 2009]

MP(;X)specifies a distribution over hierarchical

axis-aligned binary partitions ofX(e.g.RD,[0;1]D)

is complexity parameter of the Mondrian processFigure:Mondrian Composition II in Red, Blue and Yellow (Source: Wikipedia)12

Mondrian process [Roy and Teh, 2009]

MP(;X)specifies a distribution over hierarchical

axis-aligned binary partitions ofX(e.g.RD,[0;1]D)

is complexity parameter of the Mondrian processFigure:Mondrian Composition II in Red, Blue and Yellow (Source: Wikipedia)12

Generative process: MP(;f[`1;u1];[`2;u2]g)

1.

Dr awfrom exponential with rateu1`1+u2`2

2.IF> stop,?

1 u 1 u 2 213

Generative process: MP(;f[`1;u1];[`2;u2]g)

1.

Dr awfrom exponential with rateu1`1+u2`2

2.IF> stop,ELSE, sample a split

sp litdimension: choose dimension dwith prob/ud`d sp litlocation: choose unif ormlyfrom [`d;ud]? 1 u 1 u 2 214

Generative process: MP(;f[`1;u1];[`2;u2]g)

1.

Dr awfrom exponential with rateu1`1+u2`2

2.IF> stop,ELSE, sample cut

Ch oosedimension dwith probability/ud`d

Ch oosecut location unif ormlyfrom [`d;ud]

Recu rseon left and r ightsubtrees with par ameter? 1 u 1 u 2 215

Self-consistency of Mondrian process

SimulateT MP(;[`1;u1];[`2;u2])?

1 u 1 u 2 2 Restriction has distribution MP(;[`01;u01];[`02;u02])!16

Self-consistency of Mondrian process

SimulateT MP(;[`1;u1];[`2;u2])

RestrictTto a smaller rectangle[`01;u01][`02;u02]? 1 u 1 u 2 2 Restriction has distribution MP(;[`01;u01];[`02;u02])!16

Self-consistency of Mondrian process

SimulateT MP(;[`1;u1];[`2;u2])

RestrictTto a smaller rectangle[`01;u01][`02;u02]? 1 u 1 u 2 2 Restriction has distribution MP(;[`01;u01];[`02;u02])!16

Mondrian trees

UseXto define lower and upper limits within each node and use MP to sample splits. Difference between Mondrian tree and usual decision tree split in node jis committed only within extent of training data in nodej node jis associated with 'time of split"tj>0 (split time increases with depth and will be useful in online training) splits are chosen independent of the labels Y -is 'weighted max-depth".x

1>0:37x

2>0:5 , ,F,F-

-0

0:420:7∞?

??x 2x101 1B xj17

Mondrian trees

UseXto define lower and upper limits within each node and use MP to sample splits. Difference between Mondrian tree and usual decision tree split in node jis committed only within extent of training data in nodej node jis associated with 'time of split"tj>0 (split time increases with depth and will be useful in online training) splits are chosen independent of the labels Y -is 'weighted max-depth".x

1>0:37x

2>0:5 , ,F,F-

-0

0:420:7∞?

??x 2x101 1B xj17

Outline

Motivation and Background

Mondrian Forests

Randomization mechanism

Online training

Prediction and Hierarchical smoothing

Classification Experiments: online vs batch

Regression Experiments: evaluating uncertainty estimates

Conclusion

18

Mondrian trees: online learning

As dataset grows, we extend the Mondrian treeTby

simulating from a conditional Mondr ianprocess MTxT MT(;D1:n) T

0j T;D1:n+1MTx(;T;Dn+1)=) T0MT(;D1:n+1)

Distribution of batch and online trees are the same!

Order of the data points does not matter

quotesdbs_dbs47.pdfusesText_47

[PDF] mondrian composition avec rouge jaune et bleu 1921

[PDF] monecole evaluation

[PDF] monet impression soleil levant cycle 3

[PDF] Money can't buy hapiness

[PDF] moneyness de l option

[PDF] monica's boots

[PDF] monks oliver twist

[PDF] Monnaie et métaux: devoir de Physique

[PDF] monnaie romaine synonyme

[PDF] monnet (le parlement de Londre)

[PDF] Monochrome

[PDF] monodie polyphonie college

[PDF] monodie sur bourdon definition

[PDF] monoeuvre avis

[PDF] monoeuvre code promo