第1279期机器学习日报(2018-03-20)

更新于 2018年3月21日 机器学习
我来说两句
0 2018年3月21日

2018-03-20 日报 机器学习

机器学习日报 2018-03-20

@好东西传送门 出品,由@AI100运营, 过往目录http://daily.awesomeport.cn/ml

订阅:关注微信公众号 AI100(ID:rgznai100,扫二维码),回复“机器学习日报”,加你进日报群

微信公众号:rgznai100

本期话题有:

全部16 算法9 深度学习7 会议活动5 资源4 公告板3 自然语言处理3 应用3 视觉3 知识工程2

用日报搜索找到以前分享的内容: http://ml.memect.com/search/

wx:Angel_Kitty   网页版 2018-03-20 08:28
公告板 深度学习 算法 应用 知识工程 资源 Python 机器人 课程 强化学习 神经网络 推荐系统 问题 知识库 智能汽车
「干货|浅谈强化学习的方法及学习路线」-AI学院高薪招聘兼职AI讲师和AI助教!目前,对于全球科学家而言,“如何去学习一种新技能”成为了一个最基本的研究问题。为什么要解决这个问题的初衷是显而易见的,如果我们理解了这个问题,那么我们可以使人类做一些我们以前可能没有想到的事。或者,我们可以训练去做更多的“人类”工作,常遭一个真正的人工智能时代。虽然,对于上述问题,我们目前还没有一个完整的答案去解释,但是有一些事情是可以理解的。先不考虑技能的学习,我们首先需要与环境进行交互。无论我们是学习驾驶汽车还是婴儿学习走路,学习都是基于和环境的相互交互。从互动中学习是所有智力发展和学习理论的基础概念。今天,我们将探讨强化学习,这是一种基于环境相互交互的学习算法。有些人认为,强化学习是实现强人工智能的真正希望。这种说法也是正确的,因为强化学习所拥有的潜力确实是巨大的。目前,有关强化学习的研究正在快速增长,人们为不同的应用程序生成各种各样的学习算法。因此,熟悉强化学习的技术就变得尤其重要了。如果你还不是很熟悉强化学习,那么我建议你可以去看看我以前有关强化学习文章和一些开源的强化学习平台。一旦你已经掌握和理解了强化学习的基础知识,那么请继续阅读这篇文章。读完本文之后,你会对强化学习有一个透彻的了解,并且会进行实际代码实现。注:在代码实现部分,我们假设你已经有了Python的基本知识。如果你还不知道Python,那么你应该先看看这篇教程。强化学习是学习如何去做,如何根据与环境的交互采取相应的行动。最终的结果就是使得系统的回报信号数值最大化。学习者不会被告知去执行哪个行动,而是要他自己去发现哪种行动将产生最大的回报。让我们通过一个简单的例子来解释一下:我们将一个正在学习走路的孩子作为一个例子。  以下是孩子在学习走路时所要采取的步骤:1.孩子会观察的第一件事,就是注意你是如何走路的。你使用两条腿,一次走一步,一步一步往前走。孩子会抓住这个概念,然后试图去模仿你。2.但很快他/她又会明白,在走路之前,孩子必须先站起来!在学习走路的时候,这对于孩子来说是一个挑战。因此,孩子试图自己站起来,他/她不断跌倒,但是任然不断地站起来。3.然而还有另外一个挑战需要应付。站起来是相对容易的,但是要保持站立状态就是另一个挑战了。在一个狭小的空气中,找到支撑,孩子设法保持站立。4.现在,孩子的真正任务就是开始学习走路了。但是学习走路说起来很容易,而实际做起来就不是那么容易了。在孩子的大脑中需要处理很多事情,比如平衡身体,决定哪个脚是下一次需要放下的,放在哪里。这听起来像是一个很困难的任务,对吗?它实际上确实是一个挑战,先要学习站立,然后才能学习行走。但是,现在我们不都学会了走路嘛,再也不会被这个问题所困扰了。现在,你可以明白,为什么这对于孩子是多么困难的原因了。让我们形式化上面的例子。例子所要陈述的问题是“走路问题”,其中孩子是一个试图通过采取行动(走路)来操纵环境(在地上走路)的智能体,他/她试图从一个状态(即,他/她走的每一步)转移到另一个状态。当他/她完成任务的一个子模块(即,孩子走了几步)时,孩子会获得奖励(比如,一些巧克力),但是当他/她不会走路时,他/她不会收到任何巧克力(这是一个负反馈过程)。这就是像话学习问题的简单描述。    这是一个有关强化学习很好的介绍视频。强化学习属于更打雷的机器学习算法。以下是有关机器学习算法类型的描述。  让我们比较一下强化学习算法和别的类型算法之间的区别:监督学习与强化学习:在监督学习中,在外部有一个“监督主管”,它拥有所有环境的知识,并且与智能体一起共享这个知识,从而帮助智能体完成任务。但是这样存在一些问题,因为在一个任务中,其中存在如此多的子任务之间的组合,智能体应该执行并且实现目标。所以,创建一个“监督主管”几乎是不切实际的。例如,在象棋游戏中,存在数万个可以移动的玩法。因此,去创建一个可以获胜的玩法知识库是一个单调乏味的任务。在这些问题中,从自己的经验中学习,并且获得知识是更加合理可行的。这就是强化学习和监督学习的主要区别。在监督学习和强化学习中,在输入和输出之间都存在映射。但是在强化学习中,存在的是对智能体的奖励反馈函数,而不是像监督学习直接告诉智能体最终的答案。无监督学习与强化学习:在强化学习中,有一个从输入到输出的映射过程,但是这个过程在无监督学习中是不存在的。在无监督学习中,主要任务是找到一个最基础的模式,而不是一种映射关系。例如,如果任务是向用户推荐新闻文章,则无监督学习算法是先查看该人以前读过的类似文章,并把它们推荐给其他人。而强化学习算法则是,通过用户的一些文章,并且获得用户的不断反馈,从而构建一个“知识图谱”,从而得知用户与文章之间的喜爱关系。还有第四种类型的机器学习,成为半监督学习,其本质上是监督学习和无监督学习的组合。它不同于强化学习,类似于监督学习和半监督学习具有直接的参照答案,而强化学习不具有。为了理解如何去解决一个强化学习问题,让我们通过一个经典的例子来说明一下强化学习问题——多臂赌博机。首先,我们需要了解探索与开发的基本问题,然后去定义解决强化学习问题的框架。  Tiger Machine如上图,假设你已经在Tiger Machine上面玩了很多次了。现在你想做的是从Tiger Machine上面获得最大的回报,并且尽可能的快。你会怎么做呢?一个比较天真的想法是,只选择一个Tiger Machine,然后一整天都在玩它。这听起来非常无聊,但Tiger Machine可能会给你一些“报酬”,即让你赢钱。使用这种方法,你可能中奖的概率大约是0.00000…..1。也就是说,大多数时间你可能知识坐在Tiger Machine面前亏钱。正式说明一下,这可以被定义为一种纯粹的开发方法。但是这是最佳选择吗?答案当然是否定的。让我们看看另外一种方法。我们可以拉每个Tiger Machine的拉杆,并且向上帝祈祷,让我们至少打中一个。当然,这是另一种天真的想法,你只会一天都在拉动拉杆,但只是给你一点点报酬。正式说明一下,这种方法只是一种纯粹的探索方法。这两种方法都不是最优的,我们必须在它们之间找到适当的平衡点,已获得最大的回报。这被称为强化学习的探索和开发困境。首先,我们正式的定义解决强化学习问题的框架,然后列出可能的方法来解决这个问题。马尔科夫决策过程:在强化学习场景中,我们定义问题的数学框架被称之为马尔科夫决策过程。这可以被设计为:状态集合:S动作集合:A奖励函数:R策略:π价值:V我们必须采取一定的行动(A),让我们从开始状态移动到结束状态(S)。每当我们采取一个行动之后,我们都会得到一定的回报作为奖励。当然,所获得的奖励的性质(正面奖励还是负面奖励)是由我们的行动决定的。我们的策略集合(π)是由我们的动作集合来确定的,而我们得到的回报确定了我们的价值(V)。在这里,我们的任务就是通过选择正确的策略来最大化我们的价值。所以我们必须最大化下面的方程:  对于时间t,所有可能的S。旅行推销员问题让我们通过另外一个例子来说明一下。  这个问题是一系列旅行商(TSP)问题的代表。任务是以尽可能低的成本,完成从地点A到地点F。两个字母之间的每条边上的数字表示两地之间的距离花费。如果这个值是负数,那么表示经过这条路,你会得到一定的报酬。我们定义价值是当你用选择的策略走完整个路程时,所获得的总价值。这里说明一下符号:状态节点集合:{A,B,C,D,E,F}动作集合是从一个地点到另一个地点:{A->B, C->D, etc}奖励函数是边上的值策略函数指的是完整的路径规划,比如: {A -> C -> F}现在假设你在地点A,唯一你能看见的路就是你下一个目的地(也就是说,你只能看见B,D,C,E),而别的地点你是不知道的。你可以采取贪心算法,去获取当前状态下最有利的步骤,也就是说你从{A -> (B,C,D,E)}中选择采取 {A->D} 这种方法。同样,现在你所在的地点是D,想要到达地点F。你可以从{D -> (B, C, F)} 中采取 {D -> F} 这个方法,可以让你得到最大的报酬。因此,我们采取这一条路。至此,我们的策略就是采取{A -> D -> F},我们获得的回报是-120。恭喜!你刚刚就实现了强化学习算法。这种算法被称之为 epsilon 贪婪算法。这是一种逐步测试从而解决问题的贪婪算法。现在,如果见你(推销员)想再次从地点A到地点F,你总是会选择这一条路了。其他旅游方式?你能猜出我们的策略是属于哪个类别(纯粹的探索还是纯粹的开发)吗?请注意,我们采取的策略并不是一个最佳策略。我们必须“探索”一点,然后去寻找最佳的策略。在这里,我们采取的方法是局域策略的而学习,我们的任务是在所有可能的策略中找到最佳的策略。有很多的方法都可以解决这个问题,在这里,我们简要的列出一些主要类别:策略优先:我们的重点是找到最佳的策略回报优先:我们的重点是找到最佳的回报价值,即累计奖励行动优先:我们的重点是在每个步骤上采取最佳行动在以后的文章中,我会深入讨论强化学习算法。到那时,你可以参考这篇关于强化学习算法调研的论文。接下来,我们将使用深度Q学习算法。Q学习是一种基于策略的学习算法,它具有和神经网络近似的函数表示。这个算法被Google使用,并且打败了Atari游戏。让我们看看Q学习的伪代码:1.初始化价值表 ‘Q(s, a)’.2.观察当前的状态值 ‘s’.3.基于动作选择一个策略(例如,epsilon贪婪)作为该状态选择的动作.4.根据这个动作,观察回报价值 ’r’ 和下一个新的状态 s.5.使用观察到的奖励和可能的下一个状态所获得的最大奖励来更新状态的值。根据上述公式和参数进行更新。6.将状态设置为新的状态,并且重复上述过程,直到达到最终状态。Q学习的简单描述可以总结如下:  我们首先来了解一下 Cartpole 问题,然后继续编写我们的解决方案。当我还是一个孩子的时候,我记得我会选择一根木棍,并试图用一只手指去使它保持平衡。我和我的朋友过去有这样一个比赛,看谁能让木棍保持平衡的时间更多,谁就能得到一块巧克力作为奖励。这里有一个简单的视频来描述一个真正的 Cart-Pole 系统。让我们开始编写代码吧!在开始编写之前,我们需要先安装几个软件。步骤一:安装 keras-rl包在终端中,你可以运行以下命令: 步骤二:安装CartPole环境的依赖我们假设你已经安装好了pip,那么你只需要使用以下命令进行安装:步骤三:开始编写代码首先我们需要导入一些我们需要的模块 然后,设置相关变量 之后,我们来构建一个非常简单的单层神经网络模型。 接下来,我们配置和编译我们的智能体。我们将策略设置为 Epsilon 贪婪,我们还将我们的存储空间设置为序列存储,因为我们要需要存储我们执行操作的结果和每一个操作所获得的奖励。 现在,让我们来测试一下我们的强化学习模型下图是模型的输出结果:  瞧,你刚刚就建立了一个强化学习机器人!现在,你已经看到了强化学习的一个基本实现,让我们开始学习更多的问题吧,每次增加一点点复杂性。汉诺塔问题  对于那些不知道比赛的人来说,汉诺塔问题是在1883年发明的。它是由3根木棍和一系列大小不一的圆盘组成的(比如,上图中的3个)。从最左侧的木棍开始,目的是以最少的移动次数,把最左边的圆盘移动到最右边的圆盘上。如果我们要处理这个问题,那么我们先从处理状态开始:初始状态:三个圆盘都在最左边的木棍上(从上到下,依次编号为1,2,3)结束状态:三个圆盘都在最右边的木棍上(从上到下,依次编号为1,2,3)所有可能的状态:这里是我们可能得到的27种状态:  其中,(12)3* 表示,圆盘1和圆盘2在最左边的木棍上面(从上往下编号),圆盘3在中间那个木棍上面,最右边的木棍没有圆盘。数值奖励:由于我们想要以最少的移动步数解决这个问题,所以我们可以给每个移动赋予 -1 的奖励。策略:现在,如果我们不考虑任何的技术细节,那么前一个状态可能会存在几种下一个状态。比如,当数值奖励为-1时,状态 (123)** 会转移到状态 (23)1,或者状态 (23)1 。如果你现在看到了一个并发进行的状态,那么上面提到的这27个状态的每一个都可以表示成一个类似于旅行商问题的图,我们可以通过通过实验各种状态和路径来找到最优的解决方案。3 x 3 魔方问题虽然我可以为你解决这个问题,但是我想让你自己去解决这个问题。你可以按照我上述同样的思路,你应该就可以解决了。从定义开始状态和结束状态开始,接下来,定义所有可能的状态及其转换,以及奖励和策略。最后,你应该就可以使用相同的方法来构建自己的解决方案了。正如你所认识到的,一个魔方的复杂性比汉诺塔问题要高很多倍。现在,让我们来想象一下棋类游戏中的状态和选择的策略数量吧,比如围棋。最近,Google DeepMind公司创建了一个深度强化学习算法,并且打败了李世石。最近,随着在深度学习方面的成功。现在的重点是在慢慢转向应用深度学习来解决强化学习问题。最近洪水一般的消息就是,由Google DeepMind创建的深度强化学习算法打败了李世石。在视频游戏中也出现了类似的情况,开发的深度强化学习算法实现了人类的准确性,并且在某些游戏上,超越了人类。研究和实践仍然需要一同前进,工业界和学术界共同策划努力,以实现建立更好地自适应学习机器人。  以下是几个已经应用强化学习的主要领域:博弈论和多个智能体交互机器人计算机网络车载导航医学工业物流还有这么多的领域没有被开发,结合目前的深度学习应用于强化学习额热潮,我相信以后肯定会有突破!来源::http://www.cnblogs.com/ECJTUACM-873284962/-马上学习挑战百万年薪-点击“阅读原文”,查看详情 via: http://mp.weixin.qq.com/s?__biz=MzA4NzE1NzYyMw==&mid=2247496913&idx=2&sn=3ac545543a6215affe838ff4a4e50e26&scene=0#wechat_redirect

 

wx:让创新获得认可   网页版 2018-03-20 16:22
公告板 会议活动 架构 深度学习 视觉 算法 应用 资源 Forest Algorithm Josh Wills KNN PCA Python Spark SVM 分类 广告系统 回归 会议 活动 集成学习 聚类 决策树 社交网络 数据 数据科学 统计 医疗 预测 招聘 主题模型
「数据科学家必备的10大统计技术」「将门2018年度创新峰会」强势来袭!3月24日,我“门”将在北京举办首届将门年度创新峰会,届时将携手科技圈的技术大咖们,首次集结来自交通、医疗、零售、生活等领域的数十家行业引领大企业以及优秀的创业企业们,共同探讨AI最新技术创新趋势、解读技术激活商业场景的热点话题、深究AI落地产业发展的现在及未来,共同向创新者致敬。报名请点击本页面左下角“阅读原文”,嘉宾阵容与活动详情请参见今日的头条推送。 来源:Towards Data Science编译:Simons Road 不管你怎样看待数据科学家的研究工作,都不能轻易忽略对数据进行分析、组织和梳理的重要性。Glassdoor 网站收集了大量的雇主和员工的反馈数据,发现数据科学家位列 “美国最好的 25 个职位”榜首。尽管摘得这一桂冠,但需要数据科学家们研究的工作内容还在不断新增。随着机器学习等技术越来越普遍的应用,深度学习等热门领域受到研究人员和工程师以及企业的关注日渐增加,数据科学家必将继续站在技术创新的浪潮之巅,引领着时代的技术变革。 因此他们需要系统地研究统计机器学习,该学科脱胎于统计学和泛函分析,并结合了信息论、最优化理论和线性代数等多门学科。尽管强大的编程能力对数据科学家而言十分重要,但数据科学家也不完全就是软件工程师。事实上熟练掌握Python对于他们就已足够,真正重要的是同时具备编程、统计和批判思维的能力。 正如Josh Wills所言:“数据科学家比程序员擅长统计学,比统计学家擅长编程。” 很多软件工程师想转型数据科学家,但他们盲目地使用 TensorFlow 或 Apache Spark 等机器学习框架来处理数据,却忽略了背后的统计学理论知识。也就是统计学习理论,机器学习的理论框架,这些都源自统计学和泛函分析。 那么为什么要学习统计学习?我们只有深刻理解了不同技术背后的想法,才能学以致用。也只有先易后难,才能游刃有余、融会贯通。同时,准确评估一种方法的性能也非常重要,不仅能知道工作效果的好坏,也能得知方法的适用范围。此外,统计学习也是一个令人振奋的研究领域,在科学、工业和金融领域都有重要的应用。最后,统计学习是培养现代数据科学家的基础要素。统计学习问题应用的例子如下:确定前列腺癌的风险因素根据对数周期图对录音进行分类根据人口统计学、饮食和临床测量预测是否会患有心脏病定制垃圾邮件检测系统识别手写邮政编码对组织样本进行癌症分类建立人口调查数据中的薪资与人口统计变量的关系 在介绍常用的10种统计技术之前,我们需要先区分一下机器学习和统计学习,主要有以下几点区别: 机器学习是人工智能的一个分支统计学习是统计领域的一个分支机器学习更侧重于大规模应用和预测的精准性统计学习强调模型及其解释性、精度和不确定性但区别也在变得越来越模糊,两者很多时候交织在一起不得不说,市场营销把机器学习炒得很热 线性回归 在统计学中,线性回归是一种通过拟合因变量和自变量之间的最佳线性关系来预测目标变量的方法。最佳拟合即表示由当前的线性表达式得到的预测输出与实际观测值的误差和最小。 线性回归主要分为简单线性回归和多元线性回归。简单线性回归使用一个自变量来拟合最佳线性关系预测因变量;而多元线性回归使用多个自变量来拟合最佳线性关系预测因变量。 那么线性回归可以用在哪些实际问题上呢?实际上任意选择日常生活中相关的两件事,你便能通过线性回归模型得到他们之间的线性关系。比如你有了过去三年的月消费、月收入和月旅行次数的数据,那你可以预测下一年月支出,还可以知道是月收入还是月旅行次数对月消费更影响,甚至还能用方程式表达月收入、月旅行次数、月消费三者之间的关系呢。  分类 分类是属于一种数据挖掘技术,将数据集分成多个类别可以帮助更准确的预测和分析。分类是一种高效分析大型数据集的方法,典型的代表有逻辑回归(Logistic Regression) 分析和判别分析 (Discriminant Analysis)。 逻辑回归分析适合用于因变量为二元类别时的回归分析。 和所有回归分析一样,逻辑回归也属于预测分析。 Logistic回归用于描述数据,并解释二元因变量与一个或多个名义、序数、区间或比率级别等描述性的自变量之间的关系。 适合逻辑回归的问题类型有: 体重每超出标准体重一磅或每天每抽一包烟对得肺癌概率是否有影响(是或否)。卡路里摄入、脂肪摄入和年龄对心脏病是否有影响(是或否)。 在判别分析中,两个或多个已知的集合、簇或群体都可以作为分类的先验知识,使用时根据被测特征就可把新的观测值划分到相应类别。判别分析会对每个类中的预测因素 X 分别进行建模,然后根据贝叶斯定理便能将其转换成只需根据 X 值就可获得对应类别的概率估计。此类模型既可以是线性判别分析,也可以是二次判别分析。 Linear Discriminant Analysis线性判别分析,通过自变量的线性组合对每个观测值计算“判别分数”,并对其所处的响应变量Y类别进行分类。它假设每个类别内的观测值都服从多变量高斯分布,且每个类别的方差一样。 Quadratic Discriminant Analysis二次判别分析,提供了另一种方法。与LDA一样,QDA也假设来自Y的每类观察值都服从高斯分布。但与LDA不同的是,QDA假定每个类别都有其自己的协方差矩阵,也就是说每个类别的方差不一样。 重采样方法 重采样方法就是从原始数据样本中重复提取样本,属于统计推断的非参数方法。重采样不使用通用分布表来逼近地计算概率 p 的值,而是基于实际数据生成一个独特的采样分布。这种采用分布通过经验性方法生成,而不是分析方法,它能够基于数据所有可能结果的无偏样本获取无偏估计。为了很好的理解重采样的概念,我们需要先了解Bootstrapping和交叉验证(Cross-Validation): Bootstrapping是有助于在许多情况下验证预测模型的性能和集成方法,估计模型的偏差和方差。 它通过对原始数据进行有放回的采样,并将“未被选择”的数据点作为测试用例。 我们可以多做几次这样的操作,然后用平均值来作为我们对模型性能的估计。Cross validation交叉验证通过将训练数据分成k个部分来验证模型性能,使用k-1部分作为训练集,余下的部分作为测试集。 重复不同的k次后,将k个分数的平均值作为模型的性能估计。 通常对于线性模型而言,普通的最小二乘法是拟合数据时的主要标准。 接下来的3种方法可以为线性模型拟合提供更好的预测精度和模型可解释性。 子集选择 子集选择的主要目的是挑选出与问题最相关的 p 个预测因子,然后使用该子集特征和最小二乘法拟合模型。  最佳子集的选择,我们可以为 p 个预测因子的每个组合分别拟合普通最小二乘回归,然后再观察各个模型的拟合结果。算法分为两个阶段:(1)拟合包含 k 个预测因子的所有模型,其中 k 表示模型的最大长度;(2)使用交叉验证预测损失选择单个模型。要记住,不能单纯使用训练误差评估模型的拟合情况,验证集或测试集的误差也是十分重要的,因为 RSS 和 R^2 会随变量的增加而单调递增。最好的方法就是通过选择测试集中最高的 R^2 和最低的 RSS 来交叉验证,从而选择模型。前向逐步选择,可以选出 p 个预测因子的较小子集。算法先从不包含预测因子的模型开始,然后逐步地添加预测因子到模型中,直到所有预测因子都包含在模型中。添加预测因子的顺序是根据不同变量对模型拟合性能提升的程度来确定的,不断添加新的预测因子,直到交叉验证误差没有大的改变。后向逐步选择,与前向逐步选择相反,首先模型包含所有 p个 预测因子,然后迭代地移除用处最小的预测因子。混合法,主体遵循前向逐步方法,但在添加每个新变量之后,该方法可能还会移除对模型拟合无用的变量。 特征缩减技术 特征缩减技术使用了所有 p 个预测因子进行建模,然而,表示预测因子重要性的系数将随最小二乘误差向零收缩,这种收缩也称之为正则化,它旨在减少方差以防止模型的过拟合。常用的缩减系数方法有lasso(L1正则化),岭回归(L2正则化)。 Ridge regression岭回归,跟最小二乘法很像都是寻求减少 RSS 的系数估计,只不过它是通过对损失函数(即优化目标)加入惩罚项,使得训练求解参数过程中会考虑到系数的大小。我们不需要数学分析就能看出 Ridge 回归很擅长于将特征收缩到最小的子空间中。如主成分分析PCA,通过Ridge 回归可以将数据投影到低维空间,并在系数空间内收缩较低方差的成分而保留有较高方差的成分。但Ridge 回归有一个缺点,最终的模型需要包含所有 p 个预测因子,这源于尽管惩罚项将会令许多预测因子的系数逼近零,但又一定不等于零。虽然这对预测准确度并没有什么影响,却令模型的结果更难以解释。Lasso 方法就很好的克服了这一缺点,因为它能在 s 足够小的时候迫使一些预测因子的系数归零。当 s = 1 时,就像正常的OLS 回归,而当 s 逼近 0 时,系数将收缩到零。因此 Lasso 回归同样是执行变量选择的好方法。 降维(维数减约) 降维是将将p + 1个系数估计问题简化为为M + 1系数估计问题,其中M <p,可以通过寻找M个变量的最佳线性组合或最佳投影来实现的。降维的两种方法有主成分回归principal component regression和partial least squares偏最小二乘法。 Principal Components Regression主成分回归,是从大量的变量中寻找低维特征集的方法。数据中的第一主成分(first principal component)是指观测数据沿着这个变量方向的变化最大,也就是说若用 p 个不同的主成分分别拟合数据,那第一主成分必然是最接近数据分布的那条线。第二主成分是和第一主成分不相关的变量的线性组合,且在该约束下有最大的方差。主要思想是主成分能在各个互相垂直的方向使用数据的线性组合得到最大的方差。基于这种方法,我们还能结合相关变量的效应从数据中获取更多的信息,毕竟在常规的最小二乘法中需要舍弃其中一个相关变量。 由于PCR 方法需要得到 X 的最优线性组合。由于 X 对应的输出 Y 对主成分方向的计算没有影响,也就是说这些组合(方向)是通过无监督方法获得的,那么就无法保证这些方向是预测器的最优表征,也无法保证能获得最优预测输出。偏最小二乘法(PLS)作为 PCR 的代替方法,属于有监督方法。和 PCR 类似,PLS 也是一种降维方法,它首先提取一个新的较小的特征集合(原始特征的线性组合),然后通过最小二乘法将原来的模型拟合为一个新的具有 M 个特征的线性模型,通过对模型预测误差来评价特征集合是否是Y的最优线性组合。 非线性模型 在统计学中,非线性回归属于回归分析的一种形式,通过模型参数的非线性组合来(依赖于一个或多个独立变量)对观测数据建模,并使用逐次逼近法来拟合数据。以下是几种处理非线性模型的重要技术: 阶梯函数(step function),变量为实数,可以写成区间的效用函数的有限线性组合的形式。通俗的讲,阶梯函数就是一种只有有限部分的分段常数函数。分段函数(piecewise function)通过多个子函数定义,且每一个子函数被定义在确定的区间上。分段实际上是函数的表示方式,而不是函数自身特性,但通过额外的限定条件,它也可以用于描述函数本身。例如,一个分段多项式函数是一个在每一个子定义上为多项式的函数,其中每一个多项式都可能是不同的。 样条曲线(spline)是一种用多项式分段定义的特殊函数。在计算机图形学中,样条曲线是一种分段多项式参数化曲线。由于结构简单、评估简易和精度高,以及通过曲线拟合和交互曲线设计就能逼近复杂曲线的能力,使得样条曲线很常用。广义加性模型(generalized additive model)是一种广义线性模型,其中线性预测器线性依赖于某些预测器变量的未知平滑函数,其主要作用就是推断这些平滑函数。 基于树的方法 基于树的方法可以用于回归和分类问题,它会将预测器空间分层或分割成一些简单的区域。由于预测器空间的分裂规则集合可以总结为一个树,因此也被称为决策树方法。以下的方法是几种不同的树,它们可以组合起来投票输出统一的预测。 Bagging 能通过从原始数据中生成额外的训练数据(通过组合和重复生成和原始数据大小相同的多段数据)来减少预测的方差,但无法提高模型的预测能力。Boosting 是一种计算输出的方法,使用多个不同的模型,然后使用加权平均的方法对结果取平均值。一般结合各方法的优势来改变这些方法所占的权重,此外,针对更宽泛的输入数据还可以微调参数得到更佳的预测能力。 随机森林算法(random forest algorithm)实际上和 bagging 算法很相似,同样是对训练集提取随机 bootstrap 样本。然而,除了 bootstrap 样本以外,还可以提取特征的随机子集来训练单个树;在 bagging 中,则需要为每个树提供全部的特征。由于特征选择是随机的,相比常规的bagging 算法,每个树之间更加独立,从而通常能获得更好的预测性能(得益于更好的方差-偏差权衡)。由于每个树只需要学习特征的一个子集,因此速度也得以提升。 支持向量机 支持向量机(SVM)是一种常用的有监督学习分类技术。通俗地说,它寻找两类点集的最优超平面(hyperplane,在 2D 空间中是线,在 3D 空间中是面,在高维空间中就是超平面。超平面是n 维空间的 n-1 维子空间)。这个超平面使得两类点集的间隔最大,本质上是约束最优化问题,在一定约束下使得间隔最大化,从而实现数据的完美分类。 “支持向量”,就是那些支持着超平面的数据点,也可以说是离超平面最近的数据点。在上图中,蓝色填充圆和两个填充方块就是支持向量。使用过程中,当两类数据线性不可分时,数据点可以通过核函数投影到高维空间中,使得数据变得线性可分。而多分类问题也可以分解成多个”一对一”(one-versus-one)或”一对剩余”(one-versus-rest)的二分类问题。 无监督学习 有监督学习是机器学习中的一大部分,其中数据分类已知。当数据分类是未知时,就需要使用另一种技术了,就是无监督学习,它们需要自己去发现数据中的模式。聚类(clustring)是一种典型的无监督学习,数据会根据相关性被分为多簇。以下是几种最常用的无监督学习算法: Principal Component Analysis 主成分分析:通过保留具备最大方差和互相不相关的特征之间的线性组合,可以生成数据集的低维表示。它还有助于理解无监督学习中的隐变量交互。k-Means clustering k 均值聚类:属于硬聚类算法,根据数据到聚类中心的距离将其分成 k 个不同的簇。Hierarchical clustering层次聚类:由于k-means算法始终有K值选择和初始聚类中心点选择的问题,而这些问题也会影响聚类的效果。为了避免这些问题,我们可以选择另外一种比较实用的聚类算法,就是层次聚类算法。顾名思义,层次聚类就是一层一层的进行聚类,可以自顶向下把大的类别(cluster)分割,叫作分裂法;也可以自下而上对小的类别进行聚合,叫作凝聚法;但是一般用的比较多的是由下向上的凝聚方法。 以上就是一些帮助数据科学家理解数据基本的统计技术,了解这些基本分析技术将为为项目的开发和数据的理解带来更多的益处,对数据的抽象和操作会变得更加容易。希望这篇文章能帮助小伙伴们在理解数据科学的路上带来一些新的收获。 -The End- 将门2018招聘看这里!企业战略合作、投资总监/经理、财务总监、新媒体运营、技术专家、行业专家等多个岗位期待您的加入~也欢迎您转给身边优秀的朋友!推荐成功、一经录用将获得15000元现金作为答谢!简历请发送至>>dream@thejiangmen.com;更多详情>>将门招聘 | 2018年将门开放大量职位,期待你的加入!将门是一家专注于发掘、加速并投资技术创新激活商业价值的创业公司的创投机构,旗下设有将门创新服务、将门技术社群以及将门投资基金。将门创新服务专注于使创新的技术落地于真正的应用场景,激活和实现全新的商业价值,服务于行业领先企业和技术创新型创业公司。将门技术社群专注于帮助技术创新型的创业公司提供来自产、学、研、创领域的核心技术专家的技术分享和学习内容,使创新成为持续的核心竞争力。将门投资基金专注于投资通过技术创新激活商业场景,实现商业价值的初创企业,关注技术领域包括机器智能、物联网、自然人机交互、企业计算。在两年的时间里,将门投资基金已经投资了包括量化派、码隆科技、禾赛科技、伟景智能、Convertlab、迪英加科技等十几家具有高成长潜力的技术型创业公司。如果您是技术领域的初创企业,不仅想获得投资,还希望获得一系列持续性、有价值的投后服务,欢迎发送或者推荐项目给我“门”: bp@thejiangmen.com    将门创投让创新获得认可!微信:thejiangmenbp@thejiangmen.com 报名首届将门年度创新峰会,请点击“阅读原文”,即刻参与! via: http://mp.weixin.qq.com/s?__biz=MzAxMzc2NDAxOQ==&mid=2650366331&idx=2&sn=f11180b48e03937dd5def367aa4bb6c5&scene=0#wechat_redirect

 

爱可可-爱生活   网页版 2018-03-20 08:20
深度学习 代码
’Live training loss plot in Jupyter Notebook for Keras, PyTorch and others’ by Piotr Migdał GitHub: http://t.cn/RnVEDTz

 

爱可可-爱生活   网页版 2018-03-20 06:10
视觉 论文
《Zero-Shot Object Detection: Learning to Simultaneously Recognize and Localize Novel Concepts》S Rahman, S Khan, F Porikli [Australian National University] (2018) http://t.cn/RnVWJ6X view:http://t.cn/RnVWJ6a

 

ICTCLAS张华平博士   网页版 2018-03-19 10:11
自然语言处理
NLPIR 大数据语义智能分析客户端重装上线,融合了网络精准采集,自然语言处理,文本内容挖掘,语义精准搜索四大部分,欢迎品鉴!http://t.cn/Rn5r0lk

 

PaperWeekly   网页版 2018-03-20 17:48
深度学习 算法 神经网络
【RNN】Independently Recurrent Neural Network (IndRNN): Building A Longer and Deeper RNN 本文使用relu等非饱和激活函数使网络变得更具有鲁棒性,可以处理很长的序列(超过5000个时间步),可以构建很深的网络(实验中用了21层)。在各种任务中取得了比LSTM更好的效果。 推荐人:Zsank(PaperWeek…全文: http://m.weibo.cn/2678093863/4219704182392248

 

爱可可-爱生活   网页版 2018-03-20 16:18
视觉
【深度图像翻译实验:因为“知”所以“见”】《Learning to see: You are what you see》by Memo Akten http://t.cn/RnfrieT http://t.cn/RnfrzFx

 

数盟社区   网页版 2018-03-20 15:30
算法 神经网络
干货 | 转型人工智能,你需要掌握的八大神经网络http://t.cn/RnfE48E

 

wx:   网页版 2018-03-20 15:30
会议活动 算法 应用 语音 资源 自然语言处理 Elon Musk 安全 会议 活动 机器翻译 机器人 课程 梅德 智能汽车
「2018年最值得关注的15大技术趋势,区块链将得到更广泛的应用」通常情况下,技术趋势是很难准确预测的,因为预测未来本身就极其困难。但是我们还是可以从过往的一些显著数据指标来推测新的一年里科技行业的发展趋势。2018,有哪些值得关注的技术趋势? 01 区块链将得到更广泛的应用 区块链是一种每一个人都能够分享和访问的电子分类账,交易的双方可通过区块链来跟踪交易记录。区块链这个词在整个2017年都备受大家关注,这是因为加密货币比特币采用了一个分散式区块链来跟踪它的所有交易记录,然而区块链技术的应用范围远不限于比特币,它还有更广泛的应用范围。有些人希望将区块链技术能够应用在病历记录上,病人的病史可通过不同的数据库和软件集中导入一个加密数据库。这么做的益处在于:病人的个人病史可以存储在一个安全的、分散的地方,医生在不通过的办公室和医疗中心软件都能访问这个数据库,这样一来,这样就不存在让不同软件或办公室间相互协作来升级数据库的问题了。 02 狭义人工智能进一步扩展 最近一段时间以来,关于人工智能有很多不同的说法,但是让很多公司在2018年真正获益的地方在于采用那些擅于解决一个非常具体的任务的算法和电脑智能,这通常被称为狭义人工智能。狭义人工智能与通用人工智能(想象一下试图接管世界的自动机器人)是有区别的。狭义人工智能只是让电脑完成一些非常具体的工作,比如驾驶汽车。狭义人工智能可以应用在所有的地方,从语言翻译软件到 Facebook Newsfeed中的内容算法,2018年,很有可能我们将看到有更多公司使用狭义人工智能来让公司的业务变得更高效,同时进一步提高公司产能。 03 地下交通方式将会获得更多牵引力 2016年年末,特斯拉CEO Elon Musk宣布,他将成立一家致力于解决洛杉矶众所周知的交通问题新公司。就在去年,Musk的新公司 Boring Company挖掘了一条长达 150 多米的隧道来测试一个全新的地下高速轨道系统,旨在为乘客提供更加便利和高速的出行服务。Boring Company可能会提供两种类型的交通方式,第一种方式是一种能够一次将超过12名乘客以241 千米/小时的速度从一个城市运送到另外一个城市的轨道系统;另一种方式则是 Musk 提出的Hyperloop超级高铁概念,它由在近真空电子管中以700英里/小时的速度飞行的舱室组成。Boring Company目前正在洛杉矶打造 一个6.5英里长的隧道用于概念验证,如果这个项目获得该城市的最终批准,它最终可能会变成洛杉矶的地下隧道系统。Boring公司在马里兰州也在挖掘一个用于测试的地下交通轨道,这个轨道最终也将变成华盛顿特区和纽约市之间的一个地下交通系统。这些测试隧道在 2018 年不会完工,不过我们在2018年肯定能了解有关它们的更多信息。 04 5G无线带宽将推出 AT&T和Verizon 在 2017 年就已经开始测试 5G 无线网络了。这两家公司表示, 它们将在2018将这项服务进行有限地商用化。与 4G 和 LTE 不同,5G网络最初将主要用于家用网络领域,允许电信运营商通过无线连接向家庭提供多千兆比特的网速。作为对比,1G 的网速是目前美国家用带宽平均网速的 15 倍。相比传统的有线网络连接,5G网络不仅速度更快,同时也能极大地降低家用网络的拥堵情况(试想一下你和邻居同时在线看电影时网速有多慢),延迟也会更低(可以很快地发送信息)。Verizon将在2018年在加利福尼亚的 Sacramento以及另外四个尚未宣布布的市场中推出 5G 网络。 05 比特币将会得到更多的关注和报道 2017年年末,比特币价格的快速上涨得到了众多投资者和普通大众的关注,2018年,我们还会看到类似的趋势。比特币是一种允许它的所有者以匿名的方式安全地购买的加密货币。有些零售商已经开始接受比特币富康了,比如Home Depot和Overstock.com,预计2018年将有更多的零售商接受比特币支付,尤其是在当比特币的价格持续上涨的情况下更是如此。但比特币的波动性仍然很高,它的在线交易场所(你买卖比特币的地方)经常成为黑客攻击的目标。这意味着,在2018年,比特币的价格既有可能进一步上涨,也有可能会下跌。不管是哪种情况,我们在2018年都会看到有过加密货币的更多报道。 06 增强现实将在移动设备上成为主 2017年,通过发布内置了增强显示功能的iOS11,苹果让数亿iPhone和iPad用户都使用上了增强现实功能,这是一个巨大的进展。苹果公司允许开发者可以开发自己的AR应用,比如宜家的 Place应用,这款应用允许用户扫描家中的房间,并在房间内添加虚拟家具,看看家居在房间内的实际效果。Facebook在2017年也采取了一些措施,让用户在2018 年在Facebook的平台上更多地使用增强现实应用。Facebook新推出的 AR Studio 允许开发者为 Facebook 和 Messenger 应用开发滤镜和镜头效果插件,比如在自拍时添加增强现实面具。此外,苹果还将AR 滤镜的应用范围扩展到了 Instragram 应用里。根据德勤会计师事务所的研究,苹果和 Facebook对移动 AR的重视是2018年预计有 10 亿智能手机用户通过手机生成 AR 内容的重要原因之一。 07 我们将会看到世界上第一个真正的无人驾驶汽车服务的出现 众多汽车制造商和大型科技公司在很多很长一段时间以来一直在测试无人驾驶汽车技术,但是在2018年,Alphabet旗下的无人驾驶汽车公司 Waymo将会取得更大突破。在过去几个月时间里,Waymo一直在亚利桑那州凤凰城的研究无人驾驶工具。Waymo近期曾表示,Waymo将会在几个月时间之内在凤凰城推出无人驾驶汽车服务。这意味着在凤凰城里,Waymo的汽车将会按需接人,在驾驶位没有驾驶员的情况下就能把乘客送到凤凰城内的目的地。这不仅仅是Waymo向前迈进的一大步,也是整个无人驾驶汽车技术向前迈进的一大进步,意味着 Waymo公司将领先竞争对手几年时间。大多汽车制造商和技术公司都表示将于2021年推出自己的无人驾驶汽车服务。 08 新太阳能技术的发展 2018巴菲特股东大会暨美国资产配置投资巅峰考察项目价值投资盛典——巴菲特股东大会美国顶级私人俱乐部耶鲁俱乐部内倾听中美金融行业座谈中美风险投资峰会“金融期货之父”、“CME集团终身荣誉主席”利奥·梅拉梅德演讲全球顶级对冲基金参访国际顶级衍生品交易所CBOE/CBOT参访 参访顶级投资银行/资产管理公司,倾听资产管理与家族理财讲座 地点:芝加哥 • 奥马哈 • 纽约时间:2018年5月1日—11日(报名截止日期:4月1日)报名电话/微信:18516600808 2017年,麻省理工学院的一群科学家开始研究一种名为太阳能热光伏电池(Hot Solar Cells)的新型的太阳能面板技术。和传统的太能能光伏电板而言,太阳能热光伏电池在将太阳能转化为电能上更高效,是传统的太能能光伏电板的两倍,因为它使用的材料更先进,捕捉光线的流程更先进。太阳能热光伏电池本质上是将光线导入碳纳米管,然后在将其加热至大概 1000摄氏度后,再将热量转移到聚焦于太阳能电池的光线中。和传统的太阳能面板相比,这个过程将太阳能转化为能源的效率更高,还能吸收并储存一些热能供今后使用。太阳能热光伏电池的研究现在还处在非常早期的阶段,但它可以在未来几年时间内让太阳能面板技术超越传统的太阳能面板 09 家用数字虚拟助理将会变得越来越流行 像Amazon的 Echo(配有Alexa虚拟助手)这样的支持语音的智能音箱其实在2014 年就有了,但是到2017 年年底才得到了更多的关注和普及,相信这个趋势将会延续到 2018 年。这类智能音箱可以回答有关天气咨询、在线订购产品和网页搜索等服务,甚至还可以帮用户叫Uber或线上订Pizza。智能音箱还可以与其他智能家居产品配合起来使用,比如恒温器,这样一来,用户使用语音就能够控制家里的所有设备。调研结构Juniper Research发布的数据现实,从2016年到2017年,使用这类智能音箱设备的美国人增加了将近 130%,预计到 2020 年,将会有超过一半的美国家庭都会拥有至少一台智能家用音箱。所有这些数据都意味着,2018年,我们将会看到越来越多的用户将会使用数字虚拟助理。 10 量子计算将会越来越普遍 量子计算是一个比较难理解的概念,对于量子计算最简单的解释是:借助量子力学定律,让计算机能够将信息同时处理 为1 和 0,传统的计算机只能将信息处理为 1 或 0。如此一来,计算机就能够一次性计算出多个结果,而不用按顺序处理答案。因为量子计算机能够按这种方式处理信息,因此量子计算机远比传统计算机更为强大。2017年年底,Google在量子计算机领域取得了重大进展,目前Google已经为化学家和材料科学家提供免费的、开源量子计算软件。虽然目前的量子计算机还处于非常早期的阶段,但是很多科技巨头都相信,量子计算机很快就能用来解答气候变迁问题,并且有助于新的医学发现的出现。Google、IBM、微软等公司已经在量子计算领域加大了投入,Google最新的软件与 IBM 等公司的量子计算机是兼容的,这为量子计算技术在2018年的广泛采用铺平了道路。 11 外科手术机器人将会进入越来越多的手术室 多年以来,Intuitive Surgical 公司在外科手术机器人市场一直占据主导地位,这家公司的达芬奇手术机器人从2000年开始就已经投入使用了,但是因为这家公司的专利即将到期,这就为其它科技公司和大型医疗公司进入外科手术机器人市场打开了一扇大门。外科手术机器人不能自己做手术,需要由外科医生来控制才可以。在有些情况下,医生在外科手术机器人的配合下能够更精确地完成手术。如今,这些外科手术机器人已经变得越来越智能了。最近《经济学人》撰文表示,Google已经开始与Johnson & Johnson合作建立了一家名为 Verb Surgical合资公司,这家公司已经推出了可联网的手术机器人。这种手术机器人能够与其他外科手术机器人共享数据和视频信息,然后再利用机器学习来改善手术的效果。随着越来越多的公司进入这一市场,而且Google进一步扩展了这些机器人协助手术的方式,2018年,我们势必将在这一领域看到更多突破。 12 飞行出租车将会出现 如今,已经有很多公司吹嘘自己有在大型城市推出无人驾驶飞行器(AAV)的能力,但是一家名为“ 亿航”的中国公司将在2018年率先将这一想法变为现实。这家公司目前已经有一架单人的飞行出租车原型机,公司宣称将在 2018 年开始量产能搭载两名乘客的飞行出租车。亿航的 e-184 型看起来就像是一个大型的无人机,它的顶部是一个能够容纳一个人的座舱,它能够以高达 62英里公里/小时的速度飞行到预先设置好的目的地,电池可供支持 25 分钟的航行时间。亿航目前已经签署了一份合同,根据合同,亿航将于2018 年将飞行出租车带到迪拜。目前亿航还在与欧洲的一些城市就引进飞行出租车产品进行洽谈。飞行出租车未来究竟能够变得有多普及,现在还很难预测。但是,2018年将是飞行出租车变成现实的一年。 13 Alphabet将用激光为印度提供互联网服务 Alphabet旗下的X研究部门在2018年将向印度政府出售部分高科技激光束技术,这样它就能为数千万印度用户提供高速互联网服务。这种设备使用的是“空间光学技术”,它是由用来相互间发送和接收激光信号的盒子组成,进而来传输互联网信号,而不是采用常用的铜线或光纤材料。最终的互联网信号将会通过Wifi或者蜂窝信号发送给用户。因为它使用光来发送信号,所以它是终极的无线信号。路透社近日发表的一篇文章表示,Alphabet将提供 2000 个空间光盒,这些光盒彼此间距离大概20公里,大都位于屋顶和电线杆上。这些设备能以 20G/秒的速度发送网络信号。太空光学技术通常会遭遇与天气有关的问题障碍(它非常不喜欢雨雾天气),但 Alphabet表示公司的技术已解决了这里面的一部分问题。 14 物联网继续高歌猛进 物联网(IoT)指的是指那些有传感器来收集数据、并且能够连接到互联网的设备,它们产生的信息可用来分析或者用于自动化。这些设备可以是任何东西,从Apple Watch这类智能手表到能够向计算机发送信号、告知计算机某个机械部件即将失效的工业机械。2016年,在使用中的物联网设备有64 亿个;到2018年,物联网设备数量将达112亿。随着物联网设备数量的不断增加,而且随着物联网设备接管越来越多的工业和企业系统,它们就需要变得更加安全、更容易更新。正因为如此,我们很可能会在未来一年里看到更多的物联网平台软件的出现,而且它的安全性也会继续提高。许多物联网设备非常小,也非常便宜,这意味着基于云计算的软件和基于网络的安全可能是日益增长的物联网市场的关键。市场研究公司Gartner表示,从2018年开始,我们将会看到更多市场空间更大、成本更低的物联网设备的出现,这些设备将会用于生活中的各个领域,从互联安全系统到智能LED灯等等。 15 AR头戴设备的归来 2012年,Google就已经推出了一款名为Google Glass的增强现实眼镜,但是这款设备最终在大家的广泛关注下失败了,因为它无法为用户带来实际的用处。但是在这之后,Google又发布了一款企业级的AR眼镜。Google投资过的AR公司Magic Leap 也将于2018 年发布“混合现实”眼镜。Magic Leap的混合现实眼镜名为“Lightwear”,用于可以用它来浏览互联网、开电话会议或者玩游戏。这款设备的报价目前尚未公布。不过Lightwear的预计销售对象是软件开发者,这样这些开发者就能为这款眼镜开发更多内容和应用。到目前为止,Magic Leap共获得约19亿美元的融资。备受外界期待的 Lightwear眼镜的发布很可能会成为我们将在2018年看到的众多AR眼镜中的第一个。当然了,现在还无法知道上面列的这些技术趋势中的哪些趋势将会在2018 年实现真正的腾飞。但是,上面这些技术趋势都是建立在现有的技术创新的基础之上的,这意味着它们已经不仅仅是昙花一现的想法了。来源 : 36氪 【宽客网络课堂】性价比最高的课程:金融量化分析以Matlab为工具咨询电话/微信:18516600808 via: https://mp.weixin.qq.com/s?__biz=MzA3MDI3ODQxOA==&mid=2651248112&idx=2&sn=b46650d937440ab00aa3abcb7add7269&chksm=84cd398db3bab09b8771321bdc9ae5433911cf3365c7b0c158a09590556d9905c2a695cbe526&scene=27#wechat_redirect

 

wx:   网页版 2018-03-20 15:30
公告板 会议活动 算法 资源 Else If 会议 活动 课程 梅德
「图论的各种基本算法」本篇主要涉及到图论的基本算法,不包含有关最大流的内容。图论的大部分算法都是由性质或推论得出来的,想朴素想出来确实不容易。二分图(Is-Bipartite)一个图的所有顶点可以划分成两个子集,使所有的边的入度和出度顶点分别在这两个子集中。这个问题可以转换为上篇提到过的图的着色问题,只要看图是否能着2个颜色就行了。当然,可以回溯解决这个问题,不过对于着2个颜色可以BFS解决。同样,一维数组colors表示节点已着的颜色。伪代码:IS-BIPARTITE(g,colors)  let queue be new Queue  colors[0] = 1  queue.push(0)  while queue.empty() == false    let v = queue.top()    queue.pop()    for i equal to every vertex in g      if colors[i] == 0        colors[i] = 3 – colors[v]        queue.push(i)      else if colors[i] == colors[v]        return false    end  end  return true时间复杂度:Θ(V+E),V表示顶点的个数,E表示边的个数DFS改良(DFS-Improve)上篇文章提到过,搜索解空间是树形的,也就是在说BFS和DFS。那么在对图进行BFS和DFS有什么区别呢,这个问题要从解空间角度去理解。对图进行BFS的解空间是一颗树,可叫广度优先树。而DFS是多棵树构成的森林,可叫深度优先森林。这里要对DFS进行小小的改良,它的性质会对解多个问题会很有帮助。原版DFS搜索的时候,会先遍历本顶点,再递归遍历临接的顶点。DFS改良希望能先递归遍历临接的顶点,再遍历本顶点,并且按遍历顺序逆序存储起来。伪代码:DFS-IMPROVE(v,visited,stack)  visited[v] = true  for i equal to every vertex adjacent to v    if visited[i] == false      DFS-IMPROVE(i,visited,stack)  end  stack.push(v)这个改良版DFS有个很有用的性质就是,对于两个顶点A、B,存在A到B的路径,而不存在B到A的路径,则从记录的顺序中取出的时候,一定会先取出顶点A,再取出顶点B。以下为这个性质的证明。假设:有两个顶点A和B,存在路径从A到B,不存在路径从B到A。证明:分为两种情况,情况一,先搜索到A顶点,情况二,先搜索到B顶点。对于情况一,由命题可得,A一定存储在B之后,那么取出时先取出的是顶点A。对于情况二,先搜索到B顶点,由于B顶点搜索不到A顶点,则A一定存储在B之后,那么取出时仍先取出的是顶点A,命题得证。DFS改良性质:对于两个顶点A、B,存在A到B的路径,而不存在B到A的路径,则从记录的顺序中取出的时候,一定会先取出顶点A,再取出顶点B。欧拉回路(Eulerian-Path-And-Circuit) 在无向图中,欧拉路径定义为,一条路径经过所有的边,每个边只经过一次。欧拉回路定义为,存在一条欧拉路径且路径的起点和终点为同一个顶点。可以看到只有连通图才能有欧拉回路和欧拉路径。这个算法很巧。如果一条路径要经过一个顶点,本质是从一条边到达一个顶点,然后从这个顶点通过另一条边出去。欧拉回路就是要求路径要经过所有的点,起点和终点还都是同一个顶点。那么就等价于要求所有顶点连接的边是2个。实际上,路径还可以经过顶点多次,那么就等价于要求所有顶点连接的边是偶数个。欧拉路径的要求就等价于所有顶点连接的边是偶数个,除了起点和终点两个顶点可以是奇数个。先判断图是否是连通图。返回0代表没有欧拉回路或者欧拉路径,返回1代表有欧拉路径,返回2代表有欧拉回路。伪代码:EULERIAN-PATH-AND-CIRCUIT(g)  if isConnected(g) == false    return 0  let odd = 0  for v equal to every vertex in g    if v has not even edge       odd = odd + 1  end  if odd > 2    returon 0  if odd == 1    return 1  if odd == 0    return 2时间复杂度:Θ(V+E),V表示顶点的个数,E表示边的个数拓扑排序(Topological-Sorting)将一张有向无环图的顶点排序,排序规则是所有边的入度顶点要在出度顶点之前。可以看到,无向和有环图都不存在拓扑排序,并且拓扑排序可能存在多种解。拓扑排序有两种解法,一种是从搜索角度。如果我能保障先递归遍历临接的顶点,再遍历本顶点的话,那么遍历的顺序的逆序就是一个拓扑排序。那么就可以直接用DFS改良求解出拓扑排序。伪代码:TOPOLOGICAL-SORTING-DFS(g)  let visited be new Array  let result be new Array  let stack be new Stack  for v equal to every vertex in g    if visited[v] == false      DFS-IMPROVE(v,visited,stack)  end  while stack.empty() == false      result.append(stack.top())      stack.pop()  end  return result时间复杂度:Θ(V+E),V表示顶点的个数,E表示边的个数另一种是贪心选择。直觉上,既然要所有边的出度顶点在入度顶点之前,可以从入度和出度角度来解决问题。可以让入度最小的排序在前,也可以让出度最大的排序在后,排序后,这个顶点的边都不会再影响问题了,可以去掉。去掉后再重新加入新的顶点,直到加入所有顶点。这个问题还有个隐含条件,挑选出、入度最小的顶点就等价于挑选出、入度为0的顶点。这是因为图必须是无环图,所以肯定存在出、入度为0的顶点,那么出、入度最小的顶点就是出、入度为0的顶点。直觉上这是一个可行的策略,细想一下,按出度最大排序和按入度为零排序是否等价。实际上是不等价的,按入度为零排序,如果出现了多个入度为零的顶点,这多个顶点排序的顺序是无关的,可以任意排序。而按出度最大排序,出现了多个入度最大的顶点,这多个顶点排序是有关的,不能任意排序。所以,只能按入度为零排序。实际上,这个想法就是贪心选择。下面以挑选入度为零的边作为贪心选择解决问题,同样地,还是先证明这个贪心选择的正确性。命题:入度为零的顶点v排序在前。假设:S为图的一个拓扑排序,l为此排序的首个顶点。证明:如果l=v,则命题得证。如果l不等于v,将l顶点从S中去除,然后加入顶点v得到新的排序S‘。因为S去除l以后l以后的排序没有变,仍为拓扑排序,v入度为零,v前面可以没有顶点,所以S’也为图的一个拓扑排序,命题得证。伪代码:TOPOLOGICAL-SORTING-GREEDY(g)  let inDegree be every verties inDegree Array  let stack be new Stack  let result be new Array  for v equal to every vertex in g    if inDegree[v] == 0      stack.push(v)  end  while stack.empty() == false    vertex v = stack.top()    stack.pop()    result.append(v)    for i equal to every vertex adjacent to v       inDegree[i] = inDegree[i] – 1      if inDegree[i] == 0        stack.push(i)    end  end  return result.reverse()时间复杂度:Θ(V+E),V表示顶点的个数,E表示边的个数强连通分量(Strongly-Connected-Components)图中的一个顶点与另一个顶点互相都有路径可以抵达,就说这两个顶点强连通。图中有多个顶点两两之间都强连通,则这多个顶点构成图的强连通分量。朴素的想法是,假如从一个顶点A可以搜索到另一个顶点B,如果从B顶点再能搜索回A顶点的话,A、B就在一个强连通分量中。不过,这样每两个顶点要进行两次DFS,复杂度肯定会很高。这里可以引入转置图(将有向边的方向翻转)的性质。这样问题就转换成了,从A顶点搜索到B顶点,将图转置后,如果再A顶点还能搜索到B顶点,A、B顶点就在一个强连通分量中。用算法表述出来就是先从A顶点DFS,然后将图转置,再从A顶点DFS,两次DFS都能搜索到B顶点的话,B顶点就与A顶点在同一个强连通分量中。然而朴素想法只能想到这里了。有多个算法被研究出来解决这个问题,下面先介绍Kosaraju算法。KosarajuKosaraju算法使用了DFS改良的性质去解决问题,想法很有趣。Kosaraju算法现将图进行DFS改良,然后将图转置,再进行DFS。第二次DFS每个顶点能够搜索到的点就是一个强连通分量。算法正确性和说明如下。通过DFS改良性质可以得出定理,一个强连通分量C如果有到达另一个强连通分量C’的路径,则C’比C先被搜索完,这个定理很明显,如果C中有路径到C’,那么根据DFS改良性质一定会先搜索到C,再搜索完C’,再搜索完C。将这个定理做定理1。定理1:一个强连通分量C如果有到达另一个强连通分量C’的路径,则C’比C先被搜索完。定理1还可以再进行推论,如果一个强连通分量C有到达另一个强连通分量C’的路径,则将图转置后,C比C’先被搜索完,这个推论也很明显,将图转置后,不存在C到C’的路径,存在C’到C的路径,而仍是先搜索C再搜索C‘,所以C比C‘先被搜索完,这个推论作为推论1。推论1:如果一个强连通分量C有到达另一个强连通分量C’的路径,则将图转置后,C比C’先被搜索完。以下为用结构归纳法对算法正确性进行证明。命题:第二次DFS每个顶点能够搜索到的点就是一个强连通分量。假设:n代表图中有多少个强连通分量。 证明:如果n=1,则第二次DFS就是搜索一遍所有顶点,命题得证。现在假设n=k时,命题成立。现证明n=k+1时,是否成立。假设搜索到第k+1个强连通分量的第一个顶点为u,u肯定能搜索到所有k+1个强连通分量的顶点。并且根据推论1,此时被转置后的图,所有从第k+1个强连通分量能到达的其他强连通分量都已经被搜索过了。所以u只能搜索到所有第k+1个强连通分量的顶点,即第二次DFS每个顶点只能够搜索到包含此顶点的强连通分量中的顶点,命题得证。伪代码:KOSARAJU-STRONGLY-CONNECTED-COMPONENTS(g)  let visited be new Array  let stack be new Stack  for v equal to every vertex in g    if visited[v] == false      DFS-IMPROVE(v,visited,stack)  end  let gt = transpose of g  for v equal to every vertex in g    visited[v] = false  end  while stack.empty() == false    vertex v = stack.top()    stack.pop()    if visited[v] == false      DFS(v,visited)      print ‘ Found a Strongly Connected Components ‘  end  DFS(v,visited)  visited[v] = true  print v  for i equal to every vertex adjacent to v    if visited[i] == false      DFS(i,visited,stack)  end时间复杂度:Θ(V+E),V表示顶点的个数,E表示边的个数Kosaraju算法需要进行两次DFS,那么可不可以只进行一次DFS,边遍历边找强连通分量?Tarjan就是这样的算法。Tarjan同样,还是要基于DFS搜索性质来思考问题。DFS创建出的深度优先搜索树会先被访问根节点再被访问子孙节点。什么时候会出现强连通分量?只有子孙节点有连通祖先节点的边的时候。如果从某个节点,其子孙节点都只有指向自己子孙节点的边的时候,这是明显没有构成强连通分量的。那么,出现了子孙节点指向其祖先节点的时候,从被指向的祖先节点一直搜索到指向的子孙节点所经过所有顶点就构成了一个强连通分量。如果出现了多个子孙节点都指向了祖先节点怎么办?最早被指向、访问的祖先节点到最晚指向、访问的子孙节点构成了“最大“的强连通分量,这才是想要找的强连通分量。如果遇到了一个指向祖先节点的子孙节点,就算构成一个强连通分量,会导致找到多个互相嵌套的强连通分量。那么,要记录访问顺序就要为每个节点设置一个被访问顺序的编号,让属于同一个强连通分量的顶点编号一致。上面讨论的是构成了一个强连通分量怎么处理,如果没有多个节点构成的强连通分量怎么处理?在搜索节点之前,为这个节点默认设置上被访问的顺序编号,这样如果没有搜索到多个节点构成的强连通分量,每个节点就是自己的强连通分量。算法表述为,从某个节点开始搜索,默认设置自己为一个强连通分量。只要节点有子孙节点,就要等待子孙节点都搜索完,再更新自己强连通分量信息。只要节点有指向祖先节点,也要更新自己的强连通分量。判断子孙节点构成的强连通分量”大“还是自己构成的强连通分量”大“,自己属于最”大“的强连通分量。也就是说,算法找出了所有顶点的所属的最“大”强连通分量。数组disc表示顶点被访问顺序的编号,数组low表示顶点所在的强连通分量编号。最后当顶点在disc和low中编号一致时,代表顶点是所在强连通分量中第一个被搜索到的顶点。此时,输出所在的强连通分量所包括的顶点。伪代码:TARJAN-STRONGLY-CONNECTED-COMPONENTS(g)  let disc be new Array  let low be new Array  let stack be new Stack  let isInStack be new Array  for i from 1 to the number of vertex in g    disc [i] = -1    low [i] = -1  end  for u from 1 to the number of vertex in g     if disc[i] != -1      TARJAN-STRONGLY-CONNECTED-COMPONENTS-UTIL(u,disc,low,stack,isInStack)  end   TARJAN-STRONGLY-CONNECTED-COMPONENTS-UTIL(u,disc,low,stack,isInStack)  let time be static  time = time + 1  disc[u] = low[u] = time  stack.push(u)  isInStack[u] = true  for v equal to every vertex adjacent to u    if disc[v] == -1      TARJAN-STRONGLY-CONNECTED-COMPONENTS-UTIL(v,disc,low,stack,isInStack)      low[u] = min(low[u],low[v])    else if isInStack[v] == true      low[u] = min(low[u],disc[v])  end  let w = 0    if low[u] == disc[u]      while stack.top() != u        w = stack.top()        isInStack[w] = false        stack.pop()        print w      end      w = stack.top()      isInStack[w] = false      stack.pop()      print w      print ‘ Found a Strongly Connected Components ‘时间复杂度:Θ(V+E),V表示顶点的个数,E表示边的个数图的割点(Articulation Points)、桥(Bridge)、双连通分量(Biconnected Components)图的割点(Articulation-Points)图的割点也叫图的关节点,定义为无向图中分割两个连通分量的点,或者说去掉这个点,图中的连通分量数增加了。可以看到如果求出了连通分量,那么不同连通分量中间的顶点就是割点。什么时候某个顶点不是这样的割点?如果这个顶点的子孙顶点有连接这个顶点祖先顶点的边,那么去掉这个顶点,这个顶点的子孙顶点和祖先顶点仍然连通。那么,寻找割点的过程就等价于寻找子孙顶点没有连接祖先顶点的顶点。这个问题的求解过程类似于Tarjan强连通分量的求解过程。不过,这个问题有个例外就是根顶点,对一般顶点的处理方式处理根顶点行得通吗?根顶点肯定没有子孙顶点指向祖先顶点,但是根顶点可以是割点。所以,根顶点需要特殊处理。根顶点什么时候是割点?当根顶点有多颗子树,且之间无法互相到达的时候。那么,存不存在根顶点有多颗子树,且之间可以互相到达?不存在,如果互相之间可以到达,那在根顶点搜索第一颗子树的时候,就会搜索到可到达的子树,就不会存在多颗子树了。所以,根顶点有多颗子树,那么这多颗子树之间一定无法互相到达。根顶点有多颗子树,且之间无法互相到达的时候就等价于根顶点有多颗子树。所以,只要根顶点有多颗子树,那么根顶点就是割点。同样地,数组disc表示顶点被访问顺序的编号,数组low表示顶点所在的强连通分量编号。数组parent找出根顶点。伪代码:ARTICULATION-POINTS(g)  let disc be new Array  let low be new Array  let result be new Array  let parent be new Array  let visited be new Array  for i from 1 to the number of vertex in g    result [i] = false    visited [i] = false    parent [i] = -1  end  for u from 1 to the number of vertex in g     if visited[i] == false      ARTICULATION-POINTS-UTIL(u,disc,low,result,parent,visited)  end  for i from 1 to the number if vertex in g    if result[i] == true      print ‘ Found a Articulation Points i ‘  end   ARTICULATION-POINTS-UTIL(u,disc,low,result,parent,visited)  let time be static  time = time + 1  let children = 0  disc[u] = low[u] = time  visited[u] = true  for v equal to every vertex adjacent to u    if visited[v] == false      children = children + 1      parent[v] = u      ARTICULATION-POINTS-UTIL(u,disc,low,result,parent,visited)      low[u] = min(low[u],low[v])      if parnet[u] == -1 and children > 1        result[u] = true      if parent[u] != -1 and low[v] >= disc[u]        result[u] = true    else if v != parent[u]      low[u] = min(low[u],disc[v])  end时间复杂度:Θ(V+E),V表示顶点的个数,E表示边的个数桥(Bridge)桥定义为一条边,且去掉这个边,图中的连通分量数增加了。类似于寻找割点,寻找桥就是寻找这样一条,一端的顶点的子孙顶点没有连接这个顶点和其祖先顶点的边。求解过程和求割点基本一致。伪代码:BRIDGE(g)  let disc be new Array  let low be new Array  let parent be new Array  let visited be new Array  for i from 1 to the number of vertex in g    visited [i] = false    parent [i] = -1  end  for u from 1 to the number of vertex in g     if visited[i] == false      BRIDGE-UTIL(u,disc,low,parent,visited)  end   BRIDGE-UTIL(u,disc,low,parent,visited)  let time be static  time = time + 1  disc[u] = low[u] = time  for v equal to every vertex adjacent to u    if visited[v] == false      parent[v] = u      BRIDGE-UTIL(u,disc,low,parent,visited)      low[u] = min(low[u],low[v])      if low[v] > disc[u]        print ‘ Found a Bridge u->v ‘    else if v != parent[u]      low[u] = min(low[u],disc[v])  end时间复杂度:Θ(V+E),V表示顶点的个数,E表示边的个数双连通分量(Biconnected-Components)双连通图定义为没有割点的图。双连通图的极大子图就为双连通分量。双连通分量就是在割点分割成多个连通分量处,共享割点。也就是说双连通分量是去掉割点后构成的连通分量,加上割点和到达割点的边。可以看出,双连通分量可分为不含有割点、一个割点、两个割点三种情况。对于不含有割点,说明图为双连通图。对于含有一个割点,可能为初始搜索的顶点到第一个割点之间的边构成的双连通分量,可能为遇到一个割点后到不再遇到割点之间的边构成双连通分量。对于含有两个割点,两个割点之间的边构成了一个双连通分量。求解此问题,只要在求割点的算法上做更改就可以了。按照求割点的算法求解割点,找到一个割点,输出找到的边,然后删除找到的边的记录,再去搜索下一个割点。每搜索完图某个顶点的可达顶点,输出找到的边。这样就涵盖了所有的情况。伪代码:BICONNECTED-COMPONENTS(g)  let disc be new Array  let low be new Array  let stack be new Stack  let parent be new Array  for i from 1 to the number of vertex in g    disc [i] = -1    low [i] = -1    parent [i] = -1  end  for u from 1 to the number of vertex in g     if disc[i] == -1      BICONNECTED-COMPONENTS-UTIL(u,disc,low,stack,parent)    let flag = flase    while stack.empty() == false      flag = true      print stack.top().src -> stack.top().des      stack.pop()    end    if flag == true      print ‘ Found a Bioconnected-Components ‘  end   BICONNECTED-COMPONENTS-UTIL(u,disc,low,stack,parent)  let time be static  time = time + 1  let children = 0  disc[u] = low[u] = time  for v equal to every vertex adjacent to u    if disc[v] == -1      children = children + 1      parent[v] = u      stack.push(u->v)      BICONNECTED-COMPONENTS-UTIL(u,disc,low,stack,parent)      low[u] = min(low[u],low[v])      if (parnet[u] == -1 and children > 1) or (parent[u] != -1 and low[v] >= disc[u])        while stack.top().src != u or stack.top().des != v          print stack.top().src -> stack.top().des          stack.pop()        end        print stack.top().src -> stack.top().des        stack.pop()        print ‘ Found a Bioconnected-Components ‘    else if v != parent[u] and disc[v] < low[u]      low[u] = min(low[u],disc[v])      stack.push(u->v)  end时间复杂度:Θ(V+E),V表示顶点的个数,E表示边的个数最小生成树(Minimum-Spanning-Tree)生成树是指,在一个连通、无向、有权的图中,所有顶点构成的一颗树。图中可以有多颗生成树,而生成树的代价就是树中所有边的权重的和。最小生成树就是生成树中代价最小的。朴素的想法就是从图中选择最小权重的边,直到生成一颗树。看通用的算法之前,同样要讨论一下最小生成树的性质。对于一个连通、无向、有权图中,一定有最小生成树。如果图不包含最小生成树的任意一条边,那么图就是不连通的了,这与已知连通图不符,所以图必包含最小生成树。假设,A为某个最小生成树的子集(任意一个顶点都是最小生成树的子集)。那么,为A一直添加对的边,A最后就会成为一颗最小生成树。那么最小生成树问题就转换成为了,一直找到对的边,直到成为一颗最小生成树。这个对的边可以叫做安全边。安全边如何寻找显然就成了解决这个问题的关键点。再假设,图中所有顶点为V,将所有顶点切割成两个部分S和V减去S。所有连接这两个部分的边,很形象的叫做横跨切割,这些边横跨了两个部分,成为这两个部分的桥梁。这里还有个问题,如何切割?使A不包含横跨切割。这样的切割有多种切法,切割后,横跨切割的最小代价边就为A的安全边。将这个作为定理1。定理1:存在这样一个将所有顶点分成两个部分的切割,且使某个最小生成树子集A不包含横跨切割。则横跨此切割的最小代价边,就是A的安全边。以下为此定理的证明,这个定理的基础实际上是连通性。命题:横跨切割的最小代价边为A的安全边。假设:横跨切割后的最小代价边为x,有最小生成树T包含A,但是不包含x。证明:既然T不包含x,那么T必须包含另一条连接x两端顶点的路径,这条路径上又必须有条边横跨切割。假设这条边为y。T将y减去后,x两端的顶点就无法互相到达。这时如果再加上x,那么x两端的顶点又可以互相到达,并且构造了另一颗生成树T’。可以看到,x的代价小于或等于y的代价,那么T‘的代价也小于或等于T的代价,那么T’也就是一颗最小生成树。那么x既不在A中,x又在一颗包含A的最小生成树中。命题得证。可以看到这个证明过程使用的就是经常拿来证明贪心选择的技巧,也就是说最小生成树问题符合贪心算法的特征,也就解释了为什么下面将要提到的两个算法都是贪心算法。定理1还可以进行推论,既然切割有多种方法,那可不可以对A和其余的顶点进行切割,设B为包括A和所有顶点构成的一个森林,C是其中的一个连通分量,那么C连接其他的连通分量的最小代价边是A的安全边。这个推论很好证明,因为A是B中的一个或者多个连通分量,如果按照C去切割图分成C和B减去C,不可能切割A,即A中必定不包含横跨切割。那么,横跨这个切割的最小代价边就是安全边,即C连接其他连通分量的最小代价边,推论成立。将这个推论作为推论1。推论1:某个最小生成树子集A和其他顶点构成的森林中,任意一个连通分量连接其他连通分量的最小代价边都为A的安全边。如果从所有不在A中的边选择最小代价的边,这个边一定连接着某个连通分量,这个推论也就将选安全边的范围拓展到任意一条不在A中的边。这个推论正好可以证明朴素想法的正确性。接下来看一下最小生成树的三个通用的算法Kruskal、Prime、Boruvka。Kruskal朴素想法和Kruskal已经很接近了。Kruskal算法做的就是一直选择代价最小的边,不过,如果选择这个边后,无生成最小生成树,而生成图了怎么办?Kruskal比朴素想法巧的地方就是不选择会成环的边。Kruskal常用的检查是否成环的数据结构是UnionFind(并查集),UnionFind有个操作,一个是Find检查元素所在集合的编号,Union将两个元素合并成一个集合。KRUSKAL(g)  let edges be all the edges of g  sort(edges)  let uf be new UnionFind  let e = 0  let i = 0  let result be new Array  while e < edges.length()    let edge = edges[i]    i = i + 1    if uf.find(edge.src) != uf.find(edge.des)      result.append(edge)      e = e + 1      uf.union(edge.src,edge.des)  end  return resultV表示顶点的个数,E表示边的个数,排序E个边加上E次UnionFind操作时间复杂度:O(Elog2E+Elog2V)Prim有了推论1,Prim算法的正确性理解起来就很简单了,一直只对最小生成树子集进行切割,然后选择出最小生成树子集与其他连通分量的最小代价边就OK了。Prim算法就是一直选择最小生成树子集与其他顶点连接的最小代价边。Prim算法维持这样一个最小堆,存储最小生成树子集以外的顶点,与最小生成树子集临接的顶点的权重是其临接边的值,其余的最小堆中的顶点权重都是无穷。Prim算法初始将起始顶点在最小堆中的权重置为0,其余的顶点置为无穷。然后从最小堆中一直取权重最小的顶点,即选择最小代价边加入最小生成树,如果取出的顶点的临接顶点不在最小生成树中,且这个临接顶点在最小堆中的权重比边大,则更新临接顶点在最小堆的权重,直到从最小堆中取出所有的顶点,就得到了一颗最小生成树。伪代码:PRIM(g,s)  let heap be new MinHeap  let result be new Array  for i from 1 to the number of vertex in g    let vertex be new Vertex(i)    vertex.weight = INT_MAX    heap.insert(vertex)  end  heap.decrease(s,0)  while heap.empty() == false    vertex v = heap.top()    for u equal to every vertex adjacent to v      if heap.isNotInHeap(u) and v->u < heap.getWeightOfNode(u)        result[u] = v        heap.decrease(u,v->u)    end    end  return resultV表示顶点的个数,E表示边的个数,对V个顶点和E条边进行decrease操作时间复杂度:O(Elog2V+Vlog2V)BoruvkaKruskal是根据所有边中最小代价边的一端的连通分量分割,Prim根据最小生成子树的子集分割,Boruvka根据所有的连通分量分割,实际上都是基于推论1。Boruvka算法将所有连通分量与其他连通分量的最小代价边选择出来,然后将这些边中未加入最小生成树子集的加进去,一直到生成最小生成树。Boruvka算法同样使用了UnionFind去记录连通分量,用cheapest数组记录连通分量与其他连通分量连接的最小代价边的编号。伪代码:Boruvka(g)  let uf be new UnionFind  let cheapest be new Array  let edges be all the edge of g  let numTree = the number of vertex in g  let result be new Array  for i from 1 to number of vertex in g    cheapest[i] = -1  end  while numTree > 0    for i from 1 to the number of edge in g      let set1 = uf.find(edges[i].src)      let set2 = uf.find(edges[i].des)      if set1 == set2        continue      if cheapest[se1] == -1 or edges[cheapest[set1]].weight > edges[i].weight        cheapest[set1] = i      if cheapest[set2] == -1 or edges[cheapest[set2]].weight > edges[i].weight        cheapest[set2] = i    end    for i from 1 to the number of vertex in g      if cheapest[i] != -1        let set1 = uf.find(edges[cheapest[i]].src)        let set2 = uf.find(edges[cheapest[i]].des)        if set1 == set2          continue        result[edges[cheapest[i]].src] = edges[cheapest[i]].des         uf.union(set1,set2)        numTree = numTree – 1    end  end  return result2018巴菲特股东大会暨美国资产配置投资巅峰考察项目价值投资盛典——巴菲特股东大会美国顶级私人俱乐部耶鲁俱乐部内倾听中美金融行业座谈中美风险投资峰会“金融期货之父”、“CME集团终身荣誉主席”利奥·梅拉梅德演讲全球顶级对冲基金参访国际顶级衍生品交易所CBOE/CBOT参访 参访顶级投资银行/资产管理公司,倾听资产管理与家族理财讲座 地点:芝加哥 • 奥马哈 • 纽约时间:2018年5月1日—11日(报名截止日期:4月1日)报名电话/微信:18516600808 时间复杂度:O(Elog2V),V表示顶点的个数,E表示边的个数单源最短路径(Single-Source-Shortest-Paths)给出一张连通、有向图,找出一个顶点s到其他所有顶点的最短路径。可以看到,如果图中存在负环,不存在最短路径。因为存在负环就可以无限循环负环得到更短的路径。看通用的算法之前,同样要讨论一下问题的性质。假设,存在一条顶点s到顶点v的最短路径,i、j为路径上的两个顶点。那么在这条s到v最短路径上,i到j的路径是否是i到j的最短路径?是的,如果存在i到j的更短路径,就等价于存在一条s到v的更短路径,这与假设不符。也就是说,如果存在一条从s到v的最短路径,这条路径上任意两个顶点的路径都是这两个顶点的最短路径。那么,这个问题就具有动态规划的状态转移特征。解决此问题的朴素想法就是求出所有顶点s到顶点v的路径,然后取最小值。那么要是实现这个步骤,就要为v点存储一个估计值d,并设起始为无穷,如果有到达v的路径小于这个估计值,更新这个估计值,并且记录v的现阶段最小路径。这步操作叫做松弛操作(relax)。假设u为小于估计值路径上的上个顶点。RELAX(u,v,result)  if v.d > u.d + u->v    v.d = u.d + u->v    result[v] = u那么,算法要做的就是一直松弛到达v顶点的路径,从无穷直到最小路径。可以看到,所有的求最短路径的算法都要基于这个操作去求解,不同的算法只能就是执行这个操作顺序不同或者次数不同。那么松弛操作会不会出问题,会不会松弛操作做过头了,将v的估计值松弛的比最短路径还小?不会,在算法运行期间,对于所有顶点,一直对顶点进行松弛操作,顶点的预估值不会低于最短路径。以下用结构证明法证明。假设:u代表任意一个连接v的顶点,s->v代表s到v的边,s~>v代表s到v的最短路径。命题:对到达v的所有路径松弛操作有v.d >= s~>v证明:对于v=s的情况,v.d=0 s~v即s~s也为0,命题得证假设对于顶点u,u.d >= s~>u成立。有s~>v <= s~>u + u->v,因为s~>v是一条最短路径,对于任意一条经过u到达v的路径,必小于最短路径。s~>v <= u.d + u->v因为经过松弛操作v.d = u.d + u->v,所以v.d >= s~>v,命题得证。松弛操作只能同时对一条边起作用。所以,最短路径长为n的路径,只能从最短路径长为n-1的路径,转移过来。这里就得到了这个问题最重要的性质,单源最短路径问题是个最短路径每次递增一的动态规划问题。单源最短路径性质:此问题是个最短路径每次长度递增一的动态规划问题。在介绍通用算法之前,先介绍一种专对于有向无环图很巧的算法。有向无环图单源最短路径(DAG-Shortest-Paths)对于有向无环图,可以先对图进行拓扑排序,然后按拓扑排序的顺序对每个顶点作为出度的边进行松弛操作,就得到了问题的一个解。以下证明算法的正确性。假设v为对图拓扑排序后的某个顶点。当对v作为出度的边进行松弛操作前,所有能到达v的路径都已经做过了松弛操作,此时已经找到了到达v的最短路径。那么,当对所有顶点作为出度的边进行松弛操作后,所有顶点的最短路径就已经被找到。算法的正确性得到证明。伪代码:DAG-SHORTEST-PATHS(g)  let sorted = TOPOLOGICAL-SORTING-GREEDY(g)  let result be new Array  for u equal to every vertex in sorted    for v equal to every vertex adjacent to u       if v.d > u.d + u->v        RELAX(u,v,result)    end  end  return result时间复杂度:Θ(V+E),V表示顶点的个数,E表示边的个数接下来介绍两种通用的算法Bellman-Ford和Dijkstra。Bellman-Ford和Dijkstra有什么联系呢?Bellman-Ford可以解决有负权重图的单源最短路径问题,并且可以侦测出图中是否存在负环。Dijkstra只能解决没有负权重边的图的单源最短路径问题。Bellman-Ford是进行必须的最少次数的松弛操作。而Dijkstra发现,只要没有负权重边,还能进行更少的松弛操作解决问题。Bellman-FordBellman-Ford是最通用的解决单源最短路径算法,初始将所有顶点估计值设为无穷,将源点设为零。然后,对所有边进行松弛操作,这个步骤作为内部循环。再将这个步骤做图的顶点个数减一次。Bellman-Ford的正确性不难证明,可以看到随着Bellman-Ford算法内部的循环,Bellman-Ford找到的最短路径的长度也在增加。首先证明内部循环在循环到第n次时,找到了所有最短路径长为n的路径。我们用结构证明法。在以下证明中,可以看出Bellman-Ford虽然不是经典的动态规划算法,但是其原理是基于这个问题的动态规划性质的。证明:对于n=0时,最短路径为0,命题得证。 假设所有最短路径为n-1的路径已经被找到。因为根据单源最短路径的动态规划性质,最短路径长为n的路径,可以从最短路径长为n-1的路径,转移过来的。因为Bellman-Ford算法会对所有的边进行松弛操作。所以,所有长为n的最短路径会从相应的长为n-1的最短路径找到。命题得证。只要最短路径上不存在负环,那么所有最短路径就必小于V-1。所以,Bellman-Ford内部循环执行V-1次,能找到最长的最短路径,也就是能找到所有的最短路径。Bellman-Ford正确性证毕。Bellman-Ford实现也很简单,这里添加一个flag位,提前省去不必要的循环。伪代码:BELLMAN-FORD(g,s)  let edges be all the edge of g  let result be new Array  for i from 1 to the number of vertex of g    result[i] = INT_MAX  end  result[s] = 0  for i from 1 to the number of vertex of g minus 1    let flag = false    for j from 1 to the numnber of edge of g      let edge = edges[j]      if result[edge.src] != INT_MAX and edge.src > edge.des + edge.weight        RELAX(u,v,result)        flag = true    end    if flag == false      break  end  return result时间复杂度:O(V⋅E),V表示顶点的个数,E表示边的个数 为什么Bellman-Ford算法可以侦测出有负环?算法完成后再对图的所有边进行一次松弛操作,如果最短路径求得的值改变了,就是出现了负环。这个证明看一下松弛操作的定义就行了。根据松弛操作的性质,顶点的估计在等于最短路径后不会再改变了,如果改变了就是出现了负环,从而没有得到最短路径。DijkstraDijkstra是个贪心算法,朴素的想一下,用贪心算法怎么解决问题。既然没有负权边,选出当前阶段最短的路径,这个路径就应该是到达这个路径终点的最短路径。Dijkstra就是这样一个贪心算法,初始将所有顶点估计值设为无穷,将源点设为零。维护一个集合S代表已经找到的最短路径顶点,然后从集合S外所有顶点,选择有最小的估计值的顶点加入到集合中,然后再对这个顶点在S中的临接顶点做松弛操作,一直到所有顶点都在集合S中。Dijkstra的贪心选择使用简单的反证法就可以证出。假设,现阶段要选从s到某个顶点u的路径作为最短路径加入到集合S中,并且这个选择是错误的。有另一条最短路径从s到达u,那么这条路径和原选择的路径肯定不一致,经过不同的顶点,假设这条最短路径上到达u的前一个顶点为k,既然这是一条从s到达u的最短路径,那么从s到k肯定比从s到v小,那么算法会先选择从s到k,然后选择最短路径,不会选择假设的路径,这与假设矛盾,假设不成立,贪心选择正确性得证。以下是算法导论上的证明,尝试从实际发生了什么去证明正确性,我认为有点clumsy(笨重),核心的想法其实和上面简单的反证法一致。命题:选择有最小估计值的顶点加入集合S,那么这个估计值必定是这个顶点的最小路径。 同样使用反证法来证,并且关注已经选择了最小预估值的顶点但还没加入顶点S时的情形。假如选择了顶点u,这时,将从s到u作为最小条路径加入到S中,分为两种情况。情况一,选择的从s到u的路径就是最短路径,那么命题已经得证。情况二,选择的从s到u的路径不是最短路径,存在u.d>s~>u。这种情况下,可以找到一个顶点x,使得x在集合S中,并在对x进行松弛操作后,找到另一个顶点y,使得y不在集合中且y的估计值就等于s到y的最短路径即s~>y。x可以与s重合,y可以与u重合。那么有y.d = s~>y因为从s到y是从s到u的子路径,有s~>u >= s~>y得出s~>u >= y.d因为选择了顶点u,有u.d <= y.d得出s~>u >= u.d这与假设矛盾,所以假设不成立,命题得证。实现和时间复杂度与Prim算法类似,集合S用最小堆实现。伪代码:DIJKSTRA(g,s)  let heap be new MinHeap  let result be new Array  for i from 1 to the number of vertex in g    let vertex be new Vertex(i)    vertex.d = INT_MAX    heap.insert(vertex)  end  heap.decrease(s,0)  while heap.empty() == false    vertex u = heap.top()    for v equal to every vertex adjacent to u      if heap.isNotInHeap(v) and u.d v.d > u.d + u->v        RELAX(u,v,result)        heap.decrease(v,v.d)    end    end  return resultV表示顶点的个数,E表示边的个数,对V个顶点和E条边进行decrease操作时间复杂度:O(Elog2V+Vlog2V)可以看到,如果运气好,Bellman-Ford不需要V次循环就可以找到所有最短路径,但是运气不好,Bellman-Ford要经过最少V次循环,这就是上文说到的,Bellman-Ford是进行必须的最少次数的松弛操作。而如果不存在负权重边,Dijkstra可以进行更少次的松弛操作,至多对每个顶点连接的边进行一次松弛操作就可以了,Bellman-Ford与Dijkstra的联系实际上就是动态规划与贪心算法的联系。Bellman-Ford和Dijkstra算法本质都是单源最短路径性质。全对最短路径(All-Pair-Shortest-Paths)全对最短路径就是将图中任意两点之间的最短路径求出来,输出一个矩阵,每个元素代表横坐标作为标号的顶点到纵坐标作为标号的顶点的最短路径。当然,可以对所有顶点运行一次Bellman-Ford算法得出结果,不过这样的复杂度就太高了。尝试去找到更好的算法解决这个问题。既然单源最短路径是个最短路径递增一的动态规划问题,尝试对全对最短路径使用这种性质,然后看看能不能降低复杂度。假设有n个顶点,dpij代表从顶点i到顶点j的最短路径,假设这条最短路径长为m,且k为任意顶点。那么,根据这个问题的动态规划状态转移特征,dpij是由长度为m−1的dpik加上k->j转移过来的。看来即使在单源最短路径动态规划的性质上进行求解,复杂度仍然很高。尝试不从最短路径长度角度考虑动态规划,从顶点角度去考虑动态规划,引出一个通用的算法Floyd-Warshall。Floyd-Warshall好,从顶点的角度去思考动态规划。从顶点i到顶点j要经过其他顶点,假设经过的顶点为k。然后根据解动态规划的经验,猜想dpij与dpik和dpkj怎么能沾到边?假设从i到j只需要经过[1,k]集合中的顶点。如果从i到j经过k,那么dpik就代表从i到k的最短路径,dpkj就代表从k到j的最短路径,dpij就等于从dpik和dpkj转移过去,而dpik和dpkj都不经过k,都只需要经过[1,k-1]集合中的顶点。如果从i到j不经过k,dpij就等于从i到j只需要经过[i,k-1]集合中的顶点时的dpij。伪代码:FLYOD-WARSHALL(g)  let dp be new Table  for i from 1 to the number of vertex in g    for j from 1 to the number of vertex in g      dp[i][j] = g[i][j]    end  end  for k from 1 to the number of vertex in g    for i from 1 to the number of vertex in g      for j from 1 to the number of vertex in g        if dp[i][k] + dp[k][j] < dp[i][j]          dp[i][j] = dp[i][k] + dp[k][j]      end    end  end  return dp时间复杂度:Θ(V3),$V$表示顶点的个数Johnson对于稀疏图的话,还有办法降低算法复杂度。直观上看,对于稀疏图,对每个顶点运行Dijkstra算法是快过Floyd-Warshall算法的,但是这样要求图中不能有负权边。那么,可不可以将有负权边的图转化为没有负权边的图。Johnson就是这样一个算法,将所有的边进行重新赋权重(reweight),然后再对所有顶点运行Dijkstra算法。那怎么进行重新赋权重呢?朴素想法是找出所有的边中最小的值,然后所有边增加这个值。很可惜,这样不行。考虑这样一个情况,顶点a到b的最短路径有3条边,最短路径为4。有a到b另一条路径只经过一条边,路径权重为5。如果对所有边增加1权重,那么顶点a到顶点b的最短路径就改变了。重新赋权重改变了最短路径是明显有问题的。可以看出重新赋权重有两点要求:1.对起点和终点相同的路径改变同样的权重,保持原来的最短路径结果。2.所有边重新赋权以后不存在负权边。Johnson算法先对顶点重新赋值,然后将边的重新赋值由两端顶点的重新赋的值得出。假设u和v为相邻的两个顶点。这样定义w’()函数以后,对路径重新赋的值影响的只有起点和终点两个顶点,中间顶点重赋的值都被消掉了。等价于保持原来的最短路径结果。那么,怎么保证第二点?Johnson算法会为图增加一个顶点s,然后对图运行一次Bellman-Ford算法。得出新增的顶点s与所有原顶点的最短路径,这个最短路径就是h()数的值。而且在运行Bellman-Ford算法的时候,正好可以侦测出图中是否有负环。伪代码:JOHNSON(g)  let s be new Vertex  g.insert(s)  if BELLMAN-FORD(g,s) == flase    there is a negative cycle in graph  else    for v equal to every vertex in g      h(v) = min(v~>s)    end    for (u,v) equal to every edge in graph      w’(u,v) = w(u,v) + h(u) – h(v)    end    let result be new Table    for u equal to every vertex in g      DIJSKTRA(g,u)      for v equal to every vertex in g        result[u][v] = min(u~>v) + h(v) – h(u)      end    end  return result时间复杂度:O(V⋅Elog2V+V2log2V+V⋅E),V表示顶点的个数,E表示边的个数证明了这么多的算法正确性,可以看到,证明是有技巧的,常用的只有三个方法,反证法、结构归纳法、Cut-And-Paste法。经过图论的探讨,便可以理解算法与数学之间紧密的联系。解决问题要对问题本身的特征、属性进行总结或者提炼。有时要对问题进行相应的转化。然后根据问题的特征、性质推导出定理。再将定理拓展,提出推论。最后,算法就在灯火阑珊处了。这感觉就像,不是你找到了合适的算法。而是合适的算法找到了你。 编辑:Gemini来源:Mr.Riddler’s Puzzle 【宽客网络课堂】性价比最高的课程:金融量化分析以Matlab为工具咨询电话/微信:18516600808 via: https://mp.weixin.qq.com/s?__biz=MzA3MDI3ODQxOA==&mid=2651248112&idx=3&sn=932c50d29f3c3347ebcb9ae31acae762&chksm=84cd398db3bab09b529d31ff3c1ab519d082167e367d5a972ff371093fd7992f0facf93b6c2b&scene=27#wechat_redirect

 

爱可可-爱生活   网页版 2018-03-20 15:25
会议活动 算法 ICML 会议 神经网络
【现代神经网络标定】《On Calibration of Modern Neural Networks(ICML 2017)》by Geoff Pleiss http://t.cn/RnfRWY3

 

ChatbotsChina   网页版 2018-03-20 15:13
深度学习 算法 神经网络
新型循环神经网络IndRNN:可构建更长更深的RNN(附GitHub实现)@机器之心Synced http://t.cn/RnVCvsl

 

刘康_自动化所   网页版 2018-03-20 10:28
会议活动 知识工程 会议 语言学 知识库
全国知识图谱与语义计算大会(CCKS-2018)由中国中文信息学会语言与知识计算专业委员会组织和承办,今年将在天津南开大学召开,有想赞助本次大会的可以与本人联系。赞助方案见:http://t.cn/Rnf77fZ

 

人工智能机器人   网页版 2018-03-20 08:03
人工智能进入国家战略,彰显顶层设计之高瞻远瞩。无论是提高创新能力、信息化与工业化深度融合,还是推动重点领域突破发展、提高制造业国际化发展水平,都离不开人工智能,人工智能是智能制造不可或缺的核心技术 http://t.cn/RnVK2SD

 

爱可可-爱生活   网页版 2018-03-20 06:12
深度学习 算法 论文 神经网络
《Studying Invariances of Trained Convolutional Neural Networks》C Bunne, L Rahmann, T Wolf [ETH Zurich] (2018) http://t.cn/RnVWOGv view:http://t.cn/RnVWOGP

 

爱可可-爱生活   网页版 2018-03-19 08:20
深度学习 自然语言处理 Michael Petrochuk 代码
【PyTorch文本工具库/数据集】’ PyTorch-NLP – Text utilities and datasets for PyTorch’ by Michael Petrochuk GitHub: http://t.cn/Rn5YKWe

 

回复