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.