MCS: AF: Small: Algorithms for Large Scale Prediction Problems

在许多应用领域出现的大规模预测问题中，数据非常丰富，计算资源制约着预测方法的性能。本研究项目的主要目标是设计和分析大规模预测问题的方法，使有限的计算资源得到有效利用。主要目的是：提高我们对预测方法的准确性与其计算需求之间权衡的理解；开发自适应选择模型复杂度的模型选择方法，使可用的计算资源具有最佳的预测精度；提高我们对使用分布式计算资源解决大规模预测问题的难度的理解；开发异步在线预测的分析技术和方法，利用其灵活性来响应无序查询；从而为大规模预测问题开发出有效的方法。随着数据采集和存储成本的降低，大量的数据集可以在许多领域使用，包括网络信息检索、生物、医学和物理科学、制造业、金融和零售业。因此，对于许多统计预测问题，可用的数据量是如此之大，以至于我们可以将其视为无限的。例如，使用图像和标题数据来训练一个预测规则，该规则可以自动为图像选择合适的标签，网络提供了有效的无限量的训练数据。类似的情况也出现在使用点击流数据来预测访问热门网站的访问者的选择，或者使用客户对电影的评分来提供有用的推荐。对于这些大规模的预测问题，性能的瓶颈不是数据量，而是可用的计算资源。许多现代预测方法都是从数据宝贵的角度来设计和分析的：它们的目标是在给定的样本量下获得最佳的预测精度。但对于大规模的问题，这是错误的观点；计算是宝贵的资源，必须明智地使用。这种观点的转变带来了一些新的权衡。最重要的权衡之一是选择预测规则的复杂性。我们是否应该使用我们的计算资源来尝试优化一个非常复杂的预测规则家族，这将不允许我们收集很多数据？或者我们应该通过使用更简单的预测规则来节省计算，而把这些计算花在收集更多的数据上？本研究项目旨在提高我们对这些权衡的理解，从而为大规模预测问题制定策略，最好地利用可用的计算资源。

In large scale prediction problems that arise in many application areas, data is plentiful, and it is computational resources that constrain the performance of prediction methods. The broad goal of this research project is the design and analysis of methods for large scale prediction problems that make effective use of limited computational resources. The main aims are: to improve our understanding of the tradeoff between the accuracy of a prediction method and its computational requirements; to develop model selection methods that adaptively choose the model complexity to give the best predictive accuracy for the available computational resources; to improve our understanding of the difficulty of solving large scale prediction problems using distributed computational resources; to develop analysis techniques and methods for asynchronous online prediction, which exploit the flexibility to respond to queries out of order; and hence to develop effective methods for large scale prediction problems.As data acquisition and storage has become cheaper, enormous data sets have become available in many areas, including web information retrieval, the biological, medical, and physical sciences, manufacturing, finance and retail. Consequently, for many statistical prediction problems, the amount of data available is so huge that we can treat it as unlimited. For instance, in using image and caption data to train a prediction rule that can automatically choose appropriate labels for images, the web provides an effectively unlimited supply of training data. Similar situations arise in using click stream data to predict the choices of visitors to a popular web site, or in using customers' ratings of movies to make useful recommendations. For these large scale prediction problems, the bottleneck to performance is not the amount of data, rather it is the computational resources that are available. Many modern prediction methods have been designed and analyzed from the perspective that data is precious: they aim for optimal predictive accuracy for a given sample size. But for large scale problems, this is the wrong perspective; computation is the precious resource that must be used wisely. This shift in perspective introduces some novel tradeoffs. One of the most important tradeoffs arises in choosing the complexity of a prediction rule. Should we use our computational resources trying to optimize over a very complex family of prediction rules, which would not allow us to gather much data? Or should we save computation by using simpler prediction rules, and instead spend this computation on gathering more data? This research project is aimed at improving our understanding of these tradeoffs, and hence developing strategies for large scale prediction problems that best exploit the available computational resources.