第10章模式识别的理论与方法

1、数字图像处理学数字图像处理学 第第10章章 模式识别的理论模式识别的理论 和方法和方法 （第五讲）（第五讲） 5 句法结构的分类与聚合的基本概念句法结构的分类与聚合的基本概念 （） 最小距离分类 最小距离分类是研究句子之间的距离，根据距离大 小来分类。 m , , , 21 m xxx , , , 21 ) ,(yxd i ), ,(yxd i W mi , 2, , 1 jiyxdyxd ji ) ,() ,( (1050) 则指定y为 类。 i 假设有m个模式类 。每一类有一个模板链， 共有m个模板 。当输入一个链y时，则可计算 利汶施坦距离 或加权利汶施坦距离 。 如果： （） 最近邻域

2、分类 对于m个模式类 ，每一类中有若干 个模板链 1, , , 2 m xxxxim iiii n , 12 1 2 , 计算 或 ，如果：d xy i k (,) dxyin W i k (,), 2, , 1 min (,)min (,) k i k i l d xyd xy (1051) 则指定y为 类。 i 图1023 度量W的图示 （） 句子到句子的聚合 如果输入是一组样本 ， 输出要x分成m个聚合，可按下述步骤进行： xxxxn , 1 , 2 1) 令jm11, ，指定x j到Cm类； 2) 将j增加1，对所有的i计算 mixxdD jli 1 ,(min 1 令DD ki mi

3、n()，如果Dt k 则指定 x j 到 k C类 ，则对 建立了一个新类别，m再增加1。这 里t是某一阈值。 Dt k x j 3) 重复第二步，直到中每一样本都被指定到一类为 止。 在利用距离的概念时，需要在一类中找到一个或 少数几个基本样板作参考，如果这一要求作不到， 就需要很多样板作参考，这就要存储许多句子，此 时就不如用文法推断了。 6 误差校正剖析误差校正剖析 （）（） 最小距离误差较正剖析程序最小距离误差较正剖析程序 这是一种算法。设 是一个给定的语言，y是给定 的句子。最小距离误差校正剖析的实质是在L(G)中寻 找一个句子x，使它满足下述的最小距离准则。 L G( ) d x

4、yd z yzL G( ,)min ( , )( ) (1052) 在这里x称为y的误差校正链。 例如：对一个上下文无关语言的误差校正剖析可采用 如下方法。如果有一个语言L(G)，现在有一条链y，y 有两种可能性，一是y在L(G)中，另外是y在L(G)外面。 第一种情况可能是由于噪声的原因使y在L(G)内部换 成了另一个句子。第二种情况是原来的文法就不能产 生y。 在第二种情况下，可将原来的文法扩大，用改变产 生式的方法将三种误差加进去，使扩大了的文法产 生的语言包括受噪声影响的链，然后用扩大了的文 法 去剖析y，y可以被 接受，而且可以知道 最少用了几次误差转换。最后再把所用到的误差转 换式

5、去掉，就可得到L(G)中的链x，x就是y的误差 校正链。 G G 扩大的文法可用如下方法构成： 假如给定一个上下文无关文法 GVVPS NT , , 扩大的文法为 GVVPS NT , , 则 1) VVSEaVVV NNaTTT , 2) 如果如果 是是P中的一个产生中的一个产生 式，式， 。于是把。于是把 合到合到 中去，其中中去，其中 是一个新的非终止符。是一个新的非终止符。 0, 2110 mbbbA mm aVbV iNiT * , AEEE bbbmm 0112 P EV biN * 3)在 中加入下列产生式：P SS SS a 对所有的 aVT Ea a 对所有的aVT Eb a

6、 所有 ba V T Ea EbE aa 所有bVT 在求链与语言之间的距离过程中，结构分析用扩大的 文法 设计。 G （） 最近邻域结构识别 如果有两个模式类 和 ，分别用文法 和 加以 描述。输入链y，如果 12G1G2 d L Gyd L Gy (), (), 12 (1053) 则判定y是 类。如果1 d L Gyd L Gy (), (), 21 (1054) 则判定y属于 类。2 若有m类，就应把每类文法都扩大，然后进行剖析。记下每类 文法剖析所用的误差转换次数，这就表示输入y和每类之间的距 离。最后检测与某类语言的距离最小，则y属于该类。除了决定 y属于哪一类外，还可以知道y的误

7、差校正链。 这种结构识别，首先要知道各类文法，有了原 来的法G去产生扩大的文法 ，再进行剖析， 所以叫ECP（Error Correcting Parsing）。 G 分类器框图如图1024所示 （） 句法模式聚合步骤 如果有n个样本 ，首先对 推断一 个文法 ，然后将 和 作误差校正剖析， 计算 和 的距离，如果距离较小，则将 和 分为一类，重新推断包括 和 的文法 ；如果距 离较大，则将 另立一类，并推断第二类文法 。 xxxn 12 , x1 G1 1( ) x2G11 ( ) x2 L G() ( ) 1 1 x1x2 x1 x2G21 ( ) x2 G1 2( ) 这样对样本依次作下

8、去，直到每个样本 都被分到某一类中去。每一类中，每次 有新的链加进来，就重新推断这一类文 法。结果，n个样本被分到m类中，并形 成m类文法。综上所述，聚合步骤可归纳 如下： 1） 从 推断文法 ； 2） 为 构造一个误差校正剖析 ； 3） 用 确定 是否与 相似，如果 和 相似， 则归入一类且从 推断文法 ，如果 和 不相似， 则从 推断文法 ； x1 G11 ( ) G1 1( ) A1 1( ) A 1 1( ) x2x1x1 x2 ,xx 12 G21 ( ) x1 x2 x2 G1 2( ) G21 ( ) ）重复步骤（2），为 构造 或为 构造 ； ）对新样本重复步骤（3），直到所有

9、样本都 考虑到为止。 A21 ( ) G1 2( ) A1 2( ) G21 ( ) ）代替误差 （） 随机误差校正剖析 随机误差校正剖析是在误差产生式增加了概率值的 剖析方法。按照误差转换的符号，与 、 、 三类 转换相关联的畸变概率可定义如下： TS TI TD 2121 )(, b abqT a SS )(abqS b a ba 其中，是用代换 ，且的概率。 ）抹去误差 ）插入误差 2121 )(, ba abqT a II 其中 是在a前边插入终止符b的概率。q b a I () 1212 a Tqa DD ,( ) qa D ( )a 其中是抹去的概率。 ）在一条链的末尾插入误差：

10、ax aqT x II )(, 其中， 是在一条链的末端插入终止符a的概率。 qa I ( ) 令 是a不发生误差的概率，可以认为它是在a上发生无误 差转换的概率。 qa a S () 假定对于每一个终止符最多只能有一个误差存在，如果 b V SD b V I TT qb aqaqb a ()( )()1 (1055) 且对于所有的 ba aVT 则这种单误差模型上的畸变概率是一致的。 下面可以通过一个例子来说明如何从一条链 畸变为另一条链 。畸变过程可由图1025来 说明。在图中，水平分支表示插入转换，垂直分支表 示抹去转换，对角线分支表示代换转换或无误差转换。 xa a a 123 yb

11、b b b 1234 b1a 1 b2 aa 12 , b3 a3b4 1234 11 223344 bbbb, qa a a q ba qba qaqbaqq b ISDSII () ()()()()()() 1234123 11112334 1 (1056) 当然，x畸变到y可以有很多路径，可以说畸变概率 是从B点到E点可能性最大的通路相联系的概率。 q y z() 图中，从点B到点E的每一条通路代表x畸变为y的一种 方式。粗线表示的是如下通路， 是 前的一个插入， 代换 被抹去， 代换 ， 插入到链尾。如果把 y分成 ，就可形成这种畸变，其 中 。这样就有 图 1025 用网络描述的随机

12、畸变模型 对于 ， 符号a号畸变 的概率可按下式计 算（畸变概率表示为 ） aVV TT , * )(aq )()(),(max)()( )()(),(max )( )( 11 aqabqabqabqabq baaqabqabq aq aq DLILSLII DIS D 如果 如果 如果1 , 1 lbb l (1057) 把)( * T V插入到一条链末尾的概率为 1,)()()()1 ( 1 )( 1 2 1 lbbabqbqbqq aq aq llIIII I 当 (1058) 假定 其 中 ， 则对于x畸变为y的概率如下 其中 )( aqq I Va I T )()()()( 1 11

13、21121 nnnnn qaqaqaaaq Tn Vaaa, 21 * 121 , Tnn Vaaaa q y xq aaq a i j n j i jn ()max()() 1 1 (1059) 其中， 是y分成n+1段子链的一种 划分。 0, 121 i j i n i n ii a aa a a （） 最大似然误差校正剖析 设 是一个随机上下文无关语言，另外有一条噪声 链y。可提出一个最大似然误差校正剖析算法，该算法 在于找出一条链x， ,使得 L G S () xL GS () q y x P xq y z P z z I GS () ( )max () ( ) () （1060） 的

14、计算可如前面介绍的方法进行。y要对 中每个句子 进行计算，然后指出畸变概率最大的情况，所以算法与ECP相 似。 L G S ()q y z() 首先构成随机扩展文法。方法如下： 输入一个随机上下文无关文法 GVVP S SNT , , 输出是一个随机扩展文法 GVVPS SNTS , , VVSE NNa a VT VV TT 0 , 2110 mabbabaA mm P P S ai VN *bi VTP S 0 , 2110 maEEaEaA mbmbb P bi E nbi VE (a) SS I q 1 , 其中 qqa I V I T I () (b) aSS aqI )( ，对于所

15、有的t Va 其步骤如下： 1) 2） 3)如果 是 中的一个产生式， 在 中， 在 中，于是在 中加入产生 式 ，其中每个 都是一 个新的非终止符， 。 4）在中加入下列产生式 5) 对于所有的 ，在 中加入下列产生式 (a) (b) , 对所有的 ; (c) (d) , 对所有的 aVTP S aE aaq a S )|( bE abq a S )|( bVba T , )(aq a D E a abq a bEE I )|( 假定y是x的一个误差畸变链， 。用第三步中加 到 的产生式，可知 bVT xa aan 12 P S 0 XS i S P G 其中 ，当且仅当 ，其中 是 中的第

16、i个导出式的概率。首先用步骤4)的(b)，可进一 步导出 ，其中 。如 果 ，是的一种划分，则步骤5)中的产生式 产生 ，对所有的 。 XE EE aaan 12 xS i S P G i PCS 1 n P G XaS i S PPq d iin ( ) 1 a aan 121 , S i aaq ai G aE ii )|( 1 in 步骤5)中的(a)、(b)、（c）、(d)分别对应于非误差 转换、代换转换、抹去转换和允许多重插入的插入 转换。于是，由 产生的随机语言是 S C )()()(,)(,()( 1 * xPxyqyPyPyGL i Gx r i Vy S S t (1061)

17、 其中r是从x导出y的相异转换序列的数目。 是与 第i个序列相联系的概率， 。 )(xyqi ri 1 于是，贝叶斯决策规则为 如果有两个句法模式 和 ，假设x在 中的概率为 是已知的，如果考虑贝叶斯分类，运用贝叶斯规则 可知x在第j类的后验概率为 C1C2 Ci PCi i ( ), 1 2 P Cx P x CP C P x C P C j jj i ii () () () () () 1 2 i=1,2 (1062) )()( )()( 212 211 xCPxCPC xCPxCPC x 如果 如果 (1063) 有时候往往会出现两个文法产生同一个句子的情况， 如 C1 类产生英文字母B

18、， C2 类产生数字8，在有 噪声干扰时，B和8可能在两类交叠处，也可能在两类 之外。对于交叠处的可以用随机文法计算概率，用最 大似然分类器解决。在两类之外可用最大似然误差校 正剖析来解决。 10.3.4 文法推断文法推断 在句法模式识别中，有两个问题比较困难，一是噪声和干扰， 另一个就是文法推断。文法推断是在解决了被研究模式的基元 提取问题后，研究如何构成能正确描述这类模式的文法。这实 际上是句法结构的学习问题。即从句子中学习文法，。由于模 式可分别用链、树、图来表示，所以就有链文法推断，树文法 推断以及图文法推断。 文法推断课题主要涉及推断一个未知文法的句法规则所 有的方法，推断的依据是产

19、生的语言中句子或链的一个 有限集合，也可能还有的补集中的链的有限集合。推断 出的文法是一种规则，它描述中的给定有限集合，并预 测给定集以外的链，这些链与给定集在某种意义上具有 同样的性质。文法推断的方框图如图1027所示。 1. 有限状态文法推断有限状态文法推断 有限状态文法可用下述方法实现：有限状态文法可用下述方法实现： 输入输入k个样本个样本 ， 。其。其 中中 ， 中不同的终止符中不同的终止符。对。对 个样本中的一条链个样本中的一条链 寻找其产生式寻找其产生式 。因为正规文法的产。因为正规文法的产 生式只有两种形式，即生式只有两种形式，即 及及 。 X Xxxxk , 12 xaaaa

20、iiiiin 123 ,VX V xiP i AaB A BVN( ,) Aa aVT() P i: Niii VZZaS 111 , , , 3332 2221 Niiii Niiii VZZaZ VZZaZ , , , , , , , ) 1(21 ) 1( ) 1() 1()2( )2()2()3( SPVVG ZZZSV aZ ZaZ ZaZ iTiNi niiiiN inni ninini ninini 所以对于每一条链，其产生式规则为: 上述方法可通过一个例子来说明。 例: 所以这个文法共有9个非终止符，2个终止符，12个产生式。 X ,01 100 111 0010 1 ,0 :

21、 01 1 0, 11111 1 ZZSP x VT x PSZZZZ 2 221212222 100 100 :, x PSZZZZ x PSZZZZZZ 3 331313232 4 4414142424343 111 111 0010 0010 :, :, VS ZZZZZZZZ N , 1121223132414243 2. 上下文无关文法的推断上下文无关文法的推断 在实用中，用有限数目的句子来推断文法一般总能用正规文 法产生这些句子。但是有时 会很大。如果采用上下文无关 文法来推断， 的数目会大大减小，因此，实现起来自动机的 状态也会大大减少。 VN VN 上下文无关文法的推断大致有两

22、种方法，一种方法是 Pumping Lemma方法，另一种方法是采用具有结构性 样本的推断法。 VN 上下文无关的语言有一个特性，即如果一个句子可以 分成5段UVWXY，这个句子在 内，那么形如 的句子也在 内（UVWXY定理）。例如 ， 用人机对话的方式，逐个询问机器 是否在 内，如果机器回答 ，则检验 是否在 内，如果它们都在 内，则得到产生式 X UV WX Y kk X abaX a b aa ab ba, , X bX a baa baa ba kk2233 , X X 这种方法的缺点是需要大量的外界信息， X 中的句子也较多。 SaSa Sb 采用具有结构特性的样本的方法是不仅要知

23、道句子， 还要知道句子的结构。为说明方便起见，在此结构 用括弧来表示。 例如： ，结构信息为 。结构树如图 1028所示。产生这个句子的文法 的产生式为 xaaaX 1 aaa G1 Na NNN NNN SN 1 211 212 2 L Gaa aaa aaaa(), 1 xaaa 2 ()它的结构信息为 ( ) aaa 求出产生 的文法 的产生式 X 2 G2 Na NNN NN NNN SN 1 212 32 431 4 () L Gaaaaaaa( )(), (), L GGL GL G()()() 1212 这种方法需要知道句子的结构，这对于模式识别来说是 可以做到的。用这个方法推断

24、出的文法，由于基本模式 数目很少，可能得到的文法质量不高，但这个缺点可用 ECP来补偿。 3. 图文法推断图文法推断 定义正样本集 Xxxxh , 12 和负样本集 Xxxxi , 12 ，而XxxxXX n , 12 。 如果X 和 X 图文法规则如下： 拱型 分别是图1029所示的景物，希望有个文法 产生这个图形。此图的关系图如图1030所示。 第一个样本进来，只有A在B、C上，B在C的左边； 第二个样本进来，B与C不能靠得太近；第三个样本 进来，A一定在B、C上而不能在下面；第四个样 本等等。按上述步骤，从根向下不断加入新的关 系就可推断出图文法。 4. 树文法推断树文法推断 链可以看成

25、是只有一枝的树，而树是多枝的链。如果只对于 树支全从根开始的这种特殊形状的树，则可直接把链的方法搬 过来用。 5. 上下文敏感文法推断上下文敏感文法推断 对于上下文敏感的文法对于上下文敏感的文法(即上下文有关的文法即上下文有关的文法)还没有推断还没有推断 办法。对于这类问题可用两种办法解决，一种是上下文无办法。对于这类问题可用两种办法解决，一种是上下文无 关程序文法，另一种是用属性文法。关程序文法，另一种是用属性文法。 6. 关于属性文法关于属性文法 在属性文法中，每一个基元都由两部分组成，基元为在属性文法中，每一个基元都由两部分组成，基元为( )。 其中其中b表示名字，表示名字， 表示属性或

26、语义信息，这是识别基元的根表示属性或语义信息，这是识别基元的根 据。在使用产生式时，要考虑属性之间的关系。据。在使用产生式时，要考虑属性之间的关系。b Xb, X b 例如：图1031的树图，子模式为( )，B的属性由 a,b ,c 的属性得到。 。式中的 可能 是简单的函数，也可能是复杂的运算式。上例中的产 生式规则为 ，属性规则为 。 B XB, X B (,)XXX abc BabcXXXX Babc (,) 属性文法的优点在于当每个模式结构一样只是大小不同的情况， 可利用属性这一信息将二者分开。属性往往是识别基元时所需 要的特征量。属性并不限于一个量，可以是一组参量。属性的 计算顺序是从基元属性计算起，然后是子模式属性，再往上计 算模式属性。 例如 是上下文无关语言，基元如图 1032(a)所示，其所描述的图形如图1032 (b)所示的 两个三