【NLP】小结：fasttext模型中的层次softmax策略

一. fasttext介绍

1. fasttext的作用

作为NLP工程领域常用的工具包, fasttext有两大作用:

• 进行文本分类
• 训练词向量

2. fasttext的优势

在保持较高精度的前提下, 快速的进行训练和预测是fasttext的最大优势。
fasttext有上述优势的原因可以简单总结为以下几点:

• fasttext工具包中内含的fasttext模型具有十分简单的网络结构；
• 使用fasttext模型训练词向量时使用层次softmax策略, 来提升超多类别下的模型性能；
• 由于fasttext模型过于简单无法捕捉词序特征, 因此会进行n-gram特征提取以弥补模型缺陷提升精度。

下面就对其中的“层次softmax策略”做一些说明。

二. 层次softmax策略

首先，一句话概括：层次softmax（Hierarchical Softmax）是一种优化softmax运算的策略，在训练词嵌入模型（如word2vec）时用于减少计算复杂度。它通过构建一个二叉树结构（通常是哈夫曼（Huffman）树，根据词频进行编码）来代替一次性计算所有词的概率分布。
具体来说，在word2vec中，传统的softmax函数需要计算词汇表中所有词的概率分布，时间复杂度随词汇表大小线性增长（O(N)，N为词汇表大小），对于大规模词汇表而言非常耗时。
而层次softmax则通过构建一个哈夫曼树来替代直接的softmax层。在这个哈夫曼树中，每个叶子节点代表词汇表中的一个词，且高频词对应的节点距离根节点更近，从而使得计算该词的概率时所需经过的节点更少，大大减少了计算量。
使用层次化softmax之后时间复杂度的log(N) (二叉树的高度和宽度的近似), 从而在多分类的场景提高了效率。
因此，可以说层次softmax是结合了哈夫曼编码思想的一种算法设计，它并不是哈夫曼树本身，而是利用哈夫曼树来实现对softmax函数的有效优化。

三. 层次softmax与普通softmax的区别与联系

层次softmax与普通softmax都是在神经网络中用于处理多分类问题时的输出层非线性函数，它们的主要区别在于计算效率和表达形式上：

3.1 普通softmax

1. 定义：普通softmax函数接收一个向量作为输入，并将其转换为一个归一化的概率分布。每个输入单元对应一个类别，输出的是属于各个类别的概率值，且所有类别的概率和为1。
   公式表示为：
   
   其中，z 是输入向量经过权重矩阵变换后的值，K 是类别总数。

2. 计算复杂度：普通softmax需要计算所有类别的指数函数并求和，因此当类别数非常多时（如在自然语言处理中的词汇表大小），计算量较大且耗时。

3.2 层次softmax

1. 结构：层次softmax是一种优化策略，它通过构建一棵哈夫曼树（通常是根据词频构建的平衡树）来减少计算量。每个类别作为一个叶子节点，从根节点到每个叶子节点有一条唯一的路径。
2. 计算过程：不是直接计算所有类别的softmax概率，而是通过沿着从根节点到目标类别叶子节点的路径上的内部节点执行一系列二元分类任务，每次分类仅涉及两个分支，从而大大减少了计算次数。
3. 效率：层次softmax显著降低了计算复杂度，从原来的O(K)降低至接近O(log₂K)，尤其是在处理大规模词汇表时效果明显。
4. 不足：虽然计算效率提高了，但是层次softmax引入了额外的模型参数，即哈夫曼树的内部节点权重，这可能增加了模型的学习和优化难度。

所以，两者之间的联系在于都是用于概率预测和多分类任务；而区别主要体现在优化方法和计算效率上，层次softmax是针对普通softmax在大规模分类问题上效率不高的改良版本。在实践中，如果类别数量不大或者计算资源充足，一般使用普通softmax；而在类别数量极大且计算资源有限的情况下，层次softmax是一个更为高效的替代方案。随着计算硬件的发展和注意力机制等新型解决方案的提出，例如在Transformer模型中，往往会采用其他策略如稀疏注意力或自适应softmax来进一步优化大规模分类问题的计算效率。

四. 层次softmax的计算过程

层次softmax的基本计算过程如下：

1. 构建哈夫曼树：

• 根据词汇表中词的频率构建一棵哈夫曼树，高频词被分配到较短的路径上，低频词则位于较长的路径上；
• 每个词汇表中的词映射到哈夫曼树的一个叶子节点。

2. 计算概率：
   对于给定的中心词和目标词（上下文词）：

• 输入中心词的向量表示，经过隐藏层计算后得到一个向量;
• 从根节点开始，沿树向下遍历：
  • 对于每个内部节点，向量会被用来计算左孩子节点和右孩子节点的条件概率；
  • 使用二元逻辑回归或sigmoid函数来进行二分类决策，决定应该走左分支还是右分支；
  • 沿着目标词对应的路径，重复上述步骤，直到抵达目标词所在的叶子节点。

3. 损失函数和梯度计算：

• 目标词的预测概率是沿路径上所有内部节点预测结果的乘积；
• 损失函数是基于负对数似然（Negative Log-Likelihood, NLL）计算的，即对于目标词路径的所有节点的负对数概率之和；
• 梯度通过反向传播法沿着从叶子节点到根节点的路径逐级计算，更新对应的内部节点和输入向量的权重。

通过这种方式，层次softmax不需要对词汇表中所有词进行一次完整的softmax运算，而只需进行与树高度相关的几次二分类操作，因此极大地减少了计算量。