异常检测
异常检测(Anomaly detection)是一种特殊的无监督学习，但其和监督问题有些类似之处。
问题动机
从下图可以看出，对训练集建立模型后，输入$x_{test}$，通过概率来判断它是否异常。
异常检测的运用：
- 欺诈检测
- 工业生产领域
- 检测数据中心的计算机
高斯分布
就是正态分布，因为其性质和异常检测的性质差不多，由下图可以很明显看出，样本集中的位置同样也是高斯分布中概率（面积）较大的位置。
参数估计要做的则是确定高斯分布的参数，具体而言就是确定$\mu$和$\sigma^{2}$
- 均值：$\mu=\frac{1}{m} \sum_{i=1}^{m} x^{(i)}$
- 方差：$\sigma^{2}=\frac{1}{m} \sum_{i=1}^{m}\left(x^{(i)}-\mu\right)^{2}$
算法：
第一步：选取你认为能够指示出异常例子的特征$x_{i}$
第二步：拟合参数 $\mu_{1}, \dots, \mu_{n}, \sigma_{1}^{2}, \dots, \sigma_{n}^{2}$
第三步：给定一个新的输入，计算$p(x)=\prod_{j=1}^{n} p\left(x_{j} ; \mu_{j}, \sigma_{j}^{2}\right)=\prod_{j=1}^{n} \frac{1}{\sqrt{2 \pi} \sigma_{j}} \exp \left(-\frac{\left(x_{j}-\mu_{j}\right)^{2}}{2 \sigma_{j}^{2}}\right)$
也就是根据不同的特征，计算出每个特征的概率，再将所有概率累乘起来。最后如果$p(x)<\varepsilon$，则标注为异常。
以二维特征为例：
开发和评估异常检测系统
前面所提到的内容都是在只有正常样本（y=0，normal）的情况下训练的吗，也就是无监督学习。但如果你还有异常样本（y=1，anomalous），则可以用于评估算法的准确性。而且，当为样本选择特征时，如果不确定是否该纳入某一个特征，可以分别在两种情况下进行训练，在验证集上分别评估效果，从而决定是否纳入该特征(模型选择问题)。
假设现在你有一些带标签数据，即含有正常样本和异常样本。可以把数据集划分为训练集、交叉验证集和测试集。
- 数据集尽量都为正常样本
- 异常样本放入交叉验证集和测试集中。
举个例子：飞机引擎，10000个正常引擎，20个有瑕疵的引擎。把正常引擎按60%、20%、20%的比例划分为训练集、CV和测试集。同时把瑕疵引擎平均分配到CV和测试集中。
用6000个正常引擎数据拟合出概率分布$p(x)$。
推广到一般情况下
- 利用训练集来拟合出概率分布p(x)
- 将CV中的x输入p(x)，设置好阈值$\varepsilon$，从而预测出结果y
- 根据y，计算TP、FP、FN、TN。准确率和找回率，计算F1分数
- 调整$\varepsilon$直到找到最高F1的函数作为最优拟合模型
- 把测试集代入最优拟合模型。
异常检测 vs 监督学习
在有标签的情况下，异常检测和监督学习具有相似之处，但仍然有许多明显的差别。从图中可以看出，如果样本中含有大量的负样本（y=0，正常样本），少量正样本（y=1，非正常样本）。那么常使用异常检测；而当正样本数量和负样本数量都很多时，采用监督学习。
在用途上也略有不同：
选择要使用的功能
在应用异常检测之前，有一个很重要的是就是选择合适的特征。下面介绍几个常用的方法：
- 特征不服从高斯分布
如果特征不服从高斯分布，那就需要通过一些转换方法（比如取对数或是开根号）来构造出符合高斯分布的样子。
- 异常检测误差分析
也可以尝试用有标签的样本，先选择一个比较原始的特征，计算出$p(x)$，在验证集上验证，找到不符合验证结果的样本，观察它的特征，看看能否构建出新的特征，从而能够达到区分的目的。
例如下图中在只有特征$x_{1}$的情况下，很难看出绿色样本是异常样本。
此时对可以对这个绿色样本进行分析，看能不能构建出一个特征$x_{2}$，把这个异常样本给检测出来：
以数据中心的计算机为例：
通常不会选取值特别大或者特别小的特征。
如果突然我怀疑一台计算机陷入了死循环，那么$x_{3}$的数值会变得很大而$x_{4}$的数值则基本不变。那么我可以通过设置其它特征$x_{5}$和$x_{6}$来判断是哪台计算机出现了该问题。
多变量高斯分布
对比单元高斯分布，多元高斯分布在处理某些问题上具有优势。
以数据中心的计算机为例：
我们用到CPU负载和内存使用两个特征，如果使用单元高斯分布，则分别对这两个特征训练出p(x)，再相乘得到最终结果。反映在左图中，其概率的范围应该是粉红色圈。
但事实上，我们知道CPU负载和内存的使用之间的关系应该呈现出左图蓝色线圈那样的正线性关系。具体来说，如果此时有一个异常样本点——小绿叉，根据单元高斯分布计算出的结果，小绿叉落在的粉红色线圈范围是概率较高的范围，也就是会被判定为正常样本（从右图也可以看出）。但这显然不符合真实情况。
要解决这个问题，第一种方法是上一节说过的，可以通过构建新的特征，比如这里可以用x3=x1/x2。还有一种方法就是利用多元高斯分布。
多元高斯分布考虑了每两个特征之间可能存在的关系。
而多元高斯分布公式：
其中，粉色圈内的表示行列式。
在多元高斯分布公式中，$\Sigma$表示的是协方差矩阵，衡量的是方差，也就是$x_{1}$和$x_{2}$之间的变化量。其中对角线上元素上表示维度之间的方差。
从下面的图中可以看出，当对角线元素相等时，图像的投影为圆形。而当对角线元素不等时，投影为椭圆。
非对角的元素表示维度之间的协方差，以下是为正值的情况。
如果非对角线的元素为负值：
我们还可以改变$\mu$值，即移动峰值所在位置：
使用多变量高斯分布的异常检测
以下是多变量高斯模型的计算过程：
可以看出计算过程和之前的原始模型（单元高斯分布模型）：
$p(x)=p\left(x_{1} ; \mu_{1}, \sigma_{1}^{2}\right) \times p\left(x_{2} ; \mu_{2}, \sigma_{2}^{2}\right) \times \cdots \times p\left(x_{n} ; \mu_{n}, \sigma_{n}^{2}\right)$
有相似的地方。其实只要把多元高斯分布中的$\Sigma$非对角线元素全部改为0，就消除了不同纬度的相关性，得到的就是原始模型了。
- 原始模型和多变量高斯分布模型比较
多元高斯分布模型的优点在于能够自动找到不同维度之间的关系；而原始模型的优点在于计算效率高，适用于维度小或是样本少的情况。值得注意的是多元高斯分布模型的$\Sigma$必须可逆，所以必须满足m>n（NG建议m>=10n），而且维度之间必须是线性无关的。
推荐系统
问题规划
后面几个小节都会通过这个预测电影评分的例子来讲解，目的是预测左下角表格中’?’的评分
基于内容的推荐算法
假设我们已经知道了衡量电影类型的属性，$x_{1}$和$x_{2}$。再添加一个偏置，即可以用三个特征来表示一个样本，例如《Love at last》的特征就是[1 , 0.9 , 0]。
对于每个样本而言，接下来就需要求出参数$\theta^{(j)}$（单个用户j的参数向量），再通过$\left(\theta^{(j)}\right)^{T} x^{(i)}$即可求出结果。以第一个粉红色圈圈为例，假设我们已知它的参数$\theta^{(1)}$，那么就能预测出评分为4.95。
那么如何求出参数$\theta^{(j)}$呢？
这相当于一个线性回归问题：
得到优化目标之后，可以使用梯度下降法、BFGS等方法来进行优化。
使用基于内容的推荐算法的前提是，我们已经有了用于描述算法的不同特征，这个例子中，就是用了描述电影成分的$x_{1}$和$x_{2}$。但是大多数情况下，我们不具有这些特征时又应该怎么做呢？
协同过滤
特征学习：学习算法能自动习得所需要的所有特征。这个和上一节中学习参数$\theta$放在一起，有点类似于先有蛋还是先有鸡的问题。
从图中可以得出，需要知道每个用户对于不同类型电影的喜爱程度，从而计算出电影含有爱情的成分$x_{1}$和含有动作$x_{2}$的成分。
对比之前求$\theta$的步骤如下：
那么到底是先计算$\theta$还是先计算$x_{j}$呢？
简单来说，就是先猜测一个$\theta$值，然后不断迭代，从而使得参数和特征都收敛于某个最终值。
协同过滤算法
除了上个例子中的反复计算特征和参数的方法，我们还可以把特征和参数放在同一个优化目标中计算。实际操作就是把前面提到的两个优化目标放在一起，因为他们本质上也是针对那些被用户评分了的电影（即r(i,j)=1）。
值得注意的是，因为协同过滤算法是自动学习参数和特征，所以不需要像以前一样手动去添加偏置项。可以理解为如果算法需要，他会自己去计算出这一项。
矢量化：低秩矩阵分解
我们可以把用户对电影的评分的表格记录成矩阵的形式。
而我们的预测矩阵应该和矩阵Y中的值差不多
具体而言，可以把预测矩阵看成是由对每个特征向量转秩后放入矩阵x中，每位用户对某一电影类型的喜好放在矩阵$\Theta$中：
实施细节：均值规范化
如果多了一位用户Eve，她还没对任何电影做出过评分。那么应该如何预测她的评分呢？
如果我们仍然使用之前说过的方法来计算$\theta$和$x$，那么显然式子中的前两项为0，而只需要最后的正则项，又由于正则化项的性质可知（使得参数接近0），在没有数据时，根本不存在过拟合情况。最后一项中$\theta^{(5)}=0$。再根据$\left(\theta^{(5)}\right)^{T} x^{(i)}=0$可以得到上图中我们对Eve评分的预测值全为0，这显然没有意义。
为了解决这个问题，我们引入均值化。
上图中$\mu$为每一行的平均值，再用$Y-\mu$得到右边的矩阵。
这样在预测评分时，只需要把$\mu$加回去即可，既不会影响已经评分过了的用户，也使得还会评分的用户的预测值不会为0。
