INTRODUCTION TO �Machine Learning�2nd Edition

ETHEM ALPAYDIN

© The MIT Press, 2010

​

alpaydin@boun.edu.tr

http://www.cmpe.boun.edu.tr/~ethem/i2ml2e

Lecture Slides for

CHAPTER 4: �Parametric Methods

Parametric Estimation

• X = { x^t }_t where x^t ~ p (x)
• Parametric estimation:

Assume a form for p (x |θ ) and estimate θ , its sufficient statistics, using X

e.g., N ( μ, σ²) where θ = { μ, σ²}

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

3

Maximum Likelihood Estimation

• Likelihood of θ given the sample X

l (θ|X) = p (X |θ) = ∏_t p (x^t|θ)

​

• Log likelihood

L(θ|X) = log l (θ|X) = ∑_t log p (x^t|θ)

​

• Maximum likelihood estimator (MLE)

θ^* = argmax_θ L(θ|X)

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

4

Examples: Bernoulli/Multinomial

• Bernoulli: Two states, failure/success, x in {0,1}

P (x) = p_o^x (1 – p_o ) ^{(1 – x)}

L (p_o|X) = log ∏_t p_o^xt (1 – p_o ) ^{(1 – xt)}

MLE: p_o = ∑_t x^t / N

​

• Multinomial: K>2 states, x_i in {0,1}

P (x₁,x₂,...,x_K) = ∏_i p_i^xi

L(p₁,p₂,...,p_K|X) = log ∏_t ∏_i p_i^xit

MLE: p_i = ∑_t x_i^t / N

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

5

Gaussian (Normal) Distribution

• p(x) = N ( μ, σ²)

​

​

• MLE for μ and σ²:

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

6

μ

σ

Bias and Variance

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

7

Unknown parameter θ

Estimator d_i = d (X_i) on sample X_i

​

Bias: b_θ(d) = E [d] – θ

Variance: E [(d–E [d])²]

​

Mean square error:

r (d,θ) = E [(d–θ)²]

= (E [d] – θ)² + E [(d–E [d])²]

= Bias² + Variance

θ

Bayes’ Estimator

• Treat θ as a random var with prior p (θ)
• Bayes’ rule: p (θ|X) = p(X|θ) p(θ) / p(X)
• Full: p(x|X) = ∫ p(x|θ) p(θ|X) dθ
• Maximum a Posteriori (MAP): θ_MAP = argmax_θ p(θ|X)
• Maximum Likelihood (ML): θ_ML = argmax_θ p(X|θ)
• Bayes’: θ_Bayes’ = E[θ|X] = ∫ θ p(θ|X) dθ

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

8

Bayes’ Estimator: Example

• x^t ~ N (θ, σ_o²) and θ ~ N ( μ, σ²)
• θ_ML = m
• θ_MAP = θ_Bayes’ =

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

9

Parametric Classification

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

10

• Given the sample

​

​

​

• ML estimates are

​

​

​

​

• Discriminant becomes

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

11

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

12

Equal variances

Single boundary at

halfway between means

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

13

Variances are different

Two boundaries

Regression

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

14

Regression: From LogL to Error

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

15

Linear Regression

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

16

Polynomial Regression

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

17

Other Error Measures

• Square Error:

​

​

• Relative Square Error:

​

• Absolute Error: E (θ |X) = _∑t |r^t – g(x^t| θ)|
• ε-sensitive Error:

E (θ |X) = _{∑ t} 1(|r^t – g(x^t| θ)|>ε) (|r^t – g(x^t|θ)| – ε)

​

​

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

18

Bias and Variance

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

19

Estimating Bias and Variance

• M samples X_i={x^t_i , r^t_i}, i=1,...,M

are used to fit g_i (x), i =1,...,M

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

20

Bias/Variance Dilemma

• Example: g_i(x)=2 has no variance and high bias

g_i(x)= _∑t r^t_i/N has lower bias with variance

​

• As we increase complexity,

bias decreases (a better fit to data) and

variance increases (fit varies more with data)

• Bias/Variance dilemma: (Geman et al., 1992)

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

21

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

22

bias

variance

f

g_i

g

f

Polynomial Regression

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

23

Best fit “min error”

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

24

Best fit, “elbow”

Model Selection

• Cross-validation: Measure generalization accuracy by testing on data unused during training
• Regularization: Penalize complex models

E’=error on data + λ model complexity

Akaike’s information criterion (AIC), Bayesian information criterion (BIC)

• Minimum description length (MDL): Kolmogorov complexity, shortest description of data
• Structural risk minimization (SRM)

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

25

Bayesian Model Selection

• Prior on models, p(model)

​

​

​

• Regularization, when prior favors simpler models
• Bayes, MAP of the posterior, p(model|data)
• Average over a number of models with high posterior (voting, ensembles: Chapter 17)

​

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

26

Regression example

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

27

Coefficients increase in magnitude as order increases:

1: [-0.0769, 0.0016]

2: [0.1682, -0.6657, 0.0080]

3: [0.4238, -2.5778, 3.4675, -0.0002

4: [-0.1093, 1.4356,

-5.5007, 6.0454, -0.0019]