机器学习（1）

机器学习：

模式识别

计算机视觉

数据挖掘

语音识别

统计学习

自然语言处理

1. 训练样本
2. 特征抽取
3. 学习函数
4. 预测

• 有监督问题：有label

• 无监督问题：无label

• 回归：输出具体的值

• 分类：所分类的问题

线性回归

$h_{\theta }(x)={\theta }_0+{\theta }_1{x}_1+{\theta }_2{x}_2$

$h_{\theta }(x)=\sum _{i=0}^n{\theta }_i{x}_i={\theta }^{T}x$

$y^{(i)}={\theta }^T{x}^{(i)}+{\varsigma }^{(i)}$

误差是独立并且具有相同的分布通常认为服从均值为0方差为${\theta }^2$的高斯分布

$p({\varsigma }^{(i)})=\frac{1}{\sqrt{2\pi }\sigma }exp(-\frac{{\varsigma }^{(i{)}^2}}{2{\sigma }^2})$

$p(y^{(i)}|x^{(i)};\theta )=\frac{1}{\sqrt{2\pi }\sigma }exp(-\frac{(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2}{2{\sigma }^2})$

最大似然函数：
$$\begin{gathered} L(\theta )=\prod _{i=1}^{m}p(y^{(i)}|x^{(i)};\theta ) \\ =\prod _{i=1}^{m}p(y^{(i)}|x^{(i)};\theta )\frac{1}{\sqrt{2\pi }\sigma }exp(-\frac{(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2}{2{\sigma }^2}) \end{gathered}$$
即需要求$\arg \max (L(\theta ))$

$l(\theta )=logL(\theta )$

$l(\theta )=m\log \frac{1}{\sqrt{2\pi }\sigma }-\frac{1}{{\sigma }^2}.\frac{1}{2}\sum _{i=1}^m(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2$

$J(\theta )=\frac{1}{2}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)}{)}^2$

即需要求$arg\min J(\theta )$

$$\begin{gathered} J(\theta )=\frac{1}{2}(X\theta -y{)}^T(X\theta -y) \\ {\nabla }_{\theta }J(\theta )={\nabla }_{\theta }(\frac{1}{2}({\theta }^T{X}^T-y^T)(X\theta -y)) \\ ={\nabla }_{\theta }(\frac{1}{2}({\theta }^T{X}^{T}X\theta -{\theta }^T{X}^{T}y-y^{T}X\theta +y^{t}y)) \\ =X^{T}X\theta -X^{T}y \\ \theta =(X^{T}X{)}^{-1}{X}^{T}y \end{gathered}$$

逻辑回归

可用于分类（二分类）与回归

$h_{\theta }(x)=g({\theta }^{T}x)=\frac{1}{1+e^{-{\theta }^{T}x}}$

取值范围[0,1]

$h_{\theta }(x{)}^{{}^{\prime }}=h(x)(1-h(x))$

采用梯度下降进行优化

不用求出其导数

决策树和随机森林

分类算法

树状结构表示数据分类的结果

• 根节点
• 非叶子节点（决策点）
• 叶子节点（分类标记）
• 分支（测试的结果）

训练阶段

分类阶段

两个事件相互独立：$P(X,Y)=P(X)\ast P(Y)$ $Log(XY)=Log(X)+Log(Y)$

从根开始，一层一层开始分类。

需要用熵来判断谁是层数低的结点

$H(x)$当成事件发生的不确定性，内部的混乱程度

$P(几率越大)->H(X)值越小$

$P(几率越小)->H(X)值越大$

熵 = $-\sum _{i=1}^n{p}_{i}ln(P_i)$

$Gini系数=Gini(p)=\sum _{i=1}^K{p}_k(1-p_k)=1-\sum _{k=1}^K{p}_k^2$

p越大，熵和Gini系数越小

构造决策树基本思想

构造树的基本想法是随着树深度的增加，节点的熵迅速降低。

熵降低的速度越快越好，可以使深度越小

根据每一次划分后，集合的熵之和最小最好，可以导致信息增益最大，使得信息熵下降得最快

决策树的版本

ID3：信息增益

C4.5：信息增益率

CART：Gini系数

ID3缺陷：

信息增益率过大： 样本过多，每个样本的数量稀少

评价函数：$C(T)=\sum _{t\in leaf}{N}_{t}H(t)$ $N_t$权重值，$H(t)$熵值

评价函数越小越好，类似于损失函数

能够处理连续型的属性，首先将连续型属性离散化，把连续型属性的值分成不同的区间

缺失数据的考虑：构建决策树，可以忽略损失数据，计算增益时，仅考虑具有属性值的记录

决策树剪枝

预剪枝：构建决策树的过程时，提前终止（防止过拟合）

后剪枝：决策树构建好后，才开始裁剪

$C_{\alpha }(T)=C(T)+\alpha |T_{leaf}|$ 叶子节点个数越多，损失越大

随机森林

Bootstrapping：有放回采样

Bagging：有放回采样n个样本一共建立分类器

一片决策树共同进行相同的决策

随机：随机选择百分之多少的样本进行训练，随机选择特征

贝叶斯算法

贝叶斯公式

$P(A|B)=\frac{P(B|A)P(A)}{P(B)}$

拼写纠正

垃圾邮件过滤

模型比较理论

最大似然：最符合观测数据（$P(h|D)$最大的最有优势） 后验概率越大越有优势

奥卡姆剃刀：$P(h)$较大的模型有较大的优势 先验概率越大越有优势，越是高阶的多项式越是不常见

朴素贝叶斯：特征之间相互独立，互不影响

Xgboost

集成分类器

预测值：$\widehat{y_i}={\sum }_j{w}_j{x}_{ij}$

目标函数：$l(y_i,\widehat{y_i})=(y_i-\widehat{y_i}{)}^2$

最优解：$F^{\ast }(x)=\arg \min E_{(x,y)}[L(y,F(x))]$

基本思想：是在每加一棵树在原先的基础之上有提升

${\widehat{y_i}}^{(0)}=0$

${\widehat{y_i}}^{(1)}=f_1(x_i)={\widehat{y_i}}^{(0)}+f_1(x_i)$

${\widehat{y_i}}^{(t)}=\sum _{k=1}^t{f}_k(x_i)={\widehat{y_i}}^{(t-1)}+f_t(x_i)$

等价于第t轮的模型预测，再保留前面$t-1$轮的模型预测上，加入一个新的函数

惩罚项：$\Omega (f_t)=\gamma T+\frac{1}{2}\lambda \sum _{j=1}^T{w}_j^2$ 针对每一棵树来说

第一项是叶子结点的个数，后面一项是正则化的惩罚项，构成总的损失函数

$ob{j}^{(t)}=\sum _{i=1}^{n}l(y_i,{\widehat{y_i}}^{(t)})+{\sum }_{i=1}^t\Omega (f_i)$

​ $=\sum _{i=1}^{n}l(y_i,{\widehat{y_i}}^{(t-1)}+f_t(x_i))+\Omega (f_t)+c$

目标需要找到$f_t$来优化目标

用泰勒展开进行优化

$ob{j}^{(t)}={\sum }_{i=1}^n[l(y_i,{\widehat{y_i}}^{(t-1)})+g_i{f}_t(x_i)+\frac{1}{2}{h}_i{f}_t^2(x_i)]+\Omega (f_t)+const$

$g_i$为一阶导，$h_i$为二阶导

转化为对叶子结点的遍历

$ob{j}^{(t)}={\sum }_{i=1}^n[g_i{w}_q(x_i)+\frac{1}{2}{h}_i{w}_{q(x_i)}^2]+\gamma T+\lambda \frac{1}{2}{\sum }_{j=1}^T{w}_j^2$

​ $={\sum }_{j=1}^T[({\sum }_{i\in I_j}{g}_i)w_j+\frac{1}{2}({\sum }_{i\in I_j}{h}_i+\lambda )w_j^2]+\gamma T$

$G_j={\sum }_{i\in I_j}{g}_i$ $H_j={\sum }_{i\in I_j}{h}_i$

$ob{j}^{(t)}={\sum }_{i=1}^T[G_j{w}_j+\frac{1}{2}(H_j+\lambda w_j^2)]+\gamma T$

偏导数=0

计算出$w_j=-\frac{G_j}{H_j+\lambda }$

$Obj=-\frac{1}{2}{\sum }_{j=1}^T\frac{G_j^2}{H_j+\lambda }+\gamma T$

是否要进行左节点与右节点的切分

计算切分后的差异

$Gain=\frac{1}{2}[\frac{G_L^2}{H_L+\lambda }+\frac{G_R^2}{H_R+\lambda }-\frac{(G_L+G_R{)}^2}{H_L+H_R+\lambda }]-\gamma$

Adaboost

自适应增强

前一个分类器分错的样本会得到加强，加权后全体样本再次被用来训练下一个基本分类器。同时，在每一轮加入一个新的弱分类器，直到达到某个预定足够小的错误率，或者预先指定的最大迭代次数

最后新的分类器由多个分类器加权得到的

1. 初始化数据的权值分布，初始时所有样本的权重相同
2. 训练弱分类器，若某个样本未被准确分类，则提高其权重；若正确分类，降低权重
3. 将弱分类器加权组合成强分类器

支持向量机

分类问题

假定有一个超平面：$w^{T}x+b=0$

超平面上有两个点：$x^{{}^{\prime }}{x}^{{}^{\prime \prime }}$ 满足$w^T{x}^{{}^{\prime }}=-b{w}^T{x}^{{}^{\prime \prime }}=-b$

平面的法向量w：$w^T(x^{{}^{\prime \prime }}-x^{{}^{\prime }})=0$

$x^{\prime \prime }和x^{\prime }$是向量形式

distance(point to line)=$\frac{w^T}{||w||}(x-x^T)$=$\frac{1}{||w||}|w^{T}x+b|$

SVM在分类中，正例的时候$y=1$，负例的时候$y=-1$

这样就可以满足$y_{i}y(x_i)>0$

找到一个直线，使得离该线最近的点越远：

$\underset{w,b}{\arg }\max (\min \frac{y_i(w^T{x}_i+b)}{||w||})$

通过放缩：$y_i(w^T{x}_i+b)\ge 1$

则需要求$ma{x}_{w,b}\frac{1}{||w||}$

转换成求最小值${\min }_{w,b}\frac{1}{2}{w}^2$且$y_i(w^T{x}_i+b)\ge 1$

利用拉格朗日乘子法：

$L(w,b,\alpha )=\frac{1}{2}||w|{|}^2-\sum _{i=1}^n{\alpha }_i(y_i(w^T{x}_i+b)-1)$

对偶问题：$\underset{w,b}{\min }\underset{\alpha }{\max }L(w,b,\alpha )>\underset{\alpha }{\max }\underset{w,b}{\min }L(w,b,\alpha )$

分别对w和b求偏导，分别得到两个条件

$\frac{\partial L}{\partial w}=0$ -> $w=\sum _{i=1}^n{\alpha }_i{y}_i{x}_n$

$\frac{\partial L}{\partial b}=0$ -> $\sum _{i=1}^n{\alpha }_i{y}_i=0$

在对$\alpha$求导即可

拉格朗日乘子法

$\min f(x)$

$s.t.g_i(x)\le 0i=1,\dots ,m$

支持向量决定着分割面的点，决定了间隔分离超平面

软间隔

出现个别的点影响整个超平面的分隔情况

引入松弛因子，变成了软间隔问题

$y_i(w{x}_i+b)\ge 1-{\epsilon }_i$

目标函数：$\min \frac{1}{2}||w|{|}^2+C\sum _{i=1}^n{\epsilon }_i$

当C趋近于无穷大时：意味着分类严格不能有错误

当C趋近于很小时：意味着可以有更大的错误容忍

核函数

从低维空间到高维空间进行映射

核函数的好处：在一个低维空间完成高维度样本内积的计算

可以简化成在低维进行内积将结果映射到高维上

与在高维上进行内积结果相同

高斯核函数

K(X,Y)=exp{∣∣X−Y∣∣22σ2}K(X,Y)=exp\{\frac{||X-Y||^2}{2\sigma^2}\}K(X,Y)=exp{2σ2∣∣X−Y∣∣2​}

ARIMA

平稳性：

• 平稳性就是要求经由样本时间序列所得到的拟合曲线，在未来的一段期间内仍能顺着现有的形态“惯性”地延续下去
• 平稳性要求序列的均值和方差不发生明显变化

严平稳与弱平稳：

• 严平稳：严平稳表示的分布不随时间的改变而改变。白噪声：无论怎么取，期望是0，方差是1
• 弱平稳：期望与相关系数（依赖性）不变。未来某时刻的t的值依赖它的过去信息，所以需要依赖性

数据相对稳定：

• 差分法：时间序列t与t-1时刻的差值

自回归模型（AR）

• 描述当前值与历史值之间的关系，用变量自身的历史时间数据对自身进行预测
• 自回归模型必须满足平稳性的要求
• p阶自回归过程的公式定义：$y_t=\mu +{\sum }_{i=1}^p{\gamma }_i{y}_{t-i}+{ϵ}_t$
• $y_t$是当前值，$\mu$是常数项，$P$是阶数，${\gamma }_i$是自相关系数，${ϵ}_t$是误差

自回归模型的限制：

• 自回归模型是用自身的数据来进行预测
• 必须具有平稳性
• 必须具有自相关性，如果自相关系数$({\phi }_i)<0.5$，则不宜采用
• 自回归只适用于预测与自身前期相关的现象

移动平均模型（MA）

• 移动平均模型关注的是自回归模型中误差项的累加
• q阶自回归过程的公式定义：$y_t=\mu +{ϵ}_t+{\sum }_{i=1}^q{\theta }_i{ϵ}_{t-i}$
• 移动平均法能有效地消除预测中的随机波动

自回归移动平均模型：$(ARMA)$

• 自回归与移动平均的结合
• 公式定义：$y_t=\mu +{\sum }_{i=1}^p{\gamma }_i{y}_{t-i}+{ϵ}_t+{\sum }_{i=1}^q{\theta }_i{ϵ}_{t-i}$

ARIMA：差分自回归移动平均模型

将非平稳时间序列转化为平稳时间序列

然后将因变量仅对它滞后值以及随机误差项的现值和滞后值进行回归所建立的模型

选择p值和q值

自相关函数ACF

• 有序的随机变量序列与其自身相比较 自相关函数反映了同一序列在不同时序的取值之间的相关性
• $ACF(k)={\varrho }_k=\frac{Cov(y_t,y_{t-k})}{Var(y_t)}$

偏自相关函数（PACF）

• ACF中得到的并不是$x(t)$与$x(t-k)$之间单纯的相关关系
• $x(t)$同时还会受到$x(t-1)\dots x(t-k+1)$的影响
• PACF剔除了中间$k-1$个随机变量$x(t-1),\dots ,x(t-k+1)$的干扰之后，$x(t-k)$对$x(t)$影响的相关程度

模型	ACF	PACF
AR（p）	衰减趋于0（几何型或振荡型）	p阶后结尾
MA（q）	q阶后结尾	衰减趋于0（几何型或振荡型）
ARMA（p，q）	q阶后衰减趋于0（几何型或振荡型）	p阶后衰减趋于0（几何型或振荡型）

截尾：落在置信区间之内（95%的点都符合该规则）

建模流程

• 将序列平稳（差分法确定d）
• p和q阶数确定：ACF与PACF
• ARIMA（p，d，q）

模型选择AIC与BIC：（越低越好）

AIC：赤池信息准则。 $AIC=2k-2ln(L)$

BIC：贝叶斯信息准则 $BIC=kln(n)-2ln(L)$

k为模型参数个数，n为样本数量，L为似然函数

模型残差检验：

ARIMA模型的残差是否是平均值为0且方差为常数的正态分布

神经网络

一张图片在计算机中表示成三维数组的形式

K近邻算法

一个东西它最近的k个中更多属于哪个类，它就被划分到哪个类

对于未知类别属性数据集中的点：

• 计算已知类别数据集中的点和当前点的距离
• 按照距离依次排序
• 选取与当前点距离最小的k个点
• 确定前k个点所在类别的出现概率
• 返回前k个点出现频率最高的类别作为当前点预测分类

不需要训练，计算复杂度和训练集中的文档数目成正比，复杂度$O(n)$

距离计算：

$d_1(I_1.I_2)=\sum _p|I_1^p-I_2^P|$

距离也称为超参数

曼哈顿距离：$L1$：$d_1(I_1,I_2)=\sum _p|I_1^P-I_2^p|$

欧式距离：$L2$：$d_2(I_1,I_2)=\sqrt{\sum _p(I_1^p-I_2^p{)}^2}$

K近邻参数确定：

采用交叉验证：将训练集去一部分作为验证集（调节模型参数）（交替取其中的一份作为验证集）

神经网络损失函数

$L_i=\frac{1}{N}{\sum }_{i=1}^N{\sum }_{j\ne y_i}max(0,f(x_i;W{)}_j-f(x_i;W{)}_{y_i}+\delta )$

$\delta$可容忍程度

正则化惩罚项

$L_i=\frac{1}{N}{\sum }_{i=1}^N{\sum }_{j\ne y_i}max(0,f(x_i;W{)}_j-f(x_i;W{)}_{y_i}+\delta )+\lambda \sum _k\sum _l{W}_{k,l}^2$

作用：惩罚权重参数

Softmax分类器

$softmax$输出：归一化的分类概率

损失函数：交叉熵损失 $L_i=-\log \frac{e^{f_{y_i}}}{{\sum }_j{e}^{f_j}}$

$f_j(z)=\frac{e^{z_j}}{{\sum }_k{e}^{z_k}}$，称作softmax函数

输入值是一个向量，向量中元素为任意实数的评分值

输出一个向量，每个元素值在0到1之间，且所有元素之和为1

机器学习优化

反向传播

梯度下降

$batchsize$：计算机承受的负载量，一次迭代多张（前向传播+反向传播）

训练中，整体趋势是收敛下降的

epoch：所有的数据都跑完一遍

反向传播中

加法门单元：均等分配

MAX门单元：给最大的

乘法门单元：互换

特点：

• 层次结构
• 非线性结构

sigmoid函数梯度消失现象严重，已经不再采用

现在主要采用RELU $max(0,x)$

神经元数量越多，分类的效果越好

防止过拟合：正则化

数据预处理

权重初始化：b常量初始化，w随机

防止过拟合：

drop-out：训练的时候，随机保留一部分的神经元进行前向传播与反向传播