自然语言理解大作业!
——基于 HMM 的分词以及基于 SVM 的文本分类!
冯亚伟
!
陈呈辉
!
祥保庆
!
一.作业框架!
基于 "#$ 实现文本分类的主要步骤包括:%、文本分词处理,&、特征选择,'、特
征权重计算,'、文本特征向量表示,(、基于训练文本的特征向量数据,训练 "#$ 模
型,)、对于测试集进行特征向量表示,代入训练得到的 "#$ 模型中进行预测分类。!
在这次大作业中,我们使用 *$$ 模型实现了一个分词程序,其中使用了 +,-./0! 的
0123, 库,然后对搜狗语料库中的文本进行分词处理。在这里我们对搜狗预料库进行
了裁剪,只选择了 &&44 个文本,每个类别 &&4 个文本,其中前 &44 个文本用作训练,
后 &4 个文本用作测试。在这次大作业中,我们实现的分词程序的正确率在 546左右,
具体分词正确率结果在 7.809:9"9;290-<-8/0=+>?@AB=:C/D9E-F- 文件中!
特征选择我们采用的是开方检验的算法G选择的特征在 "#$H9<-1D9E-F- 文件中,每
个类别选取 %444 个特征,%4 个类别 %4444 特征,由于重复,计算出来的特征为 I)45
个。!
特征权重计算,采用的是 JHKLMH 计算算法,训练文本的特征向量表示数据在
-D<80E:N2 文件中,测试文本的特征向量表示数据在 -9:-E:N2 中。!
对 -D<80E:N 2 对于模型训练,和对于 -9:-E:N2 模型预测,使用的是 OLB"#$ 库,链接
为 .--3PQQRRREC:89E0-1E9S1E-RQTCUV80QV8W:N2Q,文本分类正确率为 %X(Q&44Y4E5&。文本分
类具体结果在 OLB"#$ 文件夹中G具体测试命令在这个文件夹下的“测试命令E-F-”文件
中。!
二E! 背景知识!
%E! 隐马尔科夫模型Z*$$[!
*$$! 是在! $<D\/N! 链基础上发展起来的G 是一个双重随机过程G 其中之一是!
$<D\/N! 链G是基本的随机过程G描述状态的转移]另一个随机过程描述状态和观察值之间
的统计对应关系。站在观察者的角度G只能看到观察值G不能直接看到状态G是通过一个随
机过程去感知状态的存在及特性。因此称为“隐”$<D\/N! 模型G即! *$$。!
*$$ 可以记为 ^!YZ_G$G`GaGB[G简写 ^!YZ`GaGB[。更形象的说G*$$! 分为两部分P一个!
$<D\/N! 链G由! `G!a! 描述G! 产生的输出为状态序列]另一个随机过程G由! B! 描述G产生输出
观察值序列。! !
*$$! 模型具体可以由下列参数描述P! !
Z%[!_!P模型中! $<D\/N! 链状态数目。记! _! 个状态为! "%GG"_!G记! -! 时刻! $<D\/N! 链
所处状态为! b-!G显然! b-!Z"%GG"_[。 !
Z&[$!P每个状态对应的可能的观察值数目。记! $! 个观察值为 #%G…G#$!G记 - 时刻的
观察值为 c-!G!c-!Z#%GG#$[。! !
Z'[`P初始状态概率矢量G`YZ`%GG` _![。其中G!
!
Z([a 为状态转移概率矩阵GaYZ<8U[_d_! 。其中G! !
!
Z)[B 为观察值概率矩阵GBYZWU\[_d$! 。其中G! !
!
应用 *$$ 模型的步骤如下:!
Z!%![! 得! 到! 观! 察! 序! 列! c!Y!c%!G! …G!c!0! 和! 模! 型! ^!Y!Z!`!G!a!G!B![!G! 利用前向e后向
算法快速计算出在该模型下G观察事件序列发生的概率 +ZcQ^[。Z评估问题[。!
Z&[利用! #8-9DW8! 算法选择对应的状态序列! "! Y! b%! GG! b0! G使! "! 能够合理的解释观察
序列! c! 。即揭开模型的隐含部分G在优化准则下找到最优状态序列。Z解码问题[。!
Z'[利用! B<12ef9VC.! 算法调整模型参数! ^! Y! Z`G! aG! B[! G! 即得到模型中的五个参数G
使得! +Zc!Q!^[! 最大。Z学习问题[。!
&.支持向量机方法("#$)!
"#$ 方法适合大样本集的分类G特别是文本分类G它将降维和分类结合在一起。"#$
算法基于结构风险最小化原理G将原始数据集合压缩到支持向量集合G然后用子集学习得
到新知识G同时也给出由这些支持向量决定的规则。并且可得到学习错误的概率上界。
假设线性分类面的形式为P! !
360
(, ,π,,)
N
MAB
λ
=
(π,,)
A
B
λ
=
π,
A
B
N
N
1
,,
N
SS
t
t
q
t
q ∈
1
,,
N
SS
M
M
1
,,
M
VV
t
t
O
t
O
1
(, , )
M
VV∈
π π
1
π ,,π
N
i1
1
π (),1 ,
π 0,
π 1
i
i
N
i
i
Pq S i N
°
=
⎧
⎪
==≤≤
⎪
≥
⎨
⎪
=
⎪
⎩
∑
A
A
()
ij N N
a
×
1
1
(/),1,,
0,
1
ij t j t i
ij
N
ij
j
apq SqS ijN
a
a
+
°
=
⎧
⎪
===≤≤
⎪
⎪
≥
⎨
⎪
⎪
=
⎪
⎩
∑
B
()
jk N M
b
×
=B
1
() ( / ) ( | ),1 ,1 ,
() 0,
() 1
jtktjkj
j
M
j
k
bk pO V q S pV S j N k M
bk
bk
°
=
⎧
⎪
== == ≤≤≤≤
⎪
⎪
≥
⎨
⎪
⎪
=
⎪
⎩
∑
1
,,
n
OO O=
(π,,)
A
B
λ
=
(/)PO
λ
1
,,
n
Sq q=
O
(π,,)
A
B
λ
=
(/)PO
λ
2
2
41
N
77
00
(2 1) π
(,) ()() (, )cos( )
8
(2 1) π
cos( )
8
xy
xu
Cuv auav f xy
yv
==
+
=
⋅
+
∑∑
.3
360
(, ,π,,)
N
MAB
λ
=
(π,,)
A
B
λ
=
π,
A
B
N
N
1
,,
N
SS
t
t
q
t
q ∈
1
,,
N
SS
M
M
1
,,
M
VV
t
t
O
t
O
1
(, , )
M
VV∈
π π
1
π ,,π
N
i1
1
π (),1 ,
π 0,
π 1
i
i
N
i
i
Pq S i N
°
=
⎧
⎪
==≤≤
⎪
≥
⎨
⎪
=
⎪
⎩
∑
A
A
()
ij N N
a
×
1
1
(/),1,,
0,
1
ij t j t i
ij
N
ij
j
apq SqS ijN
a
a
+
°
=
⎧
⎪
===≤≤
⎪
⎪
≥
⎨
⎪
⎪
=
⎪
⎩
∑
B
()
jk N M
b
×
=B
1
() ( / ) ( | ),1 ,1 ,
() 0,
() 1
jtktjkj
j
M
j
k
bk pO V q S pV S j N k M
bk
bk
°
=
⎧
⎪
== == ≤≤≤≤
⎪
⎪
≥
⎨
⎪
⎪
=
⎪
⎩
∑
1
,,
n
OO O=
(π,,)
A
B
λ
=
(/)PO
λ
1
,,
n
Sq q=
O
(π,,)
A
B
λ
=
(/)PO
λ
2
2
41
N
77
00
(2 1) π
(,) ()() (, )cos( )
8
(2 1) π
cos( )
8
xy
xu
Cuv auav f xy
yv
==
+
=
⋅
+
∑∑
.3
360
(, ,π,,)
N
MAB
λ
=
(π,,)
A
B
λ
=
π,
A
B
N
N
1
,,
N
SS
t
t
q
t
q ∈
1
,,
N
SS
M
M
1
,,
M
VV
t
t
O
t
O
1
(, , )
M
VV∈
π π
1
π ,,π
N
i1
1
π (),1 ,
π 0,
π 1
i
i
N
i
i
Pq S i N
°
=
⎧
⎪
==≤≤
⎪
≥
⎨
⎪
=
⎪
⎩
∑
A
A
()
ij N N
a
×
1
1
(/),1,,
0,
1
ij t j t i
ij
N
ij
j
apq SqS ijN
a
a
+
°
=
⎧
⎪
===≤≤
⎪
⎪
≥
⎨
⎪
⎪
=
⎪
⎩
∑
B
()
jk N M
b
×
=B
1
() ( / ) ( | ),1 ,1 ,
() 0,
() 1
jtktjkj
j
M
j
k
bk pO V q S pV S j N k M
bk
bk
°
=
⎧
⎪
== == ≤≤≤≤
⎪
⎪
≥
⎨
⎪
⎪
=
⎪
⎩
∑
1
,,
n
OO O=
(π,,)
A
B
λ
=
(/)PO
λ
1
,,
n
Sq q=
O
(π,,)
A
B
λ
=
(/)PO
λ
2
2
41
N
77
00
(2 1) π
(,) ()() (, )cos( )
8
(2 1) π
cos( )
8
xy
xu
Cuv auav f xy
yv
==
+
=
⋅
+
∑∑
.3