最新一朋友在做比特币矿池方向的创业,受邀请帮忙研究下运营矿池的破产概率问题,以尽可能地规避风险。下面会将相应的一些概念与问题一一道来。

1.泊松分布与挖矿问题

泊松分布

  • 泊松分布适合于描述单位时间内随机事件发生的次数。
  • 泊松分布的参数λ是单位时间(或单位面积)内随机事件的平均发生率。
  • 泊松分布的期望和方差均为λt.

1.1 问题

比特币挖矿的数目服从泊松分布。

这是为什么?且细细看来。

  • 1.btc挖矿机的一次计算是否产生一个合法区块可以认为是一个随机事件,任何所有的计算hash彼此相互独立。

  • 2.每次hash计算有对应的计算难度,标为D,决定着发现一个合法块的难度。

  • 3.每次hash计算(32位hash计算,共有1/2^32个hash值)都会有 $ \frac{1}{2^{32}D} $的概率产生一个合法区块。

  • 4.矿工的算力(hashrate:每秒计算hash的次数):h

ok,这个问题可以化简为:

t时间内,该算力的矿工可以挖到多少btc区块?它服从什么分布?

1.2 解释

ok,很明显,速率问题,泊松分布.

速率λ(即:每秒能挖到多少个区块)为:$ \lambda=\frac{h}{2^{32}D} $

  • 单人在t时间内挖到的区块数目期望:$ E(X)=\lambda t=\frac{ht}{2^{32}D} $
  • 单人在t时间内挖到的区块数目方差:$ D(X)=\lambda t=\frac{ht}{2^{32}D} $

另外,还有一个条件:即一个合法区块对应着B个btc。换算成btc的话,这一个常数项的线性变换,即是一个POI(BX)的问题.

根据期望和方差的性质:

  • C为常数,X为随机变量
  • 期望性质:$ E(CX)=CE(X) $
  • 方差性质:$ D(CX)=C^{2}D(X), D(X+C)=D(X) $

从而,我们得到:

单人在t时间内对应回报的期望为:$ E(BX)=BE(X)=\frac{htB}{2^{32}D} $

单人在t时间内对应回报的方差为:$ D(BX)=B^{2}D(X)=\frac{htB^{2}}{2^{32}D} $

单人在t时间内对应回报的标准差为: $ \sigma(BX)=\sqrt{D(BX)}=\sqrt{\frac{htB^{2}}{2^{32}D} $

单人在t时间内对应回报的标准差/期望(标准差是期望的多少倍)为: $ \frac{\sigma(BX)}{E(BX)}=\sqrt{\frac{2^{32}D}{ht}} $

1.3 进一步

矿池挖矿模式与单人solo挖矿模式略有不同:

  • 1.它集合了矿池内所有矿工的算力:其hashrate为:H

矿池将在周期t内获得的区块数同样服从泊松分布(为做区分,此处为随机变量Y)。修改一下算力,得到相应的期望/方差:

矿池将在周期t内获得的区块数期望:$ E(Y)=\frac{Ht}{2^{32}D} $

矿池将在周期t内获得的区块数方差:$ D(Y)=\frac{Ht}{2^{32}D} $

将区块数换算成btc,对应的期望/方差:

矿池在周期t内获得的btc期望:$ E(BY)=\frac{HtB}{2^{32}D} $

矿池在周期t内获得的btc方差:$ D(BY)=B^2D(Y)=\frac{HtB^2}{2^{32}D} $

那么在矿池中,单个矿工的收益又是肿么样的一个期望/方差呢?

这里又有另外一项变换:单个矿工的hashrate为:h=qH(其中:q是该矿工对该矿池中总算力的贡献,0<q<1)

根据期望/方差性质,再做一次换算:

在矿池中,个人在周期t内获得的btc期望: $ E(X)=E(qBY)=qE(BY)=\frac{qHtB}{2^{32}D}=\frac{htB}{2^{32}D} $,该值与solo模式一样

在矿池中,个人在周期t内获得的btc方差:$ D(X)=D(qBY)=q^{2}D(BY)=\frac{q^{2}HtB^2}{2^{32}D}=\frac{qhtB^2}{2^{32}D} $,是solo模式的q倍。(0<q<1,因而方差变小,风险也变小了)

2.矿池如何实现收支平衡?

2.1 一般的矿池

矿池通常由一个矿池运营者(pool operator)来维护,它会在相应的服务上花费一定的费用。这通常是区块回报的一个固定百分比:f。因此,对于每个发现的区块,operator都将收到一笔fB的费用,余下的(1-f)B将分配给矿工。

再做一次变换,利用期望/方差的性质:

矿池中,单个矿工获得的的实际btc收入的期望为:$ E(X)=E((1-f)qBY)=(1-f)E(qBY)=\frac{(1-f)htB}{2^{32}D} $,与solo模式略有下降(但其实个人挖一样需要支付电费等问题存在)

矿池中,单个矿工获得的的实际btc收入的方差为: $ D(X)=D((1-f)qBY)=(1-f)^{2}D(qBY)=(1-f)^{2}q\frac{htB^2}{2^{32}D} $,是solo模式的(1-f)^2q倍. 方差更小。

2.2 变态的矿池

PPS矿池就是这样。

只要挖,不管有没挖到,在周期t时间里,矿工都会有收入。

在矿池中,单个矿工的收入的方差为0。operator承担所有的方差,风险更大,因而需要对operator再做一定的补偿。如果operator不正确平衡矿池的费用以及他的财产准备金,矿池有很大可能会破产。

这里有两个问题:

  • 补偿方式有变化?
  • 在有限资源的情况下,准备金至少需要多少,才能让破产机率更低?

先回到原先讲的:

  • 1.矿池中每次hash计算成为一个share的概率:$ \frac{1}{2^{32}} $
  • 2.每个share成为合法区块都有一个概率:$ p=\frac{1}{D} $
  • 3.矿工在每次提交一个share时将平均接收到的回报:pB
  • 4.对于operator则收到的费用: $ (1-f)pB $

2.2.1 推导阶段一

如何分配它?

这里,每次提交share可以当成一个step。在这个周期t内,计算出来的share本身有两个状态:合法(可得到btc)、非法(无效计算,得不到btc)。合法的概率为p,非法的概率为:1-p。

如果合法,则获得B个btc。然后拿出(1-f)pB进行分配给矿工,剩余的归operator自己。如果非法,那就没有收入了,但仍要拿出(1-f)pB进行分配给矿工。这是一个典型的连续时间随机过程,可以用马尔可夫链来表示。一个周期间,operator所得到的收入(包括损失):

$ X_{t+1}-X_{t}={ \begin{aligned} &-(1-f)pB+B & w.p. & & p \ &-(1-f)pB & w.p. & & 1-p \end{aligned} $$

它的期望为:

同理使用方差计算公式可得,真实的方差为:$ p(1-p)B^{2} $ ,而btc矿池paper将它近似认为:$ pB^{2} $,这里有些疑问(只有当p的概率较大时,才有可能近似)。

根据中心极限定理可知(这一步有待进一步求证),长期行为服从$ (fpB, p(1-p)B^{2}) $的正态分布。而这面的这个随机过程正好服从该分布(期望/方差一致),因而可以近似等价为:

我们再对这个初始条件按因子$ \sqrt{p}/B $做一下缩放:

这样缩放的好处,对后面推导有利。每次输赢为常量(f恒定, p恒定)。

2.2.2 推导阶段二

剩下的问题,其实就等价于随机过程中马尔可夫链的经典问题:《赌徒输光问题》。

$a_n$表示,从状态n开始要达到0的概率(表示矿池破产)。我们在第一步得到的条件,表示:$q=(1+f\sqrt{p})/2 $

这个随机过程可以表示为:

可以用常系数齐次线性方程求解该多项式特征方程:

该方程的解为:

整个特征方程,它的通解形式为:

代入初始值(边界条件):$a_0=1,a_{\infty}=0 $

即:A=0, B=1,得到$ a_n $:

如果operator以一个R的话准备金启动,矿池的破产概率为:

相反地,为了维持一个破产概率最大为$ \delta $,矿池应至少保有准备金:

参考:

1.Analysis of Bitcoin Pooled Mining Reward Systems. Meni Rosenfeld

attention机制在2014年被引入到NLP中:《NEURAL MACHINE TRANSLATION BY JOINTLY LEARNING TO ALIGN AND TRANSLATE》,我们可以看下具体实现:

2.背景:神经机器翻译

从概率角度,翻译等同于:给定一个源句子(source sentence)x,发现这样一个目标句子y(target sentence),使得它的条件概率最大化: 。在神经机器翻译中,会拟合一个参数化模型,使用一个并行训练语料,来最大化关于句子对(sentence pairs)的条件概率。一旦通过一个翻译模型学到了条件分布后,对于给定一个源句子,对应的翻译可以通过搜索使条件概率最大的句子来生成。

最近,许多paper已经提出使用神经网络来直接学习该条件概率。 这些神经机器翻译方法通常包含两个组件:第1个组件会编码(encode)一个源句子x,第2个组件会解码(decode)成一个目标句子y。例如,(Cho.2014a)使用两个RNN来将一个变长的源句子编码到一个固定长度的vector上,然后将该vector解码到一个变长的目标句子上。

神经机器翻译已经成为相当新的方法,并展示了很好的结果。Sutskever 2014, 在English-to-Frech翻译任务上,使用基于RNN与LSTM units的神经机器翻译已经达到了接近state-of-the-art的效果。。。

2.1 RNN encoder-decoder

这里,我们描述了下述框架,称为RNN Encoder-Decoder,由Cho 2014a和Sutskever 2014提出。 在此基础上我们构建了一个新结构,它可以同时学到对齐(align)和翻译(translate)。

在Encoder-Decoder框架中,encoder会读取输入句子(input sentence),一个向量序列:,将它映射到一个向量c上。使用RNN时最常用的方法是:

…(1)

…(2)

其中:

  • 是一个在时间t时的hidden state
  • **c是一个从hidden states序列生成的vector。
  • f和q是一些非线性函数。例如:Suskever 2014使用一个LSTM作为f,

decoder通常被训练成:在给定上下文向量(context vector)c、以及之前预测过的词的情况下,用来预测下一个词。换句话说,decoder定义了一个在翻译y上的概率,它通过将联合概率(joint probability)解耦成顺序条件(ordered conditionals):

…(2)

其中,。在一个RNN中,每个条件概率被建模成:

…(3)

其中:

  • g是一个非线性、可能多层的函数,会输出概率
  • 是RNN的hidden state。

需要注意的是,其它结构(比如:一个RNN与一个de-convolutional网络进行混合的结构)可以被使用。

3.学习align和translate

在本节中,我们提出了一个新的神经机器翻译结构。新结构包含了一个Bidirectional RNN作为一个encoder(3.2节),以及一个decoder,它在对一个翻译进行decoding期间,通过一个源句子进行模拟搜索来完成。

3.1 Decoder: 通用描述

在新模型结构中,我们定义了等式(2)中的每个条件概率:

…(4)

其中,是一个在时间i上的RNN hidden state,可以通过下述公式计算得到:

需要注意的是,不同于已经存在的encoder-decoder方法(等式(2)),这里的概率是条件概率,它基于对于每个目标词(target word)上一个不同的上下文向量(context vector) 得到。

上下文向量依赖于一个annotation序列:,一个encoder会将输入句子(input sentence)映射到它上。每个annotation 包含了整个输入序列相关的信息,它会强烈关注围绕在输入序列第i个词周围的部分。后续我们会解释 annotation是如何被计算的。

1.png

图1: 给定一个源句子,提出的模型尝试生成第t个目标词图示

上下文向量通过对这些 annotations 进行加权求和得到

…(5)

每个annotation 的权重通过计算下述公式得到:

其中:

是一个对齐模型(alignment model),它会对围绕位置j的输入与位置i的输出间的匹配度进行打分。该得分基于RNN hidden state (等式(4))和关于输入句子的第j个 annotation 计算得到。

我们将对齐模型(alignment model)a参数化成一个前馈神经网络,它会与系统的所有其它组件一起进行jointly train。注意,这与在传统的机器翻译不同,对齐(alignment)不会被当成一个隐变量来考虑。相反的,对齐模型(alignment model)会直接计算一个软对齐(soft alignment),它允许cost函数的梯度可以进行BP。该梯度可以被用于联合训练alignment model与translation model。

我们可以理解,采用对所有annotations进行加权求和的方法来计算一个期望注解(expected annotation),其中期望是对所有alignments进行的。假设是目标词与源词对齐的概率、或从源词进行翻译的概率。接着,第i个上下文向量是使用概率在所有annotations上的expected annotation。

概率,或者它相关的能量,会影响annotation 在关于前一hidden state 在决定下一state 和生成的重要性。直觉上,这实现了在decoder中的attention机制。该decoder决定着源句子中要关注(pay attention to)的部分。通过让decoder具有一个attention机制,我们会减轻encoder将源句子中的所有信息编码成一个固定长度向量的负担。使用这种新方法,可以通过annotations序列进行传播信息,这些annotations可以根据相应的decoder进行选择性检索。

3.2 Encoder:对annotating序列使用Bi-RNN

常用的RNN,如等式(1)所描述,会以从的顺序读取一个输入序列x。然而,在提出的scheme中,我们希望每个词的annotation可以归纳不仅仅是前面出现的词,也可以归纳后续跟着的词。因而,我们提出使用一个BiRNN。

BiRNN包含forward和backward RNN两部分。forward RNN 会按从的顺序读取输入序列,并计算一个forward hidden states序列。backward RNN 会以逆序 (即:从的顺序)来读取序列,产生backward hidden state序列

我们通过将forward hidden state 和backward 进行拼接(concatenate)(如:),来为每个词获得一个annotation。这种方式下,annotation 包含了前面词和后续词的总结信息(summaries)。由于RNN可以更好地表示最近输入,annotation 将关注周围的词。该annotations序列被用在decoder上,alignment model后续会计算该上下文向量(等式(5)-(6))。

4.实验

参考

我们来看下《AutoRec: Autoencoders Meet Collaborative Filtering》,它提出的autorec,会使用新的autoencoder框架来进行CF:

1.介绍

CF模型的目的是,根据用户对items(评分)的偏好进行探索,从而来提供个性化推荐。Netflix竞赛提出了一全套不同的CF模型,比较流行的方法有:矩阵分解[1,2]以及邻近模型[5]。该paper提出了AutoRec,一种新的基于autoencoder范式的CF模型。它的灵感原自于最近在视觉和语音任务上的深度学习上获得的成功。AutoRec对于已经存在的CF上的神经网络方法[4]在表征和计算上均有优势,我们会展示它的效果要好于state-of-art方法。

2.AutoRec模型

在基于评分(rating)的CF中,我们有m个用户,n个items,以及:

  • 一个部分可观察(相对的,有一部分missing)到的user-item评分矩阵
  • 每个用户,可以被表示成一个部分可观察向量(partially observed vector):

相似的,每个item ,可以被表示成:

我们的目标是,设计一个item-based(user-based)的autoencoder,它可以将输入看成是每个部分可观测的,将它投影到一个低维的隐空间(hidden/latent space),接着,在输出空间将进行重构来预测缺失的ratings。

正式的,给定在中的一个S集合,,一个autoencoder可以求解:

…(1)

其中,是对输入的重构(reconstruction):

对于激活函数 。这里,对于转换(transformations): ,其中biases为: 。该目标函数对应于一个自关联的神经网络(auto-associative neural network),它使用单个k维的hidden layer。参数可以通过backpropagation进行学习。

图1: Item-based AutoRec模型。我们使用plate notation来表示,该网络存在n个拷贝(每个item一个),W和V跨多个拷贝绑定。

item-based AutoRec模型,如图1所示,使用一个autoencoder作为等式(1)到向量集合中,有两个重要变化。第一,我们会解释:每个通过在BP期间的更新上关权重来被部分观测,这一点与矩阵分解和RBM方法相同。第二,我们会对学习参数进行正则化,以便防止在观测到的ratings上overfitting。正式的,Item-based AutoRec (I-AutoRec)模型的目标函数是:

…(2)

其中,意味着,我们只需考虑可观测评分的贡献即可。User-based AutoRec (U-AutoRec)则由 而来。总之,I-AutoRec 需要估计 个参数。给定要学习的参数,I-AutoRec会为用户u和item i预测相应的评分:

…(3)

图一展示了该模型,阴暗色节点表示观测到的评分,实线连接对应于权重(对于输入要更新的权重)

AutoRec与已经存在的CF方法不同。对比RBM-based CF模型,有一些不同之处:

  • 1.RBM-CF提出了一种通用的概率模型,它基于Boltzmann机;而AutoRec是一个判别模型(discriminative model),它基于autoencoders
  • 2.RBM-CF通过最大化log似然来估计参数,而AutoRec直接最小化RMSE(在评分预测上的标准评判指标)。
  • 3.训练RBM-CF需要使用对比散度( contrastive divergence),而训练AutoRec需要比较快的基于梯度的BP算法。
  • 4.RBM-CF也用于离散评分,并每个评分值估计一个独立的参数集合

对于r个可能的评分,这意味着对于user-based RBM有nkr个参数;对于item-based RBM有mkr个参数。AutoRec对于r是不可知的,因而需要更少的参数。更少参数能让AutoRec具有更少的内存占用,不容易overfitting。对于MF(矩阵分解)方法,会将users和items嵌入到一个共享的隐空间中;而item-based AutoRec模型只会将items嵌入到隐空间中。再者,MF会学到一个线性隐表示,AutoRec可以通过激活函数学到一个非线性隐表示

3.实验评估

在本部分,在数据集:Movielens 1M, 10M and Netflix datasets上评估了AutoRec、RBM-CF、BiasedMF、以及LLORMA。接着,我们使用一个缺省的评分3用于测试users或items,没有训练观察。我们将数据划分为:随机的90%-10%的train-test集合,并留下10%的训练集数据进行超参数调节。我们会重复5次的splitting过程,并上报平均的RMSE。在RMSE上的95%置信区间是,或者更小。对于所有baselines,我们会将正则参数以及合理的隐维度

训练autoencoders的一个挑战是,目标函数的非凸性。我们发现RProp与L-BFGS对比来说会更快。因此,我们在所有实验中使用RProp:在item-based和user-based方法上,对于RBM或AutoRec autoencoding哪个更好?表1a展示了item-based(I-)方法上,RBM和AutoRec通常会更好;这很可能是因为每个item的评分平均数,比单用户的要多;对于user-based方法,user ratings的数目的高偏差会导致更低可靠性的预测。I-AutoRec的效果要比所有RBM变种要好。

AutoRec的效果随线性和非线性激活函数是如何变化的?表1b展示了在hidden layer中的非线性(通过)对于I-AutoRec上取得好效果是很重要的,它比MF更好。将sigmoid替换为Relu效果会差些。所有AutoRec实验使用标准的和sigmoid 函数。

AutoRec的hidden units数目与效果是啥关系?在图2中,我们评估了AutoRec模型的效果,AutoRec会随着hidden units数目变化,并且收益递减。所有AutoRec实验使用k=500.

图2: I-AutoRec在Movielens 1M上的RMSE,随hidden units数目k而变化

AutoRec的效果与所有baseline相比如何?表1c展示了AutoRec会一直好于所有baseline。

表1: a) I/U-AutoRec与RBM模型的比较 b) I-AutoRec中线性与非线性选择 c) I-AutoRec与其它baseline模型的比较

对autoRec的深度做扩展如何?我们开发了一个深度版本的I-AutoRec,它有三个hidden layers(500, 250, 500),每个使用sigmoid激活。我们使用贪婪预训练,接着通过梯度下降调参。在Movielens 1M上,RMSE会从0.831降至0.827, 表示有提升。

参考

http://users.cecs.anu.edu.au/~u5098633/papers/www15.pdf

先来看一下 paper中提取的FFM。

一、前置

对于一个有m个样本的数据集:$(y_i, x_i)$,i=1,…,m,其中$y_i$是label,$x_i$是一个n维特征向量,模型w通过对下面问题进行最优化求解得到。

…(1)

其中λ是正则参数,在loss function,如果是线性模型(LM: Linear Model),则:

另外,有两种其它的模型:Poly2和FM。

Poly2(度为2的多项式)可以有效捕获特征交叉信息。通过在线性模型上应用度为2的mapping的显式形式,训练和测试时间可以比使用kernel方式更快。这种方法可以学到每个feature pair的weight:

…(2)

其中$ h(j_1, j_2) $是一个用于将j1和j2编码成一个自然数的函数。计算(2)的复杂度为 $O(\bar{n}^2)$,其中n是每个实例非零元素个数的平均值。

FM则可以为每个feature学到一个隐向量。每个隐向量包含着k个隐因子,其中k是一个用户指定的参数。接着,特征交叉的效果通过两个隐因子进行内积建模而成:

…(3)

变量数为n x k,直接计算(3)的代价是 $O(\bar{n}^2 k)$。可以进行化简,得到:

其中:

复杂度可以减少到$ O(\bar{n}k) $.

二、FFM

FFM的idea来自于带有个性化标签的推荐系统中提出的PITF(paper 7)。在PITF中,假设有三种fields:User,Item,Tag,在独立隐空间中对(User, Item), (User, Tag), (Item, Tag)进行因子分解。在paper[8]中,将PITF泛化到更多的fields(比如:AdID, AdvertiserID, UserID, QueryID),并有效地将它应用在CTR预估上。由于 paper[7]的目标是推荐系统,并受限于三个特定的fields(User, Item, Tag),paper[8]在FFM上缺乏详细讨论,在本节中,我们提供了一个更复杂的在CTR预测上的研究。对于大多数像表 1所示的CTR数据集,“features”可以被分组成”fields”中。在我们的示例中,有三个features:ESPN,Vogue,NBC,它们都属于Publisher field;而其它三个features:Nike,Gucci,Adidas,它们都属于Advertiser field。FFM是FM的一个变种,它会利用这些信息。为了解释FFM是如何工作的,我们来看下面的新样本:

1
2
Clicked	Publisher(P)	Advertiser(A)	Gender(G)
Yes		ESPN			Nike			Male

回顾下FM,$ \phi_{FM}(w,x) $ 等于:

在FM中,每个feature都只有一个隐向量(latent vector)来学到与其它任何features的隐式影响。以ESPN为例,$ w_{ESPN} $用于学到与Nike(),以及Male()的隐式影响(latent effects)。然而,由于Nike和Male属于不同的fields,(ESPN, Nike)和(ESPN, Male)的隐式影响可能是不同的。

在FFM中,每个features具有不同的隐向量(latent vectors)。这取决于其它features的fields,其中之一会被用于做内积。在我们的示例中,$ \phi_{FM}(w,x) $ 为:

我们看到,为了学到(ESPN, Nike)的隐式影响,会被使用,因为Nike属于field(Advertiser:A),同理, 会被使用,因为ESPN属于field(Publisher:P)。

同理,学了学到(EPSN, Male)的隐因子,会被使用,因为Male会属于field(Gender: G);会被使用,因为ESPN属于field(Publisher: P)。 数学上:

…(4)

其中$f_1$和$f_2$各表示$j_1$和$j_2$的fields。如果f是fields的数目,那么FFM的变量数目为$ \bar{n}fk $,计算公式(4)的复杂度为$ O(\bar{n}^2 k) $。在FFM中,由于每个隐向量只需要学到一个特定field的影响,通常:

表2比较了不同模型的变量数和计算复杂度。

三、求解最优化问题

FFM的最优化问题与LM相似。这里使用的是SG方法(stochastic gradient)。最近,一些adaptive learning-rate方法有提出:AdaGrad等。使用AdaGrad是因为它对于矩阵因子分解(包括FFM)很有效。

在SG的每一个step中,会抽样一个数据点(y,x) 来更新 $ w_{j_1,f_2}$和$ w_{j_2,f_1}$。注意,由于x在我们的应用中高度稀疏,我们只会使用非零值来更新维度(dimensions)。首先,子梯度(sub-gradients)为:

…(5)

…(6)

其中:

接着,对于每个坐标 d=1,…,k,梯度平方和会进行如下累积:

…(7)

…(8)

最终,$ (w_{j_1,f_2})d$和$ (w{j_2,f_1})_d$会进行如下更新:

…(9)

…(10)

其中$\eta$是一个用户指定的learning-rate。w的初始值从一个在$[0, 1/\sqrt{k}]$间的均匀分布中进行随机抽样。G的初始值被设置成1以便于阻止一个关于$ (G_{j_1,f_2})_d^{\frac{1}{2}}$大值。整个过程如算法1所示。

经验中,我们发现归一化每个实例到单位长度上,可以让accuracy稍好,对参数更不敏感些。

3.2 共享内存系统上进行并行化

现代计算机基本都采用多核CPUs。如果这些核能被充分利用,训练时间可以极大缩短。许多SG的并行方法被提出。在这paper中,我们应用HOG-WILD!,它允许每个线程独立运行,没有任何锁。特别的,在算法1中的第3行的for循环是并行的。

3.3 增加Field信息

考虑到我们使用的是LIBSVM的数据格式:

1
label feat1:val1 feat2:val2 · · · 

其中每个(feat,val)pair 表示特征index和value。对于FFM,我们扩展了以上的格式:

1
label field1:feat1:val1 field2:feat2:val2 · · ·

也就是说,我们必须为每个feature分配一个对应的field。这种分配在某些类型的特征上很容易,但是在另外一些类型的特征上不太容易。这里讨论了三种类型。

Categorical Features

对于线性模型,一个categorical feature常以被转换成一些二值特征。对于一个数据实例:

1
Yes P:ESPN A:Nike G:Male

我们生成了它的Libsvm格式:

1
Yes P-ESPN:1 A-Nike:1 G-Male:1

注意,对应于在一个categorical feature中可能值的数目,会生成相同数目的二值特征,每次只有其中之一会具有值1。在Libsvm格式中,零值的features不会被存储。我们将这种setting应用到所有模型中。为了添加field信息,我们可以将每个category看成是一个field。以上的实例就变成了:

1
Yes P:P-ESPN:1 A:A-Nike:1 G:G-Male:1

Numerical Features

考虑到以下的示例是预测一个paper是否会被某会议接收。我们使用三种数值型特征:“会议接收率:accept rate of the conference (AR),”“作者的h-index:h-index of the author (Hidx),” and “作者的引用数:number of citations of the author (Cite):”.

1
2
3
Accepted	AR		Hidx	Cite
Yes			45.73	2		3
No			1.04	100		50000

这里有两种可能的方式来分配fields。一种自然的方式是,将每个feature看成是一个dummy field,因而生成的数据是:

1
Yes AR:AR:45.73 Hidx:Hidx:2 Cite:Cite:3

然而,该dummy fields可能没有任何信息量,因为它们仅仅只是特征的复制。

另一个可能的方式是,对每个数值型特征离散化成一个类别型特征。接着我们使用和categorical features相同的setting来添加field信息。生成的数据如下:

1
Yes AR:45:1 Hidx:2:1 Cite:3:1

其中,AR特征被归整(round)为一个整数。主要的缺点是,通常决定最好的离散化设置并不容易。例如,我们可能将45.73转化成: 45.7, 45, 40, 或者 int(log(45.73))。另外,我们会在离散化后失去一些信息。

single-field features

在一些数据集上,所有的features都属于单个field,因而,为它分配一个field是无意义的。通常该情况发生在NLP数据集中。考虑到以下示例:预测一个句子表达是好心情,还是坏心情。

1
2
3
good mood		sentence
Yes				Hooray! Our paper is accepted!
No				Well, our paper is rejected.

在该例中,只有一个field:“sentence”。如果我们为所有的words分配一个field,那么FFM就成了FM。读者们可能会问到可以分配类似numerical features的dummy field。回顾下FFM的model size为:O(nfk)。使用dummy fields不实际,因为f=n,n通常很大。

4.实验

详见paper。

参考

我们都清楚word2vec,这是Deep NLP最基本的任务。对于词有词向量,对于句子,或者是段落,也一样可以生成相应的向量(注意:两者的向量空间是不一样,不能合在一个空间中)。paragraph2vec在[1]有详细介绍,我们先来看下具体的概念:

1.PV-DM:(Paragraph Vector:Distributed Memory model)

受词向量(word vector)方法的启发,我们也学习到段落向量(paragraph vector)。词向量会被用于预测句子中的下一个词。因此,尽管实际上词向量的初始化是随机的,它们仍可以捕获语义,作为预测任务的间接结果。我们在paragraph vector中使用相类似的方式。在给定从段落中抽样获取多个上下文的情况下,也可使用paragraph vector来预测下一个词。

在我们的Paragraph Vector框架中(见图2), 每个段落(paragraph)都被映射到一个唯一的vector中,表示成矩阵D中的某一列;每个词(word)都映射到一个某一个向量中,表示成矩阵W中的某一列。对paragraph vector和word vector求平均,或者级联(concatenated)起来,以预测在上下文中的下一个词。在该试验中,我们使用级联(concatenation)作为组合向量的方法。

图2: 学习paragraph vector的框架。该框架与word2vec的框架相似;唯一的区别是:会有额外的paragraph token通过矩阵D映射到一个vector中。在该模型中,对该向量以及再带上一个三个词的上下文,对它们进行级联或者求平均,用来预测第4个词。paragraph vector表示从当前上下文缺失的信息,可以看成是关于该段落(paragraph)的主题(topic)的记忆单元。

更正式的,在模型中与词向量框架的唯一变化是,h是从W和D中构建的。

paragraph的token可以认为是另一个词。它扮演的角色是,作为一个记忆单元,可以记住当前上下文所缺失的东西–或者段落(paragraph)的主题。出于该原因,我们经常称该模型为Paragraph Vector分布式记忆模型(PV-DM:Distributed Memory Model of Paragraph Vectors)。

上下文是固定长度的,从沿段落(paragraph)滑动的一个滑动窗口中采样。所有在相同段落(paragraph)上生成的上下文,共享着相同的paragraph vector。在不同的段落(paragraphs)间,则共享着相同的词向量矩阵W,比如,单词”powerful”的向量,对于所有段落(paragraphs)是相同的。

Paragraph Vectors和Word Vectors都使用SGD进行训练,梯度通过backpropagation算法求得。在SGD的每一步,你可以从一个随机paragraph中抽样一个固定长度的上下文,计算error的梯度,更新模型参数。

在预测阶段,对于一个全新的段落(paragraph),需要执行一个推断步骤(inference)来计算paragraph vector。这也可以通过梯度下降法获取。在该步骤时,对于模型其余部分的参数,word vectors:W以及softmax的权重,是固定的。

假设在语料中有N个段落(paragraph),词汇表中有M个词,我们希望学到paragraph vectors,每个paragraph都被映射到p维上,每个word被映射到q维上,接着该模型具有总共N x p + M x q 个参数(将softmax参数排除在外)。尽管当N很大时,参数的数目会很大,在训练期间的更新通常是稀疏的,并且很有效。

在训练之后,paragraph vectors可以当成是该段落(paragraph)的特征(例如:代替bow或作为bow的额外附加)。我们可以将这些features直接输入到常用的机器学习技术(LR, SVM或者K-means)中。

总之,算法本身有两个关键步骤:

  • 1) 在训练(training)阶段:在已知的段落(paragraphs)上,获取词向量W,softmax的权重(U,b)以及paragraph vector: D.
  • 2) 在推断(inference)阶段:保持W,U,b固定不变,通过增加D中的更多列,在D上进行梯度下降,为新未曾见过的的段落(paragraph)获取paragraph vectors: D。我们使用D来做预测关于更多的特定labels。

paragraph vectors的优点:paragraph vectors的一个重要优点是,它们可以从未标记的数据(unlabeled data)中学到,在没有足够多带标记的数据(labeled data)上仍工作良好。

Paragraph vectors也处理了一些BOW模型所具有的主要缺点。首先,它们继承了词向量的一个重要特性:词的语义(semantics)。在该空间中,对比”Paris”与”strong”,”powerful”与”strong”更接近。Paragraph vector的第二个优点是:它们会考虑词顺序(至少在某个小上下文上会考虑),与n-gram模型(有一个大的n)的方式相同。这十分重要,因为n-gram模型保留着一部分段落(paragraph)的信息,包括词顺序。也就是说,我们的模型可能优于一个bag-of-n-gram模型,因为一个bag-of-n-gram模型可以创建出一个高维表示,这很难泛化。

2.PV-DBOW: (无词序的Paragraph Vector: Distributed BOW)

上面的方法会将paragraph vector和词向量串联起来来预测一个文本窗口中的下一个词。接下来的另一种方法则是忽略掉输入中的上下文词汇,强制模型去预测从段落(paragraph)中随机抽样出的词作为输出。在实际上,这意味着,在SGD的每次迭代中,我们可以抽样一个文本窗口,接着从该文本窗口中抽样一个随机词汇,去构建这样一个分类器任务来获取Paragraph Vector。该技术如图3所示。我们将该版本称为:PV-DBOW (Distributed Bag of Words version of Paragraph Vector)

图3: PV-DBOW.在该版本中,训练该paramgraph vector以预测在一个小窗口中的词汇.

除了概念简单之外,该模型存储的数据也更少。我们只需要存储softmax的权重,而PV-DM则需要存储softmax权重以及词向量。该模型与word2vec中的skip-gram模型相类似。

在我们的试验中,每个paragraph vector是一个两种向量的组合:一个向量由标准PV-DM模型学到,另一个向量由PV-DBOW模型学到的。对于大多数任务PV-DM单独工作也能达到很好的效果(state-of-art),如果与PV-DBOW组合在一起使用,在许多不同任务上可以更一致,强烈推荐使用组合方式

3.实验

我们会对paragraph vectors的表现进行实验。

对于语义分析,我们使用两个数据集:Stanford sentiment treebank dataset 以及 IMDB dataset。这些数据集中的文档在长度上区别很大:Stanford数据集是单句,而IMDB则包含着多句。

我们也在一个信息检索任务上测试我们的方法,目标是:给定一个query,一个文档是否该被索引出。

3.1 基于sentiment-treebank数据集的Sentiment Analysis

数据集:该数据集首先在2005年提出,随后在2013进行扩展,是sentiment analysis的一个benchmark。它包含了11855个句子,从烂蕃茄(Rotten Tomatoes)的电影评论中获取。

该数据集包含了三个集合:8544个句子用于训练(training),2210个句子用于测试(test),1101个句子用于验证(validation)。

数据集中的每个句子都有一个label,表示极性的正负程度,从0.0到1.0.label由亚马逊的众包(Amazon Mechanical Turk)人工标注完成。

该数据集对于句子有详细的label,子句(subphrases)同样也需要。为了达成该目标,Socker et al.(2013b)使用Stanford Parser(Klein & Manning,2003)来将每个句子解析成子句(subphrases)。子句接着以相同的方式被人工标注。目前该数据集总共有239232个带标记的句子。数据集下载地址:https://nlp.stanford.edu/sentiment/

任务以及Baselines: 在(Socker et al.,2013b)中,作者提出了两种benchmarking的方法。首先,可以考虑5-way细粒度分类任务,对应的label为:{Very Negative, Negative, Neutral, Positive, Very Positive}或一个2-way的粗粒度分类:{Negative, Positive}。另外,可以分为:是对整句,或者子句的划分。本工作主要针对完整句子的labeling.

在该数据集中,Socher应用许多方法,并发现Recursive Neutral Tensor Network比BOW模型更好! 这里仍有争议,因为电影评论通常很短,语义合成性(compositionality)在决定评论极性正负时扮演着重要角色。对于这个小训练集,对词语间的相似度也同样很重要。

试验约定:我们按照(Socher et al.2013b)所描述的实验约定。为了充分利用带标记数据,在我们的模型中,每个子句,都被当成是一个独立的句子,我们将为训练集中所有的子句学到它的向量表示。

在学习到训练句子和它们的子句的向量表示之后,我们将它们输入到一个logistic regression中来学习电影评分的预测。

在测试时,我们确定每个词的向量表示,使用梯度下降学到句子的向量表示。一旦学到测试句子的向量表示,我们将它们输入到logistic regression中来预测电影评分。

在我们的试验中,我们使用验证集对window size交叉验证,可选的window size为8。该分类器的向量表示是两个向量的串联:一个来自PV-DBOW,另一个来自PV-DM。在PV-DBOW中,学到的段落向量表示为400维。在PV-DM中,学到的词向量和段落向量表示均为400维。为了预测第8个房屋中,我们将paragraph vectors和7个word vectors相串联。我们将特征字符“,.!?”这些看成是一个普通词。如果该段落(paragraph)少于9个词,我们会预补上(pre-pad)一个特殊的NULL符号(NULL word symbol)。

结果:如表1所示。我们上报了不同方式的错误率。该表中高度部分是BOW或者是bag-of-n-gram模型(NB, SVM, NiNB)的效果很差。对词向量求平均(以BOW的方式)不会提升结果。因为BOW模型不会考虑句子是如何构成的(比如:词顺序),因此在识别许多复杂语义现象时(例如:反讽:sarcasm)会失败。结果也展示了更多的高级方法(比如:Socher.2013b的RNN),它需要parsing以及会对语义合成性做理解,效果更好。

我们的方法比所有的这些baselines都要好,尽管实际上不需要parsing。在粗粒度分类任务上,我们的方法在error-rates上有2.4%的提升。相对提升16%!

3.2 多句:IMDB数据集的Sentiment Analysis

前面的技术只应用在单句上,而非带有多句的段落或者文档上。例如:RNN会基于在每个句子上进行parsing,而对于多个句子上的表示的组合是不清楚的。这种技术只限制在句子上,而不能用在段落或者文档上。

我们的方法不需要parsing,它可以对于一个包含多句的长文档生成一个表示。这个优点使人们的方法比其它方法更通用。下面的试验在IMDB数据集上展示了该优点。

数据集:IMDB数据集,首先由Maas et al., 2011提出作为sentiment analysis的一个benchmark. 该数据集包含来自IMDB的10W的电影评论。该数据集的一个关键点是,每个电影评论都有多句话组成。

10w的电影评论被分成三个数据集:2.5W带标记的训练实例,2.5W带标记的测试实例,5W未标记的训练实例。有两类label: 正向(Positive),负向(Negative)。这些label对于训练集和测试集是均衡的(balanced)。数据集下载:http://ai.stanford.edu/~amaas/data/sentiment/

实验约定:我们会使用7.5W的训练文档(2.5W已经标注的实例,5W未标注的实例)来学到word vectors和paragraph vectors。对于2.5W已标注实例的paragraph vectors,接着会输入(feed)到一个单层的、含50个单元神经网络中,以及一个logistic分类器来预测语义。

在测试时,给定一个测试语句,我们再次固定网络的其余部分,通过梯度下降学到测试评论中段落向量(paragraph vectors)。当学到向量时,我们将它们输入到神经网络中来预测评论的sentiment。

我们的paragraph vector模型的超参数,和先前的任务相同。特别的,我们交叉验证了window size,最优的window size为10个词。输入到分类器的向量表示,是两个向量的串联,一个是PV-DBOW,另一个是PV-DM。在PV-DBOW中,学到的向量表示具有400维。在PV-DM中,为words和documents学到的向量表示都有400维。为了预测第10个词,我们将paragraph vectors和word vectors相串联。特殊词:”,.!?”被看成是一个普通词来对街。如果文档比9个词少。我们会使用一个特殊的NULL词符号进行以预补足(pre-pad)。

结果:Paragraph Vectors的结果和其它baselines如表2所示。对于长文档,BOW模型执行很好,很难在它们之上使用词向量进行提升。最大的提升发生在2012年(Dahl et al.2012),它将一个RBM模型与BOW相组合。两种模型的组合在error-rates上有1.5%的提升。

另一个大提升来自(Wang & Manning,2012)。他们使用了许多变种,在bigram特征上使用NBSVM,效果最好,在error-rates上有2%的提升。

在该paper上描述的方法,超出了10%的error-rate提升。它达到了7.42%,比上面最好的模型有1.3%的绝对提升(相对提升有15%)

表2: IMDB的Paragraph vector的效果对比.

3.3 使用PV的IR

我们在IR任务中,使用固定长度的paragraph表示。

这里,我们有一个段落数据集,给定100W的最流行搜索,返回有10个结果。这些段落的线一个都被称为片段“snippet”,它是一个网页的内容摘要,以及一个网页是如何匹配query的。

从这些collection中,我们派生了一个新的数据集作为测试集的paragraph向量表示。两个段落(paragraph)是对于相同的query的结果,第三个段落(paragraph)是从该collection的其它部分随机抽样得到的paragraph(作为一个不同的query得到的结果返回)。我们的目标是,确认这三个paragraph中哪些是相同query返回的结果。为了达到该目的,我们使用paragraph vectors,并计算paragraphs间的距离(distance)。也就是说:相同查询的段落对的距离的距离小,以及不同查询的段落对(paragraphs pairs)间的距离大。

这里有关于三个段落的一个样本,第一个段落更接近于第二个段落(比第三个):

  • 段落1: calls from ( 000 ) 000 - 0000 . 3913 calls reported from this number . according to 4 reports the identity of this caller is american airlines .
  • 段落2: do you want to find out who called you from +1 000 - 000 - 0000 , +1 0000000000 or ( 000 ) 000 - 0000 ? see reports and share information you have about this caller
  • 段落3: allina health clinic patients for your convenience , you can pay your allina health clinic bill online . pay your clinic bill now , question and answers…

该三联体(triplets)被划分为三个数据集:80%训练,10%验证,10%测试。任何方法都需要在训练集上学习,而超参数的选择则在验证集上选择。

我们对4种方法做benchmark,并计算段落的特征:bag-of-words, bag-of-bigrams, 对词向量求平均,对Paragraph Vector求平均。为了提升bag-of-bigrams,我们也学到了一个加权的martix:前2个的距离最小化,第1个和第3个段落的距离最大化(两个losses间的加权因子是个hyperparameter)

当每个方法中,两个段落的距离越来越小,第一个和第三个段落的距离越来越大时,我们记录了对应的时间数。如果方法不生成期望的结果,会出来一个error。

Paragraph Vector的结果和其它baseline如表3所示。在该任务中,我们发现,TF-IDF的加权效果比raw counts要好,因此,我们只上报了TF-IDF weighting方法。

结果展示了Paragraph Vector工作良好,在error-rate给出了一个32%的相对提升。实际上,paragraph-vector的方法好于bag-of-words以及bag-of-bigrams。

3.4 一些进一步观察

  • PV-DM比PV-DBOW的一致性要好。单独使用PV-DM达到的效果与本paper中的许多结果相接近(见表2)。例如,在IMDB上,PV-DM只达到了7.63%。PV-DM与PV-DBOW合一起更好一些(7.42%),因而推荐使用。
  • 在PV-DM中使用串联(concatenation),通常比求和(sum)更好。
  • 对window-size进行cross-validate更好。许多应用的window size在:5-12之间.
  • Paragraph Vector的计算开销大,但可以在测试时并行完成。平均的,我们的实现花了30分钟来计算IMDB测试集的paragraph vector,使用16-core机器(2.5W文档,每个文档平均230个词)

4.实现

4.1 gensim实现

gensim的models.doc2vec实现了该模型。

class gensim.models.doc2vec.Doc2Vec(documents=None, 
	dm_mean=None, 
	dm=1, 
	dbow_words=0, 
	dm_concat=0, 
	dm_tag_count=1, 
	docvecs=None, 
	docvecs_mapfile=None, 
	comment=None, 
	trim_rule=None, 
	**kwargs)

它的基类是gensim中的: gensim.models.word2vec.Word2Vec

  • documents:一个元素为TaggedDocument的list,对于更大的语料可以使用磁盘/网络。如果不提供documents,则模型会未初始化。
  • dm: 缺省为1. dm=1,表示使用PV-DM。否则使用PV-DBOW.
  • size: 特征向量的维度(基类中)
  • window: 要预测的词与上下文间的最大距离,用于文档中的预测
  • alpha: 初始的learning-rate(随着训练的进行,会线性降至0)
  • seed: 用于随机数字生成器。注意,对于一个完整的确定可再生的运行过程,你必须将该模型限制到单个worker线程上, 以便消除OS线程调度引起的时序抖动。(在python 3中,不同解释器加载之间可再生也需要使用PYTHONHASHSEED环境变量来控制hash随机化)
  • min_count: 忽略总频率低于该值的所有词
  • max_vocab_size: 在词汇表构建时的最大RAM限制; 如果有许多单个的词超过该值,会对频率低的进行剪枝。每1000w的词类型,需要大概1GB的RAM。缺省设为None,即无限制。
  • sample: 配置的阀值,更高频的词会随机下采样(random downsampled)。缺省为0(off), 有用的值为1e-5.
  • workers: 使用多个worker线程来训练模型(多核机器更快)
  • iter: 在语料上的迭代次数(epoches)。缺省值从Word2Vec继承下来,为5. 但对于’Paragraph Vector’来说,10或20更常用。
  • hs: 如果为1, 表示使用hierarchical sampling来进行模型训练,否则为0. 缺省为1
  • negative: 如果>0, 会使用negative sampling,int值表示应抽样“noise words”多少次。(通常设在5-20间)
  • dm_mean: 如果为0(缺省情况), 会使用上下文的词向量的求和(sum)。如果为1,则使用求平均(mean)。如果dm以非级联(non-concatenative)的模式,才会使用它。
  • dm_concat: 如果为1,则使用上下文向量的级联方式(concatenation),而非(sum/average)方式;缺省为0(off)。注意,级联(concatenation)会导致一个大的多的模型,输入不再是一个词向量(被抽样出或者算术结合)的size,而是使用该tag(s)的size和上下文中的所有词捆在一起。
  • dm_tag_count: 当使用dm_concat模式时,每个文档所期望常数个文档标签;缺省为1
  • dbow_words: 如果设置为1, 则会训练word-vectors(以skip-gram的方式),同时训练DBOW的doc-vector;缺省为0(只训练doc-vectors训练会更快)
  • trim_rule: 词汇表剪枝规则,指定了特定的词是否应保留在词汇表中,是否被削剪掉,或者使用缺省方式处理(如果词的count<min_count,直接抛弃). 可以置为None(即使用min_count),或者使用一个回调,使用参数(word,count,min_count),返回下述值:util.RULE_DISCARD, util.RULE_KEEP or util.RULE_DEFAULT. 注意:如果给定该规则,会使用它在build_vocab()期间来剪枝词汇表,不会被当成是模型的一部分进行保存。

另几个比较重要的函数:

  • delete_temporary_training_data(keep_doctags_vectors=True, keep_inference=True)

抛弃在训练时和评分时用到的参数。如果你确认模型训练完了,就可以使用它。keep_doctags_vectors=False,不会保存doctags向量,这种情况下,不可以使用most_similar进行相似度判断。keep_inference=False表示,你不希望保存用于infer_vector的参数.

相应的示例代码,可以参见:

二、Tomas Mikolov的c实现

Tomas Mikolov在https://groups.google.com/forum/#!msg/word2vec-toolkit/Q49FIrNOQRo/J6KG8mUj45sJ处提供了他的sentence2vec的实现。

  • cbow=0: 表示PV-DBOW.

三、其它实现

https://github.com/zseymour/phrase2vec

参考