
Title:

Description:

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 timeconsuming 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
bestknown 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 warmup 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.