概率论知识点树状图(想了解概率图模型)
概率论知识点树状图(想了解概率图模型)
2024-11-21 11:11:03  作者:苏更生  网址: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

  • 插座的六个小细节(插座少不够用线缆乱不美观)
  • 2024-11-22插座少不够用线缆乱不美观懂生活、爱生活的人,都喜欢买买买,日子过得越久,家里东西越多,随之而来的、最突出的问题就是,插座严重不够用,各类线缆越来越多,越来越乱,长此以往,家将不家啊!遇到问题,就要面对问题,解决问题!为此,我。
  • 福原爱为何和江宏杰离婚(日媒曝福原爱江宏杰离婚详细真相)
  • 2024-11-22日媒曝福原爱江宏杰离婚详细真相乒坛名将福原爱和江宏杰近期频繁被分居或离婚的消息占据娱乐版面,3月3日日媒报道两人已经离婚,而后还曝光福原爱疑似出轨,不过后来福原爱回应只是和好友聚会,两人没有住在一起,而江宏杰方面的回应是不认识和福。
  • 国庆节吃什么最安全(国庆三重奏鉴健康常识真与伪)
  • 2024-11-22国庆三重奏鉴健康常识真与伪千呼万唤始出来!国庆长假即将来临!也到了健康中国头条兑现红包承诺的时候了如果我告诉你国庆七天的假期里前三天都有红包是不是超兴奋!不过光送红包显得不够COOOOOOL!我可是爱健康的健康君为什么不能既送。
  • it的用法(it如何用)
  • 2024-11-22it如何用it的用法有几类,最常见的是做普通代词,代指前文提到的某种物体或某个事情,比如Iboughtatable,it代指前面的table第二个用法是用it或there来代指不确定的东西第三种用法是it做强调。
  • 你当宝的东西在别人眼里一文不值(你把我当成什么了)
  • 2024-11-22你把我当成什么了图片来源于网络 “离婚,我会给你十个亿”  慕知寒的嗓音淡漠极了,他靠着沙发,俊美无俦的脸上没有多余的情绪,骨节分明的手递过去一支钢笔  他看着面前化着浓妆的绿发少女,眸色深邃如夜  “十个亿?”颜芷。
  • 梅长苏和南楚有什么联系(燕洵梅长苏同样选择复仇)
  • 2024-11-22燕洵梅长苏同样选择复仇细细想来,燕洵和梅长苏何其相似,原本都是胸怀坦荡之人,然旦夕之变让命运偏离原来的轨道,只是梅长苏是平反昭雪、扶植明君,拼尽此生余力还大梁百姓一个清明盛世;而燕洵却走上复仇之路,只想“血洗长安”,以慰亡。
  • 5款良心面膜分享好用不肉疼(我的黑面膜经验)
  • 2024-11-22我的黑面膜经验国货之光—最好用的黑面膜top3我最早的时候都是用的白膜,之后看见好多人都在使用黑面膜我那时觉得黑色膜布贴在脸上看了怪怪哒因为好奇我也就跟风买了尝试一下结果一用就爱上了然后就陆陆续续的买了好几种黑面膜。
  • 乍暖还寒时候最难将息(乍暖还寒时候)
  • 2024-11-22乍暖还寒时候乍暖还寒时候,最难将息…这原本清明的雨却是今天下了,感觉似乎一年没有下过雨了很久没有爬山了,记得自从老父亲病的时候开始,就再也没有爬过事情好像都是这样,一旦放下久了,就再也不想拿起来了,有时想都会懒得。
  • 新版神雕侠侣小郭襄演员(神雕侠侣又拍新版)
  • 2024-11-22神雕侠侣又拍新版文/韦春花近日,电视剧新版《神雕侠侣》官方爆出宣传海报,主角杨过和小龙女都分别采用了新人演员,而一代大侠郭靖之女郭襄则是由大家所熟悉的00后金马最佳女配文淇出演一代经典再度被翻拍,引起网友们的热议,究。
  • 美团打车一般什么时候上线(美团上线美团打车)
  • 2024-11-22美团上线美团打车美团这些年一路势如破竹,发展很迅猛,从团购到外卖业务的时候发力很猛,后来和大众点评合并,再接着美团收购了摩拜单车,后来又开始上线了打车业务,2019年04月26日,美团打车在南京上线“聚合模式”,一键。
  • 塑料袋大袋都是用什么材质(令人眼花缭乱的塑料袋材质类型)
  • 2024-11-22令人眼花缭乱的塑料袋材质类型塑料袋的种类很多,按生产原料可以分类为高压聚乙烯塑料袋、低压聚乙烯塑料袋、聚丙烯塑料袋、聚氯乙烯塑料袋、醋酸乙烯、聚乙烯醋酸乙烯、聚乙烯复合聚丙烯、聚乙烯复合醋酸乙烯、聚乙烯复合聚氯乙烯、聚乙烯复合尼。