Statistical Methods for Prediction of Individual Sequences

预测个体序列的统计方法

• 批准号: 0707060
• 负责人: Peter Bartlett
• 金额: $ 23.72万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-07-01 至 2011-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0707060&HistoricalAwards=false
• 关键词: Statistical; Methods; Prediction; Individual; Sequences

In many prediction problems that arise, for example, in computer security and computational finance, the process generating the data is best modeled as an adversary with whom the predictor competes. The broad goal of this research project is the analysis and design of statistical methods for complex prediction problems in an adversarial setting: a prediction strategy must predict any individual sequence almost as accurately as the best strategy in some comparison class. The research focuses on statistical methods, which are based on probabilistic models of the data, since (a) these methods are commonly used in practice; (b) there is evidence that these methods perform well in adversarial settings; (c) there are good prospects of exploiting the computationally efficient approaches that have been developed for probabilistic settings, which is especially important for high-dimensional problems; and (d) positive results in adversarial settings should provide better understanding of the robustness of statistical methods in probabilistic settings. The research aims are: to develop techniques for analyzing the performance of statistical methods, such as Bayesian methods, for the prediction of individual sequences; to improve the understanding of appropriate ways to measure the complexity of a probability model used by these methods; to elucidate the impact of computational simplifications (such as empirical Bayes approaches and MAP estimates) on the performance of these prediction strategies; and hence to develop design methodologies for computationally efficient statistical methods for complex adversarial prediction problems.There are many estimation and prediction problems for which it is appropriate to model the process generating the data as an adversary with whom the predictor competes. Such problems are common in information technology. For instance, in the problem of spam filtering, the aim is to label incoming email as either legitimate or spam, but at the same time, spammers try to design email messages that slip past these spam filters. Thus, the prediction problem is a two-player repeated game. Similar decision problems arise in computer network security (for instance, the problem of deciding whether network traffic is normal or the result of a denial-of-service attack) and in internet search (for instance, deciding if a highly linked web page is genuinely authoritative and should have a high page rank). In these problems, some fraction of the data seen by the prediction strategy is chosen by an adversary who aims to fool the prediction strategy. These adversarial problems are also common in financial applications. Suppose that the predictions that emerge from a financial time series analysis are used to optimize the allocation of capital across a portfolio. Then, in the short term, it is in the interests of other market players to act so as to diminish the returns of the portfolio, and thus render the predictions inaccurate. It is common for statistical methods, such as Bayesian methods, to be applied to these adversarial prediction problems, despite the fact that they are designed for probabilistic, rather than adversarial, models of the data. This research project aims to develop techniques to understand the inherent limitations on the performance of these prediction methods, and hence inform the design of more powerful prediction methods. It focuses on the predictive accuracy and computational efficiency of methods that are suitable for the complex and high-dimensional prediction problems that arise in practise.

在出现的许多预测问题中，例如在计算机安全和计算金融领域，生成数据的过程最好被建模为与预测器竞争的对手。该研究项目的总体目标是分析和设计对抗性环境中复杂预测问题的统计方法：预测策略必须几乎与某些比较类别中的最佳策略一样准确地预测任何单个序列。 研究重点是基于数据概率模型的统计方法，因为 (a) 这些方法在实践中普遍使用； (b) 有证据表明这些方法在对抗性环境中表现良好； (c) 利用为概率设置开发的计算高效方法具有良好的前景，这对于高维问题尤其重要； (d) 对抗性环境中的积极结果应有助于更好地理解统计方法在概率环境中的稳健性。研究目标是：开发分析统计方法性能的技术，例如贝叶斯方法，用于预测单个序列；提高对衡量这些方法所使用的概率模型复杂性的适当方法的理解；阐明计算简化（例如经验贝叶斯方法和 MAP 估计）对这些预测策略性能的影响；因此，为复杂的对抗性预测问题开发计算有效的统计方法的设计方法。对于许多估计和预测问题，适合将生成数据的过程建模为与预测器竞争的对手。此类问题在信息技术中很常见。例如，在垃圾邮件过滤问题中，目标是将传入的电子邮件标记为合法邮件或垃圾邮件，但与此同时，垃圾邮件发送者试图设计能够绕过这些垃圾邮件过滤器的电子邮件。因此，预测问题是一个两人重复博弈。类似的决策问题也出现在计算机网络安全（例如，确定网络流量是否正常或拒绝服务攻击的结果的问题）和互联网搜索（例如，确定高度链接的网页是否真正有效）中。具有权威性并且应该具有较高的页面排名）。 在这些问题中，预测策略看到的数据的一部分是由旨在欺骗预测策略的对手选择的。 这些对抗性问题在金融应用中也很常见。假设金融时间序列分析得出的预测用于优化投资组合中的资本配置。 然后，在短期内，采取行动减少投资组合的回报，从而导致预测不准确，符合其他市场参与者的利益。 统计方法（例如贝叶斯方法）通常应用于这些对抗性预测问题，尽管它们是为概率模型而不是对抗性数据模型设计的。 该研究项目旨在开发技术来了解这些预测方法性能的固有局限性，从而为更强大的预测方法的设计提供信息。 它侧重于适用于实际中出现的复杂和高维预测问题的方法的预测精度和计算效率。