Transcript ENGO Assessment of Environmental Goal Achievement under

Separating hyperplane
1
x T    0 0.80
x2
0.6
0.4
0.2
0
0
0.2
0.6
0.4
x1
Data mining and statistical learning lecture 13
0.8
1
Optimal separating hyperplane
- support vector classifier
1
x T    0 0.8
0
Find the
hyperplane
that creates
the biggest
margin
between the
training
points for
class 1 and -1
0.6
margin
0.4
0.2
0
0
0.2
0.4
0.6
0.8
Data mining and statistical learning lecture 13
1
Formulation
of the optimization problem
max  . 0 ,  1 C
subject to yi ( x    0 )  C , i  1, ..., N
T
i
Signed distance to
decision border
y=1 for one of the groups
and y=-1 for the other one
Data mining and statistical learning lecture 13
Two equivalent formulations
of the optimization problem
max  . 0 ,  1 C
subject to yi ( xiT    0 )  C , i  1, ..., N
min  . 0 
subject to yi ( xiT    0 )  1, i  1, ..., N
Data mining and statistical learning lecture 13
Optimal separating hyperplane
– overlapping classes
1
Find the
hyperplane
that creates
the biggest
margin
subject to
i  constant
0.8
1
0.6
xT    0  0
0.4
2 
3
0.2
0
0
0.2
0.4
0.6
0.8
1
Data mining and statistical learning lecture 13
Characteristics of the support vector classifier
Points well inside their class boundary do not play a big
role in the shaping of the decision border
Cf. linear discriminant analysis (LDA) for which the
decision boundary is determined by the covariance matrix
of the class distributions and their centroids
Data mining and statistical learning lecture 13
Support vector machines
using basis expansions (polynomials, splines)
1
f ( x)  h( x)T    0 0.80
h2(x)
0.6
0.4
0.2
0
0
0.2
0.6
0.4
h1(x)
Data mining and statistical learning lecture 13
0.8
1
Characteristics of support vector machines
The dimension of the enlarged feature space can be very
large
Overfitting is prevented by a built-in shrinkage of beta
coefficients
Irrelevant inputs can create serious problems
Data mining and statistical learning lecture 13
The SVM as a penalization method
Misclassification: f(x) < 0 when y=1 or f(x)>0 when y=-1
Loss function:
N
 [1  y f (x )]
i 1
i
i

Loss function + penalty:
N
 [1  yi f (xi )]   
2
i 1
Data mining and statistical learning lecture 13
The SVM as a penalization method
Minimizing the loss function + penalty
N
 [1  yi f (xi )]   
2
i 1
is equivalent to fitting a support vector machine to
data
The penalty factor  is a function of the constant
providing an upper bound of
N

i 1
i
Data mining and statistical learning lecture 13
Some characteristics of different learning methods
Characteristic
Neural
networks
Support
vector
machines
Trees
MARS
Natural handling of data of “mixed” type
Poor
Poor
Good
Good
Handling of missing values
Poor
Poor
Good
Good
Robustness to outliers in input space
Poor
Poor
Good
Poor
Insensitive to monotone transformations of
inputs
Poor
Poor
Good
Poor
Computational scalability (large N)
Poor
Poor
Good
Good
Ability to deal with irrelevant inputs
Poor
Poor
Good
Good
Ability to extract linear combinations of features
Good
Good
Poor
Poor
Interpretability
Poor
Poor
Fair
Good
Predictive power
Good
Good
Poor
Fair
Data mining and statistical learning lecture 13
Ve (r )
-insensitive error function
-6
-4
-
-2
4
3.5
3
2.5
2
1.5
1
0.5
0
0
2
Data mining and statistical learning lecture 13
4
6
SVMs for linear regression
Estimate the regression coefficients by minimizing
N

i 1
2
H (  ,  0 )   V ( yi  f (xi )) 

2
(i) The fitting is less sensitive than OLS to outliers
(ii) Errors of size less than  are ignored
(iii) Typically, the parameter estimates are functions of only
a minor subset of the observations
Data mining and statistical learning lecture 13
Ensemble methods




Bootstrapping (Chapter 8)
Bagging (Chapter 8)
Boosting (Chapter 10)
Bagging and boosting in SAS EM
Data mining and statistical learning lecture 13
Major types of ensemble methods
• Manipulation
of the model
• Manipulation
of the data set
Data mining and statistical learning lecture 13
Terminology
 Bagging=Manipulation of the data set
 Boosting = Manipulation of the model
Data mining and statistical learning lecture 13
The bootstrap
We would like to determine a functional F(P) of an unknown
probability distribution P
The bootstrap: Compute F(P*) where P* is an approximation of P
Data mining and statistical learning lecture 13
Resampling techniques
- the bootstrap method
Resampled data
Observed data
62
90
22
41
34
67
88 79
39
73
58
x1* , x2* , ...60
, xN*
88
Sampling with
replacement
58
90 88 79
41
22
44
70 60
44
70 60
85
85
x
34
41
x1* , x2* , ..., x N*
Data mining and statistical learning lecture 13
The bootstrap for assessing the accuracy of an
estimate or prediction
Compute
 
Var e X
Bootstrap samples X k*  ( X k*1 , ..., X kn* ) are generated by
sampling with replacement from the observed data
1. Generate N bootstrap samples and compute
2. Compute the sample variance of Tk
Data mining and statistical learning lecture 13
Tk  e
X k*
Bagging
- using the bootstrap to improve a prediction
Question:
Given the model Y=f(X)+ε and a set of observed
values Z={Yi, Xi, i=1,…,N}, what is E P fˆ X  , where
P denotes the distribution of (X,Y)?


Solution:
Replace P with P*:
• Produce B bootstrap samples Z1* ,, Z*B and, for
each sample, compute fˆ *b x 
• Compute the sample mean by averaging over the
bootstrap functions.
Data mining and statistical learning lecture 13
Bagging
Formula:
B
1
fˆbag  x    fˆ *b  x 
B b 1
Construct graphs,
compute average
Data mining and statistical learning lecture 13
Properties of bagging
 Bagging of fitted functions reduces the variance
 Bagging makes good predictions better, bad predictions
worse
 If the fitted function is linear, it will asymptotically coincide
with the bagged estimate (B -> Infinity)
Data mining and statistical learning lecture 13
Bagging for classification
Given a K-class classification problem with
Z={Yi, Xi, i=1, …, N} and a computed indicator
function (or class probabilities)
fˆ x   p1 x, , pK x , Gˆ x  arg max k pk x
B
1
we produce a bagging estimate fˆbag  x    fˆ *b  x 
B b 1
and predict class variables
Data mining and statistical learning lecture 13
Boosting
- basic idea
Consider a 2-class problem with Y  1, 1 and a
classifier G x  .
Produce a sequence of classifiers and combine them.
The weights for misclassified observations are
increased to force the algorithm to classify them
correctly at next step.
Data mining and statistical learning lecture 13
Boosting
Data mining and statistical learning lecture 13
Boosting
Data mining and statistical learning lecture 13
Boosting
- comments
 Boosting can be modified for regression
 AdaBoost.M1 can be modified to handle
categorical output
Data mining and statistical learning lecture 13
Bagging and boosting in EM
 Create a diagram (Input node (define target!) –
Partition node – Group processing node – Your
model – Ensemble node)
 Comment: boosting works only for classification
(categorical output)
Data mining and statistical learning lecture 13
Group processing: General
Modes:
• Unweighted resampling for bagging
• Weighted resampling for boosting
Data mining and statistical learning lecture 13
Group processing
- Unweighted resampling for bagging
• Specify sample size
Data mining and statistical learning lecture 13
Group processing: weighted resampling for
boosting
• Specify target
Data mining and statistical learning lecture 13
Ensemble results
Data mining and statistical learning lecture 13