Relative loss bounds for on-line density estimation with the exponential family of distributions
Relative loss bounds for on-line density estimation with the exponential family of distributions
复制标题
DOI：
10.1023/a:1010896012157
复制
发表时间：
2001-06-01
期刊：
影响因子：
7.5
通讯作者：
Warmuth, MK
中科院分区：
文献类型：
--
作者：
Azoury, KS;Warmuth, MK
我们考虑在线密度估计的参数化密度从指数族。在线算法每次接收一个示例，并保持一个参数，该参数基本上是过去示例的平均值。在接收到一个例子之后，该算法会产生一个损失，这是该例子相对于该算法的当前参数的负对数似然。离线算法可以根据所有的例子来选择最佳的参数。我们证明的额外的总损失的最佳离线参数的总损失的在线算法上的界限。这些相对损失界限适用于任意序列的示例。目标是设计具有最佳可能的相对损失界限的算法。我们使用Bregman分歧来推导和分析每个算法。这些分歧是两个指数分布之间的相对熵。我们还使用我们的方法来证明线性回归的相对损失界。
We consider on-line density estimation with a parameterized density from the exponential family. The on-line algorithm receives one example at a time and maintains a parameter that is essentially an average of the past examples. After receiving an example the algorithm incurs a loss, which is the negative log-likelihood of the example with respect to the current parameter of the algorithm. An off-line algorithm can choose the best parameter based on all the examples. We prove bounds on the additional total loss of the on-line algorithm over the total loss of the best off-line parameter. These relative loss bounds hold for an arbitrary sequence of examples. The goal is to design algorithms with the best possible relative loss bounds. We use a Bregman divergence to derive and analyze each algorithm. These divergences are relative entropies between two exponential distributions. We also use our methods to prove relative loss bounds for linear regression.