鈕澤平,李國良

(清華大學(xué) 計算機(jī)科學(xué)與技術(shù)系,北京 100084)

近年來,數(shù)據(jù)量爆炸式增長.生產(chǎn)環(huán)境中,大部分?jǐn)?shù)據(jù)都由數(shù)據(jù)庫管理系統(tǒng)進(jìn)行管理.機(jī)器學(xué)習(xí)算法目前廣泛應(yīng)用于各種數(shù)據(jù)分析與線上應(yīng)用場景,然而在易用性方面,由于編寫機(jī)器學(xué)習(xí)代碼的復(fù)雜性且數(shù)據(jù)分析師更熟悉SQL 而存在較大提升空間;在執(zhí)行效率方面,由于機(jī)器學(xué)習(xí)算法與數(shù)據(jù)庫操作分離而無法借助數(shù)據(jù)庫查詢優(yōu)化過程進(jìn)行優(yōu)化[1,2].數(shù)據(jù)庫提供的SQL 接口具有聲明式的特點,用戶通過SQL 簡練地指定查詢?nèi)蝿?wù),無需關(guān)注內(nèi)部實現(xiàn)方法,數(shù)據(jù)庫就可以通過一系列查詢處理過程,將查詢語句轉(zhuǎn)化為一系列算子操作,利用索引、緩存等進(jìn)行加速,選取合適的多表連接方案,確保準(zhǔn)確而高效地獲得數(shù)據(jù).機(jī)器學(xué)習(xí)的訓(xùn)練與預(yù)測可以看作新的操作符,通過SQL 支持這種新的操作符,一方面可以將數(shù)據(jù)獲取與訓(xùn)練/預(yù)測過程通過SQL 進(jìn)行融合,使系統(tǒng)更易于使用;另一方面,提供了使用數(shù)據(jù)庫優(yōu)化機(jī)器學(xué)習(xí)算子的可能.已有的工作中,主要為通過數(shù)據(jù)庫的用戶定義函數(shù)(UDF)功能,對機(jī)器學(xué)習(xí)運(yùn)算進(jìn)行支持;或者通過結(jié)合硬件特點,利用數(shù)據(jù)庫內(nèi)聯(lián)用戶定義函數(shù),將聲明式查詢與命令式數(shù)據(jù)處理轉(zhuǎn)化為中間表示后統(tǒng)一優(yōu)化等方式進(jìn)行加速[2].

然而,在機(jī)器學(xué)習(xí)推理過程的優(yōu)化中,前人的工作主要集中于通過查詢語句中的謂詞特點對模型進(jìn)行剪枝,而對模型特征的利用仍不夠徹底.考慮一個例子“選擇周營業(yè)額預(yù)測值大于20 萬元的商店”,可以通過SQL 查詢表示為:

在這類查詢中,滿足條件,需要返回給用戶的數(shù)據(jù)可能只占全部數(shù)據(jù)中很小的比例.類似的例子還有:大型連鎖超市希望知道各分店各銷售部門中,營業(yè)額少于特定金額的有哪些;銀行希望找出違約概率高于一定值的賬戶等.這些場景中,通過支持UDF 的SQL 可以表示為WHERE 子句中包含機(jī)器學(xué)習(xí)預(yù)測函數(shù)的形式,即,使用機(jī)器學(xué)習(xí)模型預(yù)測結(jié)果對數(shù)據(jù)進(jìn)行篩選可看作一種新的謂詞.當(dāng)數(shù)據(jù)量較大時,如果按照用戶定義函數(shù)的方式進(jìn)行執(zhí)行,首先需要將多個包含特征列的表進(jìn)行代價較為高昂的連接操作,之后必須在得到的全部數(shù)據(jù)上進(jìn)行機(jī)器學(xué)習(xí)推理,才能得到占總數(shù)據(jù)量比例很小的查詢結(jié)果.

然而,這種樸素的方式不一定是最優(yōu)的.一方面,在未進(jìn)行連接時,通過單表中某些重要特征的取值已經(jīng)可以排除其在最終結(jié)果中的可能,但這種樸素的方式仍然會將連接操作進(jìn)行到底,造成計算的浪費;另一方面,機(jī)器學(xué)習(xí)的推理過程與簡單謂詞相比復(fù)雜得多——較為復(fù)雜的決策樹預(yù)測一條數(shù)據(jù)可能相當(dāng)于十余條簡單謂詞的執(zhí)行時間,故連接操作生成過多的無用結(jié)果,也會造成推理過程時間大幅增加.對于這類使用了機(jī)器學(xué)習(xí)推理結(jié)果對結(jié)果進(jìn)行篩選的SQL 查詢,如果能夠提前從模型中提取一些條件對數(shù)據(jù)預(yù)先進(jìn)行篩選過濾,則可以同時減少數(shù)據(jù)獲取中的連接代價與后續(xù)模型推理過程中的計算代價,從而提高執(zhí)行效率.這樣的規(guī)則需要是保守的,即不能因為應(yīng)用規(guī)則導(dǎo)致應(yīng)在最終結(jié)果中的數(shù)據(jù)被丟棄.直接進(jìn)行連接操作得到的數(shù)據(jù)記為Sjoin,經(jīng)過機(jī)器學(xué)習(xí)推理謂詞過濾得到的結(jié)果記為Sresult,使用規(guī)則篩選得到的數(shù)據(jù)記為Sfilter,它們之間的關(guān)系可以表示為圖1.對于一個特定問題,Sjoin與Sresult越大,使用規(guī)則進(jìn)行初篩的優(yōu)化潛力就越大;而為了實際達(dá)到良好的加速效果,我們的目標(biāo)便是讓Sfilter盡可能接近Sresult.

Fig.1 Relation of Sjoin,Sfilter and Sresult圖1 Sjoin,Sfilter,Sresult 三者應(yīng)滿足的關(guān)系

用于初篩的規(guī)則一定與模型相關(guān)——只有模型才能夠決定推理的結(jié)果,故我們可以嘗試從以下兩個角度切入.

(1)構(gòu)建更容易獲得初篩規(guī)則的模型.機(jī)器學(xué)習(xí)模型中,各種特征重要性不同,如果我們能夠在構(gòu)建模型過程中,在不顯著損失預(yù)測準(zhǔn)確率的情況下構(gòu)建出能夠讓更多數(shù)據(jù)僅通過少量重要特征判斷即可得到結(jié)果的模型,那么對這種更簡單的模型放寬條件,有助于我們得到更接近Sresult的Sfilter;

(2)對已有模型進(jìn)行簡化,提取結(jié)果數(shù)據(jù)的“大致特征”(使用謂詞進(jìn)行刻畫)作為初篩規(guī)則.這里的謂詞必須足夠簡單,因為過于復(fù)雜的謂詞用于初篩會造成查詢優(yōu)化過程與執(zhí)行過程中的性能損失.如果能得到滿足上述特征的簡單謂詞,那么就可以借助數(shù)據(jù)庫查詢優(yōu)化過程,下推用于初篩的簡單謂詞,降低數(shù)據(jù)獲取過程中的多表連接開銷;同時,初篩去掉大量結(jié)果后,需要執(zhí)行推理的數(shù)據(jù)量也會顯著降低.

本工作以機(jī)器學(xué)習(xí)中經(jīng)典的決策樹算法為例,通過SQL 對決策樹模型的訓(xùn)練方法以及包含決策樹推理的謂詞進(jìn)行了支持,并設(shè)計算法進(jìn)行性能優(yōu)化.本文嘗試?yán)脭?shù)據(jù)庫對一種特定的機(jī)器學(xué)習(xí)算法,決策樹的推理過程進(jìn)行優(yōu)化.主要的貢獻(xiàn)是:實現(xiàn)了通過SQL 進(jìn)行模型訓(xùn)練,加速模型推理的工作流程;提出通過預(yù)篩選+驗證方法加速決策樹推理SQL 的速度,并設(shè)計了從決策樹提取用于對查詢結(jié)果預(yù)篩選的謂詞算法;在真實數(shù)據(jù)集上測試加速效果,并分析實驗結(jié)果.

本文第1 節(jié)介紹使用數(shù)據(jù)庫支持機(jī)器學(xué)習(xí)方向已有的工作.第2 節(jié)以決策樹模型為例,介紹了AI 模型訓(xùn)練和推理SQL 在數(shù)據(jù)庫內(nèi)的優(yōu)化工作流程.第3 節(jié)介紹數(shù)據(jù)庫內(nèi)決策樹訓(xùn)練和推理的主要優(yōu)化算法,針對前文提出的兩個切入點進(jìn)行嘗試.第4 節(jié)介紹在真實數(shù)據(jù)集上進(jìn)行測試的效果并分析原因.第5 節(jié)對其他AI 模型上的優(yōu)化進(jìn)行探討.最后,在第6 節(jié)中進(jìn)行總結(jié).

1 相關(guān)工作

機(jī)器學(xué)習(xí)包括數(shù)據(jù)清洗與特征工程、模型訓(xùn)練、模型選擇與評估、模型上線部署等一整套流程.消耗更少時間、得到更好的模型有利于提高數(shù)據(jù)分析師的效率,提升模型開發(fā)效率,降低應(yīng)用系統(tǒng)處理延遲.近年來,數(shù)據(jù)庫研究者對對機(jī)器學(xué)習(xí)整個流程的優(yōu)化做出了諸多貢獻(xiàn)(DB4AI),主要集中于擴(kuò)展SQL 語句支持機(jī)器學(xué)習(xí)算法、自動特征選取、模型訓(xùn)練加速、執(zhí)行引擎優(yōu)化方面.

? 聲明式機(jī)器學(xué)習(xí)

為了能夠降低機(jī)器學(xué)習(xí)算法的使用門檻,數(shù)據(jù)庫社區(qū)出現(xiàn)了一些通過擴(kuò)展SQL 對機(jī)器學(xué)習(xí)算法進(jìn)行支持的嘗試.其思想為:通過聲明式語言對復(fù)雜的機(jī)器學(xué)習(xí)算法執(zhí)行過程進(jìn)行封裝,讓用戶能像使用SQL 一樣只需定義任務(wù),系統(tǒng)便能自動實現(xiàn)細(xì)節(jié),完成整個機(jī)器學(xué)習(xí)流程.MADlib[3]是開源的數(shù)據(jù)庫內(nèi)分析算法庫,提供了基于SQL 的機(jī)器學(xué)習(xí)算法,用戶無需將數(shù)據(jù)導(dǎo)入導(dǎo)出其他工具即可完成機(jī)器學(xué)習(xí)任務(wù).MADlib 的實現(xiàn)利用了PostgreSQL 數(shù)據(jù)庫的服務(wù)器端編程特性,將C++,Python 編寫的機(jī)器學(xué)習(xí)算法聲明為用戶定義函數(shù).C++語言用于實現(xiàn)對性能要求較高的機(jī)器學(xué)習(xí)算法底層操作,如矩陣運(yùn)算;Python 實現(xiàn)算法更高抽象層次上的邏輯.訓(xùn)練算法方面,MADlib 支持迭代式的訓(xùn)練過程;推理算法方面,MADlib 要求數(shù)據(jù)預(yù)先被連接為單表,推理結(jié)果亦通過表的方式返回給用戶.MLlib[4]是Spark 上原生的機(jī)器學(xué)習(xí)API,它提供了快速、分布式的機(jī)器學(xué)習(xí)算法實現(xiàn).MLlib 具有易于搭建機(jī)器學(xué)習(xí)全流程的API,便于用戶對從數(shù)據(jù)與處理、特征選取、訓(xùn)練模型、驗證的全流程中各種方法進(jìn)行替換.MLog[5]支持類似 SQL 的語法.MLog 將查詢中機(jī)器學(xué)習(xí)運(yùn)算與數(shù)據(jù)庫運(yùn)算分開,在Tensorflow,Keras 等平臺上通過GPU 執(zhí)行機(jī)器學(xué)習(xí)任務(wù),在數(shù)據(jù)庫中執(zhí)行數(shù)據(jù)庫運(yùn)算.由于運(yùn)算分開在不同平臺執(zhí)行,所以會有較大的通信開銷.

? 自動特征選取

機(jī)器學(xué)習(xí)算法使用的數(shù)據(jù)需要包含足夠的有用特征,盡量減少無關(guān)特征.給定一個用于訓(xùn)練機(jī)器學(xué)習(xí)任務(wù)的數(shù)據(jù)庫,數(shù)據(jù)分析師需要耗費很多精力判斷需要連接哪些表、是否需要通過額外的數(shù)據(jù)表增加特征.文獻(xiàn)[6]首先提出,數(shù)據(jù)庫中某些連接是可以避免的,他們提出數(shù)據(jù)庫中一些表主鍵的值可以作為其中新特征的表示,避免與這些表的連接不會對模型的預(yù)測準(zhǔn)確度產(chǎn)生影響.ARDA[7]借助用戶給定的一個用于機(jī)器學(xué)習(xí)任務(wù)的數(shù)據(jù)基表和一個與該任務(wù)可能相關(guān)的大量數(shù)據(jù)表構(gòu)成的數(shù)據(jù)倉庫,自動發(fā)掘數(shù)據(jù)間的潛在連接關(guān)系,并尋找對機(jī)器學(xué)習(xí)任務(wù)幫助大的特征對數(shù)據(jù)集進(jìn)行增強(qiáng).

? 模型訓(xùn)練加速

(1)通過分布式訓(xùn)練加速模型訓(xùn)練,其主要目標(biāo)為提高并行度,降低通信中數(shù)據(jù)與模型的通信代價.LAPSE[8]將數(shù)據(jù)分布于各個計算節(jié)點,實現(xiàn)了在計算節(jié)點之間動態(tài)分配參數(shù).ColumnSGD[9]提出將數(shù)據(jù)按列組織,將模型參數(shù)巧妙拆分,分配到各個計算節(jié)點,支持邏輯回歸、SVM 和部分DNN 模型;

(2)DB4ML[10]提出通過擴(kuò)展SQL 使其支持迭代事務(wù)時,傳統(tǒng)的事務(wù)執(zhí)行過于笨重,該工作針對不同機(jī)器學(xué)習(xí)算法使用不同隔離級別,調(diào)整迭代事務(wù)中MVCC 記錄方式,可以在滿足訓(xùn)練要求條件下大幅提升訓(xùn)練效率.

? 執(zhí)行引擎優(yōu)化

機(jī)器學(xué)習(xí)算法中常會涉及到線性代數(shù)運(yùn)算,對其執(zhí)行進(jìn)行優(yōu)化可以提升訓(xùn)練和推理算法執(zhí)行速度.LARA[11]提出一種新代數(shù),在邏輯表示方式上融合了線性代數(shù)(LA)和關(guān)系代數(shù)(RA),從而獲得了更多優(yōu)化機(jī)會.SPORES[12]引入了對線性代數(shù)表達(dá)式的一種新的通用優(yōu)化方法:構(gòu)建一系列線性代數(shù)表達(dá)式和關(guān)系代數(shù)表達(dá)式之間相互轉(zhuǎn)化的規(guī)則,借助規(guī)則先將線性代數(shù)表達(dá)式轉(zhuǎn)換為關(guān)系代數(shù)表達(dá)式,對后者進(jìn)行優(yōu)化,再將結(jié)果轉(zhuǎn)換回線性代數(shù)表達(dá)式.

當(dāng)前,對模型推理進(jìn)行加速的工作相對少.與本文舉例介紹的通過數(shù)據(jù)庫技術(shù)優(yōu)化決策樹模型推理較為接近的研究為文獻(xiàn)[13],該工作介紹了LinkedIn(領(lǐng)英)對職位搜索和推薦系統(tǒng)的優(yōu)化,他們訓(xùn)練決策樹學(xué)習(xí)文檔特征到文檔質(zhì)量高低的映射,為了獲得top-k文檔,借助決策樹葉子上包含樣本正負(fù)例數(shù)目比例選取部分葉子到根路徑上的條件得到新查詢.本文在技術(shù)上雖然同樣借助了決策樹解釋性強(qiáng)的特點從模型中提取信息,但本文并非解決top-k問題,從而引起從模型中提取的篩選謂詞過多的問題,本文給出了謂詞合并算法加以解決,并提出了通過初篩對含機(jī)器學(xué)習(xí)模型推理謂詞的查詢進(jìn)行優(yōu)化的總體框架.

2 數(shù)據(jù)庫內(nèi)AI 模型工作流程

AI 算法通常包含訓(xùn)練與推理算法,需要通過設(shè)計SQL 接口從語法上分別進(jìn)行支持,SQL 接口的封裝整合了AI 算法與數(shù)據(jù)庫查詢操作,賦予AI 算法聲明式特點,同時也是借助數(shù)據(jù)庫特性進(jìn)行優(yōu)化的前提.為了加速推理執(zhí)行速度,在訓(xùn)練過程中,可以構(gòu)建適合于數(shù)據(jù)庫優(yōu)化的模型,離線提取特征;在推理過程中,可以借助提取出的模型特征設(shè)計數(shù)據(jù)庫算子和機(jī)器學(xué)習(xí)算子的聯(lián)合優(yōu)化.本文以決策樹為例給出訓(xùn)練和推理過程中的優(yōu)化技巧,整體工作流程如圖2 所示,本節(jié)將對其進(jìn)行詳細(xì)介紹.

Fig.2 In-database decision tree optimization workflow圖2 數(shù)據(jù)庫內(nèi)決策樹優(yōu)化工作流程

2.1 決策樹訓(xùn)練SQL的執(zhí)行過程

首先,用戶輸入定義模型的SQL 語句,SELECT 子句中包含DecisionTree.train函數(shù),其參數(shù)依次序分別指定參與訓(xùn)練過程的特征列表(fea_list)、各特征是定類特征或數(shù)值特征(is_numeric)、預(yù)測目標(biāo)列名稱(target_column),以及訓(xùn)練決策樹需要的超參數(shù)(如使用gini系數(shù)或cross entropy、決策樹最大深度等).定義模型訓(xùn)練任務(wù)的SQL 語句首先進(jìn)入數(shù)據(jù)收集器(data collector),收集器會從Decision.train函數(shù)參數(shù)中提取出訓(xùn)練所需的特征列名,通過修改原SQL 語法樹的方式構(gòu)造生成訓(xùn)練數(shù)據(jù)的SQL 語句,進(jìn)而通過數(shù)據(jù)庫獲取訓(xùn)練數(shù)據(jù)集.收集器獲取到訓(xùn)練數(shù)據(jù)后,將訓(xùn)練數(shù)據(jù)與訓(xùn)練超參數(shù)傳遞給訓(xùn)練模塊生成決策樹.

本工作復(fù)現(xiàn)了CART(classification and regression tree)算法[14]進(jìn)行模型訓(xùn)練.在CART 算法之外,亦嘗試修改決策樹訓(xùn)練算法.通過按照表的順序建立決策樹,借助后減枝[15]避免過擬合,在不顯著降低模型準(zhǔn)確度的情況下,獲得更多只包含少量表特征的分支,從而降低推理過程的計算代價,并通過這種方式初步簡化模型以利于提取謂詞,相關(guān)部分見第3.2 節(jié).

訓(xùn)練后的決策樹模型會被傳遞給謂詞提取模塊(predicate extractor).由于謂詞提取過程較為耗時,且可以在進(jìn)行推理前進(jìn)行離線預(yù)處理,故我們會在訓(xùn)練得到?jīng)Q策樹后馬上進(jìn)行謂詞提取,并將提取出的謂詞與原決策樹模型一同存入數(shù)據(jù)庫.決策樹的葉子節(jié)點對應(yīng)一個分類結(jié)果,根到葉子的路徑上每個節(jié)點對應(yīng)一個謂詞,這些謂詞組成的合取表達(dá)式可篩選出到達(dá)這個葉子節(jié)點的數(shù)據(jù).然而,決策樹模型的葉子數(shù)量可能十分龐大,如果用過多葉子節(jié)點對應(yīng)的謂詞共同組成的析取表達(dá)式直接生成SQL 表達(dá)式,相當(dāng)于每條數(shù)據(jù)需要對所有的決策樹分支進(jìn)行判斷,在計算量上是不可接受的,所以謂詞提取步驟是必要的.謂詞提取器會對每個分類結(jié)果對應(yīng)的謂詞析取表達(dá)式進(jìn)行合并,通過適當(dāng)“放寬”條件,獲得能夠描述該類別主要特征的少量謂詞.最終,提取后的謂詞、決策樹模型以及關(guān)于決策樹使用的各特征類型(數(shù)值或者定類)將被存入到數(shù)據(jù)庫中,同時將新創(chuàng)建的模型名稱被返回給用戶,以供包含決策樹推理的SQL 查詢調(diào)用.

2.2 含決策樹推理的SQL查詢優(yōu)化過程

用戶希望借助訓(xùn)練好的決策樹模型篩選預(yù)測值為特定值的數(shù)據(jù)時,可輸入WHERE 子句中包含決策樹推理謂詞的SQL.

查詢首先到達(dá)重寫器(rewriter),重寫器將查詢轉(zhuǎn)化為語法樹,從決策樹推理函數(shù)的參數(shù)中提取出模型名稱與期望篩選的分類結(jié)果.借助模型名稱,重寫器從數(shù)據(jù)庫中取出決策樹模型、被提取出的預(yù)篩選謂詞以及各列特征的類型信息.隨后,重寫器從預(yù)篩選謂詞中取出篩選的分類目標(biāo)對應(yīng)的初篩條件,將其轉(zhuǎn)化為謂詞的語法樹格式后,對決策樹推理謂詞進(jìn)行整體替換.需要注意:當(dāng)決策樹推理謂詞被NOT 否定時,替換過程中有一些細(xì)節(jié)問題需要處理,將在第3.4 中進(jìn)行討論.修改后的語法樹被轉(zhuǎn)換回用于初篩的SQL,在數(shù)據(jù)庫中進(jìn)行執(zhí)行得到初篩后的結(jié)果.初篩后的結(jié)果被送達(dá)驗證模塊.驗證模塊將初篩后的數(shù)據(jù)逐條通過決策樹模型進(jìn)行預(yù)測,篩除不符合用戶輸入語義的部分,將最終結(jié)果返回給用戶.

3 數(shù)據(jù)庫內(nèi)決策樹模型優(yōu)化算法

本節(jié)會從引言部分最后給出的兩個角度入手,引入并詳細(xì)介紹上一節(jié)中決策樹訓(xùn)練與推理優(yōu)化過程中的關(guān)鍵算法.

3.1 通過謂詞篩選執(zhí)行決策樹推理

決策樹推理算法的輸入是一棵決策樹以及一組需要執(zhí)行推理算法的數(shù)據(jù),輸出是這組數(shù)據(jù)中每條的分類結(jié)果.通常的推理算法需要對數(shù)據(jù)中的每個條目,從決策樹根開始,根據(jù)是否滿足節(jié)點所對應(yīng)的謂詞條件選擇向左/右分支前進(jìn),直到走到葉子節(jié)點得到分類結(jié)果.然而,我們也有另一種策略可供選擇,下面舉例介紹.

例:醫(yī)院需要用決策樹模型獲得預(yù)測手術(shù)后住院時間大于等于10 天的患者.數(shù)據(jù)集包含屬性:患者姓名,患者年齡,患者性別,手術(shù)類別,醫(yī)生姓名,醫(yī)生年齡,醫(yī)生職稱.訓(xùn)練后得到圖3 所示的決策樹.

我們可以采用一種從結(jié)果逆推條件、在數(shù)據(jù)中進(jìn)行選擇的方式進(jìn)行決策樹推理.從決策樹中我們可以看出:滿足條件的數(shù)據(jù)在逐條執(zhí)行推理時,必定會到達(dá)值為10,12,15 的葉子之一.到達(dá)值為10 的葉子需滿足(手術(shù)類別=類別AAND 手術(shù)時長≥3h),記為P1;到達(dá)值為12 的葉子需滿足(手術(shù)類別=類別BAND 患者年齡≥30歲 AND 醫(yī)生職稱=主任),記為P2;到達(dá)值為15 的葉子需滿足(手術(shù)類別=類別B AND 患者年齡≥30 歲 AND醫(yī)生職稱=非主任),記為P3.所以我們可以通過條件(P1ORP2ORP3)得到預(yù)測住院時間大于等于10 天的患者.借助這種表示方式,P2和P3可以合并為(手術(shù)類別=類別BAND 患者年齡≥30 歲).對應(yīng)于決策樹上,也就是針對問題對決策樹進(jìn)行了簡化.

Fig.3 An example of decision tree for predicting length of stay圖3 預(yù)測住院時間的決策樹示例

3.2 決策樹訓(xùn)練模型優(yōu)化——按照表的順序構(gòu)建決策樹

繼續(xù)借助上文中的例子,需要進(jìn)行推理的數(shù)據(jù)在醫(yī)院數(shù)據(jù)庫中以多表方式存儲為3 個關(guān)系表:患者(patient),手術(shù)(operation),醫(yī)生(doctor),見表1.

Table 1 Schema of tables in operation information database表1 患者手術(shù)信息數(shù)據(jù)庫示例

借助上文得到的篩選謂詞,這個推理并篩選的過程可以表示為下面的SQL 查詢.

由于構(gòu)建決策樹時,我們的依據(jù)是每個特征將數(shù)據(jù)分割前后的信息增益,選擇信息增益較大的特征,并沒有考慮特征在表中的分布,所以提取出的葉子節(jié)點的謂詞(如P1～P3)中往往含有多個表中的特征.這樣構(gòu)造的SQL查詢在進(jìn)行查詢優(yōu)化時,由于被OR 連接的謂詞中分散著關(guān)于多個表的謂詞,故難以進(jìn)行謂詞下推操作.

我們嘗試在構(gòu)建決策樹時,初始只使用一張表中的特征,之后在構(gòu)建好的樹上,每個葉子節(jié)點作為新的根節(jié)點繼續(xù)使用第2 張表、第3 張表、…,以此類推.在決策樹生長中,使用預(yù)剪枝;在所有表都使用完畢后,使用代價-復(fù)雜性剪枝算法減小過擬合.希望借助這種建樹方式得到更多只使用單表中的特征就可得到分類結(jié)果的分支,使生成的SQL 更利于查詢處理過程中的優(yōu)化.

3.3 決策樹模型推理優(yōu)化——從決策樹中獲得預(yù)篩選謂詞

第3.1 節(jié)提出的謂詞提取方式可能會導(dǎo)致過多葉子節(jié)點對應(yīng)的謂詞進(jìn)行OR 連接.這種情況下,由于OR 連接的謂詞有重疊的部分(如上面例子中,P2與P3都滿足op.type=‘B’以及p.age≥30),推理性能反而會下降.為了減少謂詞的數(shù)量,同時便于查詢優(yōu)化中謂詞下推,我們對直接通過葉子節(jié)點提取出的謂詞進(jìn)行合并,目標(biāo)是得到包含較少謂詞、易于進(jìn)行謂詞下推的SQL 查詢.

為了正式地描述上面的過程,我們首先引入葉子節(jié)點謂詞的定義.

定義1.葉子節(jié)點對應(yīng)的謂詞,記為Pleaf,定義為決策樹根到某個葉子節(jié)點經(jīng)過分支條件的合取,即:

Pleaf中可能存在關(guān)于相同特征列的和,我們進(jìn)行如下處理:當(dāng)該特征是數(shù)值型時,進(jìn)行表2 中的轉(zhuǎn)換;當(dāng)該特征是定類的時,進(jìn)行表3 中的轉(zhuǎn)換.經(jīng)過整理后,各特征列最多在每個Pleaf中出現(xiàn)一次.在到達(dá)葉子節(jié)點路徑上未進(jìn)行選擇的特征列不會出現(xiàn)在Pleaf中,我們使用值為TRUE 的Pleaf項進(jìn)行填充.至此,我們可以得到,其中,n為特征列的數(shù)目,Pileaf為第i個特征列上的謂詞或者常量TRUE.

Table 2 Rules to transform predicates on numeric columns表2 數(shù)值謂詞整理規(guī)則

Table 2 Rules to transform predicates on numeric columns表2 數(shù)值謂詞整理規(guī)則

Table 3 Rules to transform predicates on categorical columns表3 定類謂詞整理規(guī)則

Table 3 Rules to transform predicates on categorical columns表3 定類謂詞整理規(guī)則

3.3.1 謂詞表達(dá)式的合并

所有在篩選范圍內(nèi)的結(jié)果對應(yīng)的葉子節(jié)點記為leaves,借助Pleaf,可以得到通過篩選進(jìn)行推理的謂詞為

如前文所述,#{leaves}可能相當(dāng)多,我們不應(yīng)將如此多Pleaf組成的析取式放到SQL 中進(jìn)行執(zhí)行.注意到:不同對于相同的i,都是關(guān)于第i個特征列的謂詞,通過對不同葉子關(guān)于相同特征列謂詞進(jìn)行合并,我們可以將謂詞降低到特征列數(shù)級別.

命題1.篩選數(shù)據(jù)得到的結(jié)果集合記為R,篩選數(shù)據(jù)得到的結(jié)果集合記為S,則R?S.

命題1 是我們進(jìn)行謂詞合并的依據(jù).通過更改析取和合取操作的順序,相同特征的謂詞可以通過析取運(yùn)算進(jìn)行合并,命題保證了合并后謂詞篩選得到的數(shù)據(jù)不會缺少原先謂詞篩選出的數(shù)據(jù),所以這種合并是保守且可行的.這個命題可以通過數(shù)學(xué)歸納法證明.

證明:對特征列數(shù)目n歸納,記葉子節(jié)點數(shù)#{leaves}為m.

(1)n=1 或m=1,轉(zhuǎn)換前后形式相同,為平凡情況n=2,m>1 時有:

故n≤2 時命題成立;

(2)假設(shè)n=n0?1 時命題1 成立;

(3)當(dāng)n=n0時,通過n=2 的情況以及情形(2)中的歸納假設(shè),可知對n=n0時也成立.□

據(jù)此,對于同特征列上的謂詞,我們通過OR 運(yùn)算進(jìn)行合并.規(guī)則如下.

數(shù)值特征.對于數(shù)值特征,均為區(qū)間形式,計算這些謂詞的析取即為計算這些區(qū)間的并集.可以通過貪心的算法進(jìn)行:按照區(qū)間左端點進(jìn)行排序后進(jìn)行一次遍歷,遍歷中臨近的區(qū)間貪心地擴(kuò)展.

定類特征.對于定類特征,的形式為feature∈S或者feature?S,可根據(jù)表4 進(jìn)行化簡.

Table 4 Rules to merge predicates on categorical columns表4 定類謂詞合并規(guī)則

Table 4 Rules to merge predicates on categorical columns表4 定類謂詞合并規(guī)則

3.3.2 避免謂詞被全部抵消

然而,上述合并方式仍存在一定問題:如果每個特征i都存在TRUE=的葉子,那么最終全部謂詞都會被消去.為了能夠盡可能避免這種情況,并且仍能夠進(jìn)行謂詞下推,我們從以特征為單位進(jìn)行合并轉(zhuǎn)為以表為單位進(jìn)行合并.下面用一個簡單的例子說明.

如表5 所示,有兩個關(guān)系表T1和T2以及4 個特征f1～f4,每一行是一個葉子上對應(yīng)的謂詞.

Table 5 An example in which predicates are all eliminated after merging表5 謂詞全部被消除情況示例

表中每一列均包含TRUE,進(jìn)行第3.3.1 節(jié)中的合并后只能留下TRUE,所有能進(jìn)行數(shù)據(jù)篩選的謂詞全部被消除了.然而我們發(fā)現(xiàn):如果以關(guān)系表為單位考慮,則不存在使T1或者T2中關(guān)于所有特征的謂詞同時為TRUE的葉子.所以我們可以先選擇一個特征,將葉子節(jié)點按照在這個特征上的謂詞是否為常量TRUE 分為兩部分,對為TRUE 的部分使用其他特征的謂詞進(jìn)行描述.即,上表中的謂詞可合并為

這樣合并后,不同關(guān)系表的特征不會通過析取進(jìn)行連接,依然可以直接將各個表的謂詞表達(dá)式下推到底.

3.4 決策樹推理謂詞取反的情況

上文的謂詞合并過程默認(rèn)了決策樹推理謂詞沒有被否定運(yùn)算NOT 修飾.比較隱蔽的一點是:如果決策樹推理謂詞被NOT 修飾,而我們直接將原謂詞替換為模型提取得到的預(yù)篩選表達(dá)式,那么我們會丟失很多本應(yīng)在結(jié)果中的數(shù)據(jù).這是因為:若全部數(shù)據(jù)為U,使用決策樹推理謂詞篩選得到的數(shù)據(jù)集合為Stree,使用提取出的初篩謂詞篩選得到的數(shù)據(jù)集合為Sfilter,那么用決策樹推理謂詞的否定進(jìn)行篩選得到的數(shù)據(jù)集合為UStree,使用初篩謂詞的否定篩選出的數(shù)據(jù)集合為USfilter.由于Sfilter?Stree,所以有Sresult=UStree?USfilter,即:替換后,篩選得到的數(shù)據(jù)丟失了部分本應(yīng)包含在結(jié)果中的數(shù)據(jù).這種情況的解決亦不困難:設(shè)決策樹全部葉子節(jié)點集合為Sleaves,根據(jù)決策樹推理謂詞得到的葉子集合為Starget,那么當(dāng)發(fā)現(xiàn)推理謂詞被NOT 修飾時,使用Sleaves?Starget的葉子節(jié)點集合對應(yīng)的謂詞進(jìn)行合并,便可保證初篩過程不會遺漏最終結(jié)果.

4 實驗與分析

4.1 實驗設(shè)置

4.1.1 數(shù)據(jù)集介紹

本工作使用Kaggle 上公開的Walmart 銷量預(yù)測數(shù)據(jù)集(https://www.kaggle.com/c/walmart-recruiting-storesales-forecasting)進(jìn)行實驗與性能測試.該數(shù)據(jù)集由3 個數(shù)據(jù)表構(gòu)成,分別是Sales(預(yù)測目標(biāo)周銷量),Features(各商店所在地區(qū),各周反映經(jīng)濟(jì)狀況、天氣等的參數(shù)),Store(超市大小,類型).3 個數(shù)據(jù)表的連接關(guān)系如圖4 所示,圖中數(shù)據(jù)表后的括號中為數(shù)據(jù)條數(shù).

Fig.4 Join graph of Walmart sales prediction dataset圖4 Walmart 銷量預(yù)測數(shù)據(jù)集連接關(guān)系

原數(shù)據(jù)中,預(yù)測目標(biāo)Weekly_Sales是浮點數(shù),為了更好地適應(yīng)決策樹算法,以及研究本文中算法關(guān)于結(jié)果數(shù)據(jù)量多少的運(yùn)行效率,我們對Weekly_Sales進(jìn)行等深分箱,并按照銷量從小到大,離散化為等級1,2,…,k.原數(shù)據(jù)中部分屬性值缺失,我們提前使用平均值進(jìn)行填充.

4.1.2 實驗環(huán)境與實現(xiàn)細(xì)節(jié)

本工作使用PostgreSQL 12.2 數(shù)據(jù)庫,將Sales,Features,Store這3 個數(shù)據(jù)表導(dǎo)入.測試用SQL 查詢通過決策樹推理謂詞篩選達(dá)到某個銷量等級的商店與日期,形式如下.

實驗代碼使用python 編寫,借助moz_sql_parser(https://github.com/mozilla/moz-sql-parser)進(jìn)行SQL 查詢語法解析.實驗中,決策樹訓(xùn)練使用Gini指數(shù)作為選取屬性的指標(biāo),按表順序構(gòu)建決策樹時人為指定了順序(Sales,Store,Features).

4.1.3 評測指標(biāo)

關(guān)于按表順序建樹得到的模型與CART 決策樹模型的對比,本工作使用模型大小(葉子節(jié)點總數(shù))、葉子節(jié)點謂詞少于3 個表的數(shù)目、在測試集上預(yù)測準(zhǔn)確率進(jìn)行評價.

對決策樹推理謂詞優(yōu)化效果最直觀的評價指標(biāo)是推理查詢執(zhí)行時間.本工作對比以下幾個執(zhí)行時間:從輸入SQL 到連接數(shù)據(jù)或初篩后數(shù)據(jù)返回的時間tjoin,主要受單表掃描與多表連接用時影響;使用決策樹模型進(jìn)行決策樹推理過程所用時間tpredict;總用時ttotal.

PostgreSQL 支持通過添加EXPLAIN(ANALYZE ON)獲得實際執(zhí)行計劃,本工作通過對比加入初篩謂詞前后執(zhí)行計劃變化分析性能提升原因.

4.2 優(yōu)化效果

4.2.1 執(zhí)行時間測試

圖5 為是否使用決策樹模型中提取出的初篩謂詞對數(shù)據(jù)獲取SQL 在數(shù)據(jù)庫中執(zhí)行效率的影響.橫坐標(biāo)為分類數(shù)目,由于使用了等深分箱,測試用SQL 篩選其中一個類別,故分類數(shù)k越大,最終結(jié)果中數(shù)據(jù)越少,從圖中可看出加速數(shù)據(jù)篩選過程越好,其中,k=20 時的加速比可以達(dá)到43%.表明謂詞被下推到單表,減小了連接運(yùn)算計算量.

Fig.5 Data fetch time comparision between with/without using extracted predicates圖5 初篩謂詞對數(shù)據(jù)獲取過程的加速效果

表6 中列出了結(jié)果數(shù)據(jù)百分比(實驗中通過分類數(shù)控制)、初篩過濾的數(shù)據(jù)占比、初篩+驗證對決策樹推理謂詞加速比之間的關(guān)系.可以看出:初篩過濾移除的數(shù)據(jù)越多,整體加速效果越好,二者數(shù)值上也十分接近.

Table 6 Relationship between speedup ration and proportion of result data表6 加速比與結(jié)果數(shù)據(jù)百分比關(guān)系

4.2.2 從執(zhí)行計劃分析性能提升

分類數(shù)目k=15 時,圖6 與圖7 分別為在獲取數(shù)據(jù)SQL 中是否加入初篩謂詞得到的兩個執(zhí)行計劃,各個執(zhí)行節(jié)點中,actual_time表示實際實行消耗的時間,格式為“準(zhǔn)備時間..執(zhí)行時間”.從執(zhí)行計劃中可以看出,使用了初篩謂詞時,對sales表進(jìn)行掃描的過程中篩掉了183 942 條數(shù)據(jù),用時226.513ms;未使用初篩謂詞時,對sales表進(jìn)行線性掃描耗時63.202ms,故使用初篩謂詞首先會增加掃描數(shù)據(jù)表的代價增加.sales與features表哈希連接前,對features表進(jìn)行了線性掃描后哈希,這個步驟的性能與是否使用初篩謂詞無關(guān),二者用時分別為6.069ms與5.837ms.對于sales與features表進(jìn)行哈希連接的代價,可以通過總時間減去sales表的線性掃描以及features表的線性掃描并哈希的時間,使用初篩謂詞用時125.976ms,未使用初篩謂詞為233.789ms.同理可計算得到最后與store表進(jìn)行連接時,使用初篩謂詞用時83.686ms,未使用初篩謂詞用時114.258ms.驗證了初篩謂詞會加速連接操作的想法.

Fig.6 Execution plan of SQL with extracted predicates圖6 使用初篩謂詞的執(zhí)行計劃

Fig.7 Execution plan of SQL without extracted predicates圖7 未使用初篩謂詞的執(zhí)行計劃

從執(zhí)行計劃可以看出:使用了初篩謂詞后,會增加線性掃描表時的代價,降低連接操作的代價.在上面的例子中,使用初篩謂詞時增加的代價與減小的代價近乎抵消,最終只比未使用初篩謂詞快大約5ms,在系統(tǒng)波動范圍內(nèi)可以視作無差別.

然而實際測試中,k=15 時,使用初篩謂詞獲取數(shù)據(jù)過程的加速比達(dá)到了33.9%.這是因為實驗中優(yōu)化過程作為PostgreSQL 的擴(kuò)展部分,為獨立的進(jìn)程,獲取數(shù)據(jù)過程中會產(chǎn)生進(jìn)程間數(shù)據(jù)拷貝的代價,而這個代價與傳輸數(shù)據(jù)量成正比.故使用初篩謂詞的算法由于過濾掉了44%的數(shù)據(jù),使它的數(shù)據(jù)通信代價大幅減小,最終在數(shù)據(jù)獲取階段優(yōu)于連接全部數(shù)據(jù).

對使用/不使用初篩謂詞的執(zhí)行方法,在獲得數(shù)據(jù)后,均需要進(jìn)行決策樹推理.由于二者的決策樹相同,這個過程的執(zhí)行時間依賴于需要進(jìn)行推理的數(shù)據(jù)條數(shù),故使用謂詞初篩后進(jìn)行推理計算的計算量小于不進(jìn)行初篩的方法.表7 支持這個觀點.

Table 7 Influence of prefilter predicates on inference execution time表7 初篩謂詞對推理執(zhí)行時間的影響

4.3 構(gòu)建決策樹方法的影響

表8 中,按表順序構(gòu)建決策樹時,其與CART 決策樹的預(yù)測準(zhǔn)確度是近似相同的,未造成推理誤差顯著提高.

Table 8 Accurcy comparision between table-order constructed tree and CART表8 按表順序建樹與CART 決策樹準(zhǔn)確率比較

按表順序建樹的目的,是讓訓(xùn)練得到的決策樹模型更多分支上只含較少表中的特征,然而實際測試發(fā)現(xiàn)效果較為有限.表9 中,按表順序建樹后,包含更少表的葉子謂詞增加量不大,絕大多數(shù)葉子對應(yīng)的謂詞仍然與全部3 個數(shù)據(jù)表中的特征相關(guān).

Table 9 Difference of extracted predicates between CART and table-order constructed tree表9 決策樹葉子按照對應(yīng)謂詞相關(guān)的數(shù)據(jù)表統(tǒng)計數(shù)量

模型的結(jié)構(gòu)變化不大,暗示了這種構(gòu)建決策樹的方式對查詢推理的加速效果十分有限.并且從葉子總數(shù)可以看出,按表順序建樹通常會造成模型的葉子數(shù)目增加,即模型復(fù)雜度增加,這對驗證過程的執(zhí)行效率會產(chǎn)生負(fù)面影響.從表10 可以看出:按表順序構(gòu)建出的決策樹執(zhí)行推理查詢時,性能沒有明顯優(yōu)于CART 算法構(gòu)建出的決策樹.

Table 10 Influence of decision tree construction method on query execution time表10 按表順序建立決策樹對查詢執(zhí)行效率的影響

5 其他AI 模型推理優(yōu)化

本文提出初篩方法中使用的初篩謂詞需要從模型中提取,決策樹模型優(yōu)化中的關(guān)鍵步驟——提取根節(jié)點到葉子節(jié)點路徑上的謂詞與其強(qiáng)解釋性密切相關(guān).對于其他AI 模型,機(jī)器學(xué)習(xí)解釋性領(lǐng)域有一些在局部通過強(qiáng)解釋性模型對弱解釋性模型進(jìn)行擬合的方法[16,17]可以帶來啟發(fā).機(jī)器學(xué)習(xí)解釋性領(lǐng)域?qū)τ谀Ｐ驼w解釋性主要考慮方便人類進(jìn)行理解,而選取若干有代表性的單個預(yù)測實例的解釋作為對模型的整體解釋[16].而為了從模型中提取各類別特征需要更強(qiáng)的整體解釋方法,由于從模型提取謂詞是離線進(jìn)行的,可以考慮對特征空間中進(jìn)行適度采樣以構(gòu)建局部和整體解釋的聯(lián)系,這方面仍有待深入探索.

當(dāng)前,機(jī)器學(xué)習(xí)領(lǐng)域也有結(jié)合規(guī)則增強(qiáng)深度模型解釋性的嘗試.文獻(xiàn)[18]中提出了一種基于規(guī)則的層次化模型,并給出了對應(yīng)的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)和對應(yīng)的新訓(xùn)練方法,最終在多個數(shù)據(jù)集上準(zhǔn)確度均能優(yōu)于邏輯回歸、SVM、MLP、GBDT 等模型.我們認(rèn)為:在這類新的具有較強(qiáng)解釋性和較高精度的模型上,本文提出的框架有推廣潛力;且隨著機(jī)器學(xué)習(xí)領(lǐng)域?qū)忉屝缘闹匾曉黾?有望在未來見到更多這類模型.

6 總結(jié)與未來工作

本工作提出了通過預(yù)篩選+驗證對AI 模型推理進(jìn)行優(yōu)化的框架,舉例進(jìn)行了決策樹模型優(yōu)化,并對其他解釋性較弱的模型優(yōu)化思路進(jìn)行了探討.本工作通過擴(kuò)展SQL 支持了決策樹訓(xùn)練與推理,并借助框架對決策樹推理函數(shù)出現(xiàn)在謂詞中的查詢進(jìn)行了優(yōu)化.為了實現(xiàn)預(yù)篩選,本工作給出了從決策樹中提取謂詞并進(jìn)行適當(dāng)合并的算法.此外,本工作也嘗試設(shè)計了按照表順序構(gòu)建決策樹的訓(xùn)練算法,其預(yù)測誤差與標(biāo)準(zhǔn)的決策樹算法沒有顯著差別.在Walmart 銷量預(yù)測任務(wù)上,上述算法達(dá)到了提高包含決策樹推理謂詞的SQL 執(zhí)行效率的目標(biāo).

本工作也引起了我們一些新的思考,未來工作將從以下幾個方面展開:首先,對于本文提出的謂詞提取與合并算法,謂詞數(shù)量和謂詞篩選效果的權(quán)衡中,很可能存在更好的方案有待發(fā)現(xiàn);第二,對決策樹外的機(jī)器學(xué)習(xí)模型,通過構(gòu)建局部解釋性和模型全局特點的聯(lián)系來設(shè)計模型無關(guān)的謂詞提取算法;最后,針對新的解釋性較強(qiáng)的模型,設(shè)計新的謂詞提取算法.