統一框架下在線核選擇的競爭性分析*

廖 蕓，張 驍，廖士中

天津大學 智能與計算學部，天津300350

1 引言

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

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

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

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

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

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

2 預備知識

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

2.1 在線核選擇

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

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

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

2.2 專家建議與度量任務系統的統一框架

專家建議框架（EAF）與度量任務系統（MTS）均是在線學習算法的數學模型。在線學習的專家建議框架與在線決策的度量任務系統既有相似又有區別，二者的統一框架中既可分別得到相應的理論保證，又可研究不同理論之間的關系。

文獻[16]最早介紹度量任務系統模型，并給出形式化定義。度量任務系統作為研究競爭比的工具，設置從wt-1到wt會產生移動代價。與專家建議框架不同的是，根據觀察到第t回合的代價，給出分布wt再進行預測。度量任務系統一般用競爭性分析作為理論保證，并與最優離線序列相比較。考慮α-不公平競爭比：

其中，α是與專家建議框架放在統一框架中討論的參數，α≥1。當α≠1 時可弱化競爭，此時最優序列的移動代價要大于預測序列的移動代價。當α→∞，等同于在線環境下的最優分布，即與固定的最優分布相比較。

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

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

可按下式統一更新wt,i:

算法1 是專家建議框架與度量任務系統統一框架算法。

算法1EAF與MTS的統一框架

3 OKS算法后悔界的改進

先給出Hoeffding引理。

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

應用引理1可改進定理1的后悔界如下。

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

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

證明記Wt=

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

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

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

又由原定理證明可得：

聯立上下界可得：

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

4 統一框架下的在線核選擇

在線核選擇旨在每回合選擇一個最優核以使累積后悔最小?？蓪⒃诰€核選擇問題歸約為專家建議框架問題，每個專家可以對應一個核，專家每回合的代價即為對應核的預測損失。

下面定義統一框架觀點下在線核選擇的幾個相關概念。

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

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

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

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

其中，ct為回合t每個核預測的代價，w*為候選核集合的最優分布。

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

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

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

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

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

其中，d為獨立于回合T的常數。

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

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

5 理論結果

期望在線核選擇問題歸約為專家建議框架問題后，可應用專家建議框架與度量任務系統的統一框架來更新權重wt,i。在文獻[18]工作的基礎上，可得到如下定理。

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

（1）若α→∞，則統一框架所選擇的核序列關于最優分布核是(1+η)-競爭的。

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

定理3 的結論是在損失函數值域為[0，1]時得到的。當損失函數的值域擴展后，下面兩個推論分別給出期望在線核選擇在統一框架下，所選擇的核序列的累計損失關于最優動態核序列累積損失和最優靜態核累積損失的競爭比。

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

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

帶入定理3中再依據條件2可得：

由此可得，當損失函數值域為[0,M]時，仍可得到(1+3η)的競爭比。 □

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

推論2當損失函數的值域為ct,i∈[0,M]時，依據定理3的條件可得，統一框架所選擇的核序列關于最優分布核仍是(1+η)-競爭的。

證明同上。 □

對于有監督的在線核學習問題，期望在線核選擇在第t回合選擇最優核后，需要給出預測。假設第t回合的預測由在線核學習方法OKL(it)（應用核）產生的假設給出。令第t回合所選擇的核在(xt,yt)上的損失為：

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

其中

可得如下定理。

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

其中，Hκ為κ對應的再生核希爾伯特空間。

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

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

令ct為定義3中的代價，有：

則由式（7）可得：

最終由推論2可得結論。 □

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

推論3對于有監督在線核學習問題，若損失函數滿足定理4中的條件，且：

則統一框架所選擇的核序列關于最優分布核是[1+(1+γ)η+γ]-競爭的。

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

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

證明依據定理4的證明和定理3結果可證。□

由上述定理可得最優分布核序列的競爭比。

推論4對于有監督在線核學習問題，若損失函數滿足定理5中的條件，且：

則統一框架所選擇的核序列關于最優分布核序列是[1+3(1+γ′)η+γ′]-競爭的。

統一框架針對在線核選擇問題，可給出關于最優核及最優核序列的后悔界，對η取特殊值，可得到亞線性的后悔界。同時，此方法也可給出對于不同競爭假設的競爭比。

6 結束語

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

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