概率论知识点树状图(想了解概率图模型)
概率论知识点树状图(想了解概率图模型)
2024-11-08 03:29:04  作者:苏更生  网址:https://m.xinb2b.cn/tech/wkl242999.html

选自Dev To

作者:vaidehijoshi等

机器之心编译

参与:蒋思源、李泽南

图论一直是数学里十分重要的学科,其以图为研究对象,通常用来描述某些事物之间的某种特定关系。而在机器学习的世界里,我们希望从数据中挖掘出隐含信息或模型。因此,如果我们将图中的结点作为随机变量,连接作为相关性关系,那么我们就能构造出图模型,并期望解决这一问题。本文将为构造该模型提供最基础的概念。

我们都知道机器学习里的决策树,其可以表示为给定特征条件下类的条件概率分布。并且我们知道决策树由结点和有向边组成,结点又由表示特征的内部结点和表示类的叶结点构成。而通常决策树的学习又包括了特征的选择、决策树的生成和决策树的剪枝。那么这种树型算法又是来自哪呢?其实树型只是图的一个小分支,而接下来我们将进一步了解源于离散数学并十分重要的分支:图论(graph theory)。

如果这是你第一次涉足关于图论的内容,那么本篇文章将会给你一个清晰的概念。同时也希望本文能将图论的思想、基本模型阐述清楚,因此不论是对以后的机器学习模型构建还是概率图模型的理解都能提供一定的助力。

而通过图,所有的这些限制好像都突然消失了。因为图是没有任何「根结点」、「叶节点」和「单向边」等这些概念的,所以图中的结点可以连接多个子结点也可以有多个父结点,路径也可以是有向流或者无向边。或者如果想要图更加复杂一点,也可以采用有向流和无向边的组合,但是本文暂时并不会关注这些复杂系统。

有向图和无向图

现在我们已经知道图确实打破了构造树型的所有规则。但每一个图都必须遵守一个基本原则:即图有且至少有一个单结点。就像树型至少需要一个根结点才可以看作是「树」,图也至少需要一个单结点以便可以看作是「图」。只有一个结点的图通常称为「单例图」,基本上我们不会使用这种单例图处理任务。

通常能进行运算处理的图都是更复杂一些的图,但是不要太担心,本文所描述的图都不会太复杂,不过有些图真的是超级复杂的。

首先我们会探讨一下很容易辨认和理解的两种图:有向图(directed graphs)和无向图(undirected graphs)。这两种图在图论(graph theory)探讨的问题中十分常见。

在图中,结点和结点之间的连接并没有确切的规则,边(有时候也称为链接)能以任何方式连接结点。


不同类型的边或路径对定义和识别图时非常重要。边的类型实际上是图之间最大、最明显的区别之一。大多数情况下(只有一种例外),图会有两种类型的边:即具有方向或流向的边和不具有方向或流动的边。我们将其称为有向边(directed edges)和无向边(undirected edges)。

在有向边中,两个结点以特定的方式连接。如下图结点 A 连接结点 B 的方式所示,有向边规定了两个结点之间只有单一的方向,即只能从起始结点(origin)沿特定方向到目标结点(destination),永远不能反过来从目标结点到起始结点。这种类型的有向边在图论问题中十分常见。


现在,我们再介绍一下与有向边完全不同的无向边。在无向边(undirected edge)里,可通过的路径是双向的。也即两个结点之间的路径是双向互通的,起始结点和目标结点并没有固定。

这种差异是十分重要的,因为图中的边确定了图的类型。如果图中所有的边都是有向边,那么该图就是有向图(directed graph)。如果图所有的边都是无向边,那么该图就是无向图(undirected graph)。


以上所描述的图看起来很有结构性,但也许我们更应该关心两件事情:首先具体是什么条件或事件填充了图,其次我们具体要关注图的什么信息?

轻轻地:我们来到了图的王国

计算机科学喜欢借鉴其他学科。具体来说是喜欢借鉴逻辑学和数学的许多概念。而图论也是一样,其最开始就是数学的一个分支,且以图为研究对象,图论经常是研究顶点和边组成图的数学理论和方法。而我们所熟悉的图数据结构或树型算法等计算机概念实际上都来自于数学,而对图的研究就是图论(graph theory)。

在数学中,图是一种正式表征网络的结构,其基本上是所有互连对象的集合。

事实证明,当计算机科学家将图论应用于代码(创造出图数据结构或树型算法等)时,那些理论并没有改变多少。所以本文描述和实现图的术语就是在数学图论中的确切术语。

在数学术语中,我们将图描述为有序对(ordered pairs)。还记得以前学过的函数,它的定义就是在二维坐标轴上分布的有序对(x,y)集合。图也是使用类似的定义,只不过使用图的结点(vertices)v 和边(edges)e 代替 x 和 y。

因此,图的正式数学定义即为:G=(V,E)


但是问题来了,如果我们的图有多个结点和多条边怎么办,实际上有多个结点通常就会有多条边,那么这种情况又该怎么定义图呢。

实际上上述定义式并不会失效,因为有序对(V,E)实际上是由两组对象组成:一组结点,一组边。

现在广义的图定义变得更加有意义,但如果能有一个实例来说明的话,这个概念就会比较好理解,所以下图是我们使用 8 个结点,12 条边组成的一个无向图,我们会详细解释该图是如何用数学正式定义。


那么上图那个例子到底说了些什么。

我们将有序对记为(V,E),但因为每一项都是一个对象,所以我们必须把这些项写出来。V 已经定义为八个结点的无序集,而「无序」这一概念在这里非常重要。因为图与树型不同,其结点没有层次结构。因此排序并不重要,我们也不需要对它们进行排序。

我们还须将 E 定义为包含所有边的项。同样,边这一对象也是无序的。原因就在于图的边是无向边,它没有固定的流向或方向,也就是没有固定的起始节点和目标节点,所以每条边都是无序地。

当然,无向图的「无序」这一特性可能会引起一些疑惑,但有向图又有什么性质呢?下面是另一个案例,该图是由三个结点和三条有向边组成的有向图。


在有向图中,定义结点的方式和无向图中是一样的,但有向边和无向边的定义是不一样的。在有向图中,边的对象定义为有序对(使用圆括弧表示),因为这种情况下,边的方向十分重要。因为在有向图中,边只能是从起始结点到目标结点,所以边必须进行排序,从而定义 E 中有序对前一个元素为起始结点,后一个元素为目标结点。

所以以上就是我们如何定义一个图,但是在定义图之后,我们什么时候才能实际应用图呢。下面我们将一起来了解一下图的应用和计算。

超级社交图

图其实就在我们身边,只是我们不了解而已。

事实上,你在阅读这篇文章的时候,你就是处于一张图中。网络就是巨大的图结构,每个终端是一个结点,而互联网就是网络的边。网页也是,当我们点击网站并在 URL 之间来回浏览时,我们就是在图中浏览。有的网页之间是无向边,可以在两个网页之间来回切换,而有的是有向边,只能从一个网页转到另一个。

现在,我们使用一个更加生动的案例,以说明图与日常的交互:社交网络。

微信是一个庞大的社交网络,它也是一种图。如果我们能更多地去思考它实际的功能,那么我们可以更好地理解怎样定义和确定图的类型是什么。在微信上,如果我希望成为你的朋友,那么我需要添加你为好友,且你必须接受我的请求。在你不是我的微信好友情况下,我也会不是你的微信好友。两个用户之间的关系(图中的结点和边)是双向的。其没有起始节点和目标节点这一概念。

那你现在能判断微信的图是什么类型了么。


因此微信就是一种大型无向图,用户之间可以同时相互传递信息。

但另外一种社交网络微博却是有向图,因为在用户发布微博时,博文这一信息会在同时间点由用户向粉丝发送,这一过程是有方向不可逆的。

在了解了图论的基础概念和定义表达式后,或许我们可以进一步窥探一些概率图模型的重要思想。

机器学习的一个核心任务是从观测到的数据中挖掘隐含的知识,而概率图模型是实现这一任务的重要手段。概率图模型巧妙地结合了图论和概率论。从图论的角度来说,概率图模型就是一个包含结点与边的图。结点可以分为两类:隐含结点和观测结点。边可以分为有向边或无向边。从概率论的角度来看,概率图模型是一个概率分布,图中的结点对应于随机变量,边对应于随机变量的相关性关系。给定一个实际问题,我们通常会观测到一些数据,并且希望能够挖掘出隐含在数据中的知识。那么怎样才能使用概率图模型挖掘这些隐藏知识呢?通常情况下我们会构建一个图:用观测结点表示观测到的数据,用隐含结点表示潜在的知识,用边来描述知识与数据的相互关系,最后获得一个概率分布。给定概率分布之后,通过进行两个任务获取知识:即推断 (给定观测结点,推断隐含结点的后验分布)和学习 (学习概率分布的参数)。

基本的图模型可以大致分为两个类别:贝叶斯网络 (Bayesian Network) 和马尔可夫随机场 (Markov Random Field)。它们的主要区别在于采用不同类型的图来表达变量之间的关系:贝叶斯网络采用有向无环图 (Directed Acyclic Graph) 来表达因果关系,马尔可夫随机场则采用无向图 (Undirected Graph) 来表达变量间的相互作用。这种结构上的区别导致了它们在建模和推断方面的一系列微妙的差异。

至此,我们已经知道了图论到底是什么,也知道基本有向图和无向图的标准定义。在文章的最后,我们更是将图论的基本概念和概率论的基本思想相结合来理解概率图模型。但我们都知道概率图模型十分强大与重要,所以我们也许需要进一步专门地学习这一机器学习方法。

这里有一些图论相关资源:

Difference between Trees and Graphs:http://suo.im/2qN4yS

What's the difference between the data structure Tree and Graph?:http://suo.im/1wjBzi

Applications of Graph Theory In Computer Science: An Overview:http://suo.im/4twRke

Graph Traversal:http://suo.im/2cu4oH

Data structures: Introduction to graphs(视频):http://suo.im/4z1QbH

  • DNF调查GBL神殿任务怎么做(怎么做DNF调查GBL神殿任务)
  • 2024-11-08怎么做DNF调查GBL神殿任务进入游戏打开任务栏领取任务,需要通关神殿外围地下城打开小地图,从西海岸北部进入天帷巨兽副本在副本选择界面中,选择进入神殿外围,在神殿外围中找到领主大祭司和主教,击败他们就能完成任务,最后,返回西海岸城。
  • 张馨予何捷现身兰州吃小吃(张馨予何捷兰州度蜜月)
  • 2024-11-08张馨予何捷兰州度蜜月新婚燕尔,总是分外甜蜜张馨予选择与在军队的何捷结婚,朴素简洁的婚礼的婚礼更是圈粉不少,难怪章子怡说她:生活中终于拨云见日了9月15日,“拨云见日”的张馨予发了一条微博,表示自己正在丈夫何捷的家乡甘肃享。
  • 梦见牛追我但躲开了(梦见牛追我但躲开了的解释)
  • 2024-11-08梦见牛追我但躲开了的解释梦见牛追我但躲开了,预示近期只会动动嘴皮子的功夫,没有什么实际行动说着努力打拼的口号,却都没有实际性的付出,建议要好好重新审视自己是不是在某一些方面并没有好好用心,并且积极行动起来恋爱中的人梦牛追我但。
  • 什么精华素好用(十款好用的面部精华液推荐)
  • 2024-11-08十款好用的面部精华液推荐因为有的精华液超级贵,所以很多刚刚上班的或者是学生党为了得了一瓶精华液都要吃土好几个月,其实贵的就一定好用吗?恰恰相反,很多平价的精华液比昂贵的好的多的是今天我们就给大家介绍真正好用的精华液,各方面都。
  • 乒乓球的基本知识和技术要领(掌握这两个理论)
  • 2024-11-08掌握这两个理论点我观看视频版教学第一个理论平面支撑原理,可以说乒乓网第一次提出的理论,可以解决所有乒乓球技术错误的动作问题,通过它可以建立所有技术的动作框架第二个理论在打球的过程当中,如何能做到相对固定、绝对放松能。
  • 推荐8部评价很高的韩剧(近8年口碑最好的9部韩剧)
  • 2024-11-08近8年口碑最好的9部韩剧不是随便一部都能称之为好剧,韩剧也不例外从2016年到2023年这8年上线的韩剧是一部接着一部,可能让观众满意的屈指可数今天,我们就来聊一聊这8年间口碑最佳的9部韩剧,这些剧中难免也有笑中带泪的剧情(。
  • 杜鹃花的正确养法(杜鹃花的简单养法)
  • 2024-11-08杜鹃花的简单养法杜鹃花7到9月份的时候,早上和晚上各浇一次水,月中旬至11月这期间水量应适量减少,在隔天的清晨浇夏季的时候需要遮阴,来挡住强烈的阳光但是秋天缩短遮阴的时间,修剪一下非常长的枝条,一些病枝或者长势很衰弱。
  • 木地板怎么选才是正确的(装修木地板怎么选)
  • 2024-11-08装修木地板怎么选家里装修时,少不了温馨自然的木地板作为常见材料,木地板种类多,价格差距大,让业主们眼花缭乱今天阿芋就教大家,如何挑选适合自己小家的木地板,经济实用不买亏!>>1.适合普通家装的性价比之王—。
  • 车子被别人刮蹭了怎么办(车子不知道被谁刮蹭了)
  • 2024-11-08车子不知道被谁刮蹭了很多车主朋友都有这样的经历:“自己的爱车停了一会就被撞了,关键还不知道到谁干的,简直心态爆炸!”你也有过类似的经历吗?爱车被划伤,肇事者逃得无影无踪,这种情况该怎么处理?今天轮谷就来给朋友们说说这个话。
  • 南昌还会投放共享单车吗(共享电单车超额投放)
  • 2024-11-08共享电单车超额投放  青山湖区京东大道世纪风情小区停车场入口(图)  大江网/江西头条客户端讯(黄思农)报道:绿色、低碳、环保,有效解决了群众出行的“最后一公里”,共享单车、电动车的出现深受大家欢迎,然而大量堆积、停放。