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

摘要：

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

關(guān)鍵詞：

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

中圖分類號： TP 391文獻(xiàn)標(biāo)志碼： A文章編號： 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)目： 國家自然科學(xué)基金（61572326，61702333）;上海市教育科學(xué)規(guī)劃項(xiàng)目（C160049）;上海市科委地方院校能力建設(shè)項(xiàng)目（17070502800）

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

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

*通信作者

引用格式： 江龍泉，張波，胡志鵬.問答系統(tǒng)中基于語義核函數(shù)的問題分類算法 [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

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

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

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

1基于語義核函數(shù)的分類算法

1.1支持向量機(jī)

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

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

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

通過

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

得到解：

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

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

1.2語義核函數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

Π=UkQ-1k，（8）

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

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

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

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

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

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

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

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

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

通過在輸入特征空間應(yīng)用不同的核函數(shù)來對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é)果是通過所有3個(gè)內(nèi)核的組合獲得的.將所提出的語義核函數(shù)SVM算法在TREC數(shù)據(jù)集上的性能與現(xiàn)有的問題分類算法進(jìn)行了比較（表3）.

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

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

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

3結(jié)束語

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