Information Distance
Inhaltsverzeichnis
Reference
Bennet, C., Gács, P., Li, M., Vitányi, P., Zurek, W.: Information Distance. IEEE Transactions on Information Theory 44(4), 1407–1423 (1998)
DOI
http://dx.doi.org/10.1109/18.681318
Abstract
While Kolmogorov (1965) complexity is the accepted absolute measure of information content in an individual finite object, a similarly absolute notion is needed for the information distance between two individual objects, for example, two pictures. We give several natural definitions of a universal information metric, based on length of shortest programs for either ordinary computations or reversible (dissipationless) computations. It turns out that these definitions are equivalent up to an additive logarithmic term. We show that the information distance is a universal cognitive similarity distance. We investigate the maximal correlation of the shortest programs involved, the maximal uncorrelation of programs (a generalization of the Slepian-Wolf theorem of classical information theory), and the density properties of the discrete metric spaces induced by the information distances. A related distance measures the amount of nonreversibility of a computation. Using the physical theory of reversible computation, we give an appropriate (universal, antisymmetric, and transitive) measure of the thermodynamic work required to transform one object in another object by the most efficient process. Information distance between individual objects is needed in pattern recognition where one wants to express effective notions of "pattern similarity" or "cognitive similarity" between individual objects and in thermodynamics of computation where one wants to analyze the energy dissipation of a computation from a particular input to a particular output.
Extended Abstract
Bibtex
Used References
P. A. Benioff, "Quantum mechanical Hamiltonian models of discrete processes that erase their histories: Applications to Turing machines", Int. J. Theoret. Phys., vol. 21, pp.177 -202 1982 http://dx.doi.org/10.1007/BF01857725
P. A. Benioff, "Quantum mechanical Hamiltonian models of computers", Ann. New York Acad. Sci, vol. 480, pp.475 -486 1986 http://dx.doi.org/10.1111/j.1749-6632.1986.tb12450.x
C. H. Bennett, "Logical reversibility of computation", IBM J. Res. Develop., vol. 17, pp.525 -532 1973 http://dx.doi.org/10.1147/rd.176.0525
C. H. Bennett, "The thermodynamics of computation A review", Int. J. Theoret. Phys., vol. 21, pp.905 -940 1982 http://dx.doi.org/10.1007/BF02084158
C. H. Bennett, "Time/space trade-offs for reversible computation", SIAM. J. Comput., vol. 18, pp.766 -776 1989 http://dx.doi.org/10.1137/0218053
C. M. Caves, W. G. Unruh, and W. H. Zurek, "Comment on quantitative limits on the ability of a Maxwell Demon to extract work from heat", Phys. Rev. Lett., vol. 65, pp.1387 1990 http://dx.doi.org/10.1103/PhysRevLett.65.1387
G. Chaitin, "A theory of program size formally identical to information theory", J. Assoc. Comput. Mach, vol. 22, pp.329 -340 1975 http://dx.doi.org/10.1145/321892.321894
I. Csiszar and J. Körner, Information Theory, 1980 :Academic
A. N. Kolmogorov, "Three approaches to the definition of the concept `quantity of information',", Probl. Inform. Transm., vol. 1, no. 1, pp.1 -7 1965
R. P. Feynman, "Quantum mechanical computers", Opt. News, vol. 11, pp.11 1985 http://dx.doi.org/10.1364/ON.11.2.000011
E. Fredkin and T. Toffoli, "Conservative logic", Int. J. Theoret. Phys., vol. 21, no. 3/4, pp.219 -253 1982 http://dx.doi.org/10.1007/BF01857727
P. G ́acs and J. Körner, "Common information is far less than mutual information", Probl. Contr. and Infotm. Theory, vol. 2, pp.149 -162 1973
P. G ́acs, "On the symmetry of algorithmic information", Sov. Math.&ndash,Dokl., vol. 15, pp.1477 -1480 1974
P. G ́acs, 1987 :Comp. Sci. Dept., Boston Univ.
R. W. Keyes and R. Landauer, "Minimal energy dissipation in logic", IBM J. Res. Develop., vol. 14, pp.152 -157 1970 http://dx.doi.org/10.1147/rd.142.0152
R. Landauer, "Irreversibility and heat generation in the computing process", IBM J. Res. Develop., pp.183 -191 1961 http://dx.doi.org/10.1147/rd.53.0183
R. Landauer, Int. J. Theor. Phys., vol. 21, pp.283 1982
Y. Lecerf, "Machines de Turing reversibles. Recursive insolubilite en $n \in N$ de l',equation $u = \theta^n$ ou $\theta$ est un &ldquo,isomorphism des codes", Compt. Rend., vol. 257, pp.2597 -2600 1963
R. Y. Levine and A. T. Sherman, "A note on Bennett',s time-space trade-off for reversible computation", SIAM. J. Comput, vol. 19, pp.673 -677 1990
M. Li and P. M. B. Vita´,nyi, Reversibility and adiabatic computation: Trading time and space for energy, vol. 452, pp.769 -789 1996
M. Li, J. Tromp, and L. Zhang, "On the neirest neighbor interchange distance between evolutionary trees", J. Theor. Biol, vol. 182, pp.463 -467 1996 http://dx.doi.org/10.1006/jtbi.1996.0188
M. Li and P. M. B. Vita´,nyi, An Introduction to Kolmogorov Complexity and Its Applications, 1997 :Springer-Verlag
K. Likharev, "Classical and quantum limitations on energy consumption on computation", Int. J. Theoret. Phys., vol. 21, pp.311 -326 1982 http://dx.doi.org/10.1007/BF01857733
D. Sleator, R. Tarjan, and W. Thurston, "Short encodings of evolving structures", SIAM J. Discr. Math., vol. 5, pp.428 -450 1992
J. Ziv and N. Merhav, "A measure of relative entropy between individual sequences with application to universal classification", IEEE Trans. Inform. Theory, vol. 39, pp.1270 -1279 1993 http://dx.doi.org/10.1109/18.243444
W. H. Zurek, "Thermodynamic cost of computation, algorithmic complexity and the information metric", Nature, vol. 341, pp.119 -124 1989 http://dx.doi.org/10.1038/341119a0
W. H. Zurek, "Algorithmic randomness and physical entropy", Phys. Rev, vol. A40, pp.4731 -4751 1989 http://dx.doi.org/10.1103/PhysRevA.40.4731
A. K. Zvonkin and L. A. Levin, "The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms", Russ. Math. http://dx.doi.org/10.1070/rm1970v025n06ABEH001269
Links
Full Text
http://www.cs.bu.edu/~gacs/papers/info-distance.pdf
