@leo9年前
2016-10-26
18:19
Reference:
https://github.com/zhangchen-qinyinghua/word2vector/blob/master/word2vec_full_chinese_comment.c
#include <stdio.h> // 文件输入输入使用的标准化函数
#include <stdlib.h>
// C 标准函数库的头文件，声明了数值与字符串转换函数，伪随机数生成函数，动态内存分配函数，
// 进程控制函数等公共函数。
#include <string.h>
// 涉及字符串和大量内存处理函数
#include <math.h>
// 提供用于常用高级数学运算的运算函数
#include <pthread.h>
// POSIX的线程标准，定义了创建和操纵线程的一套API
#define MAX_STRING 100 // 字符串最大字符数
#define EXP_TABLE_SIZE 1000 // sigmoid函数表格
#define MAX_EXP 6 // sigmoid函数只计算-6~6
#define MAX_SENTENCE_LENGTH 1000 // 句子最大长度，以换行符为界
#define MAX_CODE_LENGTH 40 // 哈夫曼编码的最大码长
const int vocab_hash_size = 30000000;
// maximum 30*0.7=21M words in the vocabulary
// 定义了字典里词的最大数目
typedef float real;
struct vocab_word {
long long cn;
// 词频数
int *point;
// point表示这个词汇对应的辅助向量列的index序列，其长度是codelen
// 辅助向量定义在syn1中
char *word, *code, codelen;
// *word是词本身
// *code是词对应的哈夫曼编码
// codelen是code的长度
// 参见hierarchical softmax原理
}
char train_file[MAX_STRING], output_file[MAX_STRING];
// 定义了输入输出文件（文件名），以字符数组形式储存
char save_vocab_file[MAX_STRING], read_vocab_file[MAX_STRING];
// 定义了存取词典和读词典文件（文件名）
struct vocab_word *vocab;
// 定义了动态变化的词典结构，定义见第*行
int binary=0, cbow=1, debug_mode=2, window=5, min_count=5, num_threads=12, min_reduce=1;
// 定义默认参数
// binary: 是否使用二进制
// cbow: 是否使用cbow，否则使用skip-gram
// window: 窗长，默认为5
// min_count: 出现频次小于一定值的词被舍弃
// min_reduce: 参见ReduceVocab
int *vocab_hash;
// 词典词的哈希值，一个数组
long long vocab_max_size=1000, vocab_size=0, layer1_size=100;
// 词典词数最大值为1000，之后不够用再加，当前词数为0
// layer1_size指的应该是embedding vector的维数为100，即cbow第一层的节点数
long long train_words=0, word_count_actual=0, iter=5, file_size=0, classes=0;
// 词频统计
// train_words是所有有效词汇的频率之和?
// word_count_actual ?
// iter应该是迭代次数 ?
// file_size定义文件最大体积，用于并行化时负载均衡
// classes ?
real alpha=0.025, starting_alpha, sample=1e-3;
// alpha是学习率learning rate
// starting_alpha 初始学习率，可指定
// sample参见词汇表初始化部分
real *syn0, *syn1, *syn1neg, *expTable;
// *syn0: word2vec的最终结果，大小是vector维数×输出词汇数目，以*point作为index
// *syn1: 全部辅助变量，个数比*syn0少一个 ?
// *syn1neg: 随机负采样得到的向量表
// *expTable是预先计算的sigmoid函数值，参见main函数底部
clock_t start; // 计时器，考察程序时间复杂度
int hs=0, negative=5; // 定义hierarchical softmax和negative sampling默认参数，前者默认关
// negative不为零时表示每一个word和上下文要负采样的个数
const int table_size=1e8;
int *table;
// 用于负采样，初始化负采样辅助table，保证一个单词被选为负样本的概率d1为
// (词频数)^0.75/所有词[(词频数)^0.75]之和
void InitUnigramTable() {
int a,i;
double train_word_pow=0;
double d1, power=0.75; // 为什么选择0.75作为指数尚不清楚
table=(int *)malloc(table_size * sizeof(int));
for (a=0;a<vocab_size;a++) train_words_pow+=pow(vocab[a].cn, power); // ?
i=0;
d1=pow(vocab[i].cn, power)/train_word_pow;
for (a=0;a<vocab_size;a++) {
table[a]=i;
if (a/(double)table_size>d1) {
i++;
d1+=pow(vocab[i].cn, power)/train_word_pow;
}
if (i>=vocab_size) i=vocab_size-1;
}
}
// Reads a single word from a file, assuming space+tab+EOL to be word boundaries
// 从文件中读取单个词，以空格、制表符和EOL(EOF和'\n')作为边界
// char(13)是回车('\r)
// 不同的操作系统中换行符不同，win是\r\n, unix是\n, mac是\r，需统一转换为'\n'换行
// 不认为'\r'是有效符号
// 单个换行符号'\n'被认为是有效符号，并被记为词"</s>"
// 遇到换行符作为结尾，换行符将被回退到输入流，形成一个单个换行符，下一次读为"</s>"
void ReadWord(char *word, FILE *fin) {
int a=0, ch;
while (!feof(fin)) {
ch=fgetc(fin);
if(ch==13) continue;
if((ch==' ')||(ch=='\t')||(ch=='\n')) {
if (a>0) {
if (ch=='\n') ungetc(ch,fin); // 换行符被回缩到输入流中
break;
}
if(ch=='\n') {
strcpy(word,(char*)"</s>");
return;
} else continue;
}
word[a]=ch;
a++;
if (a>=MAX_STRING-1) a--; // Truncate too long words
// 单个词汇太长时需要截断
}
word[a]=0;
}
// Return hash value of a word
// 计算词的hash值
int GetWordHash(char *word) {
unsigned long long a, hash=0;
for (a=0;a<strlen(word);a++) hash=hash*257+word[a];
hash=hash%vocab_hash_size;
return hash;
}
// Return position of a word in the vocabulary; if the word is not found, return -1
// 根据hash表查找词在词典里的位置
int SearchVocab(char *word) {
unsigned int hash=GetWordHash(word);
while(1) {
if (vocab_hash[hash]==-1) return -1;
if (!strcmp(word, vocab[vocab_hash[hash]].word) return vocab_hash[hash];
hash=(hash+1)%vocab_hash_size;
}
return -1;
}
// Reads a word and returns its index in the vocabulary
// 从输入文件中读取一个单词，返回其在词典中的位置
int ReadWordIndex(FILE *fin) {
char word[MAX_STRING];
ReadWord(word, fin);
if (feof(fin)) return -1;
return SearchVocab(word);
}
// Adds a word to the vocabulary
int AddWordToVocab(char *word) {
unsigned int hash, length=strlen(word)+1;
if (length>MAX_STRING) length=MAX_STRING; // 截断词使其长度不超过MAX_STRING
vocab[vocab_size].word=(char *)calloc(length, sizeof(char));
strcpy(vocab[vocab_size].word, word);
vocab[vocab_size].cn=0;
vocab_size++;
// Reallocate memory if needed
if (vocab_size+2>=vocab_max_size) {
vocab_max_size+=1000;
vocab=(struct vocab_word *)realloc(vocab, vocab_max_size*sizeof(struct vocab_word));
}
hash=GetWordHash(word); // 获取词的hash
while (vocab_hash[hash]!=-1) hash=(hash+1)%vocab_hash_size;
// 在hash表中线性探测，如果有位置为-1(即没有词)就将当前词插入到这个位置
vocab_hash[hash]=vocab_size-1;
return vocab_size-1;
}
// Used later for sorting by word counts
// 比较词频
int VocabCompare(count void *a, const void *b) {
return ((struct vocab_word *)b)->cn - ((struct vocab_word *)a)->cn;
}
// Sorts the vocabulary by frequency using word counts
// 重排词典
void SortVocab() {
int a, size;
unsigned int hash;
// Sort the vocabulary and keep </s> at the first position
qsort(&vocab[1], vocab_size-1, sizeof(struct vocab_word), VocabCompare);
// 用快速排序，按照词频对词典里的词进行排序，词频大的排前面
for (a=0;a<vocab_hash_size;a++) vocab_hash[a]=-1; // 重置hash表为空
size=vocab_size;
train_words=0;
for (a=0;a<size;a++) {
// Words occuring less than min_count times will be discarded from the vocab
// 词频小于某一个阈值的词，丢弃
if ((vocab[a].cn<min_count) && (a!=0)) {
vocab_size--;
free(vocab[a].word);
} else {
// Hash will be recomputed, as after the sorting it is not actual
// 剩下的词重新排列在hash表中
hash=GetWordHash(vocab[a].word);
while(vocab_hash[hash]!=-1) hash=(hash+1)%vocab_hash_size;
vocab_hash[hash]=a;
train_words+=vocab[a].cn;
// train_words是词典中所有有效词的词频之和
}
}
// 精简词典占用的内存
vocab=(struct vocab_word *)realloc(vocab,(vocab_size+1)*sizeof(struct vocab_word));
// Allocate memory for the binary tree construction
// 为哈夫曼树分配内存
for (a=0;a<vocab_size;a++) {
vocab[a].code=(char *)calloc(MAX_CODE_LENGTH,sizeof(char));
vocab[a].point=(int *)calloc(MAX_CODE_LENGTH,sizeof(int));
}
}
// Reduces the vocabulary by removing infrequent tokens
void ReduceVocab() {
int a,b=0;
unsigned int hash;
// 对于词a，若词频大于阈值，则移动到词典位置b，否则舍弃
for (a=0;a<vocab_size;a++) {
if (vocab[a].cn > min_reduce) {
vocab[b].cn=vocab[a].cn;
vocab[b].word=vocab[a].word;
b++
} else free(vocab[a].word);
vocab_size=b;
}
for (a=0;a<vocab_hash_size;a++) vocab_hash[a]=-1;
for (a=0;a<vocab_size;a++) {
// Hash will be recomputed, as it is not actual
// 重构hash表
hash=GetWordHash(vocab[a].word);
while(vocab_hash[hash]!=-1) hash=(hash+1)%vocab_hash_size;
vocab_hash[hash]=a;
}
fflush(stdout);
min_reduce++; // 每执行一次，舍弃阈值+1 why?
}
// Create binary Huffman tree using the word counts
// Frequent words will have short unique binary codes
// 构造哈夫曼树，给每个词赋予一个哈夫曼编码，词频高者码长短
// 哈夫曼树的构建使用贪心法
/*
Huffman树：最优二叉树，WPL=∑码长x权值 最低
贪心法构造Huffman树的过程：
对于已知的一组叶子节点，权值分别为W1,W2,...,Wn，约定权值小的为左子树，大的为右子树
（1）首先把n个叶子节点看成n棵树（仅有一个节点的二叉树），把它们看做一个森林
例： 2 4 5 8
（2）合并森林中最小和次小的两棵树，该树根节点的权值为两棵子树之和，此时森林中还有n-1棵树
i. 6 5 8
/ \
2 4
（3）重复第（2）步直到森林中只有一棵树为止
ii. 11 8
/\
5 6
/ \
2 4
iii. 19
/ \
8 11
/\
5 6
/ \
2 4
(done)
*/
void CreateBinaryTree() {
long long a,b,i,min1i,min2i,pos1,pos2,point[MAX_CODE_LENGTH];
// min1i,min2i是两个权值最小的节点，权值为vocab[a].cn即每个词的词频
char code[MAX_CODE_LENGTH];
long long *count=(long long *)calloc(vocab_size*2+1,sizeof(long long));
// 每个词的词频
long long *binary=(long long *)calloc(vocab_size*2+1,sizeof(long long));
// 每个词的Huffman编码，为了对齐用了更大的长度(最大码长为MAX_CODE_LENGTH=40)
long long *parent_node=(long long *)calloc(vocab_size*2+1,sizeof(long long));
// 记录所有子树的父节点
for (a=0;a<vocab_size;a++) count[a]=vocab[a].cn;
for (a=vocab_size;a<vocab_size*2;a++) count[a]=1e15;
// 剩下节点赋权一个大树，方便获取两个最小的权值
pos1=vocab_size-1;
pos2=vocab_size;
// Following algorithm constructs the Huffman tree by adding one node at a time
// 每次合并两棵权值最小的子树，直到合并vocab_size-1次
for (a=0;a<vocab_size-1;a++) {
// First, find two smallest nodes 'min1,min2'
if (pos1>=0) {
if (count[pos1]<count[pos2]) {
min1i=pos1; pos1--;
} else {
min1i=pos2; pos2++;
}
} else {
min1i=pos2; pos2++;
}
if (pos1>=0) {
if (count[pos1]<count[pos2]) {
min2i=pos1; pos1--;
} else {
min1i=pos2; pos2++;
}
} else {
min2i=pos2; pos2++;
}
count[vocab_size+a]=count[min1i]+count[min2i];
parent_node[min1i]=vocab_size+a;
parent_node[min2i]=vocab_size+a;
binary[min2i]=1;
// binary[min1i]=0, 即左子树编码0，右子树编码1
}
// Now assign binary code to each vocabulary word
for (a=0;a<vocab_size;a++) {
b=a;
i=0;
while(1) {
code[i]=binary[b];
point[i]=b;
i++;
b=parent_node[b];
if (b==vocab_size*2-2) break;
}
vocab[a].codelen=i;
vocab[a].point[0]=vocab_size-2;
for (b=0;b<i;b++) {
vocab[a].code[i-b-1]=code[b];
vocab[a].point[i-b]=point[b]-vocab_size;
}
}
free(count);
free(binary);
free(parent_node);
}
// 从训练文件中获取词语，同时读取训练文件大小用于并行计算时负载均衡
void LearnVocabFromTrainFile() {
char word[MAX_STRING];
FILE *fin;
long long a,i;
for (a=0;a<vocab_hash_size;a++) vocab_hash[a]=-1; // 初始化hash表
fin=fopen(train_file,"rb");
if (fin==NULL) {
printf("ERROR: training data file not found!\n");
exit(1);
}
vocab_size=0;
AddWordToVocab((char *)"</s>");
// 首先加入一个特殊词汇</s>, 这个词表示换行符，用于分隔行的标记
while (1) {
ReadWord(word,fin); // 读入一个词
if(feof(fin)) break;
train_words++; // train_words是词典中词的数目
if ((debug_mode)>1 && (train_words%100000==0)) {
printf("%lldK%c",train_words/1000,13);
fflush(stdout);
}
i=SearchVocab(word);
if(i==-1) {
a=AddWordToVocab(word);
vocab[a].cn=1;
}
else vocab[i].cn++;
if (vocab_size>vocab_hash_size*0.7) ReduceVocab();
// 如果词典中词汇数目达到一定数量，则清理掉一些词频较小的词
}
SortVocab(); // 排序
if(debug_mode>0) {
printf("Vocab size: %lld\n", vocab_size);
printf("Words in train file: %lld\n", train_words);
}
file_size=ftell(fin);
fclose(fin);
}
// 写入词汇到文件save_vocab_file
// 格式：词汇 词频\n
void SaveVocab() {
long long i;
FILE *fo=fopen(save_vocab_file,"wb");
for(i=0;i<vocab_size;i++) fprintf(fo, "%s %lld\n",vocab[i].word, vocab[i].cn);
fclose(fo);
}
// 从格式为“词汇 词频\n”的文件中读取词汇
void ReadVocab() {
long long a,i=0;
char c;
char word[MAX_STRING];
FILE *fin=fopen(read_vocab_file,"rb");
if (fin==NULL) {
printf("Vocabulary file not found\n");
exit(1);
}
for (a=0;a<vocab_hash_size;a++) vocab_hash[a]=-1;
vocab_size=0;
while(1) {
ReadWord(word,fin);
if(feof(fin)) break;
a=AddWordToVocab(word);
fscanf(fin,"%lld%c", &vocab[a].cn, &c);
// 读入词频，由于fscanf和ReadWord的问题，需要退掉词频后面表示边界的字符，否则scanf不会
// 读入这些符号，ReadWord会读入
i++;
}
SortVocab(); // 重排词典
if (debug_mode>0) {
printf("Vocab size: %lld\n", vocab_size);
printf("Words in train file: %lld\n", train_words);
}
fin=fopen(train_file,"rb");
if (fin==NULL) {
printf("ERROR: training data file not found!\n");
exit(1);
}
fseek(fin,0,SEEK_END);
file_size=ftell(fin);
fclose(fin);
}
void InitNet() {
long long a,b;
a=posix_memalign((void **)&syn0, 128, (long long)vocab_size*layer1_size*sizeof(real));
// 内存动态对齐
// syn0就是word2vec的计算结果，即词的向量化表示，向量维数为100，alignment=128要求为2的整数次幂
if (syn1==NULL) {
printf("Memory allocation failed\n");
exit(1);
}
//hierarchical softmax
if (hs) {
a=posix_memalign((void **)&syn1, 128, (long long)vocab_size*layer1_size*sizeof(real));
// syn1是辅助向量，大小为layer1_size，数量比syn0少一个，全零初始化
if (syn1==NULL) {
printf("Memory allocation failed\n");
exit(1);
}
for(b=0;b<layer1_size;b++) {
for(a=0;a<vocab_size;a++) syn1[a*layer1_size+b]=0;
}
}
// negative sampling
if (negative>0) {
a=posix_memalign((void **)&syn1neg,128, (long long)vocab_size*layer1_size*sizeof(real));
// 每个词一个负采样向量
if (syn1neg==NULL) {
printf("Memory allocation failed\n");
exit(1);
}
for(b=0;b<layer1_size;b++) {
for(a=0;a<vocab_size;a++) syn1neg[a*layer1_size+b]=0;
}
}
// 所有词的对应向量初始化，随机数，范围在(-0.5/维度)~(0.5/维度)上均匀分布
for(b=0;b<layer1_size;b++) {
for(a=0;a<vocab_size;a++) {
syn0[a*layer1_size+b]=(rand()/(real)RAND_MAX-0.5)/layer1_size;
}
}
//构造Huffman树
CreateBinaryTree();
}
// word2vec模型训练的主要过程
void *TrainModelThread(void *id) {
long long a,b,d,word,last_word,sentence_length=0,sentence_position=0;
// word是词在词典中的位置
long long word_count=0, last_word_count=0, sen[MAX_SENTENCE_LENGTH+1];
// word_count统计学习了多少词，每学一个就加一
// last_word_count的作用是动态变化学习率
// 每学习10000个样本，学习率就变小一次，直到变小到starting_alpha*0.0001
long long l1,l2,c,target,label,local_iter=iter;
// local_iter ?
unsigned long long next_random=(long long)id;
// 随机数以公式 next_random=next_random*(unsigned long long)*25214903917+11 产生
// 25214903917是一个大质数
real f,g;
clock_t now;
real *neu1=(real *)calloc(layer1_size, sizeof(real));
// neu1是所有输入的上下文向量之和
// neu1e是一轮迭代之后每一个word对应的向量的增量
real *neu1e=(real *)calloc(layer1_size, sizeof(real));
FILE *f1=fopen(train_file,"rb");
fseek(f1,file_size/(long long)num_threads*(long long)id, SEEK_SET(); // 并行计算
while(1) {
// 学习率更新，新句子读取，根据一个词及其上下文进行模型学习
// 学习率更新
if (word_count-last_word_count>10000) {
// 每学习10000个词，学习率就变小一次
word_count_actual += word_count+last_word_count;
last_word_count=word_count;
if ((debug_mode)>1)) {
now=clock();
printf("%cAlpha: %f Progress: %.2f%% Words/thread/sec: %.2fk ",13,alpha,
word_count_actual/(real)(iter*train_words+1)*100,
word_count_actual/((real)(now-start+1)/(real)CLOCKS_PER_SEC*1000));
fflush(stdout);
}
alpha=starting_alpha*(1-word_count_actual/(real)(iter*train_words+1));
// 学习率变化公式
if(alpha<starting_alpha*0.0001) alpha=starting_alpha*0.0001;
}
// 新句子读取
if(sentence_length==0) {
while(1) {
word=ReadWordIndex(fi); // 读入一个新句子
if(feof(fi)) break;
if(word==-1) continue;
word_count++; // 读到一个有效词，word_count增加1
if(word==0) break;
// The subsampling randomly discards frequent words while
// keeping the ranking same
if(sample>0) {
// 高频词亚采样
real ran=(sqrt(vocab[word].cn/(sample*train_words))+1)*
(sample*train_words)/vocab[word].cn;
// ran是高频词不被舍弃的概率, sample是一个参数
// ran=sqrt(f/s)*s/f=sqrt(s/f)=sqrt(sample/frequency)
// 其中s为采样数sample*train_words, f=vocab[word].cn
// 分母用s+1只是为了防止其为零，实际几乎不影响数值
// 出现频率越高的词，被舍弃的概率越大
// 于是高频词被舍弃的概率为max{0,1-ran} (?)
next_random=next_random*(unsigned long long)25214903917+11;
if(ran<(next_random&0xFFFF)/(real)65536) continue;
// 将next_random缩放到(0,1)
// 如果这个随机数大于ran(即被舍弃概率1-ran)，即被舍弃
}
sen[sentence_length]=word;
sentence_length++;
if(sentence_length>=MAX_SENTENCE_LENGTH) break;
// 如果句子过长，则只取前MAX_SENTENCE_LENGTH
}
sentence_position=0;
}
// 学习一个词及其上下文
if(feof(fi)||(word_count>train_words/num_threads)) {
word_count_actual += word_count-last_word_count;
local_iter--; // 这段的意思应该是重复迭代学习一定次数
if(local_iter==0) break;
word_count=0;
last_word_count=0;
sentence_length=0;
fseek(fi,file_size/(long long)num_threads*(long long)id, SEEK_SET);
continue;
}
word=sen[sentence_position];
// 从sentence_position=0开始一个一个词学习
if(word==-1) continue; // ?
for(c=0;c<layer1_size;c++) neu1[c]=0; // 初始化
for(c=0;c<layer1_size;c++) neu1e[c]=0; // 初始化
next_random=next_random*(unsigned long long)25214903917+11;
b=next_random%window;
// b是0到window-1的数
// 选取的上下文是(sentence_position-(window-b),sentence_postion+(window-b))的去心集合
// -----------------------------------------------------------------------------------------
// 以下部分自己敲了一遍，看了一遍Reference提供的注释，但是还是不太懂，还需要边读papaer边做笔记
// 目前找到的打算读的paper：
//
// [1] Goldberg Y, Levy O. word2vec Explained: deriving Mikolov et al.'s negative-sampling
// word-embedding method[J]. arXiv preprint arXiv:1402.3722, 2014.
// [2] Mikolov T, Sutskever I, Chen K, et al. Distributed representations of words and
// phrases and their compositionality[C]//Advances in neural information processing
// systems. 2013: 3111-3119.
// [3] Morin F, Bengio Y. Hierarchical Probabilistic Neural Network Language Model[C]//
// Aistats. 2005, 5: 246-252.
// [4] Mikolov T, Chen K, Corrado G, et al. Efficient estimation of word representations
// in vector space[J]. arXiv preprint arXiv:1301.3781, 2013.
//
// -----------------------------------------------------------------------------------------
if(cbow) {
// train the cbow architeture
// in->hidden
// CBOW模型，根据上下文学习
// 首先获取word的上下文，加和到neu1
// 然后根据是否采用hierarchical softmax和negative sampling使用不同的梯度公式
// 依次根据两种梯度公式更新辅助向量syn1，然后再更新word向量syn0
//
// CBOW: Skip-Gram:
// input projection output input projection output
// w(t-2) w(t-2)
// w(t-1) ╲ ↗ w(t-1)
// ╲ ╲ ╱ ↗
// ↘ ↘ ╱ ╱
// [sum] ─→ w(t) w(t) ─→ [ ]
// ↗ ↗ ╲ ╲
// ╱ ╱ ╲ ↘
// w(t+1) ╱ ↘ w(t+1)
// w(t+2) w(t+2)
//
cw=0;
for(a=b;a<window*2+1-b;a++) if(a!=window) {
c=sentence_position-window+a;
if(c<0) continue;
if(c>=sentence_length) continue;
last_word=sen[c];
if(last_word==-1) continue;
for(c=0;c<layer1_size;c++) neu1[c]+=syn0[c+last_word*layer1_size];
cw++;
}
if(cw) {
for(c=0;c<layer1_size;c++) neu1[c]/=cw;
if(hs) for(d=0;d<vocab[word].codelen;d++) {
f=0;
l2=vocab[word].point[d]*layer1_size;
// Propagate hidden -> output
for(c=0;c<layer1_size;c++) f+=neu1[c]*syn1[c+l2];
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' is the gradient multiplied by learning rate
g=(1-vocab[word].code[d]-f)*alpha;
// Propagate errors output -> hidden
for(c=0;c<layer1_size;c++) neu1e[c]+=g*syn1[c+l2];
// Learn weights hedden -> output
for(c=0;c<layer1_size;c++) syn1[c+l2]+=g*neu1[c];
}
// Negative Sampling
if(negative>0) for(d=0;d<negative+1;d++) {
if(d==0) {target=word; label=1;} else {
next_random=next_random*(unsigned long long)25214903917+11;
target=table[(next_random>>16)%table_size];
if(target==0) target=next_random%(vocab_size-1)+1;
if(target==word) continue;
label=0;
}
l2=target*layer1_size;
f=0;
for(c=0;c<layer1_size;c++) f+=neu1[c]*syn1neg[c+l2];
if(f>MAX_EXP) g=(label-1)*alpha;
else if(f<-MAX_EXP) g=(label-0)*alpha;
else g=(label-expTable[(int)((f+MAX_EXP)*(EXP_TABLE_SIZE/MAX_EXP/2))])*alpha;
for(c=0;c<layer1_size;c++) neu1e[c]+=g*syn1neg[c+l2];
for(c=0;c<layer1_size;c++) syn1neg[c+l2]+=g*neu1[c];
}
// hidden -> in
for(a=b;a<window*2+1-b;a++) if(a!=window) {
c=sentence_position-window+a;
if(c<0) continue;
if(c>=sentence_length) continue;
last_word=sen[c];
if(last_word==-1) continue;
for(c=0;c<layer1_size;c++) syn0[c+last_word*layer1_size]+=neu1e[c];
}
}
} else {
// train skip-gram
for(a=b;a<window*2+1-b;a++) if(a!=window) {
c=sentence_position-window+a;
if(c<0) continue;
if(c>=sentence_length) continue;
last_word=sen[c];
if(last_word==-1) continue;
l1=last_word*layer1_size;
for(c=0;c<layer1_size;c++) neu1e[c]=0;
// hierarchical softmax
if (hs) for (d=0;d<vocab[word].codelen;d++) {
f=0;
l2=vocab[word].point[d]*layer1_size;
// Propagate hidden -> output
for(c=0;c<layer1_size;c++) f+=syn0[c+l1]*syn1[c+l2];
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' is the gradient multiplied by the learning rate
g=(1-vocab[word].code[d]-f)*alpha;
// Propagate errors output -> hidden
for(c=0;c<layer1_size;c++) neu1e[c]+=g*syn1[c+l2];
// Learn weights hidden -> output
for(c=0;c<layer1_size;c++) syn1[c+l2]+=g*syn0[c+l1];
}
// Negative Sampling
if(negative>0) for (d=0;d<negative+1;d++) {
if(d==0) {target=word; label=1;}
else {
next_random=next_random*(unsigned long long)25214903917+11;
target=table[(next_random>>16)%table_size];
if(target==0) target=next_random%(vocab_size-1)+1;
if(target==word) continue;
label=0;
}
l2=target*layer1_size;
f=0;
for(c=0;c<layer1_size;c++) f+=syn0[c+l1]*syn1neg[c+l2];
if(f>MAX_EXP) g=(label-1)*alpha;
else if(f<-MAX_EXP) g=(label-0)*alpha;
else g=(label-expTable[(int)((f+MAX_EXP)*(EXP_TABLE_SIZE/MAX_EXP/2))])*alpha;
for(c=0;c<layer1_size;c++) neu1e[c]+=g*syn1neg[c+l2];
for(c=0;c<layer1_size;c++) syn1neg[c+l2]+=g*syn0[c+l1];
}
// Learn weights input -> hidden
for(c=0;c<layer1_size;c++) syn0[c+l1]+=neu1e[c];
}
}
sentence_position++;
if(sentence_position>=sentence_length) {
sentence_length=0;
continue;
}
}
fclose(fi);
free(neu1);
free(neu1e);
pthread_exit(NULL);
}
[1] Goldberg Y, Levy O. word2vec Explained: deriving Mikolov et al.’s negative-sampling
word-embedding method[J]. arXiv preprint arXiv:1402.3722, 2014.