https://www.youtube.com/playlist?list=PLruBu5BI5n4aFpG32iMbdWoRVAA-Vcso6
信息论是克劳德·香农为解决通信问题而创立。香农定义的基本问题是在不可靠通道上实现可靠通信。
通道是一个从源信号到接收信号的传递介质。常见通道例子包括:
所有通道的共同属性是:接收信号与发送信号不完全相同。这是因为通道Noise或其他因素使得接收信号会与发送信号有差异。
信息论常用的二进制对称通道模型假设:
通信系统的目标是使接收消息等于发送消息,实现高质量的通信。
实现可靠通信的方法有两种:
信息论就是研究第二种系统层方法,通过编码增加冗余来实现可靠通信。
在上一次讲座中,我们介绍了可靠通信,以及如何通过添加冗余来纠正错误。本次讲座将讨论数据压缩,以便理解如何利用源中的冗余来压缩文件。
首先,我们将通过具有固定输出概率分布的理想化源来理解压缩,例如假设骰子。源的输出序列包含可预测的模式,这就是可压缩的原因。
香农提出用来量度信息量的香农信息量(H)定义为输出事件的概率倒数对数。也就是说,低概率事件包含更多信息。H的单位是比特。
香农还提出,独立随机变量的H是可加成的。例如掷骰子和掷毛笔的H等于各自H之和。
基于H,我们可以定义熵(Havg)概念。熵衡量整个源的不可预测性。对于骰子,熵等于每次掷骰子取得各个点数的H平均值。
压缩目标是尽可能地接近源的熵下限。我们将用几个理想化源例子来验证这一点,并解释如何实现压缩。
香农信息内容可以用来量测信息的量,其定义为事件发生概率的对数 Reciprocal。如果事件的概率为P,则其香农信息内容为log2(1/P) 位。
熵是一组事件的平均香农信息内容,用来衡量平均信息量。如果事件概率分别为P1,P2…Pn,则熵定义为:-ΣiPilog2Pi
香农源码定理断言,假设从源头获取一长串n个结果,则可以用大约n×熵位数来压缩它们。
63游戏中,答案可选0、1、63三个数,可以采用二进制问题将答案找出,每个问题的香农信息内容都为1bit。总共需要6bit就可以唯一确定答案。
潜水艇游戏中,64个方格中只有1个放有潜水艇。每个方格开枪询问的香农信息内容取决于其中是否有潜水艇的概率。
弯钱彩票中,弯钱每次掷出0或1,1000次结果决定中奖票号。如果要保证99%中奖概率,需要买多少张票。
这次课主要探讨了香农源编码定理及符号编码。
香农源编码定理指出,如果从一个随机源中得到一个很长的独立同分布的字符串,那么这些结果可以用大约n倍熵的位数进行压缩。
上次课通过计算典型集进行了证明。典型集的概念指,如果从一个源中得到一个长度为n的独立结果字符串,那么这个字符串极有可能属于典型集。典型集中的元素近似具有相同概率,数量为2^nH,其中H为熵。
符号编码是一种可以应用于英语或其他有字母表的语言的编码方法。假设每个字符发生的概率分布是已知且非均匀的。
符号编码的工作流程为:
给定一个字母表和每个字母的发生概率。
将每个字母映射到一个二进制代码字,例如:a映射为001。
将源文件中每个字母替换为对应的代码字,无间隔拼接输出。
接收者根据代码表将编码还原为原始字符串。
符号编码的理想性目标为:编码长度期望最小,且可唯一解码。可唯一解码表示对任意不同字符串x和y,其编码C(x)不等于C(y)。
在上一课时,我们定义了符号码,并从理论和实践两方面提出了符号码相关的问题。这给我们提供了更充分的证据支持这个 CLAIM,我们现在已将其正式证明。
信息内容的正确量度标准是使用log2基作为可能性P的倒数。这不仅是一个合理的信息内容量度标准,还反映出如果使用良好的压缩方法,我们应该能将这个结果编码为的位数。
熵是信息内容平均值。源编码定理指出,如果源的熵为H,我们可以将结果压缩为NH位。
我们研究了符号码,它是通过给字母表中的每个字母分配二进制字符串来完成编码的。我们阐述了一些理论结果,其中一些没有给出证明。
我们理解了唯一可解码性如何限制代码长度。如果让某些代码长度更短,就必须让其他代码长度更长。
我们介绍了前缀码概念,即编码和二叉树有关的易于解码的码。如果代码长度等于信息内容,我们就可以获得最佳压缩效果,每个符号的平均长度就是熵。
我们还断定,使用最优符号码可以将长度控制在熵的1位范围内。
最后,我们研究了Huffman算法,这是一个非常简单的生成最优符号码的算法。
Huffman算法保证生成前缀码,同时也生成最优符号码。任何非前缀码的预期长度我们都可以用前缀码匹配。
然而,符号码存在一个问题就是无法与动态概率分布匹配。需要一个方法来解决这个问题。
最后一次课程中,介绍了符号码和算数编码两种数据压缩方法。
符号码可以通过哈夫曼算法获得最优符号码,但其压缩效率一般在熵值以上1位/字符范围内,当源数据的熵值很低时(如0.1位/字符),压缩效率不高。
算数编码将二进制文件看作一个0-1实数区间,将任何源文件映射成一个实数区间,可以将压缩误差控制在源文件整体信息量的2位以内,通常比符号码效率高得多。
本课程将介绍“噪声信道编码”,也即在传输过程中可能发生错误的信道上如何编码和解码数据。
首先给出一个4元集合的符号码实例,计算如果从此源中编码出来的二进制流中随机选择1位,其为1的概率。通过信息论证明最终答案应为0.5。
然后进一步解释信息理论思想,信息量不仅可以用来衡量源数据的压缩上限,也可以描述通道上的噪声水平。本课将介绍相关的信息量度量,为后续的信道编码奠定理论基础。
介绍现实压缩算法PPM的工作原理:
根据文档中已看到的最后5字符作为上下文
检索文档中是否以此上下文开头,统计各可能后续字符出现的频率
根据频率生成条件概率分布预测下一个字符
同时为未见字符留有概率,便于应对新文本
该方法利用上下文信息做出近似概率预测,实现语义级的压缩,效率很高。
以此为例说明现代压缩如何结合信息源特征与统计数据,实现高效编码。
上次讨论了推理和信息量度对一对相关随机变量的定义。
推理的一例是三门问题。这个游戏中,游戏主持人会将奖品随机藏在三扇门中的一扇后面。玩家选择其中一扇门,例如选择第一扇门。然后游戏主持人会开启另一扇门以不泄漏奖品,并给玩家选择是否坚持原选择或者选择另一扇没开的门。
| 信息量度中定义了联合熵H(X,Y)、边缘熵H(X) H(Y)、条件熵H(X | Y) H(Y | X)以及互信息I(X;Y)。互信息衡量了两个随机变量之间的依赖程度。 |
噪声信道通过一组条件概率表征信道本身。要得到联合概率分布,需要给出输入概率分布P(X)。这样通过输入分布与条件概率相乘,可以定义联合分布P(X,Y),从而进行推断和信息量计量。
常见的噪声信道包括:
选择翻转概率为10%的二元对称信道,输入概率分布为0的概率为0.9,1的概率为0.1。
给定 observes输出,求输入概率:
P(X=1|Y) = P(Y|X=1)P(X=1)/P(Y) = (1-F)×0.1/(1-F)×0.9 + F×0.1 = 0.1/(0.9×(1-F)+0.1×F)
| P(X=0 | Y) = 1 - P(X=1 | Y) |
通过合适的编码和解码方案,即使使用不可靠的噪声信道,也可以实现随意接近理想可靠性的通信。
上一讲中,我们定义了信道的容量,信道是一个输入与输出概率分布的集合。计算容量的方法是:
发明一个输入概率分布
计算输入与输出之间的互信息
最大化互信息,得到的最大值就是该信道的容量
我们介绍了一个简单的“打字机”信道模型。在这个模型中,输入字母会有概率发生错误,输出一个随机的字母。
我们计算了这个模型的容量和最优输入分布:
容量是log27比特
最优输入分布是每个字母以1/27的概率发送
这样可以使输出分布均匀,从而达到最大的互信息。
噪声信道编码定理说明,对任何信道来说:
都存在各种编码方案
各个方案都有码率和错误率两个参数
可以找到方案,使错误率趋近于0,码率可以任意接近信道的容量C
也就是说,理论上可以在任意非零码率下,实现几乎无错误的通信。
为了证明这个定理,我们引入“扩展信道”的概念。
对一个信道连续使用n次,就是一个扩展信道。它的输入字母集大小是原信道字母集的n次方。
如果输入分布选择Capacity- achieving分布,扩展信道的“典型输出集”规模将是2^{nC}个。
这意味着,我们可以找到约2^{nC}个“非混淆”输入,每次使用扩展信道能够传输nC比特信息。
最后,笔记给出了噪声信道编码定理对二值对称信道的具体证明。
根据信道编码理论定理,对于任何一个信道,通过最大化互信息来找到它的容量。然后可以设计一个编码器和解码器通过这个信道可靠地传输信息,意思就是可将误差概率降低到任意接近于0的值。
通道容量就是在不产生误码的前提下,可以通过该通道传输的最大信息速率。
二值擦除通道中,信号有三种可能结果:0、1或问号。问号表示信号丢失。
通道容量的计算分两种方法:
计算输入和输出的联合熵,然后输入给定输出的条件熵。
将Capacity看作三步传输的和:第一步判断是否丢失,第二步如果没有丢失判断是0还是1,第三步如果丢失则没有信息。
两种方法计算结果都为:Capacity = 1 - F,其中F表示问号的概率。
如果通道加入反馈链接,编码器可以知道输出结果,则可以采取如下编码策略:
这样采用反馈,平均每1-F时间内就可以传输1个 bit,传输速率不变,仍为1-F。
所以反馈虽然方便编码,但不会提高通道实际传输率。信息论最佳编码不需要依赖反馈。
贝叶斯推断是一种统计推断方法,用于从观测数据中推断未知参数的值。
例如在宇宙论研究中,通过观测数据估计未知的宇宙模型参数;或通过实验数据推断实验模型的参数值。
这节课主要介绍高斯分布下的参数估计,后续会介绍更广泛的概率模型和推断方法。高斯模型推断比较简单,真正推广视野的是学习更通用的贝叶斯推断思想。
k-means聚类算法假设数据点存在于一个实值空间内,例如自动识别蔬菜的属性如波长反射率和形状等长宽比。
算法包含以下步骤:
随机将k个数据点作为初始聚类中心点(即means)
将每个数据点分配到与其距离最近的聚类中心点。这里使用欧式距离。
更新每一个聚类中心点的位置,使其等于该聚类内所有数据点的平均位置。
重复步骤2和3,直到聚类中心点位置不再改变。
把数据假设成来自多个高斯分布的混合,可将聚类问题建模为求解这个混合高斯模型的参数问题。
例如,如果数据来自两个高斯分布,则参数包括每个高斯的平均值和方差。
许多聚类算法的工作原理就是通过求解这个隐含的混合高斯模型,找到每个数据点所属的高斯分布,即其所属的聚类。
将一个推断问题建模为贝叶斯网络,通过求解后验概率分布解决这个问题。
例如判断一组数据点是否来自一个还是一个以上高斯分布,可以建立模型假设数据来自一个或两个高斯,使用贝叶斯定理计算后验概率。
用来近似无法用解析方法求解的积分或概率分布,常用于解决贝叶斯推断问题。
下一课将详细介绍常见的蒙特卡罗算法,如标识采样、重数采样等,以解决更复杂的混合模型推断问题。
这节课主要介绍变分方法来拟合概率分布。
变分方法的基本思想是:将难以计算的复杂概率分布P(x),用一个易于计算的分布Q(x)来近似。Q(x)通过一些可调节的参数θ来定义。然后通过调整θ,使Q(x)尽可能接近P(x)。
常用衡量两个分布之间距离的方法是KL散度。KL散度有两种形式:
| D_{KL}(Q | P) = ∫Q(x)log(Q(x)/P(x))dx | |
| D_{KL}(P | Q) = ∫P(x)log(P(x)/Q(x))dx |
它们的公式分别表示Q分布相对P分布的期望误差和P分布相对Q分布的期望误差。
变分法的对象函数定义为变分自由能:
F(θ) = 〈E(x)〉_Q - H(Q)
其中〈E(x)〉_Q表示Q分布下E(x)的期望值,H(Q)表示Q分布的香农熵。
通过调整θ,使F(θ)达到最小,即实现Q(x)近似P(x)。此外,当F(θ)达到最小时,它也提供对对数归一化常数logZ的下界。
如果P(x)的能量函数E(x)和Q(x)选择合适的形式,变分自由能F(θ)是可能计算的。
以正态分布为例,如果选择Q(x)也为正态分布,就可以计算F(θ),从而实现Q(x)来拟合难计算的后验分布P(x)。
内容寻址存储器就是根据内容来识别和提取记忆,即使部分信息含糊不清。
这个挑战的具体描述是:设计一个有25个变量的动态系统,每个记忆以25位状态表示。该动态系统的25个变量会随时间变化,使得动态的稳定点定位于3个所需的记忆上。且设计的动态系统要有能调节动态的多个参数。通过调整这些参数,可以使稳定点位于正确的位置上。且这些稳定点应该是吸引稳定点,即如果状态接近所需记忆,动态就会把状态带向该记忆。
内容寻址存储器的正统方法包括:
使用存储器区域保存不同记忆,每个记忆附带标签。
将状态x与每一个记忆进行距离计算,得到各个距离值。
找到这些距离值中最小的一个,即closest记忆。
将状态x覆写为closest记忆。
但是这个方法不具有可扩展性和鲁棒性。如果有记忆需要增加,需要更换硬件;如果参数受损,整个动态系统将无法正常工作。
约翰·霍普菲尔德提出使用反馈神经网络来解决内容寻址存储器问题。
该网络包含若干个神经元,每个神经元都会将输出广播给其他所有的神经元。网络中的连接是双向的。记忆以网络状态的稳定点表示。
霍普菲尔德网络的关键规则是:权重对称,即从神经元1到神经元3的权重,等于从神经元3到神经元1的权重。
通过调整这些对称权重,可以使网络在所需记忆处形成吸引稳定点。且新记忆可以通过轻微调整现有权重来添加,网络参数受损后仍可以正常工作。
本质上,它利用了动态系统的稳定性来实现内容寻址,具有可扩展性和鲁棒性。解决了正统方法中的问题。