Huffman Tree

Huffman Tree

Huffman Tree的构建

定义

哈夫曼树

给定n个权值作为n个子节点,构建一颗二叉树,若该树的带权路径长度最小,则此树为哈夫曼树。

结点的带权路径长度

对于一个结点:

结点的带权路径长度 = 该结点的路径长度*该结点权值 = $w_k * l_k$

树的带权路径长度

n个结点带权路径之和

树的带权路径长度 = $\sum_{k=1}^{n}w_kl_k$

构建

构建方法:

  1. 从下往上构建,倒数第一层,选取两个权值最小的值,构建左右树,小的在左,大的在右,构成新的二叉树,该二叉树结点值为两个权值之和。同一层,再选除了这两个之外最小的,构建二叉树。
  2. 倒数第二层,选两个新的最小的二叉树结点值,构建新的二叉树,重复。
  3. 直到构建到顶部。

例子1

例子2

Word2vec中的哈夫曼树

假设word2vec的最后面构建了一个Huffman Tree,这个Tree点叶结点是词汇表的没个词,为N个。构建的方法为按照词等频次进行构建。

那么对于每一个词,从根节点算上去,向左为1,向右为0。那么每一个词,其实都是有唯一的一个编码表示,例如:的=’010011’。

假设word2vec的最后一层,有K个神经元。

K个神经中的每一个,与每一个内接点(分叉口)相连。有参数$w$来影响这个结点往左走还是往右走。也就是对于每一内接点,向左为$P_i$,向右为$1 - P_i$。

当CBOW或者SKIP-GRAM,我们根据上下文,来预测 ‘的’ 的时候,可以根据K个神经元,连接内接点的目前的参数,算出’010011’的概率为:$w(n) = \prod_0^{i}Pi \ or\ (1-Pi)$

那么损失函数就是:
$$
1 - w(n)
$$
也就可以通过SGD来训练word2vec和huffman Tree中的参数了。

如果不用Huffman Tree,计算复杂度为O(N),但是用了Huffman Tree之后,计算复杂度为O(long2(N))