梦家博客

背景 指数平滑是在 20 世纪 50 年代后期提出的，并激发了一些十分成功的预测方法。使用指数平滑方法生成的预测是过去观测值的加权平均值，并且随着过去观测值离预测值距离的增大，权重呈指数型衰减。换句话说，观察值越近，相应的权重越高。该框架能够快速生成可靠的预测结果，并且适用于广泛的时间序列，这是一个巨大的优势并且对于工业应用来说非常重要。 本文主要学习四种常见的指数平滑方法： Exponential smoothing：针对没有趋势和季节性的序列 一次指数平滑，从最邻近到最早的数据点的权重呈现指数型下降的规律。 Holt exponential smoothing：针对有趋势但没有季节性的序列 二次指数平滑，通过引入一个额外的系数来解决指数平滑无法应用于具有趋势性数据的问题。 Holt-Winters exponential smoothing：针对有趋势且有季节性的序列 三次指数平滑，通过再次引入一个新系数的方式同时解决了 Holt exponential smoothing 无法解决具有季节性变化数据的不足。 所有的指数平滑法需要更新上一时间点的计算结果，并使用当前 ...

论文标题 ｜ An End-to-End Deep Learning Architecture for Graph Classification 论文来源 ｜ AAAI 2018 论文链接 ｜ https://www.cse.wustl.edu/~muhan/papers/AAAI_2018_DGCNN.pdf 源码链接 ｜ https://github.com/muhanzhang/pytorch_DGCNN 很久之前看过这篇比较经典的针对图分类任务的文章：https://dreamhomes.top/posts/201904192122/，但是有些细节忘了 😂 因此再次复习下其内容想在最近的任务中用到。 TL;DR Algorithm/Model Experiments Thoughts

开源图数据集 目前在多个库中可以直接下载处理好的图数据集： DGL：https://docs.dgl.ai/en/0.6.x/api/python/dgl.data.html PyG：https://pytorch-geometric.readthedocs.io/en/latest/modules/datasets.html 其它数据源推荐： papers with code KONECT datasets Stanford Large Network Dataset Collection 经典数据集 目前图神经网络应用较广的数据集主要有以下几大类： 引文网络：Cora、PubMed、Citeseer 社交网络：BlogCatalog、Reddit、Epinions 蛋白质交互网络：PPI、PROTEINS 化学分子结构：MUTAG、NCI-1、NCI-109 引文网络 由论文间的关系构成的网络，关系包括例如引用关系、共同的作者等，具有天然的图结构，数据集的任务一般是论文的分类和连接的预测，比较流行的数据集有三个，分别是 Cora、PubMed、Citeseer。 数据 ...

论文标题 ｜ High-recall causal discovery for autocorrelated time series with latent confounders 论文来源 ｜ NeurIPS 2020 论文链接 ｜ https://arxiv.org/abs/2007.01884 源码链接 ｜ https://github.com/jakobrunge/tigramite TL;DR Algorithm/Model Experiments Thoughts

论文标题 ｜ Groot: An Event-graph-based Approach for Root Cause Analysis in Industrial Settings 论文来源 ｜ ASE 2021 论文链接 ｜ https://arxiv.org/abs/2108.00344 源码链接 ｜ 未公布 TL;DR 针对工业界微服务架构下根因定位的 operation, system scale, monitoring complexities 三大问题，论文中提出了基于事件图的根因分析 RCA 方法 Groot，该方法构建基于事件的实时因果关系图，这些事件是总结分析下的系统中各种类型的指标、日志和活动。 此外，为了采用 SRE 的领域知识，Groot 可以通过用户自定义事件和领域规则进行定制化。目前 Groot 可用于 5000 ± 微服务规模的根因定位问题，实验部分收集了 952 个历史故障案例来验证 Groot 的有效性，实验结果表明 Groot 可以达到准确率 Top-3 95%，Top-1 78%，而且运行时间约为 5s。 Algorithm/Model 首先以一 ...

论文标题 ｜ Random Walk Graph Neural Networks 论文来源 ｜ NeurIPS 2020 论文链接 ｜ https://proceedings.neurips.cc/paper/2020/file/Paper.pdf 源码链接 ｜ https://github.com/giannisnik/rwgnn TL;DR 这篇论文中作者提出了更加直观透明的图神经网络模型 RWNN(Random Walk Graph Neural Network)，RWNN 模型的第一层由一系列可训练的 “hidden graphs”组成，这些“hidden graphs”与随机游走核 (random walk kernel) 对应的输入图进行对比，以此来生成 graph-level 的表示，然后经过全连接神经网络来得到最终的分类结果。其中随机游走核是可微的因此模型 RWNN 可以端到端进行训练。实验部分在人工数据集中说明了 RWNN 的透明度（解释性），且在真实图数据集的图分类任务中验证了模型的强大性能。 Problem Definition 为了得到 graph-level ...

论文标题 ｜ Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks 论文来源 ｜ ICML 2021 论文链接 ｜ https://arxiv.org/abs/2101.05974 源码链接 ｜ https://github.com/snap-stanford/CAW TL;DR 为了学习到时序网络中的三元闭包规律，论文中提出了因果匿名游走 Causal Anonymous Walks (CAWs) 的方法对时序网络进行归纳表示学习，CAWs 主要是基于时序网络进行随机游走，以此捕获时序网络中 motifs 来表示网络的动态变化；CAWs 采用新的匿名策略，以节点的命中次数代替节点的区分特征，以保持算法的归纳性能力。为了学习 CAWs 特征，论文中还提出了模型 CAW-N 进行编码，可以达到常量级的内存和时间开销。实验部分采用 6 个真实网络数据集中验证了 CAW-N 在归纳学习的链路预测任务中平均优于当前 baselines 15% AUC，同时在 5-6 个数据集上的直推 ...

很久之前在博客中记录了 GraphSAGE 的理论 NIPS 2017 | GraphSAGE：大规模图上的归纳表示学习模型，此时再回首阅读这篇经典的论文发现描述得仍不够通俗易懂，大部分是对论文的翻译工作，对此领域了解较少的同学仍会感到疑惑。因此本文以更加简单清晰的图示方法解释 GraphSAGE 并介绍下用于 Graph-level 和 Node-level 的 inductive learning 任务，最后进行简单总结。 背景 经典的谱图卷积 GCN 和 Node2vec 系列难以解决新节点的表示学习问题而且图是固定的，仅适用于 transductive learning 任务而且不符合现实很多复杂网络的场景，因此提出了 inductive learning 框架 GraphSAGE (SAmple and aggreGatE) 对未知节点生成节点 embedding。GraphSAGE 的主要思想是：学习特征映射函数而不是直接为每个节点学习 embedding，学习映射函数的好处是可以通过一个节点的局部邻居采样并聚合节点特征来生成节点表示。 具体理论和 motivation ...

论文标题 ｜ Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks 论文来源 ｜ KDD 2020 论文链接 ｜ https://arxiv.org/abs/2005.11650 源码链接 ｜ https://github.com/nnzhan/MTGNN TL;DR 考虑到多变量间存在的依赖关系，论文中针对多变量时序预测问题提出了一个通用的图神经网络框架 MTGNN。首先可以通过 graph learning 模块学习到变量间的单向关系构图，然后通过 graph convolution 模块和 temporal convolution 模块来捕获时间序列间的时空依赖特征，此外这三个模型可以端到端地进行联合训练。实验部分在 3 个基准数据集和 2 个交通流量数据集中验证了 MTGNN 性能优于当前多个 baselines。 Problem Definition 令向量 zt∈RN\mathbf{z}_{t} \in \mathbf{R}^{N}zt​∈RN 表示 NNN ...

论文标题 ｜ Handling Missing Data with Graph Representation Learning 论文来源 ｜ NeurIPS 2020 论文链接 ｜ https://arxiv.org/abs/2010.16418 源码链接 ｜ https://github.com/maxiaoba/GRAPE TL;DR 针对数据特征缺失的 feature imputation 和 label prediction 问题，论文提出了一种基于图的处理框架 GRAPE。GRAPE 基于图表示学习的方法来处理缺失特征填充和标签预测问题，主要思路是将观测样本点和特征类型作为二分图中的两种类型节点，其观测特征值作为边，按二分图建模即可：将特征填充问题转为边级别的预测任务，将标签预测问题转为节点级别的预测任务。实验部分在九个基准数据集中验证了 GRAPE 在缺失值填充任务中 MAE 可提高 20% 且在标签预测任务中提高 10%。 Problem Definition 给定 nnn​​​​ 个数据点的 mmm​​​​ 维特征 D∈Rn×m\mathbf{D} \in \math ...

背景 json_data = {"data":[{"line":{"color":"blue","dash":"solid","shape":"linear","width":1.8},"mode":"lines","name":"value","showlegend":true,"text":"","type":"scatter","x":["2020-09-11 00:00:00","2020-09-11 00:05:00","2020-09-11 00:10:00","2020-09-11 00:15:00","2020-09-11 00:20:00","2020-09-11 00:25:00","2020-09-11 00:30:00","2020-09-11 00:35:00","2020-09-11 00:40:00","2020-09-11 00:45:00","2020-09-11 00:50:00","2020-09-11 00:55:00","2020-09-11 01:00:00","2020-09-11 01:05:00","2020-0 ...

背景 任何事物在两个不同时刻都不可能保持完全相同的状态，但很多变化往往存在着一定的规律，例如 24 小时日出日落，潮起潮落，这些现象通常称为周期。 周期性，指时间序列中呈现出来的围绕长期趋势的一种波浪形或振荡式变动。准确提取周期信息，不仅能反映当前数据的规律，应用于相关场景，还可以预测未来数据变化趋势。 一般而言，时间序列周期性分为三种： 符号性周期，例如序列 fbcnfkgbfops中 f 周期为 4； 部分周期性，例如序列 ansdcdmncdcacdascdmc 中 cd 周期为 4； 分段周期性，例如上面给定的时间序列即为分段周期性； 针对时间序列的周期性检测问题，这篇文章主要介绍傅里叶变换和自相关系数两种方法及其在实际数据中的效果； 傅里叶变换 傅里叶变换是一种将时域、空域数据转化为频域数据的方法，任何波形（时域）都可以看做是不同振幅、不同相位正弦波的叠加（频域），详细介绍可以参考：An Interactive Guide To The Fourier Transform，👇🏻 此处放上经典图镇场！ 对于一条具备周期性的时间序列，它本身就很接近正弦波，所以它包含一 ...

背景 在时间序列分析中，比较关注的点包括两方面：异常和趋势，例如医生查看心电图判断患者是否存在病患，零售业查看历史业绩曲线判断在哪个季节进行销售来提高业绩等。 对于时间序列的异常和趋势分析，其中一种方案是 相似连接（similarity join），其主要思想就是：给定时间序列和窗口长度，计算子序列与时间序列内其它子序列间的距离，得到序列片段与自身进行比较的结果，以此来表征时间序列。 这种方法显而易见的缺点就是计算复杂度非常高，而且随着时间序列长度增大而增大。此时就可以引入 Matrix Profile（MP） 来减少计算时间。 📢 注意 Matrix Profile 本身不是一种算法而是表征时间序列的一种数据结构。至于 Matrix profile 有多么强大，此处引入官方的 claim： The Matrix Profile has the potential to revolutionize time series data mining because of its generality, versatility, simplicity and scalability. I ...

本文主要介绍智能运维中多维指标根因定位问题及其解决方案，以下内容主要源于我们组内一位同学对该问题的概述 传送门~，笔者为清华大学博三在读研究生，主要研究领域为智能运维中的根因定位问题。 关于智能运维领域另一个关键问题 【调用链根因定位】可以参考另一篇文章 智能运维 AIOps 系列丨调用链根因定位算法综述 智能运维领域 AIOps 平台调研，结果来自于 G2 统计： https://www.g2.com/categories/aiops-platforms 问题定义 多维度指标的异常定位是 AIOps 领域的一个典型且有挑战的问题。在互联网服务运维中，当某个总指标（如总流量）发生异常时，需要快速准确地定位到是哪个交叉维度的细粒度指标（如“省份=北京 & 运营商=联通”的流量）的异常导致的，以便尽快做进一步的修复止损操作。由于运维中的指标维度多、每个维度取值范围大，导致异常定位时的搜索空间非常大，因此需要一个高效的算法解决该问题。 举 🌰 说明：一个 KPI 指标根据多种属性分别监控，例如 Page Views（PV），分别统计来自不同 ISP 和不同省份的 PV。如 Fi ...

论文标题 ｜ Faster, Deeper, Easier: Crowdsourcing Diagnosis of Microservice Kernel Failure from User Space 论文来源 ｜ ISSTA(A) 2021 论文链接 ｜ https://dl.acm.org/doi/10.1145/3460319.3464805 源码链接 ｜ https://github.com/PanYicheng/dycause_rca TL;DR 论文提出了基于用户空间和众包策略的微服务内核故障诊断方案 DyCause，以此来解决诊断信息不对称问题。DyCause 以分布式方式部署在应用端，通过轻量级 API 日志共享，程序可以协同收集内核服务的运行状态来按需启动诊断，DyCause 部署非常简单而且轻量级不依赖于内核的架构和功能。为了从不对称诊断信息中挖掘服务间的关系，论文中还设计了一种基于统计的算法来挖掘服务间随时间变化的因果关系，可以有助于了解异常传播的时序关系。实验部分在 testbed 和真实云系统中测试 DyCause，证明它在性能上优于当前的 baselin ...