传统的监督学习方法

0. 监督学习的分类和任务

李航书将监督学习分为生成方法和判别方法。两者的定义如下：

生成方法：由数据学习联合概率分布$P(X,Y)$，然后求出条件概率分布$P(Y

X) = P(X,Y)/P(X)$作为预测的模型，即生成模型。（朴素贝叶斯，隐马尔可夫模型）

判别方法：由数据直接学习决策函数$f(X)$或者条件概率分布$P(Y|X)$作为预测的模型，即判别模型。（感知机，k近邻，决策树，回归，提升，条件随机场）李航书中的监督学习任务包括分类、标注、回归。
分类：输出离散的类别标签，如垃圾邮件分类。
标注：输出序列标签，如中文分词，地图匹配等Seq2Seq任务。HMM和CRF是标注任务的经典模型。
回归：输出是连续的数值，如房价预测，量化交易等。
1. 感知机

我的理解：解决不了XOR的老东西，没有激活函数的单个神经元
李航：二分类线性模型，学习一个超平面将样本切分为两类。SVM的本质是带L2正则化的感知机
感知机模型：$f(x) = sign(w \cdot x + b)$
感知机策略：在数据是线性可分的前提下，学习一个超平面将样本切分为两类，即学习法向量w和截距b。（线性可分的数学表达：所有样本满足$y_i(w \cdot x_i + b) > 0$）
损失函数:为所有样本点到超平面的距离和（不选用误分类点总数因为不可导）: $ \sum{\omega_i}^{-1} (\omega_i \cdot x_i + b)$ 为了计算方便去掉$\omega$的倒数;$L(\omega, b) = \sum_iy_i(\omega_i \cdot x_i + b)$
感知机学习算法：由于感知机的线性可分数据集合性质，感知机的原始形式是必然收敛的，并且可以算出误分类次数上界，可能的分隔超平面有无数种。（Novikoff定理，李航书42）
1. 原始形式：每次从误分类点集合中选取一个点$x_i \in X$ 进行梯度更新 $\omega = \omega + \alpha y_i x_i$和$b = b+ \alpha y_i$直到$X= \emptyset$
2. 对偶形式：先算Gram矩阵 $G = [x_i \cdot x_j]_{N\cdot N}$；
3. 为什么用对偶：对偶形式将学习过程中暗含的内积操作替换为了可预处理好的查表操作，每取出一个样本的更新复杂度由 O(n) 降为了 O(1)，但付出了初始化 Gram 矩阵 O(NNn) 的代价。当 N 较小，且实际所需迭代次数较多（难分类）时，效率提升明显。

2. k近邻

2.1 KNN的原理

k-neighbors既可以做分类也可以做回归，李航书只说了分类，原理一样。
k近邻给定一个训练数据集合$T = {(x_1, y_1), (x_2, y_2), …, (x_N, y_N)}$，其中$x_i \in X \subseteq R^n$为实例的特征向量，$y_i \in Y$为实例的类别，$i=1,2,…,N$。对于一个新的输入实例$x$，算法会搜索训练集中与$x$最近的k个实例，然后输出这k个实例中出现最多的类别作为$x$的类别。KNN不具有显式学习过程。

k近邻的三个要素：距离度量（如欧式距离、马氏距离等）、k值的选择、分类决策规则（如多数投票、权重投票等）。

距离度量：欧式距离$d(x_i, x_j) = \sqrt{\sum_{l=1}^n(x_i^{(l)} - x_j^{(l)})^2}$，马氏距禽$d(x_i, x_j) = \sqrt{(x_i - x_j)^T \Sigma^{-1} (x_i - x_j)}$，曼哈顿距离$d(x_i, x_j) = \sum_{l=1}^n

x_i^{(l)} - x_j^{(l)}

$，切比雪夫距离$d(x_i, x_j) = \max_l

x_i^{(l)} - x_j^{(l)}

$。

k的选择：k值较小，模型复杂，容易过拟合；k值较大，模型简单，容易欠拟合。一般通过交叉验证选择最优的k值。
分类决策规则：多数投票规则，即输出实例的多数类别作为预测类别；加权投票规则，即对距离远近进行加权，距离近的实例权重大。
2.2 K-D树

实现KNN时需要考虑如何对训练数据进行快速搜索，kd树可以将复杂度从O(n)的线性扫描降低到0(logn).
kd树 对k维空间中的实例点进行存储以便对其进行快速检索,是二叉树，表示对k维空间的一个划分。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。(这里的k和KNN的不是一个意思)

构造kd树：构造平衡kd树，选择坐标轴和切分点，递归地构造左右子树，$T = {(x_1, y_1), (x_2, y_2), …, (x_N, y_N)}$，其中$x_i \in X \subseteq R^n$为实例的特征向量，先选择$x_1$所在坐标轴，训练数据集中所有实例在该坐标轴上的中位数为切分点，将数据集划分为两个子区域，将落在分割超平面上的实例点保存在根节点，然后递归地构造左右子树。见李航P55图。

def createKDTree(dataSet, depth=0):
  if len(dataSet) == 0: # 数据集为空，递归出口
      return None
  n = len(dataSet[0])
  axis = depth % n 
  dataSet.sort(key=lambda x: x[axis])
  median = len(dataSet) // 2 # 选取切分点
  return {
      'point': dataSet[median], # 保存切分点
      'left': createKDTree(dataSet[:median], depth + 1)，# 递归构造左子树
      'right': createKDTree(dataSet[median + 1:], depth + 1) # 递归构造右子树
  }

kd树搜索：给定一个实例点x，搜索kd树，找到包含x的叶节点，从而找到k个最近邻点。（下面k=1为例子）
1. 从根节点出发，递归地向下访问kd树。若目标点x当前维的坐标小于切分点的坐标，则移动到左子树，否则移动到右子树。直到子节点为叶节点，此时的子节点即为“当前最近点”
2. 递归地向上回退，对于每个节点，如果该节点保存的实例点比当前最近点更近，则更新当前最近点。
3. 否则检查该节点的兄弟区域内是否有以目标点为球心、以目标点与当前最近点间距为半径的超球体相交的可能，（有就说明兄弟点里有更近的点，需要检查兄弟点）。
4. 否则继续向上回退，直到根节点，搜索结束，输出“当前最近点”的类别，即为x的类别。

3. 朴素贝叶斯

3.1 基本方法&&模型假设

基于特征条件独立假设，即对已知类别，假设所有特征相互独立。朴素贝叶斯分类器是一种生成模型，通过训练数据学习联合概率分布$P(X,Y)$，然后求出条件概率分布$P(Y|X)$作为预测的模型。
特征条件独立：$P(X=x|Y=c_k) = P(X_1 = x_1, X_2 = x_2, …,X_n= x_n|Y=c_k) = \prod_{i=1}^nP(X_i = x_i|Y)$。好处：参数规模大大减小，降低了学习难度（和准确度）。
朴素贝叶斯模型：对于给定的$x$,计算模型输出$Y$属于各个类别$c_k$的概率，将最大可能性的作为结果输出。$P(Y=c_k) = \frac{\sum_{i=1}^N I(y_i = c_k)}{N}$，$P(X=x|Y=c_k) = \prod_{i=1}^nP(X_i = x_i|Y=c_k)$，$P(Y=c_k|X=x) = \frac{P(X=x|Y=c_k)P(Y=c_k)}{\sum_kP(X=x|Y=c_k)P(Y=c_k)}$

上述模型用贝叶斯定理+全概率公式记忆；$P(Y|X) = \frac{P(X|Y)P(Y)}{P(X)}$，分母全概率公式展开，$P(X) = \sum_kP(X|Y=c_k)P(Y=c_k)$；分子特征独立假设展开，$P(X|Y=c_k) = \prod_{i=1}^nP(X_i = x_i|Y=c_k)$。
朴素贝叶斯分类器：对于给定的实例$x$，计算$P(Y=c_k|X=x)$，选择使得$P(Y=c_k|X=x)$最大的类别作为输出：$y = \arg\max_{c_k}P(Y=c_k)\prod_{i=1}^nP(X_i = x_i|Y=c_k)$ （为什么不需要分母？因为对于任意$y=c_k$,分母一样，所以不要算了。）
后验概率最大化：朴素贝叶斯将实例分到后验概率最大的类中，等价于期望风险最小化。（证明见李航P61，0-1损失函数推的）
3.2 参数估计

朴素贝叶斯作为生成模型，学习联合分布P(X,Y)的参数，即先验概率$P(Y=c_k)$和条件概率$P(X=x|Y=c_k)$。这两个可以用MLE估计。比较符合直觉，就是样本的统计频率。
先验概率$P(Y=c_k)$：$P(Y=c_k) = \frac{\sum_{i=1}^N I(y_i = c_k)}{N}$，即类别$C_K$在训练集中出现的频率,显然。

**条件概率$P(X=x

Y=c_k)$**：$P(X_i = x_i

Y=c_k) = \frac{\sum_{i=1}^N I(x_i^{(j)} = a_{ij}, y_i = c_k)}{\sum_{i=1}^N I(y_i = c_k)}$，即在类别$C_K$中，第j个特征取值为$a_{ij}$的频率。

MLE估计有时候会出概率为0，所以可以贝叶斯估计带平滑系数$\lambda$,当$\lambda=1$时，称为拉普拉斯平滑。

先验概率$P(Y=c_k)$：$P(Y=c_k) = \frac{\sum_{i=1}^N I(y_i = c_k) + \lambda}{N + K\lambda}$，$\lambda$是一个常数，$K$是类别数。
条件概率$P(X=x|Y=c_k)$：$P(X_i = x_i|Y=c_k) = \frac{\sum_{i=1}^N I(x_i^{(j)} = a_{ij}, y_i = c_k) + \lambda}{\sum_{i=1}^N I(y_i = c_k) + S\lambda}$，$\lambda$是一个常数，$S$是特征取值数。
3.3 naive bayes algorithm

输入：训练数据$T = {(x_1, y_1), (x_2, y_2), …, (x_N, y_N)}$，实例$x$
step1: 计算先验概率和条件概率，用3.2里的方法都行，核心从T中算出$P(Y), P(X|Y)$
step2: 对于给定的实例$x = ({x^{(1)},x^{(2)}…,x^{(n)}})^T$，依次计算对于$c_1…c_k$的 $y = \arg\max_{c_k}P(Y=c_k)\prod_{i=1}^nP(X_i = x_i|Y=c_k)$
step3: 确定类别，最大的类别作为输出：$y = \arg\max_{c_k}P(Y=c_k)\prod_{i=1}^nP(X_i = x_i|Y=c_k)$

4. 决策树

决策树通过消除训练样本的信息不确定来进行分类/回归。既可以看成是if-then规则的集合，也可以看成是定义在特征空间与类空间上的条件概率分布。决策树的本质是从训练集$T$中归纳分类规则，由于同一个T对应多个决策树，需要找到泛化能力最好的，因此损失函数一般有正则项，为了防止过拟合，需要剪枝。
决策树要素：特征选择、树的生成、树的剪枝

4.1 特征选择，ID3，C4.5，CART

特征选择决定节点的划分，ID3，C4.5，CART是三种常见的决策树生成算法，采用不同的特征选择准则A进行划分。
熵的定义：$H(D) = -\sum_{k=1}^K\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$，其中$C_k$是D中属于第k类的样本子集，K是类别数。观察发现H与具体的D取值无关，和分布概率p有关，所以也可以改写为$H(p) = -\sum_{k=1}^Kp_klog_2p_k$。单位是bit，0log0=1log1=0。H(p)越大，随机变量不确定性越大，样本D越混乱。
条件熵的定义：$H(D|A) = \sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)$，其中$H(D_i) = -\sum_{k=1}^K\frac{|C_{ik}|}{|D_i|}log_2\frac{|C_{ik}|}{|D_i|}$，$C_{ik}$是$D_i$中属于第k类的样本子集，K是类别数。条件熵H(D|A)表示在特征A给定的条件下，对数据集D进行划分的经验熵。

ID3：信息增益最大化，定义为：$g(D, A) = H(D) - H(D

A)$；得知特征A的信息后，数据集D的不确定性减少的程度；问题是信息增益偏向于选择取值较多的特征（取值多的更混乱，信息增益大），因此引入信息增益比。

C4.5：信息增益比最大化，定义为：$g_R(D, A) = \frac{g(D, A)}{H_A(D)}$，其中$H_A(D) = -\sum_{i=1}^n\frac{

D_i

}{

}log_2\frac{

D_i

}{

}$，$n$是特征A的取值数。为了能解决回归问题，CART树引入了基尼指数。

CART分类：基尼指数最小化，定义为：$Gini(D) = \sum_{k=1}^K\sum_{k’\neq k}p_kp_{k’} = 1 - \sum_{k=1}^Kp_k^2$，$Gini(D

A) = \sum_{i=1}^n\frac{

D_i

}{

}Gini(D_i)$，$Gini(D

A)$和熵的一半曲线接近，都可以衡量有序程度。

CART回归：最小二乘回归树，定义为：$J(D) = \sum_{i=1}^N(y_i - c)^2$，$J(D|A) = \sum_{i=1}^n\frac{|D_i|}{|D|}J(D_i)$，$c = \frac{1}{N}\sum_{i=1}^Ny_i$，即用特征A划分后，每个叶节点的值为该节点所有样本的均值。

4.2 建树和剪枝

建立决策树的方法核心区别就是特征A选择，建树流程如下：输入训练样本集$D$，特征集$A$，阈值$\epsilon$
STEP1：递归出口，如果$D$中样本全属于同一类别$C_k$，将$C_k$作为该节点类别；如果A为空，将D中样本最多的类$C_k$作为节点类别；返回决策树T。
STEP2：递归流程，不满足递归出口，选择最优特征A，对A的每一个可能取值$a_i$,将D划分为若干非空的$D_1,D_2…,D_i$，生成节点，并递归地对子集生成节点。
STEP3：若A的信息增益小于阈值$\epsilon$，剪枝防止过深，将该节点标记为叶节点，类别为D中样本最多的类别；返回T。
剪枝：决策树生成后，自底向上对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来泛化性能提升，则将该子树替换为叶节点。减少深度。
具体方法：
对于一颗完全生长的决策树$T_0$,任意非叶节点t，计算剪枝前后的损失函数$C_\alpha(t) = C(t) + \alpha|T_t|$，其中$C(t)$是节点t训练的损失函数，如信息增益之类，$|T_t|$是t的叶节点数，$\alpha$是参数。

其实会发现剪枝对应的损失函数就是带有正则项的损失函数，正则项是叶节点数，$\alpha$是参数。
CART剪：输入：决策树$T_0$，参数$\alpha = \inf$，轮数$k$,输出：最优子树$T_\alpha$

自底向上对非叶节点t计算$C_\alpha(t)$，从下往上计算，对每个t，计算$C(T_t)$,$

T_t

更新$g(t) = \frac{C(t) - C(T_t)}{ T_t - 1}$； $\alpha = min(\alpha, g(t))$
对每一个$g(t) = \alpha$的t，剪枝，得到$T$
$k = k+1$, $\alpha_k = \alpha$，$T_k = T$
如果$T_k$不是单节点树，返回第二步，否则记k=n，返回$T_n$
用交叉验证法在${T_0, T_1,…T_n}$选择$T_{\alpha}$，使得损失函数最小。

5. Logistic回归

5.1 二项逻辑回归

逻辑分布：随机变量X服从逻辑分布， $F(x) = P(X<=x) = \frac{1}{1+e^{-(x-\mu)/\sigma}}$ ,其中$\mu$是位置参数，$\sigma$是尺度参数。逻辑分布的密度函数是$P(X=x) = \frac{e^{-(x-\mu)/\sigma}}{\sigma(1+e^{-(x-\mu)/\sigma})^2}$
逻辑分布的分布函数是Sigmod曲线，，$F(x)$以点$(\mu, 0.5)$为中心对称，$\sigma$越小，曲线越陡峭,越接近符号函数。

二项逻辑回归：逻辑回归是一种广义线性回归模型，适用于二分类问题。逻辑回归模型的假设是：给定特征X，输出Y=1的概率是X的线性组合的sigmoid函数，即$P(Y=1

X) = \frac{1}{1+e^{-(w \cdot x + b)}}$，$P(Y=0

X) = 1 - P(Y=1

X)$。逻辑回归将比较两个概率的大小，将$x$划分到概率更大的一类中\或者说，模型输出的是正类的概率。

几率odds：一件事情发生的概率p和不发生的概率1-p的比值，$odds = \frac{p}{1-p}$，对数几率logit：$logit(p) = log\frac{p}{1-p}$，对于逻辑回归模型，$log\frac{P(Y=1

X)}{1-P(Y=1

X)} = w \cdot x + b$。

逻辑回归的参数估计：最大化似然函数，即最小化交叉熵损失函数。证明过程见李航P93
5.2 多项逻辑回归

在二项回归模型基础上，多项逻辑回归是一种广义线性回归模型，适用于多分类问题。多项逻辑回归模型的假设是：给定特征X，输出Y=c的概率是X的线性组合的softmax函数，即$P(Y=c|X) = \frac{e^{w_c \cdot x + b_c}}{\sum_{c=1}^Ce^{w_c \cdot x + b_c}}$，$c=1,2,…,C$。多项逻辑回归将比较C个概率的大小，将$x$划分到概率最大的一类中。
对于K个类别的多项逻辑回归，$Y=c$的概率是$P(Y=c|X) = \frac{e^{w_c \cdot x + b_c}}{\sum_{c=1}^Ce^{w_c \cdot x + b_c}}$，$c=1,2,…,C$。

传统的监督学习方法

0. 监督学习的分类和任务

1. 感知机

2. k近邻

2.1 KNN的原理

2.2 K-D树