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

廖 蕓，張 驍，廖士中

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

1 引言

在線核選擇（online kernel selection）旨在從候選核集中為在線核學(xué)習(xí)的每回合選擇一個最優(yōu)核，使得累積后悔最小且保證亞線性的累積后悔界。由于在線學(xué)習(xí)實(shí)時性和亞線性后悔界的要求，現(xiàn)有離線核選擇的方法[1-2]和理論[3-4]均不適用于在線核選擇。并且由于在線核選擇需要同時進(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)典的方法，適用于候選核集合是有限的情況。該類方法中，候選核集合中的每個核可看作是一個專家，通過選擇一個核或核的分布來進(jìn)行預(yù)測，每回合各個專家計(jì)算損失并更新下一回合選擇核的策略。權(quán)重更新是基于專家建議框架的在線核選擇中的關(guān)鍵步驟，有效的權(quán)重更新策略可以得到緊的后悔界。Yang 等[6]應(yīng)用指數(shù)加權(quán)平均的方法來更新每回合各個核的權(quán)重，根據(jù)概率分布選出一個最優(yōu)核，并通過在線到批處理的轉(zhuǎn)換給出亞線性的期望后悔界。但該項(xiàng)工作面向的是離線核選擇問題，且每次只更新所選擇的核的權(quán)重。在線核選擇也可以依據(jù)一個準(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]提出基于增量素描核對齊的在線核選擇方法，對于強(qiáng)凸損失函數(shù)具有最優(yōu)O(lnT)的后悔界，并且每回合具有常數(shù)的時間和空間復(fù)雜度。文獻(xiàn)[10]提出基于局部后悔的在線核選擇方法，具有亞線性后悔和關(guān)于回合數(shù)對數(shù)的時間復(fù)雜度。

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

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

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

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

2 預(yù)備知識

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

2.1 在線核選擇

在線核選擇問題旨在在線地選擇一個核序列，使得所選擇的假設(shè)（序列）能得到亞線性的后悔界。文獻(xiàn)[6]提出一個在線核選擇算法（online kernel selection，OKS）。應(yīng)用指數(shù)加權(quán)預(yù)測的專家建議框架，在第t回合更新m個專家的第i個專家下一回合的權(quán)重wt,i，根據(jù)所選的核與調(diào)用的子算法得到對應(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個專家的損失，η為步長，λ為正則化參數(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)作為研究競爭比的工具，設(shè)置從wt-1到wt會產(chǎn)生移動代價(jià)。與專家建議框架不同的是，根據(jù)觀察到第t回合的代價(jià)，給出分布wt再進(jìn)行預(yù)測。度量任務(wù)系統(tǒng)一般用競爭性分析作為理論保證，并與最優(yōu)離線序列相比較。考慮α-不公平競爭比：

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

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

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

可按下式統(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，則對任意的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個專家的損失，η為步長，λ為正則化參數(shù)，δ∈(0,1)為OKS 算法的平滑參數(shù)。

證明記Wt=

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

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

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

又由原定理證明可得：

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

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

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

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

下面定義統(tǒng)一框架觀點(diǎn)下在線核選擇的幾個相關(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的每個分量對應(yīng)著候選核集合中不同核在每回合的重要程度。即wt-1,i為回合t專家i的權(quán)重。注意，若權(quán)重或概率分布為一確定分布（wt-1的分量只有一個分量為1，其余的都為0），則期望在線核選擇退化為一般的在線核選擇。

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

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

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

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

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

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

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

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

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

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

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

5 理論結(jié)果

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

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

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

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

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

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

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

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

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

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

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

證明同上。 □

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

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

其中

可得如下定理。

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

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

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

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

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

則由式（7）可得：

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

由定理4可得如下競爭比。

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

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

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

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

證明依據(jù)定理4的證明和定理3結(jié)果可證。□

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

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

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

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

6 結(jié)束語

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

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