当前位置 博文首页 > dastu的博客:深入理解Hierarchical Softmax机制
Hierarchical Softmax是利用哈夫曼树结构来减少计算量的一种方式。由word2vec论文应用,
能够加快模型的训练速度。
原始在word2vec中提到的计算条件概率的公式为:
P ( v ∣ v i ) = e x p ( ( v ′ ) T ? v i ) ∑ w = 1 W e x p ( v w ′ ? v i ) P(v| v_i) =\frac{exp((v')^{T} *v_i)}{\sum_{w=1}^{W} exp(v'_w*v_i)} P(v∣vi?)=∑w=1W?exp(vw′??vi?)exp((v′)T?vi?)?
但是,分母部分需要遍历所有的word,显然是一个非常耗时的操作。假设词库里有W个单词,
那么时间复杂度将会是O(W),W一般来说会非常大(因为单词数往往会很大)。
利用Hierarchical Softmax可以很大程度减少时间复杂度。
Hierarchical Softmax的思想是利用哈夫曼树。这里和逻辑回归做多分类是一样的。
One VS Rest
将class1看作正样本,其他全部看作负样本,训练第一个分类器C1;
接着将class2看作正样本,其他类型(包括class1)全部看作负样本,同理得到分类器C2;
以此循环,我们可以得到n个分类器(n为类别数)。
这时每个分类器 i i i 都有参数 w i w_i wi? 和 b i b_i bi?,利用Softmax函数来对样本x做分类。
分为第i类的概率为: p ( X = k ) = e x p ( w i T ? x k + b ) ∑ j = 1 n e x p ( w j T ? x k + b ) p(X=k)=\frac{exp(w_i^T*x_k+b)}{\sum_{j=1}^n exp(w_j^T*x_k+b)} p(X=k)=∑j=1n?exp(wjT??xk?+b)exp(wiT??xk?+b)?
在Hierarchical中,将word以词频作为哈夫曼树的权值来构建哈夫曼树,
这样经常出现的单词路径就会更短。
哈夫曼树是一种二叉树,实际上就是在不断的做二分类,哈夫曼树每一层的分类就是做One VS Rest。
以下图为例,当需要查找到单词 C C C时,从根节点开始做二分类,判断往左还是往右,得到往右的概率为 p 1 = 1 ? 1 1 + e x p ( w d x + b d ) p1=1-\frac{1}{1+exp(w_dx+b_d)} p1=1?1+exp(wd?x+bd?)1?, 到达节点14,继续判断往右的概率为 p 2 = 1 ? 1 1 + e x p ( w b x + b b ) p2=1-\frac{1}{1+exp(w_bx+b_b)} p2=1?1+exp(wb?x+bb?)1?,到达节点7,判断往左的概率为 p 3 = 1 1 + e x p ( w c x + b c ) p3=\frac{1}{1+exp(w_cx+b_c)} p3=