Algorithmic information approximations in data analysis

Abstract

Despite being highly heterogeneous, all data can be reduced to a string of bits. Kolmogorov complexity analyses data in this way, measuring a string’s complexity by determining the length of a smallest program which, when executed, generates that string and halts. Even though Kolmogorov complexity is noncomputable, it can be approximated, and as such, it is possible to perform data analysis using these approximations. This dissertation ties in directly with this subject since it studies Kolmogorov complexity approximations in data description and its potential applications. First, we use Kolmogorov complexity approximation measures in genomic data. We demonstrate that using specific data compressors to quantify data complexity profoundly impacts genomic taxonomic identification, classification, and organization. Afterwards, we examine the application of information-based measures in 2-dimensional digital objects, specifically artistic paintings. Using these measures, we developed techniques that can be valuable for art authorship attribution and validation, art style categorization and organization, and art content explanation. Subsequently, we apply Kolmogorov approximations to data generated by Turing Machines. Specifically, using these measures, we investigate the relationship between the algorithmic and probabilistic complexities of the Turing Machine tapes. Complexity is studied globally by investigating probabilistic complexity patterns yielded by sequentially generated TMs, and locally using complexity profiles. Furthermore, we also introduce a method for increasing probabilistic complexity while retaining the same algorithmic complexity. Finally, using the knowledge from studying Turing Machine tapes, we introduce a methodology that, given a string, searches for programs that generate approximately the same output.

Apesar de serem altamente heterogéneos, todos os dados podem ser reduzidos a uma sequência de bits. A complexidade de Kolmogorov analisa os dados dessa maneira, medindo a complexidade de uma sequência de bits, ao determinar o comprimento de um dos programas mais pequenos que, quando executado, gera essa sequência de bits e pára. Embora a complexidade de Kolmogorov não seja computável, ela pode ser aproximada e, como tal, é possível realizar análises de dados usando essas aproximações. Esta dissertação relaciona-se diretamente com este assunto, uma vez que estuda estas aproximações na descrição de diferentes tipos de dados, criando potenciais aplicações. Primeiro, usamos medidas de aproximação de complexidade de Kolmogorov em dados genómicos. Demonstramos que o uso de compressores de dados específicos para quantificação da complexidade dos dados impacta profundamente a identificação taxonómica de genomas, a sua classificação e organização. Em seguida, examinamos a aplicação destas medidas em objetos digitais bidimensionais, especificamente em pinturas artísticas. Usando estas medidas, desenvolvemos técnicas que podem ser valiosas para atribuição e validação de autoria de arte, categorização e organização de estilo de arte e explicação de conteúdo de arte. Posteriormente, aplicamos essas medidas a dados gerados por Máquinas de Turing. Especificamente, usando estas medidas, investigamos a relação entre as complexidades algorítmicas e probabilísticas das fitas da Máquina de Turing. A complexidade é estudada globalmente por meio da investigação dos padrões gerados por Máquinas de Turing, criadas sequencialmente e localmente por meio de perfis de complexidade. Além disso, introduzimos um método para aumentar a complexidade probabilística mantendo a complexidade algorítmica. Finalmente, usando o conhecimento do estudo efetuado à complexidade das fitas da Máquina de Turing, apresentamos uma metodologia que procura programas que geram aproximadamente a mesma sequência de dados que fornecemos ao programa.