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.