马上开始秋招了，自己总结了一份算法常用知识点，如有错误，欢迎指教。如有遗漏，欢迎补充。

逻辑回归

模型总结

简介：LR回归是一个线性的二分类模型，可计算样本发生的概率。LR的最终结果是通过使用sigmoid函数（指数族函数）将线性回归的结果与分类任务的真实标记结合起来。
基本假设：假设数据服从伯努利分布，且样本为正概率为 $p=\dfrac{1}{1+e^{-\theta^{T} x}}$
损失函数：极大似然函数： $L _ \theta\left(x\right )= \prod _ {i=1}^{m}h _ \theta(x^{i};\theta )^{y{i}}*(1-h _\theta(x^{i};\theta))^{1-y^{i}}$
求解方法：梯度下降法(拓展知识点：随机梯度下降，批梯度下降，small batch 梯度下降,Adam，动量法等优化方法)
为什么LR要使用sigmoid函数：LR属于广义线性模型，sigmoid函数则是指数族函数，
优点：
1. 适用于二分类问题，以概率形式输出结果，可以通过取阈值得到分类结果。
2. 判别模型：LR模型直接对分类可能性进行建模，无需事先假设数据分布，这样就避免了假设分布不准确所带来的问题
3. 实现简单，分类时计算量非常小，速度快，存储资源低
4. 可解释性强：线性回归的参数取值反应特征的强弱。
缺点：
1. 准确性不高，容易过拟合
2. 只能处理两分类问题（在此基础上衍生出来的softmax可以用于多分类），且必须线性可分；
适用场景：
1. 是否支持大规模数据：支持，并且有分布式实现
2. 特征维度：可以很高
3. 是否有 Online 算法:有（参考自）
4. 特征处理：支持数值型数据，类别型类型
5. 预估问题场景（如推荐、广告系统中的点击率预估，转化率预估等）
6. 分类场景（如用户画像中的标签预测，判断内容是否具有商业价值，判断点击作弊等
多分类问题：
1. 对k个类别的分类，建立k个二元分类器
2. 将逻辑回归推广到多元逻辑回归（Multinomial Logistic Regression），模型使用softmax对概率建模，$P(y=i|x, \theta) = \dfrac{e^{\theta_i^T x}}{\sum_j^K{e^{\theta_j^T x}}}$，其中决策函数为$y^* = argmax_i P(y=i|x,\theta)$，损失函数为$J(\theta)=-\dfrac{1}{N} \sum_i^N \sum_j^K {1[y_i=j] \log{\dfrac{e^{\theta_i^T x}}{\sum {e^{\theta_k^T x}}}}}$
3. 如何选择：如果如果类别之间互斥，则使用softmax.如果类别间有联系，则选用k个二元分类器。
模型比较：
1. 与线性回归比较：
  - 相同点：都是广义线性模型
  - 不同点：
    1. 经典线性模型的优化目标函数是最小二乘，而逻辑回归则是似然函数
    2. 线性回归输出连续值，分布范围在整个实数域。逻辑回归通过sigmoid函数将预测值限定为[0,1]间，输出值代表真实标记概率，因而对于这类问题来说，逻辑回归的鲁棒性比线性回归的要好。
2. 与svm比较，答案2
  - 相同点：
    1. LR和SVM都可以处理分类问题，且一般都用于处理线性可分的二分类问题（在改进的情况下可以处理多分类问题）
  - 不同点：
    1. LR是参数模型，SVM是非参数模型。
    2. 逻辑回归采用的是Logistical Loss，SVM采用的是hinge loss.这两个损失函数的目的都是增加对分类影响较大的数据点的权重，减少与分类关系较小的数据点的权重。
    3. SVM的处理方法是只考虑Support Vectors，也就是和分类最相关的少数点，去学习分类器。而逻辑回归通过非线性映射，大大减小了离分类平面较远的点的权重，相对提升了与分类最相关的数据点的权重。
    4. 逻辑回归相对来说模型更简单，好理解，特别是大规模线性分类时比较方便。而SVM的理解和优化相对来说复杂一些，只需要计算与少数几个支持向量的距离,这个在进行复杂核函数计算时优势很明显,能够大大简化模型和计算。
3. 与感知机比较
  - 相同点：
    1. 都是线性分类模型，原始模型都只能处理二分类问题
    2. 模型的形式相似(都是在线性模型外通过联系函数映射到另外的空间，只不过感知机是符号函数，LR是sigmoid(或者说Logistic)函数)
    3. 训练方法都是使用梯度下降法
  - 不同点：
    1. LR输出为仅是概率的值，而感知机输出为1/-1

参考资料

支持向量机

模型总结

简介：SVM是一个面向数据的分类算法，它的目标是为确定一个分类超平面，使不同的数据分隔开的同时,不同样例点到分割超平面的距离尽可能大。线性支持向量机通过最大化硬间隔得到线性分类器，当样本近似线性可分时通过最大化软间隔得到线性分类器，当样本线性不可分时可通过核函数及软间隔得到非线性分类器。
基本思想：求解能正确划分训练样本并且其几何间隔最大化的超平面。
间隔：
1. 函数间隔：$y_i(w\cdot x_i+b)$ 表示分类预测的确信程度,其中$y_i$表示分类是否正确
2. 几何间隔：$\dfrac{y_i(w \cdot x_i+b)}{||w||}$,其中$||w||$为w的L2范数，几何间隔为函数间隔对超平面法向量加上一定约束，不会因为参数比例的改变而改变
损失函数：折叶损失（hinge loss）$L=\sum\limits_{i=1}^n(0,1-wx_iy_i)$ 常用替代损失函数，通常具有较好的数学性质，比如凸的连续函数且是0/1损失函数的上界。作用是最小化经验分类错误
算法推倒：硬间隔最大化（几何间隔）—学习的对偶问题—软间隔最大化（引入松弛变量）—非线性支持向量机（核技巧）
为何转化对偶问题：参考[1]
1. 求解对偶问题可以将支持向量机原问题约束中的不等式约束转化为等式约束,因此对偶问题往往更加容易求解(结合拉格朗日和kkt条件)。
2. 使用对偶问题可以就可以导出含有内积形式的目标函数，方便引用核函数（拉格朗日表达式里面有内积，而核函数也是通过内积进行映射的）
3. 目前处理的模型严重依赖于数据集的维度d，如果维度d太高就会严重提升运算时间。对偶问题事实上把SVM从依赖d个维度转变到依赖N个数据点，考虑到在最后计算时只有支持向量才有意义，所以这个计算量实际上比N小很多。（对偶问题详解）
为何引入核函数：
1. 当样本在原始空间线性不可分时，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。
2. 在核函数给定的条件下，可利用解线性分类问题的方法求解非线性分类问题的支持向量机；学习是隐式地在特征空间进行的，不需要显式地定义特征空间和映射函数
3. 实际应用中，常依赖于领域知识直接选择核函数，其有效性通过实验验证
核函数性质：$K(x,y)=<ϕ(x),ϕ(y)>$，即在特征空间的内积等于它们在原始样本空间中通过核函数K计算的结果。
常用核函数有:
1. 线性核函数：$\kappa(x,x_i) = x \cdot x_i$ 简单，速度快，但是需要线性可分
2. 多项式核函数：$\kappa(x, x_i) = ((x\cdot x_i) + 1)^d$ 比线性核拟合程度更强，知道具体的维度，但是高次容易出现数值不稳定，参数选择比较多。
3. 高斯(RBF)核函数：$\kappa(x, x_i) = \exp(-\dfrac{||x - x_i||^2}{\delta^2})$ 拟合能力最强，但是要注意过拟合问题。不过只有一个参数需要调整。
4. sigmoid核函数：$\kappa(x, x_i) = \tanh(\eta<x, x_i> + \theta)$
优缺点：
1. 优点：
  1. SVM 的最终决策函数只由少数的支持向量所确定,计算的复杂性取决于支持向量的数目,而不是样本空间的维数,这在某种意义上避免了“维数灾难”
  2. 少数支持向量决定了最终结果，使该方法不但算法简单,而且具有较好的“鲁棒”性。
2. 缺点：对参数和核函数的选择比较敏感；对大规模数据训练比较困难。
SMO：SMO算法是支持向量机学习的一种快速算法，其特点是不断的将原二次规划问题分解为只有两个变量的二次规划问题，并对子问题进行解析求解，直到所有变量满足KKT条件为止，这样通过启发式的方法得到原二次规划问题的最优解，因为子问题有解析解，所以每次计算子问题都很快，虽然计算子问题次数很多，但在总体上还是高效的。
多分类问题：
1. 一对多方法：每一次把某个样本定为正样本，其余样本作为负样本。
  - 优点：每个优化问题规模小，分类器少，分类速度快；
  - 缺点：每一个分类器都说它属于它那一类—分类重叠；每一个分类器都说它不是它那一类—不可分类现象。
2. 一对一方法：每次选一个类的样本作正类样本，负类样本则变成只选一个类。
  - 优点:不会出现分类重叠现象。
应用场景：在文本分类，图像分类，生物序列分析和生物数据挖掘，手写字符识别等领域有很多的应用
回归问题：目标函数：$\min\bigg(\dfrac{1}{2}||w||^2_2+C\sum\mathit{l}_\epsilon\left(f\left(x_i\right)-y_i\right)\bigg)$，其中C为正则项，$\mathit{l}_\epsilon(x)$为$\epsilon$不敏感损失。

参考资料

决策树

模型总结

简介：决策树是一种分类和回归的基本模型，是一系列if-then决策规则的集合，该集合是决策树上的所有从根节点到叶节点的路径的集合。
决策树的构建：
1. 决策树的学习本质上就是从训练数据集中归纳出一组分类规则，使它与训练数据矛盾较小的同时具有较强的泛化能力。
2. 决策树的损失函数通常是正则化的极大似然函数，学习的策略是以损失函数为目标函数的最小化。
3. 由于这个最小化问题是一个NP完全问题，现实中，我们通常采用启发式算法来递归地选择最优特征及对数据集进行分割,直到所有子集基本被正确分类为止。为了使防止过拟合，还可搭配一定的剪枝策略，使模型有更好的泛化能力。
4. 总结而言，决策树构建分为三步：特征选择、模型生成、决策树的剪枝
节点划分（通常采用信息增益、信息增益比、基尼指数进行最优特征选择）：
1. 熵（entropy）: $\mathrm{entropy}(D) = -\sum\limits_{i=1}^n P_i\log_2 P_i$ 熵是表示随机变量不确定性的度量。熵越大，随机变量的不确定性就越大。
2. 条件熵：$\mathrm{entropy}(D,A) = \sum\limits_{i=1}^k \dfrac {D_{A_i}}{D} \log_2D_{A_i}$ 定义为X给定的条件下Y的条件概率分布的熵对X的数学期望。
3. 信息增益：$\mathrm{gain}(D,A) = \mathrm{entropy}(D) - \mathrm{entropy}(D,A)$ 特征A对训练数据集D的信息增益g（D，A），定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差
4. 信息增益率：$\mathrm{gainrate}(D,A) = \dfrac{\mathrm{gain}(D,A)}{\mathrm{entropy}(D,A)}$ 特征A对训练数据集D的信息增益比定义为信息增益g(D,A)与训练数据集D关于特征A的值的熵Ha(D)之比
5. 基尼指数：$\mathrm{gini}(D) = \sum_{i=1}^n p_k (1-p_k)$ 基尼指数反应了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此，gini(D)越小，则数据集D的纯度越高。
常见模型：
1. ID3：该算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。ID3算法缺点是往往偏向于选择取值较多的属性，而且不能处理具有连续值的属性，也不能处理具有缺失数据的属性。
2. C4.5：使用的是增益率的划分方法，是ID3的一个改进，具有较高的准确率且可以处理连续属性。可以在构造树的过程中进行剪枝，能够完成对连续属性的离散化处理；能够对不完整数据进行处理。
3. CART：使用基尼指数的划分准则；通过在每个步骤最大限度降低不纯洁度，CART能够处理孤立点以及能够对空缺值进行处理。树划分的终止条件：1、节点达到完全纯度； 2、树的深度达到用户所要深度 3、节点中样本的数量属于用户指定的个数；
对缺失值的处理(以c4.5为例)：
1. 信息增益率将按照缺失比例进行折减
2. 缺失样本将分别进入所有子节点，缺失值样本所占比重将根据子节点样本权重来下调
剪枝策略：由于根据训练数据生成的决策树往往过于复杂，导致泛化能力比较弱，所以，实际的决策树学习中，会将已生成的决策树进行简化，以提高其泛能力，这一过程叫做剪枝。
1. 预减枝：
  1. 预剪枝即提前终止树的生长。
  2. 预剪枝方式为：指定结点所包含的最小样本数目；指定树的高度或者深度；当划分节点不能带来泛化能力提升，则停止划分。（如何判断泛化能力提升提升与否？可以将一部分数据当作测试集。）
  3. 特点：预剪枝使得决策树的很多分支都没有展开,这不仅降低了过拟合风险，还显著减少时间开销。但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高。预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟含的风险。
2. 后剪枝：
  1. 后剪枝将在决策树构造完成后进行剪枝。剪枝的过程将依次对内部节点进行检查，判断如果将该节点下子树删除，验证集精度是否会提高。如果验证集精度提高，则进行剪枝策略。否则不变。
  2. 后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。
处理连续值方法：
1. 对连续特征进行排序$[A_1,A_2,…,A_n]$
2. 依次选取2个$A_i,A_{i-1}$取中间的一个点$a(A_{i}<a<A_{i-1})$，则数据集可以分为小于a与大于a两个部分（即将连续的特征离散化，可以理解为将质量特征转化为大小特征，只有大西瓜与小西瓜2种状态），计算a的信息增益率。
3. 不断循环执行(2)步骤，计算得到的最大信息增益率作为该特征的信息增益率，最大的信息增益率对应的a即为该节点分裂依据。
模型优缺点：
1. 优点：
  1. 生成的决策树很直观。
  2. 基本不需要预处理，不需要提前归一化，处理缺失值。
  3. 可以处理多维度输出的分类问题。
  4. 可以交叉验证的剪枝来选择模型，从而提高泛化能力。
  5. 对于异常点的容错能力好，健壮性高。
  6. 既可以处理离散值也可以处理连续值。
2. 缺点：
  1. 决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
  2. 决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变，而我们想要的分类器对噪声是健壮的。这个可以通过集成学习之类的方法解决。
  3. 寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。
  4. 有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
  5. 如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

参考资料

朴素贝叶斯

条件概率：在某条件下事件发生的概率。
后验概率：已知原分布，在实际发生某事件时,是原先某情况的可能性。
后验概率在某些情况下是条件概率的一种

模型总结

简介：基于贝叶斯定理，通过特征独立假设，计算后验概率分布的分类模型。
何为朴素：利用贝叶斯定理求解联合概率P(XY)时，需要计算条件概率P(X|Y)。在计算P(X|Y)时，朴素贝叶斯做了一个很强的条件独立假设（当Y确定时，X的各个分量取值之间相互独立），即$P(X1=x1,X2=x2|Y=yk) = P(X1=x1|Y=yk)*P(X2=x2|Y=yk)$。
为什么属性独立性假设在实际情况中很难成立，但朴素贝叶斯仍能取得较好的效果：
1. 对于分类任务来说，只要各类别的条件概率排序正确、无需精准概率值即可导致正确分类；
2. 如果属性间依赖对所有类别影响相同，或依赖关系的影响能相互抵消，则属性条件独立性假设在降低计算开销的同时不会对性能产生负面影响。
在估计条件概率P(X|Y)时出现概率为0的情况怎么办:使用Laplace修正（Laplace修正实际上假设属性与类别均匀分布，在朴素贝叶斯学习过程种额外引入数据的先验），具体做法是对没类别下所有划分的计数加1。
优缺点：
1. 优点：
  1. 对小规模的数据表现很好，适合多分类任务，适合增量式训练。
  2. 对缺失数据不太敏感，算法也比较简单，常用于文本分类。
  3. 朴素贝叶斯模型发源于古典数学理论，有稳定的分类效率。
2. 缺点：
  1. 对输入数据的表达形式很敏感（离散、连续，值极大极小之类的）。
  2. 模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，在属性个数比较多或者属性之间相关性较大时，分类效果不好(可考虑使用半朴素贝叶斯)。
  3. 需要知道先验概率，且先验概率很多时候取决于假设，假设的模型可以有很多种，因此在某些时候会由于假设的先验模型的原因导致预测效果不佳。
  4. 由于我们是通过先验和数据来决定后验的概率从而决定分类，所以分类决策存在一定的错误率。
朴素贝叶斯与LR的区别：
1. 朴素贝叶斯是生成模型，根据已有样本进行贝叶斯估计学习出先验概率P(Y)和条件概率P(X|Y)，进而求出联合分布概率P(XY),最后利用贝叶斯定理求解P(Y|X)。
2. 而LR是判别模型，根据极大化对数似然函数直接求出条件概率P(Y|X)；
3. 朴素贝叶斯是基于很强的条件独立假设（在已知分类Y的条件下，各个特征变量取值是相互独立的），而LR则对此没有要求；朴素贝叶斯适用于数据集少的情景，而LR适用于大规模数据集。

参考资料

kmeans

简介：k近邻算法是无监督聚类算法，是基本的分类、回归算法。k-means就是把空间内点，分成K类。最大化簇间距离，最小化簇内距离。用均值来代表类中心，并用于衡量与新点的距离。
有监督学习和无监督学习的区别：、
1. 监督学习：对具有标记的训练样本进行学习，以尽可能对训练样本集外的数据进行分类预测。（LR,SVM,BP,RF,GBRT）
2. 无监督学习：对未标记的样本进行训练学习，比发现这些样本中的结构知识。(KMeans,DL)
基本要素：k值的选择、距离度量及分类决策规则。
算法过程
1. 初始化：随机初始化每个类别的质心
2. 计算每个点到各个质心的距离，并把点归到最近的质心的类
3. 重新计算已经得到的各个类的质心
4. 迭代2~3步，直到没有点变更所属类别，算法收敛
k值的选择：
1. 依据一个合适得类簇指标，如平均直径等，只要我们假设的类簇的数目等于或者高于真实的类簇的数目时，该指标上升会很缓慢，而一旦试图得到少于真实数目的类簇时，该指标会急剧上升。
2. 首先采用层次凝聚算法决定结果的大致数目，并找到一个初始聚类，然后用迭代重定位来改进该聚类。
初始质心的选取：
1. 层次聚类或者Canopy预处理，选择质心。
2. 选择批次距离尽可能远的K个点：随机地选择第一个点，或取所有点的质心作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点。
优缺点：
1. 优点：
  1. 经典聚类算法，算法简单、快速
  2. 处理大数据集的时候，该算法可以保证较好的伸缩性和高效率
  3. 当簇近似高斯分布的时候，聚类效果不错
2. 缺点:
  1. K值是用户给定的，在进行数据处理前，K值是未知的，不同的K值得到的结果也不一样；
  2. 对初始簇中心点是敏感的
  3. 不适合发现非凸形状的簇或者大小差别较大的簇
  4. 特殊值、离群值对模型的影响比较大
距离度量：一般采用欧式距离。
1. 为什么不用曼哈顿距离：曼哈顿距离只计算水平或垂直距离，有维度的限制。另一方面，欧氏距离可用于任何空间的距离计算问题。因为，数据点可以存在于任何空间，欧氏距离是更可行的选择。
停止迭代准则：达到最大迭代次数、簇中心点变化率、最小平方误差
优化方法：在数据量较大，并且每个数据的特征维度较高的情况下，执行Kmeans聚类将是极为耗费代价的。因为，每一次聚类过程都是需要计算整个数据空间的。使用kd树或者ball tree，将所有的观测实例构建成一颗kd树，之前每个聚类中心都是需要和每个观测点做依次距离计算，现在这些聚类中心根据kd树只需要计算附近的一个局部区域即可
与GMM对比：
1. 相同点：
  1. 都对初始值敏感
  2. 都需要定义簇数K
2. 不同点
  1. 需要计算的参数不同：k-means是簇心位置；GMM是各个高斯分布的参数
  2. 计算目标参数的方法不同：k-means是计算当前簇中所有元素的位置的均值；GMM是基于概率的算法，是通过计算似然函数的最大值实现分布参数的求解的。

参考资料

神经网络

模型总结

简介：人工神经元通过一定的结构组织起来，就可以构成人工神经元网络。最常见的神经网络一般称为多层前馈神经网络，除了输入和输出层，中间隐藏层的个数被称为神经网络的层数。BP算法是训练神经网络中最著名的算法，其本质是梯度下降和链式法则。神经元网络对信息处理的快速性和强有力的学习记忆功能是由其大规模的并行工作方式、非线性处理、网络结构的可变性等固有结构特性决定的。
Backpropagation(误差逆传播)：重要需要会推导
1. 基本思想：计算出输出与标签间的损失函数值，然后计算其相对于每个神经元的梯度，根据梯度方向更新权值。
误差函数：均方误差
为什么引入激励函数：因为如果不用非线性激励函数，每一层都是上一层的线性函数，无论神经网络多少层，输出都是输入的线性组合，与只有一个隐藏层效果一样。相当于多层感知机了。所以引入非线性激励函数，深层网络就变得有意义了，可以逼近任意函数。
常见的激励函数,参考链接2：
1. sigmoid ( $y = (1 + \exp(-x))^{-1}$ ) ：将输出实值压缩到0-1之间。
  1. 缺点：（输入非常大或非常小的时候）容易梯度消失；sigmoid函数是非0均值的，Sigmoid函数的输出值恒大于0，这会导致模型训练的收敛速度变慢。计算exp比较耗时。
2. Tanh (读作Hyperbolic Tangent，双曲正切函数，表达式为 $y = {\exp(x) - \exp(-x)\over {\exp(x) + \exp(-x)}}$ ) ：Tanh 激活函数使得输出与输入的关系能保持非线性单调上升和下降关系，比sigmoid 函数延迟了饱和期（即导数接近0），解决了sigmoid函数非0均值的问题，对神经网路的容错性好。
3. Relu（修正线性单元）$y = max(0,x)$ ReLu使得网络可以自行引入稀疏性，在没做预训练情况下，以ReLu为激活的网络性能优于其它激活函数。
  1. 好处：收敛快，求梯度简单。计算复杂度低，不需要进行指数运算；具有稀疏特性（relu函数在负半区的导数为0 ，所以一旦神经元激活值进入负半区，那么梯度就会为0，也就是说这个神经元不会经历训练，即所谓的稀疏性）。
  2. 缺点：ReLU的输出不是zero-centered；Dead ReLU Problem（神经元坏死现象）：某些神经元可能永远不会被激活，导致相应参数永远不会被更新（在负数部分，梯度为0）。产生这种现象的两个原因：参数初始化问题；learning rate太高导致在训练过程中参数更新太大。解决方法：采用Xavier初始化方法，以及避免将learning rate设置太大或使用adagrad等自动调节learning rate的算法。ReLU不会对数据做幅度压缩，所以数据的幅度会随着模型层数的增加不断扩张。
4. Leaky ReLU($f(x) = \mathbb{1}(x < 0) (\alpha x) + \mathbb{1}(x>=0) (x)$)：解决了神经死亡问题
5. Relu与sigmoid对比：sigmoid反向传播求误差梯度时，求导计算量很大，而relu求导简单；对于深层网络，sigmoid反向传播时，在sigmoid接近饱和区时，变换太缓慢，导数趋0，从而无法完成深层网络的训练；Relu会使一部分神经元的输出为0，造成了网络的稀疏性，并且减少了参数的相互依存关系，缓解了过拟合问题。
6. Sigmoid 和 ReLU 比较：sigmoid 的梯度消失问题，ReLU 的导数就不存在这样的问题，
7. 各激活函数图像可参考，参考2
梯度消失：这本质上是由于激活函数的选择导致的，最简单的sigmoid函数为例，在函数的两端梯度求导结果非常小（饱和区），导致后向传播过程中由于多次用到激活函数的导数值使得整体的乘积梯度结果变得越来越小，也就出现了梯度消失的现象。
梯度爆炸：同理，出现在激活函数处在激活区，而且权重W过大的情况下。但是梯度爆炸不如梯度消失出现的机会多。
解决过拟合：
1. 数据集增强，获取更多的数据，创建更多的数据；
2. 使用合适的模型：网络结构简单化，正则化；提前终止
3. 结合多种模型：dropout，bagging，boosting
权值初始化方式,参考2：
1. 把w初始化为0【不可行】：如果把w初始化0，那么每一层的神经元学到的东西都是一样的（输出是一样的），而且在bp的时候，每一层内的神经元也是相同的，因为他们的gradient相同。
2. 随机初始化：缺点：随机数其实是在一个均值为0，方差为1的高斯分布中采样。当神经网络的层数增多时，会发现越往后面的层的激活函数（使用tanH）的输出值几乎都接近于0，会导致梯度消失
3. 哈维尔初始化（Xavier initialization）：w=np.random.randn(fan_in, fan_out)/np.sqrt(fan_in)，保持输入和输出的方差一致，这样就避免了所有输出值都趋向于0，缺点是只对tanh有效，对ReLU无效
4. He initialization：在ReLU网络中，假定每一层有一半的神经元被激活，另一半为0，所以，要保持variance不变，只需要在Xavier的基础上再除以2。
5. Batch Normalization：对输出值进行正则化变换，可以削弱不好地权值初始化方式带来的影响。
  1. Batch Normalization中所有的操作都是平滑可导，这使得back propagation可以有效运行并学到相应的参数$\gamma,\beta$。需要注意的一点是Batch Normalization在training和testing时行为有所差别。Training时$\mu_\mathcal{B}$和$\sigma_\mathcal{B}$由当前batch计算得出；在Testing时$\mu_\mathcal{B}$和$\sigma_\mathcal{B}$应使用Training时保存的均值或类似的经过处理的值，而不是由当前batch计算。
dropout：在每一次迭代训练中随机的选择一定的单元进行隐藏，因此每一次迭代的模型都是不同的，每一个神经元都不能过度依赖于另一个神经元，因此增强了模型的鲁棒性。
1. 为什么dropout可以防止过拟合：
  1. 取平均的作用：dropout掉不同的隐藏神经元就类似在训练不同的网络（随机删掉一半隐藏神经元导致网络结构已经不同)，整个dropout过程就相当于对很多个不同的神经网络取平均。
  2. 减少神经元之间复杂的共适应关系：因为dropout程序导致两个神经元不一定每次都在一个dropout网络中出现。使得神经网络不再依赖某些固定关系的神经元，迫使网络取学习更加鲁棒的特征。
batch normalizatin（批量归一化）：
1. BN的本质原理：相当于一个归一化层，也就是先做一个归一化处理（归一化至：均值0、方差为1），然后再进入网络的下一层，它是一个可学习、有参数（γ、β）的网络层。
2. 作用：
  1. 改善流经网络的梯度(具体来说就是反向传播中，经过每一层的梯度会乘以该层的权重，权重的大小影响了梯度的消失和爆炸，batchnorm就是通过对每一层的输出规范为均值和方差一致的方法，消除了权重带来的放大缩小的影响，进而解决梯度消失和爆炸的问题，或者可以理解为BN将输出从饱和区拉倒了非饱和区)
  2. 允许更大的学习率，大幅提高训练速度
  3. 模型隐藏输出特征的分布更稳定，更利于模型的学习
  4. 减少对初始化的强烈依赖
  5. 改善正则化策略：作为正则化的一种形式，轻微减少了对dropout的需求
  6. 你再也不用去理会过拟合中dropout、L2正则项参数的选择问题，采用BN算法后，你可以移除这两项了参数，或者可以选择更小的L2正则约束参数了，因为BN具有提高网络泛化能力的特性；
  7. 再也不需要使用使用局部响应归一化层了（局部响应归一化是Alexnet网络用到的方法，搞视觉的估计比较熟悉），因为BN本身就是一个归一化网络层；
神经网络优缺点:
1. 优点：
  1. 自学习和自适应能力强：能够通过学习自动提取输出、输出数据间的“合理规则”，并自适应的将学习内容记忆于网络的权值中。（可以利用神经网络中某一层的输出当做是数据的另一种表达，从而可以将其认为是经过神经网络学习到的特征。）
  2. 有很强的非线性拟合能力，可映射任意复杂的非线性关系，而且学习规则简单，便于计算机实现。
  3. 泛化能力强
  4. 容错能力强：BP神经网络在其局部的或者部分的神经元受到破坏后对全局的训练结果不会造成很大的影响，也就是说即使系统在受到局部损伤时还是可以正常工作的。
2. 缺陷：
  1. 随着网络层数的加深，优化函数越来越容易陷入局部最优解，并且这个“陷阱”越来越偏离真正的全局最优，利用有限数据训练的深层网络，性能还不如浅层网络。
  2. 随着网络层数增加，梯度消失现象越来越严重，（一般指sigmoid函数，反向传播时，每传递一层，梯度衰减为原来的1/4。层数一多，梯度指数衰减后，底层基本接收不到有效的训练信号。）
  3. 算法收敛慢
  4. 网络结构不统一：网络结构的选择至今尚无一种统一而完整的理论指导，而网络的结构直接影响网络的逼近能力及推广性质。
无监督逐层训练：预训练：每次训练一层隐结点。训练时将上一层隐结点的输出作为输入，而本层隐结点的输出作为下一层隐结点的输入。在预训练结束后，再对整个网络进行微调训练。

参考资料

深度学习相关

前面也涉及到一部分深度学习的内容（如梯度爆炸等）

基础

对卡在局部极小值的处理方法：
1. 调节步伐：调节学习速率，使每一次的更新“步伐”不同；
2. 优化起点：合理初始化权重（weights initialization）
3. 预训练网络（pre-train），使网络获得一个较好的“起始点”，如最右侧的起始点就比最左侧的起始点要好。常用方法有：高斯分布初始权重（Gaussian distribution）、均匀分布初始权重（Uniform distribution）、Glorot 初始权重、He初始权、稀疏矩阵初始权重（sparse matrix）。
为何使用Batch Normalization：
1. BN本质上解决的是反向传播过程中的梯度问题，指在采用梯度下降法训练DNN时，对网络层中每个mini-batch的数据进行归一化，使其均值变为0，方差变为1，这样可以防止神经元进入sigmoid函数的饱和区，缓解DNN训练中的梯度消失/爆炸现象，加快模型的训练速度。
2. 为什么在normalize后还有一个scale and shift操作？简单的对网络层输入作归一化可能会改变原本的输入表示，而加入scale and shift操作，让归一化操作有机会通过对参数γ,β 的学习将其变回去，不改变输入表示。

卷积神经网络(CNN)

原理：由于图片的特殊性，CNN改变全连接为局部连接，通过局部连接和参数共享大范围的减少参数值。CNN的输入可以是tensor，例如二维矩阵，通过filter获得局部特征，较好的保留了平面结构信息。池化是一种降维的方法，按照卷积计算得出的特征向量维度大的惊人，可以通过池化的方式把图像中局部区域的特征做一个平滑压缩处理，保留主要的特征同时减少参数(降维，效果类似PCA)和计算量，防止过拟合，还可使模型具有一定的平移不变性。
卷积的作用：卷积核就相当于一个特征提取器，可以自动地从图像中提取特征，并且卷积核是二维的，可以把图像本身具有局部特性提取出来。使模型更加关注对模型有用的信息，而不是图像中的噪声。（关键词：局部相关性，权值共享-平移不变性）
参数共享机制
1. 在卷积层中每个神经元连接数据窗的权重是固定的，每个神经元只关注一个特性。神经元就是图像处理中的滤波器，比如边缘检测专用的Sobel滤波器，即卷积层的每个滤波器都会有自己所关注一个图像特征，比如垂直边缘，水平边缘，颜色，纹理等等，这些所有神经元加起来就好比就是整张图像的特征提取器集合。
2. 需要估算的权重个数减少: AlexNet 1亿 => 3.5w
3. 一组固定的权重和不同窗口内数据做内积: 卷积
1*1卷积的作用：
1. 实现跨通道的交互和信息整合
2. 进行卷积核通道数的降维和升维
3. 对于单通道feature map 用单核卷积即为乘以一个参数，而一般情况都是多核卷积多通道，实现多个feature map的线性组合
4. 可以实现与全连接层等价的效果。
请解释为什么3X3的卷积是最为常用的卷积核大小？小尺寸卷积核（1x1）和大尺寸卷积核（如7x7）都具有哪些优势和劣势，各自适用于什么场景？卷积核的尺寸可否为偶数，为什么？
1. 3x3卷积3x3是最小的能够捕获像素八邻域信息的尺寸。可以通过小尺寸卷积层的堆叠替代大尺寸卷积层，并且感受野大小不变。多个3x3的卷基层比一个大尺寸filter卷基层有更多的非线性（更多层的非线性函数），使得判决函数更加具有判决性。多个3x3的卷积层比一个大尺寸的filter有更少的参数，假设卷基层的输入和输出的特征图大小相同为C，那么三个3x3的卷积层参数个数3x（3x3xCxC）=27C2；一个7x7的卷积层参数为49C2；所以可以把三个3x3的filter看成是一个7x7filter的分解（中间层有非线性的分解, 并且起到隐式正则化的作用。
2. 卷积层尺寸越大，感受野越大，小尺寸的卷积层可以通过多层堆叠的方式获得大尺寸卷积层相同的感知野，同时还可以减少计算参数。使用大的卷积核，提取的特征更少，更粗犷。一般而言，对于图片较为简单如风景蓝天大海等，可以使用大尺寸的卷积核。图片较为复杂则选用小尺寸的卷积核。
3. 对于1x1卷积，可以代替全联接层，可以起到降维作用，也可以保持特征尺度不变的情况下做非线性变换，加深网络。
4. 是否可以是偶数：可以，但一般使用奇数是因为奇数有中心点，方便提取特征，另外也可以对称地padding。
假设我们有一个已经训练好的网络模型，有哪些方法可以在尽可能保证精度损失小的前提下实现模型压缩及网络加速？分别有什么需要注意的地方？　
　　1. 网络权值从高精度转化成低精度，模型准确率等指标与原来相近，模型大小变小，运行速度加快。
　　2. 将标准卷积层拆分成两个卷积层的MolileNet网络，可以在基本保证准确率的前提下大大减少计算时间和参数数量。
　　3. http://ai.51cto.com/art/201710/555869.htm

RNN

RNN原理：在普通的全连接网络或CNN中，每层神经元的信号只能向上一层传播，样本的处理在各个时刻独立，因此又被成为前向神经网络(Feed-forward+Neural+Networks)。而在RNN中，神经元的输出可以在下一个时间戳直接作用到自身，即第i层神经元在m时刻的输入，除了（i-1）层神经元在该时刻的输出外，还包括其自身在（m-1）时刻的输出。所以叫循环神经网络。
LSTM、GRU、RNN的原理以及差别：
1. RNN引入了循环的概念，但是在实际过程中却出现了初始信息随时间消失的问题，即长期依赖（Long-Term Dependencies）问题，所以引入了LSTM。
2. LSTM：因为LSTM有进有出且当前的cell informaton是通过input gate控制之后叠加的，RNN是叠乘，因此LSTM可以防止梯度消失或者爆炸。推导forget gate，input gate，cell state， hidden information等因为LSTM有进有出且当前的cell informaton是通过input gate控制之后叠加的，RNN是叠乘，因此LSTM可以防止梯度消失或者爆炸的变化是关键。（画LSTM示意图）
3. GRU是LSTM的变体，将忘记门和输入门合成了一个单一的更新门。

参考资料

集成学习

总结

概览

简介：集成学习的目的是通过结合多个基学习器的预测结果来改善单个学习器的泛化能力和鲁棒性。根据个体学习器的生成方式，目前的集成学习方法大致分为两大类：即个体学习器之间存在强依赖关系、必须串行生成的序列化方法，以及个体学习器间不存在强依赖关系、可同时生成的并行化方法；前者的代表就是Boosting，后者的代表是Bagging和“随机森林”（Random Forest）。
分类：
1. Bagging：Bagging方法中每一个基学习器的数据来源，都是将整体样本和所有特征进行一种有放回的抽取。每个基学习器在“不同”的数据集中学习出一个模型，最后的预测结果通过所有基学习器共同决定。分类问题采用投票的方式，回归问题采用平均值的方式。代表：随机森林
2. Boosting：用所有的数据去训练基学习器，每一个基学习器相互依赖，基于前面所有的学习器的结果，学习他们与真实值之间的残差，集中关注预测出错的地方，来形成一个新的学习器。是一种串行的学习方式。代表：AdaBoost、gbdt
3. Stacking：Stacking 是一种集成学习技术，通过元分类器或元回归聚合多个分类或回归模型。基础层次模型（level model）基于完整的训练集进行训练，然后元模型基于基础层次模型的输出进行训练。
Bagging和Boosting的区别（关键点：1. 降低方差 & 降低偏差 2. 降低过拟合 & 降低欠拟合 3. 并行，彼此独立 & 串行，相互依赖）：
1. 样本选择：
  1. Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。
  2. Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。
2. 样例权重：
  1. Bagging：使用均匀取样，每个样例的权重相等。
  2. Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。
3. 预测函数：
  1. Bagging：所有预测函数的权重相等。
  2. Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。
4. 并行计算：
  1. Bagging：各个预测函数可以并行生成。
  2. Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。
bagging是减少variance，而boosting是减少bias，参考2？
1. Bagging 通过再取样 (Bootstrap) 然后在每个样本上训练出来的模型取平均，因为每个基学习器权重相等，因此集成后的模型的偏差与单个基学习器的偏差近似，集成后主要降低的是模型的偏差。
2. Boosting 选用的基模型一般为弱模型，导致了每个基模型的准确度都不是很高（低方差，高偏差）。因此boosting集成之后主要降低模型的偏差。
使用gbdt处理分类与回归问题的不同点：损失函数不同：处理回归问题采用的是均方误差（MSE)，而处理分类问题的损失函数则是对数似然函数（https://blog.csdn.net/Liangjun_Feng/article/details/80668461 or https://www.cnblogs.com/pinard/p/6140514.html）
gbdt为何要采用负梯度拟合残差：当损失函数为误差平方函数时，gbdt拟合的是残差，当损失函数推广到一般函数时，一般通过损失函数的负梯度来拟合，这是一种通用的拟合损失误差的办法，这样无轮是分类问题还是回归问题，我们通过其损失函数的负梯度的拟合，就可以用GBDT来解决我们的分类回归问题。区别仅仅在于损失函数不同导致的负梯度不同而已。
随机森林的数量与过拟合：随机森林中的决策树的泛化误差都收敛于：$\underset{n \rightarrow \infty}{\lim}PE^{*}=P _ {xy}(P _ {\Theta}(k(X,\Theta)=Y)-\underset{j\neq Y}{\max}P _ {\Theta}(k(X,\Theta)\neq Y) > 0)$，随着随机森林中决策树数量(n)的增加，随机森林泛化误差(PE∗)将趋向一个上界。随机森林对未知实例有很好的扩展性，也就是说随机森林随着决策树数量的增多不易过拟合
优缺点：
1. bagging：
  1. 优点
    - 高效(训练一个bagging集成与训练一个基学习器复杂度同阶)
    - 与Adaboost不同，bagging可以不经修改地适用于多分类以及回归问题
    - 包外估计——自助采样过程中剩余的样本可以作为验证集来对泛化性能进行“包外估计”
    - 当基学习器为决策树时，还可使用包外样本来辅助剪枝，或用于估计决策树中各结点的后验概率以辅助对零训练样本节点的处理。
    - 当基学习器为神经网络时，可使用包外样本来辅助早停。
  2. 缺点：
    - 在某些噪音比较大的样本集上，RF模型容易陷入过拟合。
    - 取值划分比较多的特征容易对RF的决策产生更大的影响，从而影响拟合的模型的效果。

参考资料

boosting

gbdt简介：gbdt是一种boosting算法，通过多轮迭代,每轮迭代产生一个弱分类器，每个分类器在上一轮分类器的残差基础上进行训练，最终组成的强分类与回归模型。
gbdt部分面试总结：https://www.cnblogs.com/ModifyRong/p/7744987.html、https://blog.csdn.net/tinkle181129/article/details/79681702
传统Boosting 与 GradientBoost:
1. 原始的Boost算法是在算法开始的时候，为每一个样本赋上一个权重值，初始的时候，大家都是一样重要的。在之后的学习过程种，增加分错的点的权重，减少分对的点的权重，这样使得某些点如果老是被分错，那么就会被“严重关注”，也就被赋上一个很高的权重。、
2. Gradient Boost与传统的Boost的区别是，每一次的计算是为了减少上一次的残差(residual)，而为了消除残差，我们可以在残差减少的梯度(Gradient)方向上建立一个新的模型。
简述GBDT与XGBoost的区别:
1. 传统GBDT以CART作为基分类器，xgboost还支持线性分类器
2. 传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。
3. xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。
4. XGB的权重衰减:xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。
5. XGB支持列抽样:xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。
6. xgboost工具支持并行。
LightGBM相对XGBoost的改进参考:https://zhuanlan.zhihu.com/p/25308051 ，http://msra.cn/zh-cn/news/blogs/2017/01/lightgbm-20170105.aspx，http://izhaoyi.top/2017/08/02/model-cmp/
为什么XGBoost要用泰勒展开，优势在哪里？ XGBoost使用了一阶和二阶偏导, 二阶导数有利于梯度下降的更快更准. 使用泰勒展开取得二阶倒数形式, 可以在不选定损失函数具体形式的情况下用于算法优化分析.本质上也就把损失函数的选取和模型算法优化/参数选择分开了. 这种去耦合增加了XGBoost的适用性。

stacking

Stacking是指训练一个模型用于组合(combine)其他各个模型。即首先我们先训练多个不同的模型，然后再以之前训练的各个模型的输出为输入来训练一个模型，以得到一个最终的输出。实际中，我们通常使用单层logistic回归作为组合模型。

优化算法

梯度类

梯度类算法是求解优化问题种最常见的优化算法，梯度类算法以负梯度方向为搜索方向的，通过不断迭代逐渐逼近最优值。
$$\theta_i = \theta_i - \alpha\frac{\partial}{\partial\theta_i}J(\theta_0, \theta_1…, \theta_n)$$

梯度下降法

优缺点：

选择一个合理的学习速率很难。如果学习速率过小，则会导致收敛速度很慢。如果学习速率过大，那么其会阻碍收敛，即在极值点附近会振荡。
模型所有的参数每次更新都是使用相同的学习速率。如果数据特征是稀疏的或者每个特征有着不同的取值统计特征与空间，那么便不能在每次更新中每个参数使用相同的学习速率，那些很少出现的特征应该使用一个相对较大的学习速率。
初值依赖，容易陷入那些局部最优点中。

批量梯度下降(Batch graduebt descent)

批量梯度下降算法使用整个训练集计算目标函数的梯度并更新参数θ,因为每更新一次参数就需要计算整个数据集，所以批量梯度下降算法十分缓慢而且难以存放在内存中计算，更致命的是，使用批量梯度下降的算法无法在线更新。

随机梯度下降(Stochatic gradient decent， SGD)

与批量梯度下降方法不同，随机梯度下降方法一次只使用一个样本进行目标函数梯度计算，SGD计算非常快并且适合线上更新模型。但是，由于随机梯度下降法一次迭代一个样本，导致迭代方向变化很大，不能很快的收敛到局部最优解。

小批量梯度下降法（Mini-batch Gradient Descent）

小批量梯度下降结合了批量梯度下降和随机梯度下降的优点，它一次以小批量的训练数据计算目标函数的权重并更新参数。这个算法比SGD增加了一次更新使用的训练数据量，使得目标函数收敛得更加平稳；可以使用矩阵操作对每批数据进行计算，大大提升了算法的效率。

Momentum

SGD方法的一个缺点是其更新方向完全依赖于当前batch计算出的梯度，因而十分不稳定。Momentum算法会观察历史梯度$v_{t−1}$，若当前梯度的方向与历史梯度一致（表明当前样本不太可能为异常点），则会增强这个方向的梯度，若当前梯度与历史梯方向不一致，则梯度会衰减。类似于动量概念。这样一来，可以在一定程度上增加稳定性，从而学习地更快，并且还有一定摆脱局部最优的能力：
$$v_{t} = \gamma \cdot v_{t-1} + \alpha \cdot \triangledown_\Theta J(\Theta )$$
$$\Theta = \Theta-v_{t}$$

Adagrad

Adagrad算法能够在训练中自动的对learning rate进行调整，对于出现频率较低参数采用较大的α更新；相反，对于出现频率较高的参数采用较小的α更新。因此，Adagrad非常适合处理稀疏数据。

Adam

Adam(Adaptive Moment Estimation)是另一种自适应学习率的方法。它利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率。Adam的优点主要在于经过偏置校正后，每一次迭代学习率都有个确定范围，使得参数比较平稳。

参考资料

牛顿法

牛顿法迭代公式为：
$$x_{n+1}=x_{n}-\frac{\nabla f(x_n)}{\nabla^2 f(x_n)}$$

简介牛顿法用目标函数的二阶泰勒展开近似该目标函数，通过求解这个二次函数的极小值来求解凸优化的搜索方向。
优缺点：
1. 优点从：收敛速度快。从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径
2. 缺点：牛顿法每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。（改进：拟牛顿法）

参考资料

拟牛顿法

拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。

重要知识点

牛顿法和梯度下降法有什么不同
1. 梯度下降法用目标函数的一阶偏导、以负梯度方向作为搜索方向，只考虑目标函数在迭代点的局部性质；
2. 牛顿法同时考虑了目标函数的一、二阶偏导数，考虑了梯度变化趋势，因而能更合适的确定搜索方向加快收敛，但牛顿法也存在以下缺点：1)对目标函数有严格要求，必须有连续的一、二阶偏导数，海森矩阵必须正定；2)计算量大，除梯度外，还需计算二阶偏导矩阵及其逆矩阵。
梯度下降法找到的一定是下降最快的方向么？
1. 梯度下降法并不是下降最快的方向，它只是目标函数在当前的点的切平面（当然高维问题不能叫平面）上下降最快的方向。在practical implementation中，牛顿方向（考虑海森矩阵）才一般被认为是下降最快的方向，可以达到superlinear的收敛速度。

机器学习基础

特征

特征选择和降维
1. 特征选择：原有特征选择出子集，不改变原来的特征空间，包括以下方法：
  1. 过滤式（Filter方法）：过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关
  2. 包裹式（Wrapper方法）：包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。
  3. 嵌入式（Embedded方法）：在学习器训练过程中自动地进行了特征选择。主要方法：正则化
2. 降维：将原有的特征重组成为包含信息更多的特征，改变了原有的特征空间。主要包括：
  1. 主成分分析算法（PCA）：PCA是最常用的线性降维方法，它的目标是通过某种线性投影，将高维的数据映射到低维的空间中表示，并期望在所投影的维度上数据的方差最大，以此使用较少的数据维度，同时保留住较多的原数据点的特性。
  2. LDA：LDA是为了使得降维后的数据点尽可能地容易被区分，即同类的数据点尽可能的接近（within class），不同类的数据点尽可能的分开（between class）
  3. 局部线性嵌入（LLE）：是一种非线性降维算法，它能够使降维后的数据较好地保持原有流形结构。
  4. Laplacian Eigenmaps 拉普拉斯特征映射：它的直观思想是希望相互间有关系的点（在图中相连的点）在降维后的空间中尽可能的靠近。Laplacian Eigenmaps可以反映出数据内在的流形结构。
  5. 参考资料：http://blog.csdn.net/xbinworld?viewmode=contents
对特征工程的理解：特征工程是一种将原始数据转化为能更好地表现预测模型本质问题的特征，使模型对没见过的数据能取得更好的预测效果。一般特征工程包括：
1. 数据处理：包括统一量纲（归一化、标准化等），虚拟变量（离散型的数据转化为连续型的数据），缺失值填充（数据补齐、删除缺失行）
2. 特征选择：数据中可能存在不相关的特征，特征之间也可能存在相互依赖，容易导致如下的后果：特征个数越多，分析特征、训练模型所需的时间就越长。特征个数越多，容易引起“维度灾难”。特征选择能剔除不相关(irrelevant)或亢余(redundant)的特征，从而达到减少特征个数，提高模型精确度，减少运行时间的目的。另一方面，选取出真正相关的特征简化了模型，使研究人员易于理解数据产生的过程。
3. 维度压缩：减少数据集的维度的同时，包含信息更多的信息。
4. 特征构建：从原始数据中人造新特征，要求在样本数据上花费大量的时间并且思考问题的本质，以及怎么最好的在预测模型中利用他们。
过拟合：学习器学习能力过强，在训练集上过度学习，导致模型在训练集表现好，在真实数据表现不好，即模型的泛化能力不够。从另外一个方面来讲，模型在达到经验损失最小的时候，模型复杂度较高，结构风险没有达到最优。可以通过以下方式解决：
1. 降维、特征选择
2. 正则化
3. 早停
4. 增加训练样本
5. 交叉验证
6. dropout
正则化：正则化是在模型求解目标函数时引入约束项，用于控制模型的复杂度。换种说法：正则化等价于结构风险最小化，通过在经验风险后面加上表示模型复杂度的正则化项或惩罚项，达到选择经验风险和结构风险都较小的模型的目的。比较常用的是L1正则与L2正则。
1. L1 与 L2 正则的区别:
  1. L1正则假设参数的先验分布是Laplace分布，可以保证模型的稀疏性，也就是某些参数等于0；
  2. L2正则假设参数的先验分布是Gaussian分布，可以保证模型的稳定性，也就是参数的值不会太大或太小
  3. 在实际使用中，如果特征是高维稀疏的，则使用L1正则；如果特征是低维稠密的，则使用L2正则。
2. 为何L1产生稀疏特征：L1和L2都是规则化的方式，我们将权值参数以L1或者L2的方式放到代价函数里面去。然后模型就会尝试去最小化这些权值参数。而这个最小化就像一个下坡的过程，L1和L2的差别就在于这个“坡”不同，如下图：L1就是按绝对值函数的“坡”下降的，而L2是按二次函数的“坡”下降。所以实际上在0附近，L1的下降速度比L2的下降速度要快。所以会非常快得降到0。因此L1偏向稀疏特征（可筛选出重要特征）。
有监督学习和无监督学习：
1. 有监督学习：对具有概念标记（分类）的训练样本进行学习，以尽可能对训练样本集外的数据进行标记（分类）预测。如：决策树、神经网络、线性回归等。
2. 无监督学习：对没有概念标记（分类）的训练样本进行学习，以发现训练样本集中的结构性知识。这里，所有的标记（分类）是未知的。因此，训练样本的岐义性高。聚类就是典型的无监督学习。
判别模型与生成模型：
1. 区别：
  1. 判别模型：寻找不同类别之间的最优分类面，反映的是异类数据之间的差异，估计的是条件概率分布: $P(y|x)$。
  2. 生成模型：对后验概率建模，从统计的角度表示数据的分布情况，能够反映同类数据本身的相似度，估计的是联合概率分布（joint probability distribution: P(x, y)
2. 优缺点：
  1. 判别模型：
    1. 优点：
      1. 分类边界更灵活，比使用纯概率方法或生产模型得到的更高级。
      2. 能清晰的分辨出多类或某一类与其他类之间的差异特征
      3. 在聚类、viewpoint changes, partial occlusion and scale variations中的效果较好
      4. 适用于较多类别的识别
      5. 判别模型的性能比生成模型要简单，比较容易学习
    2. 缺点：
      1. 不能反映训练数据本身的特性。能力有限，可以告诉你的是1还是2，但没有办法把整个场景描述出来。
      2. 黑盒操作: 变量间的关系不清楚，不可视
  2. 生成模型：
    1. 优点：
      1. 实际上带的信息要比判别模型丰富
      2. 研究单类问题比判别模型灵活性强
      3. 模型可以通过增量学习得到
      4. 能用于数据不完整（missing data）情况
    2. 缺点：
      1. 学习和计算过程比较复杂
3. 常见模型：
  1. 判别模型：线性回归、对数回归、线性判别分析、支持向量机、 boosting、条件随机场、神经网络等
  2. 生成模型：隐马尔科夫模型、朴素贝叶斯模型、高斯混合模型、 LDA
模型优缺点
数据不均衡问题：
1. 过采样或欠采样：
  1. 随机欠采样：目标是通过随机地消除占多数的类的样本来平衡类分布；直到多数类和少数类的实例实现平衡，目标才算达成。
    1. 优点：它可以提升运行时间；并且当训练数据集很大时，可以通过减少样本数量来解决存储问题。
    2. 缺点：它会丢弃对构建规则分类器很重要的有价值的潜在信息。被随机欠采样选取的样本可能具有偏差。它不能准确代表大多数。从而在实际的测试数据集上得到不精确的结果。
  2. 随机过采样（Over-Sampling）：通过随机复制少数类来增加其中的实例数量，从而可增加样本中少数类的代表性。
    1. 优点：与欠采样不同，这种方法不会带来信息损失。表现优于欠采样。
    2. 缺点：由于复制少数类事件，它加大了过拟合的可能性。
  3. 基于聚类的过采样：使用K-均值聚类算法识别数据集中的聚类。随后，对每一个聚类过采样，使聚类拥有相同的实例数量。
    1. 优点：这种聚类技术有助于克服类之间不平衡的挑战。有助于克服由不同子聚类组成的类之间的不平衡的挑战。每一个子聚类不包含相同数量的实例。
    2. 缺点：可能过拟合
  4. 信息性过采样：合成少数类过采样技术（SMOTE）：通过插值的方式创建相似的新合成的实例，可以避免直接复制少数类实例带来的过拟合问题。
    1. 优点：可以缓解过拟合的问题。不会损失有价值信息。
    2. 缺点：当生成合成性实例时，SMOTE并不会把来自其他类的相邻实例考虑进来，这导致了类重叠的增加，并会引入额外的噪音。并且，SMOTE 对高维数据不是很有效。
  5. 改进的合成少数类过采样技术（MSMOTE）：该算法将少数类别的样本分为3个不同的组：安全样本、边界样本和潜在噪声样本。该算法是从安全样本出发随机选择k-最近邻的数据点，并从边界样本出发选择最近邻，并且不对潜在噪声样本进行任何操作。
2. 选用合适评价函数
3. 代价敏感学习
4. 使用集成学习方法
异常点检测：
1. 基于距离离群检测（聚类）：考虑给定样本的一定距离内样本点个数小于一个阈值，则是离群点
2. 基于密度的离群检测：离群点周围的密度显著不同于其邻域周围的密度
3. 基于统计方法的离群点检测：一般根据样本分布给出概率分布模型，一般也可假设样本呈正态分布，绘制样本箱型图（依据四分位极差）判断离群点
4. 孤立森林、one class SVM
5. 参考： https://www.jianshu.com/p/ac6418ee8e3f

评价指标

错误率与精度：错误率是分类错误的样本数占样本总数的比例，精度则是分类正确的样本数占样本总数的比例
查准率、查全率与F1：
1. 查准率 $P={TP\over TP+FP}$ ：在所有被分类为正例的样本中，真正是正例的比例。
2. 查全率 $R={TP\over TP+FN}$ ：实际为正例的样本中，被预测为正例的样本比例。
3. $F1={2\times P\times R\over P+R}={2\times TP\over D+TP-TN}$ ：F1是基于查准率与查全率的调和平均（harmonic mean）定义的。
ROC 与 AUC：
1. ROC ：我们对预测结果按大小排序，将每个概率值依次作为阈值，得到多个混淆矩阵。对于每个混淆矩阵，我们计算两个指标TPR（真阳性率：True positive rate）和FPR（伪阳性率：False positive rate），以伪阳性率为x轴，真阳性率为y轴画图，就得到了ROC曲线。
2. AUC：AUC是一个模型评价指标，只能用于二分类模型的评价，其值等于ROC曲线下的面积。AUC常常被用来作为模型排序好坏的指标，原因在于AUC可以看做随机从正负样本中选取一对正负样本，其中正样本的得分大于负样本的概率！AUC相较于查准率、查全率的特点是：当数据集正负样本不平衡时，ROC曲线能保持相对的稳定，但查准率、查全率会出现较大的变化。
类别不均衡问题：类别不均衡是指在分类学习算法中，不同类别样本的比例相差悬殊，它会对算法的学习过程造成重大的干扰。在类别不均衡时，准确度这个评价指标并不能work，甚至误导分类器。

距离的度量

欧式距离：$d = \sqrt{\sum _ {i=1}^N(x _ {1i}-x _ {2i})^2}$
1. 缺点：每个坐标对欧氏距离的贡献是同等的。它将样品的不同属性（即各指标或各变量）之间的差别等同看待，这一点有时不能满足实际要求。
马氏距离：$\sqrt{(x-u _ x)^T\Sigma^{-1}(y-u _ y)}$，其中$\Sigma$为协方差，计算公式为$E(XY)-E(X)E(Y)$
1. 优点：它不受量纲的影响，两点之间的马氏距离与原始数据的测量单位无关。它考虑到各种特性之间的联系，并且是尺度无关的
2. 缺点：夸大了变化微小的变量的作用。受协方差矩阵不稳定的影响，马氏距离并不总是能顺利计算出。

偏差与方差

$$E(f;D)=bias^2(x)+var(x)+\epsilon^2$$
泛化误差为偏差方差与噪声之和。

偏差度量了学习算法的期望预测与真实结果的偏离程度，即刻画了学习算法本身的拟合能力。
$$bias^2(x)={(\overline{f}(x)-y)^2}$$
方差度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响。
$$var(x)=\mathbb{E}_D\big[(f(x;D)-\overline{f}(x))^2\big]$$
噪声则表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界，即刻画了学习问题本身的难度。
$$\epsilon^2=\mathbb{E}_D\big[(y_D-y)^2\big]$$

偏差方差窘境

机器学习之模型评估/error.png

假如学习算法训练不足时，这个时候偏差主导了算法的泛化能力。
随着训练的进行，学习器的拟合能力逐渐增强，偏差逐渐减小，但此时通过不同数据学习得到的学习器就可能会有较大的偏差，即此时的方差会主导模型的泛化能力。
若学习进一步进行，学习器就可能学到数据集所独有的特征，而这些特征对于其它的数据是不适用的，这个时候就是发生了过拟合。

在线算法

在线学习实际上就是每来一个/批样本增量更新一次，主要有两类：

基于贝叶斯公式，这种更新方式非常自然。有名的应用包括微软的MatchBox，以及其在广告点击率上的应用，具体的paper名字大概是web-scale ctr prediction
基于sgd的方法，基于梯度优化的算法大都可以应用。这一类方法有很多变种，大多数是加速sgd的收敛速度，以及减少调参对收敛的影响，神经网络的训练基本都是此类方法。另外google有一篇文章Ad Predictor，算是把ctr预估的方向指向实时更新了其他还有一些online的方法，不过往往需要各种trick,比如近邻法，因为这类方法是非参数模型
基于kernel(非线性)的方法则不能online，虽然可以每来一个样本就更新一次，但是必须把之前看所有的数据都保存下来来构建kernel matrix，这样空间需求会越来越大。
总结如下：logistic regression, linear svm, 神经网络