劉清華，廖士中

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

0 引言

在線核學習需要在后悔界和計算復雜度之間做出權衡，具體是指在線學習算法在降低計算復雜度的同時，必須保證一個關于回合數(shù)T的亞線性后悔界。在線線性學習中，在線梯度下降（Online Gradient Descent，OGD）是高效且通用的算法，但可能會遭遇“核化詛咒”（Curse of Kernelization）［1-4］。隨著回合數(shù)T的增加，核矩陣的規(guī)模也會逐漸增大，使得處理核矩陣的時間會大幅增加，從而導致計算復雜度提高。

在線核學習中有多種方法用于避免核化詛咒的發(fā)生。

有些方法是基于對支持向量（Support Vector，SV）的維護：預算維護策略的主要思想是維護一個規(guī)模有限的支持向量集合，每回合的計算復雜度至多是支持向量集的規(guī)模的多項式級；隨機預算感知機（Randomized Budget Perceptron，RBP）［5］、Forgetron［6］、預算在線梯度下降（Budget Online Gradient Descent，BOGD）以及預算感知機［7］都是遵循不同的策略，在每回合舍棄一些支持向量。除此之外，很多方法還會通過對支持向量的投影或歸并操作來維護支持向量集。

有些方法基于核函數(shù)近似技術，比如傅里葉在線梯度下降（Fourier Online Gradient Descent，F(xiàn)OGD）和Nystr?m 在線梯度下降（Nystr?m Online Gradient Descent，NOGD）［8］。NOGD應用Nystr?m 方法近似核矩陣，然后再應用在線梯度下降方法進行學習。相關文獻已經證得NOGD 是一個通用框架，且在所有現(xiàn)存方法中有相當可觀的性能表現(xiàn)。

跟導（Follow-The-Leader，F(xiàn)TL）［9］方法是在線凸優(yōu)化中一個很重要的思想，該方法考慮所有過往的回合來獲得當前的假設，具體來說，當前假設應使得過往所有回合的累計損失最小。首先用Nystr?m 方法近似核矩陣，然后提出一個新穎的梯度下降方法用于后續(xù)的學習。參考FTL 的思想，在第t回合中，使用前t-1 回合的累計損失的平均梯度來做梯度下降，將這種方法稱為跟導在線核回歸（FTL-Online Kernel Regression，F(xiàn)-OKR）。后面會給出該方法的亞線性后悔界。

為了給F-OKR 方法加速，選擇應用素描方法嵌入其中，素描技術廣泛應用于流數(shù)據學習的領域［10-15］。Ye 等［16］提出了一種基于素描技術的方法來近似矩陣乘法，用于在線典型相關性分析（Canonical Correlation Analysis，CCA），并且證明了該方法的空間復雜度比現(xiàn)存其他CCA 方法都低；文獻［17］中提出了應用高斯隨機投影、頻繁方向（Frequent Directions，F(xiàn)D）、Oja 素描來近似二階在線學習中高計算復雜度的海森陣（Hessian），并提出了素描在線牛頓法（Sketched Online Newton，SON），該方法的時間復雜度是關于特征維度線性的，同時后悔界為亞線性的；張驍?shù)龋?8］應用隨機素描技術構造假設空間素描，在此基礎上研究在線模型選擇，給出系統(tǒng)的在線核選擇理論，設計了在線核選擇準則及高效的在線核選擇算法，但該項工作針對的是在線核選擇中的問題，而下文所針對的是在線回歸學習提出了學習算法，并應用矩陣素描技術進行算法計算復雜度的優(yōu)化。

特殊地，應用FD 方法來計算累計損失的梯度，將這種修改后的版本稱為素描在線核回歸（Sketched Online Kernel Regression，SOKR）。實驗表明F-OKR 和SOKR 的回歸精確度比NOGD 高，且SOKR 的運行時間顯著小于F-OKR。

1 預備知識

1.1 符號表示

用大寫加粗的字母（如A）表示矩陣，小寫加粗字母（如a）表示向量，不加粗字母（如a或B）表示標量。矩陣A的第i行表示為[A]i；用It∈Rt×t表示t維的單位矩陣；A≥B表示A-B是一個半正定矩陣；用‖ ‖?表示向量的?2范數(shù)和矩陣的譜范數(shù)；‖ ?‖F(xiàn)表示矩陣的F 范數(shù)；令[T]表示集合｛1，2，…，T｝。

給定一個正定核函數(shù)κ：X× X→R，其中X表示一個任意的輸入空間。與κ相關的再生核希爾伯特空間表示為H，可得相關的特征映射為?：X→H，則κ(x，x′)表示一個內積。一般情況下，特征映射?的具體形式難以得知，通常使用這樣的內積形式來隱式地表達這個映射及特征空間，且對任意函數(shù)fw∈H，可以將其表示為映射值和權重w相乘的形式，即fw=?(x)Tw。定義權重假設第t回合的可行集為且。

在線核學習中，第t回合的核矩陣可寫為一個協(xié)方差矩陣的形式，其中定義特征矩陣為Φt=。

1.2 跟導方法

在線凸優(yōu)化是一個很重要的學習模型。以在線凸優(yōu)化為問題背景，在當前回合，選擇最小化過往回合累計損失的向量，這個思想稱為跟導方法[9]。在第t回合，目標函數(shù)為：

令損失函數(shù)? 為平方損失。

FTL 的在線二次優(yōu)化可以導出O(lbT)的后悔界，其中T為總回合數(shù)。

1.3 Nystr?m在線梯度下降

Nystr?m 在線梯度下降是一個大規(guī)模在線核學習的框架，其基本思想是通過函數(shù)化近似技術近似核函數(shù)，該方案可以表示為兩個階段。在早期學習階段，當支持向量的數(shù)量小于b時，應用任意在線學習方法（如在線梯度下降）即可，其中b是算法里提前定義的預算。一旦支持向量的數(shù)量達到了預算值，再接收到新樣本時，將會用當前的支持向量集近似其核映射值，這意味著將用核矩陣的一部分列來近似整個核矩陣。這個思想簡化了第二階段的計算，即不用再考慮用一些策略維護支持向量集，而是直接固定支持向量集；所以在線核學習中，NOGD 比其他方法更高效、可擴展。

參考NOGD 的框架，本文選用Nystr?m 近似方法［19-20］近似核矩陣。在大規(guī)模在線核學習中，Nystr?m 方法廣泛應用于批處理核矩陣近似方法，且有后悔界的理論結果。

1.4 頻繁方向

近些年，大規(guī)模矩陣的近似問題在大規(guī)模機器學習中越來越受重視，其中頻繁方向算法由于其逐行處理矩陣的特點，與在線學習很契合。本文應用頻繁方向算法[21]來獲得一個高效的協(xié)方差矩陣的近似，這樣的近似矩陣具有與原矩陣相同的規(guī)模，但同時會大幅減小計算量。

接下來簡單描述FD 算法（詳見算法1）。給定一個矩陣A∈Rn×d，F(xiàn)D算法會輸出A的一個素描矩陣，表示為B∈Rc×d，其中c?n。這個素描矩陣將會一直保持c×d的規(guī)模，每當新的一行到達時，矩陣內容都會更新，新到達的一行插入矩陣B的第c行，也就是最后 1 行。[U，Σ，V]←SVD(B)表示對矩陣B的奇異值分解（Singular Value Decomposition，SVD）。算法第4）、5）行會保證矩陣B的最后1 行一直為全零行。由于UTU=VTV=Ic，所以在算法中有。這一步驟不僅對于BTB的值沒有影響，還可以簡化得到B及BTB的計算量。

具體地，本文需要將矩陣Φ進行轉置來適應FD 算法。對于任意數(shù)據矩陣Φ=[?(x1)，?(x2)，…，?(xT)]∈Rd×T，則Φ的協(xié)方差矩陣為ΦΦT∈Rd×d。

應用素描矩陣近似該協(xié)方差矩陣得：

其中C∈Rd×c，c?T。

算法1 FD 算法。

輸入c，A∈Rn×d，B∈Rc×d為一個全零矩陣。

輸出。

2 素描在線核學習

本章將給出跟導在線核學習方法及一個用素描方法加速的版本。首先，應用Nystr?m 方法近似核；然后，通過跟導在線核回歸算法更新假設。

2.1 跟導在線核回歸

參考FTL 的思想，在線核學習在第t回合的目標函數(shù)可寫作：

然后選用梯度下降方法求解該函數(shù)，其中用到的是前t-1 回合的累計損失的平均梯度。設定? 為平方損失，則該梯度為：

在第t回合，根據下式更新假設wt：

其 中Φt-1=[?(x1)，?(x2)，…，?(xt-1)]∈Rd×(t-1)，且yt-1=[y1，y2，…，yt-1]∈R1×(t-1)，t=2，3，…，T。

將這種方法稱為跟導在線核回歸。該方法的精度比在線梯度下降方法更好，但運行時間會更長。每當新的樣本xt到來，用近似核得到?(xt)，然后將這一列向量加入到矩陣Φt-1以得到Φt，類似地，將yt加入向量yt-1以得到y(tǒng)t。根據梯度下降公式，每回合都必須計算，所以學習過程中主要的計算代價依賴于假設更新這一步驟。

關于協(xié)方差矩陣的計算，有很多種加速的方法?？紤]將矩陣Φ近似為一個低秩矩陣，然后再計算其協(xié)方差矩陣。如果需要逐行或逐列地得到一個低秩近似，有很多流行的方法可以選擇，如CX 分解、CUR 矩陣分解[22]、Nystr?m 近似等。素描技術也是一個很好的選擇，可以應用一些基于隨機采樣或隨機投影的素描技術，但本文選擇基于奇異值分解（SVD）的FD 算法來加速大規(guī)模協(xié)方差矩陣的計算。

2.2 素描在線核回歸

根據上述分析，更新假設的關鍵問題已經轉換為更新協(xié)方差矩陣的問題，接下來考慮應用FD 算法來加速計算。

通過FD 算法得到Φt的近似，然后計算的協(xié)方差矩陣，即為的近似。矩陣Φt∈Rd×t的規(guī)模會隨回合數(shù)增加，即t會線性增加，但是會一直保持d×c的規(guī)模，所以的規(guī)模也會一直與規(guī)模相同。將這個加速版本的算法稱為素描在線核回歸算法，具體如算法2。

算法2 素描在線核回歸算法。

算法可以分成兩部分來看。在第一部分，構建了支持集Q。對于每個新樣本xt，算法預測其回歸值，如果其對應的損失非零，則將它加入支持集。重復這個過程直至支持集的大小達到提前設定的預算值b。支持集Q就這樣確定下來，在算法的剩余部分都不會再改變。

在第二部分開始前，根據Qt構建核矩陣。分解，得到核矩陣的奇異向量和奇異值。然后初始化wt，其中αi是第i個支持向量的系數(shù)，i∈[b]。這個求解的過程詳見文獻［8］。

在第二部分，根據每個新樣本xt構建?(xt)，則有wT?(x)=[α1，α2，…，αB](κ(x，)，κ(x，)，…，κ(x，))T。這個過程和FD 逐行處理的算法過程非常契合。所以根據FD可以得到Φt的近似。預測之后，再根據所有過去t回合的累計損失的平均梯度來更新得wt+1。

為了后續(xù)理論分析，除了平方損失具有凸性這一性質，這里還會給出一些損失函數(shù)的性質和本文的一些假設。

定義1給定一個線性函數(shù)空間F ?Rd，?w、w′∈F，如果一個函數(shù)?：F→R 滿足不等式

則? 被稱為是β-光滑的。

引理1如果一個函數(shù)?：F→R 是β-光滑的，?w、w′∈F，有

假設1 ?w、|w|≤C，損失函數(shù)? 滿足‖?′(w)‖≤L。該假設旨在表示出損失函數(shù)? 的利普希茨（Lipschitz）常數(shù)。

假設2 ?σ≥0，?w、w′∈F，則函數(shù)? 有下述界

3 理論分析

本章將分析一些本文涉及的理論結果。首先定義T回合的在線學習算法的后悔為：

令?(wT?(x)；y)：Rd→R為平方損失函數(shù)，可以將SOKR的后悔RS分為四部分來分析：

其中w*為理論上的最優(yōu)假設（若能提前獲知所有樣本）；而當應用Nystr?m 方法做核矩陣近似并進行學習時，wN為理論上的最優(yōu)假設（若能提前獲知所有樣本）；在學習的第t回合中，應用在線梯度下降更新得到的假設為wt；而將瞬時損失替換為累計損失再做梯度下降（即F-OKR 的思想）得到的假設為；最后，為SOKR 算法在第t回合的假設，與的區(qū)別在于其更新時應用了素描技術。注意到，F(xiàn)-OKR 的后悔為RF=RB+RC+RD。

另外，從T個樣本x1，x2，…，xT中導出一個核矩陣K，然后應用Nystr?m 方法得到其近似。下面給出兩個方法的后悔理論。

定理1，t∈[T]表示F-OKR 方法生成的假設序列。假設常數(shù)L是所有迭代中梯度的范數(shù)界，即利普希茨常數(shù)，λ為正則化參數(shù)，η為學習率（步長）。令fN(x)=(x)為應用了Nystr?m 核近似后的最優(yōu)假設，則F-OKR 有一個后悔上界為：

這個后悔界的結果和NOGD 的后悔很相似，因為這個方法的框架參考了NOGD，但是直覺上來講，這個方法的后悔界應該比NOGD 的更緊。這個想法將會在后續(xù)的實驗中驗證，具體表現(xiàn)為F-OKR 的回歸精度明顯好于NOGD。

與F-OKR 不同的是，SOKR 需要考慮素描算法造成的后悔，所以SOKR 的后悔界會更松弛一些。在這一章的最后會對這兩種方法的后悔界進行討論。

與后面的實驗結果相對應，SOKR 的回歸精度與F-OKR相當，但仍遠優(yōu)于NOGD。

定理2，t∈[T]表示SOKR 生成的假設序列。假設C為任意w∈F 的范數(shù)界，即‖w‖≤C，p為空間中任意向量，則SOKR 有一個后悔上界為：

本章剩余部分將會分別討論后悔RS的各個部分。

3.1 素描算法造成的后悔界

首先需要分析由于應用了素描技術而造成的后悔界，即FD 算法導致的后悔界RA?？紤]到平方損失的性質，如果一個損失函數(shù)?：F→R 是凸函數(shù)，則?w、w′∈F，有

所以結合?(w)的凸性，有：

其中L是損失函數(shù)的利普希茨常數(shù)。將和的更新公式代入可得上述最后一個式子。與此同時，已知文獻［24］中的引理2 可引用于此。

引理2設是對矩陣Φt應用FD 方法的輸出矩陣，則有且

其中：c為素描規(guī)模，為矩陣的跡。

將式（1）代入，RA可以重寫為：

將的相關項都替換掉，則若可以界定，就能界定RA。

該式由矩陣的譜范數(shù)的三角不等式導出，?(x)為空間中任意向量，將其簡記為p。

對任意矩陣A，B∈Rn×n，都有tr(mA+nB)=mtr(A) +ntr(B)，所以

由此可以得出：

上式由矩陣譜范數(shù)的定義式推得，其中用λm表示矩陣的最大奇異值。

總結這一部分，如果tr(ppT)為一個常數(shù)，則這一部分后悔界可得：

3.2 梯度下降法造成的后悔界

這一部分將RB和RC放在一起分析，即。因為RB+RC這部分后悔是一個梯度下降法的變形造成的。

應用梯度下降更新，其中用到的是前t回合在上的累計損失的平均梯度，即。

又因為? 為凸函數(shù)，得：

結合式（4）、（5），并在t∈[T]上求和，得：

其中L為利普希茨常數(shù)。

這樣就得到了梯度下降法造成的后悔，與在線梯度下降的后悔相當。如果選定合適的學習率η，則可以保證該后悔界是亞線性的。

3.3 Nystr?m近似法造成的后悔界

通過一個固定的支持向量集來得到核矩陣K的近似矩陣，兩個方法皆是如此。具體應用的方法為Nystr?m 近似法，該方法是一個基于列采樣技術的高效方法，用于獲得矩陣的低秩近似。

在這一部分中，將會分析由核近似造成的后悔界。這一理論結果在文獻［20］中的引理1 中已經給出。

引理3定義L(w)為：

令w*為用準確核矩陣K進行學習的最優(yōu)解，而wN為用近似核矩陣進行學習的最優(yōu)解，近似核矩陣由Nystr?m 方法求得，則有：

結合上述引理，則在方法中有：

如文獻［8］的引理1 所述，核近似差的譜范數(shù)‖K-，其中b為預算值。

3.4 F-OKR的后悔界

3.5 SOKR的后悔界

為了分析SOKR 的后悔，必須要考慮到素描技術造成的后悔，所以需要確認RF加上素描部分的后悔是否還保持亞線性。

如定理2 中所見，將RF和RA兩部分后悔合并，當設定，c?T為任意常數(shù)時

4 實驗與結果分析

本章將會給出F-OKR 和SOKR 的實驗結果，用到的標準數(shù)據集在表1 中列出。

表1 選定的數(shù)據集信息Tab.1 Information of selected datasets

實驗涉及F-OKR、SOKR 和NOGD 算法。實驗旨在說明，在不同的數(shù)據集上：1）SOKR 相較于NOGD 提高了回歸精度；2）FD 算法的引入使得SOKR 的運行時間相對F-OKR 大幅減小，同時精度不受影響。

首先，實現(xiàn)第1 個算法F-OKR：設置徑向基函數(shù)（Radial Basis Function，RBF）核，應用Nystr?m 方法近似核矩陣；用平方損失函數(shù)，并用過往回合累計損失的平均梯度來更新假設，這個思想與FTL 算法是一致的；然后，應用FD 算法來近似計算梯度時會出現(xiàn)的協(xié)方差矩陣，本文主要的算法SOKR，可看作是F-OKR 的加速版本；最后實現(xiàn)NOGD 算法作為對比實驗。

現(xiàn)在討論參數(shù)的設置。在前面的章節(jié)中，建議設b=，c是一個很小的常數(shù)。一開始對所有的數(shù)據集設b=30，c=5，這個設定符合理論分析中的假設；然后在保證的同時變動其數(shù)值，依次設b=50、70并分別進行實驗。對比發(fā)現(xiàn)，不同預算值下的實驗對于三種算法的回歸精度都幾乎沒有影響，而隨著b的增大，核矩陣計算越來越復雜，反而會增加運行時間。最終選定b=30 作為一個最合適的預算值來進行實驗，在回歸精度和運行時間之間獲得平衡。

除此之外，對于不同的數(shù)據集選用了不同的γ最優(yōu)值，其中γ是RBF 的核參數(shù)，同時根據分析計算得出了每個數(shù)據集的學習率η，詳見表2。

表2 核參數(shù)γ和步長ηTab.2 Kernel parameterγ and step sizeη

重復每項實驗10 次，然后計算平均精度和運行時間，圖1 展示了在4 個標準數(shù)據集上，SOKR 和F-OKR 兩種方法以及NOGD 的平均損失和運行時間。通過實驗結果可以看出，兩種算法的平均損失都低于NOGD，尤其是SOKR 比F-OKR的性能還要更好一些。精度提高的原因是，該目標函數(shù)旨在最小化累計損失，常規(guī)方法只考慮當前回合的損失的梯度，而SOKR 和F-OKR 考慮所有過往回合的累計損失的梯度，形式上也更接近于在線學習的目標函數(shù)。

注意到SOKR 和F-OKR 的平均損失幾乎不依賴于樣本的數(shù)量，即當樣本數(shù)量很少時，這兩種算法也可以得到一個很好的回歸精度，4 個數(shù)據集上平均損失減小了64%左右。相反，NOGD 的回歸精度隨著樣本量增加到一個程度才會逐漸收斂，當樣本量較少時，SOKR 的運行時間比F-OKR 的還要長。這是因為數(shù)據量太少時，素描技術的優(yōu)勢無法展現(xiàn)，反而會復雜化原有的計算過程；而當樣本量逐漸增加，素描技術的加速效果才得以展現(xiàn)，如圖1（d）所示。故當數(shù)據集規(guī)模較小時，SOKR 的優(yōu)勢不明顯，而在適當?shù)臄?shù)據集上，SOKR 可將運行時間減少16.7%左右。

圖1 三種算法在4個數(shù)據集上的實驗結果對比Fig.1 Experimental results comparison of three algorithms on 4 datasets

F-OKR 在第t回合時，需要計算Φt-1的協(xié)方差矩陣，其中Φt-1∈Rd×(t-1)，矩陣乘法時間復雜度為O(Td2)，所以整個學習過程的時間復雜度為O(T2d2)。當應用了FD 算法時，獲得一個近似矩陣的時間復雜度為O(dc2)，計算協(xié)方差矩陣的時間復雜度降低為O(cd2)，所以SOKR 的時間復雜度為O(Tcd2)，其中c為一個常數(shù)且c

從圖1 中還可以看到，在樣本數(shù)逐漸增加后，F(xiàn)-OKR 和SOKR 算法的運行時間也隨之增加。這是因為在更新式中涉及矩陣Φt的計算，該矩陣的規(guī)模隨著在線學習回合數(shù)的增加而增加，在大規(guī)模的在線核回歸問題中，亟需解決這個問題。這里給出一個優(yōu)化思路：應用隨機素描技術對這一計算步驟進行加速，但需注意到不能應用矩陣低秩近似的相關算法，因為具體問題情境下，要求該步驟計算后所得向量的每一個分量都非零，否則會使得最終更新的假設有較大誤差。

圖中顯示NOGD 的求解速度優(yōu)于F-OKR 和SOKR，原因可以從算法過程中分析。NOGD 算法在進行假設更新時，應用每回合的瞬時損失的梯度，這意味著NOGD 更新的計算復雜度主要來自兩個向量相乘，即(xt)；而 在F-OKR 和SOKR 算法中，每回合根據累計損失的平均梯度進行假設更新，這表示每回合更新的計算復雜度主要源于協(xié)方差矩陣的計算，即ΦΦT及，因此運行時間會比NOGD 方法更長。

5 結語

本文提出了一個可以提升在線回歸學習精度的算法F-OKR；然后基于素描技術設計了一個算法SOKR，該算法可以將計算復雜度從F-OKR 的O(T2)降低到O(Tcd2)，且理論上證明了兩種算法的亞線性后悔界。理論證明及實驗驗證了該方法是高效的，且可以應用于大規(guī)模在線核回歸問題中。