Category Archives: Information Theory

Multiscale Structure via Information Theory

We have scienced:

B. Allen, B. C. Stacey and Y. Bar-Yam, “An Information-Theoretic Formalism for Multiscale Structure in Complex Systems” [arXiv:1409.4708].

We develop a general formalism for representing and understanding structure in complex systems. In our view, structure is the totality of relationships among a system’s components, and these relationships can be quantified using information theory. In the interest of flexibility we allow information to be quantified using any function, including Shannon entropy and Kolmogorov complexity, that satisfies certain fundamental axioms. Using these axioms, we formalize the notion of a dependency among components, and show how a system’s structure is revealed in the amount of information assigned to each dependency. We explore quantitative indices that summarize system structure, providing a new formal basis for the complexity profile and introducing a new index, the “marginal utility of information”. Using simple examples, we show how these indices capture intuitive ideas about structure in a quantitative way. Our formalism also sheds light on a longstanding mystery: that the mutual information of three or more variables can be negative. We discuss applications to complex networks, gene regulation, the kinetic theory of fluids and multiscale cybernetic thermodynamics.

There’s much more to do, but for the moment, let this indicate my mood:


One day, I’ll be able to explain the story behind how I got into this, but looking back on all the oddities of it, I’m not sure that a medium other than manga could do it justice.

My Struggles with the Block Universe [arXiv:1405.2390]

Christopher A. Fuchs, Maximilian Schlosshauer (foreword), Blake C. Stacey (editor)

This document is the second installment of three in the Cerro Grande Fire Series. Like its predecessor arXiv:quant-ph/0105039, “Notes on a Paulian Idea,” it is a collection of letters written to various friends and colleagues, most of whom regularly circuit this archive. The unifying theme of all the letters is that each has something to do with the quantum. Particularly, the collection chronicles the emergence of Quantum Bayesianism as a robust view of quantum theory, eventually evolving into the still-more-radical “QBism” (with the B standing for no particular designation anymore), as it took its most distinctive turn away from various Copenhagen Interpretations. Included are many anecdotes from the history of quantum information theory: for instance, the story of the origin of the terms “qubit” and “quantum information” from their originator’s own mouth, a copy of a rejection letter written by E. T. Jaynes for one of Rolf Landauer’s original erasure-cost principle papers, and much more. Specialized indices are devoted to historical, technical, and philosophical matters. More roundly, the document is an attempt to provide an essential ingredient, unavailable anywhere else, for turning QBism into a live option within the vast spectrum of quantum foundational thought.

As the comment field says, “CAUTION, do not unthinkingly print from a printer: 2,348 pages, 4 indices, 6 figures, with extensive hyperlinking.”

MSwtBU was originally submitted to the arXiv on 10 May 2014, the anniversary of the predecessor volume and before that of the Cerro Grande Fire, which started the whole business. To my knowledge, it is the longest item currently on the arXiv.

omg 2000+ pages. There goes my free time.
— Dave Bacon, via Twitter

Currently Reading

Xiaotie Denga and Li-Sha Huang (2006), “On the complexity of market equilibria with maximum social welfare” Information Processing Letters 97, 1: 4–11 [DOI] [PDF].

We consider the computational complexity of the market equilibrium problem by exploring the structural properties of the Leontief exchange economy. We prove that, for economies guaranteed to have a market equilibrium, finding one with maximum social welfare or maximum individual welfare is NP-hard. In addition, we prove that counting the number of equilibrium prices is #P-hard.

Found by citation-hopping from here.

Currently Reading

Juan A. Bonachela, Haye Hinrichsen, Miguel A. Munoz, “Entropy estimates of small data sets” J. Phys. A: Math. Theor. 41 (2008). arXiv: 0804.4561.

Estimating entropies from limited data series is known to be a non-trivial task. Naive estimations are plagued with both systematic (bias) and statistical errors. Here, we present a new “balanced estimator” for entropy functionals (Shannon, Rényi and Tsallis) specially devised to provide a compromise between low bias and small statistical errors, for short data series. This new estimator out-performs other currently available ones when the data sets are small and the probabilities of the possible outputs of the random variable are not close to zero. Otherwise, other well-known estimators remain a better choice. The potential range of applicability of this estimator is quite broad specially for biological and digital data series.

As an exercise, discuss the relation of this approach to the coincidence-based methods of Ma, Bialas et al.

Categorical Information Theory

Ben Allen is now on the arXivotubes, with a category-theoretic arithmetic of information.

The concept of information has found application across the sciences. However, the conventional measures of information are not appropriate for all situations, and a more general mathematical concept is needed. In this work we give axioms that characterize the arithmetic of information, i.e. the way that pieces of information combine with each other. These axioms allow for a general notion of information functions, which quantify the information transmitted by a communication system. In our formalism, communication systems are represented as category-theoretic morphisms between information sources and destinations. Our framework encompasses discrete, continuous, and quantum information measures, as well as familiar mathematical functions that are not usually associated with information. We discuss these examples and prove basic results on the general behavior of information.

It looks like a discussion about this is starting over at the n-Category Café. If I didn’t have to spend today cutting down a 12-page paper to eight pages for an overpriced book of conference proceedings which nobody will read, I’d totally be writing more about it!

Aaronson on Turing, Gödel and Searle

Computer-science guru Scott Aaronson has begun to put lecture notes for his “Great Ideas In Theoretical Computer Science” course online. (That’s 6.080 in MIT-speak: words are for the weak.) Prepared by the students and edited by the instructors, the notes are terse but clear and enjoyable. I particularly like lecture 6, “Minds and Machines,” of which the following is a taste:

We already established that no Turing Machine exists can solve the halting problem. If we had a proof system that could analyze any Turing machine and prove if it halted or did not halt, we could use this system to solve the halting problem by brute force (also known as the “British Museum algorithm”) by trying every possible string that might be a proof. You would either terminate and find a proof that it halts or terminate and find a proof that it doesn’t halt. If this proof system was sound and complete, it would violate the unsolvability of the halting problem. Therefore, there is no such sound and complete proof system.

I also like this bit:
Continue reading Aaronson on Turing, Gödel and Searle

Shorter Uncommon Descent

BPSDBTyler DiPietro finds a fresh example of steaming creationist nonsense at the weblog of Dembski and sycophants, Uncommon Descent. I summarize for the busy reader:

Because running an image of a face through a software filter makes it look less like a face, Darwin was a fuddy-duddy and materialism is on its last leg.

The cream on the cocoa is, however, this bit, from a commenter:

I’m not sure about the CSI [complex specified information] decreasing, however. Anyone able to get values of the CSI for each picture?

Gee, given that “complex specified information” has never been consistently defined, I wonder how one could compute it.

Currently Reading

Oliver Johnson, Christophe Vignat (2006). Some results concerning maximum Renyi entropy distributions.

We consider the Student-t and Student-r distributions, which maximise Renyi entropy under a covariance condition. We show that they have information-theoretic properties which mirror those of the Gaussian distributions, which maximise Shannon entropy under the same condition. We introduce a convolution which preserves the Renyi maximising family, and show that the Renyi maximisers are the case of equality in a version of the Entropy Power Inequality. Further, we show that the Renyi maximisers satisfy a version of the heat equation, motivating the definition of a generalized Fisher information.

Luciano da F. Costa, Francisco A. Rodrigues, Gonzalo Travieso, P. R. Villas Boas (2006). Characterization of complex networks: A survey of measurements.
Continue reading Currently Reading

Info Theory and DNA/Evolution

We’re reviewing the IEEE papers.

After reviewing the first batch of papers, we came up with some questions to answer in the future, in order of difficulty/open-ness:

1. Given the robustness of a code (e.g. due to a many-to-one codon->AA mapping), can we calculate bounds on the channel capacity of such a code? How does the empirical R (info transmission rate) of the codon->AA code compare with the empirical C (channel capacity, e.g. from mutation rates)?

2. How does the length/entropy/complexity of code-bits (e.g. parity bits, non-message bits used for error correcting) relate to the complexity of the error-correcting task, and e.g. the entropy and length of the data-bit sections (e.g. the actual message you’re sending) to satisfy R≤C?

– Is the von Neumann entropy,
[tex]H = {\rm Tr\,} \rho\log\rho = \sum\lambda_i\log\lambda_i [/tex]
where {λ} are the eigenvalues of the matrix, useful for discussing network robustness? (There’s a paper where they use Kolmogorov-Sinai/Shannon entropy to do this, which Blake has somewhere…) If so, then can we apply this to a genetic-regulatory network, and tie in the error-correcting or homeostatic abilities of such a network with VNE or other network metrics?

Next week:

We meet Monday at BU for group theory. Ben will be discussing SU(2) and SO(3) from Artin. Friday, Blake will present on the symmetry-breaking-in-genetics paper, and possibly on the information-theoretic considerations for BLAST.

BLAKE SEZ: I believe the paper which caught my eye was L. Demetrius and T. Manke (15 February 2005) “Robustness and network evolution — an entropic principlePhysica A 346 (3–4): 682–96.

Entropy for Non-Majors

Every once in a while (well, actually, pretty frequently) I see a post out there in the Blagopelago which makes me feel bad about ranting so much and discussing science so little. Today’s entry in this category is Jacques Distler’s treatment of Boltzmann entropy. He explains his motivation as follows:

This semester, I’ve been teaching a Physics for non-Science majors (mostly Business School students) class.

Towards the end of the semester, we turned to Thermodynamics and, in particular, the subject of Entropy. The textbook had a discussion of ideal gases and of heat engines and whatnot. But, somewhere along the line, they made a totally mysterious leap to Boltzmann’s definition of Entropy. As important as Boltzmann’s insight is, it was presented in a fashion totally disconnected from Thermodynamics, or anything else that came before.

So, equipped with the Ideal Gas Law, and a little baby kinetic theory, I decided to see if I could present the argument leading to Boltzmann’s definition.

Continue reading Entropy for Non-Majors

A Lower Bound

This is how Carl Sagan begins the introduction to The Varieties of Scientific Experience.

In these lectures I would like, following the wording of the Gifford Trust, to tell you something of my views on what at least used to be called natural theology, which, as I understand it, is everything about the world not supplied by revelation. This is a very large subject, and I will necessarily have to pick and choose topics. I want to stress that what I will be saying are my own personal views on this boundary area between science and religion. The amount that has been written on the subject is enormous, certainly more than 10 million pages, or roughly 1011 bits of information. That’s a very low lower limit. And nevertheless no one can claim to have read even a tiny fraction of that body of literature or even a representative fraction. So it is only in the hope that much that has been written is unnecessary to be read that one can approach the subject at all.

This arithmetic does, I think, shed an interesting light on the Courtier’s Reply.

It’s rather common practice in some domains of the Blagnet to list one’s current mood or the music to which one is currently listening. I don’t have a handy collection of mood-marking icons (and if I did, I’d break them, because I’m a proud iconoclast), but I should note that my stereo is currently playing Infected Mushroom‘s 2003 album Converting Vegetarians. Stored in MP3 format, the two discs of this album occupy 239,317,690 bytes of hard-drive real estate. That’s roughly 1.9 × 109 bits, about one fiftieth of Sagan’s estimate for all theological writing, for two and a half hours of music. So, one hundred CDs of psy-trance (which could in principle include Goa and Suomisaundi) would take us into the regime of natural theology, content-wise.

The Psychedelic Mind Expander lists 636 different CDs released during 2006 alone, lumping together the Ambient, Breaks, Drum & Bass, Goa, Progressive, Psychedelic, Techno and Trance sub-genres (I get the feeling nobody else knows how to assign these labels, either — has anybody actually conducted a blind discrimination test between Drum & Bass and Neurofunk?).

It’s no wonder I have a hard time keeping up with divinity studies. Good thing we have theologians like Ishkur to organize the information for us.

Wobosphere Trick of the Day (plus seminar)

0. Go to Google Maps.

1. Click “get directions”.

2. Get directions from New York, New York to Paris, France.

3. Scroll down to item 23 in the list of directions.

4. Return in time for the seminar tomorrow afternoon at NECSI, where we shall discuss the first two (possibly three) sections in chapter four of Ash.

(Tip o’ the beret to Audentes at the Achenblog. It also works with Boston, Massachusetts.)

Where Was I When They Were Passing Out the Wit?

Scott Aaronson has a new comment policy:

If you reject an overwhelming consensus on some issue in the hard sciences — whether it’s evolution, or general relativity, or climate change, or anything else — this blog is an excellent place to share your concerns with the world. Indeed, you’re even welcome to derail discussion of completely unrelated topics by posting lengthy rants against the academic orthodoxy — the longer and angrier the better! However, if you wish to do this, I respectfully ask that you obey the following procedure:

1. Publish a paper in a peer-reviewed journal setting out the reasons for your radical departure from accepted science.
2. Reference the paper in your rant.

If you attempt to skip to the “rant” part without going through this procedure, your comments will be deleted without warning. Repeat offenders will be permanently banned from the blog. Life is short. I make no apologies.

It looks like Dave Bacon can now talk about time travel, but my own conspiracy theories will have to wait. But soon, I promise, the real meaning behind supersymmetric quantum mechanics will be made clear. They laughed at me when I suggested that the BPS interpretation of shape invariance may have a non-topological origin. The fools — I’ll show them all!
Continue reading Where Was I When They Were Passing Out the Wit?

CRE paper

Friday 4/6/07 we reviewed Rao et al. (2004) IEEE Trans Info Theor, V 50 (6) “Cumulative Residual Information […]”, here.

We decided that while the motivation for the paper was valid, that it was undesirable for a number of reasons — mostly that the CRE of many well-behaved distributions (power laws notably) diverged. We’re all currently working on better generalizations.