RI: Small: Efficient Learning and Inference with Perturbations

学习和推理推动了许多不同领域的研究，如自然语言处理，计算机视觉，语音处理和计算生物学。在这些领域中，需要复杂的模型以便更好地表示真实世界对象（例如，句子、图像、语音、蛋白质）。因此，人们的目标是通过将对象表达为大量组成元素的相互作用来获得更多的表征能力。在产生更真实的模型的同时，这也增加了推断此类对象以及从数据学习此类推断模型的计算成本。随着现实世界中的对象变得大规模，这种情况也随之发生，这为研究使用随机算法来提高学习和推理的计算效率提供了机会。该项目还将通过实践学习理论课程、本科生参与研究以及在关于学习和推理主题的主要会议上举办研讨会来提供教育和推广机会。该项目的目标是开发用于大规模结构化预测问题的学习和推理的新型随机多项式时间算法。该项目旨在分析最大边际模型，最大后验扰动模型，潜变量模型，以及正则化和不同扰动概念之间的关系。该项目利用理论方法来创建新的算法，这些算法比现有方法具有实际优势。该项目的目标是产生在多项式时间内工作的算法，使用足够和必要的少量训练样本，并保证小的泛化误差。该项目中产生的所有软件都将是开源的，并可供下载。

Learning and inference drives much of the research in many diverse domains, such as natural language processing, computer vision, speech processing and computational biology. In these fields, complex models are required in order to better represent real-world objects (e.g., sentences, images, speech, proteins). As such, one aims to obtain more representational power by expressing objects as the interaction of a large number of constituent elements. While producing more realistic models, this also increases the computational cost of inferring such objects, as well as of learning such inference models from data. The situation worsens as real-world objects become large scale, which opens the opportunity to investigate the use of randomized algorithms to make learning and inference more computationally efficient. This project will also provide education and outreach opportunities through a Hands-on Learning Theory course, undergraduate involvement in research and workshops at major conferences on the topic of learning and inference.The goal of this project is to develop novel randomized polynomial-time algorithms for learning and inference in large-scale structured prediction problems. The project aims to analyze maximum margin models, maximum a-posteriori perturbation models, latent variable models, and the relationship between regularization and different notions of perturbation. The project makes use of theoretical methods for creating new algorithms with practical advantages over current methods. The project aims to produce algorithms that work in polynomial-time, use a small sufficient and necessary number of training samples, and have a guarantee of small generalization error. All the software produced in this project will be open-sourced, and made available for download.