竞赛总结
1. 能源预测（时序）（比赛结束后更新）
1 | #!/usr/bin/env python |
基于tensorflow的多层感知机的代码实现
1 | # coding=utf-8 |
1 | import tensorflow as tf |
1 | # 读取数据并处理（测试集验证集） |
1 | # 定义模型参数（一层隐藏层） |
1 | # 定义激活函数 ReLu softmax |
1 | # dropout(H, drop_prob) |
1 | # 定义损失函数 交叉熵 L2正则项 |
1 | # 定义get_K_fold_data函数 |
1 | # 定义训练函数 |
1 | # 预测函数 predict() |
1 | params = [W1, b1, W2, b2] |
1 | result = predict(net, params, X_test) |
Reference
Ensemble
发表于
分类于
ML
boosting
bagging
stacking
1. boosting
- 代表算法：AdaBoost
只能分类？
弱分类器：比较粗糙的分类规则
强分类器：精确的分类规则
提升方法就是组合弱分类器，构成一个强分类器
大多数的提升方法都是改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习
对于提升方法来说有两个问题需要回答：
每一轮如何改变训练数据的权值或概率分布
如何将弱分类器组合成一个强分类器
1.1 AdaBoost
AdaBoost的做法：
针对问题1，提高被前一轮弱分类器错误分类的样本的权值，降低分类正确的样本的权值
针对问题2，组合采用加权多数表决的方法
算法8.1 (AdaBoost)
输入：训练数据集 $T$ ；弱学习算法
输出：最终的分类器 $G(x)$
初始化训练数据权值分布
$$
D_1 = (w_{11}, \cdots, w_{1i}, \cdots, w_{1N}),\quad w_{1i} = \frac{1}{N}, \quad i = 1,2,…,N
$$对 $m = 1,2,…, M$
a. 使用具有权值分布的 $D_m$ 的训练数据集学习得到基本分类器(学习的依据就是分类误差率最小，分类错误的权重和)
$$
G_m(x) : \mathcal{X} \rightarrow \lbrace c_1,c_2,\cdots, c_k \rbrace
$$
b.计算 $G_m(x)$ 在训练数据集上的分类误差率
$$
e_{m}=\sum_{i=1}^{N} P\left(G_{m}\left(x_{i}\right) \neq y_{i}\right)=\sum_{i=1}^{N} w_{mi} I\left(G_{m}\left(x_{i}\right) \neq y_{i}\right)
$$
c. 计算 $G_m(x)$ 的系数
$$
\alpha_m = \frac{1}{2} \log(\frac{1-e_m}{e_m})
$$
这里的对数是自然对数d. 更新训练数据集的权值分布
$$
D_{m+1} = (w_{m+1,1}, …, w_{m+1, i}, …, w_{m+1, N}) \\
w_{m+1, i} = \frac{w_{mi}}{Z_m} \exp(-\alpha_m I\left(G_{m}\left(x_{i}\right) = y_{i}\right)), \quad i =1,2,…,N
$$
这里， $Z_m$规范因子
$$
Z_m = \sum_{i = 1}^{N}w_{mi}\exp(-\alpha_m I\left(G_{m}\left(x_{i}\right) = y_{i}\right))
$$
$I\left(G_{m}\left(x_{i}\right) = y_{i}\right)$，当分类正确的时候取1，分类错误取0。二分类时可以 $y_iG_m(x_i)$ 代替它使 $D_{m+1}$ 称为一个概率分布
构建基本分类器的线性组合
$$
f(x) = \sum_{m=1}^{M}\alpha_mG_m(x)
$$
最终得到分类器
$$
G(x) = \text{sign}(f(x))
$$
注： $e_m$ 大的，$\alpha_m$ 小，这个时候观察权值的更新公式，对于分子来说，正确率高的，分子小，正确率低的，分子大， 这样就达到了提高被前一轮弱分类器错误分类的样本的权值，降低分类正确的样本的权值的目的
Q：Adaboost终止条件是什么？为什么不容易过拟合？
有些代码将终止条件设置为一个超参数，即弱分类器的个数。
为什么不容易过拟合？
Adaboost在实验中表现出更加不容易过拟合（相对于别的boosting方法）的现象，尤其是在实验中发现，迭代中经验误差都已经不变化了的情况下，测试误差居然还能下降一段时间。
对于二分类问题，AdaBoost的训练误差以指数速率下降就很具有吸引力
1.2 AdaBoost算法解释
AdaBoost = 加法模型 + 损失函数(指数函数) + 学习算法(前向分步算法)
- 加法模型
$$
f(x) = \sum_{m=1}^{M} \beta_m b(x;\gamma_m)
$$
- 损失函数
$$
L(y,f(x)) = \exp(-yf(x))\\
(\alpha_m, G_m(x)) = \arg \min_{\alpha,G}\sum_{i = 1}^{N}\exp[-y_i(f_{m-1}(x_i) +\alpha G(x_i))]
$$
1.3 Adaboost代码实现
1 | # 解决的问题：二分类，Y_label = {-1, 1} 这里简化特征X Xi = {0,1} (二值化处理) |
1.3 boosting tree
以决策树为基函数的提升方法称为提升树。可以是二叉分类树，或二叉回归树。
- 模型
$$
f_M(x) = \sum_{m = 1}^M T(x;\Theta_m)
$$
其中， $T(x;\Theta_m)$ 表示决策树， $\Theta_m$ 为决策树的参数， $M$ 为树的个数
- 参数确定(经验风险极小化)
$$
\hat{\Theta_m}=\arg \min_{\Theta_m} \sum_{i=1}^{N} L\left(y_{i}, f_{m-1}\left(x_{i}\right)+T\left(x_{i}; \Theta_{m}\right)\right)
$$
- 损失函数
- 平方误差损失函数的回归问题
- 指数损失函数的分类问题
- 一般损失函数的决策问题
当分类问题是二分类，AdaBoost算法的弱分类器限制为二分类即可，就是boosting tree
回归问题的提升树
$$
T(x;\Theta)=\sum_{j=1}^{J}c_j I(x \in R_j)
$$
其中，参数 $\Theta = \lbrace (R_1, c_1), (R_2, c_2),…,(R_J, c_J) \rbrace$ 表示树的区域划分和各区域上的常数， $J$ 是回归树的复杂度即叶结点的个数。- 采用平方误差损失函数
$$
\begin{align*}
L(y,f_{m-1}(x) + T(x; \Theta_m)) &= [y - f_{m-1}(x) - T(x;\Theta_m)]^2\\
&=[r-T(x;\Theta_m)]^2
\end{align*}
$$
所以从损失函数可以看出，当前层树的确定，是通过拟合上一层模型的残差。所以算法可以通过将该层的训练数据给改为残差即可递归得到每一层的tree
- 采用平方误差损失函数
参数更新(梯度下降)
$$
-[\frac{\partial L(y, f(x_i))}{\partial f(x_i)}]{f(x)=f{m-1}(x)}
$$
2. Bagging[Beriman, 1996a]
采用自主抽样法(bootstrap sampling)
- 确定样本集个数 $m$
- 又放回的抽取 $m$ 个样本
- 采样出 $T$ 个含 $m$ 样本的采样集
- 然后基于每个样本集训练一个基学习器
- 预测可以使用简单投票法
可以记录一下使用的数据，未被使用的数据可以用来对泛化性能进行“包外估计”
代码难度不大
使用random.sample()或者np.random.choice()就可以实现重抽样
random.sample()默认不重复抽样，可以抽取多维数据
np.random.choice() 默认重复抽样 replace=True, 不可以抽取多维数据，所以可以用这个函数产生下标。
3. Random Forest(RF)
Bagging 的变体，RF在基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。具体来说， 传统决策树在选择划分属性时是在当前结点的属性集合(假定有d个属性)中选择一个最优属性； 而在RF中， 对基决策树的每个结点， 先从该结点的属性集合中随机选择一个包含k个属性的子集， 然后再从这个子集中选择一个最优属性用于划分。若令$k=d$,则基决策树的构建与传统决策树相同；若令$k = 1$,则是随机选择一个属性用于划分； 一般情况下， 推荐值$k = log_2d$
算法：
输入：训练数据 $T$ ，基决策树(CART)，重抽样参数 $m$，属性集合参数 $k$
输出：最终分类器
for 1,2,…T
重抽样数据(m个)，记录未被抽取的数据
随机抽取k个属性
根据重抽样的数据和确定的属性，学习基分类器 (如：CART)
end for
输出：最终分类器
4. Stacking
- 介绍
假设是五折的stacking，我们有一个train数据集和一个test数据集，那么一个基本的stacking框架会进行如下几个操作：
1、选择基模型。我们可以有xgboost，lightGBM，RandomForest，SVM，ANN，KNN，LR等等你能想到的各种基本算法模型。
2、把训练集分为不交叉的五份。我们标记为train1到train5。
3、从train1开始作为预测集，使用train2到train5建模(model1)，然后预测train1，并保留结果；然后，以train2作为预测集，使用train1，train3到train5建模，预测train2，并保留结果(model2)；如此进行下去…….直到把train1到train5各预测一遍；
4、把预测的结果按照train1到trian5的位置对应填补上，得到对train整个数据集在第一个基模型的一个stacking转换。
5、在上述建立的五个模型过程中，每个模型分别对test数据集进行预测，并最终保留这五列结果，然后对这五列取平均，作为第一个基模型对test数据的一个stacking转换。
6、然后进入第二层，将新特征作为第二层的train data，第一层的预测结果作为test data
7、一般使用LR(逻辑回归)作为第二层的模型进行建模预测。
但使用stacking会比较耗时，所以真正比赛的时候可以改为3折或4折
- Stacking的输出层为什么用逻辑回归？
stacking的有效性主要来自于特征抽取。而表示学习中，如影随形的问题就是过拟合，试回想深度学习中的过拟合问题。
在[5]中，周志华教授也重申了stacking在使用中的过拟合问题。因为第二层的特征来自于对于第一层数据的学习，那么第二层数据中的特征中不该包括原始特征，以降低过拟合的风险。举例：
- 第二层数据特征：仅包含学习到的特征
- 第二层数据特征：包含学习到的特征 + 原始特征
另一个例子是，stacking中一般都用交叉验证来避免过拟合，足可见这个问题的严重性。
为了降低过拟合的问题，第二层分类器应该是较为简单的分类器，广义线性如逻辑回归是一个不错的选择。在特征提取的过程中，我们已经使用了复杂的非线性变换，因此在输出层不需要复杂的分类器。这一点可以对比神经网络的激活函数或者输出层，都是很简单的函数，一点原因就是不需要复杂函数并能控制复杂度。
因此，stacking的输出层不需要过分复杂的函数，用逻辑回归还有额外的好处：
- 配合L1正则化还可以进一步防止过拟合
- 配合L1正则化还可以选择有效特征，从第一层的学习器中删除不必要的分类器，节省运算开销。
- 逻辑回归的输出结果还可被理解为概率
Reference
[1]. https://github.com/Dod-o/
[2]. 《统计学习方法》 – 李航
[3]. 《机器学习》 – 周志华
[4]. 【SPA大赛】腾讯广告点击大赛：对stacking的一些基本介绍
[5]. Zhou, Z.H., 2012. Ensemble methods: foundations and algorithms. CRC press.
DecisionTree
基本的分类与回归方法。本文主要是关于分类的决策树。
通常包括三个步骤：特征选择、决策树的生成和决策树的修剪
1. 模型与学习
- 模型
可以将决策模型看作是一个if-then结构，具有的重要性质是互斥且完备
- 学习
目标是根据给定的训练数据集构建一个决策树模型， 使它能够对实例进行正确的分类。通常使用损失函数(正则化的极大似然函数)表示这一目标。
决策树学习的算法通常是一个递归地选择最优特征， 并根据该特征对训练数据进行分割， 使得对各个子数据集有一个最好的分类的过程。
如果特征数量很多， 也可以在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征
一般而言决策树学习算法包含
- 特征选择
- 决策树的生成
- 决策树的剪枝过程
常用的算法有ID3、C4.5、CART
2. 特征选择
特征选择在于选取对训练数据具有分类能力的特征。 如果利用一个特征进行分类的结果与随机分类的结果没有很大差别， 则称这个特征是没有分类能力的
通常选择的准则是信息增益或信息增益比。
2.1 信息增益
- 熵
随机变量X的熵定义为
$$
H(X) = H(p) = -\sum_{i=1}^{n} p_{i} \log p_{i}
$$
熵越大，随机变量的不确定性就越大。
- 条件熵
已知随机变量X的条件下随机变量Y的不确定性
$$
H(Y \mid X)=\sum_{i=1}^{n} p_{i} H(Y \mid X=x_{i})
$$
其中 $p_i = P(X=x_i)$ .
当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时， 所对应的熵与条件熵分别称为经验熵（empirical entropy)和经验条件熵。
- 信息增益
表示得知特征 $X$ 的信息而使得类 $Y$ 的信息的不确定性减少的程度。
特征A对训练数据集D的信息增益 $g(D,A)$，定义为集合 $D$ 的经验熵 $H(D)$ 与特征 $A$ 给定条件下 $D$ 的经验条件熵 $H(D|A)$之差
$$
g(D,A) = H(D) - H(D|A)
$$
一般地， 熵H(y)与条件熵H(y|X)之差称为互信息（mutual information)。 决策树学习中的信息增益等价于训练数据集中类与特征的互信息
根据信息增益准则的特征选择方法是: 对训练数据集（或子集）D， 计算其每个特
征的信息增益，并比较它们的大小，选择信息增益最大的特征。
设训练数据集为 $D,|D|$ 表示其样本容量，即样本个数。设有 $K$ 个类 $C_{k}, k=$ $1,2, \cdots, K,|C_{k}|$ 为属于类 $C_{k}$ 的样本个数, $\sum_{k=1}^{K}\left|C_{k}\right|=|D|$ 设特征 $A$ 有 $n$ 个不同的取值 $\lbrace a_{1}, a_{2}, \cdots, a_{n} \rbrace$ 根据特征 $A$ 的取值将 $D$ 划分为 $n$ 个子集 $D_{1}, D_{2}, \cdots, D_{n}$ ，$|D_{i}|$ 为 $D_{i}$ 的样本个数， $\sum_{i=1}^{n}\left|D_{i}\right|=|D|$ 记子集 $D_{i}$ 中属于类 $C_{k}$ 的样本的集合为 $D_{i k}$ ，即 $D_{ik}=D_{i} \cap C_{k},|D_{ik}|$ 为 $D_{ik}$ 的样本个数。于是信息增益的算法如下。
算法5.1（信息增益的算法）
输入: 训练数据集 $D$ 和特征 $A$；
输出：特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D, A)$ 。
(1) 计算数据集 $D$ 的经验熵 $H(D)$
$$
H(D)=-\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|} \log_{2} \frac{|C_{k}|}{|D|}
$$
(2) 计算特征 $A$ 对数据集 $D$ 的经验条件嫡 $H(D \mid A)$
$$
H(D \mid A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} H\left(D_{i}\right)=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \sum_{k=1}^{K} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|} \log_{2} \frac{\left|D_{ik}\right|}{\left|D_{i}\right|}
$$
(3) 计算信息增益
$$
g(D, A)=H(D)-H(D \mid A)
$$
2.2 信息增益比
- 定义(信息增益与熵之比)
$$
g_{R}(D, A)=\frac{g(D, A)}{H_{A}(D)}
$$
其中，$H_{A}(D)=-\sum_{i=1}^{n} \frac{|D_{i}|}{|D|} \log {2} \frac{|D{i}|}{|D|}, n$ 是特征 $A$ 取值的个数。
3. 决策树的生成
3.1 ID3算法
具体方法是： 从根结点（root node)开始， 对结点计算所有可能的特征的信息增益， 选择信息增益最大的特征作为结点的特征， 由该特征的不同取值建立子结点；再对子结点递归地调用以上方法， 构建决策树； 直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一颗决策树。ID3算法相当于用极大似然法进行概率模型的选择。
算法3.1 （ID3算法）
输入：训练数据集 $D$ ,特征集 $A$ 阈值 $\varepsilon$
输出：决策树 $T$ 。
（1）若 $D$ 中所有实例属于同一类 $C_{k},$ 则 $T$ 为单结点树，并将类 $C_{k}$ 作为该结点的类标记，返回 $T$;
（2）若 $A=\varnothing$ ，则 $T$ 为，sh单结点树，并将 $D$ 中实例数最大的类 $C_{k}$ 作为该结点的类标记，返回 $T$;
（3）否则，计算 $A$ 中各特征对 $D$ 的fanjia信息增益，选择信息增益最大的特征 $A_{g}$ ；
（4）如果 $A_{g}$ 的信息增益小于阈值 $\varepsilon$ ，则设置 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_{k}$ 作为该结点的类标记，返回 $T$;
（5）否则，对 $A_{g}$ 的每一可能值 $a_{i},$ 依 $A_{g}=a_{i}$ 将 $D$ 分割为若干非空子集 $D_{i},$ 将$D_{i}$ 中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树 $T$ ，返回 $T$;
（6）对第 $i$ 个子结点，以 $D_{i}$ 为训练集，以 $A-\lbrace A_{g}\rbrace$ 为特征集，递归地调用步 (1)$\sim$ 步 $(5),$ 得到子树 $T_{i},$ 返回 $T_{i}$
缺点：只有树生成，没有树剪枝，容易过拟合
3.2 C4.5算法
与ID3相比，在生成过程中用信息增益比来选择特征。
算法 3.2 （C4.5的生成算法）
输入: 训练数据集 $D$, 特征集 $A$ 阈值 $\varepsilon ;$
输出: 决策树 $T_{\circ}$
（1）如果 $D$ 中所有实例属于同一类 $C_{k},$ 则置 $T$ 为单结点树，并将 $C_{k}$ 作为该结点的类，返回 $T$;
（2）如果 $A=\varnothing,$ 则置 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_{k}$ 作为该结的类，返回 $T$;
（3）否则，计算 $A$ 中各特征对 $D$ 的信息增益比，选择信息增益比最大的特征 $A_{g} ;$
（4）如果 $A_{g}$ 的信息增益比小于阈值 $\varepsilon$ ，则置 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_{k}$ 作为该结点的类，返回 $T$;
（5）否则，对 $A_{g}$ 的每一可能值 $a_{i},$ 依 $A_{g}=a_{i}$ 将 $D$ 分割为子集若干非空 $D_{i}$ ，将 $D_{i}$ 中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树 $T$ ，返回 $T$;
（6）对结点 $i$,以 $D_{i}$ 为训练集，以 $A-\left{A_{g}\right}$ 为特征集，递归地调用步(1)$\sim$步 $(5),$ 得到子树 $T_{i},$ 返回 $T_{i}$ 。
4. 决策树的剪枝
以上两种算法均未考虑树的复杂度，这样产生的决策树容易出现过拟合的问题。因此需要将生成的树进行简化。
决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。设树 $T$ 的叶节点个数为 $|T|$ ，$t$ 是树 $T$ 的叶节点，该叶节点有 $N_t$ 个样本点，其中 $k$ 类样本点有 $N_{tk}$ 个， $H_t(T)$ 为叶节点 $t$ 上的经验熵。 $\alpha$ 为参数。则决策树的损失函数可以定义为
$$
\begin{array}{c}
C_{\alpha}(T)=\sum_{t=1}^{|T|} N_{t} H_{t}(T)+\alpha|T| \\
H_{t}(T)=-\sum_{k} \frac{N_{tk}}{N_{t}} \log \frac{N_{tk}}{N_{t}}
\end{array}
$$
将第一项记做 $C(T)$，这时有
$$
C_{\alpha}(T) = C(T)+ \alpha|T|
$$
第一项表示对训练数据的预测误差，第二项表示模型的复杂度。$\alpha \geq 0$ 控制两者之间的影响。由此可以看出，决策树的生成学习局部的模型，而决策树剪枝学习整体的模型。
算法 4.1 （树的剪枝算法）
输入：生成算法产生的整个树 $T$ ，参数 $\alpha$
输出：修剪后的子树 $T_{\alpha}$
（1）计算每个结点的经验熵
（2）递归的从树的叶结点向上回缩。
设一组叶结点回缩到其父结点之前与之后的整体树分别为 $T_B$ 与 $T_A$ ,其对应的损失函数值分别是 $C_{\alpha}(T_B)$ 与 $C_{\alpha}(T_A)$ ， 如果
$$
C_{\alpha}(T_A) \leq C_{\alpha}(T_B)
$$
则进行剪枝，即将父结点变为新的叶结点。
（3）返回2，直至不能继续为止，得到损失函数最小的子树 $T$
5. CART (classification and regresstion tree)算法 –1984
CART由特征选择、树的生成及剪枝组成的二叉树。既可以用于分类也可以用于回归。左分支是“是”的分支，右分支是“否”的分支。
CART是在给定输入随机变量 $X$ 条件下输出随机变量 $Y$ 的条件概率分布的学习方法。
5.1 CART的生成
回归树：平方误差最小化准则
分类树：基尼指数(Gini index) 最小化准则
- 回归树的生成
每个输入空间 $R_m$ 的标签值为，所有输入空间中实例的标签的均值
$$
\hat{c} = ave(y_i|x_i \in R_m)
$$
算法 5.1 (最小二乘回归树生成算法）
输入: 训练数据集 $D$;
输出: 回归树 $f(x)$
在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树:
（1）选择最优切分变量 $j$ 与切分点 $s$ ，求解
$$
\min_{j, s}\left[\min_{c_{1}} \sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min_{c_{2}} \sum_{x_{i} \in R_{2}(j, s)}\left(y_{i}-c_{2}\right)^{2}\right]
$$
遍历变量 $j,$ 对固定的切分变量 $j$ 扫描切分点 $s$ ，选择使上述目标函数达到最小值的对
$(j, s)$
（2）用选定的对 $(j, s)$ 划分区域并决定相应的输出值:
$$
\begin{array}{c}
R_{1}(j, s)=\lbrace x \mid x^{(j)} \leqslant s\rbrace, \quad R_{2}(j, s)=\lbrace x \mid x^{(j)}>s\rbrace \\
\hat{c}{m}=\frac{1}{N{m}} \sum_{x_{i} \in R_{m}(j, s)} y_{i}, \quad x \in R_{m}, \quad m=1,2
\end{array}
$$
（3）继续对两个子区域调用步骤 $(1),(2),$ 直至满足停止条件。
（4）将输入空间划分为 $M$ 个区域 $R_{1}, R_{2}, \cdots, R_{M}$ ，生成决策树:
$$
f(x)=\sum_{m=1}^{M} \hat{c}{m} I\left(x \in R{m}\right)
$$
当数据量大的时候，遍历的效率不高。
- 分类树的生成
分类树用基尼指数选择最优特征， 同时决定该特征的最优二值切分点。
基尼指数的定义
$$
\text{Gini}(p) = \sum_{k = 1}^{K} p_k (1 - p_k) = 1 - \sum_{k=1}^{K}p_k^2
$$
对于给定样本集合D， $p_k = \frac{|C_K|}{|D|}$
基尼指数表示集合D的不确定性，数值越大，样本集合的不确定性就越大。这一点与熵类似。
算法 $5.6(\mathrm{CART}$ 生成算法）
输入: 训练数据集 $D$ ，停止计算的条件;
输出: CART 决策树。
根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树:
（1）设结点的训练数据集为 $D,$ 计算现有特征对该数据集的基尼指数。此时，对每一个特征 $A$ ，对其可能取的每个值 $a$，根据样本点对 $A=a$ 的测试为“是”或“否” 将 $D$ 分割成 $D_{1}$ 和 $D_{2}$ 两部分， 计算 $A=a$ 时的基尼指数。
（2）在所有可能的特征 $A$ 以及它们所有可能的切分点 $a$ 中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
（3）对两个子结点递归地调用 $(1),(2),$ 直至满足停止条件。
（4） 生成 CART 决策树。
5.2 CART剪枝
具体地， 从整体树 $T_0$ 开始剪枝。 对 $T_0$ 的任意内部结点 $t$ ，以 $t$ 为单结点树的损失函数是
$$
C_{\alpha}(t) = C(t) + \alpha
$$
以 $t$ 为根节点的子树 $T_t$ 的损失函数是
$$
C_{\alpha}(T_t) = C(T_t) + \alpha ｜T_t|
$$
当 $\alpha = 0$ 及 $\alpha$ 充分小时，有
$$
C_{\alpha}(T_t) < C_{\alpha}(t)
$$
当 $\alpha$ 增大时，在某一 $\alpha$ 有
$$
C_{\alpha}(T_t) = C_{\alpha}(t)
$$
所以只要 $\alpha =\frac{C(t)-C\left(T_{t}\right)}{\left|T_{t}\right|-1}$，就可以选择结点更少的t。
而Beriman等人证明：可以用递归的方法对树进行剪枝。将 $\alpha$ 逐渐增大，$0 = \alpha_0 < \alpha_1 <\cdots <\alpha_n < +\infty$ ，产生一系列的区间 $[\alpha_i, \alpha_{i+1}), i = 0,1,…,n$ ；剪枝得到的子树序列对应着区间 $\alpha \in [\alpha_i, \alpha_{i+1})$，的最优子树序列 $\lbrace T_0, T_1, \cdots, T_n \rbrace$。然后利用交叉验证挑出一个最好的
算法 5.7 （$\mathbf{C A R T}$ 剪枝算法）
输入: $\mathrm{CART}$ 算法生成的决策树 $T_{0} ;$
输出：最优决策树 $T_{\alpha^{\circ}}$
（1）设 $k=0, T=T_{0}$ 。
（2）设 $\alpha=+\infty$ 。
（3）自下而上地对各内部结点 $t$ 计算 $C\left(T_{t}\right),\left|T_{t}\right|$ 以及
$$
\begin{aligned}
g(t) &=\frac{C(t)-C\left(T_{t}\right)}{\left|T_{t}\right|-1} \\
\alpha &=\min (\alpha, g(t))
\end{aligned}
$$
这里， $T_{t}$ 表示以 $t$ 为根结点的子树， $C\left(T_{t}\right)$ 是对训练数据的预测误差， $\left|T_{t}\right|$ 是 $T_{t}$ 的叶 结点个数。
（4）对 $g(t)=\alpha$ 的内部结点 $t$ 进行剪枝，并对叶结点 $t$ 以多数表决法决定其类，
得到树 $T$ 。
（5）设 $k=k+1, \alpha_{k}=\alpha, T_{k}=T_{\circ}$
（6）如果 $T_{k}$ 不是由根结点及两个叶结点构成的树，则回到步骤 (2)$;$ 否则令
$T_{k}=T_{n}$
（7）采用交叉验证法在子树序列 $T_{0}, T_{1}, \cdots, T_{n}$ 中选取最优子树 $T_{\alpha} \circ$
6. 代码实现
1 | import numpy as np |
1 | # 经验熵 |
1 | datasets = [['青年', '否', '否', '一般', '否'], |
1 | info_gain_train(np.array(datasets)) |
ID3算法
1 | # 定义节点类 二叉树 |
1 | datasets, labels = create_data() |
1 | tree |
1 | dt.predict(['老年', '否', '否', '一般']) |
scikit-learn实例
1 | ## sklearn里并没有实现后剪枝，只有预剪枝操作，例如设置树的最大深度max_depth |
1 | from sklearn.tree import DecisionTreeClassifier |
1 | from sklearn.tree import DecisionTreeClassifier |
Reference
[1]. https://github.com/fengdu78/lihang-code/
[2]. 《统计学习与方法》 – 李航
Naive Bayes
发表于
分类于
ML
生成模型
对于给定数据集，首先基于特征条件独立假设学习输入输出的联合概率分布； 然后基于此模型， 对给定的输入 $x$， 利用贝叶斯定理求出后验概率最大的输出 $y$。 朴素贝叶斯法实现简单， 学习与预测的效率都很高， 是一种常用的方法。
1. 学习与分类
- 首先学习先验概率分布以及条件概率分布。
$$
P(Y=c_k),\quad k=1,2,…k
$$
$$
P(X=x \mid Y=c_{k})=P(X^{(1)}=x^{(1)}, \cdots, X^{(n)}=x^{(n)} \mid Y=c_{k}), \quad k=1,2, \cdots, K
$$
于是学到联合概率分布 $P(X,Y)$
由于朴素贝叶斯假设条件独立，于是条件概率为
$$
\begin{aligned}
P(X=x \mid Y=c_{k}) &=P(X^{(1)}=x^{(1)}, \cdots, X^{(n)}=x^{(n)} \mid Y=c_{k}) \\
&=\prod_{j=1}^{n} P(X^{(j)}=x^{(j)} \mid Y=c_{k})
\end{aligned}
$$
参数学习(极大似然)
$$
P\left(Y=c_{k}\right)=\frac{\sum_{i=1}^{N} I\left(y_{i}=c_{k}\right)}{N}, \quad k=1,2, \cdots, K
$$$$
\begin{array}{l}
P\left(X^{(j)}=a_{j l} \mid Y=c_{k}\right)=\frac{\sum_{i=1}^{N} I\left(x_{i}^{(j)}=a_{j l}, y_{i}=c_{k}\right)}{\sum_{i=1}^{N} I\left(y_{i}=c_{k}\right)} \\
j=1,2, \cdots, n ; \quad l=1,2, \cdots, S_{j} ; \quad k=1,2, \cdots, K
\end{array}
$$分类器
$$
y=f(x)=\arg \max_{c_{k}} \frac{P\left(Y=c_{k}\right) \prod_{j} P\left(X^{(j)}=x^{(j)} \mid Y=c_{k}\right)}{\sum_{k} P\left(Y=c_{k}\right) \prod_{j} P\left(X^{(j)}=x^{(j)} \mid Y=c_{k}\right)}
$$
2. 原理(后验概率最大化 == 期望风险最小化)
假设选择0-1损失函数
$$
L(Y,f(X)) = \begin{cases}
1, & Y \neq f(X) \\
0, & Y = f(X)
\end{cases}
$$
期望风险函数为
$$
R_{\exp }(f)=E[L(Y, f(X))]
$$
期望是对联合分布 $P(X,Y)$取的，由此条件期望
$$
R_{\exp }(f)=E_{X} \sum_{k=1}^{K}\left[L\left(c_{k}, f(X)\right)\right] P\left(c_{k} \mid X\right)
$$
为了使期望风险最小化，只需对 $X=x$ 逐个极小化，
$$
\begin{aligned}
f(x) &=\arg \min_{y \in \mathcal{Y}} \sum_{k=1}^{K} L\left(c_{k}, y\right) P\left(c_{k} \mid X=x\right) \\
&=\arg \min_{y \in \mathcal{Y}} \sum_{k=1}^{K} P\left(y \neq c_{k} \mid X=x\right) \\
&=\arg \min_{y \in \mathcal{Y}}\left(1-P\left(y=c_{k} \mid X=x\right)\right) \\
&=\arg \max_{y \in \mathcal{Y}} P\left(y=c_{k} \mid X=x\right)
\end{aligned}
$$
3. 贝叶斯估计(拉普拉斯平滑)
用极大似然估计可能会出现所要估计的概率值为0的情况。 这时会影响到后验概率的计算结果， 使分类产生偏差。 解决这一问题的方法是采用贝叶斯估计。具体的条件概率的贝叶斯估计是
$$
P_{\lambda}\left(X^{(j)}=a_{j l} \mid Y=c_{k}\right)=\frac{\sum_{i=1}^{N} I\left(x_{i}^{(j)}=a_{j l}, y_{i}=c_{k}\right)+\lambda}{\sum_{i=1}^{N} I\left(y_{i}=c_{k}\right)+S_{j} \lambda}
$$
$l=1,2,\cdots,S_j,k=1,2,…,K$ ，$\lambda \geq 0$，等价于在随机变量各个取值上赋予一个正数。$\lambda = 0$ 是极大似然估计。常取 $\lambda = 1$，称为拉普拉斯平滑。检验可知，概率和为1，并且每个概率大于0
先验概率的贝叶斯估计是
$$
P_{\lambda}\left(Y=c_{k}\right)=\frac{\sum_{i=1}^{N} I\left(y_{i}=c_{k}\right)+\lambda}{N+K \lambda}
$$
4. 代码实现
1 | import numpy as np |
1 | # import data |
1 | class NaiveBayes: |
1 | model = NaiveBayes() |
1 | model.fit(X_train, Y_train) |
1 | result1 = model.predict(X_test) |
1 | model.score(X_test, Y_test) |
scikit-learn 实例
1 | from sklearn.naive_bayes import GaussianNB |
Reference：
[1]. https://github.com/fengdu78/lihang-code
[2]. 《统计学习方法》 – 李航
K-nearest neighbor(K-NN)
基本的分类和回归方法
给定一个训练数据集， 对新的输入实例， 在训练数据集中找到与该实例最邻近的k个实例， 这k个实例的多数属于某个类， 就把该输入实例分为这个类。
1. k 近邻模型
三个基本要素：距离度量，k值选择、分类决策规则
1.1 距离度量
$x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \cdots, x_{i}^{(n)}\right)^{\mathrm{T}}$ $L_{p}$ 距离：
$$
L_{p}\left(x_{i}, x_{j}\right)=\left(\sum_{l=1}^{n}\left|x_{i}^{(l)}-x_{j}^{(l)}\right|^{p}\right)^{\frac{1}{p}}
$$
当 $p=2$ 为欧式距离（常用）
当 $p=1 $ 为曼哈顿距离
当 $p=\infty$ 时，是各个坐标距离的最大值
$$
L_{\infty}(x_{i}, x_{j})=\max_{l}\left|x_{i}^{(l)}-x_{j}^{(l)}\right|
$$
1.2 k值选择
k值选择较小时，近似误差小，估计误差大，过拟合
k值选择较大时，近似误差大，可以减少估计误差
Trick: k值一般取一个比较小的数值。 通常采用交叉验证法来选取最优的k值
1.3 分类决策规则
往往是多数表决：由输入实例的k个邻近的训练实例中的多数类决定输入实例的类
误分类率：
$$
\frac{1}{k} \sum_{x_{i} \in N_{k}(x)} I\left(y_{i} \neq c_{j}\right)=1-\frac{1}{k} \sum_{x_{i} \in N_{k}(x)} I\left(y_{i}=c_{j}\right)
$$
2. 模型实现：kd树
实现k近邻法时， 主要考虑的问题是如何对训练数据进行快速k近邻搜索。 这点在特征空间的维数大及训练数据容量大时尤其必要
线性扫描不可取，因为遍历所有的数据计算量太大
解决方法：kd树（kd tree）
kd树是二叉树， 平衡的kd树搜索时的效率未必是最优的
算法 3.2 (构造平衡 $k d$ 树）
输入: $k$ 维空间数据集 $T= \lbrace x_{1}, x_{2}, \cdots, x_{N} \rbrace$，其中 $x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \cdots, x_{i}^{(k)}\right)^{\mathrm{T}}$，$i=1,2, \cdots, N$
输出: $k d$ 树。
(1) 开始: 构造根结点，根结点对应于包含 $T$ 的 $k$ 维空间的超矩形区域。
$x^{(1)}$ 为坐标轴，以 $T$ 中所有实例的 $x^{(1)}$ 坐标的中位数为切分点，将根结点选择对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴 $x^{(1)}$ 垂直的超平面实现。
由根结点生成深度为 1 的左、右子结点: 左子结点对应坐标 $x^{(1)}$ 小于切分点的子$x^{(1)}$ 大于切分点的子区域。 区域，右子结点对应于坐标将落在切分超平面上的实例点保存在根结点。
(2)重复: 对深度为 $j$ 的结点，选择 $x^{(l)}$ 为切分的坐标轴，$l=j(\bmod k)+1,$ 以该结点的区域中所有实例的 $x^{(l)}$ 坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴 $x^{(l)}$ 垂直的超平面实现。
由该结点生成深度为 $j+1$ 的左、右子结点：左子结点对应坐标 $x^{(l)}$ 小于切分点 的子区域，右子结点对应坐标 $x^{(l)}$ 大于切分点的子区域。
将落在切分超平面上的实例点保存在该结点。
(3)直到两个子区域没有实例存在时停止。从而形成 $k d$ 树的区域划分.
搜索kd树
给定一个目标点， 搜索其最近邻。 首先找到包含目标点的叶结点； 然后从该叶结点出发， 依次回退到父结点； 不断查找与目标点最邻近的结点， 当确定不可能存在更近的结点时终止
算法 $3.3$(用 $k d$ 树的最近邻搜索)
输入: 已构造的 $k d$ 树，目标点 $x$
输出: $x$ 的最近邻。
(1) 在 $k d$ 树中找出包含目标点 $x$ 的叶结点: 从根结点出发，递归地向下访问 $k d$ 树。若目标点 $x$ 当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点。直到子结点为叶结点为止。
(2) 以此叶结点为“当前最近点”。
(3) 递归地向上回退，在每个结点进行以下操作:
(a)如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”。
(b)当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体地，检查另一子结点对应的 区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。
如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动 到另一个子结点。接着，递归地进行最近邻搜索;
如果不相交，向上回退。
(4) 当回退到根结点时，搜索结束。最后的“当前最近点”即为 $x$ 的最近邻点。
3. 代码实现
1 | ## max()函数技巧 |
K-NN
1 | import numpy as np |
1 | ## load data |
1 | data = np.array(df.iloc[:,:]) # 数据由Datafrom转化为array |
1 | ## 数据标准化 |
- 线性遍历最近的K个点
1 | class KNN_LinearSearch: |
1 | KNN = KNN_LinearSearch(X_train, Y_train) |
- Kd树-最近邻搜索
1 | class KdNode: |
1 | ## 寻找最近的k个点 |
1 | data = [[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]] |
1 | from time import clock |
1 | ret = find_nearest(kd, [3, 4.5]) |
1 | N = 400000 |
Reference:
[2] 《统计学习方法》 —李航
Perceptron(未完待更)
二分类线性模型
1. 模型
$$
f(x)=\operatorname{sign}(w \cdot x+b)
$$
Loss function:
$$
L(w, b)=-\sum_{x_{i} \in M} y_{i}\left(w \cdot x_{i}+b\right)
$$
因此其目标函数为
$$
\min_{w, b}L(w, b)=-\sum_{x_{i} \in M} y_{i}(w \cdot x_{i}+b)
$$
优化方法：
- 随机梯度下降(SGD)：每次更新使用一个数据
算法2.1:
输入：训练数据集 $T = {(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$ ，其中 $x_{i} \in \mathcal{X}=\mathbf{R}^{n}$，$y_{i} \in \mathcal{Y}=\lbrace -1,+1 \rbrace$, $i=1,2, \cdots, N $ ；学习率 $\eta (0<\eta \leqslant 1) ;$
输出 ：$ w, b $ 知机模型 $f(x)=\operatorname{sign}(w \cdot x+b)$ 。
(1) 选取初值 $w_{0}, b_{0} ;$
(2) 在训练集中选取数据 $\left(x_{i}, y_{i}\right) ;$
(3) 如果 $y_{i}\left(w \cdot x_{i}+b\right) \leqslant 0$,
$$
\begin{array}{l}
w \leftarrow w+\eta y_{i} x_{i} \\
b \leftarrow b+\eta y_{i}
\end{array}
$$
(4) 转至 (2)，直至训练集中没有误分类点。
2. 算法的收敛性
对于线性可分的的数据集，perceptron经过有限次迭代一定会收敛
证明过程待后续补充：
3. 感知机的对偶形式
对偶形式的基本想法是，将 $w$ 和 $b$ 表示为实例 $x_{i}$ 和标记 $y_{i}$ 的线性组合的形式, 通过求解其系数而求得 $w$ 和 $b$ 。不失一般性，在算法中可假设初始值 $w_{0}, b_{0}$ 均为
$0 。$ 对误分类点 $\left(x_{i}, y_{i}\right)$ 通过
$$
\begin{array}{l}
w \leftarrow w+\eta y_{i} x_{i} \\
b \leftarrow b+\eta y_{i}
\end{array}
$$
最后学得的 $w,b$ 可以表示为
$$
\begin{array}{c}
w=\sum_{i=1}^{N} \alpha_{i} y_{i} x_{i} \\
b=\sum_{i=1}^{N} \alpha_{i} y_{i}
\end{array}
$$
算法 2.2(感知机学习算法的对偶形式)
输入：线性可分的数据集 $T = \lbrace (x_1,y_1),(x_2,y_2),…,(x_N,y_N) \rbrace$, 其中 $x_{i} \in \mathbf{R}^{n}$，$y_{i} \in\lbrace -1,+1 \rbrace, i=1,2, \cdots, N $ 学习率 $\eta(0<\eta \leqslant 1) ;$
输 出：$\alpha, b$； 感 知 机 模型 $f(x)=\operatorname{sign}\left(\sum_{j=1}^{N} \alpha_{j} y_{j} x_{j} \cdot x+b\right), \quad$ 其 中 $\alpha=\left(\alpha_{1}, \alpha_{2}, \cdots, \alpha_{N}\right)^{\mathrm{T}}$
(1) $\alpha \leftarrow 0, b \leftarrow 0 ;$
(2) 在训练集中选取数据 $\left(x_{i}, y_{i}\right) ;$
(3) 如果 $y_{i}\left(\sum_{j=1}^{N} \alpha_{j} y_{j} x_{j} \cdot x_{i}+b\right) \leqslant 0$,
$$
\begin{array}{l}
\alpha_{i} \leftarrow \alpha_{i}+\eta \\
b \leftarrow b+\eta y_{i}
\end{array}
$$
(4）转至 (2) 直到没有误分类数据。
讨论感知机的对偶有什么意义？
这两个不应该是一样的吗？
4. 感知机代码
1 | import numpy as np |
RL总结
发表于
分类于
ML
1. 有/无模型学习
有模型学习
方法：动态规划
无模型
方法：蒙特卡洛、时序差分
2. 同/异策学习
- 同策回合更新（策略$\pi$和环境交互得到==完整轨迹==，然后学习更新价值函数$V^{\pi}$）
- 每次访问回合更新
- 首次访问回合更新
- 带起始探索的同策回合更新（避免陷入局部最优）
- 基于柔性策略的同策回合更新（避免陷入局部最优）
- 异策回合更新（行为策略$\pi’$和环境交互得到==完整轨迹==，目标策略$\pi$学习更新价值函数$V^{\pi}$）
- 重要性采样 李宏毅讲的很好
- 异策回合更新策略评估 # 利用行为策略估计目标策略的动作状态价值对函数和状态价值对函数
- 异策回合更新最优策略的求解 # 评估 + 改进 改进部分是依据每个状态下的最大价值动作。
3. 回合更新/时序差分更新
- 回合更新（无偏差但方差大，和环境完整的交互一个回合）
- 利用蒙特卡洛方法，对完整的G进行无偏差估计，但是方差较大
- 时序差分更新（有偏差，但方差小，收敛快，n步就和环境交互n次）
- 同策，策略$\pi$生成轨迹，然后策略$\pi$学习更新$q(s,·)$，然后根据q值更新策略
- $TD(\lambda)$(除极端的无穷外是时序差分，同策)
- SARSA算法 = 单/多步时序差分（策略评估）+ 策略改进 （同策）
- 期望SARSA算法：$U_t=R_{t+1}+\gamma \sum_{a\in \mathcal{A}}\pi(a|S_{t+1})q(S_{t+1},a)$ 也有单步和多步 （同策）
- 异策，行为策略$b$和环境进行交互得到轨迹，然后依据此轨迹对策略$\pi$进行学习更新q值，然后根据q值对策略进行更新
- 单步/多步时序差分
- SARSA算法/期望SARSA算法
- Q-learning
- Double Q-learning
- 同策，策略$\pi$生成轨迹，然后策略$\pi$学习更新$q(s,·)$，然后根据q值更新策略
- 资格迹
- 资格迹和以上时序差分策略都可以结合，不管是同策还是异策。
4. 基于价值/策略/二者结合
基于价值的
- 蒙特卡洛方法估计G
- 动态规划
- $TD(\lambda)$
- SARSA
- Q-learning
- Double Q-learning
基于策略（回合更新，利用策略交互不断得到完整轨迹，多个回合更新目标是使策略$\pi$的期望$E(G)$最大
- 同策回合更新策略梯度算法
- 异策回合更新策略梯度算法
执行者/评论者方法 = 价值更新 + 策略更新 (价值更新部分使用深度强化学习方法+单步时序差分，策略更新也是用深度强化学习方法)
动作价值执行者评论者算法 $E(\Psi_t \nabla \ln\pi(a_t|s_t;\theta)), \Psi_t=\gamma^tq_{\pi}(s_t,a_t)$
A2C-优势执行者/评论者算法 $\Psi_t=\gamma^t[q_{\pi}(s_t,a_t)-v_{\pi}(s_t)]$
时序差分执行者/评论者算法 $\Psi_t=\gamma^t[r_{t+1}+\gamma v_{\pi}(s_{t+1})-v_{\pi}(s_t)]$
A3C-异步优势执行者/评论者算法；利用多个agent同时搜集经验更新自己的参数并传给一个总的agent，可以单/多步时序差分
带资格迹的执行者评论者算法
基于代理优势的同策算法
- 邻近策略优化PPO2，在目标中添加描述分布差异的指标，$E_{\pi(\theta_{old})}[\min(\frac{\pi(A_t|S_t;\theta_{new})}{\pi(A_t|S_t;\theta_{old})}a_{\pi(\theta_{old})}(S_a,A_t), a_{\pi(\theta_{old})}(S_a,A_t)+\varepsilon|a_{\pi(\theta_{old})}(S_a,A_t)|)]$
信任域算法
自然策略梯度算法NPG，最大化代理优势，并添加约束条件，KL散度小于$\delta$，但NPG是对目标函数进行泰勒一阶近似，约束条件进行泰勒二阶近似。对近似后的问题进行求解。
$\mathbf{\theta} \leftarrow \mathbf{\theta} + \sqrt{\frac{2\delta}{\mathbf{g^TF^{-1}g}}}\mathbf{F^{-1}g}$
带共轭梯度的自然策略梯度算法
利用共轭梯度算法求解$\mathbf{F^{-1}g}，\mathbf{Fx=g}$，$\mathbf{\theta} \leftarrow \mathbf{\theta} + \sqrt{\frac{2\delta}{\mathbf{x^TFx}}}\mathbf{x}$
信赖域策略优化TRPO，在NPG的基础上修改得到，因为其近似问题可能不一定导致问题有最优解，在个别情况下可能使情况更糟，TRPO对迭代式进行改进
$$
\boldsymbol{\theta_{k+1} = \theta_k}+\alpha^j \sqrt{\frac{2\delta}{\boldsymbol{[x([\theta_k])^T]Fx([\theta_k])}}}\boldsymbol{x([\theta_k])}
$$
其中$\alpha$是学习参数，$j$是某个非负整数，对于自然策略梯度$j$总是0，TRPO用一下方法确定$j$的值：从非负整数d到0，1，2…中依次寻找首个满足期望KL散度约束并且能够提升代理梯度的值。不过由于一般近似的不错，所以一般为0，个别情况为1，其他值几乎没有。Kronecker因子信任域执行者/评论者算法 ACKTR，将Kronecker因子近似曲率算法用到信任域策略优化算法中，减少计算量
重要性采样异策执行者/评论者算法
- 异策执行者/评论者算法，将目标期望$E_{\pi(\boldsymbol{\theta})}(\Psi_t \nabla \ln\pi(a_t|s_t;\theta))$，变为$E_b(\frac{\pi(A_t|S_t;\boldsymbol{\theta})}{b(A_t|S_t)}\Psi_t \nabla \ln\pi(a_t|s_t;\theta))$
- 带经验回放的异策执行者/评论者算法（ACER）
柔性执行者/评论者算法（SAC）
确定性策略
- 同策确定性算法
- 异策确定性算法
- 深度确定性策略梯度算法(DDPG)
- 双重延迟深度确定性策略梯度算法(TD3)
5. 深度强化学习/非深度强化学习
- 深度Q学习
- 双重深度Q网络
- 对偶深度Q网络
- 对于某个状态S，有些action可能采样不到，但通过对偶深度Q网络也可以更新
- Noise Net
- 对采样的Q网络的参数添加噪声，探索
- Distributional Q_function
- 该方法认为Q(s, a)有一个分布，即相同的状态和行为的价值，是一个分布，用神经网络估计这个分布
6. 离线学习/在线学习（待更）
资格迹
如何理解资格迹
考虑这样一个回合$S_0,A_0,R_1,S_1,A_1,…,R_n,S_n,A_n$
我们知道对于 $(S_0,A_0)$计算$q_(S_0,A_0)$，可以用$U(S_0,A_0)=R_1+q(S_1,A_1)$近似为真实值去更新$q_(S_0,A_0)$，这个时候时序误差为$TD_{error}=U(S_0,A_0)-q(S_0,A_0)$，时序误差所包含的信息全部用来更新$q_(S_0,A_0)$
$(S_5,A_5)$时，
$U(S_5,A_5)=R_6+\gamma q(S_6,A_6)$
$U(S_0,A_0)=R_1+\gamma R_2+\gamma ^2R_3+\gamma ^3R_4+\gamma ^4R_5+\gamma ^5U(S_5,A_5) $
这个时候$(S_5,A_5)$处的时序误差对于更新 $(S_0,A_0)$处的$q_(S_0,A_0)$所产生的作用是$\gamma ^5 *TD_{error}$
从上式可以看出与$(S_0,A_0)$状态相距越远的$(S_k,A_k)$所产生的时序误差对于$(S_0,A_0)$所起的作用就越小，所以间隔步数每增加一步，前面的每个动作状态对的资格迹都要进行衰减.
比如在$t=4$时，
$U(S_0,A_0):\gamma^4,U(S_1,A_1):\gamma^3，U(S_2,A_2):\gamma^2，U(S_3,A_3):\gamma$。
前进一步，$t=5$时,
$U(S_0,A_0):\gamma^5,U(S_1,A_1):\gamma^4，U(S_2,A_2):\gamma^3，U(S_3,A_3):\gamma^2，U(S_4,A_4):\gamma$
而对于$TD(\lambda)$ 来说
$U(S_0,A_0)=R_1+q(S_1,A_1)\qquad 1-\lambda$
$U(S_0,A_0)=R_1+\gamma U(S_1,A_1) \qquad (1-\lambda)\lambda$
$U(S_0,A_0)=R_1+\gamma R_2+\gamma ^2 U(S_2,A_2) \qquad (1-\lambda)\lambda ^2$
…….
所以其间隔步数每增加一步，当前状态动作价值产生的时序误差，用到更新前面的状态动作价值时要相应的衰减对应$\gamma\lambda$次幂。
考虑资格迹其实看起来很合理，因为当回合轨迹逐渐延伸，不仅当前的动作状态价值需要更新，由于新的信息的出现，又会使得之前已经更新的动作状态价值，和我们的$U$(类似机器学习的目标)之间重新产生新的误差，我们理应将这部分考虑到损失函数中，进行梯度更新。
带资格迹的梯度下降
《强化学习导论》Richard S.Sutton：资格迹$\mathbf{z}_t$是一个和权值向量$\mathbf{w}_t$ 同维度的向量，在$TD(\lambda)$中，资格迹向量被初始化为零，然后在每一步累加价值函数的梯度，以$\gamma\lambda$
$$
\begin{align}
\mathbf{z_{-1}} &= \mathbf{0}, \\
\mathbf{z_t} &= \gamma\lambda\mathbf{z_{t-1}}+\nabla\hat{v}(S_t,\mathbf{w_t}), 0 \leq t\leq T
\end{align}
$$
某一时刻的单步时序差分误差为
$$
\delta_t=R_{t+1}+\gamma\hat{v}(S_{t+1},\mathbf{w_t})-\hat{v}(S_t,\mathbf{w_t})
$$
在$TD(\lambda)$中，权值向量每一步的更新正比于时序差分的标量的误差和资格迹。
$$
\mathbf{w_{t+1}}=\mathbf{w_t}+\alpha\delta_t\mathbf{z_t}
$$
当时看资格迹时候特别迷这一部分，其实自己稍微推导两个回合就明白了。这里的资格迹其实就是把后面的梯度中的学习率和时序误差提出来剩下的内容。因为是利用函数近似，所以会包含价值的梯度。具体推导两步。
当$t=0$时：
$$
\begin{align*}
U(S_0) &= R_1+\gamma v(S_1,\mathbf{w_0}) \\
Loss &= [U(S_0)-v(S_0,\mathbf{w_0})]^2 \\
\mathbf{w_1} &= \mathbf{w_0}+\alpha[U(S_0)-v(S_0,\mathbf{w_0})]\nabla v(S_0,\mathbf{w_0}) \\
&= \mathbf{w_0}+\alpha\delta_0\nabla v(S_0,\mathbf{w_0}) \\
\mathbf{z_0} &=\mathbf{0} + \nabla v(S_0,\mathbf{w_0})
\end{align*}
$$
从上式资格迹可以看出，其和权值向量是同维度的。
当$t=1$时：
$$
U(S_1)=R_2+\gamma v(S_2,\mathbf{w_1})
$$
这时时序误差为$\delta_1=U(S_1)-v(S_1)$，而$U(S_0) = R_1 + \gamma U(S_1)$，所以在$TD(\lambda)$下，$U(S_0)$和$v(S_0,\mathbf{w_1})$的误差为$\gamma\lambda\delta_1$，这两部分的误差理应都考虑，这个时候的损失函数就变为
$$
Loss=[U(S_0)-v(S_0,\mathbf{w_1})]^2 + [U(S_1)-v(S_1,\mathbf{w_1})]^2
$$
进行梯度更新
$$
\begin{align*}
\mathbf{w_2} &= \mathbf{w_1}+\alpha[U(S_0)-v(S_0,\mathbf{w_1})]\nabla v(S_0,\mathbf{w_1})+ \alpha[U(S_1)-v(S_1,\mathbf{w_1})]\nabla v(S_1,\mathbf{w_1})\\
&= \mathbf{w_1}+\alpha\gamma\lambda\delta_1\nabla v(S_0,\mathbf{w_1}) +\alpha\delta_1\nabla v(S_1,\mathbf{w_1})\\
\end{align*}
$$
把学习率和时序误差$\delta _1$提出来，得到资格迹
$$
\mathbf{z_1} =\gamma\lambda\nabla v(S_0,\mathbf{w_1}) + \nabla v(S_1,\mathbf{w_1})
$$
由于$\nabla v(S_0,\mathbf{w_0})=\nabla v(S_0,\mathbf{w_1})$，所以
$$
\mathbf{z_1} =\gamma\lambda\mathbf{z_0} + \nabla v(S_1,\mathbf{w_1})
$$
以次往下更新……