机器学习笔记一

写在前边，大纲基于吴恩达机器学习系列课程，以机器学习西瓜书作为补充。
大部分靠随堂记的笔记写成，所以可能概念上很不清楚
MH 2021.06.12

什么是机器学习

NULL

线性模型

LinearRegression线性回归

基于输入数据，由假设函数去预测值。

有m个数据的输入，每个数据有n个特征项。记输入数据为

$\pmb{X}=\left[ \begin{matrix} x_{11}&x_{12}&\cdots&x_{1n}\\ x_{21}&x_{22}&\cdots&x_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ x_{m1}&x_{m2}&\cdots&x_{mn} \end{matrix} \right]^T$

取列向量：

$\pmb{x_i}=[x_{i1},x_{i2},\cdots,x_{in}]^T\text{代表第i个输入数据，}x_{ij}\text{代表第i个输入数据的第j个特征}$

m个数据对应实际的输出值：

$\pmb{Y}=\left[ \begin{matrix} Y_1&\cdots&Y_m \end{matrix} \right]^T$

假设函数是输入项的线性组合，记$h_{\theta}$为假设函数即：

$\begin{aligned} & h_{\theta}(\pmb{x}) = \pmb{\theta}^T\pmb{x}+b \\ & \pmb{\theta} = \left[ \begin{matrix} \theta_1&\cdots&\theta_j \end{matrix} \right]^T \text{为系数向量} \\ & b\text{为常数} \\ & h_{\theta}(\pmb{x})\text{的值表示}\pmb{x}\text{输入时函数的预测值} \\ \end{aligned}$

我们也可以把常数归入系数中去，实际上吴恩达的课程就是这么做的：

$\begin{aligned} \pmb{X} & =\left[ \begin{matrix} x_{10}&x_{11}&\cdots&x_{1n} \\ x_{20}&x_{21}&\cdots&x_{2n} \\ \vdots&\vdots&\ddots&\vdots \\ x_{m0}&x_{m1}&\cdots&x_{mn} \\ \end{matrix} \right]^T \\ \pmb{\theta} & =\left[ \begin{matrix} \theta_0&\theta_1&\cdots&\theta_n \end{matrix} \right]^T \\ x_{10} & =x_{20}=\cdots=x_{m0}=1 \\ \end{aligned}$

由此我们可以有：

$[h_{\theta}(\pmb{x})] =\pmb{\theta}^T\pmb{X}$

现在的问题是如何求出系数向量，使得假设函数能很好的去预测，一个很直观的想法就是如果假设函数能很好的去预测，那么同样的假设函数对训练集（train set）也应该取得很好的效果（未考虑 过拟合），而正好在高中阶段我们就已经接触过这一方面的概念，即最小二乘法的线性规划。

$\begin{aligned} y & = \hat{a}x+\hat{b} \\ \hat{a} & = \frac{\sum_{i=1}^m{y_i(x_i-\bar{x})}}{\sum_{i=1}^m{x_i^2}-\frac{(\sum_{i=1}^m{x_i})^2}{m}} \\ \hat{b} & = \frac{\sum_{i=1}^m{y_i-\bar{a}x_i}}{m} \end{aligned}$

其中的原理是定义了一个距离函数，最小二乘法能让该距离函数的取值最小。我们也定义一代价函数（cost function）

$\begin{aligned} J(\theta_0,\theta_1,\cdots,\theta_n) & =\frac{1}{2m}\sum_{i=1}^m{(h_{\theta}(\pmb{x_i})-y_i)^2} \\ & = \frac{1}{2m}(\pmb{\theta}^T\pmb{X}-\pmb{Y})^T(\pmb{\theta}^T\pmb{X}-\pmb{Y}) \\ & = \frac{1}{2m}(\pmb{X}^T\pmb{\theta}-\pmb{Y})^T(\pmb{X}^T\pmb{\theta}-\pmb{Y}) \\ \end{aligned}$ $\pmb{\theta}\text{使得代价函数最小时取得的值}\quad\pmb{\theta}=\min_{\pmb{\theta}}(J(\theta_0,\theta_1,\cdots,\theta_n))$

正定方程求解

$\frac{\partial J}{\partial\pmb{\theta}}=\pmb{X}^T(\pmb{X}\pmb{\theta}-\pmb{Y})/m\\$

取极值时，导数为0，如果对于凸函数，为极小值点，此时有：

$\pmb{\theta}=(\pmb{X}^T\pmb{X})^{-1}\pmb{X}^TY$

要求$\pmb{X}^T\pmb{X}$为满秩矩阵

但是也可以不满秩，在Otcave中可以使用pinv求

梯度下降法求解

梯度是函数变化最快的点，负梯度是下降最快的方向，对于一个凸函数，我们沿着其负梯度一路走下，肯定能到达一个局部最优点，对于只有一个谷底的凸函数，我们一定能到达最优点。
由此得到一个迭代式

$\theta_j=\theta_j-\alpha\frac{\partial J}{\partial\theta_j}=\theta_j-\frac{\alpha}{m}\sum_{i=1}^m{(h_{\theta}(\pmb{x_i})-y_i)x_{ij}}$

$\alpha$为学习率，只要学习率足够小，$J$每次迭代都会变小。选择合适的学习率很重要，太大反复，太小太慢。

迭代退出条件可设置为结果小于某一值或者自己设置步数，注意的是不能随时更新系数的值，要等待所有新系数的都被计算出来后才能更新

FeaturingScalling特征缩放

使得开始时特征的数量级在差不多相近的水平上，加快收敛

最大最小归一化：$x_i=\frac{x_i-min}{max-min}$
均值归一化：$x_i=\frac{x_i-\mu}{max-min}$
标准化：$x_i=\frac{x_i-\mu}{\sigma}$

LogisticRegressionClassification逻辑回归分类问题

考虑一个分类问题，我们并不关心预测的值是什么，而只关心它是不是。如对于一个二分类问题，其输出只有是与不是。在这类问题中：

有m个数据的输入，每个数据有n个特征项

$\pmb{xi}=[x{i1},x{i2},\cdots,x{in}]^T$代表第i个输入数据，$x_{ij}$代表第i个输入数据的第j个特征。其中$x_i0 = 1$

$\pmb{X}=\left[ \begin{matrix} x_{10}&x_{11}&\cdots&x_{1n}\\ x_{20}&x_{21}&\cdots&x_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ x_{m0}&x_{m1}&\cdots&x_{mn} \end{matrix} \right]^T$

m个数据对应实际的输出值:

$\pmb{Y}=\left[ \begin{matrix} y_1&\cdots&y_m \end{matrix} \right]^T ,\quad y\in\{0,1\}$

如何开发一个算法使得其能正确的分类呢。考虑上面的线性回归，我们可以把预测值与是与否联系起来，如是设置一个一个边界，在靠边界区分。西瓜书使用了“广义线性模型”，寻找一个单调可微函数将分类任务的真实标记与预测值联系起来。（为什么一定要单调可微）

对二分类问题，记z为预测值，y为标记值，采用阶跃函数

$y=\begin{cases} 0 & z<0 \\ 0.5 & z=0 & \text{此时为临界值，可任意判别} \\ 1 & z>0 \end{cases}$

但阶跃函数在0点不可微，所以要找一个代替函数

$g(x)=\frac{1}{1+e^{-x}}\quad g(x)\in[0,1]$

Sigmoid函数

$h_{\theta}(\pmb{x})=g(\pmb{\theta}^T\pmb{x})=\frac{1}{1+e^{-\theta^T\pmb{x}}}\\$ $P(y=1|\pmb{x};\pmb{\theta})=h_{\pmb{\theta}}(\pmb{x}) ;\quad P(y=0|\pmb{x};\pmb{\theta})=1-h_{\pmb{\theta}}(\pmb{x})$

又：

$y=\frac{1}{1+e^{-x}}\rightarrow x=\ln{\frac{y}{1-y}}$ $\Rightarrow\theta^T\pmb{x}=\ln{\frac{P(y=1|\pmb{x};\pmb{\theta})}{P(y=0|\pmb{x};\pmb{\theta})}}$

那么代价函数就不能使用LinearRegression一样的代价函数了，如果这么去使用会得到一个波浪型的函数图像，为非凸函数，存在多个局部最小值。
考虑到这是个概率问题，且要确定的是参数，在《概率论与数理统计》第7章参数估计中有依样本均值估计总体的方法。

最大似然估计法

若总体$X$的分布形式$p(x;\theta)$已知，其中$\theta\in\Theta$为未知参数，$\Theta$是$\theta$可能的取值范围。

$X_1, \cdots, X_m$来自是来自总体的样本，

其值为$x_1, \cdots, x_m$，

称$L(\theta)=\Pi_{i=1}^mp(x_i;\theta)$为参数$\theta$的似然函数。

很容易看出似然函数其实就是$X_1,\cdots,X_m$一起发生的可能性，即联合概率。很直观的，如果我们观察到了这些样本值，就很有把握去说能使得似然函数取最大值的，参数$\theta$是最好去符合总体的参数。

对应LogisticRegression问题，训练集对应的值为$\pmb{Y}$。问题转为

$\begin{aligned} L(\pmb{x_1},\pmb{x_2},\cdots,\pmb{x_m};\pmb{\theta}) & =\max_{\pmb{\theta}\in\pmb{\theta}}{\Pi_{i=1}^mp(\pmb{x_i};\pmb{\theta})}\\ p(\pmb{x_i};\pmb{\theta}) & =(1-h_{\theta}(\pmb{x_i}))^{1-y_i}\cdot h_{\theta}(\pmb{x_i})^{y_i},\quad y_i\in\{0,1\}\\ \end{aligned}$

很明显$yi$与$h{\pmb{\theta}}(\pmb{x_i})$为0-1分布

而最大似然函数的求解方法
三步走

$\begin{aligned} L(\pmb{\theta})&=\Pi_{i=1}^mp(\pmb{x_i};\pmb{\theta})\\ \ln{L(\pmb{\theta})}&=\sum_{i=1}^mp(\pmb{x_i};\pmb{\theta})\\ &=\sum_{i=1}^m\{\ln[1-h_{\theta}(\pmb{x_i})]\cdot{(1-y_i)}+\ln[h_{\theta}(\pmb{x_i})]\cdot{y_i}\}\\ \frac{\partial\ln{L(\pmb{\theta})}}{\partial\theta_j}&=0,\quad j=0,1,2,3,\cdots,n \end{aligned}$

我们先对$h_{\theta}(\pmb{x})=g(\pmb{\theta}^T\pmb{x})=\frac{1}{1+e^{-\theta^T\pmb{x}}}$求导看看

$\begin{align} \frac{\partial\{\ln[1-h_{\theta}(\pmb{x_i})]\cdot{(1-y_i)}\}}{\partial\theta_j}&=\frac{1-y_i}{1-h_{\theta}}\frac{-x_{ij}e^{-\pmb{\theta}^T\pmb{x_i}}}{(1+e^{-\pmb{\theta}^T\pmb{x_i}})^2}\\ &=\frac{(1-y_i)(1+e^{-\pmb{\theta}^T\pmb{x_i}})}{e^{-\pmb{\theta}^T\pmb{x_i}}}\frac{-x_{ij}e^{-\pmb{\theta}^T\pmb{x_i}}}{(1+e^{-\pmb{\theta}^T\pmb{x_i}})^2}\\ &=\frac{(y_i-1)x_{ij}}{(1+e^{-\pmb{\theta}^T\pmb{x_i}})} \end{align}\\ \frac{\partial\ln[h_{\theta}(\pmb{x_i})]\cdot{y_i}}{\partial\theta_j}=\frac{y_ix_{ij}e^{-\pmb{\theta}^T\pmb{x_i}}}{(1+e^{-\pmb{\theta}^T\pmb{x_i}})}\\ \frac{\partial\ln{L(\pmb{\theta})}}{\partial\theta_j}=-\sum_{i=1}^m\{[h_{\theta}(\pmb{x_i})-y_i]x_{ij}\}$

定义cost function$=-y\ln{h{\theta}}-(1-y)\ln(1-h{\theta})$
$J=\frac{1}{m}\sum_{i=1}^{m}cost_i$
可用梯度下降法，不断重复：

$\begin{align} \theta_j&=\theta_j-\alpha\frac{\partial J}{\partial\theta_j} \tag 1\\ \frac{\partial J}{\partial\theta_j}&=\frac{1}{m}\sum_{i=1}^m\{[h_{\theta}(\pmb{x_i})-y_i]x_{ij}, \; j=0,1,2,\cdots,n \tag 2 \end{align}\\$

即有$\pmb{\theta}=\pmb{X}^T[h_\theta-\pmb{Y}]/m$

Overfitting过度拟合

无法泛化。
解决方法：

减少变量个数
正则化，加入惩罚项(缩小某些不重要项的权重？)

过度拟合时，加入惩罚项，那么修改代价函数

RegulaziedLinearRegression

$J=\frac{1}{2m}\left[\sum_{i=1}^m[h_\theta(\pmb{x_i})-y_i]^2+\lambda\sum_{j=1}^n\theta_j^2\right]\\$

$\lambda$称为正规化参数
对梯度下降法：

$\begin{cases} \theta_0=\theta_0-\frac{\alpha}{m}\sum_{i=1}^m{(h_{\theta}(\pmb{x_i})-y_i)x_{i0}} \\ \begin{aligned} \theta_j & =\theta_j-\frac{\alpha}{m}\left\{\sum_{i=1}^m[h_\theta(\pmb{x_i})-y_i]x_{ij}+\lambda\theta_j\right\} \\ & = \theta_j(1-\frac{\alpha\lambda}{m})-\frac{\alpha}{m}\sum_{i=1}^m{(h_{\theta}(\pmb{x_i})-y_i)x_{ij}} \\ & (j=1,2,\cdots,n)\\ \end{aligned} \\ \end{cases}$

对正则方程，有解析求解法，这里直接给出结果：

$\pmb{\theta}=(\pmb{X}^T\pmb{X}+\lambda\pmb{L})^{-1}X^T\pmb{Y}$

其中：

$\pmb{L}=\left[ \begin{matrix} 0&0&\cdots&0\\ 0&1&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&1 \end{matrix} \right]$

并且不加证明的给出矩阵$\pmb{X}^T\pmb{X}+\lambda\pmb{L}$一定是可逆的

RegulaziedLogisticRegression

$J=-\frac{1}{m}\sum_{i=1}^{m}[y_i\ln{h_{\theta}(\pmb{x_i})}+(1-y_i)\ln(1-h_{\theta}(\pmb{x_i})]+\frac{\lambda}{2m}\sum_{j=1}^n\theta_j^2$