-1. 契机
回顾一下2012年夏天帮同学完成的一个作业。虽然及其入门级，但对于基础概念的理解还是有所帮助。现在做以回顾，算是总结机器学习算法的开篇。
0. 问题定义
训练集中\(N\)个样本，每个样本\(p\)个特征，共包含\(K\)个类别。
1. 为何结合三种分类算法
从最终的测试结果来看，三种算法的结合似乎没有比单独使用其中两个甚至一个算法有特别大的提高。但是作为学习的过程，还是有其价值的。毕竟单独的算法就只是该算法本身，而算法的结合就需要从理论层面上考虑更多的因素。
2. 围绕LDA展开讨论
2.1 LDA用于分类的基本思路描述
这里是指线性判决分析，Linear Discriminant Analysis（LDA），而非文本主题模型中的Latent Dirichlet Allocation。已经忘了当初帮人做作业时候参阅哪本资料了，最近一年我是重新学习The Element of Statistical Learning。凑着有这个心情，就简单总结一下。
LDA是一种生成模型，根据Bayes原理直接用联合概率分布直接表示后验概率。\[\mathcal{P}(\mathcal{G}=k|X=x)=\frac{\mathcal{P}(X=x|\mathcal{G}=k)\mathcal{P}(\mathcal{G}=k)}{\mathcal{P}(X=x)}\] LDA模型对数据做两个假设
- 似然概率\(\mathcal{P}(X|\mathcal{G}=k)\)近似服从高斯分布，即\(X_{k} \sim{}\mathcal{N}(\mu_{k}, \Sigma_{k})\)
- 不同类别数据的协方差是相同的，即\(\Sigma_{i}=\Sigma_{j}, i\neq{}j\)。
这两个都算是比较强的假设。尤其是假设(1)，是使得Bayes原理可以进一步计算的基础。然而假设(2)通过修改，可以用来扩展算法。比如，如果认为每种类型的协方差并不相同，则获得二次判决分析，Quadratic Discriminant Analysis，QDA模型。再比如，如果二次多项式扩Features，并仍然假设不同类别的协方差相同，则获得另一种QDA。这似乎比前一种QDA有更多的约束条件，但是却更容易计算。毕竟协方差可是一个矩阵，太多总会影响计算效率。关于这些问题的讨论，这里不再一一展开，而专注于LDA本身，即\(\Sigma_{k}=\Sigma, k=1,\cdots,K\)。
既然后验概率都满足相同的比例关系，\(\mathcal{P}(\mathcal{G}=k|X=x)\propto{}\mathcal{P}(X=x|\mathcal{G}=k)\mathcal{P}(\mathcal{G}=k)\)，模型假设又保证了计算的可行性，通过比较不同类别之间的概率大小就可以提供判别依据。显然，应该选择概率最大的类别。为便于计算，对后验概率取对数。记\(\mathcal{P}(\mathcal{G}=k)=\pi_{k}\)。则有如下判别函数，
\[\delta_{k}(x)=-\frac{1}{2}(x-\mu_{k})^{T}\Sigma^{-1}(x-\mu_{k})-\frac{1}{2}\log|\Sigma|\]这似乎是个二次函数，但是线性分类条件之所以是线性，是因为分类边界是线性。这里的二次项并不会对分类结果产生影响，算式上可以直接省掉。但是为了便于衔接上下文，也便于后续分析，这里依然保留最原始的形式。
2.2 LDA中的参数估计
根据判别函数\(\delta_{k}(x)\)，对于任意给定的新样本，需要计算其对应函数值。显然，需要\(K\)个类别的\(\mu_{k}\)，以及公共的协方差矩阵\(\Sigma\)，方法如下。
\[N_{k}=\sum_{i=1}^{N}\mathcal{I}(\mathcal{G}_{i}=k)\]
\[\hat{\mu}_{k}=\frac{1}{N_{k}}\sum_{i\in{}\mathcal{G}_{k}}x_{i}\]
\[\hat{\Sigma}=\frac{1}{N-K}\sum_{k=1}^{K}\sum_{i\in{}\mathcal{G}_{k}}(x_{i}-\hat{\mu}_{k})(x_{i}-\hat{\mu}_{k})^T\]
到此为止，一切都很美好，过程非常的Straightforward，故事似乎可以告一段落。很多看过LDA的人一定要说，LDA可以降维。我个人觉得降维或许是LDA最初的动机，也或者是在某种程度上LDA得以应用的关键因素。但是我个人认为，LDA的分类核心思想确实应该到此为止。从功能上而言，这已经是完备的，也就是说，总是可以计算得到分类的，哪怕没有降维。
2.3 数据降维
数据降维毕竟不是LDA的专利，但是有了降维，这个算法可以更大程度的发挥作用。相比于主成分分析，Principal Component Analysis (PCA)，LDA的降维是有监督的，也就是说把样本类别信息考虑在内。这应该算是一种宏观上的不同点。
此外，我相信也并非所有的算法发明者从一开始就站在上帝的视角，用完美主义驱动着算法的改进，或是敏锐地察觉到算法本身的不足。改进永远都是后话。数据降维也未必是从计算效率的角度出发的，而是遇到了实际上的难题。在LDA算法中，当特征维度\(p\)十分大(\(p>N-K\))的时候，以上的计算就不可行了。因为计算得出的协方差矩阵\(\Sigma\)不可逆。
由训练数据样本组成的矩阵，先进行排列重组，将同一类别的样本相邻存放，得到
\[X_{k}=[x_{\mathcal{G}_{k},1}, \cdots, x_{\mathcal{G}_{k},N_{k}}]^{T}\]则整个训练数据集为
\[X=[x_{\mathcal{G}_{1},1},\cdots,x_{\mathcal{G}_{1},N_{1}};\cdots;x_{\mathcal{G}_{K},1},\cdots,x_{\mathcal{G}_{K},N_{K}}]\]
则协方差用矩阵重新表示为
\[\hat{\Sigma}=\frac{1}{N-K}A^{T}A\]其中，
\[A=[x_{\mathcal{G}_{1},1}-\mu_{1},\cdots,x_{\mathcal{G}_{1},N_{1}\mu_{1}};\cdots;x_{\mathcal{G}_{K},1}\mu_{K},\cdots,x_{\mathcal{G}_{K},N_{K}}-\mu_{K}]\]
如果看起来很奇怪，可以先考虑类内协方差
\[\hat{\Sigma}_{k}=\frac{1}{N_{k}-1} [x_{\mathcal{G}_{k},1}-\mu_{k}, \cdots, x_{\mathcal{G}_{k},N_{k}}-\mu_{k}][x_{\mathcal{G}_{k},1}-\mu_{k}, \cdots, x_{\mathcal{G}_{k},N_{k}}-\mu_{k}]^{T} \]
数学上容易证明，协方差的数值估计\(\hat{\Sigma}\)与矩阵\(A\)有相同的秩。而\(Rank(A)=min(p, N-K)\)。显然，如果\(p>N-K\)，矩阵非满秩，因此不可逆。然而不必惊慌，PCA这个原生态的降维手段总可以让过程进行下去。只要将\(X\)的特征维度缩减到\(N-K\)或以下即可。
2.3.1 PCA降维
2.3.2 LDA降维
2.4 数据分类
（未完待续……）