Polynomial Curve Fitting

[Pages:19]Machine Learning

Srihari

Polynomial Curve Fitting

Sargur N. Srihari

1

Machine Learning

Srihari

Topics

1. Simple Regression Problem 2. Polynomial Curve Fitting 3. Probability Theory of multiple variables 4. Maximum Likelihood 5. Bayesian Approach 6. Model Selection 7. Curse of Dimensionality

2

Machine Learning

Srihari

Simple Regression Problem

? Begin discussion on ML by introducing a simple regression problem

? It motivates a no. of key concepts

? Problem:

? Observe Real-valued input variable x ? Use x to predict value of target variable t

? We consider an artificial example using synthetically generated data

? Because we know the process that generated the data, it can be used for comparison against a learned model

3

Machine Learning

Synthetic Data for Srihari Regression

? Data generated from the function sin(2 x)

? Where x is the input

? Random noise in target values

Target Variable

Input Variable Input values {xn} generated uniformly in range (0,1). Corresponding target values {tn} Obtained by first computing corresponding values of sin{2x} then adding random noise with a Gaussian distribution with std dev 0.3

4

Machine Learning

Training Srihari Set

? N observations of x

x = (x1,..,xN)T t = (t1,..,tN)T

? Goal is to exploit training set to predict valuet^ for some new value x^

? Inherently a difficult problem

? Probability theory provides framework for expressing uncertainty in a precise, quantitative manner

? Decision theory allows us to make a prediction that is optimal according to appropriate criteria

Data Generation: N = 10 Spaced uniformly in range [0,1] Generated from sin(2x) by adding small Gaussian noise Noise typical due to unobserved variables

5

Machine Learning

Srihari

A Simple Approach to Curve Fitting

? Fit the data using a polynomial function

M

y(x, w) = w0 + w1x + w2x 2 + .. + wMx M = wjx j

? where M is the order of the polynomial

j =0

? Is higher value of M better? Well see shortly!

? Coefficients w0 ,...wM are collectively denoted by vector w

? It is a nonlinear function of x, but a linear function of the unknown parameters w

? Have important properties and are called Linear Models

6

Machine Learning

Error Function Srihari

? We can obtain a fit by minimizing an error function

? Sum of squares of the errors between the predictions y(xn,w) for each data point xn and target value tn

E(w)

=

1 2

N n=1

{y(xn,

w) -

tn

}2

? Factor ? included for later convenience

Red line is best polynomial fit

? Solve by choosing value of w for which E(w) is as small as possible

7

Machine Learning

Srihari

Minimization of Error Function

? Error function is a quadratic in coefficients w

E(w)

=

1 2

N n=1

{y(xn, w) - tn }2

? Thus derivative with respect to coefficients will be linear in elements of w

? Thus error function has a unique solution which can be found in closed form

? Unique minimum denoted w*

? Resulting polynomial is y(x,w*)

M

Since y(x, w) = wjx j j =0

E(w)

wi

=

N

{y(xn

,

w)

-

tn

}x

i n

n=1

N M

= { wjxnj - tn }xni n=1 j =0

Setting equal to zero

NM

N

w

j

x i+j n

=

tnxni

n=1 j =0

n=1

Set of M+1 equations (i=0,..,M )

over M+1 variables are

solved to get elements of w*

8

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download