定义

1. 属性空间：所有属性值张量组成的集合

2. 版本空间：使得所有错误度为0的假设组成的空间

3. 奥卡姆剃刀：若有多个假设符合观察，选取最简单的那个假设

4. NFL定理：对于两个不同的学习算法，在所有问题出现机会相等前提下，两者的性能期望值相同。实际情况下，所有问题出现的机会不完全相同，我们要找到符合最大出现问题的算法

5. 判别式模型：直接对条件概率$P(y|X)$P(y∣X)进行建模，判断在X条件下y发生的概率。线性模型，LDA,SVM,NN都是判别式模型

   生成式模型：对X,Y的联合概率分布建模，通过bayes公式求得$P(y|X)$P(y∣X),选取使$P(y|X)$P(y∣X)最大的y。HMM,NB,高斯混合模型都是生成式模型

6. 维数灾难：学习器的性能随着特征个数的增加不会一直提升，当低维映射到高维的时候，学习器在训练集的性能肯定是提升的，但是泛化性能下降，其实维数灾难就是在维度上的过拟合。同时高维度会造成矩阵稀疏，距离计算困难——缓解维数灾难的方法：降维和特征选择

基本数学概念

1. 极大似然估计(MLE),最大后验概率(MAP),最小二乘法，EM

先验概率：根据以往经验分析和得到的概率，不用做实验就知道的概率

后验概率：后验概率是在考虑了一个事实之后的条件概率

极大似然和最大后验

1. MLE

   求参数θ，使得P(X|θ)最大

   知道分布的具体情况，但是不知道具体的参数，比如说知道了使正态分布，但是不知道μ和σ

   求解
   $argmax_{\mu}p(X,\mu)$argmaxμ​p(X,μ)
   其中p(X,μ)就是似然函数，表征在参数μ下出现观测数据的概率，假设每次观测时独立的
   $p(x_1,x_2,...,x_n;\mu)=\prod p(x_i;\mu)$p(x1​,x2​,...,xn​;μ)=∏p(xi​;μ)
   即求解
   $argmax_{\mu}\log(p(X,\mu))=argmax_\mu \sum\log p(x_i;\mu)$argmaxμ​log(p(X,μ))=argmaxμ​∑logp(xi​;μ)
   前提假设：

   训练样本的分布能代表样本的真实分布。每个样本集中的样本都是所谓独立同分布的随机变量 (iid条件)，且有充分的训练样本

2. MAP

   求参数θ，使得P(X|θ)*P(θ)最大

   由于：
   $P(\theta|X)=\frac{P(X|\theta)P(\theta)}{P(X)}$P(θ∣X)=P(X)P(X∣θ)P(θ)​

   由于$P(X)$P(X)为常数，则MAP即求$θ$θ，使得$ P(θ|X)$最大，MLE和MAP的区别：MLE是把先验概率$最大，MLE和MAP的区别：MLE是把先验概率P(θ)$认为等于1，即认为θ是均匀分布

3. 最小二乘法

   最小二乘法是找到一个（组）估计值，使得实际值与估计值的距离最小

   基本假设

   1. 解释变量是确定变量，不是随机变量
   2. 随机误差项具有零均值，同方差，服从正态分布
   3. 随机误差项与解释变量之间不相关

4. EM

   EM老是跟MLE放在一起，我们来判别一下MLE和EM的不同

   MLE:已知数据分布模型，采样的数据，但是不知道模型的具体参数，根据采样数据反推使得采样数据概率最大的模型的参数

   EM:相当于是MLE又进阶了一层，已知各个类别的分布模型，以及采样的数据，不知道采样的数据究竟来自于哪个类别，以及每个类别模型的参数

   在这个例子里面，本身数据来自于哪个类别这个应该是我们已知的，但实际情况我们并不知道，所以把数据来自于哪个类别成为隐变量$Z$Z,则我们就要求解$argmaxP(\theta|X,Z)$argmaxP(θ∣X,Z).

   E步：

   给定初始超参数$\Theta^t$Θt,计算$Q=P(Z|X;\Theta^t)$Q=P(Z∣X;Θt)

   M步:
   根据Q，计算使似然函数最大的$\Theta^{t+1}$Θt+1

   推导：

   1. 在未知子模型的分布$\alpha_k$αk​时，其自变量分布如下$P(x ; \theta)=\sum_{i=1}^{k} \alpha_{k} \phi\left(x ; \theta_{k}\right)$P(x;θ)=∑i=1k​αk​ϕ(x;θk​)

      似然函数：

      $l(\theta)=\sum_{i=1}^{m} \log p\left(x_{i} ; \theta\right)$l(θ)=∑i=1m​logp(xi​;θ)

      我们需要求得这个似然函数的一个最大值

   2. 由于我们不知道观察到的序列来自于哪个子模型，则
      $l(\theta)=\sum_{i=1}^{m} \log p\left(x_{i} ; \theta\right)=\sum_{i=1}^{m}\log \sum_{Z}Q(z)p(x_i|z;\theta)$l(θ)=i=1∑m​logp(xi​;θ)=i=1∑m​logZ∑​Q(z)p(xi​∣z;θ)
      其中，$m$m:样本数量；$Q(z)$Q(z):子模型的概率分布

      由于$\sum_{Z}Q(z)=1$∑Z​Q(z)=1，则上式有

   3. $l(\theta)=\sum_{i=1}^{m}\log \sum_{Z}Q(z)\frac{p(x_i,z;\theta)}{Q(z)}\ge\sum_{i=1}^{m} \sum_{Z} Q\left(z\right) \log \frac{p(x_i,z;\theta)}{Q\left(z\right)}$l(θ)=i=1∑m​logZ∑​Q(z)Q(z)p(xi​,z;θ)​≥i=1∑m​Z∑​Q(z)logQ(z)p(xi​,z;θ)​

      上述第二条用了Jensen不等式，因为log是凹函数

   4. 考虑不等式取得等号的条件$\frac{p(x_i,z;\theta)}{Q(z)}=c$Q(z)p(xi​,z;θ)​=c，同时考虑$\sum_{Z}Q(z)=1$∑Z​Q(z)=1，则有
      $Q(z)=\frac{p(x_i,z;\theta)}{\sum_zp(x_i,z;\theta)}=\frac{p(x_i,z;\theta)}{p(x_i;\theta)}=p(z|x_i;\theta)$Q(z)=∑z​p(xi​,z;θ)p(xi​,z;θ)​=p(xi​;θ)p(xi​,z;θ)​=p(z∣xi​;θ)

   5. 则有EM算法，初始化$\theta$θ，E步：根据$\theta$θ求出$Q(z)$Q(z),即第$x_i$xi​个数据来自$z_i$zi​的概率;M步：根据所求出的Q，最大化第二步得到的$l(\theta)$l(θ)，利用MLE求出新的$\theta$θ

2. 优化方法汇总(GD家族,一阶导数)

优化方法总结

简单说明几个特点：

1. SGD
   $\Theta_{t+1,i}=\Theta_{t,i}-\alpha g_{t,i}$Θt+1,i​=Θt,i​−αgt,i​

   $\Theta_{t,i}:t轮学习中参数\theta_i的取值$Θt,i​:t轮学习中参数θi​的取值

   BGD:下降速度慢，若cost function为凸函数，保证到全局最优

   SGD:下降快，但是容易收敛到局部最优且困在鞍点

   MBGD:取一个batch来计算

   总的缺点：

   1. 选取适当的学习率α较为困难，需要再训练过程中给调整学习率的大小（预先设定迭代次数m，执行m次后减小学习率）
   2. 每个参数的学习率是相同的（不合理！）对于稀疏矩阵不合理，解决方案是对于稀疏矩阵中频率较低的特征设置大学习率，高频特征设置小学习率

2. Momentum
   $v_t=\gamma v_{t-1}+\alpha g_{t,i}$vt​=γvt−1​+αgt,i​

   $\Theta=\Theta-v_t$Θ=Θ−vt​

   会观察历史梯度，若当前梯度方向与历史梯度一直，增强该梯度，否则，衰减该梯度

   Nesterov和Momentum的区别

   

   momentum同时计算该点的历史速度和梯度，然后叠加，nestreov是计算该点的速度，计算前进后的梯度，将两者叠加

   Nestreov
   $v_t=\gamma v_{t-1}+\alpha \nabla f(x_t+\gamma v_t)$vt​=γvt−1​+α∇f(xt​+γvt​)

   $x_{t+1}=x_t-v_t$xt+1​=xt​−vt​

3. Adagrad

   Momentum中对于每个参数的训练使用了相同的学习率，Adagrad可以实现对学习率的调整
   $\Theta_{t+1,i}=\Theta_{t,i}-\frac{\alpha}{\sqrt{G_{t,ii}+\epsilon}}g_{t,i}$Θt+1,i​=Θt,i​−Gt,ii​+ϵ​α​gt,i​

   $G_{t,ii}=\sum_{j=1}^{t-1}g_{j,i},代表\theta_i从第1轮到第t轮的梯度平方和，\epsilon为平滑项，避免分母为0$Gt,ii​=j=1∑t−1​gj,i​,代表θi​从第1轮到第t轮的梯度平方和，ϵ为平滑项，避免分母为0

   缺点：中后期分母项越来越大，导致梯度趋近于0

   容易困在局部极值点

4. RMSprop
   $\Theta_{t+1,i}=\Theta_{t,i}-\frac{\alpha}{\sqrt{E_{t}+\epsilon}}g_{t,i}$Θt+1,i​=Θt,i​−Et​+ϵ​α​gt,i​
   其中：
   $E_{t}=0.9E_{t-1}+0.1g_t^2$Et​=0.9Et−1​+0.1gt2​,将Adagrad中的累加变为平均值，缓解梯度下降过快问题

5. Adam

   不仅把学习率改了，连梯度也改了
   $m_{t}=\beta_{1} m_{t-1}+\left(1-\beta_{1}\right) g_{t}$mt​=β1​mt−1​+(1−β1​)gt​

   $v_{t}=\beta_{2} v_{t-1}+\left(1-\beta_{2}\right) g_{t}^{2}$vt​=β2​vt−1​+(1−β2​)gt2​

   $\hat{m}_{t}=\frac{m_{t}}{1-\beta_{1}^{t}}$m^t​=1−β1t​mt​​

   $\hat{v}_{t}=\frac{v_{t}}{1-\beta_{2}^{t}}$v^t​=1−β2t​vt​​

   $\Theta_{t+1}=\Theta_{t}-\frac{\alpha}{\sqrt{\hat{v}_{t}}+\epsilon} \hat{m}_{t}$Θt+1​=Θt​−v^t​​+ϵα​m^t​

   在稀疏矩阵时，常用Adagrad，RMSprop，Adam，因为可以动态调整学习率

3.优化方法汇总(Newton家族，二阶导数)

为什么深度学习不采用newton家族的算法作为优化算法：

答：牛顿法需要用到梯度和Hessian矩阵(二阶梯度矩阵)，很难写出深度神经网络你和函数的表达式，更不用说求解梯度和Hessian矩阵了，即使能够求解，在输入特征维度较高的时候，Hessian矩阵大小是n*n，耗费内存较高，求逆更是做梦；另外，当为凸函数的时候，牛顿法一定会下降，但是非凸的时候不一定

1. 牛顿法

   基本思想:在现有极小点估计值的附近对f(x)做二阶泰勒展开，进而找到极小点的下一个估计值

   

2.拟牛顿法

为了解决牛顿法中Hessian矩阵的问题，构造Hessian矩阵的近似矩阵来还原Hessian矩阵，常有DFP,BFGS算法

4.距离的度量

对于距离的度量需要满足一些基本的性质：

非负性：

同一性：

对称性：

三角不等式：

常用的度量距离的方案：

1. 闵科夫斯基距离（适用于度量连续或者有序的类别特征）
2. VDM距离（无序的类别特征）

特征工程

1. 特征选择

2. 正负样本不均衡

1. 调整二分类中的阈值

2. 选用ROC或F1指标

3. 过采样和欠采样

   过采样:重复正比例数据，实际上没有为模型引入更多数据，过分强调正比例数据，会放大正比例噪音对模型的影响

   欠采样:丢弃大量数据，和过采样一样会存在过拟合的问题

   SMOTE:加强版的过采样，基本思想是对少数类样本插值，合成少数类样本的新样本，从少树类样本集T中随机选取一个样本，再从T中选取K个近邻（距离的定义多种多样）。1.从这k个近邻中随机选取一个样本，2. 从0-1中随机选取一个数 3.插值得到一个新的样本 4.重复上述步骤

3. 特征组合

模型评估

1. 评估方法：

留出法

交叉验证法

自助法(bootstrap)：

每次随机从样本空间D中有放回采样一个样本，重复m次，得到有m个样本的样本空间D’
$\lim_{n\to+\infty}(1-\frac{1}{m})^m=\frac1e\approx0.368$n→+∞lim​(1−m1​)m=e1​≈0.368
即通过自主采样，初始数据集中约有36.8%的样本未出现在采样数据集D’中，可用这部分数据作为测试集，这就是包外估计 ；自助法会引入估计偏差，常采用留出法和交叉验证法

2. 回归和分类问题的性能度量

见：常见回归和分类损失函数比较

回归问题：

1. 平方损失：

   缺点：对异常值较为敏感，不够鲁棒

$MSE=\frac1m\sum({f(x_{i})-y_{i}})^2$MSE=m1​∑(f(xi​)−yi​)2

2. 绝对值损失

   特点：对异常值表现较好，缺点是不是处处可导，不容易优化
   $|y-f(x)|$∣y−f(x)∣

3. Huber损失

对于分类问题来讲，损失函数中的$f(x)$f(x)并不是预测出来的0或1的值，对于LR$f(x)=wx+b$f(x)=wx+b，对于adaboost来讲，$f(x)=\sum_{j=1}^t g_j(x)$f(x)=∑j=1t​gj​(x)，最终的分类结果是$sign(f(x))$sign(f(x)),对于SVM，$f(x)=y_i(wx_i+b)$f(x)=yi​(wxi​+b)可以认为是到各个点到分类间隔的距离

分类问题：

1. 0-1损失

   特点：不连续，非凸，优化困难
   $L(x)=\left\{ \begin{array}{rcl} 0 &{if f(x)=y}\\ 1 &{if f(x)!=y}\\ \end{array} \right.$L(x)={01​iff(x)=yiff(x)!=y​

2. 交叉熵损失(LR)——类别为{-1，1}
   $L(y,f(x))=\sum\log(1+e^{-yf(x)})$L(y,f(x))=∑log(1+e−yf(x))
   推导：
   $g(f(x))=P(y=1|x)=\frac1{1+e^{-f(x)}}$g(f(x))=P(y=1∣x)=1+e−f(x)1​
   则：
   $P(y=-1|x)=1-P(y=1|x)=\frac1{1+e^{f(x)}}$P(y=−1∣x)=1−P(y=1∣x)=1+ef(x)1​
   利用极大似然思想，使得
   $F(x)=\prod(\frac1{1+e^{-y_if(x_i)}})$F(x)=∏(1+e−yi​f(xi​)1​)
   $F(x)$F(x)最大，则两边同取对数，得到
   $L(y,f(x))=\log(1+e^{-yf(x)})$L(y,f(x))=log(1+e−yf(x))
   求$min(L)$min(L)即可

3. 交叉熵损失——类别为{0,1}
   $L(y,f(x))=\sum y\log f(x)+(1-y)\log(1-f(x))$L(y,f(x))=∑ylogf(x)+(1−y)log(1−f(x))
   求$argmax(L)$argmax(L)

4. 对数似然代价函数(当为二分类时，与交叉熵相等)：
   $L(y,f(x))=\sum_{i=1}^{m}\sum_{j=1}^{|D|} p(y_i,y_i')log(f(x_{ij}))$L(y,f(x))=i=1∑m​j=1∑∣D∣​p(yi​,yi′​)log(f(xij​))
   其中

   $y_{n}$yn​':第n个样本的预测label
   $y_{n}$yn​:第n个样本的真实label
   $f(x_n)$f(xn​):学习器将第n个样本预测为y_i’的概率

   $p(y,y')=\left\{ \begin{array}{rcl} 0 &{if y'!=y}\\ 1 &{if y'=y}\\ \end{array} \right.$p(y,y′)={01​ify′!=yify′=y​

5. Hinge Loss

$L(y,f(x))=max(0,1-yf(x))$L(y,f(x))=max(0,1−yf(x))

6. 指数损失(Adaboost):

$L(y,f(x))=e^{-yf(x)}$L(y,f(x))=e−yf(x)

3.P-R,ROC,AUC

	预测结果(+)	预测结果(-)
真实情况(+)	TP	FN
真实情况(-)	FP	TN

1. 准确率
   $Accuracy=\frac{n_{correct}}{n_{total}}=\frac{TP+TN}{total}$Accuracy=ntotal​ncorrect​​=totalTP+TN​
   受样本不均衡影响较大

2. 精确率
   $Precision=\frac{TP}{TP+FP}$Precision=TP+FPTP​

3. 召回率
   $Recall=\frac{TP}{TP+FN}$Recall=TP+FNTP​

4. P-R曲线

   纵轴为精确率，横轴为召回率，当一个学习器A的P-R曲线被另一个B完全包住，则性能A优于B，当两个PR曲线有交叉时，看与y=x的相交点的横轴坐标，越大证明性能越好

   P-R曲线上的点的含义：在某一阈值下，学习器将大于该阈值的输出为+，小于该阈值的输出为-，与此相对应的Precision和Recall

5. F1-score
   $F1=\frac{2\times precision\times recall}{precision+recall}$F1=precision+recall2×precision×recall​
   两者的调和平均值，介于0-1之间

6. ROC曲线
   $TPR=\frac{TP}{TP+FN}=Recall$TPR=TP+FNTP​=Recall

   $FPR=\frac{FP}{FP+TN}$FPR=FP+TNFP​

   AUC为ROC曲线下的面积，一般处于0.5-1之间，因为若AUC<0.5，把预测的正样本变成负样本，把负样本变成正样本，就可以得到一个更好的分类器

   ROC曲线的绘制，变换学习器预测为正类的阈值，得到在不同阈值下，学习器对应的TPR以及FPR，连接即为ROC曲线

4. 偏差与方差

偏差度量了学习算法的期望预测与真实结果的偏离程度，刻画了算法本身的拟合能力
$bias=(\bar f(x)-y)^2$bias=(fˉ​(x)−y)2
方差度量了同样大小的训练集变动导致的学习性能的变化，刻画了数据扰动的影响

误差=偏差+方差

噪声表达了当前任务上任何学习算法所能达到的期望泛化误差的下界

随着训练程度的增加，偏差逐渐减小，方差逐渐增大，即欠拟合是偏差大，方差小，过拟合是方差大，偏差小

5. 过拟合和欠拟合

过拟合：偏差小，方差大

解决方案：

1. 获取更多的训练数据
2. 降低模型复杂度
3. 正则化方法
4. 集成学习bagging

欠拟合：偏差大，方差小

解决方案：

1. 添加新特征(升维度）
2. 增加模型复杂度
3. 减小正则化系数

调参方法