logo
搜索
我的图书馆

发文章

发文工具

其他工具

留言交流
搜索
分享

word2vec中的数学模型

 520jefferson 2021-07-01

图片

1. 简介


2. 预备知识

2.1 logistic回归

逻辑回归（Logistic Regression）是一种用于解决二分类（0 or 1）问题的机器学习方法，用于估计某种事物的可能性。比如某用户购买某商品的可能性，某病人患有某种疾病的可能性，以及某广告被用户点击的可能性等。

逻辑回归（Logistic Regression）与线性回归（Linear Regression）都是一种广义线性模型（generalized linear model）。逻辑回归假设因变量 y 服从伯努利分布，而线性回归假设因变量 y 服从高斯分布，因此与线性回归有很多相同之处，去除Sigmoid映射函数的话，逻辑回归算法就是一个线性回归。可以说，逻辑回归是以线性回归为理论支持的，但是逻辑回归通过Sigmoid函数引入了非线性因素，因此可以轻松处理0/1分类问题。

首先介绍一下Sigmoid函数：

图片
其函数曲线如下：

图片


从上图可以看到sigmoid函数是一个s形的曲线，它的取值在[0, 1]之间。
逻辑回归的假设函数形式如下：

图片

因此

图片

其中 图片 是我们的输入， 图片 为我们要求取的参数向量

逻辑回归中的代价函数为交叉熵损失函数：

图片

使用梯度下降算法更新参数图片，以最小化代价函数图片：

图片

在逻辑回归中，假设函数 图片 用于计算样本属于某类别的可能性；决策函数 图片 用于计算给定样本的类别；决策边界 图片是一个方程，用于标识出分类函数（模型）的分类边界。使用sklearn实现 Logistic Regression 代码如下：
# coding: UTF-8import numpy as npimport pandas as pd
import matplotlib.pyplot as pltimport seaborn as sns
from sklearn.linear_model import LogisticRegressionfrom sklearn.model_selection import train_test_splitfrom sklearn.preprocessing import StandardScalerfrom sklearn.metrics import classification_report,confusion_matrix,accuracy_score,roc_curve, auc
import statsmodels.api as sm
# Making the Confusion Matrixdef confusion_matrix_c(y_test,y_pred): cm = confusion_matrix(y_test, y_pred) class_label = ['No Affair', 'Had Affair'] df_cm = pd.DataFrame(cm, index=class_label,columns=class_label) sns.heatmap(df_cm, annot=True, fmt='d') plt.title('Confusion Matrix') plt.xlabel('Predicted Label') plt.ylabel('True Label') plt.show()
def plot_roc_auc_curve(fpr, tpr): plt.figure() plt.plot(fpr, tpr, color='darkorange', lw=2, label='ROC curve (area = %0.2f)' % roc_auc) plt.plot([0, 1], [0, 1], color='navy', lw=2, linestyle='--') plt.xlim([0.0, 1.0]) plt.ylim([0.0, 1.05]) plt.xlabel('False Positive Rate') plt.ylabel('True Positive Rate') plt.title('ROC Curve') plt.legend(loc='lower right') plt.show()
df = sm.datasets.fair.load_pandas().data
def check_affair(x): if x != 0: return 1 else: return 0
df['Had_Affair'] = df['affairs'].apply(check_affair)df = pd.get_dummies(df, prefix=['occupation', 'occupation_husb'], columns=['occupation', 'occupation_husb'])df.drop(['occupation_1.0','occupation_husb_1.0'],axis=1,inplace=True)X = df.drop(['affairs','Had_Affair'],axis=1)y = df['Had_Affair']
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size = 0.3, random_state = 42)sc = StandardScaler()X_train = sc.fit_transform(X_train)X_test = sc.transform(X_test)
# Fitting Logistic Regression to the Training setlr= LogisticRegression(C=1,penalty='l1',random_state=42)lr.fit(X_train,y_train)
# Predicting the Test set resultsy_pred_lr= lr.predict(X_test)print(classification_report(y_test,y_pred_lr))
# Confusion Matrixconfusion_matrix_c(y_test, y_pred_lr)
#Score of Predictionlr_score_train = lr.score(X_train,y_train)print('Train Prediction Score',lr_score_train*100)lr_score_test = accuracy_score(y_test,y_pred_lr)print('Test Prediction Score',lr_score_test*100)
y_predict_probabilities = lr.predict_proba(X_test)[:,1]fpr, tpr, _ = roc_curve(y_test, y_predict_probabilities)roc_auc = auc(fpr, tpr)plot_roc_auc_curve(fpr, tpr)
运行后得到 Logistic Regression 模型预测的混淆矩阵、热图和 ROC 曲线如下：

图片

图片  图片

2.2 Huffman编码

霍夫曼树是二叉树的一种特殊形式，又称为最优二叉树，其主要作用在于数据压缩和编码长度的优化。

2.2.1 路径和路径长度

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

图片

图中所示二叉树结点A到结点D的路径长度为2，结点A到达结点C的路径长度为1。

2.2.2 带权路径长度

若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

图片

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。上图所示二叉树的WPL: WPL = 6 * 2 + 3 * 2 + 8 * 2 = 34。

2.2.3 霍夫曼树

给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为霍夫曼树(Huffman Tree)。

图片

上图所示的两棵二叉树，叶子结点为A、B、C、D，对应权值分别为7、5、2、4。

第一棵树的WPL = 7 * 2 + 5 * 2 + 2 * 2 + 4 * 2 = 36
第二棵树的WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3 = 35

由ABCD构成叶子结点的二叉树形态有许多种，但是WPL最小的树只有上图右边所示的形态。则第二棵树为一棵霍夫曼树。

构造霍夫曼树主要运用于编码，称为霍夫曼编码。上图中霍夫曼树的构造过程如下：

(1) 选择结点权值最小的两个结点构成一棵二叉树

图片

(2) 则现在可以看作由T1，A，B构造霍夫曼树，继续执行步骤1。选则B和T1构成一棵二叉树

图片

(3) 现在只有T2和A两个结点，继续执行步骤1。选择A和T2构成一棵二叉树

图片

经过上述步骤可以构造完一棵霍夫曼树。通过观察可以发现，霍夫曼树中权值越大的结点距离根结点越近。图中四个叶子结点的编码结果为：

结点

编码
A0
B10
C110
D111

采用霍夫曼树可以适当降低编码长度，尤其是在编码长度较长，且权值分布不均匀时，采用霍夫曼编码可以大大缩短编码长度。

2.2.4 代码实现

给定n个权值 {w1,w2,...,wn} 作为二叉树的n个叶子结点，可通过以下算法来构造一棵霍夫曼树：

(1) 将 {w1,w2,...,wn} 看成是有n棵树的森林，每棵树只有一个结点。

(2) 在森林中选出两个根节点权值最小的树合并，作为一棵新树的左右子树，且新  

    树的根节点权值为其左右子树根节点权值之和。

(3) 从森林中删除选取的两棵树，并将新树加入森林。

(4) 重复(2)(3)步，直到森林中只剩一棵树为止，该树即为所求的Huffman树。

在word2vec中，将词典中的所有单词作为叶子结点，词频为叶子结点的权值，构造一棵Huffman树，词频越大的词离根节点越近。对每个单词进行Huffman编码，左、右子树中权值较大的孩子结点编码为1，较小的孩子结点编码为0。

#include <iostream>#include <cstdlib>#include <vector>#include <algorithm>
using namespace std;
const int maxWeight = 1e8;const int maxBit = 40;
struct HuffmanNode {  int weight;  int parent;  int left_child;  int right_child;};
struct Code {  int bit[maxBit];  int depth;  int weight;};
vector<HuffmanNode> build_huffman_tree(const vector<int>& weight) {  size_t n = weight.size();  vector<HuffmanNode> ht(2 * n - 1);  for (size_t i = 0; i < 2 * n - 1; i++) {    ht[i].weight = (i < n) ? weight[i] : maxWeight;    ht[i].parent = 0;    ht[i].left_child = -1;    ht[i].right_child = -1;  }  // 构造霍夫曼树的非叶子结点  int index1 = n - 1;  int index2 = n;  int min1, min2;  for (size_t i = 0; i < n - 1; i++) {    // 找出权重最小的两个结点编号    if (index1 >= 0) {      if (ht[index1].weight < ht[index2].weight) {        min1 = index1;        index1--;      } else {        min1 = index2;        index2++;      }    } else {      min1 = index2;      index2++;    }    if (index1 >= 0) {      if (ht[index1].weight < ht[index2].weight) {        min2 = index1;        index1--;      } else {        min2 = index2;        index2++;      }    } else {      min2 = index2;      index2++;    }    // 合并两个权值最小的结点    ht[min1].parent = n + i;    ht[min2].parent = n + i;    ht[n + i].weight = ht[min1].weight + ht[min2].weight;    ht[n + i].left_child = min1;    ht[n + i].right_child = min2;  }  return ht;}
vector<Code> huffman_code(const vector<HuffmanNode>& ht) {  size_t n = (ht.size() + 1) / 2;  if ((ht.size() + 1) % 2 != 0) {    cerr << 'Invalid Huffman Tree!' << endl;    exit(EXIT_FAILURE);  }  Code cd;  int child, parent;  vector<Code> hc(n);  // 叶子结点的霍夫曼编码  for (size_t i = 0; i < n; i++) {    cd.depth = 0;    cd.weight = ht[i].weight;    child = i;    parent = ht[child].parent;    while (parent != 0) {      if (ht[parent].left_child == child) {        cd.bit[cd.depth] = 0;      } else {        cd.bit[cd.depth] = 1;      }
      cd.depth++;      child = parent;      parent = ht[child].parent;    }    for (int j = cd.depth - 1; j >= 0; j--) {      hc[i].bit[cd.depth - j - 1] = cd.bit[j];    }    hc[i].depth = cd.depth;    hc[i].weight = cd.weight;  }  return hc;}
int main() {  vector<int> weight = {2, 4, 5, 7};  sort(weight.rbegin(), weight.rend());  auto ht = build_huffman_tree(weight);  auto code = huffman_code(ht);  int wpl = 0;  for (size_t i = 0; i < code.size(); i++) {    cout << 'Weight=' << code[i].weight << '  Code=';    for (size_t j = 0; j < code[i].depth; j++) {      cout << code[i].bit[j];    }    wpl += code[i].depth * code[i].weight;    cout << endl;  }  cout << 'Huffman's WPL is: ' << wpl << endl;  return 0;}

代码运行结果：

图片

3. 基于 Hierarchical Softmax 的模型

本节开始介绍word2vec中用到的两个重要模型：CBOW模型 (Continuous Bag-Of-Words Model) 和 Skip-gram模型 (Continuous Skip-gram Model)，如下图所示：

图片

由图可见，两个模型都包含三层：输入层、投影层和输出层。前者是在已知当前词w(t) 的上下文 w(t-2), w(t-1), w(t+1), w(t+2) 的前提下预测当前词 w(t)；而后者恰恰相反，是在已知当前词 w(t) 的前提下，预测其上下文 w(t-2), w(t-1), w(t+1), w(t+2)。

对于 CBOW 和 Skip-gram 两个模型，word2vec 给出了两套框架，它们分别基于 Hierarchical Softmax 和 Negative Sampling 来进行设计。本节介绍基于 Hierarchical Softmax 的 CBOW 和 Skip-gram 模型。

基于神经网络的语言模型的目标函数通常取为如下对数似然函数：

图片

其中的关键是条件概率函数 p(w|Context(w)) 的构造。对于 word2vec 中基于 Hierarchical Softmax 的 CBOW 模型，要优化的目标函数形如上式；而对于基于 Hierarchical Softmax 的 Skip-gram 模型，要优化的目标函数则形如：

图片

讨论过程中我们将重点放在 p(w|Context(w)) 和 p(Context(w)|w) 的构造上，接下来将从数学推导的角度对这两个模型进行详细介绍。

3.1 CBOW 模型

下图给出了 CBOW 模型的网络结构，它包含3层：输入层、投影层和输出层。下面以单个样本 (Context(w), w) 为例（假设 Context(w) 由 w 前后各 c 个词构成），对这三个层做简要说明。

图片

1. 输入层：包含 Context(w) 中 2c 个词的词向量：

图片

    其中 m 表示词向量的长度。

2. 投影层：将输入层 2c 个词的词向量求平均，即

图片

3. 输出层：输出层对应一棵二叉树，它是以语料中出现过的词为叶子结点，以各词在语料中出现的次数为权值构造出来的 Huffman 树。在这棵 Huffman 树中，叶子结点共 N=|V| 个，分别对应词典 V 中的词，非叶子结点 N-1 个（图中标记为黄色的那些结点）。

Hierarchical Softmax 是 word2vec 中用于提高性能的一项关键技术。在具体介绍该技术前，先引入若干相关符号，考虑 Huffman 树中的某个叶子结点，假设它对应词典 V 中的词 w，记

  • 图片：从根结点出发到达 w 对应叶子结点的路径。

  • 图片：路径中包含的结点个数。

  • 路径中的所有结点：

图片

        其中第一个表示根结点，最后一个表示词 w 对应的叶子结点。

  • 词 w 的 Huffman 编码：

图片

        表示路径中第 j 个结点对应的编码（根结点不对应编码）。

  • 路径的权重参数：

图片

        表示路径中第 j 个非叶子结点对应的权重向量。该权重向量为算法的辅助向  

        量。

图片

对于词典 V 中的任意词 w，Huffman 树中必存在一条从根结点到词 w 对应叶子结点的路径（且这条路径是唯一的）。路径上存在 n - 1 个分支，将每个分支看成一次二分类，每一次二分类就产生一个概率，将这些概率连乘起来，就是所需的 p(w|Context(w))。条件概率 p(w|Context(w)) 的一般公式可写为：

图片

word2vec 中约定编码为0的结点为正类，编码为1的结点为负类。根据 2.1 中介绍的逻辑回归，一个结点被分为正类的概率为

图片

一个结点被分为负类的概率为

图片

因此

图片

将上式代入对数似然函数，可得

图片

为了梯度求解方便，将上式中双重求和符号下花括号内的内容记为

图片

至此，已经推导出基于 Hierarchical Softmax 的 CBOW 模型的目标函数。word2vec 中采用随机梯度上升法最大化对数似然函数。随机梯度上升法的做法是：每取一个样本 (Context(w), w)，就对目标函数中的所有相关参数进行一次更新。目标函数对参数向量的梯度计算如下

图片

参数向量的更新公式为

图片

下面以样本 (Context(w), w) 为例，给出 CBOW 模型中采用随机梯度上升法更新各参数向量的伪代码

图片

3.2 Skip-gram 模型

本小节介绍 word2vec 中的另一个重要模型 — Skip-gram 模型，推导过程与 CBOW 大同小异，将沿用上一小节引入的记号。

图片

上图给出了 Skip-gram 模型的网络结构，与 CBOW 模型的网络结构一样，也包括三层：输入层、投影层和输出层。下面以样本 (w, Context(w)) 为例，对这三个层做简要说明：

1. 输入层：只含当前样本中心词 w 的词向量 v(w)；

2. 投影层：这是个恒等投影，把 v(w) 投影到 v(w)。因此这个投影层是多余的，之      所以保留主要是方便和 CBOW 模型的网络结构做对比；

3. 输出层：和 CBOW 模型一样，输出层也是一棵霍夫曼树。

对于 Skip-gram 模型，已知的是当前词 w，需要对其上下文 Context(w) 中的词进行预测，关键是条件概率函数 p(Context(w)|w) 的构造，Skip-gram 模型中将其定义为

图片

上式中的 p(u|w) 可以按照上一小节介绍的 Hierarchical Softmax 思想，类似地写为

图片

其中

图片

对数似然目标函数为

图片

同样，为了梯度推导方便，将三重求和符号下花括号里的内容记为

图片

接下来推导目标函数对参数向量的梯度

图片

利用对称性可得

图片

使用随机梯度上升法更新各参数向量

图片

下面以样本 (w, Context(w)) 为例，给出 Skip-gram 模型中使用随机梯度上升法更新各参数向量的伪代码

图片

word2vec 代码中，并不是等 Context(w) 中的所有词都处理完后才更新 v(w)，而是每处理完 Context(w) 中的一个词 u，就及时更新一次 v(w)。

4. 基于 Negative Sampling 的模型
本节将介绍基于 Negative Sampling 的 CBOW 和 Skip-gram 模型。使用 Negative Sampling（简称为NEG）主要是为了提高训练速度并改善所得词向量的质量。与 Hierarchical Softmax 相比，NEG 不再使用复杂的 Huffman 树，而是利用相对简单的随机负采样，能大幅度提高性能，因此可作为 Hierarchical Softmax 的一种替代。

4.1 负采样算法

顾名思义，在基于 Negative Sampling 的 CBOW 和 Skip-gram 模型中，负采样是个很重要的环节，对于一个给定的词 w，如何生成它对应的负样本集合 NEG(w) 呢？

词典 V 中的词在语料 C 中出现的次数有高有低，对于那些高频词，被选为负样本的概率就应该比较大；反之，对于那些低频词，被选为负样本的概率就应该比较小。这本质上是一个带权采样问题，下面用一段通俗的描述理解带权采样的机理。

图片

在 word2vec 中使用 InitUnigramTable 函数生成负采样需要用到的查找表
图片

查找表 table 的最大长度为 1e8，其中词典 V 中每个词 w 对应的长度为

图片

负采样时，随机生成 0～table_size 内的整数，该整数落到词典中哪个词的长度区间内，就取出改词进行判断是否作为负样本。
4.2 CBOW 模型

在 CBOW 模型中，已知词 w 的上下文 Context(w)，需要预测 w，对于给定的 (Context(w), w)，词 w 是一个正样本，词典中其它词为负样本，但词典很大，负样本太多，需要进行随机负采样，得到一个关于词 w 的负样本子集 NEG(w)。定义

图片

对于一个给定的样本 (Context(w), w)，我们希望最大化

图片

其中

图片

或者写成整体表达式

图片

其中 x_w 仍然表示 Context(w) 中各词的词向量求平均，将上式代入 g(w) 中可得

图片

对数似然函数

图片

为了梯度推导方便起见，记

图片

目标函数对参数向量的梯度计算如下

图片

利用对称性可得

图片

使用随机梯度上升法更新各参数向量

图片

下面以样本 (Context(w), w) 为例，给出基于 Negative Sampling 的 CBOW 模型中使用随机梯度上升法更新各参数向量的伪代码

图片

4.3 Skip-gram 模型

在 word2vec 中，基于 Negative Sampling 的 Skip-gram 模型的目标函数定义为

图片

其中

图片

最终的对数似然目标函数就是

图片

为了梯度推导方便起见，将三重求和符号下花括号内的内容记为

图片

目标函数对参数向量的梯度计算如下

图片

利用对称性可得

图片

使用随机梯度上升法更新各参数向量

图片

下面以样本 (w, Context(w)) 为例，给出基于 Negative Sampling 的 Skip-gram 模型中使用随机梯度上升法更新各参数向量的伪代码

图片

5. 结尾

本文主要介绍了 nlp 领域著名模型 word2vec 的数学原理，分别介绍了基于 Hierarchical Softmax 和 Negative Sampling 两种架构的 CBOW 模型和 Skip-gram 模型。内容多有参考 CSDN 博客：https://blog.csdn.net/itplus/article/details/37969519

一起交流

    本站是提供个人知识管理的网络存储空间，所有内容均由用户发布，不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息，谨防诈骗。如发现有害或侵权内容，请点击一键举报。
    转藏 分享 献花（0）

    来自： 520jefferson > 《机器学习/深度学习/tensorflow》

    举报/认领

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多