AF: Small: Integrated Knowledge Discovery and Analysis Using Sum-of-Squares Proofs

AF：小：使用平方和证明进行综合知识发现和分析

• 批准号: 1718380
• 负责人: Brendan Juba
• 金额: $ 44万
• 依托单位: Washington University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-01 至 2021-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1718380&HistoricalAwards=false
• 关键词: AF; Small; Integrated; Knowledge; Discovery

Developing approaches to subjects as diverse as advertising, bioinformatics, counterterrorism, fraud detection, politics, sociology, and so on are based on data analysis. This project will develop new algorithms for data analysis with strong guarantees of their correctness and efficiency. Tools based on these algorithms will be usable as-is, without expert knowledge, in innovative data-driven applications far removed from academia. The project will also involve the training of students in advanced techniques for data analysis.The algorithms considered in this project involve automated reasoning with an algebraic logic known as "sum-of-squares." Automated reasoning requires a delicate trade-off between expressiveness and simplicity, to facilitate reasoning that is both fast and effective. Sum-of-squares is capable of expressing much statistical reasoning, and yet is sufficiently simple to allow the design of tractable algorithms for reasoning. This project will consider how these algorithms can be used to reason about an overall distribution or population from a sample of data drawn from it. The main aim of the project is to develop efficient algorithms that guarantee that all of the relevant statistical facts are discovered during data analysis. The project will further develop these algorithms to solve problems in domains such as Computer Vision and Natural Language Processing.In addition to the development of domain-specific algorithms, the project will consider sum-of-squares reasoning with high-degree polynomials. Although such reasoning in the standard sense is intractable, the project aims to simulate reasoning with such high-degree expressions with the aid of the sample of data from the distribution to be reasoned about. The project will also investigate the expressive power of sum-of-squares with such high-degree expressions. Specifically, the project will investigate whether or not such reasoning can simulate other logics such as resolution (or vice-versa), and will further investigate the extent of its ability to basic capture statistical notions.

开发各种学科的方法，如广告、生物信息学、反恐、欺诈检测、政治、社会学等，都是基于数据分析。该项目将开发新的数据分析算法，并强有力地保证其正确性和效率。基于这些算法的工具无需专业知识，就可以在远离学术界的创新数据驱动应用中使用。该项目还将包括培训学生掌握数据分析的先进技术。在这个项目中考虑的算法涉及一种称为“平方和”的代数逻辑的自动推理。自动推理需要在表达性和简单性之间进行微妙的权衡，以促进快速有效的推理。平方和能够表达大量的统计推理，但又足够简单，可以设计易于处理的推理算法。该项目将考虑如何使用这些算法从从中抽取的数据样本中推断总体分布或总体。该项目的主要目的是开发有效的算法，以保证在数据分析过程中发现所有相关的统计事实。该项目将进一步开发这些算法来解决计算机视觉和自然语言处理等领域的问题。除了开发特定领域的算法外，该项目还将考虑使用高次多项式的平方和推理。虽然这种标准意义上的推理是难以处理的，但该项目旨在借助待推理分布的数据样本来模拟具有这种高阶表达式的推理。该项目还将研究平方和在这种高阶表达式中的表达能力。具体来说，该项目将调查这种推理是否可以模拟其他逻辑，如分辨率（反之亦然），并将进一步调查其基本捕获统计概念的能力的程度。

项目成果

Hardness of Maximum Likelihood Learning of DPPs

• DOI: 10.48550/arxiv.2205.12377
• 发表时间: 2022-05
• 期刊: Electron. Colloquium Comput. Complex.
• 作者: Elena Grigorescu;Brendan Juba;K. Wimmer;Ning Xie

More Accurate Learning of k-DNF Reference Classes

更准确学习k-DNF参考课

• DOI: 10.1609/aaai.v34i04.5864
• 发表时间: 2020
• 期刊: Proceedings of the AAAI Conference on Artificial Intelligence
• 作者: Juba, Brendan;Li, Hengxuan
• 通讯作者: Li, Hengxuan

Conditional Linear Regression

条件线性回归

• 发表时间: 2020
• 期刊: Proceedings of Machine Learning Research
• 作者: Calderon, Diego;Juba, Brendan;Li, Sirui;Li, Zongyi;Ruan, Lisa
• 通讯作者: Ruan, Lisa

Polynomial-time Implicit Learnability in SMT

SMT 中的多项式时间隐式可学习性

• 发表时间: 2020
• 期刊: Proceedings of the 24th European Conference on Artificial Intelligence - ECAI 2020
• 作者: Mocanu, Ionela G;Belle, Vaishak;Juba, Brendan
• 通讯作者: Juba, Brendan

List Learning with Attribute Noise

使用属性噪声进行列表学习

• 发表时间: 2021
• 期刊: Proceedings of The 24th International Conference on Artificial Intelligence and Statistics
• 作者: Cheraghchi, Mahdi;Grigorescu, Elena;Juba, Brendan;Wimmer, Karl;Xie, Ning
• 通讯作者: Xie, Ning