問(wèn)答系統(tǒng)中基于語(yǔ)義核函數(shù)的問(wèn)題分類(lèi)算法

江龍泉 張波 胡志鵬 丁峻宏 劉波

摘要：

提出一種基于語(yǔ)義核函數(shù)的問(wèn)題分類(lèi)算法，該算法基于問(wèn)題的語(yǔ)法結(jié)構(gòu)構(gòu)建支持向量機(jī)（SVM）核函數(shù).首先，將給定的問(wèn)題解析為語(yǔ)法樹(shù)結(jié)構(gòu)，用語(yǔ)法樹(shù)的子樹(shù)表示該問(wèn)題;然后，從詞法、語(yǔ)法、語(yǔ)義三個(gè)層面提取問(wèn)題的特征，構(gòu)成更加豐富的特征空間;接著，基于問(wèn)題的語(yǔ)法樹(shù)構(gòu)建核函數(shù);最后，使用潛在語(yǔ)義索引方法并結(jié)合問(wèn)題的詞法、語(yǔ)法以及語(yǔ)義特征，通過(guò)語(yǔ)義核函數(shù)將特征空間映射到更有效的空間中進(jìn)行問(wèn)題分類(lèi).TREC數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，通過(guò)詞法、語(yǔ)法以及語(yǔ)義增強(qiáng)的問(wèn)題特征空間可以提高分類(lèi)準(zhǔn)確率.

關(guān)鍵詞：

問(wèn)答系統(tǒng); 監(jiān)督學(xué)習(xí); 支持向量機(jī); 問(wèn)題分類(lèi); 語(yǔ)義核函數(shù); 特征空間

中圖分類(lèi)號(hào)： TP 391文獻(xiàn)標(biāo)志碼： A文章編號(hào)： 1000-5137（2018）01-0053-04

A semantic kernel function based question classification algorithm in

question answering system

Jiang Longquan1， Zhang Bo1*， Hu Zhipeng1， Ding Junhong2， Liu Bo2

（1.The College of Information，Mechanical and Electrical Engineering，Shanghai Normal University，

Shanghai 200234，China; 2.Shanghai Super Computing Technology Co.Ltd.，Shanghai 201203，China）

Abstract：

A question classification algorithm based on semantic kernel function is proposed.This algorithm constructs Support Vector Machine （SVM） kernel function based on the grammatical structure of the question.Firstly，the given question is parsed into syntactical structural tree，and then sub-trees of syntactical tree are used to represent the question.Secondly，features are extracted from three aspects of the question：lexical，syntactical and semantic，to form a richer feature space.Thirdly，the kernel function is constructed based on syntactical structural tree of the question.Finally，using the potential semantic indexing method and the lexical，grammatical and semantic features of the question，the feature space is mapped into a more efficient space by the semantic kernel.The experimental results on the TREC dataset show that the classification accuracy can be improved by lexical，grammatical，and semantic enhancement.

收稿日期： 2017-07-10

基金項(xiàng)目： 國(guó)家自然科學(xué)基金（61572326，61702333）;上海市教育科學(xué)規(guī)劃項(xiàng)目（C160049）;上海市科委地方院校能力建設(shè)項(xiàng)目（17070502800）

作者簡(jiǎn)介： 江龍泉（1991-），男，碩士研究生，主要從事自然語(yǔ)言處理、智能問(wèn)答系統(tǒng)、機(jī)器學(xué)習(xí)方面的研究.E-mail：longquan.jiang@yahoo.com

導(dǎo)師簡(jiǎn)介： 張波（1978-），男，副教授，主要從事智能信息處理、智能數(shù)據(jù)分析、語(yǔ)義計(jì)算、可信計(jì)算方面的研究.E-mail：zhangbo@shnu.edu.cn

*通信作者

引用格式： 江龍泉，張波，胡志鵬.問(wèn)答系統(tǒng)中基于語(yǔ)義核函數(shù)的問(wèn)題分類(lèi)算法 [J].上海師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2018，47（1）：53-56.

Citation format： Jiang L Q，Zhang B，Hu Z P，et al.A semantic kernel function based question classification algorithm in question answering system [J].Journal of Shanghai Normal University（Natural Sciences），2018，47（1）：53-56.

Key words：

question answering; supervised learning; SVM; question classification; semantic kernel function; feature space

開(kāi)放領(lǐng)域的問(wèn)答系統(tǒng)應(yīng)該能夠像人類(lèi)一樣對(duì)用自然語(yǔ)言描述的問(wèn)題作出回答.許多情況下用戶只需要一條特定的信息而不是許多篇文檔，系統(tǒng)只需要給用戶一個(gè)簡(jiǎn)短的答案而不必讓用戶讀懂整篇文檔[1].

Mishra等[2]提出了一種基于問(wèn)題語(yǔ)法子樹(shù)的最大熵分類(lèi)方法，將問(wèn)題解析成語(yǔ)法樹(shù)結(jié)構(gòu)，其子樹(shù)被當(dāng)做問(wèn)題分類(lèi)的特征.Li等[3]采用Winnows離散網(wǎng)絡(luò)（SNoW）學(xué)習(xí)問(wèn)題分類(lèi)器，他們工作的最大特色是引入了一種層級(jí)結(jié)構(gòu)的分類(lèi)器，先給問(wèn)題分配一個(gè)粗粒度的標(biāo)簽，然后使用該標(biāo)簽與其他特征一起作為下一層分類(lèi)器的輸入特征.Silva等[4]使用線性核函數(shù)的支持向量機(jī)（SVM）算法進(jìn)行分類(lèi).然而，上述研究雖然在問(wèn)題分類(lèi)任務(wù)上取得了不錯(cuò)的效果，但所選取的特征空間較為單一，無(wú)法表現(xiàn)問(wèn)題更深層次的特點(diǎn).

本文作者針對(duì)上述研究的不足，提出了一種基于語(yǔ)義核函數(shù)的問(wèn)題分類(lèi)算法，主要的創(chuàng)新點(diǎn)在于從詞法、語(yǔ)法以及語(yǔ)義三個(gè)層面提取問(wèn)題的特征，定義一種語(yǔ)義核函數(shù)，并基于問(wèn)題的語(yǔ)法結(jié)構(gòu)構(gòu)建核函數(shù).通過(guò)該語(yǔ)義核函數(shù)將問(wèn)題的特征空間減少到更為有效的空間中進(jìn)行分類(lèi).

1基于語(yǔ)義核函數(shù)的分類(lèi)算法

1.1支持向量機(jī)

分類(lèi)器的選擇很大程度上影響著最終的問(wèn)題分類(lèi)系統(tǒng)性能，支持向量機(jī)（SVM）是問(wèn)題分類(lèi)中使用最廣泛的分類(lèi)器之一.SVM是用于分類(lèi)數(shù)據(jù)的非概率學(xué)習(xí)模型，它嘗試找到一個(gè)具有最大邊距的用于區(qū)分類(lèi)別的超平面.[5]

假設(shè)訓(xùn)練集（xi，yi），i=1，…，n，其中xi=（xi1，…，xid）是一個(gè)d維樣本，yi∈{+1，-1}是相應(yīng)的標(biāo)簽.支持向量分類(lèi)器的任務(wù)是找到線性判別函數(shù)g（xi）=wTxi+w0（w為權(quán)重向量，w0為偏移）.對(duì)于yi=+1，使得wTxi+w0≥+1成立;對(duì)于yi=-1，使得wTxi+w0≤-1成立.因此，尋求解決方案，滿足：

yi（wTxi+w0）≥1，i=1，…，n，（1）

通過(guò)

min12wTw-∑ni=1αi（yi（wTxi+w0）-1），（2）

得到解：

w=∑ni=1αiyixi.（3）

其中，αi是拉格朗日乘數(shù).

1.2語(yǔ)義核函數(shù)

線性分割數(shù)據(jù)的典型做法是將特征空間映射到高維空間.這種映射由所謂的核函數(shù)完成.核函數(shù)是一個(gè)方程，其從輸入空間χ獲取2個(gè)樣本，將其映射到表示其相似性的1個(gè)實(shí)數(shù).對(duì)于任意兩個(gè)樣本xi，xj∈χ，核函數(shù)

k（xi，xj）=〈（xi），（xj）〉，（4）

其中，是從輸入空間χ到點(diǎn)積特征空間H的顯式映射.

為了將核函數(shù)應(yīng)用于SVM分類(lèi)器，通常求解方程（2）的對(duì)偶形式：

max∑ni=1αi-12∑ni=1∑nj=1αiαjyiyjxi·xj，（5）

其中xi·xj是兩個(gè)樣本的內(nèi)積，它是測(cè)量xi和xj之間相似度的隱含核.

在問(wèn)題分類(lèi)任務(wù)中，通常需要在非常高的維度空間中表示問(wèn)題，而SVM對(duì)高維數(shù)據(jù)具有良好的性能.問(wèn)題分類(lèi)任務(wù)中，問(wèn)題可以表示為：

xi=（wi1，…，wik，…，wiN），（6）

其中，wik表示問(wèn)題xi中的第k個(gè)詞的頻率，而N是詞的總數(shù).

當(dāng)使用BOW（Bag of Words）表示問(wèn)題特征時(shí)，SVM隱含地使用線性核函數(shù).對(duì)于兩個(gè)問(wèn)題xi和xj，線性核函數(shù)的定義為：

KBOW（xi，xj）=∑Nk=1wikwjk.（7）

雖然使用BOW特征的線性核能夠滿足問(wèn)題分類(lèi)任務(wù)中的基本需求，但對(duì)于需要更加深入分析問(wèn)題潛在特征的應(yīng)用場(chǎng)景，該方法顯然不能反映問(wèn)題與回答之間復(fù)雜的隱含關(guān)系[6].本文作者提出一種基于問(wèn)題的語(yǔ)法結(jié)構(gòu)構(gòu)建的樹(shù)核函數(shù)，首先將一個(gè)給定的問(wèn)題解析為其語(yǔ)法樹(shù)，然后用語(yǔ)法樹(shù)的子樹(shù)來(lái)表示該問(wèn)題.使用潛在語(yǔ)義索引方法，通過(guò)潛在語(yǔ)義核將特征空間減少到更有效的空間，通過(guò)查看大型語(yǔ)料庫(kù)中的信息共現(xiàn)來(lái)定義詞的相似矩陣.

潛在語(yǔ)義核可以使用奇異值分解（SVD）獲得.假設(shè)D是來(lái)自維基百科文檔語(yǔ)料庫(kù)的term-by-document矩陣，其中Di，j表示文檔dj中的詞wi的頻率.SVD將D分解成樹(shù)形矩陣：D=UQVT，其中U和V分別是DDT和DTD的特征向量的正交矩陣，Q是對(duì)角線中包含DDT特征值的對(duì)角矩陣.縮小空間中的相似矩陣可以如下獲得：

Π=UkQ-1k，（8）

其中Uk是包含k（xi，xj）=〈（xi），（xj）〉的前k列的N×k矩陣，Qk是相應(yīng)特征值的對(duì)角矩陣.相似矩陣Π可以用于定義一個(gè)變換：將一個(gè)問(wèn)題xi映射到向量x^i：

π（xi）=xi（WΠ）=x^i.（9）

其中，W是N×N對(duì)角矩陣，Wi，i=idf（wi）是詞wi的逆文檔頻率（IDF）.通過(guò)測(cè)量詞出現(xiàn)在文檔語(yǔ)料庫(kù)中的頻率來(lái)反映單詞的重要性.假設(shè)經(jīng)常出現(xiàn)的詞不太重要，則具有較低的值，而不常出現(xiàn)的詞卻很重要，則具有較高的值.潛在語(yǔ)義核定義為：

KLS（xi，xj）=〈π（xi），π（xj）〉.（10）

本文作者還基于手動(dòng)構(gòu)建的相關(guān)詞列表定義了語(yǔ)義相關(guān)核函數(shù)KRel：

KRel（xi，xj）=xiPPTxTj=x^ix^Tj，（11）

其中，P是反映列表中單詞之間的相似性的相似矩陣.

2實(shí)驗(yàn)

本文作者采用Text REtrieval Conference（TREC）會(huì)議評(píng)測(cè)數(shù)據(jù)集，該數(shù)據(jù)集最初由伊利諾伊大學(xué)香檳分校發(fā)布，由6 000個(gè)已標(biāo)記的問(wèn)題組成，其中5 500個(gè)用作模型訓(xùn)練集，500個(gè)用作測(cè)試集.TREC數(shù)據(jù)集提供了兩種不同粒度的問(wèn)題類(lèi)別標(biāo)簽，粗粒度描述了廣義的問(wèn)題類(lèi)別（如動(dòng)物），而細(xì)粒度則描述了狹義的問(wèn)題類(lèi)別（如貓、狗等）.

通過(guò)在輸入特征空間應(yīng)用不同的核函數(shù)來(lái)對(duì)TREC數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，不同的核函數(shù)在TREC數(shù)據(jù)集上的實(shí)驗(yàn)準(zhǔn)確率如表2所示.

表2不同的核函數(shù)在TREC數(shù)據(jù)集上的實(shí)驗(yàn)準(zhǔn)確率

從表1中可以看出，最好的結(jié)果是通過(guò)所有3個(gè)內(nèi)核的組合獲得的.將所提出的語(yǔ)義核函數(shù)SVM算法在TREC數(shù)據(jù)集上的性能與現(xiàn)有的問(wèn)題分類(lèi)算法進(jìn)行了比較（表3）.

表3不同分類(lèi)器在TREC數(shù)據(jù)集上的問(wèn)題分類(lèi)準(zhǔn)確率比較

注：字母U、B、T、P、H、HY、NE與R分別表示unigrams、bigrams、trigrams、POS-tags、headword、hypernyms、named-entities、related-words特征.

從表2中的結(jié)果可以看出，基于語(yǔ)義核函數(shù)的SVM問(wèn)題分類(lèi)算法（語(yǔ)義核SVM）在TREC數(shù)據(jù)集粗粒度類(lèi)別下的準(zhǔn)確率達(dá)到最高的95.7%，而在細(xì)粒度類(lèi)別下的準(zhǔn)確率達(dá)到89.1%.當(dāng)分類(lèi)器在更豐富的特征空間上訓(xùn)練時(shí)，它們可以提供更好的性能.語(yǔ)法和語(yǔ)義特征通常可以為特征空間增加更多信息，提高分類(lèi)準(zhǔn)確率.由于問(wèn)題分類(lèi)中的特征非常具有依賴性，通常將所有特征組合在一起并不是特征的最佳選擇，并且根據(jù)決策模型，特征的最佳組合可以不同.

3結(jié)束語(yǔ)

問(wèn)答系統(tǒng)中的問(wèn)題分類(lèi)是一個(gè)難題，實(shí)際上，機(jī)器需要理解問(wèn)題并將其分類(lèi)到正確的類(lèi)別.這需要通過(guò)一系列復(fù)雜的步驟才能完成.本文作者詳細(xì)介紹了基于語(yǔ)義核函數(shù)的SVM問(wèn)題分類(lèi)方法，通過(guò)語(yǔ)法和語(yǔ)義特征增強(qiáng)特征空間可以提高分類(lèi)準(zhǔn)確率.

參考文獻(xiàn)：

[1]Liu Y，Yi X，Chen R，et al.A Survey on Frameworks and Methods of Question Answering [C].International Conference on Information Science and Control Engineering.IEEE，2016：115-119.

[2]Mishra A，Jain S K.A survey on question answering systems with classification [J].Journal of King Saud University-Computer and Information Sciences，2016，28（3）：345-361.

[3]Li X，Roth D.Learning question classifiers [C].Proceedings of the 19th international conference on Computational linguistics，Taipei：ACM，2002.

[4]Silva J，Coheur L，Mendes A C，et al.From symbolic to sub-symbolic information in question classification [J].Artificial Intelligence Review，2011，35（2）：137-154.

[5]Ray S K，Singh S，Joshi B P.A semantic approach for question classification using WordNet and Wikipedia [J].Pattern Recognition Letters，2010，31（13）：1935-1943.

[6]Loni B，Tulder G V，Wiggers P，et al.Question Classification by Weighted Combination of Lexical，Syntactic and Semantic Features [M].Berlin：Springer Heidelberg，2011.