# 6 -- Support Vector Regression 上節課我們主要介紹了Kernel Logistic Regression，討論如何把SVM的技巧應用在soft-binary classification上。方法是使用2-level learning，先利用SVM得到參數b和w，然后再用通用的logistic regression優化算法，通過迭代優化，對參數b和w進行微調，得到最佳解。然后，也介紹了可以通過Representer Theorem，在z空間中，引入SVM的kernel技巧，直接對logistic regression進行求解。本節課將延伸上節課的內容，討論如何將SVM的kernel技巧應用到regression問題上。 ### **Kernel Ridge Regression** 首先回顧一下上節課介紹的Representer Theorem，對于任何包含正則項的L2-regularized linear model，它的最佳化解w都可以寫成是z的線性組合形式，因此，也就能引入kernel技巧，將模型kernelized化。  那么如何將regression模型變成kernel的形式呢？我們之前介紹的linear/ridge regression最常用的錯誤估計是squared error，即。這種形式對應的解是analytic solution，即可以使用線性最小二乘法，通過向量運算，直接得到最優化解。那么接下來我們就要研究如何將kernel引入到ridge regression中去，得到與之對應的analytic solution。 我們先把Kernel Ridge Regression問題寫下來：  其中，最佳解必然是z的線性組合。那么我們就把代入到ridge regression中，將z的內積用kernel替換，把求的問題轉化成求的問題，得到：  ridge regression可以寫成矩陣的形式，其中第一項可以看成是的正則項，而第二項可以看成是的error function。這樣，我們的目的就是求解該式最小化對應的值，這樣就解決了kernel ridge regression問題。 求解的問題可以寫成如下形式：  是關于的二次多項式，要對求最小化解，這種凸二次最優化問題，只需要先計算其梯度，再令梯度為零即可。已經在上式中寫出來了，令其等于零，即可得到一種可能的的解析解為：  這里需要關心的問題是的逆矩陣是否存在？答案是肯定的。因為我們之前介紹過，核函數K滿足Mercer’s condition，它是半正定的，而且，所以一定是可逆的。從計算的時間復雜上來說，由于是NxN大小的，所以時間復雜度是。還有一點，是由兩項乘積構成的，另一項是K，會不會出現K=0的情況呢？其實，由于核函數K表征的是z空間的內積，一般而言，除非兩個向量互相垂直，內積才為零，否則，一般情況下K不等于零。這個原因也決定了是dense matrix，即的解大部分都是非零值。這個性質，我們之后還會說明。 所以說，我們可以通過kernel來解決non-linear regression的問題。下面比較一下linear ridge regression和kernel ridge regression的關系。  如上圖所示，左邊是linear ridge regression，是一條直線；右邊是kernel ridge regression，是一條曲線。大致比較一下，右邊的曲線擬合的效果更好一些。這兩種regression有什么樣的優點和缺點呢？對于linear ridge regression來說，它是線性模型，只能擬合直線；其次，它的訓練復雜度是，預測的復雜度是，如果N比d大很多時，這種模型就更有效率。而對于kernel ridge regression來說，它轉換到z空間，使用kernel技巧，得到的是非線性模型，所以更加靈活；其次，它的訓練復雜度是，預測的復雜度是，均只與N有關。當N很大的時候，計算量就很大，所以，kernel ridge regression適合N不是很大的場合。比較下來，可以說linear和kernel實際上是效率（efficiency）和靈活（flexibility）之間的權衡。  ### **Support Vector Regression Primal** 我們在機器學習基石課程中介紹過linear regression可以用來做classification，那么上一部分介紹的kernel ridge regression同樣可以來做classification。我們把kernel ridge regression應用在classification上取個新的名字，叫做least-squares SVM（LSSVM）。 先來看一下對于某個問題，soft-margin Gaussian SVM和Gaussian LSSVM結果有哪些不一樣的地方。  如上圖所示，如果只看分類邊界的話，soft-margin Gaussian SVM和Gaussian LSSVM差別不是很大，即的到的分類線是幾乎相同的。但是如果看Support Vector的話（圖中方框標注的點），左邊soft-margin Gaussian SVM的SV不多，而右邊Gaussian LSSVM中基本上每個點都是SV。這是因為soft-margin Gaussian SVM中的大部分是等于零，的點只占少數，所以SV少。而對于LSSVM，我們上一部分介紹了的解大部分都是非零值，所以對應的每個點基本上都是SV。SV太多會帶來一個問題，就是做預測的矩，如果非零值較多，那么g的計算量也比較大，降低計算速度。基于這個原因，soft-margin Gaussian SVM更有優勢。  那么，針對LSSVM中dense 的缺點，我們能不能使用一些方法來的得到sparse ，使得SV不會太多，從而得到和soft-margin SVM同樣的分類效果呢？下面我們將嘗試解決這個問題。 方法是引入一個叫做Tube Regression的做法，即在分類線上下分別劃定一個區域（中立區），如果數據點分布在這個區域內，則不算分類錯誤，只有誤分在中立區域之外的地方才算error。  假定中立區的寬度為，,那么error measure就可以寫成：，對應上圖中紅色標注的距離。  通常把這個error叫做-insensitive error，這種max的形式跟我們上節課中介紹的hinge error measure形式其實是類似的。所以，我們接下來要做的事情就是將L2-regularized tube regression做類似于soft-margin SVM的推導，從而得到sparse 。 首先，我們把tube regression中的error與squared error做個比較：  然后，將err(y,s)與s的關系曲線分別畫出來：  上圖中，紅色的線表示squared error，藍色的線表示tube error。我們發現，當|s-y|比較小即s比較接近y的時候，squared error與tube error是差不多大小的。而在|s-y|比較大的區域，squared error的增長幅度要比tube error大很多。error的增長幅度越大，表示越容易受到noise的影響，不利于最優化問題的求解。所以，從這個方面來看，tube regression的這種error function要更好一些。 現在，我們把L2-Regularized Tube Regression寫下來：  這個最優化問題，由于其中包含max項，并不是處處可微分的，所以不適合用GD/SGD來求解。而且，雖然滿足representer theorem，有可能通過引入kernel來求解，但是也并不能保證得到sparsity 。從另一方面考慮，我們可以把這個問題轉換為帶條件的QP問題，仿照dual SVM的推導方法，引入kernel，得到KKT條件，從而保證解是sparse的。  所以，我們就可以把L2-Regularized Tube Regression寫成跟SVM類似的形式：  值得一提的是，系數和C是反比例相關的，越大對應C越小，越小對應C越大。而且該式也把即b單獨拿了出來，這跟我們之前推導SVM的解的方法是一致的。 現在我們已經有了Standard Support Vector Regression的初始形式，這還是不是一個標準的QP問題。我們繼續對該表達式做一些轉化和推導：  如上圖右邊所示，即為標準的QP問題，其中和分別表示upper tube violations和lower tube violations。這種形式叫做Support Vector Regression（SVR） primal。  SVR的標準QP形式包含幾個重要的參數：C和。C表示的是regularization和tube violation之間的權衡。large C傾向于tube violation，small C則傾向于regularization。表征了tube的區域寬度，即對錯誤點的容忍程度。越大，則表示對錯誤的容忍度越大。是可設置的常數，是SVR問題中獨有的，SVM中沒有這個參數。另外，SVR的QP形式共有個參數，2N+2N個條件。  ### **Support Vector Regression Dual** 現在我們已經得到了SVR的primal形式，接下來將推導SVR的Dual形式。首先，與SVM對偶形式一樣，先令拉格朗日因子和，分別是與和不等式相對應。這里忽略了與和對應的拉格朗日因子。  然后，與SVM一樣做同樣的推導和化簡，拉格朗日函數對相關參數偏微分為零，得到相應的KKT條件：  接下來，通過觀察SVM primal與SVM dual的參數對應關系，直接從SVR primal推導出SVR dual的形式。（具體數學推導，此處忽略！）  最后，我們就要來討論一下SVR的解是否真的是sparse的。前面已經推導了SVR dual形式下推導的解w為：  相應的complementary slackness為：  對于分布在tube中心區域內的點，滿足，此時忽略錯誤，和都等于零。則complementary slackness兩個等式的第二項均不為零，必然得到和，即。 所以，對于分布在tube內的點，得到的解，是sparse的。而分布在tube之外的點，。至此，我們就得到了SVR的sparse解。 ### **Summary of Kernel Models** 這部分將對我們介紹過的所有的kernel模型做個概括和總結。我們總共介紹過三種線性模型，分別是PLA/pocket，regularized logistic regression和linear ridge regression。這三種模型都可以使用國立臺灣大學的Chih-Jen Lin博士開發的Liblinear庫函數來解決。 另外，我們介紹了linear soft-margin SVM，其中的error function是，可以通過標準的QP問題來求解。linear soft-margin SVM和PLA/pocket一樣都是解決同樣的問題。然后，還介紹了linear SVR問題，它與linear ridge regression一樣都是解決同樣的問題，從SVM的角度，使用，轉換為QP問題進行求解，這也是我們本節課的主要內容。  上圖中相應的模型也可以轉化為dual形式，引入kernel，整體的框圖如下：  其中SVM，SVR和probabilistic SVM都可以使用國立臺灣大學的Chih-Jen Lin博士開發的LLibsvm庫函數來解決。通常來說，這些模型中SVR和probabilistic SVM最為常用。 ### **總結** 本節課主要介紹了SVR，我們先通過representer theorem理論，將ridge regression轉化為kernel的形式，即kernel ridge regression，并推導了SVR的解。但是得到的解是dense的，大部分為非零值。所以，我們定義新的tube regression，使用SVM的推導方法，來最小化regularized tube errors，轉化為對偶形式，得到了sparse的解。最后，我們對介紹過的所有kernel模型做個總結，簡單概述了各自的特點。在實際應用中，我們要根據不同的問題進行合適的模型選擇。 **_注明：_** 文章中所有的圖片均來自臺灣大學林軒田《機器學習技法》課程