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投票打分得到。这一项和用户及对应偏好, 仅和video自身质量有关,就类似于搜索中pagerank得到的page质量度一样
  2. user specificity: 在触发后,可以通过使用user profile和电影的一些质量, 或是内容属性进行排序。这一项反映的是用户对电影的偏好得分
  3. divercification:特别是类似video这种兴趣相关的内容, divercification的引入就显得非常重要了,否则推荐的video会逐渐收拢到可数的一两个品类,可以使用的方式是限制每一个category video的推荐数量,或者本文中限制每个seed video出的video的数量;相反, divercification在不同的场景下可能不同,百度关键词推荐中, 根据种子词直接检索得到的结果需要考虑与种子query的强相关性, 此时divercification的引入, 或者引入的程度需要比较慎重保守。
当然, ranking机制一般都会非常复杂, 论文中此处只是简单介绍; 例如在构造百度关键词推荐系统的过程中, 我们引入了提词率预估, 效用预估, 价值预估等模型对返回结果进行ranking。同时也需要结合user interaction的样式,算法出口(interface)等进行调整。 具体ranking机制会在后续blog中介绍。
效果上, 级联二步图的引入,能够找到非常多靠谱的结果(当然二步图边的建立是核心,选对了边的建立方式,才会有好效果),具体效果数据就不便透露了:)   反正是基本上能够覆盖全部凤巢用户,每个客户都能推出数量惊人的关键词(当然,需要使用字面, 语义等技术进行后续filtering and ranking)
更进一步, 级联二步图是图关系挖掘的一个简单有效的特例, 使用类似于pagerank等经典算法, 也能够很好地找出类似的关系进行推荐。
参考来源:
  1. Davidson J, Liebald B, Liu J, et al. The YouTube video recommendation system[C]//Proceedings of the fourth ACM conference on Recommender systems. ACM, 2010: 293-296.
  2. Google Adwords
  3. 百度关键词推荐工具 :http://support.baidu.com/product/fc/4.html?castk=e6f89hg77d37ada65d612
或者直接访问 http://semocean.com

google的商业产品之路

之前公司从google总部招了一位经验非常丰富的PM。入职后就请他给大家为大家布道google的商业产品推进的方法。 听了之后感触颇多, 在此与记录并与大家分享(因为自己也是学习别人在google的经验, 当中会加上一些自己工作中的感受, 其中有疑问的地方欢迎讨论)

        像google这样的公司, 做出的产品基本上能够直接影响到全球, 或者说是全人类的生活。 而它的商业产品, 也能够为这个公司成为你全球最大互联网公司提供收入保障。那google在进行商业产品的推进上,思路流程是怎样的呢?
        从系统产生, 项目开发的生命周期来看, 比较自然地就分为三个阶段: 提出想法, 设计, 执行/实现(即inspiration, design,   excution)
        首先是想法的提出(inspiration), google在提创意的原则是:‘ think big, start small’,作为世界级的公司,google 的产品都是直接影响全球的, 所以一般很多想法, 创意都是冲着改变整个产业去的(to change industry, to change world)。 例如google 比较成功的商业产品adwords,现在google大部分的收入, 都和这个产品有关; 又如百度的凤巢,贡献了百度绝大部分的变现。 当然不积跬步无以至千里, 一口也吃不成个胖子。 在一开始的时候虽然有着美好的憧憬和无端的自信, 做事的时候也是以某个具体的点入手, 开始逐步推进。
        然后是设计阶段(design)。  我们经常讲, 网民, 广告主, 搜索引擎三者参与商业产品的游戏, 三者相互关联, 获取自己想要的利益。  网民需要的是信息,  广告主进行自己信息的推广并希望在有限的支出下获取到最大的转化, 而搜索引擎希望从广告主获取最大化的利益。    而google 相较于通过搜索引擎从广告主获取最大利益, 更注重广告主的收益(至少我感觉跟国内搜索引擎公司相比), google的原则更像是: ‘make customers happy, and I’m happy’。 同时google认为advertisering is a repeat bussiness,让客户玩爽了, 客户才会持续地投入更多的钱, 从长远来说, 让客户爽就能挣更多的钱。 所谓细水长流, 才能天长地久; 但很多企业为了追求短期漂亮的财务报表, 不惜杀鸡取卵。
        另一个design阶段让我感触比较深的原则, 就是enpower users。 google(包括baidu等其他搜索引擎公司)其实是在做平台, 例如baidu未来的目标是成为全球第一大媒体平台, 全球有一半的人都在用baidu的产品。。。 而用户/客户才是平台上的主角, 平台的目的是让之上的参与者更高效, 所以google会有意地为客户提供各种提升效率的工具(self-help system and material helps customers),例如各种API, Batch工具,分析工具, 让客户随时随地能够满足自己的需求。 毕竟人民才是真正的用户,  PM,工程师的力量再大, 也大不过人民的群体智慧。
        在执行阶段, google 使用data driven的方式, 其实这个方式在很多策略型项目中都在使用:  dash board线性开发, 快速上线, 线上数据说话并根据效果的分析结论快速,持续迭代。 就算是失败, 也能从失败的数据中定位失败的原因, 然后迅速纠正。 总结起来就是: persistence(持续迭代优化), fail and learn(正确看待失败并从失败的经验,数据中进行改进), data driven(数据平台的建设)。  我是策略RD, 所以这方面感触比较深, 很多时候我们做的都是策略的优化,  最常见的情况是策略上线后效果不明显,甚至是负面效果, 此时对上线后的效果数据进行分析, 一般都能发现一些之前策略设计实现的时候没有碰到的问题, 之后策略中有针对性地对这些问题进行解决, 几次迭代后, 一般都能取得比较好的效果。
        当然google商业产品的思路, 远远不止这些, 而且各个公司的具体环境也不一样。种子只有在合适的突然才能发芽。此处也只记录了自己粗浅的理解及感受。
        写在最后,这位Google的PM大牛,就是现在力美的CTO梁信屏

Google experiment infrastructure 阅读心得

背景

Google 的文化就是数据驱动:不停实验,不断得到实验结果进行分析并进行改进,这样就会导致所有R&D(Researcher&Developer)都会有不断实验的冲动和需求。这就对实验框架提出了文中重点描述的三个需求:
1.        More: 更多能够同时进行的实验
2.        Better:不合法的实验不能在框架中实验, 而合法的实验, 但如果效果不佳, 则应该能够被及时发现并下线
3.        Faster:实验应该能快速建立并启动
和google search engine面临的问题一样,推荐系统也存在大量实验,故文中的思想可以在后续关键词推荐的设计中借鉴。
原有相关工作
一般来说,进行实验的目的有以下两个:
1.        测试新的features
2.        在已有features上,测试各种参数的最优值及组合
而原有框架却有较多限制。例如google在2007年以前使用single Layer模式,该方式实现较为简单, 却有很多限制, 包括:
1.        每个请求最多只能做一个实验,可能导致很多实验流量不足
2.        添加条件进行分流时会使框架变得复杂
3.        上游模块做了较多流量划分后,下游模块可能出现stravation的状况
另一种方式:Mutil-factorialdesign,让每个参数都相对独立地做实验,最多能同时做N个实验,其中N为参数个数。缺点是不容易调整,且很多参数是不独立的,文中给的例子是UI显示文字,背景的颜色不能相同。

Overlapping Experiment Infrastucture

主要思想:
1.        将待实验参数划分为独立的N组subsets。例如,不同的binary功能不一样,则可以认为他们的parameters不相交,可划分到不同的subsets中
2.        定义domain, layer,experiment后,对流量进行划分及条件判断,其中:
l  Domain: 流量的划分,domain之间流量是不能有交集的
l  Layer:每组相关的subset参数组成一个实验layer
l  Experiment:具体实验,在一个subset中,测试0个及多个测试参数
3.        Domain, layer, experiment可以嵌套
如下图所示:
其中(a)为single layer,(b)为带有非覆盖domain的简单示例,(c)中包含两个launchlayer(d)中则存在更多嵌套
具体的参数设置, 既可以通过代码修改来实现, 也可以通过更新数据来制定(对应文中的binarypush 和data push,一般情况下data push 能够更快地进行更新)。
对于domain流量的划分,在searchengine 中一般是通过cookie来划分(不能通过request等非机器/用户属性进行划分,否则用户看到的效果可能出现跳动),而在Overlapping Experiment Infrastucture中,流量划分有以下原则:
1.        Domain 流量不能有交集,一旦流量划分到某个domain,则流量不能再其他平级的domain中被使用,所以一般domain的划分可以使用。一般使用cookie,或是cookie-day,userid取模来进行划分。
2.        Layer可以考虑使用不同的功能模块binary来进行划分参数。在各layers中,分流可使用mod =f(cookie, layer)进行流量划分
3.        在具体实验中,需要考虑condition(具体实验条件是否成立)
具体实验逻辑参见下图:
同时文中提到会使用配套数据校验工具校验数据格式正确性(其实这个是上线的必须具有的工具,并无新意),另外线上会时时关注重要指标,例如CTR,如果CTR等重要KPI超过异常边界,则新实验直接下线。这样的检测固然能保证避免异常,但是否会限制实验的上线速度需要思考,毕竟线上多个实验同时进行的话, CTR类似的KPI发生异常时,不能很快确认是哪个实验导致。
和传统方式一样, 实验框架提供的是实验流量的定位,但具体实验中,某次请求究竟是走了实验组逻辑,还是走了控制组逻辑,则仍需要从日志中分析。
其他
文中提到的以下内容也非常值得借鉴:
1.        文中提到了canary code的概念,表明google会在线上开实验,小流量测试代码正确性。也是正式,让google公司中RD/QA的比例很高(中国主要的search engine公司中,代码正确性更多是在线下验证,这就要求更多测试工程师)
2.        所有和实验框架的代码均被抽离成shared library的形式编译到各binary中,这样就让实验代码实现高度统一。但这里有一个问题:很多复杂系统中数据流是通过很多层binary后,才能得到最后的结果,如何控制各层之间的数据流向,设计时需要重点考虑。
需思考的问题
1.        涉及到多层次模块的架构中,如何控制各实验在各层之间的数据传输(如使用binary push的方式,则同一层的binary可能不一样,除非统一binary,而由data push控制)
2.        如何记录实验结果:文中使用logging的方式仍然会导致线下需要较多的logging事后分析的工作
也可关注我的微博:  weibo.com/dustinsea
或直接访问 semocean.com