图论一直是数学中非常重要的一门学科。它以图为研究对象，通常用来描述某些事物之间的某种关系。在机器学习的世界里，我们希望从数据中挖掘隐藏的信息或模型。因此，如果我们把图中的节点看成随机变量，把连接看成相关关系，那么我们就可以构建图模型，有望解决这个问题。本文将提供构建模型的最基本概念。我们都知道机器学习中的决策树，可以表示为类在给定特征条件下的条件概率分布。而我们知道决策树是由节点和有向边组成的，节点又是由代表特征的内部节点和代表类的叶子节点组成的。通常，决策树的学习包括特征的选择、决策树的生成和决策树的剪枝。那么这个树算法从何而来呢？其实树只是图的一个小分支，接下来我们会详细了解离散数学衍生出的一个非常重要的分支：图论。如果这是您第一次涉足图论，本文将为您提供清晰的思路。同时，也希望本文能够清晰地阐述图论的思想和基本模型，从而为以后机器学习模型的构建和概率图模型的理解提供一定的帮助。Loosey-gooseydiagrams当我们刚开始研究非线性结构时，我们需要了解它们最基本的特征：即数据不遵循特定的顺序，至少没有明显的数值关系，也就是我们看到的数组就像链表。我们知道，树结构是从根结点开始，可以与其他结点相连接，也就是说可以由它的子树组成一棵完整的树。一棵树由一组规则定义：根节点可能连接也可能不连接到其他节点，但最终所有叶节点或内部节点都可以追溯到这个特定位置。有些树有更具体的规则，例如二叉搜索树，其中每个节点在任何时候都只连接到两个子节点。机器学习中常用的决策树可以看作是IF-THEN规则的集合。即决策树的根节点到叶子节点的每条路径构造一条规则，路径上内部节点的特征对应规则的条件，叶子节点的类对应结论规则。那我们是不是可以丢弃这些构成树的规则，不严格按照这些规则生成图呢？这样做当然没有错，但是不能生成树，也不能按树结构计算。但我们可以更进一步，将图用于计算或处理任务。树不过是一个受限图，不过是一个遵守无数规则的图。树始终是图的一种，但图远不止于树。那么究竟是什么使树类型与伞形图不同呢？首先，一棵树只能在一个方向上传播，即树类型是由有向边组成的。每棵树从根节点开始，向下传播到子节点或叶节点。同一树类型的每条路径都是唯一的，路径上的所有子节点只有一个父节点。因此，这个树结构中一定不能有循环结构或链接。有了图表，所有这些限制似乎突然消失了。因为图中没有“根节点”、“叶节点”、“单向边”等任何概念，所以图中的节点可以连接多个子节点或者有多个父节点，路径也可以be是有向流或无向边。或者如果你想要一个更复杂的图，你也可以使用有向流和无向边的组合，但本文暂时不会关注这些复杂的系统。有向图和无向图现在我们知道图确实打破了构建树的所有规则。但是每一个图都必须遵守一个基本原则：即图至少有一个单节点。正如一棵树需要至少一个根节点才能被视为“树”一样，图也需要至少一个单个节点才能被视为“图”。只有一个节点的图通常称为“单例图”，基本上我们不会用这种单例图来处理任务。通常可以处理的图都是比较复杂的图，不过不用太担心，本文介绍的图都不算太复杂，但有些图确实超级复杂。首先，我们将探索两种易于识别和理解的图：有向图和无向图。这两种图在图论讨论的问题中很常见。在图中，没有关于节点如何相互连接的确切规则，边（有时称为链接）可以以任何方式连接节点。不同类型的边或路径对于定义和识别图形很重要。边类型实际上是图之间最大和最明显的区别之一。在大多数情况下（只有一个例外），图将有两种类型的边：有方向或流向的边和没有方向或流向的边。我们称它们为有向边和无向边。在有向边中，两个节点以特定方式连接。如下图节点A连接节点B的方式，有向边规定两个节点之间只有一个方向，即只能从源节点到目的节点的特定方向.),永远不会从目标节点反向到起始节点。这种有向边在图论问题中很常见。现在，让我们介绍无向边，它与有向边完全不同。在无向边中，可穿越路径是双向的。即两个节点之间的路径是双向的，起始节点和目标节点不固定。这种差异很重要，因为图中的边决定了图的类型。如果图中的所有边都是有向的，则图是有向图。如果图的所有边都是无向的，则图是无向图。上面描述的图看起来很结构化，但也许我们更应该关心两件事：第一，什么条件或事件填充了这个图，第二，我们应该关注图中的哪些信息？轻轻地：我们来到了图的王国计算机科学喜欢借鉴其他学科。具体来说，我喜欢从逻辑和数学中借用很多概念。图论也是如此，它从一开始就是数学的一个分支，以图为研究对象。图论通常是研究由顶点和边组成的图的数学理论和方法。我们熟悉的图数据结构或者树算法等计算机概念其实都来源于数学，图的研究就是图论。在数学中，图是一种正式表示网络的结构，网络基本上是所有互连对象的集合。事实证明，当计算机科学家将图论应用于代码（创建图数据结构或树算法等）时，这些理论并没有太大变化。因此，本文中用于描述和实现图的术语与数学图论中使用的术语完全相同。在数学术语中，我们将图描述为有序对。还记得之前学过的函数吗，它的定义是一组分布在二维坐标轴上的有序对(x,y)。图使用类似的定义，但使用图的顶点v和边e而不是x和y。因此，一个图的形式化数学定义是：G=(V,E)但是问题来了，如果我们的图有多个节点和多条边怎么办，实际上通常有多个节点，这种情况下，如何定义一个图形。其实上面的定义不会失败，因为有序对(V,E)实际上是由两组对象组成的：一组节点和一组边。现在广义图的定义变得更有意义了，但是如果有例子来说明，这个概念会更容易理解，所以下图是一个由8个节点和12条边组成的无向图。我们详细解释了这个图是如何在数学上正式定义的。那么上面的例子说明了什么？我们将有序对表示为(V,E)，但由于每个项目都是一个对象，因此我们必须将项目写出来。V被定义为八个节点的无序集合，“无序”的概念在这里非常重要。因为与树不同，图没有节点层次结构。所以排序无所谓，我们也不需要对它们进行排序。我们还必须将E定义为包含所有边的项。同样，边缘对象也是无序的。原因是图的边是无向边，没有固定的流向或流向，即没有固定的起始节点和目标节点，所以每条边都是无序的。当然，无向图的“无序”特性可能会引起一些混淆，但有向图的本质是什么？这是另一种情况。该图是由三个节点和三个有向边组成的有向图。在有向图中，节点的定义方式与无向图中相同，但有向边和无向边的定义不同。在有向图中，边对象被定义为有序对（用括号表示），因为在这种情况下边的方向很重要。因为在有向图中，边只能是起始节点到目标节点，所以必须对边进行排序，从而定义E中的有序对。前一个元素为起始节点，下一个元素为目标节点。所以上面就是我们如何定义一个图，但是定义了图之后，我们什么时候才能真正应用这个图。下面我们一起来看看图的应用和计算。超级社交图其实就在我们身边，只是我们不了解而已。事实上，当您阅读这篇文章时，您就置身于一幅画中。网络是一个巨大的图结构，每个终端都是一个节点，互联网就是网络的边。网页也是如此，当我们点击一??个网站并在URL之间来回导航时，我们就是在图中导航。有的网页有无向边，可以在两个网页之间来回切换，有的网页有有向边，只能从一个网页切换到另一个网页。现在，我们用一个更形象的案例来说明图的日常交互：社交网络。微信是一个庞大的社交网络，也是一个图。如果我们能更多地思考它的实际功能，那么我们就能更好地理解如何定义和确定图的类型。在微信上，如果我想成为你的朋友，那么我需要加你为好友，你必须接受我的请求。如果你不是我的微信好友，我也不会是你的微信好友。两个用户之间的关系（图中的节点和边）是双向的。它没有起始节点和目标节点的概念。那么现在你能分辨出微信上都有哪些图片了吗？因此，微信是一个大规模的无向图，用户之间可以同时传递信息。而另一个社交网络微博是一个有向图，因为当用户发布微博时，博文的信息会同时被用户发送给粉丝，这个过程是有方向的，是不可逆的.在理解了图论的基本概念和定义表达式之后，或许我们可以进一步探索概率图模型的一些重要思想。机器学习的核心任务是从观测数据中挖掘隐藏的知识，而概率图模型是实现这一任务的重要手段。概率图模型巧妙地结合了图论和概率论。从图论的角度来看，概率图模型是包含节点和边的图。节点可以分为两类：隐藏节点和观察节点。边可以分为有向或无向。从概率论的角度来看，概率图模型是一个概率分布，图中的节点对应随机变量，边对应随机变量的相关关系。给定一个实际问题，我们通常会观察一些数据，希望挖掘隐藏在数据中的知识。那么我们如何使用概率图模型来挖掘这些隐藏的知识呢？通常我们会构建一个图：用观察节点表示观察到的数据，用隐藏节点表示潜在知识，用边描述知识与数据的相关性，最后得到一个概率分布。给定概率分布，通过执行两个任务获取知识：推理（给定观察节点，推断隐藏节点的后验分布）和学习（学习概率分布的参数）。基本图模型大致可以分为两大类：贝叶斯网络和马尔可夫随机场。它们的主要区别在于使用不同类型的图来表达变量之间的关系：贝叶斯网络使用有向无环图（DirectedAcyclicGraph）来表达因果关系，马尔可夫随机场使用无向图（UndirectedAcyclicGraph）。图）来表达变量之间的相互作用。这种结构上的差异导致了它们在建模和推理上的一系列细微差别。至此，我们已经知道什么是图论以及基本有向图和无向图的标准定义。在文章的最后，我们结合图论的基本概念和概率论的基本思想来理解概率图模型。但是我们都知道概率图模型是非常强大和重要的，所以我们可能需要进一步专门研究这种机器学习方法。原文：https://dev.to/vaidehijoshi/a-gentle-introduction-to-graph-theory?utm_content=buffer6fb86&utm_medium=social&utm_source=twitter.com&utm_campaign=buffer【本文为专栏机器心、微信原创翻译公众号《机器之心（id：almosthuman2014）》】点此阅读作者更多好文
