Machine Learning Tutorial
===

# 什么是机器学习
机器学习是由一帮计算机科学家们希望让计算机像人类一样思考而延伸出来的一门计算机理论。机器学习最早来自心理和生物科学，科学家们认为人和计算机其实没有什么差别，都是一大批相互连接的信息传递和存储元素所组成的系统。机器学习是一门典型的跨领域科学，其中包含了概率学、统计学等等方面。随着计算机性能的提升和计算机运算速度的升级，机器学习的应用才真正开始融入我们日常的生活当中。而不久的将来，机器学习必将成为人类探索机器世界的关键钥匙。**总的来说**，机器学习就是一个寻找方法的过程（Looking for a function）。我们所要做的就是构建一个function set（也就是model），其中的function结合起来**能够真正将输入和输出拟合起来的function**。

**以下的内容出自自己的理解，如有疑问欢迎留言探讨。**

## 应用
图像识别， AI对话式智慧型家居, 聊天机器人， 股市风险预测...

## 分类
机器学习可以按照目的不同划分成几个不同功能的种类：
- `Regression`: Output a scalar
- `Classification`: Output a class(one_hot vevtor)
- `Structured Learning/Prediction`: Output a sequence, a matrix, a graph, a tree...(Output is composed of **components with dependency**)

在**Structured Learning**领域中，而这种机器学习方式的可靠指出在于它能够适应更加复杂的环境。对于**One-shot、Zero-shot Learning**的问题上，传统的机器学习分类模式讲究的是利用监督式学习的方法用大量例子来拟合网络结构。而Structured Learning除了能够拟合那些带有Label的数据外，还能够在输出范围较大的时候**主动去尝试拟合**那些模型从未处理过的数据类别。从而**创造出全新的类别成员**，因此该学习方式也要求模型的结构更加智能。

Structured Learning还有一个重要的问题需要克服，那就是要让模型自己学会如何**安排数据流的模型**（Learn how to planning）。机器学习模型能够自我生成一些新的数据样本，但是这些数据通常是依靠已知的记忆进行组合而成的。这就需要我们的模型能够**考虑全局再做决定**，避免因为 **“盲人摸象”** 的认知而做出错误的决定：


- 图中就是一些模型因为只认知到局部而产生的错误理解所导致的结果。

## 算法
机器学习的实现方式多种多样，在程式语言中我们称之为算法。
Machine Learning的学习方式主要包括：
- **监督式学习（Supervised Learning）**
- **Input**: Values and Labels
- **Principle**: 通过让计算机学习这些label来标记相应的value，从中找出它认为重要的部分作为判断依据。（**既定规律**）
- **Example**: Logistic Regression、Back Propogation Neural Network
- **非监督式学习（Un-Supervised Learning）**
- **Input: Values**
- **Principle**: 只提供value的情况下，计算机事先无法得知value所代表的含义以及需要学习的正确结果，这时候就需要让计算机自己学会分类不同的value，从而总结出不同value背后所隐藏的重要规律作为判断依据。（**生成规律**）
- **Example**: Apriori、K-Means
- **半监督式学习（Semi-Supervised Learning）**
- **Input**: Values and A few Labels
- **Principle**: 这种学习方式主要让计算机考虑如何利用少量的label总结出最适合value的判断规则，从而引申到更大范围的value中。
- **Example**: Laplacisn SVM、Graph Inference
- **强化学习（Reinforcement Learning）**
- **Input**: Environment and Set of Operations
- **Principle**: 通过将计算机设定在一个复杂的环境中，让机器去随机尝试各种可能的操作，并通过环境的回馈（正确加分，不正确扣分）的方式让机器的行为向加分的方面靠近，最终适应环境。
- **Example**: Alpha GO、Robot Control

Machine Leaning的算法主要分为这几类：
- **回归算法（Regression）**
- 该算法主要是试图通过对误差的衡量来探索变量之间的关系问题。常见的回归算法包括：**最小二乘法（Ordinary Least Square）**、**逻辑回归（Logistic Regression）**、**逐步回归（Stepwise Regression）**、**多元自适应回归样条（Multivariate Adaptive Regression Splines）** 和 **本地散点平滑估计（Locally Estimated Scatterplot Smoothing）** 等。
- 常用的**情形**有：信用评估、度量成功率、预测收入水平、预测地震发生几率等等。
- **基于实例的算法（Instance-Based Algorithm）**
- 该算法常常用来对决策性问题建模，通常会选取一批样本数据，然后根据某些特性和新数据样本的比较，通过匹配度来找到最佳的匹配相性。因此可以理解为 **“赢家通吃”** 的贪婪（Greedy）学习方式。
- 常见的算法包括：**K-Nearest Neighbor（KNN）**、**学习矢量量化（Learning Vector Quantization，LVQ）** 以及 **自组织映射算法（Self-Organizing Map，SOM）**。
- **正则化方式（Regular Expression）**
- 该算法是基于回归算法的延伸，根据算法的复杂度对其进行的调整。正则化方法会对简单模型基于奖励而对复杂模型算法基于惩罚（一个类似强化学习的概念）。
- 常见的算法包括：**Ridge Regression**、**Least Absolute Shrinkage and Selection Operator（LASSO）** 和 **弹性网络（Elastic Net）**。
- **决策树（Decision Tree）**
- 该算法根据数据的属性采用树状的结构建立决策模型，常常被用来解决**分类**和**回归**问题。
- 常见的算法包括：**分类及回归树（Classification And Regression Tree，CART）**、**Iterative Dichotomiser 3（ID3）**、**随机森林（Random Forest）** 以及 **梯度推进（Gradient Boosting Machine，GBM）**。
- **贝叶斯（Bayesian）**
- 该算法是基于贝叶斯定理的一类演算法，主要也是来解决**分类**和**回归**的问题。
- 常见的算法包括: **朴素贝叶斯（Naive Bayesian）**、**平均单依赖评估（Averaged One-Dependence Estimators，AODE）** 以及 **Bayesian Belief Network（BBN）**。
- 常用范例：垃圾邮件分类、文章分类、情绪分类、人脸识别等。
- **基于核的算法（Kernel-Based Algorithm）**
- 该算法最著名的应该是支持向量机（SVM）了，其将输入数据映射到一个高阶的向量空间中，在这些高阶空间里，有些分类或者回归问题就能得到解决。
- 常见的算法包括：**支持向量机（Support Vector Machine，SVM）**、**径向基函数（Radial Basis Function，RBF）** 和 **线性判别分析（Linear Discriminate Analysis，LDA）**。
- **聚类算法（Clustering）**
- 该算法和回归类似，就是在处理分类问题的时候，通常以中心点或者分层的方式输入数据进行归并。所以聚类算法目的是找到数据的内部结构，以便按照最大的共同特征进行归类。
- 常见的聚类算法包括：**K-Means算法** 以及 **期望最大化算法（Expectation Maximization，EM）**。
- 聚类的关注特征也分为好多种，包括：质心、连通性、密度、概率、维度以及神经网络结构等。
- **关联法则（Association Rule）**
- 该算法通过寻找最能解释数据变量之间关系的规则，从而找出大量多元数据集中的有用关联法则。
- 常见的算法包括：**Apriori算法** 和 **Eclat算法**。
- **遗传算法（Genetic Algorithm）**
- 源自进化理论，淘汰弱者，适者生存。通过不断更新和淘汰的机制去选择最优的设计模型。后诞生的模型会继承先带模型的参数，并能够根据环境自我优化或消失。
- **人工神经网络（Neural Network）**
- 该算法主要是模拟生物神经网络，属于模型匹配算法的一种。通常用于解决**分类** 和 **回归**的问题。人工神经网络是机器学习的一个庞大分支，有几百种不同的算法结构（包括深度学习）。
- 重要的神经网络算法包括：**感知神经网络（Perceptron Neural Network）**、**反向传递（Back Propagation）**、**自组织映射（Self-Organizing Map，SOM**) 等。
- **深度学习（Deep Learning）**
- 深度学习算法是基于人工神经网络的延伸，通过建立更复杂的神经网络结构来提升神经网络的效果。很多深度学习的算法是半监督式学习算法，用来处理少量未label的数据集。
- 常见的深度学习算法包括：**受限波尔兹曼机（Restricted Boltzmann Machine，RBN）**、**Deep Belief Networks（DBN）**、**卷积网络（Convolutional Network）** 和 **堆栈式自动编码器（Stacked Auto-encoders）**。
- **降低维度算法（Reduce Dimension）**
- 与聚类相似，降低纬度算法也是试图分析数据内部的结构，不过该算法属于非监督学习的方式，在缺乏信息的情况下归纳或解释数据。这类算法利用高维度的数据作为监督的label使用，从而完成迁移的降维动作。
- 常见的算法包括：**主成分分析（Principle Component Analysis，PCA）**、**偏最小二乘回归（Partial Least Square Regression，PLS）** 和 **投影追踪（Projection Pursuit**等。

# 十大常见机器学习算法
常用的机器学习算法，几乎可以用在所有的数据问题上：

## 线性回归（Linear Regression）

线性回归通常用于根据**连续变量**估计实际数值等问题上。通过拟合最佳的**直线**来建立**自变量（X，features）** 和 **因变量（Y，labels）** 的关系。这条直线也叫做回归线，并用**Y = a* X + b**来表示。

在这个等式中：
- `Y` : 因变量（也就是Labels）
- `a` : 斜率（也就是Weights）
- `X` : 自变量（也就是Features）
- `b` : 截距（也就是Bias）


系数 `a` 和 `b` 可以通过**最小二乘法**（即让所有pairs带入线性表达式等号两边的方差和最小）获得。

### 最小二乘法（Least Squares）
最小二乘法最重要的应用是在曲线拟合上。最小平方所包含的最佳拟合，即残差（观测值与模型提供的拟合值之间的差距）平方总和的最小化。当问题在自变量（x变量）有重大不确定性时，那么使用简易回归和最小二乘法会发生问题；在这种情况下，须另外考虑变量-误差-拟合模型所需的方法，而不是最小二乘法。

**Example:**
某次实验得到了四个数据点:

$$
{\displaystyle (x,y)}： {\displaystyle (1,6)}、 {\displaystyle (2,5)}、 {\displaystyle (3,7)}、 {\displaystyle (4,10)}
$$

我们希望找出一条和这四个点最匹配的直线:

$$
y=\beta _{1}+\beta _{2}x
$$

即找出在某种 **“最佳情况”** 下能够大致符合如下超定线性方程组的参数：

$$
\beta _{1}+1\beta _{2} = 6 \\
\beta _{1}+2\beta _{2} = 5 \\
\beta _{1}+3\beta _{2} = 7 \\
\beta _{1}+4\beta _{2} = 10
$$

最小二乘法的思路是让等号的两边方差最小。也就是说此时能够算出下面这个函数的最小值：

$$
S(\beta _{1}, \beta _{2})=[6-(\beta _{1}+1\beta _{2})]^2+[5-(\beta _{1}+2\beta _{2})]^2+[7-(\beta _{1}+3\beta _{2})]^2+[10-(\beta _{1}+4\beta _{2})]^2
$$

求解的过程可以通过对S分别对两个参数做偏导数，然后让他们等于0:

$$
{\frac {\partial S}{\partial \beta _{1}}}=0=8\beta _{1}+20\beta _{2}-56 \\
{\frac {\partial S}{\partial \beta _{2}}}=0=20\beta _{1}+60\beta _{2}-154.
$$

此时可以求解出：

$$
\beta _{1}=3.5 \\
\beta _{2}=1.4
$$

也就是说直线方程：

$$
y = 3.5+1.4x
$$

为最佳解。

## 逻辑回归（Logistic Regression）

逻辑回归虽然名字中带有**回归**字样，但其实是一个**分类**算法而不是回归算法。该算法根据已知的一系列因变量估计**离散的数值**（0或1，代表假和真）。该算法通过将数据拟合进一个逻辑函数来预估一个事件发生的**概率**。由于其估计的对象是概率，所以输出的值大都在0和1之间。

逻辑回归通常用于解决二分类的问题，例如判断人是男是女等。逻辑回归就是通过人的一些基本性状特征来判断属于男女的概率。

从数学角度看，几率的对数使用的是**预测变量的线性组合**模型。

# Probability of event occurence / not occurence
odds = p / (1 - p)
ln(odds) = ln(p / (1 - p))
logit(p) = ln(p / (1 - p)) = b0 + b1X1 + b2X2 + ... + bnXn

式子中 `p` 指的是特征出现的概率，它选用使观察样本可能性最大的值（**极大似然估计**）作为参数，而不是通过最小二乘法得到。

- 那么为什么要取对数log呢？

- 简而言之就是对数这种方式是复制阶梯函数最好的方法之一。


- 关于改进模型的方法：
- 加入交互项（**X1 * X2**等）
- 对输入输出进行正规化
- 使用非线性模型

- 二分类Logistic Regression使用的非线性函数是sigmoid（多分类则用softmax）：


输出的值对应出现概率（0和1分别对应 y 和 1-y），利用极大似然估计可以得到模型的目标函数（此时不考虑正规化项）：


对所有的变量而言：


为了方便计算梯度，我们会用log函数对公式进行转换：


Tips：利用log函数能够将y和1-y的指数计算转换成乘积形式的系数计算，同时我们通常加上负号来将最大化相似度的问题转换成最小化误差的问题。

- **传统GD**容易陷入局部最优，得到cost需要遍历全部样本。而**SGD**在计算cost的时候只用当前得到的error进行反向传递，随机选取遍历对象后求和得到。

### 优缺点
**Logistic Regression优点**：容易实现、分类计算量相对较小、速度快、存储资源低。
**Logistic Regression缺点**：容易欠拟合、准确度不高、不用softmax情况下只能简单二分类，要求结果必须二维线性可分。

## 决策树（Decision Tree）

该算法属于监督式学习的一部分，主要用来处理分类的问题，它能够适用于分类连续因变量。我们将主体分成两个或者更多的类群，根据重要的属性或者自变量来尽可能多地区分开来。


- 根据不同的决策属性，我们可以依次将输入进行分类，最终会得到一个标签（Label）。为了把总体分成不同组别，需要用到许多技术，比如**Gini、Information Gain** 和 **Entropy** 等。

### 基尼系数（Gini）


图中的实际分配曲线（红线）和绝对平衡线（绿线）之间的**面积**为A，和绝对不平衡线（蓝线）之间的面积为B，则横纵坐标之间的比例的**Gini系数**为：
$$
{A \over A + B}
$$
- A为零时，Gini系数为0，表示完全平衡。B为零时，Gini系数为1，表示完全不平衡。

在选择样本的时候，如果Gini系数越小，说明数据的纯度越高，例如：给出西瓜的数据，这些数据的西瓜都是优质的西瓜，那么pk=1，从而得到Gini = 0。在决策树分裂过程中，我们会尽量选择Gini系数小的特征属性进行分裂，但同时也需要考量树的复杂程度。

### 信息增益和熵（Information Gain & Entropy）
在我们建立决策树的时候，常常会有许多属性，那么用哪一个属性作为数的根节点呢？这个时候就需要用到 **信息增益（Information Gain）** 来衡量一个属性区分以上数据样本的能力强弱。信息增益越大的属性作为数的根节点，就能使得这棵树更加简洁。


- 以图中数据为例，要想知道信息增益，就必须先算出分类系的**熵值（Entropy）**。最终结果的label是yes或者no，所以统计数量之后共有9个yes和5个no。这时候**P（“yes”） = 9 / 14，P（“no”） = 5 / 14**。这里的熵值计算公式为：

$$
Entropy(S) = {-(9 / 14) * log _{2}(9 / 14) - (5 / 14) * log _{2}(5 / 14)}
$$

- 之后就可以计算每一个属性特征的信息增益（Gain）了。以wind属性为例，Wind为Weak的共有8条，其中yes的有6条，no的有2条；为Strong的共有6条，其中yes的有3条，no的也有3条。因此相应的熵值为：

$$
Entropy(Weak) = {-(6 / 8) * log _{2}(6 / 8) - (2 / 8) * log _{2}(2 / 8)}
$$

$$
Entropy(Strong) = {-(3 / 6) * log _{2}(3 / 6) - (3 / 6) * log _{2}(3 / 6)}
$$

- 现在就可以计算Wind属性的**信息增益**了：

$$
Gain(Wind) = {Entropy(S) -(8 / 14) * Entropy(Weak) - (6 / 14) * Entropy(Strong)}
$$

### 决策树分类
- ID3： 采用信息增益选择最佳分裂子节点
- C4.5： 采用信息增益率（正规化）选择最佳分裂子节点

以上两种决策树的形态在决策过程中准确率相对较高，但是需要反复对比扫描排序，运算效率低。

- CART： 利用Gini系数来选择分类问题的最佳节点，利用Square Error来选择最佳的回归分裂节点。

CART的决策树形态在处理数据时可以根据数据的趋势自行处理**缺失值**。但是单棵树的能力有限，很难拟合较大的数据集，因此通常伴随着随机森林的形态呈现。

### 缺失数据的处理方法
大数据处理的问题中往往不会得到完整的数据集合，而是存在一定质量问题的数据。包括：数据不完整、数据冗余、数据不一致、噪声数据等等。这些问题会降低数据挖掘算法的性能，因此不得不花费大量的经理和时间来处理这些数据。

数据缺失的类型：
- 完全随机缺失
- 随机缺失
- 非随机（不可忽略）缺失

数据缺失的处理方法：
- 直接删除元组
- 特殊值填充
- 平均值填充
- 使用最有可能的直来填充
- 保留缺失数据不予处理

## 支持向量机（Support vector machine,SVM）
SVM是一种常用的机器学习分类方式。在这个算法过程中，我们将每一笔数据在**N维度的空间中用点表示（N为特征总数，Features）**，每个特征的值是一个坐标的值。

如果以二维空间为例，此时有两个特征变量，我们会在空间中画出这两个变量的分布情况，每个点都有两个坐标（分别为tuples所具有的特征值组合）。


- 现在我们找一条直线将两组不同的数据在维度空间中分开。分割的曲线满足让两个分组中的距离最近的两个点到直线的距离**动态最优化**（都尽可能最近）。


- 那么看到这里一定很多人和我一样有一个疑问，那就是这种线性分类的SVM和之前提到的逻辑回归（Logistic Regression）有什么**区别**呢？

其实他们在二维空间的**线性分类**中都扮演了重要的角色，其主要区别大致可分为两类：
- 寻找最优超平面的方式不同。
- 形象来说就是Logistic模型找的超平面（二维中就是线）是尽可能让所有点都远离它。而SVM寻找的超平面，是只让最靠近的那些点远离，这些点也因此被称为**支持向量样本**，因此模型才叫**支持向量机**。

- SVM可以处理非线性的情况。
- 比Logistic更强大的是，SVM还可以处理**非线性**的情况（经过优化之后的Logistic也可以，但是却更为复杂）。

- **本质区别**为不同的目标函数。
- SVM采用的loss function为Hinge loss,而Logistic Regression采用的是Cross entropy loss。两者均为discriminative model。前者为了找到一个超平面区分支持向量，所以为Maximum margin classifier。后者为了表示一个数据的分布，所以为Log loss classifier。
- 举个例子：如果有一万个数据分布在点（1， 1）；而只有10个数据分布在点（-1， -1），那么SVM得到的分类超平面会是原点，而Logistic Regression得到的超平面会是接近点（-1， -1）的范围上。


- 数学模型要点：
- 注意区分软硬间隔函数
- 支持向量边界间隔是2倍的w宽度
- 原型和对偶型的区别（后者引用了拉格朗日算子和kkt，使得结果更容易求解）
- 对偶性的决策面计算用到了内积，可以方便地迁移到核函数的使用和高纬度非线性分割

### 优缺点
**SVM 优点**：使用核函数可以提高维度，解决分线性分类问题、分类思路明确、分类效果较好。
**SVM 缺点**：对大规模数据训练困难、难以很好地支持多分类。

## 朴素贝叶斯（Naive Bayesian）
在假设变量间**相互独立**的前提下，根据贝叶斯定理（Bayesian Theorem）可以推得朴素贝叶斯这个分类方法。通俗来说，一个朴素贝叶斯分类器假设分类的特性和其他特性不相关。朴素贝叶斯模型容易创建，而且在非监督式学习的大型数据样本集中非常有用，虽然简单，却能超越复杂的分类方法。其基本思想就是：对于给出的待分类项，求解**在此项出现的条件下各个目标类别出现的概率**，哪个最大，就认为此待分类项属于哪个类别。

贝叶斯定理提供了从P（c）、P（x）和P（x | c）计算后验概率P（c | x）的方法:

$$
P(c | x) = {P(x | c) P(c) \over P(x)}
$$

式子中的变量表示如下：
- P（c | x）是已知预测变量（属性特征）的前提下，目标发生的后验概率。
- P（c）是目标发生的先验概率。
- P（x | c）是已知目标发生的前提下，预测变量发生的概率。
- P（x）是预测变量的先验概率。

举一个例子：


- 这是一个训练资料集，提供一些身体特征，用来预测人的性别。此时假设特征之间独立且满足高斯分布，则得到下表：


- 通过计算方差、均值等参数，同时确认Label出现的频率来判断训练集的样本分布概率，P（male） = P（female） = 0.5。


- 此时给出测试资料，我们希望通过计算得到性别的后验概率从而判断样本的类型：

**男子的后验概率**:

$$
Posterior(male) = {P(male) P(height | male) P(weight | male) P(footsize | male) \over evidence}
$$

**女子的后验概率**:

$$
Posterior(female) = {P(female) P(height | female) P(weight | female) P(footsize | female) \over evidence}
$$

证据因子（evidence）通常为常数，是用来对结果进行归一化的参数。

$$
evidence=P(male)\,p(height|male)\,p(weight|male)\,p(footsize|male)+P(female)\,p(height|female)\,p(weight|female)\,p(footsize|female)
$$

- 因此我们可以计算出相应结果（这里为概率密度）：

$$
P(height | male) = {1 \over \sqrt{2\pi\sigma^2}}exp({-(6 - \mu^2) \over 2\sigma^2}) \\
P(weight | male) = ...
$$

- 其中 `μ` 和 `σ` 分别指的是模型训练后的特征正态分布参数中间值和标准差。

- 最后假设初始条件为平衡条件：

$$
P(male) = P(female) = 0.5
$$

- 就可以得出后验概率:

$$
Posterior Numerator(male) = {6.1984e^{-09}} \\
Posterior Numerator(female) = {5.3778e^{-04}}
$$

- 可以看出女性的概率较大，我们估计结果为女性。

### 优缺点
**Naive Bayes优点：** 对小规模表现好，可适用于多分类，增量式训练。
**Naive Bayes缺点：** 对传入数据敏感（边缘不平滑）。

## K近邻（K Nearest Neighbors）
该算法可以用于分类和回归问题，然而我们更常将其被用于解决分类问题上。KNN能够存储所有的案例，通过对比周围K个样本中的大概率情况，从而决定新的对象应该分配在哪一个类别。新的样本会被分配到它的K个最近最普遍的类别中去，因此KNN算法也是一个基于距离函数的算法。

这些**距离函数**可以是欧氏距离、曼哈顿距离、明氏距离或是汉明距离。前三个距离函数用于**连续函数**，最后一个用于**分类变量**。如果K = 1，新的样本就会被直接分到距离最近的那个样本所属的类别中。因此选择K是一个关系到模型精确度的问题。


- 如图所示，如果我们取K = 3，即为中间的圆圈内，我们可以直观地看出此时绿点应该被归为红三角的一类。而如果K = 5，此时延伸到虚线表示的圆，则此时绿点应该被归为蓝色的类。

在选择KNN之前，我们需要考虑的事情有：

- KNN在K数量大的时候的计算成本很高。
- 变量（Features）应该先标准化（normalized），不然会被更高数量单位级别的范围带偏。
- 越是**干净**的资料效果越好，如果存在偏离度较高的杂讯噪声，那么在类别判断时就会受到干扰。

### 欧式距离
空间中点X = （X1，X2，X3，...，Xn）与点Y = （Y1，Y2，Y3，...，Yn）的欧氏距离为：

$$
d(x, y) := {\sqrt{(X1 - Y1)^2 + (X2 - Y2)^2 + ... + (Xn - Yn)^2}}
$$

### 曼哈顿距离
在平面上，坐标（X1，X2，...，Xn）的点和坐标（Y1，Y2，...，Yn）的点之间的曼哈顿距离为:

$$
{|X1 - Y1| + |X2 - Y2| + ... + |Xn - Yn|}
$$

### 明氏距离
两点 P = (X1，X2，...，Xn) 和 Q = （Y1，Y2，...，Yn）之间的明氏距离为:

$$
{(|X1 - Y1|^p + |X2 - Y2|^p + ... + |Xn - Yn|^p)^{1 \over p}}
$$

- 其中p取1时为曼哈顿距离，p取2时为欧氏距离。

### 汉明距离
对于固定长度n，汉明距离是该长度字符串向量空间上的度量，即表示长度n中不同字符串的个数。

例子：
- **"toned"** 和 **“roses”** 之间的汉明距离就是3。因为其中 **t - > r，n -> s，d -> s** 三个字符不相同。

### 优缺点
**KNN 优点**：思想简单、可分类也可回归、可用于非线性分类问题、训练时间复杂度小、对outliner不敏感。
**KNN 缺点**：对于k值和距离计算的选取很难把持。

## K均值（K-means）
K-means方法是一种**非监督式学习**的算法，能够解决**聚类**问题。使用K-means算法将一个数据样本归入一定数量的集群中（假设有K个）中，每一个集群的数据点都是均匀齐次的，并且异于其它集群。


K-means算法如何形成**集群**？
- 给一个集群选择K个点，这些点称为质心。
- 给每一个数据点与距离最接近的质心形成一个集群，也就是K个集群。
- 根据现有的类别成员，找出每个类别的质心。
- 当有新的样本输入后，找到距离每个数据点最近的质心，并与质心对应的集群归为一类，计算新的质心位置，重复这个过程直到数据收敛，即质心位置不再改变。
- 如果新的数据点到多个质心的距离相同，则将这个数据点作为**新的质心**。

如何决定K值？
- K-means算法涉及到集群问题，每个集群都有自己的质心。一个集群的内的质心和个数据点之间的距离的平方和形成了这个集群的平方值之和。我们能够直观地想象出当集群的内部的数据点增加时，K值会跟着下降（数据点越多，分散开来每个质心能够包揽的范围就变大了，这时候其他的集群就会被吞并或者分解）。**集群元素数量的最优值**也就是在集群的平方值之和最小的时候取得（每个点到质心的距离和最小，分类最精确）。

## 随机森林（Random Forest）
Random Forest是表示**决策树总体**的一个专有名词。在算法中我们有一系列的决策树（因此为**森林**）。为了根据一个新的对象特征将其分类，每一个决策树都有一个分类结果，称之为这个决策树**投票**给某一个分类群。这个森林选择获得其中（所有决策树）**投票数最多**的分类。在回归问题中往往是取所有节点样本输出的平均值，以上两个过程（分类、回归）均属于**Bagging**的问题。其结果评估采用**泛化误差评估**（out-of-bag）。

Random Forest中的Decision Tree是如何形成的？
- 如果训练集的样本数量为N，则从N个样本中用重置抽样的方式随机抽取样本。这个样本将作为决策树的训练资料。
- 假如有N个输入特征变量，则定义一个数字**m << M**。m表示从M中随机选中的变量，这m个变量中最好的切分特征会被用来当成节点的决策特征（利用Information Gain等方式）。在构建其他决策树的时候，m的值**保持不变**。
- 尽可能大地建立每一个数的节点分支。


### 泛化误差评估（OOB）
泛化误差评估方式是采用训练集之外的未抽取样本作为测试集，对结果model进行测试，而最终的OOB值为 **error number / total number**。

### 随机森林的类别
随机森林根据建构森林的树种类不同也分为三类：
- ID3 Forest： 适合处理离散的数据集
- C4.5 Forest： 适合处理连续的数据集
- CART Forest： 适合处理离散或者连续的数据集

### 随机森林的优却点
随机森林的优点有：
- 对于很多种资料，它可以产生高准确度的分类器。
- 它可以处理大量的输入特征，并且不用做特征选择。
- 它可以在决定类别时，评估变数的重要性。
- 在建造森林时，它可以在内部对于一般化后的误差产生不偏差的估计。
- 它包含一个好方法可以**估计遗失的资料**，并且，如果有很大一部分的资料遗失，仍可以**维持准确度**。
- 它提供一个实验方法，可以去侦测variable interactions。
- 对于**不平衡的分类资料集**来说，它可以平衡误差。
- 它计算各例中的亲近度，对于数据挖掘、侦测离群点（outlier）和将资料视觉化非常有用。
- 使用上述。它可被延伸应用在未标记的资料上，这类资料通常是使用非监督式聚类。也可侦测偏离者和观看资料。
- 学习过程是**很快速**的。
- 抽样独立，容易实现**并行化**。

随机森林的缺点有：
- 树的维护代价（Maintain cost）太大。

### 梯度提升决策树（GBDT）
梯度提升决策树（Gradient Boosting Decision Tree）又叫做MART（Multiple Additive Regression Tree）, GBRT， Tree Net等，是一种迭代的决策树算法，同样由多棵树组成，所有树的结果**累加**起来就是最终结果。它和SVM一样都是泛化能力比较强的算法。GBDT属于**Boosting**的算法。

GBDT中的树是回归树不是分类树，但是经过调试后也能够用于分类。**GBDT具有天然优势能够发现多种具有区分性的特征以及特征组合**。

GBDT通过迭代多棵回归树来共同决策。当采用平方误差损失函数（Squared Loss function）时，每一棵回归树学习的是**之前所有树的结论和残差**，拟合得到一个当前的残差回归树（残差 = 真实值 - 预测值），训练过程遵循**Shrinkage原则**，即每次走一小步去逼近结果比每次迈一大步去逼近结果更容易避免过拟合。

**Example:**
利用GBDT模型预测年龄：训练集4人，年龄分别为14， 16， 24， 26。样本中有购物金额，经常到百度知道提问解答等特性。GBDT建立过程如下：


预测结果由所有树累加得到：
- A : 14岁购物少，经常在百度知道上提问，预测年龄A = 15 - 1 = 14
- B : 16岁购物少，经常在百度知道上回答，预测年龄B = 15 + 1 = 16
- C : 24岁购物多，经常在百度知道上提问，预测年龄C = 25 - 1 = 24
- D : 26岁购物多，经常在百度知道上回答，预测年龄D = 25 + 1 = 26

### Random Forest & GBDT差别
随机森林(random forest)和GBDT都是属于集成学习（ensemble learning)的范畴。集成学习下有两个重要的策略**Bagging和Boosting**。Boosting主要关注降低偏差（bias），因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成；Bagging主要关注降低方差（Variance），因此它在不剪枝的决策树、神经网络等学习器上效用更为明显。

- 如下图所示，当模型越复杂时，拟合的程度就越高，模型的训练偏差就越小。但此时如果**换一组数据**可能模型的变化就会很大，即模型的方差很大。所以模型过于复杂的时候会导致过拟合。


- 对于Bagging算法来说，由于我们会并行地训练很多不同的分类器的目的就是降低这个方差(variance) ,因为采用了相互独立的基分类器多了以后，h的值自然就会靠近。所以对于每个基分类器来说，目标就是如何降低这个偏差（bias)，所以我们会采用深度很深甚至不剪枝的决策树。
- 对于Boosting来说，每一步我们都会在上一轮的基础上更加拟合原数据，所以可以保证偏差（bias）,所以对于每个基分类器来说，问题就在于如何选择variance更小的分类器，即更简单的分类器，所以我们选择了深度很浅的决策树。

## 降维（Dimensionality reduction）
当今的社会中信息的捕捉量都是呈上升的趋势。各种研究信息数据都在尽可能地捕捉完善，生怕遗漏一些关键的特征值。对于这些数据中包含许多特征变量的数据而言，看似为我们的模型建立提供了充足的**训练材料**。但是这里却存在一个问题，那就是**如何从上百甚至是上千种特征中区分出样本的类别呢？**样本特征的**重要程度**又该如何评估呢？

- 其实随着输入数据特征变量的增多，模型很难拟合众多样本变量（高维度）的数据分类规则。这样训练出来的模型不但**效果差**，而且**消耗大量的时间**。
- 这个时候，降维算法和别的一些算法（比如**Decision Tree**、**Random Forest**、**主成分分析（PCA）** 和 **因子分析**）就能帮助我们实现根据相关矩阵，压缩维度空间之后总结特征规律，最终再逐步还原到高维度空间的训练模式。

### 主成分分析（PCA）
在多元统计分析中，PCA是一种分析、简化数据集的技术，经常用于减少数据集的维数，同时保留数据集中的**对方差贡献最大**的那些特征变量。

- 该算法会根据不同维度的压缩（在这个维度上的**投影**）来测试**各个维度对方差的影响**，从而对每一个维度进行重新排序（影响最大的放在第一维度）。之后只需要取有限个数的维度进行训练，就能够保证模型拟合最佳的数据特征了。

### 因子分析
该算法主要是从关联矩阵内部的依赖关系出发，把一些重要信息重叠，将错综复杂的变量归结为少数几个不相关的综合因子的多元统计方法。基本思想是：根据**相关性大小**把变量分组，使得同组内的变量之间相关性高，但不同组的变量不相关或者相关性低。每组变量代表一个基本结构，即公共因子。

## Gradient Boost & Adaboost & Xgboost
当我们想要处理很多数据来做一个具有高度预测能力的预测模型时，我们会用到Gradient Boost和AdaBoost这两种Boosting算法。**Boosting算法**是一种集成学习算法，它结合了建立在多个基础估计值上的预测结果，来增强单个估计值的准确度。（增强对于不同的点权重可以不一致）

### Adaboost


Bossting能够对一份数据建立多个模型（如分类模型），通常这些模型都比较简单，称为**弱分类器（Weak Learner）**。每次分类都将上一次分错的数据权重值调大（放大的圆圈），然后再次进行分类，最终得到更好的结果，所有被分错的样本**权重更新比例相同**。最终所有学习器（在这里值分类器）共同组成完整的模型。

### Gradient Boost
与Adaboost不同的是，Gradient Boost在迭代的时候选择梯度下降的方向来保证最后的结果最好。损失函数（Loss function）用来描述模型的误差程度，如果模型没有Over fitting，那么loss的值越大则误差越高。如果我们的模型能够让损失函数值下降，说明它在不断改进，而最好的方式就是让函数在**梯度的方向**上改变。（类似神经网络的**Gradient Descend**）

### Xgboost
Xgboost是boosting算法的一种延伸，能够有效处理多特征混杂的批量数据集，因此被称为大数据比赛的神器。

Xgboost有以下几个特点：
- 支持Linear Classification，其过程相当于LR + L1/L2 normalization。
- xgboost与gbdt相比使用了残差的二阶泰勒展开式，能够获得更多资讯并加速学习。
- xgboost加入了norm项，包括叶节点个数，每个叶节点输出的Score和L2 norm等信息传递给下一层，降低了Variance，防止过拟合。
- 利用了Shrinkage算法，利用小学习率大迭代数的方式学习。
- xgboost可以自动学习出分裂方向，预测缺失值。
- xgboost在特征选择时可以利用存储在block中的实现排序的信息增益数组来并行处理，减少计算量。

# 神经网络（Neural Network）
基于生物学的神经结构，将神经细胞的电信号传播机制应用到计算机结构中来，通过对信号传导和演变来组成网络架构。人工神经网络中的每一个“神经元”就是一个Neuron，用来以一定的算法改变输入的信号，从而改变传输的信息，达到对环境做出反应的目的。另一方面，通过神经网络产生的反应收到环境的反馈（做的好或不好），这些反馈和目标行为的误差会通过神经网络的反向传递从原先的路径传送回去，沿途中这些反馈信号会反过来刺激Neuron调整相应的参数从而使得下一次正向传递的结果能够更加贴近目标。如此往复便是整个神经网络训练的过程。


人类通过学习，能够掌握和判别事物的特征从而对事物的本质做出判断，而机器同样是利用这种机制建立起相应的“识别”模型，这些模型对不同的事物具有不同的反应强度，利用强度的不同来区别事物的本质。

## 神经网络的基本结构

一个简单的神经网络由3个部分组成：
- **Input Layer**
- 输入层，用来将资料喂给神经网络
- **Hidden Layer**
- 隐藏层，用来尝试改变和调整神经网络的模型和数据的转化
- **Output Layer**
- 输出层，用来将神经网络处理后的信号输出成最终的结果

### 神经元（Neuron）的激活函数（Activation Function）

在神经网络学习的过程中，需要对输入的信号做出某种调整，才能真正得到最终的结果。
传统的激活函数包括：
**Sigmoid**、**TanHyperbolic(tanh)**、**ReLu**、 **softplus**以及**softmax**函数


例如当我们输入一只猫，输入层神经网络会把信号传递给隐藏层的神经元。每一个接收到信息的神经元会通过自己现有的经验对信号做出判断，利用激活函数（activation function）来判断此时的神经元是否需要被激活。激活后的神经元就会对输入信号进行处理并传递给下一层的神经网络层，如此往复当信号传递到输出层时则会经由最终的刺激函数（一般为softmax）产生相应的结果确定输出的信号是属于哪一个标签（label）。


如果此时计算机得到了错误的结果，我们就会通过反向的传递将误差传导回去，改变**所有**的神经元参数，继而那些原本活跃的神经元就会被弱化，在下一次的神经传导过程中就会逐渐被激活函数淘汰。


经过更新的神经网络能够在下一次迭代过程（epoch）中就会改变思路，转而尝试其他的判断方法。


直到得到正确的结果，误差就会小到可以忽略，如此神经网络得以生成。

## 卷积神经网络（CNN）
卷积神经网络（Convolution Neural Network）在图片识别方面能够给出不错的结果。而卷积的作用实际上是对Fully connected的控制：


利用卷积的方式来选取进入下一个hidden layer中每一个neuron的链接数量，这样可以有效控制每个neuron处理信息的**针对性**。（Different neurons have different, but overlapping, receptive fields）



利用**图片**作为例子，任何输入的信号都会被转化成计算机能够识别的数字信号集合，例如矩阵（matrix）。**文字**也是一样的，我们把文字抽象成一个固定维度的向量，在这个维度空间中，每个字都是独立区别开来的，文字的多样性就有这些数字的排列组合来定义。这些信号集会通过输入层读取信息并进入神经网络中。
卷积神经网络就是其中的一种网络模式，我们可以把它分成**卷积**和**神经网络**两个部分来理解。
- **卷积**：可以理解为对一个区域信号强弱的总体分析。通过卷积运算可以在一定的区域内总结有用信号的强弱分布，从而对一定区域内信号的变化情况能够有一个较好的认知。卷积能够增强信号的连续性，用区域单位代替点电位。


- **神经网络**：卷积神经网络利用批量过滤的方式，在大范围的信号中不断收集信息，每一次得到的区域信息都是区域中的一小块，之后从这些信息中总结出一些所谓的边缘信号（edges，例如：竖线，横线，斜线，圆圈等基本边缘，其可能分别代表人脸眼睛的左上角，中间，右上角等等部位的区域信息）。同样，用相同的方式从边缘信息组合的图像中总结出更大范围的边缘信息（例如：利用竖线，横线，圆圈等结构组合出整个眼睛）。最后将得到的结果传入全连接层的分类神经网络中就能得到相应的label了。

**Example：**
如果以灰阶图像为例，其高度为1，fsize = 5。此时ksize = 3, strides = 1。那么结果为一个reshape_size = 3的图像。

$$
rsize = {fsize - ksize + 2* padding \over strides} + 1
$$


- 卷积的过程就是将物件的特征值（图像多为基本颜色）拆分成小块区域，然后计算其中**各个特征值**的和。最后输出为一个压缩后的图像。如上图，以0为黑色，1为白色，那么求得的最后图像中每一个方格的值就是kernel中所有格子数的加权和。


图片的维度信息有长、宽和高，长和宽用来表示图片的信号集，高度则是表示颜色的信号分布。黑白颜色只有1个高度单位，而彩色的图片则有R、G、B三种基本颜色的信息单位。


利用批量过滤从图片中收集一定区域中的像素块，而输出的值就是一个高度更高，长和宽都更小的图片。这些图片存储的就是边缘（edges）信息。


反复进行同样的过滤步骤，就可以对图片的信息有更好的理解。之后再对结果进行分类就行了。


在卷积的过程中，神经元可能无意中会丢失一些信息。池化（pooling）就是为了解决这样的问题而被设计出来的。既然我们的信息是在卷积过程中压缩的时候丢失的，那么我们就舍弃这个步骤，直接保留原本的长宽，最后在由池化层统一进行压缩长宽的动作。

跟踪细节如下：


### CNN常用结构

比较流行的**CNN结构**先是输入信号，经过卷积层进行卷积运算，然后经过池化压缩长宽的维度。常用的是Max Pooling的结构：


在区域中区最大值作为代表这个区域的信号。之后再次对结果进行相同的卷积和池化，进一步压缩信号。之后通过两个全连接层将信号传导给分类器进行分类预测。

## 递归神经网络（RNN）
递归神经网络（Recurrent Neural Network）在自然语言处理和序列化信息分析方面能够给出不错的结果。如果说CNN是图像识别的代表性神经网络，那么RNN就是文字处理领域的“CNN”。
- **语言文字**就是一个典型的**序列化信号集**，我们说出的每一句话之间，甚至每一个词之间都有先后关系的依赖，如果抛开字的先后顺序，我们的语言将会失去原本的含义。


假设现在有许多不同的数据信号，如果神经网络只是基于当前的输入信号进行结果的预测，那么就相当于无视了所谓的连续规则，其中必然会丢失重要的时序信息。就好比做菜，酱料A要比酱料B先放，否则就会导致串味的现象。因此一般的NN结构无法让机器了解数据之间的关联。

**那么要如何做到让计算机也具有处理连续信号的能力呢？**
- 从人的角度出发，不难想到的方式就是记住先前处理过的信号，并将这些信号一同作为输入传递到当前的神经网络中。


我们将先前处理的结果存入记忆中，在分析当前信号时会产生新的记忆。由于记忆之间不会相互关联，因此我们可以直接将先前的记忆调用过来一起进行处理：


如此一来往复多次，神经网络就能携带长期的序列信号进行处理了。**总结之前的流程：**


- 在RNN运作过程中，每次的结果都会被存储为一个State状态信号，并通过不断迭代传递到下一个乃至更远的神经网络中去。


- 在RNN下一个时刻到来时，State状态同样会被存储成T+1时刻的State，但这是的 **Y（t）** 不再只是由 **S（t+1）** 来决定的，而是通过 **S（t）** 和 **S（t+1）** 共同处理 **X(t+1)** 得到的结果。因此这个State结构也可以用递回的方式来表示。

### RNN常用结构
RNN的形式多种多样，一般需要根据处理的情况不同选择相应适合环境的模型进行建模。


通常可以看到以下几种：
- 如果是用于**分类**的话，例如在判断一句话的情感取向，判断是positive或者negative的情况下，倾向于使用根据最终结点的结果来输出判断的RNN：


- 如果是用于**描述**的话，例如通过一些集成度高的特征信号（图片等）来产生一个描述性的句子或者序列的情况下，倾向于使用根据单一输入来逐步读取时序信息的RNN：


- 如果是用于**翻译**的话，例如通过一段连续的输入信号来预测下一段连续输出信号的情况下，倾向于使用多对多输出的序列化RNN（Sequence-to-Sequence）：


## LSTM(Long Short-Term Memory)
RNN的网络在训练的时候会通过递归的方式传回之前网络学习到的记忆，从而使神经网络能够保留先前的信息。而传统的RNN在处理记忆单元的时候时常还是很容易 **“遗忘”** 重要信息的，因此我们需要一个更加强大的网络结构来帮我们锁住重要的过去式信息流，而最流行的结构也就是所谓的 **LSTM** 了。

那么传统的RNN模型究竟是为何会经不起**长时间记忆**的考验呢？这里用一个例子来说明：


- 假如我们所要分析的句子如上图所示，要想让机器知道我们吃的是 “红烧排骨” 而不是 “辣子鸡”，这时候神经网络就会将误差反向传递回去。

- 在反向传递的过程中，由于我们所要改变的句子成分在时序信息的最开始部分，因此需要经过很长的误差传递才能到达（也就是我们说的长记忆或久远记忆）。这个时候我们的误差在反向传递的过程中都会经由梯度在每一个神经网络层进行一个 Weight 权重的改变。而加入这个权重值是一个大于0小于1的数值，则反向传递的误差在经过每一次的传递过程就会损失一部分的信息，如此往复到了久远的网络层之后，这个误差就会因为信息太弱而 **消失** 了，这样我们的神经网络就无法回忆起重要的信息了，也就是所谓的梯度消失（Gradient Vanishing）。


- 而另一方面，如果这个权重值是一个大于1的数，在不断迭代的过程中就会让误差不断放大，最终达到无法修复的地步，也就是所谓的梯度爆炸（Gradient Exploding）。


- 而LSTM网络就是利用了在RNN结构基础上加入了三个Gate来作为控制器，从而控制误差的传递和信息的更新的。这三个 **Gate** 分别为 **Input Gate** 、 **Forget Gate** 和 **Output Gate**。


- 我们可以将LSTM的输入分成两部分，一部分是从一开始就持续进行的信息累加（也就是所有时刻的信息加总，我们成可以想象成主线剧情）。另一部分就是每一个神经网络层单独拥有的信息部分（可以想象成支线剧情）。主线剧情随着神经层的传递不断累加信息，而直线剧情则是每一层的神经元将重要的信息通过不同的权重值传递给主线剧情，而不重要的部分则经由遗忘控制器（Forget Gate）来替换掉。输出控制则是用来规划每一个神经层传递到下一级的时候需要如何分配输出的权重问题。这些控制器都会接受反向传递的误差来动态调整权重值，从而使网络能够正常地运作。


## 如何选择合适的模型
不同的神经网络结构能够将输入和输出转换成不同的形态，针对**不同的Domain**，我们就能够对模型进行选择。


如图所示：
- 如果输入和输出信号是Vector，多用在分类和特征提取的时候，我们会选择使用Fully Connected Feedforward Network。

- 如果输入和输出信号是Matrix（例如图片或者多维度特征集合），我们多选用Convolutional Neural Network。

- 如果输入和输出信号是Sequence Vector（例如声音和文字），我们多选用Recurrent Neural Network。

# 神经网络非监督式学习实现Auto-encoder
在神经网络训练过程中，往往会需要输入大量的信息，而这些信息对于计算机的学习来说具有十分巨大的负担。想想人类的学习过程，如果一次性塞给我们大量的信息，不但达不到很好的学习效果，还会浪费大量的时间。

因此我们需要一个特殊的神经网络来将原本的信息进行压缩，提取其中最具有代表性的信息，这个网络就是所谓的**编码器（encoder）**。之后再通过放大压缩后的信息，重现原始资料的全部信息，也就是 **解码（decoder）** 的过程。而我们所需要做的就是取得编码器压缩之后的简要信息，送入神经网络进行学习，从而达到我们的目的。


- 压缩和解压的过程共同构成自编码（Autoencoder）的行为，通过训练编码器和解码器的神经网络结构，依据每次压缩前和解压后数据的对比情况来判断压缩的好坏程度，并利用反向传递来修正误差，从而最大程度上的压缩和还原原始信号。由于从头到尾我们所需要的输入信息为原始信号的信息，整个过程不需要对应的标签信息（label），因此autoencoder属于非监督学习的方式。


- 通常会使用到的部分是自编码的结果，也就是压缩过后的概括性讯息。我们建构的其他神经网络只需要对这些精髓的信息进行学习就行了。这样的方式不仅减少了神经网络的负担，还能达到很好的学习效果。

自编码的思路和传统的主成分分析算法的精髓类似，都是试图从数据中抓住决定性的关键内容，来概括和分类数据的特征。相比于传统的降维算法中的PCA主成分分析方法，Autoencoder甚至能够取得更好的效果，因此也常被用来对原始数据进行**降维**。

# 生成对抗网络（GAN）
生成对抗网络（Generative Adversarial Net）不同于传统的FNN、CNN和RNN是将输入的数据和输出的结果通过某种关系联系起来的神经网络模型，GAN则是一种**凭空生成结果**的模型。

- 当然所谓的 **凭空** 并不是真正意义上的**无**，而是通过一些随机的尝试（随机数组合）创造出一些东西。比如一张图片（像素集合）。


- 我们可以把这个随机尝试生成图片的网络比喻成一名新手画家，他们根据自己的灵感用现有的技术生成一些画作。一开始可能有了灵感但是由于作画技术的限制，往往无法生成理想中的图片。


- 于是这名画家就找到了自己的好朋友新手鉴赏家，可是因为新手鉴赏家本身不具备良好的分辨能力，因此往往给出错误的回答。


- 这个时候就会有外部的干涉参与其中，通过一些标记好的资料来训练这名新手鉴赏家，让他一步步能够辨别画作的好坏。


- 最重要的是在训练新手鉴赏家的过程中，随着鉴赏技术不断成熟，鉴赏家开始对新手画家的一些作品做出正确的判断和反馈。这时新手画家就会从这个新手鉴赏家手中得到**真正的有用的标签（label）**，进而利用这些标签改变自己的网络，让自己能够画得更好。


- 总结之前的流程，就是新手鉴赏家这个神经网络利用从外部监督得到的反馈提升自己，然后再利用自己去训练另外一个神经网络，随着新手画家神经网络的不断提升，鉴赏家网络得知自己的能力已经无法鉴赏该画作时，就再次求助外部反馈。就在这一次一次地**对抗**中，两个神经网络就会越来越强大。


- 在GAN网络中，新手画家就是我们的**生成器（Generator）**，新手鉴赏家就是所谓的**Discriminator（辨别器）**，画家的每一幅画都是通过不同的数字排列组合成的像素矩阵，也就是我们说的图片。


## GAN的应用
GAN因为能够通过随机组合产生新的数据，因而常被用在数据的合成和生成新数据的方面。

- 其中一个重要的例子就是数据序列的加减法：


图中的二次元人物是通过GAN神经网络的学习，然后利用描述性的选项组合，来生成不同特征的人物图像的一个神经网络网络应用。

# 理解神经网络的“ 黑盒子 ”
神经网络的成功之处在于它能够从输入和输出的数据中总结出一个抽象的算法函式，基于这个函式的关系我们就能够对未知的数据进行预测。

例如：
$$
y = {ax + b \over 2}
$$

这个就相当于一个已经训练好的神经网络模型，对于输入信号`X`通过网络的处理之后得到输出结果`Y`。

而神经网络建立的模型就像是把算法公式中所有参数进行一个**封装**，然后开放一个相应的**接口(Interface)**用于呼叫和取值。因此神经网络也被亲切地称之为 **“ 黑匣子 ”** 。


- 神经网络一般分为三个部分，输入和输出都是人类能够理解的信息，而中间的部分就是所谓的**盲区**。


- 如果我们将神经网络的中间层注意拆解后会发现输出的事物往往会是我们看不懂的东西，这就是为什么神经网络 **“黑”** 的原因了。对于人而言，我们在记忆复杂的环境和事物时往往会用一些自己熟知的**记号来标记事物**，使得我们能够更加清楚地记得事物的特征。计算机也是一样的：


- 我们知道神经网络处理的信息大都是数字集，通过神经层的分离可以看到这些数字集发生了改变，这些改变在人类看来无法理解，但事实上却是计算机利用自己的方式将这些事物通过它们捕捉到的特征信息转换成**它们眼中的记号**。也就是说计算机正在试图用自己能够理解的方式标记这些特征。


- 在神经网络中，我们称人们能够识别的**特征**记作**Features**，而机器转换后的**特征标记**记作**Feature Representation**。


- Feature的取值不同，结果所呈现的Feature Representation也会有所不同


- 利用手写数字的特征来理解的话，神经网络的Feature Representation就是空间中不同区域的分布状况。不同的位置聚集了不同的数字集合，落在不同的区域内就说明该输入属于哪一个输出。也就是说计算机把我们熟知的**数字（也就是Features）** 用 **空间坐标区域（也就是Feature Representation）** 来表示。


- 理解神经网络的内部结构和Feature Representation的含义可以很好地利用 **迁移学习（Transform Learning）** 的方式来组合我们的神经网络，从而达到更好的效果。


- 例如我们已经训练好了从图片中解析物体的神经网络，它能够从图像的序列信息中提取关键的特征事物，此时只需要将输出层替换掉，再加入新的神经网络结构进行连接，就可以生成全新的模型。


- 新的神经网络重新训练之后就能够具有全新的功能，利用原先的网络优势来拓展生成新的**特征标记**，一定程度上减少了神经网络训练的复杂度。基于先前的图像提取，能够从图中得到事物的**特征信息（Feature Representation）**，再利用新的网络将这些信息进一步转换成表示事物价格的**特征信息**，如此一来神经网络的功能就得以演化了。

# 如何优化神经网络（Optimization）
优化（Optimization）一直是人类领先于其他生物而在环境中不断成长的重要因素，机器也不例外，通过优化的方式自我更新才能不被复杂的环境所淘汰。

## 神经网络梯度下降算法（Gradient Descent）
神经网络能够自我学习自我更新不仅仅归功于它能够学习并记忆输入和输出的规律，最重要的是它能够根据学习的规律进行自我调整以让自身适应这个变化的环境。那么机器学习模块又是如何进行优化的呢？答案就是所谓的**梯度下降**了。

- 先前说过神经网络的自我调整是基于结果的反馈，也就是所谓的误差来修正自己：

$$
Cost = {(predicted - real)^2}
$$


- Cost函式表达的结果近似可以看成一条平滑的二次曲线，而在更高纬度的层面上就是一个**弯曲的面**，越是接近曲面的底部，误差的Cost就会越小。而梯度下降（Gradient Descent）就是在这个曲面中通过微分的方式找到一个能够向最低点移动的方向，并以此作为动力开始优化自己。当达到最低点时，求导的结果和二次曲线相切，这个时候梯度就消失了，也就是所谓的最佳化状态。


- 然而按照理论而言，这样的方式也太容易得到想要的结果了，那么神经网络的优化（Optimization）也太神了吧，其实这一切是**很难实现**的。

- 不同于之前所看到的梯度下降曲面，我们生活中的信号往往需要有许多的维度来表示，尤其是复杂的信号（例如图片或者文字）。这些信号在低纬度的时候几乎无法将他们区别分类，因此我们只能将他们丢到更高的维度上面进行非线性分割。这时候就会存在一个问题了，随着维度的提高，我们所熟知的曲面渐渐变得不再平滑了：


- 这样的曲面反映出一个关键问题就是**优化的不确定性**。


- 在多维的复杂曲面中，我们能够找到不止一个梯度消失的点，而这些至低点并不都是我们所谓的**最优解**。当我们初始化的位置不同，我们的结果就会随着梯度下降（Gradient Descent）的优化模式寻找距离自己最近的一些至低点。如此一来**不同的初始值**就会很大程度上影响我们优化的结果。针对这个问题，目前比较好的解决方式就是给信号加上一个 **动量（Momentum）** 以至于在运动至最低点的时候，动量会趋势信号的Cost继续改变（此时梯度又恢复了）。如果我们设定的动量足以让信号摆脱当前的梯度曲面（说明曲面不够深，也就是所谓的局部最优解），信号就会继续去寻找一个更加**难以摆脱的梯度曲面（更深）**，如此一来就能够尽量靠近**全局最优解**。

# 迁移学习(Transfer Learning)
学习的过程往往是通过累计的知识一步一步总结经验,然后优化升级从而解决更加复杂的任务。而这个升级的过程就是不断地将已有的知识整理加工，运用到其他乃至更为复杂的领域。这样的思路在神经网络训练过程中就被称为**迁移学习（transfer learning）**。


神经网络复杂的结构造就了庞大的计算量，如果需要在短时间内同时维护许多个功能类似的模型往往代价巨大。这个时候迁移学习就能派上用场了，利用模型的迁移能力，将具有相同特性的模型转移到新的任务上来，从而免去了重复训练模型的时间和计算量。

- 然而不是所有的模型都需要利用迁移学习。在一些结构相对简单的网络中，我们通常选择重新训练一个新的网络而不会选择使用迁移学习。原因是小的网络参数相对较少，而且需要拟合的资料特征有限，这些特征之间往往会有一些独特的特性不适合用在迁移后的网络中，这样就会造成网络自身的误差相对较高，影响模型的效率。

# 如何评估神经网络的优越性
机器学习的过程中，神经网络往往会存在一些问题，例如学习效率低，学习误差（loss）变化幅度摇摆不定，或是因为杂讯和信号太多没有办法找到有效的规律和结论。而这些问题可能来自**数据**、**参数**以及**模型结构本身**等各方面的因素。

## 数据集评估
在评估数据和模型的吻合度上，我们需要对数据进行一个初步的认知，也就是确定数据集和结果之间的特征关系，也就是所谓的**Features**。这些Features能够很大程度地影响神经网络的学习效率。

- 传统的机器学习算法通常会通过采用 **Cross-Validation** 的方式来对数据进行评估。也就是现将数据集依照6:2:2（不固定）的比例进行拆分，分别表示为**训练集（Training Data）**、**验证集（Validating Data）** 和 **测试集（Testing Data）** 三个部分。

评估模型最终结果的好坏往往是测试集决定的，这里面会有训练的时候不曾出现过的输入信号，这也是对神经网络效能的一个**考验**。而要在学习的过程中让学习训练集的模型意识到不单单是要学好那些见过的部分，**没见过的部分**也需要充分地准备，这时候就会用到验证数据集的检验了。在训练完毕之后，我们重新划分3个资料集的比例和分布，就可以重新定义出新的训练资料了。在不断变换数据集的同时，我们可以对模型的**参数进行更加科学的优化和分析**。

- 评价机器学习的方式（Evaluation Function）包括了**误差（Error或Loss）** 以及 **精确度（Accuracy）**，误差就是预测结果和实际结果的差值，而精确度就是在预测过程中的正确率了。

有的时候在训练的时候往往结果让人满意，可是到了测试的时候结果却不尽人意，这又是为什么呢？


原来在训练过程中，神经网络太过优秀了，以至于它将自身优化成为了完全符合这个输入数据的一个模型。而一旦我们测试的输入和训练样本差别很大，就会让模型无从下手，这种现象就是所谓的过拟合（Overfitting）。

- 比较常用来解决Overfitting的方式为**Dropout**，也就是在训练的过程中随机舍弃掉一些数据，从而让自己的模型留有一些变通的空间，来适应突发的情况。

# 为什么要对特征进行标准化（Normalization）
现实中的数据可能来自不同的地方，不同来源的数据有各自的取值范围。而在学习的过程中，这些取值范围往往**差距悬殊**，这样就会对训练产生障碍。想象一下，如果我们两个权重矩阵M1和M2,我们给M1一个三位数量级的输入参数，给M2一个一位数量级的输入参数，会发生什么事情呢？答案很明显，当我们改变M1的参数时，对于总体的影响是十分巨大的，而相比之下想要达到这样的差距，就必须对M2进行很大幅度的调整。

## 如何标准化
延续之前的例子，如果这时候的误差值是：
$$
Error = {predicted - real}
$$
那么对这个误差我们应该确保对所有的权重矩阵（Weight Matrix）具有类似的跨度。

通常用于标准化（Normalization）的方法有两种：

- 一种是**最小-最大标准化（Minmax Normalization）**。它会将所有的数据按照一个缩放比例转换到0和1的区间中。对单独的特征而言，这个权重是唯一的（全局适用）。

- 另一种方法是**标准正规化（Standard Normalization）**。它会将所有数据转换成平均值为0，标准差（Std）为1的数据。

这样的标准化问题不但能够平衡数据间的波动和差异，还能提高学习的效率，让机器学习能够正常地平衡每一个特征变数的优化和调节。

# 什么是批标准化（Batch Normalization）
Batch Normalization和传统的正规化方式类似，都是为了将分散的数据统一成为一定的样式，也是优化机器学习的一种方法。之前讨论过为什么要对数据进行标准化，为的就是让训练的参数不特别偏袒某一个数据。从而让机器更好地学习多元的规律。

回忆之前的内容，我们为什么需要在输入的时候对我们的数据进行标准化呢？

- 那是因为在训练过程中神经网络对偏差较大的数据很难平衡他们的权重。试想一下如果一个输入为1而一个输入为20：


- 在经过一层神经网络运算之后，由于激励函数的关系两者的值会被投射到特殊的函数空间中，这个时候数据的差异就凸显了出来。以tanh为例，1的输入经过tanh计算后取值处于tanh函数的敏感部分（梯度最大）。而大数值20经过tanh计算后反而位于不敏感的部分（几乎水平）。这个时候的值对于神经网络而言已经不再重要了，因为无论怎么变化其数值也不会相差太多。就像是轻轻拍一下自己和重重打一下是一个感觉，这样的结果对于神经网络是致命的。

- 那么既然我们对输入层的网络进行了正规化（Normalization），那么又为何需要batch normalization呢？

- 原来在hidden layer的部分也会存在这个问题，因为神经网络的隐藏层也同样使用了激励函数。


- 这个时候我们就是用Batch Normalization的方式将数据分成几个大小相同的Batch进行训练，在每次经过神经网络的全连接之后进行一次正规化，然后才送入激励函数中进行计算。


对于激励函数（Activation Function）而言，最佳的数据传递范围是下图红色的区域，也就是所谓的**敏感区**。而位于这些区间的数据更容易被传递到下一层网络中。而正规化的目的就是让更多的数据集中在这个敏感区中，这样可以防止数据呈现**两极分化**的状态，让神经网络的训练更有价值。


- 与神经网络的反向传递类此，在进行了正向传递的正规化之后，我们会将结果利用一个线性的方式反向传递回来，这种方式为的是让机器自己学习正规化的有效程度，从而自我修正和改变。就相当于在神经网络中嵌套了另一个神经网络用以训练前一个神经网络的更新能力。


- 通过对比没是否有Batch Normalization的结果我们发现，Batch Normalization能够让训练过程中的数据更加具有连续性，同时也让数据在每层神经网络之间能够更好地传递下去。


# 如何判断特征的的好坏
机器学习的过程中，特征是我们的模型训练和测试的重要参照指标，好的特征往往能使得模型快速拟合资料的分布，也就能取得更好的预测结果。那么什么样的特征是真正有用的特征（Features）呢？

在分类问题中，没用的特征会为我们的分类带来不必要的计算和误导，以 `Iris Corpus` 为例。


- 以花萼宽度的特征来看，两种花的分布大概能够满足如下的分布状况：


- 可以看出在该特征的情况下，两种花的特征分布呈现一种趋于平衡的关系，如此就可以判断光凭这种特征是很难将花的品种区分开来的。因此我们称这样的特征为无意义的特征（不好的特征）。

此外，如果我们改变特征的选取，转而采用 **花瓣长度** 来作为评判的特征，那么会如何分类呢？

- 我们利用Python的可视化library `Matplotlib` 来观察特征的变化情况吧。

import matplotlib.pyplot as plt
import numpy as np

setosa, versicolor = 500, 500
setosa_length = 1.5 + 0.4 * np.random.randn(setosa)
versicolor_length = 4.5 + 1.2 * np.random.randn(versicolor)

plt.hist([setosa_length, versicolor_length], stacked = True, color = ['r', 'b'])
plt.xlabel('Petal Length')
plt.ylabel('Numbers')
plt.show()


- 从图中可以看出，当花瓣长度大于等于3之后，我们基本可以断定这种花就是versicolor，相反当花瓣长度小于3的时候，我们就可以很大程度上断定花的种类就是setosa。这样能够明显区分不同事物的特征就是所谓的好的特征。

- 另外，当一种特征在特定的取值上难以区分类别的时候，我们就需要其他新的特征来辅助我们判断事物的种类，这也就是神经网络的特征集合的作用所在了。

特征压缩的方式有很多，常用的包括之前提及的 **Auto-encoder** 等。总而言之，想要得到好的特征信息，我们就需要遵循以下几点：
- 避免无意义的信息。
- 避免重复性的信息。
- 避免复杂的信息。

# 什么是激励/刺激函数（Activation Function）
Activation Function是人工神经网络中的一个重要环节，想要探讨它的重要性，那么首先就需要知道为什么我们的神经网络离不开这个结构呢？其实在神经网络的训练过程中，许多问题我们往往无法用单纯的线性方式解决。这时候我们就需要借助Activation Function的帮助了。

那么什么样的模型表示才是线性的呢？
- 所谓的线性方程（Linear Function）就是能够用一条直线反应出模型的变化趋势。


- 比方说随着商品人气的升高，销量也持续不断地上涨。然而并不是所有喜欢这个商品的人都会购买它，因此在销售达到饱和的时候，即使人气还在不断上升，但是销量的增长却开始变慢，这个时候我们就无法用线性的方式表示这个趋势了。因此我们便会选择非线性的方式（NonLinear Function）表示我们的模型变化：


- 我们可以用一个式子来统一描述神经网络的流程：

$$
y = Wx
$$

- 而这个时候的模型就是线性的，我们需要借助Activation Function的力量来 **“掰弯”** 这个线性的模型。

$$
y = AF(Wx)
$$

- 新的模型表示式中的 **AF** 就是我们的Activation Function。其实 **AF** 的作用并没有想象的那么奇幻，它就是一些非线性方程的集合：


- 通过非线性方程的转换，就可以把连续的输入信号在不同时刻进行不同程度的改变，使它们之间不再遵从线性关系的约束。

- 当然我们可以使用的Activation Function远不止上面的那些，我们甚至可以自己创造适合我们模型的激励函数。但是重要的一点是，这些函数必须是 **可微分** 的，也就是可以通过求导得到相应的梯度。原因是我们之后的Optimization的过程中会使用反向传递的方式更新模型的参数，而反向的核心步骤就是对**原方程微分**，这样才能完整地把误差传递回模型。


如何选择合适的神经网络是训练一个好的模型的重要先决条件。那么应该怎么选择适度的Activation Function呢？

- 在小的模型中，**激励函数**的影响往往没有那么明显，因此我们不需要做太多的考虑。相比之下在大型模型中，由于曾与曾之间的传递复杂度高，因此草率地选择Activation Function会导致**梯度消失**、**梯度爆炸**等问题。


一些常见的神经网络结构推荐使用的激励函数也不同，这些关系到模型的特性和实际的应用场景。在CNN中我们推荐使用**Relu**作为层级之间的激励函数；而在RNN中我们则推荐使用**Relu或者Tanh**作为激励函数。

# 什么是模型过拟合（Overfitting）
在训练神经网路的过程中，我们有时会遇到这样的情况：在训练过程中我们对训练资料和预测结果的比对发现，模型的拟合效果非常优秀（也就是Accuracy很高）。而在我们使用测试资料再次试探我们的模型时，发现结果却不尽人意。这时候很可能的情况就是出现了**过拟合（Overfitting）**。


- 以一个例子而言，通过机器学习训练后，我们可以用一条回归直线表示空间中分布的输入信号，这时候的误差范围取决于离直线最远的点。但是如果我们的机器仍不满足这个误差，想要继续降低它的时候，就会出现这个情况：


- 这时机器改变了原来的拟合线，转而开始依次调整每个点的距离，让回归线不再只是一条直线，而是一条设法穿过每一个点的曲线。这个时候的拟合度固然很高，但是却让模型变得越发不灵活。如果用在测试数据上，那么曲线比起原先的直线就**更难拟合新的数据**，这就是Overfitting的根本原因了。

- 在分类问题上的过拟合主要体现在曲线完美区分所有的数据点（下图圆点），这个时候加入新的数据（下图十字）后发现曲线很难将他们完全区隔开来，这种模型不是我们想要获得的。


那么既然过拟合会对模型的预测带来影响，要避免它的发生我们又应该怎么做呢？

缓解Overfitting的方式有这么几种：
- 首先就是**增加**数据量


随着数据量的增加原先过拟合的曲线也会慢慢变得**平滑**起来，能够覆盖的范围就变大了。


- 其次就是利用正规化（Regularization）

主要用于解决机器学习过拟合的正规化方法包括了 **L1** 和 **L2** 正规化。

针对机器学习，我们之前将这个过程简化成：
$$
y = Wx
$$
而其中的 **W** 就是我们模型所要学习的参数，过拟合的出现就是模型对于 W 的值进行了太大幅度的调整。为了避免这个问题，我们会对这个变化进行一个惩罚，也就是约束的机制。原始的误差**cost**为：
$$
cost = (Wx - real y)^2
$$
如果 W 变化太大，我们就让cost也跟着变大，也就是 L1 正规化：
$$
cost = (Wx - real y)^2 + abs(W)
$$
L2 正规化和L1类似，只是在惩罚项的不同：
$$
cost = (Wx - real y)^2 + (W)^2
$$
用这些方法我们就可以保证得到的模型曲线不会因为数据的关系而变得那么扭曲。

- 最后是一种经常用在神经网络训练过程中的方式，叫做Dropout Regularization。


在训练过程中，我们选择每次都忽略掉一些神经网络的神经元（Neuron）来使得我们的结果不会每次都过分依赖所有的数据信息，这样训练出来的模型就不容易出现Overfitting的情况。


# L1 / L2正规化
之前提到了过拟合的问题会对模型的预测造成影响，模型往往会通过使用更精密的参数（指数更高的项）来拟合数据。而这些参数的数据虽然能够让模型更好地贴近测试数据，但是却无法灵活地反应测试数据以外的其他数据。


- 图中比起红色的曲线，我们更希望通过蓝线来概括回归的特性。为了能够让模型不会学的那么“完美”，我们就会选择使用L1、L2正规化来约束神经网络参数的更新。

- 训练的过程中我们利用反向传递的误差来调整参数，而误差的值反应为：

$$
Cost(\theta) = [Y\theta(x) - Y] ^ 2
$$

- L1、L2正规化就是在这个误差的情况下多加上了一个误差，也称作**对真实结果的惩罚:**

$$
Cost(\theta) = [Y\theta(x) - Y] ^ 2 + [\theta1 ^ 2 + \theta2 ^ 2 + ...]
$$

或

$$
Cost(\theta) = [Y\theta(x) - Y] ^ 2 + [|\theta1| + |\theta2| + ...]
$$

通俗的来说现在我们的误差不再是我们理解中的结果和真实值得差距了，还包括了**新的误差项**，也就是那些用来拟合的参数所拥有的**权重大小**。如果是对平方项的惩罚就是L2正规化，如果是绝对值则是L1正规化。

- 那么这些惩罚又能对结果产生怎么样的影响呢？以L2正规化为例：


- 在训练过程中，通过减小误差来优化我们的神经网络，而其中**非线性越强（指数越大）的参数**往往会修改的越多。因为曲折的线条往往才是分离局部误差的关键，这个时候非线性强的项次就会凸现出来。而误差方程中的惩罚项此时就会对这个情况作出反击。在它看来，所有的指数项共同组成了一个团队，如果光是依靠那些能力强的参数改变效能是十分危险的，如果它们做错了，那么结果可能会非常糟糕。因此惩罚就是一个**限制两极分化**的最好途径。

- 在抑制过拟合的情况下，L1、L2正规化的优劣也各有不同：


- 图中是我们模型的试图，假设此时只有横纵坐标两个输入特征，而蓝线表示我们学习的梯度曲线（等高线）。越靠近中心越是拟合原来的结果，误差就越小。而正规化的**惩罚项**就是图中粉色线条表示的区域，平方表示圆，而绝对值表示直线。这个时候模型为了保证两边的误差最小，那么就是求解**两个曲面的交点位置**。这样一来模型就不会一直向着蓝线梯度的中心点直奔而去了。

- 不难看出，使用L1正规化的时候，我们很可能得到的结果是坐落在某一个坐标轴上，此时其他坐标的特征就消失了。因此我们可以利用这一点来选择**对结果贡献度最大的特征**。


- 但是L1的结果相对L2正规化而言较不稳定。如上图所示，我们训练的过程中梯度的变化时常发生，这个时候L1正规化可能会存在**不止一个**相对距离最短（也就是误差最小）的点。这也侧面说明了L1正规化的优化不稳定的问题。

- 为了控制正规化的强度会加入一些限制参数来平衡这个惩罚机制的强弱。

$$
Cost(\theta) = [Y\theta(x) - Y] ^ 2 + \lambda * \Sigma\theta i ^ p
$$

- 我们会利用Cross Validation的方式来训练和选取最佳的参数，从而得到更好的正规化结果。

# 如何加速神经网络
不难想象，越是复杂的神经网络结构和越大的数据量，就会让神经网络的训练过程花费更多的时间。原因是计算量和复杂度太高了，可是在解决一些复杂问题时，我们所需要的结构恰恰又是以这样的形式出现，因此我们就需要一些特殊的方法来让神经网络的训练得到 **优化和提升**。

最基础的方法叫做SGD（Stochastic Gradient Descent）


- 未经SGD优化过神经网络训练通常是把整个资料集重复不断地全部喂给网络训练，这样在每次训练中消耗的资源会很大。通过SGD的优化后我们选择将整个资料集分成几个部分，一次将资料的一部分放入神经网络进行训练。虽然这样无法反应整体的资料特性，但是却能加速训练过程，同时保有相当高的准确率。


除了SGD以外，还有一些神经网络的优化方式能够通过优化神经网络的参数，从而达到加速训练的效果。

- 传统的参数更新方法是利用误差的反向传递，让参数的误差值乘上一个学习效率来进行更新的：

$$
W += -Learning\ rate * dx
$$

而这种方法会让收敛的过程曲折无比，就像是一个喝醉的人摇摇晃晃地行走一般，在到达目的地的过程中往往需要走许多弯路。


- 为了防止这种不必要的更新误差，我们会选择使用 **动量（Momentum）** 的形式来优化误差更新方法。

$$
m = b1 * m - Learning\ rate * dx
$$

$$
W += m
$$

- 动量的使用就仿佛给这个误差一个 **向下冲的初始速度**，让他在前进的时候有一个**惯性**的作用。打个比方也就是原先喝醉酒的人走到了一个下坡，他就会改变摇晃的行走方式，转而变成拥有向下冲的一个趋势。


- 与动量（Momentum）类似的优化方式还包括 **AdaGrad**，这种优化的方式是通过给予参数优化一个限制，让他在学习的过程中因为走弯路而受到一定的惩罚，从而减少这种行为的发生。

$$
v += dx ^ 2
$$

$$
W += {-Learning\ rate * dx \over \sqrt{v}}
$$

- AdaGrad的形式就仿佛给喝醉酒的人一双鞋子，在他摇晃前行的过程中由于鞋子的摩擦而脚疼，从而让他避开这种行走方式，转而走直线。

那么不妨试想一下如果将动量和AdaGrad两者**结合**起来，效果是不是会更好呢？的确，结合了两者的方法被称为 **RMSProp**。

- RMSProp结合了两者的优势，从而共同优化神经网络的参数计算：

$$
v = b1 * v + (1 - b1) * dx ^ 2
$$

$$
W += {-Learning\ rate * dx \over \sqrt{v}}
$$

- 而在RMSProp保留两者的有点过程中，神经网络由于动量的加速和AdaGrad的惩罚限制，变得能够走出较为理想的直线了。但是可能不难发现，在结合两个优化形式的过程中，RMSProp似乎并没有完全地将二者进行合并，从公式中可以看出，它似乎抛弃了重复的学习更新作用项 **dx** 在m上的作用。

而 **Adam** 的优化方式则完全融合了动量（Momentum）和AdaGrad的数学形式，将他们完全融入神经网络的训练优化参数的过程中来。

- Adam的参数学习率公式如下：

$$
m = b1 * m + (1 - b1) * dx
$$

$$
v = b2 * v + (1 - b2) * dx ^ 2
$$

$$
W += {- Learning\ rate * m \over \sqrt{v}}
$$

- 就这样，在计算m时将动量优化考虑进去，在计算v时将AdaGrad优化考虑进去，而在最后计算参数的时候将m和v一起考虑进去，这样就能将两者完全结合近神经网络的优化过程中了。

事实证明在大多数神经网络的训练过程中，**Adam Optimizer** 都能让网络迅速收敛，达到目标。

# 如何处理不均衡数据
如果在分类问题中，我们可能会遇到这样的情况：绝大多数的数据Label都偏向于其中的一种类别，而另外一种或是多种类别的成员数量则远远小于它。这样的数据就是我们说的**不均衡**的数据了。

用不均衡数据训练出来的模型思考模式很简单，永远都是猜多的那一方正确几率比较高，久而久之机器就学乖了，总是预测多数派的情况，这样的训练结果往往不是我们希望看到的。


那么面对这样的数据要如何训练呢？

- 第一种方式是对数据进行分层统计：一般情况下神经网络的训练集分布多为均匀分布，但是也可能存在一些特例，像是一开始比例不均匀，一边很大而另一边则很小的情况。这时候一开始的训练结果往往就会是我们说的不均衡情况，但是如果我们能够找到后阶段的数据集刚好相反的分布，那么就会让我们模型慢慢回归正常的预测模式。也就是所谓的以长远的目光看待数据。

- 第二种方式是改变评估的方式：通常我们会用到的评估数据模型的参数有 **准确率（Accuracy）** 和 **误差（Cost）**，但是这些评判标准换到了一个不均衡的数据中来看就显得不那么重要（因为大多数情况都是正确的，而且误差几乎为0）。因此我们选择更换我们的评估模式，改成使用Confusion Matrix来计算 **精确率（Precision）** 和 **召回率（Recall）** ，然后再利用这两者计算出 **F1 Score（F-score）**。

以一个例子来说，假定我们的正类有10个，负类只有4个，此时我们的预测结果为10个正类被判断为10个正类，4个负类被判断为2个正类和2个负类。那么通过Confusion Matrix我们可以计算出TP（正类别猜正类别）、FP（负类别却猜是正类别）、TN、FN四个值。TP = 10，FP = 2，TN = 2，FN = 0;这时候的：

$$
Precision = {TP \over {TP + FP}} = 0.833
$$

$$
Recall = {TP \over {TP + FN}} = 1
$$

因此F1 score可以表示成：

$$
F1 = {2Precision * Recall \over {Precision + Recall}} = 90.9\%
$$

- 第三种方式就是重新组合数据，让数据保持均衡分布。例如砍掉一些数量较多的资料，让二者的数量保持在一个稳定的比例上，或者利用复制和组合的方式增加少数类别的资料数量，使他们比例重新稳定。

- 第四种方式是使用其他的机器学习方法：


在面对不均衡的数据时，神经网络通常是束手无策的，而相比而言一些传统的机器学习算法则能够不受资料集的影响，从而做出正确的判断，比如决策树（Decision Tree）。由于在决策的过程中依赖的是输入数据的特性而非分布情况，因此决策树能够准确地对资料做出分类判断。

- 最后的方式是改变传统的算法：


传统的激活函数算法有一个比较平衡的门槛值作为分类的区隔条件。例如sigmoid函数会以x = 0作为分界线，左边的分布为Label1，而右边的分布则为Label2。但是由于此时资料分布不均衡的情况下，导致坐落在右边的几率大大升高。那么我们就会对这个门槛值进行一个调整：


如图所示，增大门槛值的x坐标，让他只有在**极端条件**（Y十分接近1）的时候才会判定为右边的分类结果（也就是概率较大的Label）。这样我们就能够比较完美地对预测进行一个权衡。

# 强化学习（Reinforcement Learning）

## 什么是强化学习
强化学习是一种让计算机自我学习的算法总结，是让计算机通过自己对环境的不断尝试和探索自我修正并适应的一个过程。有些时候（尤其是在复杂环境中）这样的学习方式比起人为的干预来得更为有效。

那么强化学习又是如何进行的呢？

- 原来在计算机学习的过程中也需要以为好的导师。然而这位导师不会手把手告诉计算机应该如何行动，他的存在只是为计算机尝试的每一个行为进行**打分（评价好坏）**。因此计算机只需要记住那些能够得到较高分数的行为序列就能够在环境中更好地生存下去。

- 换句话说，强化学习就好比是机器自己在环境中手无寸铁地摸索，然后收集信息进行总结，最后得出结论并自我更新的过程。而这些在尝试中得到的信息就会成为我们所谓的监督式学习的数据了（Data & Labels）。

## 强化学习的应用
- `Alpha Go`
- `Video Game`
- `Image Recognition`
- `Chatbot`
- `Robot Controller`

## 强化学习常见算法
- 通过价值（Reward）选择行为：

- `Q Learning`
- `Sarsa`
- `Deep Q Network`

- 直接选择行为：

- `Policy Gradients`

- 自我假象环境并从中学习行为：

- `Model based RL`

### Q Learning
我们在现实中的行为都会有一个标准的规范，例如：父母常说的不写完作业就不能看电视。

Q Learning的方式和决策树（Decision Tree）类似，都是在一个特定的情形下对不同的决策进行概率的计算，然后继续延伸到下一个分支。每一个时刻的模型都可以用time state machine来表示。

- 以上面的例子来说，假设现在处于写作业的状态，这个时候我们的环境告诉我们可以选择的行为是：1、继续写作业 2、去看电视。这个时候因为模型从未尝试过任何一个选择，它可能会选择看电视，然后继续看电视。就这样让状态一直走下去，直到被父母责骂后，环境就会反馈一个**负面的分数**（也就是被惩罚）。这个时候模型深刻理解了这一系列的动作产生的后果是让自己被环境淘汰，因而它会极力去改变这样的结果。


- Q Learning通过一个数据表（Table）来保存每一个state下获得的**价值分数**，而这些分数会随着每一次环境反馈的R（Reward）而做出改变。此时我处在写作业的state，而经过刚才的经验我得知了写作业比看电视带来的潜在收益更大一些，而此时Q表中记录的就是两个选择所带来的价值分数了，显然（S1，a1）小于（S2，a2），因此我决定选择写作业。一次迭代循环也就构成了Q Learning的学习过程。


- 了解了正向的决策过程，那么Q Learning的Table又是如何更新的呢？


- 学习过程最开始的时候，我们会对Q表进行一个初始化，对每一个状态下的所有行为进行一个估计的价值分数。而此时状态为S1的时候，我们通过初始化的价值分数进行第一步行为的决策，然后到达S2状态。此时我们需要**通过S2的状态好坏来给予S1的行为一个反馈**，此时我们会假象自己选择了S2的不同行为，并得到了相应的奖励R。这个时候我们就能够通过：

$$
Real(S1, a2) = R + \gamma * max(S2)
$$

- 来得到S1在环境反馈后真实的价值分数，这个时候就能够通过计算误差：

$$
Cost = Real(S1, a2) - Estimate(S1, a2)
$$

- 然后利用类似于Back-Propagation的方式将误差传递回去，进而利用学习效率更新原有的价值分数。

**Tips**：如果此时的S2并不是最终的结果，而且使用的Q Learning由限定为回合更新的话，那么此时的R并不会在这个时刻体现出来。因此S1更新所需要的Real（S1，a2）会来自之后所有state的结果总和，也就是一个**迭代**的过程。


以上是Q Learning的算法，可以看出Q Learning的神奇之处在于它将当前获得的奖励和下一步行为（也可以理解为衰减）的最大估计作为当前的现实。

公式中的参数：

- ε-greedy是一个调变参数，例如当ε = 0.9时，我们就会有90%的概率根据Q表的最佳解法进行行为选择；而10%的概率会随机选择行为。这样能让模型在拟合的同时还**不忘探索更好的方法**。

- α是一个学习效率，介于0和1之间，能够调控当下对于误差的学习率。

- γ则是对未来奖励的一个衰减值。假设我们的Q表分成很多个States，那么从第一个State开始就会累积今后的Reward值：

$$
Q(S1) = r2 + γQ(S2) = r2 + γ[r3 + Q(S3)] = ... = r2 + γ*r3 + γ^2r4 + γ^3r5+...
$$

就如下图所示:


因为γ是一个介于0和1的值，那么不妨想象一下这个时候的γ = 1，此时所有的r都被保留了下来，因此我们的模型就会考虑到当下行为对所有未来的状态所获得的奖励。另外如果γ = 0时，此时只有r2还存在，我们的模型就只考虑到下一步行为对此刻造成的奖励而已。以此类推，γ < 1可以得知越往后的奖励对当下的行为决定得越浅，因此γ也被称为奖励的**衰减值**。

### Sarsa
强化学习中的Sarsa和Q Learning十分相近。Sarsa也是通过Q Table中的值来对下一步的行为做出估计的，数值越大行为的可能性就越大，Sarsa也是通过这种方式来从环境中获得Rewards的。与Q Learning不同之处在于它们对模型的**更新方式**。


- 与Q Learning不同的是，Sarsa在Q现实的计算过程中，不是通过**潜在收益**最大的奖励方式而选择行为的，而是基于**当下最优条件**来选择行为（去除max运算）。


- 从算法中可以看出除了去除了max的估计运算外，Sarsa和Q Learning几乎没有差别。而就是因为Sarsa这种 **“说到做到”** 的特点，它也被称为**On-Policy（在线学习）**；而Q Learning则被称为**Off-Policy（离线学习）**。


- 有了MaxQ的运算辅助，Q Learning会根据最终奖励回传的潜在Rewards来估计当前的结果好坏，所以即使当前行为的分数是最高的，但是考虑到了潜在奖励的关系，模型可能还是会放弃选择该行为。而Sarsa相反则永远都是选择当前分数最高的行为来作为下一次的选择，进而一步步逼近结果。这样看来Q Learning在学习的过程中仍会尝试一些相对危险但是它认为可行的方法，因为它想要得到的永远是**最佳解**，而Sarsa则是尽可能地回避一切风险**稳步求胜**。

### Sarsa(λ)
按照对模型的更新方式可以分为 **单步更新** 和 **回合更新**。而传统的Sarsa属于单步更新的模式，也就是只有得到奖励的那一次更新能够得到来自当前奖励的Reward，然后更新最后一个步骤，以此类推慢慢往前移动。显然这样的更新是很**没有效率**的。


如果选择回合更新的方式，那么在获得奖励之后，先前所有的决策都会得到更新。乍一看这样的模型似乎更符合我们的需要，但是事实真是如此吗？


- 有些时候我们的学习并不是完全朝着最终的目标笔直前行的，图中难免会走一些**弯路**，而这些不必要的行为如果也能够得到奖励，那么就不是我们所期望的结果了。

- 这个时候就需要使用Sarsa(λ)来帮助模型克服这样的问题了。Sarsa(λ)中的λ参数可以看做是一个反馈的衰减系数，和Sarsa公式中的γ差不多，能够根据更新的回合动态调整奖励的分配。


- 当λ = 0时模型为单步更新，也就是所有的奖励都反馈在了最后一次的行为上。
- 当λ = 1时模型为回合更新，也就是奖励反馈在了途中的所有行为上，并且具有相同的权重分配。
- 而当λ介于0和1之间时，也就是我们的Sarsa(λ)的实现了。它能够以λ系数作为一个衰减，将**靠近结果的行为定义成对结果越重要的部分**，而越远离的行为则作用较小。按照这样的思路**从奖励倒推回起点**的更新方式显得更为的科学。

### Deep Q Network（DQN）
DQN的结构从名字来看就能够推测出个大概，它就是在原有的Neural Network的基础上加上了Q Learning的部分。之所以会有DQN的出现，是因为传统的Q Learning维护表格的方式存在一些瓶颈。即当我们决策的行为次数多到一定的程度，就很难使用Table来记录，就比如围棋（GO）。

- 复杂的决策行为虽然无法使用Table来记录所有的可能性，却并不是不能解决的。在Deep Learning中的神经网络结构就能够很好地解决这个问题。


- 如果能够通过状态来即时预测每一个对应行为的价值分数，那么我们就不需要维护所谓的Q Table了。而DQN正是利用了这样的方法，通过将当前状态和对应的行为输入神经网络，让网络结构分析后得到相应的行为（类似分类）。这样的话我们**只需要维护一个网络结构**就能够解决所有的决策问题，最后再用强化学习的方法来选择动作。

那么我们又是如何来训练我们的神经网络结构从而拟合强化学习的模型呢？


- 通过网络预测的结果和Q Learning通过Reward得出的最终结果的误差值可以用来反向传递给Neural Network模型。

当然即使是这样，我们也只是在大量数据中重现了Q Leanring的性能，那么DQN究竟有哪些**过人之处**呢？

#### Experience Replay
根据强化学习的更新模式分为On-Policy和Off-Policy两种方式。而Q Learing就属于Off-Policy的一种，除了敢于尝试最佳化意外，它还能够学习**自己实践**的经历，也可以学习**别人记录下来的经历**，甚至是**过去**的经验。而这也是DQN的运用之一：

- DQN有个记忆库用来记录之前的经历，也可以加入其它网络尝试的经历。在训练的过程中，我们可以随机抽取一些记忆库中的经历来**重新学习（复习）** ，通过这样抽样的离散型**打乱了经历的相关性**，也让网络的**更新更有效率**。

#### Fixed Q-target
Fixed Q-target也是一种打乱经历相关性的方法。每次训练过程中在得到Reward计算Q现实的 `Q'` 和 预测行为的 `Q` 估计都是使用同一个神经网络预测得到的，这样一来网络的训练数据间就拥有了一定程度的**相关性**。


Fixed Q-target的做法是用一个结构相同，但是参数是**几个训练流程前**的数据的神经网络来进行Q现实的预测。这么做的好处是利用一个较慢的网络来进行现实的预测，从而打破数据间的依赖，让更新更有效率。同时放慢的现实估计能够根据几轮的观察来评估预测的结果，提高了可调性范围，也让Q估计的模型看得更远（更有远见）。

### Policy Gradient
如果按照对行为的选择方式，强化学习可以分为**基于价值**和**基于概率**两种方式。之前的Q Learning、Sarsa和DQN都是基于计算行为的价值来预测下一步的动作，但是如果动作是一个**大范围的连续区域**，那么通过价值的计算来选择动作就变得十分复杂而且难以实现（需要维护大量的价值和行为的匹配关系）。因此Policy Gradient的方式解决了这个问题，它不再是通过计算价值来选择行为，而是通过预测行为的**概率**来直接输出对应的动作，而这点与神经网络的行为十分类似。

我们都知道神经网络的训练是通过反向传递误差来修正隐藏层的权重值得。那么如果没有了价值的计算，我们的误差又是什么呢？

- 答案是**没有误差**。在训练Policy Gradient的神经网络时，我们是直接通过概率选择行为的，因此我们没有一个明确的值表示行为的对于错。


- 如果以一个例子来看：输出的结果是所有行为的softmax vector——**[0.1, 0.2, 0.1, 0.4, 0.2]**，那么很显然下一次选择的行为很可能就会是第4个动作（不是绝对的）。这样一来通过动作获得的奖励（Reward），我们就能够判断行为发生的可靠性，也就是好坏。有了这个标准，我们就会在下一次预测的时候 **改变这个行为出现的概率** 。如果是好的行为，那么下一次输出就可能变成 **[0.1, 0.1, 0.1, 0.5, 0.2]** ；反之增加的幅度就会被衰减。

### Actor-Critic
Actor-Critic的强化学习方式可以根据名称分为**两个部分**，分别时Actor和Critic。两部分分别结合了Policy Gradient和Value Based RL的优势之处。


- Actor部分是采用了Policy Gradient对于动作的选择优势，因为是一个基于概率的模型，因此能够输出一个连续范围内的行为。

- Critic部分是采用了Q Learning以及其他传统的Value-Based RL的更新方式，通过单步更新的方式让模型的学习更有效率。


- Actor-Critic的方式和GAN神经网络十分相似，它是通过Actor部分的Policy Gradient神经网络来生成动作（相当与Generator），而利用Critic来判断行为的好坏，进而做出反馈（相当于Discriminator）。

- Critic通过自己的神经网络学习环境、行为和Reward之间的关系（通过价值），然后对Actor每一步产生的行为做出**即时的判断**，进而通过模型学习到的行为潜在价值来单步更新Actor网络。


- 当然事物总有它的利与弊，Actor-Critic虽然能够解决Policy Gradient的单步更新问题，却无法很好的改善行为的**连续性判断**。Actor-Critic的两个神经网络都是基于一个连续动作的每一步进行更新（单步），这样的话就**无法掌控行为之间的潜在关系**，模型看待问题就显得**相对片面**，甚至学不到东西。

为此，Google Deepmind团队通过将Actor-Critic和DQN的精髓结合起来，开发了全新的 **Deep Deterministic Policy Gradient（DDPG）** 成功解决了这个问题。

### Deep Deterministic Policy Gradient(DDPG)
从Actor-Critic延伸而来的DDPG强化学习算法，能够让强化学习在连续的行为上得到更好的学习效果。

我们可以将Deep Deterministic Policy Gradient结构分成三个部分：Deep + Deterministic + Policy Gradient。

- **Deep**：DDPG利用了DQN中**Experience Replay**和**Fixed Q-target**的概念，通过随机筛选的方式新型重复学习以及利用两个神经网络分别估计Q现实和Q估计。将传统的Value Based RL提升到了DQN的效率范围。

- **Deterministic**：传统的Policy Gradient结构输出的结果为一个连续的动作区间（例如 **[0.1, 0.1, 0.6...]**），然后随机选择一个作为动作的输出。而Deterministic则是鄙弃了这种繁琐的输出方式，转而只输出决策完的单一动作，这样对于模型的更新更有效率。

- **DDPG**：在结合了前两者的功能之后，Policy Gradient在连续行为的处理上就能更加得心应手了：


- 图中的Actor负责通过一个动作估计网络来预测当前的行为，并通过Deterministic输出一个特定的行为。同理根据DQN的思想另一个预测动作现实的网络也会根据较早期的输出一个真实的行为。

- 另一方面，对于Critic而言也是使用两个神经网络作为现实和估计的预测结构。但是不同的是，此时的输入除了从环境中得到的观测值意外，还包括了从Actor得到的**上一个时间点输出的行为**。咦？这种思想好像很眼熟？没错，这就和我们熟悉的RNN（Recurrent Neural Network）思想类似。都是通过**将上一个状态值保留给下一个时刻进行学习的方法**。有了这个结构的辅助，在训练连续行为的时候就能够很好地把握行为的**相关性**了。

### Asynchronous Advantage Actor-Critic(A3C)
A3C是一种用来提升强化学习效率的一种算法，它的精髓是能够让强化学习的模型通过分裂从而在同一个时刻学习不同的经验，然后总结之后得到完整的学习结果，这也是其中Asynchronous的含义。

假设现在为了获得Reward我们有16中不同的行为方式能够选择，那么不妨想想我们能够将这16中行为分成4*4的状态**分散**放置在一个同样的环境中。让它们自我学习，最后将结果也就是学习的经验汇总到一个统一的网络中进行更新，这样就能大大地提升学习效率了。


如果计算机拥有多核心处理特性，那么A3C绝对是提升训练效率的一个方式。类似于多线程的概念，能够在同一时刻平行地处理多种可能性，而A3C的强化学习模组使用的是Actor-Critic，能够在异步有效更新Actor的行为状态，然后**汇总**到统一的模型中，模型会总结完所有异步状态的结果，整合之后再**将这个秘籍（加总的结果）传递给每一个子模型（一个类似Map-Reduce的概念）**。

### Why AlphaGo Zero so powerful
2017年10月19日Google Deep Mind发布了新一轮的围棋人工智能——AplhaGo Zero。那么这个技术在机器学习方面又是利用了什么样的方式从而在策略上战胜人类呢？答案很简单，就是**多元计划**。

要知道围棋的走法如果全部罗列出来可谓是比天上的星星还要多，计算机不可能在每一步做不同的尝试。因此它利用了 **蒙特卡洛检索（Monte Carlo Tree Search）** 的方式，对未来的决策进行探索。而这种方式最早来自于IBM开发的国际象棋AI Deep Blue的决策方式。


但是在围棋方面的决策复杂度比起象棋要大得多，因此Alpha Go放弃了在检索方面的广度，转而进行深度检索。


- Alpha Go在传统的Monte Carlo检索树的基础上结合了强化学习网络对每一步的决策进行价值评估，从而让深度的尝试更加精确和有效率。


旧版本的Alpha Go利用了两个深度神经网络结构来辅助决策的过程。其中一个属于决策分类，每次输出一个概率值，用于评估当下最可能的Action。而另一个网络则是用于评估这个决策对于总体环境的一个价值。


传统的Alpha Go和人类的思维模式类似，利用学习大量的前人经验（棋谱）来提升自己的能力，因此很难跳脱人类下棋的一些套路和定式。而Alpha Go Zero在这一点上则完全不同，它仅仅通过自我学习来理解和强化自己对于围棋的认知，从而跳脱人的思维，真正意义上以机器的角度进行学习。打破了定式的枷锁，模型就能自我总结出人们难以发现并且有效的技巧，这也是战胜人类的关键（在认知上超越人类）。


- 此外，Alpha Go Zero仅采用了一个神经网络结构，这样能够充分有效地利用资源，在决策的同时对当下的决策进行价值评估，并通过reward结果反馈给模型进行更新。

Alpha Go Zero的出现和它产生的影响不仅仅是对于围棋AI的一个重要突破，更重要的是它开创了AI的一个新思路，利用无监督的方式让机器自己学习一个Domain的Knowledge是未来几乎所有AI领域的研究所要解决的问题。

## 如何根据问题选择强化学习方法
我们可以通过分类的方式来区分不同的强化学习。

### 对环境的反馈

通过**对环境的反馈**可以分为两大类：

- **理解环境（Model-Based RL）**
- **不理解环境（Model-Free RL）**

如果我们的模型从一开始就没有打算去理解环境的本质，而只是一味地依靠尝试从环境中获得反馈来得以生存。那么就属于不理解环境的类型；相反，如果模型从一开始就试图理解环境的本质，那么就能自行对环境进行建模。


- 试想一下，如果只是单纯地依靠环境给予的反馈来决定下一步的行为，那么所有的行为所造成的后果就会直接作用在模型本身。如果所采取的行为**一直没有办法适应环境**，那么模型就会一步步走向崩溃。

- 而如果是能够理解环境的强化学习模型（Model-Based），它能够实现根据了解到的环境数据对整个环境系统新型建模（虚拟环境）。然后在虚拟的环境中进行训练，最后模型不但能够在虚拟环境中适应，还能够迁移到真实的环境中去。

除了能够建立虚拟环境来模拟学习过程以外，Model-Based RL还有一个优点是Model-Free RL所羡慕的，那就是**想象力**。


- Model-Free RL模型只能够一步一步按照环境给予的参数来思考下一步的动作，无法跳脱反馈信息的控制。因而只能**按部就班**循序渐进。而Model-Based RL由于已经理解了环境的本质，因此除了能够接受来自环境的反馈以外，还能够通过想象来同时**预测多种行为的可能后果**，最后选择一个模型觉得最佳的结果。这样就不必受到反馈信息的牵制了。

- 想象一下如果我们想要让一只猫到达一个特定的目标，那么我们可能需要在路线上摆好食物来引诱它。而Model-Free RL的方式就是相当于在每一步朝着正确目标的方向上摆上和步数相同的事物，这样就能够一步步**逼近最终目标**。但是如果是Model-Based RL的做法，它可能不会完全按照事物摆设的路线去逼近最终目标，而是不断地**尝试其他新的可能性**，最终找到一个最佳（距离最短）的路径作为模型的训练目标。这也是为什么**Alpha Go**能够下出人们所无法理解的路数了，因为在它看来目标是获胜，而为了达到这个目标可能有更加简单的方式。

### 对行为的选择方式

通过**对行为的选择方式**也可以分为两大类：

- **基于概率（Policy-Based RL）**
- **基于价值（Value-Based RL）**

基于概率的方法输出的值是所有动作的概率，然后根据概率做出行动，因此比较**灵活**。所有的行动都有可能被选到，只是概率大的动作被选中的情况比较多罢了。但是基于价值的方式则不痛，它的输出是所有动作对结果做出的贡献度（也就是价值）。这样的话只有**价值最高**的那个动作才会被选中。


- 我们现实环境中的决策往往不会是单一的一个动作，而是一连串连续的动作（Sequential Action），下一个动作的行为是基于上一个动作的结果而决定的。这样的情况下就不能使用基于价值的方式了，因为没有办法依靠单次的行为给出准确的价值分数。而基于概率的方式就变得尤为重要，因为我们可以使用**条件概率分布**来表示现在的动作被选中的几率大小。


那么基于概率和基于价值的方式又有哪些强化学习的算法呢？

- 基于概率的方式有：

- `Policy Gradients`

- 基于价值的方式有：

- `Q Learning`
- `Sarsa`

- 还有结合两者优势而得到的方法：

- `Actor-Critic`


- Actor-Critic顾名思义分为**两个部分**，Actor的部分通过概率计算做出下一步动作，而Critic根据做出的动作对结果的贡献评估价值分数。如此一来就把Policy-based和Value-based的功能整合在了一起，加速了学习过程。

### 对模型的更新方式

通过**对模型的更新方式**也可以分为两大类：

- **回合更新（Monte-Carlo update）**
- **单步更新（Temporal-Difference update）**

回合更新指的是当学习开始到达到目的的一**整个过程**结束后才开始更新我们模型的行为准则；而单步更新则是学习的过程中根据不同的决策**动态即时地**更新模型的参数。


回合更新的强化学习方法包括：

- `最原始的Policy Gradients`
- `Monte-Carlo Learning`

单步更新的方法则有：

- `Q Learning`
- `Sarsa`
- `升级版的Policy Gradients`

比起回合更新而言，单步更新更有效率，因此普遍的强化学习都是使用单步更新的方式。

### 学习的模式

通过**模型学习的不同模式**也可以分为两大类：

- **在线学习（On-Policy）**
- **离线学习（Off-Policy）**

在线学习指的是必须由待训练的模型**自行进入环境学习**，所有的决策都是由模型自己决定的。而离线学习则是可以选择模型自己进入环境学习，亦或者是通过**总结别人的经验来学习**。同时离线学习也**不需要强制使学习和更新同步**，换句话说就是可以先在环境中尝试各种行为，记录下环境的反馈，到了**适当的时机（不需要环境）**在通过这些数据更新自己的模型。


比较典型的在线学习方式有：

- `Sarsa`
- `Sarsa(λ)`

而典型的离线学习方法有:

- `Q Learning`
- `Deep Q Network`

# 进化算法（Evolutionary Algorithms）
物竞天择，适者生存是大自然永恒的规律，这些规律引导者人们为了适应环境而不断进化。同样在机器学习的领域中，我们是否也能够让计算机依照环境的不同而变异来适应环境呢？

## 遗传算法（Genetic Algorithm）
遗传算法是进化理论中的重要环节之一，其核心思想来源于生物学的进化论。模型算法的训练过程中，往往会尝试不同的参数选择来演化下一代的模型。而这个过程势必会产生新的**物种**，如果该新生代能够更好地适应环境，那么我们就有理由相信它能够更好地繁衍并被保留下来。


模型建构过程中，计算机通过0和1将特征信息编码成为机器能够表示和存取的代码格式。有了这种让计算机理解遗传DNA的方式，我们就能够通过迁移学习的方式将生物科学中传统的DNA遗传理论转换到计算机模型算法的实现过程中来了。


- 假设现在模型中有一组父母的特征序列，他们会根据环境训练出许许多多不同的儿子序列，而这些儿子序列中融合了父母两代的遗传信息。


- 而在训练的过程中，遗传信息往往会因为环境的不同而发生变化，而这些变化也会体现在编码上，只要修改了其中一部分特征序列，就会改变整个模型的行为。因此有了这样的机制，我们就能够在机器学习模型的训练中加入遗传理论的特性，尝试生成大量的模型样本，然后根据**适者生存，不适者淘汰**的自然法则来选择最终的模型。

## 进化策略（Evolution Strategy）
进化策略和遗传算法的共同之处在于它们都是通过继承上一代的优势，然后通过局部变异来选择更加适应环境的新生代，不断进化。

遗传算法是通过二进制编码来表示遗传信息的结构，这样在现实生活中的许多问题上是难以直观应用和实现的。因此我们引入进化策略来辅助计算机理解并表示实数形态的遗传特征：


- 假设我们的父母特征信息是一组实数的集合，而这些实数往往可以用来表示例如算法公式的系数部分，从而通过遗传和变异的思维来改变这些实数，达到更新和优化算法的功能。


- 同样在繁衍新生代模型参数的过程中我们同样可以通过交叉配对的方式进行遗传，而新生代的模型同样是由一组实数组成的参数构成的。但是问题来了，面对实数我们应该如何变异呢？传统的二进制通过取not方式来进行的方式似乎不再奏效了。

针对这个问题，首先想到了应该是类似SGD的方式进行局部位移来改变实数了。进化策略中引用了**变异强度**这个变量来表示这个过程的变化率，如果我们将祖先的实数集当成是正态分布的平均值，我们只需要为这个平均值附加一个标准差来进行偏置就能够达到变异的效果了。


- 以8.8的参数为例：假设我们取1作为标准差的值，然后通过在8.8为平均值的正态分布中进行标准差为1的偏置，我们就能够得到一个变异后的新值了。之后只要对所有遗传后的信息做这个步骤，就能够达到变异的效果了。


同样父母样本自身具有的变异强度也能够通过遗传的方式继承给下一代，甚至也能够接受**变异强度自身的变异**，而这些行为也让进化策略在模型更新上更加灵活。


总而言之：进化策略在遗传的过程中总共包含了两部分的信息，其一是记录了实数具体指的**均值信息**，另一个则是记录了变异强度的**标准差信息**。有了这两个信息，我们的新生代模型就能够根据环境的不同而进行不同程度的变异了。

## 神经网络的进化（Neuron-Evolution）
一般的神经网络实质就是一些计算机能够理解和使用的高度集成化的数学模型。数据利用类似电信号的方式正向传播，输出结果，最后根据与真实数据的误差进行反向传递修正误差。而真实的神经网络却没有所谓的反向传递机制，只是透过正向传播的刺激来产生新的神经回路，从而**记忆**这些行为。


之前提到的遗传算法和进化策略都是进化算法的实现方式，但是两者在神经网络的应用上有所不同：

- 遗传算法是利用从父母那里继承下来的神经网络结构经过组合变异得到的，我们将许许多多不同变异结构的神经网络丢到环境中。根据适者生存的法则就能够得到最好的神经网络结构了。

- 而进化策略则是倾向于先固定好神经网络的结构，然后将这些结构的链接权重和以及链接方式加以修改，得到许多新生代的神经网络结构。然后将这些结构同样至于环境中让它们适者生存。最后将环境中的神经网络根据适应程度给予不同的权重组成新的神经网络，这样一来优质的模型链接就会逐渐主宰这个结构。


- 我们知道传统的监督式学习神经网络是利用梯度下降的方式来更新网络参数的，而这比起遗传算法的更新策略更加有效率。原因是梯度下降算法是通过在梯度的方向上进行模型参数的更新，而梯度标记了当前的最优更新方向，只要以梯度躺平的方向前进，模型就能够越来越好。
- 而遗传算法的更新模式则是利用不同的新生代模型产生不同的参数，然后在众多参数中选择最优的参数进行替换。也就是说每一次更新神经网络都需要产生大量的新模型，这一点无疑会加大运算量。


- 尽管如此，遗传算法的更新还是有一些优势所在的，其中重要的一点就是能够防止局部最优的情况。我们知道，利用梯度下降的方式会让神经网络陷入局部最优的情况。而遗传算法由于是在全局情况下随机产生新的模型参数，因此模型的更新不受梯度的影响，能够到达曲线的任何位置。


- 除了监督式神经网络以外，进化算法也可以用在强化学习中。而且研究指出利用进化算法得到的强化学习比起传统的梯度下降的训练方式更加有效率，因为我们可以通过A3C等方式将许多不同种类的模型分配到许多的平行的环境中，从而做到分布式学习的目的。也许当以梯度下降为主的神经网络遇到瓶颈时，基于遗传进化算法的神经网络能够为我们打开另一扇窗。

# KeyWords

###### Tags: `Machine Learning` `Deep Learning` `nn` `GAN`