統(tǒng)一框架下在線核選擇的競(jìng)爭(zhēng)性分析*

廖 蕓，張 驍，廖士中

天津大學(xué) 智能與計(jì)算學(xué)部，天津300350

1 引言

在線核選擇（online kernel selection）旨在從候選核集中為在線核學(xué)習(xí)的每回合選擇一個(gè)最優(yōu)核，使得累積后悔最小且保證亞線性的累積后悔界。由于在線學(xué)習(xí)實(shí)時(shí)性和亞線性后悔界的要求，現(xiàn)有離線核選擇的方法[1-2]和理論[3-4]均不適用于在線核選擇。并且由于在線核選擇需要同時(shí)進(jìn)行模型的訓(xùn)練和選擇，其實(shí)現(xiàn)方法和理論分析較離線核選擇和一般的在線核學(xué)習(xí)更為復(fù)雜。因而近年來，在線核選擇研究受到機(jī)器學(xué)習(xí)界的關(guān)注。

已有的在線核選擇方法可分為專家建議框架（expert advice framework，EAF）和核學(xué)習(xí)（kernel learning）兩類。在綜述文獻(xiàn)[5]中詳細(xì)介紹了在線核選擇的現(xiàn)有方法。在線核選擇的專家建議框架方法是最經(jīng)典的方法，適用于候選核集合是有限的情況。該類方法中，候選核集合中的每個(gè)核可看作是一個(gè)專家，通過選擇一個(gè)核或核的分布來進(jìn)行預(yù)測(cè)，每回合各個(gè)專家計(jì)算損失并更新下一回合選擇核的策略。權(quán)重更新是基于專家建議框架的在線核選擇中的關(guān)鍵步驟，有效的權(quán)重更新策略可以得到緊的后悔界。Yang 等[6]應(yīng)用指數(shù)加權(quán)平均的方法來更新每回合各個(gè)核的權(quán)重，根據(jù)概率分布選出一個(gè)最優(yōu)核，并通過在線到批處理的轉(zhuǎn)換給出亞線性的期望后悔界。但該項(xiàng)工作面向的是離線核選擇問題，且每次只更新所選擇的核的權(quán)重。在線核選擇也可以依據(jù)一個(gè)準(zhǔn)則，并通過更新核參數(shù)來學(xué)習(xí)核。這種方法稱為自適應(yīng)核方法或核學(xué)習(xí)方法，該方法的效果依賴于原始設(shè)定的核參數(shù)。文獻(xiàn)[7]通過應(yīng)用梯度下降方法來更新核參數(shù)，從而得到核序列。文獻(xiàn)[8]提出一種基于隨機(jī)傅里葉特征的在線核選擇方法，采用在線梯度下降來更新核參數(shù)。這兩項(xiàng)工作均沒有給出所提出方法的理論保證。文獻(xiàn)[9]提出基于增量素描核對(duì)齊的在線核選擇方法，對(duì)于強(qiáng)凸損失函數(shù)具有最優(yōu)O(lnT)的后悔界，并且每回合具有常數(shù)的時(shí)間和空間復(fù)雜度。文獻(xiàn)[10]提出基于局部后悔的在線核選擇方法，具有亞線性后悔和關(guān)于回合數(shù)對(duì)數(shù)的時(shí)間復(fù)雜度。

不同于離線核選擇的評(píng)價(jià)方法，在線核選擇常采用后悔分析的評(píng)價(jià)方法，即分析并比較所選擇的核的累計(jì)損失與對(duì)手環(huán)境下最優(yōu)預(yù)測(cè)的累計(jì)損失之差。文獻(xiàn)[11]系統(tǒng)綜述了專家建議框架下在線凸優(yōu)化算法的后悔分析。由于必須考慮對(duì)手的環(huán)境的設(shè)定，因而也可以采用博弈問題中的競(jìng)爭(zhēng)性分析的評(píng)價(jià)方法。

競(jìng)爭(zhēng)性分析旨在選取競(jìng)爭(zhēng)比最小的方案。競(jìng)爭(zhēng)比最早定義為在線算法的代價(jià)與最優(yōu)離線算法的代價(jià)的最大比率[12]。該文獻(xiàn)也詳細(xì)綜述了競(jìng)爭(zhēng)性分析的問題和方法。亞線性的后悔表明在線決策者與離線最優(yōu)決策差距不會(huì)太大，而常數(shù)倍的競(jìng)爭(zhēng)比表明在線決策者與離線最優(yōu)決策幾乎可以一樣好[13]。通過競(jìng)爭(zhēng)比也可以得到預(yù)測(cè)者的后悔，此種后悔界說明對(duì)手越強(qiáng)預(yù)測(cè)者的后悔越小。競(jìng)爭(zhēng)性分析可以從一個(gè)新的角度來評(píng)價(jià)在線核選擇方法性能的優(yōu)劣。已有的在線核選擇理論關(guān)注在線核選擇的靜態(tài)后悔（static regret）分析，即競(jìng)爭(zhēng)假設(shè)為單個(gè)假設(shè)的情形，而缺乏在競(jìng)爭(zhēng)假設(shè)為假設(shè)序列的情形下對(duì)在線核選擇競(jìng)爭(zhēng)比的分析。

原始對(duì)偶方法是設(shè)計(jì)競(jìng)爭(zhēng)性在線算法和證明競(jìng)爭(zhēng)比的常用方法[14]，也被拓展到非線性規(guī)劃用來處理無法自然松弛到線性規(guī)劃的問題[15]。度量任務(wù)系統(tǒng)（metric task system，MTS）常應(yīng)用競(jìng)爭(zhēng)分析來評(píng)價(jià)性能，并且度量任務(wù)系統(tǒng)的競(jìng)爭(zhēng)比可以不依賴于回合數(shù)[16]。度量任務(wù)系統(tǒng)雖與專家建議框架類似，但二者也有本質(zhì)的不同：前者是已知代價(jià)再給預(yù)測(cè)（1-lookahead），后者是先預(yù)測(cè)再給出代價(jià)（0-lookahead）。這使得二者雖然過程相似但很難放在一個(gè)統(tǒng)一的框架中進(jìn)行分析[17]。Buchbinder等基于專家建議框架和度量任務(wù)系統(tǒng)的相似性，將二者放在統(tǒng)一框架中進(jìn)行分析。雖然二者理論度量不同，但采用原始對(duì)偶方法，既可以得到亞線性后悔，也可以得到較小的競(jìng)爭(zhēng)比[18]。注意到?jīng)]有在線學(xué)習(xí)算法可以同時(shí)得到亞線性的后悔和常數(shù)倍的競(jìng)爭(zhēng)比[13]，該項(xiàng)統(tǒng)一框架工作非常值得關(guān)注。

已有在線核選擇工作只采用了后悔分析的評(píng)價(jià)方法，既沒有采用競(jìng)爭(zhēng)性分析的評(píng)價(jià)方法，更沒有嘗試后悔分析與競(jìng)爭(zhēng)性分析統(tǒng)一框架的工作?；谶@一分析，提出期望在線核選擇的概念，拓廣了在線核選擇的概念，并將期望在線核選擇問題歸約為專家建議框架問題。通過應(yīng)用專家建議框架和度量任務(wù)系統(tǒng)的統(tǒng)一框架，同時(shí)給出期望在線核選擇的亞線性后悔界和各類競(jìng)爭(zhēng)比保證，將現(xiàn)有在線核選擇研究推向新的階段，為將來在線核選擇研究開辟新的途徑。

2 預(yù)備知識(shí)

定義所用到的符號(hào)并介紹相關(guān)概念。樣本序列S={(x1,y1),(x2,y2),…,(xT,yT)}，其中(xt,yt)∈X×Y，X 為輸入空間，Y 為輸出空間。損失函數(shù)也稱代價(jià)函數(shù)定義為c:Y×Y →?。令核函數(shù)κ對(duì)應(yīng)的再生核希爾伯特空間為Hκ，Hκ中假設(shè)f∈Hκ的范數(shù)記為||f||Hκ。記[T]={1,2,…,T}，并定義：

2.1 在線核選擇

在線核選擇問題旨在在線地選擇一個(gè)核序列，使得所選擇的假設(shè)（序列）能得到亞線性的后悔界。文獻(xiàn)[6]提出一個(gè)在線核選擇算法（online kernel selection，OKS）。應(yīng)用指數(shù)加權(quán)預(yù)測(cè)的專家建議框架，在第t回合更新m個(gè)專家的第i個(gè)專家下一回合的權(quán)重wt,i，根據(jù)所選的核與調(diào)用的子算法得到對(duì)應(yīng)的假設(shè)序列fi，i∈[m]，進(jìn)而給出期望意義下的后悔界。

定理1[6]假設(shè)損失0≤ct,i≤L且||??(?,?)||≤G，i∈[N]，t∈[T]，則OKS算法的后悔界為：

其中，ct,i表示第t回合選擇第i個(gè)專家的損失，η為步長(zhǎng)，λ為正則化參數(shù)，δ∈(0,1)為OKS 算法的平滑參數(shù)。

2.2 專家建議與度量任務(wù)系統(tǒng)的統(tǒng)一框架

專家建議框架（EAF）與度量任務(wù)系統(tǒng)（MTS）均是在線學(xué)習(xí)算法的數(shù)學(xué)模型。在線學(xué)習(xí)的專家建議框架與在線決策的度量任務(wù)系統(tǒng)既有相似又有區(qū)別，二者的統(tǒng)一框架中既可分別得到相應(yīng)的理論保證，又可研究不同理論之間的關(guān)系。

文獻(xiàn)[16]最早介紹度量任務(wù)系統(tǒng)模型，并給出形式化定義。度量任務(wù)系統(tǒng)作為研究競(jìng)爭(zhēng)比的工具，設(shè)置從wt-1到wt會(huì)產(chǎn)生移動(dòng)代價(jià)。與專家建議框架不同的是，根據(jù)觀察到第t回合的代價(jià)，給出分布wt再進(jìn)行預(yù)測(cè)。度量任務(wù)系統(tǒng)一般用競(jìng)爭(zhēng)性分析作為理論保證，并與最優(yōu)離線序列相比較?？紤]α-不公平競(jìng)爭(zhēng)比：

其中，α是與專家建議框架放在統(tǒng)一框架中討論的參數(shù)，α≥1。當(dāng)α≠1 時(shí)可弱化競(jìng)爭(zhēng)，此時(shí)最優(yōu)序列的移動(dòng)代價(jià)要大于預(yù)測(cè)序列的移動(dòng)代價(jià)。當(dāng)α→∞，等同于在線環(huán)境下的最優(yōu)分布，即與固定的最優(yōu)分布相比較。

專家建議框架也可考慮更強(qiáng)的專家——漂移專家（drifting experts），即預(yù)測(cè)分布序列與最優(yōu)分布序列對(duì)比，且最優(yōu)分布序列滿足如下約束：

專家建議框架與度量任務(wù)系統(tǒng)的統(tǒng)一框架方法，主要思想是將在線度量任務(wù)系統(tǒng)與在線學(xué)習(xí)專家建議框架放入統(tǒng)一框架中，同步更新權(quán)重w，可同時(shí)得到亞線性后悔和較低的競(jìng)爭(zhēng)比。記：

可按下式統(tǒng)一更新wt,i:

算法1 是專家建議框架與度量任務(wù)系統(tǒng)統(tǒng)一框架算法。

算法1EAF與MTS的統(tǒng)一框架

3 OKS算法后悔界的改進(jìn)

先給出Hoeffding引理。

引理1令X為隨機(jī)變量且滿足a≤X≤b，則對(duì)任意的s∈?，有：

應(yīng)用引理1可改進(jìn)定理1的后悔界如下。

定理2假設(shè)損失0≤ct,i≤L且||??(?,?)||≤G，i∈[N],t∈[T]，則OKS算法的改進(jìn)后悔界為：

其中，ct,i表示第t回合選擇第i個(gè)專家的損失，η為步長(zhǎng)，λ為正則化參數(shù)，δ∈(0,1)為OKS 算法的平滑參數(shù)。

證明記Wt=

應(yīng)用引理1 可改進(jìn)ln(Wt/Wt-1)的上界。只列關(guān)鍵步驟。由原文可得=I(it=i)，且。其中為第t回合第i個(gè)核的概率。對(duì)t∈[T]：

其中，Li,t-1為前t-1 個(gè)回合的累積損失。由引理1可得式（5）的上界：

其中，上述的不等式依賴于損失函數(shù)在第一項(xiàng)上的凸性。整理前T回合可得：

又由原定理證明可得：

聯(lián)立上下界可得：

與式（1）相比較可得定理2給出的后悔界較定理1 給出的在常數(shù)項(xiàng)上改進(jìn)4 倍。當(dāng)回合數(shù)較小時(shí)，該后悔界會(huì)有顯著的提升。但后悔界的改進(jìn)不能直接得到更優(yōu)的競(jìng)爭(zhēng)比，有以下兩點(diǎn)原因：（1）定理2中的后悔為靜態(tài)后悔，即競(jìng)爭(zhēng)策略為單個(gè)專家的預(yù)測(cè)，而競(jìng)爭(zhēng)比中的競(jìng)爭(zhēng)策略為專家序列的預(yù)測(cè)；（2）定理2中后悔界是由損失函數(shù)曲率參數(shù)和假設(shè)的范數(shù)表示的，而競(jìng)爭(zhēng)比分析需要將后悔界表示為最優(yōu)專家的累計(jì)損失。

4 統(tǒng)一框架下的在線核選擇

在線核選擇旨在每回合選擇一個(gè)最優(yōu)核以使累積后悔最小。可將在線核選擇問題歸約為專家建議框架問題，每個(gè)專家可以對(duì)應(yīng)一個(gè)核，專家每回合的代價(jià)即為對(duì)應(yīng)核的預(yù)測(cè)損失。

下面定義統(tǒng)一框架觀點(diǎn)下在線核選擇的幾個(gè)相關(guān)概念。

定義1（期望在線核選擇）給定候選核集合K={κ1,κ2,…,κN}，設(shè)||wt||1=1，wt,i≥0，t∈[T]，i∈[N]。期望在線核選擇第t回合依據(jù)概率分布wt-1選擇最優(yōu)核κit∈K，其中it～wt-1，it∈[N]。

期望在線核選擇中的wt的每個(gè)分量對(duì)應(yīng)著候選核集合中不同核在每回合的重要程度。即wt-1,i為回合t專家i的權(quán)重。注意，若權(quán)重或概率分布為一確定分布（wt-1的分量只有一個(gè)分量為1，其余的都為0），則期望在線核選擇退化為一般的在線核選擇。

由于與不同類型的專家相比可引出不同的后悔和競(jìng)爭(zhēng)性分析，故下面給出不同的后悔與競(jìng)爭(zhēng)比的定義。

定義2（最優(yōu)分布核后悔）期望在線核選擇的最優(yōu)分布核后悔為：

其中，ct為回合t每個(gè)核預(yù)測(cè)的代價(jià)，w*為候選核集合的最優(yōu)分布。

上述定義中的最優(yōu)分布為離線條件下得到的最優(yōu)分布，此時(shí)可應(yīng)用原始的競(jìng)爭(zhēng)性分析方法。

下面給出針對(duì)漂移專家的期望在線核選擇的后悔定義。

定義3（最優(yōu)分布序列核后悔）期望在線核選擇的最優(yōu)分布序列核后悔為：

定義3中后悔的競(jìng)爭(zhēng)策略為最優(yōu)分布序列核，但最優(yōu)分布序列核的性能不能評(píng)價(jià)該后悔上界的優(yōu)劣，即后悔上界不可由最優(yōu)分布序列核的累積損失表示。而競(jìng)爭(zhēng)比可以建立最優(yōu)分布序列核的累積損失和后悔上界的關(guān)系，因此考慮應(yīng)用專家建議框架與度量任務(wù)系統(tǒng)的統(tǒng)一框架來進(jìn)行期望在線核選擇問題的理論分析，既可以得到一個(gè)較低的競(jìng)爭(zhēng)比，又可以得到具有競(jìng)爭(zhēng)意義的亞線性后悔界。為此給出期望在線核選擇的競(jìng)爭(zhēng)比定義。

定義4（最優(yōu)分布核競(jìng)爭(zhēng)比）對(duì)于期望在線核選擇問題，T回合依據(jù)所選擇分布wt-1得到的期望累計(jì)損失，與最優(yōu)分布核的競(jìng)爭(zhēng)比定義為最小的β，使得對(duì)任意的損失向量ct有：

其中，d為獨(dú)立于回合T的常數(shù)。

定義5（最優(yōu)分布序列核競(jìng)爭(zhēng)比）對(duì)于期望在線核選擇問題，T回合依據(jù)所選擇分布wt-1得到的期望累計(jì)損失，與最優(yōu)分布序列核的競(jìng)爭(zhēng)比定義為最小的β′，使得對(duì)任意的損失向量ct有：

其中，d為獨(dú)立于回合T的常數(shù)。若競(jìng)爭(zhēng)比為β，也可稱為是β-競(jìng)爭(zhēng)的。

5 理論結(jié)果

期望在線核選擇問題歸約為專家建議框架問題后，可應(yīng)用專家建議框架與度量任務(wù)系統(tǒng)的統(tǒng)一框架來更新權(quán)重wt,i。在文獻(xiàn)[18]工作的基礎(chǔ)上，可得到如下定理。

定理3對(duì)于期望在線核選擇問題，假設(shè)每個(gè)回合所選擇核的預(yù)測(cè)代價(jià)為ct,i∈[0,1]，α(α≥1)為不公平競(jìng)爭(zhēng)比中的參數(shù)（見式（2）），η為式（3）中更新w的參數(shù)。對(duì)任意的α≥1,η＞0，可分別得到如下的最優(yōu)分布核競(jìng)爭(zhēng)比和最優(yōu)分布序列核競(jìng)爭(zhēng)比。

（1）若α→∞，則統(tǒng)一框架所選擇的核序列關(guān)于最優(yōu)分布核是(1+η)-競(jìng)爭(zhēng)的。

（2）若α=lnN/η，則統(tǒng)一框架所選擇的核序列關(guān)于最優(yōu)分布序列核為(1+3η)-競(jìng)爭(zhēng)的。

定理3 的結(jié)論是在損失函數(shù)值域?yàn)閇0，1]時(shí)得到的。當(dāng)損失函數(shù)的值域擴(kuò)展后，下面兩個(gè)推論分別給出期望在線核選擇在統(tǒng)一框架下，所選擇的核序列的累計(jì)損失關(guān)于最優(yōu)動(dòng)態(tài)核序列累積損失和最優(yōu)靜態(tài)核累積損失的競(jìng)爭(zhēng)比。

推論1當(dāng)用所選擇的核預(yù)測(cè)得到的損失函數(shù)ct,i∈[0,M]時(shí)，由定理3 的條件可得，統(tǒng)一框架所選擇的核序列關(guān)于最優(yōu)分布序列核是(1+3η)-競(jìng)爭(zhēng)的。

證明考慮將損失函數(shù)映射到[0，1]后再帶入到定理3。當(dāng)損失函數(shù)ct,i∈[0,M]時(shí)，可將損失函數(shù)成比例縮減為：

帶入定理3中再依據(jù)條件2可得：

由此可得，當(dāng)損失函數(shù)值域?yàn)閇0,M]時(shí)，仍可得到(1+3η)的競(jìng)爭(zhēng)比。 □

由推論1 給出的后悔界（6）可知，每回合的最優(yōu)核序列預(yù)測(cè)的累計(jì)損失越小，得到的后悔界越好，且當(dāng)損失函數(shù)為[-M,0 ]時(shí)，可得到同樣的競(jìng)爭(zhēng)比。但當(dāng)損失函數(shù)閾值為[-M,M] 時(shí)，做映射：

推論2當(dāng)損失函數(shù)的值域?yàn)閏t,i∈[0,M]時(shí)，依據(jù)定理3的條件可得，統(tǒng)一框架所選擇的核序列關(guān)于最優(yōu)分布核仍是(1+η)-競(jìng)爭(zhēng)的。

證明同上。 □

對(duì)于有監(jiān)督的在線核學(xué)習(xí)問題，期望在線核選擇在第t回合選擇最優(yōu)核后，需要給出預(yù)測(cè)。假設(shè)第t回合的預(yù)測(cè)由在線核學(xué)習(xí)方法OKL(it)（應(yīng)用核）產(chǎn)生的假設(shè)給出。令第t回合所選擇的核在(xt,yt)上的損失為：

其中，?(?,?)為損失函數(shù)。定義Regret(i)為OKL(i)的后悔界，i∈[N]，即：

其中

可得如下定理。

定理4對(duì)于期望在線核選擇，假設(shè)每回合核選擇的概率分布由式（3）產(chǎn)生。假設(shè)損失函數(shù)?(?,?)是L-利普希茨連續(xù)的且?(0,yt)=0,t∈[T]。令≤W，t∈[T]，α和η滿足定理3中條件，則：

其中，Hκ為κ對(duì)應(yīng)的再生核希爾伯特空間。

證明由損失函數(shù)的L-利普希茨連續(xù)性可得：

由于?(0,yt)=0，i∈[T]，則：

令ct為定義3中的代價(jià)，有：

則由式（7）可得：

最終由推論2可得結(jié)論。 □

由定理4可得如下競(jìng)爭(zhēng)比。

推論3對(duì)于有監(jiān)督在線核學(xué)習(xí)問題，若損失函數(shù)滿足定理4中的條件，且：

則統(tǒng)一框架所選擇的核序列關(guān)于最優(yōu)分布核是[1+(1+γ)η+γ]-競(jìng)爭(zhēng)的。

上面的定理考慮的是最優(yōu)核的后悔和競(jìng)爭(zhēng)比，下面定理考慮最優(yōu)分布核序列的后悔和競(jìng)爭(zhēng)比。

定理5對(duì)于期望在線核選擇，假設(shè)每回合核選擇的概率分布由式（3）產(chǎn)生。定義OKL(i)關(guān)于的后悔界為Regret(i)，i∈[N]，若同樣滿足定理4 的條件，則對(duì)于最優(yōu)分布核序列有：

證明依據(jù)定理4的證明和定理3結(jié)果可證?！?/p>

由上述定理可得最優(yōu)分布核序列的競(jìng)爭(zhēng)比。

推論4對(duì)于有監(jiān)督在線核學(xué)習(xí)問題，若損失函數(shù)滿足定理5中的條件，且：

則統(tǒng)一框架所選擇的核序列關(guān)于最優(yōu)分布核序列是[1+3(1+γ′)η+γ′]-競(jìng)爭(zhēng)的。

統(tǒng)一框架針對(duì)在線核選擇問題，可給出關(guān)于最優(yōu)核及最優(yōu)核序列的后悔界，對(duì)η取特殊值，可得到亞線性的后悔界。同時(shí)，此方法也可給出對(duì)于不同競(jìng)爭(zhēng)假設(shè)的競(jìng)爭(zhēng)比。

6 結(jié)束語

提出期望在線核選擇的概念，將期望在線核選擇問題歸約為專家建議框架問題，并應(yīng)用專家建議框架和度量任務(wù)系統(tǒng)的統(tǒng)一框架，分析了期望在線核選擇的后悔界和競(jìng)爭(zhēng)比。在統(tǒng)一框架下，不僅可全面拓展在線核選擇的概念，涵蓋期望意義和概念飄移情形下的在線核選擇，又可同時(shí)研究這類在線核選擇的后悔收斂性和競(jìng)爭(zhēng)性，是在線核選擇的一項(xiàng)嶄新的研究工作。由于已有在線核選擇問題是期望在線核選擇問題的特例，這項(xiàng)工作更具一般性的理論價(jià)值，為在線核選擇的未來研究工作開辟了新的途徑。

應(yīng)用統(tǒng)一框架不僅能給出較好的理論保證，也揭示出在對(duì)手環(huán)境下，對(duì)手的累計(jì)損失越小，在線核選擇的競(jìng)爭(zhēng)性越強(qiáng)。進(jìn)一步工作擬研究新的專家權(quán)重更新方法以提高在線核選擇的競(jìng)爭(zhēng)性和收斂率。