好久没写日志, 今天看到个有意思的问题, 也能很快说清楚, 记录一下.

问题: 有一对夫妇有两个孩子, 已知其中一个是男孩, 则另一个也是男孩的概率是多少?
候选答案一: 因为生男生女的概率都是 1/2, 每次生育都是独立事件, 所以概率是 1/2
候选答案二: 因为两个孩子的性别总共有四种等概率可能, 分别是 男男, 男女, 女男, 女女, 现在已知其中一个是男孩, 排除掉 女女 这 1/4 的概率, 所以另一个为男孩的概率是 1/3

这个问题引起了很多争论, 两种说法的支持者都很坚定. 今天看了一堆讨论, 最后发现其实是对题意理解不一致导致的, 关键问题就是 “已知其中一个是男孩” 代表了什么意思.

说 1/2 概率的把那句话理解成 “已知大孩子是男孩”, 所以把四种等概率可能排除掉了 女男, 女女 两种可能, 剩下两种可能里, 小孩子是男孩的概率是 1/2.
说 1/3 概率的把那句话理解成 “已知其中有一个孩子是男孩, 但是不知道是大孩子还是小孩子”, 所以只能排除 女女 这一种可能, 剩下三种可能里, 另一个孩子是男孩的概率是 1/3.

感觉我应该把分歧说清楚了. 下次如果有人遇到类似问题的时候, 可以看看问题中的条件是否有 tricky :P

最近去围观了几场年会, 刨开文化的差异, 从不同公司里领导层和员工更关注更强调的点也是可以看出来不同产品的差异. 把自己看过做过的一些东西揉进去连起来看, 有一些关于 “需求满足” 的想法, 抛砖引玉, 请大家提供更多的观察角度和建议.

搜索和推荐, 以及计算广告

我不知道业界对 “搜索” 和 “推荐” 的定义分别是什么, 我自己的定义是
推荐: 对一个特定的用户, 根据其历史行为, 推测其可能的需求, 推送满足潜在需求的内容给用户
搜索: 对一次特定的请求, 推送满足该请求的内容给用户

这么一分, 搜索就可以看成是推荐的一个真子集. 搜索相对发展的比较成熟一些, 个人觉得现在的发展重点更多在 “理解需求本身”, “内容丰富度” 以及 “内容时效性” 几个方向上. 而推荐, 现在更多的问题应该都在 “推测需求” 这个环节.

计算广告, 则是在搜索和推荐的内容中加入商业结果, 本质是一样的, 只是需要额外考虑商业收益和可持续性. 任意一家商业公司都需要收入来维持整个公司运作和发展, 在资源受限的情况下, 一般都会先考虑商业结果接入, 毕竟活下去才是王道, 死了就啥都没得搞了.

搜索中的需求

搜索的需求都更直接, 而且相对独立, 比如我搜 “西二旗地铁站附近的饭馆” 或 “北京到上海的机票代理”, 直接给结果就行了. 而一些比较复杂的搜索, 因为事件本身需要更多考虑, 或是因为需求比较难用文字表达, 则会引起一系列的搜索, 但是这一堆搜索请求也都是可以比较容易将其黏合在一起成立一个系列事件. (各搜索引擎的个性化搜索中的短期行为个性化)

因为搜索需求是如此的直接暴力, 用户就是需要某物品或服务, 所以广告也可以直接暴力的给出, 效果还很好 (稍微好点的广告应该都可以做到百分之几的点击率, 转化率也不低)

也因为搜索需求的独立性, 偏搜索的产品在考核时更多都用 PV (Page View, 页面访问数) 说话, 用户黏度不大, 流失风险也不低 (甚至压根就没有用户概念, 只有请求的定义). 个人感觉这就是百度推新首页, 阿拉丁, 开放平台等产品的目的, 留住用户, PV 至上向 UV (User View, 独立用户访问数) 转换, 而且还能降低系统消耗并提升效率 (变现/搜索结果满足需求等效率)

推荐的需求猜测

和推荐有关的东西很多, Netflix 的影片推荐, douban 的读书推荐, 各种个性电台的音乐喜好推荐, 电商网站的商品推荐, Web 2.0/SNS 的内容推荐. 其中有一些是能比较直接带来收入的, 比如影片推荐, 商品推荐, 做的人很多且深入, 而另一些变现能力不明朗的产品, 比如个性化电台, 大部分都还只是玩票, 公司有人的情况下做着玩玩, 攒点技术.

Web 2.0/SNS 的内容推荐在推荐中的位置比较尴尬, 一方面用户需要更多更好的内容推荐 (用户需求强烈), 另一方面变现比较难 (公司投入回报比低). 为了留住用户显然要做推荐, 从中能挤出点商业需求弄点钱让自己活下去也是很多推荐团队要考虑的事.

回到推荐的需求判断, 一般推荐系统都是在根据历史行为猜用户的未来需求 (实时的直接需求那都是搜索, 不管是通用搜索还是站内搜索), 所以最朴素的想法就是用户过去看过啥, 喜欢啥, 关注啥, 买过啥, 就给 TA 推荐类似的东西. 这种简单粗暴的方法在影片推荐什么的会比较有用, 效率高, 相关性也好, 用户的个人喜好一般不会变化太快, 而且会一直有相关需求, 如果需要维持内容丰富度, 可以做一些随机化, 或用用户的朋友的喜好来推荐.

但是其他行业中, 就会有是否是 “持续性需求” 的差异. 电影我看了这部还会看别的, 吃饭我吃过这家店还会考虑别的类似的店, 但是有一些需求一次完成很久不会变, 比如我买了个路由器, 只要不坏或脑子抽了要骚包下, 一般不会去买第二个 (帮别人买这种行为应该分开考虑, 或者现在这种行为也很多?), 再比如学英语我报了个老罗英语后, 至少短时间内我不会再考虑去报个新东方或别的.

不同的持续性, 也应该有不一样的做法. 电影, 音乐等已经有良好分类标签的持续性需求, 可以直接提关键属性来做推荐 (主演, 主唱, 导演, 词曲作者, 风格等), 还会有一些影评乐评等用来辅助标记, 还有排行榜, 感觉相对比较容易, 至少做个原型出来要容易, 同时, 用户兴趣的相似度也是可以考虑的, 比如看了电影 A 的人都看了电影 B, 那现在有一个人说他看了电影 A, 我们也可以推荐他去看电影 B. 视频等没有明确分类标签的持续性需求, 计算被推荐条目和用户的相关性比较麻烦, 也不够准确, 这时候用户之间以及被推荐条目之间的相似度似乎是一个更可以考虑的点, YouTube 曾经发过两篇 paper, 其中 08 年的 paper 有很多很炫的方法, 但是同样的那批人在 10 年发的 paper 就回归到最朴素的相关浏览算法了, 而且还特别说了, 数据量大是一个非常明显的优势, 另外展示位置和展现样式的影响因子也非常非常大 (除非算法有天翻地覆的差异, 位置和样式才是最大的影响因子吧 :P). 而像衣服等 “有搭配的持续性需求”, 除了用户购买的相似度, 是否可以考虑从搭配需求上去做? 比如有 MM 买过一件大衣, 除了继续推荐类似的大衣 (通过所有用户的查看/收藏序列), 其实更应该去推荐可搭配的帽子/围巾/靴子什么的才对? 比如笨狗前年脑抽买了个大显示器, 过了一段就攒了台电脑主机, 然后还买了一个音箱… 这就是典型的可搭配持续性需求. 有关搭配性的持续性需求还没去找相关的 paper, 如果有麻烦告诉我一下.

人人的推荐需求

回到人人或其他生活平台级的推荐系统, 因为信息源过多且不集中, 所以简单的文本提取关键词然后按这些关键词推荐的方式绝对不会工作的很好. 在 NLP/IR/DM 支持下, 我们可以识别出用户讨论的内容, 如果能再识别出 TA 是在说需求还是在提供反馈评论, 那接下来需要一个需求转换图, 按这个有向图的下游节点来推荐就好了. 一个已经买了智能机的用户你给他看无线路由的评测或购买信息是顺理成章的 (当然前提是他还没买路由), 一个正在找留学信息的用户你除了推荐留学中介, 外语培训应该也是可以的, 甚至一些出国教程, 必需品购买等都是可以的 (教人打包行李的日志视频等等)

一个好的推荐系统最大的问题在于怎么识别或预判出一个合理的需求. 大概流程如下

1. 提取用户目前的兴趣点或兴趣方向
2. 判断用户是在 seek 阶段还是 review 阶段
-a. 如果还在 seek, 直接按搜索的方法做推荐, END
-b. 如果是在做 review, 转 3
3. 判断 review 的内容是否有重复性
-a. 如果有重复性, 直接按经典相似度的方法做推荐, END
-b. 如果没有重复性, 但是有搭配延续性, 转 4
4. 离线挖掘有搭配延续性需求的转换图, 按图指导推荐方向, END

在一个信息充分度足够的平台上, 应该更容易做 4 中的那个转换图, 否则平台太过垂直, 就只能做到 2.a 或 3.a 那个地步. 比如京东如果没有商品评论, 他只能知道我现在在京东上找什么, 买过什么, 然后在同类别内做推荐. 但是如果换到一个非常大的平台上, 可以根据一些蛛丝马迹来推荐更多相关的东西 (当然因为信息量更大, 推荐的准确度会下降, 但是整体来最后的成功数应该会接近或更高). 比如知道我买了机票后, 除了可以向我推荐相关酒店, 旅游等资源 (目前 qunar, kuxun 等已经做到的), 当地的纪念品 (以前在百度, 有出差回来带当地小吃给大家分享的传统), 甚至旅行用的拉杆箱 (今天在电梯里看到一个实际案例), 这些都谁可以推荐?

如果推荐靠谱, 而且有更多的信息提交渠道, 用户可以继续提供更丰富的信息, 形成良性循环. (说提交是从数据的角度来看, 产品上包装下可能就是用户非常愿意做的分享, 比如人气之星, 分享送礼等)

十月份的时候写了一篇 面试题, 随机抽样问题及扩展, 当时这个 blog 没整好, 发在了好几个地方

• http://www.yewen.us/blog/2011/10/random-select-problem/
• http://hi.baidu.com/whusnoopy/blog/item/4f54b3de5d708344cdbf1a08.html
• http://blog.renren.com/blog/bp/Q7fr2sueah

前几天跟 Lee.Mars 聊, 又把这堆问题解答了一遍, 并指出其中一个问题的 bug.

原始版, 数据流 n 选 1. 构建一个可容纳一个数的 buffer, 数据流中第 i 个数过来时做一次 [0, 1] 的 random, 如果小于 1/i, 则更新 buffer. (证明过程略, 很简单的)

buf = 0
cnt = 0
for i in sys.stdin:
  cnt += 1
  if random.random() < 1.0/cnt:
    buf = int(i)

print buf

加强版, 数据流 n 选 k. 同上, 构建的 buffer 大小变为 k, 每次 rand 小于 k/i 时, 将 rand*i 对应的 buffer 更新

k = 3 
buf = []
cnt = 0 
for i in sys.stdin:
  cnt += 1
  rd = int(random.random()*cnt)
  if rd < k:
    if cnt <= k:
      buf.append(int(i))
      buf[cnt-1] = buf[rd]
    buf[rd] = int(i)

print buf 

带权版, 带权数据流 n 选 1. 同原始版, 只是对权重为 w[i] 的第 i 个数, rand 时判断是否小于 w[i]/SUM(w)

sum = 0
buf = 0
cnt = 0 
for i in sys.stdin:
  cnt += 1
  sum += int(i)
  if random.random() < float(i)/sum:
    buf = int(i)

print buf 

带权选 k 版. 这个有 bug, 无解, 因为无法保证最后选出来的 k 个数, 其 SUM(w[k1..kk])/sum(w[1..n]) = k/n, 那个概率无法算

分布式版, m 个序列最后选 k. 每个序列先按加强版选 k 个, 然后将 m*k 个数放到一起, 做带权版的 n 选 k. 由于带权选 k 版有 bug, 所以这里会有一定误差. 而实际上一般的分布式框架是可以保证每个序列数据规模分布都比较均匀, 所以最后的 m*k 个数可以当无权版直接选 k, 这样的误差在工业应用是可以接受的

注: 从 n 选 k 那个就可以很容易看出来, 这其实就是那个把一个序列打乱成随机状态的算法简化, n 选 1 只是 n 选 k 的一个特例

今天看到张栋在新浪微博上说一个他当时被 Google 面试时碰到的一个问题 (其实我也碰到过), 觉得这个问题很有意思, 我自己也在工作中碰到过该问题的实际应用, 扩展一下, 大家一起活动下脑子玩玩 :) (答案我就不说了, 不然多没意思)

原始版
有一个店老板, 他决定从每天光顾他的店的顾客中随机选出一个人, 在当天打烊时给这位顾客发去一份小礼品, 问怎样选才能保证随机 (我表达能力太弱, 没看懂的请直接看抽象版. 关键点, 顾客不是同时来, 所以没法让这一堆人站好随机挑, 而且每天会来多少人你不知道, 可能打烊前突然来一大拨人, 老板比较呆, 只能记住一两个人, 没法把所有人的信息都记录下来)

抽象版
有一个数据流输入过来, 请在数据流停止时, 返回数据流中的随机的一个数. 注意, 数据是流, 只能一次读, 而且数据流很大, 本机无法完整存储 (最多也就很少几条)

实际应用
从每天的日志中, 对符合条件的日志, 随机抽出一条来做校验, 数据太大只能一次读过去, 要保证是随机的

加强版
如果店老板每天不是送一个人礼品, 而是送 k 个人礼品, 怎么办?

加强版的抽象
从数据流中返回随机的 k 个数

加强版的实际应用
从每天的日志中随机挑出 k 条来做校验

带权版
每个顾客有一个会员级别, 级别越高的人获奖概率越大, 怎么办?

带权版的抽象
数据流中每个数有权重 w[i], 对数字 i, 返回他的概率从 1/n 变为 w[i] / SUM(w[j], j from 1 to n). k 个数的情况类推

带权版的实际应用
从日志中按权重挑出一条或 k 条来做校验

分布式版
老板开了 m 家分店, 希望还能按平均概率给随机一位或 k 位顾客奖品, 怎么办?

分布式版的抽象
有 m 个数据流, 最后返回的是 m 个数据流合并后的随机数, 一个或 k 个

分布式版的实际应用
日志太大, 一台机器搞不定, 分布式抽取随机的一条或 k 条来做校验 (我下星期会做这个, 所以不要说面试题都是面试官蛋疼想出来坑爹的…)