机器学习笔记

# 线性回归的代价函数

$$J(\theta)=\frac{1}{2m}\sum_{i=1}^m\left(h_\theta(x^{(i)})-y^{(i)}\right)^2$$

# 梯度下降

通过梯度下降，找到$J(\theta)$的局部最优解

$repeat\;until\;convergence:$

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

# Logistic 回归

$$\left. \begin{array}{lr} h_\theta(x)=g(\theta^Tx) \\ g(z)=\frac{1}{1+e^{-z}} \end{array} \right\} \Rightarrow h_\theta(x)=\frac{1}{1+e^{-\theta^Tx}}$$

# Logistic 回归的代价函数

$$J(\theta)=\frac{1}{m}\sum_{i=1}^{m}Cost(h_\theta(x),y)$$

$$Cost(h_\theta(x),y)= \left\{ \begin{array}{lr} -\log(h_\theta(x)) \quad y=1 \\ -\log(1-h_\theta(x)) \quad y=0 \end{array} \right.$$

$P(y=1|x;\theta)$表示给定$x,\theta$后$y=1$的概率

假设预测$y=1$的概率$h_\theta(x)=1$，而$y$的真实值是$1$，那选用第一个代价函数，此时$Cost$为$0$；如果$y$的真实值是$0$，那选用第二个代价函数，此时$Cost$为$\infty$。

将$Cost$合并简化：

$$J(\theta)=-\frac{1}{m}\left[\sum_{i=1}^my^{(i)}\log h_\theta(x^{(i)})+(1-y^{(i)})\log(1-h_\theta(x^{(i)}))\right]$$

# 多元分类

对于每个$Class\;i$，将其转化为二分类问题，用上述$Logistic$回归的代价函数$J(\theta)$，结合梯度下降，训练各自的分类器$h_\theta^{(i)}(x)$，用来预测$y=i$时的概率

$$h_\theta^{(i)}(x)=P(y=i|x;\theta) \quad (i=1,2,3\dots)$$

对于一个新的输入$x$，找到最大的$h_\theta^{(i)}(x)$即可，此时的$i$便是预测的类。

# 正则化代价函数

正则化线性回归的代价函数：

$$J(\theta)=\frac{1}{2m}\left[\;\sum_{i=1}^m\left(h_\theta(x^{(i)})-y^{(i)}\right)^2+\underbrace{\lambda\sum_{j=1}^n\theta_j^2}_{Ragularization}\;\right]$$

正则化逻辑回归的代价函数和上述类似，加一个正则化项$\frac{\lambda}{2m}\sum_{j=1}^n\theta_j^2$。

# 神经网络

$\Theta_{ij}^{(k)}:$右上角的$(k)$表示神经网络第$k$层与第$k+1$层之间的参数（或者说权重），右下角的$ij$表示$a_i^{k+1}$的$i$和$x_j$的$j$。

# 多元分类

图中是一个四分类问题，训练集$(x^{(i)},y^{(i)})$，其中$x^{(i)}$表示图片的特征，$y^{(i)}$是一个四维的标签，我们想要让$h_\Theta(x^{(i)})\approx y^{(i)}$。

# 代价函数

和逻辑回归的代价函数类似，逻辑回归的代价函数$J(\theta)$（经过正则化）是

$$J(\theta)=-\frac{1}{m}\left[\sum_{i=1}^my^{(i)}\log h_\theta(x^{(i)})+(1-y^{(i)})\log(1-h_\theta(x^{(i)}))\right]+\frac{\lambda}{2m}\sum_{j=1}^n\theta_j^2$$

神经网络的代价函数$J(\Theta)$是

$$J(\theta)=-\frac{1}{m}\left[\sum_{i=1}^m\sum_{k=1}^Ky_k^{(i)}\log (h_\Theta(x^{(i)}))_k+(1-y_k^{(i)})\log(1-(h_\Theta(x^{(i)}))_k)\right]+\frac{\lambda}{2m}\sum_{l=1}^{L-1}\sum_{i=1}^{s_l}\sum_{j=1}^{s_{l+1}}(\Theta_{ji}^{(l)})^2$$

# 反向传播

一开始让$\Delta_{ij}^{(l)}=0$，用来计算$\frac{\partial}{\partial\Theta_{ij}^{(l)}}J(\Theta)$

遍历训练集的每个样本$(x^{(i)},y^{(i)})$

首先让输入层的激活函数$a^{(1)}=x^{(i)}$

运用正向传播算法

$$z^{(l+1)}=\Theta^{(l)}a^{(l)} \\ a^{(l+1)}=g(z^{(l+1)})$$

计算之后每层的激活函数$a^{(l)}\;(l=2,3,\dots,L)$

然后用样本的标签（或者说真值）$y^{(i)}$，计算输出值的误差项$\delta^{(L)}=a^{(L)}-y^{(i)}$

运用反向传播算法

$$\delta^{(l)}=(\Theta^{(l)})^T\delta^{(l+1)}.\ast \underbrace{g'(z^{(l)})}_{a^{(l)}.\ast(1-a^{(l)})}$$

计算$\delta^{(l)}\;(l=L-1,L-2,\dots,2)$，注意没有$\delta^{(1)}$，因为不需要对输入层考虑误差项

最后让$\Delta_{ij}^{(l)}:=\Delta_{ij}^{(l)}+a_j^{(l)}\delta_i^{(l+1)}$，或者写成向量形式$\Delta^{(l)}:=\Delta^{(l)}+\delta^{(l+1)}(a^{(l)})^T$

由此计算出

$$D_{ij}^{(l)}:= \left\{ \begin{array}{lr} \frac{1}{m}\Delta_{ij}^{(l)}+\lambda\Theta_{ij}^{(l)} \quad if \; j \neq 0 \\ \frac{1}{m}\Delta_{ij}^{(l)} \quad if \; j = 0 \end{array} \right.$$

而我们所需要的偏导$\frac{\partial}{\partial\Theta_{ij}^{(l)}}J(\Theta)=D_{ij}^{(l)}$

得到了神经网络的代价函数关于每个参数$\Theta_{ij}^{(l)}$的偏导项后，就可以使用梯度下降或者其他高级优化算法了。

# 梯度检测

反向传播算法可能会出现错误，因此需要用梯度检测来检验偏导，看是否近似

$$\frac{J(\dots,\Theta_{ij}^{(l)}+\epsilon,\dots)-J(\dots,\Theta_{ij}^{(l)}-\epsilon,\dots)}{2\epsilon}\approx\frac{\partial}{\partial\Theta_{ij}^{(l)}}J(\Theta)=D_{ij}^{(l)}$$

# 随机初始化

如果将所有参数都初始化为0，会造成所有单元都相等的现象。为了避免这种情况，需要对参数进行随机初始化

$$initialize \; each \; \Theta_{ij}^{(l)} to \; a \; random \; value \; in \; [-\epsilon,+\epsilon]$$

# 训练集、验证集、测试集

先使用测试集对不同的假设模型$i$得到参数$\theta^{(i)}$

$$\min_{\theta^{(i)}} J_{train}(\theta^{(i)})$$

再用验证集选择出交叉验证误差最小的模型$i$

$$\min_i J_{cv}(\theta^{(i)})$$

然后用测试集计算泛化误差

$$J_{test}(\theta^{(i)})$$

# 偏差和方差

# 模型多项式次数$d$与偏差、方差

如果训练集误差$J_{train}(\theta)$高，验证集误差$J_{cv}(\theta)$也高（图中左侧红框），则是一个偏差问题$(bias)$；

如果训练集误差$J_{train}(\theta)$低，但验证集误差$J_{cv}(\theta)$高（图中右侧红框），则是一个方差问题$(variance)$。

# 正则化参数$\lambda$与偏差、方差

通过取不同的$\lambda$值，让$J(\theta)$最小

$$\min_{\theta} J(\theta)$$

得到对应的参数$\theta$，计算在参数$\theta$下$J_{train}(\theta),J_{cv}(\theta)$的变化

$\lambda$越小，惩罚程度越小，正则化项可以忽略，可能会出现过拟合现象（正则化是为了防止过拟合现象），即对训练集的拟合效果非常好，此时$J_{train}(\theta)$很小；$\lambda$越大，惩罚程度越大，可能连训练集都不能很好地拟合，此时$J_{train}(\theta)$很大。

同理，在$\lambda$很小时，可能会出现过拟合现象，对应高方差问题$(variance)$，因此$J_{cv}(\theta)$较大；在$\lambda$很大时，可能会出现欠拟合现象，对应高偏差问题$(bias)$，因此$J_{cv}(\theta)$也较大。而中间总会有某个$\lambda$值，此时的表现刚好合适。

# 精确度和召回率

$precision:$预测为1的数据中实际为1的比例

$$\dfrac{true\;positive}{predicted\;positive}=\dfrac{true\;positive}{true\;positive+false\;positive}$$

$recall:$实际为1的数据中真正被预测为1的比例

$$\dfrac{true\;positive}{actual\;positive}=\dfrac{true\;positive}{true\;positive+false\;negative}$$

# 精确度和召回率的权衡

通过改变$threshold$，精确度和召回率会变化。具体来说，当$threshold$增大时，会有更高的精确度（预测为1的数据中实际为1的比例更大）和更低的召回率（实际为1的数据不变，但由于更加保守，预测为1的数据变少了）；当$threshold$减小时，会有更低的精确度和更高的召回率。

两者不可兼得，可以使用$\;F score\;$来评估算法（当然，也有很多其他评估方式）

$$F \; score=2\dfrac{PR}{P+R}$$

$P:precision \quad R:recall$

# 支持向量机

# 代价函数

支持向量机的代价函数和逻辑回归的代价函数类似

$$J(\theta)=\min_{\theta} C \sum_{i=1}^{m}\left[ y^{(i)}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)}) \right] + \frac{1}{2}\sum_{i=1}^{n}\theta_j^2$$

其中，$cost_1,cost_0$和$h_\theta(x)$类似，前者是分段直线，后者是曲线（参考上图）

同时，去掉了参数$\frac{1}{m}$，并从原来的$A+\lambda B$形式变为了$CA+B$形式

当$y=1$时，我们希望$\theta^Tx$不仅仅是$\geq0$，而是$\geq1$，这样$cost_1$为$0$，$A$项就为$0$，使代价函数尽量小，反之$y=0$时希望$\theta^Tx<-1$。

当得到了使代价函数$J(\theta)$最小的参数$\theta$后，带入交叉验证集/测试集的数据$x$，就能得到支持向量机的输出$h_\theta(x)$

$$h_\theta(x)= \left\{ \begin{array}{lr} 1 \quad if \quad \theta^T x \geq 0 \\ 0 \quad if \quad \theta^T x < 0 \end{array} \right.$$

# 非线性决策边界

$Predict \; y=1 \; if$

$$\theta_0+\theta_1f_1+\theta_2f_2+\theta_3f_3+\dotsb\geq0$$

以高斯核函数为例，给定一个输入$x$，得到

$$f_i=k(x,l^{(i)})=exp\left(-\dfrac{\parallel x-l^{(i)} \parallel^2}{2\sigma^2}\right)$$

其中，$l^{(i)}$是标记点，等同于训练样本点（$l^{(i)}=x^{(i)}$）；$x$可以是训练集，交叉验证集，测试集等等。

如果$x\approx l^{(i)},f_i\approx 1;$ 如果$x$距离$l^{(i)}$很远，则$f_i\approx 0$，可以理解为相似度。

如图所示，靠近$l^{(1)},l^{(2)}$的点将会预测为$1$，远离则为$0$。

# 核函数与$SVM$

对于训练样本$(x^{(i)},y^{(i)})$，可以得到$m$个$f_{j}^{(i)}=k(x^{(i)},l^{(j)})$，即

$$f^{(i)}=\left[f_{1}^{(i)},f_{2}^{(i)},\dotsb,f_{m}^{(i)}\right]^T$$

$m$为训练样本的大小，因为$l^{(j)}$标记点就是训练样本点，所以$l^{(j)}$标记点有$m$个，$f^{(i)}$为$m$维向量。

将$x^{(i)}$映射为$f^{(i)}$（描述第$i$个训练样本的特征向量由$x^{(i)}$变成$f^{(i)}$），则$\theta^Tx^{(i)}$变为$\theta^Tf^{(i)}$。

# 主成分分析$PCA$

假如要将$2$维降成$1$维，则找出使得投影误差最小的向量$u$，即点到投影后的点之间的距离。

要将$n$维降成$k$维，则找出使得投影误差最小的$k$个向量$u^{(1)},u^{(2)},\dotsb,u^{(k)}$。

同时，主成分分析$PCA$与线性回归不同，如上图所示，左边是线性回归，右边是$PCA$，蓝色线段代表各自的误差，两者的误差并不相同。

# 主成分分析算法

将数据从$n$维降到$k$维

• 首先计算协方差矩阵$Sigma$

$$Sigma=\frac{1}{m}\sum_{i=1}^{n}(x^{(i)})(x^{(i)})^T$$

$x^{(i)}\in\R^{n \times 1},Sigma\in\R^{n \times n}$

• 然后计算$Sigma$的特征向量矩阵$U$

$$U= \begin{bmatrix} u^{(1)} & u^{(2)} & \dotsb & u^{(n)} \end{bmatrix} \in\R^{n \times n}$$

$u^{(i)}\in\R^{n \times 1}$

• 取前$k$个向量组成$U_{reduce}$

$$U_{reduce}= \begin{bmatrix} u^{(1)} & u^{(2)} & \dotsb & u^{(k)} \end{bmatrix} \in\R^{n \times k}$$

• 对于一个样本$x^{(i)}\in\R^{n \times 1}$，降维后新的坐标$z^{(i)}\in\R^{k \times 1}$

$$z^{(i)}=[U_{reduce}]^T x^{(i)}= \begin{bmatrix} (u^{(1)})^T \\ (u^{(2)})^T \\ \dotsb \\ (u^{(k)})^T \end{bmatrix} x^{(i)}= \R^{k \times n} \times \R^{n \times 1} \in\R^{k \times 1}$$

# 异常检测

# 原始模型

训练集为$\{x^{(1)},x^{(2)},\dotsb,x^{(m)}\}$，样本$i$有$n$个特征$\{x^{(i)}_1,x^{(i)}_2,\dotsb,x^{(i)}_n \}$

每一种特征$x_j$都满足正态分布，计算参数$\mu_1,\dotsb,\mu_n,\sigma^2_1,\dotsb,\sigma^2_n$

特征$j$的平均值$\mu_j:$

$$\mu_j=\frac{1}{m}\sum_{i=1}^{m}x^{(i)}_j$$

特征$j$的方差$\sigma^2_j:$

$$\sigma^2_j=\frac{1}{m}\sum_{i=1}^{m}(x^{(i)}_j-\mu_j)^2$$

然后对于一个新的特征向量$x$，计算$p(x)$概率

$$p(x)=\prod_{j=1}^{n}p(x_j;\mu_j,\sigma^2_j)$$

如果概率$p(x)<\epsilon$，则$x$是不正常的样本

# 多元高斯模型

不再将多个特征视作独立分开的高斯分布，而是将$p(x)$看作一个多元高斯分布，参数$\mu\in\R^{n}$，协方差矩阵$\Sigma\in\R^{n \times n}$

# 协同过滤算法

以电影评分为例，电影$i$的特征为$x^{(i)}$，能够描述电影的特点；用户$j$的参数为$\theta^{(j)}$。$(\theta^{(j)})^T x^{(i)}$表示用户$j$对电影$i$的预测评分。

给出$x$，能通过代价函数预测$\theta$；反之，给出$\theta$，能通过代价函数预测$x$。

其中，$r(i,j)=1$表示用户$j$评价了电影$i$，$y^{(i,j)}$表示用户$j$对电影$i$的实际评分。

协同过滤算法能同时最小化参数$x$和$\theta$，其代价函数为上图中前两个代价函数的组合。

首先将参数初始化为较小的随机值（和神经网络类似），通过梯度下降等方法将代价函数最小化，可以得到参数$x$和$\theta$。如果用户$j$尚未评价电影$i$，可以通过$(\theta^{(j)})^T x^{(i)}$计算出预测的评分。

# 梯度下降

# 批量梯度下降

$$J_{train}(\theta)=\frac{1}{2m}\sum_{i=1}^m\left(h_\theta(x^{(i)})-y^{(i)}\right)^2$$

$$\theta_j:=\theta_j-\alpha\frac{1}{m}\sum_{i=1}^{m}\left(h_\theta(x^{(i)})-y^{(i)}\right)x_j^{(i)} \; (j=0,\dots,n)$$

# 随机梯度下降

在批量梯度下降算法中，每次进行迭代都需要遍历所有的训练样本，并且整个流程会进行多次上述运算。在数据很多的时候计算量会非常大，需要运用到随机梯度下降。

随机梯度下降先打乱训练样本，然后依次遍历训练样本$\left(x^{(i)},y^{(i)}\right)$，进行迭代

$$\theta_j:=\theta_j-\alpha\left(h_\theta(x^{(i)})-y^{(i)}\right)x_j^{(i)} \; (j=0,\dots,n)$$

这样，每遍历一个样本便进行了一次迭代，不需要频繁地遍历所有训练样本。

在上图中，红色是批量梯度下降的收敛过程，紫色是随机梯度下降的收敛过程。随机梯度下降的内层循环取决于训练集的大小，外层循环通常只需要进行1-10次。

# $Mini-Batch$梯度下降

批量梯度下降一次性用所有训练样本进行迭代；

随机梯度下降一次只用一个训练样本进行迭代；

而$Mini-Batch$梯度下降则一次用$b$个训练样本来迭代。