RI: Small: Theory and Algorithms for Learning Perturbation Models

机器学习涉及设计和理解从经验中学习的计算机程序。现代复杂的环境(例如自然语言)需要使用灵活的概率模型，这些模型允许人们考虑大量可能的假设(语义)来支持观察(句子)。在这样的模型中，可能的结构(解析树)由功能引导，这些功能通过将结构分解成更小的片段来评估结构的适宜性。更丰富的模型需要更大的子集，这使得有效地探索大量可能的假设具有挑战性。这个项目通过结合参数随机化和组合优化来开发一种新的建模范式，从而对结构化建模进行了全新的审视。该组合提供了一种机制，用于在结构上诱导复杂的分布，同时明确地保持容易产生可能的结构。我们追求一个全面的计划来理解、扩展和设计这些扰动模型，以解决自然语言处理中重要的横切应用问题，如句法分析或结构化推荐任务，如释义。除了建模，拟议的工作有可能将工具和技术融合到从理论计算机科学(稳定性、可处理性)、组合优化(松弛、证书)到概率(凸体采样)等领域。开发的工具将在重要领域广泛使用，从计算机视觉、自然语言处理到医学信息学和计算生物学。拟议的工作本身就迫使从理论到应用的跨学科边界建立强大的协作关系。公安部将积极寻求这些机会。在这个项目中生产的所有软件都将是开源的，并可供下载。国际和平协会还将参与使高中生能够参与的外展活动。

Machine learning concerns designing and understanding computer programs that learn from experience. Modern complex settings (for example natural language) require the use of flexible probability models that permit one to entertain large numbers of possible hypotheses (semantics) underlying the observations (sentences). In such models likely structures (parse trees) are guided by functions that assess the suitability of structures by breaking them into smaller pieces. Richer models require larger subsets making it challenging to efficiently explore large sets of possible hypotheses. This project takes a fresh look at structured modeling by developing a new paradigm for modeling by combining randomization of parameters and combinatorial optimization. The combination provides a mechanism for inducing complex distributions over structures yet explicitly maintaining easy generation of likely structures. We pursue a comprehensive plan to understand, extend, and design these perturbation models towards the end goal of solving significant cross-cutting applied problems in natural language processing such as parsing or structured recommender tasks such as paraphrasing. Beyond modeling, the proposed work has the potential to merge tools and techniques across areas from theoretical computer science (stability, tractability), combinatorial optimization (relaxations, certificates), to probability (sampling from convex bodies). The tools developed will be broadly useful across prominent areas, from computer vision, natural language processing, to medical informatics and computational biology. The proposed work by its very nature compels strong collaborative relationships across disciplinary boundaries, from theory to applications. The PI will actively pursue these opportunities. All the software produced in this project will be open-sourced, and made available for download. The PI will also engage in outreach activities that enable high school students to participate.