0
雷鋒網 AI 研習社按：本文為 seaboat 為雷鋒網 AI 研習社撰寫的獨家稿件，未經雷鋒網許可不得轉載。
SVM 即支持向量機，常用于二分類模型。它主要的思想是：
它是特征空間上間隔最大的線性分類器。
對于線性不可分的情況，通過非線性映射算法將低維空間的線性不可分的樣本映射到高維特征空間，高維特征空間能夠進行線性分析。
其實機器學習中，如果按照輸出空間不同可以分為：
二元分類(binary classification)
多元分類(multiclass classification)
回歸問題(regression)
結構化預測(structured prediction)
其中前面三類都是我們常見且經常用的，第四種結構化預測重點體現在結構化上，前面三類的輸出都是標簽類別或者回歸值之類的單變量，而結構化預測輸出是一種結構化的數據結構，比如輸入一句話，輸出是一顆語法樹。此外，結構還可以是圖結構、序列結構等。
把前面的SVM與結構化結合起來就是結構化SVM了。它為了處理更加復雜的彼此之間互相存在依賴關系的結構數據，對傳統SVM進行了改進，可以說結構化SVM是在傳統SVM的基礎上擴展出來的。結構化SVM使用時主要涉及學習和推理兩個過程，與大多數機器學習算法一樣，學習其實就是確定模型的參數的過程，而推理就是根據學習到的模型對給定的輸入進行預測的過程。
假設給定了訓練集
，其中X和Y是兩個集合，結構化SVM就是通過這些樣本來訓練一個輸入輸出對的函數
。預測時，對于給定的輸入X，在所有X∈Y中取得最大值的Y即為預測項。
學習結構化數據就是要找到上述的一個判別函數，使之在判別函數確定后，對給定的輸入X，能選擇最大化函數f值的Y作為輸出。假定函數f的形式為，
其中判別函數
，W是參數向量，而Ψ(X,Y)可以看成是輸入輸出對的特征表示，代表將輸入輸出對合并起來的特征向量，它的形式取決于具體問題。 一般會假設F(X,Y;W)是(X,Y)和參數向量W的線性函數，即
。
接著還得再定義一個損失函數Δ:Y×Y→R，它應該滿足Y=Y＇時Δ(Y,Y＇)=0，當Y≠Y＇,時Δ(Y,Y＇)>0。那么有經驗風險函數，
所以我們的目標是要找到一個
使得經驗風險函數最小，而它可能存在經驗風險為0的情況，此時，滿足如下條件
其中，
。根據間隔最大化來求解，固定ww的長度，求能使得間隔最大的W。兩個超平面的距離為
，最大化
其實就等價于最小化
，這時已經可以轉成SVM中優化問題的形式了，
但實際情況中經驗風險為0可能會導致過擬合現象，這時要考慮容忍訓練集中某些樣本錯誤分類，從而引入松弛變量，于是優化問題變為：
約束條件引入損失函數的影響，得
那么現在不管是經驗風險為0還是不為0，剩下要做的事就是求解上述優化問題，即根據上述各個式子中的約束條件解得最優值W。怎么求解還是個難題，如果樣本數較少且Y狀態數較少，能用傳統的二次優化求解。
而實際情況中樣本數和狀態數都較多，于是產生的約束條件規模非常大，總數量為 n*(|Y|-1)，其中n為樣本數，|Y|為y可能的狀態數。所以在求解過程中需要先將上述優化問題轉換成對偶形式，采用割平面訓練法，具體優化過程不考慮所有約束條件，從無約束問題出發，逐步選擇約束直到精度滿足期望后停止。
常用的標注策略有IOB標記，即塊的第一個符號處標注為B，塊內部的符號標注為I，塊外的符號標注O。其中B為Begin，表示開始；I為Intermediate，表示中間；O為Other，表示其他。比如：
我明天去北京。
OBIOBI
使用dlib庫實現結構化SVM序列標注功能，以下僅僅是一個簡單的功能。對“我 昨 天 在 學 校 看 到 小 明”，“小 紅 剛 剛 才 去 晚 自 習”中的人名進行標注，并且使用BIO標記方式，通過訓練后對“我 昨 天 在 學 校 見 到 大 東”句子進行人名提取。
輸出分別為：
小 明
小 紅
大 東
#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("我 昨 天 在 學 校 看 到 小 明"));
names.push_back(make_pair(8, 10));
segments.push_back(names); names.clear();
samples.push_back(split("小 紅 剛 剛 才 去 晚 自 習"));
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("我 昨 天 在 學 校 見 到 大 東")); 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]);
}
}
雷峰網特約稿件，未經授權禁止轉載。詳情見轉載須知。
