基於結構化SVM進行序列標註

原標題：基於結構化SVM進行序列標註

關於SVM

SVM 即支持向量機，常用於二分類模型。它主要的思想是：

它是特徵空間上間隔最大的線性分類器。

對於線性不可分的情況，通過非線性映射演算法將低維空間的線性不可分的樣本映射到高維特徵空間，高維特徵空間能夠進行線性分析。

什麼是結構化

其實機器學習中，如果按照輸出空間不同可以分為：

二元分類(binary classification)

多元分類(multiclass classification)

回歸問題(regression)

結構化預測(structured prediction)

其中前面三類都是我們常見且經常用的，第四種結構化預測重點體現在結構化上，前面三類的輸出都是標籤類別或者回歸值之類的單變數，而結構化預測輸出是一種結構化的數據結構，比如輸入一句話，輸出是一顆語法樹。此外，結構還可以是圖結構、序列結構等。

結構化SVM

把前面的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標記

常用的標註策略有IOB標記，即塊的第一個符號處標註為B，塊內部的符號標註為I，塊外的符號標註O。其中B為Begin，表示開始；I為Intermediate，表示中間；O為Other，表示其他。比如：

我明天去北京。

OBIOBI

實現例子

使用dlib庫實現結構化SVM序列標註功能，以下僅僅是一個簡單的功能。對「我 昨 天 在 學 校 看 到 小 明」，「小 紅 剛 剛 才 去 晚 自 習」中的人名進行標註，並且使用BIO標記方式，通過訓練後對「我 昨 天 在 學 校 見 到 大 東」句子進行人名提取。

輸出分別為：

小 明

小 紅

大 東

#include

#include

#include

#include

using namespace std;using namespace dlib;class feature_extractor unsigned long num_features() const { return 1; } template

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

& samples, std::vector

& segments

){ std::vector

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

& sentence, const std::pair

& segment){ for (unsigned long i = segment.first; i

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！