前言

完结撒花！！！但是感觉只是了解了部分算法的思想，具体的实现还得找东西练一练。

该篇笔记包括：

1. 第十五章————异常检测
2. 第十六章————推荐系统
3. 第十七章————大规模机器学习
4. 第十八章————图片OCR

视频链接：[中英字幕]吴恩达机器学习系列课程

一、异常检测(Anomaly Detection)

1. 问题动机

在正常和异常的数据集都很大的时候，我们可以使用监督学习的算法，对正常类别以及出现各种异常类别进行区分。

但是，当异常的数据集较小而且异常种类很多时，监督学习很难对异常有明确的感觉，我们更倾向于使用接下来要提到的异常检测算法。

2. 异常检测算法

2.1 数据划分

已知数据集有较大量的正常样本，以及少量异常样本，例如：10000正常样本，20异常样本。我们将其划分为：

1. 训练集：6000正常样本
2. 验证集：2000正常样本，10异常样本
3. 测试集：2000正常样本，10异常样本

2.2 算法描述

给定训练集$(x^{(1)},x^{(2)},...,x^{(m)})$，样本的每一特征都互相独立且满足正态分布，即$x_j\sim N({\mu }_j,{\sigma }_j^2)$

得到样本每个特征的均值和方差：

$${\mu }_j=\frac{1}{m}\sum _{i=1}^m{x}_j^{(i)}$$

$${\sigma }_j^2=\frac{1}{m}\sum _{i=1}^m(x_j^{(i)}-{\mu }_j{)}^2$$

给定需要预测的样本$x$，计算该样本在已有均值和方差的情况下出现的概率，也就是正常的概率为：

$$p(x)=p(x_1;{\mu }_1,{\sigma }_1^2)\times p(x_2;{\mu }_2,{\sigma }_2^2)\times ...\times p(x_n;{\mu }_n,{\sigma }_n^2)=\prod _{j=1}^{n}p(x_j;{\mu }_j,{\sigma }_j^2)$$

该式子成立的隐含条件为样本的每一个特征互相独立

我们人为设置一个边界$ϵ$用于判断当$p(x)<ϵ$是，$x$为异常点

2.3 优化方法

1. 选择合适的$ϵ$：使用$F_1=2\frac{PR}{P+R}$评估异常检测系统，其中$P$为查准率，$R$为召回率，使用交叉验证集对$ \epsilon $作选择

2. 对不服从正态分布的特征$x$做操作如：$x\leftarrow log(x+C)$、$x\leftarrow x^C$ ，使其近似呈正态分布

3. 当不同特征如$x_1$和$x_2$之间有相关性时，构造特征$x_3=f(x_1,x_2)$如$x_3=\frac{x_1}{x_2}$来鉴别新样本中$x_1$和$x_2$之间的关系正常

4. 人工检查预测错误的异常点，增加对应的特征

3. 多元高斯分布的异常检测

3.1 算法描述

对每一特征都满足正态分布的训练集$(x^{(1)},x^{(2)},...,x^{(m)})$，求多元高斯分布的均值和协方差矩阵为

$$\mu =\frac{1}{m}\sum _{i=1}^m{x}^{(i)}$$

$$\Sigma =\frac{1}{m}\sum _{i=1}^m(x^{(i)}-\mu )(x^{(i)}-\mu {)}^T$$

给定需要预测的样本$x$，计算该样本是正常的概率为：

$$p(x)=\frac{1}{(2\pi {)}^{\frac{n}{2}}|\Sigma {|}^{\frac{1}{2}}}exp(-\frac{1}{2}(x-\mu {)}^T{\Sigma }^{-1}(x-\mu ))$$

3.2 与原本的模型比较

1. 多元高斯分布能自动检测到各特征之间的相关性
2. 多元高斯分布需要计算$n\times n$维矩阵$\Sigma$的逆，在$n$即特征数量很多时表现不好
3. 多元高斯分布只有在$m>n$或者说矩阵$\Sigma$可逆时可以使用(未考究)

二、推荐系统(Recommender Systems)

1. 问题描述

已知用户的数量$n_u$，作品的数量$n_m$，
$r(i,j)$表示用户$j$对作品$i$打过分，$y^{(i,j)}$表示用户用户$j$对作品$i$打的分，可记作$n_m\times n_u$维矩阵$Y$
$x^{(j)}$表示作品$j$的特征，可记作$n_m\times n$维矩阵$X$，$n$为特征的数量
${\theta }^{(i)}$表示用户的偏好，即$({\theta }^{(i)}{)}^T{x}^{(i)}$可以用于预测$y^{(i,j)}$，可记作$n_u\times n$维矩阵$X{\Theta }^{1}T$
那么$X{\Theta }^T$可用于预测$Y$

1. 已知用户对部分作品的打分和作品的的特征，求用户的偏好，预测用户对其他作品的打分
2. 已知用户对部分作品的打分和用户的偏好，推断作品的特征

2. 基于内容的推荐算法

基于内容的推荐算法，适用的问题是：
已知用户对部分作品的打分和作品的的特征，求用户的偏好，预测用户对其他作品的打分

基于内容的推荐算法本质是梯度下降求解线性回归的问题，优化目标为

对于每个用户$j$，找到${\theta }^{(j)}$，最小化损失函数如下

$$J({\theta }^{(j)})=\frac{1}{2}\sum _{i:r(i,j)=1}(({\theta }^{(j)}{)}^T{x}^{(i)}-y^{(i,j)}{)}^2+\frac{\lambda }{2}\sum _{k=1}^n({\theta }_k^{(j)}{)}^2$$

由于每个用户之间互不相关，可以对每个用户的优化目标的加和作为总的优化目标，即最小化

$$J({\theta }^{(1)},...,{\theta }^{(n_u)})=\frac{1}{2}\sum _{j=1}^{n_u}\sum _{i:r(i,j)=1}(({\theta }^{(j)}{)}^T{x}^{(i)}-y^{(i,j)}{)}^2+\frac{\lambda }{2}\sum _{j=1}^{n_u}\sum _{k=1}^n({\theta }_k^{(j)}{)}^2$$

得到梯度下降的迭代式如下：

$${\theta }_k^{(j)}={\theta }_k^{(j)}-\alpha \sum _{i:r(i,j)=1}({\theta }^{(j)}{)}^T{x}^{(i)}-y^{(i,j)})x_k^{(i)}whenk=0$$

$${\theta }_k^{(j)}={\theta }_k^{(j)}-\alpha (\sum _{i:r(i,j)=1}({\theta }^{(j)}{)}^T{x}^{(i)}-y^{(i,j)})x_k^{(i)}+\lambda {\theta }_k^{(j)})whenk\ne 0$$

3. 协同过滤

同理可得，已知用户对部分作品的打分和用户的偏好，推断作品的特征可以转化为：

对于每个作品$i$，找到$x^{(i)}$，最小化损失函数如下：

$$J(x^{(i)})=\frac{1}{2}\sum _{j:r(i,j)=1}(({\theta }^{(j)}{)}^T{x}^{(i)}-y^{(i,j)}{)}^2+\frac{\lambda }{2}\sum _{k=1}^n(x_k^{(i)}{)}^2$$

同理可得总的优化目标为最小化

$$J(x^{(1)},...,x^{(n_m)})=\frac{1}{2}\sum _{i=1}^{n_m}\sum _{j:r(i,j)=1}(({\theta }^{(j)}{)}^T{x}^{(i)}-y^{(i,j)}{)}^2+\frac{\lambda }{2}\sum _{i=1}^{n_m}\sum _{k=1}^n(x_k^{(i)}{)}^2$$

与基于内容的推荐算法相结合，可以在随机初始化$\Theta$或$X$的情况下，对它们依次作梯度下降，比如：

$$\Theta \to X\to \Theta \to X\to \Theta \cdots$$

或者，抽象出它们共同的优化目标，即最小化以下损失函数：

$$J({\theta }^{(1)},...,{\theta }^{(n_u)},x^{(1)},...,x^{(n_m)})=\frac{1}{2}\sum _{(i,j):r(i,j)=1}(({\theta }^{(j)}{)}^T{x}^{(i)}-y^{(i,j)}{)}^2+\frac{\lambda }{2}\sum _{j=1}^{n_u}\sum _{k=1}^n({\theta }_k^{(j)}{)}^2+\frac{\lambda }{2}\sum _{i=1}^{n_m}\sum _{k=1}^n(x_k^{(i)}{)}^2$$

在仅有用户对部分作品打分的情况下，同时求解$\Theta$和$X$，其梯度下降的迭代式为

$$x_k^{(i)}=x_k^{(i)}-\alpha (\sum _{j:r(i,j)=1}({\theta }^{(j)}{)}^T{x}^{(i)}-y^{(i,j)}){\theta }_k^{(j)}+\lambda x_k^{(i)})$$

$${\theta }_k^{(j)}={\theta }_k^{(j)}-\alpha (\sum _{i:r(i,j)=1}({\theta }^{(j)}{)}^T{x}^{(i)}-y^{(i,j)})x_k^{(i)}+\lambda {\theta }_k^{(j)})$$

4. 实现细节

1. 对矩阵$Y$作均值化，可以使模型对未曾打分的用户的预测有意义
2. 可以用$|x^{(i)}-x^{(j)}|$表示两个作品的相似程度

三、大规模机器学习(Large Scale Machine Learning)

1. 随机梯度下降、Min-Batch梯度下降和在线学习

不同于原本的批量梯度下降(Batch Gradient Descend)每次迭代需要遍历并减去每个样本的偏导数的加和，随机梯度下降(Stochastic Gradient Descend, or SGD)的步骤为：

1. 打乱数据的顺序
2. 遍历样本，每次迭代只减去一个样本的偏导数
3. 重复以上步骤直到模型收敛

注意：随机梯度下降只能使模型在最优解周围徘徊

Min-Batch梯度下降介于Batch梯度下降和随机梯度下降之间，需要选择每轮迭代使用的样本数$b$，步骤为：

1. 遍历样本，每次迭代减去$b$个样本求偏导数的加和
2. 重复以上步骤直到模型收敛

在线学习(Online Learning)应用在有不断涌入的用户流和数据流的情况，直接对每个用户提供的数据作拟合

2. 优化技巧

1. 画出学习曲线，预先检查模型是否是低偏差，是否能在大数据集的情况下被优化
2. 设定随机梯度下降的学习率$\alpha =\frac{cons{t}_1}{iterationsCounts+cosn{t}_2}$，在迭代次数增加时，学习率下降，模型会收敛到最优解
3. Map-reduce：将数据分散到多个计算机或者内核去并行处理，最后汇总到中心服务器。

四、图片OCR(Photo Optical Character Recognition)

从Photo OCR去看设计复杂的机器学习系统的一些理念

1. 将一个复杂的机器学习系统分解为流水线上多个机器学习模块。例如，将图片OCR分解为：文本检测、字符分割、字符识别。滑动窗口+监督学习实现文本检测，监督学习完成字符分割和字符识别
2. 人工数据：人工合成全新的数据 或者 在已有的数据上添加噪声
3. 上限分析(Ceiling Analysis)：人为提高某个模块的准确率，观察其对整个系统的准确率的影响，评估出最值得优化的一个模块