• The Amara editor has new beta features! Explore the new features, try them out and let us know what you think!
Learn Beta! Hide

## ← 7.11 Applications of Logical Depth to Image Classification

• 2 Followers
• 92 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=sz97zwPW2xw" data-team="complexity-explorer"></div> ``` 1 Language

Showing Revision 2 created 02/04/2019 by cathcaptioner.

1. In this lecture we will see how measures
motivated or based on logical depth

2. derived from CTM can find
some interesting applications,
3. even when logical depth
is a much more difficult measure
4. than althorithmic probability
and algorithmic complexity
5. because logical depth is neither lower
or upper semicomputable.
6. So one can never know whether one
is really approximating it or not.
7. Yet one can define frameworks in which
logical depth is very interesting to apply.
8. We will first see how approximating logical depth
9. by using the compression times
with lossless compression algorithms
10. is something that has not been done before
11. and it is capable of producing
some interesting results.
12. We will also see how the compression times
and making perturbations in some of these experiments
13. conform with the theoretical expectations
of logical depth.
14. Remember that the main idea behind logical depth
15. is that the decompression instructions
for trivial or random objects
16. are very simple to follow
and are therefore executed very fast
17. with the compression process
taking only a small amount of time
18. simply because the compression algorithm
19. either compresses very well in the case of simple objects
20. or simply does not compress at all for random objects
21. and instructions for the compressing random objects
are almost nonexistent.
22. Longer run times, however, are the result of a process
23. following a set of time-consuming decompression instructions,
24. hence a deep, complex process according to logical depth.
25. The decompression time of the compressed version of a string
26. can be considered an estimation of Bennett's logical depth
based on the algorithm used.
27. There seems to have been no previous attempt
to implement an application of ideas
28. based on Bennett's logical depth or using other compression times.
29. But we implemented a simple framework to test some ideas
30. and they turned out to be very interesting.
31. What we did was to assess the feasibility
of an application of the concept
32. to the problem of image characterization
and classification by logical depth.
33. We performed a series of experiments
34. starting from fully controlled experiments
35. and proceeding to the use of the
best-known compression algorithms
36. over a large data set.
37. The first experiments consisted
in controlling all the parameters involved.
38. For example, adding random lines
would first increase the structure, but weakly,
39. even before reaching half the image,
40. of full of random black pixels and white pixels,
41. back to low logical depth because the image
started looking random and finally simple.
42. The battery of tests involved a series of images
43. devised to tune and verify different aspects of the methodology
44. and a more realistic data set was also used,
45. indicating whether the results were stable enough
46. to yield their same values for replication purposes
47. and whether they were consistent with the theory
48. and consonant with an intuitive sense
49. of complex or sophisticated versus a simple object.
50. Here we have a classification of images by compression length
51. using a compression algorithm called png croche
52. which is a lossless compression algorithm that compresses png images.
53. And the results are very stable
when you see another compression algorithm
54. such as bzip2 and Compress.
55. The png format is in some way ideal
because png is a lossless compression format,
56. unlike other formats such as jpg that store images
by applying lossy compression.
57. In other words, png images do not lose
any information of the image.
58. Here is the ranking by the compression times.
59. The execution time was given by the mathematical function timing.
60. The function timing evaluates an expression
and returns a list of the time taken in seconds,
61. together with the result obtained.
62. The function includes only CPU time spent
in the mathematical kernel.
63. The fact that several processes run concurrently
in computing systems
64. as part of their normal operation
65. is one of the greatest challenges faced
66. in attempting to measure with accuracy
the time that the compression process takes,
67. even when it is isolated from all other computer processes.
68. This instability is due to the fact that
the internal operation of the computer comes in several layers,
69. mostly at the operating system level.
70. So we killed all processes and ran the experiments
after dummy warm-up computations,
71. yielding rather stable results on the same computer.
72. One can see the differences in the way
in which compression lengths
73. and the compression times produced
results from the last two figures.
74. And they are in agreement with the theory
75. assigning low compression and low decompression time
76. to random and simple objects,
77. but high logical depth to some objects in the middle.
78. One can see the differences as they were theoretically expected.
79. On the left we have the algorithmic complexity
to logical depth mapping of each image,
80. and on the right we have groups by logical depth
based on the decompression times.
81. So we can see how simple images remained shallow for logical depth,
82. but random images that were incompressible,
83. and thus ranked high according to algorithmic complexity,
84. were ranked low for logical depth,
85. thereby exhibiting everything that has more structure
86. as logical depth would quantify.
87. The groups that resonate very much with intuition
of what is complex in the sense of a structure or sophistication
88. processes that require computational time to be produced or generated
89. versus other objects that do not require such computation, such as simple or random objects,
90. were found exactly in the middle, as predicted by logical depth.
91. In the next lesson we will see how many of these tools and measures,
in particular algorithmic probability,
92. can make serious contributions
to areas of machine learning and artificial intelligence.