推荐系统中的冷启动问题和探索利用问题

冷启动和探索利用问题是推荐系统技术中的两个关键问题,本文结合达观数据的技术实战,对问题的解决方案进行了梳理和介绍。

1 前言

互联网技术和大数据技术的迅猛发展正在时刻改变我们的生活,视频网站、资讯app、电商网站等每天都有大量的活跃用户在不断的产生海量的用户行为,同时,每天又都产生大量的新增PGC或者UGC内容(如小说、资讯文章、短视频等)。

推荐系统的角度来看,系统每时每刻都面临大量的新旧用户、新旧物品和大量的用户行为数据,对于用户,我们需要对要用户进行建模,去刻画用户的肖像和兴趣,然而我们常常面对的情况是用户的行为是稀疏的,而且可能存在比例不一的新用户,如何给新用户推荐,是推荐系统中的一个著名问题,即冷启动问题,给新用户展示哪些item决定了用户的第一感和体验;同时在推荐过程中,我们需要考虑给新item展示的机会,比如给一个喜欢科幻电影的user推荐一些非科幻类型的电影,提高推荐的多样性,这就是推荐系统中另外一个问题,即探索和利用的问题。

2 冷启动和EE问题

推荐系统需要根据历史的用户行为和兴趣偏好预测用户未来的行为和兴趣,因此历史用户行为某种程度上成为推荐推荐的重要先决条件。实际过程中,我们面对大量的新用户,这些用户我们并不知道他们的profile,对于这些用户,常用的冷启动的算法包括根据已有的个人静态信息(年龄、性别、地理位置、移动设备型号等)为用户进行推荐。然而实际情况下,我们很难在系统中直接获取这些用户信息。给新用户推荐的item,由于成本较高(用户不感兴趣就再也不来了),我们需要保证item要足够热门,要保证足够的多样性,同时尽量保证可区分。 

与用户的冷启动相对应的,则是item的冷启动,当一个新物品加入站内,如何快速的展现的用户。特别是在某些场景下,推荐列表是给用户展示的唯一列表,那么显而易见,只能在推荐列表中尝试给用户推荐新物品。对于CF算法来说,无论是基于领域还是基于模型,如果想要这个新物品被推荐出来,显然我们需要获得用户对这个物品的行为数据。一个最简单的做法就是在推荐列表中随机给用户展示新物品,但是这样显然不太个性化。一个较好的做法是将新物品推荐给曾经喜欢过与新物品相似物品的用户。由于新item没有用户行为,因此物品相似度只能从item自身出发,包括根据item的内容信息挖掘出item的向量表示,通过向量相似度来刻画物品相似度,还可以利用topic model挖掘出item的主题分布等等。

推荐系统需要考虑对用户兴趣的不断探索和细化,同时也需要尽可能的扩大展示物品的多样性和宽度。比如极端情况下给用户展示物品的场景只有推荐列表,同时我们需要尽可能优化的ctr,那么给冷启动用户我们该如何选择物品,如何快速的探测出用户的兴趣?

举例来说,对于一个热爱足球的足球迷我们该如何选择给他推荐的物品?比较简单的方式我们可以可以根据ctr排序,给冷启动用户推荐最热门、点击率最高的物品,给他推荐点击率最高的足球相关物品,显然这样做会保证我们推荐结果的ctr会比较高,但是这样做会减少我们推荐结果的覆盖率,降低推荐结果的多样性,以致于推荐物品候选集也会收敛,出现反复推荐。比如对于资讯来说,用户看到的资讯都是点击率较高的搞笑类,但是显然“搞笑”并不能刻画的兴趣。而这也就是我们必须得不断探索用户兴趣,扩大推荐结果多样性的原因。

简单来看这其实是一个选择问题,即探索(exploration)和利用(exploitation)问题。接下来本文接下来将详述EE问题和某些已有算法。

3 多臂老虎机模型和UCB算法

当你走进一家赌场,面对20个一模一样的老虎机,你并不知道它们吐钱的概率。假设你的成本是1000元,每摇一次的成本是2元,那么你在总共500次摇臂的机会下,该如何最大化你的收益呢? 这就是多臂老虎机问题(Multi-armed bandit problem, K-armed bandit problem, MAB)。

一个简单的做法就是每台老虎机我们都摇10次,余下的300次都选择成功率最高的那台。但是显然我们耗费了200次机会来探索,而且我们仍然无法保证实验成功率最高的那台老虎机就是真实成功率最高的。大家也可以猜到,如果我们有足够多的探索机会,那么我们几乎可以选择出成功率最高的老虎机。很遗憾,我们没有足够的探索机会,对应到我们的推荐问题中就是任何的用户展示pv都是珍贵的,况且实际情况的“老虎机”远远不止20台,而且还存在不断新加入的情况,这就导致获取每个item收益率的成本太大。

 我们使用累计遗憾(collect regret)来衡量策略的优劣:

t表示当前轮数,表示平均最大收益,表示 第t轮的实际收益。累计遗憾公式表明了实际累计收益和理想最佳收益的差值。为了简单起见,我们假设每台机器的收益为伯努利收益,即收益要么是0,要么是1。对应到推荐系统中,老虎机即对应我们的物品(item),每次摇臂即认为是该物品的一次展示,我们可以用是否点击来表示收益,点击(win)的收益就是1,没有点击(lose)的收益就是0。

解决bandit问题的算法众多,一般分为基于semi-uniform的策略、probability matching 策略、pricing策略等。这里只列举若干个策略,具体大家可以参考(https://en.wikipedia.org/wiki/Multi-armed_bandit)。

Epsilon-greedy策略:每次试验都以的概率选择前面试验中平均收益最佳的item,以的概率等概率随机选择其他item,该策略简单,而且可以通过 

Epsilon-first策略:该策略探索和利用交叉选择,总试验次数为N,探索次数为,探索阶段也是等概率随机选择所有item,利用阶段也是选择平均收益最好的机器。

 Epsilon-decreasing策略:与Epsilon-greedy策略近似,不同地方在于随着试验的进行会不断减少。

UCB(Upper Confidence Bound)算法

推荐系统中,通常量化一个物品的收益率(或者说点击率)是使用点击数/展示数,例如点击为10,展示数为8,则估计的点击率为80%,在展示数达到10000后,其表现ctr是否还能达到80%呢? 显然是不可能的。而这就是统计学中的置信度问题,计算点击率的置信区间的方法也有很多,比如威尔逊置信空间(https://en.wikipedia.org/wiki/Binomial_proportion_confidence_interval#Wilson_score_interval)。

UCB算法步骤包括:首先对所有item的尝试一下,然后每次选择以下值最大的那个item:

,其中是物品到目前的收益均值,本质上是均值的标准差。t是目前的试验次数,是这个item被试的次数。

这个公式表明随着每个物品试验次数的增加,其置信区间就越窄,收益概率就越能确定。如果收益均值越大,则被选中的机会就越大(exploit),如果收益均值越小,其被选中的概率也就越少,同时哪些被选次数较少的item也会得到试验机会,起到了explore的作用。

Probability-matching策略表明一台机器的选择次数应当与它是最佳收益item的概率相同。其中Thompson采样就是一种Probability-matching策略算法,该算法也是一个的在线学习算法,即通过不断的观察数据来更新模型参数

Thompson采样

Thompson采样假设每个item的收益率为p,那么如何来估计一个item的收益概率p呢?直接用试验结果的收益概率p是否合理呢? 比如一个item给用户展示了20次,用户点击了16次,那么我们可以认为这个item的收益率是80%吗?而这显然是不合理的,因为我们首先需要考虑的就是这个收益率的置信度,20次试验得出的结果置信度小于试验了10000次试验的置信度,其次可能我们的经验表明所有item的平均收益率只有10%。

Thompson采样使用Beta分布来描述收益率的分布(分布的分布: https://en.wikipedia.org/wiki/Beta_distribution),我们通过不断的试验来估计一个置信度较高的基于概率p的概率分布。假设概率p的概率分布符合Beta(wins, lose),beta分布有两个参数wins和lose,每个item都维护了beta分布的参数,每次试验都选择一个item,有点击则wins增加1,否则lose增加1。每次选择item的方式则是:用每个item的beta分布产生一个随机数,选择所有item产生的随机数中的最大的那个item。Beta分布概率密度函数如下:

举例来说,推荐系统需要试探新用户的兴趣,假设我们用内容类别来表示每个用户的兴趣,通过几次展示和反馈来获取用户的兴趣。针对一个新用户,使用Thompson算法为每一个类别采样一个随机数,排序后,输出采样值top N 的推荐item。获取用户的反馈,比如点击。没有反馈则更新对应类别的lose值,点击了则更新对应类别的wins值。

4 LinUCB算法 

回到推荐列表的场景,推荐系统为用户推荐物品。user和item都可以用一系列特征表示。用户特征包括用户的统计历史行为、人口学属性信息;物品特征包括描述信息、类别信息等等。在这种场景下,探索和利用也必须是个体用户级别上实施,因为不同用户看到相同的物品的反馈差异较大。

LinUCB算法是一种基于上下文特征(用户特征、物品特征)的UCB算法,基于特征进行探索和利用。该算法结合上下文特征,选择给用户的推荐物品,同时利用用户反馈及时修正选择策略,以达到最大化收益(提升点击率)的目标。

使用互斥线性模型的LinUCB

LinUCB算法假设推荐item的每次展现收益(是否点击)是和上下文特征成线性关系的,即:

其中表示用户特征和物品特征的合集,表示第t次尝试的收益,a表示item,表示物品a的位置系数向量。可以看出各个item的模型参数是相互独立的(互斥)。设(d*m)表示为m个训练上下文,表示每个上下文的实际收益,对训练数据使用岭回归训练出的物品a的参数为:

其中表示d*d的单位矩阵。其中在置信度下,模型收益与期望收益满足:

其中

上述等式给出了物品a期望收益的一个UCB,因此也就引申出了UCB的选择策略,对于第t次试验,选择以下式中最大值的物品,

其中。上述模型中预期收益的标准差

以上为互斥线性模型LinUCB的基本算法流程,其中结合上述内容,第一行参数控制了explore的程度,即越大,置信区间上限也就越大,也就加大了explore的程度;4-7行对于新物品,使用单位阵和0l向量进行参数初始化;8-9行计算item a的置信区间上限;11行选择最优item;12-13行更新选择item的模型参数

思想上LinUCB算法类似于对召回结果重排序的方法,也是考虑用户和item的特征,来计算出收益最大的item,不同的是LinUCB借鉴了UCB的置信区间的方法来平衡exploit和explore问题,同时从LinUCB算法是一个在线的学习算法,与一般离线算法需要离线训练不同,LinUCB随着每次展示和反馈会不断优化我们的模型参数和收益。

关于LinUCB算法的介绍请参考论文http://rob.schapire.net/papers/www10.pdf 

5 CLUB算法

CLUB(online clustering bandits)算法假设将全部用户划分成若干个用户群,每个用户群对相同推荐内容的反馈是一致的,同时自适应的调整用户群。与liner bandit一样,CLUB算法也是根据特征计算收益,不同的是CLUB算法中相同群体用户共享相同的参数向量,即第i个用户对item a的收益为:

其中表示第i个user,表示第i个user所属的用户群编号,表示每个用户群的参数向量,x表示上文下特征,表示噪声项。

该算法在时刻t,对于用户i,维护一个向量的估计值。与liner bandit算法相似,根据收益反馈不断更新。与LinUCB算法类似的,可以根据协方差矩阵(d*d维,初始化为单位阵)的逆和向量(d维向量,初始化为0向量)计算得出。除此之外,算法需要维护一个无向图,每个节点表示一个user。算法首先从完全图开始,根据表示时刻t的用户划分群。显然初始状态下的演化逐步移除节点之间的边。定义第t时刻的用户群个数为,……表示时刻t的用户划分群。显然初始状态下=1,(全部用户)。

在每个时刻t(1,2,……),用户,相关上下文特征向量集合为,用户所属的群为。CLUB算法根据收益选择item的式如下:

其中是通过同用户群内各个节点通过最小方差逼近拟合计算得出的聚合权重向量,CB为向量的置信区间上限。

CLUB算法观察到item的收益后,更新协方差矩阵,更新

;虽然不会更新其他节点的M和b,但是会隐式的影响下一轮的聚合权重向量;接下来判断节点与相邻节点的参数向量()距离,如果足够大,则将该边移除。

CLUB算法的完整流程如下:

其中控制探索的程度,是用户关系是否删除的控制参数。上述算法流程包含了删除关系边的条件,其中 是t时刻前历史上i用户被选中的次数。

CLUB算法首先提出了基于协同概念的bandit算法,即每次用户预测对item收益是由这个所属的群体的聚合权重向量参数所决定的,同时根据个人反馈更新个人参数,个人参数又隐式的影响群体参数和用户群体的划分。据CLUB算法论文介绍,在一些公共数据集中,取得了比LinUCB更好的效果,关于CLUB算法的更多细节请参考https://arxiv.org/abs/1401.8257

结束语

本文简单介绍了推荐系统中一直存在的两大问题:冷启动和EE问题,并简单阐述了业界解决这两大问题的一些常见解决方法和算法。正如前文所说,EE问题某种程度中一直以矛盾共同体存在,在实际场景中,需要平衡两者。

达观数据
达观数据

达观数据是一家专注于文本智能处理技术的国家高新技术企业,获得2018年度中国人工智能领域最高奖项 “吴文俊人工智能科技奖”,也是本年度上海市唯一获奖企业。达观数据利用先进的自然语言理解、自然语言生成、知识图谱等技术,为大型企业和政府客户提供文本自动抽取、审核、纠错、搜索、推荐、写作等智能软件系统,让计算机代替人工完成业务流程自动化,大幅度提高企业效率。

入门CLUB算法置信区间UCB算法多臂老虎机模型推荐系统
3
相关数据
权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

概率分布技术

概率分布(probability distribution)或简称分布,是概率论的一个概念。广义地,它指称随机变量的概率性质--当我们说概率空间中的两个随机变量具有同样的分布(或同分布)时,我们是无法用概率来区别它们的。

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

推荐系统技术

推荐系统(RS)主要是指应用协同智能(collaborative intelligence)做推荐的技术。推荐系统的两大主流类型是基于内容的推荐系统和协同过滤(Collaborative Filtering)。另外还有基于知识的推荐系统(包括基于本体和基于案例的推荐系统)是一类特殊的推荐系统,这类系统更加注重知识表征和推理。

协方差矩阵技术

在统计学与概率论中,协方差矩阵(也称离差矩阵、方差-协方差矩阵)是一个矩阵,其 i, j 位置的元素是第 i 个与第 j 个随机向量(即随机变量构成的向量)之间的协方差。这是从标量随机变量到高维度随机向量的自然推广。

置信区间技术

在统计学中,一个概率样本的置信区间(Confidence interval),是对这个样本的某个总体参数的区间估计(Interval Estimation)。置信区间展现的是,这个总体参数的真实值有一定概率落在与该测量结果有关的某对应区间。置信区间给出的是,声称总体参数的真实值在测量值的区间所具有的可信程度,即前面所要求的“一定概率”。这个概率被称为置信水平。举例来说,如果在一次大选中某人的支持率为55%,而置信水平0.95上的置信区间是(50%, 60%),那么他的真实支持率落在50%和60%之区间的机率为95%,因此他的真实支持率不足50%的可能性小于2.5%(假设分布是对称的)。

大数据技术技术

大数据,又称为巨量资料,指的是传统数据处理应用软件不足以处理它们的大或复杂的数据集的术语。

在线学习技术

在计算机科学中,在线学习是一种机器学习方法。和立即对整个训练数据集进行学习的批处理学习技术相反,在线学习的数据按顺序可用,并在每个步骤使用未来数据更新最佳预测器。

360机构

奇虎360科技有限公司,是中国领先的互联网和手机安全产品及服务供应商。据第三方统计,按照用户数量计算,360是中国领先的互联网安全公司,用户6亿,市场渗透率96.6%;中国领先的移动互联网安全公司,用户数近8亿,市场渗透率近70%;中国领先的浏览器公司之一,活跃用户达到4亿,渗透率超过70%。 360致力于通过提供高品质的免费安全服务,为中国互联网用户解决上网时遇到的各种安全问题。面对互联网时代木马、病毒、流氓软件、钓鱼欺诈网页等多元化的安全威胁,360以互联网的思路解决网络安全问题。360是免费安全的首倡者,认为互联网安全像搜索、电子邮箱、即时通讯一样,是互联网的基础服务,应该免费。为此,360安全卫士、360杀毒等系列安全产品免费提供给中国数亿互联网用户。同时,360开发了全球规模和技术均领先的云安全体系,能够快速识别并清除新型木马病毒以及钓鱼、挂马恶意网页,全方位保护用户的上网安全。

https://www.360.cn/
暂无评论
暂无评论~