# 线性二分类
不同于回归问题，线性分类问题的标签是离散的二值
$$
f(x)=\pm1
$$

希望用一条直线$y=w_1x+w_0$把数据分成两类，称其为**决策边界**
$$
Sign(w_1x+w_0)=\pm1
$$



可以将其推广到多变量的情形，可以如此定义一个**超平面**
$$
w^Tx+b=0
$$

一个超平面可以通过一个截距$b$和一个法向量$w$确定，它也称为**权重向量**

如果数据集可以被线性分类器分离，则称其为**线性可分的**

# 硬阈值线性分类器

回到一维情形，假定有权重，$w=(w_0,w_1)^T$，为了表示方便再定义$x=(1,x)^T$，那么决策边界就是直线
$$
w^Tx=0
$$

定义一个阈值函数
$$
Threshhold(z)=
\begin{cases}
1&z\geq0\\
0&z<0
\end{cases}
$$

学习到的函数是
$$
h_w(x)=Threshhold(w^Tx)
$$

# 感知机

感知机是一种硬阈值线性分类器，它可以如图画出

<center>
 <img src="/static/img/e47b6766153851f998eaa1042335f9c0.image.webp"/>
</center>

由于使用了硬阈值函数，在权重空间中几乎所有点梯度都为零，因而常规的梯度下降方法失效，需要使用**权重更新算法求解**

:::info{title="Note"}
$$
w_i=w_i+\alpha(y-h_w(x))x_i
$$
:::

每一次更新随机选择一个样例进行学习

# 基于Logistic函数的线性分类器

硬阈值线性分类器始终做出确定性的判断，不能处理边界上的样本，因而无法应对噪声数据。这可以通过引入软阈值解决
$$
Logistic(z)=\dfrac{1}{1+e^{-z}}
$$


![image.png](/static/img/2792ba3d09ee9fcebbd505c163ad1967.image.webp)


用Logistic函数代替阈值函数得到
$$
h_w(x)=Logistic(w^Tx)
$$

线性分类与感知机

# 线性回归
假设空间：连续值输入、连续值输出的**线性函数**（linear function）
$$
y=w_1x+w_0
$$
其中$w_0$和$w_1$是待学习的系数



# 预测误差
若记学习到的函数为$h_w(x_j)$，单个样本上的误差定义为
$$
y_j-h_w(x_j)
$$
所有样本上的误差则是
$$
\sum_j(y_j-h_w(x_j))
$$
显然不能用这个作为损失函数，引入**最小化平方损失函数$L_2$**，它是所有样本误差的平方和

:::info{title="Note"}
$$
\sum_j[y_j-h_w(x_j)]^2
$$
:::

为了使其最小，应当使得权重参数为极值点
$$
\dfrac{\partial Loss}{\partial w_0}=-2\sum_j[y_j-(w_0+w_1x_j)]=0\\
\dfrac{\partial Loss}{\partial w_1}=-2\sum_j[y_j-(w_0+w_1x_j)]x_j=0
$$
求解该方程即可得到参数
$$
w_1=\dfrac{N\sum_jx_jy_j-\left(\sum_j x_j\right)\left(\sum_j y_j\right)}{N\sum_jx_j^2-\left(\sum_jx_j\right)^2},~ w_0=\dfrac{1}{N}\left(\sum_jy_j-w_1\sum_jx_j\right)
$$

<center>
 
 <hr width=40%>
 
</center>

对于多变量的线性回归，将数据一行一行拼成一个矩阵$X$，权重记为一个列向量$w$，则预测的输出为
$$
y'=Xw
$$
平方误差损失为
$$
L(w)=||Xw-y||^2
$$
令其梯度为零
$$
\nabla_wL(w)=2X^T(Xw-y)=0
$$
解的
$$
w=(X^TX)^{-1}X^T y
$$

# 梯度下降
梯度下降法是指在参数空间中朝着$Loss$下降最快的方向前进，即进行迭代

:::info{title="Note"}
$$
w_i=w_i-\alpha\dfrac{\partial}{\partial w_i}Loss(w)
$$
:::

其中$\alpha$称为**学习率**

若进行梯度计算时使用所有训练样例进行迭代，称为**批梯度下降**，遍历了所有训练样例的一步更新称为**轮(epoch)**

批梯度下降也称确定性梯度下降，其损失曲面是凸函数，可以达到全局最小值。但由于使用所有的样例进行训练，资源消耗比较大，因而引入**随机梯度下降**，在每一步中随机选择少量训练样例进行迭代。不过小批量的随机梯度下降会在最小值附近波动而不收敛。不过它被证明了可以有效找到接近全局最小值的性质良好的局部最小值

# 过拟合与正则化

高维空间中进行多变量回归时可能会导致过拟合，因而添加一个惩罚项，选取要最小化的函数为
$$
Loss(w)+\lambda\cdot penalty(w)
$$
惩罚项称为**正则化函数**，可以选取
$$
penalty(w)=\sum_{j=1}|w_j|^q
$$

线性回归

# 决策树

决策树适用于输入离散的情况。如餐厅等台问题

![image.png](/static/img/ada48f70c0cf0f25137fa9c4ddb69e69.image.webp)




期望中应当构造这样一棵树，沿着树一路往下走最后完成决策过程

![image.png](/static/img/c462075b1246d55b03f7550a5d5b9590.image.webp)

# 决策树的构造-ID3与C4.5

为了使得决策树的效率最高（树的高度应当尽量低），应当先决策重要的属性。“重要”的衡量标准是

:::info{title="Note"}
重要的属性能减小最大的不确定度
:::

一个随机变量的不确定性由**熵**衡量

:::tip{title="熵"}
$$
H(V)=-\sum_kP(v_k)\log_2P(v_k)
$$
:::

为了衡量一个变量对不确定度的贡献，需要引入**条件熵**


:::tip{title="条件熵"}
$$
H(X|Y)=-\sum_{i,j}P(y_j)P(x_i|y_j)\log_2 P(x_i|y_j)
$$
:::

由此定义某个随机变量的**信息增益**，即获知$Y$后减小的$X$的不确定度

$$
Gain(Y)=H(X)-H(X|Y)
$$

每次选择信息增益最大的节点，由此构造高度最矮的决策树，这就是**ID3算法**

<center>
 
 <hr width=40%>
 
</center>

如果某属性的取值特别多，它的熵就会很高，这不利于决策树的构造，需要进行归一化，使得取值多和取值少的属性贡献度一致。**C4.5算法**中采用**信息增益率**代替信息增益做决策

$$
IGR(E_1)=\dfrac{Gain(E_1)}{H(E_1)}=\dfrac{H(W)-H(W|E_1)}{H(E_1)}
$$

决策树

# 监督学习
监督学习的目标是学习一个未知的目标函数$f$

学习的输入称为**训练集**，其中的数据是成对的，称为**有标签样本**
$$
D=\{(x_j,y_j)\}
$$

它满足
$$
y_j=f(x_j)
$$

若$y$是离散的，称为**分类问题**；若是连续的，称为**拟合问题**


学习的结果是目标函数$f$的近似，记为$h$，它取自一个预先设置的假设空间$\mathscr{H}$，其中包含了所有的可能函数

学习的过程是对假设空间施加约束的过程

# 学习效果的衡量

学习误差定义为

:::tip{title="提示"}
学习误差=偏差+方差
:::

其中**偏差**是不同训练集上预测结果偏离期望值的平均程度，方差是改变训练集导致的预测结果的变化。常用**MSE**衡量学习误差

:::info{title="相关信息"}
$$
E(h,f)^2=[E(h)-f]^2+E[h-E(h)]^2
$$
:::

偏差和方差不能同时降低，因而需要根据实际的需要选择不同的权重对偏差和方差进行加权求和，称为**偏差-方差折衷准则**

![image.png](/static/img/1106952230e6f965b58ab1b7ed578266.image.webp)

- 在训练不足时，学习器拟合能力不强，训练
数据的扰动不足以使学习器的拟合能力产生
显著变化，此时偏差主导泛化错误率
- 随着训练程度加深，学习器拟合能力逐渐增
强，训练数据的微小扰动导致学习器发生显
著变化，此时方差逐渐主导泛化错误率
- 训练充足后，学习器的拟合能力非常强，训
练数据的轻微扰动都会导致学习器的显著变
化，若训练数据自身非全局特性被学到则会
发生过拟合


# 模型评估

机器学习希望找到一个和未来的样例最佳拟合的假设。每个样例应当满足
- 每个样例出现的概率应当相等
- 每个样例出现与先前出现的样例无关，即是独立的

最佳拟合即希望错误率最小，即$h(x)\neq y$的比例。不过根据实际情况，机器学习中用**损失函数**代替错误率

损失函数$L(x,y,y')$定义为当真实情况为$f(x)=y$时，模型预测值为$y'$的效用损失，即输入为$x$时，输出$y$与$y'$的效用差值

对于回归任务常用的度量是**均方误差MSE**
$$
E(f;D)=\dfrac{1}{m}\sum_{i=1}^m(f(x_i)-y_i)^2
$$

也可以使用**平均绝对值误差MAE**
$$
E(f;D)=\dfrac{1}{m}\sum_{i=1}^m|f(x_i)-y_i|
$$

对于分类任务，错误率和精度是常用的性能度量
- 错误率：分错样本占样本总数的比率
- 精度（正确率）：分对样本占样本总数的比率


$$
E(f;D)=\dfrac{1}{m}\sum_{i=1}^m\mathbb{I}(f(x_i)\neq y_i),~acc(f;D)=1-E(f;D)
$$

统计真实标记和预测结果的组合可得到**混淆矩阵**

![image.png](/static/img/5a08a5a8dbef966f92d7b0e67954e214.image.webp)

定义**查准率**和**查全率**
$$
查准率P=\dfrac{TP}{TP+FP},~查全率P=\dfrac{TP}{TP+FN}
$$

这是一对矛盾的指标，不可能都高。对样本进行分类时，模型给出样本为目标类别的概率。根据预测结果按正例可能性大小对样例进行排序，并逐个把样本作为正例进行预测，则可以得到查准率-查全率曲线，简称**P-R曲线**

![image.png](/static/img/841585751e189ddf1e6bb6120c736775.image.webp)

平衡点取为
$$
查准率=查全率
$$

对于P-R曲线有交叉的分类器可以用平衡点衡量性能高低。更常用的是F1度量
$$
F1=\dfrac{2PR}{P+R}=\dfrac{2TP}{总数N+TP-TM}
$$

若对查准率和查全率的重视程度不同，应用$F_\beta$
$$
F_\beta=\dfrac{(1+\beta^2)PR}{\beta^2\cdot P+R}
$$

- $\beta=1$：F1
- $\beta>1$：重视查全率
- $\beta<1$：重视查准率

以假正例率为横轴，真正例率为纵轴，可以画出**ROC曲线**

![image.png](/static/img/20f6f573ccdd3b5b6b11d990c8adb1f1.image.webp)

![image.png](/static/img/7e91d24215011f84daf7dc8e0656751a.image.webp)

给定$m^+$个整理和$m_-$个反例，根据预测结果对样本排序，将分类阈值设为每个样本的预测值，记样本坐标
$$
(x:序号, y:预测值)
$$

进行坐标映射
$$
(x,y)\to
\begin{cases}
(x,y+\dfrac{1}{m^+})&真正例\\
(x+\dfrac{1}{m^-},y)&假正例
\end{cases}
$$
连接邻接点得到ROC图，面积称为**AUC值**

![image.png](/static/img/d935b7361be5420fc6825dcbeeecb9cc.image.webp)

# 训练集、测试集、验证集
一般将样例分为两组
- **训练集**(Training set)：用于训练从而得到假设
- **测试集**(Test set)：用于评估假设的错误率

若模型需要超参数优化，或是评估不同的备选模型，还需要**验证集** (Validation set)

直接将数据集划分为两个互斥集合的方式称为**留出法**。若样例数量不够，无法构成这三个数据集，可以采取如下的办法
- **k折交叉验证**（k-fold cross-validation）的方法：每个样例都被作为训练数据和验证数据，但不同时提供
- **数据增强**（Data Augmentation）：使用少量数据通过先验知识产生更多的相似生成数据来扩展训练数据集

k折交叉验证即将数据集分层采样划分为k个大小相似的互斥子集，每次用$k-1$子集的并作为训练集，余下一个子集作为测试集，最终返回k个测试结果的均值。常用k取10

![image.png](/static/img/799b77777462c87966a660bfa3642480.image.webp)

对数据的划分方式可能存在多种，所以可以随机使用不同的划分方式重复p次，评估结果取为p次结果的均值，称为**p次k折交叉验证**

在数据集较小时，可以对数据集进行有放回采样。假定数据集大小为m，进行m次有放回采样得到训练集，会存在一些样本多次出现，一些样本不出现。对于一个样本，一次采样不被抽到的概率为
$$
1-\dfrac1m
$$
所以m次采样都不被抽到的概率为
$$
\left(1-\dfrac1m\right)^m
$$
令m趋于无穷得到
$$
\lim_{m\to+\infty}\left(1-\dfrac1m\right)^m=\dfrac{1}{e}=0.368
$$
约摸三分之一的样本不会被抽到。这种方法称为**自助法**

# 泛化与过拟合
- **过拟合**：创建的模型与训练数据过于匹配，以致于模型无法对新数据做出正确的预测
- **欠拟合**：在训练集和测试集上的误差都很大
- **泛化能力**：指模型对以前未见过的新数据做出正确预测的能力

监督学习

# 贝叶斯网络

贝叶斯网络是一张图，用`节点`表示随机变量，用一组`有向边`连接节点。如果一条边从$X$指向$Y$，则称$X$是$Y$的父节点

贝叶斯网络是一个无环图，对于每一个节点都有一张概率表，表示在其父亲给定的条件下节点的取值概率

可以简单地将边理解为因果关系



# 朴素贝叶斯

朴素贝叶斯的图由一个父节点和$n$个子节点组成，在父节点的条件下各子节点独立

![image.png](/static/img/6e754ef9c4bd36e3853ab7a3b8c77fdd.image.webp)

父节点没有父亲，它记录它自己的概率
$$
P(Cause)
$$
各个子节点记录在其父亲取各值的条件下取值的概率
$$
P(Effect|Cause)
$$

# 一般的贝叶斯网络

一个浅显的例子是

![](https://gbwater.icu/static/img/fb80bf5d3c0236d2c056487d64fb9bfd.image.webp)

# 全局语义

如果需要查询$n$个节点取值的联合概率
$$
P(x_1,x_2,\cdots,x_n)
$$
它们对应的变量节点记为
$$
X_1,X_2,\cdots,X_n
$$
由链式法则，应有
$$
P(x_1,x_2,\cdots,x_n)=P(x_n|x_{n-1},x_{n-2,\cdots,x_1})P(x_{n-1},x_{n-2},\cdots,x_1)
$$
将后面的联合概率进一步拆解，最终会得到

:::info{title="Note"}

$$
P(x_1,x_2,\cdots,x_n)=P(x_n|x_{n-1},x_{n-2,\cdots,x_1})P(x_{n-1}|x_{n-2},\cdots,x_1)\cdots P(x_1)
$$

:::

如果这些节点存在一种顺序，满足

1. 每个节点的父亲在前面的节点中
$$
Parent(X_i)\subseteq {X_{i-1},X_{i-2},\cdots,X_1}
$$
2. 在给定父节点为条件的情况下，它与前面的其他节点是独立发的
$$
P(X_i|X_{i-1},\cdots,X_N)=P(X_i|Parent(X_i))
$$

那么联合概率就可以表示为乘积

:::info{title="Note"}
$$
P(X_1,X_2,\cdots,x_n)=\prod_i P(X_i|Parent(X_i))
$$
:::

一个良好的贝叶斯网络应当能够满足这个条件

# 局部语义
注意到上一节“顺序”中的第二条

> 2. 在给定父节点为条件的情况下，它与前面的其他节点是独立发的
> $$
> P(X_i|X_{i-1},\cdots,X_N)=P(X_i|Parent(X_i))
> $$

它也可以表述为

1. 给定一个节点的父节点, 那么它与其非后代节点条件独立
2. 给定一个节点的父节点、子节点和子节点的父节点（马尔可夫毯）, 其条件独立与网络中其他所有节点

# 枚举推断

枚举推断即利用
$$
P(X_1,X_2,\cdots,x_n)=\prod_i P(X_i|Parent(X_i))
$$

需要枚举所有的可能事件。在上面的简单例子中

![](https://gbwater.icu/static/img/fb80bf5d3c0236d2c056487d64fb9bfd.image.webp)

查询$P(B|j,m)$
$$
P(B|j,m)=\alpha\sum_e\sum_aP(B,j,m,e,a)=\alpha\sum_e\sum_aP(m|a)P(j|a)P(a|B,e)P(B)P(e)
$$

计算时考虑$B$的两种取值可能，它们具有相同的$\alpha$，计算完成后它们之和应当为$1$，做归一化得到系数$\alpha$

<center>
 
<hr width=30%/>
 
</center>

也可以采取深度优先的方式,从根节点（根本原因）出发做DFS，遍历所有情况。虽然也需要 $ O(2^n)$ 的时间复杂度，但是空间复杂度变为了$O(n)$


![image.png](/static/img/7433df7604e2cfbe39d93252738ffcd0.image.webp)

# 变量消元法

定义**逐点乘积**操作$\times$，它将合并两个多元函数中的变量
$$
f(X,Y)\times g(Y,Z)=h(X,Y,Z)
$$

对于一组自变量的取值$(x,y,z)$，$h(x,y,z)$定义为
$$
h(x,y,z)=f(x,y)\cdot g(y,z)
$$
再定义**求和消元**，它通过枚举某个自变量的所有取值并求和，进而消去它
$$
\sum_X h(X,Y,Z)=\sum_xh(x,Y,Z)
$$
对于布尔变量，自然有
$$
\sum_X h(X,Y,Z)=h(x,Y,Z)+h(\neg x,Y,Z)
$$

那么对于上面的计算

> $$
> P(B|j,m)=\alpha\sum_e\sum_aP(m|a)P(j|a)P(a|B,e)P(B)P(e)=\alpha P(B)\sum_eP(e)\sum_aP(a|B,e)P(m|a)P(j|a)
> $$

它就可以写为
$$
\alpha f_1(B)\times\sum_ef_2(e)\sum_af_3(a,B,e)\times f_4(a)\times f_5(a)
$$

使用逐点乘积与求和消元即可完成计算