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

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

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.