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.