(1) One-against-Rest(One-vs-All, OvA, OvR)：一對多

這個策略的想法是，就是針對每一個類別，分別建立一個SVM(或其他二元分類器)：屬於此類別的樣本視為(+1)，其他類別的樣本視為(-1)，如此一來，就轉換成一個二元分類的問題了！

以第1節的資料為例，資料中有六個類別(1~6，玻璃材質)，那我們便會建立六個SVM：

• 第一個SVM：屬於類別1的資料為(+1)，其他類別為(-1)，這個SVM用來區別這兩者

• 第二個SVM：屬於類別2的資料為(+1)，其他類別為(-1)，這個SVM用來區別這兩者

• 第三個SVM：屬於類別3的資料為(+1)，其他類別為(-1)，這個SVM用來區別這兩者

• 以此類推…

換句話說，針對有t個類別的資料，就會存在著t個SVM。

當有一筆新資料要預測時，會分別丟進這t個SVM，得到t組值(v1, v2, v3…vt)，再從中判別最大的值(如果類別是+1,-1)出現第幾個位置，那這筆資料便是屬於那一類。

這樣的做法很直覺，而且執行時間與記憶體並不會消耗太多。

但缺點是，將「剩下類別」視為同一個類別(-1)的這種做法，很容易導致(+1,-1)之間的資料筆數差距很大，也就是類別不平衡(class imbalance)的問題。

(2) One-against-One(OvO)：一對一

這個策略的想法，很像高中數學的排列組合：從T種類別中任取2種類別，共會有幾種組合？

答案是：C(T,2) = T(T-1)/2

所以在這個策略底下，我們便會從多元類別(multi classes)的資料中，任選某兩個類別(2 classes)的資料，訓練一個SVM(只能區分這兩個類別)，並重複這樣的動作，直到所有的類別組合，都有其對應的SVM為止。

因此，最後會有 T(T-1)/2 個SVM模型。

當有一筆新資料要預測時，會分別丟進這 T(T-1)/2 個SVM，每一個SVM都會將這筆資料分到某一類，就像是投票一樣，該類別會記錄+1，最後判斷哪一個類別獲得最多票數，即可預測這筆資料屬於哪一個類別。

和One-against-Rest不同，這樣比較並不會造成類別不平衡的問題；

但相對的，這個策略所需的運行時間較長；也吃較多的記憶體；而且有時候會發生兩個以上的類別獲得同票數的狀況，造成判斷上的困擾。

另一個預測的思維是，用淘汰賽的方式(來源：Support Vector Machines 簡介(林宗勳))：

以上就是在面對多元分類問題時，最常用的兩種解法。

這兩種解法各有優劣，很難說哪一種方式比較好。在這篇paper中也提到，要使用哪一種方法，其實端看你的資料狀況而定。

然而，我們在第1節中，其實並沒有使用上面兩種方法，只是單純使用e1071套件裡的svm()，就針對六個類別的資料訓練出SVM。這又是怎麼回事呢？

這個問題的答案，提供在林智仁實驗室的LIBSVM官網FAQ中，裡面提到：他們是使用One-against-One來解決多元分類的問題。

所以說，在使用svm()的時候，裡面其實已經做了One-against-One。

C(cost)

一開始的SVM，是要尋找一個能夠完美將「所有」資料分成兩邊，具有最大margin的超平面，這又被稱為“hard-margin SVM”。

但由於hard-margin SVM，追求要將資料完美分好，因此很容易有overfitting的風險。於是1995年，Vapnik等人提出了“soft-margin SVM”，讓SVM能容許一些被分錯的資料存在。

在soft-margin SVM的損失函數(loss function)中，這個大C的存在，就是容錯項。

藉由C，我們能給予那些被分錯的資料懲罰值，控制support vectors(用來決定超平面的那些資料點)的影響力。

• soft-margin SVM的 primal 型態：

• 轉為Lagrange Formulation：

換句話說：

• C越大，代表容錯越小，越少support vectors，越接近hard-margin SVM的概念，卻容易overfitting

• C越小，代表容錯越大，越多support vectors，可以追求更大的margin

如下圖所示，圈圈的點代表support vectors，用來決定margin的大小。

當C=1000時，support vectors的點幾乎都發生在線上面，很接近hard-margin SVM的概念。

當C越來越小，隨著support vectors的點越來越多，表示margin的範圍越來越大。

以第1節的例子來說，我們依序提高C的值(從1~1000)，然後觀察support vectors的數量變化：

require("mlbench")
data(Glass, package="mlbench")
data = Glass

# 記錄每一次提高C時，對應的support vectors數量
num.SV = sapply(X=1:1000, 
                FUN=function(C) svm(Type~., data, cost=C, epsilon =.1)$tot.nSV)

# 隨著C越大，support vectors數量越少，代表margin的範圍越窄，越接近hard-margin SVM，越容易overfitting
plot(x=1:1000, y=num.SV, xlab="C value", ylab="# of support vectors", pch=16, cex=.5, main="# of SVs in soft-margin SVM")

Epsilon (ε)

這個參數主要影響的會是SVR，而非SVM。因為在SVR的損失函數中，使用的是epsilon intensive hinge loss。

Epsilon(ε)的概念是給予一個margin of tolerance，創造一個「絕對領域」的感覺。

在「絕對領域」內的資料點會被忽視，它們的殘差(error)一點幫助也沒有，換句話說：它們對訓練SVR一點幫助也沒有。

如下圖所示，Epsilon(ε)會創造一個width of zone，讓在這個容忍區塊裡面的資料被忽視。

因此我們可以這樣說：

• Epsilon越大，代表容忍區塊越大，越多資料會被忽視，造成模型的準確度越低，support vectors的數量減少(記得，所謂的support vectors是那些across margin的資料點，它們的殘差會被納入考量，用來決定最後的margin)。

• Epsilon越低(→0+)，所有的資料殘差(error)都會被考慮，卻也容易造成overfitting。

這邊改以第3節的SVR案例來說明，當逐漸調高Epsilon(0~1)，觀察support vectors的數量：

df = data.frame(x=1:20,
                y=c(3,4,8,2,6,10,12,13,15,14,17,18,20,17,21,22,25,30,29,31))


# 記錄每一次提高Epsilon時，對應SVR中的support vectors數量
num.SV = sapply(X=seq(0,1,0.01), 
                FUN=function(e) svm(y~x, df, cost=1, epsilon =e)$tot.nSV)
# 隨著Epsilon越大，support vectors的數量減少
plot(x=seq(0,1,0.01), y=num.SV, xlab="ε value", ylab="# of support vectors", pch=16, cex=.5, main="# of SVs in SVR")

# 記錄每一次提高Epsilon時，對應SVR中的RMSE
RMSE = sapply(X=seq(0,1,0.01), 
              FUN=function(e) sqrt(mean((svm(y~x, df, cost=1, epsilon =e)$residuals)^2)))
# 隨著Epsilon越大，模型的準確度越低，RMSE提高
plot(x=seq(0,1,0.01), y=RMSE, xlab="ε value", ylab="RMSE", pch=16, cex=.5, main="RMSE in SVR")

Gamma

這是用在kernel function中的參數，主要是polynomial、radial basis(RBF)和sigmoid。

這邊有不同kernel function的優劣討論，可以事先讀一下。

Gamma的意義比較難以說明，當使用kernel function將原始資料映射到特徵空間(feature space)時，它隱含地決定了資料在特徵空間的分佈狀況。

以幾何的觀點來看，當gamma增加時，會讓Radial Basis Function(RBF)裡面的σ變小，而σ很小的高斯分佈會又高又瘦，讓只在附近的資料點有所作用。(參考)

在定義中，Gamma = How far the influence of a single training example reaches，意思是(參考)：

• gamma大，資料點的影響力範圍比較近，對超平面來說，近點的影響力權重較大，容易勾勒出擬合近點的超平面，也容易造成overfitting。

• gamma小，資料點的影響力範圍比較遠，對超平面來說，較遠的資料點也有影響力，因此能勾勒出平滑、近似直線的超平面。

這裡拿第1小節的SVM來說明，當陸續提高gamma的值時，所對應的訓練資料、測試資料的分類準確率度：

require("mlbench")
data(Glass, package="mlbench")
data = Glass
smp.size = floor(0.8*nrow(data)) 
set.seed(516)                     
train.ind = sample(seq_len(nrow(data)), smp.size)
train = data[train.ind, ] # 80%
test = data[-train.ind, ] # 20%

# 記錄每一次提高gamma時，對應的訓練資料的分類準確率
train.accuracy = sapply(X=seq(0.1,10,0.1), 
                        FUN=function(g){
                        model = svm(Type~., train, gamma=g, epsilon =.1)
                        pred = predict(model, train)
                        confus.matrix = table(real=train$Type, predict=pred)
                        sum(diag(confus.matrix))/sum(confus.matrix)
                        } 
)

# 記錄每一次提高gamma時，對應的測試資料的分類準確率
test.accuracy = sapply(X=seq(0.1,10,0.1), 
                       FUN=function(g){
                       model = svm(Type~., train, gamma=g, epsilon =.1)
                       pred = predict(model, test)
                       confus.matrix = table(real=test$Type, predict=pred)
                       sum(diag(confus.matrix))/sum(confus.matrix)
                       } 
)


# Train accuracy(紅點)
plot(x=seq(0.1,10,0.1), y=train.accuracy, pch=16, cex=.5, col="red", ylim=c(0,1),xlab="gamma value", ylab="Class Accuracy", main="Accuracy in soft-margin SVM")
# Test accuracy(藍點)
points(x=seq(0.1,10,0.1), y=test.accuracy, pch=16, cex=.5, col="blue")

legend("bottomright", pch = 16, col = c("red","blue"),legend=c("Train-Accuracy", "Test-Accuracy"))

隨著gamma增加，訓練資料的準確度也提高，但測試資料的準確度卻降低，表示有overfitting的問題產生。

(更多SVM參數的討論可以參閱這篇：SVM Parameters)

Tune parameters in SVM(soft-margin)

在SVM中，一般會去調的參數是(cost, gamma)：

# data
require("mlbench")
data(Glass, package="mlbench")
data = Glass

# tune cost and gamma in SVM(soft-margin)
tune.model = tune(svm,
                  Type~.,
                  data=data,
                  kernel="radial", # RBF kernel function
                  range=list(cost=10^(-1:2), gamma=c(.5,1,2))# 調參數的最主要一行
)

• 在訓練的過程中，我們訓練的是一堆模型，包含cost=10^-1, 10^0, 10^1, 10^2，gamma=0.5, 1, 2，這兩種參數的排列組合，換句話說，會有 4x3=12 個SVM模型。

• 裡面的值是classification error

summary(tune.model)

## 
## Parameter tuning of 'svm':
## 
## - sampling method: 10-fold cross validation 
## 
## - best parameters:
##  cost gamma
##    10   0.5
## 
## - best performance: 0.2937229 
## 
## - Detailed performance results:
##     cost gamma     error dispersion
## 1    0.1   0.5 0.6062771 0.10333568
## 2    1.0   0.5 0.3504329 0.07419505
## 3   10.0   0.5 0.2937229 0.06307295
## 4  100.0   0.5 0.3216450 0.07721204
## 5    0.1   1.0 0.5926407 0.07969758
## 6    1.0   1.0 0.3642857 0.08119400
## 7   10.0   1.0 0.3402597 0.08195816
## 8  100.0   1.0 0.3781385 0.08188350
## 9    0.1   2.0 0.5976190 0.08711625
## 10   1.0   2.0 0.3833333 0.09368097
## 11  10.0   2.0 0.3874459 0.08350728
## 12 100.0   2.0 0.3926407 0.08643085

plot(tune.model)

這張圖挺有意思的，根據顏色的深淺，可以看得出來有一層一層的山峰出現在圖中，表示在特定範圍內的cost和gamma，會有互相配合/影響的可能性。

而我們會希望classification error越小越好，也就是圖中的顏色越深越好。最後模型給出的最佳參數組合是：cost=10, gamma=0.5。

進一步，可以根據這張圖，縮小cost和gamma的範圍，再去去tune更多的參數組合。

最後，要挑出表現最佳的模型，可以直接從tune()回傳的結果中取出($best.model)：

# Best model in set of tuning models
tune.model$best.model

## 
## Call:
## best.tune(method = svm, train.x = Type ~ ., data = data, ranges = list(cost = 10^(-1:2), 
##     gamma = c(0.5, 1, 2)), kernel = "radial")
## 
## 
## Parameters:
##    SVM-Type:  C-classification 
##  SVM-Kernel:  radial 
##        cost:  10 
##       gamma:  0.5 
## 
## Number of Support Vectors:  162

Tune parameters in SVR

在SVR中，一般會去調的參數是(cost, epsilon)：

# data
data = data.frame(x=1:20,
                  y=c(3,4,8,2,6,10,12,13,15,14,17,18,20,17,21,22,25,30,29,31))

# tune cost and epsilon in SVR
tune.model = tune(svm,
                  y~x,
                  data=data,
                  range=list(cost=2^(2:9), epsilon = seq(0,1,0.1))# 調參數的最主要一行
)

這裡有兩個重點：

• 在訓練的過程中，我們訓練的是一堆模型，包含cost=2^2., 2^3. … 2^9.，epsilon=0, 0.1, 0.2…1，這兩種參數的排列組合，換句話說，會有8x11=88個SVR模型。

• 裡面的值是mean squared error

tune.model

## 
## Parameter tuning of 'svm':
## 
## - sampling method: 10-fold cross validation 
## 
## - best parameters:
##  cost epsilon
##     4       0
## 
## - best performance: 4.532176

plot(tune.model)

而這張圖的分層也很有意思，隨著epsilon越高，模型的表現越糟(顏色越淺)。同時它也希望cost比較低，所以最後得出的最佳參數組合： cost=4, epsilon=0

最後，要挑出表現最佳的模型，可以直接從tune()回傳的結果中取出($best.model)：

# Best model in set of tuning models
tune.model$best.model

## 
## Call:
## best.tune(method = svm, train.x = y ~ x, data = data, ranges = list(cost = 2^(2:9), 
##     epsilon = seq(0, 1, 0.1)))
## 
## 
## Parameters:
##    SVM-Type:  eps-regression 
##  SVM-Kernel:  radial 
##        cost:  4 
##       gamma:  1 
##     epsilon:  0 
## 
## 
## Number of Support Vectors:  20