哈夫曼树Huffman tree

哈夫曼树Huffman tree 一句话解释，哈夫曼树将一个softmax的多分类问题转换成了多个logistic的二分类问题 以连续词袋模型（CBOW）为例，输入多个词向量，输出层则输出最可能的w，最简的实现自然是softmax，但为了计算难度，使用哈夫曼树简化计算 p w p^wp w 为从根节点到词汇w 叶子节点对应的路径 d j w {d_j^w}d j w 表示p w p^wp w 中第j个节点对应的编码，而θ 1 w \theta^w_1θ 1 w 表示路径p w p^wp w 中的参数向量 根据上述定义，我们可以写出基于Hierarchical Softmax优化的连续词袋模型（CBOW）的条件概率： p ( w ∣ context ( w ) ) = ∏ j = 1 I w p ( d j w ∣ x w ; θ j − 1 w ) 其中，每一项都是一个Logistic回归 后半部分略去，有想法在写 负采样优化每次采样一小部分，更新一个训练样本的一小部分权重

Logistic回归 用sigmoid函数模拟阶跃函数，sigmoid函数即： σ = 1 1 + e − z = 1 1 + e − w T x \sigma =\frac{1}{1+e^{{-z}}=\frac{1}{1+e}{-w^T x}}σ= 1+e −z

1 = 1+e −w T x

1

定义对数几率为l n y 1 − y = w T x ln\frac{y}{1-y}=w^T xln 1−y y =w T x 显然，y可视为正例的概率，1-y为负例的概率则 p ( y = 1 ) = e w T x 1 + e w T x = 1 1 + e − w T x = σ p(y=1)=\frac{e^{wT x}}{1+e^{wT x}}=\frac{1}{1+e^{-wT x}}=\sigmap(y=1)= 1+e w T x

e w T x

= 1+e −w T x

1 =σ 则p ( y = 0 ) = 1 − σ p(y=0)=1-\sigmap(y=0)=1−σ 用梯度上升算法进行Logistic回归 w = w + ∇ f ( w ) w=w+\nabla{f(w)}w=w+∇f(w)