Linear Regression

Vector dimensions:

• $w$ is $(d,1)$ (weights)
• $y$ is $(n,1)$ (targets)
• $x_i$ is $(d,1)$ (features)
• $X$ is $(n,d)$ each row is $x_i^T$

Linear regression makes predictions ${\hat{y}}_i$ using a linear function of $x_i$: ${\hat{y}}_i=w^T{x}_i$

We set $w$ to minimize the sum of squared errors: $f(w)={\sum }_{i=1}^n(w^T{x}_i-y_i{)}^2$

1. Take the derivative of $f$ and set it equal to 0 $f^{\prime }(w)=0$ gives us $w=\frac{{\sum }_{i=1}^n{x}_i{y}_i}{{\sum }_{i=1}^n{x}_i^2}$
2. Check to second derivative to make sure we have a minimizer (if double derivative is positive). $f^{\prime \prime }(w)={\sum }_{i=1}^n{x}_i^2$. As $x_i^2$ by definition must always be positive, this is a minimizer.

In d-dimensions, we minimize

$$\begin{array}{c}\begin{array}{rl}f(w)& =\frac{1}{2}\sum _{i=1}^n(w^T{x}_i-y_i{)}^2\\ & =\frac{1}{2}\Vert Xw-y{\Vert }^2\\ & =\frac{1}{2}{w}^T{X}^{T}Xw-w^T{X}^{T}y+\frac{1}{2}{y}^{T}y\\ & =\frac{1}{2}{w}^{T}Aw-w^{T}b+c\end{array}\end{array}$$

where $A$ is a matrix, $b$ is a vector, and $c$ is a scalar

The generalized version of “set the derivative to 0 and solve” in d-dimensions is to find where the gradient is zero (see calculus). We get

$$\begin{array}{c}\begin{array}{rl}\nabla f(w)& =\left[\begin{array}{c}\frac{\partial f}{\partial w_1}\\ \frac{\partial f}{\partial w_2}\\ ⋮\\ \frac{\partial f}{\partial w_d}\end{array}\right]\\ & \\ & =\left[\begin{array}{c}{\sum }_{i=1}^n(w^T{x}_i-yi)x_{i,1}\\ {\sum }_{i=1}^n(w^T{x}_i-yi)x_{i,2}\\ ⋮\\ {\sum }_{i=1}^n(w^T{x}_i-yi)x_{i,d}\end{array}\right]\\ & \\ & =Aw-b\\ & =X^{T}Xw-X^{T}y\end{array}\end{array}$$

We can fit to polynomial equations using a change of basis

Cost

Of solving equations in the form $Aw=b$

1. $O(nd)$ to form vector $b$
2. $O(n{d}^2)$ to form matrix A
3. Solving a $(d,d)$ system of equations is $O(d^3)$

Overall cost is $O(n{d}^2+d^3)$

Robust Regression

We minimize the L1-norm of residuals instead of L2-norm

$f(w)=\Vert Xw-y{\Vert }_1$

However, as the L1-norm uses the absolute function, it is non-differentiable at 0. We can use a smooth approximation of the L1-norm instead, like Huber loss:

$$h(r_i)=\{\begin{array}{ll}\frac{1}{2}{r}_i^2& |r_i|\le ϵ\\ ϵ(|r_i|-\frac{1}{2}ϵ)& \text{otherwise}\end{array}$$

Absolute error is more robust and non-convex errors are the most robust.

• Generally not influenced by outlier groups
• But it is non-convex so finding global minimum is hard

Brittle Regression

You want to minimize size of worst error across examples. For example, if in worst case the plane can crash or you perform badly on a group.

We can instead minimize the $L_{\infty }$ norm which is convex but non-smooth. This effectively minimizes the highest error (effectively Minimax regret in DUI).

The smooth approximation to the max function is the log-sum-exp function:

${\max }_i\{z_i\}\approx \log ({\sum }_i\exp (z_i))$

Penalizing Model Complexity

Optimize $score(p)=\frac{1}{2}\Vert Z_{p}v-y{\Vert }^2+p$ where $p$ is the degree of the polynomial.

Other ones also exist which replace the $p$ term with $\lambda k$ where $k$ is the estimated degrees of freedom (for polynomials, $k=p+1$). $\lambda$ controls how strongly we penalize complexity.

$\lambda =1$ is called the Akaike information criterion (AIC)

See also: regularization