word2vec中的數(shù)學模型

520jefferson 2021-07-01

展開全文

1. 簡介

2. 預(yù)備知識

2.1 logistic回歸

邏輯回歸（Logistic Regression）是一種用于解決二分類（0 or 1）問題的機器學習方法，用于估計某種事物的可能性。比如某用戶購買某商品的可能性，某病人患有某種疾病的可能性，以及某廣告被用戶點擊的可能性等。

邏輯回歸（Logistic Regression）與線性回歸（Linear Regression）都是一種廣義線性模型（generalized linear model）。邏輯回歸假設(shè)因變量 y 服從伯努利分布，而線性回歸假設(shè)因變量 y 服從高斯分布，因此與線性回歸有很多相同之處，去除Sigmoid映射函數(shù)的話，邏輯回歸算法就是一個線性回歸?？梢哉f，邏輯回歸是以線性回歸為理論支持的，但是邏輯回歸通過Sigmoid函數(shù)引入了非線性因素，因此可以輕松處理0/1分類問題。

首先介紹一下Sigmoid函數(shù)：

其函數(shù)曲線如下：

從上圖可以看到sigmoid函數(shù)是一個s形的曲線，它的取值在[0, 1]之間。

邏輯回歸的假設(shè)函數(shù)形式如下：

因此

其中是我們的輸入，為我們要求取的參數(shù)向量

邏輯回歸中的代價函數(shù)為交叉熵損失函數(shù)：

使用梯度下降算法更新參數(shù)，以最小化代價函數(shù)：

在邏輯回歸中，假設(shè)函數(shù)

用于計算樣本屬于某類別的可能性；決策函數(shù)

用于計算給定樣本的類別；決策邊界

是一個方程，用于標識出分類函數(shù)（模型）的分類邊界。使用sklearn實現(xiàn) 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 模型預(yù)測的混淆矩陣、熱圖和 ROC 曲線如下：

2.2 Huffman編碼

霍夫曼樹是二叉樹的一種特殊形式，又稱為最優(yōu)二叉樹，其主要作用在于數(shù)據(jù)壓縮和編碼長度的優(yōu)化。

2.2.1 路徑和路徑長度

在一棵樹中，從一個結(jié)點往下可以達到的孩子或?qū)O子結(jié)點之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點的層數(shù)為1，則從根結(jié)點到第L層結(jié)點的路徑長度為L-1。

圖中所示二叉樹結(jié)點A到結(jié)點D的路徑長度為2，結(jié)點A到達結(jié)點C的路徑長度為1。

2.2.2 帶權(quán)路徑長度

若將樹中結(jié)點賦給一個有著某種含義的數(shù)值，則這個數(shù)值稱為該結(jié)點的權(quán)。結(jié)點的帶權(quán)路徑長度為：從根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積。

樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點的帶權(quán)路徑長度之和，記為WPL。上圖所示二叉樹的WPL: WPL = 6 * 2 + 3 * 2 + 8 * 2 = 34。

2.2.3 霍夫曼樹

給定n個權(quán)值作為n個葉子結(jié)點，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為霍夫曼樹(Huffman Tree)。

上圖所示的兩棵二叉樹，葉子結(jié)點為A、B、C、D，對應(yīng)權(quán)值分別為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構(gòu)成葉子結(jié)點的二叉樹形態(tài)有許多種，但是WPL最小的樹只有上圖右邊所示的形態(tài)。則第二棵樹為一棵霍夫曼樹。

構(gòu)造霍夫曼樹主要運用于編碼，稱為霍夫曼編碼。上圖中霍夫曼樹的構(gòu)造過程如下：

(1) 選擇結(jié)點權(quán)值最小的兩個結(jié)點構(gòu)成一棵二叉樹

(2) 則現(xiàn)在可以看作由T1，A，B構(gòu)造霍夫曼樹，繼續(xù)執(zhí)行步驟1。選則B和T1構(gòu)成一棵二叉樹

(3) 現(xiàn)在只有T2和A兩個結(jié)點，繼續(xù)執(zhí)行步驟1。選擇A和T2構(gòu)成一棵二叉樹

經(jīng)過上述步驟可以構(gòu)造完一棵霍夫曼樹。通過觀察可以發(fā)現(xiàn)，霍夫曼樹中權(quán)值越大的結(jié)點距離根結(jié)點越近。圖中四個葉子結(jié)點的編碼結(jié)果為：

結(jié)點	編碼
A	0
B	10
C	110
D	111

采用霍夫曼樹可以適當降低編碼長度，尤其是在編碼長度較長，且權(quán)值分布不均勻時，采用霍夫曼編碼可以大大縮短編碼長度。

2.2.4 代碼實現(xiàn)

給定n個權(quán)值 {w1,w2,...,wn} 作為二叉樹的n個葉子結(jié)點，可通過以下算法來構(gòu)造一棵霍夫曼樹：

(1) 將 {w1,w2,...,wn} 看成是有n棵樹的森林，每棵樹只有一個結(jié)點。

(2) 在森林中選出兩個根節(jié)點權(quán)值最小的樹合并，作為一棵新樹的左右子樹，且新

樹的根節(jié)點權(quán)值為其左右子樹根節(jié)點權(quán)值之和。

(3) 從森林中刪除選取的兩棵樹，并將新樹加入森林。

(4) 重復(fù)(2)(3)步，直到森林中只剩一棵樹為止，該樹即為所求的Huffman樹。

在word2vec中，將詞典中的所有單詞作為葉子結(jié)點，詞頻為葉子結(jié)點的權(quán)值，構(gòu)造一棵Huffman樹，詞頻越大的詞離根節(jié)點越近。對每個單詞進行Huffman編碼，左、右子樹中權(quán)值較大的孩子結(jié)點編碼為1，較小的孩子結(jié)點編碼為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;  }  // 構(gòu)造霍夫曼樹的非葉子結(jié)點  int index1 = n - 1;  int index2 = n;  int min1, min2;  for (size_t i = 0; i < n - 1; i++) {    // 找出權(quán)重最小的兩個結(jié)點編號    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++;    }    // 合并兩個權(quán)值最小的結(jié)點    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);  // 葉子結(jié)點的霍夫曼編碼  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;}

代碼運行結(jié)果：

3. 基于 Hierarchical Softmax 的模型

本節(jié)開始介紹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) 的前提下預(yù)測當前詞 w(t)；而后者恰恰相反，是在已知當前詞 w(t) 的前提下，預(yù)測其上下文 w(t-2), w(t-1), w(t+1), w(t+2)。

對于 CBOW 和 Skip-gram 兩個模型，word2vec 給出了兩套框架，它們分別基于 Hierarchical Softmax 和 Negative Sampling 來進行設(shè)計。本節(jié)介紹基于 Hierarchical Softmax 的 CBOW 和 Skip-gram 模型。

基于神經(jīng)網(wǎng)絡(luò)的語言模型的目標函數(shù)通常取為如下對數(shù)似然函數(shù)：

其中的關(guān)鍵是條件概率函數(shù) p(w|Context(w)) 的構(gòu)造。對于 word2vec 中基于 Hierarchical Softmax 的 CBOW 模型，要優(yōu)化的目標函數(shù)形如上式；而對于基于 Hierarchical Softmax 的 Skip-gram 模型，要優(yōu)化的目標函數(shù)則形如：

討論過程中我們將重點放在 p(w|Context(w)) 和 p(Context(w)|w) 的構(gòu)造上，接下來將從數(shù)學推導的角度對這兩個模型進行詳細介紹。

3.1 CBOW 模型

下圖給出了 CBOW 模型的網(wǎng)絡(luò)結(jié)構(gòu)，它包含3層：輸入層、投影層和輸出層。下面以單個樣本 (Context(w), w) 為例（假設(shè) Context(w) 由 w 前后各 c 個詞構(gòu)成），對這三個層做簡要說明。

1. 輸入層：包含 Context(w) 中 2c 個詞的詞向量：

其中 m 表示詞向量的長度。

2. 投影層：將輸入層 2c 個詞的詞向量求平均，即

3. 輸出層：輸出層對應(yīng)一棵二叉樹，它是以語料中出現(xiàn)過的詞為葉子結(jié)點，以各詞在語料中出現(xiàn)的次數(shù)為權(quán)值構(gòu)造出來的 Huffman 樹。在這棵 Huffman 樹中，葉子結(jié)點共 N=|V| 個，分別對應(yīng)詞典 V 中的詞，非葉子結(jié)點 N-1 個（圖中標記為黃色的那些結(jié)點）。

Hierarchical Softmax 是 word2vec 中用于提高性能的一項關(guān)鍵技術(shù)。在具體介紹該技術(shù)前，先引入若干相關(guān)符號，考慮 Huffman 樹中的某個葉子結(jié)點，假設(shè)它對應(yīng)詞典 V 中的詞 w，記

：從根結(jié)點出發(fā)到達 w 對應(yīng)葉子結(jié)點的路徑。
：路徑中包含的結(jié)點個數(shù)。
路徑中的所有結(jié)點：

其中第一個表示根結(jié)點，最后一個表示詞 w 對應(yīng)的葉子結(jié)點。

詞 w 的 Huffman 編碼：

表示路徑中第 j 個結(jié)點對應(yīng)的編碼（根結(jié)點不對應(yīng)編碼）。

路徑的權(quán)重參數(shù)：

表示路徑中第 j 個非葉子結(jié)點對應(yīng)的權(quán)重向量。該權(quán)重向量為算法的輔助向

量。

對于詞典 V 中的任意詞 w，Huffman 樹中必存在一條從根結(jié)點到詞 w 對應(yīng)葉子結(jié)點的路徑（且這條路徑是唯一的）。路徑上存在 n - 1 個分支，將每個分支看成一次二分類，每一次二分類就產(chǎn)生一個概率，將這些概率連乘起來，就是所需的 p(w|Context(w))。條件概率 p(w|Context(w)) 的一般公式可寫為：

word2vec 中約定編碼為0的結(jié)點為正類，編碼為1的結(jié)點為負類。根據(jù) 2.1 中介紹的邏輯回歸，一個結(jié)點被分為正類的概率為

一個結(jié)點被分為負類的概率為

因此

將上式代入對數(shù)似然函數(shù)，可得

為了梯度求解方便，將上式中雙重求和符號下花括號內(nèi)的內(nèi)容記為

至此，已經(jīng)推導出基于 Hierarchical Softmax 的 CBOW 模型的目標函數(shù)。word2vec 中采用隨機梯度上升法最大化對數(shù)似然函數(shù)。隨機梯度上升法的做法是：每取一個樣本 (Context(w), w)，就對目標函數(shù)中的所有相關(guān)參數(shù)進行一次更新。目標函數(shù)對參數(shù)向量的梯度計算如下

參數(shù)向量的更新公式為

下面以樣本 (Context(w), w) 為例，給出 CBOW 模型中采用隨機梯度上升法更新各參數(shù)向量的偽代碼

3.2 Skip-gram 模型

本小節(jié)介紹 word2vec 中的另一個重要模型 — Skip-gram 模型，推導過程與 CBOW 大同小異，將沿用上一小節(jié)引入的記號。

上圖給出了 Skip-gram 模型的網(wǎng)絡(luò)結(jié)構(gòu)，與 CBOW 模型的網(wǎng)絡(luò)結(jié)構(gòu)一樣，也包括三層：輸入層、投影層和輸出層。下面以樣本 (w, Context(w)) 為例，對這三個層做簡要說明：

1. 輸入層：只含當前樣本中心詞 w 的詞向量 v(w)；

2. 投影層：這是個恒等投影，把 v(w) 投影到 v(w)。因此這個投影層是多余的，之所以保留主要是方便和 CBOW 模型的網(wǎng)絡(luò)結(jié)構(gòu)做對比；

3. 輸出層：和 CBOW 模型一樣，輸出層也是一棵霍夫曼樹。

對于 Skip-gram 模型，已知的是當前詞 w，需要對其上下文 Context(w) 中的詞進行預(yù)測，關(guān)鍵是條件概率函數(shù) p(Context(w)|w) 的構(gòu)造，Skip-gram 模型中將其定義為

上式中的 p(u|w) 可以按照上一小節(jié)介紹的 Hierarchical Softmax 思想，類似地寫為

其中

對數(shù)似然目標函數(shù)為

同樣，為了梯度推導方便，將三重求和符號下花括號里的內(nèi)容記為

接下來推導目標函數(shù)對參數(shù)向量的梯度

利用對稱性可得

使用隨機梯度上升法更新各參數(shù)向量

下面以樣本 (w, Context(w)) 為例，給出 Skip-gram 模型中使用隨機梯度上升法更新各參數(shù)向量的偽代碼

word2vec 代碼中，并不是等 Context(w) 中的所有詞都處理完后才更新 v(w)，而是每處理完 Context(w) 中的一個詞 u，就及時更新一次 v(w)。

4. 基于 Negative Sampling 的模型

本節(jié)將介紹基于 Negative Sampling 的 CBOW 和 Skip-gram 模型。使用 Negative Sampling（簡稱為NEG）主要是為了提高訓練速度并改善所得詞向量的質(zhì)量。與 Hierarchical Softmax 相比，NEG 不再使用復(fù)雜的 Huffman 樹，而是利用相對簡單的隨機負采樣，能大幅度提高性能，因此可作為 Hierarchical Softmax 的一種替代。

4.1 負采樣算法

顧名思義，在基于 Negative Sampling 的 CBOW 和 Skip-gram 模型中，負采樣是個很重要的環(huán)節(jié)，對于一個給定的詞 w，如何生成它對應(yīng)的負樣本集合 NEG(w) 呢？

詞典 V 中的詞在語料 C 中出現(xiàn)的次數(shù)有高有低，對于那些高頻詞，被選為負樣本的概率就應(yīng)該比較大；反之，對于那些低頻詞，被選為負樣本的概率就應(yīng)該比較小。這本質(zhì)上是一個帶權(quán)采樣問題，下面用一段通俗的描述理解帶權(quán)采樣的機理。

在 word2vec 中使用 InitUnigramTable 函數(shù)生成負采樣需要用到的查找表

查找表 table 的最大長度為 1e8，其中詞典 V 中每個詞 w 對應(yīng)的長度為

負采樣時，隨機生成 0～table_size 內(nèi)的整數(shù)，該整數(shù)落到詞典中哪個詞的長度區(qū)間內(nèi)，就取出改詞進行判斷是否作為負樣本。

4.2 CBOW 模型

在 CBOW 模型中，已知詞 w 的上下文 Context(w)，需要預(yù)測 w，對于給定的 (Context(w), w)，詞 w 是一個正樣本，詞典中其它詞為負樣本，但詞典很大，負樣本太多，需要進行隨機負采樣，得到一個關(guān)于詞 w 的負樣本子集 NEG(w)。定義

對于一個給定的樣本 (Context(w), w)，我們希望最大化

其中

或者寫成整體表達式

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

對數(shù)似然函數(shù)

為了梯度推導方便起見，記

目標函數(shù)對參數(shù)向量的梯度計算如下

利用對稱性可得

使用隨機梯度上升法更新各參數(shù)向量

下面以樣本 (Context(w), w) 為例，給出基于 Negative Sampling 的 CBOW 模型中使用隨機梯度上升法更新各參數(shù)向量的偽代碼

4.3 Skip-gram 模型

在 word2vec 中，基于 Negative Sampling 的 Skip-gram 模型的目標函數(shù)定義為

其中

最終的對數(shù)似然目標函數(shù)就是

為了梯度推導方便起見，將三重求和符號下花括號內(nèi)的內(nèi)容記為

目標函數(shù)對參數(shù)向量的梯度計算如下

利用對稱性可得

使用隨機梯度上升法更新各參數(shù)向量

下面以樣本 (w, Context(w)) 為例，給出基于 Negative Sampling 的 Skip-gram 模型中使用隨機梯度上升法更新各參數(shù)向量的偽代碼

5. 結(jié)尾

本文主要介紹了 nlp 領(lǐng)域著名模型 word2vec 的數(shù)學原理，分別介紹了基于 Hierarchical Softmax 和 Negative Sampling 兩種架構(gòu)的 CBOW 模型和 Skip-gram 模型。內(nèi)容多有參考 CSDN 博客：https://blog.csdn.net/itplus/article/details/37969519