读算法简史：从美索不达米亚到人工智能时代12推荐算法

1. 马克·扎克伯格

1.1. Mark Zuckerberg
1.2. 1984年出生于纽约州怀特普莱恩斯
1.3. 在他读初中时，他的父亲教会了他如何编程

• 1.3.1. 后来，他父亲雇用了一位专业的程序员来指导他
  

1.4. 进入了哈佛大学，并入选了计算机科学和心理学的联合学位项目
1.5. 扎克伯格对人的行为也怀有长久的兴趣

• 1.5.1. 大多数人都对别人正在做的事情很感兴趣
  
• 1.5.2. 这种痴迷正是日常八卦、重量级传记、名人文化和电视真人秀的精髓所在
  

1.6. 建立了一个名为“脸谱网”(Facemash)的网站

• 1.6.1. 模仿了一个已经存在的名为“人气高不高”(Hot Or Not)的网站
  
• 1.6.2. 有争议的是，脸谱网使用的学生照片是从哈佛大学网站下载的
  

1.7. 新网站“脸书网”(thefacebook.com)于2004年2月上线

• 1.7.1. 扎克伯格当时只有19岁
  
• 1.7.2. 为了绕开大学的制度限制，新网站要求用户自己上传自己的数据
  
• 1.7.3. 学生们利用这个网站做各种各样的事情——规划聚会、组织学习，不可避免地，还有约会
  
• 1.7.4. 扎克伯格开始接受投资、招聘员工，并从大学辍学
  

1.8. 动态消息算法

• 1.8.1. 该算法后来被证明是这家年轻公司面临的最大的工程挑战
  
• 1.8.2. 动态消息不仅仅是一个新功能
  
  
  
  • 1.8.2.1. 它是脸书的再发明
    
  
  
• 1.8.3. 动态消息会为每一名用户生成一个独有的消息页面
  
• 1.8.4. 脸书于2006年9月5日星期二激活了动态消息功能
  
  
  
  • 1.8.4.1. 用户的反应几乎完全一样，每个人都讨厌它，人们觉得这太像跟踪狂了
    
  • 1.8.4.2. 用户花在脸书上的时间比以往任何时候都多
    

    1.8.4.2.1. 脸书为此道歉，并增加了隐私控制措施，静待这场风波平息下来
    

    
    
  
  
• 1.8.5. 动态消息的核心工程学挑战在于，如何创建一种能选择最佳消息项显示给用户的算法
  
  
  
  • 1.8.5.1. 计算机算法如何确定人类用户最感兴趣的是什么？
    
  
  
• 1.8.6. 用户的动态消息是通过按边缘等级分降序排列来呈现的
  
• 1.8.7. 动态消息让病毒式消息传播(viral messaging)变得流行起来
  

1.9. “边缘排序”(EdgeRank)算法

• 1.9.1. 脸书上的每一个动作都被称为一个“边缘”(edge)，可以是用户发帖、状态更新、评论、点赞、加入群组或分享消息
  
• 1.9.2. 对于某一名用户，一个边缘的边缘等级分通过将3个因子相乘来计算
  
  
  
  • 1.9.2.1. 边缘等级分=亲密度×权重×时间衰减
    
  
  
• 1.9.3. 亲密度是衡量用户与边缘的连接强度的指标，反映了用户与创建该边缘的人的关系亲疏程度
  
  
  
  • 1.9.3.1. 脸书上的好友比非好友更亲密
    
  • 1.9.3.2. 两个朋友的共同朋友越多，他们之间的亲密度就越高
    
  • 1.9.3.3. 用户之间的交互次数也影响他们的亲密度得分
    
  
  
• 1.9.4. 权重取决于边缘的类型
  
  
  
  • 1.9.4.1. 需要更多努力来创建的边缘具有更高的权重
    
  • 1.9.4.2. 评论的权重大于点赞
    
  
  
• 1.9.5. 在其他条件相同的情况下，边缘等级分会随着边缘变旧而降低
  
  
  
  • 1.9.5.1. 这确保了算法优先推荐最新的帖子而不是旧的帖子
    
  • 1.9.5.2. 每隔15分钟，算法会针对每个用户和每个帖子重新计算边缘等级分
    
  
  

1.10. 脸书通过在用户发布的帖子中穿插付费广告，将动态消息的浏览量转化为收入
2. 奈飞大奖赛

2.1. 为奈飞(Netflix)开发的一种算法将这项技术提升到了一个新的高度

• 2.1.1. 该算法利用机器学习来识别和利用大量用户数据中潜藏的模式
  

2.2. 奈飞公司由里德·黑斯廷斯(Reed Hastings)和马克·伦道夫(Marc Randolph)于1997年创立

• 2.2.1. 黑斯廷斯和伦道夫原本是东海岸人，后来被吸引到硅谷
  

2.3. 奈飞的推荐系统“电影匹配”(Cinematch)运行良好

• 2.3.1. 到了2006年，该公司开始寻找更好的算法
  

2.4. 奈飞没有靠自己开发新算法，而是采取了不同寻常的举措：发起一场公开竞赛

• 2.4.1. 奈飞宣布为第一个比电影匹配系统准确性高10%的推荐系统颁发100万美元的奖金
  
• 2.4.2. 为了促进竞争，奈飞发布了一个训练数据集，其中包含约50万名客户为近1.8万部不同电影给出的1亿次电影评分
  
  
  
  • 2.4.2.1. 每个数据点包含电影名、用户名、给出的星级评分（1～5星）和记录评分的日期
    
  • 2.4.2.2. 电影名和评分都是真实的，但用户名是匿名处理的，因此无法识别出个人的身份
    
  
  
• 2.4.3. 奈飞还发布了第二个测试数据集
  
  
  
  • 2.4.3.1. 它的内容与训练数据集相似，只是奈飞隐去了星级评分
    
  • 2.4.3.2. 测试数据集要小得多，只包含280万个条目
    
  
  

2.5. 竞赛的目标是建立一个推荐系统，让它能够准确预测测试数据集中隐去的电影评分

• 2.5.1. 参赛者的估计结果是通过测量预测误差(prediction error)来评估的，预测误差是指预测评分和实际评分之差的平方的平均值
  

2.6. 最有效的技术是将尽可能多的不同预测结合在一起

• 2.6.1. 用预测者的话说，任何可以用来帮助预测的信息都是在最终计算中必须纳入考量的因素
  

2.7. 最简单的因素是训练数据集中电影的平均评分

• 2.7.1. 这是所有看过那部电影的用户给出评分的平均值
  

2.8. 评分正在接受预测的用户的慷慨程度

• 2.8.1. 用户的慷慨度可以用他们的平均评分减去所有用户对同一组电影的平均评分来计算
  

2.9. 某些用户给电影的评分，这些用户通常具有与评分正在接受预测的用户相同的评分方式
2.10. 权重能决定因素的相对重要性

• 2.10.1. 权重高就意味着相关因素对最终预测结果的影响更大，权重低意味着该因素不是那么重要
  
• 2.10.2. 将加权后的因子相加，就得出了最终的预测结果
  

2.11. 预测算法

• 2.11.1. 将训练数据集和测试数据集作为输入
  
• 2.11.2. 对测试数据集中每个用户-电影组合，重复以下步骤
  
  
  
  • 2.11.2.1. 对每一个因素，重复以下步骤
    

    2.11.2.1.1. 利用这个因素对用户的电影评分进行预测
    

    2.11.2.1.2. 当所有因素评估完成后，停止重复
    

    
    
  • 2.11.2.2. 对预测因素进行加权和求和
    
  • 2.11.2.3. 输出该用户和电影的最终预测结
    
  • 2.11.2.4. 当所有的用户-电影组合都预测完成后，停止重复
    
  
  

2.12. 训练算法的工作流程

• 2.12.1. 将训练数据集和验证数据集作为输入
  
• 2.12.2. 猜测最佳参数值
  
• 2.12.3. 重复以下步骤
  
  
  
  • 2.12.3.1. 对验证数据集中的所有项执行预测算法
    
  • 2.12.3.2. 调整参数以减少误差
    
  • 2.12.3.3. 当不再有进一步改善时，停止重复
    
  
  
• 2.12.4. 输出预测误差最小的参数
  

2.13. 机器学习方法的美妙之处在于，相比于人类，计算机能够进行的参数组合实验要多很多
2.14. “大人物拿破仑”(Napoleon Dynamite)问题

• 2.14.1. 《大人物拿破仑》是最难预测评分的电影
  
• 2.14.2. 大多数电影的评分都可以很容易地被预测到，因为数据集中存在类似的电影
  
• 2.14.3. ​《大人物拿破仑》的问题在于，没有任何与之相似的影片
  
• 2.14.4. 这部电影是一部古怪的独立喜剧，当时已经成为一部很流行的邪典电影
  
  
  
  • 2.14.4.1. 人们要么喜欢它，要么讨厌它
    
  
  
• 2.14.5. 这是那种朋友之间会为之争吵几个小时的电影
  

2.15. 2009年9月21日，​“贝尔科实用混沌”(BellKor’s Pragmatic Chaos)团队获得了奈飞大奖

• 2.15.1. 该团队取得了比“电影匹配”提升10.06%的成绩
  
• 2.15.2. 该团队是个融合团队，由来自美国AT&namp;T研究所的“科贝尔”(KorBell)团队、来自奥地利的“大混沌”(Big Chaos)团队和来自加拿大的“实用理论”团队合并而成
  
• 2.15.3. 奈飞决定不使用获胜的算法
  
  
  
  • 2.15.3.1. 该公司已经用早期阶段的获胜算法取代了“电影匹配
    
  • 2.15.3.2. 奈飞认为8.43%的改进已经足够好了，并将其保持在这个水平
    
  
  

2.16. 如今，奈飞是全世界最大的互联网电视网络，拥有超过1.37亿用户
3. 谷歌流感趋势

3.1. 2009年，大数据结合机器学习可以预测几乎任何事情的趋势，已经初见端倪
3.2. 对谷歌网络搜索查询进行数据分析可以追踪流感样疾病在美国的传播

• 3.2.1. 该算法能够提前一到两周预测CDC的数据，具有一致性和准确性
  

3.3. 谷歌推出了谷歌流感趋势(Google Flu Trends)网站，为大家提供流感病例数量的实时估计
3.4. 一个研究小组甚至证明，谷歌流感趋势预测的准确性还比不上如今基于两周前CDC数据的流感预测

• 3.4.1. 很多匹配都是随机的
  
• 3.4.2. 统计数据是碰巧被匹配上，但这些查询词条的出现并不是任何人真正感染了流感的结果
  
• 3.4.3. 查询词条和流感数据是相关的，但两者之间没有因果关系
  
• 3.4.4. 在一片喧嚣中，谷歌流感趋势关停了
  

3.5. 问题的极限是，机器学习算法的准确度最多只能达到提供给算法的训练数据所能达到的程度
3.6. 临近预测(nowcasting)的科学有了显著的进展

• 3.6.1. 将情感分析应用于推特帖子上，可以预测票房和选举结果
  
• 3.6.2. 收费站的收入被用来实时评估经济活动
  
• 3.6.3. 智能手机中的运动传感器已经被用于监测地震
  
• 3.6.4. 在未来，当我们有了更为可靠的健康传感器时，我们将再次审视疾病流行的临近预测
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！