Learning Markov distributions: Does estimation trump compression?
Learning Markov distributions: Does estimation trump compression?
复制标题
学习马尔可夫分布：估计胜过压缩吗？
DOI：
10.1109/isit.2016.7541787
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
A. Suresh
中科院分区：
文献类型：
--
作者：
Moein Falahatgar;A. Orlitsky;Venkatadheeraj Pichapati;A. Suresh
大量的多学科研究集中在i.i.d的速度上。从理想化的I.I.到更实际的分布，我们可以估计Markov分布的速度具有相同的增长率，其估计损失具有不同的增长率，而对于I.I.D。最佳估计意味着最佳压缩从某种意义上说，这可以保证Markov分布的最佳估计，我们还构建了一种最适合估计和压缩的算法。远离此子类的零。
A significant amount of multidisciplinary research has recently focused on the rate at which i.i.d. distributions can be estimated. In particular, it was shown that for these distributions, optimal estimation implies optimal compression, hence in a sense for i.i.d. distributions, estimation “trumps” compression. Progressing from idealized i.i.d. to more practical distributions, we define and study the rate at which Markov distributions can be estimated. We determine this rate up to a constant factor and show two perhaps surprising implications. First, while the compression redundancy of i.i.d. and Markov distributions have the same growth rate, their estimation losses have different growth rates. Second, while for i.i.d. distributions optimal estimation implies optimal compression, for Markov distributions this implication does not hold, yet we show that any optimal compression algorithm has a smaller cumulative estimation loss than that guaranteed for optimal estimators, hence in a sense, for Markov distributions, compression "trumps" estimation. We also construct an algorithm that is optimal for both estimation and compression. Finally, we consider the important subclass of Markov distributions where all transition probabilities are bounded away from zero. For this subclass we determine the best estimation rate to the right constant factor and show that unlike i.i.d. distributions, for Markov distributions, the estimation rate of the full simplex and its interior differ.
近线性时间内的样本最优密度估计
DOI：
10.48550/arxiv.1506.00671
发表时间：
2015
期刊：
--
影响因子：
--
作者：
Acharya J
通讯作者：
Acharya J