aWeek-5

Karthik Thiagarajan

1. Supervised Learning 1.1. Regression 1.2. Classification 2. Regression 3. Linear Regression 3.1. Model 3.2. Loss Function 3.3. Optimization 3.3.1. Gradient 3.3.2. Normal equations 3.4. Gradient descent 3.5. Stochastic Gradient Descent 3.6. Evaluation 4. Geometric Perspective 4.1. Best-fit surface 4.2. Projections 5. Probabilistic Perspective 6. Kernel Regression 6.1. Learning 6.2. Prediction 1. Supervised Learning 1.1. Regression Given a dataset D={(x1,y1),⋯,(xn,yn)}, where yi∈R, learn a function f:Rd→R that captures the underlying relationship (pattern) between data-points and labels and generalizes it to unseen data-points. The defining characteristic of a regression problem is that the labels are continuous valued real numbers. 1.2. Classification Given a dataset D={(x1,y1),⋯,(xn,yn)}, where yi∈{1,⋯,k}, learn a function f:Rd→{1,⋯,k} that captures the underlying relationship (pattern) between data-points and labels and generalizes it to unseen data-points. The defining characteristic of a classification problem is that the labels are from a finite, discrete set. If k=2, the problem is called binary classification. If k>2, the problem is called multi-class classification. 2. Regression If f:Rd→R is a potential mapping (model) from data-points to labels, we use the following metric to measure the goodness of the model. L(f,D)=1

2n∑i=1[f(xi)-yi]2 • yi → true label for xi• f(xi)→predicted label• f(xi)-yi→error in prediction This is called the sum of squared errors or SSE. The 0.5 is added for mathematical convenience. Dividing this by n gives the mean squared error or MSE: L(f,D)=1

2nn∑i=1[f(xi)-yi]2 The task is to find a function f that minimizes the loss function on the training dataset while generalizing well to unseen data-points. Since the class of functions is so huge, we usually choose a more tractable set. Almost any ML algorithm can be understood in terms of four components: • Model• Loss function• Optimization• Evaluation We will study a specific approach called linear regression. 3. Linear Regression 3.1. Model When f is assumed to be a linear function, the resulting solution approach is called linear regression: f(x)=wTx=w1x1+⋯+wdxd where w∈Rd is called the weight vector. We also call f a linear model. For a given data-point-label pair (xi,yi), f(xi) is called the predicted label and yi is the true label. For all data-points, the predicted label vector can be expressed as: y=XTwExpanded as: y=a

xT1w

⋮

xTnw

where, y∈Rn. 3.2. Loss Function The SSE loss function with a linear model expressed in three different but equivalent forms: Vector-scalar form L(w)=1

2n∑i=1[wTxi-yi]2 Vector-vector form If y=XTw, we have: L(w)=1

2||y-y||2 Matrix-vector form L(w)=1

2||XTw-y||2 An visualization of the squared loss and its contours for w∈R2:

L(w1,w2)w1w2L(w)=(w1-1)2+(w2+1)2+1w=a

1

-1

• The height of the surface above the w1-w2 plane is the value of the loss function.• The SSE loss function is convex. 3.3. Optimization The task is to find a w that minimizes the loss: w=

min

w 1

2n∑i=1[wTxi-yi]2 The SSE loss function L(w) is convex. Hence, all its local minima are global minima. 3.3.1. Gradient The gradient of the SSE is given as follows: ∇L(w)=a

∂L(w) ∂w1

⋮

∂L(w) ∂wd

Vector-scalar form ∇L(w)=n∑i=1[wTxi-yi]xi Matrix-vector form ∇L(w)=XXTw-Xy 3.3.2. Normal equations The system linear equations equations below are called the normal equations: XXTw=Xy This system is consistent for any choice of X and y. One special solution is given by: w=(XT)†y

Why do we need the pseudo-inverse? (out of syllabus, can be skipped): Consider the system: Ax=b If Ax=b is not consistent, you can still hunt for an approximate solution by looking for x that minimizes ||Ax-b||2. In other words, we are trying to get as close to b as possible: Ax≈b The resulting solution is given using the pseudo-inverse of A: x=A†b In the linear regression setting, A=XT,x=w,b=y: XTw≈y The solution is given by: w=(XT)†y If rank(X)=d, then the pseudo-inverse of XT can be written as: (XT)†=(XXT)-1X Note that the pseudo-inverse is defined for all matrices. For more details, refer to Moore Penrose inverse. If Ax=b is consistent, A†b gives the solution that has the least norm.

(XT)† is the pseudo-inverse of XT and is a d×n matrix. w lies in the span of the data-points. If rank(X)<d, there are infinitely many solutions. Out of all of them, w is the solution that has the least norm. Any solution to the system can be written as w+w⟂, where w⟂ is perpendicular to the span of the data-points since: XXT(w+w⟂)=Xy Specifically, if rank(X)=d the solution is unique and is given by: w=(XXT)-1Xy w is sometimes termed as the least squares solution, since it is obtained by minimizing the SSE. 3.4. Gradient descentThe optimum weight vector can also be found using gradient descent. If w(t) represents the weight vector at time t, the update is given by: w(t+1)=w(t)-𝜂∇L(w)|w(t) Substituting the gradient: w(t+1)=w(t)-𝜂(XXTw(t)-Xy) 𝜂>0 is the learning rate. Since the objective is convex, gradient descent is guaranteed to converge for suitable choices of the learning rate 𝜂. 𝜂 is called a hyperparameter (something that you choose). 3.5. Stochastic Gradient Descent For large datasets, computing the entire gradient in one go might be costly. In such cases, a random subset (random sample) of the dataset is extracted. The approximate gradient from this subset is used in the update equation. If X′∈Rd×m represents a sample of m points: w(t+1)=w(t)-𝜂[(X′)(X′)Tw(t)-X′y] The progress of SGD is less smooth given that we are only using an approximate version the gradient. Eventually both reach the minimum.

Gradient DescentStochastic Gradient Descent 3.6. EvaluationThe model's performance is evaluated on a test dataset which is a collection of data-points not seen during training. A good performance metric is the root mean squared error (RMSE): 1

nn∑i=1(wTxi-yi)2 This has the same units as the label which the error more interpretable. 4. Geometric Perspective 4.1. Best-fit surface The geometry of the relationship between predicted label and features in linear regression takes the following form in different dimensions:

d	Space	Object	Interpretation
1	R2	Line passing through the origin	Best-fit line
2	R3	Plane passing through the origin	Best-fit plane
⩾3	Rd+1	Hyperplane passing through the origin	Best-fit hyperplane

Here is a visualization of the first two cases:

yxy=wxyx1x2y=w1x1+w2x2Each blue point here represents (xi,yi), where yi is the true label. Note that the point (xi,yi) need not lie on the hyperplane. However, the point (xi,yi) will lie on the hyperplane. 4.2. Projections Feature vectors If all the feature values for a given feature are added as components of a vector, we get a feature vector. For example, rj will have the values for the jth feature for all data-points: rj∈Rn We can now look at X in two ways: Columns made up of data-points X=a

|		|
x1	⋯	xn
|		|

,XT=a

-	xT1	-
-	xn	-

Rows made up of feature vectors X=a

-	rT1	-
	⋮
-	rTd	-

,XT=a

|		|
r1	⋯	rd
|		|

The row space of X, which is the same as the column space of XT, is the span of the feature vectors. The SSE objective can be understood as follows. Find a point in the row space of X that is closest to y:

min

w ||XTw-y||2

yXTwRowspace of XRn

The required point is the projection of y on the row space of X. This means that y-XTw is orthogonal to the row space of X: X(y-XTw)=0 This leads us back to the normal equations, XXTw=Xy. The projection of y onto the row space of X is given by (XT)†y. 5. Probabilistic Perspective We assume that yi is generated by adding a noise term to wTxi: yi=wTxi+𝜖i Assuming 𝜖i∼N(0,𝜎2), we have: yi | xi∼N(wTxi,𝜎2) We can now use MLE to estimate w. Likelihood L(w)∝n∏i=1exp[-(yi-wTxi)2

2𝜎2] Log-likelihood After collecting terms that do not affect the optimization in c: l(w)=-1

2𝜎2n∑i=1(yi-wTxi)2+c Maximizing the log-likelihood is the same as minimizing the negative log-likelihood. Therefore we end up with the same optimization problem that we saw before:

min

w n∑i=1(yi-wTxi)2 Minimizing the SSE is equivalent to maximizing the likelihood under a zero mean, Gaussian noise assumption. 6. Kernel Regression6.1. LearningConsider the non-linear transformation of the features: 𝜙:Rd→RD The transformed dataset is: {(𝜙(x1),y1),⋯,(𝜙(xn),yn)} The transformed data-matrix is: 𝜙(X)∈RD×n We can now perform regression in the transformed feature space. The model is: f:RD→R f(x)=wT𝜙(x) The loss function becomes: L(w)=||𝜙(X)Tw-y||2 Since w lies in the span of the data-points, for coefficient vector 𝛼∈Rn w=𝜙(X)𝛼=a

|		|
𝜙(x1)	⋯	𝜙(xn)
|		|

a

𝛼1

⋮

𝛼n

The loss now becomes: L(w)=||𝜙(X)T𝜙(X)𝛼-y||2 If the kernel associated with 𝜙 is: k:Rd×Rd→R the kernel matrix K∈Rn×n is: K=𝜙(X)T𝜙(X) which is computed element-wise as Kij=k(xi,xj) With this, the loss function's final form is: L(w)=||K𝛼-y||2 Minimizing the L would result in: 𝛼=K†y If K is invertible, we have 𝛼=K-1y With this, w=𝜙(X)𝛼, which cannot be explicitly known since 𝜙 is not explicitly computed. 6.2. Prediction For a test data-point xtest, the predicted label is: y=𝜙(xtest)Tw Using w=𝜙(X)𝛼, we have: y=𝜙(xtest)T𝜙(X)𝛼 The product before 𝛼 is a 1×n vector: 𝜙(xtest)Ta

|		|
𝜙(x1)	⋯	𝜙(xn)
|		|

=a

𝜙(xtest)T𝜙(x1)

⋯

𝜙(xtest)T𝜙(xn)

Expanding the RHS of the predicted label: y=n∑i=1𝛼i⋅k(xtest,xi) • 𝛼i: importance of ith data-point in predicting the label for xtest• k(xtest,xi): similarity between xtest and xi