0%

Robust Classification with Convolutional Prototype Learning 一文是自动化所刘成林、殷飞老师组 Hong-Ming Yang 师兄的工作,CVPR 2018 录用。
论文地址:https://arxiv.org/abs/1805.03438v1
论文代码:https://github.com/YangHM/Convolutional-Prototype-Learning

这篇文章在原型学习(prototype learning)与 CNN 的基础之上,提出了一种有效的学习方式,并设计了几种不同的 loss 函数,这些损失函数均能从直观上理解其效果并在实验中证明它们的有效性。通过学习这篇文章,可以更好地了解原型学习以及 loss 的设计,同时可以直接将文中的方法用于一些下游应用。

此外需要注意的是,这篇文章的“Robust classification”和 Goodfellow 提出的对抗样本型“Robust model”是两码事。这篇文章没有对模型对于对抗样本的 Robust 进行分析,但本文提出的方法学习到的分类器对于任务来说是 Robust 的。从文章的实验结果来看,将这篇文章提出的方法称为“Robust”一点也不为过,毕竟“Robust”又不是 Goodfellow 发明的,各人可以有自己的理解。

概述

这篇文章主要按以下的框架描述了作者提出的方法:

  • 背景与相关工作
  • 卷积原型学习(Convolutional prototype learning)
  • 设计的各种 loss 函数
  • 实验结果与分析

因此,这篇笔记也按照论文作者的写作顺序记录。

背景与相关工作

文章开头就给了这张图,描述了传统的 CNN 模型 + cross entropy loss 在 MNIST 上训练出来的特征的二维表示。作者用此图片说明了传统 CNN 模型的问题:学习出来的分类特征在特征空间内非常集中,甚至有很多类内距离(intra-class)小于类间距离(inter-class)的情况。这种情况也就会导致最终的分类效果变差,并且分类模型不易拓展等不够“Robust”的问题。

这个图片的具体作图方法,是把模型输出层前的最后隐层(bottleneck layer)设定为两个神经元,训练完成后,将样本送入神经网络,取出这两个神经元的输出,将输出分别设为 X 与 Y 轴,即得到了这张图。(这个方法可以用在别的需要可视化特征的场景中,可以免去 PCA 等降维步骤。不过在一些比较复杂的任务里貌似这么训练会很难收敛)

尽管后来还有人为此做了各种改进,比如 triple loss、centre loss 等,来改善这种情况,但这些方法都没有离开 softmax + cross entropy 的范畴,也没有根本解决问题。因此作者基于原型学习的思想,利用 CNN 作为特征提取的工具,提出了一种原型学习框架 Convolutional prototype learning(后文直接记为 CPL),同时为它设计了几种模式的 loss 函数,在实验上取得了良好的效果。

关于什么是原型学习,可以了解一下 LVQ 算法。

卷积原型学习

如图所示。这个框架其实思路很简单:

  1. 利用 CNN 进行特征提取:直接将 CNN 看做是一个 $f(x,\theta)$ 的函数,输入的 x 是数据,$\theta$ 是 CNN 的参数;输出的是特征。
  2. 用一个或多个原型来对应每一个分类(文章后来用实验证明了一个分类对应一个原型就可以有足够好的效果)。
  3. 在训练时,让原型与原型间的欧式距离尽量远,让特征与对应类别原型的欧式距离尽量近:

(上式中各符号代表的含义请参考原论文 3.1 与 3.2)

loss 函数

这部分是文章的核心。为了实现上面一节说的 CPL,必须要有合适的 loss 函数,这种 loss 函数需要满足以下几个条件:

  1. 符合 CPL 的思路,及让原型与原型间距离尽量远,让特征与对应原型的距离尽量近。
  2. 需要对 CNN 可导(这样才能通过 BP 算法去优化 CNN 的参数 $\theta$,也就才能让 CNN 提取出正确的特征)
  3. 需要对原型可导(这样才符合原型学习的思想,才能去不断调整原型在特征空间中的位置)

因此,这篇文章设计的几个 loss 函数都会去证明 $\frac { \partial l } { \partial f }$ 与 $\frac { \partial l } { \partial M }$ 的可导性。(l 是 loss 函数,f 是 CNN 特征提取器,M 是原型集),笔记中就不再赘述。

下文将逐个说明论文提出的 loss 函数。

Minimum classification error loss(MCE)

MCE 即“最小分类误差”,是《Discriminative learning for minimum error classification》提出的一种经典的测量指标,主要公式如下:

作者在列这个公式的时候貌似忘了解释 $\eta$ 的作用了。查阅原文发现,这个指标可以用来控制考虑误分类的程度多少。当 $\eta$ 为正无穷的时候,上式等于

其中 $g _ { r } ( x ) = \max _ { k \neq y } g _ { k } ( x )$,是“错的最离谱”的错分距离。因此可以将 MCE 记为

作者按照《Discriminative learning for minimum error classification》中的 Translated sigmoid 公式定义了这个方法最终的 loss 函数计算公式:

综上,这个 loss 方法其实优化的是 MCE 指标,重点是作者将 $\mu_y$ 转换为了原型的形式,换句话就是说这个 loss 在优化时,除了会让 CNN 提取出正确的特征外,还会尽量让原型靠近正确的类的特征分布密集区域,远离错误的类的特征分布区域。通过这种方式,可以实现笔记最开头提到的目标。

Margin based classification loss(MCL)

顾名思义,这个 loss 是“基于边距的分类 loss”。这个“margin”在 triple loss 等方法中其实都有用到。作者提出这个方法的思想就是“让一个样本的特征和对应分类的原型在特征空间中的距离,要小于和其它原型在特征空间内的距离”,通过这种思路,就能使得样本尽量不被误分类。按照这个思路,作者提出了公式:

这个公式中的 d 函数就是求样本和原型在特征空间中的欧式距离。整个 loss 用 $\left[ \right] _+$ 包含着,表示只取正值。因为如果样本距离正确分类的原型的距离已经满足要求时,loss 值应该为 0。

根据上式,作者进一步对这个 loss 进行完善,为它添加了 margin(作用和 triple loss、centre loss 的 margin 是一致的),让“样本离本类原型”的距离要比“样本离其它类原型”距离+margin要更小:

这样就能达成前文所说的目的。

作者在此基础上,又为 margin 的值做了进一步的改进。因为在上述 loss 中,margin 的值必须和“样本与原型的距离”值在同一个数量级上才能顺利进行优化。为此,作者稍作转换:

这样,m 在 (0,1) 的范围内取值即可保证数量级的一致性。

Distance based cross entropy loss(DCE)

这个 loss 函数是基于一个约等式:

这个式子的意义是,可以用“样本距离原型的距离”来测度“样本属于一个原型类别的概率”。这样就能用 cross entropy 之类的方法对概率进行优化了。因此,需要用一个确切的值来把上式给写出来,同时满足:

  1. 概率值是正数
  2. 所有概率(即一个样本属于各个原型的概率)的和需要为 1

    为此,作者定义

    此时,样本属于一个分类的概率即为样本属于这个分类的各个原型的概率之和,即为:

    应用 cross entropy,可以将最终的 loss 函数写出来:

    这个 loss 相当于换了一个角度考虑,把距离换成了概率然后代入 cross entropy。

Generalized CPL with prototype loss(GCPL)

除了上述的 loss 之外,作者还提出了一种可以加入上述 loss 中的约束方法。作者给的理由是,由于 CPL 中的参数比较少(因为 CNN 的参数本来就不多),很容易过拟合,因此需要这么一个约束来防止 overfit 情况的发生:

这个式子的意义是,计算在特征空间内样本的位置与对应分类的原型(且为距离最近的一个原型)位置的距离。利用这个约束,可以将前文提到的几种 loss 记为:

上式中的 $\lambda$ 作用是控制此约束的强硬程度。通过这个约束,可以让同类的原型间的距离更近,不同类的原型间的距离更远。与此同时,就能保证样本在特征空间中的类内距离更近,类间距离更远。

实验结果

基于以上方法,作者在 MNIST、CIFAR-10、OLHWDB 数据集上进行了实验。其中,OLHWDB 数据集是一个大规模的中文手写文字数据集,甚至比 ImageNet 还要大。(不过我觉得作者还是应该在 ImageNet 上进行实验,不然整个实验还是不够完整。另外,作者的实验虽然都很置信且完善,但是对比实验选择的 baseline 不够 solid,只用了最基本的 softmax 作为对比,没有考虑最近几年涌现出的各种 softmax 的进阶版。)

基本分类实验结果

  • MNIST:

  • CIFAR-10:

  • OLHWDB

可以看到,结果还是不错的,至少证明这篇文章提出的方法在最基本的分类效果上不会比 softmax 差。

拒识实验

这个实验结果比较亮眼。最近对模型的“拒识能力”的要求越来越高,所谓拒识,就是在输入 invalid 的测试样本时,模型可以判断出这个是 out-of-domain 的东西,返回拒绝的结果。

作者的实验方法是,在 MNIST 上进行训练,然后混入 CIFAR 数据集的数据来测试模型的拒识能力。在这种 open-domain 的实验中,我们经常会用某种类似于 min-confidence 的指标来判断送入的数据是不是 out-of-domain,但是像传统的 softmax + cross-entropy 方法中,min-confidence 越大,拒识率虽然会增加,但是准确率却也会明显下降。

作者提出的方法由于让不同类别的特征分布非常紧密,留出了大量的类间空间,因此在拒识率这块效果很好。

不过这个实验结果表格还是很微妙,因为每一横行参数啥的都不一样,虽然是为了做 AR 和 RR 的 trade-off 研究,但这样放着还是很奇怪。

类增量实验

这个实验其实还不是很常见,一般在 life-long learning 相关的工作里会有这个实验。目的是,测试一个模型在训练完成后新增一个类别的能力。对于标准的 softmax + cross-entropy 来说,自然不存在这一种能力,原因可以参考这篇笔记的第一个图,本来各个类就离的近了,再加一个类直接就乱套了。

而本文的方法,可以在“基本分类实验”一章的图中看出,样本按照类原型聚集的非常紧密。这样新增一个类并不是什么很困难的事。

作者的实验方法是,在 MNIST 训练出的模型中,增加 CIFAR-10 的类。可以看上图,做出来的结果依然很不错。

小样本训练

这个实验其实槽点也是 baseline 太 weak 了。现在做小样本的模型其实不占少数,但作者还是只选了 softmax 做比较。尽管如此,可以看到 GCPL 的效果还是很不错的。

多原型实验

前面的所有实验都是在“一个类别对应一个原型”的设定之下完成的,都有不错的效果。作者在文章最后用“一个类别对应多个原型”的假设进行了实验,结果如下表所示:

可以观察到,一个类别对应的原型数量其实对结果没有太大的影响。作者给出的解释是,CNN 提取特征的能力已经足够强大,即使初始数据的分布非常复杂,经过 CNN 变换之后,依然可以得到符合单高斯分布的特征分布,也就是一个类别一个原型的分布。

不过,在更复杂的情景下,一些更复杂的分类状况,多原型可能会发挥它应有的作用。

这块其实也是 trade-off。因为增加一个原型相当于在隐层输出时增加了 Dense Node,会极大地增加空间占用和计算量。

总结

这篇文章提出的方法足够新颖,并且取得的结果也非常好。虽然实验部分有些小遗憾(没有和各个任务顶尖的方法对比),但是仍然体现了这篇文章方法的综合性能的优越性。

够标题党吧?既然你点进来了,那我也得说一些干货了!毫无疑问,WebPageTest 是我最喜欢的 Web 性能测试工具之一。它功能强大、完全免费,为世界各地的网页提供测试。

如果你曾经用过 WebPageTest,那你应该知道它是多么的好用:只需要几下点击就能得到你网站加载的详细信息。不过,它还有一些你可能闻所未闻的功能!

最近我在 Santa Clara 参加了 Velocity Conference,偶遇了 Pat Meenan(WebPageTest 的创始人)并问了一些关于 WebPageTest 的问题。在本文中,我将列出 WebPageTest 的 10 个最酷的功能(我自己评的),希望你还没有用过它们。按照钓鱼文的标准套路,本文章节的标号会从 10 开始数。

Read more »

1

使用 Ionic 与 Angular 有许多方法可以让你在你的 app 中制作动画。你可以直接使用 Angular Animations,也可以使用其它的包(仅需几分钟就能装好)来实现动画。

在本文中我们将介绍 5 个不同的动画包,可以轻松地将它们引入你的 APP,使用它们预设的动画或者利用这几个框架轻松自定义动画效果。

Read more »

1

为了加密互联网流量中未被加密的最后一部分,我们与 Cloudflare DNS 合作进行了一个试点项目。这个试点项目利用安全传输层协议(即 TLS,一种被广泛应用的、经过时间证明的机制,可用于双方在不安全信道上建立通讯时,为通讯提供身份认证及加密)与 DNS 进行结合。这个 DNS over TLS(DoT)方案能够加密并验证 Web 流量的最后一部分。在 DoT 测试中,人们可以在浏览 Facebook 时使用 Cloudflare DNS 享受完全加密的体验:不仅是在连接 Facebook 时用的 HTTPS 时进行了加密,而且在 DNS 级别,从用户计算机到 Cloudflare DNS、从 Cloudflare DNS 到 Facebook 域名服务器(NAMESERVER)中全程都采用了加密技术。

Read more »

NIPS 2000 经典论文 非负矩阵分解算法 翻译

摘要

非负矩阵分解(NMF)是一种可以有效处理多变量数据的方法。本文介绍、分析了两种不同的 NMF 算法,这两种算法仅在更新规则(update rule)中使用的乘性因子(multiplicative factor)有所区别。其中一种可以对传统的最小二乘误差进行最小化(minimize),而另一种可以对广义 Kullback-Leibler 散度(KL 散度)进行最小化。可以使用与证明最大化期望算法收敛性类似的辅助函数来证明这两种算法的单调收敛性。这两种算法均可理解为用斜向最陡下降法(diagonally rescaled gradient descent)对因子进行最优化,以保证算法收敛。

简介

PCA、矢量量化(Vector Quantization)等无监督学习算法可以理解为在不同约束条件下对数据矩阵进行分解。根据其约束的不同,分解所得的因子的会表现出大相径庭的性质。比如,PCA 仅使用了弱正交约束,从而得到非常分散的表示,对这些表示使用消去法来产生多样性;矢量量化使用一种严格的全局最优型约束,最终会得到互斥的数据聚类原型。

我们之前已经证明过,在矩阵分解用于学习数据的部分表示中,非负性(non-negative)是一种非常有用的约束。学习得到的非负基向量是分散的,但仍可通过稀疏的组合,在重建时得到效果良好的表达向量。在本文中,我们详细分析了这两种用于在数据中学习最优的非负因子的数值算法。

非负矩阵分解

下面我们正式开始分析如何用算法解决以下问题:

在非负矩阵分解(NMF)中,给定非负矩阵V,找到非负矩阵因子W和H,使得:

NMF 可以应用下面的方法用于对多变量数据进行统计分析。给定一组多变量的 n 维数据向量,其向量位于一个 $n\times x$ 矩阵 V 的列中(m 表示数据集中的示例数)。然后将此矩阵近似分解为 $n\times r$ 的 W 矩阵与 $r\times m$的 H 矩阵。通常 r 要小于 n 或 m,以使 W 和 H 小于原始矩阵 V。最终得到的是原始数据矩阵的压缩形态。

公式(1)中约等于的意义在于它可以将公式逐列用 $v\approx Wh$ 来表示,其中 v 和 h 是矩阵 V 和矩阵 H 的对应的列。也就是说,每个数据向量 v 近似地由矩阵 W 的各列线性组合而成,同时用 h 的分量进行加权。因此可以被认为 W 包含了对 V 中的数据的线性近似优化的基向量。由于要使用少量的基向量来表示大量的数据向量,因此只有在基向量发现数据中的潜在结构时才能实现较好的近似。

本文不会涉及关于 NMF 的应用,而会侧重于在技术方面探讨非负矩阵分解的技术。当然,已经有许多其它的矩阵分解方式在数值线性代数中得到了广泛的研究,但是以前的大多数工作都不适用于非负性约束情况。

在此,我们讨论了基于迭代更新 W 和 H 的两种 NMF 算法。由于这两种算法易于实现,同时能保证其收敛性,因此它们在现实情况中非常实用。其他算法可能在总计算时间方面更有效率,但是更难实现,并且很难推广到不同的代价函数(cost function)。因子与我们类似的算法,已经被用于对发射断层扫描和天文图像进行反卷积(deconvolution)。

在我们算法的每次迭代中,会用当前值乘某些取决于公式(1)中的“近似程度”的因数,来找到 W 或 H 的新值。我们可以证明“近似程度”会随着不断应用这些乘法更新规则而单调减小。这正意味着更新规则的重复迭代可以保证矩阵分解算法收敛到局部最优。

代价函数

为了找到$ V\approx WH $的近似解,我们首先需要定义一个代价函数,用以量化近似的程度。可以使用两个非负矩阵 A 和 B 的距离来构造此代价函数。一种使用的距离度量方法为:计算 A 和 B 之间的欧几里得距离(Euclidean distance)的平方值。

此公式下界为 0,仅当 A=B 时距离消失。

另一种实用的度量方式为:

与欧几里得距离相同,它的下界也为 0,且在 A=B 时距离消失。但它不能被称为“距离”,因为这个式子在 A 与 B 中并不对称,因此我们将其称为 A 对于 B 的“散度”(divergence)。它可以归纳为 KL 散度或者相对熵,当 $\sum_{ij}A_{ij}=\sum_{ij}B_{ij}=1$ 时,A 与 B 可以看做是标准化的概率分布。

现在,我们可以按照以下两种公式来将 NMF 化为最优化问题:

最优化问题1:在约束条件 $W, H \geq 0$ 下,以 W 和 H 作为参数,最小化 $||V - WH||^2$。

最优化问题2:在约束条件 $W, H \geq 0$ 下,以 W 和 H 作为参数,最小化 $D(V||WH)$。

虽然方程 $||V - WH||^2$ 和 $D(V||WH)$ 在只考虑 W 或 H 之一时为凸,但在同时考虑 WH 两个变量时不为凸。因此,寻找一种可以找到全局最小值的算法去解决以上两个最优化问题是不切实际的。但是,还有许多数值优化方法可以用于寻找局部最小值。

虽然梯度下降法(Gradient descent)的收敛速度很慢,但它的实现最为简单。其它方法(比如共轭梯度法)可以更快地收敛(至少在局部最小值附近会更快),但是它们比梯度下降更复杂。此外,梯度下降方法的收敛对步长的选择非常敏感,这对于大规模应用十分不利。

乘法更新规则

我们发现在解决上述两个最优化问题时,在速度与实现难度中权衡,“乘法更新规则”是一种综合性能很好方法。

定理1:欧几里得距离 $||V-WH||$ 在下面的更新规则中呈非增:

在上述更新规则中,W 与 H 在距离公式的驻点上时,欧几里得距离将固定不动。

定理2:散度 $D(V|WH)$ 在下面的更新规则中呈非增:

在上述更新规则中,W 和 H 在散度公式的驻点上时,散度将不再更新。

上述定理的证明将在后面给出。我们可以发现,每次更新都是乘以一个因子。特别地,当V = WH时,可以直观地看出这个乘数因子是一样的,当更新规则固定时,才会得到完美的分解。

乘法与加法更新规则

可以将乘法更新与梯度下降更新进行对比。特别的,对 H 进行更新以减小平方距离可以记为:

如果将 $\eta_{a\mu}$ 设置为较小的正数,上式就和常规的梯度下降等价。只要数字充分小,就能在更新时减小 $||V-WH||$。

如果我们按照斜向最陡调整变量,并设置:

就能得到定理 1 中给出的 H 更新规则。注意,该调整可得出乘性因子(分母中的梯度的正分量和因子的分子中的负分量的绝对值)。

对于散度公式,我们按照下述公式调整斜向最陡梯度下降:

同样的,如果将 $\eta_{a\mu}$ 设置为较小的正数,上式就和常规的梯度下降等价。只要数字充分小,就能在更新时减小 $D(V||WH)$。如果设置:

那么就能得到定理 2 中给出的 H 更新规则。该调整可得出乘性因子(分母中的梯度的正分量和因子的分子中的负分量的绝对值)。

由于我们对 $\eta_{a\mu}$ 的取值并不够小,看起来不能保证这种调整过后的梯度下降的代价函数减小。不过让人惊讶的是,如下节所示,上述假设是事实。

收敛证明

我们将使用一个类似于 EM 算法的辅助函数来证明定理 1 与定理 2。

定义 1:$G(h,h’)$ 是 $F(h)$ 的辅助函数,满足以下条件成立:

根据下面的引理,此辅助函数是一个有用的概念。(在图1中的插图也显示了这一点)

引理 1:如果 G 为辅助函数,则 F 在下述更新时为非增:

证明:$F(h^{t+1}) \leq G(h^{t+1}, h^t) \leq G(h^t,h^t) = F(h^t)$

请注意,只有在$h^t$为$G(h,h^t)$的全局最小值时满足$F(h^{t+1})=F(h^t)$。如果 F 的导数存在,且在$h^{t}$的邻域连续,也就是说$\nabla F(h^t) = 0 $。因此通过公式11反复更新,我们就能得到目标函数收敛的局部最小值 $h_{min} = \arg\min_h F(h)$

-w663

下面,我们证明如何为$||V-WH||$与$D(V,WH)$定义适当的辅助函数$G(h,h^t)$。定理 1 与定理 2 可以直接遵循公式 11 的更新规则。

引理 2:如果$K(h^t)$为对角矩阵,

的辅助函数。

证明:因为显然 $G(h,h)=F(h)$,因此只需证明 $G(h,h’) \geq F(h)$。为了证明此不等式,需要将

与公式 14 进行对比,发现 $G(h,h’) \geq F(h)$ 等价于

为证明半正定情况,考虑矩阵:

仅是$K-W^TW$的调整形式。因此,仅当 M 符合下列公式时,$K-W^TW$具有半正定性:

现在,我们可以证明定理 1 的收敛性。

定理 1 证明:使用公式14的结果替换公式11中的$G(h,h^t)$,得到更新规则:

因为公式14为辅助函数,根据引理1,F 在更新规则中为非增。将上式完整的写下来,可以得到:

反转引理 1 与引理 2 中 W 和 H 的角色,F 可以以类似的方法证明在 W 的更新规则下为非增。

接下来,我们为散度代价方程寻找辅助函数。

引理 3:定义

的辅助函数。

证明:因为显然 $G(h,h)=F(h)$,因此只需证明 $G(h,h’) \geq F(h)$。我们通过对数函数的凸性来推导此不等式:

上式对所有的联合求合数 $a_a$ 均成立。设

可以得到:

上面的不等式遵循 $G(h,h’) \geq F(h)$。

定理 2 的证明遵循引理 1 及其应用:

定理 2 证明:要令 $G(h,h^t)$ 最小化,则需要将梯度设为 0 来求出 h:

因此,公式 11 采取的更新规则应当如下所示:

因为 G 为辅助函数,公式 28 中的 F 在更新规则中为非增。用矩阵形式重写上述公式,发现与 公式 5 的更新规则等价。反转 W 和 H 的角色,可以以类似的方法证明 F 在 W 的更新规则下为非增。

讨论

我们已经证明了在公式 4 与公式 5 中应用更新规则,可以找到问题 1 与问题 2 的局部最优解。借助定义合适的辅助函数证明了函数的收敛性。我们将把这些证明推广到更复杂的约束条件下去。更新规则在计算上非常容易实现,有望进行广泛的应用。

感谢贝尔实验室的支持,以及 Carlos Brody, Ken Clarkson, Corinna Cortes, Roland Freund, Linda Kaufman, Yann Le Cun, Sam Roweis, Larry Saul, Margaret Wright 的帮助与讨论。

概述

提取关键词将得到一系列的词库,要将这些词应用于文本筛查、分类则必须要对这些词进行拆分、组合,形成特定的规则,再应用这些规则对文本进行匹配,得到某文本所对应的模式。

要生成规则,即需要从系列关键词通过某些算法找出在不同样本文本下关键词的共有特征(或规律),再对多种特征(或规律)进行组合得到某种策略,最终通过策略对目标文本进行判定。因此关键词规则生成可以总结为以下几个主要步骤:

  1. 关键词特征或规律查找
  2. 策略生成
  3. 策略优化与化简

对于关键词特征与规律的查找,可以视为机器学习中的分类问题的反向过程。分类问题简要来说即给定标注样本,通过特征训练,得到一个可适用于同类样本的分类策略。常用的分类方法包括决策树、SVM、神经网络等方法。

决策树算法是常用的数据分类算法。决策树算法具有以下优点:

  1. 决策树算法中学习简单的决策规则建立决策树模型的过程非常容易理解
  2. 决策树模型可以可视化,非常直观
  3. 应用范围广,可用于分类和回归,而且非常容易做多类别的分类
  4. 能够处理数值型和连续的样本特征

由于它生成分类策略的可解释性,以及树状结构的可编辑性,在本步骤中可选用决策树算法作为样本分类策略。

下图为对某样本文本进行决策树(CART)生成的分类器策略可视化图像:

-w889

可以从图片中看出,决策树算法根据样本标注训练而成了对应的基于关键词的文本分类器。此分类器策略为清晰的树状结构,每个节点代表一个判断条件,每个树杈代表一个条件分支。为了得到在特定计算性能高、可解释性更好的策略,需要对其进行进一步的策略挖掘及精简。

由于决策树得到的策略为树状结构,因此在这种结构上的进一步策略挖掘可选用盲目搜索算法;又由于此模型为树状结构,最终分类落于叶子节点中,故采用深度优先搜索(DFS)对此树的路径进行检索,进一步优化策略。

在决策树得到的规则通过深度优先搜索之后,会得到一系列的组别,每个组别中包含各个关键词的“与”和“或”两种逻辑关系。在目标文本中使用时,即可通过这些逻辑关系的匹配找出对应的模式。

但由于决策树得到的策略叶子节点通常较多(如上图所示),通过深度优先搜索得到的策略也非常繁杂,最终生成得到的规则也会非常复杂,因此还可以进行进一步的策略化简。

在此步骤中,实质上是对多个逻辑代数运算及逻辑代数复合运算组合而成的逻辑函数进行化简。逻辑函数的化简方法一般有如下三种:

  1. 公式化简法
  2. 卡诺图法
  3. Q-M 法

由于在此步骤实际应用时逻辑规则较为繁杂,且“与”—“或”逻辑对较多,比起公式化简法或卡诺图法,Q-M 算法在选取出可以覆盖逻辑规则真值的最小质蕴涵项时更能发挥优势。

最终,通过决策树算法生成树、对决策树进行深度优先搜索得到包含“与”、“或”的分类逻辑、对分类逻辑应用 Q-M 算法,最终得到了包含“与”、“或”、“非”三种逻辑关系的可解释性强、精简的规则。

决策树

决策树是一个树结构,其每个非叶节点表示一个特征属性上的测试,每个分支代表这个特征属性在某个值域上的输出,而每个叶节点存放一个类别。运用决策树进行决策的过程就是从根节点开始,测试待分类项中相应的特征属性,并按照其值选择输出分支,直到到达叶子节点,将叶子节点存放的类别作为决策结果。

决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法,首先对数据进行处理,利用归纳算法生成可读的规则和决策树,然后使用决策对新数据进行分析。本质上决策树算法是通过一系列规则对数据进行分类的过程。

决策树算法构造决策树来发现数据中蕴涵的分类规则.如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树构造可以分两步进行:

第一步,决策树的生成:由训练样本集生成决策树的过程。一般情况下,训练样本数据集是根据实际需要有历史的、有一定综合程度的,用于数据分析处理的数据集。

第二步,决策树的剪枝:决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修下的过程,主要是用新的样本数据集(称为测试数据集)中的数据校验决策树生成过程中产生的初步规则,将那些影响预衡准确性的分枝剪除。

在第一步决策树的生成中,需要确定树杈的分裂属性(即在多个自变量中,优先选择哪个自变量进行分叉)。而采用何种计算方式选择树杈决定了决策树算法的类型,典型的分裂属性的选择的方法有 ID3 算法、C4.5 算法、CART 算法三种,三种决策树算法选择树杈的方式是不一样的。

ID3 算法

ID3 算法是目前决策树算法中较有影响力的算法,于 1986 年由 Quinlan 提出。该算法只是一个启发式算法。ID3 算法的核心是判断测试哪个属性为最佳的分类属性。ID3 算法选择分裂后信息增益最大的属性进行分裂,以信息增益度量属性选择。ID3 算法中常用到的两个概念是熵和信息增益。

熵是刻画任意样本例集的纯度,如果目标属性具有 m 个不同的值,那么 D 相对于 m 这个状态的分类的熵定义为:

其中 Pi 表示 Pi 是 m 类别的比例。

一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低,更精确来讲,一个属性A相对样本例集合S的信息增益 Gain(S,A) 被定义为:

A 对 D 划分的期望信息为:

ID3 算法不足之处是只能处理离散型数据,信息增益的选择分裂属性的方式会偏向选择具有大量值得属性。

C4.5 算法

ID3 算法在实际应用中存在一些问题,于是 Quilan 在保留 ID3 算法优点基础上提出了 C4.5 算法,C4.5 算法只是 ID3 算法的改进算法。C4.5 算法采用最大信息增益率的属性被选为分裂属性。C4.5 算法中用到了“分裂信息”这一概念,该概念可以表示为:

信息增益率的定义是:

C4.5 算法是对 ID3 算法的一种改进,改进后可以计算连续型属性的值。对于连续型属性的值,只需将连续型变量由小到大递增排序,取相邻连个值的中点作为分裂点,然后按照离散型变量计算信息增益的方法计算信息增益,取其中最大的信息增益作为最终的分裂点。

C4.5 算法继承了 ID3 算法的优点,并在以下几方面对 ID3 算法进行了改进:

  • 用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足;

  • 在树构造过程中进行剪枝;

  • 能够完成对连续属性的离散化处理;能够对不完整的数据进行处理。

CART 算法

CART 算法选择分裂属性的方式首先要计算不纯度,然后利用不纯度计算 Gini 指标,然后计算有效子集的不纯度和 Gini 指标,选择最小的 Gini 指标作为分裂属性。

由于 CART 算法在处理离散数据上具有优势,因此对于关键词规则的生成可选用此方法生成决策树。

深度优先搜索算法

搜索算法可分为盲目搜索算法和启发式搜索算法两种,二者的区别在于:启发式搜索算法的每一步都试图向着目标状态方向进行搜索,而盲目搜索算法则是每一步按照固定的规则进行搜索,然后判断是否达到目标状态。相比之下,启发式搜索算法克服了盲目搜索算法的盲目性问题。

虽然启发式搜索算法可以解决盲目搜索算法的盲搜索问题,但是在实际问题求解中,缺少一些必要的信息来构建启发式搜索算法,此时采用盲目搜索算法仍然是解决问题的有效手段。盲目搜索算法有两种:一种按照广度优先展开搜索树的搜索算法,叫广度优先搜索法;另一种则是按照深度优先展开搜索的搜索算法,叫深度优先搜索法算法。

深度优先搜索算法是优先扩展尚未扩展的且具有最大深度的节点;广度优先搜索法是在扩展完第 K 层的节点后才扩展 K+1 层的节点。在此应用深度优先搜索算法。

假设初始状态是图中所有顶点未曾被访问,从图中某个顶点 i 出发,访问此顶点,然后依次从 i 的未被访问的邻接点出发深度优先遍历图,直至图中所有和 i 有路径的顶点都被访问为止。若此时图中尚有顶点未被访问,则另选图中未曾访问的顶点为起始点,重复上述过程,直至图中所有顶点都被访问为止。在节点遍历过程中,应该注意节点的回溯搜索以及避免节点被重复搜索。

在搜索过程中,如何避免被搜过的节点不被重复搜索以及节点的回溯是主要难点。根据关联矩阵以及深度优先搜索算法,从节点 i 搜索出节点 j,如果节点 j 已经被搜索过,那么修改关联矩阵中对应节点 i 和节点 j 的元素为 0,并返回节点 i 重新搜索与之相联的另一节点。当节点 j 是该条树枝的最后一个节点时,修改关联矩阵中相应的元素,并且返回节点 i 重新搜索与之相连的另一树枝。依此类推,直至遍历所有节点,也就是关联矩阵的所有元素都变为 0 时,停止搜索。在遍历各节点的同时,根据节点的先后顺序以及树枝集合,合理地安排各节点坐标。其搜索过程逻辑如下图所示:

-w241

Q-M 算法

在得到只包含“与”、“或”的逻辑函数之后,可对逻辑进行更进一步的简化与合并,并加上“非”逻辑来使得逻辑函数更具解释性。

下图为一个简单逻辑函数的卡诺图,101 项被覆盖了 3 次,明显可对函数进行化简。

-w386

Q-M 算法是由 Quine 和 Mccluskey 提出的一种系统列表化简法。这种化简方法和卡诺图化简法的基本思想大致相同, 是通过找出函数 F 的全部质蕴涵项、必要质蕴涵项以及最简质蕴涵项集来求得最简表达式。

下面为蕴含项与质蕴涵项的定义:

蕴涵项:在函数的“与”—“或”表达式中,每个“与”项被称为该函数的蕴涵项。显然在函数卡诺图中,任何一个 1 方格所对应的最小项或者卡诺圈中的 $2^n$ 个 1 方格所对应的“与”项都是函数的蕴涵项。

质蕴涵项:若函数的一个蕴涵项不是该函数中其它蕴涵项的子集,则此蕴涵项称为质蕴涵项,简称为质项。显然在函数卡诺图中,按照最小项合并规律,如果某个卡诺圈不可能被其它更大的卡诺圈包含,那么该卡诺圈所对应的“与”项为质蕴涵项。

必要质蕴涵项:若函数的一个质蕴涵项所包含的某一个最小项不被函数的其它任何质蕴涵项包含,则此质蕴涵项被称为必要质蕴涵项,简称为必要质项。在函数卡诺图中,若某个卡诺圈包含了不可能被任何其它卡诺圈包含的 1 方格,那么该卡诺圈所对应的“与”项为必要质蕴涵项。

一般的化简步骤是:

第一步:将函数表示成“最小项之和”形式,并用二进制码表示每—个最小项。

第二步:找出函数的全部质蕴涵项。先将 n 个变量函数中的相邻最小项合并,消去相异的—个变量,得到 (n-1) 个变量的“与”项,再将相邻的 (n-1) 个变量的“与”项合并,消去相异的变量,得到 (n-2) 个变量的“与”项。依此类推,直到不能再合并为止。所得到的全部不能再合并的“与”项(包括不能合并的最小项),即所要求的全部质蕴涵项。

第三步:找出函数的必要质蕴涵项。

第四步:找出函数的最小覆盖。