Word2Vec2021-10-16

背景知识

Log-linear Model

定义（Log Linear Models）：将语言模型的建立看成是一个多分类问题，相当于线性分类器加上softmax操作。

\begin{matrix} (1) & Y = softmax (w x + b) \end{matrix}

符号定义

$w$
$\mathcal{D} = \{ w_1,w_2,\cdots,w_N \}$ $N$ 为单词个数。由单词组成的集合。
$\mathcal{C}$ ，由单词组成的文本序列。
$\operatorname{Context}(w_t)$ $w_t$ $c$ $c$ $w_t$ $c$ 为窗口长度
$\mathbf{v}(w)$ $w$ 对应的词向量

两种模型

Word2Vec简介

语言模型基本思想：句子中下一个词的出现和前面的词是有关系的，所以可以使用前面的词预测下一个词。

Word2Vec基本思想：句子中相近的词之间是有联系的，比如今天后面经常出现上午、下午。所以Word2Vec的基本思想就是用词来预测词，CBOW使用周围词预测中心词，Skip-gram使用中心词预测周围词。

单个词到单个词

为了便于理解CBOW和Skip-gram模型，先介绍一个词到一个词的简单模型。

假设输入为：我喜欢观看巴西足球世界杯。经过分词，得到词表：['我','喜欢','观看','巴西','足球','世界杯']。为了构建一个词到一个词的模型，将单词两两分组，得到数据集：[['我','喜欢'],['喜欢','观看'],['观看','巴西'],['巴西','足球'],['足球','世界杯']]。使用one-hot对单词进行表示如下图所示：

巴西onehot

接下来，输入数据：['我', '喜欢']，在输出中，期望'喜欢'的概率最大。

巴西世界杯

扩展到一般的网络结构：

标准网络结构

定义如下符号：

$V$ ：词表大小（或语料库中不同单词的数目）
$N$ ：词向量维度
$\mathbf{X}_{N \times 1}$ ：输入单词，使用one-hot编码表示
$w$ ：原始单词
$\operatorname{Context}(w_i)_c$ $w_i$ $c$ $1 \le c \le C$
$\mathbf{W}_{V \times N}$ ：输入层与隐藏层之间的权重
$\mathbf{W^{\prime }}_{N \times V}$ ：隐藏层与输出层之间的权重
$\mathbf{u}_{V \times 1}$ ：每个单词的预测值，通过softmax计算可得到概率
$\mathbf{y}_{V \times 1}$ ：每个单词的概率

前向计算：

$\mathbf{h}_{N \times 1} = \mathbf{W}^{\mathrm{T}} \mathbf{X}$
$h_i = \sum_{k=1}^{V} w_{ki} x_k$
$\mathbf{u}_{V \times 1} = \mathbf{W^{\prime }}^{\mathrm{T}} \mathbf{h}$
$u_j = \sum_{i=1}^{N} w^{\prime }_{ij} h_i$ $h_i$ $u_j$ $h_i$ $u_j$
$\mathbf{y} = \operatorname{softmax} (\mathbf{u})$

损失函数：

$w_i$ $w_j$ 的概率
$\begin{matrix} (2) & p (w_{j} ∣ w_{i}) = y_{j} = \frac{e^{u_{j}}}{\sum_{k = 1}^{V} e^{u_{k}}} \end{matrix}$
损失函数
$a^*$ $p(w_{a^*} \mid w_i)$ 最大，等价地，可以导出如下损失函数：
$\begin{matrix} (3) & E = - \log {\frac{e^{u_{a^{*}}}}{\sum_{k = 1}^{V} e^{u_{k}}}} = - u_{a^{*}} + \log (\sum_{k = 1}^{V} e^{u_{k}}) \end{matrix}$

反向传播：

\begin{matrix} (4) & \begin{aligned} (1) 对 W^{'} 求 导 \\ \frac{\partial E}{\partial u_{j}} & = - t (j, a^{*}) + y_{j} := e_{j} \\ \frac{\partial E}{\partial w_{i j}^{'}} & = \frac{\partial E}{\partial u_{j}} \cdot \frac{\partial u_{j}}{\partial w_{i j}^{'}} = e_{j} h_{i} \\ \frac{\partial E}{\partial W^{'}} & = \sum_{i = 1}^{N} \sum_{j = 1}^{V} h_{i} \cdot e_{j} = h \otimes e^{T} \\ (2) 对 W 求 导 \\ \frac{\partial E}{\partial h_{i}} & = \sum_{j = 1}^{V} \frac{\partial E}{\partial u_{j}} \cdot \frac{\partial u_{j}}{\partial h_{i}} = \sum_{j = 1}^{V} e_{j} \cdot w_{i j}^{'} := E H_{i} \\ \frac{\partial E}{\partial w_{k i}} & = \frac{\partial E}{\partial h_{i}} \cdot \frac{\partial h_{i}}{\partial w_{k i}} = (\sum_{j = 1}^{V} e_{j} \cdot w_{i j}^{'}) \cdot x_{k} = E H_{i} \cdot x_{k} \\ \frac{\partial E}{\partial W} & = \sum_{k = 1}^{V} \sum_{i = 1}^{N} E H_{i} \cdot x_{k} = X \otimes E H^{T} ， 得 到 V \times N 的 矩 阵 ， 由 于 X 只 有 1 行 非 0 ， 所 以 矩 阵 只 有 1 行 非 0 ， 为 E H^{T} \\ 其 中 ， t (j, a^{*}) = {\begin{cases} 1, j = a^{*} \\ 0, j \neq a^{*} \end{cases} \end{aligned} \end{matrix}

参数更新：

$\mathbf{W}^{\prime}$ 更新：需要更新整个矩阵
$\mathbf{W}$ $a^*$ $w_t$ $\mathbf{X}$ $\mathbf{W}_2$ $\mathbf{W^{\prime}}$ ）

CBOW

CBOW1

首先，需要定义window，即选取多少个周围词，上图中window=2。通过周围词预测中心词，该问题为多分类问题。

$\mathbf{v}$

$w_{i-1},w_{i-2},w_{i+1},w_{i+2}$ $\mathbf{v}_o$

$w_i$ $M$ $\mathcal{C}$ 中的中心词个数

使用向量内积表示词向量的相似度，那么，中心词的预测概率为：

\begin{matrix} (5) & \begin{aligned} p (w_{i} ∣ w_{i - 2}, w_{i - 1}, w_{i + 1}, w_{i + 2}) & = \frac{\exp (v_{o}^{T} v_{w_{i}})}{\sum_{j = 1}^{N} \exp (v_{o}^{T} v_{j})} \\ 其 中 ， v_{w_{i}} 、 v_{j} 为 中 心 词 的 词 向 量 \end{aligned} \end{matrix}

损失函数（使中心词的概率最大）：

\begin{matrix} (6) & \begin{aligned} J (θ) & = - \frac{1}{M} \sum_{i = 1}^{M} \log p (w_{i} ∣ w_{o}) \\ = - \frac{1}{M} \sum_{i = 1}^{M} \frac{\exp (v_{o}^{T} v_{w_{i}})}{\sum_{j = 1}^{M} \exp (v_{o}^{T} v_{j})} \\ 其 中 ， M 为 中 心 词 个 数 ， w_{i} 为 & 中 心 词 ， w_{o} 为 w_{i} 对 应 的 周 围 词 ， v_{o} 为 周 围 词 词 向 量 的 和 ， v_{j} 为 中 心 词 词 向 量 \end{aligned} \end{matrix}

Skip-gram

skip-gram1

首先，需要定义window，即选取多少个周围词，上图中window=2。通过中心词预测周围词，该问题为多分类问题。

$\mathbf{v}$

$w_i$

$w_{i-1},w_{i-2},w_{i+1},w_{i+2}$ $M$ 为周围词个数

使用向量内积表示词向量的相似度，那么，周围词的预测概率为：

\begin{matrix} (7) & \begin{aligned} p (w_{i - 1} ∣ w_{i}) & = \frac{\exp (v_{w_{i - 1}}^{T} v_{w_{i}})}{\sum_{j = 1}^{M} \exp (v_{j}^{T} v_{w_{i}})} \\ 其 中 ， v_{j} 为 周 围 词 的 词 向 量 \end{aligned} \end{matrix}

损失函数（使周围词的概率最大）：

\begin{matrix} (8) & \begin{aligned} J (θ) & = - \frac{1}{M} \sum_{m = 1}^{M} \sum_{- c \leq j \leq c, j \neq 0} \log p (w_{m + j} ∣ w_{m}) \\ 其 中 ， c 为 窗 口 大 小 \end{aligned} \end{matrix}

计算优化

为了解决上述模型中softmax计算量太大的问题，使用以下两种方法进行优化。

Hierarchical softmax

核心思想：将多分类问题转化为多个二分类问题。

搜索路径 $X$ 单词 $y$ ，那么，从根结点到目标单词（叶子结点），便是若干个二分类过程。至此，完成了问题的转化。

CBOW

HS1

针对上述哈夫曼树，各层解释如下：

输入层
$\mathbf{v}\left(Context(w)_1 \right)，\mathbf{v}\left(Context(w)_2 \right)，\cdots，\mathbf{v}\left(Context(w)_{2c} \right) \in \mathbb{R}^{m}$ $\mathbf{v}(\cdot)$ 为单词的向量化表示
投影层
$\begin{matrix} (9) & x_{w} = \sum_{i = 1}^{2 c} v (Context (w)_{i}) \in R^{m} \end{matrix}$
输出层
$w$ $w$ $p(w \mid \text{Context}(w))$

为方便计算损失函数，定义如下变量：

路径 $\large p^w = (p_1 ^w, p_2 ^w, \cdots, p_{l_w}^w)$
$w$ $l^w$ $p_i ^w$ $p_1^w$ $p_{l_w}^w$ $w$ 对应的叶子结点。
编码 $\large d^w = (d_1 ^w, d_2 ^w, \cdots, d_{l_w}^w)$
$w$ $d_i ^w \in \{0,1 \}$ $p^w$ $i$ 个结点对应的编码（根结点不对应编码）。
权值 $\large \theta^w = (\theta_1 ^w, \theta_2 ^w, \cdots, \theta_{l_w - 1}^w)$
$p^w$ $\theta_i \in \mathbb{R}^m$ $p^w$ $i$ 个非叶子结点对应的参数向量。

$Context(w)$ $w$ 的概率为：

\begin{matrix} (10) & \begin{aligned} p (w ∣ Context (w)) & = \prod_{j = 2}^{l^{w}} p (d_{j}^{w} ∣ x_{w}, θ_{j - 1}^{w}) \\ 注 ： 顺 着 路 径 走 \end{aligned} \end{matrix}

其中，

\begin{matrix} (11) & \begin{aligned} p (d_{j}^{w} ∣ x_{w}, θ_{j - 1}^{w}) & = {\begin{matrix} σ (x_{w}^{T} θ_{j - 1}^{w}), d_{j}^{w} = 0 \\ 1 - σ (x_{w}^{T} θ_{j - 1}^{w}), d_{j}^{w} = 1 \end{matrix} \\ 注 ： 该 概 率 决 定 往 左 还 是 往 右 \end{aligned} \end{matrix}

该概率也可以写成如下形式：

\begin{matrix} (12) & p (d_{j}^{w} ∣ x_{w}, θ_{j - 1}^{w}) = {[σ (x_{w}^{T} θ_{j - 1}^{w})]}^{1 - d_{j}^{w}} \cdot {[1 - σ (x_{w}^{T} θ_{j - 1}^{w})]}^{d_{j}^{w}} \end{matrix}

那么，似然函数为：

\begin{matrix} (13) & \begin{aligned} ℓ & = \prod_{w \in C} p (w ∣ Context (w)) \\ = \prod_{w \in C} \prod_{j = 2}^{l^{w}} p (d_{j}^{w} ∣ x_{w}, θ_{j - 1}^{w}) \end{aligned} \end{matrix}

对数似然函数为：

\begin{matrix} (14) & \begin{aligned} L & = \log \prod_{w \in C} \prod_{j = 2}^{l^{w}} p (d_{j}^{w} ∣ x_{w}, θ_{j - 1}^{w}) \\ = \sum_{w \in C} \log \prod_{j = 2}^{l^{w}} p (d_{j}^{w} ∣ x_{w}, θ_{j - 1}^{w}) \\ = \sum_{w \in C} \sum_{j = 2}^{l^{w}} {(1 - d_{j}^{w}) \cdot \log [σ (x_{w}^{T} θ_{j - 1}^{w})] + d_{j}^{w} \cdot \log [1 - σ (x_{w}^{T} θ_{j - 1}^{w})]} \end{aligned} \end{matrix}

$\mathcal{L}$ $\theta_{j-1}^w$ 求偏导为：

\begin{matrix} (15) & \begin{aligned} \frac{\partial L}{\partial θ_{j - 1}^{w}} & = \frac{\partial}{\partial θ_{j - 1}^{w}} {\sum_{w \in C} \sum_{j = 2}^{l^{w}} {(1 - d_{j}^{w}) \cdot \log [σ (x_{w}^{T} θ_{j - 1}^{w})] + d_{j}^{w} \cdot \log [1 - σ (x_{w}^{T} θ_{j - 1}^{w})]}} \\ = (1 - d_{j}^{w}) [1 - σ (x_{w}^{T} θ_{j - 1}^{w})] x_{w} - d_{j}^{w} σ (x_{w}^{T} θ_{j - 1}^{w}) x_{w} \\ = [1 - d_{j}^{w} - σ (x_{w}^{T} θ_{j - 1}^{w})] x_{w} \end{aligned} \end{matrix}

$\theta_{j-1}^w$ 的更新公式为：

\begin{matrix} (16) & θ_{j - 1}^{w} = θ_{j - 1}^{w} + η [1 - d_{j}^{w} - σ (x_{w}^{⊤} θ_{j - 1}^{w})] x_{w} 其 中 ， η 为 学 习 率 \end{matrix}

$\mathcal{L}$ $\mathbf{x}_{w}$ 求偏导为：

\begin{matrix} (17) & \frac{\partial L}{\partial x_{w}} = \sum_{j = 2}^{l^{w}} [1 - d_{j}^{w} - σ (x_{w}^{⊤} θ_{j - 1}^{w})] θ_{j - 1}^{w} \end{matrix}

$\mathbf{v}(\tilde{w})$ 的更新公式为：

\begin{matrix} (18) & v (\tilde{w}) = v (\tilde{w}) + η \frac{\partial L}{\partial x_{w}} 其 中 ， \tilde{w} \in C o n t e x t (w) \end{matrix}

Skip-gram

HS2

针对上述哈夫曼树，各层解释如下：

输入层
$w$ $\mathbf{v}(w) \in \mathbb{R}^m$
映射层
恒等映射，多余，为了和CBOW模型的网络结构进行对比。
输出层

$w$ $Context(w)$ 的条件概率为：

\begin{matrix} (19) & p (Context (w) ∣ w) = \prod_{u \in Context (w)} p (u ∣ w) \end{matrix}

其中，

\begin{matrix} (20) & p (u ∣ w) = \prod_{j = 2}^{l^{u}} p (d_{j}^{u} ∣ v (w), θ_{j - 1}^{u}) \end{matrix}

并且：

\begin{matrix} (21) & p (d_{j}^{u} ∣ v (w), θ_{j - 1}^{u}) = {[σ (v (w)^{T} θ_{j - 1}^{u})]}^{1 - d_{j}^{u}} \cdot {[1 - σ (v (w)^{T} θ_{j - 1}^{u})]}^{d_{j}^{u}} \end{matrix}

所以，似然函数为：

\begin{matrix} (22) & \begin{aligned} ℓ & = \prod_{w \in C} p (Context (w) ∣ w) \\ = \prod_{w \in C} \prod_{u \in C o n t e x t (w)} \prod_{j = 2}^{l^{u}} p (d_{j}^{u} ∣ v (w), θ_{j - 1}^{u}) \end{aligned} \end{matrix}

对数似然函数为：

\begin{matrix} (23) & \begin{aligned} L & = \sum_{w \in C} \log \prod_{u \in Context (w)} \prod_{j = 2}^{l^{u}} {{[σ (v (w)^{T} θ_{j - 1}^{u})]}^{1 - d_{j}^{u}} \cdot {[1 - σ (v (w)^{T} θ_{j - 1}^{u})]}^{d_{j}^{u}}} \\ = \sum_{w \in C} \sum_{u \in Context (w)} \sum_{j = 2}^{l^{u}} {(1 - d_{j}^{u}) \cdot \log [σ (v (w)^{T} θ_{j - 1}^{u})] + d_{j}^{u} \cdot \log [1 - σ (v (w)^{T} θ_{j - 1}^{u})]} \end{aligned} \end{matrix}

$\mathcal{L}$ $\theta_{j-1}^u$ 的偏导为：

\begin{matrix} (24) & \begin{aligned} \frac{\partial L}{\partial θ_{j - 1}^{u}} & = \frac{\partial}{θ_{j - 1}^{u}} {\sum_{w \in C} \sum_{u \in C o n t e x t (w)} \sum_{j = 2}^{l^{u}} {(1 - d_{j}^{u}) \cdot \log [σ (v (w)^{T} θ_{j - 1}^{u})] + d_{j}^{u} \cdot \log [1 - σ (v (w)^{T} θ_{j - 1}^{u})]}} \\ = \sum_{w \in C} {(1 - d_{j}^{u}) [1 - σ (v (w)^{T} θ_{j - 1}^{u})] v (w) - d_{j}^{u} σ (v (w)^{T} θ_{j - 1}^{u}) v (w)} \\ = \sum_{w \in C} [1 - d_{j}^{u} - σ (v (w)^{T} θ_{j - 1}^{u})] v (w) \end{aligned} \end{matrix}

$\theta_{j-1}^u$ 的更新公式为：

\begin{matrix} (25) & \begin{aligned} θ_{j - 1}^{u} & = θ_{j - 1}^{u} + η \sum_{w \in C} [1 - d_{j}^{u} - σ (v (w)^{T} θ_{j - 1}^{u})] v (w) \\ 其 中 ， η 为 学 习 率 \end{aligned} \end{matrix}

$\mathcal{L}$ $\mathbf{v}(w)$ 的偏导为：

\begin{matrix} (26) & \frac{\partial L}{\partial v (w)} = \sum_{u \in Context (w)} \sum_{j = 2}^{l^{u}} [1 - d_{j}^{u} - σ (v (w)^{T} θ_{j - 1}^{u})] θ_{j - 1}^{u} \end{matrix}

$\mathbf{v}(w)$ 的更新为：

\begin{matrix} (27) & v (w) = v (w) + η \sum_{u \in Context (w)} \sum_{j = 2}^{l^{u}} [1 - d_{j}^{u} - σ (v (w)^{T} θ_{j - 1}^{u})] θ_{j - 1}^{u} \end{matrix}

Negative Sampling

CBOW

$Context(w)$ $w$ 的周围词）为：

$N E G(w) \neq \varnothing$

$\forall \tilde{w} \in \mathcal{D}$ $L^{w}(\tilde{w})$ $\tilde{w}$ $\tilde{w}$ $w$ 的周围词，正样本标签为1，负样本标签为0：

\begin{matrix} (28) & L^{w} (\tilde{w}) = {\begin{cases} 1, \tilde{w} = w \\ 0, \tilde{w} \neq w \end{cases} \end{matrix}

$\text {Context}(w)$ $\{w\} \cup N E G(w)$ ，其似然函数为：

\begin{matrix} (29) & g (w) = \prod_{u \in {w} \cup N E G (w)} p (u ∣ Context (w)) = σ (x_{w}^{T} θ^{w}) \prod_{u \in N E G (w)} [1 - σ (x_{w}^{T} θ^{w})] \end{matrix}

其中，

\begin{matrix} (30) & \begin{array}{r} p (u ∣ Context (w)) = {\begin{cases} σ (x_{w}^{T} θ^{u}), L^{w} (u) = 1 \\ 1 - σ (x_{w}^{T} θ^{u}), L^{w} (u) = 0 \end{cases} \\ 其 中 ， x_{w} 为 Context (w) 词 向 量 之 和 ， θ^{u} \in R^{m} 为 模 型 参 数 \end{array} \end{matrix}

上式也可以写为：

\begin{matrix} (31) & p (u ∣ Context (w)) = {[σ (x_{w}^{T} θ^{u})]}^{L^{w} (u)} \cdot {[1 - σ (x_{w}^{T} θ^{u})]}^{1 - L^{w} (u)} \end{matrix}

$\mathcal{C}$ 的对数似然函数为：

\begin{matrix} (32) & \begin{aligned} L & = \log \prod_{w \in C} g (w) \\ = \sum_{w \in C} \log g (w) \\ = \sum_{w \in C} \log \prod_{u \in {w} \cup N E G (w)} {{[σ (x_{w}^{T} θ^{u})]}^{L^{w} (u)} \cdot {[1 - σ (x_{w}^{T} θ^{u})]}^{1 - L^{w} (u)}} \\ = \sum_{w \in C} \sum_{u \in {w} \cup N E G (w)} {L^{w} (u) \cdot \log [σ (x_{w}^{T} θ^{u})] + [1 - L^{w} (u)] \cdot \log [1 - σ (x_{w}^{T} θ^{u})]} \end{aligned} \end{matrix}

$\mathcal{L}$ $\theta^u$ 的偏导为：

\begin{matrix} (33) & \begin{aligned} \frac{\partial L}{\partial θ^{u}} & = \frac{\partial}{\partial θ^{u}} {\sum_{w \in C} \sum_{u \in {w} \cup N E G (w)} {L^{w} (u) \cdot \log [σ (x_{w}^{T} θ^{u})] + [1 - L^{w} (u)] \cdot \log [1 - σ (x_{w}^{T} θ^{u})]}} \\ = L^{w} (u) [1 - σ (x_{w}^{T} θ^{u})] x_{w} - [1 - L^{w} (u)] σ (x_{w}^{T} θ^{u}) x_{w} \\ = [L^{w} (u) - σ (x_{w}^{T} θ^{u})] x_{w} \end{aligned} \end{matrix}

$\theta^u$ 的更新公式为：

\begin{matrix} (34) & θ^{u} = θ^{u} + η [L^{w} (u) - σ (x_{w}^{T} θ^{u})] x_{w} \end{matrix}

$\mathcal{L}$ $\mathbf{x}_w$ 的偏导为：

\begin{matrix} (35) & \frac{\partial L}{\partial x_{w}} = \sum_{u \in {w} \cup N E G (w)} [L^{w} (u) - σ (x_{w}^{T} θ^{u})] θ^{u} \end{matrix}

$\mathbf{v}(\tilde{w})$ 的更新公式为：

\begin{matrix} (36) & \begin{array}{r} v (\tilde{w}) = v (\tilde{w}) + η \frac{\partial L}{\partial x_{w}} \\ 其 中 ， \tilde{w} \in Context (w) \end{array} \end{matrix}

Skip-gram

$w$ $\tilde{w}$ $NEG^{\tilde{w}}(w)$ $(w, \tilde{w})$ 的负样本。

$\tilde{w}$ $\{w \} \cup NEG^{\tilde{w}}(w)$ 的似然函数为：

\begin{matrix} \begin{matrix} (37) & g (w) = \prod_{\tilde{w} \in Context (w)} \prod_{u \in {w} ⋃ N E G^{\tilde{w}} (w)} p (u ∣ \tilde{w}) \end{matrix} \\ 其 中 ， N E G^{\tilde{w}} (w) 为 处 理 周 围 词 \tilde{w} 时 生 成 的 负 样 本 子 集 \end{matrix}

其中，

\begin{matrix} \begin{matrix} (38) & p (u ∣ \tilde{w}) = {\begin{cases} σ (v (\tilde{w})^{T} θ^{u}), L^{w} (u) = 1 \\ 1 - σ (v (\tilde{w})^{T} θ^{u}), L^{w} (u) = 0 \end{cases} \end{matrix} \end{matrix}

上式又可以写为：

\begin{matrix} (39) & p (u ∣ \tilde{w}) = {[σ (v (\tilde{w})^{T} θ^{u})]}^{L^{w} (u)} \cdot {[1 - σ (v (\tilde{w})^{T} θ^{u})]}^{1 - L^{w} (u)} \end{matrix}

$\mathcal{C}$ 的对数似然函数为：

\begin{matrix} (40) & \begin{aligned} L & = \log \prod_{w \in C} g (w) \\ = \sum_{w \in C} \log g (w) \\ = \sum_{w \in C} \log \prod_{\tilde{w} \in Context(w)} \prod_{u \in {w} ⋃ N E G^{\tilde{w}} (w)} {{[σ (v (\tilde{w})^{T} θ^{u})]}^{L^{w} (u)} \cdot {[1 - σ (v (\tilde{w})^{T} θ^{u})]}^{1 - L^{w} (u)}} \\ = \sum_{w \in C} \sum_{\tilde{w} \in Context (w)} \sum_{u \in {w} \cup N E G^{\tilde{w}} (w)} {L^{w} (u) \cdot \log [σ (v (\tilde{w})^{T} θ^{u})] + [1 - L^{w} (u)] \cdot \log [1 - σ (v (\tilde{w})^{T} θ^{u})]} \end{aligned} \end{matrix}

$\mathcal{L}$ $\theta^u$ 的偏导为：

\begin{matrix} (41) & \begin{aligned} \frac{\partial L}{\partial θ^{u}} & = \frac{\partial}{\partial θ^{u}} {\sum_{w \in C} \sum_{\tilde{w} \in Context (w)} \sum_{u \in {w} \cup N E G^{\tilde{w}} (w)} {L^{w} (u) \cdot \log [σ (v (\tilde{w})^{T} θ^{u})] + [1 - L^{w} (u)] \cdot \log [1 - σ (v (\tilde{w})^{T} θ^{u})]}} \\ = L^{w} (u) [1 - σ (v (\tilde{w})^{T} θ^{u})] v (\tilde{w}) - [1 - L^{w} (u)] σ (v (\tilde{w})^{T} θ^{u}) v (\tilde{w}) \\ = [L^{w} (u) - σ (v (\tilde{w})^{T} θ^{u})] v (\tilde{w}) \end{aligned} \end{matrix}

$\theta^u$ 的更新公式为：

\begin{matrix} (42) & θ^{u} = θ^{u} + η [L^{w} (u) - σ (v (\tilde{w})^{T} θ^{u})] v (\tilde{w}) \end{matrix}

$\mathcal{L}$ $\mathbf{v}(\tilde{w})$ 的偏导为：

\begin{matrix} (43) & \frac{\partial L}{\partial v (\tilde{w})} = \sum_{u \in {w} \cup N E G^{\tilde{w}} (w)} [L^{w} (u) - σ (v (\tilde{w})^{T} θ^{u})] θ^{u} \end{matrix}

$\mathbf{v}(\tilde{w})$ 的更新公式为：

\begin{matrix} (44) & v (\tilde{w}) = v (\tilde{w}) + η \frac{\partial L}{\partial v (\tilde{w})} \end{matrix}

采样

负采样

非等距剖分：

$\mathcal{D}$ $w_i$ $l(w_i)$ ，其长度为：

\begin{matrix} (45) & \begin{array}{r} len (w_{i}) = \frac{counter (w_{i})}{\sum_{u \in D} counter (u)} \\ 其 中 ， counter (\cdot) 为 词 在 语 料 C 中 的 出 现 次 数 \end{array} \end{matrix}

$l(w_1),\cdots,l(w_N)$ 拼接为长度为1的单位线段。记：

\begin{matrix} \begin{matrix} (46) & \begin{aligned} l_{0} = 0 \\ l_{k} = \sum_{j = 1}^{k} len (w_{j}), k = 1, 2, \dots, N \end{aligned} \end{matrix} \end{matrix}

$l_j, j \in \{0,1,\cdots,N \}$ $[0,1]$ 上的一个非等距剖分：

\begin{matrix} (47) & I_{i} = (l_{i - 1}, l_{i}], i = 1, 2, \dots, N \end{matrix}

等距剖分：

$[0,1]$ $m_j, j \in \{0,1,\cdots,M \}$ $M \gg N$ 。

等距与非等距映射：

$\{m_j \}_{j=1} ^ {M-1}$ $\{m_j \}_{j=1} ^ {M-1}$ $\{I_j \}_{j=1} ^ {N}$ $\{w_j \}_{j=1} ^ {N}$ 之间的映射。

\begin{matrix} (48) & Table (i) = w_{k}, where m_{i} \in I_{k}, i = 1, 2, \dots, M - 1 \end{matrix}

重采样

重采样的目的：提高低频次出现的频率，降低高频词出现的概率。

$w_i$ $P\left(w_{i}\right)$ $P\left(w_{i}\right)$ 计算公式为：

\begin{matrix} \begin{matrix} (49) & P (w_{i}) = 1 - \sqrt{\frac{t}{f (w_{i})}} \end{matrix} \\ 其 中 ， f (w_{i}) 为 词 w_{i} 在 数 据 集 中 出 现 的 频 率 ， 论 文 中 t 取 10^{- 5} \end{matrix}

复杂度分析

使用模型参数量表征模型复杂度。

定义符号：

$O$ ：训练复杂度
$E$ ：迭代次数
$T$ ：数据集大小
$Q$ ：参与本次计算的参数的数目
$O = E \times T \times Q$

NNLM(前馈神经网络)

NNLM_model

$N$ 个词预测下一个词

\begin{matrix} (50) & \begin{matrix} y = U \tanh (W X + d) \\ p (x_{i} ∣ x_{i - 1}, \dots, x_{i - N}) = \frac{e^{y_{i}}}{\sum_{j = 1}^{V} e^{y_{j}}} \\ 其 中 ， X = [x^{(1)}, x^{(2)}, \dots, x^{(N)}], y = [y_{1}, y_{2}, \dots, y_{V}] \end{matrix} \end{matrix}

符号定义：

$N$ ：上文词（训练数据）个数
$D$ ：词向量维度
$V$ ：词表的大小
$H$ ：隐藏层大小
$\mathbf{x}_{N \times D}$
$\mathbf{W}_{N \times D \times H}$
$\mathbf{U}_{V \times H}$

参数个数：

$N \times D$
$N \times D \times H$
$V \times H$ $\log _2 V$ $\theta$ $H$ $H \cdot \log _2 V$

$Q = N \times D + N \times D \times H + V \times H$

RNNLM(循环神经网络语言模型)

RNNLM_model

\begin{matrix} (51) & \begin{aligned} s (t) & = U w (t) + W s (t - 1) + d \\ y (t) & = V s (t) \\ 其 中 ， w (t) 表 示 时 刻 t 的 当 前 输 入 & 单 词 的 词 向 量 ， s (t - 1) 代 表 隐 藏 层 的 前 一 次 输 出 \end{aligned} \end{matrix}

符号定义：

$\mathbf{w}(t)$ $D \times 1$
$\mathbf{U}_{H \times D}$
$\mathbf{W}_{H \times H}$
$\mathbf{s}(t)$ $H \times 1$
$\mathbf{V}_{V \times H}$
$\mathbf{y}(t)$ $V \times 1$

复杂度计算：

$1 \times D$
$D \times H + H \times H$
$H \times V$
$D \approx H$
$1 \times D + D \times H + H \times H +H \times V \\ \approx 1 \times H + H \times H \times 2+V \times H \\ \approx H \times H + V \times H$

Skip-gram

符号定义：

$C$ ：中心词个数
$D$ ：词向量维度
$V$ ：单词个数

原始复杂度：

$1 \times D$
$\mathbf{W}_{D \times V}$ $\mathbf{u}$ $\mathbf{y}$ $D \times V$
$C (1 \times D + D \times V)$

Hierarchical softmax复杂度：

$\log_2V$ $\theta$ $D$ $C (1 \times D + D \times \log_2V)$

Negative Sampling复杂度：

$1$ $K$ $D$ $C (1 \times D + D \times (K+1))$

CBOW

$N$ $D$ $N \times D$ $1 \times D$ $\mathbf{W}_{D \times V}$ $N \times D$ 。

$N \times D + D \times V$

$N \times D + D \times \log_2V$

$N \times D + D \times (K+1)$

复杂度总结

如下对各模型复杂度进行总结：

$Q = N \times D + N \times D \times H + H \times \log_2V$
$Q = H \times H + H \times \log_2V$
$Q = C (1 \times D + D \times \log_2V)$
$Q = C (1 \times D + D \times (K+1))$
$Q = N \times D + D \times \log_2V$
$Q = N \times D + D \times (K+1)$

问题

为什么可以使用向量内积度量相似度？
$\mathbf{a} \cdot \mathbf{b} = |\mathbf{a}| |\mathbf{b}| \cos \theta$ $\theta$ 单位化 $\cos \theta$ ，此时，两向量越接近，夹角越小，内积越大。
对比Skip-gram和CBOW。训练速度上CBOW更快；对低频词，Skip-gram效果更好，因为Skip-gram是用当前词预测上下文，当前词是低频还是高频没有区别，但是CBOW相当于是完形填空，更倾向于选择常见的词而不是低频词。总体上讲，Skip-gram模型的效果更好。

背景知识

Log-linear Model

符号定义

两种模型

Word2Vec简介

单个词到单个词

CBOW

Skip-gram

计算优化

Hierarchical softmax

CBOW

Skip-gram

Negative Sampling

CBOW

Skip-gram

采样

负采样

重采样

复杂度分析

NNLM(前馈神经网络)

RNNLM(循环神经网络语言模型)

Skip-gram

CBOW

复杂度总结

问题

参考链接