机器学习期末复习

第一章 机器学习简介

机器学习的概念

是一种实现人工智能的方法

机器学习的要素

• 模型：对于监督学习，模型就是要学习的条件概率或者决策函数
• 策略
  • 目标：选择最优的模型
  • 损失函数，损失函数越小，模型就越好
    • 平方损失函数：\(L(Y，f(X))=(Y-f(x))^2\), 其中\(Y\)是标签（真实值), \(f(X)\)是预测值。
  • 风险函数（期望损失）：损失函数的期望
  • 经验风险：训练集的平均损失，训练集的拟合情况 \[结构风险 = 经验风险 + 正则化项 (系数 * 模型复杂度)\]
• 算法：用什么样的计算方法求解最优模型。归结为最优化问题

机器学习的类型

• 监督学习：监督学习是指通过让机器学习大量带有标签的样本数据，训练出一个模型，并使该模型可以根据输入预测相应输出的过程
• 无监督学习：训练数据不再是（input, output）对的形式，样本数据没有标签
• 强化学习：通过感知外界环境的变化来调整学习方式，然后通过奖惩的方式来判别学习方式是否正确，通过一步步调整学习方式，最终找到一个最优的方式。通过一个智能体在与复杂而不确定的环境交互中最大化总回报来学习的一种计算方法

训练误差与测试误差

训练误差：训练集的平均损失

测试误差：测试集的平均损失

回归和分类

回归：因变量𝑦 ∈ ℝ是连续变量 分类：label是离散变量

过拟合

欠拟合：模型在训练集上误差很大，在测试集上误差也大。由于模型能力不足（不灵活）

过拟合(Over-fitting) ：模型在训练集上误差很低，但是在测试数据上误差很高。由于训练数据太少和/或模型能力太强等原因造成

解决过拟合的方法:

• 扩大训练集
• 正则化Regularization：通过修改目标函数来惩罚模型的复杂度
  • L1正则化：可以使参数稀疏化
  • L2正则化：可以防止过拟合
• 通过验证集来选择模型

模型选择方法

正则化:

结构风险 = 经验风险 + 正则化项

在回归问题中，正则化项可以是L1,L2范数：

其中，L1 L2范数分别为

奥卡姆剃刀原理：在已知数据的情况下，越简单的模型越好

贝叶斯估计视角：正则化项为模型先验概率

交叉验证

数据集划分为三个部分：训练集，测试集，验证集。训练集用于模型训练，测试集用于最终对学习方法评估，验证集用于模型选择。在学习到不同复杂度的模型中，选择验证集最小预测误差的模型。

• 简单交叉验证：划分训练集和测试集，用不同的模型对训练集进行训练，最终在测试集评价每一个模型的误差，选出误差最小的模型。
• S折交叉验证：把数据集划分成s份，用其中的s-1份训练模型，用剩下的一份测试模型。其中，一共有s种组合，对s种组合重复对对模型进行训练和评测。最终，选出在这s次训练和评测中，平均误差最小的模型。
• 留一交叉验证：s折交叉验证的特殊情况：S=N，N为数据集的个数。即为：只留一个样本用作测试。

泛化能力

对未知数据集的预测能力

生成模型与判别模型

• 生成模型：生成方法由数据学习联合概率分布\(P(X,Y)\),然后求出条件概率分布 \(P(Y|X)\)作为预测的模型：\(P(Y|X) = {P(X,Y)/P(X)}\)。最后模型: \(P(Y)=P(Y|X)*P(X)\)。
• 判别模型：直接学习决策函数或者 P(Y|X)作为预测的模型。

二分类评价指标

精确率和召回率：TP, FP, TN, FN（true/false positive/negitive）

精确率: \(P = \frac{TP}{TP + FP}\)

召回率: \(R = \frac{TP}{TP+FN}\)

贝叶斯定理

\(P(A|H) = \frac{P(A)P(H|A)}{P(H)}\)

朴素贝叶斯分类器

先验概率:\(P(Y=c_k),k=1,2,...,K\)

条件概率（似然概率）:\(P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)},...,X^{(n)}=x^{(n)}|Y=c_k),k=1,2,...,K\)

后验概率:\(P(Y=c_k|X=x)=\frac{P(Y=c_k)P(X=x|Y=c_k)}{\sum_{k=1}^K P(Y=c_k)P(X=x|Y=c_k)}\)

第二章 概率论概述

频率论学派和贝叶斯学派

频率论学派（Frequentist）：通过大量独立实验将概率解释为事件发生频率的均值（大数定律）

贝叶斯学派（Bayesian）：则将概率解释为信念度（degree of belief）。当考虑的试验次数非常少的时候，贝叶斯方法的解释非常有用。此外，贝叶斯理论将我们对于随机过程的先验知识纳入考虑，当我们获得新数据的时候，这个先验的概率分布就会被更新到后验分布中

高斯分布

极大似然估计和最大后验估计

极大似然估计（频率学派模型参数估计常用方法）：通俗理解来说，就是利用已知的样本结果信息，反推最具有可能（最大概率）导致这些样本结果出现的模型参数值！即最大化\(P(x_0|\theta)\)

最大后验估计（贝叶斯派模型参数估计的常用方法）：最大化在给定数据样本的情况下模型参数的后验概率。即最大化 \(P(\theta | x_0) = \frac{P(x_0 | \theta)P(\theta)}{P(x_0)}\)。最大似然估计是求参数 \(\theta\)使似然函数最大 。最大后验概率估计则是想求\(\theta\)使\(P(x_0|\theta)\)最大 。求得的\(\theta\)不单单让似然函数大,\(\theta\)自己出现的先验概率也得大。

第三章 优化方法简介

梯度下降法

一种求解的最优化算法（无约束），主要解决求最小值问题，基本思想是下山，即不断逼近最优点的思想，通过求梯度的反方向，来确定错误面中的最低点的方向（有可能是局部最低点），从而不断逼近最小值。设损失函数为： \(J(\theta)=\frac{1}{2}[f(x)-y]^2\),则梯度下降为： \(\theta_{n+1} = \theta_{n} - \alpha J'(\theta)\) 其中\(\alpha\)为学习率。

确定学习率的方法

• 线性搜索法：\(\eta_t = argminf(x - \eta \Delta f(x))\),一般来说在实际中代价太高
• 线性回溯搜索算法：\(f(x-\eta \Delta f(x)) \le f(x) - \alpha \eta ||\Delta f(x)||^2\),在实际中work well

应用梯度下降的不同形式

• 批量梯度下降（BGD）：更新参数时使用所有样本进行更新，梯度更新比较耗时，但是会更准确朝极值方向更新，迭代次数少
• 随机梯度下降(SGD)：每步仅选取一个样本求梯度，梯度更新快，但下降时候波动大，更容易从一个局部最优跳到另一个局部最优，准确度下降。迭代次数多，可能不收敛，或陷入局部极值或鞍点。
• 小批量梯度下降(MBGD)：上面两个的折衷，每步采用固定一部分的样本计算梯度梯度更新比BGD快，迭代次数比SGD少。学习过程仍会有振荡，为更接近最小值，需要增加学习率衰减项，避免过度振荡。

使用建议：当训练集比较小时，批学习，采用拟牛顿或者共轭梯度下降；当训练集大时，随机梯度下降；当训练集介于其间时，小批量学习

拉格朗日乘子法和KKT条件

梯度下降只能求解无约束问题，对于有约束问题，使用梯度下降法，很可能最小值点根本不在约束范围内，所以用拉格朗日乘子法。

拉格朗日乘子法

求解有约束最小值问题（约束为等式）：

\[\min{f(x)} \\ s.t.g(x) = 0\]

即在 \(g(x)=0\)的条件下，求 \(f(x)\)的最小值，引入一个自由变量 \(\lambda\),构造拉格朗日函数：

\[L(x,\lambda)=f(x) + \lambda g(x)\]

则新的方程又变成了无约束问题，对其中的 \(x,\lambda\)求偏导，联立方程组使其等于0，则所得解就是原方程的解。

KKT条件

用于求解约束为不等式时候的约束问题，只是判断x是否为最优解的必要条件。和拉格朗日乘子法一样，引入自由变量，构造拉格朗日函数，设约束条件：

\[g(x)=0 \\ t(x)≤0\]

求解 \(\min f(x)\).

同理构造拉格朗日函数：

\[L(x,\lambda,\theta)=f(x) + \lambda g(x) + \theta t(x)\]

则对应kkt条件有：

• L对x的偏导数为0；
• g(x)=0;
• \(\theta t(x)=0\);
• \(\theta \ge 0\);

拉格朗日乘子法求解

总结：同时包含等式和不等式约束的一般优化问题

对偶

在机器学习中，对偶（duality）是指将一个优化问题转化为其对偶形式，从而更容易地解决原始问题。具体来说，对于一个原始优化问题，通过构建一个拉格朗日函数，并对其进行最大化或最小化，可以得到对偶问题。通过解决对偶问题，我们可以获得原始问题的解。这种方法在解决某些优化问题时非常有用，因为对偶问题可能比原始问题更容易求解。

用\(p^*\)表示原问题（最小化）的最优值；\(d^*\)表示对偶问题（最大化）的最优值。

弱对偶性：\(d^* \le p^*\)。即使原问题不是凸优化，不等式也成立

强对偶性：\(d^* = p^*\)

为什么要研究对偶问题

• 虽然对偶方法并不能保证成功，但是它对于某些类别的函数有效，在这些情况下， 它总能带来更简单的优化问题，特别是当原问题中自变量的维度比约束的数量大得多的情况下,
• 对偶函数总是凹函数，无论原问题如何。所以对偶函数的优化是个凸优化问题

牛顿法

用目标函数的二阶泰勒展开近似该目标函数，通过求解这个二次函数的极小值来求解凸优化的搜索方向

第四章 回归的线性模型

线性回归最小二乘法

回归就是一个输入连续输出连续的模型，比如 \(f(x) = \lambda x + \beta\),其中： \(\lambda\)为要学习的参数， \(\beta\)为偏置，过于简单不多说。

最小二乘法标准：平方损失函数达到最小

对于上述一元线性回归模型来说，损失函数 \(J(\lambda,\beta)=(f(x_i)-y_i)^2\),使损失函数最小，便是求偏导=0，所以去算损失函数关于参数和偏置的偏导为0 即可求解。

岭回归

岭回归是一种特殊的线性回归方法，它在普通线性回归的基础上增加了一个L2正则化项。

普通线性回归的损失函数为：

\[J(\boldsymbol{\theta}) = \frac{1}{m} \sum_{i=1}^{m}{(\boldsymbol{\theta}^{\top}\boldsymbol{x}^{(i)} - y^{(i)})^2}\]

岭回归损失函数为：

\[J(\boldsymbol{\theta}) = \frac{1}{m} \sum_{i=1}^{m}{(\boldsymbol{\theta}^{\top}\boldsymbol{x}^{(i)} - y^{(i)})^2} + \alpha \sum_{j=1}^{n}{\theta_j^2}\]

其中， \(\alpha\)是正则化强度的调节参数， \(\boldsymbol{\theta}\)是回归系数向量， \(\boldsymbol{x}^{(i)}\)是第 \(i\)个样本的特征向量，\(y^{(i)}\)是第 \(i\)个样本的目标值(标签)， \(n\)是特征数。

岭回归通过增加正则化项，使得回归系数更加稳定，从而防止过拟合。在L2正则化下，回归系数会被压缩到接近于0的数值，但不会变成0。因此，岭回归可以保留所有的特征，而不用像特征选择那样舍弃一些特征。

岭回归的求解方法与普通线性回归类似，只是在最小化损失函数时需要加上正则化项的贡献。最常用的方法是使用解析解：

\[\boldsymbol{\theta} = (\boldsymbol{X}^{\top}\boldsymbol{X} + \alpha\boldsymbol{I})^{-1}\boldsymbol{X}^{\top}\boldsymbol{y}\]

其中， \(\boldsymbol{X}\)是样本特征矩阵， \(\boldsymbol{y}\)是目标值向量， \(\boldsymbol{I}\)是单位矩阵。

岭回归的一个关键问题是如何选择正则化强度参数 \(\alpha\)。通常可以通过交叉验证来选择最佳的 \(\alpha\)值。

Lasso回归

Lasso回归是一种用于特征选择的线性回归模型，它的损失函数是平方损失加上L1正则化。L1正则化会让一部分特征的系数变为0，从而达到特征选择的目的。

Lasso回归的损失函数为：

\[J(\theta) = \frac{1}{2m} \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})^2 + \alpha \sum_{j=1}^n |\theta_j|\]

其中，第一项是平方损失，第二项是L1正则化项， \(\alpha\)是正则化参数。

Lasso回归的优化算法是坐标轴下降法，也称为坐标下降法。它的基本思想是，每次只更新一个参数的值，将其他参数的值固定住。

Lasso回归有一个重要的应用场景是特征选择。如果某个特征的系数为0，说明这个特征对目标变量没有太大的影响，可以将其从模型中剔除，从而简化模型并提高泛化性能。

第五章 分类的线性模型

线性分类概念

线性分类是一种常见的机器学习技术，旨在将数据分成两个或多个类别。它的基本思想是在特征空间中找到一条直线、平面或超平面，将不同类别的数据分开。线性分类可以用于二元分类（将数据分成两个类别）和多元分类（将数据分成三个或更多类别）问题。

在二元分类中，线性分类器会将数据点分为两个类别，通常用“+1”和“-1”表示。对于一个新的数据点，分类器会计算它与这条直线、平面或超平面之间的距离，并根据其距离的符号来预测其所属的类别。如果距离为正，则预测其属于正类；如果距离为负，则预测其属于负类。

线性分类器可以用很多不同的算法来训练。其中，最常用的算法是支持向量机（SVM）。SVM算法通过寻找最大间隔超平面来分割数据。这条超平面可以最大限度地扩大不同类别数据点之间的距离，从而提高分类器的性能。

除了SVM之外，还有其他的线性分类器算法，例如感知器（perceptron）和逻辑回归（logistic regression）。这些算法也可以用来解决线性分类问题，但它们的性能和训练速度可能会有所不同。

判别函数、概率生成模型、概率判别模型

判别函数模型

判别函数模型通过学习一个判别函数来直接将输入映射到输出类别，它不需要生成训练样本的概率分布。判别函数模型通常适用于高维稠密数据，并且由于它只关注分类结果，而不是关注如何生成数据，因此在训练数据不太充分或噪声较大的情况下也能够有很好的表现。常见的判别函数模型包括支持向量机（SVM）和神经网络（Neural Network）。

概率生成模型

概率生成模型先对样本的概率分布进行建模，然后通过贝叶斯公式计算后验概率来进行分类或预测。概率生成模型适用于多类别分类或回归问题，并且能够较好地处理缺失数据和噪声。常见的概率生成模型包括朴素贝叶斯（Naive Bayes）和高斯混合模型（Gaussian Mixture Model）。

概率生成模型先对类条件密度\(p(x|C_k)\)和先验类概率分布\(p(C_k)\)建模然后再使⽤贝叶斯定理计算后验类概率分布\(p(C_k|x)\).最后，使⽤决策论来确定每个输⼊\(x\)的类别等价地，直接对联合概率分布建模，再归一化得到后验概率。

概率判别模型

概率判别模型是通过直接对条件概率分布进行建模来预测输出。与概率生成模型不同，它不需要显式地建模输入的概率分布，而是直接估计类别条件概率。概率判别模型适用于多分类问题，其预测性能优于概率生成模型。常见的概率判别模型包括逻辑回归（Logistic Regression）和多层感知器（Multilayer Perceptron）。

概率判别模型直接对后验概率\(p(C_k|x)\)建模, 再使⽤决策论来确定每个新的输⼊\(x\)的类别。

逻辑回归

Logistic Regression 虽然被称为回归，但其实际上是分类模型，并常用于二分类

逻辑回归是一种经典的机器学习算法，用于处理分类问题。它基于线性模型，将输入特征与输出标签之间的关系建模为一个sigmoid函数，并通过最大化似然函数来学习模型参数。在预测时，逻辑回归将输入特征传入模型，并通过sigmoid函数计算输出标签的概率值，从而得到最终的分类结果。

假设我们有一个二分类问题，样本集合为

\[D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)\}\]

其中 \(x_i\in R^m\)表示第 \(i\)个样本的 \(m\)维输入特征向量, \(y_i\in\{0,1\}\)表示第 \(i\)个样本的标签。

逻辑回归的目标是学习一个函数 \(f(x)\)，将输入特征 \(x\)映射到一个 \([0,1]\)之间的概率值，即：

\[P(Y=1|X=x)=\sigma(w^Tx+b)\]

其中, \(\sigma\)是sigmoid函数，定义为：

\[\sigma(z)=\frac{1}{1+e^{-z}}\]

逻辑回归使用极大似然估计来学习模型参数 \(w\)和 \(b\)。

假设每个样本独立同分布地采样，根据贝叶斯定理，我们可以将样本的似然函数写为：

\[L(w,b)=\prod_{i=1}^nP(Y=y_i|X=x_i;w,b)\]

对数似然函数为：

\[\log L(w,b)=\sum_{i=1}^n\log P(Y=y_i|X=x_i;w,b)\]

我们的目标是最大化对数似然函数，可以通过梯度上升法来求解。具体来说，我们可以首先计算对数似然函数关于 \(w\)和 \(b\)的梯度，然后更新模型参数，重复这个过程直到收敛。

在预测时，将输入特征 \(x\)传入训练好的模型，计算 \(P(Y=1|X=x)\)的值，若大于0.5则预测为正类，否则预测为负类。

朴素贝叶斯分类器

朴素贝叶斯分类器是一种基于贝叶斯定理和特征条件独立假设的分类算法。它通常用于文本分类、垃圾邮件过滤、情感分析等自然语言处理任务。

假设我们有一个包含 \(n\)个训练样本的数据集 \(D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)\}\)，其中 \(x_i=(x_{i1},x_{i2},\cdots,x_{im})\)表示第 \(i\)个样本的 \(m\)个特征， \(y_i\in\{c_1,c_2,\cdots,c_k\}\)表示第 \(i\)个样本的类别。

朴素贝叶斯分类器基于贝叶斯定理计算后验概率 \(P(y|x)\)

即给定特征 \(x\)下类别 \(y\)的条件概率。根据贝叶斯定理，可以将 \(P(y|x)\)表示为：

\[P(y|x)=\frac{P(x|y)P(y)}{P(x)}\]

其中， \(P(y)\)是类别 \(y\)的先验概率， \(P(x)\)是特征 \(x\)的边缘概率， \(P(x|y)\)是在类别 \(y\)下特征 \(x\)的条件概率。在朴素贝叶斯分类器中，我们假设所有特征都是相互独立的，即：

\[P(x|y)=\prod_{i=1}^m P(x_i|y)\]

根据上述假设，朴素贝叶斯分类器将 \(P(y|x)\)简化为：

\[P(y|x)=\frac{P(y)\prod_{i=1}^m P(x_i|y)}{P(x)}\]

由于 \(P(x)\)是与类别无关的常量，因此可以忽略掉。于是我们只需要计算先验概率 \(P(y)\)和条件概率 \(P(x_i|y)\)即可。

先验概率 \(P(y)\)可以通过样本中每个类别出现的频率来估计。对于条件概率 \(P(x_i|y)\)，我们可以根据不同类型的特征进行不同的处理。

• 对于离散型特征，我们可以直接计算每个取值出现的频率。
• 对于连续型特征，通常假设其服从正态分布，然后估计每个类别下的均值和方差。

在预测时，我们将测试样本的特征代入上述公式，计算每个类别的后验概率，最终预测为概率最大的类别。

第六章 支持向量机

简单点讲，SVM就是一种二类分类模型，他的基本模型是的定义在特征空间上的间隔最大的线性分类器，SVM的学习策略就是间隔最大化。

对于支持向量机来说，数据点若是\(p\)维向量，我们用\(p-1\)维的超平面来分开这些点。但是可能有许多超平面可以把数据分类。最佳超平面的一个合理选择就是以最大间隔把两个类分开的超平面。因此，SVM选择能够使离超平面最近的数据点的到超平面距离最大的超平面。

以上介绍的SVM只能解决线性可分的问题，为了解决更加复杂的问题，支持向量机学习方法有一些由简至繁的模型:

• 线性可分SVM

  当训练数据线性可分时，通过硬间隔(hard margin，什么是硬、软间隔下面会讲)最大化可以学习得到一个线性分类器，即硬间隔SVM

• 线性SVM

  当训练数据不能线性可分但是可以近似线性可分时，通过软间隔(soft margin)最大化也可以学习到一个线性分类器，即软间隔SVM

• 非线性SVM

当训练数据线性不可分时，通过使用核技巧(kernel trick)和软间隔最大化，可以学习到一个非线性SVM

3个关键想法

• 通过优化来求解一 个超平面分类器
• 寻找最大间隔分类器来提高模型 的 泛化能力（结构风险最小化）
• 采用核技巧使得在高维特征空间的计算更有效率

线性可分SVM——硬间隔

考虑如下形式的线性可分的训练数据集:

\[(X_1, y_1),(X_2, y_2),...,(X_n,y_n)\]

其中\(X_i\)是一个含有\(d\)个元素的列向量, 即\(X_i \in R^d\);\(y_i\)是标量,\(y \in +1, -1\),\(y+i=+1\)时表示\(X_i\)属于正类别,\(y_i=-1\)时表示\(X_i\)属于负类别。注：这里的\(X\)、\(X_i\)、\(W\)都是列向量。

回忆一下感知机的目标: 找到一个超平面使其能正确地将每个样本正确分类。感知机使用误分类最小的方法求得超平面，不过此时解有无穷多个。而线性可分支持向量机利用间隔最大化求最优分离超平面,这时解是唯一的。

一个超平面由法向量\(W\)和截距\(b\)决定,其方程为\(X^TW+b = 0\), 可以规定法向量指向的一侧为正类,另一侧为负类。下图画出了三个平行的超平面，法方向取左上方向。

为了找到最大间隔超平面，我们可以先选择分离两类数据的两个平行超平面，使得它们之间的距离尽可能大。在这两个超平面范围内的区域称为“间隔(margin)”，最大间隔超平面是位于它们正中间的超平面。这个过程如上图所示。

间隔最大化

将高数里面求两条平行直线的距离公式推广到高维可求得上图中margin的\(\rho\):

\[margin = \rho = \frac{2}{||W||}\]

我们的目标是使\(\rho\)最大，等价于使\(p^2\)最大：

\[\max\limits_{W,b} \rho \Longleftrightarrow \max\limits_{W,b}\rho^2 \Longleftrightarrow \min\limits{W,b}\frac{1}{2}||W||^2 \tag{1}\]

上式的\(\frac{1}{2}\)是为了后续求导后刚好能消去，没有其他特殊意义。

同时也不要忘了有一些约束条件:

\[X_i^tW+b\ge +1,y_i=+1 \\ X_i^tW+b\le -1,y_i=-1\]

总结一下，间隔最大化问题的数学表达就是

\[\begin{equation} \min\limits_{W,b} J(W)= \min\limits_{W,b}\frac{1}{2}||W||^2 \\ s.t. \quad y_i(X_i^T+b) \ge 1, i = 1,2,...,n \tag{2} \end{equation} \]

通过求解上式即可得到最优超平面\(\hat{W}\)和\(\hat{b}\)。

支持向量

在线性可分的情况下，训练数据集的样本点中与分离超平面距离最近的数据点称为支持向量(support vector)，支持向量是使\((2)\)中的约束条件取等的点，即满足

\[y_i(X_i^TW+b)=1\]

的点。也即所有在直线\(X_i^TW+b=1\)或直线\(X_i^TW+b=-1\)的点。如下图所示:

在决定最佳超平面时只有支持向量起作用，而其他数据点并不起作用。如果移动非支持向量，甚至删除非支持向量都不会对最优超平面产生任何影响。也即支持向量对模型起着决定性的作用，这也是“支持向量机”名称的由来。

对偶问题

如何求解式\((2)\)呢？

我们称式\((2)\)所述问题为原始问题(primal problem), 可以应用拉格朗日乘子法构造拉格朗日函数(Lagrange function)再通过求解其对偶问题(dual problem)得到原始问题的最优解。转换为对偶问题来求解的原因是:

• 对偶问题更易求解，由下文知对偶问题只需优化一个变量\(\alpha\)且约束条件更简单；
• 能更加自然地引入核函数，进而推广到非线性问题。

首先构建拉格朗日函数。为此需要引进拉格朗日乘子(Lagrange multiplier),\(\alpha_i \ge 0,i=1,2,...,n\)。则拉格朗日函数为:

\[L(W,b,\alpha)=\frac{1}{2}||w||^2 - \sum\limits_{n}^{i=1}\alpha_i [y_i(X_i^TW+b)-1]\]

因此，给定一个\(W\)和\(b\), 若满足式\((1)\)的约束条件，那么有

\[\max\limits_{\alpha}L(W,b,\alpha)=J(W)=\frac{1}{2}||W||^2\]

则由上式可知，优化问题

\[\min\limits_{W,b} \max\limits_{\alpha}L(W,b,\alpha)\]

与式\((1)\)所述问题完全等价。

根据拉格朗日对偶性，式\((1)\)所述问题即原始问题的对偶问题是:

\[\max\limits_{\alpha} \min\limits_{W,b} L(W,b,\alpha)\]

为了求得对偶问题的解，需要先求得\(L(W,b,\alpha)\)对\(W\)和\(b\)的极小再求对\(\alpha\) 的极大。

1. 求\(\min\limits_{W,b} L(W,b,\alpha)\):对拉格朗日函数求导并令导数为0，有：

\[ \begin{equation} \nabla_W L(W, b, \alpha)=W-\sum_{i=1}^n \alpha_i y_i X_i=0 \Longrightarrow W=\sum_{i=1}^n \alpha_i y_i X_i \tag{3} \end{equation} \]

\[ \begin{equation*} \nabla_b L(W, b, \alpha)=-\sum_{i=1}^n \alpha_i y_i=0 \Longrightarrow \sum_{i=1}^n \alpha_i y_i=0 \end{equation*} \]

将上面两式代入\(L(W,b,\alpha)\):

\[ \begin{aligned} & L(\mathbf{w}, b, \boldsymbol{\alpha})=\frac{1}{2}\|\mathbf{w}\|^2-\sum_{i=1}^n \alpha_i\left[y_i\left(\mathbf{x}_i^T \mathbf{w}+b\right)-1\right] \\ & =\frac{1}{2} \sum_{i=1}^n \alpha_i y_i \mathbf{x}_i^T \sum_{j=1}^n \alpha_j y_j \mathbf{x}_j-\sum_{i=1}^n \alpha_i y_i \mathbf{x}_i^T \sum_{j=1}^n \alpha_j y_j \mathbf{x}_j-b \sum_{i=1}^n \alpha_i y_i+\sum_{i=1}^n \alpha_i \\ & =\sum_{i=1}^n \alpha_i-\frac{1}{2} \sum_{i=1}^n \alpha_i y_i \mathbf{x}_i^T \sum_{j=1}^n \alpha_j y_j \mathbf{x}_j=\sum_{i=1}^n \alpha_i-\frac{1}{2} \sum_{i, j=1}^n y_i y_j \alpha_{i} \alpha_j \mathbf{x}_i^T \mathbf{x}_{i=1} \end{aligned} \]

所以

\[\begin{equation} \min _{W, b} L(W, b, \alpha)=-\frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j X_i^T X_j+\sum_{i=1}^n \alpha_i \tag{4} \end{equation} \]

2. 求\(\min\limits{W,b}L(W,b,\alpha)\)对\(\alpha\)的极大：

等价于式\((4)\)对\(\alpha\)求极大，也等价于式\((4)\)取负数后对\(\alpha\)求极小，即

\[\min _\alpha \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j X_i^T X_j-\sum_{i=1}^n \alpha_i \tag{5}\]

同时满足约束条件：

\[ \begin{aligned} & \sum_{i=1}^n \alpha_i y_i=0 \\ & \alpha_i \geq 0, i=1,2, \ldots, n \end{aligned} \tag{6} \]

至此，我们得到了原始最优化问题\((2)\)和对偶最优化问题\((5)\)、\((6)\)。

因为原始优化问题的目标函数和不等式约束条件都是凸函数，并且该不等式约束是严格可行的(因为数据是线性可分的), 所以存在\(\hat{W},\hat{b},\hat{\alpha}\)，使得\(\hat{W},\hat{b}\)是原始问题的解，\(\hat{\alpha}\)是对偶问题的解。这意味着求解原始最优化问题 \((2)\)可以转换为求解对偶最优化问题\((5),(6)\)。

那么如何求解优化问题\((5)\)、\((6)\)的最优解\(\hat{\alpha}\)呢？ 不难发现这是一个二次规划问题，有现成的通用的算法来求解。

假设我们现在求得了\((4)\)、\((5)\)的最优解\(\hat{\alpha}\)，则根据式\((4)\)可求得最优\(\hat{W}\)：

\[\hat{W}=\sum\limits_{i=1}^n \hat{\alpha}_i y_i X_i \tag{5}\]

因为至少存在一个\(\hat{\alpha}_j > 0\)(若不存在，即\(\hat{\alpha}\)全为0，则\(\hat{W}=0\), 即\(margin=\frac{2}{||W||} = \infty\),显然不行), 再根据KKT条件，即

\[ \left\{\begin{array}{l} \text { 乘子非负 }: \alpha_i \geq 0(i=1,2, \ldots n . \text { 下同 }) \\ \text { 约束条件 }: y_i\left(X_i^T W+b\right)-1 \geq 0 \\ \text { 互补条件 }: \alpha_i\left(y_i\left(X_i^T W+b\right)-1\right)=0 \end{array}\right. \]

所以至少存在一个\(j\),使\(y_j(X_T \hat{W}+\hat{b})-1=0\),即可求得最优\(\hat{b}\):

\[ \begin{aligned} \hat{b} & =\frac{1}{y_j}-X_j^T \hat{W} \\ & =y_j-X_j^T \hat{W} \\ & =y_j-\sum_{i=1}^n \hat{\alpha}_i y_i X_j^T X_i \end{aligned} \tag{7} \]

至此，所以我们就求得了整个线性可分SVM的解。求得的分离超平面为:

\[ \sum_{i=1}^n \hat{\alpha}_i y_i X^T X_i+\hat{b}=0 \]

则分类的决策函数为

\[ f(X)=\operatorname{sign}\left(\sum_{i=1}^n \hat{\alpha}_i y_i X^T X_i+\hat{b}\right) \]

再来分析KKT条件里的互补条件，对于任意样本\((X_i,y_i)\)，总会有\(\alpha_i=0\)或者\(y_if(X_i)=y_i(X^T_i \hat{W}+b)=1\)。则有若\(\alpha_i=0\)，此样本点不是支持向量，对模型没有任何作用；若\(\alpha_i > 0\)，此样本点位于最大间隔边界上，是一个支持向量，如下图所示:

此外，当样本点是非支持向量时，因为\(\alpha_i=0\)，所以SVM的解中的求和项中第\(i\)项就为0，所以SVM的解\((6)\)、\((7)\)可简化为如下形式:

\[ \hat{W}=\sum\limits_{i\in S V}\hat{\alpha}_{i}y_{i}X_{i}\\ \hat{b}=y_{j}-\sum\limits_{i\in S V}\hat{\alpha}_{i}y_{i}X_{j}^{T}X_{i} \]

类似的，判别函数也可转换成如下形式:

\[f(X)=s i g n(\sum\limits_{i\in S V}\hat{\alpha}_{i}y_{i}X^{T}X_{i}+\hat{b})\]

所以，整个SVM的解只与支持向量SV有关，与非支持向量无关。

线性SVM——软间隔

上述硬间隔是完全分类准确，其损失函数不存在；其损失值为0；只要找出两个异类正中间的那个平面，而软间隔允许一定量的样本分类错误，即允许少量样本不满足约束

\[y_{i}(X_{i}^{T}W+b)\geq1\]

为了使不满足上述条件的样本点尽可能少，我们需要在优化的目标函数\((1)\)里面新增一个对这些点的惩罚项。最常用的是hinge损失:

\[l_{h i n g e}(z)=m a x(\mathsf{0,1-z})\]

即若样本点满足约束条件损失就是0, 否则损失就是,则优化目标\(（1）\)变成

\[\begin{equation} \min\limits_{W,b} \frac{1}{2}||W||^2 + C\sum\limits_{i=1}^n \max{(0, 1 - u_i(X_i^TW + b))} \tag{8} \end{equation}\]

其中\(C>0\)称为惩罚参数，\(C\)越小时对误分类惩罚越小，越大时对误分类惩罚越大，当\(C\)取正无穷时就变成了硬间隔优化。实际应用时我们要合理选取\(C\),\(C\)越小越容易欠拟合，\(C\)越大越容易过拟合。

如果我们引入“松弛变量”\(\xi_i \ge 0\), 那么式\((8)\)可重写成

\[ \min\limits_{W,b,\xi} {\frac{1}{2}||W||^{2}+C\sum\limits_{i=1}^{n}\xi_{i}} \\ s.t. \quad y_i(X_i^TW+b) \ge 1 - \xi_i \\ \xi_i \ge 0, i = 1,2,...,n \]

上式所述问题即软间隔支持向量机。

而其对偶问题与硬间隔同理。

非线性SVM——核技巧

首先回顾前面的线性SVM的优化目标

\[\min _\alpha \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j X_i^T X_j-\sum_{i=1}^n \alpha_i\]

以及约束条件

\[ \begin{aligned} & \sum_{i=1}^n \alpha_i y_i=0 \\ & \alpha_i \geq 0, i=1,2, \ldots, n \end{aligned} \]

前面介绍的都是线性问题，但是我们经常会遇到非线性的问题(例如异或问题)，此时就需要用到核技巧(kernel trick)将线性支持向量机推广到非线性支持向量机。如果样本在特征空间内线性不可分，则需要利用核函数将其映射到高维空间中，让其在高维空间中线性可分。根据SVM基础形式的求解，我们可能会想到下面的方式：

\[f(\boldsymbol X)=\sum_{i=1}^{N} w_i \phi_i(\boldsymbol X)+b\]

这里的\(\phi_i()\)就是从输入的特征空间到某个更高维的特征空间的映射，这就意味着建议了非线性的学习器分为两步：

• 使用一个变换将原空间的数据映射到新空间(例如更高维甚至无穷维的空间)；
• 然后在新空间里用线性方法从训练数据中学习得到模型。

这种基本型的求解是非常难的，因为这个映射函数是非常难以寻找和求解的！（据说NP难），而了解了SVM的对偶形式给了另一种求解思路：

\[f(\boldsymbol X)=\sum_{i=1}^{l} \alpha_i y_i \left \langle \boldsymbol \phi_i(\boldsymbol X_i) \cdot \boldsymbol \phi(\boldsymbol X) \right \rangle + b\]

注意到，我们在求解的时候需要计算\(ϕi(X_i)⋅ϕ(X)\)，也就是映射后的两个样本的高维特征的内积形式，如果有一种方法可以在特征空间中直接计算这个东西，是不是就很方便了？对的，核函数就是做这个的：

\[K(\boldsymbol X, \boldsymbol X_i) = \boldsymbol \phi(\boldsymbol X) \cdot \boldsymbol \phi(\boldsymbol X_i)\]

那么现在的优化目标就变为

\[ \min\limits_{\alpha}\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_{i}\alpha_{j}y_{i}y_{j}K(X_{i},X_{j})\;-\;\sum_{i=1}^{n}\alpha_{i} \\ s.t.\,\,\,\,\sum_{i=1}^{n}\alpha_{i}y_{i}=0 \\ 0\leq\alpha_{i}\leq C,i=1,2,\cdot\cdot,n. \]

上述的思想就是SVM核函数的核心思想。

多项式核函数

对于一个多项式核函数

\[K(\boldsymbol X, \boldsymbol X_i) = [(X \cdot X_i) + c]^q\]

可以得到q阶多项式分类器

高斯径向基核RBF

\[K(\boldsymbol X, \boldsymbol X_i) = exp(-\frac{|X-X_i|^2}{\sigma^2})\]

每个基函数中心对应一个支持向量，它们及输出权值由算法自动确定。

Sigmod核

\[K(X, X_i)=tanh(\nu (X,X_)+c)\]

包含一个隐层的多层感知器，隐层节点数是由算法自动确定。

注：上述SVM内容转载于看了这篇文章你还不懂SVM你就来打我

第七章 混合模型与期望最大

聚类基本思想：将相似的实例分组在一起。聚类结果在很大程度上取决于待聚类点之间的相似性（或距离）度量

聚类算法

• 原型聚类：如K均值算法、高斯混合模型
• 密度聚类：如DBSCAN算法、Mean-Shift 算法
• 层次聚类：如Agglomerative 算法、Divisive算法、BIRCH 算法
• 谱聚类

K-means 聚类

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

如果用数据表达式表示，假设簇划分为\((C_1,C_2,...C_k)\)，则我们的目标是最小化平方误差\(E\)：

\[E = \sum\limits_{i=1}^k\sum\limits_{x \in C_i} ||x-\mu_i||_2^2\]

其中\(μ_i\)是簇\(C_i\)的均值向量，有时也称为质心，表达式为：

\[\mu_i = \frac{1}{|C_i|}\sum\limits_{x \in C_i}x\]

如果我们想直接求上式的最小值并不容易，这是一个NP难的问题，因此只能采用启发式的迭代方法。

K-Means采用的启发式方式很简单，用下面一组图就可以形象的描述。

K-Means的算法步骤为:

1. 选择初始化的 k 个样本作为初始聚类中心\(a=a_1,a_2,...,a_k\)
2. 针对数据集中每个样本\(x_i\)计算它到 \(k\) 个聚类中心的距离并将其分到距离最小的聚类中心所对应的类中；
3. 针对每个类别 \(a_j\)，重新计算它的聚类中心\(a_{j}=\frac{1}{|c_{i}|}\sum\limits_{x\in c_{i}}x\)（即属于该类的所有样本的质心）;
4. 重复上面 2 3 两步操作，直到达到某个中止条件（迭代次数、最小误差变化等）。

高斯混合模型（GMM）

高斯混合模型（Gaussian Mixed Model）指的是多个高斯分布函数的线性组合，理论上GMM可以拟合出任意类型的分布，通常用于解决同一集合下的数据包含多个不同的分布的情况（或者是同一类分布但参数不一样，或者是不同类型的分布，比如正态分布和伯努利分布）。

\[p(\alpha)=\sum_{k=1}^{K}\pi_{k} \mathcal{N}(x \mid\mu_{k},\Sigma_{k})\]

其中\(\mathcal{N}(x \mid\mu_{k},\Sigma_{k})\)称为混合模型中的第\(k\)个分量（component）。混合系数\(\pi_k\)满足\(\sum\limits^{K}_{k=1}\pi_k =1 \quad0\le \pi \le 1\)。可以认为\(\pi_k\)就是每个分量\(\mathcal{N}(x | \mu_k, \Sigma_k)\)的权重。

EM算法

EM 算法，全称 Expectation Maximization Algorithm。期望最大算法是一种迭代算法，用于含有隐变量（Hidden Variable）的概率参数模型的最大似然估计或极大后验概率估计。

EM算法思想

EM 算法的核心思想非常简单，分为两步：Expection-Step 和 Maximization-Step。

• E-Step 主要通过观察数据和现有模型来估计参数，然后用这个估计的参数值来计算似然函数的期望值；
• 而 M-Step 是寻找似然函数最大化时对应的参数。由于算法会保证在每次迭代之后似然函数都会增加，所以函数最终会收敛。

EM算法例子的执行过程如何感性地理解EM算法？

事实上隐变量估计也可以通过梯度下降等优化方法求解，但由于求和的项数将随着隐变量的数目以指数级别上升，会给梯度计算带来麻烦；而EM算法可以看作一种非梯度优化方法。

第八章 高斯过程

高斯过程 Gaussian Processes 是概率论和数理统计中随机过程的一种，是多元高斯分布的扩展，被应用于机器学习、信号处理等领域。本文对高斯过程进行公式推导、原理阐述、可视化以及代码实现，介绍了以高斯过程为基础的高斯过程回归 Gaussian Process Regression 基本原理、超参优化、高维输入等问题。

高斯过程 Gaussian Processes 原理、可视化及代码实现

第九章 集成学习

Bagging

Bagging（装袋算法）的集成学习方法非常简单，假设我们有一个数据集\(D\)，使用Bootstrap sample（有放回的随机采样，这里说明一下，有放回抽样是抽一个就放回一个，然后再抽，而不是这个人抽\(10\)个，再放回，下一个继续抽，它是每一个样本被抽中概率符合均匀分布）的方法取了\(k\)个数据子集（子集样本数都相等）：\(D_1，D_2，…，D_k\)，作为新的训练集，我们使用这\(k\)个子集分别训练一个分类器（使用分类、回归等算法），最后会得到\(k\)个分类模型。我们将测试数据输入到这\(k\)个分类器，会得到\(k\)个分类结果，比如分类结果是\(0\)和\(1\)，那么这\(k\)个结果中谁占比最多，那么预测结果就是谁。

算法流程：

• 从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行k轮抽取，得到k个训练集。（k个训练集之间是相互独立的）
• 每次使用一个训练集得到一个模型，k个训练集共得到k个模型。（注：这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知机等）
• 对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）

特点：

• 关于bagging所采用的抽样方式为有放回抽样，抽样的样本数量等于总体样本数量；
• 由于某些样本在有放回的情况下不止被抽到一次，有些样本一次也不会被抽到；
• 可以并行产生所需要的样本子集个数以及并行训练子模型
• 对于二分类问题，一般选取样本子集个数为奇数（避免出现两个类别投票数相同）

AdaBoost

Boosting指的是一类集成方法，其主要思想就是将弱的基学习器提升(boost)为强学习器。具体步骤如下:

1. 先用每个样本权重相等的训练集训练一个初始的基学习器；
2. 根据上轮得到的学习器对训练集的预测表现情况调整训练集中的样本权重(例如提高被错分类的样本的权重使之在下轮训练中得到更多的关注), 然后据此训练一个新的基学习器；
3. 重复2直到得到\(M\)个基学习器，最终的集成结果是\(M\)个基学习器的组合。

Boosting算法簇中最著名的就是AdaBoost。

基本思想

对于上述的Boosting算法步骤，需要回答两个问题:

1. 如何调整每一轮的训练集中的样本权重？
2. 如何将得到的[公式]个组合成最终的学习器？

AdaBoost(Adaptive Boosting, 自适应增强)算法采取的方法是:

1. 提高上一轮被错误分类的样本的权值，降低被正确分类的样本的权值；
2. 线性加权求和。误差率小的基学习器拥有较大的权值，误差率大的基学习器拥有较小的权值。

AdaBoost算法的流程如下：

输入：训练数据集\(T={(x1,y1),(x2,y2),(xN,yN)}\)，其中，\(xi∈X⊆R^n\)，\(yi∈Y=−1,1\)，迭代次数\(M\)

1. 初始化训练样本的权值分布: \[D_1=(w_{1,1},w_{1,2},…,w_{1,i}),w_{1,i}=\frac{1}{N},i=1,2,…,N\]

2. 对于\(m=1,2,…,M\)

   1. 使用具有权值分布\(D_m\)的训练数据集进行学习，得到弱分类器\(Gm(x)\)

   2. 计算\(Gm(x)\)在训练数据集上的分类误差率: \[e_m=\sum_{i=1}^Nw_{m,i} I(G_m (x_i )≠y_i )\]

   3. 计算\(Gm(x)\)在强分类器中所占的权重： \[α_m=\frac{1}{2}log \frac{1-e_m}{e_m}\]

   4. 更新训练数据集的权值分布（这里，\(z_m\)是归一化因子，为了使样本的概率分布和为\(1\)）：

   \[w_{m+1,i}=\frac{w_{m,i}}{z_m}exp⁡(-α_m y_i G_m (x_i ))，i=1,2,…,10\]

   \[z_m=\sum_{i=1}^Nw_{m,i}exp⁡(-α_m y_i G_m (x_i ))\]

3. 得到最终分类器:

   \[F(x)=sign(\sum_{i=1}^Nα_m G_m (x))\]

Bagging和Boosting的区别

1. 样本选择上

Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。

Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。

2. 样例权重

Bagging：使用均匀取样，每个样例的权重相等

Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。

3. 预测函数

Bagging：所有预测函数的权重相等。

Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。

4. 并行计算

Bagging：各个预测函数可以并行生成

Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。

第十章 半监督学习

基于图的半监督学习

图的概念

我们首先来看看如何从训练数据中构建出图，给定半监督数据集\(\{(𝑥_𝑖,𝑦_𝑖 )\}_{𝑖=1}^𝑙\)和\(\{𝑥_𝑗 \}_{𝑗=𝑙+1}^{𝑙+𝑢}\)，每个数据样本（有标签&无标签）是图上的一个顶点，显然，图会非常大，因为无标签数据很多，一旦图构建完成，学习的过程就包括给图中的每一个定点设置标签y值。在图中可以通过边将有标签和无标签数据点相连，边通常是无向的，表示的是两个节点（样本）之间的相似性。将边权重记作\(w_{ij}\)，\(w_{ij}\)越大，\(x_i\)和\(x_j\)越相似，两者的标签越可能相同。所以边权重非常重要，人们常常将边的权值定义为如下形式：

• 全连接图：

每一对定点之间都有边相连，边的权重随欧式距离\(||x_i-x_j||\)的增加而降低，常用的权重方程如下：

\[w_{ij}= \exp(-\frac{||x_i-x_j||^2}{2\sigma^2})\]

\(σ\)叫做带宽参数用来控制权重衰减的速度。这个权重方程和高斯方程的形式相同，也叫做高斯核或者径向基函数；

• KNN图：

每一个定点定义它的欧式距离上的最近邻，注意，如果\(x_i\)在\(x_j\)的\(k\)近邻内，\(x_j\)不一定在\(x_i\)的\(k\)近邻内，如果\(x_i\),\(x_j\)中有一个在对方的\(k\)近邻内我们就用边将它们连接，这就意味着一个定点可能会有超过\(k\)条边，如果\(x_i,x_j\)有边相连，边的权重\(w_{ij}\)就是\(1\)，否则为\(0\)。KNN图可以自适应地适应样本在特征空间的密度（密集区KNN范围的半径小）；

• \(ε\)NN图：

将距离小于\(ε\)的顶点连一条边。

MINCUT

我们将带有正标签的样本作为源点（就好像流从这里出发流经边），相似的，负标签样本作为终点（流消失的点），目标是找到一个最小的边集，使得删除这些边可以阻止所有从源点到终点的流，我们定义这样的一组边集叫做“cut”，割的大小用这些边的权重和来定义。一旦图被“割”开，与源点相连的点都被标记为正，反之为负。也就是说，我们想要找到这样的一个作用在顶点上的函数\(f(x)\in\{0,1\}\)用来标记x的标签，使得对于有标签样本来说\(f(x_i)=y_i\)，而且cut最小:

\[\sum_{i,j\geq f(x_{i})\neq f(x_{j})}w_{i j}\]

我们将最小割问题形式化为正则化风险最小化问题（合适的损失函数和正则化器）。对任何有标签的顶点\(x_i\)，\(f(x_i)\)就是\(x_i\)对应的标签\(y_i\)，可以用这样一个损失函数来表示：\(c(\mathbf{x},\mathbf{y},f(\mathbf{x}))=\infty\cdot(\mathbf{y}-f(\mathbf{x}))^{2}\),而正则化项则对应cut的大小，考虑到所有无标签样本的类别非负即正，cut的大小可以重写为\(\Omega(f)=\sum\limits_{i,\,i=1}^{i=n}w_{i j}(f(\mathbf{x}_{i})-f(\mathbf{x}_{j}))^{2}/4\)。注意，当前的和是针对所有点对的，如果\(x_i\),\(x_j\)不相连，\(w_{ij}=0\)。那么最小割的正则化风险最小化问题可以写作

\[\min\limits_{f:f(x) \in \{-1,1\}} \infty \sum_{i=1}^{l}(y_{i}-f(\mathbf{x}_{i}))^{2}+\sum_{i,j=1}^{l+u}w_{i j}(f(\mathbf{x}_{i})-f(\mathbf{x}_{j}))^{2}\]

这是一个整数规划问题，因此，最小割问题可以有许多多项式时间算法可以解决。这种形式的最小割问题可能存在多个最优解，比如下图有两个带标签点一正一负，每条边有相同的权重，有6种最小割解决方案（移除任意一条边即可）。

调和函数（HARMONIC FUNCTION）

对于有标签数据，调和函数的值为标签值；对于无标签数据，标签值是其邻居顶点标签值的权重平均

\[\begin{array}{r c l}{f(\mathbf{x}_{i})}&{=}&{y_{i},}&{i=1,\cdot\cdot, l}\end{array}\]

\[f(x_j) = \frac{\sum\limits_{k=1}^{l+u} w_{jk}f(x_k)}{\sum\limits_{k=1}^{l+u} w_{jk}}, j = l+1,\cdots,l+u\]

然后把它代入上面提到过的目标函数，并松弛\(f\)使它的值域为实数：

\[\min\limits_{f:f(x)\in\mathbb{R}} \infty \sum\limits_{i=1}^{l}(y_{i}-f({\bf x}_{i}))^{2}+\sum\limits_{i=1}^{l+u}w_{i j}(f({\bf x}_{i})-f({\bf x}_{j}))^{2}\]

相当于求解：

\[\min\limits_{f:f(x)\in\mathbb{R}}\sum\limits_{i=1}^{l+u}w_{i j}(f({\bf x}_{i})-f({\bf x}_{j}))^{2}\]

对\(f\)进行松弛使得\(f\)有一个闭式解，也就是说上述目标方程有全局最优解，缺点是\(f(x)\)现在是一个\([0,1]\)的实数，并不能直接作为一个标签。这可以通过设定阈值进行处理（如，若\(f(x)>=0.5\)，预测标签\(y=1\)，否则为\(0\)）.

调和函数有许多有趣的解释，比如，将图看作一张电网，每一条边的电阻为\(1/w_{ij}\)，有标签的点连接到\(1v\)的电池，正标签顶点连接电池正极，零标签顶点连接电池负极，每个节点两端的电压就是调和函数值，如下图所示：

也可以解释为图上的随机游走，想象一个粒子在顶点\(i\)上，那么这个粒子会随机走到下一个顶点\(j\)的概率是，随机游走以这种方式继续，直到粒子到达一个有标记的顶点。那么顶点\(i\)的调和函数值\(f(x_i)\)就是粒子从\(i\)顶点出发最终走到一个正标签的顶点的概率，如下图所示：

调和函数的求解

求解调和函数的过程是迭代的，初始的，我们设定：对于有标签顶点，\(f(x_i)=y_i\)，对于无标签顶点，\(f\)为任意值。每一轮迭代都用无标签顶点邻居的权重平均更新该无标签顶点的标签值：

\[f(\mathbf{x}_{i})={\frac{\sum\limits_{j=1}^{l+u}w_{i j}f(\mathbf{x}_{j})}{\sum\limits_{j=1}^{l+u}w_{i j}}}\]

半监督支持向量机(S3VMs/TSVMs)

Semi-Supervised Support Vector Machines(S3VMs)最初被称为直推式支持向量机(Transductive Support Vector Machines(TSVMs))，因为它的理论是为了给无标记样本提供性能界限(理论保证)。但是由于学习到的函数\(f\) 应用到了无标记的样本中，所以被称为半监督支持向量机S3VMs。

对于S3VMs的直观理解是使得有标记和无标记样本处于间隔边界之外。但是，对于无标记样本，我们无法得知其是否处于处于正确的分类。这里给出一种方法将无标记样本用到学习中。

对于样本\(x\),它的预测值\(\hat{y} = sign(f(x))\)，将该预测值假定为该样本的真实标签，则\(x\)的hinge损失函数为

\[\begin{align} c(x, \hat{y}, f(x)) & = \max(1-\hat{y}(w^Tx+b), 0) \\ & = \max(1-sign(w^Tx+b)(w^Tx+b), 0) \\ & = \max(1- |w^Tx+b|, 0) \end{align}\]

该损失函数与hinge损失的不同之处在于它不需要样本真实的标签，而是由\(f(x)\)替代。该损失函数由上图中的右图所示。基于该损失函数的图形的形状，将其命名为hat loss。

虽然假设预测的分类结果都是正确的，但是基于hat loss，有些样本还是会存在惩罚。对于\(f(x) \le -1\)或\(f(x) \ge 1\)的样本，它们处在间隔边界之外，远离决策边界，是不存在惩罚的。但是对于\(-1 \le f(x) \le 1\)的样本，尤其是\(f(x) \approx 0\)的样本，它们在决策边界内，对于预测值\(f(x)\)是存在不确定性的，所以存在惩罚。

将无标记样本\(\{x_j\}_{j=l+1}^{l+u}\)的hat loss加到SVM的损失函数中，定义S3VMs的损失函数

\[\min_{w,b} \sum_{i=1}^{l} \max(1 - y_i(w^Tx_i+b), 0) + \lambda_1 ||w||^2 + \lambda_2\sum_{j=l+1}^{l+u} \max(1 - |w^Tx_i+b|, 0)\]

由上式可以看出，S3VMs更希望无标记数据能够在决策边界的外边，也就是决策边界更希望出现在数据的低密度区域。此时，可以将hat loss看做正则化项

\[\Omega(f) = \lambda_1 ||w||^2 + \lambda_2\sum_{j=l+1}^{l+u} \max(1 - |w^Tx_i+b|, 0)\]

注意，有些时候，无标记数据的预测值只存在一个类，也就是无标记数据都被预测成了同一个类。为了纠正这种不平衡性，一种直接的想法就是限制预测值中各个类的比例。假设无标记数据的预测值中各个类的比例与有标记数据中各个类的比例相同，即

\[\frac{1}{u}\sum_{j=l+1}^{l+u} \hat{y}_j = \frac{1}{l}\sum_{i=1}^{l} y_i\]

因为\(\hat{y}_j = sign(f(x_j))\)不是一个连续函数，所以很难满足上述约束条件。因此放松该约束条件为

\[\frac{1}{u}\sum_{j=l+1}^{l+u} f(x_j) = \frac{1}{l}\sum_{i=1}^{l} y_i\]

该约束被称为类别的平衡约束。

所以，带类别平衡约束的S3VMs可以表示为

\[\begin{align} \min_{w,b} & \sum_{i=1}^{l} \max(1 - y_i(w^Tx_i+b), 0) + \lambda_1 ||w||^2 + \lambda_2\sum_{j=l+1}^{l+u} \max(1 - |w^Tx_i+b|, 0) \\ s.t. & \frac{1}{u}\sum_{j=l+1}^{l+u} f(x_j) = \frac{1}{l}\sum_{i=1}^{l} y_i \tag{4} \end{align}\]

S3VMs的解是很难计算的，因为它的目标函数是非凸的。

上述S3VMs部分转载自Semi-Supervised Support Vector Machines(S3VMs)

第十二章 强化学习

强化学习（Reinforcement Learning, 简称 RL）是机器学习的范式和方法论之一，用于描述和解决智能体（Agent）在与环境（Environment）的交互过程中通过学习策略（Policy）以达成奖励或回报（Reward）最大化或实现特定目标的问题。

强化学习主要涉及无模型（Model-Free）和有模型（Model-based）两大类算法。Model-Free算法可分为Q-Learning和基于策略优化（Policy Optimization）两大类。Model-based算法可分为模型学习（Learn the Model）和给定模型（Given the Model）两大类。