In this lecture we will see how measures motivated or based on logical depth
derived from CTM can find some interesting applications,
even when logical depth is a much more difficult measure
than althorithmic probability and algorithmic complexity
because logical depth is neither lower or upper semicomputable.
So one can never know whether one is really approximating it or not.
Yet one can define frameworks in which logical depth is very interesting to apply.
We will first see how approximating logical depth
by using the compression times with lossless compression algorithms
is something that has not been done before
and it is capable of producing some interesting results.
We will also see how the compression times and making perturbations in some of these experiments
conform with the theoretical expectations of logical depth.
Remember that the main idea behind logical depth
is that the decompression instructions for trivial or random objects
are very simple to follow and are therefore executed very fast
with the compression process taking only a small amount of time
simply because the compression algorithm
either compresses very well in the case of simple objects
or simply does not compress at all for random objects
and instructions for the compressing random objects are almost nonexistent.
Longer run times, however, are the result of a process
following a set of time-consuming decompression instructions,
hence a deep, complex process according to logical depth.
The decompression time of the compressed version of a string
can be considered an estimation of Bennett's logical depth based on the algorithm used.
There seems to have been no previous attempt to implement an application of ideas
based on Bennett's logical depth or using other compression times.
But we implemented a simple framework to test some ideas
and they turned out to be very interesting.
What we did was to assess the feasibility of an application of the concept
to the problem of image characterization and classification by logical depth.
We performed a series of experiments of gradually increasing sophistication
starting from fully controlled experiments
and proceeding to the use of the best-known compression algorithms
over a large data set.
The first experiments consisted in controlling all the parameters involved.
For example, adding random lines would first increase the structure, but weakly,
even before reaching half the image,
of full of random black pixels and white pixels,
back to low logical depth because the image started looking random and finally simple.
The battery of tests involved a series of images
devised to tune and verify different aspects of the methodology
and a more realistic data set was also used,
indicating whether the results were stable enough
to yield their same values for replication purposes
and whether they were consistent with the theory
and consonant with an intuitive sense
of complex or sophisticated versus a simple object.
Here we have a classification of images by compression length
using a compression algorithm called png croche
which is a lossless compression algorithm that compresses png images.
And the results are very stable when you see another compression algorithm
such as bzip2 and Compress.
The png format is in some way ideal because png is a lossless compression format,
unlike other formats such as jpg that store images by applying lossy compression.
In other words, png images do not lose any information of the image.
Here is the ranking by the compression times.
The execution time was given by the mathematical function timing.
The function timing evaluates an expression and returns a list of the time taken in seconds,
together with the result obtained.
The function includes only CPU time spent in the mathematical kernel.
The fact that several processes run concurrently in computing systems
as part of their normal operation
is one of the greatest challenges faced
in attempting to measure with accuracy the time that the compression process takes,
even when it is isolated from all other computer processes.
This instability is due to the fact that the internal operation of the computer comes in several layers,
mostly at the operating system level.
So we killed all processes and ran the experiments after dummy warm-up computations,
yielding rather stable results on the same computer.
One can see the differences in the way in which compression lengths
and the compression times produced results from the last two figures.
And they are in agreement with the theory
assigning low compression and low decompression time
to random and simple objects,
but high logical depth to some objects in the middle.
One can see the differences as they were theoretically expected.
On the left we have the algorithmic complexity to logical depth mapping of each image,
and on the right we have groups by logical depth based on the decompression times.
So we can see how simple images remained shallow for logical depth,
but random images that were incompressible,
and thus ranked high according to algorithmic complexity,
were ranked low for logical depth,
thereby exhibiting everything that has more structure
as logical depth would quantify.
The groups that resonate very much with intuition of what is complex in the sense of a structure or sophistication
processes that require computational time to be produced or generated
versus other objects that do not require such computation, such as simple or random objects,
were found exactly in the middle, as predicted by logical depth.
In the next lesson we will see how many of these tools and measures, in particular algorithmic probability,
can make serious contributions to areas of machine learning and artificial intelligence.