Showing posts with label information theory. Show all posts
Showing posts with label information theory. Show all posts

20120116

Equivalence of Statistics on a Pair of Gaussian Channels

This post is a departure from our usual discussions. It relates to statistics and information theory, as applied to a somewhat limited model of communication. In this model, we have two variables with normally distributed amplitudes. One variable is the "true" signal, and the other contains the "true" signal mixed in with some noise. This is a model of a noisy Guassian communication channel. The main purpose is to show that, under these conditions, correlation, squared error, mutual information, and signal-to-noise ratio all become equally good and interconvertible measurements of how related the two signals are. This topic was of interest because many people apply all of these statistics separately to the same data. These notes are not written for a general audience, I'm just putting this out here in case someone, somewhere, finds it interesting.

For a pair of Gaussian channels ( continuous random variables who's values follow a normal distribution ), the mutual information, correlation, root mean squared error, correlation, and signal to noise ratio, are all equivalent and can be computed from each-other. Without loss of generality we restrict this discussion to zero-mean unit variance channels. This discussion elaborates on the discussion of mutual information between Gaussian channels presented in the third chapter of Spikes.

Correlation & Mutual Information

Consider a single gaussian channel $y = g x + n$, where $x$ is the input, $y$ is the output, $g$ is the gain, and $n$ is addative gaussian noise. Without loss of generality, assume that $x$, $n$ and $y$ have been converted to z-scores. Reconstructed z-scores can always be mapped back to the original gaussian variable by multiplying by the original standard deviations and adding in the original means. This means that all random variables have zero mean and unit variance. If we do this, we will need a separate gain for the signal and noise, say, $a$ and $b$.
\[y = a x + b n\]
Since ths signal and noise are independent, their variances add:
\[\sigma^2_{y} = \sigma^2_{a x} + \sigma^2_{b n}\] and the gain parameters can be factored out
\[\sigma^2_{y} = a^2 \sigma^2_{x} + b^2 \sigma^2_{n}.\]
Since $\sigma^2_{y}=\sigma^2_{x}=\sigma^2_{n}=1$,
\[a^2+b^2=1\]
This can be parameterized as
\[\sigma^2_{y} = \alpha \sigma^2_{x} + (1-\alpha) \sigma^2_{n},\,\,\alpha=a^2\in[0,1]\]
and
\[y = x\sqrt{\alpha} + n\sqrt{1-\alpha}\]

The relationships between mutual information $I$ and signal-to-noise ration $SNR$ come from Spikes, chapter 3.
\[I=\frac{1}{2}lg(1+\frac{\sigma^2_{a x}}{\sigma^2_{b n}})=\frac{1}{2}lg(1+SNR)\]
Where $lg(\dots)$ is the base-2 logarithm.
The $SNR$ simplifies as :
\[SNR=\frac{\sigma^2_{a x}}{\sigma^2_{b n}}=\frac{\alpha \sigma^2_x}{(1-\alpha) \sigma^2_n}=\frac{\alpha}{1-\alpha}\]
Mutual information simplifies as :
\[I=\frac{1}{2}lg(1+SNR)=\frac{1}{2}lg{\frac{\sigma^2_y}{\sigma^2_{b n}}}=\frac{1}{2}lg{\frac{\sigma^2_y}{(1-\alpha)\sigma^2_n}}=\frac{1}{2}lg{\frac{1}{1-\alpha}}\]
The correlation $\rho$ is the standard definition of Pearson's product-moment correlation coefficient, which can be viewed as the angle $\theta$ between vectors defined by the samples of random variables $x$ and $y$.
\[\rho=cos(\theta)=\frac{x y}{|x||y|}\]

Since $x$ and $n$ are independent, the samples of $x$ and $n$ can be viewed as an orthonormal basis for the samples of $y$, where the weights of the components are just previously defined $a$ and $b$, respectively. This relates our gain parameters to the correlation coefficient: the tangent of the angle between $y$ and $x$ is just the ratio of the noise gain to the signal gain
\[tan(\theta)=\frac{b}{a}=\frac{\sqrt{1-\alpha}}{\sqrt{\alpha}}\]
Then $tan(\theta)$ can be expressed in terms of the correlation coefficient $\rho$ :
\[tan(\theta)=\frac{sin(\theta)}{cos(\theta)}=\frac{\sqrt{1-cos(\theta)^2}}{cos(\theta)}=\frac{\sqrt{1-\rho^2}}{\rho}\]
This gives the relationship $\sqrt{1-\alpha}/\sqrt{\alpha}=\sqrt{1-\rho^2}/\rho$, which implies that that $\alpha=\rho^2$, or $a=\rho$. (There is a slight problem here in that correlation can be negative, but it is the magnitude of the correlation that really matters. As a temporary fix, correlation now means "absolute value of the correlation".) This can be used to relate $\rho$ to $SNR$ and mutual informtaion:
\[SNR=\frac{\rho^2}{1-\rho^2}\]
\[I=\frac{1}{2}lg{\frac{1}{1-\rho^2}}=-\frac{1}{2}lg(1-\rho^2)\]
As a corollary, if $\phi=\sqrt{1-\rho^2}$ is the correlation of $y$ and the noise $n$, then information is simply $I=-lg(\phi)$. Mean squared error ($MSE$) is also related :
\[MSE=(1-\rho)^2+(1-\rho^2)=1-2\rho+1=2(1-\rho)\]
which implies that
\[\rho=1-\frac{1}{2}MSE\]
and gives a relationship between mutual information and mean squared error:
\[I=-\frac{1}{2}lg(1-\rho^2)=-\frac{1}{2}lg(1-(1-MSE/2)^2)\]

The relationships between correlation $\rho$, root mean squared error $RMSE$, information $I$, and signal to noise ratio $SNR$, all increase monotonically, implying that correlation, SNR, and mutual information, all give the same quality ranking for a collection of channels.

Further Speculation

This can be generalized (as in chapter 3 of Spikes) to vector-valued Gaussian variables by transforming into a space where $Y=AX+BN$ is diagonal, treating each component independently, and then transforming back into the original space.

Similarly to how chapter 3 of Spikes generalizes mutual information of a Gaussian channel into a bound on mutual information for possibly non-gaussian, vector valued, channels, these relationships can be generalized to inequalities for non-Gaussian channels :

\[I\geq-lg(\Phi)=-\frac{1}{2}lg(1-\Sigma^2)=-\frac{1}{2}lg(1-(1-MSE/2)^2)\]
Where, for vector valued variables, $\phi$, $\rho$, and $MSE$ become matrices $\Phi$, $\Sigma$, and $MSE$.


20110331

Bits of Intellectual Property II

I was reading "What Color are the Bits?", an in depth discussion of the interplay between information theory and copyright law. I like this discussion, with one exception.

The authors reference an interesting thought experiment. If I take a copyrighted file, x-or it with a public domain file to produce gibberish, is that gibberish still copyrighted? Their argument is that a Lawyer would say "yes of course, those bits still came from someones intellectual property", and a computer scientist would say "no, now its just nonsense".

Why the confusion ?

These two differing opinions arise because each party is considering different pieces of information. When we scramble the bits of a copyrighted file, we might render the file itself meaningless. However, not all the information is contained within the file. We must also consider the information needed to de-code the file. The scrambled file, along with the string "This file can be decoded by x-oring it with the file found at www.foo.bar/baz57", constitutes an encoding of the original, copyrighted work. Without the knowledge of how to decode the x-ored file, it appears to be gibberish. However, with just a few more bits we can reconstruct the original copyrighted work.

This may sound familiar. The x-or example is really an example of encryption. In this case, the decryption password is a reference to the public-domain file that can be used to recover the original copyrighted work. I believe common sense dictates that encrypting a copyrighted work does not strip it of its copyrighted status, although the bits (encoding) may change significantly. The Lawyers are correct, provided that the decryption scheme is distributed in a way that can be associated with the x-ored file.

This logic also applies to the illegal numbers. These are numbers which, if represented in binary, correspond to information that it is illegal to posses. People, myself included, have gotten terribly excited about this. How can a number be illegal ? This must mean our entire legal system is bankrupt.

No. These numbers are only illegal if you know how to use them.

For instance, this prime is perfectly innocuous, unless, of course, you mention that "it unzips via the gzip algorithm into the c source for a program that breaks DVD encryption". That last piece of information is crucial. It is, in fact, the ( number, how_to_use ) pair that is in violation. Neither on its own has any meaning.

We do not consume, directly, series of zeros and ones from our computers. To ascribe meaning to these sequences of bits, we define procedures for turning these bits into something more familiar. For example, the ASCII standard defines how to turn a sequence of 8-bit chunks into the text you're reading now. The mp3 codex defines how to turn a series of bits into an audible sound file. Information is always paired with a decoding algorithm to convert it into something meaningful to humans. This concept captured by file extensions : we, or at least our computers, know to interpret 'foo.mp3' differently from 'foo.txt' or 'foo.doc'. All of these tricks to disguise copyrighted or illegal information are just clever re-encoding.

Since it is impossible to outlaw sequences of bits, it follows that to stop distribution of copyrighted or illegal information, you must simply dissociated the (information,encoding) pair. Both the information and the encoding scheme have legitimate uses on their own, but together they represent the infringing file. Some legal definitions more true to information theory might look like :

"An (information,encoding) pair A is considered to infringe upon an existing copyrighted (information,encoding) pair B if and only if the decoding of A would be considered infringing on the decoding of B."

and

"For a given illegal or copyrighted (information,encoding), it is unlawful to distribute (information) and (encoding) in such a way that through expressed or implied means, the (information,encoding) pair can be reconstructed".

I'm not sure what the implications of this are, if any.