西瓜书笔记

于是，

通过上式，可知泛化误差可分解为方差、偏差与噪声之和。回顾偏差、方差、噪声的定义：

• 偏差：度量了学习算法的期望预测与真实结果的偏离程度，刻画了学习算法本身的拟合能力。
• 方差：度量了同样大小的训练集的变动导致的学习性能的变化，刻画了数据扰动所造成的影响，或者说刻画了模型的稳定性和泛化能力。
• 噪声：表达了当前任务上任何学习算法所能达到的期望泛化误差的下界，即刻画了学习问题本身的难度。

通过对泛化误差进行分解说明，模型泛化性能是由学习算法的能力、数据的充分性以及任务本身的难度所共同决定的。模型欠拟合表现为偏差较大, 此时偏差主导了泛化错误率；模型过拟合表现为偏差小但是方差很大，方差主导了泛化错误率。

一般来说，偏差与方差是有冲突的，这称为偏差-方差窘境（bias-variane dilemma）。

第 3 章 线性模型

3.5 多分类学习

3.6 类别不平衡问题

公式中，\(y\) 是预测值，分类器决策规则为：若 \(\frac{y}{1-y}\) 则预测为正例。令 \(m^+\) 表示正例数目， \(m^-\) 表示反例数目，则观测几率是 \(\frac{m^-}{m^+}\)。

类别不平衡学习的一个基本策略是 “再缩放”（rescaling）。再缩放技术主要有三种方法实现：

• 对训练集的反类样例进行“欠采样”（undersampling），即去除一些反例使得正负样例数目接近，然后再进行学习。
• 对训练集的正类样例进行“过采样”（oversampling），即增加一些正例使得正、负样例数目接近，然后再进行学习（或者叫模型训练）。
• 直接对原始训练集进行学习，但是在对训练好的分类器进行预测时，将式（3.48）嵌入到分类器推理过程中，称为“阈值移动”（threshold-moving）。

值得注意的是过采样的方法不能简单地对初始正例样本进行重复采样，否则会招致严重的过拟合；过采样方法的代表性算法 SMOTE 是通过对训练集的正例进行插值来产生额外的正例（图像数据就进行数据增强）。

第 5 章 神经网络

5.1 神经元模型

神经网络有很多种定义，一种较为广泛的定义是，其是由具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应。

神经网络中最基本的成分是神经元（neuron）模型，即上述定义中的简单单元。经典的"M-P神经元模型”如下所示，其中的 \(f\) 表示激活函数，\(w\) 表示神经元权重。

5.2 感知机与多层网络

感知机（perception）由两层神经元组成，如下图所示，输入层接收外界输入信号后传递给输出层，输出层是 M-P 神经元，也称“阈值逻辑单元”（threshold logic unit）。感知机能容易地实现逻辑与、或、非运算，只需要设置合理的 \(w\)、\(\theta\) 参数。感知机模型的公式可表示为：

给定训练数据集，感知机的 \(w\) 和 \(\theta\) 参数可通过学习得到。其学习规则很简单，对于训练样本\((x,y)\)，如果感知机输出为 \(\hat{y}\)，则感知机的参数将做如下调整：

其中 \(\eta\) 称为学习率，从上式可以看出当感知机预测输出 \(\hat{y}\) 和样本标签 \(y\) 相等时，参数不改变；否则将根据偏差的严重程度进行相应调整。

需要注意的是，感知机只能解决与、或、非这样的线性可分（即存在一个线性超平面将它们分开）问题，但是甚至不能解决异或这样简单的非线性可分问题。

要解决非线性可分问题，可以使用多功能神经元。如下图所示的就是一种常见的“多层前馈神经网络”（multi-layer feedforward neural），每层神经元与下一层神经元全互连，同层神经元之间不连接，也不存在跨层连接。

“前馈” 并不意味着网络中信号不能反向传播，而单纯是指网络拓扑结构上不存在环或回路。

5.3 误差反向传播算法

很明显多层神经网络的学习能力比单层网络（单层感知机）强得多。感知机参数的学习规则很简单，因此其对于多层神经网络是不够用的，由此，诞生了强大的误差反向传播（error BackPropagation，简称 BP）算法，并使用至今，现阶段的所有深度神经网络的参数都是由 BP 算法训练得到的。

反向传播指的是计算神经?络参数梯度的?法。总的来说，反向传播依据微积分中的链式法则，沿着从输出层到输?层的顺序，依次计算并存储?标函数有关神经?络各层的中间变量以及参数的梯度。

前向传播：输入层-->输出层；反向传播：输出层-->输入层。

下面通过前馈神经网络的 BP 算法来深入理解 BP 过程。

给定训练集 \(D = {(x_1, y_1), (x_2, y_2),...,(x_m, y_m)}, x \in \mathbb{R}^d, y_i \in \mathbb{R}^l\)，即每个输入样本都由 \(d\) 个属性表征，模型输出的是 \(l\) 维实值向量。为了便于 BP 算法的推导，下图给出了一个拥有 \(d\) 个输入神经元、\(l\) 个输出神经元、\(q\) 个隐层神经元的多层前馈神经网络，其中输出层第 \(j\) 个神经元的阈值用 \(\theta_j\) 表示，隐层第 \(h\) 个神经元的阈值用 \(\gamma_h\) 表示。输入层第 \(i\) 个神经元与隐层第 \(h\) 个神经元之间的连接权重参数为 \(v_{ih}\)，隐层第 \(h\) 个神经元与输出层第 \(j\) 个神经元之间的连接权为 \(w_{hj}\)。记隐层第 \(h\) 个神经元接收到的输入为 \(\alpha_h = \sum_{i=1}^{d}v_{ih}x_i\)，输出层第 \(j\) 个神经元接收到的输入为 \(\beta_j = \sum_{h=1}^{q}w_{hj}b_h\)，其中 \(b_h\) 为隐层第 \(h\) 个神经元的输出。这里假设隐层和输出层神经元的激活函数都为 Sigmoid 函数。

对训练样本 \((x_k,y_k)\)，假设神经网络的输出为 \(\hat{y}_k =(\hat{y}_1^k,\hat{y}_2^k,...,\hat{y}_l^k)\)，即

则网络在 \((x_k,y_k)\) 上的均方误差损失为

输入层到隐层需要 \(d \times q\) 个权重参数、隐层到输出层需要需要 \(q \times l\) 个权重参数，以及 \(q\) 个隐层的神经元阈值、\(l\) 个输出层的神经元阈值。BP 是一个迭代学习算法，在迭代的每一轮中采用广义的感知机学习规则对参数进行更新估计，因此任意参数 \(v\) 的更新估计表达式都可为

下面我会首先推导出隐层到输出层的权重 \(w_{hj}\) 更新公式，而后类别推导 \(\theta_{j}\)、\(v_{ih}\)、\(\gamma_{h}\)。

BP 算法是基于梯度下降（gradient desent）策略，以目标的负梯度方向对参数进行调整，对式\((5.4)\)的误差 \(E_k\)，给定学习率 \(\eta\)，可得权重参数更新公式如下：

同时，

注意到 \(w_{hj}\) 先影响到第 \(j\) 个输出层神经元的输入值 \(\beta_j\)，再影响到其输出值 \(\hat{y}_j^k\)，最后才影响到损失 \(E_k\)，根据梯度的链式传播法则，有

根据前面 \(\beta_j\) 的定义，显然有

再因为 Sigmoid 函数的一个很好的性质：

再联合式\((5.3)\)和\((5.4)\)，有：

注意这里的 \(f\) 是 Sigmoid 函数。令 \(g_{j} = \hat{y}_j^{k}(1-\hat{y}_j^{k})(y_{j}^{k} - \hat{y}_{j}^{k})\) 。将 \(g_{j}\) 和式 \((5.8)\) 带入式 \((5.6)\)，就得到了 BP 算法中关于 \(w_{hj}\) 的更新公式：

类似式 \((5.10)\) 的推导过程可得其他参数的更新公式：

\(v_{ih}\) 梯度的详细推导公式如下所示。因为，

所以

最后一层激活使用 softmax 激活和交叉熵损失函数的反向传播推导，可参考这里。

学习率 \(\eta \in (0,1)\) 控制着算法每一轮迭代中更新的步长，若太大则容易振荡，太小则收敛速度幽会过慢。有时为了做精细调节，可令式\((5.11)\)与\((5.12)\)使用 \(\eta_1\)， 式\((5.13)\)与\((5.14)\)使用 \(\eta_2\)，两者未必相等。

下图给出了 BP 算法的工作流程：

对每个训练样本，BP 算法操作流程如下：

1. 前向传播:将输入样本输入给输入神经元，然后逐层将信号前向传播，直到输出层产生结果。
2. 反向传播：计算输出层的误差，沿着输出层到输入层的顺序，依次计算并存储损失函数有关各层的中间变量及参数梯度，并对参数进行调整。
3. 1，2 过程循环进行，直到达到某些停止条件为止，如训练误差已达到一个很小的值。

停止条件与缓解 BP 过拟合的策略有关。

值得注意的是，BP 算法的目标是要最小化训练集 \(D\) 上的累计误差：

但是我们前面描述的“标准 BP 算法”的计算过程，其实每次仅针对一个训练样本更新连接权重和阈值的，因此，图5.8中算法发更新规则同样也是基于单个 \(E_k\) 推导而得的。如果类似地推导出基于累计误差最小化的更新规则，就得到了累计误差反向传播（accumulated error backpropagation）算法。

一般来说，标准 BP 算法每次更新仅针对单个样本，参数更新很频繁，而且不同样本对进行更新的效果可能出现“抵消”现象。因此，为了达到同样的累计误差极小点，标准 BP 算法往往需要进行更多次数的迭代。而累计 BP 算法直接将累计误差最小化，它是在读取整个训练集 \(D\) 一遍（one epoch）后才对神经网络各层权重参数进行更新，其参数更新频率低得多。但是在很多任务中，累计误差下降到一定程度后，进一步下降会非常缓慢，这是标准 BP 往往会更快获得较好的解，尤其是在训练集 \(D\) 非常大时很明显。

标准 BP 算法和累计 BP 算法的区别类似于随机梯度下降（stochastic gradient descent，简称 SGD）与标准梯度下降之间的区别。

[Hornik et al.,1989] 证明，只需一个包含足够多神经元的隐层（即深度神经网络层数足够多），多层前馈神经网络就能以任意精度逼近任意复杂度的连续函数。但是，深度神经网络层数的选择依然是一个未决问题，在实际应用中通常依靠“试错法”（trial-by-error）调整。

因为神经网络的表示能力太过强大，因此 BP 神经网络在训练过程中经常遭遇过拟合，即训练误差持续降低，但验证集误差却可能上升。目前常用来缓解 BP 网络过拟合问题的策略，有以下两种：

第一种策略是“早停”（early stopping）:将数据分为训练集和验证集，训练集用来更新权重参数，验证集用来估计误差，若训练集误差降低但验证集误差升高，则停止训练，同时返回具有最小验证集误差的权重参数模型。

第二种策略是“正则化”（regulazation）：其基本思想是在误差目标函数中增加一个用于描述网络复杂度的部分，例如连接权重与阈值的平方和。仍令 \(E_k\) 表示第 \(k\) 个训练样本上的误差，\(w_i\)表示连接权重和阈值，则误差目标函数\((5.16)\)更改为：

其中 \(\lambda \in (0,1)\)用于对经验误差与网络复杂度这两项进行折中，常通过交叉验证法估计。

常用的刻画模型复杂度 \(R(w)\) 的函数有两种，一种是 \(L1\) 正则化，即绝对值的之和；另一种是 \(L2\) 正则化，即绝对值平方之和，计算公式如下：

无论是哪一种正则化，其基本思想都是希望通过限制权重的大小，使得模型不能任意拟合训练数据中随机噪声。\(L1\) 与 \(L2\) 有很大区别，\(L1\) 正则化会让参数变得更加稀疏，而 \(L2\) 不会。所谓参数变得更加稀疏是指会有更多的参数变为 0，这样可以达到类似特征选取的功能。

L2范数正则化（regularization）等价于权重衰减的概念。

5.4 全局最小与局部最小

若用 \(E\) 表示神经网络在训练集上的误差，则它显然是关于连接权重 \(w\) 和阈值 \(\theta\) 的函数。此使，神经网络的训练过程可看作是一个参数寻优的过程，即在参数空间中，寻找一组最优参数使得 \(E\) 最小。

显然，参数空间内梯度为零的点，只要其误差函数值小于零点的误差函数值，就是局部极小点；可能存在多个局部极小值，但有且仅有一个全局最小值。

基于梯度的搜索是使用最为广泛的参数寻优方法。在这类方法中，一般先从参数随机初始解出发，迭代寻找最优参数解。每次迭代我们先计算误差函数在当前点的梯度，然后根据梯度确定搜索方向。例如，由于负梯度方向是函数值下降最快的方向，因此梯度下降法就是沿着负梯度方向搜索最优解。若误差函数在当前点的梯度为零，则已达到局部极小，参数更新量也将为零，也意味着参数的迭代更新将在此停止。

在现实任务中，我们常用以下启发式策略（非理论策略）来试图“跳出”局部极小，从而进一步接近全局最小：

• 以多组不同参数值初始化多个神经网络，按标准方法训练后，取其中最小的解作为最终参数。
• 使用”模拟退火“（simulated annealing）技术。模拟退火在每一步都以一定的概率接受比当前解更差的结果，从而有助于”跳出“局部极小。在每次迭代过程中，接收”次优解“的概率要随着时间的推移而逐渐降低，从而保证算法的稳定性。
• 使用随机梯度下降算法。

5.5 其他常见神经网络

2010 年之前常见的神经网络有 RBF 网络、ART 网络、SOM 网络、级联相关网络、Elman网络、Boltzmann 机。

5.6 深度学习

典型的深度学习模型就是很深层（层数很多）的神经网络。值得注意的是，从增加模型复杂度的角度来看，增加隐藏层的数目显然比增加隐藏层神经元的数目更有效，即网络的“深”比“宽”重要。因为隐藏层层数的增加不仅增加了拥有激活函数神经元的数目，还增加了激活函数嵌套的层数，即非线性能力进一步增强。

第 9 章 聚类

9.1 聚类任务

在“无监督学习”中，训练样本是无标签信息的，目标是通过对无标记训练样本的学习来揭示数据的内在性质和规律，为进一步的数据分析提供基础。这类学习任务中应用最广的就是“聚类”（clustering）算法，其他的无监督学习任务还有密度估计（density estimation）、异常检测（anomaly detection）等。

聚类的任务是将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个“簇”（cluster），簇所对应的概念和语义由使用者来把握。

聚类可用作其他学习任务的一个前驱过程。基于不同的学习策略，有着多种类型的聚类算法，聚类算法涉及的两个基本问题是性能度量和距离计算。

9.2 性能度量

聚类性能度量也叫聚类“有效性指标”（validity index），和监督学习的性能度量作用类似，都是用来评估算法的好坏，同时也是聚类过程中的优化目标。

聚类性能度量大致有两类。一类是将聚类结果与某个“参考模型（reference model）”进行比较，称为“外部指标（external index）”；另一类是直接考察聚类结果而不利用任何参考模型，称为“内部指标”（inderna index）。

外部指标包括 Jaccard 指数（简称 JC）、FM 指数（简称 FMI）和 Rand 指数（简称 RI），范围在 [0,1] 之间，且越大越好；内部指标包括 DB 指数（简称 DBI）和 Dunn 指数（简称 DI），DBI 值越小越好，DI 越大越好。

具体计算公式太多了，这里不给出，可以参考原书 199 页。

9.3 距离计算

函数 \(dist(\cdot,\cdot)\) 用于计算两个样本之间的距离，如果它是一个“距离度量”（distance measure），则需满足一些基本性质：

• 非负性：\(dist(x_i,x_j) \geq 0\)；
• 同一性：\(dist(x_i,x_j)=0\) 当前仅当 \(x_i = x_j\)；
• 对称性：\(dist(x_i,x_j) = dist(x_j,x_i)\)；
• 直递性：\(dist(x_i,x_j \geq dist(x_i,x_k) + dist(x_k,x_j))\)。

给定样本 \(x_i = (x_{i1};x_{i2};...;x_{in})\) 与 \(x_j = (x_{j1};x_{j2};...;x_{jn})\)，最常用的是“闵可夫斯距离”（Minkowski distance）。

上式其实就是 \(x_i - x_j\) 的 \(L_p\) 范数 \(\left \| x_i - x_j \right \|_p\)。\(p = 2\)，上式为欧氏距离。

属性通常划分为“连续属性”（continuous attribute）和“离散属性”（categotical attribute），前者在定义域上有无穷多个可能的取值，后者在定义域上是有限个取值。但是在涉及距离计算时，属性上定义了“序”更为重要。能直接在属性上计算距离：“1” 和 “2” 比较近、和“4”比较远，这样的属性称为“有序属性”（ordinal attribute ）；而定义域为{汽车、人、椅子}这样的离散属性则不能直接在属性上计算距离，称为“无序属性”（non-ordinal atribute）。显然，闵可夫斯距离可用于有序属性。

对无序属性采用 VDM（Value Difference Metric），同时将闵可夫斯距离和 VDM 集合可处理混合属性。

9.4 原型聚类

原型聚类算法假设聚类结构能通过一组原型刻画，这里的原型是指样本空间中具有代表性的点。一般算法先对原型进行初始化，然后对原型进行迭代更新求解。采用不同的原型表示、不同的求解方式，将产生不同的算法。

9.4.1 k 均值算法

K-Means 算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为 \(K\) 个簇，让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。

给定样本集 \(D = \{x_1, x_2,...,x_m\}\)，假设簇划分为 \(C = \{C_1,C_2,...,C_m\}\)，算法目标是最小化平方误差。

其中 \(u_i=\frac{1}{C_i}\sum_{x \in C_{i}}x\) 是簇 \(C_i\) 的均值向量，也称质心。上式一定程度上刻画了簇内样本围绕簇均值向量的紧密程度，\(E\) 值越小簇内样本相似程度越高。

找到 \(E\) 的最优解需要靠擦样本集 \(D\) 所有可能的簇划分，这是一个 \(NP\) 难问题。\(k\) 均值算法采用了贪心策略，通过迭代优化近似求解，算法流程如图 9.2 所示。其中第 1 行对均值向量进行初始化，4-8 行与 9-16 行依次对当前簇划分即均值向量迭代更新，若更新后聚类结果保持不变，则在第 18 行将当前簇划分结果返回。

参考此文章的代码，我修改为如下精简版的 K-Means 算法代码。

def kmeans(dataset, k):
    """K-means 聚类算法

    Args:
        dataset ([ndarray]): 数据集，二维数组
        k ([int]): 聚簇数量
    """
    m = np.shape(dataset)[0]  # 样本个数
    
    # 1, 随机初始化聚类中心点
    center_indexs = random.sample(range(m), k)
    center = dataset[center_indexs,:]
    
    cluster_assessment = np.zeros((m, 2))
    cluster_assessment[:, 0] = -1  # 将所有的类别置为 -1
    cluster_changed = True 
    while cluster_changed:
        cluster_changed = False
        # 4-8，计算样本x_i与各聚类中心的距离，根据距离最近的聚类中心确定x_j的簇标记，并将对应样本x_i划入相应的簇
        for i in range(m):
            # 初始化样本和聚类中心的距离，及样本对应簇
            min_dist = inf
            c = 0
            # 确定每一个样本离哪个中心点最近，和属于哪一簇
            for j in range(k):
                dist = distEclud(dataset[i,:], center[j,:])
                if dist < min_dist:
                    min_dist = dist
                    c = i
            # 更新样本所属簇
            if cluster_assessment[i, 0] != c:  # 仍存在数据在前后两次计算中有类别的变动，未达到迭代停止要求
                cluster_assessment[i, :] = c, min_dist  # 更新样本所属簇
                cluster_changed = True
        # 9-16 更新簇中心点位置
        for j in range(k):
            changed_center = dataset[cluster_assessment[:,0] == j].mean(axis=0)
            center[j,:] = changed_center
            
    return cluster_assessment, center

if __name__ == '__main__':
    x1 = np.random.randint(0, 50, (50, 2))
    x2 = np.random.randint(40, 100, (50, 2))
    x3 = np.random.randint(90, 120, (50, 2))
    x4 = np.random.randint(110, 160, (50, 2))
    test = np.vstack((x1, x2, x3, x4))

    # 对特征进行聚类
    result, center = kmeans(test, 4, is_kmeans=False, is_random=False)
    print(center) # 打印簇类中心点

参考资料

《机器学习》-周志华