Dimensionality Reduction for Designing Online Algorithms

已经开发了许多方法来预测一组专家中的最佳预测者。这些方法具有相同的机制，即根据专家建议的加权平均值进行预测。然而，在许多自然应用中，我们必须处理指数级或无限多的专家组合，因此显式地保持所有专家的权重在计算上是不可行的。在这项研究中，我们提出了一种方法，保持一些参数向量在一个低维空间，隐式表示的权重向量，我们可以有效地模拟加权平均预测。本文主要研究结果如下：针对图的路径所对应的指数型多个预测子，给出了一种通过在边上保持概率流来有效模拟加权平均预测的方法.本文提出了一种新的Boosting方案，通过对域的反复划分和合并，形成一个决策图作为最终假设。这给出了一个统一的框架，我们现在可以分析AdaBoost型和决策树型算法，被认为是来自完全不同的principles.We推广的模型，使学习者可以看到专家的损失（风险信息）的界限，并给出了一个严格的性能约束的聚合算法。

A number of methods have been developed for predicting nearly as well as the best predictor among a set of experts. These methods have the same mechanism of making predictions that are based on the weighted average of experts' advices. In many natural applications, however, we have to deal with exponentially or infinitely many experts to be combined, and so it is computationally infeasible to explicitly maintain weights for all experts. In this research, we proposed a method of maintaining some parameter vector in a low dimensional space that implicitly represents the weight vector, with which we can efficiently simulate the weighted average prediction. Below are the major results obtained in this research project.For the class of exponentially many predictors associated with the paths of a graph, we gave a method of efficiently simulating the weighted average prediction by maintaining probabilistic flows on the edges. This gives a new kernel called the path kernel which turned out to be useful in many applications.We proposed a new scheme of Boosting by dividing and merging the domain repeatedly to form a decision diagram as its final hypothesis. This gives a unified framework in which we can now analyze the AdaBoost-type and the Decision Tree-type algorithms that were thought to be derived from quite different principles.We generalized the model so that the learner is allowed to see the bounds on the losses of experts (risk information) and gave a tight performance bound of the Aggregating Algorithm.