介绍

FM(Factorization Machines)是一个新模型:它会结合SVM和因子分解模型的优点。FM是一个通用预测器,可以很好地与实数值特征向量一起工作。对比SVM,FM模型会使用因子分解参数来对变量进行交叉。因而,我们可以估计推荐系统中海量稀疏性(huge sparsity)问题中的交叉(这种情况SVM会失败)。我们展示了FM的模型等式,它可以在线性时间内计算,因而FM可以直接进行最优化(optimize)。不同于非线性SVM需要以对偶式做转换,FM可以直接估计模型参数,无需求解任何支持向量(support vector)。本paper也展示了FM和SVM的关系,以及FM在稀疏(sparse)环境下的参数估计的优点。

另一方面,有许多不同的因子分解模型,比如:矩阵分解,并行因子分析模型(如:SVD++,PITF or FPMC)。这些模型的缺点是,不能应用于常见的预测任务(但对于一些特殊的输入数据管用)。这些模型等式和优化算法对于每个任务各不相同。我们展示了FM可以模仿这些模型,只需要指定输入数据(即:特征向量)即可。这让FM很容易使用,即使是对于那些在因子分解模型没有专家经验的用户。

1.介绍

SVM是最流行的预测器之一。然而,在协同过滤领域,SVM基本上毫无用武之地,该领域最好的模型是标准的矩阵/张量分解模型(matrix/tensor factorization model),比如:PARAFAC或者使用因子分解参数的特殊模型[2][3][4]。在本paper中,我们展示了为什么标准的SVM预测器在这些任务上不能成功的原因:在非常sparse的数据上,不能在复杂(非线性)kernel spaces上学到可靠的参数(超平面)。另一方面,张量分解模型的缺点是:

  • (1) 它们不能应用于标准的预测数据(比如:在$R^n $ 空间中的实数值特征向量)
  • (2) 对于特定的任务,需要在建模和算法设计时进行单独构建

在本paper中,我们引入了一个新的预测器,Factorization Machine(FM),它是一个通用的预测器(类似于SVM),但也能在高度稀疏(sparsity)的数据下估计得到可靠参数。FM模型所有都嵌套着变量交叉(对比:在SVM中通过一个polynomial kernel),但它会使用一个因子分解参数( factorized parametrization)的方法,而非SVM中的dense参数化(dense parametrization)。我们展示了FM的模型等式,它可以在线性时间内计算,只依赖于一个线性数量的参数。这允许直接优化和模型参数存储,无需存储任意训练中数据(比如:支持向量)来进行预测。对比于FM,非线性SVM通常以对偶形式(dual form)进行优化,依赖于训练中数据(支持向量)来计算预测。我们也展示了,FM把许多对于协同过滤任务的成功方法(biased MF, SVD++, PITF, FPMC)包含在内。

总之,我们提出的FM的优点有:

  • 1) FM允许在非常sparse的数据(SVM会失败)上进行参数估计
  • 2) FM具有线性复杂度,可以以原始形式优化,不需要依赖像SVM中的支持向量(SV)。我们展示了FM可以扩展到大数据集上(比如:Netflix 1000w训练实例)
  • 3) FM是一个通用预测器,可以与任意实数型特征向量(real valued feature vector)一起工作。对比于FM,其它state-of-art的因子分解模型非常受限于输入数据。我们将展示通过定义输入数据的特征向量,FM可以模仿state-of-the-art的模型(biased MF, SVD++, PITF, FPMC)。

2.sparsity下的预测

最常见的预测任务是:估计一个函数:

\[y : R^n \to T\]

从一个实数值特征向量 \(x \in R^n\),到一个目标域T(比如:对于回归, T=R;对于分类,T={+, -})。

在监督学习领域,假设存在一个训练样本数据集:\(D=\lbrace (x^{(1)},y^{(1)}), (x^{(2)},y^{(2)}), ... \rbrace\),y为目标函数(target function)。我们也研究了排序任务,其中函数y的目标 T=R 可以被用于得分特征向量(score feature vectors)x,可以根据score进行排序。得分函数(score functions)可以通过pairwise的训练数据进行学习得到,其中特征tuple \((x^{(A)}, x^{(B)}) \in D\)意味着\(x^{(A)}\)的排序比\(x^{(B)}\)更高。由于pairwise的排序关系是不对称的(antisymmetric),只使用正例进行训练就足够了。

在本paper中,我们处理该问题,其中x是高度稀疏的(比如:向量x中几乎大多数元素\(x_i\)都是0)。假设m(x)是特征向量x中非零元素的数目,\(\bar{m}_{D}\)是所有向量 \(x\in D\)的m(x)的平均非零元素个数。现实世界中十分稀疏(huge sparsity )的情况很常见(\(\bar{m}_{D} \ll n\)),比如事件交互(推荐系统中的购买),或者文本分析(bag-of-word方法)。huge sparsity的一个原因是,需要处理海量的类别型变量域。

示例1:假设我们具有一个电影评论系统的交互数据。该系统记录了:用户\(u \in U\)对一部电影\(i \in I\)的评分,时间为\(t \in R\),评分为\(r \in \lbrace 1,2,3,4,5 \rbrace\)。假设用户U和item I如下:

U = {Alice (A), Bob (B), Charlie (C), . . .}

I = {Titanic (TI), Notting Hill (NH), Star Wars (SW), Star Trek (ST), . . .}

观察到的数据S:

S = {(A, TI, 2010-1, 5),(A, NH, 2010-2, 3),(A, SW, 2010-4, 1), (B, SW, 2009-5, 4),(B, ST, 2009-8, 5), (C, TI, 2009-9, 1),(C, SW, 2009-12, 5)}

对于一个使用该数据的预测任务,目标是估计一个函数\(\hat{y}\)来预测:在某个时间点上,一个用户对一个item的评分行为。

图一:示例1的交互所创建的稀疏实数特征向量x。每一行表示了一个特征向量\(x^{(i)}\),以及它对应的目标\(y^{(i)}\),前4列(蓝色)表示用户的指示变量:接下来的5列(红色)表示item的指示变量。接下来的5列(黄色)持有着额外的隐式指示(比如:该用户评过分的其它电影)。一个特征(绿色)表示了月份时间。最后的5列(棕色)表示在该电影前评过分的最后一部电影。最右边的列是target:这是评分。

图1展示了特征向量是如何从S中被创建的。首先,\(|U|\)是个二元变量(蓝色),它表示了一个交互的当前用户————通常对于一个交互\((u,i,t,r) \in S\)只有一个用户,例如:在第一个(\(x_A^{(1)} =1\) )的用户Alice。下一个\(|I|\)二元变量(红色)持有着item(例如:\(x_{T1}^{(1)}=1\))。图1的特征向量还包含了该用户评分过的其它电影(黄色)。对于每个用户,变量被归一化成总和为1. 例如:Alice评分了Titanic,Notting Hill和 Star Wars。另外,该样本包含了月份时间。最后,该向量包含了评分前最后一部电影的信息。例如,对于\(x^{(2)}\),Alice在对Notting Hill评分前,就对Titanic进行了评分。在第V节,我们展示了FM使用这样的特征向量作为输入数据,并与state-of-art算法进行比较。

我们将使用该样本数据进行本paper的演示。然而,注意FM是通用的预测器,任何实数型特征向量都可以使用,并不局限于推荐系统。

3.FM

在本节中,我们引入了因子分解机(FM)。我们详细讨论了模型等式,简短展示了如何应用FM到一些预测任务上。

A.FM模型

1)模型等式(Model Equation):阶(degree)为2,定义如下:

\[\hat{y}(x) := w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle v_i, v_j \rangle x_i x_j\]

…(1)

其中,要估计的模型参数是:

\[w_0 \in R, w \in R^{n}, V \in R^{n * k}\]

…(2)

其中<.,.>是两个size=k的向量的点乘:

\[\langle v_i,v_j \rangle := \sum_{f=1}^{k} v_{i,f} \cdot v_{j,f}\]

…(3)

在V中的一行\(v_i\)描述了具有k个因子的第i个变量。\(k \in N_{0}^{+}\)是一个超参数,它定义了因子分解的维度。

一个2-way FM(degree d = 2)捕获了所有变量间的single和pairwise交叉:

  • \(w_0\)是全局bias
  • \(w_i\)建模了第i个变量的权重
  • \(\hat{w}_{i,j} := \langle v_i, v_j \rangle\)建模了第i个和第j个变量间的交叉(interaction)。FM模型不会为每个交叉使用单独的模型参数\(w_{i,j} \in R\),作为替代,FM模型通过对它进行因子分解(factorizing)来对交叉进行建模。稍后我们可以看到,对于稀疏的高阶交叉(d>=2)允许高质量参数估计,这就是其关键点。

2) 表现力(Expressiveness):我们都知道:当k足够大时,对于任意正定矩阵W(positive definite matrix),存在一个矩阵V,使得 \(W=V \cdot V^t\)(Cholesky decomposition)。这表明:当k足够大时,一个FM可以表示任意交叉矩阵W。然而在稀疏情况下,通常会选择一个小k,因为没有足够多的数据来估计复杂交叉W。限制k(也就是限制FM的表现力),可以产生更好的泛化,这样可以提升稀疏情况下的交叉矩阵。

3)稀疏条件下的参数估计:在sparse情况下,通常没有足够多的数据来直接地、独立地估计变量间的交叉(interactions)。FM可以在这样的情况下很好地估计交叉,因为他们通过对它们进行因子分解分离出交叉参数的独立性。总之,这意味着,对于一次交叉的数据可以帮助估计相关交叉的估计。以下的示例会利用来自图1的数据,使该思想更清晰。

假设:我们希望估计在Alice(A)和Star Trek(ST)间的交叉,来预测目标y(即rating)。很明显,在训练数据中,没有这样的样本x,同时满足\(x_A\)和\(x_{ST}\)都是非零的,因而一个直接的估计是没有交叉(\(W_{A,ST}=0\))。但是,这种情况下的因子分解的交叉参数\(\langle v_A, v_{ST} \rangle\)是可以估计的。首先,Bob和Charlie具有相似的因子向量(factor vector)\(v_B\)和\(v_C\),因为对于预测评分来说,两人与Star Wars(\(v_{SW}\))的交叉相似:\(\langle v_B, v_{SW} \rangle\)和 \(\langle v_C, v_{SW} \rangle\)必须相似。相比之下,Alice(\(v_A\))和Charlie(\(v_C\))之间会具有不同的因子向量(factor vector),因为在评分上,Alice与Titanic 和 Star Wars的因子也存在不同的交叉。另外,Star Trek的因子向量可能与Star Wars的相似,因为对于预测y来说,Bob与这两部电影具有相同的交叉。总之,这意味着,Alice和Star Trek的因子向量点积(交叉) ,将与Alice和Star Wars的因子向量点积相似——这在直观上是说得通的。

4)计算

接着,我们将展示如何从计算角度来让FM可用。等式(1)的计算复杂度是\(O(k n^2)\),因为所有pairwise交叉必须被计算。但是,用公式重新表示会下降到线性运行时(linear runtime)。

引理3.1:FM的模型等式(1)可以以线性时间O(kn)被计算。

证明:由于pairwise型交叉(interaction)的因子分解,不存在直接依赖这两个变量的模型参数(例如:一个带有索引(i,j)的参数)。因而,pairwise的交叉可以重新进行公式化:

该等式具有O(kn)的线性复杂度

再者,在sparsity情况下,x中的大多数元素为0(例如:m(x)很小),因而,该求和可以通过非零元素的计算来得到。在sparse应用中,FM的计算复杂度为\(O(k \hat{m}_D)\),例如:\(\hat{m}_D=2\),对于常见的推荐系统,比如MF方法。

B.FM作为预测器

FM可以应用到许多预测任务中。比如:

  • 回归:\(\hat{y}(x)\)可以直接用于预测,最优化准则可以是在D上最小化square error。
  • 二元分类:\(sign(\hat{y}(x))\),最优化准则可以使用hinge loss或者logit loss。
  • 排序(Ranking):向量x会通过\(\hat{y}(x)\)的得分进行重新排序,最优化通过实例向量对\((x^{(a)}, x^{(b)} \in D\),根据pairwise classification loss进行分类。

在所有的case中,正则项L2通常被添加到目标函数上来进行优化来阻止overfit。

C.FM的学习

FM具有一个封闭(closed)的模型等式,可以在线性时间上计算。这样,FM的模型参数(w0, w和 V)——可以有效地通过梯度下降法学到。——例如SGD,计算square, logit or hinge loss。FM模型的梯度如下:

…(4)

\(\sum_{j=1}^{n} v_{j,f}x_j\)是与i独立的,可以预计算(例如:当计算 \(\hat{y}(x)\)时)。总之,每个梯度都可以在常数时间内被计算。对于(x,y)的所有参数更新可以在O(kn)——或者稀疏情况下O(km(x))时间内完成。

我们提供了一个泛化实现,LibSVM,使用SGD,并支持element-wise和pairwise loss。

D.d-way FM

2-way FM可以很容易泛化到d-way Fm上:

\(\hat{y}(x):=w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{l=2}^{d}\sum_{i_1=1}^{n}...\sum_{i_l=i_{l-1}+1}^{n} (\prod_{j=1}^{l} x_{i_j}) (\sum_{f=1}^{k_l}\prod_{j=1}^{l} v_{i_j,f}^{(l)})\) …(5)

其中,l次交叉的交叉参数可以通过使用以下模型参数的PARAFAC模型进行因子分解:

\(V^{(l)} \in R^{n * k_1}, k_l \in N_0^{+}\) …(6)

等式(5)的计算复杂度为 \(O(k_d n^d)\)。但与引理3.1有相近的参数,可以看到在线性时间内被计算。

E.总结

FM模型在特征向量x中的值之间所有可能的交叉,使用因子分解交叉(factorized interactions),而非完全参数化交叉(full parametrized)。这主要有两个优点:

  • 1) 即使很稀疏,值之间的交叉可以被估计。尤其是,它可以泛化到未观察到的交叉
  • 2) 参数的数目对于预测和训练时间是线性的。这可以使用SGD直接进行最优化,并可以使用多种loss。

与其它模型的对比

详见paper,此处不介绍.

https://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf

本文是youtube在2010年提出的系统,现在回过头去看看它在当时是如何实现youtube的推荐系统的。

系统设计

推荐系统的整个设计都围绕以下的目标:我们希望相应的推荐(recommendations)是适度最新的(recent)、新鲜的(fresh),多样化的(diverse),并且与用户最近的动作有相关性(relevant)。另外,重要的一点是,用户能理解为什么某个视频会被推荐给他们

推荐的视频集合通过使用一个用户的个性化行为(观看,收藏,喜欢)来生成作为种子,然后通过基于视频图的co-visitation对集合进行扩展。该视频集接着使用多个信号为相关性(relevance)和多样性(diversity)进行排序

从工程的角度看,我们希望系统的单个组件相互解耦,允许它们进行独立的调试,以便容错,降低系统的整体复杂度。

1.输入数据

在个性化视频推荐的生成期间,我们会考虑多个数据源。总之,有两大类的数据要考虑:

  • 1)内容数据(content data),比如原始视频流和视频元信息(标题,简介等)
  • 2)用户行为数据(user activity data),可以进一步分类为显式和隐式。显式行为包括:对一个视频进行打分(rating),进行收藏/喜欢,或者订阅了某个上传者。隐式行为包括:观看、交互,比如:用户开始观看一个视频,用户观察了某个视频的大部分(长播放行为:long watch)

在所有的case中,数据的处理noisy很多:视频元信息可以不存在,不完整,过期,或者不正确;用户数据只捕获了在网站端的一部分用户行为,只能间接衡量一个用户的参与度(engagement)和高兴度(happiness),比如:用户完整地观看一个视频,不足够说明她确实喜欢这个视频。视频的长度和用户的参考程度,受信号质量的影响。再者,隐式行为数据是异步生成的,可能不完整,比如:在我们接受到一个long-watch通知前,用户可能已经关闭了浏览器。

2.相关视频

推荐系统的一个构建块是:构造一个映射(mapping),将一个视频$ v_i $映射到一个相似(similar)或相关(related)的视频集合$ R_i $上。在该上下文上,我们定义了相似视频:在观看了给定的种子视频v(seed video)后,一个用户会喜欢继续观看这些视频集。为了计算该mapping,我们使用了一些著名的技术:关联规则挖掘(association rule mining)、或者 co-visitation counts。让我们来看下:用户在网站上观看行为的session。对于给定的时间周期(24小时),我们会统计每对视频对(video pair):$(v_i,v_j)$,在session内被同时观看(co-watch)的次数。将该co-visitation count置为$ c_{ij} $,我们定义了视频$ v_j $基于视频$ v_i$的相关得分:

\[r(v_i,v_j)= \frac{c_{ij}}{f(v_i,v_j)}\]

…(1)

其中,$c_i$和$ c_j $是所有session上视频$v_i$和$ v_j$各自的总共现次数。$ f(v_i,v_j)$是一个归一化函数,它会考虑种子视频和候选视频的“全局流行度(global popularity)“。一种最简单的归一化函数是,简单地除以视频的全局流行度的乘积:$f(v_i,v_j)=c_i \cdot c_j $。也可以选择另一种归一化函数。见paper[6]。当使用候选的简单乘积进行归一化时,$c_i$对于所有的候选相关视频是相同的,可以在我们的设置(setting)中忽略。这本质上会在流行视频中支持更低流行度的视频。

对于一个给定的种子视频$v_i$,我们接着选取相关视频$R_i$的集合,通过它们的得分$r(v_i,v_j)$进行排序,选取topN个候选视频。注意:除了只选取topN个视频外,我们也加入一个最低的得分阀值(minimum score threshold)。因而,对于许多视频,我们不能计算一个可靠的相关视频集合,因为它们整体的观看量(view count:与其它视频的co-visitation counts)很低。

注意,这是一个简化版的描述。实际上,还存在额外的问题需要去解决——表示偏差(presentation bias),噪声观看数据(noisy watch data),等————在co-visitation counts之外的额外数据源,也可以被使用:视频播放的sequence和time stamp、视频元信息等等。

相关视频可以被看成是在视频集上引导成一个直连图(directed graph):对于每个视频对$(v_i,v_j)$,从$v_i$到$v_j$上有一条边(edge) $ e_{ij} $,如果$v_j \in R_i $,该边的权重由等式(1)给定。

3 生成推荐候选

为了计算个性化推荐,我们将相关视频的关联规则,以及一个用户在网站上的个人行为相结合:它包括被观看的视频(超过某个固定阀值),以及显式收藏(favorited)、喜欢(liked)、打分(rated)、添加到播放列表(added to playlists)的视频。我们将这些视频集合称为种子集(seed set)

对于给定的种子集合S,为了获取候选推荐,我们将它沿着相关视频图的边进行扩展:对于种子集合里的每个视频$v_i$,会考虑它的相关视频$ R_i $。我们将这些相关视频集合的合集(union)表示为$C_1$:

\[C_1(S) = \bigcup_{v_i \in S} R_i\]

…(2)

在许多情况下,计算$C_1$对于生成一个候选推荐集合是足够的,它足够大并且足够多样化来生成有趣的推荐。然而,实际上任何视频的相关视频的范围都趋近于狭窄(narrow),经常会突显(highlighting)出那些与种子视频相似的视频。这会导致范围相当狭窄的推荐(narrow recommendation),它确实会让推荐内容与用户兴趣接近,但对于推荐新视频给用户时会很失败。

为了扩大推荐的范围,我们通过在相关视频图上采用一个有限的传递闭包(limited transitive closure),来扩展候选集。$C_n$被定义成这样的视频集合,它从种子集合中的任意视频在距离n内可达

\[C_n(S) = \bigcup_{v_i \in C_{n-1}} R_i\]

…(3)

其中$ C_0=S $是该递归定义中的base case(注意:它会为$C_1$产生一个与等式(2)的同等定义)。最终的候选集合$C_{final}$接着被定义成:

\[C_{final}=(\bigcup_{i=0}^{N} C_i) \backslash S\]

…(4)

由于相关视频图的高分支因子(high branching factor),我们发现,在一个较小的距离上扩展,可以产生一个更宽更多样的推荐集合,即使用户只有一个小的种子集合。注意:候选集中的每个视频,与种子集合中一或多个视频有关联。为了进行ranking,我们继续跟踪这些种子与候选的关联,并为推荐给用户提供解释。

4.Ranking

在生成阶段,已经产生了候选视频,它们使用许多信号进行打分和排序。这些信息可以根据ranking的三个不同阶段归类成三组:

  • 1)视频质量(video quality)
  • 2)用户特征(user specificity)
  • 3)多样化

视频质量信号,是指在不考虑用户的情况下,判断视频被欣赏的似然(likelihood)。这些信息包括:观看量(view count: 一个视频被观看的总次数),视频的评分,评论,收藏,分享行为,上传时间等。

用户特征信号,用于增强一个视频与某个用户特有的品味和偏好相匹配。我们会考虑种子视频在用户观看历史中的属性,比如:观看量(view count)、观看时长(time of watch)。

通过使用这些信号的一个线性组合,我们为这些候选视频生成了一个排序列表。因为,我们只会展示少量的推荐(4到60之间),我们必须选择列表的一个子集这里不必选择最相关的视频,我们会在相关性和跨类目多样性上做一个平衡优化。因为一个用户通常在不同时刻会在多个不同的主题上有兴趣,如果视频相互间太相似会在该阶段会被移除,以便增加多样性。解决该问题的一种简单方法是,限制单个种子视频的相关推荐数目,或者限制相似频道(channel/uploader)的推荐个数。更复杂的方式是基于主题聚类,或是进行内容分析。

5.UI

推荐的表示在整个用户体验上是很重要的一环。图1展示了推荐是如何在youtube主页上进行表示的。有少量新特性需要注意:首先,所有的推荐视频使用一个缩略图(thumbnail)、标题、视频时间、流行度进行展示。这与主页上的其它部分相类似,可以帮助用户快速决定是否对一个视频有兴趣。再者,我们添加了一个带有种子视频链接(它触发了推荐)的解释(explanation)。最后,我们给出了用户控制,可以看到在主题上有多少个推荐。

在ranking那一节,我们计算了一个推荐的排序列表,但在serving time只会展示其中一个子集。这允许在每次用户到达网站时提供新的、之前未看过的推荐,即使底层的推荐没有被重新计算。

6.系统实现

我们选择一种面向批处理的预计算方式(batch-oriented pre-computation approach),而非按需计算。这样做的优点是:推荐生成阶段访问大量数据会使用大量CPU资源,而在serving时预生成的推荐项可以有极低的访问延时。该方法最大的缺点(downside)是,在生成(generating)和(serving)一个特定的推荐数据集间的delay。我们缓和了这个现象,通过对推荐生成进行pipelining,每天更新数据集多次。

youtube推荐系统的实际的实现被分为三个主要部分:

  • 1)数据收集
  • 2)推荐生成
  • 3)推荐serving。

之前提到的原始数据信号存放在YouTube的log中。这些log会被处理,提取信号,按每用户为基础保存到BigTable中。当前处理数百万的用户和上百亿的行为事件,总的footprint为TB级别。

推荐的生成通过MapReduce计算完成,它会在user/video graph上进行walk through,来累积和计分推荐项。

生成的数据集的size相当小(GB),可以很容易通过webserver进行serving。完成一个推荐的请求时间几乎由网络传输时间决定。

评估

通过A/B testing进行在线评估,真实流量分成不同的组,其中一组作为control或baseline,其它组给新特性、新数据、或新UI。两组接着进行对比。为了评估推荐质量,我们使用不同metrics的组合。主要的metrics包括CTR,long CTR(只统计点击导致观看一个视频的大部分观看行为),session length,首次long watch的时间(time until first long watch),推荐覆盖率(coverage)。我们使用这些metrics来跟踪系统的效果。

The YouTube Video Recommendation System

二次规划(Quadratic Programming)问题是最基本的非线性规划问题,目标函数是二次函数,约束条件是线性等式或不等式。目前,已经出现了很多求解二次规划问题的算法,并且仍有很多学者在从事这方面的研究工作。

在机器学习中,我们知道QP可以用来解决SVM算法的最优解问题。二次规划问题的求解证明在此处暂不讨论。

二次规划的问题可以用数学公式(octave)描述:

1
2
3
4
5
6
7
8
 min 0.5 x'*H*x + x'*q
  x

    subject to

      A*x = b
      lb <= x <= ub
      A_lb <= A_in*x <= A_ub

相应的函数为:

  • Function File: [X, OBJ, INFO, LAMBDA] = qp (X0, H)
  • Function File: [X, OBJ, INFO, LAMBDA] = qp (X0, H, Q)
  • Function File: [X, OBJ, INFO, LAMBDA] = qp (X0, H, Q, A, B)
  • Function File: [X, OBJ, INFO, LAMBDA] = qp (X0, H, Q, A, B, LB, UB)
  • Function File: [X, OBJ, INFO, LAMBDA] = qp (X0, H, Q, A, B, LB, UB, A_LB, A_IN, A_UB)
  • Function File: [X, OBJ, INFO, LAMBDA] = qp (…, OPTIONS)

其中,H,q分别是目标函数化成标准形式后得到的实对称矩阵,列向量。求解的目标,x。A,b定义了线性约束。如果没有线性约束,A=[],b=[]。LB,UB分别是变量x的下界和上界,如果上界、下界没有约束,则LB=[],UB=[]。可以通过OPTIONS设置其它参数:比如:

‘MaxIter (default: 200)’

INFO表示算法的运行时信息。相应如下:

  • ‘solveiter’: 解的迭代数
  • ‘info’: 状态码。
  • info=0: 表示该问题是可行的,并且是convex问题。找到全局解。
  • info=1: 该问题是not convex的。找到局部解。
  • info=2: 该问题是not convex的,并且unbounded。
  • info=3: 迭代的最大次数
  • info=6: 该问题无解

示例:

  • $ min f(x)=2x_1^2-4x_1x_2+4x_2^2-6x_1-3x_2 $
  • $ x_1+x_2<=3 $
  • $ 4x_1+x+2<=9 $
  • $ x_1\geq0,x_2\geq0 $

编写程序:

H=[4,-4;-4,8];
Q=[-6;-3];
A=[1,1;4,1];
B=[3;9];
LB=zeros(2,1);
X0=[];
UB=[];
[X, OBJ, INFO, LAMBDA] = qp (X0, H, Q, A, B, LB, UB)

对应的输出为:

X =

   2.0000
   1.0000

OBJ = -11.000
INFO =

  scalar structure containing the fields:

    solveiter =  1
    info = 0

LAMBDA =

  -3.33333
   0.33333
   0.00000
   0.00000
   

这个标题起的有点大.

国内有许多做的还算不错的、各式各样的数据分析公司。如艾瑞,友盟等等之类的。在现在的大数据概念炒得火热的背后,其实它们的运作原理基本都差不多。

一切皆围绕数据去展开。那么数据是怎么来的呢?大致的数据来源基本上有这么几种,将分别说:

第一招:提供数据统计接口,有各种各样的API:各种编程语言的如JS/php/python/java、android/ios等等。当第三方的APP不希望单独花精力去维护一个数据分析平台时,那么很自然的,它们会选择这样的接口。这样数据自然地也被这些数据分析平台公司获取到了。那么有没有可能获取到该APP之外其它的一些信息呢?当然可以,由于android平台的安全性,这些公司一些接供的接口完全可以留下后门,当程序启动时,留下后台进程常驻(非360之类的工具也你真杀不掉)。ok,一个用户的其它移动非加密数据很有可能会被人家拿到了。ios则比较安全,8.0以上的版本基本无解。当然,还有一批越狱用户,这批用户的数据也是能拿到的。(别叫我流氓,这是行情潜规则)

第二招:还可以第三方合作。这一招也可以称为“空手套白狼”。中国的互联网环境竞争激烈,竞品太多。各种各样的公司很自然的会关注对手的情况。只要能和一家公司合作,那么很自然的,围绕对手想看这家公司的数据的问题,很自然地,可以和它相应的对手也开展这样的合作。这样,这个雪球也会越滚越大。

第三招:其它途径呢:花钱呗!付费招募。

第四招:还可以运营商(电信、移动、联通)合作。很自然地可以获取运营商根服务上的相关数据。比较某些特定用户访问某些站点的明文get数据(post无解)。

ok,数据有了。虽然可以拿到许多数据了。不过貌似不全,一家公司如果想让我做个分析研究肿么办。没关系,我们的“大数据”是吹出来的。(数据部分伪造,可以拿一些专业的互联网分析报告展开)

运营商 比例
移动 62.22%
联通 17.78%
电信 14.00%

我们接着看地域数据:

地区 比例
其它 18.00%
广东 13%
浙江 7%
北京 7%
江苏 6%
河南 6%
山东 5%
河北 5%
四川 4%
湖南 4%
湖北 3%
福建 3%
天津 3%
陕西 3%
辽宁 3%
上海 3%
山西 3%

还有操作系统的数据比例:

操作系统 比例
IOS 22%
Android 78%

ok,有了这些数据信息。那么我们就可以按比例去构建这样的大样本集。根据这样的大样本集去推演出真实的大致数据的分析即可。现在,就可以做各种各样的分析了:路径分析、个性化指标分析、转化率分析等等。

当然最重要的,是赚钱。有了一些行业内比较重量级的报告,那么就可以收费啦:一个app一个月就要10几w块钱。商业模式自然滚动起来啦。

由此看,这些数据分析公司中,抽样与统计占着相当重要的作用。

0.概述

条件随机场(CRF)是一个可用于构建概率模型(probalilistic model)的框架,可用于分词(segment)标记序列化(label sequence)数据。条件随机场提供了比隐马尔可夫模型(HMM)随机文法(stochastic grammars)更多的优点,能放宽这些模型中所存在的强独立性猜想。CRF也可以避免MEMM(最大熵马尔可夫模型)、以及其它基于有向图模型的判别式马尔可夫模型的基本限制,这两个模型的状态与一些后续的状态有标注偏差。本文基于CRF的迭代式参数估计模型,比较了与HMM和MEMM在人工合成数据上和自然语言数据集上所生成模型的性能。

1.介绍

许多科学领域中的许多问题,都涉及到分词(segment)与序列化标注(label sequence)。对于这类问题,HMM和随机文法(stochastic grammars)很好理解并被广泛用于解决这类问题的概率模型。在计算生物学上,HMM和随机文法(stochastic grammer)已经成功用于生物序列对齐,寻找序列差异以求证进化族谱,分析RNA二次结构。在计算语言学和计算科学上,HMM和随机文法(stochastic grammars)也被广泛用于文本和语音处理,包括话题分段(topic segmentation),词性标注(part-os-speech tagging),信息抽取,以及句法消歧。

HMM和随机文法(stochastic grammars)都是生成模型,为成对的观察和标注序列分配了联合概率;它们的参数训练目标是:对训练样本进行最大化联合似然。为了在观察和标注序列上定义一个联合概率,我们需要一个生成模型来枚举所有可能的观察序列,这通常需要一个表示方法来表示哪个观察值是适合任务的原子实体(词或核甘酸)。表示多种交叉特征(interacting features)、或者在观察值上的长范围依赖是不实际的。因为对于这样的模型,这种推断问题是很棘手的。

正因为存在这种困难,我们需要寻找另一种可替代的条件模型(conditional model)。给定观察序列后,该条件模型会给出所有可能标注序列的概率。因此,它不会在观察集上花费建模开销,它会在测试时确定。更进一步,标注序列的条件概率可以靠武断决定,而观察序列的非独立特征,不会强制模型来说明这些依赖的分布。对于相同的观察集,或相同观察序列的聚合属性(例如,文本布局),选中的特征可以表示成不同粒度的属性(例如:英文文本中的词和字符)。如果可能的话,标注之间的转移概率,不仅仅依赖当前观察(observations),也可以依赖过去和将来的观察。相反的,生成模型必须在观察集上做出十分严格的独立性假设(例如,给定标注的条件独立性),以便更容易处理。

最大熵马尔可夫模型(MEMM)是条件概率序列模型(conditional probabilistic sequence model),它具备上述提到的所有优点。在MEMM中,每个源状态(source state)都具有一个指数族模型(exponential model),它的输入是观察集特征,输出是下一可能状态的分布。这种指数族模型,会在在最大熵框架上通过一个合适的迭代归一化方法(iterative scaling method)进行训练。相对于在常用的分词任务中使用的HMM,之前发布的指数族模型的结果展示了MEMM会增加召回率(recall)以及两倍的准确率(precision)。

MEMM和其它的基于下一状态分类器的非生成式有限状态机模型,比如判别式马尔可夫模型(discriminative Marklov model),都有一个缺点:标注偏差问题(label bias problem):从一个给定状态(State)完成后离开的转换概率(transition),与其它状态相互对立,而非与模型中存在的所有转换概率相对对立。在概率术语中,转换分(transition score)指的是:给定当前状态以及观察序列,下一可能状态的条件概率。转换分的每个状态的归一化(per-state normalization of transition scores),暗示着一个“得分块的保护(conservation of score mass)”,与所有到达某一状态的块(mass)一致,即:必须是分散在可能的后继状态之间。一个观察(observation)可以影响哪个目的状态获得该块(mass),但不会影响总共有多少个块(mass)传递到给它。这就会引起了一个偏差,出去的转换(outgoing transition)会很少。在极端情况下,一个状态只有单个outgoing transition,会有效忽略观察集。在这种情况下,不同于HMM,Viterbi decoding不能基于分枝点后的观察向下查找分支,而基于状态转移结构的模型(models with state-transition structures),具有状态的稀疏连接链,它们不能被有效处理。这种在MEMM中的马尔可夫猜想(Markovian assumptions),以及相类似的状态条件模型,会将某一状态的决策,与将来的决策相孤立,不会匹配连续状态间的实际独立性。

这篇paper介绍了条件随机场(CRF),一种序列建模框架,它具有MEMM的所有优点,同时以一种有原则性的方式解决了标注偏差问题(label bias problem)。CRF与MEMM间的最不同之处是,给定当前状态,对于下一状态的条件概率,MEMM使用了一种每状态指数族模型(per-state exponential model);而CRF则不同,给定观察序列,CRF会给整个序列标注的联合概率生成单一指数族模型。因此,不同状态下的不同特征的权重,可以相互间进行权衡。

我们也可以将一个CRF看成是一个有限状态机模型,它具有未归一化的转移概率。然而,不同于其它一些加权有限状态机方法(LeCun et al.,1998),CRF分配了一个良好定义的(well-defined)在可能标注上的概率分布,通过最大似然或MAP估计进行训练。更进一步,loss函数是convex的,保证收敛到全局最优。CRF也很容易概括成上下文无关的随机文法(stochastic context-free grammars)的相似物,对于RNA的二等结构预测,以及nlp等问题很有用。

我们提出了该模型,描述两个训练过程,以及收敛的证明结构。我们也会给出在句法结构数据上的实验数据,来展示CRF,解决标注偏差问题(balel bias problem)的经典版本,并会比较CRF与HMM/MEMM间的性能。最后,我们会在基于词性标注任务上,证明这些结果,以及宣称的这些优点。

2.Label Bias Problem

经典的概率自动机(Pax, 1971),判别式Markov模型(BOttou,1991),最大熵标注器(Ratnaparkhi, 1996),以及MEMM,以及非概率序列标注和分词模型(Punyakanok & Roth, 2001)都是标注偏差(Label bias)问题的潜在受害者。

例如,图1所展示了一个简单的有限状态机模型,它设计的目的是,区分两个词: “rib”和”rob”。假设,观察到的序列是:r i b。在第一个时间阶段,r同时满足初始状态的两个转换,因此两种转换间的概率块分布相同。接下来,我们观察到:i。状态1和状态4, 两者都只有一个outgoing transition。状态1经常在训练集中观察到该观察(observation),状态4则在该观察(observation)中从未见过;与状态1相类似,状态4只能将所有块传递到单个outgoing transition,因为它不能生成该观察(observation),只能基于它。这样,带有单个outgoing transition可以有效的忽略它们的观察。更通用的说法,具有低熵的下一状态分布,将会更少地注意到观察(observations)。回到该例,上面的路径,以及下面的路径,具有相同的可能性和观察序列的依赖性。如果两个词,在训练集中很常见,从起始状态出发的转换,会更偏爱与它相关的转移(概率大),该词的状态序列将总是获胜。这种行为可以在第5部分进行演示。

Leon Bottou(1991)讨论了label bias问题的两种解决办法。其中一种是,改变该模型的状态转换结构。在以上的示例中,我们可以压缩(collapse)状态1和状态4, 延迟它们的分支,直到我们得到一个判别式观察(observation)。这种操作是决策树determinization (Mohri,1997)的一个特例。但加权有限状态机并不总是可能的,即使可能,它也会导致组合爆炸。另一种解法是,从一个完全连接的模型出发,让训练过程来指出一个好的结构。但它将导致先验结构知识的使用,在信息抽取任务中这被证明很有用(Freitag & McCallum, 2000)

想得到合适的解,需要这样的模型:比起其它依赖于相应观察的转换,它可以通过让一些转换(transition)进行更强的“投票”,来对整个状态序列作出解释。这暗示了,分值块(score mass)将不会被保留,而独自的转换可以“放大”或”抑制”它们的接受块(mass)。在上面的例子中,从起始状态的转换,在路径分上会有很弱的影响,而从状态1和状态4上的转换,将会有更强的影响,取决于实际的观察,会进行放大或衰减,对Vierbi路径的选择,会有更高的贡献。

在相关的工作部分,我们讨论了其它启发式模型,它们能为状态序列做出全局解释。充分研究发现,CRF是可以用来在纯概率设置中做到这一点,并且能保证全局最大似然收敛的唯一模型。

3.CRF

X是一个随机变量,用来表示要标注的序列数据,Y表示在相应标签序列上的一个随机变量。Y中的所有成员Yi,假设都在一个有限标注y范围内。例如,X的范围可以是所有自然语言句子,Y的范围可以是这些句子的词性标注(pos taggings),而y则是可能的词性集合(pos tags set)。随机变量X和Y是联合分布的,但在一个判别式框架上,我们会根据成对的观察和标注序列构建一个条件模型$ p(Y|X) $,而不会显式建模p(X).

定义:G = (V,E)是一个图, $ Y=(Y_v)_{v\in{V}} $, 其中Y通过G的顶点进行索引。接着(X,Y)是一个条件随机场(conditional random field),当基于条件X,假设随机变量Yv服从该图的马尔可夫属性:

\[P(Y_v|X, Y_w, w\neq{v}) = p(Y_v|X,Y_w,w\sim{v})\]

其中,w~v,意味着w和v在G中是邻居。

这样,CRF就是这样一个随机场,它完全基于条件观察X。整篇paper中,我们严肃地假设,图G是确定不变的。在最简单和最重要的序列建模示例中,G是一个简单的链(chain)或线(line):G = (V = {1,2,3,…,m}, E = {(i,i+1)})。其中,X也具有一个天然的图结构;但是总的来说,假设X和Y具有相同的图结构这一点不是必要的,X可以有任意的图结构。然后,在本篇paper中,我们最关注的是:序列X = (X1,X2,…Xn),以及Y=(Y1,Y2,…,Yn).

如果图G=(V,E),Y是一棵树(树上的一条链就是一个最简单示例),它的成员是边和顶点。因此,通过随机场(Hammersley & Clifford, 1971)的基本理论,对于给定X,在标注序列Y上的联合分布,具有以下的形式:

\(p_\theta(y|x) \subset exp(\sum_{e\in{E,k}}\lambda_{k}f_{k}(e,y|_{e},x)+\sum_{v\in{V,k}}\mu_{k}g_{k}(v,y|_{v},x))\) … (1)

其中,x是数据序列,y是标注序列,$ y|_{S} $是y的成员集合,与S子图中的顶点有关。

我们假设特征fk和gk是给定的,并且是固定不变的。例如,一个Boolean型的顶点特征gk,如果词Xi是大写的,则为true,而Yi的标注会是一个“合适的名词”。

参数估计问题,是从训练数据$ D=\left((x^{(i)},y^{(i)})\right)_{i=1}^{N} $中,根据经验分布p(x,y), 决定参数θ = (λ1, λ2, … ; µ1, µ2, . . .) ,在第4部分,我们将描述一种迭代归一化算法,来最大化log-likelihood目标函数O(θ):

\[O(\theta)=\sum_{i=1}^{N}logp_\theta(y^{(i)}|x^{(i)}) \subset \sum_{x,y}p(x,y)logp_\theta(y|x)\]

作为特例,我们可以构造一个类HMM的CRF,通过为每个状态对(state pair)(y’,y)定义一个特征,对于为每个状态-观察对(state-observation pair)(y,x),满足:

\[f_{y',y}(<u,v>,y|_{<u,v>},x)=\sigma(y_u,y')\sigma(y_v,y)\] \[g_{y,x}(v,y|_v,x)=\sigma(y_v,y)\sigma(x_v,x)\]

相应的参数$ \lambda_{y’,y} $和$ \mu_{y’,y} $与常见的HMM参数$ p(y’|y) $和$ p(x|y) $扮演着相似的角色。Boltzmann链模型也具有一个相类似的形式,但它使用单个归一化常数来生成(yield)一个联合分布;而CRF则使用依赖观察(observation-dependent)的归一化分布Z(x)来作为条件分布。

尽管它包含了类HMM的模型,条件随机场的类更具表现力,因为它允许在观察序列上存在独有的依赖。另外,特征不必完整指定一个状态(state)或观察(observation),因此,模型也可以从较少的训练数据中被估计。另一个更吸引人的特性是,loss function是凸的(convexity);确实,CRF会共享所有通用最大熵模型所具有的凸特性。

另外,我们假设:Y的依赖是基于条件X的,形成一条链。为了简化表示,我们添加start状态和stop状态:Y0=start和Yn+1=stop. 接着,我们将使用如图2所示的图结构。对于一个链结构来说,一个标注序列的条件概率,可以被表示成矩阵形式,这对于描述第4部分的参数估计和推断(parameter estimation and inference)算法来说很有用,假设$ p_\theta(Y|X) $是一个由(1)给定的CRF。对于在观察序列x上的每个位置i,我们定义了 $ |y|*|y| $ 矩阵的随机变量:$ M_{i}(x)=M_i(y’,y|x) $

\[M_i(y',y|x)=exp(\Lambda_{i}(y',y|x))\] \[\Lambda_i(y',y|x)=\sum_{k}\lambda_{k}f_{k}(e_i, Y|_{e_i}=(y',y),x)+\sum_{k}\mu_{k}g_{k}(v_{i},Y|_{v_i}=y,x)\]

其中ei是标注(Yi-1,Yi)的边(edge),而vi是标注Yi的顶点。对比于生成模型,像CRF这样的条件模型,不需要枚举所有可能的观察序列x,因此可以从给定的训练或测试观察序列x和参数向量θ上,直接计算出这些矩阵。接着,归一化(配分函数:partition function)$ Z_\theta(x) $是(start,stop)条目上所有这些矩阵的乘积:

\[Z_\theta(x)=(M_1(x)M_2(x)...M_{n+1}(x))_{start,stop}\]

使用该符号,一个标注序列y的条件概率可以写成这样:

\[p_{\theta}(y|x)=\frac{\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)}{(\prod_{i=1}^{n+1}M_i(x))_{start,stop}}\]

其中,y0=start,yn+1=stop.

4.CRF的参数估计

我们现在描述两个迭代归一化算法来寻找参数向量θ,使得它能对训练数据求得最大化条件似然。两种算法都基于改进的迭代归一化算法(IIS)。(Della Pietra et al. (1997));证明技术可以基于辅助函数,可以被扩展成展示CRF算法收敛性。

迭代归一化算法(Iterative scaling algorithms),会合理选择$ \delta\lambda_k $和$ \delta\mu_k $,来更新权重:

\[\lambda_k \leftarrow \lambda_k+\delta\lambda_k\] \[\mu_k \leftarrow \mu_k+\delta\mu_k\]

特殊的,迭代归一化算法(IIS)会为一个边特征fk来更新$ \delta\lambda_k $,来求解:

\[(\hat{E})[f_k]=\sum_{x,y}\hat{p}(x,y)\sum_{i=1}^{n+1}f_k(e_i,y|_{e_i},x)=\sum_{x,y}\hat{p}(x)p(y|x)\sum_{i=1}^{n+1}f_k(e_i,y|_{e_i},x)e^{\delta\lambda_kT(x,y)}\]

而T(x,y)是总特征数:

\[T(x,y)=\sum_{i,k}f_k(e_i,y|_{e_i},x)+\sum_{i,k}g_k(v_i,y|_{v_i},x)\]

该方程同样会为顶点特征更新$ \delta\mu_k $,具有相同的形式。

然而,对方程右手边有效计算它们的指数和(exponential sums)是有问题的,因为T(x,y)是一个关于(x,y)的全局属性,动态规划(dynamic programming)会使用潜在不同的T,在序列上求和。为了处理该算法,我们的第一个算法会使用一个”松弛特征(slack feature)”。第二个算法T,会跟踪部分T。

对于算法S,我们定义了slack feature:

\[s(x,y)=S-\sum_{i}\sum_{k}f_k(e_i,y|_{e_i},x)-\sum_{i}\sum_{k}g_k(v_i,y|_{v_i},x)\]

其中,S是一个常数,以便$ s(x^{(i)},y) $,对于在训练集中所有的y,以及所有的观察向量x(i),这样使得T(x,y)=S. 特征s是“全局”的,它不会对应于任何特定的边或顶点。

对于每个索引i=0,…,n+1,我们现在定义了前进向量(forward vector)$ \alpha_i(x) $,它的基本特例为:

\[\alpha_\theta(y|x)= \begin{cases}1&(y = start)\\0&(otherwise)\end{cases}\]

以及递归式:

\[\alpha_i(x)=\alpha_{i-1}(x)M_i(x)\]

相似的,后退向量$ \beta_i(x) $定义如下:

\[\beta_\theta(y|x)=\begin{cases}1&(y=stop)\\0&(otherwise)\end{cases}\]

其中:

\[\beta_i(x)^T=M_{i+1}(x)\beta_{i+1}(x)\]

有了这样的定义,更新方程为:

\[\delta\lambda_k=\frac{1}{S}log\frac{\hat{E}f_k}{Ef_k}\] \[\delta\mu_k=\frac{1}{S}log\frac{\hat{E}g_{k}}{Eg_k}\]

其中,

\[Ef_k=\sum_{x}\hat{p}(x)\sum_{i=1}^{n+1}\sum_{y',y}f_k(e_i,y|_{e_i}=(y',y),x)*\frac{\alpha_{i-1}(y'|x)M_i(y',y|x)\beta_i(y|x)}{Z_\theta(x)}\] \[Eg_k=\sum_{x}\hat{p}(x)\sum_{i=1}^{n}\sum_{y}g_k(v_i,y|_{v_i}=y,x)*\frac{\alpha_i(y|x)\beta_i(y|x)}{Z_\theta(x)}\]

在上面公式中,涉及到前进和后退向量的因子,与标准的马尔可夫模型(HMM),具有相同的含义。例如:

\[p_\theta(Y_i=y|x)=\frac{\alpha_i(y|x)\beta_i(y|x)}{Z_\theta(x)}\]

对于给定的观察序列x, 上面的p即是标注Yi=y的边际概率。该算法与Darroch and Ratcliff (1972)相近,其中MART算法用于图片重构上。

算法S中的常数S可以相当大,因为实际上,它是与最长训练观察序列的长度是成比例的。作为结果,算法可以收敛很慢,在每次迭代时,朝着最大化的方向前进一小步。如果观察$ x^{(i)} $以及激活特征的数目十分不同,通过为各个观察序列独自跟综特征总数,可以获取一个快速收敛算法。

定义: $ T(x)=max_yT(x,y) $。算法T累积特征期望到计数器中,由T(x)进行索引。更特别的是,给定T(x)=t,我们使用已引入的前向-后向递归(forward-backward recurrences)来计算特征fk日期望ak,t,以及特征gk的期望bk,t。接着,我们的参数更新是:

\[\delta\lambda_k=log\beta_k\] \[\delta\mu_k=log\gamma_k\]

其中,βk和γk是由以下多项式方程得到的唯一的正定根:

\(\sum_{i=0}^{T_{max}}a_{k,t}\beta_k^t=\hat{E}f_k,\sum_{i=0}^{T_{max}}b_{k,t}\gamma_{k}^{t}=\hat{E}g_k\) … (2)

它可以很容易由牛顿法进行计算。

算法S和算法T的单个迭代,与HMM的Baum-Welch算法相比,具有基本相同的时间和空间复杂度。为了证明我们算法的收敛性,我们派生了一个辅助函数,来限制似然的变化;这个方法由Della Pietra et al. (1997)提出。完整的证明很详细;然而,这里我们给出了一个点子来如何派生辅助函数。为了简化解释,我们假设,只有边特征fk带有参数λk。

给定两个特征设置:θ=(λ1,λ2, . . .) ,θ’=(λ1+δλ1, λ2+δλ2, . . .),我们使用一个辅助函数(auxiliary function)A(θ’,θ),来限定目标函数的变化:

\[O(\theta')-O(\theta)=\sum_{x,y}\hat{p}(x,y)log\frac{p_{\theta'}(y|x)}{p_{\theta}(y|x)}\] \[=(\theta'-\theta)\hat{E}f-\sum_{x}\hat{p}(x)log\frac{Z_{\theta'}(x)}{Z_\theta(x)}\] \[\geq(\theta'-\theta)\hat{E}f-\sum_{x}\hat{p}(x)\frac{Z_{\theta'}(x)}{Z_\theta(x)}\] \[=\delta\lambda\hat{E}f-\sum_{x}\hat{p}(x)\sum_{y}p_\theta(y|x)e^{\delta\lambdaf(x,y)}\] \[\geq\delta\lambda\hat{E}f-\sum_{x,y,k}\hat{p}(x)p_\theta(y|x)\farc{f_k(x,y)}{T(x)}e^{\delta\lambda_kT(x)}\] \[=A(\theta',\theta)\]

其中,不等式遵循log和exp的凸特征(convexity)。按$ \delta\lambda_k $对A进行微分,以及设置结果为0,会产生方程(2).

5.实验

我们首先使用人造数据讨论了两组试验,用来强调CRF和MEMM间的不同。第一组试验,是第二部分讨论的标注偏差问题的直接验证。第二组实验,我们会使用HMM模型来生成人造数据,它们中的每一个都是一阶和二阶的混合模型。接着训练竞争型的一阶模型,并在测试集上进行比较。随着数据变成二阶,训练模型的测试误差率(test error rates)会上升。该试验通过一阶马尔可夫模型符合常用的建模实践(近似复杂局部和长范围依赖),正如自然数据中会发生的那样。我们的结果明显指出,即使当模型以相同的方式进行参数化,CRF也比MEMM或HMM更健壮,并能解决标注偏差问题(会影响MEMM的性能)。为了避免不同影响的混淆,MEMM和CRF在实验中不会使用观察集上的重复特征。最终,在词性标注试验中,我们确认了CRF优于MEMM。我们也展示了CRF和MEMM的重复特征,它们比HMM性能更好。

5.1 建模偏注偏差

从一个简单的HMM中生成的数据,它可以编码成一个噪声版本的有限状态网络,如图1所示。每个状态会触发相应的符号,对应概率29/32,其余符号的概率为1/32. 我们同时训练了MEMM和CRF,使用与HMM生成数据相似的拓朴。观察特征可以简化成观察符号的id。在运行了2000个训练和500个测试样本中,迭代归一化算法的收敛,CRF的error只有4.6%,而MEMM的error则为42%,这说明MEMM在判别分支时失败了。

5.2 建模混合阶的源数据

对于这些结果,我们使用五种标注:a-e($ |y|=5 $),以及26个观察值,A-Z($ |X|=26 $);然而,对于y和X的size的范围取值,结果本质上是相同的。我们从一个混合阶的HMM生成数据,它具有状态转移概率:

\[p_\alpha(y_{i}|y_{i-1},y_{i-2})=\alpha p_2(y_i|y_{i-1},y_{i-2})+(1-\alpha)p_1(y_i|y_{i-1})\]

相似的,触发概率(emission probabilities)为:

\[p_\alpha(x_{i}|y_{i},x_{i-1})=\alpha p_2(x_i|y_{i},x_{i-1})+(1-\alpha)p_1(x_i|y_i})\]

这样,对于α = 0, 我们具有一个标准的一阶HMM。为了限制对于产生的模型的Bayes error rate的size,条件概率表Pα被限制为稀疏的。特别的,对于每个y,y’,$ p_\alpha(\cdot|y,y’) $具有至多两个非零条目。对于每个y,x’,$ p_\alpha(\cdot|y,x’) $可以至多三个非零条目。对于每个随机生成的模型,会生成1000个长度为25序列的样本,用于训练和测试。

在每个随机生成的训练集上,CRF会使用算法S进行训练(注意,因为序列长度,活跃特征数是常数,算法S和算法T是相同的)。该算法收敛相当慢,通常会在500次模型迭代后开始稳定。在我们的500 MHz Pentium PC上,每次迭代会花费0.2s。在相同的数据上使用MEMM进行迭代归一化训练,它不会需要前后向计算,因而更有效。MEMM训练收敛更快,在100次迭代在右就开始稳定。对于每个模型,Viterbi算法用于标注一个测试集;当使用forward-backward decoding来最小化每个符号的错误率时,试验结果不会有巨大变化。

运行结果如图3所示。每个plot都会比较了模型的两个类,每个point表示单个测试集上错误率。随着α的增加,错误率会总体增加,一阶模型会对二阶数据拟合失败。该图比较了模型参数$ \mu_y, \lambda_{y’,y}, \lambda_{y’,y,x} $;以及模型参数 $ \mu_y, \lambda_{y’,y}, \mu_{y,x} $本质上是相同的。如第一图所示,CRF总体上比MEMM更好,通常有10%-20%相对误差。(对于非常小的错误率的点,α < 0.01, 其中MEMM比CRF表现更好,这归因于CRF的训练迭代次数不够)

5.3 词性标注试验

为了证实我们的人造数据结果,我们也在Penn treebank词性标注数据集上比较了HMM,MEMM,以及CRF。其中,在结定的输入句子上的每个词,必须标注成45种标注之一。

我们在该自然语言数据集上运行了两个实验。第一个,我们在人造数据实验中训练了一阶HMM,MEMM,CRF模型,在训练集中为每个标注-词对(tag-word pair)引入了参数$ \mu_{y,x} $,以及为每个标注-标注对(tag-tag pair)引入了$ \lambda_{y’,y} $。结果与人造数据上观察到的相一致:HMM比MEMM效果更好,因为标注偏差问题,而CRF则比HMM表现更好。训练的错误率,使用了如图5.3所示的50%-50%的训练-测试集划分。结果与其它数据划分相类似。对于不在词汇表的词(oov:out-of-vocabulary)的错误率,它们不会在训练集中观察到,会独立报告结果。

在第二个实验中,通过添加少量拼字特征(orthographic features),我们充分利用了条件模型的威力:一个拼写是否从数字或大写字母开始,是否包含连字号,是否以如下的后缀结尾:-ing,-ogy,-ed, -s, -ly, -ion, -tion, -ity, -ies. 正如我们期望的那样,这里我们发现,MEMM和CRF极大地受益于这些特征的使用,整体错误率减小到了25%左右,oov错误率减小到50%左右。

6.CRF的更进一步

CRF的许多方面对于将来学习很有吸引力。这一部分我们提到两点。

条件随机场可以通过AdaBoost算法使用指数loss目标函数进行训练(Freund & Schapire, 1997). 通常的,boosting常用于分类问题,会有一个小的、固定数目的分类;boosting应用于序列化标注,可以将每个label看成是独立的分类问题(Abney et al., 1999)。然而,可以使用并行更新算法(Collins et al. 2000)来最小化单序列的指数loss。这需要一个forward-backward算法来有效计算特定的特征期望,沿着算法T的线,期望每个特征需要一个独立集合的前向和后向累加器。

CRF的另一个吸引人的特征是,你可以为它们实现有效地特征选择,以及特征引入算法。也就是说,不必指定要使用哪个(X,Y)特征,我们可以从特征生成规则开始,并在数据上自动评估生成特征的好处。特别地,特征引入算法,可以用来拟合条件随机场的动态规划技术。

致谢

对于标注偏差问题,感谢:Yoshua Bengio, Leon Bottou, Michael Collins,Yann LeCun,

对于相关工作部分,感谢:Andrew Ng、Sebastian。

参考

http://repository.upenn.edu/cgi/viewcontent.cgi?article=1162&context=cis_papers