FMitF: Track I: Symbolic Reasoning with Graph Networks

FMITF：第一轨：图网络的符号推理

• 批准号: 1918483
• 负责人: Tiark Rompf
• 金额: $ 75万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1918483&HistoricalAwards=false
• 关键词: FMitF; Track; Symbolic; Reasoning; Graph

Despite the success of deep neural networks in image recognition, speech recognition, and machine translation, big challenges remain in applying deep-learning techniques to applications that require symbolic forms of reasoning -- in particular, proving theorems in various kinds of logics. The main challenge is one of representation. In image recognition, advances are driven to a large extent by convolutional neural networks, a variation of deep learning, which exploit neighborhood relations inherent in a pixel grid. This representation has also turned out to work very well for two-dimensional game boards: combined with reinforcement-learning, variants of convolutional neural networks are employed by famous gameplay systems, including DeepMind's original Atari engine and more recently AlphaGo and AlphaZero. These techniques do not apply as well to symbolic terms and formulae often used to represent logical reasoning, however, because these constructs lack the same data-rich structure and neighborhood relations. Although it is tempting to draw analogies between game moves and such formulae, significant challenges remain in determining how to build upon the advances made in the domains of gameplay and extend them to symbolic-reasoning problems.The project addresses this representation challenge through a novel notion of neural term-graphs to represent formulae and intermediate states of symbolic formula manipulation within a reinforcement-learning framework. The project will conduct a fundamental study of gameplay-inspired machine-learning approaches to symbolic-reasoning problems, including boolean satisfiability (SAT), quantified boolean formulae (QBF), and first-order logic (FOL). The project will further connect these symbolic reasoning domains with statistical relational learning, and explore their application in the domains of explainable AI and adversarial inference.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

尽管深度神经网络在图像识别、语音识别和机器翻译方面取得了成功，但在将深度学习技术应用于需要符号形式推理的应用方面仍然存在巨大挑战，特别是在各种逻辑中证明定理。主要的挑战是代表性问题。 在图像识别中，进步在很大程度上是由卷积神经网络驱动的，卷积神经网络是深度学习的一种变体，它利用了像素网格中固有的邻域关系。这种表示方法也被证明对二维游戏板非常有效：结合并行学习，卷积神经网络的变体被著名的游戏系统所采用，包括DeepMind最初的Atari引擎以及最近的AlphaGo和AlphaZero。然而，这些技术并不适用于通常用于表示逻辑推理的符号术语和公式，因为这些构造缺乏相同的数据丰富的结构和邻域关系。 虽然这是诱人的游戏动作和这样的公式之间的类比，重大的挑战仍然存在于确定如何建立在游戏领域取得的进展，并将其扩展到符号推理problems.The项目通过一个新的概念，神经项图来表示公式和符号公式操作的中间状态的学习框架内，解决了这一表示的挑战。该项目将对游戏启发的机器学习方法进行基础研究，以解决符号推理问题，包括布尔可满足性（SAT），量化布尔公式（QBF）和一阶逻辑（FOL）。该项目将进一步将这些符号推理领域与统计关系学习联系起来，并探索它们在可解释人工智能和对抗性推理领域的应用。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Neural Networks for Learning Counterfactual G-Invariances from Single Environments

用于从单一环境中学习反事实 G 不变性的神经网络

• 发表时间: 2021
• 期刊: Proceedings of the 9th International Conference on Learning Representations
• 作者: Mouli, S Chandra;Ribeiro, Bruno
• 通讯作者: Ribeiro, Bruno

Explaining classification performance and bias via network structure and sampling technique

• DOI: 10.1007/s41109-021-00394-3
• 发表时间: 2021-10-21
• 期刊: APPLIED NETWORK SCIENCE
• 影响因子: 2.2
• 作者: Espin-Noboa, Lisette;Karimi, Fariba;Wagner, Claudia
• 通讯作者: Wagner, Claudia

Graph IRs for Impure Higher-Order Languages: Making Aggressive Optimizations Affordable with Precise Effect Dependencies

非纯高阶语言的图 IR：通过精确的效果依赖性使积极的优化变得经济实惠

• DOI: 10.1145/3622813
• 发表时间: 2023
• 期刊: Proceedings of the ACM on Programming Languages
• 作者: Bračevac, Oliver;Wei, Guannan;Jia, Songlin;Abeysinghe, Supun;Jiang, Yuxuan;Bao, Yuyan;Rompf, Tiark
• 通讯作者: Rompf, Tiark

Xatu: Richer Neural Network Based Prediction for Video Streaming

• DOI: 10.1145/3489048.3522641
• 发表时间: 2022-06
• 期刊: Abstract Proceedings of the 2022 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems
• 作者: Yun Seong Nam;Jianfei Gao;Chandan Bothra;Ehab Ghabashneh;Sanjay G. Rao;Bruno Ribeiro;Jibin Zhan;Hui Zhang

Sequential stratified regeneration: MCMC for large state spaces with an application to subgraph count estimation

• DOI: 10.1007/s10618-021-00802-3
• 发表时间: 2022-01
• 期刊: Data Mining and Knowledge Discovery
• 影响因子: 4.8
• 作者: Carlos H. C. Teixeira;Mayank Kakodkar;Vinícius Dias;Wagner Meira Jr;Bruno Ribeiro