Discriminative Embeddings of Latent Variable Models for Structured Data

论文传送门

作者

佐治亚理工学院

• Hanjun Dai
• Bo Dai
• Le Song

摘要

专为处理序列、树状结构及图数据而设计的核分类器与回归器，在多个交叉学科领域中得到了显著的应用进展。一般而言，在探索结构化数据统计特性和概率生成模型的数据类型时会预先定义内核函数。随后基于这些内核函数通过凸优化构建判别分类器的方法已成为主流方案之一。然而这种两阶段的方法论却存在一些局限性：一方面它限制了核方法对数百万实例的学习能力；另一方面它未能充分挖掘判别特征以提升特征表示的质量。为此我们提出了一种称为structure2vec的新方法它是一种高效可扩展的结构化数据表示技术其核心思想是将隐变量嵌入到特征空间并在此基础上利用判别信息来学习该空间中的特征表示机制。
为了实现这一目标我们的研究采用了与图模型推导程序类似的映射策略其中平均场置信传播等技术被系统性地纳入其中用于提取高阶特征信息。
在实际应用场景中针对包含数百万实例的应用情况我们的实验结果表明该方法运行效率提升了约一倍半以上并且实现了模型规模缩减超过1万倍的同时仍能保持与现有最先进的预测性能相当的表现水平

Introduction

bag of structures(BOS)

频谱内核, 子树内核, 基于图块的内核, 魏尔施特拉夫-莱曼图内核

这些核的特征代表事先固定不变，并且每个维度都与一个子结构相关联；此外，应用的数据集的大小受到了限制。

第二类核是基于概率图模型，来表示噪音和结构化的数据。

• 隐含马尔科夫模型系统性地分析序列数据中的模式
• 用于图数据的马尔科夫随机场中的配对模型揭示了节点之间的相互关系

代表性的有：

• Fisher kernel
• probability product kernel

本文Idea

我们提出的方法旨在将每个结构化数据点建模为潜在变量模型，并随后将图模型嵌入到特征空间中，在嵌入空间中使用内积来定义核函数。

创新：

Rather than without fixing any features or embedding spaces beforehand, this approach also enables us to directly optimize the feature space based on the label information.

不同之处：

• developing a descriptor to capture similarities between structured data
• Structure2vec learns to model nonlinear transformations of structured data based on discriminative patterns.
• A variant of Structure2vec performs mean-field updates in an efficient manner, differing from message-passing approaches.

Backgrounds

• 核方法
• 结构化数据的核
• 希尔伯特空间

Models

• Mean-Field Representation
• Loopy Belief Propagation
• Other Variational Inference Methods
• Discriminative Representation

Experiments

代码：https://github.com/Hanjun-Dai/graphnn.

数据集

• String dataset

  • SCOP
  • FC and RES dataset

• Graph datasets

  • MUTAG
  • NCI1
  • NCI109
  • ENZYMES
  • D&D

• Harvard Clean Energy Project dataset

思考

图模型、希尔伯特空间嵌入与深度学习一般方法的结合将会越来越普遍