[ML] 機器學習技法：第六講 Support Vector Regression (SVR)

ML：基礎技法學習
Package：scikit-learn
課程：機器學習技法
簡介：第六講 Support Vector Regression (SVR)

Kernel Ridge Regression (KRR)

$$ \begin{align*} \underset{\boldsymbol\beta}{min}\ \ E_{in}(\boldsymbol\beta) &=\underset{\boldsymbol\beta }{min}\ \ \frac{\lambda}{N}\sum_{n=1}^{N}\sum_{m=1}^{N}\beta _n\beta _mK(\mathbf{x}_n,\mathbf{x}_m)+\frac{1}{N}\sum_{n=1}^{N}\left ( y_n-\sum_{m=1}^{N}\beta_mK(\mathbf{x}_n,\mathbf{x}_m) \right )^2\\ &=\underset{\boldsymbol\beta }{min}\ \ \frac{\lambda}{N}\boldsymbol\beta^T\mathbf{K}\boldsymbol\beta+\frac{1}{N}(\boldsymbol\beta^T \mathbf{K}^T\mathbf{K}\boldsymbol\beta-2\boldsymbol\beta^T \mathbf{K}^T\mathbf{y}+\mathbf{y}^T\mathbf{y})\\ \\ optimal\ \mathbf{w}_*&=\sum_{n=1}^{N}\beta _n\mathbf{z}_n\\ \boldsymbol\beta &= (\lambda\mathbf{I}+\mathbf{K})^{-1}\mathbf{y} \end{align*} $$ 時間複雜度為 $O(N^3)$，且 $\boldsymbol\beta$ 大部分不為 0

Support Vector Regression (SVR)

Primal
$$ \begin{align*} \underset{\mathbf{b,w,\boldsymbol\xi^\wedge,\boldsymbol\xi^\vee }}{min}\ \ &\frac{1}{2}\mathbf{w}^T\mathbf{w}+C\sum_{n=1}^{N}(\xi_n^\wedge +\xi_n^\vee )\\ s.t.\ \ &-\epsilon -\xi_n^\vee\leq \mathbf{w}^T\mathbf{z}_n+b-y_n\leq \epsilon +\xi_n^\wedge \\ &\xi_n^\vee\geq 0,\ \xi_n^\wedge\geq 0 \end{align*} $$ QP of $\tilde{d}+1+N$ 個變數，$2N+2N$ 個條件

Dual
$$ \begin{align*} \underset{\mathbf{\boldsymbol\alpha^\wedge,\boldsymbol\alpha^\vee }}{min}\ \ &\frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}(\alpha_n^\wedge-\alpha_n^\vee)(\alpha_m^\wedge-\alpha_m^\vee)\mathbf{K}(\mathbf{x}_n,\mathbf{x}_m)+\sum_{n=1}^{N}((\epsilon -y_n)\alpha_n^\wedge+(\epsilon +y_n)\alpha_n^\vee)\\ s.t.\ \ &\sum_{n=1}^{N}(\alpha_n^\wedge-\alpha_n^\vee)=0\\ &0 \le \alpha_n^\wedge \le C,\ 0 \le \alpha_n^\vee \le C,\\ \end{align*} $$ QP of $2N$ 個變數，$4N+1$ 個條件

$$ \mathbf{w}=\sum_{n=1}^{N}\underset{\beta_n}{\underbrace{(\alpha_n^\wedge -\alpha_n^\vee)}}\mathbf{z}_n\\ C>\alpha_n^\vee>0\\ b=y_n-\mathbf{w}^T\mathbf{z}_n+\epsilon\\ \\\\ C>\alpha_n^\wedge>0\\ b=y_n-\mathbf{w}^T\mathbf{z}_n-\epsilon\\ $$ 只有在 tube 邊界和以外的才是 SV

Model 總結

$s= \mathbf{w}^T\mathbf{z}_n+b$
分類

linear

PLA/pocket

$err_{0/1}(s,y)=[ys\le0]$
solver : update
不常用，表現不好

linear soft-margin SVM

$\widehat{err}_{SVM}(s,y)=max(1-ys,0)$
solver : QP
librabry:LIBLINEAR

kernel

$\widehat{err}_{SVM}(s,y)=max(1-ys,0)$，dual SVM
solver : QP
librabry:LIBSVM

回歸

linear

linear SVR

$err_{tube}=max(0,|s-y|-\epsilon) $
solver : QP
不常用，表現不好

linear ridge regression

$err_{SQR}=(s-y)^2$
solver : 分析求解
librabry:LIBLINEAR

kernel

kernel ridge regression (KRR)

$err_{SQR}=(s-y)^2$
solver : 分析求解
不常用，效率不好

$err_{tube}=max(0,|s-y|-\epsilon) $
solver : QP
librabry:LIBSVM

機率預測

linear

regularized logistic reression

$err_{CE}=ln (1+e^{-y\mathbf{s}})$
solver : GD/SGD
librabry:LIBLINEAR

kernel

kernel logistic regression (KLR)

$err_{CE}=ln (1+e^{-y\mathbf{s}})$
solver : GD/SGD
不常用，效率不好

probabilistic SVM

$\widehat{err}_{SVM}(s,y)=max(1-ys,0)$
$err_{CE}=ln (1+e^{-y\mathbf{s}})$
solver : QP -> GD/SGD
librabry:LIBSVM

kernel model 務必小心 overfitting

程式碼

from __future__ import division
import time
import numpy as np
from sklearn.svm import SVR
from sklearn.kernel_ridge import KernelRidge
from sklearn.model_selection import learning_curve
import matplotlib.pyplot as plt

# 設定 seed
rng = np.random.RandomState(0)

# 訓練資料
X = 5 * rng.rand(10000, 1)
y = np.sin(X).ravel()

# 加入 noise
y[::5] += 3 * (0.5 - rng.rand(X.shape[0] // 5))

# 畫圖的資料，新增二維維度
X_plot = np.linspace(0, 5, 100000)[:, None]

# 訓練大小
train_size = 1000

# model
svr = SVR(kernel='rbf', gamma=0.1, epsilon=0.1)
krr = KernelRidge(kernel='rbf', gamma=0.1)

# 計算 SVR 訓練時間
t0 = time.time()
svr.fit(X[:train_size], y[:train_size])
svr_fit = time.time() - t0
print("SVR complexity and bandwidth selected and model fitted in %.3f s"
      % svr_fit)

# 計算 KRR 訓練時間
t0 = time.time()
krr.fit(X[:train_size], y[:train_size])
krr_fit = time.time() - t0
print("KRR complexity and bandwidth selected and model fitted in %.3f s"
      % krr_fit)

# 計算 SVR 預測時間
t0 = time.time()
y_svr = svr.predict(X_plot)
svr_predict = time.time() - t0
print("SVR prediction for %d inputs in %.3f s"
      % (X_plot.shape[0], svr_predict))

# 計算 KRR 預測時間
t0 = time.time()
y_krr = krr.predict(X_plot)
krr_predict = time.time() - t0
print("KRR prediction for %d inputs in %.3f s"
      % (X_plot.shape[0], krr_predict))

# SVR 的 support vector
sv_ind = svr.support_

plt.subplot(2,1,1)
# 畫出 SV
plt.scatter(X[sv_ind], y[sv_ind], c='b', s=50, label='SVR support vectors', zorder=2)
# 畫出 data
plt.scatter(X[:], y[:], c='k', label='data', zorder=1)
# 畫出 SVR 的曲線
plt.plot(X_plot, y_svr, c='r',
         label='SVR (fit: %.3fs, predict: %.3fs)' % (svr_fit, svr_predict))
# 畫出 KRR 的曲線
plt.plot(X_plot, y_krr, c='g',
         label='KRR (fit: %.3fs, predict: %.3fs)' % (krr_fit, krr_predict))
plt.xlabel('data')
plt.ylabel('target')
plt.title('SVR versus Kernel Ridge')
plt.legend()

# Visualize learning curves
plt.subplot(2,1,2)

# model
svr = SVR(kernel='rbf', C=1e1, gamma=0.1, epsilon=0.1)
krr = KernelRidge(kernel='rbf', alpha=0.1, gamma=0.1)

# cv = cross-validation，5 表示五份
train_sizes, train_scores_svr, test_scores_svr = \
    learning_curve(svr, X[:100], y[:100], train_sizes=np.linspace(0.1, 1, 10),
                   scoring="neg_mean_squared_error", cv=5)
train_sizes_abs, train_scores_krr, test_scores_krr = \
    learning_curve(krr, X[:100], y[:100], train_sizes=np.linspace(0.1, 1, 10),
                   scoring="neg_mean_squared_error", cv=5)

plt.plot(train_sizes, -test_scores_svr.mean(1), 'o-', color="r",
         label="SVR")
plt.plot(train_sizes, -test_scores_krr.mean(1), 'o-', color="g",
         label="KRR")
plt.xlabel("Train size")
plt.ylabel("Mean Squared Error")
plt.title('Learning curves')
plt.legend(loc="best")

# 調整之間的空白高度
plt.subplots_adjust(hspace=0.6)
plt.show()

參考

sklearn.kernel_ridge.KernelRidge
sklearn.svm.SVR
sklearn.model_selection.learning_curve

子風的知識庫

搜尋此網誌