N1+N2結(jié)構(gòu)語法關(guān)系判定的SVM算法

楊 泉

北京師范大學 漢語文化學院，北京 100875

短語是在語義和語法上都能搭配、沒有句調(diào)的一組詞，是造句的備用單位。短語層級的語法關(guān)系判定是中文信息處理領(lǐng)域的重要基礎性課題，其研究成果在信息搜索、自動問答、文本摘要等[1]諸多領(lǐng)域都有著較為廣泛的應用。N1+N2結(jié)構(gòu)是漢語中最為常見的短語結(jié)構(gòu)之一，對該結(jié)構(gòu)的研究也非常廣泛。在中文信息處理領(lǐng)域?qū)τ谠摻Y(jié)構(gòu)的研究目前涉及到查詢[2]、識別[3]等方面；在語言學領(lǐng)域涉及到對其語法功能、語義類型和使用情況等方面的考察、描寫和分析[4-5]，但是前人研究中對于該結(jié)構(gòu)語法關(guān)系自動判定的研究成果還鮮少得見。根據(jù)文獻[6]的研究成果，N1+N2結(jié)構(gòu)可以分成四種語法關(guān)系：定中關(guān)系、并列關(guān)系、復指關(guān)系和主謂關(guān)系，因此對于N1+N2結(jié)構(gòu)語法關(guān)系判定實際上就是一個多分類問題，而該多分類問題又可以轉(zhuǎn)化為一系列二分類問題。

支持向量機（Support Vector Machine，SVM）[7]作為一種強有力的二分類方法[8]，在文本分類[9-10]、信息檢索[11]、情感分析[12-13]、音字轉(zhuǎn)換[14]、搭配識別[15]等自然語言處理的諸多領(lǐng)域均取得了較為理想的計算結(jié)果。SVM方法對于非線性情形使用核技巧，將低維空間的數(shù)據(jù)映射到高維空間，然后在高維空間中進行基于最大間隔原則的線性學習，并使用二次規(guī)劃（Quadratic Programming，QP）技術(shù)獲得劃分超平面[7-8]。

N1+N2結(jié)構(gòu)語法關(guān)系判定屬于非線性分類問題，本文計劃在自建語料庫的基礎上，研究如何更好地利用支持向量機進行漢語短語語法關(guān)系分類，以期提高計算機理解自然語言的能力。

1 N1+N2結(jié)構(gòu)語料庫簡介

使用人工智能方法處理語言學問題離不開語料庫的支持，本研究自建語料庫，并為語料標注了語法、語義信息，具體建庫過程如下：

（1）語料獲取：從北京語言大學BCC語料庫（http：//bcc.blcu.edu.cn）自動提取N1+N2結(jié)構(gòu)語料共17 108條。

（2）語料清洗：首先去掉各類不合格語料，比如有些英文、動詞或成語當作名詞被抽取出來；另外還有重復語料也要去除，最后剩下合格語料共4 944條。詳細數(shù)據(jù)如表1所示。

表1 入庫語料各關(guān)系數(shù)量及占比表Table 1 Number and ratio of 4 relations in corpus

（3）語義標注：本文用《同義詞詞林》作為名詞語義標注體系（《同義詞詞林》是梅家駒等人早年編撰的漢語可計算詞庫，后經(jīng)哈爾濱工業(yè)大學研究人員對其進行擴展成為《哈工大信息檢索研究室同義詞詞林擴展版》，下文簡稱《詞林》），注方式采取Python編程自動標注。

（4）語法標注：為N1+N2結(jié)構(gòu)人工標注并校對定中、并列、復指、主謂四種關(guān)系。

至此，N1+N2結(jié)構(gòu)語料庫構(gòu)建完畢，具體樣例如表2所示。

表2 N1+N2結(jié)構(gòu)語料標注樣例表Table 2 Sample table of N1+N2 structure in corpus

表2中“代碼”是《詞林》中的語義編碼；dzp、blp、fzp、zwp分別表示定中、并列、復指、主謂四種語法關(guān)系。

短語的語法關(guān)系實際上就是其構(gòu)成詞的語義關(guān)系共性特征的抽象概括，N1+N2結(jié)構(gòu)內(nèi)部兩個名詞間的四種語法關(guān)系可以看作一個四分類問題。在機器學習算法中，有一大類算法可以解決分類問題，例如支持向量機就是解決分類問題的典型方法。支持向量機要求其輸入是數(shù)值向量的形式，所以無法直接對N1+N2結(jié)構(gòu)的漢語語料進行分類。要使用支持向量機，首先需要將N1+N2結(jié)構(gòu)轉(zhuǎn)換為數(shù)值向量的形式。根據(jù)前面分析，四種語法關(guān)系代表了不同名詞組成該短語時的不同語義關(guān)系，短語的語法關(guān)系是由其所構(gòu)成詞的語義類別和語義關(guān)系決定的。因而在轉(zhuǎn)換成向量時應重點考慮短語結(jié)構(gòu)中表示語義類別和語義關(guān)系的相關(guān)信息。本文在上述觀點的基礎上建立熟語料庫并生成短語結(jié)構(gòu)向量，利用支持向量機對N1+N2結(jié)構(gòu)中兩個名詞的語義類別和語義關(guān)系進行分類，進而判定該結(jié)構(gòu)的語法關(guān)系。

2 基于支持向量機的N1+N2結(jié)構(gòu)語法關(guān)系判定方法

2.1 支持向量機原理簡介

支持向量機是機器學習方法中應用最廣泛的分類方法之一。經(jīng)典的SVM是一種二分類方法，其基本框架為：

給定訓練樣本集T={(x1,R1),(x2,R2),…,(xm,R m)},其中xi為k維空間的樣本點，對應的標簽記為Ri∈{-1,+1}。當訓練集是線性可分時，則存在一個k維空間中的超平面可表示為公式（1）：

將兩類數(shù)據(jù)分開。顯然，可以劃分數(shù)據(jù)集的超平面可能不止一個，因此SVM是找到使數(shù)據(jù)集到超平面的幾何間隔最大化的最優(yōu)超平面。該平面滿足如公式（2）的優(yōu)化問題：

當數(shù)據(jù)在其樣本集空間中非線性可分時，則無法在原樣本空間中找到超平面，此時可以先用一個非線性映射把T中的所有樣本xi(i=1,2,…,m)映射到一個高維甚至是無窮維空間（特征空間）中，使其線性可分，然后在此高維空間中尋找超平面。

令φ(x)表示將x映射后的特征向量，在特征空間中劃分超平面所對應的模型可以表示為公式（3）：

由于φ(x)的維數(shù)一般較高，甚至是無窮維，所有直接求解特征空間中的超平面會面臨較大困難。因此SVM通過引入核函數(shù)κ(x,y)=φ(x)Tφ(y)，用原空間中的低維向量來計算其特征空間中高維向量的內(nèi)積。引入核函數(shù)的非線性SVM的對偶問題可以表示為公式（4）：

一般訓練SVM時需要求解一個大規(guī)模的二次規(guī)劃問題。常用的有序列最小最優(yōu)化算法、二次規(guī)劃方法和最小二乘方法等。

2.2 文本的特征選擇與向量化

SVM已經(jīng)是比較成熟和完善的算法，但要實現(xiàn)對N1+N2結(jié)構(gòu)語法關(guān)系的分類，首先需要將原始語料中的N1+N2結(jié)構(gòu)轉(zhuǎn)換為Rk空間中的向量x。本節(jié)介紹將原始語料轉(zhuǎn)換為向量的方法。

本文的語義標注體系——《詞林》使用8位編碼來表示詞語義項：第1、2、3+4位編碼代表大類、中類和小類，分別用1位大寫英文字母、1位小寫英文字母和2位十進制整數(shù)表示；第5、6+7位編碼代表詞群和原子詞群，分別用1位大寫英文字母和2位十進制整數(shù)表示；第8位編碼代表原子詞群中詞語之間的關(guān)系，用1位符號表示，＝、#、@分別表示詞語之間同義、相關(guān)、獨立的關(guān)系。表3詳細展示了《詞林》中的8位義項編碼體系。

表3 《詞林》義項編碼表Table 3 Code table of meanings in Cilin

《詞林》義項編碼是一種向量化的表示方法，其中蘊含了詞語的語義類別信息，這些語義類別也是語義關(guān)系的體現(xiàn)，在短語結(jié)構(gòu)內(nèi)部語義類別和語義關(guān)系對語法關(guān)系起到?jīng)Q定性作用，因此對于N1+N2結(jié)構(gòu)語法關(guān)系判定可以借助其內(nèi)部兩個名詞在《詞林》中的語義編碼進行。例如“單純性肥胖癥”是一個N1+N2結(jié)構(gòu)，對應的《詞林》編碼為“Ed35A01=Dl01A80#”，其語法關(guān)系dzp就是分類結(jié)果R。依此類推，每一個結(jié)構(gòu)都對應著一個由16個字符構(gòu)成的向量，而SVM需要使用數(shù)值化的向量進行計算，因此需要進一步把《詞林》編碼向量映射為數(shù)值向量。《詞林》編碼體系包含12個大類，95個中類，1 428個小類，共涉及65個不同的字母、數(shù)字和符號。將每一個符號用一個16位二進制編碼表示，則不同符號會有不同編碼，編碼示例見表4所示。

表4 16位二進制編碼示例表Table 4 Examples of 16 bit binary code

至此每一個《詞林》編碼組均可轉(zhuǎn)化為一個16×16=256位的二進制向量。而語料庫文本可轉(zhuǎn)化為標準訓練樣本集T={(x1,R1),(x2,R2),…,(xm,Rm)}，其中xi為256維取值是{0，1}的向量，Ri可取{1，2，3，4}分別代表{dzp、fzp、blp、zwp}四種不同的關(guān)系。顯然，在每一個結(jié)構(gòu)對應的256維向量中都包含大量的零元素，直接使用會影響支持向量機算法的收斂性和運行效率。

綜上，本文首先將數(shù)據(jù)集中全部結(jié)構(gòu)的向量構(gòu)成矩陣：X=[x1,x2,…,x m]T；然后，對該矩陣進行奇異值（SVD）分解：X=UDVT；最后，根據(jù)奇異值的大小分布，選取n個較大的奇異值對應的奇異向量作為最終用于結(jié)構(gòu)語法關(guān)系分類的向量。此時僅需在n維空間中尋找用于分類的超平面。一般通過奇異值分解進行準確降維后，能夠大大提高算法的運行速度和分類精度。

2.3 SVM判定N1+N2結(jié)構(gòu)語法關(guān)系方法

通過上文關(guān)于N1+N2結(jié)構(gòu)的關(guān)鍵特征提取與數(shù)量化表示，本文將待分類的短語結(jié)構(gòu)映射到了一個維數(shù)適中的向量空間中，同時也將短語結(jié)構(gòu)的語法關(guān)系用數(shù)量進行了表示。這樣從形式上已將文本及其對應的分類結(jié)果轉(zhuǎn)化為經(jīng)典SVM算法可直接使用的數(shù)值向量和數(shù)值，但有兩個關(guān)鍵問題需要進一步分析和研究。第一個關(guān)鍵問題是如何將經(jīng)典的解決二分類問題的SVM方法，直接應用到解決多分類問題中。因為結(jié)構(gòu)關(guān)系包含四種類型，因此本文研究的短語結(jié)構(gòu)判斷問題可以直接轉(zhuǎn)化為一個四分類問題。本文提出的解決思路是將多分類問題通過逐次二分進行解決，在每一次分類過程中僅需要對分類樣本進行二分。對于具有四種可能的N1+N2結(jié)構(gòu)語法關(guān)系判定轉(zhuǎn)化為3個不同的二分類問題進行解決。根據(jù)對樣本分布的統(tǒng)計結(jié)構(gòu)，在每次分類過程中盡量保持兩類分類結(jié)果樣本數(shù)量之間的均衡性，避免出現(xiàn)數(shù)量相差懸殊的兩類樣本先進行分類。根據(jù)這一原則，首先把訓練樣本集中的全部結(jié)構(gòu)分為兩類：{dzp}和{非dzp}，其標簽分別為1和-1，通過訓練分類器SVM1進行分類；然后，把訓練樣本集中除dzp以外的結(jié)構(gòu)再分為兩類：{blp}和{fzp，zwp}，并設其標簽分別為1和-1，通過訓練分類器SVM2進行分類；最后，通過分類器SVM3將{fzp，zwp}所對應的樣本進行分類。具體分類流程圖詳見圖1所示。

圖1 SVM語法關(guān)系判定流程圖Fig.1 Flowsheet of SVM syntax relation judgment

本算法訓練的三個分類器關(guān)系如下：在分類過程中先用SVM1進行判別，若分類結(jié)果為dzp，則判斷結(jié)束；否則，繼續(xù)通過SVM2進行判斷，若分類結(jié)果為blp，則判斷結(jié)束；否則繼續(xù)通過SVM3進行判斷，根據(jù)SVM3的判斷結(jié)果得到最終判斷結(jié)果。至此本文已經(jīng)完成了使用SVM對N1+N2結(jié)構(gòu)進行分類的全部數(shù)據(jù)和算法的準備工作。本文通過對N1+N2結(jié)構(gòu)進行特征標注，并將其特征集映射到相應的向量空間，要解決的第二個關(guān)鍵問題是，不同結(jié)構(gòu)映射對應的數(shù)量向量在向量空間中是否具有可分性。如果這些向量在其空間中沒有足夠好的可分性，雖然可以通過SVM進行分類，但從理論上很難得到性質(zhì)優(yōu)秀的分類器。造成向量不可分的主要因素是特征的選取不合理，這些特征不能覆蓋短語結(jié)構(gòu)的最小可分特征集。其中最小可分特征集是指能夠?qū)⑷康亩陶Z結(jié)構(gòu)進行準確分類所需要的最少特征所構(gòu)成的集合。

在實際應用中不可能掌握全部的N1+N2結(jié)構(gòu)，根據(jù)語言學的相關(guān)研究，本文所使用的語料庫從規(guī)模和代表性上可以看作是全部N1+N2結(jié)構(gòu)的一個較充分的樣本。它基本可以代表全部結(jié)構(gòu)的特征。在建設語料庫的過程中，對于這些N1+N2結(jié)構(gòu)，都通過人工比對驗證了本文所提特征在分類時的充分性。語料統(tǒng)計結(jié)果表明，基于本文所提短語結(jié)構(gòu)特征，可以對短語進行完全的分類，因此從一定程度上解決了第二個主要問題。從理論上和算法上都保證了使用SVM對N1+N2結(jié)構(gòu)進行分類的可行性。

3 實驗結(jié)果與分析

本章使用語料庫中的語料檢驗所提算法的有效性。為增加實驗結(jié)果的可信度，本文采用隨機交叉驗證的方法進行檢驗，每次實驗按訓練集與測試集9∶1的比例對語料庫中的語料進行隨機分組，共進行了9次，用9次的平均值作為最終計算結(jié)果。其中，本文算法的三個支持向量機分類器均使用了二次核函數(shù)，并通過最小二乘法進行求解。為驗證降維后不同維數(shù)對計算精度的影響，分別取不同的維數(shù)，對每一個固定的維數(shù)采取9次隨機分組訓練分類器并驗證準確率。

表5中列出了從20到40之間11組不同維數(shù)的計算結(jié)果。從驗證結(jié)果可以看出，隨著維數(shù)的升高，計算結(jié)果的準確率有上升的趨勢，但在36維時已經(jīng)達到86%的準確率。當維數(shù)繼續(xù)升高時，計算結(jié)果先降后升，但超過40后，隨著維數(shù)的繼續(xù)升高，精確率增長效果并不明顯，因此采取40維左右的向量即可達到較好的分類結(jié)果。本文方法的分類結(jié)果還有較大提升空間，由于文獻中沒有缺少使用支持向量機處理N1+N2結(jié)構(gòu)語法關(guān)系分類問題的相關(guān)研究，無法進行直接比較。但從利用支持向量機處理語言學問題的類似文獻的結(jié)果來看，本文結(jié)果達到或超過了同類問題和方法的處理水平。

表5 SVM算法實驗結(jié)果表Table 5 Experimental results of SVM algorithm %

4 結(jié)論與展望

短語結(jié)構(gòu)語法關(guān)系判定問題是計算機處理自然語言時每時每刻都可能遇到的底層問題，本文以N1+N2結(jié)構(gòu)為例研究如何使用機器學習方法處理這類問題。結(jié)果證明，基于語言學知識，將語言學問題轉(zhuǎn)化為可以通過支持向量機解決的問題能夠取得很好的處理效果。但本文算法還有較大提升空間，其錯誤主要來源于dzp和blp兩類關(guān)系的分類和判定。可從兩個方面提升區(qū)分效果：一是采取更優(yōu)的向量化方法，二是在《詞林》編碼的基礎上增加更多可用于分類的語言學信息，如上下文信息等。

由于目前相關(guān)研究不多，特別是難以找到可直接實驗的數(shù)據(jù)集，因此本文前期準備工作中進行了大量人工標注工作，未來將進一步研究自然語言處理領(lǐng)域的問題如何深入依托機器學習、人工智能的方法，在“小數(shù)據(jù)、弱標注”的前提下完成“大任務”。