百面机器学习

一. 数学基础

1. 最大似然估计，最大后验概率、贝叶斯估计

参考： https://blog.csdn.net/bitcarmanlee/article/details/81417151

1.1 最大似然估计（maximum likelihood estimates, MLE）

最大似然估计可以概括为“模型已定，参数未知”
以抛硬币为例，假设抛十次硬币的结果为，七次为正，三次为反，抛硬币行为可以假设服从二项分布，则所求的似然函数为
$f(X,θ)=θ^7(1−θ)^3$
需要注意的是，上面只是个关于θ的函数。而最大似然估计，很明显是要最大化这个函数。
首先我们取对数似然函数，这样更方便后续的数学运算：
$ln(f(X,θ))=ln(θ^7(1−θ)^3)=7ln(θ)+3ln(1−θ)$
对对数似然函数求导：
$ln′(f(X,θ))=7/θ−3/(1−θ)$
令导数为0，最终求得：
$θ=0.7$

1.2 最大后验估计(maximum a posteriori estimation)

上面的最大似然估计MLE其实就是求一组能够使似然函数最大的参数，即
$θML(x)=argmaxθ f(x|θ)$
如果我们把问题稍微弄复杂一点，如果这个参数θ有一个先验概率呢？比如上面的例子中，实际生活经验告诉我们，硬币一般都是均匀的，也就是θ=0.5的概率最大，那么这个参数该怎么估计？
这个时候就用到了我们的最大后验概率MAP。MAP的基础是贝叶斯公式：
$p(θ|x)=p(x|θ)×p(θ)/P(x)$
后验概率分布（正⽐于先验和似然函数的乘积）拥有与先验分布相同的函数形式。这个性质被叫做共轭性（Conjugacy）。共轭先验（conjugate prior）有着很重要的作⽤。它使得后验概率分布的函数形式与先验概率相同，因此使得贝叶斯分析得到了极⼤的简化。例如，二项分布的参数之共轭先验就是我们前面介绍的 Beta 分布。多项式分布的参数之共轭先验则是 Dirichlet 分布，⽽⾼斯分布的均值之共轭先验是另⼀个⾼斯分布。
总的来说，对于给定的概率分布p(X|θ)，我们可以寻求一个与该似然函数p(X|θ)共轭的先验分布p(θ)，如此一来后验分布p(θ|X)就会同先验分布具有相同的函数形式。而且对于任何指数族成员来说，都存在有一个共轭先验。

1. 3 贝叶斯估计

贝叶斯估计是在MAP上做进一步拓展，此时不直接估计参数的值，而是允许参数服从一定概率分布。回忆下贝叶斯公式：
$p(θ|x)=p(x|θ)×p(θ)/P(x)$
现在我们不要求后验概率最大，这个时候就需要求p(X)，即观察到的X的概率。一般来说，用全概率公式可以求p(X)
$p(X)=∫p(X|θ)p(θ)dθ$

1.4 什么时候 MAP 估计与最大似然估计相等？

当先验分布均匀之时，MAP 估计与 MLE 相等。直观讲，它表征了最有可能值的任何先验知识的匮乏。在这一情况中，所有权重分配到似然函数，因此当我们把先验与似然相乘，由此得到的后验极其类似于似然。因此，最大似然方法可被看作一种特殊的 MAP。
如果先验认为这个硬币是概率是均匀分布的，被称为无信息先验( non-informative prior )，通俗的说就是“让数据自己说话”，此时贝叶斯方法等同于频率方法。
随着数据的增加，先验的作用越来越弱，数据的作用越来越强，参数的分布会向着最大似然估计靠拢。而且可以证明，最大后验估计的结果是先验和最大似然估计的凸组合。

百面机器学习：算法工程师带你去面试 ——诸葛越

第一章：特征工程

特征归一化：
将所有特征统一到一个大致相同的数值区间内，使各指标处于同一数据量级。便于进行分析，使得在进行梯度下降法时随机数值的更新速度一致，减少消耗时间。
因此，一般来说，需要
利用梯度下降法的模型通常需要归一化，如线性回归、逻辑回归、SVM、神经网络等；但决策树模型则不需要。
常用归一化方法：线性函数归一化（Min-Max Scaling)
零均值归一化 Z-zero Normalization
将类别型特征转化为数值型特征
方法：one-hot 编码，序号编码（ordinal encoding), 二进制编码（binary encoding)
文本表示模型
Bag of Words, TF-IDF(Term frequency-inverse document frequency), topic model, word embedding
3.1 TF-IDF
衡量单词t对表达语义所起的重要性
TF-IDF (t, d) = TF(t, d) * IDF(t)
IDF(t) = 文章总数/（包含单词t的文章总数+1）
即如果一个单词在很多文章中都出现，则它有很大可能为通用单词，要降低权重
3.2 word2vec
实际为一种浅层的神经网络模型
与主题模型（LDA）的差别：
主题模型是一种基于概率图模型的生成式模型，其似然函数可以写成若干条件概率连乘的形式，其中包含需要推测的隐含遍历（主题）；
word2vec一般表达为神经网络的形式，似然函数定义在网络输出之上。

第二章：模型评估

准确率，精确率precision，召回率recall，均方根误差RMSE
准确率缺陷：当不同类别样本比例不均衡时，占比大的类别往往成为影响准确率的最主要因素；
precision: 分类正确的正样本个数占分类器判定为正样本的比重
recall: 分类正确的正样本个数占实际真样本比重
P-R曲线：横轴为召回率，纵轴为精确率
$F1 = 2*precison*recall /(precision +recall)$
RMSE: 受”离群点“影响
ROC曲线：曲线下的面积AUC，横轴：假阳性率 FPR = FP/N;纵轴真阳性率 TPR=TP/P
其中， FP为负样本N中错标记成正样本的数目， TP为正样本P中分类器预测为正的个数；
AUC量化地反映基于ROC曲线衡量出地\de 模型性能，取值一般在0.5-1之间，越大的话分类性能越好。
ROC曲线与P-R曲线区别：当正负样本分布发生变化时，ROC曲线形状基本保持不变，而P-R曲线形状会发生较剧烈的变化。这个特点让ROC曲线能够尽量降低不同测试集带来的干扰，更加客观地衡量模型本身地性能。因此，在正负样本数量差别很大的领域，ROC曲线能更加稳定，如排序、推荐、广告等领域。反之，P-R曲线能更加直观地反映其性能。
余弦相似度：取值范围[-1, 1]
余弦距离: 1-余弦相似度，取值范围[0, 2]
欧式距离
欧式距离体现数值上的相对差异，而余弦距离体现方向上的相对差异
在机器学习领域，被俗称为距离，却不满足三条距离公理的不仅仅有余弦距离，还有KL散度/相对熵，常用于计算两个分布之间的差异。
交叉检验：
k-fold 交叉验证
超参数调优：网格搜索，随机搜索，贝叶斯优化算法
贝叶斯优化算法：与其他两种算法不同，贝叶斯算法充分利用之前的信息，通过对目标函数形状进行学习，找到使目标函数想全局最优化提升的参数。
首先根据先验分布，假设一个搜索函数；然后每一次采用新的采样点来测试目标函数时，利用这个信息来更新目标函数的先验分布；最后，算法测试根据后验分布给出全局最值最可能出现的位置。
容易陷入局部最优。
过拟合与欠拟合：
过拟合是指模型对于训练数据拟合呈过当地情况，即在训练集上表现很好，但在测试集和新数据上表现较差。
欠拟合指模型在训练和预测时表现都不好。
过拟合解决方法：
1）获得更多数据。（生成式对抗网络？）
2）降低模型复杂度
3）L1， L2正则化
4）集成学习方法，降低单一模型的过拟合风险
欠拟合解法方法：
1）添加新特征，GBDT(gradient boosting decision tree)
2）提高模型复杂度
3）减小正则化系数u

第三章：经典算法

1. 支撑向量机

在SVM中，若给定训练集中不存在两个点在同一位置，则存在一组参数使得该SVM训练误差为0.
SVM预测公式可写为：
$f(x) = \Sigma_i \alpha _i y^{(i)}K(x^i, x) +b$
其中 $\alpha_i$ 、b, $\lambda$ 高斯和参数为训练样本的参数。
所有样本被正确预测时，训练误差为0.
训练误差为0的SVM分类器存在
即在1.1的基础上，找到一组参数使SVM训练误差为０，且使SVM模型的一个解，满足 $y^i * f(x^i) >= 1$
展开得：
$y^j * f(x^j) = y^j \Sigma_i \alpha_i y^i K(x^i, x^j) = \alpha_j+\Sigma_i\alpha_i y^i K(x^i, x^j), i!=j$
当 $\alpha_j$ 很大， $\lambda$ 很小时，满足条件。
1.3 加入松弛变量得SVM模型训练误差不能达到0.
实际应用中，使用SMO算法训练一个加入松弛变量得线性SVM模型时，优化目标改变，包含 $||w||^2/2$ ，此时，一个带有训练误差，但参数较小得点可能成为最优结果。

2. 逻辑回归

逻辑回归与线性回归最大的区别为，逻辑回归中的因变量是离散的，而线性回归中的因变量是连续的。并且在自变量和超参数确定的i情况下，逻辑回归可以看作广义线性模型在因变量服从二项分布的一个特殊情况；而使用最小二乘法求解线性回归时，可以认为因变量服从正态分布。
相同点：两者都使用了极大似然估计对训练样本进行建模。线性回归使用最小二乘法，实际上是在自变量x和超参数 $\theta$ ，因变量y服从正态分布的假设下，使用极大似然估计的一个化简；而逻辑回归通过对似然函数的学习得到最佳参数。之后两者都使用了梯度下降的方法。

利用逻辑回归处理多分类场景

如果一个样本对应于一个标签，可以假设每个样本属于不同标签的概率服从几何分布，使用softmax regression进行分类，其实质时二分类逻辑回归在多标签分类下的一种拓展。
当存在样本可能属于多个标签时，可以训练k个二分类的逻辑回归分类器。

3. 决策树

ID3：最大信息增益
$g(D, A) = H(D) - H(D|A)$
C4.5: 最大信息增益比
$g_R(D,A) = g(D, A) / H_A(D)$
$H_A(D)$ 称为数据集D关于特征A的取值熵, $H_A(D)=-\Sigma|D_i|/|D| log_2 |D_i|/|D|$
CART：最大基尼系数
与ID3、C4.5不同，CART是一棵二叉树，采用二元切割法，每一步按特征A的取值切成两份。
三者比较：
ID3 倾向于取值较多的特征，因为信息增益反应的是给定条件以后不确定性减少的程度，特征取值越多意味着确定性越高，条件熵越小，信息增益越大。导致模型泛化能力很差；
C4.5通过信息增益比，对取值较多的特征进行一定惩罚，避免过拟合，提高泛化能力。
ID3只能处理离散型变量，而C4.5和CART都可以处理连续型变量；
ID3和C4.5都只能用于分类，CART(classification and regression tree)可用于分类与回归（回归树使用最小平方误差准则）
从实现角度，ID3对样本缺失值敏感，而C4.5和CART都可以对缺失值进行处理；ID3 和C4.5特征不会复用，通过剪枝提高准确度和泛化能力，而CART直接利用所有数据对所有可能的树结构进行对比。
剪枝方法：预剪枝、后剪枝
预剪枝直接、算法简单、效率高，但存在过拟合的风险，以及预剪枝策略的采用需要经验估计
后剪枝泛化能力更强，但时间开销更大
CART剪枝方法CCP（代价复杂剪枝）：从完整决策树T0开始，生成一个字数序列；在子树序列中，根据真实误差选择最佳的决策树。

第四章：降维

1. PCA

什么是主成分？如果找到主成分？求解过程
从最大化方差角度：
主成分可以看成是数据在主轴上投影方差最大得方向。
由方差可以推出目标函数，可以发现需要找的最大方差即为协方差矩阵最大的特征值，最佳投影方向即最大特征值所对应的特征向量。
求解方法：
1）对样本数据进行中心化处理；
2）求样本协方差矩阵；
3）对协方差矩阵进行特征☞分解，将特征值由大到小排列；
4）取特征值前d个特征向量，将样本映射到d维，即为主成分上的投影。
从最小化平方误差角度：
从不同的目标函数出发，得到了与最大化方差相同的求解方法。

2. LDA Linear discrimination analysis 线性判别分析

也成为Fisher LDA，是一种有监督学习方法，经常用于对数据进行降维。
与PCA相比，PCA只考虑数据方差，因此对数据PCA后分类效果很差，而LDA可以将不同类别数据尽可能分开。
Q：对于有类别标签的数据，如果设计目标函数使得降维过程不损失类别信息？如果求解？
A：最大化类间距离，最小化类内距离
对目标函数求导，可以发现最大化的目标对应了一个矩阵的特征值，于是LDA降维变成了一个求矩阵特征向量的问题，J(w)对应了矩阵 ${Sw}^{-1}*Sb$ 最大的特征值，而投影方向就是这个特征值对应的特征向量。
由于 $S_B = (\mu 1 -\mu 2)(\mu 1 -\mu 2)^T$ ，因此S_B*w的方向始终与 $(\mu 1 -\mu 2)$ 一致，只考虑w方向，可以得出 $w = S_w^{-1} (\mu 1 -\mu 2)$ .
因此在LDA中，只需要求样本均值和类内方差，边可以马上得出最佳投影方向。
总结：Fisher LDA 相比PCA更善于对有类别信息的数据进行降维处理，但它对数据的分布做了很强的假设：每个类数据都是高斯分布、每个类的协方差相等··· 总的来说，LDA是一种很有效的降维方法，线性模型对噪声的鲁棒性较好，但由于模型简单，表达能力有一定局限性，可以通过引入核函数扩展LDA方法。

3. 比较PCA与LDA

将LDA推广到多维空间
1）计算数据集中每个类别样本的均值向量 $\mu_j$ ，及总体均值向量 $\mu$ ;
2）计算类内散度矩阵 $S_w$ 、全局散度矩阵 $S_t$ ，并得到类间散度矩阵 $S_b = S_t -S_w$ ;
3）对矩阵 $S_w^{-1}S_b$ 进行特征值分解，将特征值由大到小排列；
4）取特征值前d大的对应特征向量，将样本映射到d维。
区别
两种方法求解过程有很大相似性，但原理有所区别；
从目标上，PCA选择的是投影后数据方差最大的方向，而LDA选择是类内方差小、类间方差大的方向；
从应用角度，无监督学习任务使用PCA，有监督学习任务使用LDA。

第五章：非监督学习

聚类算法：通过多次迭代找到数据的最优分割；
特征变量关联则是利用各种相关性分析方法找到变量之间的关系。

1. k-means

非监督学习算法
迭代时依次通过调整样例所属类别和固定簇中心减小损失函数，最后中心和均值同时收敛。
缺点：受初值和离群点影响每次结果不稳定，结果通常是局部最优解；无法很好解决数据簇分布差别比较大的情况、不太适用于离散分类等；需要人工预先确定K值；
优点：K均值聚类相对可伸缩和高效，计算复杂度O(Nkt)接近线性；局部最优时性能满足要求。
调优：数据归一化；合理选择K值；采用核函数
K均值聚类的迭代算法实际上是一种最大期望算法EM
E: 计算期望
M：最大化

2. 高斯混合模型GMM

同样使用EM算法进行迭代，假设每个簇数据符合高斯分布，由此得到的聚类算法。
相比于K均值聚类的优点：
可以给出一个样本属于某类的概率；
不仅用于聚类，还可以用于概率密度的估计；
生成新的样本点。

3. 自组织映射神经网络

第六章：概率图模型

1. 概率图模型的联合概率分布

概率图：贝叶斯网络（有向图）、马尔可夫网络（无向图）
更详细的说，有朴素贝叶斯模型、最大熵模型、隐马尔可夫模型、条件随机场、主题模型等。
马尔可夫网络联合概率：团、势函数
朴素贝叶斯模型原理：后验概率决定分类结果，盘式记法。
最大熵模型： $H(P) = -\Sigma P(x)logP(x)$
条件熵： $H(P(y|x)) = -\Sigma \tilde{P}(x)P(y|x)logP(y|x)$ ，其中 $\tilde{P}(x)$ 为严格样本在训练数据集上的经验分布。
最大熵模型就是要学习到合适的分布P(y|x)，使得条件熵的取值最大

2. 生成式模型和判别式模型

生成式模型是对联合概率分布P(X, Y, Z)进行建模，即
$P(Y|X) = P(X, Y)/P(X) = \Sigma _Z P(X, Y, Z) / \Sigma _{Y,X} P(X,Y,Z)$
判别式模型是直接对条件概率分布P(Y|X)进行建模，即
$P(Y|X) = \Sigma _Z P(Y,Z|X)$
生成式模型：朴素贝叶斯、贝叶斯网络、LDA、隐马尔可夫模型
判别式模型：最大熵模型、条件随机场

3. 马尔可夫模型

隐马尔可夫模型是对含有位置参数（隐状态）的马尔可夫链进行建模的生成模型，隐状态 $x_i$ 对于观测者不可见，观测值只能见到每个隐状态对应的输出 $y_i$ ，而 $y_i$ 仅仅取决于 $x_i$ 。隐马尔可夫模型参数包括：隐状态减的转移概率、隐状态到观测状态的输出概率、隐状态的取值空间、观测状态的取值空间以及初始概率分布。
三个基本问题与求解：
1）概率计算问题：已知模型所有参数，计算观测序列出现的概率，可以用前向和后向算法求解；
2）预测问题：已知模型所有参数和观测序列，计算最可能的隐状态序列X，（维特比算法）
3）学习问题：已知观测序列，求解使得该观测序列概率最大的模型参数，包括隐状态序列、隐状态之间的转移概率分布等，——Baum-Wenlch算法

4. 最大熵马尔可夫模型：序列标注偏置

条件随机场CRF
主题模型：从文本库中发现有代表性的主题，得到每个主题上词的分布，并且计算出每篇文章对应着哪些主题。
pLSA: 生成模型，频率派思想
LDA：可以堪称pLSA的贝叶斯版本，在文本生成过程中为主题分布和词分布分别加了两个Dirichlet先验。
LDA模型中主题个数K为预先指定的超参数。

第七章：优化算法

1. 随机梯度下降法

$\theta _{t+1} = \theta _t - \eta g_t$
随机梯度下降法的加速：
评价：计算速度大、内存开销小。但是由于接受信息量有限，SGD对梯度的估计经常出现偏差，造成目标函数曲线收敛的很不稳定，伴有强烈波动，甚至无法收敛。
解决方法：惯性保持和环境感知

2. 动量方法（Momentum)——刻画运动量

借助惯性作用，迭代模型参数：
$v_t = \gamma v_{t-1} + \eta g_t$
$\theta _{t+1} = \theta _t - v_t$
具体来说，前进步伐 $-v_t$ 有两部分组成，一时学习效率乘以当前估计的梯度，二是带衰减的前一次步伐。这里，惯性就体现在对前一次步伐信息的重利用上。类比物理知识，当前梯度就好比当前时刻受力产生的加速度，前一次步伐好比前一时刻的速度，当前步伐好比当前时刻的速度，因此当前时刻速度应该考虑前一时刻速度和当前加速度。另外，衰减系数扮演了阻力的作用。

3. AdaGrad方法

对周围环境的感知
随机梯度下降法对环境的感知是指在参数空间中，根据不同参数的一些经验性判断，自适应地确定参数地学习速度，不同参数地更新步幅不同。
如文本处理中训练词嵌入模型的参数时，希望更新频率低的参数可以拥有较大的更新步幅，而更新频率高的参数步幅小。
AdaGrad采用”历史梯度平方和“来衡量不同参数的梯度的稀疏性，借助退火过程，保证收敛性。

4. Adam方向”惯性保持+环境感知

一方面，记录一阶矩，即过往梯度与当前梯度的平均，体现了惯性保持；另一方面，记录二阶矩，即过往梯度平方和当前梯度平方的平均，体现了环境感知能力。
$m_t = \beta m_{t-1} + (1-\beta _1)g_t$
$v_t = \beta _2 v_{t-1} + (1-\beta _2)g_t^2$
当 $m_t$ 大且 $v_t$ 大时，梯度大且稳定，表明遇到明显的大坡，前进方向明确； $m_t$ 趋于零且 $v_t$ 趋于0，可能到达局部最低点。

第九章：前向神经网络

1. 激活函数

sigmoid函数
在x很大或者很小时梯度趋近于0，梯度消失
tanh函数
$f(x) = (e^x -e^{-x})/(e^x+e^{-x})$
相当于sigmoid函数的平移： $tanh(x)=2sigmoid(2x)-1$
同样会出现梯度消失
relu系列函数vs sigmoid and tanh
优点
1）sigmoid, tanh计算指数，复杂度高
2）relu具有非饱和性，可以解决梯度消失，提供相对宽的激活边界；
3）relu的单侧一直提供了网络的稀疏表达能力。
局限性
relu函数训练过程中会出现神经元死亡的问题，负梯度经过relu会被置为0且无法再次激活，即流经该神经元的梯度永远为0，不对任何数据产生响应。实际训练中lr过大会导致一定比例的神经元不可逆死亡，进而参数梯度无法更新。
变种Leaky relu(LRelu) :x<0, f(x)=ax
保留部分负梯度信息，但a的值需要人工先验获多次重复训练。

2. 反向传播算法

Q1：平方误差损失函数和交叉熵损失函数分别适用于什么场景？
A：平方损失函数更适合输出为连续，并且最后一层不含sigmoid 或softmax激活函数的神经网络；交叉熵更适合二分类或多分类的场景。

3. 神经网络训练技巧

Q1：神经网络训练时是否可以将全部参数初始化为0？
A：不阔以。全连接的深度神经网络，同一层的任意神经元基本同构，拥有相同的输入和输出，如果参数初始化相同，则学习过程永远无法打破参数取值的对称性。
因此需要随机初始化神经网络参数的值，打破对称性。简单来说可以初始化参数为取值范围 $(-1/sqrt(d), 1/sqrt(d))$ ，其中d为神经元接受的输入维度。偏置可以设为0.
xavier初始化https://blog.csdn.net/shuzfan/article/details/51338178
Q2：dropout抑制过拟合的原理和实现方法
A：dropout是指在深度网络的训练中，以一定概率随机地丢弃一部分神经节点。具体来说，dropout作用于每份小批量训练数据，由于其随机丢弃部分神经元的机制，相当于每次迭代都在训练不同结构的神经网络。
类似bagging，dropout可以看做一种使用的大规模深度神经网络的模型集成算法。bagging相对来说耗费大量的运算时间和空间，而dropout提供轻量级的Bagging 集成近似。
对于任意神经元，每次训练中都与一组随机挑选的不同神经元集合共同进行优化，这个过程会减弱全体神经元之间的联合适应性，减少过拟合风险。
Q3：批量归一化的基本动机和原理
A：训练数据与测试数据分布不同会大大降低网络泛华能力，因此在训练开始前需要对输入数据进行归一化处理。
但神经网络训练中，每一层隐层参数会改变训练数据的分布，使得网络在每次迭代中都需要拟合不同的数据分布，增大训练复杂度和过拟合风险。
批量归一化是针对每一批数据，在网络的每一层输入之前增加归一化处理。可以看做在每一层输入和上一层输出之间加入了新的计算层，对数据的分布进行额外的约束，增加模型泛化能力。
问题：批量归一化同时也降低了拟合能力，例如输出为sigmoid函数时，归一化后数据整体处于函数非饱和区域，只包含线性变换，破坏了学习到的特征分布。
因此，为了恢复原始数据分布，可以引入变换重构和可学习参数：
$y^{(k)} = \lambda^{(k)}x^{(k)} + \beta^{(k)}$
其中 $\lambda$ , $\beta$ 为输入数据的方差和偏差。

4. 深度残差网络deep residual network ResNet

解决或缓解深层的神经网络训练中的梯度消失问题。
解决方法：既然离输入近的神经网络层较难训练，那么可以将它短接到更靠近输出的层，即H(x)=x+F(x),如此F(x)被设计为只需要拟合输入x和目标输出H(x)的残差。有利于模型加深。

第十章：RNN

1. 处理文本数据时，循环神经网络与前馈神经网络的区别

A：一般的前馈神经网络，通常接受一个定长的向量作为输入，难以捕获句子的长距离特征。而循环神经网络由于具备对序列顺序信息的刻画能力，往往能得到更准确的结果。

2. 循环神经网络的梯度消失问题

反向传播算法梯度消失问题：神经网络激活函数为sigmoid函数，具有饱和特性，在输入达到一定值的情况下，输出不会有明显变化。而后层梯度本来就比较小，梯度误差反传到前层时几乎衰减为0，使得无法对前层的参数进行正常的学习。

Q1：循环神经网络为什么会出现梯度消失或梯度爆炸？改进方案？
A：循环神经网络的求解可以采用BPTT算法（back propagation through time），是反向传播算法的简单变种。
$net_t = Ux_t + Wh_{t-1}$
$h_t = f(net_t)$
$y = g(Vh_t)$
$net_t$ 对 $net_{t-1}$ 的梯度，为n*n矩阵，又被成为雅可比矩阵。
当雅可比矩阵的最大特征值大于1时，随着离输出越来越远，每层的梯度大小呈指数增长，导致梯度爆炸；反之，若雅可比矩阵的最大特征值小于1，会呈指数减小，导致梯度消失。
Q2：RNN中使用Relu作为激活函数会有什么问题？
A： $net_t$ 的表达式最终包含t个W连乘。如果W不是单位矩阵，最终结果会趋向于0或者无穷，出现严重的数值问题。
CNN不会出现这种问题：因为CNN中每一层的权重矩阵不同，并且在初始化时它们独立同分布，可以相互抵消
因此，采用Relu作为激活函数时，需要将W初始化为单位矩阵。

3. LSTM

Q1：激活函数的选取：遗忘门、输入门、输出门使用sigmoid函数，生成候选记忆时，使用tanh。这两个函数都是饱和的，即输入达到定值后输出不会明显变化。sigmoid函数输出在0-1之间，符合门控的物理含义。生成候选记忆时，tanh函数输出在-1~1之间，符合大多数场景下特征分布时0中心的特点。此外，tanh在0附近比sigmoid梯度更大，收敛速度更快。

4. seq2seq模型

seq2seq模型：通过深度神经网络将一个作为输入的序列映射到一个作为输出的序列，包括编码输入和解码输出。
Q1：seq2seq模型在解码时，有哪些常用方法？
贪心法：选取一种度量标准后，每次都在当前状态下选择最佳的一个结果，直到结束。贪心法计算代价低，但只能获得局部最优解。
集束搜索：启发式算法，保存前beam size个当前最佳选择，进行下一步扩展和排序，然后选择前b个，循环迭代。
解码时使用堆叠的RNN、dropout、与编码器之间建立残差连接。

5. 注意力机制

直观理解：在生成一个输出词时，考虑每一个输出词与当前输出词的对齐关系，对齐越好的词会有更大的权重，对输出词的影响也越大。

第十一章：强化学习

第十二章：集成学习

1. GBDT, XGBoost

Boosting 是通过逐步聚焦于基分类器分错的样本，减小集成分类器的偏差。Bagging则是分而治之，通过对训练样本多次采样，并分别训练出不同模型，然后综合，来减少集成分类器的方差。
集成学习3步骤：
1）找到误差互相独立的基分类器。
2）训练基分类器。
2）合并基分类器的结果。

2. 合并基分类器的方法：voting, stacking

stacking 是用串行的方法，将前一个基分类器的结果输出到下一个分类器，将所有基分类器的输出结果相加（或者用更加复杂的算法融合）作为最终的输出。
Adaboost:
1）确定基分类器
2）训练基分类器 $h_t$
3）计算 $h_t$ 的错误率 $\epsilon$ ，确定分类器 $h_t$ 权重： $a_t = log((1-\epsilon _t)/ \epsilon _t))$ ;
4）设置下一次采样
5）合并基分类器，加权求和。

3. 基分类器

决策树，神经网络

使用决策树作为基分类器的原因：
1）决策树可以较为方便地将样本权重整合到训练过程中；
2）决策树的表达能力和泛化能力，可以通过调节树的层数折中；
3）样本数据的扰动对于决策树的影响较大，因此不同样本形成的决策树基分类器随机性较大，这样的不稳定学习器更适合作为基分类器。
线性分类器和k近邻算法可以作为基分类器吗：
A：不可以，一般为这两种算法是较为稳定的分类器，本身方差就不大。因此以它们为基分类器使用Bagging并不能获得更好的表现，甚至导致不收敛。

4. 偏差，方差

Q：如何从减小偏差和方差的角度解释Boosting，Bagging 的原理？
A：Bagging通过降低方差提高弱分类器性能，Boosting通过降低偏差提升弱分类器性能。Bagging从n个独立不相关的模型的预测结果取平均，方差是原模型的1/n.而Boosting则是不断减小残差，减小损失函数，降低偏差。但Boosting的过程并不会显著降低方差。这是因为Boosting 各个弱分类器之间是强相关的，缺乏独立性。

5. GBDT

根据当前模型损失函数的负梯度信息来训练新加入的弱分类器，之后累加。残差
通常基于CART，

Q: 梯度提升和梯度下降的区别和联系
A: 两者都是在每一轮迭代中，利用损失函数相对于模型的负梯度方向的信息来对当前模型进行更新，在梯度下降中模型以参数化形式表示，而在梯度提升中，模型并不需要进行参数化表达，而是直接定义在函数空间中，而从大大扩展了可以使用的模型种类。
GBDT的优点和局限性
优点
1）计算速度快，树与树之间并行化计算；
2）在分布稠密的数据集上，泛化能力和表达能力都很好；
3）基于决策树，GBDT具有较好的解释性和鲁棒性，能够自动发现特征间的高阶关系，而且也不需要对数据归一化。
局限性
1）在高维稀疏数据集上，表现不如SVM或者神经网络；
2）在处理文本分类特征问题上，优势不如数值特征明显；
3）训练过程串行，只能在决策树内部局部并行。

6. XGBoost VS GBDT

GBDT基于经验损失函数的负梯度来构造新的决策树，在决策树构建后剪枝。
XGBoost在决策树构建阶段就加入了正则项，加上在 $F_{t-1}$ 处进行二阶泰勒展开。
XGBoost寻找最优树结构是一个NP-hard问题，因此在实际中往往采用贪心法来构建次优树结构：从根节点开始，每次对一个叶子节点进行分裂，针对每一种可能的分裂，根据特定原则选取最优的分裂。
区别：
1）GBDT是机器学习算法，XGBoost是该算法的工程实现；
2）在利用CART作为基分类器时，XGBoost显式的加入了正则项来控制模型复杂度，有利于防止过拟合，从而提高泛化能力；
3）GBDT在训练时只采用了代价函数的一阶导数信息，XGBoost对代价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数；
4）传统GBDT一般基于CART，XGBoost支持多种基分类器，如线性分类器；
5）传统GBDT每轮迭代时使用全部数据，XGBoost采用了与随机森林相似的策略，支持对数据进行采样；
6）传统GBDT没有对缺失值进行处理，XGBoost能自动学习出缺失值的处理策略。

7. XGBoost对缺失值的处理：

xgboost把缺失值当做稀疏矩阵来对待，本身的在节点分裂时不考虑的缺失值的数值。缺失值数据会被分到左子树和右子树分别计层损失，选择较优的那一个。如果训练中没有数据缺失，预测时出现了数据缺失，那么默认被分类到右子树。

8. 什么样的模型对缺失值更敏感？

树模型对缺失值的敏感度低，大部分时候可以在数据缺失时时使用。
涉及到距离度量(distancemeasurement)时，如计算两个点之间的距离，缺失数据就变得比较重要。因为涉及到"距离"这个概念，那么缺失值处理不当就会导致效果很差，如K近邻算法（KNN）、支持向量机(SVM)。
线性模型的代价函数(loss function)往往涉及到距离(distance)的计算，计算预测值和真实值之间的差别，这容易导致对缺失值敏感。
神经网络的鲁棒强，对于缺失数据不是非常敏感，但要求数据量大。
贝叶斯模型对于缺失数据也比较稳定，数据量很小的时候用贝叶斯模型。
总体来看，对于有缺失值的数据在经过缺失处理后：
数据量很小，朴素贝叶斯
数据量适中或者较大，用树横型，优先xgboost
数据量较大，也可以用神经网络
避免使用距离度量相关的模型，如KNN和SVM

原文链接：https://blog.csdn.net/qq_19446965/article/details/81637199

第十三章：生成式对抗网络

补充

1. 理解HMM，CRF

参考https://www.zhihu.com/question/35866596

概览图

2. 生成式模型 vs 判别式模型

discrimination vs generative

前向后向算法：Baum-Welch
利用logsumexp: 防止数据指数溢出 log(sum(exp)) = a+log(sum(exp(x-a))) a=max(x)
https://www.hankcs.com/ml/computing-log-sum-exp.html

3. CRF理论与代码实现细节

CRF与HMM关系，区别
1）CRF为判别式模型，HMM为生成式模型
2）两个模型都可以用于序列标注。但HMM模型要求两个假设，一是输出值之间严格独立，二是状态的转移过程中只与前一状态相关；而序列标注不仅与前一状态有关，还与序列长度、单词上下文有关，使得HMM训练处的模型准确度不高。而CRF引入特征函数，解决了输出独立性假设的问题，可以表达当前输出值与多个状态之间的依赖性。
维特比，beam-search 时间复杂度，区别
viterbi算法：dp思想，通过状态转移概率矩阵找出最短路径（概率最大路径），一般用于HMM，CRF，seq2seq
viterbi算法找到的一定是最优解，但如果字典或者状态集特别大的情况下，查找的状态会非常多，影响效率，时间复杂度为O(NNM);
集束搜索(beam search)：可以被认为是Viterbi算法的贪心形式，即每次使用beam size来限制下一步使用词的数量。集束搜索是在测试阶段为了获得更好准确性而采取的一种策略，在训练阶段无需使用。
显然集束搜索属于贪心算法，不能保证一定能够找到全局最优解，因为考虑到搜索空间太大，而采用一个相对的较优解。而维特比算法在字典大小较小时能够快速找到全局最优解。

4. 手推SVM：https://zhuanlan.zhihu.com/p/35755150

SVM原理，对偶问题
$L(w,b) = \Sigma \alpha_i - 0.5 \Sigma_i \Sigma_j \alpha_i \alpha_j y_i y_j x_i x_j$
最小最大问题可以转化为最大最小问题，即凸优化问题

5. XGBOOST ，LGB 生长策略，分类策略https://www.cnblogs.com/IcarusYu/p/10639599.html

分类策略：
xgboost: level-wise生长策略，不加区分的分裂同一层所有叶子节点
不容易过拟合，但也带来了额外开销
lgb: leaf-wise生长策略，带深度限制，提高效率

6. auc roc

https://www.zhihu.com/question/39840928
排序 AUC公式
交叉熵损失：对数损失函数，也称交叉熵，惩罚分类错误

7. 手写kmeans#coding=utf-8

import numpy as np
import random
from sklearn import datasets
from matplotlib import pyplot as plt
def Ecdist(vec1, vec2):
    return np.sqrt(np.sum(np.power(vec1-vec2, 2)))

def randChosenCent(dataset,k):
    # 样本数
    m=dataset.shape[0]
    # 初始化列表
    centroidsIndex=[]
    #生成类似于样本索引的列表
    dataIndex=list(range(m))
    for i in range(k):
        #生成随机数
        randIndex=random.randint(0,len(dataIndex))
        #将随机产生的样本的索引放入centroidsIndex
        centroidsIndex.append(dataIndex[randIndex])
        #删除已经被抽中的样本
        del dataIndex[randIndex]
    #根据索引获取样本
    centroids = dataset[centroidsIndex]
    return np.mat(centroids)

def kMeansSSE(dataSet,k,distMeas=Ecdist, createCent=randChosenCent):
    m = np.shape(dataSet)[0]
    #分配样本到最近的簇：存[簇序号,距离的平方]
    clusterAssment=np.mat(np.zeros((m,2)))
    #step1:#初始化聚类中心
    centroids = createCent(dataSet, k)
    print('initial centroids=',centroids)
    sseOld=0
    sseNew=np.inf
    iterTime=0 #查看迭代次数
    while(abs(sseNew-sseOld)>0.0001):
        sseOld=sseNew
        #step2:将样本分配到最近的质心对应的簇中
        for i in range(m):
            minDist=np.inf;minIndex=-1
            for j in range(k):
                #计算第i个样本与第j个质心之间的距离
                distJI=distMeas(centroids[j,:],dataSet[i,:])
                #获取到第i样本最近的质心的距离,及对应簇序号
                if distJI<minDist:
                    minDist=distJI;minIndex=j
            clusterAssment[i,:]=minIndex,minDist**2 #分配样本到最近的簇
        iterTime+=1
        sseNew=sum(clusterAssment[:,1])
        print('the SSE of %d'%iterTime + 'th iteration is %f'%sseNew)
        #step3:更新聚类中心
        for cent in range(k):
            #样本分配结束后，重新计算聚类中心
            ptsInClust=dataSet[np.nonzero(clusterAssment[:,0].A==cent)[0]]
            #按列取平均,mean()对array类型
            centroids[cent,:] = np.mean(ptsInClust, axis=0)
    return centroids, clusterAssment

小兔的棋盘？

7. 从实质上看，决策树和逻辑回归的分歧是：

1．逻辑回归对数据整体结构的分析优于决策树，而决策树对局部结构的分析优于逻辑回归。
2．逻辑回归擅长分析线性关系，而决策树对线性关系的把握较差。虽然对付非线性关系是决策树的强项，但是很多非线性关系完全可以用线性关系作为近似，而且效果很好。线性关系在实践中有很多优点：简洁，易理解，可以在一定程度上防止对数据的过度拟合。
3．逻辑回归对极值比较敏感，容易受极端值的影响，而决策树在这方面表现较好。

8. word2vec 加速方法：负采样与层次softmax

一般认为，负采样适合高频词，层次softmax适用于低频词。
层次softmax即将输出的softmax层替换为层次softmax构建基于哈夫曼树，高频词离树根近，找到单词花的时间更少。
假设找到单词w_2的路径为 left-left-right, 则概率为：
$p(w_2, \theta)=p((w_2, 1), left)*p((w_2, 2), left)*p((w_2, 3), right)$
$p(w_2)=\sigma(\theta_{w_2, 1}^T h)*\sigma(\theta_{w_2, 2}^T h)*(-\sigma(\theta_{w_2, 3}^T h))$

9. fasttext的结构：

https://www.cnblogs.com/eniac1946/p/8818892.html

文本分词后排成列做输入。
lookup table变成想要的隐层维数。
隐层后接huffman Tree。这个tree就是分层softmax减少计算量的精髓。

Python基础

1.copy和deepcopy
https://blog.csdn.net/u010712012/article/details/79754132
寻常意义的复制就是深复制，即将被复制对象完全再复制一遍作为独立的新个体单独存在。所以改变原有被复制对象不会对已经复制出来的新对象产生影响。
—–而浅复制并不会产生一个独立的对象单独存在，他只是将原有的数据块打上一个新标签，所以当其中一个标签被改变的时候，数据块就会发生变化，另一个标签也会随之改变。这就和我们寻常意义上的复制有所不同了。
简单来说，python的赋值过程与其说是将值赋给变量，不如说是建立一个到值得reference

>> a = [1, 2, 3]
>>> b = a
>>> a = [4, 5, 6] //赋新的值给 a
>>> a
[4, 5, 6]
>>> b
[1, 2, 3]
# a 的值改变后，b 并没有随着 a 变

>>> a = [1, 2, 3]
>>> b = a
>>> a[0], a[1], a[2] = 4, 5, 6 //改变原来 list 中的元素
>>> a
[4, 5, 6]
>>> b
[4, 5, 6]
# a 的值改变后，b 随着 a 变了

>>> import copy
>>> origin = [1, 2, [3, 4]]
#origin 里边有三个元素：1， 2，[3, 4]
>>> cop1 = copy.copy(origin)
>>> cop2 = copy.deepcopy(origin)
>>> cop1 == cop2
True
>>> cop1 is cop2
False 
#cop1 和 cop2 看上去相同，但已不再是同一个object
>>> origin[2][0] = "hey!" 
>>> origin
[1, 2, ['hey!', 4]]
>>> cop1
[1, 2, ['hey!', 4]]
>>> cop2
[1, 2, [3, 4]]
#把origin内的子list [3, 4] 改掉了一个元素，观察 cop1 和 cop2

2.lambda
lambda作为关键字创建一个匿名函数，匿名函数不需要以标准方式声明，可以有参数可以没有参数
1、lambda只是一个表达式，函数体比def简单很多
2、lambda的主体是一个表达式，而不是一个代码块。仅仅能在lambda表达式中封装有限的逻辑进去
3、lambda函数拥有自己的名字空间，且不能访问自有参数列表之外或全局名字空间里的参数
4、简单单行代码或者一次性的函数可以用lambda函数来书写，可以让代码更简洁。
5、对于复杂函数或者函数体体量大的函数，最好不要用lambda函数，会增加代码的阅读难度，使代码晦涩难懂。
6、在非多次调用的函数的情况下，lambda表达式即用既得，提高性能
3.生成器、迭代器、装饰器
//www.greatytc.com/p/efaa19594cf4

iterable object, iterator, generator

可迭代对象、迭代器、生成器比较容易混淆，一般来说，可使用for循环进行迭代的一般都是可迭代对象，list, set, dict天然就是一个可迭代对象.
通过 iter(object) 可以对可迭代对象进行包装，来返回一个迭代器。

>>> x = [1, 2, 3]
>>> y = iter(x)
>>> type(x)
<class 'list'>
>>> type(y)
<class 'list_iterator'>

调用 iter() 之后，变成了一个 list_iterator 的对象。会发现增加了 next 方法。所有实现了 iter 和 next 两个方法的对象，都是迭代器。
迭代器是带状态的对象，它会记录当前迭代所在的位置，以方便下次迭代的时候获取正确的元素。iter返回迭代器自身，next返回容器中的下一个值，如果容器中没有更多元素了，则抛出StopIteration异常。

生成器generator
相比迭代器更加简洁，可以一边循环一边生成，减少全部生成时对内存的要求
两种生成方法：
1）改造列表生成式

>>> [x*x for x in range(10)]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
>>> (x * x for x in range(10))
<generator object <genexpr> at 0x03804630

2）定义def函数，在函数中通过yeild生成

>>>def spam():
       yield"first"
       yield"second"
       yield"third"
>>> spam
<function spam at 0x011F32B0>
>>> gen
<generator object spam at 0x01220B20>
>>> gen.next()
'first'
>>> gen.next()
'second'
>>> gen.next()
'third'

也可以使用for循环，避免出现StopIteration
进行函数调用的时候，返回一个生成器对象。在使用 next() 调用的时候，遇到 yield 就返回，记录此时的函数调用位置，下次调用 next() 时，从断点处开始。

装饰器
非常适合有切面需求的场景，比如权限校验，日志记录和性能测试等等。比如你想要执行某个函数前记录日志或者记录时间来统计性能，又不想改动这个函数，就可以通过装饰器来实现。
使用@符号
4.列表和元组

机器学习基础

1.聚类算法，
比如k-means，建议深入细节，比如怎么收敛，为什么有效果
$l(\theta) = \sum_{i=1}{m}log\sum_{z{(i)}}p(x{(i)},z{(i)};\theta) = \sum_{i=1}{m}log\sum_{z{(i)}}Q_{i}(z{(i)})\frac{p(x{(i)},z{(i)};\theta)}{Q_{i}(z{(i)})}\geq \sum_{i=1}{m}\sum_{z{(i)}}Q_{i}(z{(i)})log\frac{p(x{(i)},z{(i)};\theta)}{Q_{i}(z{(i)})}$
https://www.cnblogs.com/little-YTMM/p/5885153.html
收敛性，由EM算法的收敛性，k-means是一种特殊的EM算法，目标函数为损失函数
对比其他算法呢，比如高斯混合模型
PCA：实现的两种方式，其中SVD的好处
2.分类算法
核心的是随机森林，比如它属于集成模型，每颗树选取部分特征，类似于dropout
bagging与boast对比理解
逻辑回归的缺点和优点
svm
数据增强

最后编辑于：2020.04.02 12:29:17

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 212,332评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,508评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 157,812评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,607评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,728评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,919评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,071评论 3赞 410
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,802评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,256评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,576评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,712评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,389评论 4赞 332
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,032评论 3赞 316
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,798评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,026评论 1赞 266
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,473评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,606评论 2赞 350