{‘GNN’: {‘all’: [0.8666395046504872, 0.8562847093180651, 0.9716398861265362, 0.9640435184876287, 0.8392108836886408], 3: [0.740577392510326, 0.6974132867064621, 0.9713490333216288, 0.9953574444857026, 0.5289150545018884], 5: [0.7132009712213093, 0.6598948428883781, 0.9164499642829235, 0.877261060404862, 0.6204190666368979], 10: [0.7549749125423826, 0.697781128200463, 0.9703072593213862, 0.9009901207832645, 0.7001557231503547]}, ‘GENI’: {‘all’: [0.9309069855611901, 0.8238738380336529, 0.9729712747000933, 0.9719620766740265, 0.8306461081734778], 3: [0.9462325235314772, 0.6373588501536668, 0.9878327219510076, 0.9159966330318321, 0.5998317924878607], 5: [0.7533429897263055, 0.67245843432485, 0.9312311261887722, 0.9578477918353306, 0.5754025565797392], 10: [0.8265080904979714, 0.6405622327434298, 0.9157437166675653, 0.9332734698918093, 0.7619027199433952]}, ‘GAT’: {‘all’: [0.8555596245655666, 0.8465980934736308, 0.9584976477510745, 0.8930609644990938, 0.8626768752789649], 3: [0.5525945459302726, 0.5977292012380225, 0.9670326227412425, 0.6475357529023456, 0.6276871255736455], 5: [0.6110927507075893, 0.614132864249298, 0.8417359061576749, 0.7638554688144956, 0.6247033303272376], 10: [0.7581627824156286, 0.758758330673227, 0.882641529889002, 0.8207263924686434, 0.7957351171253747]}, ‘NN’: {‘all’: [0.8002277513211716, 0.8674393443630563, 0.8310979289086515, 0.7635506380429197, 0.8463421787422267], 3: [0.5341403077970077, 0.6530605850908788, 0.6271621216085606, 0.3562657650512551, 0.6986038635596178], 5: [0.57975623169414, 0.6875551114583911, 0.6299754686082361, 0.5313669532374767, 0.6520662425051122], 10: [0.6202459530790105, 0.7202157095152304, 0.6016180608285953, 0.6316433086414526, 0.7066265056861276]}, ‘LR’: {‘all’: [0.7739664508847449, 0.8624037009601283, 0.9669112458951776, 0.8142367077290456, 0.7840754160535165], 3: [0.4846892419088714, 0.6408933070418865, 0.9713490333216288, 0.5436837586054777, 0.48585364960170097], 5: [0.5374271717655098, 0.6360427324217333, 0.9456416172439631, 0.6725841606190123, 0.5628338932298829], 10: [0.6163597606741593, 0.7686601954483521, 0.9370728578855039, 0.679886468151579, 0.6763004462618359]}, ‘PR’: {‘all’: [0.8640454930078671, 0.9066707965219759, 0.9530699316866731, 0.7647175044481418, 0.7725227038983037], 3: [0.6322604858811137, 0.718995339608394, 0.9713490333216288, 0.40565180058713374, 0.4672834275445111], 5: [0.6305584551875181, 0.7066552515340047, 0.9131430534837388, 0.4617249639094137, 0.5450337070731556], 10: [0.7714512992799438, 0.8284111807598729, 0.8646634461688568, 0.6342572542503389, 0.6864916666298643]}}

{‘GNN’: {‘all’: [0.8102382341059589, 0.8115130498892497, 0.7998841736723116, 0.7673663402469901, 0.8338522226250886], 3: [0.3666689304787135, 0.2818249615203958, 0.27022479266596733, 0.07672014634050468, 0.4864613246424541], 5: [0.43772907395518834, 0.38591116931988606, 0.2913093346306469, 0.1233538609565703, 0.49857992327706285], 10: [0.3904189536855574, 0.4475722056773316, 0.40246950274834137, 0.24451429891070425, 0.5505841874608931]}, ‘GENI’: {‘all’: [0.9231494848673042, 0.9228164979393706, 0.9300487988835276, 0.9256051746363505, 0.923761465876585], 3: [0.8182557892368135, 0.8182557892368135, 0.8480266747478475, 0.8182557892368135, 0.8182557892368135], 5: [0.8505061564563527, 0.8505061564563527, 0.8722483562405471, 0.8505061564563527, 0.8505061564563527], 10: [0.8146217419771135, 0.8146217419771135, 0.830705232594902, 0.8146217419771135, 0.8146217419771135]}, ‘GAT’: {‘all’: [0.8465079694389793, 0.8136389653638539, 0.779097120541373, 0.8289776622460376, 0.8418664270605234], 3: [0.5447827023302919, 0.2932648636669766, 0.39257515104922314, 0.6013905384946462, 0.5693760481469372], 5: [0.5774662220739304, 0.44777368691999403, 0.35756303445304727, 0.5906882482942368, 0.5692432602741382], 10: [0.5500843461200602, 0.4767467102410899, 0.2987602109076046, 0.44355780003296186, 0.49367467484921773]}, ‘NN’: {‘all’: [0.8258733100028388, 0.910432262690875, 0.8489174966840036, 0.8534739083135623, 0.8066026842627751], 3: [0.5346495009047205, 0.9495743929339138, 0.5825233177841465, 0.7966765116318061, 0.4440054475191886], 5: [0.561928136228725, 0.910045514849479, 0.4903633082652921, 0.6594392482086858, 0.40104568540155333], 10: [0.513110198001699, 0.7232496512464613, 0.5771382000919483, 0.5729907009449682, 0.48854136910060286]}, ‘LR’: {‘all’: [0.818927782376222, 0.8055360066991756, 0.8422986350528251, 0.8252980021143829, 0.8210275925849435], 3: [0.4397524638747551, 0.411060227088669, 0.4454724149480455, 0.39760477210147455, 0.4726237249842059], 5: [0.47436895849322913, 0.3591468557109375, 0.527107085775569, 0.46991516749601236, 0.3772356383797896], 10: [0.46505684005646875, 0.4160696530285343, 0.5787795325406395, 0.479333560646027, 0.43201956011164483]}, ‘PR’: {‘all’: [0.816988321723711, 0.816988321723711, 0.816988321723711, 0.816988321723711, 0.816988321723711], 3: [0.233180681266007, 0.233180681266007, 0.233180681266007, 0.233180681266007, 0.233180681266007], 5: [0.38546689595103145, 0.38546689595103145, 0.38546689595103145, 0.38546689595103145, 0.38546689595103145], 10: [0.48903983592244027, 0.48903983592244027, 0.48903983592244027, 0.48903983592244027, 0.48903983592244027]}}

面上项目、青年科学基金项目、优秀青年科学基金项目、国家杰出青年科学基金,重大研究计划、重大项目、国际(地区)合作与交流项目、专项基金项目

This image has an empty alt attribute; its file name is image-4.png

Moreira C. Learning to rank academic experts[D]. Instituto Superior Tecnico, 2011.

Moreira C, Calado P, Martins B. Learning to rank academic experts in the DBLP dataset[J]. Expert Systems, 2015, 32(4): 477-493.

快速乘与快速幂

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

(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个块,对应到词的线段内就为线段代表的词,如果为中心词则跳过。

L1与L2正则

在模型较为复杂的情况下,我们常常用到正则化项来进行约束。

模型的训练是建立在经验风险最小化的角度,而加入的正则化项则是站在结构风险最小化的角度。所以问题变为经验风险和结构风险的共同优化问题。

而L1和L2正则也有多种角度的解释

首先L1正则(Lasso回归)是在原有的loss function上加入权重向量w的 1-范数,L2正则(岭回归)是在原有的loss function上加入权重向量w的 2-范数的平方。

下面从多个角度解释:

  • 图像解释
目标函数的等高线

令F为正则化项的值的话,F值固定,可以得到的L1,L2的图像为:

L1和L2

在上图中,可以看到,等值线与正则化项为F的图像 相切 于黑点。此时,对于红圈的值而言,w1和w2就是使结构风险最小化的参数。这也符合奥卡姆剃刀原则,对于能够达到相同效果的模型,选取最简单的。

这里为什么选择切点:如果令F值变大,则正则化项的图像向外扩张,可与红圈相交出现交点,但交点处对应的参数,虽然一样可以获得红圈代表的函数值,但所带来的的结构风险变大。所以相对于整个目标函数而言,经验风险不变,结构风险变大,所以并不会选取。

从另一个角度看L1正则的图像可以看到,由于图像不是平滑曲线并且在坐标轴方向有很多顶点,等值线更容易于顶点相切,从而使得某些参数为0(从而进行了特征选择),得到稀疏解。

当加入L2正则化的时候,分析和L1正则化是类似的,也就是说我们仅仅是从菱形变成了圆形而已,同样还是求原曲线和圆形的切点作为最终解。当然与L1范数比,我们这样求的L2范数的从图上来看,不容易交在坐标轴上,但是仍然比较靠近坐标轴因此这也就是我们老说的,L2范数能让解比较小(靠近0),但是比较平滑(不等于0)。

  • 求导角度
  • 先验概率角度

多维度协同过滤

一、摘要

在推荐系统的发展历程中,协同过滤算法有着很重要的影响。从根源上来理解该算法的 本质,可以从中看到社会关系的同质性现象——越相似的人喜欢的东西越相似。但是传统的 协同过滤算法中,进行相似度的计算时忽略了很多信息。对于推荐系统而言,其用户画像应 该是从多个维度来进行考量,单单使用一个数值来描述两个用户的相似度是不合理的。所以 基于该考虑,本文提出的是多维度协同过滤算法,从多个维度对用户之间的相似度进行考量。

二、问题提出

推荐系统是利用用户的相关信息进行分析处理从而为用户推荐有针对性商品的一个工 具。推荐系统的传统实现方法有协同过滤的方法,本文所要介绍的模型是在对同质性现象的 产生机制有了一些理解后,对协同过滤算法进行了一些改进。

三、同质性与协同过滤算法

3.1 同质性原理

在社会交往关系中,存在着同质性现象。早在很久之前,就有人观察到了社会中的同质 性现象。柏拉图曾经说过:“相似性带来友谊”,亚里士多德认为,人们喜欢与自己相似的人。 同质性的形成有两种机制:第一种是身份同质性,即具有相同社会阶层,财富和地位的人会 更趋向于相互联系;第二种是价值同质性,即用相同方式进行思考或喜欢相同东西人会更趋 向于相互联系。 基于第二种同质性机制,可以看出存在这种机制——喜欢相同东西的人会更趋向相互联 系。并且除此之外,人们可能因为相似进而产生联系,同时也有可能因为产生联系进而变得 相似。所以,对于相似的用户,除了他们共同喜欢的物品,他们也可能会喜欢另一个人的其 他物品。基于这种想法,有了推荐系统中的协同过滤算法。

3.2 协同过滤算法

协同过滤算法分为基于用户的协同过滤和基于物品的协同过滤,其内在思想是相似的, 所以接来下用基于用户的协同过滤算法来进行说明。User-User CF 是通过计算用户之间的相 似度进而预测用户对于一些商品的评分并排序,然后为用户进行推荐的。其关键在于用户之 间的相似度计算,它的实现方式是根据两个用户已有的对于所有物品的评分数据(允许有缺 失),通过相似度公式进行计算(Pearson 相关系数或余弦相似度)。之后通过用户之间的相 似度矩阵,为每个用户预测对商品的评分,由高到低将商品推荐给用户。

四、算法的改进与模型设计

4.1 改进思路

从基本的同质性现象开始,其产生是因为用户喜欢相同的东西。但是对于一个用户而言, 其画像应该是多维度的,每个用户会有多个不同的喜好,并且对于这些喜好有不同的比重。 对于两个不同的用户,他们可能在某一个喜好方向上十分相似,但其他喜好并不相似,在这 种情况下,如果用协同过滤简单的计算两用户的相似度会淡化其在同一方向上的共同喜好, 即忽略了有用的信息。所以在不同的喜好或类别分别计算用户之间的相似度是有必要的,从 而可以跟细粒度的分析用户相似关系。在相似度较大的维度上,用户之间可以提供较多的信 息,在相似度较小的维度上,则提供较少的信息。这样对于用户的评分预测也会更加精确。

4.2 模型设计

首先是模型中的各类参数:

  • 1. 可以用商品的标签全集作为所有的维度 N。
  • 2. 各个用户在各个维度下的占比矩阵。
  • 3. N 个用户相似度矩阵,每一个维度上都有一个相似度矩阵。
  • 4. 各个物品所属各个维度的矩阵(可以是用 0,1 填充的矩阵)。
  • 5. 各个用户与各个商品的评分矩阵。

对各个参数的计算方式:

  • 1. 每个商品都有一个或多个标签,所有标签的个数作为维度数 N。
  • 2. 根据每个用户的收藏商品,浏览商品以及购买过的商品的标签的比例可以得出该用 户在各个维度上的占比。
  • 3. 在每一个维度上都需要计算一个相似度矩阵。用于计算相似度的物品是属于该维度 的物品集合,使用这些物品的评分计算相似度。拿一个维度(运动装备)举例来说, 需要用到用户在跑步鞋,篮球鞋等,这些属于该维度的商品的评分来计算用户间的 相似度。对于相似度的计算公式,还是采用 Pearson 相关系数:

其中𝑅𝑖,𝑥代表的是用户 i 在 x 商品上的评分,𝑅𝑖 ̅代表的是用户 i 在𝐼𝑖𝑗上的平均评分。 𝐼𝑖𝑗的意义是在当前维度上,用户 i 和用户 j 共同评价过的,且属于该维度的商品集 合。

  • 4. 每个物品都有所属的类别标签,在所有维度上,将其所属的维度的位置的值设为 1, 其余值置 0。
  • 5. 通过用户为商品评分或者评论获得该评分矩阵的数据。 在做完这些前置工作之后,需要利用这些数据预测用户评分从而完成对用户的推荐。

下 面介绍的是对一个未评分商品预测用户的评分。 现在已有的是上面 5 个列举出来的数据,和一个用户 i 没有评分的商品 p。

  • 1) 首先得到该商品的标签,确定需要计算的多个维度。
  • 2) 得到对应维度的多个用户相似度矩阵。
  • 3) 对每一个相似度矩阵,都计算一次如下步骤:所有对商品 p 有过评分的用户,计算 加权平均和,权值为该用户与用户 i 的相似度。可以得到一个预测的评分值 x。
  • 4) 由于步骤 3 可以产生多个评分值 x,所以需要将步骤 3 产生的多个评分预测值进行 加权平均,其权值为用户在该维度的上的占比。最后得出的加权平均后的值为预测 用户 i 在商品 p 上的评分。 在得到评分后即可进行排序,进而为用户进行推荐。

4.3 模型的不足

虽然通过更细粒度的划分并计算用户相似度,但是该模型保留了之前模型的缺点:

  • 1. 数据的稀疏性问题。
  • 2. 相较于之前的模型,多个维度下的多个相似度矩阵会占用更多的内存空间。

(以上内容为自行设计,并未查证是否已经被提出过。)