干货:从相关性到RNN,一家线上“租碟店”的视频推荐算法演进


大家好,我是周涵宁,来自于Hulu。Hulu是美国第二大的视频网站,今天我要分享是视频推荐系统。

在讲基于网页的推荐之前,我想先讲讲传统的视频推荐。传统的视频更多的是出现在租碟店,也就是五年、十年以前大家经常光顾的光盘店。当你去的时候,老板就会跟你说,昨天晚上又新进了一个很好的片子。老板做这种推荐的话,你会信任这个老板对你的了解,以及他对现在电影市场的了解,他对影视内容的品位。你和租碟店老板之间形成了一种良性的互动。

到了网络时代,出现了很多视频网站,包括爱奇艺、搜狐、优酷土豆。这些网站不可能为每个用户都雇一个专职的老板来做推荐,所以它会用自动的方法,用数字的特征去描述一个用户的喜好,然后产生出一些推荐的结果。


奈飞(Netflix)大家都知道,在十年以前举办了一次推荐算法的比赛,奖金是一百万美元,比赛是为了解决它当时对于用户评分的一个预测问题,所以推荐算法在视频网站的应用历史应该是比较悠久的。

那么现在从业务的角度,我们和十年以前有哪些差别?


最大的改变可能是很多的视频网站都加入了电视直播的内容。最早的时候,点播是一个录下来的昨天放过的电视剧,或者之前已经制作好的节目。直播的场景的话就非常不一样,它是实时发生的,正在发生的可能是体育比赛、某个新闻的事件。对于这种内容的推荐,还有一些独特的挑战。今天我也会讲到,对于这种在线直播,需要用不同的模型和不同的特征。

这个是我们今天课程的一个内容提要。第一,我会讲一下优化目标和框架,第二,模型。模型里面又包括Exploitation和Exploration的两种具体的模型。然后基于这个模型,我会讲两个应用场景。


视频推荐系统的优化目标


推荐系统的优化目标,如果从用户的偏好来讲,我们是希望提供给用户一个非常健康的组合,既符合他们的口味,又有足够的多样性,就是有营养的内容。但是平台本身呢,它又有商业变现的要求,所以有的时候为了平衡用户的需求和平台本身的需求,我们就要做出某种折中。也许我们不会提供像麦当劳这样的快餐,但是我们可能要为了获得一些短期的回报,在一个完全健康的食品和这种快餐之间取得某种折中。


最后从算法或者数学抽象来讲,我们就把这个问题抽象成为“怎样最大化用户的观看时长”


为了达成这个目标,我们就要预测用户喜欢哪些内容。具体来讲,用户观看时长可以用什么方法来最大化?有几个关键的要素,第一个就是,点击进去看一个视频之后,你看了多长时间?这个跟视频本身的长度有关,跟你的完成度有关,我们叫playback_duration。第二个叫做有效点击eCTR。第三个就是整个内容的曝光量。大家如果做一个简单的代数运算,把这三项乘在一起的话,就变成了每个用户的观看时长。


为了优化总的观看时长,推荐系统可以控制的就是曝光量这个要素。具体来讲,就是把我们想要更多地展现给用户的内容排在前面,这样用户在第一屏就会看到。推荐结果的好坏表现在eCTR,这是一个我们不能够直接控制的量,我们通过选择正确的物品分配更大的曝光而间接控制eCTR。我们最终想要最大化的是eCTR和曝光量的乘积。


这个图表里,横轴是曝光量,纵轴是eCTR,我们把去年10月曝光量比较大的一些内容在这个图表里展示了一下,大家可以看到这两个量基本上是成正比的。这说明我们的推荐系统还是做了正确的决定,就是给eCTR高的内容提供了更大的曝光。


当然从这个曲线里面,我们也看到有一些eCTR不是那么高的内容,比如说College football,在最右下角的地方,它也获得了比较大的曝光,这就属于过度曝光。所以这也提出了我们优化的一些可能的空间:可以把分给点击不是那么高的物品的曝光量,匀一些给其它的更高点击、但是曝光不足的内容。

视频推荐系统的框架


刚才讲了通过KPI里面的这些维度的划分,怎么样找到一个推荐系统的表现的好坏以及改进它的机会。那么具体来讲,我们要建立一个推荐系统的话,它需要几层?


我们可以把推荐系统抽象成为四层,最底下一层是基础数据。第二层是特征,特征可以分为用户的特征和内容的特征。用户的特征具体来讲又是每个用户单独的特征,或者是一群用户的一个画像,群体特征。内容的特征可以是每个内容单独的特征,或者是一批内容的总体特征。


基于第二层的特征之上,我们会建一些模型。这些模型的优化目标有两个,一个是利用,一个是探索。利用(Exploitation)又可以有一些子目标,包括Relevant,就是相关性,包括透明度,对产品经理还是对最终用户是不是可解释,包括是不是上下文相关,充分利用了时间、设备、地点这些上下文信息。探索(Exploration)主要讲的是对新内容我们有没有给足够的展现,以及有没有给用户惊喜、发现用户隐藏的一些兴趣。当用户兴趣发生改变的时候,我们是不是非常快地适应了用户这种兴趣改变,也就是adaptive。最后一个是多样性,就是我们给出的这个套餐是不是组合了很多不同的类别,而不是非常单调、单一的。


在模型之上,我们要做一些应用。这些应用主要是服务四个用户的阶段。首先是所谓Onborading,就是一个新用户,刚刚订阅我们的服务的时候,还在一个初始的、给我们一些信号的阶段。我们让用户选择他最喜欢的内容频道,然后用户会告诉我们他喜欢体育、喜剧或者动作片。基于这些大类,我们可以给他做一个冷启动,给他第一屏的推荐结果。


之后,在一个新用户进来之后,我们大概有七天的时间把他转化为一个付费用户。从试用期到付费期的转化,就是Convert-to-Pay。在这个阶段,我们需要快速地探索用户的各种需求,让他体会到我们的服务非常有价值,那么他才愿意买单。


到了第三个阶段,就是用户已经是一个付费用户,那我们就需要留住他,所以就是不断的去给他更多的、他之前可能没有看过,但是和之前看过的很相关的内容。


最后,第四个阶段是Monetization。在有很多渠道付费订阅的时候,当然订阅费本身是一种变现的手段。但是我这里指的变现,主要还是广告变现。具体来讲,广告变现的业务指标就是用户的观看时长。因为插入广告点的个数,以及广告的库存量是直接和用户的观看时长以及活跃用户数相关的。所以这是我们所有这些模型服务的第四个任务,就是一个已经付费的用户,已经留下来的用户,我们怎么样用广告把他的流量变现。


视频推荐系统的算法

优化目标:利用(Exploitation)

利用方面的模型,如果从推荐系统、特别是相关性的利用来讲,有两大类,一个是基于用户行为的,一个是基于内容的。

基于用户行为的话就叫做协同滤波。具体来讲,协同滤波下面又有更细的分类,有基于存储的Memory-based和基于模型的Model-based。基于存储的话有item-based CF,基于模型的话有矩阵分解和神经网络的方法。矩阵分解下面又可以再细分。然后神经网络现在也有基于RBM的,还有Embedding-based Neural Network。


Hulu经历了三代相关性算法的演进,第一代是item-based CF,第二代是基于矩阵分解,现在我们正在开发的第三代是基于Embedding-based Neural Network。从Netflix公开的文件来看,它主要使用的是SVD和RBM的方法。


第1代算法:协同滤波


我们先讲比较古老的一代相关性算法:基于物品的协同滤波。最早是20年前亚马逊在它的电商网站上使用的。它会构建一个用户和物品的相对评分或者影视的相关性矩阵。就是我在左下角画的这个矩阵,它每一行是一个用户,每一列是一个物品,里面的数值可以是用户购买这个物品的次数,或者点击这个物品的次数。就是用一些用户的隐式行为,把它转换成为用户和这个物品之间的某种评分。这个分数越高的话,它就和这个物品的相关性越高。


大家可以看到里面有很多的缺失数据,因为这个矩阵是非常稀疏的,在几万个视频里面,用户能看的也可能只有几百个。所以大约有百分之七八十的数据是实际上是零。


那么,基于这么一个简单的表示,可以去度量两个物品之间的相似性。如果在这个矩阵里面两列的数值的cos distance很接近的话,我们可以认为两个物品是类似的,因为在全量用户上对这两个物品的相对评分是很接近的。


第2代算法:矩阵分解


接下来就是从协同滤波进化到矩阵分解。


刚才讲到协同滤波有一个稀疏性的问题,矩阵分解为了解决这个稀疏性的问题,使用了线性代数里面的一个特性,就是一个低秩矩阵,可以用两个相对低维度矩阵的乘积来表示。具体来讲,评分矩阵R是低秩的,它可以用一个矩阵P和矩阵Q的乘积来表示。P就是所有用户的特征,用一个大概一百多维的特征向量就可以表示,每个用户用一百多维来表示,相比原来几万维的用户和所有内容的交叉,就节省了很多的存储以及计算。相对的,每个内容也可以用一个列矩阵,就是Q来表示。


我们使用矩阵分解之后,在线上也观察到了很多好的表现,那么,我们肯定不满足于这种矩阵分解的算法,我们还想要进一步引入更多side information侧面信息,其中包括用户的demographic的这种元数据信息。

第3代算法:神经网络


在矩阵分解的框架底下,不太容易直接地使用这些side information,所以我们就引入了一种深度神经网络的框架。


也就是,把原来矩阵分解里面代数运算的步骤,用一个前向神经网络来替换。这样的好处一方面是非线性前向神经网络允许一些非线性的映射,可以有更好的表达能力去model一个更复杂的分布。另外的一个好处就是我们可以直接把关于用户的除了行为之外的所有信息,用一个矢量feed到这个神经网络里面去。对内容我们也可以做相应的处理,就是把元数据,比如说导演、演员信息用一个向量来表示,然后把它feed到神经网络里面去。


相关性算法的应用场景



相关性算法有两个应用场景,一个是所谓的货架场景,就是给一个网格里面按照相关性做了排序,然后希望用户点越靠上越靠左的这些内容。另外一个是自动播放的场景,就是播完一个内容之后,我们会自动地开始下一个我们觉得用户最可能看的内容。对应这两种不同的场景,其实需要不同的相关运算。

具体来讲,刚才所说的协同滤波方法,它比较适用于货架场景的召回和排序。对于自动连续播放的场景,我们采用了另外一种模型,就是时间序列的模型,叫做循环神经网络

我们把用户在网站上的一个行为序列,认为是由这种RNN模型所产生的。我们可以用反向传播的方法去训练一个RNN模型,来预测用户在网络上的下一个行为。采用了RNN的时间序列之后,我们在线上的测试观察到了非常高的提升。我们仿真测试的方法就是当用户看完剧A/B/C之后,我们假装不知道这个用户接下来看了哪一个,然后基于时间序列的建模,来算出一个最可能看的剧,它可能是当前这一剧的下一集,或者是跳到另外一个剧D或者是另外一个剧E。根据RNN模型,我们找到最有可能的下一个剧,然后和用户实际看的下一个剧之间做比对,这是离线的一种评估方案。

优化目标:探索(Exploration)


刚才讲完了一些利用,就是基于用户行为以及side information做货架场景的排序和自动播放的这种持续预测。接下来我们来讲探索。

自适应


我们先来看探索中的自适应的问题。为了解决用户兴趣的时变以及新内容的冷启动,我们采用一种叫做多臂老虎机(MAB)的模型。


多臂老虎机是借用了赌场的一种场景。一个赌徒可以在不同的时间选择不同的摇臂,每个摇臂会给这个赌徒不同的赢率。如果赌徒每次都选择摇臂1的话,有可能不是最优的,因为可能另外一个摇臂的反馈更好。我们把赌场的场景应用到推荐系统里面,就是每个摇臂是我们可以推给用户的一个剧,而我们的算法就是这个赌徒,它通过一些策略来选择将哪个剧推给用户。而每个摇臂获得的奖励,就是用户是否点击和观看了。用户的兴趣本身就是这个老虎机自己的一些参数设定。

多臂老虎机已经是一个历史比较悠久的问题,所以也有很多成熟的算法。我们采用了一种比较流行的算法,叫做LinUCB算法。我们会根据当前推的结果,来实时更新对每个摇臂的点击率的预测。


具体来讲,在线上部署LinUCB的算法,有一个线上更新提取特征以及模型运算的过程,以及一个线下根据之前模型采集到的信号去更新模型参数的过程。

在我们这个实验里面,可能对大家比较有参考意义的就是我们发现的LinUCB的一些特征,其中包括用户当前看剧的完成度,就是他看到了第几集、是不是看到了高潮部分还是快要结束的部分。完成度是一个很重要的特征维度。然后就是上次给用户曝光这个剧的时间和现在之间的时间间隔,以及它历史上的点击率,还有这个剧的一些元数据信息,它在外面的流行程度,以及根据刚才讲的协同滤波的方法,得到的用户和这个剧之间的相关性。

多样性


接下来讲多样性的一个模型,叫做行列式点过程。

我们为什么要关注多样性?是因为用户的兴趣爱好可能不是单峰分布的。有可能用户有多个兴趣爱好,其中有非常突出的一个,就是这个比较高的右边的峰。但是还有一个比较低的,就是右边这张图里面的靠左的这个峰值。如果我们用简单的相关性排序的方法,就会把右边峰值里的很多内容都排在前面。而用户隐含的兴趣,就是左边这个比较矮的峰,就不会出现。所以我们要用一些多样性的策略,使得左边这个矮的峰里面的一些好的内容也会被推荐。


用户多样性的问题也已经被广泛研究过。传统上使用启发式的方法,它会在多样性和相关性之间用一个加权平均的方法来获得一个总体的优化目标,然后两两之间比较当前推荐的差异性,然后试图最大化这个总的平衡了之后的优化目标,用穷举的方法。

我们在现有的启发式的搜索基础上,采用了一些不同的代数模型,就是把两两之间比较不相似性改变成为用一个多边形的体积来量化我们给出的不同物品之间的差异性。把每个物品看作一个多维空间里的向量,然后用这些向量总体张成的一个多边形的体积来度量这个集合的差异性。



这种方法也有一种贪婪式的解,它的计算复杂度是选品总数的立方,比刚才的那个Heuristic,就是两两之间比较的话,它的计算复杂度要更高一些。所以为了解决这种更优的度量带来的计算复杂度的增加,我们用了一些代数的方法去加速,最终我们达成了一种线性复杂度的方法。

就是这个图里面画的这条红色的线,它可以和刚才讲的DPP的原始实现达到同样的精度。但是由于我们采用了incremental update的方法,有效地降低了计算复杂度,把原来Y的立方的这种计算复杂度变成了线性。


视频推荐系统的应用场景

推荐的理由

最后我们来讲几个应用场景,其中比较重要的一个叫做推荐的理由。



Lady Gaga有一首歌唱的是“我有一亿种理由离开,但是我只需要一个好的理由留下”。(彩蛋来啦,Bazinga!)那么对推荐系统来说,它可能推出完全相同的结果,但是如果我们可以给出一个好的理由,那么用户会对它的信任会更高,点击率也会相应提高。


比如说,当我们推荐《终结者2》,我们说是由于你历史上看过《终结者1》,这时候就比完全没有任何原因的推荐显得更加顺理成章。如何构建一个推荐的理由?我们可以用刚才很简单的模板,就是因为你历史上看过和它相关的一个剧。


但是如果我们想做得更加人性化、更加自然,我们要用一种知识图谱的方法。在知识图谱里面构建内容,用户的群组,相关性的信息,以及一些统计信息,包括这个剧的流行程度,它在外面的排名。我们用一种N元组的方法来记录这个知识图谱。

基于这个知识图谱,我们可以设定一些推理规则,每一条规则其实对应某一种经典算法,比如第一条规则,就是如果用户喜欢电视剧,一是由于他曾经看过电视剧,二是电视剧2和1非常相近,这就是item-based CF逻辑的一种表达方式。类似的话,我们还可以把user-based CF也用一条规则来表达。比如说这个地方列出的第二条规则,就是如果用户属于某一个群组,而这个群组里面60%的人都看过剧1,那就说明当前这个用户也可能会喜欢看剧1

列出了很多这样的规则之后,我们可以在知识图谱里面建立一个规则树,就是为了推理出当前这个用户多大的几率会喜欢一个剧X。我们可以用所有的规则和每个剧之间做一个实例化,然后来度量它是否有证据来支持当前这个规则的证明。这个推理树里面的节点会随着规则的不断展开,而从根节点开始逐渐成长,长成一棵非常大的树。


大家看到这个节点里面的红色部分,就是待证明的某一个假设或者规则。蓝色的部分就是实例化之后,找到了事实去支持这个假设的部分证明。当一个节点从红色完全变成蓝色,大家看到最下面的叶子节点,那就说明它已经用所有的事实完全证毕。


当然,并不是所有的规则推理最后都能够被所有的事实来支撑,比如说最左边的这个叶子结点,它有一个红色的待证明项,是找不到事实支撑的,那么这整条路径就是失败的。但是我们在这个树里面,如果你的知识图谱足够丰富的话,它总可以找到某一个子路径,是可以证明当前这个推理的。


语音对话推荐


第二个应用场景是基于语音交互的一种对话的推荐。


当前很多的应用都是在手机上或者PC上,是基于图形界面,用户需要点击,用户能够给到系统的反馈是非常有限的。没有点击有可能是因为不喜欢,有可能是因为当前时机不对,也有可能是你之前看过了。我们是无法获得更深层次的用户反馈的。而用户要进行一个查询,他要告诉系说,“我要看一个80年代情景剧”,他要通过多级复杂的菜单嵌套来完成这个查询。所以图形界面的局限性就限制了它的交互自然性。



我们提出基于语音对话的推荐,使得整个过程更加自然。我们可以允许用户用一个简单的自然语言来表述一个非常复杂的查询条件。然后当用户对当前的推荐不满的时候,他也可以用自然语言来告诉我们,为什么他不喜欢这个剧,以及他想要换另外一个什么样的剧。我们认为语音交互会成为下一代计算的一个催化剂。大家知道PC时代,鼠标和键盘是最流行的交互方式,到了移动时代,触屏变成了手机上的最流行的交互方式。随着物联网的发展,我们认为语音会成为下一代的交互方式。


以上就是公开课的所有内容。


对话周涵宁


Q:怎么识别用户的兴趣是否改变呢?

A:其实对于多臂老虎机的问题模型来讲,我们并不是显式地去建模用户的兴趣是否改变,而是把用户的兴趣(一个老虎机的模型参数设定),认为是一个可以实时更新的参数。我们不断去追踪这个参数的改变,或者换句话讲,就是我们永远都假设用户兴趣和之前是可以有差异的。所以我们不断地在跟踪一个不断改变的参数。


Q:知识图谱是怎么建立和生成的?

A:我们所用的知识图谱,一方面是从第三方采买的,有专门的构建知识图谱的厂商,他们会做数据清洗爬取。另外一部分是我们从内容提供商那里获得的一些元数据信息。


Q:基于规则的推理要人工构建吗?规则要有多少?彼此之间会不会冲突?

A:这个规则的构建过程是手工建立的,但是规则条目其实并不多。我们如果便利现有的所有推荐的算法的话,每种算法大类来讲,大约会产生一到两条规则,所以最终我们可能只有不超过50条,规则之间是有可能冲突的,所以冲突就是它们都可以用来解释某一个用户喜欢内容X或者是说它可以推理出一个用户既喜欢内容X又喜欢内容Y。所以这个时候要做路径的选择,就是刚才推理树里面哪一条路径最有可能是真实的。所以我们会用配置认可的方法,去在这个图里面这个推理数的图里面做随机游走,然后找到最终权重最高的一条路径。


Q:能否基于用户行为和金融产品的历史表现做金融产品的推荐?

A:关于金融产品的推荐,其实美国已经有公司在做。我上次去参加推荐系统会议的时候,就有一家纽约的公司,做的事情有点类似于定向广告,就是它会根据用户之前的消费记录、投资记录,选择金融产品。

嘉宾简介

周涵宁,现任Hulu北京研发中心推荐算法研发负责人,具有15年的研发创新和管理经验,专注于应用数据和算法实现产品落地,有丰富的数据分析和机器学习实践经验。

他本科毕业于清华大学自动化系,于伊利诺伊大学香槟分校获得计算机视觉领域博士学位。历任施乐硅谷研究中心研究员,亚马逊美国总部高级技术经理,盛大创新院资深研究员兼产品总监,智谷公司技术副总裁和宝宝树CTO。他拥有十多项美国专利授权,发表学术论文二十余篇。

入门
4
暂无评论
暂无评论~
返回顶部