zdaiot

以下内容大部分转载从图(Graph)到图卷积(Graph Convolution)：漫谈图神经网络模型 (一)。觉得这篇文章写得很好，先摘抄过来，用于日后添加个人理解。

历史脉络

在开始正文之前，笔者先带大家回顾一下图神经网络的发展历史。不过，因为图神经网络的发展分支非常之多，笔者某些叙述可能并不全面，一家之言仅供各位读者参考：

1. 图神经网络的概念最早在2005年提出。2009年Franco博士在其论文 [2]中定义了图神经网络的理论基础，笔者呆会要讲的第一种图神经网络也是基于这篇论文。
2. 最早的GNN主要解决的还是如分子结构分类等严格意义上的图论问题。但实际上欧式空间(比如像图像 Image)或者是序列(比如像文本 Text)，许多常见场景也都可以转换成图(Graph)，然后就能使用图神经网络技术来建模。
3. 2009年后图神经网络也陆续有一些相关研究，但没有太大波澜。直到2013年，在图信号处理(Graph Signal Processing)的基础上，Bruna(这位是LeCun的学生)在文献 [3]中首次提出图上的基于频域(Spectral-domain)和基于空域(Spatial-domain)的卷积神经网络。
4. 其后至今，学界提出了很多基于空域的图卷积方式，也有不少学者试图通过统一的框架将前人的工作统一起来。而基于频域的工作相对较少，只受到部分学者的青睐。
5. 值得一提的是，图神经网络与图表示学习(Represent Learning for Graph)的发展历程也惊人地相似。2014年，在word2vec [4]的启发下，Perozzi等人提出了DeepWalk [5]，开启了深度学习时代图表示学习的大门。更有趣的是，就在几乎一样的时间，Bordes等人提出了大名鼎鼎的TransE [6]，为知识图谱的分布式表示(Represent Learning for Knowledge Graph)奠定了基础。

图神经网络(Graph Neural Network)

半监督学习可以利用“少”的有标记样本和“多”的无标记样本改善分类器的性能，在一定程度上提高学习能力，成为当前机器学习研究领域的热点问题。

半监督学习机理

下图给出了一个缺少概念标记的未标记数据为何能够帮助学习器学习的简单例子。用“+”表示正样本、“-”表示负样本、“.”表示未标记样本。现在需要预测“*”这个样本的标记。当仅利用有标记样本进行学习(如图 1.2(a)所示)时，会很自然地将该样本判为正样本；但若考虑大量未标记样本(如图 1.2(b)所示)的分布，则可以发现待预测样本和有标记的负样本同属于一个簇，由于处于同一个簇中样本的性质应该相似，因此将该样本预测为负样本应更加合理。从此例可以看出，未标记样本提供的分布信息能够帮助和指导学习过程。

半监督学习假设

最近在师兄的推荐下，阅读了一篇利用半监督图做PolSAR图像分类的文章，感觉这篇文章整体思路不错，值得借鉴。在这里做一下简单的笔记。

基本信息

• 年份：2019
• 期刊：IEEE Transactions on Geoscience and Remote Sensing
• 标签：Graph, PolSAR, Semisupervised
• 数据：Flevoland、San Francisco

创新点

1. 第一个将半监督图分类算法和深度卷积神经网络融合于PolSAR图像分类框架中 。
2. 设计了结合半监督项、CNN项、成对平滑损失项的能量函数。其中：
   • 半监督项强迫类标预测受人类标记样本的约束
   • CNN项负责提取具有分辨性的PolSAR特征并预测类标
   • 成对平滑损失项负责预测类标和图像边缘对齐
3. 设计了一个迭代、交替的优化过程优化模型

之前一直听说过MRF的大名，但是一直没有了解过。最近在看论文的时候，经常遇到这个专业术语，就专门对这个概念学习一下。声明下面内容主要参考了这篇文章——马尔科夫随机场(MRF)在图像处理中的应用-图像分割、纹理迁移，加了一些个人见解。

马尔科夫随机场，英文名称Markov Random Field，简写为MRF。

基础概念

条件概率和贝叶斯定理

条件概率常用来解决逆问题，也就是已知结果反推原因。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

时间复杂度是衡量算法执行效率的一种标准。但是，时间复杂度并不能跟性能划等号。算法的目的是为了提高代码执行的效率。当算法无法再继续优化的情况下，需要借助另外一种优化方法提高执行效率——并行计算。那么如何借助并行计算的处理思想对算法进行改造？

并行排序

假如要对8GB大小的数据排序，最常用的就是时间复杂度为 $O(nlogn)$ 三种排序算法——归并排序、快速排序、堆排序。理论上，这个排序问题很难再从算法层面优化了。但是借助并行的处理思想，可以轻松地把执行效率提高很多倍。具体实现思路有如下两种：

第一种是对归并排序并行化处理。可以把这8GB的数据划分为16个大小为500MB的小数据集合，使用16个线程并行地对这16个500MB 的数据集合进行排序，然后再将这16个有序集合合并。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

之前讲过，MySQL底层使用的是B+树这种数据结构，实现数据库索引的。那么类似 Redis 这样的 Key-Value 数据库中的索引，又是怎么实现的呢？底层依赖的又是什么数据结构呢？

本节讲述一下索引这种常用的技术解决思路，底层往往会依赖哪些数据结构。

为什么需要索引？

实际开发中，众多复杂的业务和功能的外壳，本质都可以抽象成“对数据的存储和计算”。对应到数据结构和算法中，那“存储”需要的就是数据结构，“计算”需要的就是算法。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

游戏中常有一个功能——人物自动绕过障碍物寻路。这是怎么实现的呢？

算法解析

这是一个非常典型的搜索问题。人物经过的路径要绕过地图上所有的障碍物，并且走的路不能太绕。理论上，最短路径显然是最好的走法，是这个问题的最优解。

但是在第43节最优出行路线规划问题中说过，若地图非常大，Dijkstra 最短路径算法的执行耗时会很多。实际运用时，经常面对的是超级大的地图和海量的寻路请求，算法的执行效率太低，这显然是无法接受的。实际上，像出行路线规划、游戏寻路这样的问题，不需要求得最优解。在权衡路线规划质量和执行效率后，寻找一个次优解就可以了。那如何快速找出一条接近于最短路线的次优路线呢？这就需要用到本节要学习的A*算法，它是对Dijkstra 算法的优化和改造。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

为了加速数据库中数据的查找速度，常常对表中数据创建索引。那么数据库索引是如何实现的呢？底层使用的是什么数据结构和算法呢？

算法解析

解决问题的前提是定义清楚问题

如何定义清楚问题呢？除了对问题进行详细的调研，还可以通过对一些模糊的需求进行假设，来限定要解决的问题的范围。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

现在的听歌软件都会根据你听歌的偏好给你推荐歌曲，那么这个功能该如何实现呢？

算法解析

这个问题的解决思路核心很简单、直白：

• 找到跟你口味偏好相似的用户，把他们爱听的歌曲推荐给你；
• 找出跟你喜爱的歌曲特征相似的歌曲，把这些歌曲推荐给你。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

上一节讲了如何用位图、布隆过滤器来过滤重复的数据。今天再讲一个与过滤相关的问题——如何过滤垃圾短信和骚扰电话。应该用什么样的数据结构和算法？

算法解析

基于黑名单的过滤器

可以维护一个骚扰电话号码和垃圾短信发送号码的黑名单。若黑名单中电话号码不多，可以用散列表、二叉树等动态数据结构来存储，对内存的消耗并不会很大。但是，若黑名单中的电话号码很多时，比如500万个，每个号码看作一个长度为16的字符串，那大概需要100MB的存储空间，有点大。