# Linear Regression

$$
h_{\theta}(x) = \theta_0 +\theta_1 x_1 +\theta_2 x_2
 = \sum_{i=0}^2 \theta_i x_i
 = \theta^T X
$$

损失函数：需要一个机制评估 $$\theta$$ 是否比较好。

$$
\min_{\theta} J(\theta) = \frac {1}{2m} \sum_{i=1}^m ( h_{\theta}(x^{(i)}) - y^{(i)} )^2 \quad  \mbox{coursera上多了个m，让迭代步长与样本数无关}  \\
$$

为何选择平方和作为错误估计函数，假设根据特征的预测结果与实际结果有误差 $$\epsilon_i$$ ，即$$y_i = \theta^T x_i + \epsilon_i$$\
一般误差 $$\epsilon_i$$ 满足正态分布，那么x和y的条件概率

$$
p(y_i | x_i;\theta) = \frac {1}{\sqrt{2\pi}\delta} \exp(-\frac{(y_i-\theta^Tx_i)^2}{2\delta^2}) \\
L(\theta) = \log \prod_{i=1}^m p(y_i | x_i;\theta) = -m \log \sqrt {2\pi} \sigma - \frac {1}{2 \sigma^2} \sum_{i=1}^m (y_i-\theta^Tx_i)^2
$$

Andrew Ng的讲义上的，它只是表示与正态分布等价，然后并没有说明为什么用最小二乘或选择正太分布。

## 正交投影与最小二乘法

最小二乘可以理解为正交投影。 MLAPP 7.3.2 Geometric interpretation（page 251）

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2F813ed00c50c46694a8969d04aa19be4132ddb68b.jpg?generation=1589383940240745\&alt=media)

$$
\hat y \in span (X) \\
\hat y = Xw \\
X^T (y- \hat y) = 0 \to X^T (y- Xw) = 0 \to w= (X^T X)^{-1} X^Ty \\
\hat y = Xw = X (X^T X)^{-1} X^Ty \\
$$

This corresponds to an **orthogonal projection** of y onto the column space of X.

[在进行线性回归时，为什么最小二乘法是最优方法？](https://www.zhihu.com/question/24095027)\
[投影矩阵与最小二乘](http://blog.csdn.net/a130098300/article/details/7661548)\
[正交性和最小二乘法](http://zhangjunhd.github.io/2014/04/11/orthogonality-and-least-squares.html)

这个几何意义，可见PRML3.1 。

求损失函数最小值，可以用梯度下降法。

## 解析解

将训练特征表示为X矩阵，结果表示为Y向量

$$
X {\theta}  - Y =
\begin{bmatrix}
(x^{(1)})^T {\theta} \\
\ldots \\
(x^{(m)})^T {\theta} \\
\end{bmatrix} 
- 
\begin{bmatrix}
y^{(1)} \\
\ldots \\
y^{(m)} \\
\end{bmatrix} 
=
\begin{bmatrix}
h_{\theta}(x^{(i)}) - y^{(i)} \\
\ldots \\
h_{\theta}(x^{(m)}) - y^{(m)} \\
\end{bmatrix} \\


J(\theta) = \frac {1}{2m} (X {\theta}  - Y )^T (X {\theta}  - Y ) = \frac {1}{2m} ||X {\theta}  - Y ||^2 \\
\frac{\partial J}{\partial \theta} = X^T( X {\theta} - Y ) =0 \\
X^T X {\theta} - X^T Y  =0 \\
\theta = (X^TX)^{-1}X^TY \\
\textbf{此解析解需要X是列满秩的，故一般求} \\
\theta = (X^TX + \lambda I)^{-1}X^TY \\
\textbf{I是单位阵，这个解形式等同于加了L2范数}
$$

若特征维度>样本数，$$X^TX$$则不会是列满秩，解析解无法求出。\
对于维度特别高的，一般会加L1范数，会产生稀疏解。此时目标函数为\
$$J(\theta) = \frac {1}{2m} ||X {\theta} - Y ||^2 + \lambda ||\theta||_1$$，一般称为LASSO

## 梯度与迹

Ng讲义上求梯度时结合了矩阵的迹。

$$
\begin{align}
\nabla_{\theta} J(\theta) & = \frac {1}{2} \nabla_{\theta} (X {\theta}  - Y )^T (X {\theta}  - Y ) \\
& = \frac {1}{2} \nabla_{\theta} (\theta^T X^T X {\theta}  - Y^T X \theta -\theta^T X^T Y + Y^T Y) \\
& = \frac {1}{2} \nabla_{\theta} tr (\theta^T X^T X {\theta}  - Y^T X \theta -\theta^T X^T Y + Y^T Y) \\
& = \frac {1}{2} [ \nabla_{\theta} tr (\theta^T X^T X {\theta} ) - \nabla_{\theta} tr ( Y^T X \theta ) - \nabla_{\theta} tr (\theta^T X^T Y ) ] \\
& = \frac {1}{2} \nabla_{\theta} tr (\theta^T X^T X {\theta} ) - \nabla_{\theta} tr ( Y^T X \theta ) \\
& = \frac {1}{2} \nabla_{\theta} tr ({\theta} \theta^T X^T X  ) - \nabla_{\theta} tr ( Y^T X \theta ) \\
& = \frac {1}{2} \nabla_{\theta} tr ({\theta} I \theta^T X^T X  ) - \nabla_{\theta} tr ( Y^T X \theta ) \\
& =  X^T X \theta  - \nabla_{\theta} tr ( Y^T X \theta ) \\
& =  X^T X \theta  - X Y^T   
\end{align}
$$

> 矩阵的迹是它的所有特征值的和
>
> [迹的几何意义是什么](https://www.zhihu.com/question/20533117)

## gradient descent

$$
\theta_j := \theta_j - \alpha \frac {\partial J(\theta)}{\partial \theta_j}
$$

按照Ng的讲义思路来，当只有一个样本时：

$$
\frac {\partial J(\theta)}{\partial \theta_j} = 
\frac {\partial }{\partial \theta_j} \frac 12 (h_{\theta}(x)-y)^2 =
(h_{\theta}(x)-y) \frac {\partial }{\partial \theta_j} (h_{\theta}(x)-y) =
(h_{\theta}(x)-y) \frac {\partial }{\partial \theta_j} \sum_{i=0}^n \theta_i x_i = 
(h_{\theta}(x)-y) x_i
$$

则

$$
\theta_j := \theta_j - \alpha (h_{\theta}(x)-y) x_i
$$

当用m个训练样本时，

$$
\theta_j := \theta_j - \alpha \sum_{i=1}^m (h_{\theta}(x^{(i)})-y^{(i)}) x_i^{(i)}
$$

## Ridge regression

就是带L2正则，可以理解为均值为0高斯分布作为先验概率：$$p(w) = \prod_j N(w_j|0,\tau^2)$$\
则MAP：

$$
\begin{align}
\arg \max_w\ &\sum_{i=1}^N \log p(y_i|x_i,w) p(w)  \\
= &\sum_{i=1}^N \log N(y_i|w_0+w^Tx_i,\sigma^2) + \sum_{j=1}^D \log N(w_j|0,\tau^2)  \\
\end{align}
$$

简化下得：$$J(w) = \frac{1}{N}\sum_{i=1}^N(y_i-(w_0+w^Tx_i))^2 + \lambda||w||_2^2$$\
解为： $$w = (X^TX + \lambda I)^{-1}X^TY$$

from MLAPP 7.5 Ridge regression (page 255)

## 贝叶斯线性回归

上面对参数加了先验，可以从**贝叶斯的角度**去看待，就成了贝叶斯线性回归。这时，在贝叶斯模型下我们需要去计算的是W的分布，而不是W的point estimation。

[https://www.zhihu.com/question/22007264](https://www.zhihu.com/question/22007264)

## 带权重的线性回归

基本假设是

* $$\min_{\theta} J(\theta) = \sum_{i=1}^m \omega_i (y_i - \theta^Tx_i)^2$$
* Output $$\theta^TX$$ &#x20;

其中假设$$\omega_i$$符合公式

$$
\omega_i = \exp(-\frac {(x_{i}-x)^2}{2\tau^2}) \\
\tau \text{是波长参数}
$$

这个假设的道理是离**要预测的X**越近的样本权重越大，越远的影响越小。\
这个公式与正态分布类似，但$$\omega_i$$不是随机变量。\
在学习的过程中，不仅要学习现行回归的参数，还是学习波长参数。

这个算法的问题在于，对于每一个要查询的点，都要重新从数据中训练一个模型出来，代价很高。

## 非线性的处理

线性回归和logistic回归中都要求数据线性，但是现实中可能会遇到数据非线性的问题，\
从本质出发，两种解决思路：

* 自变量间的非相关性： 例 $$y=w_1*x_1+w_2*x_2+ w_3*x_1*x_2$$&#x20;
* 自变量的线性变化，因变量却没有线性相关： 对自变量离散化。

[回归分析](http://nlpnoob.com/post/tong-ji-fen-xi/hui-gui-fen-xi)\
[Sparsity and Some Basics of L1 Regularization](http://freemind.pluskid.org/machine-learning/sparsity-and-some-basics-of-l1-regularization/)

[最大似然估计和最小二乘法怎么理解？](https://www.zhihu.com/question/20447622)
