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
一起交流
