1 00:00:10,160 --> 00:00:14,688 In this lecture we will see how measures motivated or based on logical depth 2 00:00:15,056 --> 00:00:19,120 derived from CTM can find some interesting applications, 3 00:00:19,248 --> 00:00:22,624 even when logical depth is a much more difficult measure 4 00:00:22,880 --> 00:00:26,064 than althorithmic probability and algorithmic complexity 5 00:00:26,176 --> 00:00:31,984 because logical depth is neither lower or upper semicomputable. 6 00:00:32,112 --> 00:00:36,816 So one can never know whether one is really approximating it or not. 7 00:00:37,360 --> 00:00:42,032 Yet one can define frameworks in which logical depth is very interesting to apply. 8 00:00:43,480 --> 00:00:46,848 We will first see how approximating logical depth 9 00:00:46,944 --> 00:00:50,784 by using the compression times with lossless compression algorithms 10 00:00:51,040 --> 00:00:53,552 is something that has not been done before 11 00:00:53,696 --> 00:00:56,992 and it is capable of producing some interesting results. 12 00:00:57,344 --> 00:01:02,752 We will also see how the compression times and making perturbations in some of these experiments 13 00:01:02,880 --> 00:01:06,448 conform with the theoretical expectations of logical depth. 14 00:01:07,320 --> 00:01:10,368 Remember that the main idea behind logical depth 15 00:01:10,560 --> 00:01:15,232 is that the decompression instructions for trivial or random objects 16 00:01:15,500 --> 00:01:19,968 are very simple to follow and are therefore executed very fast 17 00:01:20,416 --> 00:01:24,410 with the compression process taking only a small amount of time 18 00:01:24,540 --> 00:01:27,553 simply because the compression algorithm 19 00:01:27,800 --> 00:01:30,966 either compresses very well in the case of simple objects 20 00:01:31,106 --> 00:01:34,293 or simply does not compress at all for random objects 21 00:01:34,890 --> 00:01:40,446 and instructions for the compressing random objects are almost nonexistent. 22 00:01:41,600 --> 00:01:45,184 Longer run times, however, are the result of a process 23 00:01:45,184 --> 00:01:49,936 following a set of time-consuming decompression instructions, 24 00:01:49,984 --> 00:01:53,872 hence a deep, complex process according to logical depth. 25 00:01:54,496 --> 00:01:57,904 The decompression time of the compressed version of a string 26 00:01:58,032 --> 00:02:04,544 can be considered an estimation of Bennett's logical depth based on the algorithm used. 27 00:02:06,000 --> 00:02:11,088 There seems to have been no previous attempt to implement an application of ideas 28 00:02:11,080 --> 00:02:15,904 based on Bennett's logical depth or using other compression times. 29 00:02:16,752 --> 00:02:20,304 But we implemented a simple framework to test some ideas 30 00:02:20,352 --> 00:02:22,544 and they turned out to be very interesting. 31 00:02:22,912 --> 00:02:26,896 What we did was to assess the feasibility of an application of the concept 32 00:02:27,136 --> 00:02:31,696 to the problem of image characterization and classification by logical depth. 33 00:02:32,112 --> 00:02:37,872 We performed a series of experiments of gradually increasing sophistication 34 00:02:38,096 --> 00:02:40,528 starting from fully controlled experiments 35 00:02:40,520 --> 00:02:43,952 and proceeding to the use of the best-known compression algorithms 36 00:02:44,112 --> 00:02:45,904 over a large data set. 37 00:02:46,448 --> 00:02:50,448 The first experiments consisted in controlling all the parameters involved. 38 00:02:50,832 --> 00:02:55,152 For example, adding random lines would first increase the structure, but weakly, 39 00:02:55,152 --> 00:02:57,150 even before reaching half the image, 40 00:02:57,150 --> 00:03:00,928 of full of random black pixels and white pixels, 41 00:03:01,776 --> 00:03:07,152 back to low logical depth because the image started looking random and finally simple. 42 00:03:09,000 --> 00:03:12,448 The battery of tests involved a series of images 43 00:03:12,440 --> 00:03:16,448 devised to tune and verify different aspects of the methodology 44 00:03:17,008 --> 00:03:20,256 and a more realistic data set was also used, 45 00:03:20,360 --> 00:03:22,976 indicating whether the results were stable enough 46 00:03:22,980 --> 00:03:26,940 to yield their same values for replication purposes 47 00:03:27,050 --> 00:03:29,160 and whether they were consistent with the theory 48 00:03:29,168 --> 00:03:31,648 and consonant with an intuitive sense 49 00:03:31,728 --> 00:03:35,936 of complex or sophisticated versus a simple object. 50 00:03:36,576 --> 00:03:39,792 Here we have a classification of images by compression length 51 00:03:39,790 --> 00:03:44,864 using a compression algorithm called png croche 52 00:03:45,104 --> 00:03:48,880 which is a lossless compression algorithm that compresses png images. 53 00:03:49,312 --> 00:03:52,384 And the results are very stable when you see another compression algorithm 54 00:03:52,380 --> 00:03:55,680 such as bzip2 and Compress. 55 00:03:57,056 --> 00:04:03,104 The png format is in some way ideal because png is a lossless compression format, 56 00:04:03,360 --> 00:04:10,512 unlike other formats such as jpg that store images by applying lossy compression. 57 00:04:11,180 --> 00:04:15,376 In other words, png images do not lose any information of the image. 58 00:04:17,616 --> 00:04:20,224 Here is the ranking by the compression times. 59 00:04:20,416 --> 00:04:24,464 The execution time was given by the mathematical function timing. 60 00:04:24,816 --> 00:04:29,936 The function timing evaluates an expression and returns a list of the time taken in seconds, 61 00:04:30,128 --> 00:04:32,080 together with the result obtained. 62 00:04:32,512 --> 00:04:37,376 The function includes only CPU time spent in the mathematical kernel. 63 00:04:38,528 --> 00:04:43,552 The fact that several processes run concurrently in computing systems 64 00:04:43,664 --> 00:04:45,824 as part of their normal operation 65 00:04:45,888 --> 00:04:48,320 is one of the greatest challenges faced 66 00:04:48,320 --> 00:04:53,520 in attempting to measure with accuracy the time that the compression process takes, 67 00:04:54,112 --> 00:04:58,368 even when it is isolated from all other computer processes. 68 00:04:58,816 --> 00:05:04,432 This instability is due to the fact that the internal operation of the computer comes in several layers, 69 00:05:04,608 --> 00:05:06,880 mostly at the operating system level. 70 00:05:07,120 --> 00:05:11,968 So we killed all processes and ran the experiments after dummy warm-up computations, 71 00:05:12,240 --> 00:05:15,744 yielding rather stable results on the same computer. 72 00:05:16,410 --> 00:05:19,546 One can see the differences in the way in which compression lengths 73 00:05:19,546 --> 00:05:24,520 and the compression times produced results from the last two figures. 74 00:05:25,120 --> 00:05:26,900 And they are in agreement with the theory 75 00:05:26,900 --> 00:05:31,626 assigning low compression and low decompression time 76 00:05:31,626 --> 00:05:33,620 to random and simple objects, 77 00:05:33,620 --> 00:05:36,973 but high logical depth to some objects in the middle. 78 00:05:39,113 --> 00:05:42,433 One can see the differences as they were theoretically expected. 79 00:05:42,680 --> 00:05:48,040 On the left we have the algorithmic complexity to logical depth mapping of each image, 80 00:05:48,140 --> 00:05:52,960 and on the right we have groups by logical depth based on the decompression times. 81 00:05:53,480 --> 00:05:57,620 So we can see how simple images remained shallow for logical depth, 82 00:05:57,620 --> 00:06:01,100 but random images that were incompressible, 83 00:06:01,293 --> 00:06:05,340 and thus ranked high according to algorithmic complexity, 84 00:06:05,466 --> 00:06:07,673 were ranked low for logical depth, 85 00:06:07,966 --> 00:06:11,673 thereby exhibiting everything that has more structure 86 00:06:11,806 --> 00:06:15,706 as logical depth would quantify. 87 00:06:16,233 --> 00:06:22,400 The groups that resonate very much with intuition of what is complex in the sense of a structure or sophistication 88 00:06:22,713 --> 00:06:26,386 processes that require computational time to be produced or generated 89 00:06:26,430 --> 00:06:31,653 versus other objects that do not require such computation, such as simple or random objects, 90 00:06:32,133 --> 00:06:37,280 were found exactly in the middle, as predicted by logical depth. 91 00:06:38,860 --> 00:06:44,280 In the next lesson we will see how many of these tools and measures, in particular algorithmic probability, 92 00:06:44,833 --> 00:06:49,566 can make serious contributions to areas of machine learning and artificial intelligence.