Machine Learning

1 ML

机器学习 machine learning: Field of study that gives computers the ability to learn without being explicitly program.

机器学习并不是仅仅是若干算法的堆积，学会“十大算法”，熟练掌握具体算法算法的推导与编程实现，并不能让所有问题迎刃而解，因为现实世界的问题千变万化。而应该像张无忌那样，忘记张三丰传授的太极剑法的具体招式，而只记住一些规则和套路，从而根据敌人的招式去不断变化自己的招式，达到以不变应万变的效果。或者说用 Andrew Ng 的话，要成为一个 master carpenter （顶级木匠），可以灵活使用工具来制造桌椅，只有手艺差的木匠才会抱怨工具不合适。因此必须把握算法背后的思想脉络，针对具体的任务特点，对现有套路进行改造融通；要记住算法是死的，思想才是活的。

数据库提供数据管理技术，机器学习提供数据分析技术。

1.1 Supervised Learning

样本有标签的时候称为监督学习

1.1.1 Linear Regression

首先可以根据样本输入的维数来选择参数的个数（最终依据交叉验证的结果来选择模型和特征） \[ h_{\theta}(x) = \sum_{i=1}^{n} \theta_i x_i = \theta^{T}x \] 求取 \(\theta\) 的策略：在训练集上使得 \(h(x)\) 尽可能接近 y 。那么就涉及到距离的定义，距离通常定义为两者差的平方。因此损失函数(cost function)定义为 \[ J(\theta) = \frac{1}{2} \sum_{i=1}^m (h_{\theta}(x^{(i)}) - y^{(i)})^2 \]

认为数据服从高斯分布 \(y|x;\theta \thicksim (\mu, \sigma^2)\) ，即其前置概率估计是高斯分布。

Last Mean Squares Algorithm
利用最小二乘法中的误差函数来描述损失函数；利用梯度下降法不断迭代来减小损失函数：先将参数初始化为某个值，然后不断迭代跟新参数；跟新参数的规则：old value + 学习率 * 损失函数对该参数求偏导。
\begin{align} \theta_j & := \theta_j - \alpha \frac{\partial}{\partial \theta_j} J(\theta) \\ & := \theta_j + \alpha \sum_{i=1}^m (y^{(i)} - h_{\theta}(x^{(i)})) x_j^{(i)}, \quad for \ every \ j \\ & := \theta_j + \alpha (y^{(i)} - h_{\theta}(x^{(i)})) x_j^{(i)}, \quad for \ every \ j; \ outer \ for \ every \ i \\ \end{align}
最小二乘法(ordinary least squares)仅仅是描述损失函数的模型，本身不是一个最优解工具，可以求解线性以及非线性问题。最优化方法有：梯度下降法；矩阵解法；牛顿法；坐标上升法；

判断收敛：
- 两次迭代，发现 \(\theta\) 变化不大
- \(J(\theta)\) 基本不变【常用】
最优化方法
1. 梯度下降法
  梯度下降法：结果与初值有关，且最终一定会结束在某个局部最小值。若维度非常高时，可能不存在局部最小值，可能只是鞍点（深度学习）。数学上，某一函数在该点的方向导数沿着梯度方向取得最大值。
  
  梯度下降法具体包括：
  1. batch gradient descent，批量梯度下降法：每次都需要计算所有样本的误差来更新参数
  2. stochastic gradient descent / incremental gradient descent，随机梯度下降法：每次只需要计算一个样本的误差来更新参数。可以较快的收敛，但参数结果可能始终在最优解周围徘徊，但在实际应用中可以满足
  3. mini-batch：每次使用同样个数的一小批的样本来更新权重参数。
2. Newton's method
  牛顿法用于查找一个函数的零点。假如希望找到使得 \(f(\theta) = 0\) 的 \(\theta\) 值。在 \(\theta\) 处，用函数 f 的切线来近似 f ，找到切线的零值点；然后在切线的零值点开始继续用该点处的切线来近似表示函数，不断迭代直至参数满足要求。计算零值点时可以利用直角三角形一个角的对边的长度除以临边的长度来得到该角的正切值，而正切值就是函数在该点的导数。
  \begin{equation} \theta := \theta - \frac{f(\theta)}{f'(\theta)} \end{equation}
  而求解似然函数的极值点，就是找到似然函数导数的零点
  \begin{equation} \theta := \theta - \frac{\ell ' (\theta)}{\ell ''(\theta)} \\ \theta := \theta - H^{-1} _{\theta} \nabla \ell(\theta), \quad Newton-Raphson \end{equation}
  牛顿法：
  - 优点：初值不影响结果，一般选择 0 为初值；算法一般都会收敛且收敛速度比梯度下降法快很多，是二次收敛(quadratic conversions)[在解距离最优解足够近时，下一次误差为上一次误差的平方]
  - 缺点：每次迭代都需要计算 Hessian 矩阵（n*n维）。如果特征维数较多，代价会比较大。
Maximum Likelihood Estimation - MLE
- 似然：参数的函数
- 概率：数据的概率
极大似然估计：选择参数 \(\theta\) 使得数据出现的可能性尽可能大。

让所有样本出现的概率最大，需要将每个样本的概率都乘起来，而连乘操作易造成数据下溢，因此通常采用对数似然(log-likelihood)，将连乘转换成相加操作。

贝叶斯学派认为参数是未被观测的随机变量，其本身也可有分布。频率学派认为虽然参数未知，但确实客观存在的固定值。极大似然估计源自频率学派。

1.1.2 Locally Weighted Linear Regression

只利用待预测样本周围的样本来预测结果。

\begin{align} w^{(i)} = exp \left( - \frac{(x^{(i)}-x)^2}{2\tau^2} \right) \\ \sum_i w^{(i)} (y^{(i)} - \theta^T x^{(i)})^2 \end{align}

x 是待预测的值，样本距离 x 的距离 \( |x^{(i)} - x| \) 越近，权重越大；反之则越小。
\(\tau\) 称为波长参数，是一个超参，控制着权重随距离下降的速度。\(\tau\) 越小，权重衰减的钟形越窄；\(\tau\) 越大，权重衰减的钟形越宽。而且权值函数的积分可能是正无穷而不是像高斯密度函数那样积分值为 1

局部加权线性回归并没有依据训练样本学习得到一些参数，而是在每次预测的时候都需要使用训练样本来决策。是一个非参数学习算法 (non-parametric)，非正式的可以理解为其参数随着训练样本的增加而增加。

Andrew Moore 的 KD tree 讲述了在训练集较多时，高效计算的方法。

1.1.3 Logistic Regression

逻辑斯蒂回归用于处理二分类问题。由于标记只有两个：0 和 1。所以当计算的结果超过 1 或者小于 0 将变得没有意义。因此选取一个函数值从 0 平滑过度到 1 的函数用于将计算求得的结果重映射到区间[0-1]。这样的函数存在很多，但是逻辑斯蒂回归选择了 sigmoid function，也称为 logistic function。利用广义线性模型也会推导出此处选择 sigmoid 函数。

\begin{align} g(z) = \frac{1}{1+e^{-z}} \\ h_{\theta}(x) = g({\theta}^T x) = \frac{1}{1 + e^{-{\theta}^T x}} \end{align}

假设

\begin{align*} P(y=1|x;\theta) & = h_{\theta} (x) \\ P(y=0|x;\theta) & = 1 - h_{\theta} (x) \\ P(y|x;\theta) & = (h_{\theta} (x))^y (1 - h_{\theta} (x))^{1-y} \end{align*}

似然函数：损失函数没有选择成算法输出与标记误差的平方，是因为这样的损失函数是非凸的，会有很多局部最优解而无法找到全局最优解。

\begin{align*} \ell(\theta) & = ln L(\theta) \\ & = ln \prod_{i=1}^m p(y|x;\theta) \\ & = ln \prod_{i=1}^m (h_{\theta} (x^{(i)}))^{y^{(i)}} (1 - h_{\theta} (x^{(i)}))^{1-y^{(i)}} \\ & = \sum_{i=1}^m y^{(i)} ln h(x^{(i)}) + (1-y^{(i)})ln(1-h(x^{(i)})) \end{align*}

目标函数对 \(\theta\) 的每个分量求偏导，且求解过程直接使用 sigmoid 函数的导数表达式可简化计算。最终得到参数的迭代表达式

\begin{align} \frac{\partial}{\partial \theta_j} \ell(\theta) & = (y-h_{\theta}(x))x_j \\ \theta_j & := \theta_j + \alpha \sum_{i=1}^m(y^{(i)} - h_{\theta}(x^{(i)})) x_j^{(i)} \\ \theta_j & := \theta_j + \alpha(y^{(i)} - h_{\theta}(x^{(i)})) x_j^{(i)} \end{align}

sigmoid 函数的导数：

\begin{equation} g'(z) = g(z) (1-g(z)) \end{equation}

认为数据服从伯努利分布 \(y|x;\theta \thicksim Bernoulli(\phi)\) ，即数据的前置概率估计是伯努利分布。

TP – 将正类预测为正类的个数；true positive
FN – 将正类预测为负类的个数；false negative
TN – 将负类预测为负类的个数；true negative
FP – 将负类预测为正类的个数；false positive

准确率、召回率、以及两者的调和均值（准确率和召回率都高的时候也会高）：

\begin{gather} P = \frac{ TP }{ TP + FP } \\ R = \frac{ TP }{ TP + FN } \\ \frac{2}{F_1} = \frac{1}{P} + \frac{1}{R} \\ F_1 = \frac{2TP}{2TP + FP + FN} \end{gather}

1.1.4 Perception Learning Algorithm

sigmoid 函数并没有直接输出样本的类别标记，而是根据输出再与 0.5 进行比较判断样本的类别。感知机算法直接输出样本的类别 0 或者 1。其重映射使用了阈值函数来代替 sigmoid 函数。

\begin{align} g(z) = \left \{ \begin{array}{} 1 & if \ z \geq 0 \\ 0 & if \ z < 0 \end{array} \right. \end{align}

其参数的更新规则直接根据逻辑斯蒂回归的形式写出，并没有推导计算。

\begin{align} \theta_j & := \theta_j + \alpha(y^{(i)} - h_{\theta}(x^{(i)})) x_j^{(i)} \end{align}

感知机尽管表面上和逻辑斯蒂回归相似，但其实感知机与逻辑斯蒂回归以及最小二阶线性回归差别很大；感知机无法给出合理的概率解释，也无法利用极大似然估计进行推导。

1.1.5 Generalized Linear Models

Exponential Family
指数函数簇是一系列概率分布函数可以写成如下分布的分布
\begin{align} p(y;\eta) = b(y) exp(\eta^T T(y) - a(\eta)) \end{align}
- \(\eta\) 自然参数(natural parameter or canonical parameter) ：一般是一个实数
- \(T(y)\) 充分统计量(sufficient statistic) ：一般 \( T(y) = y \)
- \(a(\eta)\) log partition function：用于确保概率之和为 1
选取不同的 T、a、b 会得到不同的函数分布簇，分布簇由参数 \(\eta\) 决定，改变 \(\eta\) 可以得到分布簇中的不同函数分布。
构建广义线性模型
满足下面三个假设
1. 数据服从指数分布 \(y|x;\theta \thicksim ExponentialFamily(\eta)\)
2. 目标是求 \(E[T(y)|x]\) ，希望 \(h(x)=E[T(y)|x]\)
3. \(\eta\) 和 x 线性相关： \(\eta=\theta^Tx\)，\(\eta\) 是向量时 \(\quad \eta_i = \theta_i^Tx\)
步骤：
1. 先假设 \(y|x\) 服从某个分布（如高斯、泊松、伯努利、多项式等），即确定先验
2. 将该分布表示成指数函数的形式，确定出指数函数的 T、a、b
3. 依据假设 2 用期望会很容易表示出假设函数 \(h_{\theta}(x)\) （一般需要用到步骤 2 中计算出的参数）
4. 用所有样本条件概率的乘积表示出似然函数。（利用最大似然来求解参数）
5. 利用某种最优化方法（梯度下降法、牛顿法）求解最大似然
高斯分布表示成指数函数：
\begin{align*} T(y) & = y \\ \eta & = \mu \\ a(\eta) & = \frac{ {\mu}^2 }{2} = \frac{ {\eta}^2 }{2} \\ b(y) & = \frac{1}{\sqrt{2\pi}} e^{\frac{-y^2}{2}} \end{align*}
推导得到的假设函数：
\begin{align*} h_{\theta}(x) & = E[y|x;\theta] \\ & = \mu \\ & = \eta \\ & = {\theta}^T x \end{align*}
伯努利分布表示称指数函数：
\begin{align*} T(y) & = y \\ \eta & = ln \frac{\phi}{1-\phi} \\ a(\eta) & = -ln(1-\phi) \\ & = ln(1+e^{\eta}) \\ b(y) & = 1 \end{align*}
推导出的假设函数：
\begin{align*} h_{\theta}(x) & = E[y|x;\theta] \\ & = \phi \\ & = \frac{1}{1+e^{-\eta}} \\ & = \frac{1}{1+e^{-{\theta}^T x}} \end{align*}
正则响应函数(canonical response function)： \(g(\eta) = E[T(y);\eta]\) 正则关联函数(canonical link function)：\(g^{-1}\)

1.1.6 Softmax Regression

数据服从多项式分布(multinominal distribution) 。

softmax function

\begin{align} \phi_i = \frac{e^{\eta_i}}{\sum_{j=1}^k e^{\eta_j}} \end{align}

softmax regression 假设函数输出

\begin{align} h_{\theta}(x) & = E[T(y) | x;\theta] \\ & = E \left[ \left. \begin{array}{c} \mathit{1}\{y=1\} \\ \mathit{1}\{y=2\} \\ \vdots \\ \mathit{1}\{y=k-1\} \end{array} \right | x;\theta \right] \\ & = \left[ \begin{array}{c} \phi_1 \\ \phi_2 \\ \vdots \\ \phi_{k-1} \end{array} \right] \\ & = \left[ \begin{array}{c} \frac{e^{\theta_1^Tx}}{\sum_{j=1}^k e^{\theta_j^Tx}} \\ \frac{e^{\theta_2^Tx}}{\sum_{j=1}^k e^{\theta_j^Tx}} \\ \vdots \\ \frac{e^{\theta_{k-1}^Tx}}{\sum_{j=1}^k e^{\theta_j^Tx}} \end{array} \right] \end{align}

多项式分布表示成指数函数的形式：

\begin{align*} T(i) & = [ \begin{array}{} 0 & 0 & \cdots & 1_i & \cdots & 0 \end{array} ]_{k-1}^T \\ \eta & = \left[ \begin{array}{c} ln(\frac{\phi_1}{\phi_k}) \\ ln(\frac{\phi_2}{\phi_k}) \\ \vdots \\ ln(\frac{\phi_{k-1}}{\phi_k}) \end{array} \right] \\ a(\eta) & = -ln({\phi}_k) \\ b(y) & = 1 \end{align*}

soft 是相对于 hard ，hard ：非 0 即 1。

1.1.7 Gaussian Discriminant Analysis

判别学习模型：尝试找到一条决策线，可以直接得到新样本属于决策线的哪一侧；即由数据直接学习决策函数 f(X) 或者条件概率分布 P(Y|X) 作为预测的模型。特点：准确率更高，简化学习问题（可以对数据进行各种程度上的抽象，定义特征并使用特征）。典型的判别模型包括： k 近邻法、感知机、决策树、逻辑斯蒂回归模型、最大熵模型、支持向量机、提升方法、条件随机场。

生成学习模型：分别为每个类别建模，判定新样本更符合哪个类别。由数据学习联合概率分布 P(X，Y) ，然后求出条件概率分布 P(Y|X) 作为预测模型。特点：可以还原出联合概率分布，学习收敛速度更快，存在隐变量时仍可以使用。典型的生成模型有：朴素贝叶斯法、隐马尔科夫模型。

高斯判别模型是一个生成模型（既然是生成模型为啥加判别模型？？）。输入特征 x 是连续随机变量，使用多元高斯模型对不同的类别进行建模，不同的类别使用相应的协方差。模型如下：

\begin{gather} y \sim Bernoulli(\phi) \\ x|y = 0 \sim \mathcal{N} (\mu_0, \sum) \\ x|y = 1 \sim \mathcal{N} (\mu_1, \sum) \end{gather}

可以写出相应的概率分布：（模型的参数有 \(\phi, \ \sum \ \mu_0 \ \mu_1\)）

\begin{align*} p(y) & = \phi^y (1 - \phi)^{1-y} \\ p(x|y=0) & = \frac{1}{(2\pi)^{n/2} |\sum|^{1/2}} exp \left( -\frac{1}{2} (x-\mu_0)^T \sum^{-1} (x-\mu_0) \right) \\ p(x|y=0) & = \frac{1}{(2\pi)^{n/2} |\sum|^{1/2}} exp \left( -\frac{1}{2} (x-\mu_1)^T \sum^{-1} (x-\mu_1) \right) \end{align*}

写出对数似然函数（联合似然 Joint likelihood）：

\begin{align*} \ell (\phi, \mu_0, \mu_1, \sum) & = ln \prod_{i=1}^m p(x^{(i)}, y^{(i)}; \phi,\mu_0,\mu_1,\sum) \\ & = ln \prod_{i=1}^m p(x^{(i)}|y^{(i)};\mu_0,\mu_1,\sum) p(y^{(i)};\phi) \end{align*}

将对数似然函数分别对各个参数求偏导，并令结果等于零，可求解得各个参数：

\begin{align*} \phi & = \frac{1}{m} \sum_{i=1}^m \mathit{1}\{y^{(i)} = 1\} \\ \mu_0 & = \frac{ \sum_{i=1}^m \mathit{1}\{y^{(i)} = 0\} x^{(i)} }{ \sum_{i=1}^m \mathit{1} \{ y^{(i)} = 0\} } \\ \mu_1 & = \frac{ \sum_{i=1}^m \mathit{1}\{y^{(i)} = 1\} x^{(i)} }{ \sum_{i=1}^m \mathit{1} \{ y^{(i)} = 1\} } \\ \sum & = \frac{1}{m} \sum_{i=1}^m (x^{(i)} - \mu_{y^{(i)}})(x^{(i)} - \mu_{y^{(i)}})^T \end{align*}

预测

\begin{align*} & arg \max_y p(y|x) \\ & = arg \max_y \frac{p(x|y)p(y)}{p(x)} \\ & = arg \max_y p(x|y)p(y) \\ & = arg \max_y p(x|y) \quad \text{if p(y) is uniform which means } p(y=1)=p(y=0) \end{align*}

GDA VS Logistic Regression

高斯判别模型类别为 1 的概率表达式等同于逻辑斯蒂回归的判别函数
\begin{gather*} p(y=1|x;\phi, \sum, \mu_0, \mu_1) = \frac{1}{ 1 + exp(-\theta^T x)} \quad \text{(view as a function as x)}\\ \theta \propto \phi, \sum, \mu_0, \mu_1 \end{gather*}
GDA 使用的假设更强，当数据符合多元高斯模型的时候效果很好，且需要较少的样本就可以训练好模型。由中心极限定理：在某种一条件下，大量随机变量之和的分布逼近于正态分布。所以在样本量很大时候，GDA 算法分类准确率会很高（这里样本量大只是为了让样本总体服从高斯分布，与前面需要较少的训练样本并不冲突）。而当数据并不是很符合高斯分布时，使用逻辑斯蒂回归会得到更加鲁棒的模型（数据服从多种分布（高斯或泊松等非高斯分布）时仍然可以得到比较好的结果）。并且一般来说当数据是非高斯的有限数据集时，逻辑斯蒂回归效果更好。

一般规律，且反推仍然不成立
\begin{gather*} x|y = 1 \sim ExpFamily(\eta_1) \\ x|y = 0 \sim ExpFamily(\eta_0) \\ \Longrightarrow p(y=1|x) \sim logistic \end{gather*}

1.1.8 Support Vector Machines - SVM

SVM 的基本思想就是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。

先写算法的最终求解方法，步骤。认为此时已经知晓所有知识。

算法步骤
1. 构造含约束的最优化问题；根据 KKT 条件求得分离超平面的表达式
2. 求得相应的对偶问题
3. 利用 SMO 算法高效求解对偶问题，得到分离超平面的参数值
4. 依据分离超平面来处理新样本
再写一些术语的解释
算法演进过程：
\begin{align} \max_{w, b} & \gamma \\ s.t. \quad & y^{(i)} \left( \frac{w}{||w||} \cdot x^{(i)} + \frac{b}{||w||} \right) \geq \gamma, \quad i=1,2,\cdots,m \end{align} \begin{align} \max_{w, b} & \frac{\hat{\gamma}}{||w||} \\ s.t. \quad & y^{(i)} \left( w \cdot x^{(i)} + b \right) \geq \hat{\gamma}, \quad i=1,2,\cdots,m \end{align} \begin{align} \min_{w, b} & \frac{1}{2}||w||^2 \\ s.t. \quad & y^{(i)} \left( w \cdot x^{(i)} + b \right) \geq 1, \quad i=1,2,\cdots,m \end{align} \begin{align} \min_{w, b, \color{red}{\xi_i}} & \frac{1}{2}||w||^2 + C\sum_{i=1}^m \xi_i \\ s.t. \quad & y^{(i)} \left( w \cdot x^{(i)} + b \right) \geq 1 - \xi_i, \quad i=1,2,\cdots,m \\ & \xi_i \geq 0, \quad i=1,2,\cdots,m \end{align} \begin{align} \max_{\alpha} & W(\alpha) = \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i,j=1}^m y^{(i)}y^{(j)} \alpha_i\alpha_j \left \langle x^{(i)},x^{(j)} \right \rangle \\ s.t. \quad & 0 \leq \alpha_i \leq C, \quad i = 1,2,\cdots,m \\ & \sum_{i=1}^m \alpha_i y^{(i)} = 0 \end{align} \begin{align} \max_{\alpha} & W(\alpha) = \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i,j=1}^m y^{(i)}y^{(j)} \alpha_i\alpha_j K( x^{(i)},x^{(j)} ) \\ s.t. \quad & 0 \leq \alpha_i \leq C, \quad i = 1,2,\cdots,m \\ & \sum_{i=1}^m \alpha_i y^{(i)} = 0 \end{align} \begin{align} w^* & = \sum_{i=1}^m \alpha_i^* y^{(i)} x^{(i)} \\ b^* & = y^{(i)} - \sum_{i=1}^m \alpha_i^* y^{(i)} K(x^{(i)}, x^{(j)}) \\ f(x) & = sign \left( \sum_{i=1}^m \alpha_i^* y^{(i)} K(x \cdot x^{(i)}) + b^* \right) \end{align}
1. 因为 SVM 学习算法的目标是最大化几何间隔\(\gamma\)，所以构建相应的模型，其目标函数表示为最大化几何间隔，同时约束每个训练样本距离分离超平面的距离大于该几何间隔。
2. 由于最终需要求解的是分离超平面的权重，所以需要利用几何间隔与函数间隔的关系，让目标函数中显示出现分离超平面的权重；即将目标函数和约束中的几何间隔统一改为函数间隔 \(\hat{\gamma}\)。
3. 函数间隔的取值并不影响上述最优化问题的解（当分离超平面的权重成比例变化时，函数间隔也呈现相应比例的变化），即函数间隔成比例变化时对不等式约束没有影响（相当于不等式的两边同时乘以该变化系数），对目标函数的优化也没有影响（目标函数的分子和分母同时乘以该变化系数）。为了简化模型表达式，取函数间隔为 1 。
4. 此时目标函数的分子为 1 ，分母为分离超平面的权重，且为求最大值。由于权重处于分母时，不利于求解，此时只需要最小化目标函数的分母即可。同时将权重转化为二次。此时的约束最优化问题与原问题是等价的，这是一个凸二次规划问题（convex quadratic programming）。Andrew Ng 讲解上述的变化都是在将非凸优化问题转化成凸优化问题。
5. 由于存在线性不可分以及 outliers 让分离超平面变差的可能。使函数间隔不再始终大于1，将函数间隔减去一个松弛变量，即函数间隔大于\(1-\xi_i\)。由于不再要求函数间隔始终大于1，所以可以找打一个分离超平面来分割不同的类别。但同时也不希望松弛变量太大，所以在目标函数中增加相应的正则化项（这里使用的是\(\ell_1\) regularization）。同时使用C来调节权重与松弛变量在目标含住中的比例关系。
6. 由于该凸二次规划问题求解时间复杂度较高，所以转而去求解相应的对偶问题。使用对偶问题可以高效求解，同时可以使用核函数。
7. 如果可以将特征都转换成內积的表示形式，就可以使用核函数。转换成內积形式以后，将表达式中的\(x\)转换成\(\phi(x)\) 就表示使用了核函数。而且并不需要知道\(\phi(x)\)的具体表达式，只需要代入\(\phi(x)^T \phi(z)\)乘积的结果，即选取的核函数的表达式\(K(\phi(x),\phi(z))\)就可以，这样将大大简化计算。
8. 另外转换成对偶问题后，可以使用 SMO（sequential minimal optimization）算法来高效求解参数\(\alpha_1,\cdots,\alpha_m\)
术语解释
1. 原问题 - 对偶问题
  
  虽然有很多的最优化算法可以求解该凸二次规划问题，但是当训练样本容量很大时，这些算法往往变得非常低效。而当参数满足 Karush-Kuhn-Tucker (KKT) 条件时，原问题和对偶问题的解相同；并且将原问题转换成对偶问题后，可以使用 SMO 算法高效求解，所以才提出了原问题(primal program)及对偶问题(dual problem)。事实上这里使用的是拉格朗日对偶性(Lagrange duality)，原问题和对偶问题的函数表达式都是拉格朗日函数(Lagrange function)。我们需要解决的问题一般都是含约束的最优化问题，而求解含约束的最优化问题，一种有效的方法就是使用拉格朗日乘数法。使用拉格朗日乘数法首先构造拉格朗日函数，然后对拉格朗日函数参数的不同求解顺序构成了原问题及对偶问题。
  \begin{align} \min_{w} & f(w) \\ s.t. \quad & g_i (w) \leq 0, \quad i=1,2,\cdots,k \\ & h_i (w) = 0, \quad i=1,2,\cdots,l \end{align} \begin{equation} \mathcal{L}(w,\alpha,\beta) = f(w)+ \sum_{i=1}^k \alpha_i g_i(w) + \sum_{i=1}^l \beta_i h_i(w) \end{equation} \begin{align} \theta_p(w) & = \max_{\alpha,\beta:\alpha_i \geq 0} \mathcal{L}(w, \alpha, \beta) \\ \min_w \theta_p(w) & = \min_w \max_{\alpha,\beta:\alpha_i \geq 0} \ L(w, \alpha, \beta) \\ p^* & = \min_w \ \theta_p(w) \end{align} \begin{align} \theta_D(\alpha, \beta) & = \min_w \mathcal{L}(w, \alpha, \beta) \\ \max_{\alpha,\beta:\alpha_i \geq 0} \theta_D(\alpha, \beta) & = \max_{\alpha,\beta:\alpha_i \geq 0}\ \min_w \mathcal{L}(w, \alpha, \beta) \\ d^* & = \max_{\alpha,\beta:\alpha_i \geq 0} \theta_D(\alpha, \beta) \end{align} \begin{equation} d^* = \max_{\alpha,\beta:\alpha_i \geq 0}\min_w \mathcal{L}(w, \alpha, \beta) \leq \min_w \max_{\alpha,\beta:\alpha_i \geq 0} \mathcal{L}(w, \alpha, \beta) = p^* \end{equation}
  将原始的问题转换成拉格朗日函数，其中\(\alpha_i\) 和 \(\beta_i\)都是拉格朗日乘子，而且不等式约束\(g_i(w)\leq0\)，要求其拉格朗日乘子\(\alpha_i\geq0\)。此时只要不满足等式或者不等式约束，也就是存在一个或者多个\(i\)使得\(g_i(w) \ge 0\)或者 \(h_i(w)\neq0\)，那么求解\(\theta_p(w)\)的结果必然是无穷大；而当所有的\(i\)都满足约束时，\(\theta_p(w)=f(w)\)，此时两者等价，再对\(\theta_p(w)\)参数\(w\)求最小，即为原始问题。也就是说，两者是等价的，相当于同一个问题。
  \begin{align} \theta_p(w) = \left\{ \begin{array}{} f(w) & 如果w满足原约束 \\ \infty & 否则 \end{array} \right. \end{align}
  而对偶问题就是调节一下求解的参数的顺序。原问题中先对参数\(\alpha,\beta\)求最大，然后对\(w\)求最小；对偶问题中先对参数 \(w\)求最小，然后再对参数\(\alpha,\beta\)求最大，也就是对调了 max 和 min 的求解顺序，仅此而已。
  
  由于\(\max \min(\cdots) \leq \min \max(\cdots)\)，所以\(d^* \leq p^*\)。并且当\(w,\alpha,\beta\)满足 KKT 条件时，原问题的解和对偶问题的解相同即\(p^*=d^*\)。反之也成立，即如果原问题和对偶问题的解相同，那么\(w,\alpha,\beta\)满足 KKT 条件。
  \begin{align} \frac{\partial}{\partial w_i} \mathcal{L}(w^*,\alpha^*,\beta^*) & = 0, \quad i=1,2,\cdots,n \\ \alpha_i^*g_i(w^*) & = 0, \quad i=1,2,\cdots,k \label{kkt:ducom} \\ g_i(w^*) & \leq 0, \quad i=1,2,\cdots,k \\ \alpha^* & \geq 0, \quad i=1,2,\cdots,k \\ h_i(w) & = 0, \quad i=1,2,\cdots,l \\ \end{align}
  公式\(\eqref{kkt:ducom}\)称为 KKT 对偶互补条件（KKT dual complementary condition）；由此条件可知，若\(\alpha_i^* > 0\)，则\(g_i(w^*) = 0\)。这个条件是说明 SVM 只有少数支撑向量的关键，同时也用于证明 SMO 算法收敛性。
  
  具体到 SVM 算法，原问题的拉格朗日函数是
  \begin{align} \mathcal{L}(w,b,\xi,\alpha,\mu) = & \frac{1}{2}||w||^2 + C\sum_{i=1}^m\xi_i \notag \\ & - \sum_{i=1}^m\alpha_i[y^{(i)}(w \cdot x^{(i)} + b)-1 + \xi_i] - \sum_{i=1}^m\mu_i\xi_i \\ 其中 & \alpha_i \geq 0; \mu_i \geq 0 \quad 两者都是拉格朗日乘子 \notag \end{align}
  对偶问题是拉格朗日函数的极大极小问题。首先求\(\mathcal{L}(w,b,\xi,\alpha,\mu)\)对\(w,b,\xi\)求极小，分别求导并令导数为0
  \begin{align} \nabla_w \mathcal{L}(w,b,\xi,\alpha,\mu) & = w - \sum_{i=1}^m \alpha_i y^{(i)} x^{(i)} = 0 \\ \nabla_b \mathcal{L}(w,b,\xi,\alpha,\mu) & = -\sum_{i=1}^m \alpha_i y^{(i)} = 0 \\ \nabla_{\xi_i} \mathcal{L}(w,b,\xi,\alpha,\mu) & = C - \alpha_i -\mu_i = 0 \end{align}
  得到
  \begin{align} w=\sum_{i=1}^m \alpha_i y^{(i)} x^{(i)} \\ \sum_{i=1}^m \alpha_i y^{(i)} = 0 \\ C- \alpha_i -\mu_i = 0 \end{align}
  将结果带入原问题的拉格朗日函数，
  \begin{align} \min_{w,b,\xi} \mathcal{L}(w,b,\xi,\alpha,\mu) = -\frac{1}{2}\sum_{i=1}^m\sum_{i=1}^m \alpha_i\alpha_j y^{(i)}y^{(j)} \langle x^{(i)}x^{(j)} \rangle + \sum_{i=1}^m\alpha_i \end{align}
  再对\(\min_{w,b,\xi}\mathcal{L}(w,b,\xi,\alpha,\mu)\)求参数\(\alpha\)的极大，就得到了对偶问题目标函数的表达式，连同上面得到的约束，共同构成对偶问题：
  \begin{align} \max_\alpha & = -\frac{1}{2}\sum_{i=1}^m\sum_{i=1}^m \alpha_i\alpha_j y^{(i)}y^{(j)} \langle x^{(i)}x^{(j)}\rangle + \sum_{i=1}^m\alpha_i \\ s.t. \quad & = \sum_{i=1}^m \alpha_i y^{(i)} = 0 \\ & C - \alpha_i - \mu_i = 0, \quad i=1,2,\cdots,m \\ & \alpha_i = 0, \quad i=1,2,\cdots,m \\ & \mu_i \geq = 0, \quad i=1,2,\cdots,m \end{align}
  最后利用倒数第三个等式约束消去变量\(\mu_i\)，只留下变量\(\alpha_i\)，得到\(0 \leq \alpha_i \leq C\)，同时将目标函数中的输入属性的內积\(\langle x^{(i)},x^{(j)} \rangle\)替换成核函数\(\langle \phi(x^{(i)}),\phi(x^{(j)}) \rangle\)，并且直接使用核函数的最终形式\(K(x^{(i)},x^{(j)})\)得到对偶问题的最终形式
  \begin{align} \max_{\alpha} W(\alpha) & = \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i,j=1}^m y^{(i)}y^{(j)} \alpha_i\alpha_j K( x^{(i)},x^{(j)} ) \\ s.t. \quad & 0 \leq \alpha_i \leq C, \quad i = 1,2,\cdots,m \\ & \sum_{i=1}^m \alpha_i y^{(i)} = 0 \end{align}
2. Kernel
  
  使用核函数的方法：将原始输入的属性值\(x\)变换成\(\phi(x)\)特征作为算法的输入（仅此而已，不知道为什么原来就一直没有看懂）。只是在具体运用时利用了一点小技巧，并不是直接去计算映射后的值然后再去计算，而是先将原始输入属性值表示称內积的形式，然后巧妙的用核函数来代替內积。这样做的优势：将核函数代替內积可以高效计算；同时可以将特征映射到高维空间，从而将原来线性不可分的问题转换成线性可分。
  
  一般来说，如果输入空间\(x^{(i)} \in \mathbb{R}^n\)，对应的标记有两类\(y^{(i)} \in \{-1,1\}\)，如果能用\(\mathbb{R}^n\)中的一个超曲面将正负实例正确分开，则称这个问题为非线性可分问题。而非线性问题往往不好求解，一般采取非线性变换， 将非线性问题转换成线性问题 ，通过求解变换后的线性问题来得到原来的非线性问题的解。
  
  用线性分类方法求解非线性问题分为两步：首先使用一个变换将原空间的数据映射到新空间；然后在新空间里用线性分类学习方法从训练数据中学习分类模型。核技巧就是这样的方法。支撑向量机使用核技巧的基本想法就是通过一个非线性变换将输入空间对应到一个特征空间，使得在输入空间\(\mathbb{R}^n\)中的超曲面对应于特征空间\(\mathcal{H}\)中的超平面，这样学习任务通过在特征空间中求解线性支持向量机就可以完成。其中输入空间为欧式空间\(\mathbb{R}^n\)或离散空间，特征空间为希尔伯特空间\(\mathcal{H}\)（no see）。
  
  设\(\mathcal{X}\)是输入空间，\(\mathcal{H}\)为特征空间，如果存在一个从\(\mathcal{X}\)到\(\mathcal{H}\)的映射， \[\phi(x):\mathcal{X} \to \mathcal{H} \]使得对所有的\(x,z \in \mathcal{X}\)，函数\(K(x,z)\)满足\[K(x,z)=\phi(x) \cdot \phi(z)\]则称\(K(x,z)\)为核函数。
  
  核函数的想法是，在学习和预测时，只使用核函数\(K(x,z)\)，而不显示的定义映射函数\(\phi\)，这将比直接计算\(\phi(x) \cdot \phi(z)\)容易的多。由于算法中所有的属性值（例如目标函数和决策函数）都可以表示成內积的形式\(\langle x,z \rangle\)，因为需要将所有的\(x\)都替换成\(\phi(x)\)，那么直接将內积替换成\(\langle\phi(x),\phi(z)\rangle\)的形式，而 \(\langle\phi(x),\phi(z)\rangle\)就是一个核函数，直接带入\(K(x,z)\)的表达式就可以。最终结果就是将算法中所有的內积都直接替换成核函数即可；根本无需计算映射，也根本无需知道映射函数的表达式，只需要使用核函数的最终表达式。而且核函数并不单单可以应用在支撑向量机上，所有可以将输入属性表示成內积的形式的算法都可以使用。
  
  对于给定的核\(K(x,z)\)，特征空间\(\mathcal{H}\)和映射函数\(\phi\)的取法并不唯一。特征空间可以不同，即便在同一个特征空间也可以取不同的映射。
  
  TODO 举一个核函数和映射函数表达式的例子
  
  核函数的选取： 有时可以选择标准的核函数，有时需要自己根据问题构造核函数（需要阅读相应的论文来了解怎样为一个新问题发明一个新的核函数）。
  
  通常所说的核函数就是正定核函数（positive definite kernel function）。根据 Mercer 定理，正定核函数的 充要条件 ：设已知 \(K:\mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R} \)，则\(K(x,z)\)是正定核函数的充要条件是对任意 \(\{x^{(1)},x^{(2)},\cdots,x^{(m)}\},\ (m < \infty) \)，相应的核矩阵 Gram 矩阵\(K=[ K(x^{(i)},x^{(j)}) ]_{m \times m} \) 是对称半正定的。
  
  常用核函数: 高斯核函数（Gaussian kernel function）\[ K(x,z) = exp \left( -\frac{||x-z||^2}{2\sigma^2} \right) \] 多项式核函数（polynomial kernel function）\[ K(x,z) = (x^T z +c)^d \] 字符串核函数（string kernel function）
  
  支撑向量机，通过核函数将数据映射到高维空间只是增大了数据线性可分的可能性，但无法确保映射后一定线性可分。因此需要使用 \(\ell 1\)正则化来修正模型；同时也使得分割线对 outliers 不那么敏感。
3. 决策函数
  
  决策函数即算法最终得到的分离超平面的表达式。分离超平面\(w^*,b^*\)的表达式由原问题通过满足 KKT 条件求解得到，而表达式中参数具体的值由对偶问题通过 SMO 算法求得。原问题可以表示为
  \begin{align} \min_{w, b,\xi_i} & \frac{1}{2}||w||^2 + C\sum_{i=1}^m \xi_i \\ s.t. \quad & -[y^{(i)} \left( w \cdot x^{(i)} + b \right) - 1 + \xi_i] \leq 0, \quad i=1,2,\cdots,m \\ & -\xi_i \leq 0, \quad i=1,2,\cdots,m \end{align}
  拉格朗日函数
  \begin{align} \mathcal{L}(w,b,\xi,\alpha,\mu) = & \frac{1}{2}||w||^2 + C\sum_{i=1}^m\xi_i \notag \\ & - \sum_{i=1}^m\alpha_i[y^{(i)}(w \cdot x^{(i)} + b)-1 + \xi_i] - \sum_{i=1}^m\mu_i\xi_i \end{align}
  解满足 KKT 条件
  \begin{align} & \partial_w\mathcal{L}(w^*,b^*,\xi^*,\alpha^*,\mu^*) = w^* - \sum_{i=1}^m \alpha_i^* y^{(i)} x^{(i)} = 0 \\ & \partial_b\mathcal{L}(w^*,b^*,\xi^*,\alpha^*,\mu^*) = -\sum_{i=1}{m} \alpha_i^* y^{(i)} = 0 \\ & \partial_{\xi}\mathcal{L}(w^*,b^*,\xi^*,\alpha^*,\mu^*) = C - \alpha^* - \mu^* = 0 \\ & \alpha_i^* [y^{(i)} \left( w \cdot x^{(i)} + b \right) - 1 + \xi_i] = 0 \\ & \mu_i^* \xi_i^* = 0 \\ & -[y^{(i)} \left( w \cdot x^{(i)} + b \right) - 1 + \xi_i] \leq 0 \\ & -\xi_i^* \leq 0 \\ & \alpha_i^* \geq 0 \\ & \mu_i^* \geq 0 \end{align}
  求解上面的方程，\(w^*\)较易求解。再由 KKT 对偶互补条件可知，当存在\(\alpha_i^*\)满足\(0 < \alpha_i^* < C\)时， \(y^{(i)}(w^* \cdot x^{(i)} + b^*) - 1 = 0\)，从而可求得\(b^*\)。其中会利用一个小技巧\(y^{(i)} \cdot y^{(i)} = 1\)，并用核函数替换內积最终得到
  \begin{align} w^* & = \sum_{i=1}^m \alpha_i^* y^{(i)} x^{(i)} \\ b^* & = y^{(i)} - \sum_{i=1}^m \alpha_i^* y^{(i)} K(x^{(i)}, x^{(j)}) \\ & \sum_{i=1}^m \alpha_i^* y^{(i)} K(x \cdot x^{(i)} ) + b^* = 0 \\ f(x) & = sign \left( \sum_{i=1}^m \alpha_i^* y^{(i)} K(x \cdot x^{(i)}) + b^* \right) \end{align}
4. 支撑向量
  在线性不可分的情况下，将对偶问题的解中对应\(\alpha_i^* > 0\)的样本点\((x^{(i)},y^{(i)})\)称为支撑向量。软间隔的支撑向量可能在任何地方：可以在间隔边界上；可以在间隔边界与分离超平面之间；也可以在分离超平面误分的一侧。
  - 若\(\alpha_i^* < C\)，则\(\xi_i=0\)：支撑向量落在边界线上
  - 若\(\alpha_i^* = C, \quad 0 < \xi_i < 1\)，则分类正确：支撑向量在间隔边界与分离超平面之间
  - 若\(\alpha_i^* = C, \quad \xi_i = 1\)，则支撑向量位于分离超平面上
  - 若\(\alpha_i^* = C, \quad \xi_i > 1\)，则支撑向量位于分离超平面误分的一侧
  note：\(0 \leq \alpha_i^* \leq C, \quad 1-\xi_i\)是函数间隔；只有\(\alpha_i \ne 0\)对应的样本点才是支撑向量？？？可能 KKT 对偶互补条件中两个变量都为零？？？ TODO
5. Sequential Minimal Optimization
  
  坐标上升法： 当求解多变量最优化问题且不存在约束的时候，可以使用坐标上升法（和梯度下降法以及牛顿法都是最优化方法）来求解。利用两层循环来实现，外层循环便利所有样本，内层循环便利所有变量。在内层循环中每次仅优化一个变量，同时固定其他的变量不变，针对该变量来优化目标函数。这样总是沿着和坐标轴平行的方向取得最大值，而且选取往最优解移动的速度最快的变量来求解。
  
  序列最小最优化算法求解的对象是凸二次规划的对偶问题：
  \begin{align} \max_{\alpha} W(\alpha) & = \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i,j=1}^m y^{(i)}y^{(j)} \alpha_i\alpha_j K(x^{(i)},x^{(j)}) \\ s.t. \quad & 0 \leq \alpha_i \leq C, \quad i = 1,2,\cdots,m \\ & \sum_{i=1}^m \alpha_i y^{(i)} = 0 \end{align}
  在该问题中变量是拉格朗日乘子\(\alpha_i\)，每个样本都有一个拉格朗日乘子，变量的总数等于训练样本的个数\(m\)
  
  算法基本思路：因为 KKT 条件是该最优化问题的充分必要条件，当所有变量都满足该最优化问题的 KKT 条件，那么这个最优化问题的解就得到了。否则，选择两个变量，固定其他变量，针对这两个变量构建二次规划问题，而求解该二次规划子问题将使得目标函数值变大。这样将问题不断分解为子问题，并对子问题求解，直到所有的变量都满足 KKT 条件。
  
  由于构建的二次规划子问题可以通过解析的方法求解，这样就大大提高了整个算法的计算速度（迭代会很耗时的）。另外由于约束 \(\sum_{i=1}^m \alpha_i y^{(i)} = 0\)的存在，无法只更改一个变量，因为当其他的变量值都不改变时，该变量的值也会由于约束的存在而固定无法改变。所以子问题每次都会同时更新两个变量，在满足约束的条件下来求解二次规划问题。
  
  SMO 是启发式算法：好像两个变量的选择方法是启发式搜索算法（不确定）。
  
  整个 SMO 算法包括两个部分：\(\textcircled{1}\)求解两个变量二次规划的解析方法；\(\textcircled{2}\)选择变量的启发式方法。
  1. 两个变量二次规划的求解方法
    
    每个子问题都可以转换成一个变量的二次函数，很容易求得解析解。
    
    假设利用启发式方法选择出两个变量\(\alpha_1,\alpha_2\)，其他变量\(\alpha_3,\alpha_4,\cdots,\alpha_m\)固定不变，由约束可知 \( \alpha_1 y^{(1)} + \alpha_2 y^{(2)} = -\sum_{i=3}^{m} \alpha_i y^{(i)} \)由于公式右侧是固定的，使用一个常量符号 \(\zeta\)替代
    \begin{equation} \alpha_1 y^{(1)} + \alpha_2 y^{(2)} = \zeta \end{equation}
    虽然要同时更新两个变量，但其实只有一个自由变量。此处使用\(\alpha_2\)表示\(\alpha_1\)，利用\({(y^{(1)})}^2 = 1\)
    \begin{equation} \alpha_1 = ( \zeta - \alpha_2 y^{(2)} ) y^{(1)} \end{equation}
    因此目标函数可以写成
    \begin{equation} W(\alpha_1,\alpha_2,\cdots,\alpha_m) = W((\zeta - \alpha_2 y^{(2)})y^{(1)},\alpha_2,\alpha_3,\cdots,\alpha_m) \end{equation}
    由于将\(\alpha_3,\alpha_4,\cdots,\alpha_m\)视为固定值，目标函数可以看做关于\(alpha_2\)的二次函数，可以写成 \(a\alpha_2^2 + b\alpha_2 + c\)的形式，在没有约束的情况下，可以很容易的通过求导并令导数为零得到极值。
    
    同时每个变量都必须满足约束\(0 < \alpha_i < C\)，具体到一个子问题上，对于变量\(\alpha_1,\alpha_2\)，两个变量都必须约束在 \([0,C] \times [0, C]\)的方框中，再加上上面的线性约束，\(\alpha_1,\alpha_2\)必须约束在被方框截断的直线上。从而\(L \leq \alpha_2^{new} \leq H\)，其中L与H是\(\alpha_2^{new}\)所在的对角线段端点的界。另外线性约束中的常量\(\zeta\)可以用 \(\alpha_1 \pm \alpha_2\)表示
    \begin{align} & if \ y^{(1)} \neq y^{(2)} \notag \\ & L=\max(0, \alpha_2^{old} - \alpha_1^{old}), H=\min(C,C+\alpha_2^{old}-\alpha_1^{old}) \\ & if \ y^{(1)} = y^{(2)} \notag \\ & L=\max(0,\alpha_2^{old} + \alpha_1^{old}-C), H=\min(C,\alpha_2^{old}+\alpha_2{old}) \end{align}
    先只要求满足线性约束，求解得到α₂^{new,unclipped} 然后再裁剪来满足 box constraints
    \begin{align} \alpha_2^{new} = \left\{ \begin{array}{} H & if \alpha_2^{new,unclipped} > H \\ \alpha_2^{new,unclipped} & if L \leq \alpha_2^{new,unclipped} \leq H \\ L & if \alpha_2^{new,unclipped} < L \end{array} \right. \end{align}
    再利用线性约束求得\(\alpha_1^{new}\)
    \begin{equation} \alpha_1^{new} = \alpha_1^{old} + y^{(1)}y^{(2)} (\alpha_2^{old} - \alpha_2^{new}) \end{equation}
    \(\alpha_2\)的求解：为了叙述方便，记\[g(x)=\sum_{i=1}^m \alpha_i y^{(i)} K(x^{(i)},x) + b\] 令 \[E_i = g(x^{(i)}) - y^{(i)} = (\sum_{j=1}^m \alpha_j y^{(j)} K(x^{(j)},x^{(i)}) + b) - y^{(i)}, \quad i=1,2 \] 用于表示g(x)对输入x⁽ⁱ⁾的预测值与真实值y⁽ⁱ⁾之差。最终可得
    \begin{align} \alpha_2^{new,unclipped} = \alpha_2^{old} + \frac{y^{(2)} (E_1 - E_2)}{\eta} \\ \eta = K_{11} + K_{22} -2K_{12} = ||\phi(x^{(1)}) - \phi(x^{(2)}||^2 \end{align}
    其中\(\phi(x)\)是输入空间到特征空间的映射
  2. 变量选择方法
    
    SMO 称第一个变量的选择为外层循环，第二个变量的选择为内层循环。外层循环在训练样本中选择违反 KKT 条件最严重的样本点，将其对应的变量作为第一个变量。内层循环的标准是希望选择的变量有足够大的变化。
    \begin{align} KKT 条件 \notag \\ \alpha_i = 0 \Leftrightarrow y^{(i)}g(x^{(i)}) \geq 1 \\ 0 < \alpha_i < C \Leftrightarrow y^{(i)}g(x^{(i)})=1 \\ \alpha_i = C \Leftrightarrow y^{(i)}g(x^{(i)}) \leq 1 \\ 其中 g(x^{(i)}) = \sum_{j=1}^m \alpha_j y^{(j)} K(x^{(i)}, x^{(j)}) + b \end{align}
    外层循环首先遍历所有满足条件\(0 < \alpha_i < C\)的样本点，即在间隔边界上的支撑向量点，检验他们是否满足 KKT 条件；如果这些样本点都满足 KKT 条件，那么遍历整个训练集，检验他们是否满足 KKT 条件。这里的满足 KKT 条件都有一定的误差容忍范围，典型值为0.001~0.01。什么叫做违反最严重？实际值与要求值差别比较大？ TODO
    
    内层循环选择\(\alpha_2\)，由于\(\alpha_2^{new}\)依赖于\(|E_1 - E_2|\)，一种简单的做法是通过使\(|E_1 - E_2|\)最大来使得 \(\alpha_2\)有足够大的变化。由于\(\alpha_1\)已经确定，\(E_1\)也随之确定。如果\(E_1\)是正的，那么选择最小的\(E_i\)作为 \(E_2\)；如果\(E_1\)是负的，那么选择最大的\(E_i\)作为\(E_2\)。
    
    为了节省计算时间，将所有的\(E_i\)值保存在一个列表中。
    
    在特殊情况下，如果内层循环通过以上方法选择的\(\alpha_2\)不能使目标函数有足够的上升，那么采用以下启发式规则继续选择 \(\alpha_2\)。遍历在间隔边界上的支撑向量点，依次将其对应的变量作为\(\alpha_2\)试用，直到目标函数有足够的上升。若找不到合适的\(\alpha_2\)，那么遍历训练数据集；若仍找不到合适的\(\alpha_2\)，则放弃之前选择的\(\alpha_1\)，再通过外层循环寻找另外的\(\alpha_1\)。注：这里目标函数是上升还是下降要看目标函数具体是在求最大还是最小。
    
    计算阈值\(b\)和差值\(E_i\)：在每次完成两个变量的优化后，都要重新计算阈值\(b\)。当\(0 < \alpha_1^{new} < C\)时，由 KKT 条件可知\(\sum_{i=1}^m \alpha_i y^{(i)} K_{i1} + b = y^{(1)}\)和\(E_1\)的定义
    
    \(E_1 = \sum_{i=3}^m \alpha_i y^{(i)} K_{i1} + \alpha_1^{old}y^{(1)}K_{11} + \alpha_2^{old}y^{(2)}K_{21} + b^{old} - y^{(1)}\)可知
    \begin{align} b_1^{new} & = y^{(1)} - \sum_{i=3}^m \alpha_i y^{(i)} K_{i1} - \alpha_1^{new}y^{(1)}K_{11} - \alpha_2^{new}y^{(2)}K_{21} \\ & = -E_1 - y^{(1)}K_{11}(\alpha_1^{new} - \alpha_1^{old}) - y^{(2)}K_{21}(\alpha_2^{new} - \alpha_2^{old}) + b^{old} \end{align}
    同样，如果\(0 < α₂^new < C)，那么
    \begin{align} b_2^{new} = -E_2 - y^{(1)}K_{12}(\alpha_1^{new} - \alpha_1^{old}) - y^{(2)}K_{22}(\alpha_2^{new} - \alpha_2^{old}) + b^{old} \end{align}
    如果\(\alpha_1^{new},\alpha_2^{new}\)同时满足\(0 < \alpha_i^{new} < C, i=1,2\)，那么\(b_1^{new}=b_2^{new}\)；如果 \(\alpha_1^{new},\alpha_2^{new} = 0 \ or \ C\)，那么\(b_1^{new},b_2^{new}\)以及他们之间的数都满足 KKT 条件，这时选择 \(b_1^{new},b_2^{new}\)的中点作为\(b^{new}\)。
    
    另外再每次更新完两个变量后，还必须更新对应的\(E_i\)值，并将他们保存到列表中。
    \begin{align} E_i^{new} = \sum_S y^{(j)} \alpha_j K(x^{(i)},x^{(j)}) + b^{new} - y^{(i)} \end{align}
    其中S是所有支撑向量\(x^{(j)}\)的集合。
算法演绎
1. Support Vector Regression
  
  支撑向量回归(SVR)假设我们能容忍 f(x) 与 y 之间最多有 \(\epsilon\) 的偏差，即仅当 f(x) 与 y 之间的差别绝对值大于 \(\epsilon\) 时才计算损失。
  
  周志华 P133
2. Semi-Supervised Support Vector Machine
  
  半监督支撑向量机(S3VM)
  
  Transductive Support Vector Machine(TSVM)
  
  周志华 P298

1.1.9 Expectation-Maximization

期望最大化算法(EM)用于解决含有隐变量的问题。隐变量(latent variable)表示未观测变量，用 z 表示；x 表示观测变量(observable variable)；\(\theta\) 表示参数。并且通常若 z 可观测，那么将很容易求解最大似然。EM 算法是一种迭代式的方法，其 基本思想 是：若参数 \(\theta\) 已知，则可根据训练数据推断出最优隐变量 z的值（E 步）；反之，若 z 的值已知，则可方便的对参数 \(\theta\) 做极大似然估计（M 步）。

求最大似然函数一般是选择参数使数据的概率最大，EM 算法中，只观察到 x ，所以只求 x 的概率。EM 算法使用对数极大似然估计来求解来求解参数 \(\theta\) ，同时利用联合分布(x,z)来计算边缘分布(x)。通过对 z 计算期望，来最大化已观测数据的对数边缘似然 (marginal likelihood)。

\begin{align} \ell (\theta) & = ln \mathcal{P}(x; \theta) \\ & = ln \sum_z \mathcal{P}(x,z; \theta) \\ & = ln \left( \sum_z \mathcal{P} (x|z;\theta) \mathcal{P}(z;\theta) \right) \end{align}

直接求取 \(\ell (\theta)\) 会比较困难，所以使用如下策略：

不断的构建 \(\ell\) 的一个下界(E-step)；
然后求取下界的最大值(M-step)

EM 算法原型：以初始值 \(\theta^{0}\) 为起点，对上式迭代执行以下步骤直至收敛，

基于 \(\theta^{t}\) 推断隐变量 z 的期望，记为 z^t;
基于已观测变量 x 和 z^t 对参数 \(\theta\) 做极大似然估计，记为 \(\theta^{t+1}\);

进一步，若不是求取 z 的期望，而是基于 \(\theta^{t}\) 计算隐变量 z 的概率分布 \(\mathcal{P}(z|x;\theta^{t})\) ，从而得到 Q 函数。

EM 算法的核心是 Q 函数(Q function)：完全数据的对数似然函数 \(ln \mathcal{P} (x,z; \theta) \) 关于在给定观测数据 x 和当前参数 \(\theta^{t}\) 下对未观察数据 z 的条件概率分布 \(\mathcal{P}(z|x;\theta)\) 的期望

\begin{align} Q(\theta,\theta^{t}) & = E_{z|x;\theta^{t}} [ ln \mathcal{P}(x,z;\theta) ] \\ & = E_z [ \left( ln \mathcal{P}(x,z;\theta) \right) | x; \theta^{t} ] \\ & = \sum_z \left( ln \mathcal{P} (x,z;\theta) \right) \mathcal{P}(z|x;\theta^{t}) \end{align}

\(Q(\theta, \theta^{t})\) 的第一个变元表示要极大化的参数，第二个变元表示参数的当前估计值。 \(\mathcal{P}(z|x;\theta^{t})\)是在给定观测数据 x 和当前估计参数 \(\theta^{t}\) 下隐变量 z 的条件概率分布。

EM 算法 输入：观测数据 x ，隐变量 z ，联合分布 \(\mathcal{P} (x,z;\theta)\) ，条件分布 \(\mathcal{P} (z|x;\theta)\) ；输出：模型参数 \(\theta\)

选择参数的初值 \(\theta^{0}\) ，开始迭代；
E-step：记 \(\theta^{t}\) 为第 t 次迭代参数 \(\theta\) 的估计值，在第 t+1 次迭代的 E 步，计算 Q 函数 \(Q(\theta, \theta^{t})\) \[ Q(\theta,\theta^{t}) = \sum_z \left( ln \mathcal{P} (x,z;\theta) \right) \mathcal{P}(z|x;\theta^{t})\] 需要先求解 \(\mathcal{P}(z|x;\theta^{t})\)
M-step：求使 \(Q(\theta, \theta^{t})\) 极大化的 \(\theta\) ，确定第 t+1 次迭代的参数估计值 \(\theta^{t+1}\) \[ \theta^{t+1} = arg \max_{\theta} Q(\theta, \theta^{t}) \]
重复 E-step 和 M-step ，直到收敛。一般是用较小的正数 \(\epsilon_1,\epsilon_2\)，若满足 \(||\theta^{t+1}|| < \epsilon_1 \ or \ ||Q(\theta, \theta^{t+1}) - Q(\theta, \theta^{t})|| < \epsilon_2 \) 则停止迭代。

EM 算法说明：EM 算法对初值是敏感的；每次迭代实际在求 Q 函数并极大化，每次迭代都是似然函数增大或达到局部极值；

EM 算法可看做一种非梯度的优化方法，可以看成是坐标上升法：E-step 在最大化； M-step 在 \(\theta\) 方向最大化

EM 收敛性

EM 算法最大的优点是简单性和普适性。
三硬币模型

假设有 3 枚硬币，分别记做 A、B、C ，三枚硬币正面出现的概率分别是 \(p_a, p_b, p_c \) 。进行如下掷硬币试验：先掷硬币 A，根据其结果选择下一次需要掷的硬币，正面选硬币 B，反面选硬币 C；然后掷选出的硬币，出现正面记作 1，反面记作 0；独立地重复 n 次，观察结果为 1,1,0,1,0,0,1,1,0,1,1,1,0 ，假设只能观察到最终掷硬币的结果，不能观测掷硬币的过程。如何估计三枚硬币正面出现的概率，即三硬币模型的参数？

李航 P155
EM 算法的推广

李航 P166

1.1.10 Bayesian Decision Theory

贝叶斯决策论是概率框架下实施决策的基本方法：分类任务在所有相关概率都已知的理想情形下，如何基于这些概率和误判损失来选择最优的类别标记。

已知后验概率以及误分误差就可以求得期望损失（但实际中后验概率很难求得）。

假设有 K 种类别标记 \(\mathcal{Y} = \{ c_1,c_2,\cdots,c_K \} \)，\(\lambda_{ij}\) 表示将一个真实标记为 \(c_j\) 的样本误分类为 \(c_i\) 所产生的损失。利用后验概率 \(P(c_i | x)\) 和 \(\lambda_{ij}\) 可得样本 x 分类为 \(c_i\) 所产生的期望损失 (expected loss)（样本 x 的条件风险(conditional risk)） \(\varepsilon(c_i | x) = \sum_{j=1}^{K} \lambda_{ij} P(c_j | x) \) 。我们的任务是寻找一个判定准则以最小化总体风险 \(\varepsilon(h) = E_x [\varepsilon(h(x) | x)] \) 。贝叶斯判定准则 (Bayes decision rule)：为最小化总体风险，只需要在每个样本上选择那个能使条件风险 \(\varepsilon(c|x)\) 最小的类别标记，即 \(h^*(x) = arg \min_{c \in \mathcal{Y}} \varepsilon(c | x) \) ，此时 \(h^*\) 称为 贝叶斯最优分类器 (Bayes optimal classifier)，与之相对应的总体风险 \(\varepsilon(h^*)\) 称为贝叶斯风险(Bayes risk)，\(1 - \varepsilon(h^*)\) 反应了贝叶斯分类器所能达到的最好性能，即通过机器学习所能产生的模型精度的理论上限。

贝叶斯定理：

\begin{equation} P(c|x) = \frac{P(c) P(x|c)}{P(x)} \label{bayes:bayes} \end{equation}

1.1.11 Naive Bayes

利用贝叶斯公式 \(\eqref{bayes:bayes}\)来估计后验概率 \(P(c|x)\) 的主要困难在于类条件概率 \(P(x|c)\) 是所有属性上的联合概率，难以从有限的训练样本直接估计而得。朴素贝叶斯假设属性条件独立(attribute conditional independent assumption)：对已知类别，所有属性相互独立，也就是每个属性独立的对分类结果发生影响。这是一个较强的假设，模型包含条件概率的数量大大减少，使得学习和预测大为简化。基于该假设，贝叶斯公式可以重写为（d 为属性的数目，\(x_i\)是 x 的第 i 个属性上的取值。

\begin{equation} P(c|x) = \frac{P(c)P(x|c)}{P(x)} = \frac{P(c)P(x_1,x_2,\cdots,x_d|c)}{P(x)} = \frac{P(c) \prod_{i=1}^d P(x_i|c)}{P(x)} \end{equation}

由于对所有类别来说 P(x) 相同，根据贝叶斯判定准则可得朴素贝叶斯分类器的表达式为

\begin{equation} h^*(x) = arg \max_{c \in \mathcal{Y}} P(c) \prod_{i=1}^d P(x_i|c) \end{equation}

朴素贝叶斯将实例分到后验概率最大的类别中，等价于期望风险最小化。朴素贝叶斯法高效，且易于实现；但分类的性能不一定很高。

参数估计

朴素贝叶斯需要学习先验概率 \(P(Y=c_k)\) 和条件概率 \(P(X_i = x_i | Y=c_k)\) ，使用极大似然估计法来估计相应的概率。计算先验时，需要逐一计算每一种类别的先验概率；计算条件概率时需要分别计算每一种类别下，每一个属性的条件概率。
\begin{align} P(Y=c_k) & = \frac{\sum_{i=1}^m \mathit{1}(y^{(i)} = c_k)}{m}, \quad k=1,2,\cdots,K \\ P(X_i = v_{il} | Y = c_k) & = \frac{\sum_{j=1}^m \mathit{1} (x_i^{(j)} = v_{il},y^{(j)}=c_k)}{\sum_{j=1}^{m} \mathit{1} (y^{(j)}=c_k)}, \\ & i=1,2,\cdots,d; l=1,2,\cdots,S_i; k=1,2,\cdots,K \notag \\ P(X_i | Y = c_k) & = \text{use distribution function when x is continuous} \end{align}
一般朴素贝叶斯用于特征是离散的样本，记得 Andrew NG 还说过要计算连续的随机变量还要将其分段来离散化。但是周志华的书上写计算连续随机变量的时候考虑其第 i 个属性的概率密度函数。具体待思考 TODO，其实朴素贝叶斯就是假设属性条件独立，跟变量是连续还是离散的好像没有关系。
Laplacian Correction

为避免属性携带的信息被训练集中未出现的属性值抹去，在估计概率值时通常要进行平滑(smoothing)，常用方法为拉普拉斯修正。拉普拉斯修正实质上假设 属性值与类别均匀分布 ，这是在朴素贝叶斯学习过程中额外引入的关于数据的先验(prior)。避免了因训练样本不充分而导致概率估值为 0 的问题，同时修正过程所引入的先验的影响随着训练集变大而逐渐变得可忽略，使得估值渐趋向于实际概率值。
\begin{align} P(Y=c_k) & = \frac{\sum_{i=1}^m \mathit{1}(y^{(i)} = c_k) + 1}{m + K} \\ P(X_i = v_{il} | Y = c_k) & = \frac{\sum_{j=1}^m \mathit{1} (x_i^{(j)} = v_{il},y^{(j)}=c_k) + 1}{\sum_{j=1}^{m} \mathit{1} (y^{(j)}=c_k) + S_i} \end{align}
Semi-naive Bayes Classifiers

半朴素贝叶斯的基本想法是适当考虑一部分属性间的相互依赖信息，从而即不需要进行完全联合概率计算，又不至于忽略比较强的属性依赖关系。

1.1.12 K-Nearest Nerghbor

k 近邻 (k-NN) 是一种基本的分类与回归方法。该算法简单直观：给定一个训练数据集，对新输入的实例，在训练集中找到与该实例最近邻的 k 个实例（k 一般选择为奇数），这 k 个实例中的多数属于某个类，就把该新输入的实例分到该类。k-NN 算法三个基本要素： k 的选择、距离度量、分类规则。

k 近邻分类算法：

输入：训练数据集 \(T=\{(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),\cdots,(x^{(m)},y^{(m)})\}\) ，且 \(x^{(i)} \in \mathbb{R}^n, \ y^{(i)} \in \{c_1,c_2,\cdots,c_k\}, \ i=1,2,\cdots,m \) 。以及实例 x 的特征
输出：实例 x 所属类别 y
求解：
1. 逐个计算 x 与训练集中每个样本点的距离；
2. 根据分类决策规则（如多数表决）决定 x 的类别 \(y = arg \max_{c_j} \sum (\mathit{1}(y^{(i)}=c_j))\)

k 值的选择会对 k-NN 算法的结果产生重大的影响。通常采用交叉验证来选择 k 值

k 值的减小意味着整体模型变得复杂，容易发生过拟合。预测的结果会对近邻的实例点非常敏感，若近邻的实例点是噪声，结果很可能出错
k 值的增大意味着整体模型变得简单。与预测实例较远的样本也将对预测起作用，使预测可能发生错误。

距离度量：

\begin{align*} L_p(x^{(i)},x^{(i)}) &= \left( \sum_{l=1}^n |x_l^{(i)} - x_l^{(i)}|^p \right)^{1/p} \quad L_p \ distance \\ L_1(x^{(i)},x^{(i)}) &= \sum_{l=1}^n |x_l^{(i)} - x_l^{(i)}| \quad \text{Manhattan distance} \\ L_2(x^{(i)},x^{(i)}) &= \left( \sum_{l=1}^n |x_l^{(i)} - x_l^{(i)}|^2 \right)^{1/2} \quad \text{Euclidean distance} \\ L_{\infty}(x^{(i)},x^{(i)}) &= \max_l |x_l^{(i)} - x_l^{(i)}| \quad \text{各个坐标轴距离的最大值} \end{align*}

k 近邻搜索：实现 k 近邻时，主要考虑的问题是如何对训练数据进行快速 k 近邻搜索。常用方法为 kd 树 (kd-tree)。kd 树树存储 k 维空间数据的树结构。

1.1.13 Decision Tree

决策树是一种基本的分类与回归方法。决策树模型成树形结构；可以认为是 if-then 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。

主要优点：模型具有可读性、分类速度快

决策树学习通常包括 3 个步骤：特征选择、决策树的生成、决策树的修剪

学习时：利用训练数据，根据损失函数最小化的原则建立决策树模型
预测时：用决策树模型对新样本进行分类

1.2 Unsupervised Learning

无监督学习

1.2.1 Mixture of Gaussian

仅有训练样本 \(x^{(1)},\cdots,x^{(m)}\)，但没有相应的类别标签。类别标签作为隐变量，且认为 \( z^{(i)} \sim Multinomial(\phi)\) 其中 \(p(z^{(i)} = j) = \phi_j, \text{ and } \sum_{i=1}^k \phi_j = 1\) ；同时 \( (x^{(i)} | z^{(i)} =j) \sim \mathcal{N}(\mu_j,\sum_j)\) 。混合高斯模型为 \(x^{(i)}\) 从 \(z^{(i)}\) 的 \(\{1,\cdots,k\}\) 的值中随机选择一个类别，然后在该类别的高斯分布中采样得到。不同的类别，其协方差不同。

\begin{align*} \ell (\phi,\mu,\sum) & = \sum_{i=1}^m ln p(x^{(i)};\phi,\mu,\sum) \\ & = \sum_{i=1}^m ln \sum_{z^{(i)}=1}^k p(x^{(i)}|z^{(i)};\mu,\sum) p(z^{(i)};\phi) \end{align*}

使用 EM 算法求解，在 E-step ，尝试猜测 \(z^{(i)}\) 的值；在 M-step ，基于 E-step 的猜测更新模型的参数，由于认为在 E-step 的猜测是正确的使得最大化似然变得容易。

1.2.2 Factor Analysis

当特征的维数远远大于样本的个数时，使用混合高斯将变得困难（协方差矩阵不可逆）。

改进 1 ：将协方差限制为对角矩阵，此时协方差被限制为轴平行于坐标轴的椭圆，会丢失不同维度之间的相关性
改进 2 ：将协方差限制为单位阵乘以某个常数，此时协方差被限制称圆。

\begin{align*} z & \sim \mathcal{N}(0,I) \\ x|z & \sim \mathcal{N}(\mu + \Lambda z, \psi) \end{align*} \begin{align*} z & \sim \mathcal{N} (0, I) \\ \epsilon & \sim \mathcal{N} (0, \psi) \\ x & = \mu + \Lambda z + \epsilon \end{align*} \begin{align*} \ell (\mu, \Lambda, \psi) = ln \prod_{i=1}^m \frac{1}{(2\pi)^{n/2} |\Lambda \Lambda^T + \psi |} exp \left( -\frac{1}{2} (x^{(i)} - \mu)^T (\Lambda \Lambda^T + \psi)^{-1} (x^{(i)} - \mu) \right) \end{align*} \begin{align*} \mu_{z^{(i)} | x^{(i)}} & = \Lambda^T (\Lambda \Lambda^T + \psi)^{-1} (x^{(i)} - \mu) \\ \sum_{z^{(i)} | x^{(i)}} & = I - \Lambda^T (\Lambda \Lambda^T + \psi)^{-1} \Lambda \end{align*} \begin{align*} = \frac{1}{ (2\pi)^{k/2} | \sum_{z^{(i)} | x^{(i)} }|^{1/2} } exp \left( -\frac{1}{2} (z^{(i)} - \mu_{z^{(i)} | x^{(i)}})^T \sum_{z^{(i)} | x^{(i)}}^{-1} (z^{(i)} - \mu_{z^{(i)} | x^{(i)}}) \right) \end{align*}

1.2.3 k-means

k 均值算法用于将无标签样本分成 k 类。算法很简单，首先随机选择 k 个类的中心点，将所有样本分类到距离其最近的中心点，之后重新计算此次分类后的中心点，再次将样本重新分类，直到收敛（类别的中心点不再变化）。

\begin{gather*} \text{randomly initialize cluster centroids } \mu_1, \mu_2, \cdots, \mu_k \in {\mathbb{R}}^n \\ c^{(i)} := arg \min_j || x^{(i)} - \mu_j ||^2, \quad i = 1,2,\cdots,m \\ \mu_j := \frac{ \sum_{i=1}^m \mathit{1}\{c^{(i)} = j\} x^{(i)}}{\sum_{i=1}^m \mathit{1}\{c^{(i)} = j\}}, \quad j=1,2,\cdots,k \end{gather*}

收敛性

\begin{equation*} J(c,\mu) = \sum_{i=1}^m ||x^{(i)} - \mu_{c^{(i)}} ||^2 \end{equation*}

k-mean 是损失 J 上利用坐标下降法来最优化。算法在不断的固定 \(\mu\) ，利用 c 来最小化 J ；然后固定 J ，利用 \(\mu\) 来最小化 J 。所以 J 必定单调减小。但是 J 是非凸函数，所以无法保证算法收敛到全局最优解。但通常 k-means 算法都可以很好的工作。另外类别个数的选取具有主观性，可以多取几个值，并选取 \(J(c,\mu)\) 最小的那个。

1.2.4 Principal Components Analysis

求解
使用主成分分析 PCA 之前需要先将均值和方差做归一化处理，然后使用奇异值分解(single value decomposition, SVD)的方法来求解 top k 的特征向量。
1. 让 \(\mu = \frac{1}{m} \sum_{i=1}^m x^{(i)}\)
2. 使用 \(x^{(i)} - \mu\) 逐一替换 \(x^{(i)}\) ；这两步用于将均值变换成 0，若已知均值为 0 ，可跳过此步骤
3. 让 \(\sigma_j^2 = \frac{1}{m} \sum_i (x_j^{(i)})^2 \)
4. 使用 \(x_j^{(i)} / \sigma_j\) 逐一替换 \(x_j^{(i)}\) ；将协方差变为单位阵，方差归一化使得不同的属性拥有相同的尺度。若已知不同的属性拥有相同的尺度（如图像都是 [0,255] 的像素点），可跳过此步骤。
\begin{align*} X & = \left[ \begin{array}{ccc} -- & x^{(1)} & -- \\ -- & x^{(2)} & -- \\ & \vdots & \\ -- & x^{(m)} & -- \end{array} \right] \\ \sum & = \sum_{i=1}^m x^{(i)} {x^{(i)}}^T \\ & = X^T X \\ & = \left[ \begin{array}{cccc} | & | & & | \\ x^{(1)} & x^{(2)} & \cdots & x^{(m)} \\ | & | & & | \end{array} \right] \left[ \begin{array}{ccc} -- & x^{(1)} & -- \\ -- & x^{(2)} & -- \\ & \vdots & \\ -- & x^{(m)} & -- \end{array} \right] \end{align*}
SVD ：存在 \(m \geq n\) 和 \(m < n\) 两种情况。且不同的库在求解 SVD 分解时三者的维数会稍有不同（如有些库会省略掉全 0 的列）
\begin{gather*} X_{m \times n} = U_{m \times n} D_{n \times n} {V_{n \times n}}^T \\ D = \left[ \begin{array}{cccc} \sigma_1 & & & \\ & \sigma_2 & & \\ & & \ddots & \\ & & & \sigma_n \end{array} \right] \\ \sigma_i \text{ 是 X 的奇异值} \end{gather*}
U 的列是 \(X X^T\) 的特征向量； V 的列是 \(X^T X\) 的特征向量。因此 U 的 top K 列就是 \(\sum\) 的 top K 特征向量。

当维数较高时，使用 SVD 求解 PCA 很方便；而直接求取特征向量将变得很困难。如 \(x^{(i)} \in {\mathbb{R}}^{50000}\) 那么 \(\sum \in {\mathbb{R}}^{50000 \times 50000}\) 的维数就太高了。
推导

PCA 有 9-10 种不同的理解方法。投影应尽可能的分散，使得方差尽可能的大。因为直觉上协方差包含了样本的信息，我们希望样本投影后仍然保持这些协方差信息。使投影点到原点的距离最大（点到投影的距离的平方和最小也可以）可以让样本投影后协方差最大。选择单位投影向量 u ，来最大化投影点到原点的距离 \({x^{(i)}}^Tu\)
\begin{align*} \frac{1}{m} \sum_{i=1}^m ({x^{(i)}}^T u)^2 & = \frac{1}{m} \sum_{i=1}^m u^T x^{(i)} {x^{(i)}}^T u \\ & = u^T \left( \frac{1}{m} \sum_{i=1}^m x^{(i)} {x^{(i)}}^T \right) u \\ & = u^T \sum u, \quad \sum \text{ is the empirical convariance matrix of the data} \end{align*}
如果想要将数据投影到 k 维 (k < n) 子空间，应该选择 \(\sum\) 的 top k 特征向量来作为基 \(u_1,u_2,\cdots,u_k\) ，且这些基是正交的（\(\sum\) 是对称的）。用这组新的基来表示数据 \(x^{(i)} \in \mathbb{R}^n\)
\begin{align*} z^{(i)} = \left[ \begin{array}{c} u_1^T x^{(i)} \\ u_2^T x^{(i)} \\ \vdots \\ u_k^T x^{(i)} \end{array} \right] \in \mathbb{R} ^k \end{align*}
\(z^{(i)} \in \mathbb{R}^k\) 是 \(x^{(i)}\) 的 k 维（低维）近似表示
应用：
- 降低维数，简化计算
- 将高维数据降低到 3 维来可视化
- 存储高维数据
- 减少特征维数，降低过拟合的可能性（虽然大多数时候使用 PCA 后效果更好，但有点被滥用了；建议使用前评估一下）
- 降低人脸识别特征的维数，同时也使得相同的人脸之间的距离变得更近。对比两张人脸的相似程度时，并不直接计算两个特征的欧氏距离，而是计算两者在主特征子空间上的距离。 两个在原始空间非常远的特征在子空间可能很近。
- 当特征的不同属性并不独立时，需要去除冗余的属性参数。
- 删除数据中的噪声。x1、x2 强相关，怎样自动提取出本质特征 u1 ，而 u2 只是垂直方向上的一些噪声
- 应用到文本数据，从而剔除噪声，更好的比较文件之间的相似性。如单词 "study" 和 "learn" ，如果单纯计算余弦值，两者的相关系数为 0 ，但若将两者投影到特征向量上，两者的相关系数将变为正值，所有相似的文本将变得相关。此时使用的方法称为 latent semantic indexing (LSA) [其实就是 PCA，仅仅是换了一个名字而已]。此时将发差归一化将是一个 bad idea ，因为这将大幅增加不常出现的单词的权重。 \( \sin (x^{(i)},x^{(j)}) = \cos \theta = \frac{ {x^{(i)}}^T x^{(j)} }{||x^{(i)}|| ||x^{(j)}||} \)

1.2.5 Independent Components Analysis

独立成分分析(ICA)和主成分分析一样也是找到一组新的基来表示数据，但目的不同。ICA 用于找到样本中的相互独立的组件。ICA 要求源是非高斯的，否则无法求解。

推导

\(s^{(i)}\) 表示第 i 时刻 n 个独立的源组成的 n 维向量，\(x^{(i)}=As^{(i)}\) 为 i 时刻由 n 个采集系统得到的 n 维样本，矩阵 A 称为混合矩阵(mixing matrix) 是未知的，且用 \(W=A^{-1}\) 称为 unmixing matrix ，那么将有 \(s^{(i)}=Wx^{(i)}\) ；同时用 \(s_j^{(i)}\) 表示 i 时刻第 j 个独立源，\(W_j^T\) 表示 W 的第 i 行，从而有 \(s_j^{(i)}=w_j^T x^{(i)}\) 。
\begin{gather*} p(s)=\prod_{i=1}^n p_s (s_i) \\ p(x) = \prod_{i=1}^n p_s(w_i^T x) \cdot |W| \\ g(s) = 1/(1+e^{-s}) \quad \text{use sigmod function as CDF } \\ \ell (W) = \sum_{i=1}^m \left( \sum_{j=1}^n ln g'(w_j^T x^{(i)} + ln|W| \right) \\ W := W + \alpha \nabla_W \ell(W) \\ W := W + \alpha \left( \left[ \begin{array}{c} 1-2g(w_1^Tx^{(i)}) \\ 1-2g(w_2^Tx^{(i)}) \\ \vdots \\ 1-2g(w_n^Tx^{(i)}) \end{array} \right] {x^{(i)}}^T + (W^T)^{-1} \right) \end{gather*}
ICA 的关键是依赖数据是非高斯的，如果数据是高斯的，那么数据的旋转将产生歧义，即使有无穷多大的数据也无法恢复 A 或者 W 。

由于源的的概率密度函数未知，所以选择一个累积分布函数，并用该累计分布函数的导数作为源的概率密度函数。选择 CDF 的方法：选择一个从 0 到 1 的缓慢变化的函数，且非高斯。sigmod 是一个常用函数，且非高斯，所以较好的选择，并没有其他原因。其他相似的函数也可以，sigmod 只是一个常用的合理的选择。

向量 s 的概率密度函数是 \(p_s\) ，且 \(x=As\) ，A 可逆 \(W=A^{-1}\) ，那么 x 的概率密度函数为
\begin{equation*} p_x(x) = p_s(Wx) \cdot |W| \end{equation*}
ICA ambiguities

ICA 无法得到源的正负号、源的尺度信息、源的顺序。

ICA 源无法为高斯的原因：无论是 x 还是 x' 的分布都是相同的，从而无法区分混合矩阵是 A 还是 A' ；两者的区别是乘以一个 R 矩阵，而高斯分布是旋转对称的。
\begin{gather*} s \sim \mathcal{N}(0,I) \\ x = As \\ E[xx^T] = E[As(As)^T] = E[Ass^TA^T] = AA^T \\ x \sim \mathcal{N}(0,I) \\ RR^T = R^TR = I \quad \text{R is an arbitrary orthogonal matrix} \\ A'=AR \\ x'=A's \\ E[x'(x')^T] = E[A'ss^T(A')^T] = E[ARss^T(AR)^T] = ARR^TA^T = AA^T \\ x' \sim \mathcal{N}(0,I) \end{gather*}
应用：
- 麦克风阵列将多个不同的声源区分开来
- 使用电极采集头皮上电压的变化，每个电极采集到的都是所有信号（心跳、眨眼等）的叠加，使用 ICA 去除掉心跳和眨眼的信号，得到一个更清晰的脑电图
- 在自然图像上运行 ICA ，得到独立组件（自然图像是一些独立组件的线性组合）

1.3 Semi-supervised Learning

半监督学习

1.4 Reinforcement Learning

强化学习

1.5 Computational Learning Theory

计算学习理论用于真正理解机器学习算法，了解怎样修改算法；区分开真正了解算法与只看了书和公式的人，真正成为一个好的木匠。

思考：

学习器(机器的或非机器的)应遵循什么样的规则？
是否可能独立于学习算法确定学习问题中固有的难度？
能否知道为保证成功的学习有多少训练是必要的或充足的？
能否刻画出一类学习问题中固有的计算复杂度？

对所有这些问题的一般回答还未知。这里着重讨论只给定目标函数的训练样例和候选假设空间的条件下,对该未知的目标函数的归纳学习问题。

该理论致力于回答如下的问题:

在什么样的条件下成功的学习是可能的？
在什么条件下一特定的学习算法可保证成功运行？
我们真正关心的是泛化误差，却为什么始终在努力减小经验误差？
bias / variance 的准确定义
需要多少训练样例才足以成功地学习到目标函数，定量的上下界
学习器在达到目标前会有多少次出错，定量的上下界

为了解决这些问题，需要许多特殊的条件假设：

怎样定义学习得到的结果是成功的？是必须找到目标概念？还是以较大的概率得到目标概念的近似？
学习器如何得到训练样本？学习器自己由实验获取？还是按照某过程随机的生成而不受学习器的控制？

learning theory split to two central questions:

can we make sure that Eout(g) is close enough to Ein(g) ?
can we make Ein(g) small enough ?

1.5.1 Probably Approximately Correct

概率近似正确，简称 PAC：通常我们无法精确的学到目标概念（concept）。原因如下：

由于训练集 D 往往只包含有限数量的样本，因此，通常会存在一些在 D 上的“等效”的假设，学习算法无法区分。即存在多个假设都满足样本空间到标记空间的映射
从分布\(\mathcal{D}\)上采样得到 D 的过程有一定的偶然性。存在一定的概率使得样本都有某种特性，但该特性在总体中不存在；从而对同样大小的不同训练集，学的的结果也可能有所不同

因此我们希望以比较大的把握学的比较好的模型；即以 较大的概率 学的 误差满足预设上限 的模型。也就成为了“概率”“近似正确” 框架。

假设输入空间\(\mathcal{X}\)中所有样本服从一个 隐含未知 的分布\(\mathcal{D}\)，训练集 D 中所有样本都是独立地从这个分布上采样而得（独立同分布：independent and identically distribution，简称 i.i.d)。通常假设训练集和测试集服从相同的分布（在深度学习中，通常无法保证训练集和测试集分布形同）；训练集的样本独立同分布。

训练样本集 D 中所有从隐含未知分布 \(\mathcal{D}\) 上独立采样得到，h 是一个从输入空间 \(\mathcal{X}\) 到标记空间 \(\mathcal{Y}\) 的一个映射，h 在 D 上的经验误差（也就是训练误差）为\[ \hat{\varepsilon}(h;D) = \frac{1}{m} \sum_{i=1}^{m} \mathit{1}(h(x^{(i)} \ne y^{(i)}) \]泛化误差为\[ \varepsilon(h;\mathcal{D}) = P_{x \sim \mathcal{D}} (h(x) \ne y) \]由于 D 是\(\mathcal{D}\) 的独立同分布采样，因此 h 的经验误差的期望等于其泛化误差。 即\[ E[ \hat{\varepsilon}(h;D) ] = \varepsilon(h; \mathcal{D}) \]

note：均值是观察样本的平均值，尽管随机变量一样，但观察到的样本不同，均值很可能不同；期望是一个数学特征，针对于一个随机变量。根据大数定律（随机变量序列的前一些项的算术平均值，在某种条件下，收敛到这些项的均值的算术平均值），期望是均值随着样本趋于无穷时的极限。频率的稳定性是概率定义的客观基础。

PAC 可学习(PAC Learnable)：只要从分布\(\mathcal{D}\)中独立同分布采样得到的样例数目 m ，满足\(m \geq poly(\frac{1}{\epsilon},\frac{1}{\delta},size(x),size(c))\)，学习算法能从假设空间\(\mathcal{H}\)中 PAC 辨识概念类 \(\mathcal{C}\)，则称概念类\(\mathcal{C}\)对假设空间\(\mathcal{H}\)而言是 PAC 可学习的，有时也简称概念类\(\mathcal{C}\) 是 PAC 可学习的。若算法运行的时间也是多项式函数\(poly(\frac{1}{\epsilon},\frac{1}{\delta},size(x),size(c))\)，则称概念类 \(\mathcal{C}\)是高效 PAC 可学习的(efficiently PAC learnable)，称算法 L 是概念类\(\mathcal{C}\)的 PAC 学习算法。

仅仅要求了训练样本的个数和时间满足一个多项式函数。

假定学习算法处理每个样本的时间为常数，则算法的时间复杂度等价于样本复杂度。于是我们对算法时间复杂度的关心就转化成对样本复杂度的关心。满足 PAC 学习算法 L 所需的\(m \geq poly(\frac{1}{\epsilon},\frac{1}{\delta},size(x),size(c))\)中最小的 m ，称为学习算法 L 的 样本复杂度。

不可知 PAC 可学习(agnostic PAC learnable)：

当 \(c \not \in \mathcal{H}\) 时，学习算法无法得到目标概念 c 的 \(\epsilon\) 近似。但是在假设空间 \(\mathcal{H}\) 中必存在一个泛化误差最小的假设，找到此假设的 \(\epsilon\) 近似也不失为一个较好的目标。这是不可知学习。

PAC 学习给出了一个抽象地刻画机器学习能力的框架，基于这个框架能对很多重要的问题进行理论探讨：

研究某任务在什么样的条件下可学得较好的模型？
某算法在什么样的条件下可进行有效的学习？
需多少训练样例才能获得较好的模型？

PAC 学习中一个关键因素是假设空间\(\mathcal{H}\)的复杂度；\(\mathcal{H}\)包含了学习算法 L 的所有可能输出，一般而言， \(\mathcal{H}\)越大，其包含任意目标概念的可能性越大，但从中找到某个具体目标概念的难度也越大。\(|\mathcal{H}|\)有限时，我们称\(\mathcal{H}\)为有限假设空间，否则称为无限假设空间。

1.5.2 有限假设空间

可分情形

目标概念 c 属于假设空间 \(\mathcal{H}\) 就是可分情形。

有限假设空间 \(\mathcal{H}\) 都是 PAC 可学习的。
不可分情形

目标概念 c 不属于假设空间 \(\mathcal{H}\) 就是不可分情形。假定对于任何 \(h \in \mathcal{H}, \ \hat{\varepsilon}(h) \ne 0\) 即 \(\mathcal{H}\) 中任何一个假设都会在训练集上出现或多或少的错误。根据霍夫丁不等式可得： 当样例数目 m 较大时，h的经验误差是其泛化误差很好的近似 。

1.5.3 Vapnik-Chervonenkis Dimension

VC维用于刻画假设空间的复杂度。VC 维的定于与数据分布 \(\mathcal{D}\) 无关（在数据分布未知时，仍能计算出假设空间的VC维）

给定假设空间 \(\mathcal{H}\) 和示例集 \(D=\{x^{(1)},x^{(2)},\cdots,x^{(m)}\}, \mathcal{H} \)中每个假设 h 都能对 D 中示例赋予标记，标记结果可表示为 \(h|_D = \{(h(x^{(1)}),h(x^{(2)}),\dots,h(x^{(m)})) \}\) 随着 m 的增大，\(\mathcal{H}\) 中所有假设对 D 中的示例所能赋予标记的可能结果数也会增大（可能这就是其称为增长函数的原因）。另外对于相同的 m 不同的假设空间所能赋予的可能结果数也不相同。

Growth Function，增长函数：描述了假设空间 \(\mathcal{H}\) 的表示能力。具体定义为：增长函数 \(\prod_{\mathcal{H}} (m)\)表示假设空间 \(\mathcal{H}\) 对 m 个示例所能赋予标记的 最大可能结果数 。\(\mathcal{H}\) 对示例所能赋予标记的可能结果数越大，\(\mathcal{H}\) 的表示能力越强，对学习任务的适应能力越强；反应了假设空间的复杂度。

Dichotomy，对分：对二分类问题来说，\(\mathcal{H}\) 中的假设对 D 中示例赋予标记的 每种可能结果 称为对 D 的一种对分；每个假设会把示例集分为两类，因此称为对分。

Shattering，打散：若假设空间 \(\mathcal{H}\) 能实现对示例集 D 的 所有对分 ，即 \(\prod_{\mathcal{H}} = 2^m\) ，则称示例集D 能被假设空间 \(\mathcal{H}\) 打散。

现实学习任务所面临的通常是无限假设空间。假设空间无限和 VC 维有限的关系？？

假设空间 \(\mathcal{H}\) 的 VC 维是能被 \(\mathcal{H}\) 打散的 最大示例集 的大小， 即

\begin{equation} VC(\mathcal{H}) = \max\{ m: \prod_{\mathcal{H}} (m) = 2^m \} \end{equation}

通常计算 VC 维的方法：若存在大小为 d 的示例集能被 \(\mathcal{H}\) 打散，但不存在任何一个大小为 d + 1 的示例集能被 \(\mathcal{H}\) 打散，则 \(\mathcal{H}\) 的 VC 维是 d。

增长函数的上界（增长函数与 VC 维的关系）若假设空间 \(\mathcal{H}\) 的 VC 维为 d，

\begin{align} & \prod_{\mathcal{H}} \leq \sum_{i=0}^{d} \left( \array {m \\ i} \right), \quad m \in \mathbb{N}, Sauer 引理 \\ & \prod_{\mathcal{H}} \leq \left( \frac{e \cdot m}{d} \right) ^d, \quad m > d, 推论 \end{align}

增长函数可用于估计经验误差与泛化误差之间的关系：对假设空间 \(\mathcal{H}, m \in \mathbb{N}, 0 < \epsilon < 1, 任意 \in \mathcal{H}\) 有

\begin{equation} P \left( \left| \varepsilon(h) - \hat{\varepsilon}(h) \right| > \epsilon \right) \leq 4\prod_{\mathcal{H}} (2m) exp(- \frac{m\epsilon^2}{8}) \end{equation}

泛化误差界：只与样本个数 m 有关；基于 VC 维的泛化误差界是分布无关(distribution-free)、数据独立(data-independent)的。 定理： 若假设空间 \(\mathcal{H}\) 的 VC 维为 d，则对任意 \(m > d, \ 0 < \delta < 1, h \in \mathcal{H}\) 有

\begin{equation} P \left( \left| \varepsilon(h) - \hat{\varepsilon}(h) \right| \leq \sqrt{\frac{8dln\frac{2em}{d} + 8ln\frac{4}{\delta}}{m}} \right) \geq 1 - \delta \end{equation}

也就是说使用假设类 \(\mathcal{H}\) ，训练样本个数要是 \(VC(\mathcal{H})\) 的线性同阶函数才能够确保能够学的一个较好的假设。一般来说，对大多数假设类，其VC维数大约是其参数个数的线性阶。结合这两者，大致可以得到， 训练样本的个数一般要求为参数个数的线性同阶 。理论针对的是独立同分布的随机变量，对于最坏的情况仍然是符合的；实际选取的样本，通常会比较好，并不需要那么多样本来训练。

定理：任何 VC 维有限的假设空间 \(\mathcal{H}\) 都是（不可知） PAC 可学习的。 满足经验风险最小化(Empirical Risk Minimization, ERM)原则。

为什么 SVM 不会过拟合

核函数只是将特征映射到了无穷维，但具有较大间隔的线性分类器 VC 维都比较低。VC 维的上界并不依赖特征 X 的维数，SVM 会自动找到一个 VC 维低的假设类，而不会过拟合。\(\mathcal{H}\) 只包含较大间隔的线性分类器，间隔最小为 r，假设 \(||x^{(i)}||_2 \leq R, then VC(\mathcal{H}) \leq \lceil \frac{R^{2}}{4r^{2}} \rceil + 1 \)

1.5.4 Rademacher Complexity

Rademacher 复杂度是另一种刻画假设空间复杂度的途径，但在一定程度上考虑了数据分布。

基于 VC 维的泛化误差界是分布无关、数据独立的；也就是对任何数据分布都成立，使得基于 VC 维的学习结果具有一定的普适性。但由于没有考虑数据自身，基于 VC 维得到的泛化误差界通常比较松（如果考虑数据的分布可能会得到更加确切的泛化误差界），对那些与学习问题的典型情况相差甚远的较坏的分布来说尤其如此？？？？？？？TODO

给定训练集 \(D=\{(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),\cdots,(x^{(m)},y^{(m)})\}, y^{(i)} = \pm 1\) ，假设 h 的经验误差为

\begin{align} \hat{\varepsilon}(h) & = \frac{1}{m} \sum_{i=1}^{m} \mathit{1} (h(x^{(i)}) \ne y^{(i)}) \notag \\ & = \frac{1}{m} \sum_{i=1}^{m} \frac{1-y^{(i)}h(x^{(i)}}{2} \notag \\ & = \frac{1}{2} - \frac{1}{2m} \sum_{i=1}^{m} y^{(i)} h(x^{(i)}) \end{align}

其中 \(\frac{1}{m} \sum_{i=1}^m y^{(i)}h(x^{(i)})\) 体现了预测值 \(h(x^{(i)}\) 与样例真实标记 \(y^{(i)}\) 之间的一致性（值越大，表明两者越一致，经验误差越小；若训练样本没有错分的情况则取最大值 1）。也就是说经验误差最小的假设是

\begin{equation} arg \max_{h \in \mathcal{H}} \frac{1}{m} \sum_{i=1}^m y^{(i)}h(x^{(i)}) \end{equation}

然而现实任务中样例的标记有时会收到噪声的影响，即由于收到某些随机因素的影响，样例的标记不再是真实的标记。此时选择假设空间在训练接（？？？）上表现最好的假设，有时还不如选择事先考虑了随机噪声的假设。

Rademacher 随机变量：以 0.5 的概率取 -1，0.5 的概率取 +1 的随机变量 \(\sigma_i\) 称为 Rademacher 随机变量。

基于 Rademacher 随机变量的经验误差最小假设： \[ sup_{h \in \mathcal{H}} \frac{1}{m} \sum_{i=1}^{m} \sigma_i h(x_i) \] 由于 \(\mathcal{H}\) 是无限假设空间，有可能取不到最大值，因此使用上确界代替最大值。考虑 \(\mathcal{H}\) 中所有假设，对上式求期望可得（严重不明白取期望的原因，已经是在所有假设中取经验误差最小的那个假设了，为什么还要取期望？？？）\[ E_{\sigma} \left[ sup_{h \in \mathcal{H}} \frac{1}{m} \sum_{i=1}^{m} \sigma_i h(x_i) \right] \] 该式体现了假设空间 \(\mathcal{H}\) 的表达能力。当假设空间中只有一个假设时，该式的值为 0；当有 2^m 个假设时且 \(\mathcal{H}\) 能打散 D 时，该式的值为 1。

令 \(Z = \{z^{(1)}, z^{(2)}, \cdots, z^{(m)}\}, z^{(i)} \in \mathcal{Z}; \quad \mathcal{F}:\mathcal{Z} \to \mathbb{R}\) 其中 \(\mathcal{Z}\) 和 \(\mathbb{R}\) 都是实数域，\(\mathcal{F}\) 是从 \(\mathcal{Z}\) 到 \(\mathbb{R}\) 的映射簇。则函数空间 \(\mathcal{F}\) 关于 Z 的经验 Rademacher 复杂度和关于 \(\mathcal{Z}\) 上分布 \(\mathcal{D}\) 的 Rademacher 复杂度分别为下面两个式子

\begin{align} \hat{\varepsilon}_Z (\mathcal{F}) & = E_\sigma \left[ sup_{f \in \mathcal{F}} \frac{1}{m} \sum_{i=1}^m \sigma_i f(z^{(i)}) \right] \\ \varepsilon_m (\mathcal{F}) & = E_{Z \in \mathcal{Z}:|Z|=m} \left[ \hat{\varepsilon}_Z (\mathcal{F}) \right] \end{align}

经验 Rademacher 复杂度衡量了函数空间 \(\mathcal{F}\) 与随机噪声在集合 Z 中的相关性；下式表明函数空间 \(\mathcal{F}\) 在 \(mathcal{Z}\) 上关于分布 \(\mathcal{F}\) 的相关性。

基于 Rademacher 复杂度可得关于函数空间 \(\mathcal{F}\) 的泛化误差界。

1.5.5 稳定性

算法的稳定性研究的是算法在输入发生变化时，输出是否会随之发生较大的变化。

无论是基于 VC 维还是 Rademacher 复杂度来推导泛化误差界，所得到的结果均与具体学习算法无关，适用于所有学习算法。稳定性分析不必考虑假设空间中所有可能的假设，只需要根据算法自身的特性来讨论输出假设的泛化误差界。

学习算法 L 关于损失函数 \(\ell\) 满足 \(\beta -\) 均匀稳定性。

基于学习算法的均匀稳定性可以得到学习算法学得假设的泛化误差界。

若学习算法L是ERM且稳定的，则假设空间 \(\mathcal{H}\) 可学习。

稳定性与假设空间并无关系，但两者通过算是函数 \(\ell\) 联系起来。

1.5.6 不等式定理

The union bound ：\(A_1,A_2,\cdots,A_k\)是 k 个不同的事件，可能并不独立，那么

\begin{equation} P(A_1 \cup A_2 \cup \cdots \cup A_k) \leq P(A_1) + P(A_2) + \cdots + P(A_k) \end{equation}

Jensen inequality：对任意的凸函数 f(x) ，有

\begin{equation} f(E[x]) \leq E[f(x)] \end{equation}

Hoeffding inequality，霍夫丁不等式：若\(x_1,x_2,\cdots,x_m\)为 m 个独立随机变量，且满足 \(0 \leq x_i \leq 1\)，则对任意 \(\epsilon > 0\)，有

\begin{align} & P \left( \frac{1}{m} \sum_{i=1}^{m} x_i - \frac{1}{m} \sum_{i=1}^{m} E(x_i) \geq \epsilon \right) \leq exp(-2m \epsilon^2) \\ & P \left( \left| \frac{1}{m} \sum_{i=1}^{m} x_i - \frac{1}{m} \sum_{i=1}^{m} E(x_i) \right| \geq \epsilon \right) \leq 2exp(-2m \epsilon^2) \end{align}

McDiarmid inequality：若\(x_1,x_2,\cdots,x_m\)为 m 个独立随机变量，且对任意 \(1 \leq i \leq m\)，函数 f 满足 \[ sup_{x_1,\cdots,x_m,x_i^,} | f(x_1,\cdots,x_m) - f(x_1,\cdots,x_{i-1},x_i^,,x_{i+1},\cdots,x_m) | \leq c_i \] 则对任意 \(\epsilon > 0\)，有

\begin{align} & P(f(x_1,\cdots,x_m) - E[f(x_1,\cdots,x_m)] \geq \epsilon ) \leq exp(\frac{-2\epsilon^2}{\sum_i c_i^2}) \\ & P( | f(x_1,\cdots,x_m) - E[f(x_1,\cdots,x_m)] | \geq \epsilon ) \leq 2exp(\frac{-2\epsilon^2}{\sum_i c_i^2}) \end{align}

1.5.7 术语

concept 概念：表示从样本空间\(\mathcal{X}\)到标记空间\(\mathcal{Y}\)的映射，用符号 c 表示。不要疑惑为什么叫做概念，在机器学习中，这个映射就被称为概念。

目标概念 ：若对任何样例\((x,y)\)都有\(c(x)=y\)成立，则称 c 为目标概念。

concept class 概念类：我们希望学的的目标概念构成的集合称为概念类，用符号\(\mathcal{C}\)表示。no see 概念类到底是个什么东西？？？？

hypothesis space 假设空间：对给定的学习算法 L ，她所考虑的所有可能概念的集合称为假设空间，用符号\(\mathcal{H}\)表示。学习算法吧自认为可能的目标概念一起构成\(\mathcal{H}\)，学习算法并不可能知道概念类的真实值，因此\(\mathcal{C}\)和 \(\mathcal{H}\)通常是不同的。假设空间中任何一个假设\(h \in \mathcal{H}\)也都是从样本空间\(\mathcal{X}\)到标记空间 \(\mathcal{Y}\)的映射。

consistent 一致的：若目标概念 \(c \in \mathcal{H}\) ，则表示\(\mathcal{H}\)中存在假设能将所有示例按照与真实标记一致的方式分开，则称该问题对学习算法 L 是 可分的 (separable)，也称为一致的；若 \(c \not \in \mathcal{H}\)，则称为不可分 (non-separable)或者不一致(non-consistent)

PAC Identity PAC 辨识：对\(0 < \epsilon, \delta < 1\)，所有\(c \in \mathcal{C}\)和所有的分布\(\mathcal{D}\)，若存在学习算法 L ，其输出假设\(h \in \mathcal{H}\)满足\[ P(\varepsilon(h) \leq \epsilon ) \geq 1 - \delta \]则称学习算法能从假设空间 \(\mathcal{H}\)中 PAC 辨识概念类\(\mathcal{C}\)

2 附

2.1 AI-ML-DL

人工智能就是想让计算机拥有自行处理高级任务的能力；机器学习是实现人工智能的一种方法；深度学习是一类具体的机器学习方法。

2.1.1 Artificial Intelligence

人工智能发展：

推理期 – 赋予机器逻辑推理能力，但没有知识
知识期 – 让机器拥有知识（专家系统）；由人来把知识总结出来再教给计算机
机器学习 – 让机器自己能够学习知识

2.1.2 Machine Learning

机器学习研究方法：

连接主义（connectionism）学习 – 代表：感知机、神经网络、深度学习
符号主义（symbolism）学习 – 代表：决策树
统计学习 – 代表：SVM、核方法；（跟上述两种方法并不是完全并列）

2.1.3 Deep Learning

深度学习

现在火热的原因
- 数据量大了
- 计算能力强了
降低门槛

以往机器学习技术在应用中要取得良好的性能，对使用者的要求较高；而深度学习只要超参调节的好，性能往往就很好，显著降低了机器学习应用者的门槛。

手工调参：参数的设置缺乏理论指导，参数调节上失之毫厘，学习结果谬以千里；使用需要大量的 track （窍门）
理论基础

深度学习缺乏严格的理论基础

2.2 归纳偏好

任何一个有效的机器学习算法必有其归纳偏好，否则他将被假设空间中看似在训练集上等效的假设所迷惑，而无法产生确定的学习结果。

2.2.1 No Free Lunch Theorem – NFL

没有免费的午餐定理：所有问题出现的机会相同，或所有问题同等重要的前提下，无论算法 A 看似多精妙，算法 B 多笨拙，他们的期望性能是相同的。即：若考虑所有潜在的问题，则所有学习算法都一样好。学习算法自身的归纳偏好与问题是否匹配，往往起到决定行的作用。

脱离具体问题，空泛的谈什么学习算法更好毫无意义。

2.2.2 Occam's Razor

奥卡姆剃刀原理：在所有可能选择的模型中，能够很好的解释已知数据并且十分简单才是最好的模型。