分类问题：
其输入是输入空间\(\mathcal{X} = \mathbb{R}^d\)中的\(n\)个样本\(x_1, \ldots, x_n\)，输出是离散空间\(\mathcal{Y}\)中的某个值。当\(\mathcal{Y} = \{-1,+1\}\)或\(\{0,1\}\)时，问题是一个二元分类问题；当\(\mathcal{Y} = \{1, \ldots, K\}\)时，问题是一个多元分类问题
分类问题使用函数\(f\)（即分类器）将输入\(x\)映射到类别\(y\)上，即\(y = f(x)\)
近邻分类
其算法思想是，给定数据\((x_1, y_1), \ldots, (x_n, y_n)\)，构造分类器\(\hat{f}(x) \rightarrow y\)如下：
- 对于不在训练数据里的\(x\)，令\(x_i\)是\((x_1, y_1), \ldots, (x_n, y_n)\)中离\(x\)“最近”的点
- 返回其标签\(y_i\)
如何衡量\(x\)之间的距离？常见的是使用欧几里得距离，即 \[ |\!|u-v|\!|_2 = \left(\sum_{i=1}^d (u_i - v_i)^2\right)^{\frac{1}{2}} \] 当然也可以使用其它衡量方法，例如\(\ell_p\)、编辑距离（适用于字符串）或者相关距离（衡量两个向量的相关性）
k近邻分类
与原始的近邻分类类似，不过是选取“最近”的\(k\)个点，然后得票最多的类别是判定的类别
分类器有效的基本假定也是测试数据（未知数据）与训练数据（已知数据）独立同分布
贝叶斯分类
最优分类器
假设\((X,Y) \mathop{\sim}^{iid} \mathcal{P}\)，而且我们不知道\(\mathcal{P}\)的分布，那么关于分布\(\mathcal{P}\)有两个性质
- 一个事件的指示变量的期望是这个事件的概率。即若定义\(\mathbb{1}(\cdot) = 0{\rm \ or \ 1}\)取决于\(\cdot\)是否为真，则有 \[ \mathbb{E}_P[1(Y=1)] = P(Y=1) \]
- 条件概率的期望可能会是随机变量，但是这个随机变量的期望是一个常数，即 \[ C = \mathbb{E}[A|B], \mathbb{E}[C] = \mathbb{E}[\mathbb{E}[A|B]] = \mathbb{E}[A] \]
对于任意分类器\(f: \mathcal{X} \rightarrow \mathcal{Y}\)，其预测误差为 \[ P(f(X) \not= Y) = \mathbb{E}[1(f(X) \not= Y)] = \mathbb{E}[\mathbb{E}[1(f(X) \not= Y)|X]] \] 对每个\(x\in \mathcal{X}\)，有 \[ \mathbb{E}[1(f(X) \not= Y)|X=x] = \sum_{y \in \mathcal{Y}} P(Y=y|X=x)\cdot 1(f(x) \not= y) \]
所以上式取得最小值的条件是分类器\(f^\star\)对所有\(x \in \mathcal{X}\)，都取 \[ f^\star (x) = {\rm arg}\max_{y \in \mathcal{Y}} P(Y=y|X=x) \] 对所有\(x \in \mathcal{X}\)都具有这一属性的分类器\(f\)称为贝叶斯分类器，它在所有分类器中有最小预测误差
贝叶斯分类器
对于上式，根据贝叶斯定律，等价于有 \[ f^\star (x) = {\rm arg}\max_{y \in \mathcal{Y}} P(Y = y) \times P(X = x|Y = y) \] 其中\(P(Y=y)\)称为类别先验，\(P(X=x|Y=y)\)称为\(X\)的类别条件分布（当\(X\)是连续随机变量时，\(P(X=x|Y=y)\)写为\(p(x|Y=y)\)，称为类别条件密度）。在实际中，这两个分布我们都不知道会是什么，所以只能去近似之
（以下四段摘抄于http://blog.csdn.net/zouxy09 ）
判别方法：由数据直接学习决策函数Y=f(X)或者条件概率分布P(Y|X)作为预测的模型，即判别模型。基本思想是有限样本条件下建立判别函数，不考虑样本的产生模型，直接研究预测模型。典型的判别模型包括k近邻，感知级，决策树，支持向量机等。
生成方法：由数据学习联合概率密度分布P(X,Y)，然后求出条件概率分布P(Y|X)作为预测的模型，即生成模型：P(Y|X)= P(X,Y)/ P(X)。这样的方法之所以称为生成方法，是因为模型表示了给定输入X产生输出Y的生成关系。用于随机生成的观察值建模，特别是在给定某些隐藏参数情况下。典型的生成模型有：朴素贝叶斯和隐马尔科夫模型等。
生成方法的特点：上面说到，生成方法学习联合概率密度分布P(X,Y)，所以就可以从统计的角度表示数据的分布情况，能够反映同类数据本身的相似度。但它不关心到底划分各类的那个分类边界在哪。生成方法可以还原出联合概率分布P(Y|X)，而判别方法不能。生成方法的学习收敛速度更快，即当样本容量增加的时候，学到的模型可以更快的收敛于真实模型，当存在隐变量时，仍可以用生成方法学习。此时判别方法就不能用。
判别方法的特点：判别方法直接学习的是决策函数Y=f(X)或者条件概率分布P(Y|X)。不能反映训练数据本身的特性。但它寻找不同类别之间的最优分类面，反映的是异类数据之间的差异。直接面对预测，往往学习的准确率更高。由于直接学习P(Y|X)或P(X)，可以对数据进行各种程度上的抽象、定义特征并使用特征，因此可以简化学习问题。
plug-in分类器
通常情况下，我们并不知道\(P(Y=y|X=x), P(X=x|Y=y)\)和\(P(Y=y)\)，我们只有从分布\(\mathcal{P}\)中得到的带标签的样本。但是按照道理来讲，在不知道\(\mathcal{P}\)的情况下我们无法构建贝叶斯分类器，所以需要用手头数据去估计\(P(Y=y)\)和\(P(X=x|Y=y)\)，其代价是得到的结果不会是最好的结果——这种分类器称为plug-in分类器
对于\(\mathcal{X} = \mathbb{R}^d\)和\(\mathcal{Y} = \{1,\ldots, K\}\)，可以通过MLE来估计贝叶斯分类器。类别的先验的MLE估计\(\pi_y\)为 \[ \hat{\pi}_y = \frac{1}{n} \sum_{i=1}^n 1(y_i = y) \] 类别的条件概率密度可以假设为\(p(x|Y=y) = N(x|\mu_y, \Sigma_y)\)，两个参数的MLE估计为 \[ \begin{align*} \hat{\mu}_y &= \frac{1}{n_y} \sum_{i=1}^n 1(y_i = y)x_i \\ \hat{\Sigma}_y &= \frac{1}{n_y} \sum_{i=1}^n 1(y_i = y)(x_i - \hat{\mu}_y)(x_i - \hat{\mu}_y)^T \end{align*} \] 对应的plug-in分类器为 \[ \hat{f}(x) = {\rm arg}\max_{y \in \mathcal{Y}} \hat{\pi}_y |\hat{\Sigma}_y|^{-\frac{1}{2}}\exp\left\{-\frac{1}{2} (x - \hat{\mu}_y)^\mathsf{T}\hat{\Sigma}_y ^{-1}(x-\hat{\mu}_y)\right\} \]
例如，在垃圾邮件分类器中，使用朴素贝叶斯，其假设\(X\)的各个维度在\(y\)下条件独立，忽略了它们之间的相关性使得概率容易算，即 \[ p(X= x|Y=y) = \prod_{j=1}^d p_j(x(j)|Y=y) \]
这时类别的先验为 \[ P(Y=y) = \frac{\#{\rm observations\ in\ class\ }y}{ {\rm \# observations}} \]
条件分布使用泊松分布，即 \[ P(X=x|Y=y) = \prod_j p_j(x(j)|Y=y) = \prod_j {\rm Poisson}(x(j)|\lambda_j^{(y)}) \] 其中\(\lambda_j^{(y)}\)的MLE为 \[ \lambda_j^{(y)} = \frac{\#{\rm unique\ uses\ of\ word\ }j{\rm\ in\ observations\ from\ class\ }y}{\#{\rm observations\ in\ class\ }y} \]
