Neural networks have succeeded in many reasoning tasks. Empirically, these tasks require specialized network structures, e.g., Graph Neural Networks (GNNs) perform well on many such tasks, but less structured networks fail. Theoretically, there is limited understanding of why and when a network structure generalizes better than others, although they have equal expressive power. In this paper, we develop a framework to characterize which reasoning tasks a network can learn well, by studying how well its computation structure aligns with the algorithmic structure of the relevant reasoning process. We formally define this algorithmic alignment and derive a sample complexity bound that decreases with better alignment. This framework offers an explanation for the empirical success of popular reasoning models, and suggests their limitations. As an example, we unify seemingly different reasoning tasks, such as intuitive physics, visual question answering, and shortest paths, via the lens of a powerful algorithmic paradigm, dynamic programming (DP). We show that GNNs align with DP and thus are expected to solve these tasks. On several reasoning tasks, our theory is supported by empirical results.


翻译:神经网络在许多推理任务中取得了成功。 这些任务通常需要专门的网络结构,例如,图形神经网络(GNNS)在很多此类任务中表现良好,但结构化较少的网络失败。理论上,对于为什么网络结构比其他网络更概括化,以及当网络结构比其他网络更普遍时,理解有限,尽管网络具有同等的表达力。在本文件中,我们通过研究网络的计算结构与相关推理过程的算法结构的匹配程度,我们制定了一个框架来说明哪些推理任务可以很好地学习。我们正式定义了这种算法结构,并得出了一种精细的复杂度,并有较好的校准。这个框架为大众推理模型的经验成功提供了解释,并提出了它们的局限性。举例来说,我们通过一个强大的算法范式、动态编程(DP)的透镜,将看起来不同的推理任务统一起来。我们理论得到了实证结果的支持。

9
下载
关闭预览

相关内容

Networking:IFIP International Conferences on Networking。 Explanation:国际网络会议。 Publisher:IFIP。 SIT: http://dblp.uni-trier.de/db/conf/networking/index.html
因果图,Causal Graphs,52页ppt
专知会员服务
238+阅读 · 2020年4月19日
神经网络的拓扑结构,TOPOLOGY OF DEEP NEURAL NETWORKS
专知会员服务
29+阅读 · 2020年4月15日
【干货书】真实机器学习,264页pdf,Real-World Machine Learning
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
论文浅尝 |「知识表示学习」专题论文推荐
开放知识图谱
13+阅读 · 2018年2月12日
「知识表示学习」专题论文推荐 | 每周论文清单
Capsule Networks解析
机器学习研究会
10+阅读 · 2017年11月12日
【论文】图上的表示学习综述
机器学习研究会
12+阅读 · 2017年9月24日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Neural Module Networks for Reasoning over Text
Arxiv
9+阅读 · 2019年12月10日
Signed Graph Attention Networks
Arxiv
7+阅读 · 2019年9月5日
Arxiv
23+阅读 · 2018年10月1日
Relational recurrent neural networks
Arxiv
8+阅读 · 2018年6月28日
Arxiv
8+阅读 · 2018年5月24日
VIP会员
相关资讯
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
论文浅尝 |「知识表示学习」专题论文推荐
开放知识图谱
13+阅读 · 2018年2月12日
「知识表示学习」专题论文推荐 | 每周论文清单
Capsule Networks解析
机器学习研究会
10+阅读 · 2017年11月12日
【论文】图上的表示学习综述
机器学习研究会
12+阅读 · 2017年9月24日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
相关论文
Neural Module Networks for Reasoning over Text
Arxiv
9+阅读 · 2019年12月10日
Signed Graph Attention Networks
Arxiv
7+阅读 · 2019年9月5日
Arxiv
23+阅读 · 2018年10月1日
Relational recurrent neural networks
Arxiv
8+阅读 · 2018年6月28日
Arxiv
8+阅读 · 2018年5月24日
Top
微信扫码咨询专知VIP会员