Applying Learning Theory to Systems Problems

CCR-9877080斯科特 该项目将侧重于将学习理论中开发的结果应用于现实生活中的问题。 这种基于应用的理论工作是重要的，以便学习模型和问题研究尽可能捕捉现实生活中的问题的需要。 努力将理论技术应用于真实的问题，可以更好地理解现实世界的问题，从而有助于指导未来的理论工作，促进理论成果向实践的转化。 许多系统控制算法（例如网络协议）在其操作中严重依赖于自组织方法，并且其性能可能对这些方法的鲁棒性非常敏感。 这些自组织方法经常基于对操作环境的假设，例如，假设通信网络中的业务模式的特定分布而没有可靠的统计基础。 本项目将开发一个基于正式学习方法的框架，用于辅助自动系统控制。 该框架将有助于确定是否可以通过系统控制算法获得更好的性能。 本项目的目标之一是继续研究动态调整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.