Coursera 吴恩达机器学习入门课笔记（更新至第三课）

吴恩达在 Coursera 上的机器学习入门课的笔记。只给自己看，所以写得非常简略。

使用的是较新的 2022 版本（和之前的不太一样），双语可见 BV1Pa411X76s。

第一课

线性回归（Linear Regression）

设特征数为 $n$，样本数为 $m$。

模型：$f_{\text{w},b}(\text{x})=\text{w}\text{x}+b=\left(\sum _{i=1}^n{w}_i{x}_i\right)+b$

损失函数：

$$L(f_{\text{w},b}({\text{x}}^{(i)}),y^{(i)})=(f_{\text{w},b}({\text{x}}^{(i)})-y^{(i)}{)}^2$$

费用函数：

$$J(\text{w},b)=\frac{1}{2m}\left(\sum _{i=1}^m{(f_{\text{w},b}({\text{x}}^{(i)})-y^{(i)})}^2\right)+\frac{\lambda }{2m}\sum _{i=1}^n{w}_i^2$$

此处 $\frac{\lambda }{2m}\sum _{i=1}^n{w}_i^2$ 采用了正则化（Regularization），能使得 $w_i$ 的值减小，从而抑制过拟合（Overfitting）。

梯度下降（Gradient Descent）

$$\begin{array}{rl}\frac{\partial J(\text{w},b)}{\partial w_j}& =\frac{1}{m}\left(\sum _{i=1}^m(f_{\text{w},b}({\text{x}}^{(i)})-y^{(i)})x_j^{(i)}\right)+\frac{1}{m}{w}_j\end{array}$$

$$\begin{array}{rl}\frac{\partial J(\text{w},b)}{\partial b}& =\frac{1}{m}\sum _{i=1}^m(f_{\text{w},b}({\text{x}}^{(i)})-y^{(i)})\end{array}$$

特征缩放（Feature Scaling）

• Mean Normalization：$x^{\prime }=\frac{x-\mu }{max-min}$
• Z-Score Normalization：$x^{\prime }=\frac{x-\mu }{\sigma }$

目标是让 $x$ 尽可能趋近于 $[-1,1]$ 分布。

逻辑回归（Logistic Regression）

Sigmoid：$f(x)=\frac{1}{1+e^{-x}}$

ReLU：$f(x)=max0,x$

模型：$f_{\text{w},b}(\text{x})=\text{sigmoid}(\left(\sum _{i=1}^n{w}_i{x}_i\right)+b)$

也可以换成 ReLU。

损失函数：

$$L(f_{\text{w},b}({\text{x}}^{(i)}),y^{(i)})=\{\begin{array}{l}-\log (f_{\text{w},b}({\text{x}}^{(i)})),y^{(i)}=1-\log (1-f_{\text{w},b}({\text{x}}^{(i)})),y^{(i)}=0\end{array}$$

实际操作中，使用该损失函数比直接套用线性回归的损失函数更优。

第二课

输出层的转换函数选择

• 二元分类：$\text{Sigmoid}$
• 回归：$\text{id}$（带正负）或 $\text{ReLU}$（非负）

Softmax 回归

Softmax 回归用来解决多分类问题。

假设类别共有 $k$ 种，则 Softmax 回归的输出为一个 $k$ 维向量 $\text{x}$，$x_i$ 衡量分类为 $i$ 的相对可能性有多大。实际分类为 $i$ 的概率估计为

$$a_i=P(y=i)=\frac{e^{x_i}}{\sum _{j=1}^k{e}^{x_j}}$$

损失函数为

$$loss(a_k,y)=-\log a_y$$

交叉验证

咕了

决策树解决二分类问题

给定特征向量 $\text{x}=a_1,a_2,\dots ,a_k(a_i\in 0,1)$，估计其分类 $\hat{y}\in 0,1$。

熵：若 $p$ 为当前节点数据中第一类的占比，那么定义熵 $H(p)$ 为

$$H(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p),p\in (0,1)$$

特别地，$H(0)=H(1)=0$（这是因为 ${\log }_{2}0$ 没有定义）。可以注意到 $\underset{x\to 0}{lim}x{\log }_{2}x=0$，因此即使特殊定义 $H(0)=0{\log }_{2}0=0$ 也不会破坏函数连续性。

H(x) 的图像

信息增益：若将根节点 $root$ 分为左子树 $left$ 和右子树 $right$，记节点数据个数为 $n$，则信息增益（Information Gain，实际上就是熵减）为

$$H(p^{root})-\frac{n^{left}}{n^{root}}H(p^{left})-\frac{n^{right}}{n^{root}}H(p^{right})$$

取信息增益最大分割即可。

停止条件

停止划分的条件有几种：

• 当当前节点深度已经达到规定的最大深度时；
• 当最大信息增益小于某个阈值时；
• 当节点数据数小于某个阈值时。

One-hot 编码

对于 $a\in [1,n]\cup \text{N}$，可以将 $a$ 转化为一个长度为 $n$ 的向量 $\overrightarrow{b}=[a=1],[a=2],[a=3],\dots ,[a=n]$。可以注意到，转化后的 $\overrightarrow{b}$ 的每个元素都为 $0$ 或 $1$，并且有且仅有一个元素为 $1$（因此成为 One-hot 编码）。

对多分类问题的决策树应用 One-hot 编码，即可转化为二分类问题。

连续取值

在决策树上，对于取值为实数的特征进行分割时，可以取条件为 $x\le C$。

若当前有 $m$ 个数据，其从小到大为 $x_1\le x_2\le \dots \le x_m$，则可以考虑取 $C=\frac{x_i+x_{i+1}}{2}(1\le i\le n-1)$。

扩展到回归树

回归树和决策树类似，但其输出为一个 $y\in \text{R}$，而不是预测其分类。

类似地，可以定义回归树的信息增益为

$$D(p^{root})-\frac{n^{left}}{n^{root}}D(p^{left})-\frac{n^{right}}{n^{root}}D(p^{right})$$

其中 $D$ 为方差函数。

决策树森林

单棵决策树对数据的微小改变较为敏感。为了使其更加健壮，可以生成多棵决策树，然后收集所有决策树计算后的结果，取众数作为结果返回。

生成决策树的方式是：每次有放回抽样，抽出与数据集大小个数相等的样本（这些样本可重复），根据它们建决策树。

决策树棵数一般在 $100$ 左右，因为每增加一棵决策树，其对准确率的增加是有边际递减的。一般来讲，当超过 $100$ 之后其对性能的提升就很小了，还会减慢计算速度。

随机森林算法

仅有放回抽样构造出的决策树，在根节点附近的分类标准仍然是高度相似的。记特征数为 $n$，为了更加随机，可以在每次分割时仅随机选出 $k<n$ 个特征进行判断，取信息增益最多的那个进行分割。

一般来讲取 $k\approx \sqrt{n}$（西瓜书上据说 $k\approx {\log }_{2}n$）。

Boost

更进一步地，在每次抽样时，我们可以更有意识（更高概率地）抽出那些被当前已有决策树森林错误分类的样本。

XGBoost

XGBoost 是一个开源高效的决策树 / 回归树计算库。

决策树 Vs. 神经网络

决策树的优点：

• 适合处理天然结构化的数据。简单来说，如果数据看起来像一个表格，则适合用决策树处理。
• 训练时间短。
• 较小的决策树可能是 Human-interpretable（人类可以理解的）。

决策树的缺点：

• 不适合处理非结构化数据（图像，文本，视频，音乐等）。

神经网络的优点：

• 适合处理几乎所有类型的数据（无论是否结构化）。
• 可以和迁移学习（Tranfer learning）一起使用。
• (*) 可以更容易做到让多个机器学习模型一起配合训练。
  • 原因很复杂，暂时不展开。

神经网络的缺点：

• 训练时间长。

第三课

引入

• 无监督学习算法
  • 聚类（Clustering）
  • 异常检测（Anormaly detection）
• 推荐系统
• 强化训练

K-means 聚类算法

K-means 算法可以用来解决聚类问题。算法流程如下：

1. 随机 $k$ 个点的坐标 ${\text{p}}_1,{\text{p}}_2,\dots ,{\text{p}}_k$作为 $k$ 个簇的中心点。
2. 重复以下流程直至中心点坐标无变化：
   1. 遍历所有数据点，将每个数据点分配给离它最近的那个中心点。
   2. 将中心点坐标改为它所支配的数据点坐标的平均值。

其中若中心点无支配数据点，则要么删去该中心点，要么重新随机中心点坐标。

上面的做法实际上是在优化代价函数

$$J({c^{(m)}}, {\text{p}k}) = \frac 1m \sum{i = 1}^m | \text{x}^{(i)} - \text{p}_{c^{(i)}}|^2$$

该代价函数也称为 Distortion 函数。

可以注意到，算法流程中的 2.1. 既是在保持 ${\text{p}}_k$ 不变的前提下解得 $c^{(m)}$ 的最优解，2.2 既是在保持 $c^{(m)}$ 不变的前提下解得 ${\text{p}}_k$ 的最优解。也就是说，每一步调整后，代价函数的值都应减小或不变。

K-means 聚类算法的改进

初始化时，我们可以令 $k$ 个中心点坐标为 $k$ 个不同的样本数据，以取得更好的效果。

另外，该代价函数也有多个局部最小值，所以我们也可以运行多次 K-means 算法（一般为 $50\dots 1000$ 次），取代价函数最小的作为答案。

如何选择 K 值

肘部法则（Elbow Method）：令 $f(k)$ 为取 $K=k$ 时计算得到的最小代价，则取 $f(k)-k$ 图像上明显的拐点的横坐标作为 $k$ 的取值。但实际上不少时候这个图像是比较平缓的，所以其实也没有很大用处，吴恩达也说自己不用。

实际应用中，该算法一般是用来产生一些簇，提供给下游（Downstream）的开发人员，让他们进一步进行计算的。所以可以考虑根据下游开发人员的反馈调整 $K$ 值。

注意：你并不是在选择 $k$ 使得 $f(k)$ 最小。实际上，大多数情况下 $f(k)$ 随着 $k$ 的增大是近似单调下降的，但这并不意味着簇数越多越好。

异常检测

给出 $m$ 个向量 ${\text{x}}^{(i)}$ 作为参考，再给出一个向量 $\text{x}$，判断其对这 $m$ 个向量来说正不正常。

先强行假定每一维的参数是相互独立的，然后我们考虑用正态分布估计每一维参数的分布。计算

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

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

则可以估计给定的参数 $x_j$ 正常的概率是 $p(x_j;{\mu }_j,{\sigma }_j^2)$，此处的 $p(\dots )$ 为正态分布概率函数。

由于互相独立，可以得知

$$p(\text{x})=\prod _{j=1}^{k}p(x_j;{\mu }_j,{\sigma }_j^2)$$

若 $p(\text{x})<ϵ$（其中 $ϵ$ 为我们指定的一个常数），则认为 $\text{x}$ 是异常的。

异常检测的交叉验证

• 训练集 ${\text{x}}^{(m)}$：用于训练
• 交叉验证集 ${(\text{x}{cv}^{(m{cv})}, y_{cv}^{(m_{cv})})}$：用于选择模型
• 测试集 ${(\text{x}{test}^{(m{test})}, y_{test}^{(m_{test})})}$：用于检验模型的实际正确率

注意要点：

• 一般异常数据数远小于正常数据数（如 $1:200$）。
• 一般不需要把异常数据放入训练集，而应当放入交叉验证集和测试集。
• 若异常数据极其少（只有一两个），可考虑不适用测试集（但会带来一定的风险）。

异常检测 Vs. 监督学习

异常检测适用于：

• 异常数据极其少的时候（例如不超过 $20$）。
• 有很多种异常类型，即很难从异常数据习得其通性的时候。
  • 异常检测算法会将与正常数据偏离较大的数据当作异常，监督学习会将与异常数据相近的当作异常。也就是说，如果出现了一种新的异常类型，异常检测算法会将其视为异常（因为与正常偏离大），而监督学习不会将其视为异常（因为与异常距离远）。

监督学习则相反。

例如，金融欺诈的手段千变万化，因此更适合用异常检测；垃圾邮件的类别则相对少，因此更适合用监督学习。

特征选择

监督学习中，即使选择了一些无关特征，算法仍然可以自动调整它们的权值，使它们对结果不起作用。

但异常检测中，特征的选择极其重要。

首先，可以将特征处理一下，使得它们更加符合正态分布，例如

• $f(x)=\ln (x+C)$
• $f(x)=x^a$

尽管有些方法可以自动测量其与正态分布的相近程度，但在实践中作用不大。实践中，多尝试几个 $C$ 和 $a$ 即可。

其次，可以对实际数据作误差分析。例如，如果算法运行不优，大概率是异常数据和正常数据的 $p(\text{x})$ 大小相近。此时可以查看异常数据，分析是否有什么先前没有考虑到的特征是与大部分正常数据相离的。你也可以试着组合一些特征来产生新特征。

推荐系统：协同过滤（Collaborative filtering）

有 $n_u$ 个用户，$n_m$ 个商品，记 $r(i,j)\in 0,1$ 表示用户 $j$ 是否给商品 $i$ 评分，令 $y^{(i,j)}$ 表示其评分。

已知部分评分情况，预估用户对每个未评分商品的评分是多少。

可设商品 $i$ 有隐藏的 $n$ 维特征向量 ${\text{x}}^{(i)}$，用户 $j$ 的线性回归参数为 ${\text{w}}^{(j)},b^{(j)}$，则预计评分为

$${\hat{y}}^{(i,j)}={\text{w}}^{(j)}{\text{x}}^{(i)}+b^{(j)}$$

类似地，定义代价函数

$$J({\text{x}}^{(n_m)},{\text{w}}^{(n_u)},b^{(n_u)})=\frac{1}{2}\sum _{r(i,j)=1}{({\text{w}}^{(j)}{\text{x}}^{(i)}+b^{(j)}-y^{(i,j)})}^2+\frac{\lambda }{2}\sum _{j=1}^{n_u}{\left({\text{w}}^{(j)}\right)}^2+\frac{\lambda }{2}\sum _{i=1}^{n_m}{\left({\text{x}}^{(i)}\right)}^2$$

用梯度下降最优化 $J(\dots )$ 即可。

对于二分类预测问题（即 $y^{(i,j)}\in 0,1$），可以用逻辑回归的方法类似处理，此处不再赘述。

均值归一化

设 ${\mu }_i$ 为商品 $i$ 的平均评分，可以令所有 $y^{(i,j)}$ 减去 ${\mu }_i$ 后进行拟合。训练到最后输出时再在预测值上加上 ${\mu }_i$ 即可。

这样的好处是当用户评分过极少的电影时，算法表现也会更好。

寻找共同点

可以通过协同过滤算法求解出的 ${\text{x}}^{(i)}$，用 $|{\text{x}}^{(j)}-{\text{x}}^{(i)}{|}^2$ 来判断商品 $i,j$ 的相似度。

协同过滤的局限

• 存在冷启动问题：对于新注册的用户 / 新上架的商品，算法无法提供良好的推荐。
• 难以利用已知特性：即使拥有一些已知特性，它们也较难显著提高协同过滤算法的表现。

基于内容过滤（Content-based filtering）

协同过滤算法会根据那些给出评分和你相似的用户，来提供相近的推荐。而基于内容过滤算法，则会根据用户和商品的特征来提供推荐。

设用户 $j$ 的偏好特征为 ${\text{x}}_u^{(j)}$，商品 $i$ 的特征为 ${\text{x}}_m^{(i)}$（**${\text{x}}_u^{(j)},{\text{x}}_m^{(i)}$ 维度不一定相等），基于内容过滤算法会根据 ${\text{x}}_u^{(j)}$ 计算一个转化后的特征向量 ${\text{v}}_u^{(j)}$，根据 ${\text{x}}_m^{(i)}$ 计算 ${\text{v}}_m^{(i)}$（${\text{v}}_u^{(j)},{\text{v}}_m^{(i)}$ 维度必须相等**），并预估评分为

$${\hat{y}}^{(i,j)}={\text{v}}_u^{(j)}{\text{v}}_m^{(i)}$$

此处和之前的算法相比少了常数项，但实际证明，缺少常数项几乎不会影响算法性能。

实现基于内容过滤算法的一个方式是深度学习。构建两个神经网络 $f:{\text{R}}^{k_u}\to {\text{R}}^{k_v}$ 和 $g:{\text{R}}^{k_m}\to {\text{R}}^{k_v}$，令 ${\text{v}}_u^{(j)}=f({\text{x}}_u^{(j)}),{\text{v}}_m^{(i)}=g({\text{x}}_m^{(i)})$，我们需要训练 $f,g$ 使得其产生的预估良好。

实际上，我们可以把两个神经网络结合起来。把 ${\text{x}}_u^{(j)},{\text{x}}_m^{(i)}$ 首尾相连成为一个输入，并在 $f,g$ 的最后用一个神经元连接起来，输出其点积作为结果。这样一来，我们只需要训练一个神经网络，问题会变得简单许多。

连接示例图

先前提到说，神经网络相比决策树的好处是容易将多个神经网络结合起来使用。这就是一个鲜明的例子。

费用函数和先前的类似，也是差值平方和加上正则化项。

从大目录里推荐

现代网站通常拥有大量的资源，例如超过十万甚至百万首曲库。对于每个用户都强行枚举所有商品并放入神经网络计算是不现实的。

许多大规模推荐系统的实现可以分为两个步骤：数据检索和排名。即，检索出十几或几百个该用户可能感兴趣的商品，然后放入神经网络计算并排序。

推荐系统的危害

推荐系统并不完全是好东西，滥用它可能会造成一些不理想的效果：

• 信息茧房。
• 激化仇恨 / 引战言论，因为它们能更好地吸引读者注意。
• 公司的算法推荐的商品可能不是对用户最好的，而是对公司利益最大化的

尽力去做有益于人民的东西。

强化学习引入

强化学习的一些应用：

• 训练机器人
• 工厂优化（任务调度安排）
• 金融股票交易
• 游戏

原理：程序可以任意进行行动，算法仅指定某些状态的奖励，让程序自己学习如何最大化奖励（训狗）。

形式化描述：程序任意时刻都可以用四个参数 $(s,a,R(s),s^{\prime })$ 描述，其中：

• $s$ 为当前状态
• $a$ 为行动
• $R(s)$ 为当前奖励
• $s^{\prime }$ 为后继状态

回报和策略

为了让程序更快地拿到更多奖励，每秒程序的奖励会衰减，即乘上一个略小于 $1$ 的正实数 $\gamma$（称为折扣系数）。

程序至当前为止所获得的所有奖励，乘上对应折扣系数的次幂之和称为回报（Return）。

我们希望求出一个策略（Policy）函数 $\pi :s\to a$，表示当状态为 $s$ 时应当采取行动 $a$。