1.泊松分布与挖矿问题

泊松分布

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

1.1 问题

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

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

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

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

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

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

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

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

1.2 解释

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

速率λ(即:每秒能挖到多少个区块)为:

  • 单人在t时间内挖到的区块数目期望:
  • 单人在t时间内挖到的区块数目方差:

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

根据期望和方差的性质:

  • C为常数,X为随机变量
  • 期望性质:
  • 方差性质:

从而,我们得到:

单人在t时间内对应回报的期望为:

单人在t时间内对应回报的方差为:

单人在t时间内对应回报的标准差为:

单人在t时间内对应回报的标准差/期望(标准差是期望的多少倍)为:

1.3 进一步

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

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

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

矿池将在周期t内获得的区块数期望:

矿池将在周期t内获得的区块数方差:

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

矿池在周期t内获得的btc期望:

矿池在周期t内获得的btc方差:

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

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

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

在矿池中,个人在周期t内获得的btc期望: ,该值与solo模式一样

在矿池中,个人在周期t内获得的btc方差:,是solo模式的q倍。(0<q<1,因而方差变小,风险也变小了)

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

2.1 一般的矿池

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

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

矿池中,单个矿工获得的的实际btc收入的期望为:,与solo模式略有下降(但其实个人挖一样需要支付电费等问题存在)

矿池中,单个矿工获得的的实际btc收入的方差为:,是solo模式的(1-f)^2q倍. 方差更小。

2.2 变态的矿池

PPS矿池就是这样。

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

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

这里有两个问题:

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

先回到原先讲的:

  • 1.矿池中每次hash计算成为一个share的概率:
  • 2.每个share成为合法区块都有一个概率:
  • 3.矿工在每次提交一个share时将平均接收到的回报:pB
  • 4.对于operator则收到的费用:

2.2.1 推导阶段一

如何分配它?

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

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

它的期望为:

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

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

我们再对这个初始条件按因子做一下缩放:

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

2.2.2 推导阶段二

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

表示,从状态n开始要达到0的概率(表示矿池破产)。我们在第一步得到的条件,表示:

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

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

该方程的解为:

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

代入初始值(边界条件):

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

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

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

参考:

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

本文主要译自paper 1.

Abstract

神经网络概率语言模型(NPLM)与过去广泛使用的n-gram语言模型相互竞争,甚至偶尔优于后者。NPLM最大的缺点是训练和测试时间超长。Morin和Bengio提出了一种层次化语言模型,它会构建一棵关于词的二叉树,它比非层次化的使用专家知识的模型快2个数量级。我们引入了一种快速的层次化语言模型,它使用一种简单的基于特征的算法,可以从数据中自动构建word树。我们接着展示,产生的模型胜过非层次化神经网络模型、n-gram模型。

介绍

统计语言模型的关注点是,构建基于词序列的概率模型。这样的模型可以被用于区分可能的序列与不可能的序列,广泛用于语音识别,信息检索,机器翻译。大多数统计语言模型都基于Markov猜想:一个词的分布只依赖于 在它之前出现的固定数目的词。该猜想明显是错误的,但它很简洁方便,因为它将固定长度的词序列的概率分布建模问题,缩减成:给定前面固定数目的词(称为上下文:context),建模下一个词的分布。此处,我们使用:P(wn|w1:n-1)来表示分布,wn是下一个词, w1:n-1表示上下文(w1,..,wn-1)。

目前n-gram模型是最流行的统计语言模型,因为简单,并且性能很好。这些模型的条件概率表,通过统计训练数据中的n元组,并进行归一化进行估计。因为n元组的数据是n的指数级,对raw counts进行平滑会达到很好的性能。n-gram模型有许多平滑方法,详见paper 2. 尽管n-gram模型有许多复杂的平滑方法,n-gram模型很难利用大量上下文,因为数据的稀疏性问题很严重。这种现像的主要原因是,经典的n-gram模型是本质上有界的条件概率表,里面的条目都是相互独立的。这些模型不会利用这样的事实:即相似的词常出现在相似的上下文中,因为它们没有相似性的概率。基于分类的n-gram模型(paper 3)主要解决该问题,通过将词和上下文,基于使用模式聚类到分类中,使用这些分类信息来提升泛化。它会提升n-gram的性能,这种方法引入了严格死板的相似性,因为每个词很典型,都属于确定的某个类。

另一种可选的、更灵活的抵消数据稀疏性问题的方法是,将每个词使用一个real-valued的特征向量,它会捕获该特性,以便相似的上下文中的词,具有相似的特征向量。接着,下一个词的条件概率可以被建模成一个关于上下文词和下一个词的平滑函数。这种方法提供了自动平滑,因为对于一个给定的上下文,相似的词可以保证分配到相似的概率。同样的,相似的上下文现在也可能具有相似的表示,并会生成对下一个词相似的预测。大多数基于该方法的模型,使用一个前馈神经网络(feed-forwark NN),将上下文词汇的特征向量映射到下一个词的分布上。这种方法的可能最好模型是神经网络语言模型NPLM(paper 4),在100w词级别的语料上,它胜过n-gram模型。

层次化神经网络语言模型

NPLM的主要缺点是,这样的相类似模型,训练和测试时间很慢。因为下一个词的概率计算,需要显式对词汇表中所有词进行归一化,对于给定下一个词的概率计算开销,以及对于在下一个词之上的所有分布的计算开销,事实上两者几乎一样:它们会花费关于词汇表size的线性时间开销。由于在这样的模型上,计算精确的梯度,需要重复计算给定上下文的下一个词的概率,通过增加概率来更新模型参数,训练时间与词汇表size成线性关系。通常,自然语言数据集包含着上万的词汇,这意味着即使以最简单方式训练这种类NPLM模型,在实际中的计算开销仍过大。一种加速该过程的方法是,使用专门的重要性sampling过程,来逼近要学习所需的梯度(paper 5)。然而,该方法可以本质上加速训练时间,测试时间的开销依然很快。

我们引入了层次化NPLM(paper 6),对比普通的NPLM,它在训练和测试的时间复杂度均做到了指数级的衰减。通过二叉树替代NPLM中非结构化的词汇表,可以表示成一个层次化的词汇表词簇。每个词对应于树上的叶子节点,可以由顶点到叶子节点的路径唯一确定。如果N是词汇表的词数,并且树是一棵平衡树,任何词都可以由一串O(log N)二分决策来指定,它会指定两个子节点,当前节点可以访问到下一节点。该过程将N-way选择替换成一串O(log N)的二分选择。在概率术语中,N-way归一化,可以替换成一串O(log N)的局部(二分)归一化。结果上,词汇表中的词分布,可以通过提供访问左子节点的概率来指定。在层次化NPLM中,这样NPLM方式的局部概率的计算:采用一个特征向量作为上下文词汇,同时给当前节点的一个特征向量作为输入。下一个词的概率,由该词所对应路径的二分决策的概率指定。

当数据集包含上百万的词时,该模型的表现优于基于分类的3-gram,但比paper 6中的NPLM表现差。这种层次化NPLM模型,比普通的NPLM快2个数量级。这种方法的主要限制,主要是用于构建word树的过程。该树可以从WordNet IS-A分类体系开始,通过结合人工和数据驱动处理,并将它转换成一个二叉树。我们的目标是,将该过程替换成从训练数据中自动构建树,不需要任何专家知识。我们也探索了使用树(里面的词汇至少出现一次)的性能优点。

log-bilinear model

我们使用log-bilinear语言模型(LBL:Paper 7)作为我们层次化模型的基础,因为它的性能十分出色,并且很简洁。类似于所有神经网络语言模型,LBL模型将每个词表示成一个real-valued的特征向量。我们将词w的特征向量表示成:,所有词的特征向量组成矩阵R. 模型的目标:给定上下文w1:n-1,预测下一个词wn。我们将要预测下一个词的的特征向量表示成,它可以通过对上下文词汇的特征向量进行线性组合得到:

公式一:

其中,Ci是权重矩阵,它与位置i的上下文有关。接着,要预测的特征向量,和词汇表中每个词的特征向量,两者间的相似度通过内积计算。该相似度接着进行指数化,归一化,从而获取下一个词的分布:

公式二:

这里的bw是词w的偏置bias,它被用于捕获上下文独立的词频。

注意,LBL模型可以被解释成一种特殊的前馈神经网络,它只有一个线性隐层,以及一个softmax输出层。该网络的输入是上下文词汇的特征向量,而从隐层到输出层的权重矩阵,则可以简单通过特征向量矩阵R指定。该向量隐单元的激活,对应于下一个词的预测特征向量。不同于NPLM,LBL模型需要计算隐层激活,每次预测只计算一次,隐层不存在非线性。虽然LBL模型很简单,但表现很好,在相当大的数据集上,优于NPLM和n-gram模型。

4.层次化log-bilinear模型

我们的层次化语言模型基于该模型. 该模型的特点是,使用log-bilinear语言模型来计算每个节点的概率,并处理树中每个词多次出现率。注意,使用多个词出现率的思想,由papar 6提出,但它并没有实现。

HLBL的第一个组件是一棵关于词作为叶子的二叉树。接着,我们假设词汇表中每个词对应一个叶子结点。接着,每个词可以通过从树顶点到叶子节点的路径唯一指定。该路径本身可以编码成一串二进制字符串d(每个节点会做二分决策),对应于:访问当前节点的左子节点。例如,字符串”10”表示的是:从顶点,到左子节点,然后到右子节点。这样,每个词可以被表示成一串二进制码。

HLBL模型的第二个组件是,每个节点会做出二分决策的概率模型,在我们的case中,使用了一个LBL模型的改进版本。在HLBL模型中,和非层次化的LBL类似,上下文词汇表示成real-valued特征向量。树上的每个非叶子节点,也具有一个特征向量与它相关联,它用于区分词是在该节点的左子树还是在右子树。不同于上下文词汇,被预测的词,被表示成使用它们的二进制码。然而,这种表示相当灵活,因为编码中的每种二进制数字,相当于该节点做出的决策,它依赖于节点的特征向量。

在HLBL模型中,给定上下文,下一个词是w的概率,就是由该词编码指定的一串二分决策的概率。因为在一个节点上做出一个决策的概率,只取决于要预测的特征向量(由上下文决定),以及该节点的特征向量,我们可以将下一个词的概率表示成二分决策的概率乘积:

公式三:

di是词汇w的第i位数字编码,qi是编码所对应路径上第i个节点的特征向量。每个决策的概率为:

公式四:

其中,是logistic函数,而是使用公式一计算得到的要预测的特征向量,在该公式中的bi是该节点的偏置bias,它可以捕获当离开该节点到它的左子节点上的上下文独立的趋势。

D(w)表示词汇w所对应的一串编码集合。每个词允许多个编码,可以更好地预测词,具有多种含义或者多种使用模式。每个词使用多种编码,也可以使它更容易将多种不同的词层次结构,组合成单一的结构。这也反映了一个事实:没有单一的层次结构可以表示词之间的所有关系。

使用LBL模型(而非NPLM)来计算局部概率,允许我们避免计算隐层的非线性,这可以让我们的层次模型,比层次化NPLM模型更快作出预测。更重要的是,对于O(log N)个决策中的每一个,层次化NPLM都需要计算一次隐层激活,而HLBL模型只在每次预测时计算一次要预测的特征向量。然而,在LBL模型中,单个二分决策的概率计算的时间复杂性,仍然是特征向量维度D的二次方,这会使高维特征向量的计算开销很高昂。我们可以使时间复杂度与D是线性关系,通过将权重矩阵Ci限制为对角阵。注意,对于上下文size=1的情况,该限制条件不会减小模型表示的幂(power),我们相信,这种损失(loss),多于可以通过使用更复杂的树更快的训练时间的补偿。

HLBL模型可以通过最大化(带罚项的)log似然进行训练。因为下一个词的概率只依赖于上下文权重、上下文词汇的特征向量、以及从顶点到词汇所在叶子节点路径上的节点的特征向量,在每个训练case上,只有一小部分(log级别)的参数需要更新。

参考

介绍

Mikolov在paperDistributed Representations of Words and Phrases and their Compositionality中,提到高频词的subsampling问题,以下我对相关节选进行的简单中文翻译:

在非常大的语料中,最高频的词汇,可能出现上百万次(比如:in, the, a这些词)。这样的词汇通常比其它罕见词提供了更少的信息量。例如,当skip-gram模型,通过观察”France”和”Paris”的共现率(co-occurrence),Skip-gram模型可以从中获益;而”France”和”the”的共现率则对模型贡献很少;而几乎每个词都常在句子中与”the”共同出现过。该思路也常用在相反的方向上,高频词的向量表示,在上百万样本训练完后不会出现大变化。

为了度量这种罕见词与高频词间存在不平衡现象,我们使用一个简单的subsampling方法:训练集中的每个词wi,以下面公式计算得到的概率进行抛弃:

f(wi)是wi的词频,t为选中的一个阀值,通常为10^-5周围(0.00001)。我们之所以选择该subsampling公式,是因为:它可以很大胆的对那些词频大于t的词进行subsampling,并保留词频的排序(ranking of the frequencies)。尽管subsampling公式的选择是拍脑袋出来的(启发式的heuristically),我们发现它在实践中很有效。它加速了学习,并极大改善了罕见词的学习向量的准确率(accuracy)。

具体实现

有道之前的中,提到的该subsampling描述也不准确。在当中的描述是:

而实际中,采用的是:

部分代码:

// 进行subsampling,随机丢弃常见词,保持相同的频率排序ranking.
// The subsampling randomly discards frequent words while keeping the ranking same
if (sample > 0) {

  // 计算相应的抛弃概率ran.
  real ran = (sqrt(vocab[word].cn / (sample * train_words)) + 1) * (sample * train_words) / vocab[word].cn;

  // 生成一个随机数next_random.
  next_random = next_random * (unsigned long long)25214903917 + 11;

  // 如果random/65535 - ran > 0, 则抛弃该词,继续
  if (ran < (next_random & 0xFFFF) / (real)65536) 
      continue;
}

为此,我简单地写了一个python程序,做了个测试。程序托管在github上,点击下载

下面提供了三种方法,最终生成的图可以看下。对于前两种方法,基本能做到与原先词频正相关,最后使用时,需要设置一个阀值,砍掉高频词。而最后一种方法,效果也不错(虽然偶有会存留高频词,或者低频词也同样被砍掉)。而word2vec采用的正是第3种方法。

介绍

如果你在大学期间学过信息论或数据压缩相关课程,一定会了解Huffman Tree。建议首先在wikipedia上重新温习下Huffman编码与Huffman Tree的基本概念: Huffman编码wiki

简单的说(对于文本中的字母或词),Huffman编码会将出现频率较高(也可认为是:权重较大)的字(或词)编码成短码,而将罕见的字(或词)编码成长码。对比长度一致的编码,能大幅提升压缩比例。

而Huffman树指的就是这种带权路径长度最短的二叉树。权指的就是权重W(比如上面的词频);路径指的是:从根节点到叶子节点的路径长度L;带权路径指的是:树中所有的叶结点的权值乘上其到根结点的路径长度。WPL=∑W*L,它是最小的。

word2vec的Huffman-Tree实现

为便于word2vec的Huffman-Tree实现,我已经将它单独剥离出来,具体代码托管到github上: huffman_tree代码下载。示例采用的是wikipedia上的字母:

即:F:2, O:3, R:4, G:4, E:5, T:7

这里有两个个注意事项:

  • 1.对于单个节点分枝的编码,wikipedia上的1/0分配是定死的:即左为0,右为1(但其实分左右是相对的,左可以调到右,右也可以调到左)。而word2vec采用的方法是,两侧中哪一侧的值较大则为1,值较小的为0。
  • 2.word2vec会对词汇表中的词汇预先从大到小排好序,然后再去创建Huffman树。在CreateBinaryTree()调用后,会生成最优的带权路径最优的Huffman-Tree。

最终生成的图如下:

此图中,我故意将右边的T和RG父结节调了下左右,这样可以跳出上面的误区(即左为0,右为1。其实是按大小来判断0/1)

相应的数据结构为:

/**
 * word与Huffman树编码
 */
struct vocab_word {
  long long cn;     // 词在训练集中的词频率
  int *point;       // 编码的节点路径
  char *word,       // 词
       *code,       // Huffman编码,0、1串
       codelen;     // Huffman编码长度
};

最后,上面链接代码得到的结果:

1
2
3
4
5
6
word=T	cn=7	codelen=2	code=10	point=4-3-
word=E	cn=5	codelen=2	code=01	point=4-2-
word=G	cn=4	codelen=3	code=111	point=4-3-1-
word=R	cn=4	codelen=3	code=110	point=4-3-1-
word=O	cn=3	codelen=3	code=001	point=4-2-0-
word=F	cn=2	codelen=3	code=000	point=4-2-0-

整个计算过程设计的比较精巧。使用了三个数组:count[]/binary[]/parent_node[],这三个数组构成相应的Huffman二叉树。有vocab_size个叶子节点。最坏情况下,每个节点下都有一个叶子节点,二叉树的总节点数为vocab_size * 2 - 1就够用了。代码使用的是 vocab_size * 2 + 1。

当然,如果你有兴趣关注下整棵树的构建过程的话,也可以留意下这部分输出:

count[]:	7 5 4 4 3 2 1000000000000000 1000000000000000 1000000000000000 1000000000000000 1000000000000000 1000000000000000
binary[]:	0 0 0 0 0 0 0 0 0 0 0 0
parent[]:	0 0 0 0 0 0 0 0 0 0 0 0
	
--step 1:
count[]:	7 5 4 4 3 2 5 1000000000000000 1000000000000000 1000000000000000 1000000000000000 1000000000000000
binary[]:	0 0 0 0 1 0 0 0 0 0 0 0
parent[]:	0 0 0 0 6 6 0 0 0 0 0 0
	
--step 2:
count[]:	7 5 4 4 3 2 5 8 1000000000000000 1000000000000000 1000000000000000 1000000000000000
binary[]:	0 0 1 0 1 0 0 0 0 0 0 0
parent[]:	0 0 7 7 6 6 0 0 0 0 0 0
	
--step 3:
count[]:	7 5 4 4 3 2 5 8 10 1000000000000000 1000000000000000 1000000000000000
binary[]:	0 1 1 0 1 0 0 0 0 0 0 0
parent[]:	0 8 7 7 6 6 8 0 0 0 0 0
	
--step 4:
count[]:	7 5 4 4 3 2 5 8 10 15 1000000000000000 1000000000000000
binary[]:	0 1 1 0 1 0 0 1 0 0 0 0
parent[]:	9 8 7 7 6 6 8 9 0 0 0 0
	
--step 5:
count[]:	7 5 4 4 3 2 5 8 10 15 25 1000000000000000
binary[]:	0 1 1 0 1 0 0 1 0 1 0 0
parent[]:	9 8 7 7 6 6 8 9 10 10 0 0

参考

1.Huffman编码

机器学习中的许多模型中,对类别型变量,常作的处理是,将它们编码成one-hot。但是对于树模型来说,将类别型变量编码成one-hot,这样作是否有意义呢?像一些机器学习工具包(比如:spark gbm实现),你可以指定为类别型变量,内部自己去做one-hot实现。而像xgboost,则将输入全认为是数值型特征去处理。

一、要不要one-hot?

这在机器学习界也有争论。理论上,树模型如果够深,也能将关键的类别型特型切出来。

关于这个,xgboost的作者tqchen在某个issues有提到过:

I do not know what you mean by vector. xgboost treat every input feature as numerical, with support for missing values and sparsity. The decision is at the user

So if you want ordered variables, you can transform the variables into numerical levels(say age). Or if you prefer treat it as categorical variable, do one hot encoding.

在另一个issues上也提到过(tqchen commented on 8 May 2015):

One-hot encoding could be helpful when the number of categories are small( in level of 10 to 100). In such case one-hot encoding can discover interesting interactions like (gender=male) AND (job = teacher).

While ordering them makes it harder to be discovered(need two split on job). However, indeed there is not a unified way handling categorical features in trees, and usually what tree was really good at was ordered continuous features anyway..

总结起来的结论,大至两条:

  • 1.对于类别有序的类别型变量,比如age等,当成数值型变量处理可以的。对于非类别有序的类别型变量,推荐one-hot。但是one-hot会增加内存开销以及训练时间开销。
  • 2.类别型变量在范围较小时(tqchen给出的是[10,100]范围内)推荐使用

二、one-hot的一致性问题

当你进行one-hot编码时,有些机器学习工具包内置的one-hot编码工具会帮你做这些事,但是真实的情况是,我们有数据集有如下分类:训练集、测试集、预测集(真实数据)等。

这些数据集并不会统一,比如:

训练集上A特征有: a,b,c,d,测试集上A特征有:a,b,d,预测集上可能有b,c,e,f

因此,你需要做的是,将它们统一使用one-hot编码,而非分开做不同的one-hot编码.

参考