ECE595 / STAT598: Machine Learning I Lecture 01: Linear .

ECE595 / STAT598: Machine Learning ILecture 01: Linear RegressionSpring 2020Stanley ChanSchool of Electrical and Computer EngineeringPurdue Universityc Stanley Chan 2020. All Rights Reserved.1 / 22

Outlinec Stanley Chan 2020. All Rights Reserved.2 / 22

OutlineMathematical BackgroundLecture 1: Linear regression: A basic data analytic toolLecture 2: Regularization: Constraining the solutionLecture 3: Kernel Method: Enabling nonlinearityLecture 1: Linear RegressionLinear RegressionNotationLoss FunctionSolving the Regression ProblemGeometryProjectionMinimum-Norm SolutionPseudo-Inversec Stanley Chan 2020. All Rights Reserved.3 / 22

Basic NotationScalar: a, b, c Ra, b, c RdMatrix: A, B , C RN d ; Entries are aijVector:or [A]ij .Rows and Columns A a1 a2 . ad , — ( x 1 )T — (x 2 )T and A . .— ( x N )T —— . —{a j }: The j-th feature. {x n }: The n-th sample.Identity matrixIAll-one vector 1 and all-zero vector 0Standard basisei .c Stanley Chan 2020. All Rights Reserved.4 / 22

Line 50.60.70.80.91c Stanley Chan 2020. All Rights Reserved.5 / 22

Linear RegressionThe problem of regression can be summarized as:Given measurements: y n , (where n 1, . . . , N)Given inputs: x nGiven a model: gθ (x n ) parameterized by θDetermine θ such that y n gθ (x n ).Linear regression is one type of regression:Restrict gθ (·) to a line:gθ (x ) x T θThe inputsx and the parameters θ arex [x1 , . . . , xd ]T andθ [θ1 , . . . , θd ]TThis is equivalent togθ (x ) x T θ dXxj θj .j 1c Stanley Chan 2020. All Rights Reserved.6 / 22

Solving the Regression ProblemThe (general) regression can be solved via the following logic:Define a (Squared-Error) Loss FunctionJ(θ) NXn 1NXL(gθ (x n ), y n )(gθ (x n ) y n )2 ,defe.g., L( , ) ( )2n 1Other loss functions can be used, e.g., L( , ) .The goal is to solve an optimizationθb argmin J(θ).θThe prediction of a new inputx new is y new gθb(x new ) θbT x new .c Stanley Chan 2020. All Rights Reserved.7 / 22

Linear Regression SolutionThe linear regression problem is a special case which we can solveanalytically.Restrict gθ (·) to a line:gθ (x n ) θ T x nThen the loss function becomesNXJ(θ) (θ T x n y n )2 kAθ y k2 .n 1The matrix and — —A —vectors are defined as (x 1 )T —θ12T (x )— . , θ . ,. .θdNT(x )— andy y1 y2 . . yNk · k2 stands for the 2 -norm square. See Tutorial on Linear Algebra.c Stanley Chan 2020. All Rights Reserved.8 / 22

Linear Regression SolutionTheoremFor a linear regression problemdefθb argmin J(θ) kAθ y k2 ,θthe minimizer isθb (AT A) 1 AT y .Take derivative and setting to zero: (See Tutorial on “LinearAlgebra”.) θ J(θ) θ kAθ y k2 2AT (Aθ y ) 0.So solution is θb (AT A) 1 AT y , assumingAT A is invertible.c Stanley Chan 2020. All Rights Reserved.9 / 22

ExamplesExample 1: Second-order polynomial fittingx12A . xN2yn axn2 bxn c x1 1y1. . , y . , . . . xN1yN aθ b cExample 2: Auto-regression yn ayn 1 byn 2 y1y3 y2 y4 ,y . , . . y2 y3A .yN 1 yN 2 aθ byNc Stanley Chan 2020. All Rights Reserved.10 / 22

Generalized Linear Regression10-101234567891001234567891010-11Eg 1: Fourier series n sin(ω0 tn )x1 x n sin(2ω t ) x n .2 . 0 n .xdnsin(K ω0 tn )0-10123456789101y n θT x n dXθk sin(kω0 tn )k 10θk : k-th Fourier coefficient-1012345678910sin(kω0 tn ): k-th Fourier basis attime tn10-1-2012345678910c Stanley Chan 2020. All Rights Reserved.11 / 22

OutlineMathematical BackgroundLecture 1: Linear regression: A basic data analytic toolLecture 2: Regularization: Constraining the solutionLecture 3: Kernel Method: Enabling nonlinearityLecture 1: Linear RegressionLinear RegressionNotationLoss FunctionSolving the Regression ProblemGeometryProjectionMinimum-Norm SolutionPseudo-Inversec Stanley Chan 2020. All Rights Reserved.12 / 22

Linear SpanGiven a set of vectors {a 1 , . . . , a d }, the span is the set of all possiblelinear combinations of these vectors. dXspan a 1 , . . . , a d z z αj a j(1)j 1Which of the following sets of vectors can span R3 ?c Stanley Chan 2020. All Rights Reserved.13 / 22

Geometry of Linear RegressionGiven θ, the productAθ can be viewed as Aθ a1 a2 θ1d X . . . a d . θj a j .j 1 θd So the set of all possible Aθ’s is equivalent to span{a 1 , . . . , a d }. Definethe range of A as R(A) {by yb Aθ}. Note that y 6 R(A).c Stanley Chan 2020. All Rights Reserved.14 / 22

Orthogonality PrincipleConsider the errore y Aθ.For the error to minimize, it must be orthogonal to R(A), which isthe span of the columns.This orthogonality principle means thatj 1, . . . , d, which implies AT e 0.aTj e 0 for allc Stanley Chan 2020. All Rights Reserved.15 / 22

Normal EquationThe orthogonality principle, which states that AT e 0, implies thatAT (y Aθ) 0 by substituting e y Aθ.This is called the normal equation:AT Aθ AT y .(2)The predicted value isyb Aθb A(AT A) 1 AT ydefThe matrix P A(AT A) 1 AT is a projection onto the span of{a 1 , . . . , a d }, i.e., the range of A.P is called the projection matrix. It holds that PP P .The error e y yb ise y A(AT A) 1 AT y (I P )y .c Stanley Chan 2020. All Rights Reserved.16 / 22

Over-determined and Under-determined SystemsAssume A has full column rank.Over-determined A: Tall and skinny. θb (AT A) 1 AT y .Under-determined A: Fat and short. θb AT (AAT ) 1 y .If A is under-determined, then there exists a non-trivial null spaceN (A) {θ Aθ 0}.This implies that if θb is a solution, then θb θ 0 is also a solution aslong as θ 0 N (A). (Why?)c Stanley Chan 2020. All Rights Reserved.17 / 22

Minimum-Norm SolutionAssume A is fat and has full row rank.Since A is fat, there exists infinitely many θb such thatSo we need to pick one in order to be unique.It turns out that θb AT (AAT ) 1 y is the solution toθb argmin kθk2 subject toθAθ y .Aθb y .(3)(You can solve this problem using Lagrange multiplier. See Appendix.)This is called the minimum-norm solution.c Stanley Chan 2020. All Rights Reserved.18 / 22

What if Rank-Deficient?If A is rank-deficient, then AT A is not invertibleApproach 1: Regularization. See Lecture 2.Approach 2: Pseudo-inverse. Decompose A USV T .U RN N , with U T U I . V Rd d , with V T V I .The diagonal block of S RN d is diag{s1 , . . . , sr , 0, . . . , 0}.The solution is called the pseudo-inverse:θb V S U T y ,where(4)S diag{1/s1 , . . . , 1/sr , 0, . . . , 0}.c Stanley Chan 2020. All Rights Reserved.19 / 22

Reading ListLinear AlgebraGilbert Strang, Linear Algebra and Its Applications, 5th Edition.Carl Meyer, Matrix Analysis and Applied Linear Algebra, SIAM, 2000.Univ. Waterloo Matrix Cookbook. https://www.math.uwaterloo.ca/ hwolkowi/matrixcookbook.pdfLinear RegressionStanford CS 229 (Note on Linear nalg.pdfElements of Statistical Learning (Chapter 3.2)https://web.stanford.edu/ hastie/ElemStatLearn/Learning from Data (Chapter 3.2)https://work.caltech.edu/telecoursec Stanley Chan 2020. All Rights Reserved.20 / 22

Appendixc Stanley Chan 2020. All Rights Reserved.21 / 22

Solving the Minimum Norm problemConsider this problemθb argmin kθk2 subject toθAθ y .(5)The Lagrangian isL(θ, λ) kθk2 λT (Aθ y ).Take derivative with respect to θ and λ yields θ L 2θ AT λ 0, λ L Aθ y 0First equation gives us θ AT λ/2.Substitute into second equation yields λ 2(AAT ) 1 y .Therefore, θ AT (AAT ) 1 y .c Stanley Chan 2020. All Rights Reserved.22 / 22

Lecture 1: Linear regression: A basic data analytic tool Lecture 2: Regularization: Constraining the solution Lecture 3: Kernel Method: Enabling nonlinearity Lecture 1: Linear Regression Linear Regression Notation Loss Function Solving the Regression Problem Geome