NLP

Word2Vec源码分析

前面分析了 Word2Vec 的原理，下面就结合具体的 java代码实现 来分析这些过程。

源码下载地址: https://github.com/yao8839836/doc2vec_java

导入eclipse工程后目录结构为:

---

分析入口

我们之间运行 test 包下的 Word2VecTest.java 类；输出结果如下:

alpha:0.025 Progress: 0%
alpha:0.02478179420538269   Progress: 0%
alpha:0.024563522955572507  Progress: 1%
......
alpha:5.556709506363112E-4  Progress: 97%
alpha:3.3718151684991317E-4 Progress: 98%
Vocab size: 5574
Words in train file: 1145821
sucess train over!
......

我们先看看该测试类的 main() 方法:

//语料库
File result = new File("file//amazon_docs.txt");
//word2vec 学习器
Learn lean = new Learn();
//训练模型
lean.learnFile(result);
//保存模型
lean.saveModel(new File("model//amazon_vector.mod"));
//重新加载模型喂给其他算法
Word2VEC w2v = new Word2VEC();
w2v.loadJavaModel("model//amazon_vector.mod");
//获取单词 "windows" 的词向量
float[] vector = w2v.getWordVector("windows");

如上面注释所示，核心步就是第 5 行和第 7 行.

下面我们分别来分析.

---

学习器的构造

学习器的构造方法里主要做了一件事就是初始化 $e^x$ 的近似 ，以后可通过查表法快速的求解出 $e^x$ 的近似.

/**
 * Precompute the exp() table f(x) = x / (x + 1)
 */
private void createExpTable() {
    for (int i = 0; i < EXP_TABLE_SIZE; i++) {
        expTable[i] = Math
                    .exp(((i / (double) EXP_TABLE_SIZE * 2 - 1) * MAX_EXP));
        //防止分母为 0
        expTable[i] = expTable[i] / (expTable[i] + 1);
    }
}

我们知道 $e^x$ 曲线是在 0 的附近变换比较剧烈，差不多当 $> 6$ 或者 $< -6$ 的时候基本保持不变了，而在计算机内计算 $e^x$ 的原理是按它的泰勒展开来近似:

$$e^x = 1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots$$ 当展开的阶数比较高时，计算就比较费时了.

于是我们可以利用如下公式近似:

$$\begin{array} & \sigma(x) &\approx& \begin{cases} 0,& x \leq -6 \\ \sigma(x_k), & x \in (-6,6) \\ 1, & x \geq 6 \end{cases} \\x_k &=& x_0 + i \times h \end{array}$$ 其中 $k = round(\frac{x - x_0}{h})$，$h = \frac{12}{K}$ 为步长，$K$ 为要将 $[-6,6]$ 等距剖分的份数.

结合代码看 x 的取值为:

$$\left( \frac{i}{EXP\_TABLE\_SIZE}*2 - 1 \right) * MAX\_EXP$$
因为 $EXP\_TABLE\_SIZE$ 即为 $K$，$MAX\_EXP = -x_0$，所以 $$(\frac{i}{K}*2 - 1)*(-x_0) = x_0 + i*\frac{2*x_0}{K}$$
该计算公式与上面的理论一致.

---

训练预处理

笔者将正式训练之前的步骤都划分为训练预处理步. 下面代码跟踪到 Learn 类的 learnFile() 方法里.

词典表

由前面的理论可知，要先对语料库中的每个单词根据词频构建一棵 Haffman 树，于是先要对语料库内的单词进行统计，构建词典表.

具体方法实现是在 readVocab(file) 中:

private void readVocab(File file) throws IOException {
    MapCount<String> mc = new MapCount<>();
    //获取每个单词的词频
    try (BufferedReader br = new BufferedReader(new InputStreamReader(
                new FileInputStream(file)))) {
        String temp = null;
        while ((temp = br.readLine()) != null) {
            String[] split = temp.split(" ");
            //统计文件中所有单词数
            trainWordsCount += split.length;
            for (String string : split) {
                mc.add(string);
            }
        }
        br.close();
    }
    for (Entry<String, Integer> element : mc.get().entrySet()) {
        //过滤掉词频过小的单词，阈值为 5
        if (element.getValue() < freqThresold)
            continue;
        //为每个单词创建叶子节点，其中包括词向量
        wordMap.put(element.getKey(), 
            new WordNeuron(element.getKey(),
                element.getValue(), layerSize));
    }
}

其中后半部分会为每个单词创建一个 WordNeuron 对象，构造方法为:

public WordNeuron(String name, int freq, int layerSize) {
    this.name = name;
    this.freq = freq;
    //词向量
    this.syn0 = new double[layerSize];
    Random random = new Random();
    //词向量随机初始化: (rand()/Rand_max - 0.5)/m
    for (int i = 0; i < syn0.length; i++) {
        syn0[i] = (random.nextDouble() - 0.5) / layerSize;
    }
}

这里显示出词向量的初始化是通过公式:

$$syn0 = \frac{[rand()/RAND\_MAX] - 0.5}{m}$$
则初始词向量的分量均落在区间 $[-\frac{0.5}{m},\frac{0.5}{m}]$，这里 $m$ 表示词向量的长度，在代码中为 layerSize .

---

构建 Haffman 树

构建 Haffman 树是这一句:

//根据词频创建 haffman 树
new Haffman(layerSize).make(wordMap.values());

在 Haffman 构造方法中，设置 this.layerSize 为传入的 layerSize，表示 Haffman 树的各个结点的参数向量的维度与词向量相同，这样才能做 $X_w^T \theta$ .

具体来看 make() 方法:

//自动使用自然的顺序排序
//由小到大
private TreeSet<Neuron> set = new TreeSet<>();
public void make(Collection<Neuron> neurons) {
    set.addAll(neurons);
    //只剩一个节点时，表示整棵树已构建完成
    while (set.size() > 1) {
        merger();
    }
}
private void merger() {
    //创建最小的两个节点的父节点
    HiddenNeuron hn = new HiddenNeuron(layerSize);
    //弹出第一个元素（也是最小的）
    Neuron min1 = set.pollFirst();
    //弹出第一个元素（此时也是最小的）
    Neuron min2 = set.pollFirst();
    hn.freq = min1.freq + min2.freq;
    min1.parent = hn;
    min2.parent = hn;
    min1.code = 0;  //左边小的标记为 0
    min2.code = 1;
    set.add(hn);    //将父节点加回数据集
}

通过迭代 merger() 方法，逐步构建最小的两棵子树的父节点，并将该父节点加入到森林中. 一直到森林中只剩下一棵树时，表示 Haffman 树构建完成.

---

构建分类路径

我们知道 Hierarchical Softmax 模型 是在 Haffman树中按照根节点到达叶子节点的路径逐步做二分类来实现的. 于是要先为每个叶子节点构建分类路径.

// 为每个神经元构建分类路径
for (Neuron neuron : wordMap.values()) {
    ((WordNeuron) neuron).makeNeurons();
}

具体到 makeNeurons() 方法:

public List<Neuron> makeNeurons() {
    if (neurons != null) {
        return neurons;
    }
    Neuron neuron = this;
    //根节点到叶子节点路径上所有的非叶子节点
    neurons = new LinkedList<>();
    while ((neuron = neuron.parent) != null) {
        neurons.add(neuron);
    }
    Collections.reverse(neurons);
    // 0 1 编码
    codeArr = new int[neurons.size()];
    //d_j 从第二个开始，i 从 1开始
    for (int i = 1; i < neurons.size(); i++) {
        codeArr[i - 1] = neurons.get(i).code;
    }
    codeArr[codeArr.length - 1] = this.code;
    return neurons;
}

其中 neurons 中的每个元素 neuron 的参数向量可以相当于是一个逻辑回归分类器的参数，而 codeArr 中的 0 1 标号相当于是分类结果.

到这里预处理部分就做完了.

---

训练

训练逻辑主要在 trainModel() 方法中，这里分别实现了 CBOW 模型 和 Skip-gram 模型，后面我们分别来分析.

private void trainModel(File file) throws IOException {
    try (BufferedReader br = new BufferedReader(new InputStreamReader(
                new FileInputStream(file)))) {
        String temp = null;
        long nextRandom = 5;
        //主要用来自适应调整学习率
        int wordCount = 0;
        int lastWordCount = 0;
        int wordCountActual = 0;
        while ((temp = br.readLine()) != null) {
            if (wordCount - lastWordCount > 10000) {
                //已处理的单词数
                wordCountActual += wordCount - lastWordCount;
                lastWordCount = wordCount;
                //自适应学习率
                alpha = startingAlpha
                            * (1 - wordCountActual
                                    / (double) (trainWordsCount + 1));
                //有一个学习率过小阈值
                if (alpha < startingAlpha * 0.0001) {
                    alpha = startingAlpha * 0.0001;
                }
            }
            String[] strs = temp.split(" ");
            //更新处理的单词数
            wordCount += strs.length;
            List<WordNeuron> sentence = new ArrayList<WordNeuron>();
            //上下文采样
            for (int i = 0; i < strs.length; i++) {
                Neuron entry = wordMap.get(strs[i]);
                if (entry == null) {
                    continue;
                }
                if (sample > 0) {
                    double ran = (Math.sqrt(entry.freq
                                / (sample * trainWordsCount)) + 1)
                                * (sample * trainWordsCount) / entry.freq;
                        nextRandom = nextRandom * 25214903917L + 11;
                    //子采样
                    if (ran < (nextRandom & 0xFFFF) / (double) 65536) {
                        continue;
                    }
                }
                sentence.add((WordNeuron) entry);
            }
            //所以这里上下文并不是连续的前后几个单词
            for (int index = 0; index < sentence.size(); index++) {
                nextRandom = nextRandom * 25214903917L + 11;
                //默认使用 Skip-gram模型
                if (isCbow) {
                    // CBOW 模型
                    cbowGram(index, sentence, (int) nextRandom % window);
                } else {
                    // Skip-gram 模型
                    skipGram(index, sentence, (int) nextRandom % window);
                }
            }
        }
        br.close();
    }
}

前面通过单词数的处理进度动态的更新学习率，随着处理的句子越来越多，学习率会逐渐降低，但不会让它一直降低到 0，这里设置了一个阈值，如果学习率 alpha 小于阈值了，就直接将 alpha 设置为阈值 .

中间部分是对当前处理的句子预料做了子采样，以一定的概率去掉词频过高的单词，公式为:

$$prob(w) = 1 - \sqrt{\frac{t}{f(w)}} \\ f(w) = \frac{counter(w)}{\sum_{u \in \cal{D}} counter(u)}, w \in \cal{D}$$ 给定一个词频阈值参数 $t$，词 $w$ 将以 $prob(w)$ 的概率被舍弃.

代码中实现的公式为:

$$prob(w) = 1 - \left( \sqrt{\frac{t}{f(w)}} + \frac{t}{f(w)} \right)$$
具体做法是：假设当前处理词 $w$，先计算 $ran = \sqrt{\frac{t}{f(w)}} + \frac{t}{f(w)}$ 的值，然后产生一个 $(0,1)$ 上的随机数 $r$，如果 $r > ran$，则舍弃词 $w$. 由于在区间 $(0,1)$ 上产生一个大于 $ran$ 的随机数的概率是 $1 - ran$，因此上述做法就等同于以 $1 - ran$ 的概率舍弃词 $w$ .

接下来主要是对上下文中的每个词去调用 CBOW模型 或者 Skip-Gram模型.

---

CBOW模型

CBOW模型的训练方法 cbowGram(int index,list<WordNeuron> sentence,int b) 主要分两步：

• 从输入层到隐藏层
  将上下文其他词的词向量进行累加，然后作为 hierarchical softmax层的输入.

• Hierarchical softmax 层
  逐步从根结点二分类到当前词对应的叶子结点，更新 softmax 的权值矩阵以及单词的词向量.

先来看第一步，输入层到隐藏层:

//隐藏层
for (a = b; a < window * 2 + 1 - b; a++)
    //除当前词
    if (a != window) {
        //上下文窗口内的其他词索引
        c = index - window + a;
        if (c < 0)
            continue;
        if (c >= sentence.size())
            continue;
        last_word = sentence.get(c);
        if (last_word == null)
            continue;
        //将上下文的词向量直接相加
        for (c = 0; c < layerSize; c++)
            neu1[c] += last_word.syn0[c];
    }

这里主要是将上下文窗口内的其他词的词向量进行累加，构成 neu1 向量.

其中需要注意的是 for (a = b; a < window * 2 + 1 - b; a++)，b 是一个随机数，表示要将 window * 2 范围首尾去掉单词的个数，则 a 即在窗口中间左右 window - b 长的范围内变动；c = index -window + a 中 index - window 为 window左边界索引，index -window + a 为去掉 b 长度后上下文窗口变动范围内的单词索引.

第二步 Hierarchical softmax 层:

// HIERARCHICAL SOFTMAX
for (int d = 0; d < neurons.size(); d++) {
    HiddenNeuron out = (HiddenNeuron) neurons.get(d);
    double f = 0;
    // Propagate hidden -> output
    //先计算 X^T * theta
    for (c = 0; c < layerSize; c++)
        f += neu1[c] * out.syn1[c];
    //查 e^x 的近似表
    if (f <= -MAX_EXP)
        continue;
    else if (f >= MAX_EXP)
        continue;
    else{
        //这步没看明白为什么这么写
        f = expTable[(int) ((f + MAX_EXP) * (EXP_TABLE_SIZE / MAX_EXP / 2))];
    }
    //计算梯度 g
    // 'g' is the gradient multiplied by the learning rate
    // double g = (1 - word.codeArr[d] - f) * alpha;
    // double g = f*(1-f)*( word.codeArr[i] - f) * alpha;
    double g = f * (1 - f) * (word.codeArr[d] - f) * alpha;
    //更新 e
    for (c = 0; c < layerSize; c++) {
        neu1e[c] += g * out.syn1[c];
    }
    //更新softmax 非叶子节点的参数向量 theta
    // Learn weights hidden -> output
    for (c = 0; c < layerSize; c++) {
        out.syn1[c] += g * neu1[c];
    }
}
for (a = b; a < window * 2 + 1 - b; a++) {
    if (a != window) {
        c = index - window + a;
        if (c < 0)
            continue;
        if (c >= sentence.size())
            continue;
        last_word = sentence.get(c);
        if (last_word == null)
            continue;
        //更新 V(w) 词向量
        for (c = 0; c < layerSize; c++)
            last_word.syn0[c] += neu1e[c];
    }
}

先回顾前面的理论部分描述的算法过程:

先计算 $X_w^T \theta_{j-1}^w$ ，然后计算 $\sigma(z) = e^z$，不过源码中是通过查表法近似计算 $e^z$ 的，得到 f.

接着生成梯度 g，理论部分应该是 (1 - word.codeArr[d] - f) * alpha 的，但是源码中是 f * (1 - f) * (word.codeArr[d] - f) * alpha，这里应该是用类似神经网络中常用的梯度下降法来求的梯度:

$$g = \sigma'(f)*(y - f)*\alpha$$

接下来更新 $e$ 和 $\theta_{j-1}^w$ 就更理论算法描述一致了.

后半部分的 for 循环是为了更新当前词的上下文单词的词向量 V(u) .

---

Skip-gram 模型

Skip-gram 模型的训练过程与CBOW类似，由于Skip-gram模型丢失了词序信息，所以就没有上下文单词的词向量累加操作.

WordNeuron word = sentence.get(index);
int a, c = 0;
for (a = b; a < window * 2 + 1 - b; a++) {
    if (a == window) {
        continue;
    }
    c = index - window + a;
    if (c < 0 || c >= sentence.size()) {
        continue;
    }
    double[] neu1e = new double[layerSize];// 误差项
    // HIERARCHICAL SOFTMAX
    List<Neuron> neurons = word.neurons;
    WordNeuron we = sentence.get(c);
    for (int i = 0; i < neurons.size(); i++) {
        HiddenNeuron out = (HiddenNeuron) neurons.get(i);
        double f = 0;
        //计算 X^T*theta
        // Propagate hidden -> output
        for (int j = 0; j < layerSize; j++) {
            f += we.syn0[j] * out.syn1[j];
        }
        //查表法计算 e^z
        if (f <= -MAX_EXP || f >= MAX_EXP) {
            continue;
        } else {
            f = (f + MAX_EXP) * (EXP_TABLE_SIZE / MAX_EXP / 2);
            f = expTable[(int) f];
        }
        //计算梯度 g
        // 'g' is the gradient multiplied by the learning rate
        double g = (1 - word.codeArr[i] - f) * alpha;
        //更新 e
        // Propagate errors output -> hidden
        for (c = 0; c < layerSize; c++) {
            neu1e[c] += g * out.syn1[c];
        }
        //更新 theta
        // Learn weights hidden -> output
        for (c = 0; c < layerSize; c++) {
            out.syn1[c] += g * we.syn0[c];
        }
    }
    //更新词向量
    // Learn weights input -> hidden
    for (int j = 0; j < layerSize; j++) {
        we.syn0[j] += neu1e[j];
    }
}

先回顾下 skip-gram模型的算法过程:

for (a = b; a < window * 2 + 1 - b; a++) 其中的 a 含义与 CBOW一致.

先计算 $V(w)^T \theta_{j-1}^u$ ，然后通过查表法求得 $e^z$ 的近似值 f .

然后计算梯度 g，这里用的公式为 g = (1 - word.codeArr[i] - f) * alpha，跟算法描述中的一致.

接着更新 $e$ 和 $\theta_{j-1}^u$ 的步骤就更算法描述中一致了.

---

模型保存

public void saveModel(File file) {
    // TODO Auto-generated method stub
    try (DataOutputStream dataOutputStream = new DataOutputStream(
        new BufferedOutputStream(new FileOutputStream(file)))) {
        //单词数保存
        dataOutputStream.writeInt(wordMap.size());
        //词向量的维度保存
        dataOutputStream.writeInt(layerSize);
        double[] syn0 = null;
        for (Entry<String, Neuron> element : wordMap.entrySet()) {
            //保存每个单词
            dataOutputStream.writeUTF(element.getKey());
            syn0 = ((WordNeuron) element.getValue()).syn0;
            //保存其词向量
            for (double d : syn0) {
                dataOutputStream.writeFloat(((Double) d).floatValue());
            }
        }
        dataOutputStream.close();
    } catch (IOException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }
}

---

小结

到这里整个基于 Hierarchical Softmax 的 Word2Vec 算法实现就分析完了，希望能对读者理解 Word2Vec 有所帮助.

其中也有一处不明白的地方，f = (f + MAX_EXP) * (EXP_TABLE_SIZE / MAX_EXP / 2); 按原理来说，应该可以直接计算 $e^f$ 的，但是这里为什么要做这种转行，就想不明白.