0
雷鋒網(wǎng) AI 研習(xí)社按：本文為 seaboat 為雷鋒網(wǎng) AI 研習(xí)社撰寫的獨(dú)家稿件，未經(jīng)雷鋒網(wǎng)許可不得轉(zhuǎn)載。
SVM 即支持向量機(jī)，常用于二分類模型。它主要的思想是：
它是特征空間上間隔最大的線性分類器。
對于線性不可分的情況，通過非線性映射算法將低維空間的線性不可分的樣本映射到高維特征空間，高維特征空間能夠進(jìn)行線性分析。
其實(shí)機(jī)器學(xué)習(xí)中，如果按照輸出空間不同可以分為：
二元分類(binary classification)
多元分類(multiclass classification)
回歸問題(regression)
結(jié)構(gòu)化預(yù)測(structured prediction)
其中前面三類都是我們常見且經(jīng)常用的，第四種結(jié)構(gòu)化預(yù)測重點(diǎn)體現(xiàn)在結(jié)構(gòu)化上，前面三類的輸出都是標(biāo)簽類別或者回歸值之類的單變量，而結(jié)構(gòu)化預(yù)測輸出是一種結(jié)構(gòu)化的數(shù)據(jù)結(jié)構(gòu)，比如輸入一句話，輸出是一顆語法樹。此外，結(jié)構(gòu)還可以是圖結(jié)構(gòu)、序列結(jié)構(gòu)等。
把前面的SVM與結(jié)構(gòu)化結(jié)合起來就是結(jié)構(gòu)化SVM了。它為了處理更加復(fù)雜的彼此之間互相存在依賴關(guān)系的結(jié)構(gòu)數(shù)據(jù)，對傳統(tǒng)SVM進(jìn)行了改進(jìn)，可以說結(jié)構(gòu)化SVM是在傳統(tǒng)SVM的基礎(chǔ)上擴(kuò)展出來的。結(jié)構(gòu)化SVM使用時主要涉及學(xué)習(xí)和推理兩個過程，與大多數(shù)機(jī)器學(xué)習(xí)算法一樣，學(xué)習(xí)其實(shí)就是確定模型的參數(shù)的過程，而推理就是根據(jù)學(xué)習(xí)到的模型對給定的輸入進(jìn)行預(yù)測的過程。
假設(shè)給定了訓(xùn)練集
，其中X和Y是兩個集合，結(jié)構(gòu)化SVM就是通過這些樣本來訓(xùn)練一個輸入輸出對的函數(shù)
。預(yù)測時，對于給定的輸入X，在所有X∈Y中取得最大值的Y即為預(yù)測項。
學(xué)習(xí)結(jié)構(gòu)化數(shù)據(jù)就是要找到上述的一個判別函數(shù)，使之在判別函數(shù)確定后，對給定的輸入X，能選擇最大化函數(shù)f值的Y作為輸出。假定函數(shù)f的形式為，
其中判別函數(shù)
，W是參數(shù)向量，而Ψ(X,Y)可以看成是輸入輸出對的特征表示，代表將輸入輸出對合并起來的特征向量，它的形式取決于具體問題。 一般會假設(shè)F(X,Y;W)是(X,Y)和參數(shù)向量W的線性函數(shù)，即
。
接著還得再定義一個損失函數(shù)Δ:Y×Y→R，它應(yīng)該滿足Y=Y＇時Δ(Y,Y＇)=0，當(dāng)Y≠Y＇,時Δ(Y,Y＇)>0。那么有經(jīng)驗風(fēng)險函數(shù)，
所以我們的目標(biāo)是要找到一個
使得經(jīng)驗風(fēng)險函數(shù)最小，而它可能存在經(jīng)驗風(fēng)險為0的情況，此時，滿足如下條件
其中，
。根據(jù)間隔最大化來求解，固定ww的長度，求能使得間隔最大的W。兩個超平面的距離為
，最大化
其實(shí)就等價于最小化
，這時已經(jīng)可以轉(zhuǎn)成SVM中優(yōu)化問題的形式了，
但實(shí)際情況中經(jīng)驗風(fēng)險為0可能會導(dǎo)致過擬合現(xiàn)象，這時要考慮容忍訓(xùn)練集中某些樣本錯誤分類，從而引入松弛變量，于是優(yōu)化問題變?yōu)椋?/p>
約束條件引入損失函數(shù)的影響，得
那么現(xiàn)在不管是經(jīng)驗風(fēng)險為0還是不為0，剩下要做的事就是求解上述優(yōu)化問題，即根據(jù)上述各個式子中的約束條件解得最優(yōu)值W。怎么求解還是個難題，如果樣本數(shù)較少且Y狀態(tài)數(shù)較少，能用傳統(tǒng)的二次優(yōu)化求解。
而實(shí)際情況中樣本數(shù)和狀態(tài)數(shù)都較多，于是產(chǎn)生的約束條件規(guī)模非常大，總數(shù)量為 n*(|Y|-1)，其中n為樣本數(shù)，|Y|為y可能的狀態(tài)數(shù)。所以在求解過程中需要先將上述優(yōu)化問題轉(zhuǎn)換成對偶形式，采用割平面訓(xùn)練法，具體優(yōu)化過程不考慮所有約束條件，從無約束問題出發(fā)，逐步選擇約束直到精度滿足期望后停止。
常用的標(biāo)注策略有IOB標(biāo)記，即塊的第一個符號處標(biāo)注為B，塊內(nèi)部的符號標(biāo)注為I，塊外的符號標(biāo)注O。其中B為Begin，表示開始；I為Intermediate，表示中間；O為Other，表示其他。比如：
我明天去北京。
OBIOBI
使用dlib庫實(shí)現(xiàn)結(jié)構(gòu)化SVM序列標(biāo)注功能，以下僅僅是一個簡單的功能。對“我 昨 天 在 學(xué) 校 看 到 小 明”，“小 紅 剛 剛 才 去 晚 自 習(xí)”中的人名進(jìn)行標(biāo)注，并且使用BIO標(biāo)記方式，通過訓(xùn)練后對“我 昨 天 在 學(xué) 校 見 到 大 東”句子進(jìn)行人名提取。
輸出分別為：
小 明
小 紅
大 東
#include <iostream>#include <cctype>#include <dlib/svm_threaded.h>#include <dlib/string.h>using namespace std;using namespace dlib;class feature_extractor{public: typedef std::vector<std::string> sequence_type; const static bool use_BIO_model = true; const static bool use_high_order_features = true; const static bool allow_negative_weights = true; unsigned long window_size() const { return 3; } unsigned long num_features() const { return 1; } template <typename feature_setter> void get_features(
feature_setter& set_feature, const sequence_type& sentence, unsigned long position
) const
{ if (sentence[0].compare("小") == 0 || sentence[0].compare("明") == 0 || sentence[0].compare("紅") == 0 || sentence[0].compare("張") == 0 || sentence[0].compare("陳") == 0)
set_feature(0);
}
};void make_training_examples( std::vector<std::vector<std::string> >& samples, std::vector<std::vector<std::pair<unsigned long, unsigned long> > >& segments
){ std::vector<std::pair<unsigned long, unsigned long> > names;
samples.push_back(split("我 昨 天 在 學(xué) 校 看 到 小 明"));
names.push_back(make_pair(8, 10));
segments.push_back(names); names.clear();
samples.push_back(split("小 紅 剛 剛 才 去 晚 自 習(xí)"));
names.push_back(make_pair(0, 2));
segments.push_back(names); names.clear();
}void print_segment( const std::vector<std::string>& sentence, const std::pair<unsigned long, unsigned long>& segment
){ for (unsigned long i = segment.first; i < segment.second; ++i) cout << sentence[i] << " "; cout << endl;
}int main(){ std::vector<std::vector<std::string> > samples; std::vector<std::vector<std::pair<unsigned long, unsigned long> > > segments;
make_training_examples(samples, segments);
structural_sequence_segmentation_trainer<feature_extractor> trainer;
sequence_segmenter<feature_extractor> segmenter = trainer.train(samples, segments); for (unsigned long i = 0; i < samples.size(); ++i)
{ std::vector<std::pair<unsigned long, unsigned long> > seg = segmenter(samples[i]); for (unsigned long j = 0; j < seg.size(); ++j)
{
print_segment(samples[i], seg[j]);
}
} std::vector<std::string> sentence(split("我 昨 天 在 學(xué) 校 見 到 大 東")); std::vector<std::pair<unsigned long, unsigned long> > seg = segmenter(sentence); for (unsigned long j = 0; j < seg.size(); ++j)
{
print_segment(sentence, seg[j]);
}
}
雷峰網(wǎng)特約稿件，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
