您正在使用IE低版浏览器,为了您的雷峰网账号安全和更好的产品体验,强烈建议使用更快更安全的浏览器
此为临时链接,仅用于文章预览,将在时失效
人工智能开发者 正文
发私信给不灵叔
发送

0

基于结构化SVM进行序列标注

本文作者:不灵叔 2018-02-06 09:56
导语:实战!

雷锋网 AI 研习社按:本文为 seaboat 为雷锋网 AI 研习社撰写的独家稿件,未经雷锋网许可不得转载。

关于SVM

SVM 即支持向量机,常用于二分类模型。它主要的思想是:

  • 它是特征空间上间隔最大的线性分类器。

  • 对于线性不可分的情况,通过非线性映射算法将低维空间的线性不可分的样本映射到高维特征空间,高维特征空间能够进行线性分析。

什么是结构化

其实机器学习中,如果按照输出空间不同可以分为:

  • 二元分类(binary classification)

  • 多元分类(multiclass classification)

  • 回归问题(regression)

  • 结构化预测(structured prediction)

其中前面三类都是我们常见且经常用的,第四种结构化预测重点体现在结构化上,前面三类的输出都是标签类别或者回归值之类的单变量,而结构化预测输出是一种结构化的数据结构,比如输入一句话,输出是一颗语法树。此外,结构还可以是图结构、序列结构等。

基于结构化SVM进行序列标注

结构化SVM

把前面的SVM与结构化结合起来就是结构化SVM了。它为了处理更加复杂的彼此之间互相存在依赖关系的结构数据,对传统SVM进行了改进,可以说结构化SVM是在传统SVM的基础上扩展出来的。结构化SVM使用时主要涉及学习和推理两个过程,与大多数机器学习算法一样,学习其实就是确定模型的参数的过程,而推理就是根据学习到的模型对给定的输入进行预测的过程。

假设给定了训练集基于结构化SVM进行序列标注,其中X和Y是两个集合,结构化SVM就是通过这些样本来训练一个输入输出对的函数基于结构化SVM进行序列标注。预测时,对于给定的输入X,在所有X∈Y中取得最大值的Y即为预测项。

学习过程

学习结构化数据就是要找到上述的一个判别函数,使之在判别函数确定后,对给定的输入X,能选择最大化函数f值的Y作为输出。假定函数f的形式为,

基于结构化SVM进行序列标注

其中判别函数基于结构化SVM进行序列标注,W是参数向量,而Ψ(X,Y)可以看成是输入输出对的特征表示,代表将输入输出对合并起来的特征向量,它的形式取决于具体问题。 一般会假设F(X,Y;W)是(X,Y)和参数向量W的线性函数,即基于结构化SVM进行序列标注

接着还得再定义一个损失函数Δ:Y×Y→R,它应该满足Y=Y'时Δ(Y,Y')=0,当Y≠Y',时Δ(Y,Y')>0。那么有经验风险函数,

基于结构化SVM进行序列标注

所以我们的目标是要找到一个基于结构化SVM进行序列标注使得经验风险函数最小,而它可能存在经验风险为0的情况,此时,满足如下条件

基于结构化SVM进行序列标注

其中,基于结构化SVM进行序列标注。根据间隔最大化来求解,固定ww的长度,求能使得间隔最大的W。两个超平面的距离为基于结构化SVM进行序列标注,最大化基于结构化SVM进行序列标注其实就等价于最小化基于结构化SVM进行序列标注,这时已经可以转成SVM中优化问题的形式了,

基于结构化SVM进行序列标注

但实际情况中经验风险为0可能会导致过拟合现象,这时要考虑容忍训练集中某些样本错误分类,从而引入松弛变量,于是优化问题变为:

基于结构化SVM进行序列标注

约束条件引入损失函数的影响,得

基于结构化SVM进行序列标注

那么现在不管是经验风险为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 <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]);
}

}

雷峰网特约稿件,未经授权禁止转载。详情见转载须知

基于结构化SVM进行序列标注

分享:
相关文章
当月热门文章
最新文章
请填写申请人资料
姓名
电话
邮箱
微信号
作品链接
个人简介
为了您的账户安全,请验证邮箱
您的邮箱还未验证,完成可获20积分哟!
请验证您的邮箱
立即验证
完善账号信息
您的账号已经绑定,现在您可以设置密码以方便用邮箱登录
立即设置 以后再说