Lecture -- Linear Regression - EMPossible

6/9/2020Computational Science:Computational Methods in EngineeringLinear Regressionhttps://empossible.net/academics/emp4301 5301/Outline Linear regression – algebraic approach Linear regression – matrix approach Visualizing least squares Implementing linear regression MATLAB 4301 5301/21

6/9/2020Goal of Linear RegressionThe goal of linear regression is to fit a straight line to a set of measured data that has noise. x1 , y1 , x2 , y2 , , xM , yM y a0 a1 x3Linear Regression(Algebraic Approach)https://empossible.net/academics/emp4301 5301/42

6/9/2020Statement of ProblemGiven a set of measured data points: (x1,y1), (x2,y2), , (xM,yM),the equation of the line is written for each point.y1 a0 a1 x1 e1y2 a0 a1 x2 e2 To be completely correct, an error term e isintroduced called the residual.yM a0 a1 xM eMIt is desired to determine values of a0 and a1 such that the residual terms em are as small aspossible.5Criteria for “Best Fit”A single quantity is needed that measures how “good” the line fits the set of data.Guess #1 – Sum of ResidualsME emm 1This does not work because negative and positive residuals cancancel and mislead the overall criteria to think there is no error.Guess #2 – Sum of Magnitude of ResidualsME emThis does not work because it does not lead to a unique best fit.m 1Guess #3 – Sum of Squares of ResidualsME em2This works and leads to a unique solution.m 163

6/9/2020Equation for CriterionThe line equation for the mth sample isym a0 a1 xm emSolving this for the residual em givesem ym a0 a1 xm This is the fit value of y at point xm.This is the measured value of y.From this, the error criterion is written asMMm 1m 1ME em2 ymeasured,m yline,m ym a0 a1 xm 22m 17Least‐Squares FitIt is desired to minimize the error criterion E.Minimums can be identified where the first‐order derivative is zero. E E 0 and 0 a0 a1Values of a0 and a1 are sought that satisfy these equations.This approach is solving the problem by least‐squares (i.e. minimizing the squares of theresiduals).84

6/9/2020Derivation of Least‐Squares FitStep 1 – Differentiate E with respect to each of the unknowns. E a0 a0M ym a0 a1 xm 2m 1 E M2 ym a0 a1 xm a1 a1 m 1 2 ym a0 a1 xm m 1 a1 2 ym a0 a1 xm am 10MM M 2 ym a0 a1 xm xm M 2 ym a0 a1 xm 1 m 1m 1MM 2 ym a0 a1 xm xm 2 ym a0 a1 xm m 1m 19Derivation of Least‐Squares FitStep 2 – Set the derivatives to zero to locate the minimum of E.0 E a00 M 2 ym a0 a1 xm m 1MMMm 1m 1m 1 ym a0 a1 xmMMm 1m 1 ym Ma0 a1 xm E a1M 2 ym a0 a1 xm xmm 1M ym a0 a1 xm xmm 1MMMm 1m 1m 1 ym xm a0 xm a1 xm2105

6/9/2020Derivation of Least‐Squares FitStep 3 – Write these as two simultaneous equations. These are called the normalequations.0 E a00 MM 2 ym a0 a1 xm xm 2 ym a0 a1 xm m 1m 1MMMm 1m 1m 1M ym a0 a1 xm xm ym a0 a1 xmMMm 1m 1 E a1m 1MMMm 1m 1m 1 ym xm a0 xm a1 xm2 ym Ma0 a1 xm MMm 1m 1Ma0 a1 xm ymMMMm 1m 1m 1a0 xm a1 xm2 ym xm11Derivation of Least‐Squares FitStep 4 – The normal equations are solved simultaneously and the solution isMa0 yavg a1 xavg1M1 Mxavg yavga1 MMm 1m 12M xm ym xm ymm 1 M xm2 xm m 1 m 1 MMM xm 1Mm ymYikes!There has to be an easier way!m 1126

6/9/2020Linear Regression(Matrix Approach)https://empossible.net/academics/emp4301 5301/13Statement of ProblemIt is desired to fit a set of M measured data points to a curve containing 𝑁1 terms:f a0 z0 a1 z1 a2 z2 aN z Nf measured valuezn parameters from which f is evaluatedan coefficients for the curve fit147

6/9/2020Formulation of Matrix EquationStart by writing the function f for each of the M measurements. The residual terms are alsoincorporated.f1 a0 z0,1 a1 z1,1 aN z N ,1 e1f 2 a0 z0,2 a1 z1,2 aN z N ,2 e2 f M a0 z0, M a1 z1, M aN z N , M eMThis large set of equations is put into matrix form. f1 z0,1 z f 2 0,2 f3 z0,3 f M 1 z0, M 1 f M z0, Mz1,1z1,2z1,3 z1, M 1z1, Mz N ,1 e1 z N ,2 a0 e2 z N ,3 a1 e3 z N , M 1 aN eM 1 z N , M eM f Z a e orf Za e15Formulation of Solution byLeast‐Squares (1 of 4)Step 1 – Solve matrix equation for e.f Za e e f ZaStep 2 – Calculate the error criterion E from e.ME em2 e1 e2m 1e3 eM 1 e1 e 2 e eM 3 eT e eM 1 eM Step 3 – Substitute the equation for e from Step 1 into the equation for E from Step 2.E eT e f Za f Za T168

6/9/2020Formulation of Solution byLeast‐Squares (2 of 4)Step 4 – The new matrix equation is algebraically manipulated as follows in order to make iteasier to find its first‐order derivative.E f Za f Za Toriginal equation f T aT ZT f Za distribute the transposeT f T f f T Za aT Z f aT ZT Za expand equationThese are scalars andtransposes of each otherso they are equal. f T f 2aT ZT f aT ZT Zacombine terms17Formulation of Solution byLeast‐Squares (3 of 4)Step 5 – Differentiate E with respect to a.It is desired to determine a that minimizes E.This can be accomplished using the first‐derivative rule.E f T f 2aT ZT f aT ZT Za E T f f 2aT ZT f aT ZT Za a a T f f 2 aT ZT f aT ZT Za a a a 2ZT f 2ZT Zasubstitute in expression for Ef is not a function of afinish differentiation189

6/9/2020Formulation of Solution byLeast‐Squares (4 of 4)Step 6 – Find the value of a that makes the derivative equal to zero. E 2ZT f 2ZT Za 0 a 2ZT f 2ZT Za 02ZT Za 2ZT fObserve that this is the originalequation 𝐙𝐚 𝐟 premultiplied by 𝐙 .ZT Za ZT fa ZT Z ZT f 119DO NOT SIMPLIFY FURTHER!If the least‐squares equation was simplified further, it would givea ZT Z ZT f 1 Z 1 Z T Z T f 1I 1 Z fThis is just the original equation again (𝐟incorporated.𝐙𝐚) without the least‐squares approach2010

6/9/2020Visualizing p4301 5301/21Visualizing Least‐Squares (1 of 3)Initially, a matrix equation was given that had more equations than unknowns. 2211

6/9/2020Visualizing Least‐Squares (2 of 3)The equation was premultiplied by the transpose of A. 23Visualizing Least‐Squares (3 of 3)The matrix equation reduced to the same number of equations as unknowns, which issolvable by many standard algorithms. 2412

6/9/2020Implementing Linear Regressionhttps://empossible.net/academics/emp4301 5301/25Least‐Squares AlgorithmStep 1 – Construct matrices. Z is essentially just a matrix of the coordinates of the datapoints. f is a column vector of the measurements. f1 f 2 f f 3 f M 1 f M z0,1 z 0,2 z0,3Z z0, M 1 z0, Mz1,1z1,2z1,3 z1, M 1z1, Mz N ,1 z N ,2 z N ,3 z N , M 1 z N , M Step 2 – Solve for the unknown coefficients a.a Z T Z ZT f 1Step 3 – Extract the coefficients from a. a0 a a 1 aN 2613

6/9/2020Least‐Squares for Solving Ax bSuppose it is desired to solve Ax b, but there exists more equations than there areunknowns.This must be solved as a “best fit” because a perfect fit is impossible in the presence ofnoise.Least‐squares is implemented simply by premultiplying the matrix equation by AT.Ax b A x b A A T Ab A T b27Example 1 (1 of 3)Fit a line to the following set of points.yxy mx b2814

6/9/2020Example 1 (2 of 3)Step 1 – Build matricesy1 mx1 by2 mx2 by3 mx3 b y4 mx4 b y1 x1 y2 x2 y3 x3 y4 x41 1 m 1 b 1 0.16 1.13 f 1.57 2.35 3.01 4.98Z 6.91 8.761 1 1 1 With practice, you will be able to write thesematrices directly from the measured data.Step 2 – Solve by least squares.ZT Zx ZT f 3.01 3.01 4.98 6.91 8.76 4.98 1 111 6.91 8.76 1 0.16 1 m 3.01 4.98 6.91 8.76 1.13 1 b 1111 1.57 1 2.35 158.3462 23.6600 m 37.5437 23.6600 4.0000 b 5.2100 m 0.3656 b 0.8602 29Example 1 (3 of 3)Step 3 – Extract coefficients m 0.3656 b 0.8602 m 0.3656b 0.8602Step 4 – Plot the resulty mx b 0.3656 x 0.8602yx3015

2 Goal of Linear Regression 3 The goal of linear regression is to fit a straight line to a set of measured data that has noise. 122 1 1 0 x . Microsoft PowerPoint - Lecture -- Linear Regression