明亮如星研旅（3）—— Discriminative Learning Quadratic Discriminant Function for Handwriting Recognition
《Discriminative Learning Quadratic Discriminant Function for Handwriting Recognition》这篇文章是刘成林老师2004年早期的工作，其利用传统的方法将文字识别提高到一个极高的准确率。
这篇文章是比较经典的文章，相对于目前流行的深度学习方法，其数学分析的味道比较浓，更接近的我以往对科研的想象。不像目前大部分文章搭个网络，然后各种实验，吹嘘一下自己的网络如何如何好，各种指标刷新了多少，但是真正创新型的工作很少，更别提通过数学角度从背后分析其原理。
以下谈谈文章的工作主要内容：
文章对 modified quadratic discriminant function (MQDF)判别模型进行了改进，提出了Discriminative Learning Quadratic Discriminant Function（DLQDF）判别模型。该模型对文字识别有较高的准确率（与当时神经网络的准确率相当），并且保留了对非文字较高的拒绝能力（MQDF模型的优势）。简单说，在高斯分布的假设下，DLQDF模型采用判别学习算法，设定MCE损失误差函数，对MQDF模型的参数进行优化。
现在来讲讲文章的细节：
一、MQDF判别模型回顾
MQDF模型是对传统的二次判别模型（QDF）进行改进：
- 模型将协方差矩阵较小的特征值设定为固定值，平滑了特征值，这样便对有限样本容量下的估计误差进行平滑补偿。
- 由于基于高斯分布假设（非文字的特征对应的概率密度比较小），模型对于非文字有较好拒识能力。（而神经网络局限于训练样本，其分类面空间是开放的，在没有非文字的训练样本下，其也会有较高的置信度）
接下来呈上三种MQDF判别模型的细节，顺别回顾下模式识别的知识：
根据贝叶斯公式，类条件概率密度为：
由于P(x)不影响最后结果，得到判别函数：
在高斯分布以及每一类的先验概率相同的假设下得到：
通过KL变换，协方差矩阵调整为：
对应的特征值对角矩阵，且有特征向量标准正交化
，最后得到：
将协方差矩阵较小的特征值设定为固定值，得到MQDF2:
其中
文章说MQDF2有几个优点：1.它克服了小特征值的偏置这样分类性能就可以得到提高。2、对于计算MQDF2，只需要主体特征向量和特征值将被存储，以便减少存储空间。第三，大大节省了计算量，因为到小轴的投影是不计算的。前人也给出了的估计方法，即最小的几个特征值的均值：
在MQDF2中加入正则化项得到MQDF3判别模型：
局限：回顾MQDF2与MQDF3，模型参数（协方差矩阵以及期望向量）根据每一类样本独立估计的，极大似然估计（ML）存在较大估计误差，分类误差也没有考虑。
二、DLQDF判别模型介绍
DLQDF判别模型采用和MQDF判别模型一样的结构，用训练后的MQDF判别模型的参数来初始化DLQDF参数。但是考虑的MQDF的局限性，DLQDF根据判别学习算法，通过优化MCE损失函数，动态的调整模型参数。（显然比直接通过极大似然估计（ML）准确多）
调整思路：在期望向量可以在特征空间任意变化，但是特征值和特征向量要保证协方差矩阵对称正定（即对角特征值为正值且特征向量标准正交）,接下来呈上DLQDF判别模型的细节:
定义MEC损失函数：
1.首先定义二次距离：
其实这里的距离是同（7），类条件概率函数的相反数，以这个为度量是合理的（越相似则距离越短）。
2、定义二次判别函数：
其为二次距离的相反数。
3、定义错分类的衡量标准：
当趋向于无穷时那么可以进一步写成
其中
或者这个度量可以写成
其实这就是衡量了 样本与GT类的距离 和 样本与最相似类的距离 的 差 (分类时，希望这个差越小越好，这样更加鲁棒)
4、定义错分类的误差以及总误差
本文所谓的判别学习，就是优化以上的MCE损失函数，来提高高斯密度模型精度。根据实验表明MCE的优势在于对于任
意简单的判别函数均适应，而MSE局限于二分类的分类器。
模型参数会影响模型容量，加入了正则化项：
正则化项是类内二次距离，文章讲了不少好处，个人认为就是增加了类内的紧致性。
接下来文章介绍如何学习DLQDF判别模型：
1、采用随机梯度下降法：
其中
这里我们要明确我们训练的参数有四种：特征值，特征值固定值
，均值向量
，特征向量
；类别有两
类，GT类以及最相似的类。
2、为了保证特征值为正，这里做了变量替换：
相应的二次距离形式变成：
3、为了保证特征向量的标准正交性，在每一步训练迭代之后进行一次Gram-Schmidt ortho-normalization(GSO)
4、具体求导公式为
最后对于模型超参数的设置给出策略（个人觉得这一部分特别重要，如果能从数学推导的方式给出合理的解释是最好的）：
1、（22）式的学习率
与相应的二阶偏导成反比关系（个人认为，牛顿法、拟牛顿法为二阶展开，在每步最优步长的条件下，学习率与其Hessian矩阵成反比），具体二阶偏导在最后附录部分给出了求解，,文章设定初始的学习率为
。
2、（19）式的参数：
MCE损失函数将损失限定在0-1范围内，参数应与
的数量级成反比关系，随着参数
的增大接近于0-1损失函数。
3、（21）式的权重：
我们要使得与
有相同的数量级，则
要与
的数量级成反比。
三、实验部分
数据集选择：
NIST Special Database 19 (SD19) ,训练集由 600 writers (writers no.0–399 and no. 2100–2299)组成，测试集有 400 writers (writers no. 500–699 and no.2400–2599)组成，总计有66214个训练样本和45398个测试样本。除此之后，又自己合成了非字符样本，16000张作为训练集，10000张作为测试集。（非字符样本集包括两类1、数字拼凑2、英文字母，个人认为这样生成的非字符集是不是太局限了）
对于每个样本提取100维特征，包括轮廓、梯度、方向等等，具体特征也是根据[R. Zhang, X. Ding, and J. Zhang, “Offline handwritten character recognition based on discriminative training of orthogonal Gaussian mixture model,” in Proc. 6th Int. Conf. Document Analysis and Recognition,Seattle, WA, 2001, pp. 221–225]这篇文献（具体特征我也没有细看，这里着重还是在设计判别器）。
1、DLQDF在不标准正交化（GSO）以及不加入正则化项
DLQDF1 updates the eigenvalues and const eigenvalues
;
DLQDF2 updates the eigenvalues, const eigenvalues
, and mean vectors
;
DLQDF3 updates all the parameters;
2、分别考虑标准正价化以及加入正则化项的情况
3、与神经网络做对比
这里神经网络由三个版本：1、使用MSE损失函数 2、使用MCE损失函数 3、MSE损失函数加非字符训练样本。发现这几个版本的准确率没有太大变化，在简单的单层的网络MCE凸显出优势，上面的准确率要比DLQDF的（99.19%）要低。
MCE评价标准相比于传统的损失函数（例如均方损失MSE）有较大的优势，其适用于任意参数模型或者判别模型，但仅局限于简单的判别器，对于复杂的网络没有凸显优势。
在非字符拒绝能力来看（横坐标是错误拒绝率，纵坐标是错误接受率，所围成的面积越小，模型越好），显然MQDF与DLQDF有较好的拒绝识别能力，即使神经网络在加入非字符训练样本的情况下（EMLP、EPC）。
四、数字字符串识别
本节并没有提出什么新的字符串识别系统，而是根据之前的 ISR字符串识别系统，在字符识别上比较DLQDF与神经网络的性能，不考虑任何几何与语义信息。
识别系统从候选模式到候选格逐一计算，求解一条最优的路径。
其中评价函数为
其中代表每个切分部分，
代表每个类，d即为相应的距离。这里取均值是考虑得到，不同的字符串长度有相同的评价尺度。然而这种评价方式，使得之前的动态规划不适合，这里使用了前人的Beam Search方法。
NIST 3-DIFIT是长度为3的字符串数据集，NIST 6-DIGIT是长度为6的字符串数据结构，这里展示了不同方法相应的接受率、1%错误率以及0.5%错误率。最后其又和目前的字符串识别的主流方法进行了对比，发现甚至比考虑语义和结构的方法具有更高的识别率。
五、总结
DLQDF在高斯分布的假设下，使用判别学习方法，采用MCE损失函数，优化相应的模型参数。
- 由于是高斯分布假设下，保留了原来较好的非字符的拒绝能力。
- 根据损失函数动优化模型参数，减少了ML估计产生的误差。
个人觉得本文最大的亮点或者是创新点是能够考虑到，二次判别模型通过ML估计，具有较大的估计误差，想到用一个评价函数去进一步优化参数。