一種基于SCAD的改進謂詞發(fā)現(xiàn)方法

鄭曉東, 潘敬敏, 胡漢輝

(1. 東南大學 經(jīng)濟管理學院, 江蘇 南京 211189; 2. 東南大學-蒙納士大學蘇州聯(lián)合研究生院, 江蘇 蘇州 215000)

歸納邏輯編程(inductive logic programming, ILP)[1]是機器學習與邏輯程序設計相結合形成的新研究領域,為知識工程等工智能領域提供了新技術,是機器學習的前沿研究課題.但ILP是在受限制的一階邏輯框架中進行歸納推理,因此面臨的難題是在給定詞匯不足的情況下如何擴展假設語言.

解決該問題的方法是通過引入新的謂詞使其與給定的詞匯在邏輯形式上相適應,即謂詞發(fā)現(xiàn) (predicate invention, PI).謂詞發(fā)現(xiàn)方法可分為基于ILP和基于統(tǒng)計學習2類.然而,它們存在共同的致命缺點,即如果程序在執(zhí)行的過程中使用了一個表達不當?shù)男轮^詞,則在后續(xù)謂詞發(fā)現(xiàn)的過程中可能會導致錯誤級聯(lián).

為解決此問題,WANG W.Y.等[2]提出了基于結構化稀疏的軟謂詞發(fā)現(xiàn)方法,通過將集合的參數(shù)一起正則化的方式減少要學習參數(shù)的數(shù)量,可有效去除具有“噪聲”的謂詞以使得謂詞發(fā)現(xiàn)的魯棒性增強.

然而,由于謂詞及其領屬結構信息的復雜性,導致謂詞會產(chǎn)生較大歧義[3].筆者發(fā)現(xiàn)軟謂詞發(fā)現(xiàn)方法有如下不足: ① 沒有嘗試將更多的正則化稀疏模型引入到謂詞發(fā)現(xiàn)系統(tǒng)中; ② 考慮了有偏稀疏模型但沒有考慮無偏稀疏模型對謂詞發(fā)現(xiàn)的影響.

文中提出一種基于平滑削邊絕對偏離(smoothly clipped absolute deviation, SCAD)的正則化稀疏的改進謂詞發(fā)現(xiàn)方法.該方法在正則化稀疏的謂詞發(fā)現(xiàn)方法的基礎上,通過引入SCAD正則化稀疏模型優(yōu)化算法的性能.文中主要工作分為以下2個方面:一是在軟謂詞發(fā)現(xiàn)中引入SCAD這一正則化稀疏模型,二是針對無偏稀疏性,著重觀察SCAD對軟謂詞發(fā)現(xiàn)結果的影響.

1 基于正則化稀疏的軟謂詞發(fā)現(xiàn)

1.1 軟謂詞發(fā)現(xiàn)

傳統(tǒng)的謂詞發(fā)現(xiàn)方法通常是壓縮一組緊密相關的規(guī)則發(fā)現(xiàn)新的謂詞.但傳統(tǒng)謂詞發(fā)現(xiàn)方法的缺點是在輸入有噪音的數(shù)據(jù)時,謂詞發(fā)現(xiàn)的中間過程可能因為選擇表達不當?shù)淖泳鋵е洛e誤級聯(lián).為了解決這一難題,WANG W.Y.等[4]提出基于結構化稀疏的軟謂詞發(fā)現(xiàn)方法,它在程序執(zhí)行的過程中并不創(chuàng)建新的謂詞符號,而是將相似的概念組合在一起,并利用基于結構化稀疏的技術來探索密切相關的概念和規(guī)則.這一方法對謂詞發(fā)現(xiàn)方法研究的進展起了重大作用.劉潔群[5]提出一種基于謂詞推理的沖突檢測算法,該算法通過謂詞表達策略的觸發(fā)條件和作用效果,并通過推理自動化地獲得策略之間的沖突關系.

目前謂詞發(fā)現(xiàn)方法的研究主要分為2類:基于ILP的謂詞發(fā)現(xiàn)方法[6]和基于統(tǒng)計學習的謂詞發(fā)現(xiàn)方法[7].在這2個類別的基礎上又演變出一系列其他的謂詞發(fā)現(xiàn)方法,如矩陣排序的謂詞發(fā)現(xiàn)方法[8].

1.2 元素正則化

文中選擇一階概率語言ProPPR這一邏輯平臺進行謂詞發(fā)現(xiàn),適合間接查詢的ProPPR的默認正則項針對稀疏估計有較好的處理性能,但對于噪音估計可能不太理想,因為錯誤的一階邏輯程序可能導致下游應用中出現(xiàn)更多的錯誤.此時引入元素正則化技術,定義一個權重參數(shù)向量ω,根據(jù)使用一階邏輯參數(shù)學習的結構學習的研究,ω中每個權重元素對應于一階邏輯子句候選項.采用Lasso公式,其目標函數(shù)為

min(-η+μ||ω||1),

(1)

式中:η為誤差項;μ≥0為可調參數(shù).與嶺估計不同,即使目標函數(shù)是不可微的,上述Lasso懲罰項也將產(chǎn)生稀疏估計.為優(yōu)化上述目標函數(shù),可使用近似運算符,每個權重分量ω通過收縮值σ而趨向于0,表達式為

signum(ω)max(0, |ω|-σ).

(2)

延遲L1正則化更新為

(3)

式中:σ為累積正則化更新的總數(shù);β為學習率.

文中使用延遲L1更新算法進行優(yōu)化.主要思想如下:對每個示例中的所有特征進行正則化更新速度很慢且?guī)谉o必要,故可先緩存相關功能的正則化更新,然后再更新這些累積的正則化之變化.

1.3 結構化圖拉普拉斯正則化

一個與PI相關的挑戰(zhàn)是,因為重復使用發(fā)現(xiàn)的謂詞使得它們難以通過簡單的元素正則化從矩陣中去除.為更好地包含每個邏輯子句特征之間的依賴關系,文中使用了一個成對圖拉普拉斯(pair-wise graph Laplacian)懲罰項,表達式為

min(η+ζ∑(p,q)||ωp-ωq||A(p,q)),

(4)

式中:ζ為控制結構化補償強度的正則化系數(shù);A(p,q)為邏輯子句之間成對相似性的相鄰矩陣,基本思想是通過學習后給相似的邏輯子句賦予相似的權重.比如下面的子句:

brother(X,Y):-son(X,Z),father(Z,Y).

brother(X,Y):-son(X,Z),mother(Z,Y).

由于它們具有相同的目標并且RHS的第1謂詞也相同,因此給予2者相似的權重是有意義的.為構造稀疏矩陣A,使用類似CHAMP風格的分析方式[9]:對于所有具有相同目標并且|RHS|=1的子句對,在鄰接圖中連接它們;對于所有具有相同目標并且|RHS|=2的子句對,如果右手側的第1個謂詞相同,就在A中將這2個子句也連接在一起.例如,并不需要為第2個子句創(chuàng)建1個新的實謂詞,而是直接在關聯(lián)矩陣A中為這1對規(guī)則賦予權重值為1即可.

為實現(xiàn)這種方法,使用一個度矩陣D表示矩陣A中每個條目的連接總數(shù),并且將圖形拉普拉斯定義為L=D-A,其將優(yōu)化公式轉換為

min(-η+ζwTLw),

(5)

式中η為損失.像嶺回歸一樣,這個正則化矩陣是一個L2懲罰項.

1.4 通過組Lasso的正則化稀疏

當拉普拉斯正則化給相似的子句組賦予相似的權重值時,它通常不會通過將不正確的相關子句組的權重值置0來達到移除它們的目的,這是拉普拉斯正則化的問題.為解決這個問題,可使用組Lasso的稀疏正則化(regularized sparsity via group Lasso)[10-11]:

(6)

式中:L為特征組的總數(shù);ωl為第l組的參數(shù)向量.通過公式(6)的運用,即可將問題轉換成一個正則化稀疏的學習問題.

1.5 通過彈性網(wǎng)的正則化稀疏

組Lasso正則化稀疏的問題是在矩陣A選擇具有關聯(lián)關系的特征組時并不能實現(xiàn)自動組效應,這在一定程度上影響了軟謂詞發(fā)現(xiàn)的執(zhí)行速度.可通過樸素彈性網(wǎng)[12]解決這個問題:

(7)

1.6 通過SCAD的正則化稀疏

彈性網(wǎng)在特征選擇的過程中實現(xiàn)了自動組效應,但彈性網(wǎng)并不是無偏稀疏模型,所以文中嘗試引用SCAD懲罰這一正則化稀疏模型.SCAD[13]模型是一種近似無偏稀疏模型:

(8)

式中:l∈{1,2,…,L};φρ,γ(·)為SCAD懲罰項,懲罰項中ρ≥0,γ>2.SCAD模型對絕對值小于ρ的回歸系數(shù)(即噪聲變量的回歸系數(shù))的壓縮作用與Lasso相同,傾向于將這一部分回歸系數(shù)壓縮為0.對絕對值位于區(qū)間[ρ,ργ]內的回歸系數(shù)(即目標變量的回歸系數(shù)),隨著回歸系數(shù)絕對值的增大而減小壓縮的程度.對于絕對值大于ργ的回歸系數(shù),不再對其進行壓縮.由于減小甚至避免了對目標變量對應回歸系數(shù)的壓縮,所以SCAD模型克服了Lasso有偏估計的缺點,改善了其參數(shù)估計一致性和變量選擇一致性.

2 試 驗

2.1 試驗數(shù)據(jù)集

使用歐洲皇室家庭關系數(shù)據(jù)集[13]作為試驗數(shù)據(jù)集,可更好衡量基于SCAD的軟謂詞發(fā)現(xiàn)方法的性能.超過30 kB數(shù)據(jù)信息的家庭數(shù)據(jù)集包含3 010個個體和1 422個歐洲皇室家庭.

2.2 試驗目標

試驗目標是在一階邏輯平臺ProPPR上引入SCAD正則化稀疏算子后進行謂詞發(fā)現(xiàn)時,通過與引入彈性網(wǎng)正則化稀疏算子、組Lasso正則化稀疏算子、拉普拉斯正則化稀疏算子等正則項互相比較證明文中所提方法能夠提高謂詞發(fā)現(xiàn)的平均精準度并能減少對知識庫進行查詢的時間.同時,通過考察知識庫的完善程度來比較基于不同正則化稀疏算子謂詞發(fā)現(xiàn)方法的試驗性能.

2.3 試驗方法

確定完試驗數(shù)據(jù)集后,對家庭關系數(shù)據(jù)集按時間分割成訓練集和測試集2部分,分別包括21 430,8 899個事實.在下文的知識庫完善試驗中,隨機刪除訓練集和測試集中各自50%的事實數(shù)據(jù),并用軟謂詞發(fā)現(xiàn)方法完善缺失的事實數(shù)據(jù).

試驗采用平均準確率(mean average precision, 用θMAP表示)來衡量謂詞發(fā)現(xiàn)的準確度.θMAP已經(jīng)在很多任務中展示出它的魯棒性和穩(wěn)定性,并且已被廣泛地應用到關系學習的任務中[12,14-15],也可評估文中方法的有效性.每個試驗重復3次,并記錄試驗結果的平均值;同時比較了基于不同正則算子在測試集上進行推理的時間.

2.4 試驗與分析

本小節(jié)主要針對2.1節(jié)提到的家庭關系數(shù)據(jù)集,使用2.3節(jié)提出的試驗方法進行一系列試驗.基于5種不同的正則化稀疏算子即元素正則化稀疏算子、結構化圖拉普拉斯正則化稀疏算子、組Lasso正則化稀疏算子、彈性網(wǎng)正則化稀疏算子和SCAD正則化稀疏算子進行試驗.根據(jù)試驗結果,比較不同的正則化稀疏算子對軟謂詞發(fā)現(xiàn)性能的影響.

2.4.1μ值選擇

μ作為正則化稀疏算子的系數(shù),其取值直接影響到知識庫完善試驗的性能,因此應先確定μ的最優(yōu)值.圖1顯示了正則化算子不同時,正則化系數(shù)μ與θMAP的關系.

圖1 正則化系數(shù)μ與θMAP的關系

由圖1可見,隨著μ值的增加,θMAP的值經(jīng)歷了先增加后減少的變化趨勢.但當L1懲罰項的正則化系數(shù)μ1取值為0.000 001時,當L2懲罰項的正則化系數(shù)μ2取值為0. 000 1時,θMAP的取值達到峰值.這2個值將貫穿整個試驗過程.圖2顯示了正則化算子不同時,正則化系數(shù)μ與知識庫完善所需推理時間t的關系.

圖2 正則化系數(shù)μ與知識庫完善所需推理時間的關系

由圖2可見,在其他變量相同時,SCAD方法推理時間隨著正則化系數(shù)μ的增加而減少,且SCAD方法的推理時間與其他方法無明顯差異.

2.4.2α值選擇

α作為ProPPR中排序算法PageRank-Nibble中的1個參數(shù),其取值的大小直接影響到知識庫完善試驗的性能,所以應先通過試驗確定α的最優(yōu)值.

圖3中顯示了正則化算子不同時,正則化系數(shù)α與θMAP的關系.

圖3 正則化系數(shù)α與θMAP的關系

由圖3可見,當α=0.100時,元素正則化稀疏算子、組Lasso正則化稀疏算子、彈性網(wǎng)正則化稀疏算子和SCAD正則化稀疏算子的θMAP值達到峰值.圖4顯示了正則化算子不同時,正則化系數(shù)α與知識庫完善所需推理時間t的關系.試驗表明,α=0.100是最優(yōu)值.

圖4 正則化系數(shù)α與知識庫完善所需推理時間的關系

2.4.3 知識庫完善試驗

通過第2.4.1小節(jié)和第2.4.2小節(jié)確定μ和α的最優(yōu)值后,本小節(jié)基于5種不同正則化稀疏算子(元素正則化稀疏算子、結構化圖拉普拉斯正則化稀疏算子、組Lasso正則化稀疏算子、彈性網(wǎng)正則化稀疏算子和SCAD正則化稀疏算子)進行知識庫完善的試驗.從家庭關系數(shù)據(jù)集中抽取6對關系進行了試驗,表1給出了不同正則化方法的θMAP結果.

由表1可見,對于軟謂詞發(fā)現(xiàn)來講,基于SCAD正則化稀疏的軟謂詞發(fā)現(xiàn)方法在知識庫完善的試驗中有較好的測試性能,它遠超過傳統(tǒng)的基于嶺回歸基線(即基于元素正則化稀疏算子的軟謂詞發(fā)現(xiàn)方法)的性能,它的θMAP平均值為0.755;而基于SCAD正則化稀疏算子的軟謂詞發(fā)現(xiàn)方法的θMAP平均值達到0.798.總的來說,文中結果與先前研究中稀疏性導致正則化項經(jīng)驗損失最小的結果一致[13]:具有較少非0權重的緊致參數(shù)空間可能產(chǎn)生更好的結果.

表1 不同正則化方法的θMAP結果

將文中提出的方法應用于家庭關系數(shù)據(jù)集,在5種不同正則化稀疏算子的情況下,家庭關系數(shù)據(jù)集中推理6對關系所需推理時間的比較見表2.

表2 各方法抽取關系的平均時間比較 ms

由表2可見,在相同變量情況下,SCAD抽取關系的平均時間優(yōu)于組Lasso方法,略低于L2、彈性網(wǎng)和拉普拉斯方法.

2.4.4 試驗結果

將以上試驗結果總結如下:

1) 將L1懲罰項的正則化系數(shù)μ1的值設置為0.000 001,將L2懲罰項的正則化系數(shù)μ2的值設置為0.000 1,將參數(shù)α的值設置為0.100時,基于正則化稀疏的軟謂詞發(fā)現(xiàn)方法的試驗性能最優(yōu).

2) 從θMAP的平均值來講,文中提出的基于SCAD正則化稀疏算子的軟謂詞發(fā)現(xiàn)方法的性能比基于其他正則化項的軟謂詞發(fā)現(xiàn)方法的性能更優(yōu).從知識庫完善所需推理時間的結果來看,文中提出的基于SCAD的軟謂詞發(fā)現(xiàn)方法也具有一定優(yōu)勢.

3 結 論

1) 文中使用基于SCAD正則化算子和CHAMP方式壓縮再誘導重疊組的方法,克服傳統(tǒng)謂詞發(fā)現(xiàn)方法的不足及提高軟謂詞發(fā)現(xiàn)方法的性能.

2) 在超過30 kB數(shù)據(jù)信息的皇室家庭數(shù)據(jù)集上進行試驗,試驗表明基于SCAD正則化算子的軟謂詞發(fā)現(xiàn)方法比基于組Lasso的謂詞發(fā)現(xiàn)方法和基于彈性網(wǎng)的謂詞發(fā)現(xiàn)方法具有更好的性能,其預測結果的平均精度值達到0.798,遠遠超過基于拉普拉斯正則化的軟謂詞發(fā)現(xiàn)方法的0.726.

3) 在未來工作中,可嘗試將更多的正則化稀疏方法引入到試驗中以選擇出更優(yōu)的方案.