Machine Learning: from Theory to Practice

Author: TSINGHUA Computer Science & Finance Shiying Zhang 2021011056

Chapter0 Definition and Terms

人工智能 / Artificial Intelligence
计算机科学领域，专注于开发通常需要人类智能的任务，例如策略博弈、自然语言处理等
机器学习 / Machine Learning
是人工智能的一个子集，基于训练的算法（training algorithm），即对数据集进行学习和模式识别，从而进行预测或决策，而非对问题进行直接的人为编程
- 监督学习 / Supervised Learning：用于训练的数据集是标签的（labeled data）
  - 回归问题 / Regression：Trees (Random Forests, GBM, DT / Decision Trees 决策树), Linear / GLMS, Ensemble, Neural Networks
  - 分类问题 / Classification：SVM (支撑向量机 / Support Vector Machines), Discriminant Analysis, GNB (高斯朴素贝叶斯分类 / Gaussian Naïve Bayes) , Nearest Neighbor
- 无监督学习 / Unsupervised Learning：用于训练的数据集没有预先标签（unlabeled data）
  聚类 / Clustering：K-Means (K-均值聚类), Gaussian Mixture Model (高斯混合模型), Hierarchical, Neural Networks
- 半监督学习 / Semi-Supervised Learning：同时使用标签的和未标签的数据集进行训练（algorithm 用 labeled data 识别模式，用 unlabeled data 进一步学习和理解模式）
  self-training, generative models, S3VMs, Graph based algorithms, Multiview algorithms
- 强化学习 / Reinforcement Learning：根据环境反馈进行决策，通过trial and error学习
  Markov Decision Process (MDP), Monte-Carlo Simulation (蒙特卡洛模拟)
- 深度学习 / Deep Learning：使用Artificial Neural Network的特定领域
  全连接神经网络，卷积神经网络，循环神经网络
除此之外，机器学习还可以分为基于模型学习和基于实例学习：
- 基于模型学习 / Model-based Learning：对数据进行整体归纳提炼（从实例中构建模型，用模型进行预测）
- 基于实例学习 / Instance-based Learning：未对数据进行整体归纳提炼（学习示例，然后用相似度度量新的实例和已经学习的实例的关系，从而泛化新实例）
机器学习过程的两个阶段是训练（train / fit）和推断（inference / predict）

Chapter1 启发式搜索 Search

寻找起点s到终点g的最短路（最短耗散值）

引入：宽度优先搜索（BFS）+ Dijkstra算法、深度优先搜索（DFS）

1.1 A^* 算法

\begin{matrix} 评 价 函 数 f (n) = g (n) + 启 发 函 数 h (n) \\ \begin{aligned} g^{*} (n) : 从 起 点 s 到 n 的 最 短 路 径 的 耗 散 值 \\ h^{*} (n) : 从 n 到 终 点 g 的 最 短 路 径 的 耗 散 值 \\ f^{*} (n) : 从 起 点 s 经 过 啊 n 到 终 点 g 的 最 短 路 径 的 耗 散 值 \\ f (n), g (n), h (n) 分 别 是 f^{*} (n), g^{*} (n) 和 h^{*} (n) 的 估 计 值 \end{aligned} \\ Condition : h (n) \leq h^{*} (n) \end{matrix}

1. 伪代码及算法描述

$f(n)$ $f(终点)$ （在当前CLOSED表中）最小

Notation $m_j$ $m_k$ $m_l$ $m_i$ ：表示所有的子节点

算法：

\begin{aligned} 1 O P E N := (s), C L O S E D := () \\ 2 while OPEN 不 空 do : \\ 3 n := F i r s t (O P E N) \\ 4 if n == g o a l then return n \\ 5 E x p a n d (n) \to m_{i}, C a l c f (n, m_{i}) = g (n, m_{i}) + h (m_{i}) \\ 6 R e m o v e (n, O P E N), A d d (n, C L O S E D) \\ 7 s w i t c h m_{i} : \\ 8 A d d (m_{j}, O P E N), 标 记 m_{j} 连 接 到 n 的 指 针 \\ 9 if f (n, m_{k}) < f (m_{k}) then \\ 10 f (m_{k}) = f (n, m_{k}), 标 记 m_{k} 连 接 到 n 的 指 针 \\ 11 if f (n, m_{l}) < f (m_{l}) then \\ 12 f (m_{l}) = f (n, m_{l}), 标 记 m_{l} 连 接 到 n 的 指 针 \\ 13 A d d (m_{l}, O P E N) \\ 14 O P E N 中 的 节 点 按 f 值 从 小 到 大 排 序 \end{aligned}

举例：

g(n) $A^*$ $m_l$ $OPEN$ 表中，因此可能会多次重复扩展同一个节点，导致搜索效率下降

2. 算法分析

可采纳性定理 $h(n) \le\ h^*(n)$ 保证了A^*算法的正确性（只要存在起点s到重点g的路径）
启发信息定理 $h_2(n) > h_1(n)$ $A_2^*扩展的结点数 \le A_1^*扩展的节点数$

启发函数 $h(·)$ 的评价方法平均分叉数b^* $b^*$ $h(·)$ $d$ $N$ $N = \frac{b^{*(d+1)}-1}{b^*-1}$ 实验表明 $b^*$ 是一个比较稳定的常数，同一问题基本不随问题规模变化

1.2 改进版A^*算法

$h(·)$ 的单调性 $n_i$ $n_j$ $n_j$ $n_i$ 的子节点），满足：

\begin{matrix} h (n_{i}) - h (n_{j}) \leq c (n_{i}, n_{j}) \\ h (g) = 0 \end{matrix}

$h(·)$ 是单调的

1. 伪代码及算法描述

Notation $f_m$ $OPEN$ $f$ 值

算法：

\begin{aligned} 1 O P E N := (s), C L O S E D := (), f (s) = g (s) + h (s), f_{m} = 0 \\ 2 while OPEN 不 空 do : \\ 3 N E S T = {n_{i} | f (n_{i}) < f_{m}, n_{i} \in O P E N} \\ 4 if NEST \neq () then \\ 5 n = N E S T 中 g 最 小 的 节 点 \\ 6 else n = F i r s t (O P E N), f_{m} = f (n) \\ 7 if n == g o a l then return n \\ 8 E x p a n d (n) \to m_{i}, C a l c f (n, m_{i}) = g (n, m_{i}) + h (m_{i}) \\ 9 R e m o v e (n, O P E N), A d d (n, C L O S E D) \\ 10 s w i t c h m_{i} : \\ 11 A d d (m_{j}, O P E N), 标 记 m_{j} 连 接 到 n 的 指 针 \\ 12 if f (n, m_{k}) < f (m_{k}) then \\ 13 f (m_{k}) = f (n, m_{k}), 标 记 m_{k} 连 接 到 n 的 指 针 \\ 14 if f (n, m_{l}) < f (m_{l}) then \\ 15 f (m_{l}) = f (n, m_{l}), 标 记 m_{l} 连 接 到 n 的 指 针 \\ 16 A d d (m_{l}, O P E N) \\ 17 O P E N 中 的 节 点 按 f 值 从 小 到 大 排 序 \end{aligned}

举例：（注意，下例不满足启发函数单调性条件）

$NEST$ $h(·):=0$ $h(·)$ 满足单调性

2. 算法分析

$h(·)$ $A^*$ $n$ $n$ $n$ $g(n) = g^*(n)$
- $h(·)$ $A^*$ 条件
$OPEN$ $f(n)\lt f^*(g)$ $A^*$ $A^*$ $f(n) \le f^*(g)$

1.3 viterbi 算法

如何通俗地讲解 viterbi 算法？

维特比算法（英语：Viterbi algorithm）是一种动态规划算法，它用于寻找最有可能产生观测事件序列的维特比路径——隐含状态序列

其中，动态转移方程如下：

\begin{matrix} Q (W_{i, j}) = \min_{k} (Q (W_{i - 1, k}) + D (W_{i - 1, k}, W_{i, j})) \\ 其 中 ， Q (W_{i, j}) 表 示 起 点 到 点 W_{i, j} 的 最 短 路 径 距 离 ， \\ D (W_{i - 1, k}, W_{i, j}) 表 示 W_{i - 1, k} 到 W_{i, j} 的 距 离 \end{matrix}

算法：

\begin{aligned} 1 f o r i i n r a n g e (0, n) \\ 2 f o r j i n r a n g e (0, k) \\ 3 Q (W_{i, j}) = m i n_{k} (Q (W_{i - 1, k}) + D (W_{i - 1, k}, W_{i, j})) \\ 3 R e c o r d (p a t h (W_{i - 1, k}) + W_{i, j}) \\ 4 f i n d M a x_{k} (Q (W_{n, k}) + D (W_{n, k}, W_{n + 1})) \end{aligned}

1. 汉字识别后处理

\begin{aligned} N o t a t i o n s : \\ S ： 表 示 待 判 定 的 句 子 （ 汉 字 序 列 变 量 ） \\ O ： 表 示 输 入 图 像 或 拼 音 等 信 息 \\ w_{i} ： 表 示 句 子 中 的 第 i 个 字 \\ — — — — — — — — — — — — — — — — — — — — — — — — — — — — \\ P (S | O) = \frac{P (S) P (O | S)}{P (O)} \\ 其 中 ， P (S) = \prod_{i = 1}^{n} P (w_{i} | w_{1} . . w_{i - 1}) ， P (O) 为 常 量 ， P (O | S) 用 识 别 信 度 C F 代 替 \\ 二 元 模 型 ： P (S) = \prod_{i = 1}^{n} P (w_{i} | w_{i - 1}) \overset{f r e q u e n c y}{\Rightarrow} \frac{w_{i - 1} w_{i} 同 现 的 次 数}{w_{i - 1} 出 现 的 次 数} \\ 三 元 模 型 ： P (S) = \prod_{i = 1}^{n} P (w_{i} | w_{i - 1} w_{i - 2}) \overset{f r e q u e n c y}{\Rightarrow} \frac{w_{i - 2} w_{i - 1} w_{i} 同 现 的 次 数}{w_{i - 1} 出 现 的 次 数} \\ 平 滑 处 理 ： 解 决 P (w_{i} | w_{i - 1}) 可 能 为 0 的 问 题 \\ P (w_{i} | w_{i - 1}) \leftarrow λ P (w_{i} | w_{i - 1}) + (1 - λ) P (w_{i}) \\ \Rightarrow 二 元 模 型 下 ， 问 题 转 换 为 了 ： 求 \prod_{i = 1}^{n} P (w_{i} | w_{i - 1}) CF (w_{i}) 最 大 \end{aligned}

2. 拼音输入法

$P(O|S) ≈ 1$ $CF$ 为常数，因此问题转变为：

\begin{matrix} M a x (\prod_{i = 1}^{n} P (w_{i} | w_{i - 1})) \\ 等 价 于 求 m i n (- \sum_{i = 1}^{n} l o g (P (w_{i} | w_{i - 1}))) \end{matrix}

Chapter2 神经网络

神经网络的理论推导 + PyTorch语法实践

MLP / MultiLayer Perceptron（多层感知器神经网络）: 由多层全连接神经网络（FCN / Fully-Connected Network）组成的 feed forward neural network，由 input layer，output layer 和 hidden layer 共同组成
CNN / Convolutional Neural Network（卷积神经网络）：包含卷积计算且具有深度结构的 feed forward neural network，包括了input layer, convolutional layer, Relu layer, pooling layer and fully-connected / linear layer
RNN / Recurrent Neural Network（循环神经网络）：以序列数据为输入，在序列的演进方向进行 recursion，且所有节点/循环单元按链式连接的 recursive neural network
- LSTM / Long Short-Term Memory（长短期记忆网络）
- GRU / Gated Recurrent Unit（门控循环单元）

2.1 全连接神经网络 MLP / FCN

结构：输入层（input layer）+ 若干隐含层（hidden layer）+ 输出层（output layer）

激活函数 Activation Function
$sgn(x)$ $\{-1, 1\}$ $\sigma(x) = \frac{1}{1 + e^{-x}}$ $[0, 1]$ $tanh(x) = \frac{e^{x} - e^{-x}}{e^{x} + e^{-x}}$ $[-1, 1]$ $ReLU(x) = max(0, x)$ $o_k = \frac{e^{x_k}}{\sum_{i=1}^me^{x_i}}$ $\sum_{k=1}^mo_k = 1$
损失函数 Loss Function
- “误差平方和”损失函数
  $E_d(w) = \frac{1}{2}\sum_{k=1}^m(t_{kd} - o_{kd})^2$ 随机梯度下降算法 $E(w) = \frac{1}{2}\sum_{d=1}^n\sum_{k=1}^m(t_{kd} - o_{kd})^2$ ，对应批量梯度下降算法
  小批量梯度下降算法 $B$ $E(w) = \frac{1}{2}\sum_{i=k}^{k+B}\sum_{k=1}^m(t_{ki} - o_{ki})^2$
- 交叉熵损失函数
  $\begin{matrix} H_{d} (w) = - \sum_{k = 1}^{M} t_{k d} l o g (o_{k d}), 要求 o_{k d} 是概率值，假设有 M 个输出 \\ H (w) = \sum_{d = 1}^{N} H_{d} (w) = - \sum_{d = 1}^{N} \sum_{k = 1}^{M} t_{k d} l o g (o_{k d}) ， N 表示样本数量 \\ 其中， t_{k d} 表示样本 d 对应的希望输出值， o_{k d} 表示对应的实际输出值（概率值） \end{matrix}$
梯度下降法 Gradient Descent
$\begin{matrix} \nabla_{w} E (w) = [\frac{\partial E (w)}{\partial w_{1}}, \frac{\partial E (w)}{\partial w_{2}}, . . ., \frac{\partial E (w)}{\partial w_{n}}] \\ w^{n e w} = w^{o l d} + Δ w ，其中： Δ w = - η \nabla_{w} E (w) \\ 这里的 w 即为 F C N 隐含层的权重参数 \end{matrix}$
反向传播 Back Propagation
算法过程：
$\begin{aligned} 1 初始化所有权值为小的随机值（如 [- 0.05, 0.05] ） \\ 2 在满足结束条件前： \\ 3 每个训练样例 \to 输入网络，计算每个单元 u 的输出 o_{u} \\ 4 对于输出层单元 k ，计算误差项： δ_{k} = (t_{k} - o_{k}) o_{k} (1 - o_{k}) \\ 5 对于隐含层单元 h ，计算误差项： δ_{h} = o_{h} (1 - o_{h}) \sum_{k \in 后继 (h)} δ_{k} w_{k, h} \\ 6 更新每个权值： w_{j i} + = Δ w_{j i} ，其中 Δ w_{j i} = η δ_{j} x_{j i} \end{aligned}$
理论推导：
Notations $x_{ji}$ ：神经元j（即那一层的第j个神经元）的第i $w_{ji}$ ：神经元j（即那一层的第j个神经元）的第i $net_j$ j $\mathbf{w_j}^T$ $\mathbf{x_j}$ $\delta_j$ $(t_j-o_j)o_j(1-o_j)$ $\sigma(x)$ $\frac{1}{1 + e^{-x}}$
$\vec{x_{j}}, \vec{w_{j}} \overset{\sum}{\to} n e t_{j} \overset{σ}{\to} o_{j} \overset{E_{d}}{\to} \frac{1}{2} \sum_{k = 1}^{m} (t_{k} - o_{k})^{2}$
- 输出层
  $\begin{matrix} proof : \frac{\partial E_{d}}{\partial w_{j i}} = - δ_{j} x_{j i}, δ_{j} = (t_{j} - o_{j}) o_{j} (1 - o_{j}) \\ \begin{aligned} \frac{\partial E_{d}}{\partial w_{j i}} & = \frac{\partial E_{d}}{\partial n e t_{j}} \cdot \frac{\partial n e t_{j}}{\partial w_{j i}} (= x_{j i}) \\ 其中， \frac{\partial E_{d}}{\partial n e t_{j}} & = \frac{\partial E_{d}}{\partial o_{j}} \cdot \frac{\partial o_{j}}{\partial n e t_{j}} (= \frac{\partial σ}{\partial n e t_{j}}) \\ = - (t_{j} - o_{j}) \cdot o_{j} (1 - o_{j}) \\ = - δ_{j} \\ ∴ \frac{\partial E_{d}}{\partial w_{j i}} = - & δ_{j} x_{j i} \end{aligned} \end{matrix}$
- 隐含层
  最靠近输出层的隐含层：
  $\begin{matrix} proof : \frac{\partial E_{d}}{\partial w_{j i}} = - δ_{j} x_{j i}, δ_{j} = o_{j} (1 - o_{j}) \sum_{k \in 后继 (j)} δ_{k} w_{k, j} \\ \begin{aligned} \frac{\partial E_{d}}{\partial w_{j i}} & = \frac{\partial E_{d}}{\partial n e t_{j}} \cdot \frac{\partial n e t_{j}}{\partial w_{j i}} (= x_{j i}) \\ 其中， \frac{\partial E_{d}}{\partial n e t_{j}} & = \sum_{k \in 后继 (j)} \frac{\partial E_{d}}{\partial n e t_{k}} \cdot \frac{\partial n e t_{k}}{\partial n e t_{j}} \\ = \sum_{k \in 后继 (j)} - δ_{k} \cdot (\frac{\partial n e t_{k}}{\partial o_{j}} \cdot \frac{\partial o_{j}}{\partial n e t_{j}}) \\ = \sum_{k \in 后继 (j)} - δ_{k} \cdot (w_{k j} \cdot o_{j} (1 - o_{j})) \\ = δ_{j} \\ ∴ \frac{\partial E_{d}}{\partial w_{j i}} = - & δ_{j} x_{j i} \end{aligned} \end{matrix}$
  $\Delta w_{ji} = \eta\delta_jx_{ji}$
Softmax层：一般在输出层前采用Softmax函数转换为概率，可用于分类问题

2.2 卷积神经网络 CNN

结构：卷积层 + Relu层 + 池化层 + 全连接层等

【卷积层】 $3\cross3$ 的卷积核（代表一个feature）作用于一张图片，会产生一张feature map
- 大小 $3\cross 3 + 1 = 10$ $+1$ 表示偏置参数
- 步长：卷积核每次移动的距离
- 采用填充的方式：使得每层得到的结果和大小和输入一致（这也是为什么大小是奇数）比如：3*3填充1，5*5填充2
- （输出）通道数：即卷积核的个数（输入）通道数：即卷积核的厚度
$1$ $0$ 表示没什么关联
【Relu层】非线性激活函数Relu()：保留 feature map 中大于等于0的值，其余所有小于0的数值直接改写为0
【池化层】pooling：减少数据量的方式，一般分为最大池化（Max pooling）和平均池化（Average pooling）两种
$2\cross 2$ ，选出最大值更新进新的 feature map
【全连接层】Fully-Connected / Linear：相邻层的所有节点全部连接

举例：

LeNet神经网络（数字识别）
VGG-16神经网络（彩色图像）

神经网络遇到的两大问题：① 梯度消失问题，② 过拟合问题

梯度消失问题 $\delta_h \rightarrow 0$ $\Delta w_{ji} = \eta \delta_j x_{ji}$
$\delta_h = o_h(1-o_h)\sum_{k \in 后继(h)}\delta_k w_{kh}$ $\sum$ $0.25$
改进方式：
1. $o_h(1-o_h) \le 0.25$
2. GoogLeNet & Inception模块分布输出，使得往下输入的梯度消失得到缓解：损失函数同时考虑多个输出，求解多个输出的总和最小；训练的时候多个输出一起输出，真正输出的时候只有一个
3. 残差网络（ResNet）起因：在讨论结构“K层神经网络 + 1层恒等映射”神经网络的退化现象（更深的网络在训练过程中的难度—— training error 和 test error 更大）解决思路：将第“K+1层恒等映射”变为残差模块，按位相加
过拟合问题的解决方法
1. 使用验证集：使用验证集确定迭代轮次停止点
2. 正则化项法在原误差平方和损失函数的基础上加入正则化项（以下以2-范数为例）：
  $\begin{matrix} E_{d} (w) = \sum_{k = 1}^{m} (t_{k d} - o_{k d})^{2} + | | w | |_{2}^{2} \\ 其中， | | w | |_{2}^{2} = w_{1}^{2} + w_{2}^{2} + . . . + w_{N}^{2} \end{matrix}$
  原理：降低模型复杂性（过拟合的很大概率源自于参数过大）
  - 2-范数：很多参数值很小，但基本不会为0；抗干扰能力强
  - 1-范数：一些参数为0，起到特征选择的作用
3. 舍弃发（Dropout）：每次训练随机地临时舍弃一些神经元
4. 数据增强法：数据越多，过拟合的风险就越小人为增加一些数据（例如图像的缩放、旋转、局部截取、改变颜色）

TextCNN：自然语言处理 NLP

1. 词向量

词向量的表示
- 独热（one-hot）编码：用与词表等长的向量表示一个词，向量只有一个元素为1（第i个元素为1的向量用于表示此表中的第i个词），其余为0
  优点：编码简单，适用于稀疏向量 缺点：编码太长；无法度量词之间的相似性
- 分布式表示：可以度量词之间的相似性，适用于稠密向量
词嵌入 / Word embedding
每个词对应一个训练得到的词向量，是把词向量从高维空间嵌入到低维空间中的一个方法语义相近的词，对应词向量的“距离”也越近

2. 语言模型 & 词向量的训练

用神经网络（NNLM / Neural Network Language Model）实现语言模型

模型结构：计算一个句子概率的模型 => 训练得到的词向量
Notation $w_i$ $i\in [t-1, t-n+1]$ $w_t$ $n-1$ $C(w_k)$ $k\in [t-1, t-n+1]$ $w_k$ $m$ $u_{h,j}$ $j$ $h$ $z_h$ $h$ $tanh()$ $p_h$ $v_{k, h}$ $h$ $k$ $y_i$ $i$ $q_i$ $K$ 个神经元（对应词表长度）
$后一个词的概率 p_{i} = p (w_{i} | w_{i - (n - 1)} w_{i - (n - 2)} . . . w_{i - 2} w_{i - 1})$
模型分析 $\mathbf{w}$ ）
举例：
$3$ $2$ ：“计算机|科学”，“计算机|科学”，“计算机|工程”
$p(计算机科学，计算机科学，计算机工程) = p(科学|计算机)^2 \cross (1-p(科学|计算机))$ $p(科学|计算机)$ 的函数
$p(科学|计算机) = 2/3$
估计神经网络语言模型的参数：
$\begin{matrix} m a x_{θ} \prod_{w \in C} p (w = k | c o n t e x t (w), θ) （似然函数） \\ m a x_{θ} \sum_{w \in C} l o g p (w = k | c o n t e x t (w), θ) （对数似然函数） \\ - \sum_{w \in C} l o g p (w = k | c o n t e x t (w), θ) （负对数似然函数） \end{matrix}$
$\theta$ $context$ $C$ $w$ $k$ $\theta$
存在问题 $K$ $m(n-1)$ 个输入全连接参数多

word2vec模型

一种简化的神经网络语言模型两种实现方式：① 连续词袋模型（CBOW），② 跳词模型（Skip-Gram Model）

CBOW模型的特点： $x_w$ 是求和运算，无关乎顺序） ③ 霍夫曼树（Hierarchical Softmax）相当于NNLM中的隐含层 + 输出层

下面详细介绍CBOW模型： Word2vec如何得到词向量-CSDN博客 CBOW模型的训练输入是某一个特征词的上下文相关的词对应的词向量（one-hot），而输出是一棵哈夫曼树。

霍夫曼树与霍夫曼编码
1. 词表内的词根据出现频率编码为霍夫曼树（左边为1，右边为0）
2. $w_i$ $n(w_i, j)$ $w_i$ $j$ 个节点所选择的方向
3. 输入 $\mathbf{x_{\mathbf{w}}}$ $\theta_i$ （待求的逻辑回归模型参数）的神经元，输出 $p(R) = \sigma(\mathbf{x_{\mathbf{w}}}·\theta_i) = \frac{1}{1 + e^{-x^T_w}·\theta_i}$ $p(L) = 1 - p(R)$
4. $w_2$ $L = \Pi_{i=1}^3p(L,\theta_1)·p(L,\theta_2)·p(R,\theta_3)$
5. $\eta\frac{\part L}{\part{\mathbf{\theta}}}$ $\theta$ $\mathbf{x_w}$ $\eta\frac{\part{L}}{\part{\mathbf{x_w}}}$ ）作用到每一个输入的词向量上——从而不断更新词向量
优势：每次只计算与该词有关的参数；越是常用词涉及的参数越少

2.3 循环神经网络 RNN

RNN采用反馈网络机制，擅长处理序列数据（数据先后有所联系）

结构：全连接神经网络CNN的基础上增加上一时刻隐藏层反馈算法

单向RNN存在的问题：序列前面的内容被后面的内容淹没

双向循环神经网络

2.3.1 长短期记忆网络 LSTM

简单RNN存在的问题： ① 长期依赖问题（如：北京是一个美丽的（城市）vs 北京市一个美丽的（姑娘）） ② 重点选择问题（不同任务词的重要性不同）

2.3.2 GRU

相比LSTM，使用GRU能够达到相当的效果，并且相比之下更容易进行训练，能够很大程度上提高训练效率

结构：LSTM的基础上，使用更少的门达到同样的处理效果

Chapter3 对抗搜索

博弈问题：双人 + 一人一步交替进行 + 双方信息完备 + 零和博弈场景（极小-极大模型）：A和B对抗博弈，一方A以评分（score）大为优，另一方B以评分小为优

3.1 α-β剪枝算法

极大节点[]的下界为α，极小节点()的上界为β

剪枝条件：（注意，这里的“祖先”不只包括“父节点”）后辈节点的β值≤祖先节点的α值（极小≤极大）时，α剪枝后辈节点的α值≥祖先节点的β值时（极大≥极小）时，β剪枝

注意：一次剪枝过程只得到一次走步

方法问题：需要大量的专家知识

3.2 蒙特卡洛方法 MCM

蒙特卡洛方法（Monte Carlo methods）通过随机抽样、基于大数定律近似计算出问题的解或者评估问题的概率分布。即当样本量足够大时，样本的统计特征会趋近于总体的真实特征。

优势：应用于各种复杂的数值计算和概率统计问题，不需要事先对问题进行严格的数学推导，只需要进行大量的随机抽样和分析

劣势：计算效率通常较低，需要大量的计算资源和时间

接下来介绍蒙特卡洛树搜索 MCTS / Monte Carlo Tree Search：

一种简介的理解方式：
$\Rightarrow$ $\Rightarrow$ $\Rightarrow$ $\Rightarrow$ 决策（Decide）
$\begin{aligned} f u n c t i o n M C T S () : \\ w h i l e w i t h i n c o m p u t a t i o n a l b u d e g t do \\ n o d e \leftarrow s e l e c t (r o o t) \\ e x p a n d (n o d e) \\ s t i m u l a t e (n o d e) \\ f a t h e r s^{'} s t a t i s t i c s \leftarrow b a c k_p r o p a g a t e (n o d e) \\ r e t u r n d e c i d e () \end{aligned}$
之后介绍课本上的MCTS步骤

蒙特卡洛树搜索通常包括以下三个阶段：

\begin{aligned} f u n c t i o n S E A R C H () : \\ w h i l e w i t h i n c o m p u t a t i o n a l b u d g e t do \\ n e x t N o d e \leftarrow t r e e P o l i c y (r o o t) \\ r e w a r d \leftarrow d e f a u l t P o l i c y (n e x t N o d e) \\ b a c k p r o p a g a t i o n (n e x t N o d e) \\ r e t u r n d e f a u l t C h i l d () \end{aligned}

选择（Selection） $treePolicy(·)$
不停的遍历、扩展节点
- 对于尚未完全被拓展的节点，随机选取未被扩展的子节点进行扩展（expand()）
- 对于完全被扩展的节点，选取最有希望的子节点（bestChild()）重复上述步骤
扩展（Expansion）：对选定的子节点进行扩展，生成新的子节点
$\begin{aligned} f u n c t i o n e x p a n d (v) : \\ c h o o s e a \in u n t r i e d a c t i o n s f r o m v^{'} s e x p a n d a b l e s \\ a d d t h e n e w c h i l d v^{'} t o v \\ r e t u r n v^{'} \end{aligned}$
模拟（Simulation） $defaultPolicy(·)$
回溯（Backpropagation） $defaultPolicy(·)$
注意：更新的过程每一层都要“转换身份 / 正负号”！
$\begin{aligned} f u n c t i o n d e f a u l t P o l i c y (v) : \\ w h i l e v i s n o n - t e r m i n a l do \\ c h o o s e n e x t s t e p v^{'} f r o m v r a n d o m l y \\ u n t i l t h e r e i s a w i n n e r \\ r e t u r n (r e w a r d f o r v^{'}) \end{aligned}$
决策（Decision） $defaultChild(·)$

以上叙述中，“节点”表示某个需要决策的局面，或者当前状态（status）

UCT：“最有希望”的子节点用什么准则描述？
UCB算法（Upper Confidence Bound，信心上限算法）：
$\begin{matrix} {UCB}_{i} = win_{rate}_{i} + C \sqrt{\frac{lnN}{n_{i}}} \\ \begin{aligned} 其中： \\ w i n_r a t e_{i} ：当前节点 i 的胜率（ = \frac{w i n}{t o t a l} ） \\ N ：当前节点的父节点被访问的次数 \\ n_{i} ：当前节点 i 被访问的次数 \\ C ：探索参数; C 越大，越照顾访问次数较少的子节点，即探索性越大。 \end{aligned} \end{matrix}$
UCT算法（Upper Confidence Bound Apply to Tree，上限置信区间算法）：UCB算法 + MCTS算法
注意：UCT和上述MCTS的叙述不同——UCT中节点标注“获胜次数 / 模拟总次数”中的“获胜次数”是从本节点角度说的（下图中黑色节点代表己方状态，白色节点代表对手状态）

AlphaGo原理

待补充

3.3 深度强化学习方法（围棋）

强化学习：学习“做什么才能使得收益最大化”的方法；学习者不会被告知如何做，必须自己通过尝试发现哪些动作会产生最大的收益特征：试错和延迟收益（区别于监督学习）

深度强化学习：用深度学习（神经网络）实现的强化学习；关键在于损失函数的定义三种实现方式：基于策略梯度的强化学习、基于价值评估的强化学习、基于演员-评价方法的强化学习

基于策略梯度的强化学习：学习到的是每个落子点获胜的概率
$(s, a, p_a, t_a)$
Notations $s$ $a$ $s$ $a$ $p_a$ $s$ $a$ $t_a$ ：胜负值，胜为1，负为-1
$L(w) = -t_alog(p_a)$ 假设获胜者的行为都是正确的，负者行为都是不正确的假设获负时对权重的修改量大小与获胜时一样，方向相反
注意：
1. 在强化学习过程中，每个样本只使用一次
2. 基于策略梯度的强化学习方法学到的是在每个可落子点行棋的获胜概率（监督学习策略网络学到的是在某个可落子点行棋的概率）
基于价值评估的强化学习：学习到的是每个落子点获取最大收益的概率
对一个行棋点的价值，也就是收益进行评估
- 输入：当前棋局和行棋点
- 输出：取值在[-1,1]之间的估值
$(s, a, V(s, a), R)$
Notations $s$ $a$ $s$ $a$ $V(s, a)$ $s$ $a$ $R$ ：胜负值，胜为1，负为-1
$L(w) = (R-V(s,a))^2$
基于演员-评价方法的强化学习：学习到的是每个落子点获得最大收益增量的概率
收益增量 $A = Q(s, a)-V(s) = R - V(s)$
Notations $V(s)$ $s$ $[-1,1]$ $Q(s, a)$ $s$ $a$ $[-1,1]$ $A$ $[-2,2]$ $A$ 越大越说明走了一步妙招
损失函数：
- $L_1(w)=(R-V(s))^2$
- $L_2(w)=-Alog(p_a)$ $p_a$ $s$ $a$ 处行棋的获胜概率
- 综合损失函数 $L(w) = L_1(w)+\lambda L_2(w)$

AlphaGo Zero 强化学习

待补充

Chapter4 统计机器学习

统计机器学习方法 $A$ $D$ $H$ $g≈f$

三要素：模型、策略、算法模型：学习什么样的模型（条件概率分布、决策函数）策略：模型选择的准则（经验风险最小化、结构风险最小化）算法：模型学习的算法（一般归结为一个最优化问题）

4.1 支撑向量机 SVM

SVM：Support Vector Machines，是一个二分类器——特征空间上的间隔最大化线性分类器，通过核技巧可以实现非线性分类

\begin{aligned} 给 定 线 性 可 分 训 练 集 T & = {(x_{1}, y_{1}), . . ., (x_{N}, y_{N})}, \\ x_{i} \in X = R^{n}, y \in Y & = {+ 1, - 1}, i = 1, 2, . . ., N \\ 这 里, x_{i} 为 第 i 个 特 征 向 量 ， y_{i} 为 x_{i} 的 & 类 标 记 ， + 1 表 示 正 类 ， - 1 表 示 负 类 \\ 通 过 间 隔 最 大 化 得 & 到 分 类 超 平 面 ： \\ w^{* T} x + & b^{*} = 0 \\ 相 对 应 的 决 策 函 数 & 为 ： \\ f (x) = s i g n ( & w^{* T} x + b^{*}) \\ 称 为 线 性 可 分 支 持 & 向 量 机 \end{aligned}

函数间隔：
$\begin{matrix} 设训练集 T 和超平面 (w, b) \\ 定义超平面 (w, b) 关于样本点 (x_{i}, y_{i}) 的函数间隔为： {\hat{γ}}_{i} = y_{i} (w^{T} x_{i} + b) \\ 定义超平面关于训练集 T 的函数间隔为： \hat{γ} = m i n_{i} {\hat{γ}}_{i} \end{matrix}$
几何间隔：
$\begin{matrix} γ_{i} = y_{i} (\frac{w^{T} x_{i}}{| | w | |} + \frac{b}{| | w | |}) \\ γ = m i n_{i} γ_{i} \\ 期中， | | w | | 为 w 的 L_{2} 范数 \end{matrix}$

最优分界面：即间隔最大的超平面，满足

\begin{aligned} 用 函 数 间 隔 表 示 ： \\ m a x_{w, b} (\frac{\hat{γ}}{| | w | |}) s . t . y_{i} (w^{T} x_{i} + b) \geq \hat{γ}, i = 1, 2, . . ., N \\ 用 几 何 间 隔 表 示 ： \\ m a x_{w, b} γ s . t . y_{i} (\frac{w^{T} x_{i}}{| | w | |} + \frac{b}{| | w | |}) \geq γ, i = 1, 2, . . ., N \end{aligned}

$\hat{\gamma} = 1$

转化为如下的凸二次规划问题：

\begin{matrix} m i n_{w, b} \frac{1}{2} | | w | |^{2} s . t . y_{i} (w^{T} x_{i} + b) \geq 1, i = 1, 2, . . ., N \end{matrix}

1. SVM与对偶算法

$min_{\mathbf{w}, b}\frac{1}{2}||w||^2 \quad s.t.\quad y_i(\mathbf{w^T}\mathbf{x_i} + b) \ge 1,\quad i=1, 2, ...,N \\$

定义拉格朗日函数：

\begin{matrix} L (w, b, α) = \frac{1}{2} | | w | |^{2} + \sum_{j = 1}^{N} α_{j} [1 - y_{i} (w^{T} x_{i} + b)] \\ 其 中 ， α_{j} \geq 0, α = (α_{1}, α_{2}, . . ., α_{N})^{T} 为 拉 格 朗 日 乘 子 向 量 \end{matrix}

拉格朗日函数与原始优化问题的关系：

\begin{matrix} m a x_{α} (L (w, b, α)) = {\begin{aligned} \frac{1}{2} | | w | |^{2}, 满 足 约 束 条 件 时 \\ \infty, 其 它 \end{aligned} \\ ∴ \min_{w, b} \max_{α} (L (w, b, α)) 与 原 始 问 题 等 价 \\ 满 足 K K T 条 件 时 ， m a x_{α} m i n_{w, b} (L (w, b, α)) \leq m i n_{w, b} m a x_{α} (L (w, b, α)) 等 号 成 立 \\ ∴ 原 始 问 题 的 对 偶 问 题 为 \max_{α} \min_{w, b} (L (w, b, α)) ， \\ 且 原 始 问 题 与 对 偶 问 题 等 价 \\ \begin{aligned} 其 中 ， K K T ： \\ 1 \nabla_{w, b} L (w, b, α) = 0 \\ 2 α_{i} [1 - y_{i} (w^{T} x_{i} + b)] = 0 \\ 3 [1 - y_{i} (w^{T} x_{i} + b)] \leq 0 \\ 4 α_{i} \geq 0 \\ 5 i = 1, 2, . . . N \end{aligned} \end{matrix}

$\mathbf{w},b$ $0$ 并代入（下式为二维的情况）

\begin{matrix} \max_{α} \min_{w, b} : L (w, b, α) = \frac{1}{2} | | w | |^{2} + \sum_{i = 1}^{N} α_{i} [1 - y_{i} (w^{T} x_{i} + b)] \\ m a x_{α} (- \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} α_{i} α_{j} y_{i} y_{j} (x_{i}^{T} x_{j}) + \sum_{i = 1}^{N} α_{i}) s . t . \sum_{i = 1}^{N} α_{i} y_{i} = 0 \\ 由 此 可 以 解 得 α \end{matrix}

利用KKT条件，得到：

\begin{matrix} w^{*} = \sum_{i = 1}^{N} α_{i}^{*} y_{i} x_{i} \\ b^{*} = y_{j} - \sum_{i = 1}^{N} α_{i}^{*} y_{i} x_{i}^{T} x_{j} (选 择 一 个 α_{j} \neq 0) \end{matrix}

$\alpha_i≠0$ $\mathbf{x_i}$ 称为支持向量

例题：

2. “线性不可分”支持向量机

$1$ 松弛变量 $\xi_i$ ，使得：

\begin{matrix} m i n_{w, b, ξ} (\frac{1}{2} | | w | |^{2} + C \sum_{i = 1}^{N} ξ_{i}) \\ s . t . y_{i} (w^{T} x_{i} + b) \geq 1 - ξ_{i}, i = 1, 2, . . ., N, ξ_{i} \geq 0 \end{matrix}

软间隔最大化 $C \gt 0$ 为惩罚参数，代表目标函数惩罚项的权重。

此时，Lagrange对偶函数为：

\begin{matrix} \max_{α} \min_{w, b} : L (w, b, ξ, α) = \frac{1}{2} | | w | |^{2} + C \sum_{i = 1}^{N} ξ_{i} + \sum_{i = 1}^{N} α_{i} [1 - ξ_{i} - y_{i} (w^{T} x_{i} + b)] - \sum_{i = 1}^{N} γ_{i} ξ_{i}, γ_{i} \geq 0 \\ \frac{\partial L}{\partial ξ_{i}} = C - α_{i} - γ_{i} = 0 \Rightarrow γ_{i} = C - α_{i} \\ m a x_{α} (- \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} α_{i} α_{j} y_{i} y_{j} (x_{i}^{T} x_{j}) + \sum_{i = 1}^{N} α_{i}) s . t . \sum_{i = 1}^{N} α_{i} y_{i} = 0, 0 \leq α_{i} \leq C \end{matrix}

$b$ $\alpha_j ≠ 0$ $0 \lt \alpha_j \lt C$ :

\begin{matrix} w^{*} = \sum_{i = 1}^{N} α_{i}^{*} y_{i} x_{i} \\ b^{*} = y_{j} - \sum_{i = 1}^{N} α_{i}^{*} y_{i} x_{i}^{T} x_{j} (选 择 一 个 0 < α_{j} < C) \end{matrix}

$\alpha_i \gt 0$ $\mathbf{x_i}$ 称为（软间隔的）支持向量：

$0 \lt \alpha_i \lt C$ $\xi_i = 0$ $x_i$ 在间隔边界上
$\alpha_i = C$ $0 \lt \xi_i \lt 1$ $x_i$ 在间隔边界与分离超平面之间
$\alpha_i = C$ $\xi_i = 1$ $x_i$ 在超平面上
$\alpha_i = C$ $\xi_i \gt 1$ $x_i$ 位于误分一侧

$1$ $1-\xi$

$C$ 选取不合适，也有可能存在软支持向量

3. 非线性支持向量机

$z = \phi(x) = ((x^{(1)})^2, (x^{(1)})^2)^T$ $w_1(x^{(1)})^2 + w_2(x^{(1)})^2+b=0$ $w_1z^{(1)} + w_2z^{(2)} + b = 0$ 。这样原空间的非线性可分问题，变为了新空间线性可分问题。

核技巧：通过一个非线性变换将输入空间X（欧式空间或者离散集合）对应于一个特征空间H（希尔伯特空间），使得在输入空间X的超曲面模型对应于特征空间H中的超平面模型（支持向量机）。分类问题的学习就可以通过在H空间中求解线性支持向量机完成。

非线性支持向量机的对偶问题：

\begin{matrix} m a x_{α} (- \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} α_{i} α_{j} y_{i} y_{j} (ϕ (x_{i})^{T} ϕ (x_{j})) + \sum_{i = 1}^{N} α_{i}) \\ s . t . \sum_{i = 1}^{N} α_{i} y_{i} = 0, 0 \leq α_{i} \leq C \end{matrix}

核函数 $X$ $H$ 特征空间。如果存在映射函数

ϕ (x) : X \to H

$x, z \in \mathbf{X}$ $K(x, z)$ 满足：

K (x, z) = ⟨ ϕ (x), ϕ (z) ⟩ （ 内 积 ）

$K(x, z)$ 核函数 $\phi(x)$ 为映射函数 $H$ 的维度也不唯一）

因此，非线性支持向量机的对偶问题化简为：

\begin{matrix} m a x_{α} (- \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} α_{i} α_{j} y_{i} y_{j} (ϕ (x_{i})^{T} ϕ (x_{j})) + \sum_{i = 1}^{N} α_{i}) \\ s . t . \sum_{i = 1}^{N} α_{i} y_{i} = 0, 0 \leq α_{i} \leq C \\ — — — — — — — — — — — — — — — — — — — — — — — — — — — — \\ 选 择 一 个 0 < α_{j} < C 分 量 ： \\ w^{* T} x = \sum_{i = 1}^{N} α_{i}^{*} y_{i} K (x_{i}, x) \\ b^{*} = y_{j} - \sum_{i = 1}^{N} α_{i}^{*} y_{i} K (x_{i}, x_{j}) \\ 分 解 超 平 面 ： w^{*} \cdot ϕ (x) + b^{*} = \sum_{i = 1}^{N} α_{i}^{*} y_{i} ϕ (x_{i}) + b^{*} = 0 \\ 或 ： w^{T} x = \sum_{i = 1}^{N} α_{i} y_{i} K (x_{i}, x) \\ 决 策 函 数 ： f (x) = s i g n (\sum_{i = 1}^{N} α_{i}^{*} y_{i} ϕ (x_{i}) + b^{*}) \end{matrix}

正定核的充要条件
$\mathbf{X}\in \R^n$ $K(x, z)$ $\mathbf{X}\cross\mathbf{X}$ $K(x, z)$ $\forall \mathbf{x_i} \in \mathbf{X}$ $i = 1, ..., m$ $K(x, z)$ $K = [K(x_i, x_j)]_{m\cross m}$ 是半正定矩阵
常用的核函数
- 多项式核函数 $K(x, z) = (x·z+1)^p$ $p$ 越大，函数分界超平面越复杂
- 高斯核函数 $K(x, z) = e^{-\frac{||x-z||^2}{2\sigma^2}}$ $\sigma$ 欠拟合 $\sigma$ 过小可能造成过拟合
序列最小最优化算法 SMO $\alpha$ 求最值，检验KKT条件，迭代求解

SVM用于求解多分类问题：

$N$ 个分类器）；问题：样本不平衡
$C_N^2$ 个分类器），分类时采取投票法决定类别（效果最好，一般为默认情况）
层次法：所有类先分成两类

文本分类的特征抽取
$(w_{1,j},w_{2,j},...,w_{n,j})^T$ $w_{ij}$ $i$ $j$ 中的权重
- $tf_{ij}$ $i$ $j$ $w_{ij}$ 问题：只用词频不考虑具体内容的问题，如若想要抽取“清华”相关的新闻，则那些讨论“大学”（与分类无关的词语）的文章，“大学”一次反复出现会减弱“清华”的权重
- $tf-idf$ $df_i = \frac{出现词项i的文档数}{训练集的文档总数N}$ $idf_i=log(\frac{1}{df_i})$ $df_i$ $w_{ij} = tf_{ij}·idf_i$ $log(idf_i)$ ）

4.2 决策树

$D=\{(\mathbf{x_1}, y_1), (\mathbf{x_2}, y_2),...(\mathbf{x_N},y_N)\}$ $\mathbf{x_i} = (x_i^{(1)},...,x_i^{(n)})$ $n$ 特征 $y_i \in \{1, 2, ... K\}$ $i=1,2,...N$ $N$ 为样本容量

决策树学习就是从训练集中归纳出一组分类规则，得到一个与训练集矛盾较小的决策树的过程——是一个NPC问题，所以一般采用启发式方法得到一个近似解（损失函数最小作为优化目标）

特征选择：用信息增益选择特征
$X$ 熵 $H(X) = -\sum_{i=1}^Kp_ilogp_i$ $p_i=P(X=x_i)$ $H(p)$ $K$ $K$ $K=2$ $D$ $H(D)$
条件熵 $H(Y|X) = \sum_{i=1}^np_iH(Y|X=x_i)$ $X$ $Y$ $n$ $X$ $n$ 个取值
$A$ $D$ 信息增益 $g(D, A)=H(D) - H(D|A)$ $A$ $D$ 进行分类的不确定性减少的程度，衡量特征分类能力的强弱
$D$ $K$ $C_k$ $A$ $n$ $\{a_i, ..., a_n\}$ $A$ $D$ $n$ $D_1,...D_n$ $D_i$ $C_k$ $D_{ik}$ $|·|$ 表示样本个数，则信息增益计算如下：
$\begin{matrix} H (D) = - \sum_{k = 1}^{K} \frac{| C_{k} |}{| D |} \cdot l o g \frac{| C_{k} |}{D} \\ H (D | A) = \sum_{i = 1}^{n} \frac{| D_{i} |}{| D |} \cdot H (D_{i}) = - \sum_{i = 1}^{n} \frac{| D_{i} |}{| D |} \cdot (\sum_{k = 1}^{K} \frac{| D_{i k} |}{| D_{i} |} l o g \frac{| D_{i k} |}{| D_{i} |}) \\ 信息增益 g (D, A) = H (D) - H (D | A) \end{matrix}$

1. ID3算法

选择一个最大信息增益的特征，如果它足够好（信息增益比较大），那么就按这个特征先分一次类，然后递归建树即可

$D$ $A$ $\epsilon \gt 0$

$T$

$D$ $C_k$ $T$ $C_k$ $T$
$A$ $T$ $D$ $C_k$ $T$
$A$ $D$ $A_g$
$A_g$ $\epsilon$ $T$ $D$ $C_k$ $T$
$A_g$ $a_i$ $A_g=a_i$ $D$ $D_i$ $D$ 的子节点
$D$ $D_i$ $D_i$ $D$ 中实例最大的类作为标记，构建子节点（比如特征为头发长度，男女分类，没有中发，则该节点返回男女中较多的类别）
$D_i$ $A-\{A_g\}$ $T_i$ $T_i$

存在的问题：倾向于选择分支比较多的属性

2. C4.5算法

信息增益比 $g_R(D, A) = \frac{g(D,A)}{H_A(D)}$ $H_A(D) = -\sum_{k=1}^n\frac{|D_k|}{|D|}log\frac{|D_k|}{|D|}$

连续值 $A$ $a_0$ $≤a_0$ $\gt a_0$ 的划分到右子树

存在的问题：倾向于选择分割不均匀 $n$ $n$ 个特征中选择信息增益比最大的特征

后来发展到了C5.0

3. 决策树的剪枝

后剪枝（先生成树再剪枝）：为了防止出现过拟合，从已经生成的树上裁掉一些子树或者叶节点，将其父节点作为新的叶节点，用其实例数最大的类别作为标记。

当数据量小时，直接利用训练集进行剪枝
从下向上逐步剪枝；再验证集上测试性能，直到性能下降位置
$\alpha$ $T$ $|T|$ $t$ $T$ $N_t$ $k$ $N_{tk}$ $k=1,…,K$ $H_t(T)$ $t$ $a≥0$ 为参数
$C(T)$ $|T|$ 表示模型的复杂程度
$\begin{matrix} 损失函数： C_{α} (T) = \sum_{t = 1}^{| T |} N_{t} H_{t} (T) + α | T | \\ — — — — — — — — — — — — — — — — — — — — \\ 经验熵： H_{t} (T) = - \sum_{k} \frac{N_{t k}}{N_{t}} l o g \frac{N_{t k}}{N_{t}} \\ 记： C (T) = \sum_{t = 1}^{| T |} N_{t} H_{t} (T) = - \sum_{t = 1}^{| T |} \sum_{k = 1}^{K} N_{t k} l o g \frac{N_{t k}}{N_{t}} \\ 有： C_{α} (T) = C (T) + α | T | \end{matrix}$
$\cross$ $+$ 整棵树规模的权重值方法就是贪心，通过从树叶开始向上回溯，如果说损失函数减小，那么剪枝

4. 随机森林

随机森林是由多个决策树组成的分类器；通过投票机制改善决策树单个决策树的生成：有放回的数据采样，属性（特征）的采样集外数据的使用：单个决策树的未用到的数据

Machine Learning: from Theory to Practice

Chapter0 Definition and Terms

Chapter1 启发式搜索 Search

1.1 A* 算法

1. 伪代码及算法描述

2. 算法分析

1.2 改进版A*算法

1. 伪代码及算法描述

2. 算法分析

1.3 viterbi 算法

1. 汉字识别后处理

2. 拼音输入法

Chapter2 神经网络

2.1 全连接神经网络 MLP / FCN

2.2 卷积神经网络 CNN

TextCNN：自然语言处理 NLP

1. 词向量

2. 语言模型 & 词向量的训练

word2vec模型

2.3 循环神经网络 RNN

2.3.1 长短期记忆网络 LSTM

2.3.2 GRU

Chapter3 对抗搜索

3.1 α-β剪枝算法

3.2 蒙特卡洛方法 MCM

AlphaGo原理

3.3 深度强化学习方法（围棋）

AlphaGo Zero 强化学习

Chapter4 统计机器学习

4.1 支撑向量机 SVM

1. SVM与对偶算法

2. “线性不可分”支持向量机

3. 非线性支持向量机

4.2 决策树

1. ID3算法

2. C4.5算法

3. 决策树的剪枝

4. 随机森林

1.1 A^* 算法

1.2 改进版A^*算法