google youtube 电影推荐算法

在面试实习生的时候，我有个习惯，就是面试快结束的时候，会像聊天一样和面试的学生聊一下他们对某个技术方向的看法。很多时候不是期望他们能提供什么灵感，也不期望能聊出太多结果，更多的是想通过这些沟通，看一下现在学生对这些问题的看法达到什么程度，而且这些沟通很能反映一个面试者的个性。 比如有些人对问题比较坚持， 或者叫做偏执，或者叫做执着，都能够反映出来。

前几天面试的时候到了最后环节的时候，忘了是说什么问题了，面试的实习生提到一般工业界使用的推荐算法都是比较简单的，不会去尝试复杂的算法。 我问他为什么，他说觉得工业界不会投入太多人力； 后来我告诉他还需要考虑处理的数据量和可维护性等因素。 当然他说的这个现象的确比较普遍： 工业界一般都倾向于使简单粗暴有效的算法，只有这些方法都搞不定时，才会尝试更复杂的潜在算法。

两个例子： 一个是 youtube 使用的电影推荐算法（参见论文： The Youtube Video Recommendation System）；另一个例子就是Baidu关键词推荐系统中使用的级联二步图；  应该说Baidu关键词推荐系统中的级联二步图的思路是借鉴于youtube电影推荐算法并应用在关键词推荐的场景中。 下边就简单介绍下youtube Video推荐算法。

算法的思想其实比较简单：使用关联规则找到有关联的电影，计算权值后进行ranking推荐。其中的新意在于，这种关联关系能够进行多次传递，逐渐扩大和种子电影相关的电影集合（当然关系传递得越远，一般关联程度也会相应减弱）

具体的推荐过程可以分为3步：

建立video间的关系

建立video间关系的方式比较简单，使用关联规则中的共现方式即可。此处youtube使用的是24小时内session的co-visitation。具体为：

使用 r(vi, vj) = cij/f(vi,vj) 表示video i和video的关联程度， 其中 r为两个video/item的相关系数， ci为i，j共同出现次数， f 为 vi, vj归一化后的分母总量（最简单的方式就是ci * cj），这样就能找到相关的两个vedio

产生特定用户的video候选

该过程在经典信息检索中可以被理解为触发逻辑，及找到待推荐video/item的候选（触发逻辑在推荐系统中所处的位置及重要性参见另外一篇blog： 传统推荐引擎系统架构）

定义S为特定用户的种子video集合， 例如在youtube推荐系统中可以选择用户最新观看（或者最新完整观看的video），之后的问题就是怎么找到和种子词相关的video进行推荐。我们将其分为以下3步：

1. 定义Cn(S)为和种子集合S相关联的，通过n步扩展后的推荐候选集合。 例如 C1(S) = 所有Ri的并， 其中Ri是与S中的vi相关联的v（寻找相关联v的过程参见上述：产生特定用户的video候选）。 相当于找到所有与S中种子vi想关联的v的并集；该做法的缺点是可能范围比较小且太相似。
2. 使用Cn(S)进行触发， 即得到C(n-1)(S)后，再找到与C(n-1)(S)中每一个vi相关联的v，之后去除种子词S，我们称Cn(S)为对S的n步扩展。
3. 同时在C(n)(S)中保留着每一个v被找到的原因， 便于后续ranking及给出explanation。

经过上述3步，对于特定user的候选video就触发完毕了。 该触发步骤可以说是该论文中的值得借鉴的点。 组里之前一位工程架构策略都很牛的同学指导实习生实现了一个通用的级联二步图算法框架， 该算法框架能够将有关联的节点的关系进行传递：

例如对于关键词，我们可以使用topic 主题（由topic model产生）建立关键词之间的跳转关系， 或是关键词中的核心term(一般是归一化后的核心term)建立跳转关系。 而该框架更令人着迷的是， 二步图的左右两边可以不是同样的item， 例如左边节点是keyword而右边是user， 则可以使用topic 直接建立keyword与user的关系进行推荐。

 Ranking

youtube 的ranking策略主要考虑以下3个因素：

1. video质量， 这个可以通过网名对video投票打分得到。
2. user specificity： 在触发后，可以通过使用user profile和电影的一些质量， 或是内容属性进行排序
3. divercification：特别是类似video这种兴趣相关的内容， divercification的引入就显得非常重要了；相反， divercification在不同的场景下可能不同，百度关键词推荐中， 根据种子词直接检索得到的结果需要考虑与种子query的强相关性， 此时divercification的引入， 或者引入的程度需要比较慎重保守。

当然， ranking机制一般都会非常复杂， 论文中此处只是简单介绍； 例如在构造百度关键词推荐系统的过程中， 我们引入了提词率预估， 效用预估， 价值预估等模型对返回结果进行ranking。同时也需要结合user interaction的样式，算法出口等进行调整。 具体ranking机制会在后续blog中介绍。

效果上， 级联二步图的引入，能够找到非常多靠谱的结果（当然二步图边的建立是核心，选对了边的建立方式，才会有好效果），具体效果数据就不便透露了：）   反正是基本上能够覆盖全部凤巢用户，每个客户都能推出数量惊人的关键词（当然，需要使用字面， 语义等技术进行后续filtering and ranking）

更进一步， 级联二步图是图关系挖掘的一个简单有效的特例， 使用类似于pagerank等经典算法， 也能够很好地找出类似的关系进行推荐。

参考来源：

The Youtube Video Recommendation System

Google Adwords

百度关键词推荐工具介绍：http://support.baidu.com/product/fc/4.html?castk=11820ss78c2e1602bd140

也可关注我的微博：  weibo.com/dustinsea