The Living Thing / Notebooks :

Algorithmic statistics

The intersection between probability, ignorance, and algorithms, butting up against computational complexity, coding theory, dynamical systems, ergodic theory, and probability. When is the relation between things sufficiently unstructured that we may treat them as random? Stochastic approximations to deterministic algorithms. Kolmogorov complexity. Compressibility, Shannon information. Sideswipe at deterministic chaos. Chaotic systems treated as if stochastic. (Are “real” systems not precisely that?) Statistical mechanics and ergodicity.

I saw a provocative talk by Daniela Andrés on, nominally, Parkinson’s disease. The grabbing part was talking about the care and feeding of neural “codewords”, and the information theory of the brain, which she did in the foreign (to me) language of “algorithmic statistics”, and “Kolmogorov structure functions”. I have no idea what she meant. This is a placeholder to remind me to come back and see if it is as useful as it sounded like it might be.

To consider: relationship between underlying event space and measures we construct on such spaces. How much topology is lost by laundering our events through pullback of a (e.g. probability) measure?

Chazelle:

The discrepancy method has produced the most fruitful line of attack on a pivotal computer science question: What is the computational power of random bits? It has also played a major role in recent developments in complexity theory. This book tells the story of the discrepancy method in a few succinct independent vignettes. The chapters explore such topics as communication complexity, pseudo-randomness, rapidly mixing Markov chains, points on a sphere, derandomization, convex hulls and Voronoi diagrams, linear programming, geometric sampling and VC-dimension theory, minimum spanning trees, circuit complexity, and multidimensional searching. The mathematical treatment is thorough and self-contained, with minimal prerequisites. More information can be found on the book’s home page at http://www.cs.princeton.edu/~chazelle/book.html.

random number generation

Cosma Shalizi’s upcoming textbook:

In fact, what we really have to assume is that the relationships between the causes omitted from the DAG and those included is so intricate and convoluted that it might as well be noise, along the lines of algorithmic information theory (Li and Vitányi, 1997), whose key result might be summed up as “Any determinism distinguishable from randomness is insufficiently complex”.

John Baez has a talk on foundational issues here

Coding theory

https://www.cse.buffalo.edu/faculty/atri/courses/coding-theory/book/

information-based complexity theory

Is a specialty within this field?

ICB website:

Information-based complexity (IBC) is the branch of computational complexity that studies problems for which the information is partial, contaminated, and priced.

To motivate these assumptions about information consider the problem of the numerical computation of an integral. Here, the integrands consist of functions defined over the d-dimensional unit cube. Since a digital computer can store only a finite set of numbers, these functions must be replaced by such finite sets (by, for example, evaluating the functions at a finite number of points). Therefore, we have only partial information about the functions. Furthermore, the function values may be contaminated by round-off error. Finally, evaluating the functions can be expensive, and so computing these values has a price.

Refs

Brav08
Braverman, M. (2008) Polylogarithmic Independence Fools AC0 Circuits. J. ACM, 57(5), 28:1–28:10. DOI.
Chai66
Chaitin, G. J.(1966) On the length of programs for computing finite binary sequences. Journal of the ACM (JACM), 13(4), 547–569.
Chai69
Chaitin, G. J.(1969) On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers. J. ACM, 16(3), 407–422. DOI.
Chai77
Chaitin, G. J.(1977) Algorithmic information theory. IBM Journal of Research and Development.
Chai88
Chaitin, G. J.(1988) Information, Randomness and Incompleteness: Papers on Algorithmic Information Theory (World Scientific Series in Computer Science, Vol 8). . World Scientific Pub Co Inc
Chai02
Chaitin, G. J.(2002) The intelligibility of the universe and the notions of simplicity, complexity and irreducibility.
Chaz01
Chazelle, B. (2001) The discrepancy method: randomness and complexity. (1st paperback ed.). Cambridge: Cambridge Univ. Press
CFWS06
Clark, A., Florêncio, C. C., Watkins, C., & Serayet, M. (2006) Planar Languages and Learnability. In Y. Sakakibara, S. Kobayashi, K. Sato, T. Nishino, & E. Tomita (Eds.), Grammatical Inference: Algorithms and Applications (pp. 148–160). Springer Berlin Heidelberg
CMRR08
Cortes, C., Mohri, M., Rastogi, A., & Riley, M. (2008) On the computation of the relative entropy of probabilistic automata. International Journal of Foundations of Computer Science, 19(01), 219–242. DOI.
CoGG89
Cover, T. M., Gács, P., & Gray, R. M.(1989) Kolmogorov’s Contributions to Information Theory and Algorithmic Complexity. The Annals of Probability, 17(3), 840–865. DOI.
DGJS09
Diakonikolas, I., Gopalan, P., Jaiswal, R., Servedio, R., & Viola, E. (2009) Bounded Independence Fools Halfspaces (No. 016).
GáTV01
Gács, P., Tromp, J., & Vitányi, P. M. B.(2001) Algorithmic statistics. IEEE Transactions on Information Theory, 47(6), 2443–2463. DOI.
HaYu01
Hansen, M. H., & Yu, B. (2001) Model Selection and the Principle of Minimum Description Length. Journal of the American Statistical Association, 96(454), 746–774.
00
Information and Complexity in Statistical Modeling. (n.d.) http://www.springer.com/mathematics/probability/book/978-0-387-36610-4.
Kolm68
Kolmogorov, A. N.(1968) Three approaches to the quantitative definition of information. International Journal of Computer Mathematics, 2(1), 157–168.
KoCM06
Kontorovich, L., Cortes, C., & Mohri, M. (2006) Learning Linearly Separable Languages. In J. L. Balcázar, P. M. Long, & F. Stephan (Eds.), Algorithmic Learning Theory (pp. 288–303). Springer Berlin Heidelberg
Legg06
Legg, S. (2006) Is There an Elegant Universal Theory of Prediction?. In J. L. Balcázar, P. M. Long, & F. Stephan (Eds.), Algorithmic Learning Theory (pp. 274–287). Springer Berlin Heidelberg
LiVi09
Li, M., & Vitányi, P. M.(2009) An introduction to Kolmogorov complexity and its applications. (3rd ed.). Springer
Onei00
O’NEILL, M. E.(n.d.) PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation.
PaGr14
Paulson, E., & Griffin, C. (2014) Computational Complexity of the Minimum State Probabilistic Finite State Learning Problem on Finite Data Sets. arXiv:1501.01300 [cs, Math].
ShYC06
Shibata, T., Yoshinaka, R., & Chikayama, T. (2006) Probabilistic Generalization of Simple Grammars and Its Application to Reinforcement Learning. In J. L. Balcázar, P. M. Long, & F. Stephan (Eds.), Algorithmic Learning Theory (pp. 348–362). Springer Berlin Heidelberg
Solo64a
Solomonoff, R. J.(1964a) A formal theory of inductive inference Part I. Information and Control, 7(1), 1–22. DOI.
Solo64b
Solomonoff, R. J.(1964b) A formal theory of inductive inference Part II. Information and Control, 7(2), 224–254. DOI.
VeVi04
Vereshchagin, N. K., & Vitanyi, P. M. B.(2004) Kolmogorov’s structure functions and model selection. IEEE Transactions on Information Theory, 50(12), 3265–3290. DOI.
VeVi10
Vereshchagin, N. K., & Vitanyi, P. M. B.(2010) Rate Distortion and Denoising of Individual Data Using Kolmogorov Complexity. IEEE Transactions on Information Theory, 56(7), 3438–3454. DOI.
Vitá06
Vitányi, P. M.(2006) Meaningful information. Information Theory, IEEE Transactions on, 52(10), 4617–4626. DOI.