A decomposition method for global evaluation of shannon entropy and local estimations of algorithmic complexity
We investigate the properties of a divide-and-conquer Block Decomposition Method (BDM), which extends the power of a Coding Theorem Method (CTM) that approximates local estimations of algorithmic complexity and of logical depth based upon Solomonoff-Levin's theory of algorithmic probability, th...
| Main Authors: | , , , , |
|---|---|
| Format: | Journal article |
| Published: |
2016
|
| _version_ | 1826260679382794240 |
|---|---|
| author | Zenil, H Soler-Toscano, F Kiani, N Hernández-Orozco, S Rueda-Toicen, A |
| author_facet | Zenil, H Soler-Toscano, F Kiani, N Hernández-Orozco, S Rueda-Toicen, A |
| author_sort | Zenil, H |
| collection | OXFORD |
| description | We investigate the properties of a divide-and-conquer Block Decomposition Method (BDM), which extends the power of a Coding Theorem Method (CTM) that approximates local estimations of algorithmic complexity and of logical depth based upon Solomonoff-Levin's theory of algorithmic probability, thereby providing a closer connection to algorithmic complexity. The strategy behind BDM is to find small computer programs that produce the components of a larger, decomposed object. The set of short computer programs can then be artfully arranged in sequence so as to produce the original object and to estimate an upper bound on the greatest length of the shortest computer program that produces said original object. We show that the method provides efficient estimations of algorithmic complexity but that it performs like Shannon entropy when it loses accuracy. We estimate errors and study the behaviour of BDM for different boundary conditions, all of which are compared and assessed in detail. The measure may be adapted for use with more multi-dimensional objects than strings, objects such as arrays and tensors. To test the measure we provide proofs of the algorithmic complexity relations among dual, isomorphic and cospectral graphs. Finally, we introduce a measure based upon the seminal concept of logical depth whose numerical comparisons to CTM and BDM agree with the theoretical expectations. We provide implementations in most major programming languages --Mathematica, Matlab, R, Java, Perl, Python, Pascal, C++, and Haskell-- and a free online algorithmic complexity calculator. |
| first_indexed | 2024-03-06T19:09:31Z |
| format | Journal article |
| id | oxford-uuid:164c772f-b0b5-416d-9ce4-be12ede7c28e |
| institution | University of Oxford |
| last_indexed | 2024-03-06T19:09:31Z |
| publishDate | 2016 |
| record_format | dspace |
| spelling | oxford-uuid:164c772f-b0b5-416d-9ce4-be12ede7c28e2022-03-26T10:30:27ZA decomposition method for global evaluation of shannon entropy and local estimations of algorithmic complexityJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:164c772f-b0b5-416d-9ce4-be12ede7c28eSymplectic Elements at Oxford2016Zenil, HSoler-Toscano, FKiani, NHernández-Orozco, SRueda-Toicen, AWe investigate the properties of a divide-and-conquer Block Decomposition Method (BDM), which extends the power of a Coding Theorem Method (CTM) that approximates local estimations of algorithmic complexity and of logical depth based upon Solomonoff-Levin's theory of algorithmic probability, thereby providing a closer connection to algorithmic complexity. The strategy behind BDM is to find small computer programs that produce the components of a larger, decomposed object. The set of short computer programs can then be artfully arranged in sequence so as to produce the original object and to estimate an upper bound on the greatest length of the shortest computer program that produces said original object. We show that the method provides efficient estimations of algorithmic complexity but that it performs like Shannon entropy when it loses accuracy. We estimate errors and study the behaviour of BDM for different boundary conditions, all of which are compared and assessed in detail. The measure may be adapted for use with more multi-dimensional objects than strings, objects such as arrays and tensors. To test the measure we provide proofs of the algorithmic complexity relations among dual, isomorphic and cospectral graphs. Finally, we introduce a measure based upon the seminal concept of logical depth whose numerical comparisons to CTM and BDM agree with the theoretical expectations. We provide implementations in most major programming languages --Mathematica, Matlab, R, Java, Perl, Python, Pascal, C++, and Haskell-- and a free online algorithmic complexity calculator. |
| spellingShingle | Zenil, H Soler-Toscano, F Kiani, N Hernández-Orozco, S Rueda-Toicen, A A decomposition method for global evaluation of shannon entropy and local estimations of algorithmic complexity |
| title | A decomposition method for global evaluation of shannon entropy and local estimations of algorithmic complexity |
| title_full | A decomposition method for global evaluation of shannon entropy and local estimations of algorithmic complexity |
| title_fullStr | A decomposition method for global evaluation of shannon entropy and local estimations of algorithmic complexity |
| title_full_unstemmed | A decomposition method for global evaluation of shannon entropy and local estimations of algorithmic complexity |
| title_short | A decomposition method for global evaluation of shannon entropy and local estimations of algorithmic complexity |
| title_sort | decomposition method for global evaluation of shannon entropy and local estimations of algorithmic complexity |
| work_keys_str_mv | AT zenilh adecompositionmethodforglobalevaluationofshannonentropyandlocalestimationsofalgorithmiccomplexity AT solertoscanof adecompositionmethodforglobalevaluationofshannonentropyandlocalestimationsofalgorithmiccomplexity AT kianin adecompositionmethodforglobalevaluationofshannonentropyandlocalestimationsofalgorithmiccomplexity AT hernandezorozcos adecompositionmethodforglobalevaluationofshannonentropyandlocalestimationsofalgorithmiccomplexity AT ruedatoicena adecompositionmethodforglobalevaluationofshannonentropyandlocalestimationsofalgorithmiccomplexity AT zenilh decompositionmethodforglobalevaluationofshannonentropyandlocalestimationsofalgorithmiccomplexity AT solertoscanof decompositionmethodforglobalevaluationofshannonentropyandlocalestimationsofalgorithmiccomplexity AT kianin decompositionmethodforglobalevaluationofshannonentropyandlocalestimationsofalgorithmiccomplexity AT hernandezorozcos decompositionmethodforglobalevaluationofshannonentropyandlocalestimationsofalgorithmiccomplexity AT ruedatoicena decompositionmethodforglobalevaluationofshannonentropyandlocalestimationsofalgorithmiccomplexity |