在认知算法课里学习了一些算法，比如NCC，感知算法，LDA等等，小结一下。
Nearest Centroid Classifier
NCC. 最简单的一个归类算法。输入多个\((\mathbf x, y)\)，其中\(\mathbf x\)表示特征，\(y\)表示所属类别，比如\( y \in \{ -1,1 \} \)。将每一类的\(\mathbf x\)取平均，得到一个向量，称为原型（Prototype）。预测一个新的\(\mathbf x\)是属于哪一类的时候，计算并比较它与每一类的原型的相似度（距离），归为最相似的那一类中。比如\(y = -1： (0, 1); y = 1: (1, 0)\)，输入\(\mathbf x = (0, 2)\)，计算它与\((0, 1)\)和\((1, 0)\)的距离并比较，容易得出离前者更近，所以归入\(y = -1\)组。
基于这一思想，可以推导出一个函数\(f(\mathbf x)\)，当\(\mathbf x\)属于一个组的时候函数值为正，属于另一个组的时候函数值为负。略去推导过程，给出结果：
$$ f(\mathbf x) = {\mathbf w}^T \mathbf x - \beta $$
其中：
$$ {\mathbf w} = \mathbf w_{-1} - \mathbf w_{+1} \\ \beta = \frac{1}{2} \left( \mathbf w_{-1}^T \mathbf w_{-1} - \mathbf w_{+1}^T \mathbf w_{+1} \right) $$
感知算法
和NCC类似，输入一组数据和他们的类别，输出一个\(\mathbf w\)。
引入一个概念感知错误（Perceptron Error），衡量一个\(\mathbf w\)的好坏。定义为：
$$ E_p(\mathbf w) = - \sum_{m \in M} \mathbf w^T \mathbf x_m y_m $$
其中\(M\)是所有分类错误的数据的index。为了获得一个最优的\(\mathbf w\)，将上面的\(E_p(\mathbf w)\)最小化即可。在这里使用了随机梯度下降法（Stochastic Gradient Descent）。
$$ \mathbf w^{new} = \mathbf w^{old} - \eta \nabla E_p(\mathbf w^{old}) = \mathbf w^{old} + \eta \mathbf x_m y_m $$
其中最初的\(\mathbf w\)可以随机取得，\(\eta\)是学习率（learning rate），反应变化的速率，由于梯度下降法的特点，\(\eta\)不能太大也不能太小，太大可能得不出结果，太小的话会收敛太慢。
使用这个方法时，可以设定一个跳出条件，比如相邻两次的变化量小于某个值，让模型重复随机取值、计算即可。
Linear Discriminant Analysis
LDA，线性判别分析，是后续很多算法的基础，十分重要。和前面两个算法的目的一样，为了找出\(\mathbf w\)和\(\beta\)。
引入一个概念，费希尔标准（Fisher Criterion），用来衡量两个类别的分离程度：
$$ F = \frac{between \ class \ variance}{within \ class \ variance} = \frac{({\mathbf w_{+1} - \mathbf w_{-1}})^2}{\sigma_{+1}^2 + \sigma_{-1}^2} $$
其中：
$$ \mathbf w_i = \frac{1}{N_i}\sum_{j=1}^{N_i}\mathbf x_{ji}, \\ \sigma_i^2 = \frac{1}{N_i} \sum_{j=1}^{N_i}(x_{ji} - \mathbf w_i)^2 $$
为了找到最优的\((\mathbf w , \beta)\)组合，只需要最大化组间variance，最小化组内variance即可，即最大化\(F\)。求导、推导过程略过，计算方法如下：
首先用上面的方法计算\(\mathbf w_i\)。
计算组内方差矩阵：
$$ S_W = \frac{1}{N_{-}} \sum_{i \in y_{-}} (\mathbf x_i - \mathbf w_{-}) (\mathbf x_i - \mathbf w_{-})^T + \frac{1}{N_{+}} \sum_{i \in y_{+}} (\mathbf x_i - \mathbf w_{+}) (\mathbf x_i - \mathbf w_{+})^T $$
算出结果：
$$ \mathbf w = S_W^{-1}(\mathbf w_{+} - \mathbf w_{-}) \\ \beta = \frac{1}{2} \mathbf w^T (\mathbf w_{+} + \mathbf w_{-}) + \log (\frac{N_{-}}{N_{+}}) $$
Ordinary Least Squares
OLS，普通最小二乘法，用于线性回归。输入一组数据\((\mathbf x, y)\)，得到线性函数\(f(\mathbf x) = \mathbf \omega^T \mathbf x\)，把其中的\(\mathbf x\)替换为合适的核函数（Kernel Function）\(\mathbf \phi (\mathbf x)\)可以用于非线性回归。
引入概念最小二乘误差（Least Square Error），用于衡量线性函数与样本的契合度：
$$ E(\mathbf \omega) = \sum_{t=1}^T (y_t - \mathbf \omega^T \mathbf x_t)^2 $$
求导，置零，推导过程略过，得到结果为：
$$ \mathbf \omega = (\mathbf X \mathbf X^T)^{-1}\mathbf X y^T $$
可以把\(y\)扩展到多维，这样得到的是Linear Mapping。
很多时候时候线性函数\(f(\mathbf x) = \mathbf \omega^T \mathbf x\)不满足需求，需要添加一个偏移量，也就是把函数变成\(f(\mathbf x) = \mathbf \omega^T \mathbf x + bias\)，可以通过在样本\(\mathbf X\)的最上方加入一行\(1\)来实现。
Ridge Regression
有时候仅仅使用OLS会导致过拟合(Overfitting)的问题，即模型使用过多的参数过度适应样本而不能反应真实情况，所以控制\(\mathbf \omega\)的复杂度是有必要的。
扩展一下最小二乘误差：
$$ E_{RR} (\mathbf \omega) = (y - \mathbf \omega^T \mathbf X)^2 + \lambda \mathbf \omega^2 $$
其中\(\lambda\)被称为Ridge，控制它的大小以控制\(\mathbf \omega\)的复杂度，不能太大也不能太小，太大会导致欠拟合，太小会导致过拟合。
推导过程略过，得到的结果为：
$$ \mathbf \omega = (\mathbf X \mathbf X^T + \lambda \mathbf I)^{-1}\mathbf X y^T $$
结语
以上差不多是这门课里学到的全部算法，主要用于线性归类和回归，可以使用适当的核函数（Kernel Function）扩展到非线性的范围。另外还可以使用Cross Validation来判断一个模型的好坏。关于这两个话题之后再做总结。