Skip to main content
MathOverflow

Return to Answer

edited to use the citation feature; the second reference was to an arxiv paper, which was preseved in addition to the citation tool reference.
Source Link
François G. Dorais
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233

Inspired by the informal notion of Cognitive distance, in 2010 Charles Bennett, Peter Gács, Ming Li, Paul Vitanyí and Wojcech Zurech introduced the notion of Information Distance which was used in the seminal paper Clustering by Compression:

\begin{equation} ID(x,y)=\min\{|p|:p(x)=y \land p(y)=x\} \tag{1} \end{equation}

with $p$ a finite binary program for the fixed universal computer $U$ which takes the finite binary strings $x,y$ as inputs. They prove that:

\begin{equation} ID(x,y)=E(x,y) + \mathcal{O}(\log E(x,y)) \tag{2} \end{equation}

where the key notion:

\begin{equation} E(x,y) = \max \{K_U(x|y),K_U(y|x) \} \tag{3} \end{equation}

satisfies the criteria of a metric up to the additive term $\mathcal{O}(\log E(x,y))$.

References:

  1. Bennett, Charles H., Péter GácsBennett, Charles H.; Gács, Péter; Li, Ming; Vitányi, Paul M. B.; Zurek, Wojciech H., Ming LiInformation distance, Paul M. B. Vitányi and Wojciech HIEEE Trans. ZurekInf. “Information distanceTheory 44, No.” 2006 IEEE International Conference on Granular Computing 4, 1407-1423 (1998): 1-1. ZBL0964.94010.
  2. Cilibrasi, R.; VitanyiCilibrasi, Rudi; Vitányi, Paul M. B., P. M. B. (2011-09-27). "R. CilibrasiClustering by compression, P.M.BIEEE Trans. Vitanyi, Clustering by compression"Inf. IEEE Transactions on Information Theory. 51, No. 4, 1523-1545 (42005): 1523–1545. arXiv:cs/0312044ZBL1297.68097. ArXiv:cs:0312044

Inspired by the informal notion of Cognitive distance, in 2010 Charles Bennett, Peter Gács, Ming Li, Paul Vitanyí and Wojcech Zurech introduced the notion of Information Distance which was used in the seminal paper Clustering by Compression:

\begin{equation} ID(x,y)=\min\{|p|:p(x)=y \land p(y)=x\} \tag{1} \end{equation}

with $p$ a finite binary program for the fixed universal computer $U$ which takes the finite binary strings $x,y$ as inputs. They prove that:

\begin{equation} ID(x,y)=E(x,y) + \mathcal{O}(\log E(x,y)) \tag{2} \end{equation}

where the key notion:

\begin{equation} E(x,y) = \max \{K_U(x|y),K_U(y|x) \} \tag{3} \end{equation}

satisfies the criteria of a metric up to the additive term $\mathcal{O}(\log E(x,y))$.

References:

  1. Bennett, Charles H., Péter Gács, Ming Li, Paul M. B. Vitányi and Wojciech H. Zurek. “Information distance.” 2006 IEEE International Conference on Granular Computing (1998): 1-1.
  2. Cilibrasi, R.; Vitanyi, P. M. B. (2011-09-27). "R. Cilibrasi, P.M.B. Vitanyi, Clustering by compression". IEEE Transactions on Information Theory. 51 (4): 1523–1545. arXiv:cs/0312044

Inspired by the informal notion of Cognitive distance, in 2010 Charles Bennett, Peter Gács, Ming Li, Paul Vitanyí and Wojcech Zurech introduced the notion of Information Distance which was used in the seminal paper Clustering by Compression:

\begin{equation} ID(x,y)=\min\{|p|:p(x)=y \land p(y)=x\} \tag{1} \end{equation}

with $p$ a finite binary program for the fixed universal computer $U$ which takes the finite binary strings $x,y$ as inputs. They prove that:

\begin{equation} ID(x,y)=E(x,y) + \mathcal{O}(\log E(x,y)) \tag{2} \end{equation}

where the key notion:

\begin{equation} E(x,y) = \max \{K_U(x|y),K_U(y|x) \} \tag{3} \end{equation}

satisfies the criteria of a metric up to the additive term $\mathcal{O}(\log E(x,y))$.

References:

  1. Bennett, Charles H.; Gács, Péter; Li, Ming; Vitányi, Paul M. B.; Zurek, Wojciech H., Information distance, IEEE Trans. Inf. Theory 44, No. 4, 1407-1423 (1998). ZBL0964.94010.
  2. Cilibrasi, Rudi; Vitányi, Paul M. B., Clustering by compression, IEEE Trans. Inf. Theory 51, No. 4, 1523-1545 (2005). ZBL1297.68097. ArXiv:cs:0312044
Source Link
Aidan Rocke
Aidan Rocke
  • 3.9k
  • 19
  • 47

Inspired by the informal notion of Cognitive distance, in 2010 Charles Bennett, Peter Gács, Ming Li, Paul Vitanyí and Wojcech Zurech introduced the notion of Information Distance which was used in the seminal paper Clustering by Compression:

\begin{equation} ID(x,y)=\min\{|p|:p(x)=y \land p(y)=x\} \tag{1} \end{equation}

with $p$ a finite binary program for the fixed universal computer $U$ which takes the finite binary strings $x,y$ as inputs. They prove that:

\begin{equation} ID(x,y)=E(x,y) + \mathcal{O}(\log E(x,y)) \tag{2} \end{equation}

where the key notion:

\begin{equation} E(x,y) = \max \{K_U(x|y),K_U(y|x) \} \tag{3} \end{equation}

satisfies the criteria of a metric up to the additive term $\mathcal{O}(\log E(x,y))$.

References:

  1. Bennett, Charles H., Péter Gács, Ming Li, Paul M. B. Vitányi and Wojciech H. Zurek. “Information distance.” 2006 IEEE International Conference on Granular Computing (1998): 1-1.
  2. Cilibrasi, R.; Vitanyi, P. M. B. (2011-09-27). "R. Cilibrasi, P.M.B. Vitanyi, Clustering by compression". IEEE Transactions on Information Theory. 51 (4): 1523–1545. arXiv:cs/0312044