Applying Learning Theory to Systems Problems

这个项目的重点是将学习理论的成果应用于现实生活中的问题。这种基于应用的理论工作很重要，这样所研究的学习模型和问题才能尽可能地满足现实问题的需求。努力将理论技术应用于实际问题，可以更好地理解现实世界的问题，从而有助于指导未来的理论工作，促进理论成果向实践的转化。许多系统控制算法（例如网络协议）在其操作中严重依赖于特别方法，并且它们的性能可能对这些方法的鲁棒性非常敏感。这些特别的方法通常基于对操作环境的假设，例如，在没有可靠的统计基础的情况下，假设通信网络中流量模式的特定分布。该项目将开发一个基于正式学习方法的框架，以协助自动系统控制。该框架将有助于确定是否可以通过系统控制算法获得更好的性能。本课题的目标之一是继续研究TCP协议中动态调整应答延迟的方法。延迟确认有两个主要优点。首先，它允许对多个数据包进行一次确认。其次，如果一个数据包是在相反的方向上发送的，那么可以在传出的数据包上附带确认。但是，有一个权衡，因为延迟确认太久会增加延迟。目前使用的大多数TCP实现都采用某种类型的确认延迟机制。该项目采用不同的学习方案来预测TCP数据包到达。学习方案包括基于加权多数（WM）算法的学习方案、基于指数加权移动平均（EWMA）算法的学习方案和基于具有良好统计基础的分布假设的学习方案。新的想法包括新的损失函数（衡量学习者表现的函数），更适合于应用程序。本课题探索的另一个应用是通用程序的分支预测。一个快速、准确的分支预测器对于依赖于指令级并行（ILP）技术的计算机体系结构是无价的，例如流水线和超标量体系结构。许多商业架构采用分支预测方案，众所周知，即使预测精度的小幅提高也会大大增加可利用的ILP数量。分支预测问题的一个有趣的方面是，它需要在硬件中实现部分或全部算法。因此，无论采用什么方法，最终都会产生具有快速和紧凑硬件实现的算法。首席研究员在硬件设计和学习理论方面的经验将在这方面有所帮助。将学习理论的结果应用于这些问题和其他系统问题，将为定义新的理论学习模型提供指导，这些模型可以更好地模拟现实生活场景。本项目也将认真开发和研究这些新的学习模式。

CCR-9877080Scott This project will focus on applying results developed in learning theory to real-life problems. Such application-based theoretical work is important so that the learning models and problems studied capture as best possible the needs of real-life problems. Working to apply theoretical techniques to real problems creates a better understanding of the real-world problems and thus helps direct future theoretical work, facilitating the transfer of results from theory to practice. Many system control algorithms (e.g. networking protocols) depend heavily on ad hoc methods in their operation, and their performance can be very sensitive to the robustness of these methods. These ad hoc approaches are frequently based on assumptions made about the operating environment, e.g. assuming a particular distribution on the traffic patterns in a communication network without a sound statistical basis. This project will develop a framework based on formal learning methods for assisting in automatic system control. This framework will help to determine if better performance can be obtained by a system control algorithm. One goal of this project is to continue research on dynamically adjusting delays of acknowledgments in the TCP protocol. Delaying acknowledgments has two main advantages. First, it allows a single acknowledgment for more than one packet. Second, if a data packet is being sent in the opposite direction, then one can piggyback the acknowledgment on the outgoing packet. However, there is a tradeoff since delaying the acknowledgment too much can increase the latency. Most TCP implementations, used today employ some sort of acknowledgment delay mechanism. The project applies different learning schemes to predict TCP packet arrivals. The learning schemes include ones based on the Weighted Majority (WM) algorithm, ones based on the Exponentially Weighted Moving Average (EWMA) algorithm, and ones based on distributional assumptions with a sound statistical basis. The new ideas include new loss functions (functions that measure the learners' performance) that are more appropriate for the application. Another application explored in this project is that of branch prediction of general purpose programs. A fast, accurate branch predictor is invaluable to a computer architecture that relies on instruction-level parallelism (ILP) techniques, e.g. pipelined and superscalar architectures. Many commercial architectures employ branch prediction schemes, and it is well known that even a small increase in prediction accuracy can greatly increase the amount of ILP that can be exploited. An interesting facet of the branch prediction problem is that it requires some or all of the algorithms to be implemented in hardware. Thus whatever approaches are adapted eventually lead to algorithms that have fast and compact hardware implementations. The principal investigator's experience in hardware design and in learning theory will help in this regard. Applying learning theory results to these problems and other systems problems will then provide guidance in defining new theoretical learning models that better model real-life scenarios. This project will also carefully develop and study such new learning models.