认知算法小结

在认知算法课里学习了一些算法，比如NCC，感知算法，LDA等等，小结一下。

Nearest Centroid Classifier

NCC. 最简单的一个归类算法。输入多个(x,y)(\mathbf x, y)(x,y)，其中x\mathbf xx表示特征，yyy表示所属类别，比如y∈{−1,1} y \in \{ -1,1 \} y∈{−1,1}。将每一类的x\mathbf xx取平均，得到一个向量，称为原型（Prototype）。预测一个新的x\mathbf xx是属于哪一类的时候，计算并比较它与每一类的原型的相似度（距离），归为最相似的那一类中。比如y=−1：(0,1);y=1:(1,0)y = -1： (0, 1); y = 1: (1, 0)y=−1：(0,1);y=1:(1,0)，输入x=(0,2)\mathbf x = (0, 2)x=(0,2)，计算它与(0,1)(0, 1)(0,1)和(1,0)(1, 0)(1,0)的距离并比较，容易得出离前者更近，所以归入y=−1y = -1y=−1组。

基于这一思想，可以推导出一个函数f(x)f(\mathbf x)f(x)，当x\mathbf xx属于一个组的时候函数值为正，属于另一个组的时候函数值为负。略去推导过程，给出结果：

f(x)=wTx−β f(\mathbf x) = {\mathbf w}^T \mathbf x - \beta f(x)=wTx−β

w=w−1−w+1β=12(w−1Tw−1−w+1Tw+1) {\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) w=w−1​−w+1​β=21​(w−1T​w−1​−w+1T​w+1​)

和NCC类似，输入一组数据和他们的类别，输出一个w\mathbf ww。

引入一个概念感知错误（Perceptron Error），衡量一个w\mathbf ww的好坏。定义为：

Ep(w)=−∑m∈MwTxmym E_p(\mathbf w) = - \sum_{m \in M} \mathbf w^T \mathbf x_m y_m Ep​(w)=−m∈M∑​wTxm​ym​

其中MMM是所有分类错误的数据的index。为了获得一个最优的w\mathbf ww，将上面的Ep(w)E_p(\mathbf w)Ep​(w)最小化即可。在这里使用了随机梯度下降法（Stochastic Gradient Descent）。

wnew=wold−η∇Ep(wold)=wold+ηxmym \mathbf w^{new} = \mathbf w^{old} - \eta \nabla E_p(\mathbf w^{old}) = \mathbf w^{old} + \eta \mathbf x_m y_m wnew=wold−η∇Ep​(wold)=wold+ηxm​ym​

其中最初的w\mathbf ww可以随机取得，η\etaη是学习率（learning rate），反应变化的速率，由于梯度下降法的特点，η\etaη不能太大也不能太小，太大可能得不出结果，太小的话会收敛太慢。

使用这个方法时，可以设定一个跳出条件，比如相邻两次的变化量小于某个值，让模型重复随机取值、计算即可。

Linear Discriminant Analysis

LDA，线性判别分析，是后续很多算法的基础，十分重要。和前面两个算法的目的一样，为了找出w\mathbf ww和β\betaβ。

引入一个概念，费希尔标准（Fisher Criterion），用来衡量两个类别的分离程度：

F=betweenclassvariancewithinclassvariance=(w+1−w−1)2σ+12+σ−12 F = \frac{between \ class \ variance}{within \ class \ variance} = \frac{({\mathbf w_{+1} - \mathbf w_{-1}})^2}{\sigma_{+1}^2 + \sigma_{-1}^2} F=within class variancebetween class variance​=σ+12​+σ−12​(w+1​−w−1​)2​

wi=1Ni∑j=1Nixji,σi2=1Ni∑j=1Ni(xji−wi)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 wi​=Ni​1​j=1∑Ni​​xji​,σi2​=Ni​1​j=1∑Ni​​(xji​−wi​)2

为了找到最优的(w,β)(\mathbf w , \beta)(w,β)组合，只需要最大化组间variance，最小化组内variance即可，即最大化FFF。求导、推导过程略过，计算方法如下：

首先用上面的方法计算wi\mathbf w_iwi​。

计算组内方差矩阵：

SW=1N−∑i∈y−(xi−w−)(xi−w−)T+1N+∑i∈y+(xi−w+)(xi−w+)T 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 SW​=N−​1​i∈y−​∑​(xi​−w−​)(xi​−w−​)T+N+​1​i∈y+​∑​(xi​−w+​)(xi​−w+​)T

算出结果：

w=SW−1(w+−w−)β=12wT(w++w−)+log⁡(N−N+) \mathbf w = S_W^{-1}(\mathbf w_{+} - \mathbf w_{-}) \\ \beta = \frac{1}{2} \mathbf w^T (\mathbf w_{+} + \mathbf w_{-}) + \log (\frac{N_{-}}{N_{+}}) w=SW−1​(w+​−w−​)β=21​wT(w+​+w−​)+log(N+​N−​​)

Ordinary Least Squares

OLS，普通最小二乘法，用于线性回归。输入一组数据(x,y)(\mathbf x, y)(x,y)，得到线性函数f(x)=ωTxf(\mathbf x) = \mathbf \omega^T \mathbf xf(x)=ωTx，把其中的x\mathbf xx替换为合适的核函数（Kernel Function）ϕ(x)\mathbf \phi (\mathbf x)ϕ(x)可以用于非线性回归。

引入概念最小二乘误差（Least Square Error），用于衡量线性函数与样本的契合度：

E(ω)=∑t=1T(yt−ωTxt)2 E(\mathbf \omega) = \sum_{t=1}^T (y_t - \mathbf \omega^T \mathbf x_t)^2 E(ω)=t=1∑T​(yt​−ωTxt​)2

求导，置零，推导过程略过，得到结果为：

ω=(XXT)−1XyT \mathbf \omega = (\mathbf X \mathbf X^T)^{-1}\mathbf X y^T ω=(XXT)−1XyT

可以把yyy扩展到多维，这样得到的是Linear Mapping。

很多时候时候线性函数f(x)=ωTxf(\mathbf x) = \mathbf \omega^T \mathbf xf(x)=ωTx不满足需求，需要添加一个偏移量，也就是把函数变成f(x)=ωTx+biasf(\mathbf x) = \mathbf \omega^T \mathbf x + biasf(x)=ωTx+bias，可以通过在样本X\mathbf XX的最上方加入一行111来实现。

Ridge Regression

有时候仅仅使用OLS会导致过拟合(Overfitting)的问题，即模型使用过多的参数过度适应样本而不能反应真实情况，所以控制ω\mathbf \omegaω的复杂度是有必要的。

扩展一下最小二乘误差：

ERR(ω)=(y−ωTX)2+λω2 E_{RR} (\mathbf \omega) = (y - \mathbf \omega^T \mathbf X)^2 + \lambda \mathbf \omega^2 ERR​(ω)=(y−ωTX)2+λω2

其中λ\lambdaλ被称为Ridge，控制它的大小以控制ω\mathbf \omegaω的复杂度，不能太大也不能太小，太大会导致欠拟合，太小会导致过拟合。

推导过程略过，得到的结果为：

ω=(XXT+λI)−1XyT \mathbf \omega = (\mathbf X \mathbf X^T + \lambda \mathbf I)^{-1}\mathbf X y^T ω=(XXT+λI)−1XyT

以上差不多是这门课里学到的全部算法，主要用于线性归类和回归，可以使用适当的核函数（Kernel Function）扩展到非线性的范围。另外还可以使用Cross Validation来判断一个模型的好坏。关于这两个话题之后再做总结。