Information bottlenecks

信息瓶颈

Notes on speech processing, 2.9.2021

语音处理笔记，2021年9月2日

Information bottlenecks and dimensionality reduction in deep learning

深度学习中的信息瓶颈与降维

Autoencoders and other deep neural networks with information bottlenecks have become fashionable. The heuristic idea is that the dimensionality of the hidden layers is reduced such that the network is forced to focus on the important part of the data. Experiments have also demonstrated that autoencoders are efficient in this sense. I have however been left wondering whether the amount of information can be characterized in exact terms. How much information flows through the bottleneck? How would we even measure that?

自编码器和其他带有信息瓶颈的深度神经网络已经变得流行起来。其启发式思想是，隐藏层的维度被降低，从而迫使网络专注于数据中的重要部分。实验也表明自编码器在这方面是有效的。然而，我一直好奇信息量是否可以用精确的术语来表征。有多少信息流经瓶颈？我们究竟该如何测量它？

This short note is my attempt at characterizing and understanding the problem. I will start with some classical concepts of information theory and linear algebra and then discuss the extent to which such concepts are applicable in machine learning. A central result is that dimensionality of a hidden layer cannot alone be used as a measure of information content.

这篇短文是我尝试表征和理解这个问题的一次努力。我将从信息论和线性代数的一些经典概念开始，然后讨论这些概念在机器学习中的适用程度。一个核心结论是，隐藏层的维度本身不能作为信息含量的度量。

Information content in discrete representations

离散表示中的信息含量

If a system has two states, A and B, then obviously we can represent the state by one bit. Four states can be represented by 2 bits, 8 states by 3 bits and in general, N states by log2(N) bits. We can therefore always easily determine the number of bits required for systems with a finite number of states. The amount of bits needed to describe the state is then a direct measure of the information content or entropy of the system.

如果一个系统有两个状态A和B，那么显然我们可以用1个比特来表示状态。4个状态可以用2个比特表示，8个状态用3个比特，一般来说，N个状态用log2(N)个比特。因此，对于有限状态系统，我们总是可以容易地确定所需的比特数。描述状态所需的比特数直接就是系统信息含量或熵的度量。

We can expand this to countable sets, such as integers, if we in additional have the access to probability of each state. Then we can make statements about average bitrate, that is, if we observe the system many times, how many bits do we on average need for representing the state? If the probability of state k is Pk, then the amount of bits needed to represent that state is log2 Pk. That bitrate, log2 Pk occurs at probability Pk, such that the average bitrate can be calculated as the sum, sum Pk log2 Pk, where the summation goes over all k. This applies also when k goes over an infinite but countable set.

我们可以将其扩展到可数集合，比如整数，如果我们还能获得每个状态的概率的话。那么我们就可以对平均比特率做出判断，也就是说，如果我们多次观察该系统，平均需要多少比特来表示状态？如果状态k的概率为Pk，那么表示该状态所需的比特数为log2 Pk。该比特率log2 Pk以概率Pk出现，因此平均比特率可以计算为总和∑Pk log2 Pk，其中求和遍及所有k。这也适用于k遍历无限但可数集合的情况。

Information content in linear, continuous valued systems

线性连续值系统中的信息含量

If the title is confusing, just think of linear algebra. How much information is there in a vector x of length N. Well, it is not really defined. What we do however know is that if we multiply it with a matrix A, as y=Ax, then if the matrix A is full rank, then all information is retained. In fact, then we can recover x from y by the inverse x=inv(A)y. No information is lost. Clearly the rank of A thus defines its capacity remove information. If rank(A)<N then information is lost and cannot be recovered from y.

如果标题令人困惑，只需想到线性代数。长度为N的向量x中包含多少信息？实际上，这并没有明确的定义。然而我们知道的是，如果我们将其乘以矩阵A，即y=Ax，那么如果矩阵A是满秩的，则所有信息都被保留。事实上，此时我们可以通过逆运算x=inv(A)y从y恢复x。没有信息丢失。因此，A的秩显然定义了其移除信息的能力。如果rank(A)<N，则信息丢失。例如，如果A的所有行都相同，则y的所有元素都相同，显然除了总能量外，关于x的所有信息都丢失了。

This is not yet the whole story though. In practical implementations of the inverse, we know that it is not only the rank which is important, but also the conditioning of A. If any of the singular values of A are close to zero, then A becomes ill-conditioned such that the recovery of x from y becomes numerically difficult. In the best case, we loose accuracy, such that x can be recovered only approximately, in severe cases information can be entirely lost. The information content is thus not only described by dimensionality, but also characterized by accuracy. As we shall see, I argue that it is more useful to characterize loss of information as a loss of accuracy rather than loss of dimensions.

然而这还不是全部。在逆运算的实际实现中，我们知道不仅秩是重要的，A的条件数也很重要。如果A的任何奇异值接近零，则A变得病态，使得从y恢复x在数值上变得困难。在最好的情况下，我们会损失精度，使得x只能被近似恢复；在严重的情况下，信息可能完全丢失。因此，信息含量不仅由维度描述，还由精度表征。正如我们将看到的，我认为将信息损失描述为精度的损失比描述为维度的损失更有用。

Diversion: Space filling curves

岔题：空间填充曲线

If you have not heard about space-filling curves, start by watching the Numberphile video about them. The idea is an infinite recursion; you start with a simple shape which goes through a space. Then you add wiggles to that shape so that it spreads more over the space. Repeatedly adding more wiggles makes the curve spread out more and more, such that it converges to covering the whole space. The one-dimensional line thus covers the whole two-dimensional space (i.e. its Hausdorff dimension is 2).

如果你没有听说过空间填充曲线，可以先观看Numberphile关于它们的视频。其思想是无限递归；你从一个穿过某个空间的简单形状开始。然后你给该形状添加摆动，使其在空间中展开得更广。不断添加更多摆动使曲线展开得越来越广，最终收敛到覆盖整个空间。因此，这条一维曲线覆盖了整个二维空间（即其豪斯多夫维数为2）。

In terms of information content, now, the one-dimensional curve contains the information of the two-dimensional space. If we start with some particular point in 2D-space (x,y), we can convert that to a point d on the one-dimensional line, and then convert it back to the 2D-point (x,y). It is just that there is an infinite recursion involved, so this is not a practical algorithm.

现在就信息含量而言，这条一维曲线包含了二维空间的信息。如果我们从二维空间中的某个特定点(x,y)开始，我们可以将其转换为一维线上的点d，然后再将其转换回二维点(x,y)。只是这涉及无限递归，因此这不是一个实用的算法。

We can however, implement a finite number of recursions to get an approximation. In the example below, I have implemented an Hilbert-curve and plotted the curve for different number of recursions N.

然而，我们可以实现有限次递归来获得近似。在下面的例子中，我实现了一条Hilbert曲线，并绘制了不同递归次数N下的曲线。

We can readily see that for each iteration, the accuracy with which the curve fills space is doubled (error is halved i.e. error energy is 1/4th). By accuracy I refer to the average distance from a random point in 2D space to the closest point on the curve.

我们可以清楚地看到，每次迭代，曲线填充空间的精度都翻倍（误差减半，即误差能量为原来的1/4）。这里精度指的是二维空间中随机点到曲线上最近点的平均距离。

Each iteration, on the other hand, splits every segment into 4 sub-segments, at a cost of 2 bits. Halving the error thus comes at a cost of 2 bits. This results thus follows results of conventional lossy coding; halving error costs as many bits as we have dimensions. Now we have 2 dimensions so halving error costs 2 bits.

另一方面，每次迭代将每个线段分成4个子线段，代价为2个比特。因此，将误差减半的代价是2个比特。这个结果遵循传统有损编码的结论：将误差减半所需的比特数等于维度数。现在我们有2个维度，所以将误差减半需要2个比特。

Information content in autoencoders

自编码器中的信息含量

Observe that the above space-filling curve construction can be interpreted as an autoencoder. The 2-dimensional space is mapped (encoder) to a 1 dimensional space (bottleneck), which we can recover with the inverse (decoder). The curve is piecewise linear and could easily be implemented with a single layer of rectified linear units (RELUs). Each recursion consists of a subdivision into 4 parts, such that we can expect that the network can be implemented with 2^(2N) RELUs. Conversely, the error of the mapping is halved if the number of RELUs is quadrupled.

注意，上述空间填充曲线构造可以解释为一个自编码器。二维空间被映射（编码器）到一维空间（瓶颈），然后我们可以用逆映射（解码器）恢复。该曲线是分段线性的，可以很容易地用单层修正线性单元（RELU）来实现。每次递归包含细分为4个部分，因此可以预期该网络可以用2^(2N)个RELU来实现。反过来，如果RELU的数量翻两番，映射的误差将减半。

A red herring

一个误导性方案

One could easily be fooled to think that we can do some simpler space filling curve than Hilbert (or other equivalent curves). For example, we could draw zig-zag lines going end-to-end on dimension x and then takes a step 1/N on dimension y. This can be implemented with O(N) RELUs. The accuracy of this map would then be relative to 2^-N instead of 2^-(2N). However, we would then have error only on the y dimension and the x dimension could be always perfectly reconstructed. Our accuracy argument thus applies as before, we need 1 bit for each dimension to halve accuracy, when assuming that accuracy on each axis is equal.

人们很容易被误导，认为我们可以使用比Hilbert（或其他等价曲线）更简单的空间填充曲线。例如，我们可以画一条之字形曲线，在x维度上从头到尾走，然后在y维度上步进1/N。这可以用O(N)个RELU来实现。那么该映射的精度将是2^(-N)量级而非2^(-2N)量级。然而，这样我们只在y维度上有误差，而x维度可以始终完美重建。因此，我们的精度论证与之前相同，假设每个轴上的精度相等时，每个维度需要1个比特来将精度减半。

Reconstruction accuracy as a measure of information

重建精度作为信息的度量

The pertinent consequence for autoencoders is that the dimensionality of the bottleneck does not alone define the amount of information that passes through. By exponentially increasing the number of non-linearities in the encoder and decoder, we gain a log-linear decrease in mean square error. Since we thus cannot measure information with the number of dimensions, we should therefore rather measure the amount of information in terms of reconstruction accuracy.

对自编码器而言，相关的结论是瓶颈的维度本身并不能定义通过它的信息量。通过指数级增加编码器和解码器中非线性的数量，我们可以获得均方误差的对数线性下降。既然我们不能用维度数量来度量信息，我们就应该用重建精度来度量信息量。

This approach is in line also with conventional concepts in probability and statistics. For continuous valued variables x, we cannot define a probability, but only probability distributions, since there are an infinite number of possible values and any particular value would always have probability zero. In a similar fashion, for continuous-valued information bottlenecks, we cannot define absolute information content, but only relative information content, in terms of accuracy. That is, we can say that accuracy (and thus information content) is improved or reduced when changing the network structure, in particular with respect to the number of non-linearities. We can however not say how much information is passed through, but only compare relative amounts of information with different network structures.

这种方法也与概率和统计学中的传统概念一致。对于连续值变量x，我们无法定义概率，只能定义概率分布，因为存在无限多个可能值，任何特定值的概率总是为零。以类似的方式，对于连续值信息瓶颈，我们无法定义绝对信息含量，只能以精度的形式定义相对信息含量。也就是说，我们可以说改变网络结构时精度（从而信息含量）提高了或降低了，特别是关于非线性数量的变化。然而，我们不能说有多少信息通过，只能比较不同网络结构下的相对信息量。

Vector quantization

矢量量化

A particular form of autoencoders which have become fashionable is the VQ-VAE, or vector quantized variational autoencoder. I won’t be going into the ‘variational’ part here, but the vector quantized autoencoder refers to systems where the bottleneck is also quantized. In particular, vector quantizers have a fixed number of quantization levels such that the bitrate is well-defined. The above analysis is thus not directly applicable to such systems. Heuristically, I would argue (and guess) that the encoder complexity has to be sufficient, such that it can digest information into a form which the VQ can handle. Increasing the encoder complexity further would not improve reconstruction accuracy, since it is limited by the VQ accuracy. Conversely, if the encoder has a given structure, then the VQ bitrate has to be sufficient such that it can take full benefit of the embedding. From the space-filling curves above, you can appreciate that if the VQ bitrate is low, then it cannot model the complicated information contained in the high-recursion curves. In other words, the encoder structure and the VQ bitrate have to be jointly matched for optimal performance.

一种变得流行的特殊形式的自编码器是VQ-VAE，即矢量量化变分自编码器。我在这里不深入讨论"变分"部分，但矢量量化自编码器指的是瓶颈也被量化的系统。特别地，矢量量化器具有固定数量的量化级别，因此比特率是明确定义的。因此上述分析并不直接适用于此类系统。启发式地，我主张（并猜测）编码器的复杂度必须足够，以便能够将信息消化为VQ可以处理的形式。进一步提高编码器复杂度不会改善重建精度，因为它受到VQ精度的限制。反过来，如果编码器具有给定的结构，则VQ比特率必须足够，以便它能够充分利用嵌入。从上面的空间填充曲线中，你可以理解如果VQ比特率较低，则它无法建模高递归曲线中所包含的复杂信息。换句话说，编码器结构和VQ比特率必须联合匹配才能获得最佳性能。

Conclusion and to-do’s

结论与待办事项

This is was my first, quick-and-dirty attempt of characterizing the information content in autoencoders. My own impression is that I’m on to something. Clearly a complex encoder can compress information into a narrow bottleneck such that it can be reconstructed with high accuracy. In fact, assuming perfect accuracy (no numerical round-off errors), then any vector could be compressed to a single real value and reconstructed with arbitrary accuracy, if the corresponding encoder and decoder are sufficiently complex. The magic is in the way the space-filling curve embeds infinities; two infinitely accurate signals can be interleaved together without loss of information.

这是我首次对自编码器中信息含量进行表征的快速粗略尝试。我自己的印象是我确实触及了一些东西。显然，复杂的编码器可以将信息压缩到狭窄的瓶颈中，从而能够以高精度重建。事实上，假设完美精度（没有数值舍入误差），那么任何向量都可以压缩到单个实数值，并以任意精度重建，只要相应的编码器和解码器足够复杂。其神奇之处在于空间填充曲线嵌入无穷的方式；两个无限精确的信号可以交织在一起而不会丢失信息。

The above presentation does not have rigorous proofs and there’s plenty of hand-waving involved. For example, I detailed only the case where a 2D signal is mapped to a 1D signal (2D-to-1D), it can be easily extended to ND-to-1D, but a bit more reflection is needed to extend it to arbitrary width bottlenecks, ND-to-KD. I also did not properly define reconstruction accuracy, nor the number of RELUs in a space-filling curve and so on. I further would like to actually implement the space filling curve with something like pytorch as a demonstration. The VQ discussion was also superficial. I also haven’t done a literature study; let me know if you know of related work! Perhaps next time.

上述论述没有严格的证明，并且涉及大量粗略的表述。例如，我只详细说明了二维信号映射到一维信号（2D到1D）的情况，它可以很容易地扩展到ND到1D，但将其扩展到任意宽度的瓶颈（ND到KD）则需要更多的思考。我也没有正确定义重建精度，也没有定义空间填充曲线中的RELU数量等。我进一步想用PyTorch之类的工具实际实现空间填充曲线作为演示。关于VQ的讨论也是肤浅的。我也没有做文献调研；如果你知道相关工作，请告诉我！也许下次吧。

In any case, this is a start for a theoretical discussion about information content in autoencoders and related deep neural networks.

无论如何，这是对自编码器及相关深度神经网络中信息含量进行理论讨论的一个起点。