"A Rate-Distortion Approach to Caching" Just Got Published!

Our joint work on rate-distortion theory for caching just got published in the IEEE Transactions on Information Theory (it's also available on arXiv, of course; there's also an older post). Thanks Roy, Shirin, and Michele for letting me be a part of this!

In this paper, we consider a lossy single-user caching problem with correlated sources -- just think of streaming compressed videos! Most users will watch these videos in the evening, leading to network congestion. If you have a player with a cache, though, you can fill this cache with data during times of low network usage, even though you may not know which video the user wants to watch in the evening. In our paper, we characterize the transmission rate required in the evening as a function of the cache size and as a function of the distortion one accepts when watching the videos. We furthermore hint at what should be put in the cache such that it is useful for a variety of videos, and we connect these results to the common-information measures proposed by Wyner, Gacs and Koerner.

The picture shows achievable upper (red) and lower converse (black) bounds on the transmission rate as a function of the cache capacity $C$ for doubly symmetric binary source, with the requirement the video is reconstructed perfectly at the receiver. $I(X_1;X_2)$ denotes the mutual information between the two videos, while $K_W(X_1,X_2)$ denotes Wyner's common information.

(Lossy) Wyner's Common Information and Gacs-Körner's Common Randomness Revisited

Recently, I was involved (not so much, to be honest) in a research project dealing with caching, i.e., the storage of data close to a user such that it need not be transmitted anymore. A typical use case is Netflix: Netflix offers $N$ movies/series, and the user can choose any of these anytime. Most users watch during prime time, which taxes the communication network. During the day, the communication network has unused capacities, so one could try storing part of the Netflix database on a hard drive connected to the user's player. This reduces the network load during prime time and improves the user experience.

I our work, we not only looked at the fundamental limits of this caching scheme, but we also got a good idea of what should actually be stored in the user's hard drive ("cache"). The answers are decades old: One should store either what is known as Gacs-Körner's common randomness, or what is known as Wyner's common information.

For simplicity, we assume that there are only two files available on Netflix, namely $X$ and $Y$. The common information of these two random variables (RVs; in information theory, everything is random) is another RV $W$ that minimizes
$$I(X,Y; W)$$
subject to $X-W-Y$, i.e., subject to the fact that, given $W$, $X$ and $Y$ are conditionally independent. The common randomness of these two RVs is an RV $U$ that maximizes
$$ I(X,Y; U) $$
subject to the constraint that $X-Y-U$ and $Y-X-U$. It can be shown that
$$ I(X,Y; U) \le I(X;Y) \le I(X,Y; W).$$

Common randomness is something that is truly common, in the usual sense of the word. In particular, if $A$, $B$, and $C$ are independent RVs, and if $X=(A,B)$ and $Y=(A,C)$, then $U=A$. So much for the math. Now here comes an interpretation (and probably one for which an information theorists wants to punch me in the face): If $X$ and $Y$ are two different episodes of your favorite series, then $U$ is the opening theme. If you have a small hard drive, storing the opening theme is probably the most useful idea. Common information is a bit more intricate, but an intuitive explanation is the following: Suppose $X$ and $Y$ are two different episodes of your favorite series, and suppose the only thing $X$ and $Y$ have in common is an actress called $A$. In $A$, some parts of $A$ are seen, while in $Y$ other parts of $A$ are seen. (Say, $X$ shows $A$ running, while $Y$ shows $A$ talking to a person.) Obviously, if you could store all information about actress $A$ as a whole on your hard drive, the small computer in your player could reconstruct running scenes and talking scenes in which $A$ participates. Thus, if your hard drive is large enough, that's what you should store.

Let's take this one step further. Suppose that you are fine with watching not $X$ or $Y$, but lower-quality versions $\hat X$ or $\hat Y$, respectively. This requires the definition of lossy versions of common randomness and common information. And indeed, such definitions have been proposed in 1403.8093. Namely, the lossy common information is an RV $W$ that minimizes
$$ I(X,Y; W)$$
subject to $\hat X - W - \hat Y$ and $(X,Y) - (\hat X,\hat Y) - W$. Lossy common randomness is an RV $U$ that maximizes
$$ I(X,Y; U) $$
subject to the constraints $X-Y-U$, $Y-X-U$, $X-\hat X - U$, and $Y-\hat Y-U$. These definitions are all meaningful because they solve communication problems: The get their operational characterization in the Gray-Wyner problem (1403.8093) or in lossy caching (1610.07304).

The lossy version of common information seems fine to me: I only need to store as much information about actress $A$ in order to be able to reconstruct approximate depictions of her running and speaking. This might need more or less space on the hard drive than the perfect reconstruction: I might be able to store not only this reduced version of the actress $A$, but I might also store a, say, generic building, that allows to reconstruct two different but similar houses in episodes $X$ and $Y$. And indeed, lossy common information may be larger or smaller than lossless common information (see Lemma 1 in 1403.8093).

The lossy version of common randomness, however, is not fully satisfactory to me. If I am not interested in perfect reconstruction, should I not be able to store more on my internal hard drive? For example, if the credits of my two episodes $X$ and $Y$ differ only in a few actors' names, can I not store a "noisy" version of the credits in addition to the opening theme? Nevertheless, the lossy version of common randomness is usually smaller than the lossless version (see Corollary 2 in 1403.8093).

I would thus suggest different definitions of lossy common randomness: The lossy common randomness is an RV $U'$ that maximizes
$$ I(X,Y; U') \text{ or } I(\hat X,\hat Y; U')$$
subject to the constraints $\hat X-\hat Y-U'$, $\hat Y-\hat X-U'$, $X-\hat X - U'$, and $Y-\hat Y-U'$. The difference is subtle and mirrors the definition of lossy common information. While lossy common information requires $W$ to make the reconstructions $\hat X$ and $\hat Y$ conditionally independent, the original definition of lossy common randomness requires that $U$ is a common part of $X$ and $Y$ (the first two Markov constraints). The definition proposed here would require that $U'$ is only a common part of the reconstructions $\hat{X}$ and $\hat Y$. Given this definition, we may ask the following questions:

1. Does the new definition satisfy the desired property that it is larger than the lossless common randomness?
2. Is there a communications problem for which this definition is a single-letter characterization?

Candy Crush Codes

Candy Crush Saga is a game in which... no, I don't think I have to tell you! But I bet you didn't know yet that the game is actually NP-hard! The original proof can be found on arXiv (or, again, on arXiv; these authors claim to prove a little more general result), but there are also plenty of pop-sci articles around. (Now, that is quite interesting: Walsh posted his paper on March 8th, 2014, and the press wrote articles about it only five days later.) Anyways, that's not really what I wanted to tell you.

A typical game field of Candy Crush Saga (copyright with King Inc., taken from Wikipedia)

If you look at above picture, you will see no three candies in a row or in a column having the same flavor. Why? Because they would disappear immediately (that's more-less the only game rule). But this game rule more-less immediately leads to the following question:

If and $n\times m$ field, filled with candies of $k$ different flavors that are randomly, independently and uniformly chosen, what is the probability that there is at least one horizontal or vertical triple of the same flavor?

In other words, what is the probability that, starting a new level, something happens without you actually touching the screen. The question is obviously combinatorial and interesting in itself. But there is even more to it.

If we look at $n\times m$ fields filled with candies of $k$ different flavors, there are in total $k^{nm}$ possible arrangements. The rules of Candy Crush Saga, however, allow only a subset of these, namely,  $k^{nm}$ minus the answer to above question. For example, if we take just one row with three columns and two flavors, there are eight possible arrangements, of which two are excluded. Taking two rows allows 36 out of  64 arrangements, and three rows permit 102 out of 512. (At least that's what my first calculations show.) In other words, the set of all possible fields allows for a redundancy: If we want to transmit messages by sending pictures of Candy Crush fields, a $3\times 3$ field allows you transmit only up to 102 different messages, although there are 512 different possible arrangements. If now, during the transmission, an error occurs -- the flavor of a candy changes -- you might end up with an invalid field! Candy Crush Saga can be used as a nonlinear block code! Super-exciting, right?

At that, in turn, allows us to ask several questions:

• How should we encode a message efficiently? Is there anything better than just keeping a table of , say,102 fields? (There is.)
• How should we decode the message efficiently? That's a more difficult question if you don't want to store a table of all allowed arrangements. Maybe belief propagation can help here, as it does for Sudoku codes.
• What are the basic properties of an $(n,m,k)$ Candy Crush Code? What is the maximally possible rate given the game rule, i.e., what is the ratio between the number of possible and allowed arrangements? What is the minimum Hamming distance, etc.? How can we improve our encoder in order to guarantee a positive Hamming distance?
• Given that we change the flavor of every candy with a given probability $p \ll 1$ (and choose the new flavor uniformly among the remaining ones), what is the error probability? I.e., what is the probability that the changed arrangement is not detected as erroneous, because it also satisfies the game rules?
• What about error propagation of this code? I.e., if a given candy changes its flavor, how many "information bits" are effected? Can we still reconstruct part of the information, or is the whole block destroyed? (I guess the answer is no.)
• Connecting to the last question: What happens if we let one dimension of the field go to infinity? We would need sequential encoding and decoding techniques, such as they are usual for convolutional codes.
• What happens to all of these topics if we span the field on a cylinder (such that the rules extend over one side of the field: two candies of a given flavor on one side rule out a single candy of the same flavor on the other side) or on a torus?

Most probably, the code thus constructed is crappy. But it is nevertheless a nice topic for a research internship, I guess. And it makes learning nonlinear codes for symmetric channels as fun as Sudoku codes do for erasure channels!