机器学习

梳理复习研究生机器学习课程的复习过程。

一、宏观理解

有时间的话可以跟着这个仓库学习《统计学习方法》的代码实现和课后作业。【传送门】

0. 线性回归（Linear Regression）与逻辑回归（Logistic Regression）

线性回归估计结果为实数，可以做回归任务。

逻辑回归利用 sigmoid 等函数将线性数据进行处理，可以减小异常数据带来的影响（比如异常数据可能导致线性拟合的结果相差较大），而逻辑回归的结果在 0-1 之间，所以常用作概率预测，分类任务。

1. 决策树

决策树就是一个搭建好的模型，输入数据，就会按照设计好的路径给出输出。例如经典的用于分类的决策树"ID3"，通过输入条件的不同来判断走决策树的哪一个分支，条件越多，分类的结果也越精确。但是决策树的深度要有所权衡，太浅可能导致分类不准确，太深可能导致高代价和过拟合。将熵作为考察依据。注意 ID3 只能做分类树，要想利用决策树实现回归，可以使用 CART, C4.5, CHAID 等。

2. KNN

k 近邻算法，做分类问题，一个样本的分类参考其周围最近的 k 个点的类别，分类为这 k 个点中最多的一类。下图可以看到 KNN 分类严重依赖于 K 值，K 大了分类边界平滑但是会有更多的错分情况（Underfitting Problem），K 小了分类边界很复杂不具有代表性（Overfitting Problem）。

3. Kmeans（聚类算法）

Kmeans 算法是一类无监督分类算法。运算步骤如下：

任取 k 个样本作为 cluster 的中心；
从剩下的样本中逐个取出，选择与其最近的 cluster 加入其中；
并更新 cluster 的中心为加入新样本后的中心位置（即 cluster 的均值）；
重复 2，3 过程直到某个终止条件（每个 cluster 的中心位置不再改变，迭代次数、最小误差变化等）。

该算法受 K 的影响很大，K 就是分类的数量。

对于数据集本身样本的分布也很敏感。

4. 支持向量机 SVM

下面两个分类器的效果差别，右边的分类器保证正确分类的同时，确保两个分类边界更大。

强分类对于线性不可分的情况需要加入一些对于错误的容忍称为（SOFT-MARGIN SVM）：

线性不可分时可以提高维度再分

5. 随机森林（Random Forest）

集成学习（ENSEMBLE LEARNING : (BAGGING)）的一种。特点是以弱搏强。

这类算法注重困难问题的解决，对于难问题往往处理的不好。不过在集成学习中的另一类算法 Boosting 即可解决这种缺点。

6. Adaboost

Adaptive Boosting 自适应增强算法。

ENSEMBLE LEARNING : BOOSTING 。特点是前人栽树，后人乘凉。

针对性学习，让模型弱学习模型逐步学会解决困难问题。后一个弱学习模型建立在前一个学习模型的基础上，从而更好的解决前一个模型解决不了的困难问题。

对于做对的样本增加其困难度，对于做错的样本，减少其困难度。

7. EM & GMM

GMM 高斯混合模型：如下图，高斯混合模型就是将 k 个高斯分布加权求和得到任意分布。

然后利用 EM 对 GMM 进行参数估计。

参考

速通各个算法的直观理解【传送门】

期末复习推荐【传送门】

二、按照考点复习

1. 决策树算法——ID3 算法

基本思想

奥卡姆剃刀说过：“用较少的东西，同样可以做好事情”。同理，决策树也是小型优于大型。

决策树（Decision Tree）是一种常见的分类方法，它是一种监督学习。常见的决策树算法有 ID3，C4.5，C5.0 和 CART(classification and regression tree)，CART 的分类效果一般要优于其他决策树。

决策树是基于树状结构的，一般的，一棵决策树包括一个根节点，若干内部节点和若干叶节点。

每个内部节点表示属性上的判断
每个分支代表一个判断结果的输出
每个叶节点代表一种分类结果。
根节点包含样本全集

决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的“分而治之”（divide-and-conquer）策略。

ID3 算法的核心是根据信息增益来选择进行划分的特征，然后递归地构建决策树。

特征选择

特征选择也即选择最优划分属性，从当前数据的特征中选择一个特征作为当前节点的划分标准。随着划分过程不断进行，希望决策树的分支节点所包含的样本尽可能属于同一类别，即节点的“纯度”越来越高。

熵（entropy）

熵表示事务不确定性的程度，也就是信息量的大小（一般说信息量大，就是指这个时候背后的不确定因素太多），熵的公式如下：

Entropy = -\sum_{i=1}^{n}p(x_i)*log_2p(x_i)

其中， $p(x_i)$ 是分类 $x_i$ 出现的概率，n 是分类的数目。针对某个特征 X，对于数据 D 条件熵为：

H(D|X) = \sum_{i=1}^np(x_i)Entropy(D|x_i)

例如，当只有 A 类和 B 类的时候，不妨设 $p(A) = p(B) = 0.5$ ，熵的大小为：

Entropy = -(0.5log_2(0.5) - 0.5log_2(0.5)) = 1

当只有一类时：

Entropy = -(1log_2(1)) = 0

所以当 Entropy 最大为 1 的时候，是分类效果最差的状态，当它最小为 0 的时候，是完全分类状态。因为熵等于 0 是理想状态，一般实际情况下，熵介于 0 和 1 之间。

熵不断最小化，实际上就是提高分类正确率的过程。

信息增益（information gain）

信息增益：在划分数据集之前之后信息发生的变化，计算每个特征值划分数据集获得的信息增益，获得信息增益最大的特征就是最好的选择。

定义属性 A 对于数据集 D 的信息增益为 infoGain(D|A)，它等于 D 本身的熵，减去给定 A 的条件下 D 的条件熵，即：

infoGain(D|A) = Entropy(D) - Entropy(D|A)

其中 $A = [a_1, a_2, \dots, a_k]$ ，K 个值。

信息增益的意义：引入属性A后，原来数据集D的不确定性减少了多少。

计算每个属性引入后的信息增益，选择给D带来的信息增益最大的属性，即为最优划分属性。一般，信息增益越大，则意味着使用属性A来进行划分所得到的的“纯度提升”

步骤

从根节点开始，计算所有可能特征的信息增益，选择信息增益最大的特征作为节点的划分特征；
由该特征的不同取值建立不同分支，得到不同的子节点分类结果；
对子节点递归 1-2 步，构建决策树；
直到没有特征可以选择或类别完全相同为止，得到最终的决策树。

例题：

ID3 缺点

ID3 没有剪枝策略，容易过拟合；
信息增益校准对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1；
只能用于处理离散分布的特征；
没有考虑缺失值。

缺失值（缺省值） 解决方法：

“最通常值”办法

决策树方法：把未知属性作为“类“，原来的类作为”属性“

概率化缺失值（实际用的方法）

对缺失值的样本赋予该属性所有属性值的概率分布，即将缺失值按照其所在属性已知值的相对概率分布来创建决策树。用系数 F 来进行合理的修正计算的信息量， $F = \frac{数据库中缺失值所在的属性值样本数量去掉缺失值样本数量}{数据库中样本数量的总和}$ ，即 F 表示所给属性具有已知值样本的概率。

过拟合 的解决方法：

预剪枝：在生成决策树的时候就决定是否剪枝

后剪枝：先生成决策树，再通过交叉验证来剪枝

改进算法：C4.5

同样是贪心搜索。

相对于 ID3 的改进：

引入悲观剪枝策略进行后剪枝；
引入信息增益率作为划分标准；
将连续特征离散化，假设 n 个样本的连续特征 A 有 m 个取值，C4.5 将其排序并取相邻两样本值的平均数共 m-1 个划分点，分别计算以该划分点作为二元分类点时的信息增益，并选择信息增益最大的点作为该连续特征的二元离散分类点；
对于缺失值的处理可以分为两个子问题：
- 问题一：在特征值缺失的情况下进行划分特征的选择？（即如何计算特征的信息增益率）
- 问题二：选定该划分特征，对于缺失该特征值的样本如何处理？（即到底把这个样本划分到哪个结点里）
针对问题一，C4.5 的做法是：对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；
针对问题二，C4.5 的做法是：将样本同时划分到所有子节点，不过要调整样本的权重值，其实也就是以不同概率划分到不同节点中。

C4.5 缺点

剪枝策略可以再优化；
C4.5 用的是多叉树，用二叉树效率更高；
C4.5 只能用于分类；
C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；
C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

C4.5 改进：CART

详情参考【传送门】

ID3 和 C4.5 虽然在对训练样本集的学习中可以尽可能多地挖掘信息，但是其生成的决策树分支、规模都比较大，CART 算法的二分法可以简化决策树的规模，提高生成决策树的效率。

CART 在 C4.5 的基础上进行了很多提升。

C4.5 为多叉树，运算速度慢，CART 为二叉树，运算速度快；
C4.5 只能分类，CART 既可以分类也可以回归；
CART 使用 Gini 系数作为变量的不纯度量，减少了大量的对数运算；
CART 采用代理测试来估计缺失值，而 C4.5 以不同概率划分到不同节点中；
CART 采用“基于代价复杂度剪枝”方法进行剪枝，而 C4.5 采用悲观剪枝方法。

2. 候选消除算法

思路

概念学习 是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。

属性的取值如下：

由“?”表示任意本属性可接受的值
明确指定的属性值（如，Warm）
由“ $\emptyset$ ”表示不可接受任何值。

作为搜索的概念学习

概念学习就是一个搜索的过程，范围是假设的表示所隐含定义的整个空间
搜索的目标：为了寻找能最好地拟合训练样例的假设
当假设的表示形式选定后，也就隐含地为学习算法确定了所有假设的空间

计算

以下表为例：

如果属性 Sky 有 3 种可能的值，其他 5 个属性都只有两种可能的值；
实例空间 X： $3 \times 2 \times 2 \times 2 \times 2 \times 2 = 96$ 种不同的实例
假设空间 H：
- 语法不同的假设： $5 \times 4 \times 4 \times 4 \times 4 \times 4 = 5120$ 种
  
  包含 $\emptyset$ 和？两种表示属性
- 语义相同的假设：覆盖相同例子集合的假设
- 语义不同的假设：覆盖例子集合不同的假设
  - 包含有 $\emptyset$ 的假设代表空实例集合，即它们将每个实例都分类为反例
    
    即 $<\empty, \empty, \empty, \empty, \empty, \empty>$ 和 $<\empty, ?, ?, ?, ?, ?>$ 、 $<\empty, \empty, ?, ?, ?, ?>$ 等等其实是一样的。
  - 所以 $1 + 4 \times 3 \times 3 \times 3 \times 3 \times 3 = 973$

这部分计算也会考，来道题目练练：

(1)

① 例子空间中例子的个数 $3 \times 2 \times 2 \times 2 \times 2 \times 2 = 96$

② 语义不同的假设个数 $1 + 4 \times 3 \times 3 \times 3 \times 3 \times 3 = 973$

(2)

不会，要考试了看不进去了，哈哈哈，把资料放在下面：

考后反馈：真考了。。。题目是：为什么说无偏学习器是无用的。

概念学习可以利用偏序关系有效的搜索假设空间： 常用的两种方法如下：

FIND-S
候选消除

FIND-S

候选消除

由候选消除算法得到的变型空间能够收敛到描述目标概念的假设的条件是：

在训练样例中没有错误；
H 中确实包含描述目标概念的正确假设。

例题

上面 G2 没有将去掉的规则进行特化后再加入，修改补充如下：

更多例题【传送门】

3. 规则学习

- GS 算法

思路

输入：例子集；
输出：规则；
原则：（a) 从所有属性值中选出覆盖正例最多的属性值；
(b) 在覆盖正例数相同的情况下，优先选择覆盖反例少的属性值；

设 PE, NE 是正例，反例的集合。 PE’, NE’ 是临时正，反例集。CPX 表示公式，F 表示规则（概念描述）。

F←false;
PE’←PE, NE’←NE, CPX←true;
按上述(a) (b)两原则选出一个属性值 V0 , 设 V0 为第 j0 个属性的取值，CPX←CPX ∩ [1X1j0=V0]
PE’ ← CPX覆盖的正例，NE’ ← CPX覆盖的反例，如果NE’不为空，转(3);
否则，继续执行(5);
PE←PE\PE’, F←F ∨ CPX，如果PE= $\emptyset$ ，停止，否则转(2);

例题

学习得肺炎的规则。

肺炎和肺结核两组病例如下表：

	no	Fever	Cough	X-ray	ESR	Auscultat.
肺炎	1	high	heavy	Flack	Normal	Bubblelike
	2	mediu	heavy	Flack	Normal	Bubblelike
	3	low	slight	Spot	Normal	Dry-peep
	4	high	mediu	Flack	Normal	Bubblelike
	5	mediu	slight	Flack	Normal	Bubblelike
肺结核	1	absent	slight	Strip	Normal	Normal
	2	high	heavy	Hole	Fast	Dry-peep
	3	low	slight	Strip	Normal	Normal
	4	absent	slight	Spot	Fast	Dry-peep
	5	low	mediu	flack	fast	Normal

第一轮：

首先选择覆盖正例数最多的属性 CPX = [ESR=Normal] 得到的 PE’ 和 NE‘ 如下：

	no	Fever	Cough	X-ray	ESR	Auscultat.
肺炎	1	high	heavy	Flack	Normal	Bubblelike
	2	mediu	heavy	Flack	Normal	Bubblelike
	3	low	slight	Spot	Normal	Dry-peep
	4	high	mediu	Flack	Normal	Bubblelike
	5	mediu	slight	Flack	Normal	Bubblelike
肺结核	1	absent	slight	Strip	Normal	Normal

	3	low	slight	Strip	Normal	Normal

此时公式覆盖的反例集 NE’ 不为空，所以根据规则 (a)(b) 继续选择下一个属性，可选的有 [X-ray=Flack] 和 [Auscultat.=Bubblelike] 两个覆盖正例集最多的属性，任选一个得到 CPX = [ESR=Normal][Auscultat= Bubblelike] 得到的 PE‘ 和 NE’ 结果如下：

	no	Fever	Cough	X-ray	ESR	Auscultat.
肺炎	1	high	heavy	Flack	Normal	Bubblelike
	2	mediu	heavy	Flack	Normal	Bubblelike
	3
	4	high	mediu	Flack	Normal	Bubblelike
	5	mediu	slight	Flack	Normal	Bubblelike
肺结核

可以看到 NE’ 此时为空，第一轮搜索结束，得到 PE = PE/PE‘ 如下：

	no	Fever	Cough	X-ray	ESR	Auscultat.
肺炎

	3	low	slight	Spot	Normal	Dry-peep


肺结核	1	absent	slight	Strip	Normal	Normal
	2	high	heavy	Hole	Fast	Dry-peep
	3	low	slight	Strip	Normal	Normal
	4	absent	slight	Spot	Fast	Dry-peep
	5	low	mediu	flack	fasts	Normal

然后在新的表上开始下一轮搜索：

第二轮

选择覆盖反例集最少的属性 [X-ray= Spot] ，得到的分类结果如下：

	no	Fever	Cough	X-ray	ESR	Auscultat.
肺炎

	3	low	slight	Spot	Normal	Dry-peep


肺结核


	4	absent	slight	Spot	Fast	Dry-peep

再选择覆盖反例集最少的属性 [ESR=normal] ，得到新的 CPX=[X-ray=spot][ESR=normal] ，PE’ 和 NE’ 如下：

	no	Fever	Cough	X-ray	ESR	Auscultat.
肺炎

	3	low	slight	Spot	Normal	Dry-peep


肺结核

NE’ 为空，此时新一轮的搜索结束，PE = PE/PE’ 为空，所以搜索结束。

最终生成的学习结果是：

练习

- AQ 算法

定义1：普化(generalize) :减少规则的约束，使其覆盖更多的训练例子叫普化。

定义2：特化(specialize) : 增加规则的约束，使其覆盖训练例子较少叫特化。

定义3：一致：只覆盖正例不覆盖反例的规则被称为是一致的。

定义4：完备：覆盖所有正例的规则被称为是完备的。

思路

输入：例子集、参数#SOL、#CONS、Star的容量m、优化标准；
输出：规则；

1 Pos和NEG分别代表正例和反例的集合
1.1 从Pos中随机地选择一例子
1.2 生成例子e相对于反例集NEG的一个约束Star(reduced star)，G(e|NEG,m) ，其中元素不多于m个。
1.3 在得到的star中，根据设定的优化标准LEF找出一个最优的公式D。
1.4 若公式D完全覆盖集合Pos，则转⑥
1.5 否则，减少Pos的元素使其只包含不被D覆盖的例子。从步骤①开始重复整个过程。
1.6 生成所有公式D的析取，它是一个完备且一致的概念描述。

2 Star生成: Induce方法
2.1 例子e的各个选择符被放入PS(partial star)中，将ps中的元素按照优化标准排序。
2.2 在ps中保留最优的m个选择符。
2.3 对ps中的选择符进行完备性和一致性检查，从ps中取出完备一致的描述放入SOLUTION表中，若SOLUTION表的大小大于等于参数#SOL，则转⑤。一致但不完备的描述从ps中取出放入表CONSISTENT中，若CONSISTENT表的大小大于等于参数#CONS，则转⑤;
2.4 对每个表达式进行特殊化处理，所有得到的表达式根据优化标准排列，仅保留m个最优的。重复步骤③，④。
2.5 得到的一般化描述按优先标准排序，保留m个最优的表达式构成约束Star(e|NEG,m).

例题

例子集：肺炎和肺结核两组病例如下表：

	no	Fever	Cough	X-ray	ESR	Auscultat.
肺炎	1	high	heavy	Flack	Normal	Bubblelike
	2	mediu	heavy	Flack	Normal	Bubblelike
	3	low	slight	Spot	Normal	Dry-peep
	4	high	mediu	Flack	Normal	Bubblelike
	5	mediu	slight	Flack	Normal	Bubblelike
肺结核	1	absent	slight	Strip	Normal	Normal
	2	high	heavy	Hole	Fast	Dry-peep
	3	low	slight	Strip	Normal	Normal
	4	absent	slight	Spot	Fast	Dry-peep
	5	low	mediu	flack	fast	Normal

#SOL=2

#CONS=2

m=2

优化标准: 正例数/反例数

1.1 随机选一个正例的种子 $e_1^+$ ：

1	[Fever=high][Cough=heavy][X-ray=flack][ESR=normal][Auscultation=bubblelike]

1.2 下面生成一个约束 Star

第一轮：

2 进入 Induce 算法

2.1 加例子 $e_1^+$ 的各个选择符放入 PS 中，将 PS 中的元素按照优化标准排序，结果如下：

\begin{aligned} Ps: &⑤[Fever=high]&&<2,1> \\ &④[Cough=heavy]&&<2,1> \\ &②[X-ray=flack]&&<4,1> \\ &③[ESR=normal]&&<5,2> \\ &①[Ausculation=bubblelike]&&<4,0> \end{aligned}

2.2 在 PS 中保留最优的 m 个（2个）选择符

[Auscultation=bubblelike] [X-ray=flack]

2.3 [Auscultation=bubblelike] 一致但不完备放入 CONSISITENT 中， [X-ray=flack] 进入 2.4 特化步骤

2.4 对表达式 [X-ray=flack] 进行特化，保留最优的 m 个：

1 2	[x-ray=flack][ESR=normal] [x-ray=flack][Cough=heavy]

2.3

1 2	[x-ray=flack][ESR=normal] [x-ray=flack][Cough=heavy]

一致但不完备，加入 CONSISTENT 跳转到 2.5

2.5 保留2个表达式，2个表达式均为一致的，放入CONSISTENT中，按优先标准排序CONSISTENT中表达式，保留m(2)个表达式。
[Ausculation=bubblelike] <4, 0>

[x-ray=flack][ESR=normal] <4, 0>

（出Induce算法）

1.3 选出一个最优的作为D
D: [Auscultation=bubblelike]

1.5 将D覆盖的正例去掉。去掉 $e_1^+, e_2^+, e_4^+, e_5^+$

第一轮结束。

第二轮：

1.1 随机选择剩下的种子 $e_3^+$ ：

1	[Fever=low][Cough=slight][x-ray=spot][ESR=normal][Auscultation=dry-peep]

1.2 生成 Star 约束

2.1 将例子 $e_3^+$ 的各个选择符放入 PS（partial star）中，将 PS 中的元素按照优化标准排序：

\begin{aligned} PS: &④[fever=low]&&<1,2> \\ &⑤[Cough=slight]&&<1,3> \\ &①[x-ray=spot]&&<1,1> \\ &②[ESR=normal]&&<1,2> \\ &③[Ausculation=dry-peep]&&<1,2> \end{aligned}

2.2 保留最优的 m 个（2个）选择符：

1	[ESR=normal] [x-ray=spot]

2.3 对 PS 中的选进行完备性和一致性检查

[ESR=normal] [x-ray=spot] 均不是完备一致的，也不是一致不完备的，跳转到 2.4 进行特化

2.4

保留 m(2) 个表达式

1 2	[x-ray=spot] [ESR=normal] [x-ray=spot] [fever=low]

2.3 上面2个表达式都是完备一致的，放入SOLUTION表中，跳转到 2.5

2.5 按优先标准排序，保留 m(2) 个并离开 Induce

1.3 选出一个最优的作为 D

D: [x-ray=spot] [ESR=normal]

1.4 公式 D 完全覆盖剩下的正例集 POS，跳转到 1.6

1.6 生成所有公式 D 的析取，生成规则如下：

[\text {Ausculation}=\text {bubblelike}] \vee [\text {x}-\text {ray}=\text {spot}][\text {ESR}=\text {normal}] \rightarrow \text {肺炎}

算法结束。

练习

1）可以看出考试要考 AQ 算法的理解和执行过程，这部分得背。

2）决策树给定了 R 个训练例子，如果只有 1 个叶节点，那么所有例子分在一个类中，这显然过于粗糙。如果有 R 个叶节点，那么每个例子对应一个叶节点进行分类，这就过拟合了。所以，叶子节点的数量在 [1-R] 之间。有 M 个二值属性，那么可能的属性组合有 $2^M$ 个，但是一般由于资源限制等原因，没法全部考虑，需要剪枝等操作避免过拟合。综上所述，决策树叶子节点的数目最多是 $min(R, 2^M)$ 个。

4. 神经网络

思路

略

例题

1.1 使用梯度下降的好处

相比大规模数值矩阵，梯度下降所遵循的迭代求解效率更高；
对于某些最小二乘法无法计算全域唯一最优解的情况，梯度下降仍然能够有效进行最小值点（或解空间）的寻找。

1.2 系数 $\frac{1}{2}$ 在求导之后可以把系数凑为 1，形式简洁。该误差包含了目标和输出之间的误差，并附加了权重偏置，一定程度上避免了陷入局部最优解。

1.3 随机梯度下降或者增量梯度下降。

随机梯度下降：梯度下降的随机近似对于每个训练样例沿一个不同的误差曲面有效下降，它依靠这些梯度的平均来近似对于整个训练集合的梯度。由于这些不同的误差曲面通常有不同的局部极小值，这使得下降过程不太可能陷入任意一个局部极小值。

1.4 通用近似定理（Universal Approximation Theorem）：具有一个或多个隐藏层的前馈神经网络能够在理论上逼近任何连续函数，只要给予网络足够多的隐藏单元。这意味着，对于一个足够复杂的神经网络结构，理论上可以拟合任何复杂的函数关系。

2 可以实现，假设输入为长度为 n 的一个 01 序列，感知器的权重设置为 1，偏置设置为 $-\frac{n}{2}$ 。

5. 遗传算法

思路

算法原型

算法概述

算法迭代更新一个假设池，称位群体，包含 p 个假设。
在每一次迭代中，根据适应度函数评估群体中的所有成员，然后从当前群体中用概率方法选取适应度最高的个体产生新一代群体，在这些被选中的个体中，一部分保持原样地进入下一代群体，其他的被用作产生后代个体地基础，其中应用像交叉和变异这样的方法。
具体来看，每一次迭代产生地新一代 Ps 主要包括：
- 选择：计算每个成员的适应度，从而确定被选中地概率，从 P 中按概率选择 （1-r）p 个成员加入 Ps；
- 交叉：从 P 中按概率选择 r*p/2 对假设，每对假设 <h1, h2> 应用交叉算子产生两个后代，把所有后代加入 Ps ；
- 变异：从 Ps 中按均匀概率随机选择 m% 的成员。对每个选择的成员，在其二进制表示中随机选择一位取反。

模式定理

模式定理的推导考试考了原题。

使用数学刻画 GA 中群体随时间进化的过程。

若只考虑选择步的影响：

遗传算法编码案例
- 考虑outlook，有3个可能的值：Sunny、Overcast、Rain，则用一个3位二进制串表示，如010表示outlook=Overcast
- 属性Wind有两个可能取值：Strong或Weak，用2位二进制串表示
- （outlook=Overcast 或 Rain）且（Wind = Strong），可表示为长度5的位串：011 10**（属性内部是析取，属性之间是合取）**
- 分类情况PlayTennis=yes可以表示为2位二进制串
- IF Wind = Strong Then PlayTennis = yes，可表示为：111 10 10，前三位111表示outlook可随意取值，接着两位10表示Wind的约束，最后两位表示结果是yes

交叉和变异算子

单点交叉：
两点交叉：
均匀交叉：
点变异：

练习

解：

(1)略

(2)每个部分被选中的概率如下：

Pr(h_i) = \frac{Fitness(h_i)}{\sum_{j=1}^p Fitness(h_j)}

累积概率如下：

q(h_i) = \sum_{j=1}^i p(h_j)

计算每个个体被选中概率 $Pr(h_i)$
计算每个部分的累积概率 $q(h_i)$
随机生成一个数组 array，数组中的元素取值范围在 0-1 之间，并将其按从小到大的方式排序。若累计概率 $q(x_i)$ 大于数组中的元素 array[i] ，则个体 $x_i$ 被选中，若小于 array[i] ，则比较下一个个体 $x_{i+1}$ 直到选出一个个体为止。
若需要转盘选中 N 个个体，则将步骤（3）重复 N 次即可。

6. PCA 主成分分析

思路

目标是找一个线性映射，在低维空间表示高维数据
建立新的坐标系，用更少的坐标重新表示数据，使得恢复数据的误差最小

应用
- 数据降维，如人脸、动物等数据一般尺寸较大，如果将其发展成一维数据送入分类器，数据量过大
  - 数据维度过高，而样本不足，容易过拟合
  - 维度过高也会导致更多存储空间占用、导致计算量增加，减缓计算速度
- 人脸识别

练习

从你熟悉的角度解释主成分分析（PCA），并指出它的两种可能应用。

7. KNN k近邻

思路

训练过程：将训练数据存储起来
分类过程：
- 对于给定的查询实例 x，寻找训练样本中离 x 最近的 k 个实例
- 返回 k 个实例中某一类别实例数最多的标签
原始算法过程：
距离加权最近邻算法
局部加权回归：本质就是回归，只是将损失函数定义为局部加权
积极学习与消极学习
- 消极学习：延迟了如何从训练数据中泛化的决策，直到遇到一个新的查询案例时才进行
- 积极学习：在见到新的查询之前就做好了泛化的工作

练习

叙述 K-近邻算法的思想。

某个输入样例对应的标签，选择与其距离最近的 k 个样本点中，数量最多的一类对应的标签。

8. K-means & GMM

- K-means

思路

手动设置聚类数 K，首先从样本中随机拿出 K 个样本作为 K 类中心点的初始化。然后每次从剩余的样本中拿出一个，选择与其最近的一类，加入其中，并更新该聚类的中心点位置，重复上述步骤直到聚类中心位置不在变化。

- GMM

思路

练习

请给出 K-means 算法，并指出该方法与高斯混合模型（GMM）之间的联系与差别。

K-means 和 GMM 之间的关系：

相同点：
- 都是迭代执行的算法，且迭代的策略也相同，算法开始执行时先对需要计算的参数赋初值，然后交替执行两个步骤：
  - 第一步是对数据的估计（K-means 是估计每个点所属聚类标签，GMM 是计算样本由不同高斯产生的概率）
  - 第二步是用上一步算出的估计值重新计算参数值，更新目标参数（K-means 是计算聚类中心位置；GMM 是计算各个高斯分布的先验概率、均值、协方差矩阵）
不同点：
- 需要计算的参数不同
  - K-means 计算聚类中心位置
  - GMM 是各个高斯分布的参数
- 计算目标参数的方法不同
  - K-means 是计算当前聚类中所有元素的位置的均值
  - GMM 是基于概率的算法，是通过计算似然函数的最大值实现分布参数的求解的

9. Bayes 贝叶斯学习

考了 Bayes 的基础应用，类似概率论中的考法。

思路

概念解释

P(h)：h的先验概率，在没有训练数据之前就拥有的关于h的初始概率，通过经验获得
P(D)：将要观察的训练数据D的先验概率
P(D|h)：假设h成立的情况下观察到的数据D的概率
P(h|D)：给定训练数据D时h成立的概率，h的后验概率

贝叶斯公式提供了从先验概率 P(h) 和 P(D) 以及 P(D|h) 计算后验概率 P(h|D) 的方法。

P(h|D) = \frac{P(D|h)P(h)}{P(D)}

极大后验 MAP 假设

\begin{aligned} h_{MAP} &= \underset{h \in H}{\operatorname{argmax}} P(h|D) \\ &= \underset{h \in H}{\operatorname{argmax}} \frac{P(D|h)P(h)}{P(D)} \\ &= \underset{h \in H}{\operatorname{argmax}} P(D|h)P(h) \end{aligned}

极大似然 MLE 假设：假定每个假设先验概率相同，其中 P(D|h) 被称为给定 h 时数据 D 的似然度

h_{MLE} = \underset{h \in H}{\operatorname{argmax}} P(D|h)

贝叶斯最优分类器

解决的问题：给定训练数据，对新实例的最可能分类是什么（除了简单应用 MAP 假设）
思想：新实例的最可能分类可通过合并所有假设的预测得到，用后验概率来加权。

如果新样例的可能分类可取某集合 V 的任一值 vj，那么概率 P(vj|D) 表示新实例分类为 vj 的概率，其值为：
$P(v_j | D) = \sum_{h_i \in H}P(v_j | h_i)P(h_i|D)$
新实例的最优分类为使 P(vj|D) 最大的 vj 值，则贝叶斯最优分类器：
$\underset{v_j \in V}{\operatorname{argmax}} \sum_{h_i \in H}P(v_j|h_i)P(h_i|D)$
例子：