快速乘与快速幂

取英文首字母来命名函数名称:

(1) multiply乘;(2) power-幂;(3) quick-快速;(4) mod-取模

①快速乘由于计算机底层设计的原因,做加法往往比乘法快的多,因此将乘法转换为加法计算将会大大提高乘法运算的速度,除此之外,当我们计算 a*b%mod 的时候,往往较大的数计算 a*b 会超出long long int的范围,这个时候使用快速乘法方法也能解决上述问题。

快速乘法的原理就是利用乘法分配率来将a*b转化为多个式子相加的形式求解(注意这时使用乘法分配率的时候后面的一个乘数转化为二进制的形式计算)

eg:20*14 = 20*(1110)2 = 20*(2^3)*1 + 20*(2^2)*1+20*(2^1)*1+20*(2^0)*0 = 160+80+40 = 280

typedef long long ll;
ll qm(ll a,ll b){
ll ans=0;
while(b){
if(b&1)ans+=a;
b>>=1;
a<<=1;
}
return ans;
}

②快速乘取模

typedef long long ll;
ll qmm(ll a,ll b,ll mod){
ll ans=0;
while(b){
if(b&1)ans=(ans+a)%mod;
a<<=1;
b>>=1;
}
return ans;
}

③快速幂
typedef long long ll;
ll qp(ll x,ll p){
ll ans=1;
while(p){
if(p&1)ans*=x;
p>>=1;
x*=x;
}
return ans;
}

④快速幂取模(二阶),即求(x^p)%mod
typedef long long ll;
ll qpm(ll x,ll p,ll mod){
ll ans=1;
while(p){
if(p&1)ans=ans*x%mod;
p>>=1;
x=x*x%mod;
}
return ans;
}

⑤快速幂取模(三阶),即求(a^(b^c))%mod三阶和二阶的函数一样,只是输出方程有变:qpm(a,qpm(b,c,mod-1),mod);

⑥快速幂取模+快速乘取模(最优)
typedef long long ll;
ll qmm(ll a,ll b,ll mod){
ll ans=0;
while(b){
if(b&1)ans=(ans+a)%mod;
b>>=1;
a=(a<<1)%mod;
}
return ans;
}
ll qpm(ll x,ll p,ll mod){
ll ans=1;
while(p){
if(p&1)ans=qmm(ans,x,mod);
p>>=1;
x=qmm(x,x,mod);
}
return ans;
}

Word2Vec——CBOW·Skip-Gram&哈夫曼树与负采样

CBOW和Skip-Gram两种神经网络语言模型:

CBOW是使用上下文词预测中心词,Skip-Gram是使用中心词预测上下文词。所以在迭代过程中,CBOW会更新所有上下文的词向量,Skip-Gram只更新中心词的词向量。

不同于之前的神经网络语言模型,这两个模型的输入不是词语的one-hot向量,而是随机的M维向量。M维指定的词向量维度。相当于少了一个look up的步骤,(one-hot向量从权重矩阵获取对应行的词向量,原来的模型训练后的词向量就是输入层到隐层的权重矩阵。)现在的随机初始化每个词的向量相当于初始化了之前的权重矩阵。

CBOW将上下文中的所有词向量取平均值获得1*M的向量。Skip-gram无此步骤。

从隐层到输出层:(个人理解)之前的DNN模型在将隐层词向量经过权重矩阵后得到的向量计算softmax,即每个词的预测概率,然后计算交叉熵,计算梯度更新权重。

对于百万级的词汇表,对每个样本都需要通过softmax计算概率是十分消耗时间的。所以第一个优化策略是使用Hierarchical Softmax,具体的实现方式是使用哈夫曼树:

根据词频统计构造哈夫曼树;哈夫曼树中的每个非叶子节点都是一个逻辑回归模型。

可以看出,之前的模型计算softmax需要对每个单词计算,现在只需要按照树的结构向下走,所以复杂度是 n->logn。

对于哈夫曼树,高频的词距离根节点更近,所以如果遇到较为生僻的词,按照树的结构需要走到最底部。依旧是比较复杂。

Negative Sampling是另一种方法,负采样是通过采样的方法,一个训练样本,有一个中心词w和2c个上下文词。那么通过采样就可以得到neg个不同于w的词作为负样本进行训练,所以有一个正例和neg个负例,然后计算这些样本的二元逻辑回归,需要最大化正例样本的条件概率。

负采样的方法是通过将0-1区间划分V个块,V为词汇数目;每个块的长度由统计频率决定。

设定一个远大于V的数字M,将0-1划分M块,采样时只需从M块中选取neg个块,对应到词的线段内就为线段代表的词,如果为中心词则跳过。