算法入门

作者: amyhy | 来源:发表于2020-05-28 16:36 被阅读0次

1、特征工程

归一化

方法：(1)Min-Max: $X_{norm}=\frac{X-X_{min}}{X_{max}-X_{min}}$ ；(2)Z-Score: $Z=\frac{x-\mu}{\sigma}$
意义：归一化让不同特征映射到相同的数值区间内，使得不同特征的更新速度变得更为一致，容易更快地通过梯度下降找到最优解，对于某些不使用梯度下降法优化的模型，例如决策树，则不需要归一化

类别型特征处理

序号编码：用于处理类别间具有大小关系的数据，按照大小关系赋予一个数值ID，转换后依旧保留了大小关系
one-hot编码：用于处理类别间不具有大小关系的特征，对于一个有n种取值的类别特征，独热编码会给每个类别建立一个n维向量，该类别对应的维度值为1，其余n-1维值为0。需要注意：(1)使用稀疏向量来节省空间；(2)配合特征选择来降低维度
二进制编码：先用序号编码给每个类别赋予一个类别ID，再讲类别ID对应的二进制编码作为结果。本质上是利用二进制对ID进行hash映射，最终得到0/1特征向量，且维度少于one-hot编码，节省了存储空间

组合特征

定义：将一阶离散特征两两组合，形成高阶的组合特征。一个类别数量为n的一阶特征和一个类别数量为m的一阶特征组合，可以组成 $n\times m$ 个组合特征。
高维组合特征处理：当组合特征学习规模 $n\times m$ 量级很大时，机器几乎无法处理学习任务，此时需要将高维组合特征的两个维度都进行降维，映射到远小于 $n、m$ 的 $k$ 维空间中，此时参数的学习规模变为 $m\times k+n\times k$
寻找特征组合：使用一阶特征构造决策树，每一条从根节点到叶子节点的路径都可以看做一种特征组合的方式。

文本表示模型

词袋模型和N-gram模型：每篇文章表示成一个长向量，向量中的每一维代表一个单词，该维度对应的权重反映了这个词在原文章中的重要程度。权重的常用计算方式是TF-IDF $(t,d)$ =TF $(t,d)\times$ IDF $(t)$ ，TF $(t,d)$ 为单词 $t$ 在文档 $d$ 中出现的频率，逆文档频率IDF $(t)=log\frac{文章总数}{包含单词t的文章总数+1}$ ，对于在非常多文章里出现的通用词汇，区分特殊语义贡献较小，需要通过逆文档频率对权重做惩罚。为了解决连续出现和单独出现具有不同含义的情况，可以将连续出现的n个词组成词组(N-gram)也作为一个单独的特征放到向量表示中去，构成N-gram模型；为了解决同一个词的多种词性变化，可以对单词进行次干抽取处理，将不同词性的单词统一成为同一词干的形式。
主题模型：用于从文本库中发现有代表性的主题，能够计算出每篇文章的主题分布。
词嵌入模型与Word2Vec：词嵌入模型指将每个词都映射成低维空间（通常50～300维）上的稠密向量的词向量化模型。目前最常用的词嵌入模型是Word2Vec，它是一种浅层的神经网络，对“上下文-单词”矩阵进行学习，包含了两种由输入层、映射层和输出层组成的神经网络：CBOW根据输入的上下文出现的词语来预测当前词的生成概率；Skip-gram根据当前词来预测上下文中各词的生成概率。输入层的每一个词是独热编码的N维向量（N是词汇表单词总数），映射层含有K个隐含单元，输出层是一个N维向量，每个维度与单词表中的一个单词对应，最后对输出层向量应用Softmax激活函数： $P(y=w_n|x)=\frac{e^{x_n}}{\sum_{k=1}^N e^{x_k}}$ 计算出每个单词的生存概率。经过训练可以得到权重矩阵，使得语料库中所有单词的整体生存概率最大化。

图像数据不足时的处理方法

基于模型：降低过拟合风险，包括简化模型、添加约束项以缩小假设空间、集成学习、Dropout超参数等
基于数据：数据扩充，包括一定程度内随机旋转、平移、缩放、裁剪、翻转等变换；添加噪声扰动；颜色变换；改变图像亮度，清晰度、对比度、锐度等

2、模型评估

评估指标的局限性

准确率： $Accuracy=\frac{n_correct}{n_total}$ ， $n_correct$ 为被正确分类的样本个数， $n_total$ 为总样本个数。当不同类别的样本比例非常不均衡时，占比大的类别往往成为影响准确率的最主要的因素：当负样本占90%时，分类器把所有数据都预测为负样本也可以获得很高的准确率。
精确率和召回率：Precision指分类正确的正样本个数占分类器判定为正样本个数的比例，Recall指分类正确的正样本个数占真正正样本个数的比例，二者是矛盾统一的关系：为了提高精确率，分类器需要尽量在置信度高的情形下判定样本为正，但又会同时因为标准保守而漏掉很多正样本，导致召回率降低。可以通过绘制模型P-R曲线来综合评估两方面的表现：横坐标是召回率，纵坐标是精确率，一个点代表在某一阈值下模型将大于该阈值的结果判定为正样本，此时返回结果对应的召回率和精确率；此外，表示精准率和召回率的调和平均值的F1 score： $F1=\frac{2\times precision \times recall}{precision+recall}$ 、ROC曲线也能综合反映模型的性能。
平方根误差：一般情况下，RMSE能很好地反映回归模型预测值和真实值的偏离程度，但如果存在个别偏离程度非常大的离群点时，即使离群点数量很少，也会让RMSE指标变得很差。解决方法是：如果离群点为噪声，则预处理阶段需要过滤掉；如果离群点不是噪声，则需要提高模型预估能力，对离群点机制进行建模；采用平方绝对百分比误差来衡量模型： $MAPE=\sum_{i=1}^n |\frac{y_i-\hat{y_i}}{y_i}|\times \frac{100}{n}$ ，该指标相当于把每个点的误差进行归一化，降低了离群点带来的绝对误差的影响。

ROC曲线

ROC曲线（受试者工作特征曲线）的横坐标为假阳性率（分错的负样本占所有负样本比率），纵坐标为真阳性率（分对的正样本占所有正样本比率）。通过动态地调整分类模型的分类阈值，可以在ROC图上绘制出每一个分类阈值对应的两个坐标值，再连接所有点绘制出模型的ROC曲线。AUC指ROC曲线下面积的大小，该指标能够量化地反映基于ROC曲线的模型性能，AUC的取值一般都在0.5～1之间，值越大，说明分类器越可能把真正的正样本排在前面，分类性能越好。相比较P-R曲线，ROC曲线在正负样本的分布发生变化时，形状能够基本保持不变，而P-R曲线一般会发生较剧烈的变化，这个特点可以使得ROC曲线能够尽量降低不同测试集带来的干扰，更加客观地衡量模型本身的性能。在实际中，正负样本数量往往不均衡，因此ROC曲线的适用场景更广泛。

余弦距离的应用

采用余弦相似度的场景：欧式距离体现数值上的绝对差异，余弦距离（1-余弦相似度）体现方向上的相对差异。余弦相似度在高维情况下依然保持“相同为1,正交为0,相反为-1”的性质，而欧式距离的数值受到维度的影响，范围不固定且定义模糊。在关注相对差异的场景下，采用余弦距离，例如：文本、图像、视频等高维特征领域。
余弦距离是否是一个严格定义的距离：严格定义的距离满足三条距离公理：正定性、对称性、三角不等式。余弦距离满足正定性和对称性，但不满足三角不等式（反例法：A(1,0), B(1,1), C(0,1)），所以不是一个严格定义的距离。

A/B测试的陷阱

A/B测试的原因：离线评估无法完全消除模型过拟合的影响，得出的离线评估结果无法完全替代线上评估结果；离线评估无法完全还原线上的工程环境，例如延迟、数据丢失、标签数据缺失等情况；线上系统的某些商业指标在离线评估中无法计算，例如算法带来的点击率、留存时长、PV等变化。
如何进行A/B测试：主要手段是用户分桶，将用户分成实验组（新模型）和对照组（旧模型），注意样本的独立性和采样方式的无偏性，确保同一个用户每次只能分到同一个桶中，采用随机的user_id来确保桶中的样本是无偏的。

模型验证方法

Holdout检验：将原始样本随机划分成训练集和测试集两部分，例如按照7：3比例划分。缺点是在验证集上计算出来的评估指标和原始分组有很大关系。
交叉检验：消除样本划分随机性的方法，K-fold交叉验证：将全部样本分成K个大小相等的样本子集，依次遍历每个子集，每次把当前子集当作验证集，其余子集作为训练集，进行模型训练和评估，最后把K次的评估指标的平均值作为最终评估指标；留一验证：每次留下1个样本作为验证集，其余所有样本作为训练集，依次遍历每个样本，留一验证时间开销比较大，实际应用很少。
自助检验：在样本规模较小时使用，对于总数为n的样本集合，进行n次有放回的随机抽样，得到大小为n的训练集，将没有被抽出的样本作为验证集。当样本数量趋于无穷时，有 $\frac{1}{e}\approx 36.8%$ 的样本从未被选择过，可以用于验证。

超参数调优

网格搜索：通过查找搜索范围内所有的点来确定最优参数值。在实际应用中，一般会先使用较广的搜索范围和较大的步长来寻找全局最优值可能的位置，再逐渐缩小搜索范围和步长来寻找更精确的最优值。这种操作方案可以降低所需的时间和计算量，但是由于目标函数一般非凸，很可能会错过全局最优。
随机搜索：在搜索范围内随机选取样本点。原理是如果样本点集足够大，通过随机采样也可以大概率找到全局最优点，随机搜索速度比网格搜索快，但是结果也是没法保证。
贝叶斯优化算法：充分利用之前采样的信息，通过对目标函数形状进行学习，找到使目标函数向全局最优值提升的参数。根据先验分布假设一个搜索函数，每一次使用新采样点测试目标函数时利用这个信息来更新目标函数的先验分布，最后算法测试由后验分布给出的全局最优值最可能出现的位置的点。需要注意的是，一旦找到了一个局部最优，算法会在该区域不断采样，很容易陷入局部最优值。为了弥补这个缺陷，贝叶斯优化算法会在探索未采样区域和利用后验分布之间找到一个平衡点。

过拟合和欠拟合

定义：过拟合是指模型对于训练数据拟合程度超过测试数据和新数据，在训练集上表现优秀，在测试集和新数据上表现很差；欠拟合是指模型对于训练数据拟合较差，在训练集和测试集上都表现很差。
降低过拟合风险的方法：获取更多的训练数据，可以通过一定规则扩充训练数据（例如生成对抗网络合成）；降低模型复杂度；正则化方法，加上正则约束；采用集成学习，降低单一模型的过拟合风险
降低欠拟合风险的方法：添加新的特征，可以采用因子分解机、GBDT、Deep-crossing等方式完成特征工程；增加模型复杂度；减小正则化系数

3、经典算法

SVM

空间上线性可分的两类点向SVM分类的超平面上做投影，这些点在超平面上的投影是否线性可分？

对于任意线性可分的两组点，它们在SVM分类的超平面上的投影都是线性不可分的。由于SVM的分类超平面仅由支持向量决定，可以考虑只含有支持向量的场景：假设存在一个SVM超平面满足投影线性可分，则样本中分属两类的支持向量之间的中垂线所组成的超平面是相较于SVM超平面更优的解，这与SVM超平面为最优分类超平面的假设相违背。

SVM的KKT条件： $\begin{cases}\nabla_\omega L(\omega^*,\beta^*,\alpha^*)=\omega^*-\sum_{i=1}^N\alpha_i^*y_ix_i=0& & (1)\\ \nabla_\beta L(\omega^*,\beta^*,\alpha^*)=-\sum_{i=1}^N\alpha_i^*y_i=0& & (2)\\\alpha_i^*g_i(\omega^*)=0, i=1,...,N& & (3)\\g_i(\omega^*)\leq0,i=1,...,N& & (4)\\\alpha_i^*\geq0, i=1,...,N& & (5)\\\end{cases}$

结合(3)和(4)，当 $g_i(\omega^*)<0$ 时，必有 $\alpha_i^*=0$ ，将这一结果与拉格朗日对偶优化问题的公式相比较： $L(\omega^*,\beta^*,\alpha^*)=\frac{1}{2}\omega^{*2}+\sum_{i=1}^N\alpha_i^*g_i(\omega^*)$ ，其中 $g_i(\omega^*)=-y_i(\omega^*\cdot x_i+\beta^*)+1$ 。除了支持向量之外，其他系数均为0，因此SVM的分类结果仅依赖于支持向量，SVM的分类结果与仅使用支持向量的分类结果一致。

该问题也可以通过凸优化理论中的超平面分离定理解决。

是否存在使SVM训练误差为0的一组参数?（高斯核，给定训练集不存在两点在同一位置）

高斯核SVM的预测公式为： $f(x)=\sum_{i=1}^m\alpha_iy^{(i)}K(x^{(i)},x)+b$ ，固定 $\alpha_i=1，b=0$ ，则有 $f(x)=\sum_{i=1}^my^{(i)}K(x^{(i)},x)=\sum_{i=1}^my^{(i)}exp(-\parallel x-x^{(i)}\parallel^2/\gamma^2)$ 。由于不存在两个点在同一位置，则对于任意点 $i\neq j$ ，有 $\parallel x^{(j)}-x^{(i)}\parallel \geq \epsilon$ .

对于任意 $x^{(j)}$ ，取 $\gamma=\epsilon/\sqrt{logm}$ ，有 $\parallel f(x^{(j)})-y^{(j)}\parallel=\parallel\sum_{i=1,i\neq j}^my^{(i)}exp(-\parallel x^{(j)}-x^{(i)}\parallel^2/\gamma^2)\parallel \leq \parallel\sum_{i=1,i\neq j}^mexp(-\parallel x^{(j)}-x^{(i)}\parallel^2/\gamma^2) \parallel \leq \parallel\sum_{i=1,i\neq j}^mexp(-logm)\parallel=\frac{m-1}{m}<1$

所以，对于任意 $x^{(j)}$ ，预测结果 $f(x^{(j)})$ 与真实标签的距离小于1，所有样本的类别都被正确预测，训练误差为0.

是否存在训练误差为0的SVM分类器?

本题等价于找到使训练误差为0的参数，且是SVM模型的一个解。上述所找到的参数可以满足 $y^{(j)}f(x^{(j)})>0$ ，若想成为SVM的解，还需要满足 $y^{(j)}f(x^{(j)})\geq 1$ 。

仍然固定 $b=0$ ，则有 $y^{(j)}f(x^{(j)})=\alpha_j+\sum_{i=1,i\neq j}^m \alpha_iy^{(i)}y^{(j)}K(x^{(i)},x^{(j)})$ . 此时可以把每个 $\alpha_j$ 都选择一个很大的值，同时取一个非常小的 $\gamma$ ，使得核映射项 $K(x^{(i)},x^{(j)})$ 非常小，就可以满足题意。

加入松弛变量后，SVM的训练误差是否可以为0?

不一定能得到训练误差为0的模型，因为此时优化的目标改变了，当松弛变量模型目标函数参数C选取较小的值时，正则项将占据优化的较大比重，此时一个带有训练误差但是参数较小的点将成为更优的结果。

LR

逻辑回归与线性回归

如果把一个事件的几率定义为该事件发生与该事件不发生的概率比值，根据逻辑回归的公式 $log\frac{p}{1-p}=\theta^Tx p=P(y=1|x)$ ，逻辑回归可以看作是对于事件"y=1|x"的对数几率的线性回归，所以有回归的名称。但是逻辑回归的因变量是离散的，处理的是分类问题；线性回归中的因变量是连续的，处理的是回归问题。逻辑回归与线性回归的相似处是：都使用了极大似然估计，线性回归的最小二乘实际上是自变量和超参数确定、因变量服从正态分布的假设下使用极大似然估计的一个化简，逻辑回归中通过对似然函数的学习来得到最佳超参数；二者在求解超参数的过程中，都可以使用梯度下降法。

逻辑回归处理多标签分类

如果一个样本只对应于一个标签，可以假设每个样本属于不同标签的概率服从于几何分布，使用多项逻辑回归(Softmax Regression)来进行分类： $h_\theta(x)=\begin{bmatrix}p(y=1|x;\theta) \\p(y=2|x;\theta)\\...\\p(y=k|x;\theta)\end{bmatrix}=\frac{1}{\sum_{i=1}^ke^{\theta^T_ix}}\begin{bmatrix}e^{\theta^T_1x} \\e^{\theta^T_2x}\\...\\e^{\theta^T_kx}\end{bmatrix}$
当存在样本可能属于多个标签的情况时，可以训练k个二分类的逻辑回归分类器，第i个分类器用于区分每个样本是否可以归为第i类。

决策树

决策树的启发函数

ID3——最大信息增益： $g(D,A)=H(D)-H(D|A), 经验熵H(D)=-\sum_{k=1}^K\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|};经验条件熵H(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)$ 。D为样本集合，K为类别数量，A为某个特征， $D_i$ 为D中特征A取第i个值的样本子集， $C_k$ 为样本集合D中属于第k类的样本子集，||表示元素个数。

C4.5——最大信息增益比： $g_R(D,A)=\frac{g(D,A)}{H_A(D)},取值熵H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}$

CART——最大基尼指数： $Gini(D)=1-\sum_{k=1}^n(\frac{|C_k|}{|D|})^2,特征A的基尼指数Gini(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}Gini(D_i)$ . CART每一次迭代选取基尼指数最小的特征及其对应的切分点进行分类，CART是一个二叉树，每一次把特征A的取值切成两份，分别进入左右子树。

ID3会倾向于选取取值较多的特征，因为信息增益反应的是给定条件以后不确定性减少的程度，特征取值越多就意味着确定性更高，也就是条件熵越小，信息增益越大，C4.5通过引入信息增益比，一定程度对取值比较多的特征进行惩罚，避免ID3出现过拟合的特性，提升模型的泛化能力；ID3只能处理离散变量，而C4.5和CART都可以处理连续变量；ID3和C4.5只能用于分类任务，CART不仅可以分类也可以用于回归；ID3和C4.5可以在每个结点上产生出多叉分支，且每个特征在层级之间不会复用，而CART每个结点只会产生两个分支，且每个特征可以被重复使用；ID3和C4.5通过剪枝来权衡树的准确性与泛化能力，而CART直接利用全部数据发现所有可能的树结构进行对比。

决策树剪枝

预剪枝：在生成决策树的过程中提前停止树的生长，方法为：达到一定深度；达到当前结点的样本数量小于某个阈值；计算每次分裂对测试集的准确度的提升，当小于某个阈值时不再扩展。预剪枝效率高，适合解决大规模问题，但是有欠拟合的风险。

后剪枝：在已经生成的过拟合决策树上进行剪枝，常见的方法有：错误率降低剪枝REP、悲观剪枝PEP、代价复杂度剪枝CCP、最小误差剪枝MEP、CVP、OPP等方法。

4、降维

PCA

原理：提取可以表达数据的主要维度(主轴)，主轴的特征是数据在此的分布的方差最大，即PCA的目标为让数据在主轴上投影的方差最大化。

对于给定的一组数据点 $\{v_1,v_2,...,v_n\}$ ，中心化后表示为 $\{x_1,x_2,...,x_n\}=\{v_1-\mu,v_2-\mu,...,v_n-\mu\}$ ，其中 $\mu=\frac{1}{n}\sum_{i=1}^n v_i$ ，目标是找到一个投影方向 $\omega$ (单位方向向量)使数据点在其上的投影方差尽可能大。投影之后的均值： $\mu'=\frac{1}{n}\sum_{i=1}^n x_i^T\omega=\vec{0}\omega=0\\$ 投影之后的方差(均值为0，直接平方)： $D(x)=\frac{1}{n}\sum_{i=1}^n(x_i^T\omega)^2=\frac{1}{n}\sum_{i=1}^n(x_i^T\omega)^T(x_i^T\omega)=\frac{1}{n}\sum_{i=1}^n\omega^Tx_ix_i^T\omega=\omega^T(\frac{1}{n}\sum_{i=1}^n x_ix_i^T)\omega$ 其中， $(\frac{1}{n}\sum_{i=1}^n\omega^Tx_ix_i^T\omega)$ 是样本的协方差矩阵，将其写作 $\Sigma$ ，则有求解最大化问题： $\begin{cases}max\{\omega^T\Sigma \omega\}\\s.t. \omega^T\omega=1\\\end{cases}$ 引入拉格朗日乘子，并对 $\omega$ 求导令其等于0，可以推出 $\Sigma \omega=\lambda \omega$ ，此时 $D(x)=\omega^T\Sigma \omega=\lambda\omega^T\omega=\lambda$ 该值为协方差矩阵的最大特征值

求解方法：

(1) 对样本数据进行中心化处理

(2) 求样本协方差矩阵

(3) 对协方差矩阵进行特征值分解，将特征值从大到小排列

(4) 取特征值前 $d$ 大对应的特征向量 $\omega_1,\omega_2,...,\omega_d$ ，将 $n$ 维样本映射到 $d$ 维： $x_i'=\begin{bmatrix}\omega_1^Tx_i \\\omega_2^Tx_i\\...\\\omega_d^Tx_i \end{bmatrix}$

新的 $x_i'$ 的第 $d$ 维就是 $x_i$ 在第 $d$ 个主成分第 $\omega_d$ 方向上的投影，通过选取最大的 $d$ 个特征值对应的特征向量，将方差较小的特征抛弃，使得每个n维列向量 $x_i$ 被映射为 $d$ 维列向量 $x_i'$ 。降维后的信息占比为： $\eta=\sqrt{\frac{\sum_{i=1}^d \lambda_i^2}{\sum_{i=1}^n \lambda_i^2}}$

最小平方误差原理：将PCA与线性回归类比，将问题转化为回归问题，则PCA的目标为在高维空间中找到一个 $d$ 维超平面，使得数据点到这个超平面的距离平方和最小。

LDA

原理：数据有类别情况下的降维方法，最大化类间距离的同时最小化类内距离，使得降维后数据依旧可以区分为不同类别。

LDA的最大化目标： $max_\omega J(\omega)=\frac{\parallel\omega^T(\mu_1-\mu_2)\parallel_2^2}{D_1+D_2}$ 其中 $D_1，D_2$ 分别表示两类投影后的方差： $D_1=\sum_{x\in C_1}(\omega^Tx-\omega^T\mu_1)^2=\sum_{x\in C_1}\omega^T(x-\mu_1)(x-\mu_1)^T\omega$ 则目标函数可以写成： $J(\omega)=\frac{\omega^T(\mu_1-\mu_2)(mu_1-\mu_2)^T\omega}{\sum_{x\in C_i}\omega^T(x-\mu_i)(x-\mu_i)^T\omega}$ 定义类间散度矩阵 $S_B=(\mu_1-\mu_2)(mu_1-\mu_2)^T$ ，类内散度矩阵 $S_w=\sum_{x\in C_i}\omega^T(x-\mu_i)(x-\mu_i)^T\omega$ ，最大化 $J(\omega)$ 即是对 $\omega$ 求偏导且令其等于零： $\frac{\partial J(\omega)}{\partial\omega}= \frac{(\frac{\partial\omega^TS_B\omega}{\partial\omega}\omega^TS_w\omega-\frac{\partial\omega^TS_w\omega}{\partial\omega}\omega^TS_B\omega)}{(\omega^TS_w\omega)^2}=0$ 可以得出 $(\omega^TS_w\omega)S_B\omega=(\omega^TS_B\omega)S_w\omega$ 在简化的二分类问题中，可以令 $\lambda=J(\omega)=\frac{\omega^TS_B\omega}{\omega^TS_w\omega}$ ，则有 $S_w^{-1}S_B\omega=\lambda\omega$ 这里LDA最大化的目标对应了矩阵 $S_w^{-1}S_B$ 的特征值，而投影方向就是这个特征值对应的特征向量。

求解方法：

(1) 计算数据集中每个类别样本的均值向量 $\mu_j$ ，总体均值向量 $\mu$

(2) 计算类内散度矩阵 $S_w$ ，全局散度矩阵 $S_t$ ，并得到类间散度矩阵 $S_b=S_t-S_w$

(3) 对矩阵 $S_w^{-1}S_b$ 进行特征值分解，将特征值从大到小排列

(4) 取特征值前 $d$ 大对应的特征向量 $\omega_1,\omega_2,...,\omega_d$ ，将 $n$ 维样本映射到 $d$ 维： $x_i'=\begin{bmatrix}\omega_1^Tx_i \\\omega_2^Tx_i\\...\\\omega_d^Tx_i \end{bmatrix}$

二者比较

PCA为无监督降维算法，LDA为有监督降维算法，两种降维算法的求解过程有很大的相似性，但是对应的原理却有所区别：PCA选择投影后数据方差最大的方向，由于算法无监督，PCA假设方差越大信息量越多，用主成分来表示原始数据可以去除冗余的维度，达到降维；LDA用到了类别标签的信息，选择投影后类内方差小、类间方差大的方向，使得原始数据在这些方向上投影后不同类别尽可能区分开。应用的原则是无监督任务使用PCA，有监督任务使用LDA。

5、非监督学习

K-Means

K均值算法的具体步骤

(1) 数据预处理，如归一化、离群点处理等

(2) 随机选取K个簇中心，记为 $u_1^{(0)},u_2^{(0)},...,u_k^{(0)}$

(3) 定义代价函数： $J(c,u)=min_u min_c\sum_{i=1}^M \parallel x_i-u_{c_i}\parallel ^2$

(4) 令 $t=0,1,2,...为迭代步数，$ 重复下面过程直到J收敛：

对于每一个样本 $x_i$ ，将其分配到距离最近的簇： $c_i^{t}\gets argmin_k \parallel x_i-u_k^{(t)}\parallel ^2$ ;

对于每一个类簇 $k$ ，重新计算该类簇的中心： $u_k^{t+1}\gets argmin_u \sum_{i:c_i^{(t)}=k} \parallel x_i-u\parallel ^2$

K均值算法的优缺点

优点：对于大数据集，K均值聚类算法相对是可伸缩和高效的，它的计算复杂度是 $O(NKt)$ 接近于线性，其中 $N$ 是数据对象的数目， $K$ 是聚类的簇数， $t$ 是迭代的轮数；尽管算法经常以局部最优结束，但一般情况下达到局部最优已经可以满足聚类的需求

缺点：需要人工预先确定初始K值，且该值和真实的数据分布未必吻合；受初值和离群点的影响，每次的结果不稳定；结果通常不是全局最优而是局部最优解，效果受到初始值影响；无法良好地解决数据簇分布差别比较大的情况（比如一类是另一类样本数量的100倍）；不太适用于离散分类；样本点只能被划分到单一的类中

K均值算法的调优

(1) 数据归一化和离群点处理：K均值本质上是一种基于欧式距离度量的数据划分方法，均值和方差大的维度将对数据的聚类结果产生绝对性的影响，所以未做归一化处理和统一单位的数据是无法直接参与运算和比较的；离群点和少量噪声对均值产生较大影响使中心偏移

(2) 合理选择K值：手肘法：随着K值增大，损失函数值减小，在某一个K值处图像出现手肘一样的拐点，之后损失函数变化平缓，该拐点为最佳K值；适合自动批量化的Gap Statistic方法：将损失函数定义为 $D_k$ ，则有 $Gap(K)=E(logD_k)-logD_k$ ，期望 $E(logD_k)$ 通过蒙特卡洛模拟产生，在样本所在区域内按照均匀分布随机地产生和原始样本数一样多的随机样本，并对这个随机样本做K均值，得到一个 $D_k$ ，重复多次可得 $E(logD_k)$ 的近似值

(3) 采用核函数：传统的欧式距离本质假设了各个数据簇的数据具有一样的先验概率，并呈现球形或者高维球形分布，这种分布在实际生活中并不常见。面对非凸的数据分布形状时，需要引入核函数来优化：核K均值算法，是核聚类方法的一种。核聚类方法的主要思想是通过一个非线性映射，将输入空间中的数据点映射到高位的特征空间中，并在新的特征空间中进行聚类，增加了数据点线性可分的概率

K均值算法改进模型

K-means++算法(初始值优化)：假设已经选取了n个初始聚类中心，则在选取第n+1个聚类中心时，距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心。在选取第一个聚类中心时同样通过随机的方法

ISODATA算法(簇值优化)：当属于某个类别的样本数过少时，把该类别去除；当属于某个类别的样本数过多、分散程度较大时，把给类别分成两个子类别。该算法在K均值算法的基础上增加了两个操作：分裂操作增加聚类中心数；合并操作减少聚类中心数

K均值算法的收敛性证明：K均值聚类的迭代算法实际上是一种EM(最大期望)算法，解决的是在概率模型中含有无法观测的隐含变量情况下的参数估计问题。可以通过EM算法的收敛性证明K均值算法的收敛性。

高斯混合模型

原理：假设不同类别服从不同的高斯分布，数据可以看作从多个高斯分布中生成出来的。在该假设下，每个单独的分模型都是标准高斯模型，其均值 $\mu_i$ 、方差 $\sum_i$ 和权重 $\pi_i$ 是待估计的参数，公式为： $p(x)=\sum_{i=1}^K \pi_iN(x|\mu_i,\sum_i)$ 。
迭代计算方式：高斯混合模型是生成式模型，通常通过最大似然估计来求解，但是此类问题使用最大似然会得到一个复杂的非凸函数，故采用EM算法框架来求解该优化问题：

初始随机选择各参数的值，然后重复下述两步直至收敛(参数不再变化/变化很小)：

E步骤：根据当前参数，计算每个点由某个分模型生成的概率

M步骤：使用E步骤估计出的概率来改进每个分模型的三个参数

与K均值算法异同：都需要指定K值，都使用EM算法求解，都往往只能收敛于局部最优；相比较K均值算法，高斯混合模型可以给出一个样本属于某类的概率是多少，不仅可以用于聚类也可以用于概率密度估计，还可以用于生产新的样本点

自组织映射神经网络(聚类、高维可视化、数据压缩、特征提取)

SOM原理：假设输入空间是D维，N是神经元的总数，输入模式为 $x=\{x_i,i=1,...,D\}$ ，输入单元i和神经元j之间在计算层的连接权重为 $w=\{w_{i,j},j=1,...,N,i=1,...,D\}$ ，SOM的学习过程为：

(1)用小的随机量初始化 $w$

(2)竞争：神经元计算每一个输入模式各自的判别函数值，并宣布具有最小判别函数值的特定神经元为胜利者。其中，每个神经元j的判别函数为 $d_j(x)=\sum_{i=1}^D(x_i-w{i,j})^2$

(3)合作：获胜神经元 $I(x)$ 决定了兴奋神经元拓扑领域的空间位置：确定激活节点 $I(x)$ 之后，按照与激活节点距离远近的关系更新其他神经元，计算为： $T_{j,I(x)}(t)=exp(-\frac{S_{j,I(x)}^2}{2\delta(t)^2})$ ，其中 $S_{ij}$ 表示竞争层神经元i和j之间的距离， $\delta(t)=\delta_0 exp(-\frac{t}{\tau_\delta})$ 随时间衰减。简单来说，临近的节点距离越远，更新的程度要打更大折扣

(4)适应：适当调整相关兴奋神经元的连接权重，增强获胜的神经元对相似输入模式的后续应用的响应： $\Delta w_{ji}=\eta(t)\cdot T_{j,I(x)}(t)\cdot(x_i-w_{ji})$ ，其中依赖于时间的学习率定义为： $\eta(t)=\eta_0exp(-\frac{t}{\tau_\eta})$

(5)迭代：继续回到步骤(2)，知道特征映射趋于稳定。迭代结束之后，每个样本所激活的神经元就是它对应的类别。

SOM本质上是一个两层的神经网络，包含模拟感知的输入层和模拟大脑皮层的输出层，输出层中神经元的个数通常是聚类的个数。具有保序映射的特点，可以将任意维输入模式在输出层映射为一维或者二维图形，并保持拓扑结构不变，使得输出层神经元的空间位置对应于输入空间的特定域或特征。在SOM中，以获胜神经元为中心，近邻者相互激励，远邻者相互抑制，这种交互作用的方式以曲线可视化则类似于“墨西哥帽”。

与K均值算法的异同：

(1)K均值算法需预先设定K的值，SOM不需要

(2)K均值算法为每个输入数据找到最相似的类后，只更新这个类的参数，SOM则会更新临近的节点。所以K均值算法受噪点影响较大，SOM的准确性可能会比K均值算法低(更新了临近节点)

(3)SOM的可视化比较好，具有优雅的拓扑关系图

如何设计SOM并设定网络训练参数：

输出层神经元数量：和样本的类别数相关。若不清楚样本的类别，则尽可能地设定较多的节点数，以便更好地映射样本的拓扑结构，如果分类过细再酌情减少输出节点。这样可能会带来少量从未更新过权重的“死节点”，但一般可通过重新初始化权重来解决

输出层节点排列：排列形式应尽量直观地反映出实际问题的物理意义。例如，对于一般的分类问题，一个输出节点能代表一个模式类，使用一维线阵；对于颜色空间或者旅行路径问题，二维平面则比较直观

初始化权重：可以随机初始化，但尽量使权值的初始位置与输入样本的大概分布区域充分重合，避免出现大量初始"死节点"。可以从训练集中随机抽取m个输入样本作为初始权重

拓扑领域：设计原则是使领域不断缩小，这样输出平面上相邻神经元对应的权向量之间既有区别又有相当的相似性，从而保证当获胜节点对某一类模式产生最大响应时，其领域节点也能产生较大响应。领域的形状可以是正方形、六边形或者菱形。优势领域的大小用领域的半径表示，通常凭借经验来选择

学习率：学习率为递减函数，训练开始时，学习率可以选取较大的值，之后以较快的速度下降，有利于很快地捕捉到输入向量的大致结构，然后学习率在较小的值上缓降为0，这样可以精细地调整权值使之符合输入空间的样本分布结构。

聚类算法评估

数据簇的特点：

以中心定义：倾向于球形分布，中心为质心，即此数据簇中所有点的平均值。集合中的数据到中心的距离相比到其他簇中心的距离更近

以密度定义：呈现和周围数据簇明显不同的密度，或稠密或稀疏。当数据簇不规则或互相盘绕，并且有噪声和离群点时，常常使用基于密度的簇定义

以连通定义：数据点和数据点之间有连接关系，整个数据簇表现为图结构。该定义对不规则形状或者缠绕的数据簇有效

以概念定义：数据簇中所有数据点具有某种共同性质

估计聚类趋势：检测数据分布中是否存在非随机的簇结构

如果数据基本随机，那么聚类的结果毫无意义。可以用霍普金斯统计量来判断数据在空间上的随机性：从样本中随机找 $n$ 个点 $p_1,p_2,...,p_n$ ，对每一个 $p_i$ ，都在样本空间中找到一个离它最近的点并计算它们之间的距离 $x_i$ ，从而得到距离向量 $x_1,x_2,...,x_n$ ；从样本可能取值范围内随机生成 $n$ 个点 $q_1,q_2,...,q_n$ ，使用同样的原则得到距离向量 $y_1,y_2,...y_n$ ，则霍普金斯统计量 $H$ 可表示为： $H=\frac{\sum_{i=1}^n y_i}{\sum_{i=1}^n x_i+\sum_{i=1}^n y_i}$ 。如果样本接近随机分布，则 $H$ 的值接近于0.5，如果聚类趋势明显，随机生成的样本点距离应该远大于实际样本点距离，则 $H$ 的值接近于1。

判定数据簇数量：例如手肘法和Gap Statistic方法
测定聚类质量：

轮廓系数： $s(p)=\frac{b(p)-a(p)}{max\{a(p),b(p)\}}$ ， $a(p)$ 是点 $p$ 与同一簇中的其他点 $p’$ 之间的平均距离； $b(p)$ 是点 $p$ 与另一个不同簇中的点之间的最小平均距离。显然 $b(p)$ 越大且 $a(p)$ 越小时对应的聚类质量越好，因此可将所有点对应的轮廓系数求平均值来度量聚类效果

均方根标准偏差： $RMSSTD=(\frac{\sum_i\sum_{x\in C_i}\parallel x-c_i\parallel ^2}{P\sum_i (n_i-1)})^{\frac{1}{2}}$ ， $C_i$ 是第 $i$ 个簇， $c_i$ 是该簇的中心， $x\in C_i$ 是属于第 $i$ 个簇的一个样本点， $n_i$ 为第 $i$ 个簇的样本数量， $P$ 为样本点对应的向量维数。该指标用来衡量聚类结果的同质性，即紧凑程度，可以看作是经过归一化的标准差。

R方： $RS=\frac{\sum_{x\in D}\parallel x-c\parallel ^2-\sum_i\sum_{x\in C_i}\parallel x-c_i\parallel ^2}{\sum_{x\in D}\parallel x-c\parallel ^2}$ ， $D$ 代表整个数据集， $c$ 是数据集 $D$ 的中心点， $\sum_{x\in D}\parallel x-c\parallel ^2$ 代表将数据集 $D$ 看作单一簇时的平方误差和。该指标用来衡量聚类之后的结果与聚类之前相比，对应的平方误差和指标的改进幅度。

改进的Hubert $\Gamma$ 统计： $\Gamma=\frac{2}{n(n-1)}\sum_{x\in D}\sum_{y\in D}d(x,y)d_{x\in C_i,y\in C_j}(c_i,c_j)$ ， $d(x,y)$ 是点 $x$ 到点 $y$ 之间的距离， $d_{x\in C_i,y\in C_j}(c_i,c_j)$ 是点 $x$ 所在的簇中心 $c_i$ 与点 $y$ 所在的簇中心 $c_j$ 之间的距离， $\frac{n(n-1)}{2}$ 是所有 $(x,y)$ 点对的个数，该指标对每个点对的和做了归一化处理。理想情况下对于每个点对，如果 $d(x,y)$ 越小，对应的 $d_{x\in C_i,y\in C_j}(c_i,c_j)$ 也越小，所以 $\Gamma$ 值越大说明聚类的结果与样本的原始距离越吻合，也就是聚类质量越高

构造数据集测试效果：

观察聚类误差是否随聚类类别数量的增加而单调变化

观察聚类误差对实际聚类结果的影响

观察近邻数据簇的聚类准确性

观察数据密度具有较大差异的数据簇的聚类结果

样本数量具有较大差异的数据簇的聚类效果

7、优化算法

损失函数

二分类 $(y=\{-1,1\})$ ：输出结果 $f$ 与真实值 $y$ 相乘，若输出与真实值的符号相同，则 $fy$ 为正数，损失函数需要惩罚符号不同的部分

Hinge损失函数： $L_{hinge}(f,y)=max\{0, 1-fy\}$ 。Hinge损失函数在 $fy<1$ 时随 $fy$ 值增大而下降，光滑可导；对 $fy\geq1$ 不做任何惩罚，且在 $fy=1$ 处不可导，所以需要使用次梯度下降法进行优化。

Logistic损失函数： $L_{logistic}(f,y)=log_2(1+e^{-fy})$ 。Logistic损失函数随 $fy$ 值增大而下降，处处光滑可导，可以使用梯度下降法进行优化，但是该损失函数对所有的样本点都有惩罚，对异常值较敏感。

交叉熵损失函数： $L_{cross\ entropy}(f,y)=-log_2(\frac{1+fy}{2})$ 。当预测值的值域为 $[-1,1]$ 时，可以使用交叉熵损失函数，该损失函数处处光滑可导，在 $fy<0$ 时的惩罚力度更大。

回归：对于连续值学习，可以直接计算输出结果 $f$ 与真实值 $y$ 的差值的绝对值来构造损失函数，惩罚差值绝对值大的部分

平方损失函数： $L_{square}(f,y)=(f-y)^2$ 。处处光滑可导，但是当预测值与真实值差距较大时，惩罚力度非常大，对异常值比较敏感。

绝对损失： $L_{absolute}(f,y)=|f-y|$ 。为了解决平方损失函数鲁棒性较低(对异常值敏感)的问题，可以直接使用差值的绝对值来作为损失函数，但是该损失函数在 $f=y$ 处无法求导，对于优化算法的选取比较局限。

Huber损失函数： $L_{Huber}(f,y)=\left\{\begin{array}{rcl}(f-y)^2 & &{|f-y|\leq\delta}\\2\delta|f-y|-\delta^2 & &{|f-y|>\delta}\\\end{array}\right.$ 。Huber损失函数综合考虑了可导性和鲁棒性，在差值绝对值较小时为平方损失，在差值绝对值较大时为线性损失，处处可导且对异常值敏感度不高。

凸优化与非凸优化

凸函数定义：函数 $L(\cdot)$ 是凸函数的条件是当且仅当：对其定义域中的任意两点 $x，y$ 和任意实数 $\lambda \in [0,1]$ ，总有 $L(\lambda x+(1-\lambda)y)\leq \lambda L(x)+(1-\lambda)L(y)$ 。其几何含义是：凸函数曲面上任意两点连接而成的线段，其上的任意一点都不会处于该函数曲面的下方。验证凸性：函数的Hessian矩阵满足半正定。
凸优化：对于凸优化问题，所有的局部极小值都是全局极小值，较容易求解。例子：逻辑回归、支持向量机、线性回归等线性模型
非凸优化：优化问题的目标函数不满足凸函数的定义，一般较难求解。例子：主成分分析、矩阵分解、深度神经网络

经典优化算法

无约束问题的优化方法：

直接法：需要满足：(1)目标函数 $L(\cdot)$ 是凸函数；(2) $\nabla L(\theta^*)=0$ 有闭式解。例子：岭回归。
迭代法：迭代修正对最优解的估计。假设当前对最优解的估计值为 $\theta_t$ ，希望求解优化问题 $\delta_t=arg min_\delta L(\theta_t+\delta)$ ,来得到更好的估计值 $\theta_{t+1}=\theta_t+\delta_t$

一阶法（梯度下降法）：一阶泰勒展开函数 $L(\theta_t+\delta)\approx L(\theta_t)+\nabla L(\theta_t)^T\delta$ 。该近似式仅在 $\delta$ 较小时才比较准确，因此一般加上L2正则项，使一次迭代的优化目标为： $arg min_\delta(L(\theta_t)+\nabla L(\theta_t)^T\delta+\frac{1}{2\alpha}\parallel \delta\parallel_2^2)=-\alpha\nabla L(\theta_t)$ 。由此，一阶法的迭代公式为： $\theta_{t+1}=\theta_t-\alpha\nabla L(\theta_t)，\alpha$ 为学习率。

二阶法（牛顿法）：二阶泰勒展开目标函数，一次迭代的优化目标为： $arg min_\delta(L(\theta_t)+\nabla L(\theta_t)^T\delta+\frac{1}{2}\delta^T\nabla^2L(\theta_t)\delta)=-\nabla^2L(\theta_t)^{-1}\nabla L(\theta_t)$ ，其中 $\nabla^2L(\theta_t)是函数L在\theta_t$ 处的Hessian矩阵。由此，二阶法的迭代公式为： $\theta_{t+1}=\theta_t-\nabla^2L(\theta_t)^{-1}\nabla L(\theta_t)$ 。
-二者比较：二阶法的收敛速度一般远快于一阶法，但在高维情况下，Hessian矩阵求逆的计算复杂度很大；当目标函数非凸时，二阶法有可能会收敛到鞍点

梯度验证

梯度的定义：目标函数的梯度为： $\nabla L(\theta)=\begin{bmatrix}\frac{\partial L(\theta)}{\partial \theta_1},...,\frac{\partial L(\theta)}{\partial \theta_n}\end{bmatrix}^T$ ；梯度的第 $i$ 个元素的定义为： $\frac{\partial L(\theta)}{\partial \theta_i}=\lim\limits_{h\rightarrow0}\frac{L(\theta+he_i)-L(\theta-he_i)}{2h}$ ，其中， $e_i$ 是单位向量，维度与 $\theta$ 相同，仅在第 $i$ 个位置取为1，其余取值为0。当 $h$ 取很小的值时，将 $L(\theta+he_i)，L(\theta-he_i)$ 泰勒展开，可以求得近似式的误差为： $|\frac{L(\theta+he_i)-L(\theta-he_i)}{2h}-\frac{\partial L(\theta)}{\partial \theta_i}|\approx Mh^2$ ，其中， $M$ 是常数
梯度功能正确性验证：

随机初始化 $\theta$ ，取h为很小的数，并对 $i=1,2,...,n，$ 依次验证 $|\frac{L(\theta+he_i)-L(\theta-he_i)}{2h}-\frac{\partial L(\theta)}{\partial \theta_i}|\leq h$ 是否成立

如果对于某个下标 $i$ ，该不等式不成立，则：(1)该下标对应的 $M$ 过大；(2)该梯度分量计算不正确

此时可以固定 $\theta$ ，减小 $h$ 为原来的 $10^{-1}$ ，并再次计算下标i对应的近似误差，若近似误差约减小为原来的 $10^{-2}$ ，则对应于第一种可能，我们应该采用更小的 $h$ 重新做一次梯度验证；否则对应于第二种可能，我们应该检查求梯度的代码是否有错误

随机梯度下降法

原理：解决训练样本数量较大时，梯度下降法由于遍历所有训练数据产生的大计算量问题。随机梯度下降法用单个训练样本的损失来近似平均损失，加快收敛速率，适用于数据源源不断到来的在线更新场景。为了降低随机梯度的方差，在实际应用中会采用小批量梯度下降法同时处理m个训练数据。需要注意：

(1)m的取值：一般从2的幂次中选最优值，能充分利用矩阵运算操作；

(2)挑选训练数据：先进行随机排序，再顺序取m个训练数据；

(3)学习速率 $\alpha$ 的取值：采用衰减学习速率，一开始选择较大的学习速率，当误差曲线进入平台期后，减小学习速率做更精细的调整

失效的原因：摸着石头下山，由于采用单样本来估计整体的梯度下降方向，每一步迭代接受的信息量有限，对梯度的估计常常出现偏差，造成目标函数曲线收敛得很不稳定，伴有剧烈的波动，甚至会出现不收敛的情况。对于随机梯度下降法来说，山谷和鞍点是最害怕处理的地形：在山谷中，目标函数曲线收敛轨迹在两山壁间来回反弹，不能沿山道方向迅速下降；在鞍点处，由于梯度近似为0，随机梯度下降法无法准确觉察出梯度的微小变化而停滞下来。
优化方法：

动量方法(惯性保持)：类比质点在山谷和鞍点处的运动，当质点动量较大时，速度不会很快衰减为0，可以快速通过山谷和鞍点。此时模型参数的前进步伐(迭代式减去的项)为： $v_t=\gamma v_{t-1}+\eta g_t$ ，其中 $\eta$ 为学习速率， $g_t$ 为当前梯度，二者相乘是经典梯度下降的前进步伐，此处引入了衰减系数 $\gamma$ 和前一刻的前进步伐。物理含义为：前进步伐为t时刻的速度，梯度为t时刻受力产生的加速度，衰减系数为阻力，模拟质点质量较大的情况，向下的力度稳定不变，产生的动量不断累积，左右弹力相互抵消，下降速度越来越快。

AdaGrad方法(环境感知)：使更新频率低的参数拥有较大步伐，更新频率高的参数拥有较小步伐，采用了历史梯度的平方和来衡量不同参数的梯度的稀疏性。更新公式为： $\theta_{t+1,i}=\theta_{t,i}-\frac{\eta}{\sqrt{\sum_{k=0}^{t}g_{k,i}^2+\epsilon}}g_{t,i}$ ，其中 $\theta_{t+1,i}$ 表示t+1时刻的参数向量 $\theta_{t+1}$ 的第 $i$ 个参数， $g_{k,i}$ 表示k时刻的梯度向量 $g_k$ 的第i个维度(方向)。分母实现了退火过程，随着时间推移，学习速率越来越小，保证算法最终收敛。

Adam方法：同时考虑了惯性保持和环境感知，记录了梯度的一阶距(过往梯度与当前梯度的平均)和二阶距(过往梯度平方与当前梯度平方的平均)，采用了指数衰退平均技术。一阶矩： $m_t=\beta_1m_{t-1}+(1-\beta_1)g_t$ ，表示估计 $g_t$ 的期望；二阶矩： $v_t=\beta_2v_{t-1}+(1-\beta_2)g_t^2$ ，表示估计 $g_t^2$ 的期望。更新公式为： $\theta_{t+1}=\theta_t-\frac{\eta\cdot\hat{m_t}}{\sqrt{\hat{v_t}+\epsilon}}$ ，其中 $\hat{m_t}=\frac{m_t}{1-\beta_1^t}$ ， $\hat{v_t}=\frac{v_t}{1-\beta_2^t}$

L1正则化使模型具有稀疏性的原理

解空间形状：损失函数带正则项与带约束条件等价，例如L2正则化就是加上一个约束条件：参数的L2范数的平方不能大于m，其拉格朗日函数为： $\sum_{i=1}^{N}(y_i-w^Tx_i)^2+\lambda (\parallel w \parallel_2^2-m)$ ，根据KKT条件可以得出带L2正则项优化问题的最优解条件。由此，L2正则化相当于为参数定义了一个圆形的解空间，L1正则化相当于为参数定义了一个棱形的解空间。如果原问题目标函数的最优解不是加好落在解空间内，那么约束条件下的最优解一定是在解空间的边界上。L1的解空间边界显然更容易与目标函数等高线在角点碰撞，最优解在坐标轴上，从而产生稀疏解。
函数叠加：考虑一维的目标函数图像，加入L1正则项后，对带正则项的目标函数 $L(w)+C|w|$ 求导，正则项部分产生的导数在远点左边部分是 $-C$ ，在原点右边部分是 $C$ 。只要原目标函数的导数绝对值小于 $C$ ，那么带正则项的目标函数在原点左边部分始终递减，在原点右边部分始终是递增，最小值自然在原点处，此时对应的w是0，产生了稀疏性。
贝叶斯先验：L1正则化相当于对参数w引入拉普拉斯先验，L2正则化相当于引入了高斯先验。由高斯分布曲线图得知，高斯分布在极值点(0点)处是平滑的，即w在极值点附近取不同值的可能性接近，这就导致L2正则化只会让w更接近0点但不会等于0；由拉普拉斯分布曲线图得知，拉普拉斯分布在极值点处是尖峰，所以拉普拉斯先验分布中参数w取值为0的可能性要更高。

12、集成学习

集成学习种类

Boosting：串行学习，将基分类器层层叠加，每一层训练时，对前一层基分类器分错的样本给予更高的权重；测试时，根据各层分类器的结果的加权得到最终结果。
Bagging：并行学习，将训练集分为若干子集，每个子集单独使用基分类器进行学习，学习内容可以相同也可以不同，通过对每个基分类器的分类结果投票得到最终结果。

集成学习步骤（Adaboost）

确定基分类器：任何分类模型都可以作为基分类器，但是树形模型由于结构简单且较易产生随机性所以比较常用
训练基分类器：假设训练集为 $\{x_i,y_i\}$ ，i=1,...,N，其中 $y_i\in\{-1,1\}$ ，有T个基分类器，训练过程如下：

初始化采样分布 $D_1(i)=\frac{1}{N}$ ；
令 $t=1,2,...,T$ 循环：

(1)从训练集中，按照 $D_t$ 分布，采样出子集 $S_t$ ；
(2)用 $S_t$ 训练出基分类器 $h_t$ ；
(3)计算 $h_t$ 的错误率： $\varepsilon_t=\frac{\sum_{i=1}^{N_t}I[h_t(x_i)\neq y_i]D_t(x_i)}{N_t}$ ，其中 $I[]$ 为判别函数；
(4)计算基分类器 $h_t$ 权重 $a_t=log\frac{(1-\varepsilon_t)}{\varepsilon_t}$ ；
(5)设置下一次采样： $D_{t+1}=\left\{\begin{array}{rcl}D_t(i) or \frac{D_t(i)(1-\varepsilon_t)}{\varepsilon_t} & &{h_t(x_i)\neq y_i}\\\frac{D_t(i)\varepsilon_t}{(1-\varepsilon_t)} & &{h_t(x_i)= y_i}\\\end{array}\right.$ 并将它归一化为一个概率分布函数
合并基分类器：给定一个未知样本 $z$ ，输出分类结果为加权投票的结果 $Sign(\sum_{t=1}^{T}h_t(z)a_t)$

基分类器

常用的基分类器

最常用的基分类器是决策树，原因为：(1)可以较方便地将样本权重整合到训练过程中而不需要使用过采样法调整权重；(2)表达能力和泛化能力可通过调节树的层数来折中；(3)数据样本的扰动对决策树影响较大，不同子样本集合生成的决策树基分类器随机性较大，决策树节点分裂时随机选择一个特征子集从中找出最优分裂属性，很好地引入了随机性。此外，神经网络模型也适合作为基分类器，通过调整神经元数量、连接方式、网络层数、初始权值等方式引入随机性。

可否将随机森林中的基分类器由决策树替换为线性分类器或K-近邻

随机森林属于Bagging类的集成学习，好处是集成后的分类器的方差比基分类器的方差小。Bagging所采用的基分类器最好是本身对样本分布较为敏感的，方差较大的，才能使得Bagging学习达成效果。线性分类器或者K-近邻都是较为稳定的分类器，本身方差就不大，所以以它们为基分类器的随机森林并不能在原有基分类器的基础上获得更好的表现，甚至可能因为Bagging的采样而导致在训练过程中更难以收敛，从而增大了集成分类器的偏差。

偏差和方差

偏差：由所有采样得到的训练数据集训练出的所有模型的输出的平均值和真实模型输出之间的偏差，通常由于对学习算法做了错误的假设所导致。由偏差带来的误差通常在训练误差上就能体现出来。
方差：由所有采样的到的训练数据集训练出的所有模型的输出结果的方差，通常由于模型的复杂度相对于训练样本数过高所导致。由方差带来的误差通常体现在测试误差相对于训练误差的增量上。
从减小偏差和方差的角度解释Boosting和Bagging的原理：从提升弱分类器性能的角度来看，Boosting降低了偏差，Bagging降低了方差。Bagging学习降低方差的原理是：对于n个独立不相关的模型的预测结果取平均，方差会是原来单个模型的1/n，当然实际模型之间不可能完全独立，但是Bagging学习通过各种优化方式增强弱分类器之间的独立性，从而显著降低模型的方差。Boosting学习过程需要计算每次学习的错误或者残差作为下一次学习的输入，这个过程本身就在不断减小损失函数，使得模型偏差不断降低，但Boosting过程并不会显著降低方差，因为其训练过程使用的各弱分类器之间是强相关的，缺乏独立性。

GBDT

基本原理：在每一轮迭代中，计算出当前模型在所有样本上的负梯度，然后以该值为目标训练一个新的弱分类器（通常为CART）进行拟合并计算出该弱分类器的权重，最终实现对模型的更新。训练完毕后，将所有树的预测值加起来，最终得到预测结果。
梯度提升和梯度下降：两者都是在每一轮迭代中，利用损失函数相对于模型的负梯度方向的信息来对当前模型进行更新。只不过在梯度下降中，模型是以参数化形式表示，从而模型的更新等价于参数的更新；而在梯度提升中，模型并不需要进行参数化表示，而是直接定义在函数空间中，从而大大扩展了可以使用的模型种类。
GBDT的优点和局限性

优点：(1)预测阶段的计算速度快，树与树之间可以并行化计算；(2)在分布稠密的数据集上，泛化能力和表达能力都很好；(3)采用决策树作为弱分类器使得GBDT模型具有较好的解释性和鲁棒性，能够自动发现特征间的高阶关系，并且也不需要对数据进行特殊的预处理如归一化等。

局限性：(1)在高维稀疏的数据集上，表现不如SVM或NN；(2)在处理文本分类特征问题上，相对其他模型的优势不如它在处理数值特征时明显；(3)训练过程需要串行训练，只能在决策树内部采用一些局部并行的手段提高训练速度。

XGBoost与GBDT

XGBoost算法原理改进：XGBoost在决策树构建阶段在损失函数中加入了正则项，通过对损失函数进行二阶泰勒展开，令损失函数相对于预测值的导数为0，求出在最小化损失函数的情况下各叶子节点上的预测值，再带入得到损失函数的最小值。通过遍历所有特征的所有取值，寻找使得损失函数前后相差最大时对应的分裂方式。
区别和联系：(1)GBDT是机器学习算法，XGBoost是该算法的工程实现；(2)在使用CART作为基分类器时，XGBoost显式地加入了正则项来控制模型的复杂度，有利于防止过拟合，从而提高模型的泛化能力；(3)GBDT在模型训练时只是用了损失函数的一阶导数信息，XGBoost对损失函数进行二阶泰勒展开，可以同时使用一阶和二阶导数；(4)传统的GBDT使用CART作为基分类器，XGBoost支持多种类型的基分类器，比如线性分类器；(5)传统的GBDT在每轮迭代时使用全部的数据，XGBoost则采用了与随机森林相似的策略，支持对数据进行采样；(6)传统的GBDT没有设计对缺失值进行处理，XGBoost能够自动学习出缺失值的处理策略。