典型的集合概念

机器算法验证 直觉 信息论
2022-02-16 01:32:03

我认为典型集合的概念非常直观:如果序列出现的概率很高,则的序列将属于典型集合因此,任何可能在中的序列。(我避免使用与熵相关的正式定义,因为我试图定性地理解它。)nAϵ(n)Aϵ(n)

但是,我读过,一般来说,最可能的序列不属于典型的集合。这让我很困惑。

典型集合有直观的定义吗?或者它只是一个与常识没有太大关系的数学工具?

4个回答

我知道您明确要求提供直观的解释并省略正式定义,但我认为它们相当相关,所以让我回忆一下典型集的定义:

X1,X2,...iid随机变量那么关于 p(x) 的典型集合A_是序列的集合具有属性 这意味着对于一个固定的,典型的集合由概率接近的所有序列组成因此,为了让一个序列属于典型集合,它的概率必须接近 p(x)Aϵ(n)p(x)(x1,x2,...,xn)χn

(1)2n(H(X)+ϵ)p(x1,x2,...,xn)2n(H(X)ϵ)
ϵ2nH(X)2nH(X),但通常不会。为了理解原因,让我通过应用来重写等式 1 。log2

(2)H(X)ϵ1nlog2(1p(x1,x2,...,xn))H(X)+ϵ

现在典型的集合定义更直接地与熵的概念相关,或者换句话说,随机变量的平均信息。中间项可以被认为是序列的样本熵,因此典型的集合是由所有给我们提供的信息量接近随机变量的平均信息量的序列组成的。最可能的序列通常给我们提供的信息少于平均值。请记住,结果的概率越低,它给我们的信息就越高。为了理解为什么让我举个例子:X

假设您住在一个天气很可能是晴天和温暖的城市,温度介于 24°C 和 26°C 之间。你可能每天早上都会看天气预报,但你不会太在意它,我的意思是,它总是阳光明媚和温暖。但是,如果有一天天气男/女告诉你今天会下雨而且很冷,那会改变游戏规则。你将不得不穿一些不同的衣服,带上雨伞,做一些你通常不会做的事情,所以天气预报员给了你一个真正重要的信息。

总而言之,典型集合的直观定义是它由序列组成,这些序列为我们提供的信息量接近预期的源(随机变量)。

Diegobatt 的回答很好地直观地解释了典型集合是什么。这个答案将解决 OP 的另一个问题,由@tomwesolowski 回应:你为什么要以一种可以排除最可能元素的方式定义典型集合?

简短的回答是,典型集合主要是一种理论工具。它的定义是为了帮助证明某些东西,而这个定义是最方便证明的定义。这是一个很好的例子,说明理论需求有时可以胜过数学中的直觉偏好。

典型集合由信息论之父克劳德香农定义。他想确定一个人如何有效地编码来自固定字母表的符号流,假设每个符号都是来自某个分布的iid随机样本。他的主要见解是:

  1. 有一组易于识别的、相对较小的“典型”序列在流中经常出现不成比例的情况。
  2. 为这组“典型的”序列分配最短的编码会产生最有效的编码(渐近地,随着流的输出任意增长)。

香农发现的典型集合精确地由其自信息或“惊奇性”与流的源分布的平均预期自信息大致相同的序列组成。这样的序列是“典型的”,因为它们的信息是关于平均值的,但是这个定义隐含地排除了那些信息明显少于平均值的序列。这些信息量较少的序列也是最可能的序列。

正如 OP 所指出的,这在直觉上并不吸引人!从表面上看,典型的集合听起来应该包含所有最可能的序列,直到某个阈值。这将更好地代表通常在流中看到的内容。

但是香农不想要最“典型”的可能典型集合;他想要一个可以很容易地证明他想证明的结果。正如这个答案所指出的,香农定义的典型集合保证存在,保证很小,并且保证与您可能提出的任何其他集合一样小。添加最可能的元素使集合更有可能,这是好的,但它也会使集合更大,这是不好的。对证明可靠性的净影响尚不清楚。它可能会使证明更复杂。最好不要修复没有损坏的东西。

如果您的目标与 Shannon 不同,那么您偏好的典型性概念也可能不同。例如,在霍夫曼编码中,最可能的符号(或符号序列)得到最短的代码。从某种技术意义上说,霍夫曼编码是香农原问题的最优解,更能捕捉到我们对典型性的直觉。另一方面,香农对典型性的定义更便于证明事物。

根据这些讲义中的定理 6.3,无论我们是采用概率最高的序列子集还是概率接近的序列子集2nH(X)(来自典型集合)我们必须大约取2nH确保选择的子集包含高概率的随机序列。我们通常采用典型的集合元素,因为我们可以更容易地限制它的大小。

典型集合的想法隐含地将结果序列视为多集合,即它假设您只关心每个序列的直方图,例如,您认为所有 10 个抛硬币序列具有 7 个正面和 3 个反面是等价的。

想象一下,你有一个非常有偏见的硬币,比如说p(H)=.9. 这只是二项分布。最可能的 100 次抛掷序列是 100 次正面,但只有 1100 次正面序列。包含 10 个尾巴的序列呈指数级增长,但单独出现的可能性要小得多。最大的数列是半头半尾,但这种可能性更小。因此,单个序列的概率与类中等价序列的数量之间存在张力。当序列中的频率与概率匹配时,达到最大概率。

重要的结果是,对于足够长的序列,几乎所有采样序列都将任意接近预期频率,即随着所考虑序列长度的增加,分布变得非常峰值。

例如观察到105的折腾序列P(H)=.9硬币将获得序列104+/300尾部 99% 的时间,因为序列中尾部数量的标准偏差约为 100。尽管这是最可能的特定序列,但所有正面的概率可以忽略不计。

典型集合是这个想法的更一般的、信息理论定义的版本。