前言

这两天刷了四章视频，再来复盘一下：

第十一章————机器学习系统设计
第十二章————支持向量机
第十三章————K-Means算法
第十四章————主成分分析法

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

一、机器学习系统设计

快速构建一个较为简单的模型，然后对模型进行验证，再决定下一步应该怎么优化，而不是过早地去优化。
在引入新的想法时，可对有无引入该想法地不同模型作验证，由单一指标确定引入新想法是否有效
在对偏斜类（或者不对称类）作误差评估时，应该考虑到查准率(Percision, or P)和召回率(Recall, or R)，定义$F = 2\frac{PR}{P+R}$，通过比较$F$值选择模型保证两者处于较高的水平
在模型低偏差的情况下，增大数据集保证低方差，能有效提高模型效能。

二、支持向量机(Support Vector Machine, or SVM)

1. 逻辑回归的局限性

在分类问题中，当两个类别之间间隔较大时，我们能够得到许多不同的决策边界将其正确划分。但是不同的决策边界之间也有优劣性：
当决策边界与样本点相隔很近时，新的样本稍微有点不同就可能导致模型对其错误分类，也就是模型的泛化性不强。

因此，我们的优化目标就是找到一个最优决策边界，使得样本点到决策边界的间隔最大。

为什么逻辑回归不能得到最优决策边界

我们知道逻辑回归的损失函数为

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

当模型已经能够正确分类时，前一项几乎为0，我们的的优化目标就是最小化后一项，即最小化$\lambda \sum_{j=1}^n \theta_j^2 = \lambda | \theta |^2$

在逻辑回归中，决策边界为$\theta^T x = 0$，那么$\theta = (\theta_0, \theta_1, …, \theta_n)$为决策边界的法向量。

二维的例子就是，当$\theta = (0, A, B)$，决策边界为直线$Ax + By = 0$时，直线方向向量$l = (-B, A)$与向量$\theta$互相垂直。

那么样本点到决策边界的间隔可表示为向量$x$在向量$\theta$上的投影的绝对值，记投影

$p = \| x\| cos<\theta, x>$

其中$cos<\theta, x>$为向量$\theta$和向量$x$之间夹角的cos值。

决策边界的两边分别满足，$\theta^T x \ge 0$和$\theta^T x \lt 0$，又$\theta^T x = | \theta | | x| cos<\theta, x>$，得到

$ | \theta | p\ge 0$ 和 $ | \theta | p \lt 0$

这是$p$和$|\theta|$之间的限定关系，可知$p$的变化对$|\theta|$的减少没有什么帮助，于是逻辑回归自然就不会选择$p$更大的结果，也就是不会选择最优决策边界。

2. SVM的引入

由1可知，如果改变$p$和$|\theta|$之间的限定关系为

$ | \theta | p\ge 1$ 和 $ | \theta | p \lt -1$

为了使$|\theta|$减小，模型就会自动地去使$p$的绝对值增大，即选择最优决策边界。

为了实现这一目标，我们需要在原先的逻辑回归上做些手脚，修改损失函数为：

$J(\theta) = C\sum_{i=1}^m [y^{(i)} cost_1(\theta^T x^{(i)}) + (1-y^{(i)})cost_0(\theta^T x^{(i)}] + \frac{1}{2} \sum_{j=1}^n \theta_j^2$

其中，

$cost_1(\theta^T x^{(i)}) 与 -\ln h_\theta(x^{(i)})$相似，但是在自变量$z$属于$(1,+\infty)$时，$cost_1(z)$的值为0

$cost_0(\theta^T x^{(i)}) 与 -\ln (1-h_\theta(x^{(i)}))$相似，但是在自变量$z$属于$(-\infty, -1)$时，$cost_0(z)$的值为0

也就是说，当$y = 1$时，我们希望$\theta^T x^{(i)} >= 1$，当$y = 0$时，我们希望$\theta^T x^{(i)} < -1$

这就是SVM之所以被叫做大间隔分类器的数学原理

3. 核函数(Kernel Function)

参考文献：详解SVM模型——核函数是怎么回事 - 知乎 (zhihu.com)

在实际问题中，我们在已有的维度无法找到一个线性的边界将两个类别划分开。所以我们需要通过一个映射关系，将低维的数据映射到高维，再从高维找到一个超平面将不同类别的样本划分。

所以核函数就是为了得到非线性决策边界，实现低维到高维映射关系且不增加运算的复杂度的函数。也有译作Kernel Trick，所有核函数本质是一种运算技巧。

一个使用频率很高的核函数是高斯核： $similarity(x_i, x_j) = exp(- \frac{\|x_i - x_j\|^2}{2\sigma^2})$

由于SVM的数学性质(未考究)，把核函数与SVM结合在一起的表现特别出色。

例如，将高斯核与SVM相结合：

定义特征$f = (f_1, f_2, …, f_m)^T$取代损失函数中的$x$，其中$f_j = similarity(x, l^{(j)})$，$l^{(j)}$为样本中的某一点，那么有

$J(\theta) = C\sum_{i=1}^m [y^{(i)} cost_1(\theta^T f^{(i)}) + (1-y^{(i)})cost_0(\theta^T f^{(i)}] + \frac{1}{2} \sum_{j=1}^n \theta_j^2$

呜呜写不下去了，不知道SVM是怎么求解的

三、K-Means算法

1. 问题描述

已知我们要将没有标签的数据分为$K$类，要怎么分才最合理？

设每个$c^{i}$为样本点$x^{(i)}$被分配到的聚类的下标
每个聚类中心的坐标为$\mu_k$
则$\mu_{c^{(i)}}$为样本点$x^{(i)}$被分配到的聚类的坐标

我们可以用样本点到其分配到的聚类中心的距离作为衡量分类合理性的标准，将问题转化为

如何最小化损失函数$J(c^{(1)}, …, c^{(m)}, \mu_1, …, \mu_K) = \frac{1}{m} \sum_{i=1}^m | x^{(i)} - \mu_{c^{(i)}}|^2$

我们也将它叫作失真代价函数(Cost Distortion)

2. 迭代过程

修改每一个$c^{(i)}$为离x$^{(i)}$最近的聚类中心的下标，$1\le i \le m$
修改每一个$\mu_k$为聚类$k$中所有点的均值，$1\le k \le K$
重复以上两个步骤直到聚类中心不变

3. 优化方法

3.1 随机初始化

不同的初始化结果会导致不同的聚类结果，我们可以选择其中损失函数最小的值作为最终的结果:

进行一定次数：随机初始化聚类中心为$m$个点中的任意$k$点

修改每一个$c^{(i)}$为离x$^{(i)}$最近的聚类中心的下标，$1\le i \le m$
修改每一个$\mu_k$为聚类$k$中所有点的均值，$1\le k \le K$
重复1、2步骤直到聚类中心不变
计算$J(c^{(1)}, …, c^{(m)}, \mu_1, …, \mu_K) = \frac{1}{m} \sum_{i=1}^m | x^{(i)} - \mu_{c^{(i)}}|^2$

从中找出$J$值最小的情况作为结果