二次规划(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服从该图的马尔可夫属性:

其中,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上的联合分布,具有以下的形式:

… (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(θ):

作为特例,我们可以构造一个类HMM的CRF,通过为每个状态对(state pair)(y’,y)定义一个特征,对于为每个状态-观察对(state-observation pair)(y,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) $

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

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

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

4.CRF的参数估计

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

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

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

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

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

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

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

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

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

以及递归式:

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

其中:

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

其中,

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

对于给定的观察序列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。接着,我们的参数更新是:

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

… (2)

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

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

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

其中,不等式遵循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生成数据,它具有状态转移概率:

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

这样,对于α = 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

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

一、介绍

YouTube在2005成立,并很快成为用户发现和分享视频的流行网站。在Youtube视频库中有4500w视频,每分钟就有大量的视频上传。该巨大的视频库信息潜在包含了许多用户的视频兴趣。大量视频存在的缺点是,探索和发现新的、吸引人的视频是一项极具挑战的任务。推荐的标准方法已经被广泛应用于文本领域,比如:新闻组,网页新闻,但在视频领域并不简单。主要难点是,尽管通过计算机视觉技术可以打上少量可靠标签,但目前不存在任何比较好的机制对大部分视频内容打标签。更难的是,在YouTube视频上存在的标签相当少;它们只捕获了少量的内容信息

为非文本内容提供有价值的信息,已经在一些上下文上做了探索。最接近的是Netflix challenge,它的系统会基于之前的评分推荐DVD给订阅者。Netflix有10w的DVD,Netflix的用户在这些视频上提供了大量显式的评分。相反的,在我们的任务上,视频的数目更大,评分很稀疏。我们解决该任务的方法是,利用大量用户在视频累积的观看(views)。通过学习观看模式,来创建一种有效的视频推荐系统,它不依赖于底层视频的分析。为了创建一个个性化的视频推荐页面,它不再仅仅只展示最新或最流行的视频,也会展示根据用户行为推荐出的视频。

在该节中,我们引入了一种主要数据源:co-view statistics。在第2节,我们介绍了吸附(adsorption)算法,并描述了许多相关研究。当我们具有一些标记过的对象,以及一个丰富的关于标记和未标记对象的图结构时,吸附(adsorption)算法会是一种非常通用的分类和学习框架。该算法在数学上非常健壮,它具有三种不同但等价的解释,在应用数学和机器学习领域有多种形式。在第3节,我们介绍了所使用的数据。该系统的评估本身就是一项挑战;每个系统在部署到线上生产环境前必须彻底审查。3.1节探索了在部署前使用历史数据来解释算法效果。实验结果在第4节,第5节则是结论。

1.1 视频的Co-View Graph

Youtube有大量用户们会观看多个视频。一个基础统计是,视频共同观看(co-view)数。在最简单的形式,对于任意的视频对(video pairs),co-view数据会给出那些观看了这两个视频的用户数。该统计会在所有视频上做计算,有许多方法将它们编码成一个图(graph)。在图1中,我们展示了“video-video co-view graph”,视频(相同用户最常看的视频)间会有一个连接。在图2中,我们展示了user-view graph,从中可以看到涉及到的co-views。

图1: video-video co-view graph. 每个视频是该图中的一个节点(vertex),它会与其它视频相连接,称为共同观看(co-viewed)。通常,只有与最少数目的观看量相连接才会被实例化

图2: User-Video Graph. 另一种表示co-view信息的方法是隐式地通过user-video二分图进行表示。co-view的数目通过检查在两个视频之间长度为2的路径来计算。

co-view信息提供了视频推荐的一个基础。一些基于item-based CF的简单系统,就是基于此构建。假设用户U观看了两个视频:J和K。从我们的co-view统计上看,我们可以知道,许多观看了视频J的其他用户也会观看视频L,M,N。相似的,许多观看了视频K的其他用户也观看了视频N, O, P, Q。因此,推荐给U的视频,会基于它的观看J和K,简单通过两个co-view的联集(union)得到:L, M, N, O, P, Q。为了对该推荐进行ranking,我们会考虑视频的观看数(它可以间接描述流行程度),每个视频的co-view数,或者推荐给U的每个视频的次数(注意:视频N会推荐两次),或结合其它的heuristics。

注意,还存在其它版本的co-view统计和图(graphs)可用于上述的情况。通过将co-view限制在只在相同web session中发生可以得到更强的相似度。这种方法可能会有用,人们会认为一个用户在一段时间内在相同的主题上可能会看多个视频(例如,观看多个关于如何以烟灰墨风格进行绘画的指导视频)。其它潜在的co-view变种包括:通过使用有向边来编码顺序信息(ordering information)。这些变种的缺点是,通常会为每个video/user产生一个更小的数据。如果给定大量的视频来计算co-view统计,我们尝试使用尽可能更宽泛的co-view定义。

2.吸附算法(ADSORPTION ALGORITHM)

我们将该算法族称为“吸附(adsorption)”的源自下面的这个问题:假设我们希望将图中的一个节点(node)根据其它节点上的标签(labels)作分类,应该如何去实现?最简单的答案是,在对应图上引入一个metric,通过采用最近邻的labels来分类label。我们可以选择许多种metrics(例如:最短路径、交换时间、电阻等),但对于大图(large graphs)来说,大多数的计算开销都很大。另外,像最短路径这种简单的方法在推荐系统的上下文中存在一定的不好(undesirable)的属性。基于user-video view graph,如果我们给用户u推荐一个他没有观看过的、并且在图中距离最近的视频v,那么我们会结束推荐这样的一个节点:它只通过高的度(high-degree)的节点到达(例如,如果用户u1和u2同时观看了一个流行的视频,尽管他们没有共同兴趣,我们将终止推荐由u2观看过的视频给u1,因为u1到其它视频的路径长度为3,这对于任意u1未观看过的视频都是最短可能的距离(distance))。更复杂的方法,比如往返距离(commute distance)可以避免该问题,但需要更昂贵的计算开销;再者,这些方法不会导致算法准许增量更新,另一个因素对于大型推荐系统很重要。

推荐视频通常与一个用户的观看过的视频构成co-view关系,然而可以通过发现带标签的节点进行抽取,它们离用户节点具有多个短路径(short paths)。这样做时,必须注意不要离开该节点太远,因为,如果连接一个用户到一个视频的路径很长,那么很大程度上会发生兴趣和相关度的漂移。

对于我们的推荐系统的迫切之处是,满足以下条件,那么一个视频v就与一个用户相关

  • (1) u和v在它们之间具有一个短路径
  • (2) u和v在它们之间具有多个路径
  • (3) u和v的路径应避免高度节点(high-degree nodes)的存在

2.1 基于平均的吸附算法(Adsorption via Averaging)

该算法具有以下的思想。在一个总的图中,一些节点具有标签(labels),这些带有标签(labels)的节点,会将标签(labels)传播给他们的邻居,接着,这些邻居会继续将标签(labels)传给他们的邻居,以此类推,直接所有节点都接收到他们的标签(labels)。这样,每个节点具有两个角色,传播标签(forwarding labels)和接收标签(collecting labels)。在“完全信息(full-information)”的模型中,我们假设每个节点会跟踪它们接受到的所有标签的历史————多久会接收到,在第几轮接收到,等等。这会允许每个节点做出一个知情选择:哪些标签希望保留(retain)。该算法的重要详情是,选择如何来维持一个概要:即保留该通知的基本部分,也能保障标签分配(label assignments)的一个稳定(或收敛)集合。

正式描述如下。我们给定一个图:$ G = (V,E,w) $,其中V表示顶点(节点)集合,E表示边的集合,$w: E \rightarrow R $表示在边上的一个非负权重。假设L表示标签集合,并假设在子集$ V_L \subseteq V $中,每个节点v携带着一个在标签集合上的概率分布$ L_v $。我们通常将$ V_L $看成是带标签节点的集合。为了更好地阐述,我们引入了一个预处理step,其中对于每个顶点$ v \in V_L $,我们创建了一个“shadow”顶点($ \hat{v} $),它具有一个准确的外邻居(out-neighbor)v,通过一条权重为1的边$ (\hat{v}, v) $进行相连;更进一步,对于每个$ v \in V_L $,我们会重新分配(re-locate)从v到$\hat{v}$的权签分布$ L_v $,留下v不带label分布。给定$ \hat{V} $表示shadow顶点的集合,$ \hat{V} = \lbrace \hat{v} | v \in V_L \rbrace $。从现在开始,我们假设在算法的开始处,只有在$ \hat{V} $中的顶点具有非空的标签分布。

上述代码注释如下:

  • (1) 在求和操作中,u和$ V \cup \hat{V} $中的所有顶点各不相同,它具有一个非空的label分布$L_u$。
  • (2) 在该算法中,在一轮迭代中,如果没有任何节点的label分布发生变化,那就发生了收敛。实际上,我们会引入一个小的阈值,以便分布的变化幅度过小时就认为是收敛
  • (3) 根据收敛,对于每个节点 $ v \in V \cup \hat{V} $,都会带着一个label分布,提供了从v到节点$ u \in V_L $的路径。
  • (4) 在边$ (\hat{v}, v) $上每个节点$v \in V_L$的单位权重的选择是完全武断的,可以通过其它方法进行替换;这会是一个非常有意思的特性。
  • (5) 机智的读者可能注意到,我们没有在每轮迭代中更新(update)label分布;而是,我们会从头到尾完全计算,基于在近邻上发布的分布。这说明整个算法是平等的,算法的无内存属性可以使得它更易于数学分析。
  • (6) Adsorption算法是一个非常有效的迭代计算算法(类似于PageRank),其中,在每次迭代中,一个label分布会沿着每个边进行传递。这在MapReduce模型中很方便进行并行计算。

2.1.1 相关工作

我们的目标是,维持一个关于label的总览,这些labels可以从一个顶点可达(reachable),让我们记住,归一化阶段遵循近邻label分布的权重和计算对我们的算法来说是很重要的。在完成该step后,从多个近邻(or高权重近邻)处接收的标签(labels)趋向于具有更高的块(mass),因而该step将adsorption算法看成是一个传统ML分类器。实际上,该算法是一个关于标签传播算法的修改版本【 Zhu and Ghahrahmani】,Zhu的paper是第一篇使用图模型来设计半监督学习解决该问题。Zhu and Ghahrahmani也提到:它们的算法与【Szummer and Jaakkola】的随机游走算法不同;你可以看到,有一种非常不同的随机游走算法,它与adsorption算法完全一致。由Azran提出。

从一个科学的角度看,“重复平均(repeated averaging)”算法在数学的微分方程中具有一段很长的历史,特别是关于求边界值问题时。该邻域的一个原型问题是,给定边界温度,估计叠在2d网格上一个层流表面( laminar surface)上多个点的热度(heat);最常见的算法是,对该网格近邻的值做重复平均,直到温度收敛。实际上,该算法的天然泛化性()是可以通过一个专有图(arbitrary graph)来替代网格,其中有标签的节点与边界点对等。然而,总体上,一个图并不是一个连续结构,你必须处理多个由此引起的异常点。

2.2 基于随机游走的Adsorption算法

adsorption算法的无内存属性,可以产生一个紧密相关的解释。让我们从最后一轮“松开(unwind)”算法的执行,向后回退跟踪。

对于一个顶点$ v \in V $,$ N_v $表示在v的邻近集合上的概率分布,$ N_v(u) = w(u,v) / (\sum_{u} w(u,v)) $,也就是说,u的概率与边(u, v)的权重是成比例的。一个顶点v的标签分布,可以简单成看是一个关于它的近邻标签分布的凸组合(convex combination),也就是说,$ L_v = \sum_{u} N_v(u) L_u $;因此,如果我们根据概率$ N_v $随机选择v的一个内近邻(in-neighbor)u,根据分布$ L_u $抽样一个label,接着对于每个$ l \in L $的label, $ L_v(l) $与$ Exp_u[L_u(l)]$精确等价,其中指数(expectation)来自于根据$N_v$选择一个近邻u给出。将此扩展到距离为2的近邻上,很容易看到,对于每个标签$l \in L$,$ L_v(l)=Exp_{w} Exp_{u} [L_w(l)] $,其中,根据$N_v$选中v的一个内近邻u,根据$N_u$选中u的一个内近邻$w$。向外扩展得到:

注意,$ N_v(u) $是在从v开始的随机游走并根据$N_v$选择一个近邻中的1个step内从v到达u的概率,相类似的,$N_u(w)$则是根据$N_u$从w到u选中一个近邻的概率。注意,这里Markov属性(无内存)的使用很重要,它基于随机游走,可以到达u,在选择w时使用的唯一信息是$N_u$,它只依赖于u,而不会依赖于随机游走的初始化。

最后,注意,如果随机游走到达了一个shadow顶点$\hat{z}$,其中$z \in V_L $,接着,不存在z的入边(in-edge),因此随机游走会停止。这样,在$ \hat{V}$上的顶点是 Markov chain的“吸附状态(absorbing states)”,由随机游走定义。吸附算法(adsorption algorithm)等价于下面的变种,在图G的反向(reverse)、从$\hat{V}$到V的边进行随机游走。

在下面的表述中,算法从起点v进行随机游走,当到达一个吸附状态时为它输出一个label分布$L_v$。这样,每个节点的标签分布是一个随机变量,它们的期望(expectation)会为该顶点生成最终的label分布。为了为所有顶点获取label分布,该过程需要为每个顶点重复许多次,接着计算平均分布。很明显,该算法是一种非常低效的算法;因而,实际上,我们开发了该算法的在2.2节点的平均吸附算法的另一等价形式:它会是一个非常有效的实际,尤其适用于并行计算模型。

这里pick-neighbor(v, E, w) 会返回一个节点u,以便$ (u,v) \in E$,具有概率 $ w(u,v) / (\sum_u w(u,v))$

对比算法Adsorption-RW,在图上进行随机游走的固定分布(比如PageRank)的使用具有启发意义。像PageRank的情况,会考虑使用一个固定的Markov随机游走,因而给定了固定概率分布,对于图的每个节点,该游走的概率会访问这些节点。缺少任意的吸附节点(假设该游走是遍历的),在其上对该节点的初始化选择,随机游走的开始与对于在长期上到达任意特定节点的概率确定是完全无关的。因此,这些方法不会允许我们来衡量节点间的相互影响。相反的,在我们的情况下,带标签的节点处于随机游走的吸附状态;因此,该游走的起始点会决定着我们在任意吸附状态停止该游走的概率。这暗示着,我们可以使用这些概率作为节点间相互影响的衡量。

2.3 通过线性系统的Adsorption

该算法暴露的第三个角度,通过观看到:平均算法会自动隐含:在每每个节点v,标签集L的最终分布$ L_v $是一个在$ L_u $的凸组合,其中$ u \in V_L $ (传递给shadow $\hat{u} $)。

实际上,我们可以尝试去描述,将图中每个节点,根据它们的相似度(邻近程度、近邻重合数等),忽略掉是否有标签,作为一个关于其它节点的凸组合,这是一个非常见的问题,有许多潜在应用。实际上,这样做可以给出关于该图顶点到L1的一个embedding(因为,每个凸组合可以写看是一个unit L1 norm的n维向量,其中$ n = | V | $);这在计算机科学上的研究是一个很热门的主题。由adsorption产生的embeddings不会捕获最短距离,但具有非常相关和有用的属性。embeddings的一个有用之外是,它们具有“连续(continuity)”的天然特性: 在L1上任意节点的图片(images)都是一个关于其它近邻图片的凸组合。据我们所知,这样的embeddings在文献中没有研究,对于特定的应用会非常有用。

通过将吸附算法转换成一个线性等式的系统,你可以更精准获得这样的embedding。进一步,线性等式系统具有一个唯一解,如果底层图是连接的。这产生了在图中进行标签传播问题的第三个算法。一旦我们将每个顶点表示成关于其于顶点的一个凸组合,我们可以获得任意节点的一个label分布,通过采用一个合适的在带label顶点上label分布的凸组合。

该线性系统的视角提供了另一个标签传播的天然算法(natural algorithmic)。另外,它提供了非常自然的思想来获取该算法的高效计算版本。例如,如果u和v不会有任何路径长度超过t,对于一些参数t,我们可以限制$ X_{uv} = 0$。它具有稀疏化(sparsifying)这些等式线性系统的效果,这可以帮助更有效地求解它。对于视频推荐算法,它也具有一个良好的语义解释:一用户观看了某一视频,如果在该视频半径为t的球体内没有其它用户观看它,就不推荐该视频给用户;这可以帮助控制那些在社群内流行但离该用户距离远的视频的传播,忽略掉它们有多流行。

该视角的另一个好处是,根据等式的线性系统,可以对标签分布进行增量更新,通过为相关的近邻快速更新信息,节点的加或减可以很快适应。

该节的结论,三种adsorption算法是等价的:

理论1: s Adsorption, Adsorption-RW, 和Adsorption-LS是等价的

2.4 注入概率与哑概率(Injection and Dummy Probabilities)

该算法的三种等价形式,导致许多有意思的变种。注意,等式的线性系统的视角,允许对于一个给定节点,我们可以限制哪个标签。我们指出,另一个有趣的变种可以通过采用另一解释来获取。

回顾“shadow”节点$\hat{v}$的概念,它为v扮演着“标签搬运工(label-bearer)”的角色。随着边$ (\hat{v}, v) $边权重的明智选择,(等价的,在逆向图中从v到$\hat{v}$的转移概率的选择)可以帮助我们精准控制随机游走的行为;它具有非常有用的应用。考虑到视频推荐的应用——假设我们从一个用户u开始一个随机游走,沿着边进行,到达一个视频节点v。现在,我们进入到吸附状态$ \hat{v} $的概率必须作为一个关于v的多个特征的函数来决定——它的流行度,新鲜度,社交兴趣,上传该视频用户的声望,等等。这样,该参数(我们称为“注入概率(einjection probability)”)通常在部署一个真实推荐系统时是一个重要的设计选择。相似的,在其它应用上,我们已经发现,该概率的选择在结果质量方面扮演着重要的角色。

下一个参数在控制算法的行为方面非常有用,是我们的等价理论的另一个新探索。考虑到在加权边图上的标准随机游走,我们可以考虑一个“跛行游走(hobbled walk)”,在每一step,有一些概率,我们称之为“abandonment probability” 或“dummy probability”,该算法会放弃随机游走,不会产生任意输出标签。例如,当随机游走访问一个高度节点(high-degree node)时相当有用。例如,在视频推荐上下文中,一个随机游走从一个用户节点u开始。假设在一些step后,随机游走到达了图中的节点z。如果z是一个高度(high-degree)的视频节点(相当流行的视频),再接另一个step将肯定会导致随机游走到那些与u相当不同的用户(因为流行的视频趋向于被没有共同兴趣的大部分用户观看)。相似的,如果z是一个高度(high-degree)的用户节点,再接另一step会导致用户u并不关心的视频(z可能具有很广泛的兴趣)。为了将该特征无缝集成到算法中,我们引入了“dummy” label的思想,在每个节点上修改label分布,来包含具有适当概率的”dummy” label。(通常受节点的度的影响)

我们的实验证实了,加了一个dummy label(相等的,放弃选择性的随机游走)确实是一个有用的特征。它可以以一个可计算的方式降低随机游走:在节点u上的一个标签l的影响,会沿着从带有标签l的节点到u的路径,以带标签节点数的指数方式减少。

3.实验

我们的实验的原始数据,从youtube.com上在92天内(从2007.7.1~2007.9.30)的用户观看视频中收集。我们从指定地理区域(语言、兴趣的主题基本相似)中选择了一个接近540w用户样本。对于每个选中的用户,我们收集了他们观看超过33%完成度的所有视频列表;该限制相当于用户实际上喜欢该视频。这产生了对420w视频的接近290w总观看数(一些可能是重复观看的)。所有数据以匿名的方式抽取,因而我们可以处理用户和视频的二分图(bipartite graph)(如图2所示)。

我们将数据分成两个集合:一个训练集,它包含了前46天的所有观看数据;一个测试集,它包含了其余天的所有观看数据。这里我们使用的这种方法,对应的metrics在第3.1节会讲。训练集被用于运行所有推荐算法,并基于它们的观看生成推荐;这些推荐的效果会与测试集对比进行衡量。考虑到,如果用户u没有在训练时间周期内观看视频v,但在测试时间周期内观看了视频v,我们就认为成功给用户u推荐了视频v。我们将对precision和recall进行measure(可以分别理解成:用户是否观看算法推荐的视频,以及算法是否推荐了所有用户要看的所有视频),这样的做法在信息检索应用上很常见。在我们处理评测准则的细节之前,我们很短暂地表述了所使和数据的一个总述。

首先,如果用户在训练周期和测试周期上同时没有观看行为,我们将这些用户抛弃掉。我们的评估机制允许为每个算法访问训练数据,限制该算法只基于该信息做出推荐。如果用户在两个周期内没有数据,那么没有方法来做出推荐或者为他做出评估。相似的,如果一个视频在训练周期内没被观看过,那么它不会被推荐,我们会移除这些视频。如果一个视频在训练周期中存在,在测试周期中不存在(可能被系统移除、下架),我们不会惩罚任何算法,因为这种case很容易在推荐系统的范围外进行处理,不会影响算法表现。在这些操作后,我们得到了约110w的用户以及130w的视频,约1250w的观看量。

假设,一个用户在训练期观看了视频集合$W_1$,在测试周期上视频集合为$W$,进一步假设,推荐算法从训练周期(对于所有的用户和视频来说)给定所有数据后,会给用户推荐一个视频的排名列表R。对于$ t = 1, …, |R| $,$R_t$包含了在R中前t个视频(以rank的顺序)。下面的定义在信息检索中的标准定义:

precision@t:

recall@t:

这样,对于每个在训练周期和测试周期上同时存在的用户u,t的合理值,我们获得了一个值对(value pair): ($p_{t}^{u}, r_{t}^{u})$ 。自然的,我们对跨所有用户进行平均来获取一个关于阈值为t的pair: $(p_t, r_t)$。这些值形成了in-depth分析的基础,包括ROC曲线(Receiver Operating Characteristic),Precision-Recall-Threshold 曲线以及top-rank质量评估。我们也通过每个推荐过程分析了视频集的覆盖率,见第4节。

3.1 推荐的事后检验(Backtesting Recommendations)

我们通过事后检验,指出涉及的微妙之处、注意事项、以及采纳该方法的合理之处,来停止临界分析我们的评测方法。

当没有提供排序(ranking)时,推荐系统的目标是诱使用户观看他们感兴趣的item,评估一个推荐算法的最简单方法是,在线上服务运行该系统,评估用户观看的推荐数目,或者对推荐结果进行人工标注进行评估。然而,这些方法都有一定的实际难点。在我们的研究中,有许多种参数设置和算法变种可以被探索;在真实服务上测试所有这些并不实际。使用足够多的用户来在一段长时间内运行每个变种,来获取统计上的不同之处,与确保在Youtube上的所有用户获得一个持久的、良好的体验相冲突。在该范围内(spectrum),人工标注不能有效地扩展,由于视频和算法变种的数量大。

一个最重要的挑战是,在允许上线部署前,评估推荐的有效性。为了评估推荐系统,我们使用在user-video观看上收集的历史日志数据。回顾之前的推荐系统训练,我们使用匿名的评估周期内的前46天数据。为了测试推荐,我们使用相似的后者数据中的一半的日志数据

对于评估一个算法推荐好坏,一种看起来简单的方法是,对于由一个系统在时间T上做出的推荐,在[T, …, T+E]周期上有多少视频被一个用户实际观看过。然而,使用历史日志数据来测试一个推荐系统(不管是否是吸附算法,或基于任何其它技术)必须小心实施。其中的一些难点,如下所述:

  • (1) 事后诸葛亮(Hindsight is not 20/20): 如果一个用户做出的推荐,用户在评估期并没有观看,将它标记为不正确其实并不合理。如果推荐已经被展示,用户可能会观看它。实际上,没有被观看可以简单认为是它没有被用户发现。
  • (2) 在评估期观看的视频数随用户的不同而不同:在评估一个推荐系统时,通常在特定设置中进行评测(evaluation),例如:100个推荐。如果用户观看多于/少于推荐的视频的情况没有被正确处理,所有的评估可能都是悲观的。
  • (3) 推荐在单个时间点上做出:在该评估中,每个推荐系统在评估周期的开始之处做出它们的推荐。在评估周期间的信息,比如:新趋势,在评估周期内被观看的视频,以及新的兴趣,不会被考虑进去。
  • (4) 新视频:由于Youtube视频库的快速增长,许多视频在评估周期被上传,它们不会出现在训练集上
  • (5) 新用户:会存在首次使用YouTube的新用户,在评估周期内观看了一个视频。这些用户不会有推荐。

这些case中最易于处理的是(4)新视频和(5)新用户。为了简化所有算法的评估,我们需要视频和用户在推荐的训练阶段和测试阶段youtube上存在,以便在评估时被统计。在部署时,该限制是不必要的;所有模型将会连续更新。注意,这种恒定的重训练(constant retraining)也可以处理问题(3);新视频和新的流行的视频会被考虑到。尽管有这些不同,在单个时间内上的效果衡量提供了有价值的信息,最坏情况下会低估效果级别。

用户具有不同的观看视频数目,以多种方式被处理,如下例所示。用户U在评估周期上观看了两个视频;观看集W是{a, b}。假设推荐系统$R_1$被设计成推荐5个视频,它会推荐{a,c,b,e,f}。另一个系统$R_2$,会推荐{a,c,e,f,b}。我们尝试去评估推荐系统是否对用户U更好。

将推荐列表的size限制到至多$ |W|$直观上是吸引人的;如果用户观看了$ |W|$个视频,那么可能我们应使用$ |W|$个视频来测试我们的推荐。注意由于该size的限制,$R_1$和$R_2$具有相同的precision和recall(a正确,b不正确)。如果我们没有将推荐列表的size限制到$ |W|$个,两者在5个推荐上都会有相同的recall。然而,在立即推荐列表size上的效果也会有不同。因此,当为每个算法展示ROC曲线时,对比起R2,$R_1$对用户的展示更好,因为它会对U的第二个观看b比R2排序更高。由于这项对算法效果的理解,我们不会基于$|W|$来归一化推荐的size。

最终,我们需要处理问题(1)不会给出完美的答案—— 即使查看历史日日志,我们也不知道一个用户可能已经采取的动作会不会产生一个特别的推荐。不幸的是,没有方法来解决该问题;precision/recall的数值不能捕获任何系统的所有优点。尽管如此,他们提供了有意思的数据,可以相互做对比。他们衡量了哪个方法能更好捕获用户已知的动作————即使当该用户没有关于所有视频的完美信息。

总之,假设给定用户没有完全知道提供给他们的视频信息,事后检验(backtesting)提供了一种方法来对系统推荐的期望效果做排序。最重要的是,该排序(ranking)可以被实施,无需使用户服从多个评估测试以及相关潜在的不一致结果。

3.2 算法和变种测试

我们简单概述了youtube推荐的三种算法。而文献上到处都是推荐算法,例如,我们尝试去捕获许多推荐算法的基础理解力,并提出了一种典型的、易于分析的、功能上多样化的方法集合。

第一个最基础的算法称为GP:全局流行度(global popularity)。该算法首先在训练周期内通过流行度对所有视频做排序。当我们需要为一个用户u做出推荐时,我们以该流行度测量的顺序做处理,输出top个用户在训练周期内未观看过的视频。一个视频的整体流行度对于选择展示给用户视频来说是一个相当重要的信息。作为参考,它可以确保任何提出的算法很优雅地处理实际问题,对于大多数用户,许多它们观看过的视频可能简单地与全局流行的视频相对应。

第二个算法称为LP(局部流行度),会考虑这种情况:全局流行度对于许多用户的个性化程度不够。该算法背后的思想是另一个非常常见的item-based推荐,它基于co-views。对于每个视频v,会计算与视频z一起共同观看的列表C(v),也就是说,用户观看了v也观看了z(在训练周期内)。再者,对于每个视频v,视频z与视频v被共同观看,会分配一个分数 c(v,z),它给出了共同观看v和z的用户数。当对用户u进行推荐时,会查看用户u在训练周期上观看的所有视频集合W(u),$ C(W(u)) \doteq {z \in C(v) | v \in W(u) } $ 为用户u共同观看的视频集合。对于每个 $ z \in C(W(u)) $,分配一个分数 $ c(u,z) \doteq \sum_{v \in W(u)} c(v,z) $; 通过总分对该集合做排序,输入排序后列表中top个未观看过的视频。这很容易实现,可以捕获在许多流行的推荐系统中存在的社会现象共性。(Amazon.com:用户买了X,也会买Y)

LP在一定程度上对用户是个性化的,它仍然有缺点:它趋向于喜欢一些流行的视频。例如,对于一个已经观看了某足球运动员视频的用户,会给他提供流行的足球视频,而非推荐用户更关心的关于该足球运员员的少量被观看的视频。

第三种算法会修正该问题:它不再将在视频v和z之间的co-view分数c(v,z)定义成用户共同观看v和z的数目,而是将c(v,z)定义成:

其中U(v)表示在训练周期内观看了v的用户集合。之前,我们将用户u和视频z的c(u,z)定义成 $ \sum_{v \in W(u)} c(v,z)$。我们称该算法为LR(局部稀有:local rare)。很容易看到该算法不会偏向于流行的视频,可以期望生成高度个性化的推荐。该得分公式是标准的Jaccard系数,一种衡量两个集合相似度的公式。

我们用相应的方法比较了adsorption算法的两个变种(带dummy node和不带dummy node)。我们使用“平均版本”的Map-reduce形式的adsorption算法变种,推荐集合可以很大地收敛。

Adsorption-N:在每个用户节点上,注入概率(injection probability)和空概率( dummy probability)为0; 持续的随机游走概率(probability of continuing the random walk)为1。在每个视频节点上,注入概率是1/4, 空概率为0, 持续的随机游走概率为1/2.

Adsorption-D:在每个用户节点上,注入概率为0, 空概率为1/4, 持续的随机游走概率为3/4。在每个视频节点上,注入概率为1/4, 空概率为1/4, 持续的随机游走概率为1/2.

最终,我们指出,adsorption是如何在视频推荐上被使用的。使用该算法的一种方法是,在user-video的视图上运行该算法,使用label分布来为每个用户生成推荐;label将会是与该用户最相关的视频。另一个等价的方法是,对于每个用户,我们收集了他观看过的视频的分布,并对他们求平均。尽管这会产生相同的答案,它具有一个很重要的好处:我们可以使用该过程来对新用户做推荐(它们不在训练集内),即使他们只观看了一个视频。

由于空间的限制,我们没在对video-video co-view graph的使用做详细说明。然而,也使用该图做了一些完整实验;结果与下一节描述的user-view的view graph很接近。

4.期望结果

我们运行了每个算法来为每个视频节点生成一个相关视频列表,对于每个用户,会生成100个推荐,以确保算法不会推荐那些对于该用户已经在训练周期内观看过的视频。

4.1 Reference算法

我们通过ROC曲线(precision, recall) pairs来得到推荐视频的效果,对比三个reference算法。如图3所示。首先注意到,具有高precision和低recall值的点,对应于在算法输出的推荐结果上选择少量top(未观看过)的视频。而具有高recall值和低precision值的点(图的左手边)对应于从算法输出中选择一个大的推荐数。

图3: reference算法的ROC

第一个观察到的现象是,存在着YouTube用户社区观看的群体性视频(collective)和个体视频(individual)。考虑到YouTube相对比较年轻,如果大多数YouTube观看者都是随便的”一次性(one-off)/偶然(occasional)”的观看者,这并不令人吃惊。对于那些大多数简单模型(只预测最流行的)不会有提升。另外,我们的评估机制相当严格(跨两个46天的周期),做出成功的推荐在一定程度上是令人吃惊的。

precision值相当小。然而,该值具有一定欺诈性,有两个原因:第一,我们的评估是基于事后检验机制,它非常保守(真实用户当观看过一个推荐视频时可能会喜欢该推荐,但不能量化评估);第二,在top-100上的precision为1%是相当动人的,这意味着在测试集上具有少量观看的用户,我们可以在100个推荐中成功产生至少一个想看的视频。考虑到观看频率的分布是一个典型的长尾分布(power-law),均值大约为5,大多数用户小于该均值,相当令人吃惊。

在top 1推荐中,GP算法达到了8.4%的precision以及3.2%的recall;在top 100的推荐上,10.6%的recall和precision为0.6%。 这种简单的heuristic的成功相当令人吃惊,为我们的算法设置了一个较强的baseline。

下一个有意思的现象是,我们观看到GP算法和LR算法ROC曲线交叉点,它可以达到较高的recall和较低的precision。这意味着当允许做出大量推荐时,LR可以为每个用户更好地裁减结果。如果我们喜欢做出一个少量的推荐,更好的推荐是GP;如果我们允许做出一个量大的推荐(一直),利用co-view统计更好。

最后,LP(它会有效结合两者)近乎一致地控制着这两个reference算法,提升很大。

4.2 Adsorption算法

我们来看下adsorption算法的效果。对于简单性,我们只限制在与LP的对比上,因为它是最好的reference算法。图4展示了两个adsorption变种算法、以及LP的ROC曲线:

图4: Adsorption算法的ROC

首先,我们注意到Adsorption-D和Adsorption-N几乎相同,前者具有微略更高的precision(更少的推荐),后者具有微略更高的recall(更多的推荐)。这与我们的直觉相一致:将一个随机游走做限制,让它与源节点更接近,以便更小概率发生主题漂移,从而获得更高的precision。相反的,一个限制更少的随机游走能到达更远的节点,会获得更高的recall。该通用规则的一个异常是在位置1上,其中Adsorption-N会比Adsorption-D具有更好的recall。然而,如图5所示,该图比一开始看起来更复杂。

图4的第二个结论是,在所有操作范围内,adsorption比最好的baseline效果更好。对比起LP,对于precision最大值的位置,我们观察到有17%的recall提升;对于recall最大值的位置,我们观察到有21%的precision提升。这些幅度上的增益对应于YouTube上成千上万的点击,非常有价值。

4.3 top-1效果

略.

Video Suggestion and discovery for YouTube

我们知道,在这个ugc的年代里,网络上各种各样支持文本输出的地方(比如:无意义的微博及评论、利用随机生成器注册id等等),经常出现一些无意义的乱语(英文叫:gibberish),比如“asdfqwer”。如何去识别它,是一个有意思的主题。

直觉跳出最简单的一种方式是,收集一本较全的英文字典,然后过滤一次,看看目标是否落在字典中。这是一种方式。准确率会有大幅提升,但是肯定还是会有一些case是难以解决的,比如:两个有意义的词刚好连在一起,却不在字典中。

另外我们再进一步思考一下,是否有什么算法进行训练,进而识别直接识别是否是乱语呢?可以考虑使用markov链模型。

对于一句话或短语来说:“hello buddy”,每个字母都与上下两个字母有关,这种关系可以通过2-gram来表示。比如:he, el, ll, lo, o[space], [space]b, …。

我们可以建立这样一个状态转移矩阵:

字母 a b c [space]
a Paa Pab Pac    
b Pba      
c Pca        
         
[space]          

在一个语料库, 我们会统计这些2-gram的频数,并将它们进行归一化。这样每个字母后的下一个字母出现都有一个概率分布(26个字母加空格)。

对于字母a,它的下一个输入为b的组成的2-gram的状态转换概率为:

为什么不是直接概率,而要使用log呢?

  • 由于字典很大,但一些词的出现概率会过小,计算机下溢(undeflow problem)将它们当成0来处理。
  • 我们最后要求的是整个“hello buddy”的概率,即:p = prob(he) * prob(el) * prob(ll) * … prob(dy)的概率,这在英文2gram的语言模型,而使用log可以利用log的性质:log(ab)=log(a)+log(b)
  • 最后,再通过e转换回正常概率即可.

如何判断是否是乱语?

我们可以收集一些乱语(bad),还有一些比较好的短语或语汇(good)。然后分别统计出对应bad以及good的平均转移概率。

平均转移概率=概率/转移次数

阀值的选取?

一般来说,good的平均转移概率,要比bad的大。可以选择平均:

thresh = (min(good_probs)+max(bad_probs))/2

  • 大于thresh,认为是good。
  • 小于等于thresh,认为是bad。

ok,利用这个模型,就可以识别字典之外的乱语了。如果你的训练语料很标准的话,那么相应的效果就会好很多。

参考: