Lecture 4 Least squares and Optimization

Lecture 4 Least squares and Optimization

1. 最小二乘估计

最小二乘估计(上节课没讲的)：

如果列向量都是线性无关的找到最小化残差和的$w$是：

$$\begin{aligned} \hat {\underline w}&=(X^TX)^{-1}X^Ty \\ \Rightarrow \hat {\underline y}&=X \hat {\underline w} =X(X^TX)^{-1}X^Ty \end{aligned}\tag{1}$$

其中，$(X^TX)^{-1}X^T$又叫pseudo-inverse， 伪逆。

$P_{Xy}$投影$y$到$X$上。

2. 最小二乘法分类

二分类就是把$$输入到sign函数得到其输出。

3. 优化方法

2范数或者欧几里得范数：

$$\lVert x\rVert^2_{2} = \sum^n_{i=1}x_i^2=x^Tx=<x, x>\tag{2}$$

所以：

$$\begin{aligned} arg \ min_w\lVert y-Xw\rVert^2_2 &=arg \ min_w \ (y-Xw)^T(y-Xw) \\ &=arg \ min_w (y^Ty-y^TXw-w^TX^Ty+w^TX^TXw) \\ &=arg \ min_w (y^Ty-2w^TX^Ty+w^TX^TXw) \end{aligned}\tag{3}$$

$y^TXw和w^TX^Ty$都是标量，而且是一样的。

Warmup：$f(w) = \frac{1}{2}w^2-w-\frac{1}{2}$。求导求极值点。

4. 正定矩阵

我们需要$X^TX$是可逆的。

从优化的角度来看这个问题。$X^TX$是正定的

正定矩阵定义：

$$\begin{aligned} & \text{给定一个大小为}n \times n \text{的实对称矩阵}Q ，\text{若对于任意长度为}n\text{的非零向量}x ，\text{有}x^TQx>0\text{恒成立，则矩阵}Q\text{是一个正定矩阵}\\&(positive \ definite(p.d)。\text{简记}Q>0)。\\ \\ &\text{给定一个大小为}n \times n\text{的实对称矩阵}Q ，\text{若对于任意长度为}n\text{的非零向量}x ，\text{有}x^TQx \ge 0\text{恒成立，则矩阵}Q是\text{一个半正定矩}\\&\text{阵}(positive \ semi-definite(p.s.d)。\text{简记}Q \ge 0)。 \end{aligned} \tag{4}$$

1. 详解正定矩阵的作用和凸优化

正定矩阵详解

2. 正定矩阵的性质

性质3：

对于任意矩阵$A$，那么$A^TA \ge 0 $和$AA^T \ge 0 $

5. 最优化最小二乘法

假设$X^TX > 0$,那么：$f(w)=y^Ty-2w^TX^Ty+w^TX^TXw$是凸的。

计算其导数，让其等于0来求最小值。

例如$f(w) = c^Tw=c_1w_1+c_2w_2+ \cdots+c_pw_p$

其梯度为：

$$\nabla_{w} f=\left[\begin{array}{c} c_{1} \\ c_{2} \\ \vdots \\ c_{p} \end{array}\right]=c\tag{5}$$

例如$f(w) =w^Tw=\lVert w\rVert^2_{2}=w^2_1 + w^2_2 + \cdots+ w^2_p$

$$\nabla_{w} f=\left[\begin{array}{c} 2w_{1} \\ 2w_{2} \\ \vdots \\ 2w_{p} \end{array}\right]\tag{6}$$

总结，

$$\begin{aligned} \nabla_{w} <c, w> &= c \\ \\ \nabla_{w} \lVert w\rVert^2_{2} &= 2w \end{aligned} \tag{7}$$

例子：

$$f(w) = w^TQw=\sum^p_{i=1} \sum^p_{i=1}w_iQ_ijw_j\tag{8}$$

那么对$w$的梯度有下面四种情况:

$$\frac{d\left(w_{i} Q_{i j} w_{j}\right)}{d w_{k}}=\left\{\begin{array}{ll} 2Q_{i i} w_{i} & \text { if } k=i=j \\ Q_{i j} w_{j} & \text { if } i=k \neq j \\ Q_{i j} w_{i} & \text { if } i \neq k=j \\ 0 & \text { if } k \neq i, k \neq j \end{array}\right.\tag{9}$$

这需要把$\boldsymbol{w}^TQ\boldsymbol{w}$展开来理解，下面用一个具体的例子,其中：

$$Q=\left[\begin{array}{ccc} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{array}\right] \in \mathbb{R}^{3 \times 3}$$ $$\boldsymbol{w}=\left[\begin{array}{l} w_{1} \\ w_{2} \\ w_{3} \end{array}\right] \in \mathbb{R}^{3}$$

其部分展开得：

$$\boldsymbol{w}^{T} Q \boldsymbol{w}=\left[\left(2 w_{1}-w_{2}\right) \quad\left(-w_{1}+2 w_{2}-w_{3}\right) \quad-w_{2}+2 w_{3}\right]\left[\begin{array}{l} w_{1} \\ w_{2} \\ w_{3} \end{array}\right]$$

上式,

• 第一种情况，可以结合式7中第二个式子理解，$\boldsymbol{w}_k都是变量$。
• 第二种情况，可以结合式7中第一个式子理解，$\boldsymbol{w}_k$是变量,$\boldsymbol{w}_j$是常量。
• 第三种种情况，可以结合式7中第一个式子理解，$\boldsymbol{w}_k$是变量,$\boldsymbol{w}_i$是常量。
• 不含变量$\boldsymbol{w}_k$都是常量。

所以：

$$\frac{d f}{d w_{k}}=\sum_{i=1}^{p} \sum_{j=1}^{p} \frac{d\left(w_{i} Q_{i j} w_{j}\right)}{d w_{k}} \\ =\sum_{i=1}^{p} \frac{d\left(w_{i} Q_{i j} \right)}{d w_{k}} + \sum_{j=1}^{p} \frac{d\left( Q_{i j} w_{j}\right)}{d w_{k}} \tag{10}$$

回想下简单的公式：

$$\sum_{i=1}^{N} x_{i} y_{i}=\left[\begin{array}{c} x_{1} \\ \vdots \\ x_{n} \end{array}\right]^{T}\left[\begin{array}{c} y_{1} \\ \vdots \\ y_{n} \end{array}\right]=\mathbf{x}^{T} \mathbf{y}$$

那么：

$$\nabla_{\boldsymbol{w}} f=\frac{d f}{d w_{k}}=Q\boldsymbol{w}+Q^T\boldsymbol{w}\tag{11}$$

如果$Q$是对称矩阵($Q=Q^T$):

$$\nabla_{\boldsymbol{w}} f=2Q\boldsymbol{w}\tag{12}$$

一些其它方法的证明

而$f(w)=y^Ty-2w^TX^Ty+w^TX^TXw$,其梯度为：

$$\nabla_{w} f = -2X^Ty+2X^TXw\tag{13}$$

令其为0，同样可得：

$$\begin{array}{l} X^{\top} X \hat{\underline{w}}=X^{\top} y \\ \Rightarrow \hat{w}=\left(X^{\top} X\right)^{-1} X^{\top} y \end{array}\tag{14}$$