随着 DeepMind 成功地使用卷积神经网络（CNN）和强化学习来玩 Atari 游戏，AlphaGo 击败围棋职业选手李世石，强化学习已经成为了机器学习的一个重要研究方向。除此之外，随着人工智能的兴起，自然语言处理在聊天机器人和智能问答客服上也有着广泛的应用。之前在一篇博客里面曾经介绍了强化学习的基本概念，今天要介绍的是强化学习在文本领域的应用，也就是如何使用强化学习来玩文本游戏。要分享的 Paper 是 Deep Reinforcement Learning with a Natural Language Action Space，作者是 Microsoft 的 Ji He 与他的合作者们。

对于强化学习而言，那就不得不提到 Markov 决策过程（Markov Decision Process）。它是由状态（State），动作（Action），状态转移概率（State Transition Probability），折扣因子（Discount Factor），奖励函数（Reward Function）五个部分构成。强化学习做的事情就是该 agent 在某一个时刻处于某个状态 s，然后执行了某个动作 a，从整个环境中获得了奖励 r，根据状态 s 和奖励 r 来继续选择下一个动作 a，目标是让获得的奖励值最大。整个过程其实是一个不断地从环境中执行动作和获得奖励的过程，通过引入动作值函数 Q(s,a) 的概念，介绍了 Q-learning 这个基本算法。通过 Q-learning 来让 agent 获得最大的奖励。

在实际的生产环境中，状态空间 S 很可能是十分巨大的，如果对于 Atari 游戏的话，动作空间 A 是有限的（例如上下左右移动，攻击，躲避等）。因此 DeepMind 在处理这个问题的时候，创新性地使用了卷积神经网络（CNN）和强化学习（RL）两者结合的解决方案。通过 CNN 来读取游戏图像，然后神经网络输出的是动作值函数 Q(s,a)，其中 a 就是游戏手柄上的几个动作按钮。然后使用周围环境的反馈和强化学习方法来获得相应的样本，从而训练整个 CNN 神经网络。

下面来介绍本文的正式内容。首先文本游戏和视觉游戏有一定的差别，视觉游戏的状态就是当前的屏幕图像，文本游戏的状态是一段文本描述，然后玩家来给出一个合适的动作进入下一个状态。例如：白色的文字描述就是当前的状态，蓝色的文字就是玩家要选择的动作。

当玩家选择了其中一个状态（例如选择了第一个 A Lister sandwich）之后，就会进入下一个状态，如图所示。

注：关于文本游戏 Machine of Death 的代码和基本信息，可以参见 https://github.com/jvking/text-games.

为了做一个 agent 使其能够自主地玩文本游戏，基于当前的文本游戏背景，就要考虑到两种文本情况，分别是状态文本（state-text）和动作文本（action-text）。agent 需要同时理解这两部分的文本，然后争取在玩游戏的过程中获得最大的收益，最终才能够学会玩游戏。对于每一个时刻 t，状态是 ，动作是 。该 agent 的策略定义为在状态 执行动作 的概率 。如果折扣因子是 ，那么基于策略 的动作值函数就定义为：

.

在该paper中，作者使用 softmax 策略来进行必要的探索活动，也就是说在状态 选择 的概率是

在这里 是在状态 可以执行的所有动作的集合， 是 的第 i 个动作， 是某个常数。

因为状态文本（state-text）通常来说是长文本，动作文本（action-text）是短文本，两者有着本质的区别，因此作者在构建神经网络的时候分别对状态文本和动作文本搭建了相应的神经网络。在本文中，作者对比了三种神经网络结构，分别是 Max-action DQN，Pre-action DQN 和 DRRN。如下图所示：

对于 Max-action DQN，该模型适用于对每一个状态 中动作空间的数量都是已知的情况，因为它是把状态和动作拼成一个向量作为神经网络的输入的，然后计算出每一个动作的 Q 值。

对于 Pre-action DQN，该模型把每一对状态文本和动作文本当作输入，也就是（状态文本，动作文本）这种形式，通过神经网络计算出这一对状态文本和动作文本的 Q 值。

对于 DRRN，该模型把每一对状态文本和动作文本当作输入，依旧是（状态文本，动作文本）这种形式。然后对状态文本和动作文本分别构建一个神经网络，然后对输出的两个向量进行内积的操作，从而获得 Q 值。用数学语言来描述就是，给定一个状态文本和动作文本的对，也就是 ，使用相应的神经网络同时把 和 映射成向量 和 ，然后计算这两个向量的内积 ，最后选择 作为当前状态的动作。其中， 和 分别指的是状态网络和动作网络的第 个隐藏层神经网络的输出。, 和 , 是在第 层和第 层的权重矩阵和偏移量。也就是说，DRRN 拥有 L 个隐藏层，并且

其中 f 是激活函数，。Q 值函数定义为 ，其中 g 可以定义为两个向量的内积。

综上所述，DRRN 的伪代码如下：

DRRN 相比另外两个模型其创新点在于分别使用了两个网络来映射状态文本和动作文本，因为如果将长文本和短文本直接拼接输入单个神经网络结构的时候，可能会降低 Q 值的质量，所以把 state-text 和 action-text 分别放入不同的网络结构进行学习，最后使用内积合并的方式获得 Q 值的方法会更加优秀。

参考文献：

1. Deep Reinforcement Learning with a Natural Language Action Space

http://blog.sina.com.cn/s/blog_574a437f0102w2bk.html

第2章：知识图谱——机器大脑中的知识库

2.1 什么是知识图谱

在互联网时代，搜索引擎是人们在线获取信息和知识的重要工具。当用户输入一个查询词，搜索引擎会返回它认为与这个关键词最相关的网页。从诞生之日起，搜索引擎就是这样的模式。

直到2012年5月，搜索引擎巨头谷歌在它的搜索页面中首次引入“知识图谱”：用户除了得到搜索网页链接外，还将看到与查询词有关的更加智能化的答案。如图2.1所示，当用户输入“Marie Curie”（玛丽·居里）这个查询词，谷歌会在右侧提供了居里夫人的详细信息，如个人简介、出生地点、生卒年月等，甚至还包括一些与居里夫人有关的历史人物，例如爱因斯坦、皮埃尔·居里（居里夫人的丈夫）等。

从杂乱的网页到结构化的实体知识，搜索引擎利用知识图谱能够为用户提供更具条理的信息，甚至顺着知识图谱可以探索更深入、广泛和完整的知识体系，让用户发现他们意想不到的知识。谷歌高级副总裁艾米特·辛格博士一语道破知识图谱的重要意义所在：“构成这个世界的是实体，而非字符串（things, not strings）”。

图2.1  谷歌搜索引擎的知识图谱

谷歌知识图谱一出激起千层浪，美国的微软必应，中国的百度、搜狗等搜索引擎公司在短短的一年内纷纷宣布了各自的“知识图谱”产品，如百度“知心”、搜狗“知立方”等。为什么这些搜索引擎巨头纷纷跟进知识图谱，在这上面一掷千金，甚至把它视为搜索引擎的未来呢？这就需要从传统搜索引擎的原理讲起。以百度为例，在过去当我们想知道“泰山”的相关信息的时候，我们会在百度上搜索“泰山”，它会尝试将这个字符串与百度抓取的大规模网页做比对，根据网页与这个查询词的相关程度，以及网页本身的重要性，对网页进行排序，作为搜索结果返回给用户。而用户所需的与“泰山”相关的信息，就还要他们自己动手，去访问这些网页来找了。

当然，与搜索引擎出现之前相比，随着网络信息的爆炸式增长，搜索引擎由于大大缩小了用户查找信息的范围，日益成为人们遨游信息海洋的不可或缺的工具。但是，传统搜索引擎的工作方式表明，它只是机械地比对查询词和网页之间的匹配关系，并没有真正理解用户要查询的到底是什么，远远不够“聪明”，当然经常会被用户嫌弃了。

而知识图谱则会将“泰山”理解为一个“实体”（entity），也就是一个现实世界中的事物。这样，搜索引擎会在搜索结果的右侧显示它的基本资料，例如地理位置、海拔高度、别名，以及百科链接等，此外甚至还会告诉你一些相关的“实体”，如嵩山、华山、衡山和恒山等其他三山五岳等。当然，用户输入的查询词并不见得只对应一个实体，例如当在谷歌中查询“apple”（苹果）时，谷歌不止展示IT巨头“Apple-Corporation”（苹果公司）的相关信息，还会在其下方列出“apple-plant”（苹果-植物）的另外一种实体的信息。

很明显，以谷歌为代表的搜索引擎公司希望利用知识图谱为查询词赋予丰富的语义信息，建立与现实世界实体的关系，从而帮助用户更快找到所需的信息。谷歌知识图谱不仅从Freebase和维基百科等知识库中获取专业信息，同时还通过分析大规模网页内容抽取知识。现在谷歌的这幅知识图谱已经将5亿个实体编织其中，建立了35亿个属性和相互关系，并还在不断高速扩充。

谷歌知识图谱正在不断融入其各大产品中服务广大用户。最近，谷歌在Google Play Store的Google Play Movies & TV应用中添加了一个新的功能，当用户使用安卓系统观看视频时，暂停播放，视频旁边就会自动弹出该屏幕上人物或者配乐的信息，如图2.2所示。这些信息就是来自谷歌知识图谱。谷歌会圈出播放器窗口所有人物的脸部，用户可以点击每一个人物的脸来查看相关信息。此前，Google Books 已经应用此功能。

图2.2  Google利用知识图谱标示视频中的人物或配乐信息

2.2  知识图谱的构建

最初，知识图谱是由谷歌推出的产品名称，寓意与Facebook提出的社交图谱（Social Graph）异曲同工。由于其表意形象，现在知识图谱已经被用来泛指各种大规模知识库了。

我们应当如何构建知识图谱呢？我们先了解一下，知识图谱的数据来源都有哪些。知识图谱的最重要的数据来源之一是以维基百科、百度百科为代表的大规模知识库，在这些由网民协同编辑构建的知识库中，包含了大量结构化的知识，可以高效地转化到知识图谱中。此外，互联网的海量网页中也蕴藏了海量知识，虽然相对知识库而言这些知识更显杂乱，但通过自动化技术，也可以将其抽取出来构建知识图谱。接下来，我们分别详细介绍这些识图谱的数据来源。

2.2.1  大规模知识库

大规模知识库以词条作为基本组织单位，每个词条对应现实世界的某个概念，由世界各地的编辑者义务协同编纂内容。随着互联网的普及和Web 2.0理念深入人心，这类协同构建的知识库，无论是数量、质量还是更新速度，都早已超越传统由专家编辑的百科全书，成为人们获取知识的主要来源之一。目前，维基百科已经收录了超过2200万词条，而仅英文版就收录了超过400万条，远超过英文百科全书中最权威的大英百科全书的50万条，是全球浏览人数排名第6的网站。值得一提的是，2012年大英百科全书宣布停止印刷版发行，全面转向电子化。这也从一个侧面说明在线大规模知识库的影响力。人们在知识库中贡献了大量结构化的知识。如图2.3所示，是维基百科关于“清华大学”的词条内容。可以看到，在右侧有一个列表，标注了与清华有关的各类重要信息，如校训、创建时间、校庆日、学校类型、校长，等等。在维基百科中，这个列表被称为信息框（infobox），是由编辑者们共同编辑而成的。信息框中的结构化信息是知识图谱的直接数据来源。

除了维基百科等大规模在线百科外，各大搜索引擎公司和机构还维护和发布了其他各类大规模知识库，例如谷歌收购的Freebase，包含3900万个实体和18亿条实体关系；DBpedia是德国莱比锡大学等机构发起的项目，从维基百科中抽取实体关系，包括1千万个实体和14亿条实体关系；YAGO则是德国马克斯·普朗克研究所发起的项目，也是从维基百科和WordNet等知识库中抽取实体，到2010年该项目已包含1千万个实体和1.2亿条实体关系。此外，在众多专门领域还有领域专家整理的领域知识库。

图2.3  维基百科词条“清华大学”部分内容

2.2.2  互联网链接数据

国际万维网组织W3C在2007年发起了开放互联数据项目（Linked Open Data，LOD），其发布数据集示意图如图2.4所示。该项目旨在将由互联文档组成的万维网（Web of documents）扩展成由互联数据组成的知识空间（Web of data）。LOD以RDF（Resource Description Framework）形式在Web上发布各种开放数据集，RDF是一种描述结构化知识的框架，它将实体间的关系表示为（实体1，关系，实体2）的三元组。LOD还允许在不同来源的数据项之间设置RDF链接，实现语义Web知识库。目前世界各机构已经基于LOD标准发布了数千个数据集，包含数千亿RDF三元组。随着LOD项目的推广和发展，互联网会有越来越多的信息以链接数据形式发布，然而各机构发布的链接数据之间存在严重的异构和冗余等问题，如何实现多数据源的知识融合，是LOD项目面临的重要问题。

图2.4  开放互联数据项目发布数据集示意图

2.2.3  互联网网页文本数据

与整个互联网相比，维基百科等知识库仍只能算沧海一粟。因此，人们还需要从海量互联网网页中直接抽取知识。与上述知识库的构建方式不同，很多研究者致力于直接从无结构的互联网网页中抽取结构化信息，如华盛顿大学Oren Etzioni教授主导的“开放信息抽取”（open information extraction，OpenIE）项目，以及卡耐基梅隆大学Tom Mitchell教授主导的“永不停止的语言学习”（never-ending language learning，NELL）项目。OpenIE项目所开发的演示系统TextRunner已经从1亿个网页中抽取出了5亿条事实，而NELL项目也从Web中学习抽取了超过5千万条事实样例，如图2.5所示。

图2.5  NELL从Web中学习抽取事实样例

显而易见，与从维基百科中抽取的知识库相比，开放信息抽取从无结构网页中抽取的信息准确率还很低，其主要原因在于网页形式多样，噪声信息较多，信息可信度较低。因此，也有一些研究者尝试限制抽取的范围，例如只从网页表格等内容中抽取结构信息，并利用互联网的多个来源互相印证，从而大大提高抽取信息的可信度和准确率。当然这种做法也会大大降低抽取信息的覆盖面。天下没有免费的午餐，在大数据时代，我们需要在规模和质量之间寻找一个最佳的平衡点。

2.2.4  多数据源的知识融合

从以上数据来源进行知识图谱构建并非孤立地进行。在商用知识图谱构建过程中，需要实现多数据源的知识融合。以谷歌最新发布的Knowledge Vault(Dong, et al. 2014)技术为例，其知识图谱的数据来源包括了文本、DOM Trees、HTML表格、RDF语义数据等多个来源。多来源数据的融合，能够更有效地判定抽取知识的可信性。

知识融合主要包括实体融合、关系融合和实例融合三类。对于实体，人名、地名、机构名往往有多个名称。例如“中国移动通信集团公司”有“中国移动”、“中移动”、“移动通信”等名称。我们需要将这些不同名称规约到同一个实体下。同一个实体在不同语言、不同国家和地区往往会有不同命名，例如著名足球明星Beckham在大陆汉语中称作“贝克汉姆”，在香港译作“碧咸”，而在台湾则被称为“贝克汉”。与此对应的，同一个名字在不同语境下可能会对应不同实体，这是典型的一词多义问题，例如“苹果”有时是指一种水果，有时则指的是一家著名IT公司。在这样复杂的多对多对应关系中，如何实现实体融合是非常复杂而重要的课题。如前面开放信息抽取所述，同一种关系可能会有不同的命名，这种现象在不同数据源中抽取出的关系中尤其显著。与实体融合类似，关系融合对于知识融合至关重要。在实现了实体和关系融合之后，我们就可以实现三元组实例的融合。不同数据源会抽取出相同的三元组，并给出不同的评分。根据这些评分，以及不同数据源的可信度，我们就可以实现三元组实例的融合与抽取。

知识融合既有重要的研究挑战，又需要丰富的工程经验。知识融合是实现大规模知识图谱的必由之路。知识融合的好坏，往往决定了知识图谱项目的成功与否，值得任何有志于大规模知识图谱构建与应用的人士高度重视。

2.3  知识图谱的典型应用

知识图谱将搜索引擎从字符串匹配推进到实体层面，可以极大地改进搜索效率和效果，为下一代搜索引擎的形态提供了巨大的想象空间。知识图谱的应用前景远不止于此，目前知识图谱已经被广泛应用于以下几个任务中。

2.3.1  查询理解（Query Understanding）

谷歌等搜索引擎巨头之所以致力于构建大规模知识图谱，其重要目标之一就是能够更好地理解用户输入的查询词。用户查询词是典型的短文本（short text），一个查询词往往仅由几个关键词构成。传统的关键词匹配技术没有理解查询词背后的语义信息，查询效果可能会很差。

例如，对于查询词“李娜大满贯”，如果仅用关键词匹配的方式，搜索引擎根本不懂用户到底希望寻找哪个“李娜”，而只会机械地返回所有含有“李娜”这个关键词的网页。但通过利用知识图谱识别查询词中的实体及其属性，搜索引擎将能够更好地理解用户搜索意图。现在，我们到谷歌中查询“李娜大满贯”，会发现，首先谷歌会利用知识图谱在页面右侧呈现中国网球运动员李娜的基本信息，我们可以知道这个李娜是指中国网球女运动员。同时，谷歌不仅像传统搜索引擎那样返回匹配的网页，更会直接在页面最顶端返回李娜赢得大满贯的次数“2”，如图2.6所示。

图2.6  谷歌中对“李娜大满贯”的查询结果

主流商用搜索引擎基本都支持这种直接返回查询结果而非网页的功能，这背后都离不开大规模知识图谱的支持。以百度为例，图2.7是百度中对“珠穆朗玛峰高度”的查询结果，百度直接告诉用户珠穆朗玛峰的高度是8844.43米。

图2.7  百度中对“珠穆朗玛峰高度”的查询结果

基于知识图谱，搜索引擎还能获得简单的推理能力。例如，图2.8是百度中对“梁启超的儿子的妻子”的查询结果，百度能够利用知识图谱知道梁启超的儿子是梁思成，梁思成的妻子是林徽因等人。

采用知识图谱理解查询意图，不仅可以返回更符合用户需求的查询结果，还能更好地匹配商业广告信息，提高广告点击率，增加搜索引擎受益。因此，知识图谱对搜索引擎公司而言，是一举多得的重要资源和技术。

2.3.2  自动问答（Question Answering）

人们一直在探索比关键词查询更高效的互联网搜索方式。很多学者预测，下一代搜索引擎将能够直接回答人们提出的问题，这种形式被称为自动问答。例如著名计算机学者、美国华盛顿大学计算机科学与工程系教授、图灵中心主任Oren Etzioni于2011年就在Nature杂志上发表文章“搜索需要一场变革“（Search Needs a Shake-Up）。该文指出，一个可以理解用户问题，从网络信息中抽取事实，并最终选出一个合适答案的搜索引擎，才能将我们带到信息获取的制高点。如上节所述，目前搜索引擎已经支持对很多查询直接返回精确答案而非海量网页而已。

关于自动问答，我们将有专门的章节介绍。这里，我们需要着重指出的是，知识图谱的重要应用之一就是作为自动问答的知识库。在搜狗推出中文知识图谱服务“知立方”的时候，曾经以回答“梁启超的儿子的太太的情人的父亲是谁？”这种近似脑筋急转弯似的问题作为案例，来展示其知识图谱的强大推理能力（搜狗知立方服务的实例如图2.9所示）。虽然大部分用户不会这样拐弯抹角地提问，但人们会经常需要寻找诸如“刘德华的妻子是谁？”、“侏罗纪公园的主演是谁？”、“姚明的身高？”以及“北京有几个区？”等问题的答案。而这些问题都需要利用知识图谱中实体的复杂关系推理得到。无论是理解用户查询意图，还是探索新的搜索形式，都毫无例外地需要进行语义理解和知识推理，而这都需要大规模、结构化的知识图谱的有力支持，因此知识图谱成为各大互联网公司的必争之地。

图2.9  搜狗知立方服务

最近，微软联合创始人Paul Allen投资创建了艾伦人工智能研究院（Allen Institute for Artificial Intelligence），致力于建立具有学习、推理和阅读能力的智能系统。2013年底，Paul Allen任命Oren Etzioni教授担任艾伦人工智能研究院的执行主任，该任命所释放的信号颇值得我们思考。

2.3.3  文档表示（Document Representation）

经典的文档表示方案是空间向量模型（Vector Space Model），该模型将文档表示为词汇的向量，而且采用了词袋（Bag-of-Words，BOW）假设，不考虑文档中词汇的顺序信息。这种文档表示方案与上述的基于关键词匹配的搜索方案相匹配，由于其表示简单，效率较高，是目前主流搜索引擎所采用的技术。文档表示是自然语言处理很多任务的基础，如文档分类、文档摘要、关键词抽取，等等。

经典文档表示方案已经在实际应用中暴露出很多固有的严重缺陷，例如无法考虑词汇之间的复杂语义关系，无法处理对短文本（如查询词）的稀疏问题。人们一直在尝试解决这些问题，而知识图谱的出现和发展，为文档表示带来新的希望，那就是基于知识的文档表示方案。一篇文章不再只是由一组代表词汇的字符串来表示，而是由文章中的实体及其复杂语义关系来表示（Schuhmacher, et al. 2014）。该文档表示方案实现了对文档的深度语义表示，为文档深度理解打下基础。一种最简单的基于知识图谱的文档表示方案，可以将文档表示为知识图谱的一个子图（sub-graph），即用该文档中出现或涉及的实体及其关系所构成的图表示该文档。这种知识图谱的子图比词汇向量拥有更丰富的表示空间，也为文档分类、文档摘要和关键词抽取等应用提供了更丰富的可供计算和比较的信息。

知识图谱为计算机智能信息处理提供了巨大的知识储备和支持，将让现在的技术从基于字符串匹配的层次提升至知识理解层次。以上介绍的几个应用可以说只能窥豹一斑。知识图谱的构建与应用是一个庞大的系统工程，其所蕴藏的潜力和可能的应用，将伴随着相关技术的日渐成熟而不断涌现。

2.4  知识图谱的主要技术

大规模知识图谱的构建与应用需要多种智能信息处理技术的支持，以下简单介绍其中若干主要技术。

2.4.1  实体链指（Entity Linking）

互联网网页，如新闻、博客等内容里涉及大量实体。大部分网页本身并没有关于这些实体的相关说明和背景介绍。为了帮助人们更好地了解网页内容，很多网站或作者会把网页中出现的实体链接到相应的知识库词条上，为读者提供更详尽的背景材料。这种做法实际上将互联网网页与实体之间建立了链接关系，因此被称为实体链指。

手工建立实体链接关系非常费力，因此如何让计算机自动实现实体链指，成为知识图谱得到大规模应用的重要技术前提。例如，谷歌等在搜索引擎结果页面呈现知识图谱时，需要该技术自动识别用户输入查询词中的实体并链接到知识图谱的相应节点上。

实体链指的主要任务有两个，实体识别（Entity Recognition）与实体消歧（Entity Disambiguation），都是自然语言处理领域的经典问题。

实体识别旨在从文本中发现命名实体，最典型的包括人名、地名、机构名等三类实体。近年来，人们开始尝试识别更丰富的实体类型，如电影名、产品名，等等。此外，由于知识图谱不仅涉及实体，还有大量概念（concept），因此也有研究者提出对这些概念进行识别。

不同环境下的同一个实体名称可能会对应不同实体，例如“苹果”可能指某种水果，某个著名IT公司，也可能是一部电影。这种一词多义或者歧义问题普遍存在于自然语言中。将文档中出现的名字链接到特定实体上，就是一个消歧的过程。消歧的基本思想是充分利用名字出现的上下文，分析不同实体可能出现在该处的概率。例如某个文档如果出现了iphone，那么“苹果”就有更高的概率指向知识图谱中的叫“苹果”的IT公司。

实体链指并不局限于文本与实体之间，如图2.10所示，还可以包括图像、社交媒体等数据与实体之间的关联。可以看到，实体链指是知识图谱构建与应用的基础核心技术。

图2.10  实体链指实现实体与文本、图像、社交媒体等数据的关联

2.4.2  关系抽取（Relation Extraction）

构建知识图谱的重要来源之一是从互联网网页文本中抽取实体关系。关系抽取是一种典型的信息抽取任务。

典型的开放信息抽取方法采用自举（bootstrapping）的思想，按照“模板生成=>实例抽取”的流程不断迭代直至收敛。例如，最初可以通过“X是Y的首都”模板抽取出（中国，首都，北京）、（美国，首都，华盛顿）等三元组实例；然后根据这些三元组中的实体对“中国-北京”和“美国-华盛顿”可以发现更多的匹配模板，如“Y的首都是X”、“X是Y的政治中心”等等；进而用新发现的模板抽取更多新的三元组实例，通过反复迭代不断抽取新的实例与模板。这种方法直观有效，但也面临很多挑战性问题，如在扩展过程中很容易引入噪声实例与模板，出现语义漂移现象，降低抽取准确率。研究者针对这一问题提出了很多解决方案：提出同时扩展多个互斥类别的知识，例如同时扩展人物、地点和机构，要求一个实体只能属于一个类别；也有研究提出引入负实例来限制语义漂移。

我们还可以通过识别表达语义关系的短语来抽取实体间关系。例如，我们通过句法分析，可以从文本中发现“华为”与“深圳”的如下关系：（华为，总部位于，深圳）、（华为，总部设置于，深圳）、以及（华为，将其总部建于，深圳）。通过这种方法抽取出的实体间关系非常丰富而自由，一般是一个以动词为核心的短语。该方法的优点是，我们无需预先人工定义关系的种类，但这种自由度带来的代价是，关系语义没有归一化，同一种关系可能会有多种不同的表示。例如，上述发现的“总部位于”、“总部设置于”以及“将其总部建于”等三个关系实际上是同一种关系。如何对这些自动发现的关系进行聚类归约是一个挑战性问题。

我们还可以将所有关系看做分类标签，把关系抽取转换为对实体对的关系分类问题。这种关系抽取方案的主要挑战在于缺乏标注语料。2009年斯坦福大学的研究者提出远程监督（Distant Supervision）思想，使用知识图谱中已有的三元组实例启发式地标注训练语料。远程监督思想的假设是，每个同时包含两个实体的句子，都表述了这两个实体在知识库中的对应关系。例如，根据知识图谱中的三元组实例（苹果，创始人，乔布斯）和（苹果，CEO，库克），我们可以将以下四个包含对应实体对的句子分别标注为包含“创始人”和“CEO”关系：

我们将知识图谱三元组中每个实体对看做待分类样例，将知识图谱中实体对关系看做分类标签。通过从出现该实体对的所有句子中抽取特征，我们可以利用机器学习分类模型（如最大熵分类器、SVM等）构建信息抽取系统。对于任何新的实体对，根据所出现该实体对的句子中抽取的特征，我们就可以利用该信息抽取系统自动判断其关系。远程监督能够根据知识图谱自动构建大规模标注语料库，因此取得了瞩目的信息抽取效果。

与自举思想面临的挑战类似，远程监督方法会引入大量噪声训练样例，严重损害模型准确率。例如，对于（苹果，创始人，乔布斯）我们可以从文本中匹配以下四个句子：

在这四个句子中，前两个句子的确表明苹果与乔布斯之间的创始人关系；但是，后两个句子则并没有表达这样的关系。很明显，由于远程监督只能机械地匹配出现实体对的句子，因此会大量引入错误训练样例。为了解决这个问题，人们提出了很多去除噪声实例的办法，来提升远程监督性能。例如，研究发现，一个正确训练实例往往位于语义一致的区域，也就是其周边的实例应当拥有相同的关系；也有研究提出利用因子图、矩阵分解等方法，建立数据内部的关联关系，有效实现降低噪声的目标。

关系抽取是知识图谱构建的核心技术，它决定了知识图谱中知识的规模和质量。关系抽取是知识图谱研究的热点问题，还有很多挑战性问题需要解决，包括提升从高噪声的互联网数据中抽取关系的鲁棒性，扩大抽取关系的类型与抽取知识的覆盖面，等等。

2.4.3  知识推理（Knowledge Reasoning）

推理能力是人类智能的重要特征，能够从已有知识中发现隐含知识。推理往往需要相关规则的支持，例如从“配偶”+“男性”推理出“丈夫”，从“妻子的父亲”推理出“岳父”，从出生日期和当前时间推理出年龄，等等。

这些规则可以通过人们手动总结构建，但往往费时费力，人们也很难穷举复杂关系图谱中的所有推理规则。因此，很多人研究如何自动挖掘相关推理规则或模式。目前主要依赖关系之间的同现情况，利用关联挖掘技术来自动发现推理规则。

实体关系之间存在丰富的同现信息。如图2.11所示，在康熙、雍正和乾隆三个人物之间，我们有（康熙，父亲，雍正）、（雍正，父亲，乾隆）以及（康熙，祖父，乾隆）三个实例。根据大量类似的实体X、Y、Z间出现的（X，父亲，Y）、（Y，父亲，Z）以及（X，祖父，Z）实例，我们可以统计出“父亲+父亲=>祖父”的推理规则。类似地，我们还可以根据大量（X，首都，Y）和（X，位于，Y）实例统计出“首都=>位于”的推理规则，根据大量（X，总统，美国）和（X，是，美国人）统计出“美国总统=>是美国人”的推理规则。

图2.11  知识推理举例

知识推理可以用于发现实体间新的关系。例如，根据“父亲+父亲=>祖父”的推理规则，如果两实体间存在“父亲+父亲”的关系路径，我们就可以推理它们之间存在“祖父”的关系。利用推理规则实现关系抽取的经典方法是Path Ranking Algorithm（Lao &Cohen2010），该方法将每种不同的关系路径作为一维特征，通过在知识图谱中统计大量的关系路径构建关系分类的特征向量，建立关系分类器进行关系抽取，取得不错的抽取效果，成为近年来的关系抽取的代表方法之一。但这种基于关系的同现统计的方法，面临严重的数据稀疏问题。

在知识推理方面还有很多的探索工作，例如采用谓词逻辑（Predicate Logic）等形式化方法和马尔科夫逻辑网络（Markov Logic Network）等建模工具进行知识推理研究。目前来看，这方面研究仍处于百家争鸣阶段，大家在推理表示等诸多方面仍未达成共识，未来路径有待进一步探索。

2.4.4  知识表示（Knowledge Representation）

在计算机中如何对知识图谱进行表示与存储，是知识图谱构建与应用的重要课题。

如“知识图谱”字面所表示的含义，人们往往将知识图谱作为复杂网络进行存储，这个网络的每个节点带有实体标签，而每条边带有关系标签。基于这种网络的表示方案，知识图谱的相关应用任务往往需要借助于图算法来完成。例如，当我们尝试计算两实体之间的语义相关度时，我们可以通过它们在网络中的最短路径长度来衡量，两个实体距离越近，则越相关。而面向“梁启超的儿子的妻子”这样的推理查询问题时，则可以从“梁启超”节点出发，通过寻找特定的关系路径“梁启超->儿子->妻子->?”，来找到答案。

然而，这种基于网络的表示方法面临很多困难。首先，该表示方法面临严重的数据稀疏问题，对于那些对外连接较少的实体，一些图方法可能束手无策或效果不佳。此外，图算法往往计算复杂度较高，无法适应大规模知识图谱的应用需求。

最近，伴随着深度学习和表示学习的革命性发展，研究者也开始探索面向知识图谱的表示学习方案。其基本思想是，将知识图谱中的实体和关系的语义信息用低维向量表示，这种分布式表示（Distributed Representation）方案能够极大地帮助基于网络的表示方案。其中，最简单有效的模型是最近提出的TransE（Bordes, et al. 2013）。TransE基于实体和关系的分布式向量表示，将每个三元组实例（head，relation，tail）中的关系relation看做从实体head到实体tail的翻译，通过不断地调整h、r和t（head、relation和tail的向量），使（h + r）尽可能与t相等，即h + r = t。该优化目标如图2.12所示。

图2.12  基于分布式表示的知识表示方案

通过TransE等模型学习得到的实体和关系向量，能够在很大程度上缓解基于网络表示方案的稀疏性问题，应用于很多重要任务中。

首先，利用分布式向量，我们可以通过欧氏距离或余弦距离等方式，很容易地计算实体间、关系间的语义相关度。这将极大地改进开放信息抽取中实体融合和关系融合的性能。通过寻找给定实体的相似实体，还可用于查询扩展和查询理解等应用。

其次，知识表示向量可以用于关系抽取。以TransE为例，由于我们的优化目标是让h+r=t，因此，当给定两个实体h和t的时候，我们可以通过寻找与t-h最相似的r，来寻找两实体间的关系。（Bordes, et al. 2013）中的实验证明，该方法的抽取性能较高。而且我们可以发现，该方法仅需要知识图谱作为训练数据，不需要外部的文本数据，因此这又称为知识图谱补全（Knowledge Graph Completion），与复杂网络中的链接预测（Link Prediction）类似，但是要复杂得多，因为在知识图谱中每个节点和连边上都有标签（标记实体名和关系名）。

最后，知识表示向量还可以用于发现关系间的推理规则。例如，对于大量X、Y、Z间出现的（X，父亲，Y）、（Y，父亲，Z）以及（X，祖父，Z）实例，我们在TransE中会学习X+父亲=Y，Y+父亲=Z，以及X+祖父=Z等目标。根据前两个等式，我们很容易得到X+父亲+父亲=Z，与第三个公式相比，就能够得到“父亲+父亲=>祖父”的推理规则。前面我们介绍过，基于关系的同现统计学习推理规则的思想，存在严重的数据稀疏问题。如果利用关系向量表示提供辅助，可以显著缓解稀疏问题。

2.5  前景与挑战

如果未来的智能机器拥有一个大脑，知识图谱就是这个大脑中的知识库，对于大数据智能具有重要意义，将对自然语言处理、信息检索和人工智能等领域产生深远影响。

现在以商业搜索引擎公司为首的互联网巨头已经意识到知识图谱的战略意义，纷纷投入重兵布局知识图谱，并对搜索引擎形态日益产生重要的影响。同时，我们也强烈地感受到，知识图谱还处于发展初期，大多数商业知识图谱的应用场景非常有限，例如搜狗知立方更多聚焦在娱乐和健康等领域。根据各搜索引擎公司提供的报告来看，为了保证知识图谱的准确率，仍然需要在知识图谱构建过程中采用较多的人工干预。

可以看到，在未来的一段时间内，知识图谱将是大数据智能的前沿研究问题，有很多重要的开放性问题亟待学术界和产业界协力解决。我们认为，未来知识图谱研究有以下几个重要挑战。

1. 知识类型与表示。知识图谱主要采用（实体1，关系，实体2）三元组的形式来表示知识，这种方法可以较好地表示很多事实性知识。然而，人类知识类型丰富多样，面对很多复杂知识，三元组就束手无策了。例如，人们的购物记录信息，新闻事件等，包含大量实体及其之间的复杂关系，更不用说人类大量的涉及主观感受、主观情感和模糊的知识了。有很多学者针对不同场景设计了不同的知识表示方法。知识表示是知识图谱构建与应用的基础，如何合理设计表示方案，更好地涵盖人类不同类型的知识，是知识图谱的重要研究问题。最近认知领域关于人类知识类型的探索（Tenenbaum, et al. 2011）也许会对知识表示研究有一定启发作用。

2. 知识获取。如何从互联网大数据萃取知识，是构建知识图谱的重要问题。目前已经提出各种知识获取方案，并已经成功抽取出大量有用的知识。但在抽取知识的准确率、覆盖率和效率等方面，都仍不尽如人意，有极大的提升空间。

3. 知识融合。从不同来源数据中抽取的知识可能存在大量噪声和冗余，或者使用了不同的语言。如何将这些知识有机融合起来，建立更大规模的知识图谱，是实现大数据智能的必由之路。

4. 知识应用。目前大规模知识图谱的应用场景和方式还比较有限，如何有效实现知识图谱的应用，利用知识图谱实现深度知识推理，提高大规模知识图谱计算效率，需要人们不断锐意发掘用户需求，探索更重要的应用场景，提出新的应用算法。这既需要丰富的知识图谱技术积累，也需要对人类需求的敏锐感知，找到合适的应用之道。

2.6  内容回顾与推荐阅读

本章系统地介绍了知识图谱的产生背景、数据来源、应用场景和主要技术。通过本章我们主要有以下结论：

— 知识图谱是下一代搜索引擎、自动问答等智能应用的基础设施。

— 互联网大数据是知识图谱的重要数据来源。

— 知识表示是知识图谱构建与应用的基础技术。

— 实体链指、关系抽取和知识推理是知识图谱构建与应用的核心技术。

知识图谱与本体（Ontology）和语义网（Semantic Web）等密切相关，有兴趣的读者可以搜索与之相关的文献阅读。知识表示（KnowledgeRepresentation）是人工智能的重要课题，读者可以通过人工智能专著（Russell & Norvig 2009）了解其发展历程。在关系抽取方面，读者可以阅读（Nauseates, etal. 2013）、（Nickel, et al. 2015）详细了解相关技术。

2.7  参考文献

[1] (Bordes, et al. 2013) Bordes, A.,Usunier, N., Garcia-Duran, A., Weston, J., & Yakhnenko, O. (2013). Translatingembeddings for modeling multi-relational data. In Proceedings of NIPS.

[2] (Dong, et al. 2014) Dong, X., Gabrilovich,E., Heitz, G., Horn, W., et al. Knowledge Vault A web-scale approach toprobabilistic knowledge fusion. In Proceedings of KDD.

[3]   (Lao & Cohen 2010) Lao, N., & Cohen, W. W. (2010). Relationalretrieval using a combination of path-constrained random walks. Machinelearning, 81(1), 53-67.

[4]   (Nauseates,et al. 2013) Nastase, V., Nakov, P., Seaghdha, D. O., & Szpakowicz, S. (2013). Semanticrelations between nominals. Synthesis Lectures on Human Language Technologies,6(1), 1-119.

[5]   (Nickel,et al. 2015) Nickel, M., Murphy, K., Tresp, V., & Gabrilovich, E. A Review of RelationalMachine Learning for Knowledge Graphs.

[6] (Russell & Norvig 2009) Russell, S., & Norvig, P. (2009). ArtificialIntelligence: A Modern Approach, 3rd Edition. Pearson Press.（中文译名：人工智能——一种现代方法）.

[7]   (Schuhmacher,et al. 2014) Schuhmacher, M., & Ponzetto, S. P. Knowledge-based graphdocument modeling. In Proceedings of the 7th ACM international conference onWeb search and data mining. In Proceedings of WSDM.

How AI is helping detect fraud and fight criminals

AI is about to go mainstream. It will show up in the connected home, in your car, and everywhere else. While it’s not as glamorous as the sentient beings that turn on us in futuristic theme parks, the use of AI in fraud detection holds major promise. Keeping fraud at bay is an ever-evolving battle in which both sides, good and bad, are adapting as quickly as possible to determine how to best use AI to their advantage.

There are currently three major ways that AI is used to fight fraud, and they correspond to how AI has developed as a field. These are:

1. Rules and reputation lists
2. Supervised machine learning
3. Unsupervised machine learning

Rules and reputation lists

Rules and reputation lists exist in many modern organizations today to help fight fraud and are akin to “expert systems,” which were first introduced to the AI field in the 1970s. Expert systems are computer programs combined with rules from domain experts.They’re easy to get up and running and are human-understandable, but they’re also limited by their rigidity and high manual effort.

A “rule” is a human-encoded logical statement that is used to detect fraudulent accounts and behavior. For example, an institution may put in place a rule that states, “If the account is purchasing an item costing more than $1000, is located in Nigeria, and signed up less than 24 hours ago, block the transaction.”

Reputation lists, similarly, are based on what you already know is bad. A reputation list is a list of specific IPs, device types, and other single characteristics and their corresponding reputation score. Then, if an account is coming from an IP on the bad reputation list, you block them.

While rules and reputation lists are a good first attempt at fraud detection and prevention, they can be easily gamed by cybercriminals. These days, digital services abound, and these companies make the sign-up process frictionless. Therefore, it takes very little time for fraudsters to make dozens, or even thousands, of accounts. They then use these accounts to learn the boundaries of the rules and reputation lists put in place. Easy access to cloud hosting services, VPNs, anonymous email services, device emulators, and mobile device flashing makes it easy to come up with unsuspicious attributes that would miss reputation lists.

Since the 1990s, expert systems have fallen out of favor in many domains, losing out to more sophisticated techniques. Clearly, there are better tools at our disposal for fighting fraud. However, a significant number of fraud-fighting teams in modern companies still rely on this rudimentary approach for the majority of their fraud detection, leading to massive human review overhead, false positives, and sub-optimal detection results.

Supervised machine learning (SML)

Machine learning is a subfield of AI that attempts to address the issue of previous approaches being too rigid. Researchers wanted the machines to learn from data, rather than encoding what these computer programs should look for (a different approach from expert systems). Machine learning began to make big strides in the 1990s, and by the 2000s it was effectively being used in fighting fraud as well.

Applied to fraud, supervised machine learning (SML) represents a big step forward. It’s vastly different from rules and reputation lists because instead of looking at just a few features with simple rules and gates in place, all features are considered together.

There’s one downside to this approach. An SML model for fraud detection must be fed historical data to determine what the fraudulent accounts and activity look like versus what the good accounts and activity look like. The model would then be able to look through all of the features associated with the account to make a decision. Therefore, the model can only find fraud that is similar to previous attacks. Many sophisticated modern-day fraudsters are still able to get around these SML models.

That said, SML applied to fraud detection is an active area of development because there are many SML models and approaches. For instance, applying neural networks to fraud can be very helpful because it automates feature engineering, an otherwise costly step that requires human intervention. This approach can decrease the incidence of false positives and false negatives compared to other SML models, such as SVM and random forest models, since the hidden neurons can encode many more feature possibilities than can be done by a human.

Unsupervised machine learning (UML)

Compared to SML, unsupervised machine learning (UML) has cracked fewer domain problems. For fraud detection, UML hasn’t historically been able to help much. Common UML approaches (e.g., k-means and hierarchical clustering, unsupervised neural networks, and principal component analysis) have not been able to achieve good results for fraud detection.

Having an unsupervised approach to fraud can be  difficult to build in-house since it requires processing billions of events all together and there are no out-of-the-box effective unsupervised models. However, there are companies that have made strides in this area.

The reason it can be applied to fraud is due to the anatomy of most fraud attacks. Normal user behavior is chaotic, but fraudsters will work in patterns, whether they realize it or not. They are working quickly and at scale. A fraudster isn’t going to try to steal $100,000 in one go from an online service. Rather, they make dozens to thousands of accounts, each of which may yield a profit of a few cents to several dollars. But those activities will inevitably create patterns, and UML can detect them.

The main benefits of using UML are:

• You can catch new attack patterns earlier
• All of the accounts are caught, stopping the fraudster from making any money
• Chance of false positives is much lower, since you collect much more information before making a detection decision

Putting it all together

Each approach has its own advantages and disadvantages, and you can benefit from each method. Rules and reputation lists can be implemented cheaply and quickly without AI expertise. However, they have to be constantly updated and will only block the most naive fraudsters. SML has become an out-of-the box technology that can consider all the attributes for a single account or event, but it’s still limited in that it can’t find new attack patterns. UML is the next evolution, as it can find new attack patterns, identify all of the accounts associated with an attack, and provide a full global view. On the other hand, it’s not as effective at stopping individual fraudsters with low-volume attacks and is difficult to implement in-house. Still, it’s certainly promising for companies looking to block large-scale or constantly evolving attacks.

A healthy fraud detection system often employs all three major ways of using AI to fight fraud. When they’re used together properly, it’s possible to benefit from the advantages of each while mitigating the weaknesses of the others.

AI in fraud detection will continue to evolve, well beyond the technologies explored above, and it’s hard to even grasp what the next frontier will look like. One thing we know for sure, though, is that the bad guys will continue to evolve along with it, and the race is on to use AI to detect criminals faster than they can use it to hide.

Catherine Lu is a technical product manager at DataVisor, a full-stack online fraud analytics platform.

Reinforcement Learning, a key Google DeepMind algorithm, could overhaul news recommendation engines and greatly improve users stickiness. After beating a Go Grand Master, the algorithm could become the engine of choice for true personalization.

My interest for DeepMind goes back to its acquisition by Google, in January 2014, for about half a billion dollars. Later in California, I had conversations with Artificial Intelligence and deep learning experts; they said Google had in fact captured about half of the world’s best A.I. minds, snatching several years of Stanford A.I. classes, and paying top dollar for talent. Acquiring London startup Deep Mind was a key move in a strategy aimed at cornering the A.I. field. My interlocutors at Google and Stanford told me it could lead to major new iterations of the company, with A.I. percolating in every branch of Google (now Alphabet), from improving search to better YouTube recommendations, to more advanced projects such as predictive health care or automated transportation.

Demis Hassabis, DeepMind’s founder and CEO, a great communicator, gives captivating lectures, this Oxford University one among the best, delivered on February 24th. The 40-year old PhD in Cognitive Neuroscience, and Computer Science graduate from MIT and Harvard, offers this explanation of his work:

“The core of what we do focuses around what we call Reinforcement Learning. And that’s how we think about intelligence at DeepMind.

[Hassabis then shows the following diagram]

We start with the agent system, the A.I. That agent finds itself in some kind of environment, trying to achieve a goal. In a real-world environment, the agent could be a robot or, in a virtual environment, an avatar.

The agent interacts with the environment in two ways. Firstly against observations through its sensory operators. We currently use vision but we start to think about other modalities.

One of the jobs of the agent system is to build the best possible model of the environment out there, just based on these incomplete and noisy observations that [the agent] is receiving in real time. And it keeps updating its model in the face of new evidences.

Once it built this model, the second job of the agent is to make predictions of what is going to happen next. If you can make predictions, you can start planning about what to do. So if you try to achieve a goal, the agent will have a set of actions available. The decision making problem is to pick which action would be the best to take toward your goal.

Once the agent has decided that based on its model, and its planned trajectories, it executes actions that may or may not make some changes in the environment, and that drives the observations…”

Reinforcement Learning is a highly complex process. First, the observed environment is very noisy, incomplete and largely consists of unstructured pieces of data. When DeepMind decided to tackle basic Atari games like Breakout and Pong, the input was nothing but raw pixels, and the output was predictions — likely target position — and then actions — racket placement. All of the above aimed at maximizing the subsequent reward: survival and score. After a few hundreds games, the machine was able to devise on its own creative strategies that would surprise even its creators (read here, or view this video, time code 10:27).

Over time, the tests will migrate to more complex environment such as 3D games in which it becomes harder to distinguish the pattern of a wall from a useful piece of information.

A rather challenging signa-to-noise environment

DeepMind’s future goals involves dealing with very large and complex sets of data such as genomics, climate, energy or macroeconomics.

Regardless of the nature of the input stream, the principle is roughly the same. The A.I. system relies on a deep neural network to filter raw sensory data and form meaningful patterns to be analyzed. It then builds an optimized statistical model, updates it in real time, and derives the best possible actions from the set of observations available at a given moment. Then the whole system loops back.

How does this connect to improving news production?

Before we get into this, let’s roll back a little bit.

For a news production system, recommending related stories or videos is the most efficient way to increase reader engagement. For media who rely on advertising, sold on CPM or on a per-click basis, raising the number of page views per reader has a direct impact on ad revenue. Paid-for media are less sensitive to page views, but reminding readers of the breadth and depth of an editorial production is a key contributor to a news brand’s status — and a way to underline its economic value.

But there is a problem: today’s news recommendation systems are often terrible.

To display related stories or videos, publishers unwilling to invest in smart, fine-tuned systems have settled for engines based on crude semantic analysis of content. Hence embarrassing situations arise. For example, a piece about a major pedophile cover-up by the French clergy will trigger suggestions about child care. Or another where the state of an intellectual debate will suggest a piece on spelling, or an another one about waste management. The worst are stories automatically proposed by Outbrain or Taboola and picked up all over the web: not only are they the same everywhere, but they tap into the same endless field of click-bait items. The only virtue of these two systems is the direct cash-back for the publisher.

Something needs to be done to improve recommendation systems. A.I. and Reinforcement Learning offer a promising path.

In Demis Hassabis’ demonstration, the important words are : Environment, Observations, Models, Predictions and Actions. Let’s consider these keywords in the context of news production and consumption.

The Environment is dual. The external side is built on the general news cycle. At any given moment, automatically assessing a topic’s weight is reasonably easy, but even though they’re critical to predicting how the news cycle will evolve, detecting low-noise signals is much trickier. As for the internal news environment, it is simply the output of various contents produced (or curated) by the newsroom.

Observations are multiple: they include the vast range of available analytics, again at two levels: how a piece of contents is faring in general (against the background noise or the competition), and how each individual reader behaves. Here, things become interesting.

Models are then fed with a mix of statistical and behavioral data such as: “Stories [x] containing [semantic footprint] perform well against context [of this type of information].” Or: Reader #453.09809 is currently interested by [topics], but she has on her radar this [low-noise topic] that is small but growing.

Predictions detect both contents and topics that have the best lift in the news cycle and pique the reader’s interest, dynamically, in real time.

Actions will then range form putting stories or videos in front of the audience and, more specifically, at the individual level. Personalization will shift from passive (the system serves stories based of the presumed and generally static reader profile) to dynamic, based on current and predicted interest.

Demis Hassabis makes clear that enhanced personalization is on DeepMind’s roadmap:

“Personalization doesn’t work very well. It currently sums up to averaging the crowd as opposed to adapting to the human individual”

It would be unrealistic to see a news outlet developing such A.I.-based recommendation engine on its own, but we could easily foresee companies already working on A.I. selling it as SaaS (Software as a Service.)

A new generation of powerful recommendation engines could greatly benefit the news industry. It would ensure much higher reader loyalty, reinforce brand trust (it recommends stories that are both good and relevant), and help build deeper and more consistent news packages while giving a new life to archives.

Who will jump on the opportunity? Probably those who are the most prone to invest in tech. I would guess Buzzfeed and the Jeff Bezos-owned Washington Post.

— frederic.filloux@mondaynote.com

原文链接：http://www.twoeggz.com/news/3147867.html

规则引擎，机器学习模型，设备指纹，黑白名单（例如邮件、IP地址黑白名单）和无监督检测分析？经常会有人问，我们应该选择哪种反欺诈检测方式？其实每一种方法都有其独特的优势，企业应该结合反欺诈解决方案及反欺诈行业专家经验，搭建出一套最适合自己公司业务、产品以及用户类型的反欺诈管理系统。

规则引擎和学习模型是传统反欺诈系统构建中重要的两个基本组成部分。接下来的文章中会介绍这两套系统是如何工作的？它们各自的优势和局限性是什么？为什么无监督分析算法优越于规则引擎和机器学习模型，以及使用无监督分析算法在捕捉新型欺诈时的必要性。

>>>>规则引擎

>>>>工作机制

规则引擎将商业业务逻辑和应用程序代码划分开来，安全和风险分析师等基于SQL或数据库知识就可以独自管理运行规则。有效的规则可以通过几行逻辑代码一目了然的进行表述：If A and B, then do C。例如：

IF(user_email=type_free_email_service) AND (comment_character_count ≥ 150 per sec) {

flag user_account as spammer

mute comment

}

规则引擎同样可以使用加权打分评分机制。例如，下表中的每一项规则都对应一个分值，正数或负数，这个分值可以由分析师赋值。所有规则的分数会被加起来，之后得到一个总计分数。规则引擎基于分数临界值创建出业务运维流程。在一个典型的运维流中，根据分数范围，一般会分为三种行为类型，例如：

1.高于1000 － 否认（如拒绝交易，暂停帐户）

2.低于300－接受（如确认订单，通过内容）

3.介于300到1000－提示需要增加额外的审核，置入人工审校池

➜优势

规则引擎可以从数据库中导入数据，挑选出黑名单（如IP地址）和其它坏的列表。每当一个新的欺诈情况发生后，分析师会增加一个新规则，以保证公司在可预见范围内免于欺诈风险。这样通过使用规则引擎，公司便可以避免一些周期性出现的欺诈。

➜局限性

一旦欺诈规模增大，规则引擎就会展现出局限性。欺诈者不会在被捕捉后依旧坐以待毙，他们会研究你是如何捕捉他们，之后变换新的方式，避免再次被捉到。所以，规则作用的时间很有限,可能是几周，甚至几天。试想一下，当你在运行和测试成百上千条新的规则同时，还需要每隔几天增加新的规则，删除或更新之前的规则，并对规则进行加权，这无疑要花费大量运营资源,时间，和费用来维护。

如果一个反欺诈分析师要在3种规则下计算出通过、拒绝及比例数字，并通过比例变化情况调整每一项规则的分值，需要做出8种改变：2^3 = 8（values^rules）。而测试3种不同值的10种规则需要做出超过5.9万次变化。逐渐随着规则数量增加，改变频率也会随之快速增长。

规则引擎不会从分析观察或反馈中自动学习。由于欺诈者经常改变欺诈方式，导致数据会间歇性暴露在各种新的攻击下。此外，规则引擎是基于二进制方式处理信息，有可能无法完全检测到数据细微差别，这会导致出现更高的误判率及用户负面体验。

有监督机器学习模型

➜工作机制

有监督机器学习模式是反欺诈检测中最为广泛使用的机器学习模式。其中包含的几个学习技术分别有决策树算法，随机森林，最近邻算法，支持向量机和朴素贝叶斯分类。机器学习通常从有标签数据中自动创建出模型，来检测欺诈行为。

在创建模型的过程中，清楚了解哪些是欺诈行为，哪些不是，会起到至关重要的作用。模型中倒入的数据会影响其检测效果。用已知欺诈数据和正常数据做训练集，可以训练出学习模型来填补并增强规则引擎无法覆盖的复杂欺诈行为。

下面是一个关于有监督机器学习机制如何将新的数据划分为欺诈和非欺诈的例子。训练数据通过识别模型特点，可以预知两种类型欺诈者： 1. 信用卡欺诈者 2. 垃圾信息制造者。以下三种特征对识别欺诈攻击类型非常有帮助：1. 邮件地址结构 2. IP地址类型 3. 关联账户密度指示欺诈攻击类型（如变化的回复）。实际上，一个典型的模型有成百上千种特征。

在此例中，拥有以下特征的用户会被训练出的模型识别为信用卡欺诈：

邮箱地址前5个是字母，后3个是数字

使用匿名代理

中等密度关联账号（例如10）

有以下特征的用户会被识别为垃圾信息制造者：

邮箱地址按某种形式随机生成的

使用数据中心的IP地址

高密度关联账号（例如30+）

假设现在你的模型正在从下面一批用户里评估风险，这个模型会计算每个用户的邮件地址结构，IP地址类型以及账号关联密度。正常情况下，模型会将第二种和第三种用户归类为垃圾制造者，把第一、第四、第五种归为信用卡欺诈者。

➜优势

训练学习模型填补并增强了规则引擎无法覆盖的范围，学习模型可以通过增加训练数据持续提高其检测效率。学习模型可以处理非结构数据（如图像，邮件内容），即使有成千上万的输入信息变化特征，也可以自动识别复杂的欺诈模式。

➜局限性

虽然有监督机器学习创建模型功能比较强大，但同时也有局限性。如果出现之前没有标签案例的、新的欺诈类型该怎么办？由于欺诈方式经常变化，这种情况普遍存在。毕竟欺诈者在不停地变化欺诈手段，日以继夜的实施各种新型攻击，如果之前没有遇到这种欺诈攻击模式，也没有足够的训练数据，那么训练出的模型就不能返回优质、可靠的结果。

从下图中可以看出，收集数据和标记数据是创建有监督机器学习过程中最重要的部分。产出准确的训练标签可能需要花费数周到数月的时间。并且产生标签的过程需要反欺诈分析团队全面审核案例，将数据进行正确标签分类，并在投入使用前进行验证测试。除非学习模型之前有足够的相应训练数据，否则一旦出现新的攻击，学出的模型将会无法识别。

无监督机器学习－超越规则引擎和有监督机器学习

以上两种欺诈检测框架都有各自明显的局限性，DataVisor创新的无监督机器学习算法弥补了这两种模型的不足。无监督检测算法无需依赖于任何标签数据来训练模型。这种检测机制算法的核心内容是无监督欺诈行为检测，通过利用关联分析和相似性分析，发现欺诈用户行为间的联系，创建群组，并在一个或多个其他群组中发掘新型欺诈行为和案例。

无监督检测提供了攻击的群组信息，并自动生成训练数据，之后汇入到有监督的机器学习模块中。基于这些数据，有监督机器学习通过模型结构，可以进一步发现大规模攻击群组之外的欺诈用户。DataVisor所采用的这种框架模式不仅可以找出由个人账号发起的攻击，更重要的是可以有效发现由多个账号组成的欺诈或犯罪团伙实施的有组织的大规模攻击，为客户反欺诈检测框架增加至关重要的早期全方位检测。

DataVisor采用的关联分析方法将欺诈行为相似的群组归为一类。而另一种检测技术－异常检测，将不符合好用户行为特点的用户均列为欺诈对象。其原理是假设坏用户都是孤立于正常用户之外的单个用户或小群组。下面图表列举了欺诈者F1、F3、群组F2，以及好用户群组G1和G2。异常检测模型只能发现此类孤立的欺诈行为，但在鉴别大规模的群组欺诈时就会面临很大的挑战。在这一点上，相比于异常检测，无监督分析的优势显而易见。

DataVisor把无监督分析算法结合规则引擎和机器学习模型一起使用。对于客户来说，这种全方位的检测在提供欺诈信息列表的同时，也会提供给客户新的欺诈检测模型，并帮助用户创建新的检测规则。一旦DataVisor的检测方式发现客户遇到新型未知欺诈，无监督检测可以有效提前早期预警。

通过专注于早期检测和发现未知欺诈，DataVisor帮助客户在欺诈解决方案的各个方面提升机制、提高效率：

鉴别虚假用户注册和帐户侵权；

检测虚假金融交易和活动；

发现虚假推广和促销滥用；

阻止社交垃圾信息，虚假内容发布、虚假阅读量和虚假点赞数量；

翻译者：Lily.Wang

Unsupervised Analytics: Moving Beyond Rules Engines and Learning Models

无监督机器学习：超越规则引擎和有监督机器学习的新一代反欺诈分析方法

Rules engines, machine learning models, ID verification, or reputation lookups (e.g. email, IP blacklists and whitelists) and unsupervised analytics? I’ve often been asked which one to use and should you only go with one over the others. There is a place for each to provide value and you should anticipate incorporating some combination of these fraud solutions along with solid domain expertise to build a fraud management system that best accounts for your business, products and users. With that said, rules engines and learning models are two of the major foundational components of a company’s fraud detection architecture. I’ll explain how they work, discuss the benefits and limitations of each and highlight the demand for unsupervised analytics that can go beyond rules engines and machine learning in order to catch new fraud that has yet to be seen.

Rules Engines

Image Source

How they work

Rules engines partition the operational business logic from the application code, enabling non-engineering fraud domain experts (e.g. Trust & Safety or Risk Analysts) with SQL/database knowledge to manage the rules themselves. So what types of rules are effective? Rules can be as straightforward as a few lines of logic: If A and B, then do C. For example,

IF (user_email = type_free_email_service) AND (comment_character_count ≥ 150 per sec) {

flag user_account as spammer

mute comment

}

Rules engines can also employ weighted scoring mechanisms. For example, in the table below each rule has a score value, positive or negative, which can be assigned by an analyst. The points for all of the rules triggered will be added together to compute an aggregate score. Subsequently, rules engines aid in establishing business operation workflows based on the score thresholds. In a typical workflow, there could be three types of actions to take based on the score range:

1. Above 1000 – Deny (e.g. reject a transaction, suspend the account)
2. Below 300 – Accept (e.g. order is ok, approve the content post)
3. Between 300 and 1000 – Flag for additional review and place into a manual review bin

Advantages

Rules engines can take black lists (e.g. IP addresses) and other negative lists derived from consortium databases as input data. An analyst can add a new rule as soon as he or she encounters a new fraud/risk scenario, helping the company benefit from the real-world insights of the analyst on the ground seeing the fraud every day. As a result, rules engines give businesses the control and capability to handle one-off brute force attacks, seasonality and short-term emerging trends.

Limitations

Rules engines have limitations when it comes to scale. Fraudsters don’t sit idle after you catch them. They will change what they do after learning how you caught them to prevent being caught again. Thus, the shelf life of rules can be a couple of weeks or even as short as a few days before their effectiveness begins to diminish. Imagine having to add, remove, and update rules and weights every few days when you’re in a situation with hundreds or thousands of rules to run and test. This could require huge operational resources and costs to maintain.

If a fraud analyst wants to calculate the accept, reject, and review rates for 3 rules and get the changes in those rates for adjusting each rule down or up by 100 points, that would require 8 changes: 23^ = 8 (values^rules). Testing 10 rules with 3 different values would be over 59K changes! As the number of rules increases, the time to make adjustments increases quickly.

Rules engines don’t automatically learn from analyst observations or feedback. As fraudsters adapt their tactics, businesses can be temporarily exposed to new types of fraud attacks. And since rules engines treat information in a binary fashion and may not detect subtle nuances, this can lead to higher instances of false positives and negative customer experiences.

Learning Models

Image Source

How they work

Supervised machine learning is the most widely used learning approach when it comes to fraud detection. A few of the learning techniques include decision trees, random forests, nearest neighbors, Support Vector Machines (SVM) and Naive Bayes. Machine learning models often solve complex computations with hundreds of variables (high-dimensional space) in order to accurately determine cases of fraud.

Having a good understanding of both what is and what is not fraud plays a central role in the process of creating models. The input data to the models influences their effectiveness. The models are trained on known cases of fraud and non-fraud (e.g. labeled training data), which then facilitate its ability to classify new data and cases as either fraudulent or not. Because of their ability to predict the label for a new unlabeled data set, trained learning models fill in the gap and bolster the areas where rules engines may not provide great coverage.

Below is a simplified example of how a supervised machine learning program would classify new data into the categories of non-fraud or fraud. Training data informs the model of the characteristics of two types of fraudsters: 1) credit card fraudsters and 2) spammers. Three features: 1) the email address structure, 2) the IP address type, and 3) the density of linked accounts are indicative of the type of fraud attack (e.g. response variable). Note in reality, there could be hundreds of features for a model.

The trained model recognizes that a user with:

• an email address that has 5 letters followed by 3 numbers
• using an anonymous proxy
• with a medium density (e.g. 10) of connected accounts

is a credit card fraudster.

It also knows recognizes that a user with:

• an email address structure with a “dot” pattern
• using an IP address from a datacenter
• with a high density (e.g. 30+) of linked accounts

is a spammer.

Now suppose your model is evaluating new users from the batch of users below. It computes the email address structure, IP address type, and density of linked accounts for each user. If working properly, it will classify the users in Cases 2 and 3 as spammers and the users in Cases 1, 4 and 5 as credit card fraudsters.

Advantages

Because of their ability to predict the label for a new unlabeled data set, trained learning models fill in the gap and bolster the areas where rules engines may not provide great coverage. Learning models have the ability to digest millions of row of data scalably, pick up from past behaviors and continually improve their predictions based on new and different data. They can handle unstructured data (e.g. images, email text) and recognize sophisticated fraud patterns automatically even if there are thousands of features/variables in the input data set. With learning models, you can also measure effectiveness and improve it by only changing algorithms or algorithm parameters.

Limitations

Trained learning models, while powerful, have their limitations. What happens if there are no labeled examples for a given type of fraud? Given how quickly fraud is evolving, this is not that uncommon of an occurrence. After all, fraudsters change schemes and conduct new types of attacks around the clock. If we have not encountered the fraud attack pattern, and therefore do not have sufficient training data, the trained learning models may not have the appropriate support to return good and reliable results.

As seen in the diagram below, collecting and labeling data is a crucial part of building a learning model and the time required to generate accurate training labels can be weeks to months. Labeling can involve teams of fraud analysts reviewing cases thoroughly, categorizing it with the right fraud tags, and undergoing a verification process before being used as training data. In the event a new type of fraud emerges, a learning model may not be able to detect it until weeks later after sufficient data has been acquired to properly train it.

Unsupervised Analytics – Going Beyond Rules Engines and Learning Models

While both of these approaches are critical pieces of a fraud detection architecture, here at DataVisor we take it one step further. DataVisor employs unsupervised analytics, which do not rely on having prior knowledge of the fraud patterns. In other words no training data is needed. The core component of the algorithm is theunsupervised attack campaign detection which leverages correlation analysis and graph processing to discover the linkages between fraudulent user behaviors, create clusters and assign new examples into one or the other of the clusters.

The unsupervised campaign detection provides the attack campaign group info and also the self-generated training data, both of which can be fed into our machine learning models to bootstrap them. With this data, the supervised machine learning will pick up patterns and find the fraudulent users that don’t fit into these large attack campaign groups. This framework enables DataVisor to uncover fraud attacks perpetrated by individual accounts, as well as organized mass scale attacks coordinated among many users such as fraud and crime rings – adding a valuable piece to your fraud detection architecture with a “full-stack.”

Our correlation analysis groups fraudsters “acting” similarly into the same cluster. In contrast, anomaly detection, another useful technique, finds the set of fraud objects that are considerably dissimilar from the remainder of the good users. It does this is by assuming anomalies do not belong to any group or they belong to small/sparse clusters. See graph below for anomaly detection illustrating fraudsters F1, F3, and group F2and good users G1 and G2. The benefits of unsupervised analytics is on display when comparing it to anomaly detection. While anomaly detection can find outlying fraudsters from a given data set, it would encounter a challenge identifying large fraud groups.

With unsupervised analytics, DataVisor collaborates with rules engines and machine learning models. For customers, the analytics provides them a list of the fraudsters and also gives their fraud analysts insights to create new rules. When DataVisor finds fraud that has not been encountered by a customer previously, the data from the unsupervised campaign detection can serve as early warning signals and/or training data to their learning models, creating new and valuable dimensions to their model’s accuracy.

By focusing on early detection and discovering unknown fraud, DataVisor has helped customers to become better and more efficient in solving fraud in diverse range of areas such as:

• Identifying fake user registration and account takeovers (ATO)
• Detecting fraudulent financial transactions and activity
• Discovering user acquisition and promotion abuse
• Preventing social spam, fake posts, reviews and likes

Stay tuned for future blog posts where I will address topics such as new online fraud attacks, case review management tools, and a closer look into DataVisor’s fraud detection technology stack. If you want to learn more about how DataVisor can help you fight online fraud, please visit https://datavisor.com/ or schedule atrial.

欢迎转载，转载请注明：本文出自Bin的专栏blog.csdn.net/xbinworld。
技术交流QQ群：433250724，欢迎对算法、技术感兴趣的同学加入。

纳什均衡（或者纳什平衡），Nash equilibrium ,又称为非合作博弈均衡，是博弈论的一个重要策略组合，以约翰·纳什命名。

约翰·纳什，生于1928年6月13日。著名经济学家、博弈论创始人、《美丽心灵》男主角原型。前麻省理工学院助教，后任普林斯顿大学数学系教授，主要研究博弈论、微分几何学和偏微分方程。由于他与另外两位数学家（经济学家，约翰·C·海萨尼和莱因哈德·泽尔腾）在非合作博弈的均衡分析理论方面做出了开创性的贡献，对博弈论和经济学产生了重大影响，而获得1994年诺贝尔经济学奖。

纳什的人生非常曲折，一度学术成果不被认可，甚至换上严重的精神分裂症，在爱的力量下在很多年后奇迹般地恢复，并最终获得诺内尔经济学奖。影片《美丽心灵》（A Beautiful Mind）是一部改编自同名传记而获得奥斯卡金像奖的电影，影片以约翰·纳什与他的妻子艾莉西亚（曾离婚，但2001年复婚）以及普林斯顿的朋友、同事的真实感人故事为题材，艺术地重现了这个爱心呵护天才的传奇故事。

年轻时的Nash，很帅噢

纳什均衡定义

经济学定义[3]
所谓纳什均衡，指的是参与人的这样一种策略组合，在该策略组合上，任何参与人单独改变策略都不会得到好处。换句话说，如果在一个策略组合上，当所有其他人都不改变策略时，没有人会改变自己的策略，则该策略组合就是一个纳什均衡。

数学定义
纳什均衡的定义：在博弈G=﹛S1,…,Sn：u1,…，un﹜中，如果由各个博弈方的各一个策略组成的某个策略组合（s1*,…，sn*）中，任一博弈方i的策略si*，都是对其余博弈方策略的组合（s1*,…s*i-1,s*i+1,…，sn*）的最佳对策，也即ui（s1*,…s*i-1,si*,s*i+1,…，sn*）≥ui（s1*,…s*i-1,sij*,s*i+1,…，sn*）对任意sij∈Si都成立，则称（s1*,…，sn*）为G的一个纳什均衡。

注：经济学定义从字面上还是相对比较好理解的；这里稍微解释一下数学定义，博弈论也称Game Theory，一场博弈用G表示，Si表示博弈方i的策略，ui表示收益。因此，纳什均衡的意思是：任何一方采取的策略都是对其余所有方采取策略组合下的最佳对策；当所有其他人都不改变策略时，为了让自己的收益最大，任何一方都不会（或者无法）改变自己的策略，这个时候的策略组合就是一个纳什均衡。

纳什证明了在每个参与者都只有有限种策略选择、并允许混合策略的前提下，纳什均衡一定存在。以两家公司的价格大战为例，纳什均衡意味着两败俱伤的可能：在对方不改变价格的条件下，既不能提价，否则会进一步丧失市场；也不能降价，因为会出现赔本甩卖。于是两家公司可以改变原先的利益格局，通过谈判寻求新的利益评估分摊方案，也就是Nash均衡。类似的推理当然也可以用到选举，群体之间的利益冲突，潜在战争爆发前的僵局，议会中的法案争执等。

纳什均衡案例

以下介绍几个经典的纳什均衡案例[2][4]，因为本文主要是以科普为主，所以案例不会涉及到复杂深奥的经济学问题（事实上，我也不懂，哈~）。

（1）囚徒困境

假设有两个小偷A和B联合犯事、私入民宅被警察抓住。警方将两人分别置于不同的两个房间内进行审讯，对每一个犯罪嫌疑人，警方给出的政策是：如果一个犯罪嫌疑人坦白了罪行，交出了赃物，于是证据确凿，两人都被判有罪。如果另一个犯罪嫌疑人也作了坦白，则两人各被判刑8年；如果另一个犯罪嫌人没有坦白而是抵赖，则以妨碍公务罪（因已有证据表明其有罪）再加刑2年，而坦白者有功被减刑8年，立即释放。如果两人都抵赖，则警方因证据不足不能判两人的偷窃罪，但可以私入民宅的罪名将两人各判入狱1年。

此时产生了两个嫌疑人之间的一场博弈：

表中的数字表示A，B各自的判刑结果。博弈论分析中一般都用这样的表来表示。

该案例，显然最好的策略是双方都抵赖，结果是大家都只被判1年。但是由于两人处于隔离的情况，首先应该是从心理学的角度来看，当事双方都会怀疑对方会出卖自己以求自保、其次才是亚当·斯密的理论，假设每个人都是“理性的经济人”，都会从利己的目的出发进行选择。这两个人都会有这样一个盘算过程：假如他坦白，如果我抵赖，得坐10年监狱，如果我坦白最多才8年；假如他要是抵赖，如果我也抵赖，我就会被判一年，如果我坦白就可以被释放，而他会坐10年牢。综合以上几种情况考虑，不管他坦白与否，对我而言都是坦白了划算。两个人都会动这样的脑筋，最终，两个人都选择了坦白，结果都被判8年刑期。

注：亚当·斯密的理论（“看不见的手”原理），在市场经济中，每一个人都从利己的目的出发，而最终全社会达到利他的效果。但是我们可以从“纳什均衡”中引出“看不见的手”原理的一个悖论：从利己目的出发，结果损人不利己，既不利己也不利他。

（2）智猪博弈

猪圈里有两头猪，一头大猪，一头小猪。猪圈的一边有个踏板，每踩一下踏板，在远离踏板的猪圈的另一边的投食口就会落下少量的食物。如果有一只猪去踩踏板，另一只猪就有机会抢先吃到另一边落下的食物。当小猪踩动踏板时，大猪会在小猪跑到食槽之前刚好吃光所有的食物；若是大猪踩动了踏板，则还有机会在小猪吃完落下的食物之前跑到食槽，争吃到另一半残羹。

那么，两只猪各会采取什么策略？答案是：小猪将选择“搭便车”策略，也就是舒舒服服地等在食槽边；而大猪则为一点残羹不知疲倦地奔忙于踏板和食槽之间。

原因何在？因为，小猪踩踏板将一无所获，不踩踏板反而能吃上食物。对小猪而言，无论大猪是否踩动踏板，不踩踏板总是好的选择。反观大猪，已明知小猪是不会去踩动踏板的，自己亲自去踩踏板总比不踩强吧，所以只好亲力亲为了。

（3）普通范式博弈

GOO公司和SAM公司是某手机产品生态的两大重量级参与者，双方在产业链的不同位置上各司其职且关系暧昧，有时也往往因商业利益和产品影响力的争夺而各怀异心。二者的收益也随着博弈的变化而不断更替。

上图表格模拟了两家公司的博弈现状，双方各有两个可选策略“合作”与“背叛”，格中的四组数据表示四个博弈结局的分数（收益），每组数据的第一个数字表示GOO公司的收益，后一个数字表示SAM公司的收益。

博弈是同时进行的，一方参与者必须站在对方的角度上来思考我方的策略选择，以追求收益最大化。这在博弈论里称作Putting yourselves into other people’s shoes。

现在我们以GOO公司为第一人称视角来思考应对SAM公司的博弈策略。假如SAM公司选择合作，那么我方也选择合作带来的收益是3，而我方选择背叛带来的收益是5，基于理性的收益最大化考虑，我方应该选择背叛，这叫严格优势策略；假如SAM公司选择背叛，那么我方选择合作带来的收益是-3，而选择背叛带来的收益为-1，为使损失降到最低，我方应该选择背叛。最后，GOO公司的分析结果是，无论SAM公司选择合作还是背叛策略，我方都必须选择背叛策略才能获得最大化的收益。

同理，当SAM公司也以严格优势策略来应对GOO公司的策略选择时，我们重复上述分析过程，就能得出结论：无论GOO公司选择合作还是背叛策略，SAM公司都必须选择背叛策略才能获得最大化收益。

最后我们发现，本次博弈的双方都采取了背叛策略，各自的收益都为-1，这是一个比较糟糕的结局，尽管对任何一方来说都不是最糟糕的那种。这种局面就是著名的“囚徒困境”。

但是，博弈的次数往往不止一次，就像COO与SAM公司双方的商业往来也许会有很多机会。当二者经历了多次背叛策略的博弈之后，发现公式上还有一个（3，3）收益的双赢局面，这比（-1，-1）的收益结果显然要好很多，因此二者在之后的博弈过程中必然会尝试互建信任，从而驱使双方都选择合作策略。

这里有一个理想化假设，那就是假设双方都知道博弈次数是无限的话，也就是说双方的商业往来是无止尽的，那么二者的策略都将持续选择合作，最终的博弈收益将定格在（3，3），这就是一个纳什均衡。既然博弈次数是无限的，那么任何一方都没有理由选择背叛策略去冒险追求5点短暂收益，而招致对方在下一轮博弈中的报复（这种报复在博弈论里称作“以牙还牙”策略）。

还有另一种假设情况是，假使双方都知道博弈次数是有限的，也许下一次博弈就是最后一次，那么为了避免对方在最后一轮博弈中选择背叛策略而使我方遭受-3的收益损失，于是双方都重新采取了背叛的策略选择，最后的博弈结果又回到了（-1，-1），这就形成了第二个纳什均衡。

由此可见，随着次数（博弈性质）的变化，纳什均衡点也并非唯一。

（4）饿狮博弈

假设有A、B、C、D、E、F六只狮子（强弱从左到右依次排序）和一只绵羊。假设狮子A吃掉绵羊后就会打盹午睡，这时比A稍弱的狮子B就会趁机吃掉狮子A，接着B也会午睡，然后狮子C就会吃掉狮子B，以此类推。那么问题来了，狮子A敢不敢吃绵羊？

为简化说明，我们先给出此题的解法。该题须采用逆向分析法，也就是从最弱的狮子F开始分析，依次前推。假设狮子E睡着了，狮子F敢不敢吃掉狮子E？答案是肯定的，因为在狮子F的后面已没有其它狮子，所以狮子F可以放心地吃掉午睡中的狮子E。

继续前推，既然狮子E睡着会被狮子F吃掉，那么狮子E必然不敢吃在他前面睡着的狮子D。

再往前推，既然狮子E不敢吃掉狮子D，那么D则可以放心去吃午睡中的狮子C。依次前推，得出C不吃，B吃，A不吃。所以答案是狮子A不敢吃掉绵羊。

推理结果如下图：

但是，如果我们在狮子F的后面增加了一只狮子G，总数变成7只，用逆向分析法按照上题步骤再推一次，很容易得出结论：狮子G吃，狮子F不吃，E吃，D不吃，C吃，B不吃，A吃。这次的答案变成了狮子A敢吃掉绵羊。

对比两次博弈我们发现，狮子A敢不敢吃绵羊取决于狮子总数的奇偶性，总数为奇数时，A敢吃掉绵羊；总数为偶数时，A则不敢吃。因此，总数为奇数和总数为偶数的狮群博弈结果形成了两个稳定的纳什均衡点。

（5）硬币正反

你正在图书馆枯坐，一位陌生美女主动过来和你搭讪，并要求和你一起玩个数学游戏。美女提议：“让我们各自亮出硬币的一面，或正或反。如果我们都是正面，那么我给你3元，如果我们都是反面，我给你1元，剩下的情况你给我2元就可以了。”那么该不该和这位姑娘玩这个游戏呢？

每一种游戏依具其规则的不同会存在两种纳什均衡，一种是纯策略纳什均衡，也就是说玩家都能够采取固定的策略(比如一直出正面或者一直出反面)，使得每人都赚得最多或亏得最少；或者是混合策略纳什均衡，而在这个游戏中，便应该采用混合策略纳什均衡。

假设我们出正面的概率是x，反面的概率是1-x，美女出正面的概率是y，反面的概率是1-y。为了使利益最大化，应该在对手出正面或反面的时候我们的收益都相等，由此列出方程就是

3x + (-2)(1-x)=(-2) * x + 1*( 1-x )——解方程得x=3/8；同样，美女的收益，列方程-3y + 2( 1-y)= 2y+ (-1) * ( 1-y)——解得y也等于3/8。

于是，我们就可以算美女每次的期望收益是： （1-y）(2x-(1-x)) + y(-3x+2(1-x)) = 1/8元，也就是说，双方都采取最优策略的情况下，平均每次美女赢1/8元。

其实只要美女采取了(3/8,5/8)这个方案，不论你再采用什么方案，都是不能改变局面的。如果全部出正面，每次的期望收益是 (3+3+3-2-2-2-2-2)/8=-1/8元；如果全部出反面，每次的期望收益也是(-2-2-2+1+1+1+1+1)/8=-1/8元。而任何策略无非只是上面两种策略的线性组合，所以期望还是-1/8元。但是当你也采用最佳策略时，至少可以保证自己输得最少。否则，你肯定就会被美女采用的策略针对，从而赔掉更多。

纳什均衡分类

最后讲一讲纳什均衡的分类。纳什均衡可以分成两类：“纯战略纳什均衡”和“混合战略纳什均衡”。

要说明纯战略纳什均衡和混合战略纳什均衡，要先说明纯战略和混合战略。所谓纯战略是提供给玩家要如何进行赛局的一个完整的定义。特别地是，纯战略决定在任何一种情况下要做的移动。战略集合是由玩家能够施行的纯战略所组成的集合。而混合战略是对每个纯战略分配一个机率而形成的战略。混合战略允许玩家随机选择一个纯战略。混合战略博弈均衡中要用概率计算，因为每一种策略都是随机的，达到某一概率时，可以实现支付最优。因为机率是连续的，所以即使战略集合是有限的，也会有无限多个混合战略。

当然，严格来说，每个纯战略都是一个“退化”的混合战略，某一特定纯战略的机率为 1，其他的则为 0。
故“纯战略纳什均衡”，即参与之中的所有玩家都玩纯战略；而相应的“混合战略纳什均衡”，之中至少有一位玩家玩混合战略。并不是每个赛局都会有纯战略纳什均衡，例如“钱币问题”就只有混合战略纳什均衡，而没有纯战略纳什均衡。不过，还是有许多赛局有纯战略纳什均衡（如协调赛局，囚徒困境和猎鹿赛局）。甚至，有些赛局能同时有纯战略和混合战略均衡。

http://www.cnblogs.com/wangxiaocvpr/p/5966574.html

【重磅】无监督学习生成式对抗网络突破，OpenAI 5大项目落地

【新智元导读】“生成对抗网络是切片面包发明以来最令人激动的事情！”LeCun前不久在Quroa答问时毫不加掩饰对生成对抗网络的喜爱，他认为这是深度学习近期最值得期待、也最有可能取得突破的领域。生成对抗学习是无监督学习的一种，该理论由 Ian Goodfellow 提出，此人现在 OpenAI 工作。作为业内公认进行前沿基础理论研究的机构，OpenAI 不久前在博客中总结了他们的5大项目成果，结合丰富实例介绍了生成对抗网络，并对OpenAI 五大落地项目进行梳理，包括完善对抗生成网络（GAN）、完善变分推断（VAE）、提出GAN的扩展 InfoGAN，以及提出生成对抗模仿学习及代码。

OpenAI 旨在开发能够让计算机理解世界的算法和技术。

我们常会忽略自己对周遭世界的理解：你知道世界由三维环境构成，物体可以移动、碰撞、相互作用；人能行走、说话、思考；动物会吃草、飞翔、奔跑或者鸣叫；屏幕会显示经过编码的信息，内容涉及天气、篮球赛的结果或者 1970 年的事情。

这些海量信息就在那里，大都触手可及——其存在形式要么是现实世界中的原子，要么是数字世界里的比特。唯一的问题是如何设计模型和算法，分析和理解这些宝贵的数据。

生成模型是实现这一目标最值得期待的方法。训练生成模型，首先要大量收集某种数据（比如成千上万的图像、句子或声音），然后训练一个模型，让这个模型可以生成这样的数据。

其原理是费曼的名言：“做不出来就没有真正明白。”（What I cannot create, I do not understand.）

用于生成模型的神经网络，很多参数都远远小于用于训练的数据的量，因此模型能够发现并有效内化数据的本质，从而可以生成这些数据。

生成式模型有很多短期应用。但从长远角度看，生成模型有望自动学会数据集的类型、维度等特征。

生成图像

举个例子，假设有某个海量图像数据集，比如含有 120 万幅图像的 ImageNet 数据集。如果将每幅图的宽高设为 256，这个数据集就是 1200000*256*256*3（约 200 GB）的像素块。其中的一些样例如下：

这些图像是人类肉眼所见的样子，我们将它们称为“真实数据分布中的样本”。现在我们搭建生成模型，训练该模型生成类似上图的图像，在这里，这个生成模型就是一个输出为图像的大型神经网络，这些输出的图像称为“模型样本”。

DCGAN

Radford 等人提出的 DCGAN 网络（见下图）就是这样一个例子。DCGAN 网络以 100 个从一个高斯分布中采样的随机数作为输入（即代码，或者叫“隐含变量”，靠左红色部分），输出图像（在这里就是 64*64*3 的图像，靠右绿色部分）。当代码增量式变化时，生成的图像也随之变化——说明模型已经学会了如何描述世界，而不是仅仅是记住了一些样本。

网络（黄色部分）由标准的卷积神经网络（CNN）构成：

DCGAN 使用随机权重初始化，所以随机代码输入会生成一个完全随机的图像。但是，这个网络有好几百万的参数可以调整，而我们的目的是设置参数，让根据随机代码输入产生的样本与训练数据看上去相似。换句话说，我们想要模型分布与图像空间中真实数据的分布相匹配。

训练生成模型

假设我们使用最新初始化的网络生成 200 幅图，每次都从不同的随机代码开始。问题是：我们该如何调整网络的参数，让每次输出的新图像都更接近理想？需要注意的是，这里并非监督学习场景，我们也没有对 200 幅输出图像设定明确的预期；我们只是希望这些图像看起来跟真实的一样。

一个巧妙的处理方式是依照生成对抗网络（Generative Adversarial Network，GAN）方法。这里，我们引入另一个判别器网络（discriminator network，通常是一个标准的卷积神经网络），判断输入的图像是真实的还是生成的。我们可以将 200 幅生成的图像和 200 幅真实图像用作训练数据，将这个判别器训练成一个标准的分类器，其功能就是区分这两种不同的图像。

此外，我们还可以经由判别器和生成器反向传播（backpropagate），找出应该如何改变生成器的参数，使其生成的 200 幅样本对判别器而言混淆度更大。这两个网络就形成了一种对抗：判别器试着从伪造图像中区分出真实图像，而生成器则努力产生可以骗过判别器的图像。最后，生成器网络输出的结果就是在判别器看来无法区分的图像。

下图展示了两种从生成模型采样的过程。两种情况下，输入都是有噪声和混乱的，经过一段时间收敛，可以得到较为可信的图像统计：

VAE 学会产生图像（log time）

GAN 学会产生图像（linear time）

这令人兴奋——这些神经网络正在逐渐学会世界看起来是什么样子的！这些模型通常只有 10 亿参数，所以一个在 ImageNet 上训练的网络（粗略地）将 200GB 的像素数据压缩到 100MB 的权重。这让模型得以发现数据最主要的特征：例如，模型很可能学会位置邻近的像素更有可能拥有同样的颜色，或者世界是由水平或竖直的边构成。

最终，模型可能会发现很多更复杂的规律：例如，图像中有特定类型的背景、物体、纹理，它们会以某种可能的排列方式出现，或者在视频中随时间按某种方式变化等等。

更泛化的表现形式

数学上看，我们考虑数据集 x1，…，xn 是从真实数据分布 p(x) 中的一段。下图中，蓝色区域展示了一部分图像空间，这部分空间以高概率（超过某阈值）包含真实图像，而黑色点表示数据点（每个都是数据集中一副图像）。现在，我们的模型同样刻画了一个分布 p^θ(x) (绿色)，将从一个单位 Gaussian 分布 (红色) 获得的点，通过一个（判别器）神经网络映射，得到了生成模型 (黄色)。

我们的网络是参数为 θ 的函数，调整这些参数就能改变生成出的图像分布。目标是找到参数 θ 可以产生一个较好匹配真实数据分布的分布。因此，你可以想象绿色分布从随机开始，然后训练过程迭代式改变参数 θ 拉长和压缩自己使得更匹配蓝色分布。

生成模型三种搭建方法

大多数生成模型有一个基础的设置，只是在细节上有所不同。下面是生成模型的三个常用方法：

• Generative Adversarial Network（GAN）这个我们在上面讨论过了，将训练过程作为两个不同网络的对抗：一个生成器网络和一个判别器网络，判别器网络试图区分样来自于真实分布 p(x) 和模型分布 p^(x) 的样本。每当判别器发现两个分布之间有差异时，生成器网络便微整参数，使判别器不能从中找到差异。

   

• Variational Autoencoders（VAE）让我们可以在概率图模型框架下形式化这个问题，我们会最大化数据的对数似然（log likelihood）的下界

   

• PixelRNN 等自回归模型。训练一个建模了给定前面像素下每个独立像素条件分布的网络（从左到右，从上到下）. 这类似于将图像的像素输入到一个 char-rnn，但是 RNN 水平和垂直遍历图像，而不是 1D 的字符序列

所有这些方法有各自的优缺点。例如，变分自编码器可以执行学习和在复杂的包含隐含变量的概率图模型上进行高效贝叶斯推断（如 DRAW 或者 Attend Infer Repeat 近期相对复杂的模型）。但是，生成的样本会有些模糊不清。GAN 目前生成了清楚的图像，但是因为不稳定的训练动态性很难优化。PixelRNN 有一个非常简单和稳定的训练过程（softmax loss），并且当前给出了最优的对数似然（产生出数据的可信程度）。然而，PixelRNN 在采样时相对低效，而且没有给图像以简单的低维代码。

OpenAI 5 大落地

我们对 OpenAI 做出的生成式模型非常兴奋，刚刚发布了四个对近期工作项目改进工作. 对每个贡献，我们同样发布了技术报告和源代码.

1. 完善对抗生成网络（GAN）

GAN 是非常值得期待的生成模型，不像其他方法，GAN 产生的图像干净、清晰，并且能够学会与纹理有关的代码。然而，GAN 被构建成两个网络之间的对抗，保持平衡十分重要（而且相当考验技巧）：两个网络可能在解析度之间震荡，生成器容易崩溃。

Tim Salimans, Ian Goodfellow, Wojciech Zaremba 等人引入了一些新技巧，让 GAN 训练更加稳定。这些技巧让我们能够放大 GAN ，获得清晰的 128*128 ImageNet 样本：

［左］真实图像（ImageNet）；［右］生成的图像

我们 CIFAR-10 的样本看起来也是非常清晰的——Amazon 为图像打标签的工人（Amazon Mechanical Turk workers）在区分这些图像和真实图像时，错误率为 21.3% （50% 的错误率代表随机猜测）。

［左］真实图像（CIFAR-10）；［右］生成的图像

除了生成更好的图像，我们还引入了一种结合 GAN 和半监督学习的方法。这使我们在不需要大量带标签样本的前提下，在 MNIST、SVHN 和 CIFAR-10 获得当前最佳的结果。在 MNIST，我们对每个类仅有 10 个带标签的样本，使用了一个全连接的神经网络，达到了 99.14% 的准确率——这个结果接近已知最好的监督学习，而后者使用了 6 万个带标签的样本。由于为样本打标签非常麻烦，所以上述方法是很值得期待的。

生成对抗网络是两年多前才提出来的，我们期望在未来出现更多提升其训练稳定性的研究。

2. 完善变分推断（VAE）

在这项工作中，Durk Kingma 和 Tim Salimans 引入了一个灵活、可扩展的计算方法，提升变分推断的准确率。目前，大多数 VAE 训练采用暴力近似后验分布（approximate posterior），每个隐含变量都是独立的。最近的扩展工作虽然解决了这个问题，但由于引入的序列依赖，在计算上仍然称不上高效。

这项工作的主要贡献是“逆自递归流”（Inverse Autoregressive Flow，IAF），这种方法使 rich approximate posterior 能够并行计算，从而高度灵活，可以达到近乎随机的任意性。

我们在下面的图中展示了一些 32*32 的图像样本。前一幅是来自 DRAW 模型的早期样本（初级 VAE 样本看起来更差和模糊）。DRAW 模型一年前才发表的，由此也可以感受到训练生成模型的发展迅速。

［左］用 IAF 训练 VAE 生成的图像；［右］DRAW 模型生成的图像

3. InfoGAN

Peter Chen 等人提出了 InfoGAN ——GAN 的扩展。普通的 GAN 通过在模型里重新生成数据分布，让模型学会图像的disentangled 和 interpretable 表征。但是，其 layout 和 organization 是 underspecified。

InfoGAN 引入了额外的结构，得到了相当出色的结果。在三维人脸图像中，改变代码的一个连续维度，保持其他维度不变，很明显从每张图片给出的 5 行例子中，代码的 resulting dimension 是可解释的，模型在事先不知道摄像头角度、面部变化等特征存在的前提下，可能已经理解这些特征是存在的，并且十分重要：

（a）pose                    （b）Elevation

（c）Lighting             （d）Wide or Narrow

同时，值得一提的是，上述方法是非监督学习的方法。 因此，相比通过监督学习的方法实现了同样结果的思路，这种方法体现出了更高的水平。

3. 生成模型的深度强化学习（两项）

下面是两个强化学习场景下（另一个 OpenAI 聚焦的领域），生成式模型的完善：Curiosity-driven Exploration in Deep Reinforcement Learning via Bayesian Neural Networks。

在高维度连续空间中进行高效的探索是当前强化学习尚未解决的一个难题。没有有效的探索方法，智能体只能到处乱闯直到碰巧遇到奖励。若要对高维行动空间进行探索（比如机器人），这些算法是完全不够的。这篇论文中，Rein Houthooft 等人提出了 VIME，一个使用生成模型对不确定性进行探索的实用方法。

VIME 让智能体本身驱动；它主动地寻求意外的状态-行动。作者展示了 VIME 可以提高一系列策略搜索方法，并在更多稀疏奖励的实际任务（比如智能体需要在无指导的情形下学习原始行动的场景）取得了显著改进。

用 VIME 训练的策略

没有受训的策略

4. 生成对抗模仿学习

Jonathan Ho 等人提出了一个新的模仿学习（imitation learning）方法。Jonathan Ho 在斯坦福大学完成了这项工作的主要内容，他作为暑期实习生加入 OpenAI 后，结合 GAN 以及 RL 等相关工作的启发，最终完成了生成对抗模仿学习及代码。

标准的强化学习场景通常需要设计一个规定智能体预期行为的奖励函数。但实际情况是，有样做有时候会为了实现细节上的正确，而引入代价过高的试错过程。相较而言，模仿学习中，智能体从样本展示中学习，就免去了对奖励函数的依赖。

常用模仿方法包含两个阶段的流程：首先学习奖励函数，然后依照奖励函数执行深度强化学习。这样的过程非常缓慢，也由于这种间接性方法，很难保证结果策略的质量。这项工作展示了如何通过 GAN 直接从数据中抽取策略。这个方法在 OpenAI Gym 环境中可以根据专家表现进行策略学习。

展望未来

生成模型是快速发展的研究领域。在完善这些模型，扩展训练和数据集的同时，我们完全可以认为最终将会产生能够以假乱真的图像或视频样本。这可以用很多应用， 图像降噪（image denoising）、inpainting、高清分辨率（super-resolution）、结构化预测（structured prediction）、强化学习探索（exploration in reinforcement learning），以及神经网络预处理这些为数据打标签的很复杂、造价很高的领域，有很多潜力。

这项工作更深的启示是，在训练生成模型的过程中，我们最终会增进计算机对世界及其构成的理解。

http://www.jianshu.com/p/e112012a4b2d

cs224d-Day 6: 快速入门 Tensorflow

本文是学习这个视频课程系列的笔记，课程链接是 youtube 上的，
讲的很好，浅显易懂，入门首选， 而且在github有代码，
想看视频的也可以去他的优酷里的频道找。

Tensorflow 官网

神经网络是一种数学模型，是存在于计算机的神经系统，由大量的神经元相连接并进行计算，在外界信息的基础上，改变内部的结构，常用来对输入和输出间复杂的关系进行建模。

神经网络由大量的节点和之间的联系构成，负责传递信息和加工信息，神经元也可以通过训练而被强化。

这个图就是一个神经网络系统，它由很多层构成。输入层就是负责接收信息，比如说一只猫的图片。输出层就是计算机对这个输入信息的认知，它是不是猫。隐藏层就是对输入信息的加工处理。

神经网络是如何被训练的，首先它需要很多数据。比如他要判断一张图片是不是猫。就要输入上千万张的带有标签的猫猫狗狗的图片，然后再训练上千万次。

神经网络训练的结果有对的也有错的，如果是错误的结果，将被当做非常宝贵的经验，那么是如何从经验中学习的呢？就是对比正确答案和错误答案之间的区别，然后把这个区别反向的传递回去，对每个相应的神经元进行一点点的改变。那么下一次在训练的时候就可以用已经改进一点点的神经元去得到稍微准确一点的结果。

神经网络是如何训练的呢？每个神经元都有属于它的激活函数，用这些函数给计算机一个刺激行为。

在第一次给计算机看猫的图片的时候，只有部分的神经元被激活，被激活的神经元所传递的信息是对输出结果最有价值的信息。如果输出的结果被判定为是狗，也就是说是错误的了，那么就会修改神经元，一些容易被激活的神经元会变得迟钝，另外一些神经元会变得敏感。这样一次次的训练下去，所有神经元的参数都在被改变，它们变得对真正重要的信息更为敏感。

Tensorflow 是谷歌开发的深度学习系统，用它可以很快速地入门神经网络。

它可以做分类，也可以做拟合问题，就是要把这个模式给模拟出来。

这是一个基本的神经网络的结构，有输入层，隐藏层，和输出层。
每一层点开都有它相应的内容，函数和功能。

那我们要做的就是要建立一个这样的结构，然后把数据喂进去。
把数据放进去后它就可以自己运行，TensorFlow 翻译过来就是向量在里面飞。

这个动图的解释就是，在输入层输入数据，然后数据飞到隐藏层飞到输出层，用梯度下降处理，梯度下降会对几个参数进行更新和完善，更新后的参数再次跑到隐藏层去学习，这样一直循环直到结果收敛。

tensors_flowing.gif

今天一口气把整个系列都学完了，先来一段完整的代码，然后解释重要的知识点！

1. 搭建神经网络基本流程

定义添加神经层的函数

1.训练的数据
2.定义节点准备接收数据
3.定义神经层：隐藏层和预测层
4.定义 loss 表达式
5.选择 optimizer 使 loss 达到最小

然后对所有变量进行初始化，通过 sess.run optimizer，迭代 1000 次进行学习：

import tensorflow as tf
import numpy as np

# 添加层
def add_layer(inputs, in_size, out_size, activation_function=None):
    # add one more layer and return the output of this layer
    Weights = tf.Variable(tf.random_normal([in_size, out_size]))
    biases = tf.Variable(tf.zeros([1, out_size]) + 0.1)
    Wx_plus_b = tf.matmul(inputs, Weights) + biases
    if activation_function is None:
        outputs = Wx_plus_b
    else:
        outputs = activation_function(Wx_plus_b)
    return outputs

# 1.训练的数据
# Make up some real data 
x_data = np.linspace(-1,1,300)[:, np.newaxis]
noise = np.random.normal(0, 0.05, x_data.shape)
y_data = np.square(x_data) - 0.5 + noise

# 2.定义节点准备接收数据
# define placeholder for inputs to network  
xs = tf.placeholder(tf.float32, [None, 1])
ys = tf.placeholder(tf.float32, [None, 1])

# 3.定义神经层：隐藏层和预测层
# add hidden layer 输入值是 xs，在隐藏层有 10 个神经元   
l1 = add_layer(xs, 1, 10, activation_function=tf.nn.relu)
# add output layer 输入值是隐藏层 l1，在预测层输出 1 个结果
prediction = add_layer(l1, 10, 1, activation_function=None)

# 4.定义 loss 表达式
# the error between prediciton and real data    
loss = tf.reduce_mean(tf.reduce_sum(tf.square(ys - prediction),
                     reduction_indices=[1]))

# 5.选择 optimizer 使 loss 达到最小                   
# 这一行定义了用什么方式去减少 loss，学习率是 0.1       
train_step = tf.train.GradientDescentOptimizer(0.1).minimize(loss)


# important step 对所有变量进行初始化
init = tf.initialize_all_variables()
sess = tf.Session()
# 上面定义的都没有运算，直到 sess.run 才会开始运算
sess.run(init)

# 迭代 1000 次学习，sess.run optimizer
for i in range(1000):
    # training train_step 和 loss 都是由 placeholder 定义的运算，所以这里要用 feed 传入参数
    sess.run(train_step, feed_dict={xs: x_data, ys: y_data})
    if i % 50 == 0:
        # to see the step improvement
        print(sess.run(loss, feed_dict={xs: x_data, ys: y_data}))

2. 主要步骤的解释：

• 之前写过一篇文章 TensorFlow 入门 讲了 tensorflow 的安装，这里使用时直接导入：

import tensorflow as tf
import numpy as np

• 导入或者随机定义训练的数据 x 和 y：

x_data = np.random.rand(100).astype(np.float32)
y_data = x_data*0.1 + 0.3

• 先定义出参数 Weights，biases，拟合公式 y，误差公式 loss：

Weights = tf.Variable(tf.random_uniform([1], -1.0, 1.0))
biases = tf.Variable(tf.zeros([1]))
y = Weights*x_data + biases
loss = tf.reduce_mean(tf.square(y-y_data))

• 选择 Gradient Descent 这个最基本的 Optimizer：

optimizer = tf.train.GradientDescentOptimizer(0.5)

• 神经网络的 key idea，就是让 loss 达到最小：

train = optimizer.minimize(loss)

• 前面是定义，在运行模型前先要初始化所有变量：

init = tf.initialize_all_variables()

• 接下来把结构激活，sesseion像一个指针指向要处理的地方：

sess = tf.Session()

• init 就被激活了，不要忘记激活：

sess.run(init)

• 训练201步：

for step in range(201):

• 要训练 train，也就是 optimizer：

sess.run(train)

• 每 20 步打印一下结果，sess.run 指向 Weights，biases 并被输出：

if step % 20 == 0:
print(step, sess.run(Weights), sess.run(biases))

所以关键的就是 y，loss，optimizer 是如何定义的。

3. TensorFlow 基本概念及代码：

在 TensorFlow 入门 也提到了几个基本概念，这里是几个常见的用法。

• Session

矩阵乘法：tf.matmul

product = tf.matmul(matrix1, matrix2) # matrix multiply np.dot(m1, m2)

定义 Session，它是个对象，注意大写：

sess = tf.Session()

result 要去 sess.run 那里取结果：

result = sess.run(product)

• Variable

用 tf.Variable 定义变量，与python不同的是，必须先定义它是一个变量，它才是一个变量，初始值为0，还可以给它一个名字 counter：

state = tf.Variable(0, name='counter')

将 new_value 加载到 state 上，counter就被更新：

update = tf.assign(state, new_value)

如果有变量就一定要做初始化：

init = tf.initialize_all_variables() # must have if define variable

• placeholder：

要给节点输入数据时用 placeholder，在 TensorFlow 中用placeholder 来描述等待输入的节点，只需要指定类型即可，然后在执行节点的时候用一个字典来“喂”这些节点。相当于先把变量 hold 住，然后每次从外部传入data，注意 placeholder 和 feed_dict 是绑定用的。

这里简单提一下 feed 机制， 给 feed 提供数据，作为 run()
调用的参数， feed 只在调用它的方法内有效, 方法结束, feed 就会消失。

import tensorflow as tf

input1 = tf.placeholder(tf.float32)
input2 = tf.placeholder(tf.float32)
ouput = tf.mul(input1, input2)

with tf.Session() as sess:
  print(sess.run(ouput, feed_dict={input1: [7.], input2: [2.]}))

4. 神经网络基本概念

• 激励函数：

例如一个神经元对猫的眼睛敏感，那当它看到猫的眼睛的时候，就被激励了，相应的参数就会被调优，它的贡献就会越大。

下面是几种常见的激活函数：
x轴表示传递过来的值，y轴表示它传递出去的值：

激励函数在预测层，判断哪些值要被送到预测结果那里：

TensorFlow 常用的 activation function

• 添加神经层：

输入参数有 inputs, in_size, out_size, 和 activation_function

import tensorflow as tf

def add_layer(inputs, in_size, out_size,  activation_function=None):

  Weights = tf.Variable(tf.random_normal([in_size, out_size]))
  biases = tf.Variable(tf.zeros([1, out_size]) + 0.1)
  Wx_plus_b = tf.matmul(inputs, Weights) + biases

  if activation_function is None:
    outputs = Wx_plus_b
  else:
    outputs = activation_function(Wx_plus_b)

return outputs

• 分类问题的 loss 函数 cross_entropy ：

# the error between prediction and real data
# loss 函数用 cross entropy
cross_entropy = tf.reduce_mean(-tf.reduce_sum(ys * tf.log(prediction),
                                              reduction_indices=[1]))       # loss
train_step = tf.train.GradientDescentOptimizer(0.5).minimize(cross_entropy)

• overfitting：

下面第三个图就是 overfitting，就是过度准确地拟合了历史数据，而对新数据预测时就会有很大误差：

Tensorflow 有一个很好的工具, 叫做dropout, 只需要给予它一个不被 drop 掉的百分比，就能很好地降低 overfitting。

dropout 是指在深度学习网络的训练过程中，按照一定的概率将一部分神经网络单元暂时从网络中丢弃，相当于从原始的网络中找到一个更瘦的网络，这篇博客中讲的非常详细

代码实现就是在 add layer 函数里加上 dropout, keep_prob 就是保持多少不被 drop，在迭代时在 sess.run 中被 feed:

def add_layer(inputs, in_size, out_size, layer_name, activation_function=None, ):
    # add one more layer and return the output of this layer
    Weights = tf.Variable(tf.random_normal([in_size, out_size]))
    biases = tf.Variable(tf.zeros([1, out_size]) + 0.1, )
    Wx_plus_b = tf.matmul(inputs, Weights) + biases

    # here to dropout
    # 在 Wx_plus_b 上drop掉一定比例
    # keep_prob 保持多少不被drop，在迭代时在 sess.run 中 feed
    Wx_plus_b = tf.nn.dropout(Wx_plus_b, keep_prob)

    if activation_function is None:
        outputs = Wx_plus_b
    else:
        outputs = activation_function(Wx_plus_b, )
    tf.histogram_summary(layer_name + '/outputs', outputs)  
    return outputs

5. 可视化 Tensorboard

Tensorflow 自带 tensorboard ，可以自动显示我们所建造的神经网络流程图：

就是用 with tf.name_scope 定义各个框架，注意看代码注释中的区别：

import tensorflow as tf


def add_layer(inputs, in_size, out_size, activation_function=None):
    # add one more layer and return the output of this layer
    # 区别：大框架，定义层 layer，里面有 小部件
    with tf.name_scope('layer'):
        # 区别：小部件
        with tf.name_scope('weights'):
            Weights = tf.Variable(tf.random_normal([in_size, out_size]), name='W')
        with tf.name_scope('biases'):
            biases = tf.Variable(tf.zeros([1, out_size]) + 0.1, name='b')
        with tf.name_scope('Wx_plus_b'):
            Wx_plus_b = tf.add(tf.matmul(inputs, Weights), biases)
        if activation_function is None:
            outputs = Wx_plus_b
        else:
            outputs = activation_function(Wx_plus_b, )
        return outputs


# define placeholder for inputs to network
# 区别：大框架，里面有 inputs x，y
with tf.name_scope('inputs'):
    xs = tf.placeholder(tf.float32, [None, 1], name='x_input')
    ys = tf.placeholder(tf.float32, [None, 1], name='y_input')

# add hidden layer
l1 = add_layer(xs, 1, 10, activation_function=tf.nn.relu)
# add output layer
prediction = add_layer(l1, 10, 1, activation_function=None)

# the error between prediciton and real data
# 区别：定义框架 loss
with tf.name_scope('loss'):
    loss = tf.reduce_mean(tf.reduce_sum(tf.square(ys - prediction),
                                        reduction_indices=[1]))

# 区别：定义框架 train
with tf.name_scope('train'):
    train_step = tf.train.GradientDescentOptimizer(0.1).minimize(loss)

sess = tf.Session()

# 区别：sess.graph 把所有框架加载到一个文件中放到文件夹"logs/"里 
# 接着打开terminal，进入你存放的文件夹地址上一层，运行命令 tensorboard --logdir='logs/'
# 会返回一个地址，然后用浏览器打开这个地址，在 graph 标签栏下打开
writer = tf.train.SummaryWriter("logs/", sess.graph)
# important step
sess.run(tf.initialize_all_variables())

运行完上面代码后，打开 terminal，进入你存放的文件夹地址上一层，运行命令 tensorboard –logdir=’logs/’ 后会返回一个地址，然后用浏览器打开这个地址，点击 graph 标签栏下就可以看到流程图了：

6. 保存和加载

训练好了一个神经网络后，可以保存起来下次使用时再次加载：

import tensorflow as tf
import numpy as np

## Save to file
# remember to define the same dtype and shape when restore
W = tf.Variable([[1,2,3],[3,4,5]], dtype=tf.float32, name='weights')
b = tf.Variable([[1,2,3]], dtype=tf.float32, name='biases')

init= tf.initialize_all_variables()

saver = tf.train.Saver()

# 用 saver 将所有的 variable 保存到定义的路径
with tf.Session() as sess:
   sess.run(init)
   save_path = saver.save(sess, "my_net/save_net.ckpt")
   print("Save to path: ", save_path)


################################################

# restore variables
# redefine the same shape and same type for your variables
W = tf.Variable(np.arange(6).reshape((2, 3)), dtype=tf.float32, name="weights")
b = tf.Variable(np.arange(3).reshape((1, 3)), dtype=tf.float32, name="biases")

# not need init step

saver = tf.train.Saver()
# 用 saver 从路径中将 save_net.ckpt 保存的 W 和 b restore 进来
with tf.Session() as sess:
    saver.restore(sess, "my_net/save_net.ckpt")
    print("weights:", sess.run(W))
    print("biases:", sess.run(b))

tensorflow 现在只能保存 variables，还不能保存整个神经网络的框架，所以再使用的时候，需要重新定义框架，然后把 variables 放进去学习。

http://www.jianshu.com/p/6766fbcd43b9

CS224d－Day 2:

在 Day 1 里，先了解了一下 NLP 和 DP 的主要概念，对它们有了一个大体的印象，用向量去表示研究对象，用神经网络去学习，用 TensorFlow 去训练模型，基本的模型和算法包括 word2vec，softmax，RNN，LSTM，GRU，CNN，大型数据的 seq2seq，还有未来比较火热的研究方向 DMN，还有模型的调优。

今天先不直接进入理论学习，而是先学习一下 TensorFlow，在原课程里，这部分在第7讲，但是我觉得最高效地学习算法的方式，就是一边学理论，一边写代码，实践中才能理解更深刻。

Day 2 先认识 TensorFlow，了解一下基本用法，下一次就写代码来训练模型算法，以问题为导向，以项目为驱动。

本文结构：

• 1. TensorFlow 是什么
• 2. 为什么需要 TensorFlow
• 3. TensorFlow 的优点
• 4. TensorFlow 的工作原理
• 5. 安装
• 6. TensorFlow 基本用法
  • 要点
  • 例子
  • 概念
    • 图
    • 张量
    • 会话

1. TensorFlow 是什么

是一个深度学习库，由 Google 开源，可以对定义在 Tensor(张量)上的函数自动求导。

Tensor(张量)意味着 N 维数组，Flow(流)意味着基于数据流图的计算，TensorFlow即为张量从图的一端流动到另一端。

它的一大亮点是支持异构设备分布式计算，它能够在各个平台上自动运行模型，从电话、单个CPU / GPU到成百上千GPU卡组成的分布式系统。

支持CNN、RNN和LSTM算法，是目前在 Image，NLP 最流行的深度神经网络模型。

2. 为什么需要 TensorFlow 等库

深度学习通常意味着建立具有很多层的大规模的神经网络。

除了输入X，函数还使用一系列参数，其中包括标量值、向量以及最昂贵的矩阵和高阶张量。

在训练网络之前，需要定义一个代价函数，常见的代价函数包括回归问题的方差以及分类时候的交叉熵。

训练时，需要连续的将多批新输入投入网络，对所有的参数求导后，代入代价函数，从而更新整个网络模型。

这个过程中有两个主要的问题：1. 较大的数字或者张量在一起相乘百万次的处理，使得整个模型代价非常大。2. 手动求导耗时非常久。

所以 TensorFlow 的对函数自动求导以及分布式计算，可以帮我们节省很多时间来训练模型。

3. TensorFlow 的优点

第一，基于Python，写的很快并且具有可读性。

第二，在多GPU系统上的运行更为顺畅。

第三，代码编译效率较高。

第四，社区发展的非常迅速并且活跃。

第五，能够生成显示网络拓扑结构和性能的可视化图。

4. TensorFlow 的工作原理

TensorFlow是用数据流图(data flow graphs)技术来进行数值计算的。

数据流图是描述有向图中的数值计算过程。

有向图中，节点通常代表数学运算，边表示节点之间的某种联系，它负责传输多维数据(Tensors)。

节点可以被分配到多个计算设备上，可以异步和并行地执行操作。因为是有向图，所以只有等到之前的入度节点们的计算状态完成后，当前节点才能执行操作。

5. 安装

极客学院有官方文档翻译版，讲的很清楚，有各种安装方式的讲解。

我选择基于 Anaconda 的安装，因为这个很方便。

Anaconda 是一个集成许多第三方科学计算库的 Python 科学计算环境，用 conda 作为自己的包管理工具，同时具有自己的计算环境，类似 Virtualenv。

• 安装 Anaconda
  我之前已经安装过 Anaconda 了，直接从下面进行：
• 建立一个 conda 计算环境

# 计算环境名字叫 tensorflow:
# Python 2.7
$ conda create -n tensorflow python=2.7

• 激活环境，使用 conda 安装 TensorFlow

$ source activate tensorflow
(tensorflow)$  # Your prompt should change

# Mac OS X, CPU only:
(tensorflow)$ pip install --ignore-installed --upgrade https://storage.googleapis.com/tensorflow/mac/tensorflow-0.8.0rc0-py2-none-any.whl

• 安装成功后，每次使用 TensorFlow 的时候需要激活 conda 环境
• conda 环境激活后，你可以测试是否成功，在终端进入 python，输入下面代码，没有提示错误，说明安装 TensorFlow 成功：

$ python
...
>>> import tensorflow as tf
>>> hello = tf.constant('Hello, TensorFlow!')
>>> sess = tf.Session()
>>> print(sess.run(hello))
Hello, TensorFlow!
>>> a = tf.constant(10)
>>> b = tf.constant(32)
>>> print(sess.run(a + b))
42
>>>

• 当你不用 TensorFlow 的时候，关闭环境:

(tensorflow)$ source deactivate

$  # Your prompt should change back

• 再次使用的时候再激活:

$ source activate tensorflow
(tensorflow)$  # Run Python programs that use TensorFlow.
...

(tensorflow)$ source deactivate

在 Jupyter notebook 里用 TensorFlow
我在 (tensorflow)$ 直接输入 jupyter notebook 后，输入 import tensorflow as tf 是有错误的，可以参考这里。

6. TensorFlow 基本用法

接下来按照官方文档中的具体代码，来看一下基本用法。

你需要理解在TensorFlow中，是如何：

• 将计算流程表示成图；
• 通过Sessions来执行图计算；
• 将数据表示为tensors；
• 使用Variables来保持状态信息；
• 分别使用feeds和fetches来填充数据和抓取任意的操作结果；

先看个栗子：
例1，生成三维数据，然后用一个平面拟合它：

# (tensorflow)$ python   用 Python API 写 TensorFlow 示例代码

import tensorflow as tf
import numpy as np

# 用 NumPy 随机生成 100 个数据
x_data = np.float32(np.random.rand(2, 100)) 
y_data = np.dot([0.100, 0.200], x_data) + 0.300

# 构造一个线性模型
b = tf.Variable(tf.zeros([1]))
W = tf.Variable(tf.random_uniform([1, 2], -1.0, 1.0))
y = tf.matmul(W, x_data) + b

# 最小化方差
loss = tf.reduce_mean(tf.square(y - y_data))
optimizer = tf.train.GradientDescentOptimizer(0.5)
train = optimizer.minimize(loss)

# 初始化变量
init = tf.initialize_all_variables()

# 启动图 (graph)
sess = tf.Session()
sess.run(init)

# 拟合平面
for step in xrange(0, 201):
    sess.run(train)
    if step % 20 == 0:
        print step, sess.run(W), sess.run(b)

# 输出结果为：
0 [[-0.14751725  0.75113136]] [ 0.2857058]
20 [[ 0.06342752  0.32736415]] [ 0.24482927]
40 [[ 0.10146417  0.23744738]] [ 0.27712563]
60 [[ 0.10354312  0.21220125]] [ 0.290878]
80 [[ 0.10193551  0.20427427]] [ 0.2964265]
100 [[ 0.10085492  0.201565  ]] [ 0.298612]
120 [[ 0.10035028  0.20058727]] [ 0.29946309]
140 [[ 0.10013894  0.20022322]] [ 0.29979277]
160 [[ 0.1000543   0.20008542]] [ 0.29992008]
180 [[ 0.10002106  0.20003279]] [ 0.29996923]
200 [[ 0.10000814  0.20001261]] [ 0.29998815]

注意这几条代码：

W = tf.Variable(tf.random_uniform([1, 2], -1.0, 1.0))

y = tf.matmul(W, x_data) + b

init = tf.initialize_all_variables()

sess = tf.Session()
sess.run(init)

sess.run(train) 
print step, sess.run(W), sess.run(b)

接下来看具体概念：

• TensorFlow 用图来表示计算任务，图中的节点被称之为operation，缩写成op。
• 一个节点获得 0 个或者多个张量 tensor，执行计算，产生0个或多个张量。
• 图必须在会话(Session)里被启动，会话(Session)将图的op分发到CPU或GPU之类的设备上，同时提供执行op的方法，这些方法执行后，将产生的张量(tensor)返回。

1. 构建图
例2，计算矩阵相乘：

import tensorflow as tf

# 创建一个 常量 op, 返回值 'matrix1' 代表这个 1x2 矩阵.
matrix1 = tf.constant([[3., 3.]])

# 创建另外一个 常量 op, 返回值 'matrix2' 代表这个 2x1 矩阵.
matrix2 = tf.constant([[2.],[2.]])

# 创建一个矩阵乘法 matmul op , 把 'matrix1' 和 'matrix2' 作为输入.
# 返回值 'product' 代表矩阵乘法的结果.
product = tf.matmul(matrix1, matrix2)

默认图有三个节点, 两个 constant() op, 和一个 matmul() op. 为了真正进行矩阵相乘运算, 并得到矩阵乘法的结果, 你必须在会话里启动这个图.

2. 张量 Tensor
从向量空间到实数域的多重线性映射(multilinear maps)（v是向量空间，v*是对偶空间）
例如代码中的 [[3., 3.]]，Tensor 可以看作是一个 n 维的数组或列表。在 TensorFlow 中用 tensor 数据结构来代表所有的数据, 计算图中, 操作间传递的数据都是 tensor。

3. 在一个会话中启动图
创建一个 Session 对象, 如果无任何创建参数, 会话构造器将启动默认图。
会话负责传递 op 所需的全部输入，op 通常是并发执行的。

# 启动默认图.
sess = tf.Session()

# 调用 sess 的 'run()' 方法, 传入 'product' 作为该方法的参数，
# 触发了图中三个 op (两个常量 op 和一个矩阵乘法 op)，
# 向方法表明, 我们希望取回矩阵乘法 op 的输出.
result = sess.run(product)

# 返回值 'result' 是一个 numpy `ndarray` 对象.
print result
# ==> [[ 12.]]

# 任务完成, 需要关闭会话以释放资源。
sess.close()

交互式使用
在 Python API 中，使用一个会话 Session 来 启动图, 并调用 Session.run() 方法执行操作.

为了便于在 IPython 等交互环境使用 TensorFlow，需要用 InteractiveSession 代替 Session 类, 使用 Tensor.eval() 和 Operation.run() 方法代替 Session.run()。

例3，计算 ‘x’ 减去 ‘a’：

# 进入一个交互式 TensorFlow 会话.
import tensorflow as tf
sess = tf.InteractiveSession()

x = tf.Variable([1.0, 2.0])
a = tf.constant([3.0, 3.0])

# 使用初始化器 initializer op 的 run() 方法初始化 'x' 
x.initializer.run()

# 增加一个减法 sub op, 从 'x' 减去 'a'. 运行减法 op, 输出结果 
sub = tf.sub(x, a)
print sub.eval()
# ==> [-2. -1.]

变量 Variable

上面用到的张量是常值张量(constant)。

变量 Variable，是维护图执行过程中的状态信息的. 需要它来保持和更新参数值，是需要动态调整的。

下面代码中有 tf.initialize_all_variables，是预先对变量初始化，
Tensorflow 的变量必须先初始化，然后才有值！而常值张量是不需要的。

下面的 assign() 操作和 add() 操作，在调用 run() 之前, 它并不会真正执行赋值和加和操作。

例4，使用变量实现一个简单的计数器：

# －创建一个变量, 初始化为标量 0.  初始化定义初值
state = tf.Variable(0, name="counter")

# 创建一个 op, 其作用是使 state 增加 1
one = tf.constant(1)
new_value = tf.add(state, one)
update = tf.assign(state, new_value)

# 启动图后, 变量必须先经过`初始化` (init) op 初始化,
# 才真正通过Tensorflow的initialize_all_variables对这些变量赋初值
init_op = tf.initialize_all_variables()

# 启动默认图, 运行 op
with tf.Session() as sess:

  # 运行 'init' op
  sess.run(init_op)

  # 打印 'state' 的初始值
  # 取回操作的输出内容, 可以在使用 Session 对象的 run() 调用 执行图时, 
  # 传入一些 tensor, 这些 tensor 会帮助你取回结果. 
  # 此处只取回了单个节点 state，
  # 也可以在运行一次 op 时一起取回多个 tensor: 
  # result = sess.run([mul, intermed])
  print sess.run(state)

  # 运行 op, 更新 'state', 并打印 'state'
  for _ in range(3):
    sess.run(update)
    print sess.run(state)

# 输出:

# 0
# 1
# 2
# 3

上面的代码定义了一个如下的计算图：

Ok，总结一下，来一个清晰的代码：
过程就是：建图->启动图->运行取值

计算矩阵相乘：

import tensorflow as tf

# 建图
matrix1 = tf.constant([[3., 3.]])
matrix2 = tf.constant([[2.],[2.]])

product = tf.matmul(matrix1, matrix2)

# 启动图
sess = tf.Session()

# 取值
result = sess.run(product)
print result

sess.close()

上面的几个代码介绍了基本用法，通过观察，有没有觉得 tf 和 numpy 有点像呢。

TensorFlow和普通的Numpy的对比
在cs224d的课件中有下面这个代码，来看一下二者之间的区别：

eval()

在 Python 中定义完 a 后，直接打印就可以看到 a。

In [37]: a = np.zeros((2,2))

In [39]: print(a)
[[ 0.  0.]
 [ 0.  0.]]

但是在 Tensorflow 中需要显式地输出(evaluation，也就是说借助eval()函数)！

In [38]: ta = tf.zeros((2,2))

In [40]: print(ta)
Tensor("zeros_1:0", shape=(2, 2), dtype=float32)

In [41]: print(ta.eval())
[[ 0.  0.]
[ 0. 0.]]

通过几个例子了解了基本的用法，feed 在上面的例子中还没有写到，下一次就能用到了，其他的可以查询这里。

Day 1 宏观了解了 NLP，Day 2 搞定了工具，下次要直接先进入实战，训练模型，先从 Logistic 和 NN 开始，一边看模型一边写代码一边思考模型原理，这样理解才会更深刻！

循环神经网络（Recurrent Neural Networks）是目前非常流行的神经网络模型，在自然语言处理的很多任务中已经展示出卓越的效果。但是在介绍 RNN 的诸多文章中，通常都是介绍 RNN 的使用方法和实战效果，很少有文章会介绍关于该神经网络的训练过程。

循环神经网络是一个在时间上传递的神经网络，网络的深度就是时间的长度。该神经网络是专门用来处理时间序列问题的，能够提取时间序列的信息。如果是前向神经网络，每一层的神经元信号只能够向下一层传播，样本的处理在时刻上是独立的。对于循环神经网络而言，神经元在这个时刻的输出可以直接影响下一个时间点的输入，因此该神经网络能够处理时间序列方面的问题。

本文将会从数学的角度展开关于循环神经网络的使用方法和训练过程，在本文中，会假定读者已经掌握数学分析中的导数，偏导数，链式法则，梯度下降法等基础内容。本文将会使用传统的后向传播算法（Back Propagation）来训练 RNN 模型。

微信公众号文章：循环神经网络

This slideshow requires JavaScript.

回归方法是为了对连续型的数据做出预测，其中最简单的回归方法当然就是线性回归。顾名思义，线性回归就是使用线性方程来对已知的数据集合进行拟合，达到预测未来的目的。线性回归的优点就是结果十分容易理解，计算公式简单；缺点则是对非线性的数据拟合程度不够好。例如，用一个线性函数 去拟合二次函数 ，结果总是不尽人意。为了解决这类问题，有人提出了局部加权线性回归（locally weighted linear regression），岭回归（ridge regression），LASSO 和 前向逐步线性回归（forward stagewise linear regression）。本文中将会一一介绍这些回归算法。

（一）线性回归（Linear Regression）

假设矩阵 X 的每一行表示一个样本，每一列表示相应的特征，列向量 Y 表示矩阵 X 所对应的取值，那么我们需要找到一个列向量 使得 。当然，这样的 在现实的数据集中几乎不可能存在。不过，我们可以寻找一个  使得列向量 的 Eulidean 范数足够小。换言之，我们需要找到一个向量 使得

的取值足够小，其中 m 是矩阵 X 的行数， 表示矩阵 X 的第 i 个行向量。通过数学计算可以得到：

对 求导之后得到：，求解 之后得到 。因此，对于矩阵 和列向量 而言，最佳的线性回归系数是

举例说明：蓝色的是数据集，使用线性回归计算的话会得到一条直线。

（二）局部加权线性回归（Locally Weighted Linear Regression）

线性回归的一个问题就是会出现欠拟合的情况，因为线性方程确实很难精确地描述现实生活的大量数据集。因此有人提出了局部加权线性回归（Locally Weighted Linear Regression），在该算法中，给每一个点都赋予一定的权重，也就是

其中 表示以 为对角线的对角矩阵，其中 m 是矩阵 X 的行数， 表示矩阵 X 的第 i 个行向量。通过计算可以得到：

对 求导之后得到：

令导数等于零之后得到：。因此，如果使用局部加权线性回归的话，最佳的系数就是

局部加权线性回归需要确定权重矩阵 W 的值，那么就需要定义对角线的取值，通常情况下我们会使用高斯核。

其中 k 是参数。从高斯核的定义可以看出，如果 与 隔得很近，那么 就会较大；如果隔得较远，那么 就会趋向于零。意思就是说：在局部形成了线性回归的算法，在整体并不一定是线性回归。在局部线性回归中， 就是唯一的参数值。

如果选择了合适的 ，可以得到一条看上去还不错的曲线；如果选择了不合适的 ，就有可能出现过拟合的情况。

（三）岭回归（Ridge Regression）和 LASSO

如果在某种特殊的情况下，特征的个数 n 大于样本的个数 m，i.e. 矩阵 X 的列数多于行数，那么 X 不是一个满秩矩阵，因此在计算 的时候会出现问题。为了解决这个问题，有人引入了岭回归（ridge regression）的概念。也就是说在计算矩阵的逆的时候，增加了一个对角矩阵，目的是使得可以对矩阵进行求逆。用数学语言来描述就是矩阵 加上 ，这里的 I 是一个 的对角矩阵，使得矩阵 是一个可逆矩阵。在这种情况下，回归系数的计算公式变成了

岭回归最初只是为了解决特征数目大于样本数目的情况，现在也可以用于在估计中加入偏差，从而得到更好的估计。

从另一个角度来讲，当样本的特征很多，而样本的数量相对少的时候， 很容易过拟合。为了缓解过拟合的问题，可以引入正则化项。如果使用 正则化，那么目标函数则是

其中 。通过数学推导可以得到：

对 求导之后得到：

令导数等于零可以得到： 因此，从另一个角度来说，岭回归（Ridge Regression）是在线性规划的基础上添加了一个 范数的正则化，可以用来降低过拟合的风险。

需要注意的是：在进行岭回归的时候，需要在一开始就对特征进行标准化处理，使得每一维度的特征具有相同的重要性。具体来说就是 (特征-特征的均值)/特征的方差，让每一维度的特征都满足零均值和单位方差。

另外，如果把岭回归中的 范数正则化替换成 范数，那么目标函数就变成了

其中的参数 。 和 范数都有助于降低过拟合的风险，使用 范数的方法被称为 LASSO（Least Absolute Shrinkage and Selection Operation）。使用 范数比使用 范数更加容易获得稀疏解（sparse solution），即它求得的参数 会有更少的非零分量。 获得稀疏解意味着初始的 n 个特征中仅有对应着 的非零分量的特征才会出现在最终的模型中。于是，求解 范数正则化的结果是得到了仅采用一部分原始特征的模型；从另一个角度来说，基于 正则化的学习方法就是一种嵌入式的特征选择方法，其特征选择的过程和训练的过程融为一体，同时完成。

（四）前向逐步线性回归（Forward Stagewise Linear Regression）

前向逐步线性回归算法是一种贪心算法，目的是在每一步都尽可能的减少误差。初始化的时候，所有的权重都设置为1，然后每一步所做的据测就是对某个权重增加或者减少一个很小的值 。

该算法的伪代码如下所示：

数据标准化，使其分布满足零均值和单位方差
在每一轮的迭代中：
  设置当前最小误差为正无穷
  对每个特征：
    增大或者缩小：
      改变一个系数得到一个新的权重W
      计算新W下的误差
      如果误差Error小于当前误差：设置Wbest等于当前的W
    将W设置为新的Wbest

（五）总结

与分类一样，回归也是预测目标值的过程。但是分类预测的是离散型变量，回归预测的是连续型变量。但是在大多数情况下，数据之间会很复杂，这种情况下使用线性模型确实不是特别合适，需要采用其余的方法，例如非线性模型等。