CSE 471: MACHINE LEARNING
Learning from Examples (Continued)
Outline
Linear Regression and Classification
Ensemble Learning
Model Selection and Optimization
The Theory of Learning
Nonparametric Models
Developing Machine Learning Systems
Linear Regression &
Classification
Linear Regression
w∗ = argminw Loss(hw)
Set partial derivatives to 0 to obtain the minima
Linear Regression
Gradient Descent
- Learning rate
Constant
Decaying
The partial derivatives
The learning rules
For single
example
For Entire
training
set
Stochastic gradient descent
(SGD)
Use a random sample of examples at
each step
A minibatch of m out of N samples
Convergence of minibatch SGD is not
strictly guaranteed
It can oscillate around the minimum
without settling down
Decaying learning rate can guarantee
convergence
Useful in online learning
Multivariable Linear
Regression
Gradient Descent Step
Recall
[for
univariable
case]
Multivariable LR Vectorized
Assuming a dummy input
attribute xj,0 = 1, We can
vectorize the formulation
The
optimization
Problem
Multivariable LR Vectorized
y hat – prediction on all examples
X - Data marix. Each row is a multivariable sample
w - Weight vector
Loss over training dataset
Set the gradient to 0
Normal Equation
Ensemble Learning
Ensemble Learning
Boosting
Bootstrap aggregating (Bagging)
Random forests
Stacking
Boosting
Boosting Decision Stumps
• A decision stump is a DT with just one test (i.e. only the root)
• Notice that the test set accuracy improves slightly even after the training
accuracy reaches 1, i.e., after the ensemble fits the data exactly.
AdaBoost
AdaBoost
continue
Stacking
Base models from different model classes
SVM
Logistic regression
Decision Tree
Augment feature vector with output of the
base models
Train the ensemble model (say Logistic
regression)
On the Validation Set
Cross validation can be done
Stacking
Base
classifier-1
Base New training set
classifier-2 for meta
Meta
classifier
Training classifie
Base consisting of
set r
classifier-3 predictions from
base classifiers
.. . . ..
Base
Final
classifier-n
predicti
on
Taken from MSc thesis defense presentation of Qazi Farah Nawar
Stacking improves class
separation
This is a t-SNE plot from protein carbohydrate binding site prediction
problem. FC-1 to FC-5 are best 5 feature spaces. FC-6 is FC-1 augmented
with prediction values from the base layer (i.e., what the meta layer of
stacking ensemble will see . (Nawar et al.)
Stacking improves class
separation
This is a t-SNE plot from protein carbohydrate binding site prediction
problem. FC-1 to FC-5 are best 5 feature spaces. FC-6 is FC-1 augmented
with prediction values from the base layer (i.e., what the meta layer of
stacking ensemble will see . (Nawar et al.)
Stacking improves class
separation
This is a t-SNE plot from protein carbohydrate binding site prediction
problem. FC-1 to FC-5 are best 5 feature spaces. FC-6 is FC-1 augmented
with prediction values from the base layer (i.e., what the meta layer of
stacking ensemble will see . (Nawar et al.)
Bagging
K distinct training sets by subsampling
With replacement
Reduces variance
Most commonly used with decision trees
DTs are very sensitive to changes in
examples
Can be applied in parallel
Random forests
A form of decision tree bagging
Takes extra measures to diversify the base
DTs
At each split point, attributes are sampled.
Attribute with highest IG from the sample is
chosen
Extremely Randomized Tree (ExtraTree)
For an attribute, we randomly sample several
candidate values from a uniform distribution
over the attribute’s range
Choose the value that results in highest IG
Random forests
Can be created efficiently
Sampled attribute space
No need for DT pruning
The trees can be built in parallel
Out-of-bag error
Mean error on each example, using only
the trees whose example set didn’t include
that particular example
Can be used instead of CV error
Multivariable LR
Regularization
Cost(h) = EmpLoss(h) + λ Complexity(h)
L1 regularization produces sparse model
Easier for a human to understand
Less likely to overfit
You can use L1 loss with L2 regularization and vice versa.
L1 regularization – LASSO
L2 regularization - Ridge
L1 vs. L2 regularization
L1 regularization tends to produce a sparse model.
Linear Classification
Linear Classification
Gradient is discontinuous
Gradient is zero almost everywhere in weight space
except at those points where and at those points the
gradient is undefined
Perceptron Learning Rule
If the output is correct (i.e., ) then the weights are not changed.
If y is 1 but hw(x) is 0, then wi is increased when the corresponding input is
positive and decreased when is negative. This makes sense, because we
want to make w.x bigger so that outputs a 1.
If is 0 but is 1, then is wi decreased when the corresponding input is positive
and increased when is negative. This makes sense, because we want to
make smaller so that outputs a 0.
Logistic Regression
Logistic Regression
Logistic Regression
Likelihood
of the
parameter
s
Maximizing the log
Likelihood
For single data point
Update rule
j = j + (y - h(x))xj
Identical to the update rule in linear
regression