Complexidade de Kolmogorov: Diferenzas entre revisións

Explorar o historial de forma interactiva

← Edición máis vella Edición máis nova →

Contido eliminado Contido engadido

En liña

Revisión como estaba o 11 de febreiro de 2008 ás 05:20

A complexidade de Kolmogorov é unha teoría da información e da aleatoriedade, profunda e sofisticada, que trata da cantidade de información dos obxectos individuais, medida a través do tamaño da súa menor descripción algorítmica. É unha noción moderna de aleatoriedade, e reférese a un concepto puntual de aleatoriedade, no canto dunha aleatoriedade media como o fai a teoría da probabilidade. É un ramo derivado da teoría da información de Claude E. Shannon, aínda que hoxe poida ser considerada unha área de investigación madura e autónoma.

A complexidade de Kolmogorov define unha nova teoría da información, chamada teoría algorítmica da información (por tratar con algoritmos). Úsase a Máquina de Turing como mecanismo para descreber os obxectos (para definir os algoritmos).

Orixe

A complexidade de Kolmogorov ten súa orixe nos anos 1960, cando Andrei Kolmogorov, Ray Solomonoff e Gregory Chaitin desenvolveron, de forma independente, unha teoría da información baseada no tamaño dos programas para a Máquina de Turing. Acordouse chamar a área xenericamente como "complexidade de Kolmogorov" en homenaxe ao famoso matemático ruso, e fundador da área, Andrei Nikolaevich Kolmogorov (1903-1987).

Definición

A complexidade de Kolmogorov está definida sobre o conxunto de cadeas binarias (secuencias de ceros e uns). Ela asocia a cada cadea binaria un valor numérico que é súa "complexidade".

A complexidade de Kolmogorov pode ser definida simplificadamente como o tamaño do menor programa (ou descripción algoritmica) que calcula na Máquina de Turing unha determinada cadea binaria.

Exixese que o conxunto de descripcións (programas) forme un conxunto libre de prefixo, e chámase a esta complexidade "complexidade de prefixo", representada por $K(x)$ . Para enfatizar a Máquina que está sendo usada para definir a complexidade podemos escreber $K_{M}(x)$ en vez de $K(x)$ , onde $M$ é unha Máquina de Turing en particular.

Tamén podemos definir unha complexidade condicional, $K(x|y)$ , definida como o tamaño do programa que calcula $x$ a partir de $y$ , que é dado como entrada do programa. Intuitivamente, $K(x|y)$ representa a cantidade de información que debemos sumar á información en $y$ para calcular $x$ .

É importante que se fundamente ben o concepto de descripción (ou sexa, formalmente definido como un programa para a máquina de Turing) para evitar paradoxos. Os paradoxos (ou antinomias) son bastante frecuentes na historia da matemática. Podemos citar o famoso "paradoxo do barbeiro", de Bertrand Russel, que di que "o barbeiro é aquel que afeita aos homes que non se afeitan a si mesmos". O paradoxo é obtido ao perguntar se o barbeiro se barbea a si mesmo.

Máquina de Turing

Artigo principal: [[Máquina de Turing]].

A Máquina de Turing é un dispositivo que foi proposto en 1936 por Alan Turing co obxectivo de formalizar matematicamente o que entendemos por "computador". Ela está formada basicamente por unha fita (cinta) na cal un cabezallo pode escribir símbolos dun conxunto predefinido, e así cálculos de diversos tipos poden ser feitos apenas cos movimentos deste cabezal sobre a fita.

Unha propriedade importante da Máquina de Turing é a universalidade, ou sexa, a capacidade da Máquina de Turing de simular calquer outra máquina. Por isto, podemos chamala máquina universal.

Teorema da Invarianza

Da forma como foi definido, pode parecer que a complexidade de Kolmogorov permanece dependente da máquina escollida como máquina de referencia. Porén, existe un teorema (chamado Teorema da Invarianza) que proba que todas as máquinas universais (ou sexa, que ten a capacidade de simular todas as outras máquinas de Turing concebibles) resultan no mesmo valor de complexidade, a non ser por unha constante que é asintoticamente desprezable: $K_{U1}(x)\leq K_{U2}(x)+c$ , para algunha constante $c$ , e $U1$ e $U2$ son dúas máquinas universais calquera.

Isto significa que a complexidade pasa a ser un atributo intrínseco do obxecto, independente da máquina universal escollida como máquina de referencia.

Principio de Occam

Artigo principal: [[Navalla de Occam]].

Ao medir a complexidade dunha cadea polo tamaño do menor programa, a complexidade de Kolmogorov reedita un antigo principio, de autoría de William de Ockham (1285?-1349?), que ficou coñecido como Principio de Occam, que di que "as entidades non deben ser multiplicadas innecesariamente".

O Principio de Occam significa que entre todas as teorías que explican un fenómeno, a máis simple (ou menor) é a mellor para este fín. Isto ten evidentes connotacións filosóficas relacionadas coa expresividade dos métodos de descripción e cos sistemas formais.

Algunhas propriedades

Trivialmente, $K(x)\leq |x|+c$ , para algún $c$ , onde $|x|$ denota o tamaño da cadea (string) $x$ , xa que calquer cadea pode ser computada por un programa que a teña armacenada literalmente no programa.

Tamén sabemos que $K(x|y)\leq K(x)+c$ , xa que, na complexidade condicional, a presenza de $y$ é unha información a máis que é dada ao programa que calculará $x$ .

Se $x$ denota unha cadea binaria que é resultado dun $p$ -proceso de Bernoulli, entón ${\frac {1}{m}}K(x)\rightarrow H(p,1-p)$ en probabilidade, onde $H(p,1-p)$ é a entropía do proceso. Isto significa que $K(x)$ é asintoticamente converxente á entropía da teoría da información clásica.

Incompresividade de cadeas binarias

Se para unha cadea binaria $x$ , $K(x)\geq |x|-c$ , para algún $c$ , entón dicimos que $x$ é incompresible.

Kolmogorov asociou o concepto de incompresividade co concepto de aleatoriedade, co obxectivo de definir secuencias aleatorias, e así fornecer unha base teórica para probabilidades e estatística.

Obxectivo da complexidade de Kolmogorov

O obxectivo orixinal do traballo de Kolmogorov era obter unha definición formal de secuencia aleatoria. Kolmogorov observou que algunhas secuencias binarias podían comprimirse algoritmicamente. Hoxe en día, a maioría das persoas están afeitas a usar programas de compresión de datos, tales como winzip, gzip, etc. Así, a idea de que os datos se poidan comprimir non é extraña.

É doado entender que un número como 1.000.000.000 na base 10 pode facilmente expresarse como $10^{9}$ , mentres que o número 5.321.478.927, escollido arbitrariamente, non podería ser expresado desta forma compacta.

Se tomarmos as cadeas binarias 11111111111111111111 e 10110011010111011010, aceitaríamos facilmente a segunda como resultante do lanzamento sucesivo dunha moeda honesta (1=cara e 0=coroa); porén, dificilmente a primeira secuencia podería ser resultado dun experimento realmente aleatorio. Notamos que a primeira cadea podería ser computada polo programa:

FOR I=1 TO 20 PRINT 1

Que é un programa pequeno en relación ao tamaño da cadea. A segunda cadea non pode ser calculada por un programa tan curto, pois el deberá conter a propria cadea literalmente armacenada dentro do programa:

PRINT 10110011010111011010

Kolmogorov postulou que as secuencias que non poden ser comprimidas algoritmicamente nunha descripción de tamaño moito menor que a secuencia orixinal son secuencias aleatorias (no sentido estocástico do termo). Esta definición só funciona se se admiten soamente descripcións dentro dunha clase de descripcións libres de prefixo (ou sexa que nengunha descripción sexa prefixo doutra da clase).

Desigualdade de Kraft

A razón para exixir que o conxunto de descripcións (programas) forme un conxunto libre de prefixo debese a desigualdade de Kraft, expresión ben coñecida na teoría da información clásica. Ela significa que a serie $\sum 2^{-K(x)}$ converxe. Esta é unha propriedade importante da complexidade de Kolmogorov.

Secuencias Aleatorias de Martin-Löf

Unha resposta consistente ao problema de definir o concepto de secuencia aleatoria foi dada por Martin-Löf. A definición de Martin-Löf basease na teoría da medida, e na existencia dun conxunto efetivo nulo máximo, no conxunto das cadeas binarias. Isto significa a existencia dun conxunto nulo (con baixa probabilidade de ocorrencia) que contén todos os conxuntos nulos cuxas cadeas poden ser algoritmicamente xeradas. Esta definición equivale a afirmar a existencia dun teste de aleatoriedade universal. Interesante observar que a definición de Martin-Löf é equivalente á definición de secuencia aleatoria dada pola complexidade de Kolmogorov (via incompresividade das cadeas).

Aplicacións

Solomonoff propuxo o uso da regra de Bayes para obter previsión inductiva, ou sexa, para prever a secuencia dunha cadea binaria. Para isto el usou como probabilidade previa a probabilidade universal, que pode ser definida como $2^{-K(x)}$ , porque ela domina toda probabilidade previa semi-computable concebible. Isto constituise no núcleo dos métodos de intelixencia artificial MDL (minimum description length) e MML (minimum message length).

A complexidade $K(x|y)$ induce un concepto de distancia (ou similaridade), chamada distancia de información, que é unha medida a priori e absoluta sobre o conxunto das cadeas binarias. Esta distancia pode ser aplicada en diversos e diferentes contextos de forma moito similar a outras medidas de distancia definidas na matemática. O interesante é que podemos aproximar esta medida usando un programa compresor de dados e efetuar medicións empíricas. Destácanse como aplicacións desta distancia o recoñecimento dos xenomas, a clasificación automática de música, e o establecimento dunha hierarquía de linguaxes humanas.

Chaitin construíu un paradoxo co tamaño dos programas que constituise nunha proba alternativa ao que ficou coñecido como proba de Gödel (ou Teorema da incompletude de Gödel). Chaitin baseouse no paradoxo de Berry que supón considerar o menor número enteiro positivo que non pode ser definido por unha frase con menos de 1.000.000.000 de caracteres. Sen embargo, a propria definición do problema define o número e ten menos de 1.000.000.000 de caracteres, o que é unha contradicción. Isto resulta que as cadeas non se poden producir por programas que teñan menos complexidade que a propria cadea, sendo isto un limite dos sistemas formais.

Unha outra interesante aplicación de complexidade de Kolmogorov é o número máxico e místico $\Omega$ , proposto por Chaitin, definido como: $\Omega =\sum _{p}2^{-|p|}.$ Nesta fórmula, $p$ representa un programa que pára (finaliza) e $|p|$ é o tamaño deste programa. É interesante observar que $0\leq \Omega \leq 1$ , representando $\Omega$ a probabilidade de que un programa calquera finalice. $\Omega$ é un número real aleatorio (cuxos díxitos forman unha secuencia aleatoria) e non computable (ou sexa, non pode ser computado por un programa na máquina de Turing). Alén disto, $\Omega$ contén en si, da forma máis compacta posible, todas as verdades matemáticas posibles de seren expresas.

Diversas outras aplicacións da teoría foron desenvolvidas desde entón: intelixencia artificial, linguaxes formais, complexidade computacional, teoría de grafos, biotecnoloxía, etc.

Véxase tamén

Ligazóns externas

@@ Liña 67: / Liña 67: @@
 == Secuencias Aleatorias de Martin-Löf ==
-Unha resposta consistente ao problema de definir o conceito de secuencia aleatoria foi dada por [[Martin-Löf]]. A definición de Martin-Löf basease na [[teoría da medida]], e na existencia dun conxunto efetivo nulo máximo, no conxunto das cadeas binarias. Isto significa a existencia dun conxunto nulo (con baixa probabilidade de ocorrencia) que contén todos os conxuntos nulos cuxas cadeas poden ser algoritmicamente xeradas. Esta definición equivale a afirmar a existencia dun teste de aleatoriedade universal. Interesante observar que a definición de Martin-Löf é equivalente á definición de secuencia aleatoria dada pola complexidade de Kolmogorov (via incompresividade das cadeas).
+Unha resposta consistente ao problema de definir o concepto de secuencia aleatoria foi dada por [[Martin-Löf]]. A definición de Martin-Löf basease na [[teoría da medida]], e na existencia dun conxunto efetivo nulo máximo, no conxunto das cadeas binarias. Isto significa a existencia dun conxunto nulo (con baixa probabilidade de ocorrencia) que contén todos os conxuntos nulos cuxas cadeas poden ser algoritmicamente xeradas. Esta definición equivale a afirmar a existencia dun teste de aleatoriedade universal. Interesante observar que a definición de Martin-Löf é equivalente á definición de secuencia aleatoria dada pola complexidade de Kolmogorov (via incompresividade das cadeas).
 == Aplicacións ==
 Solomonoff propuxo o uso da regra de Bayes para obter previsión inductiva, ou sexa, para prever a secuencia dunha cadea binaria. Para isto el usou como probabilidade previa a probabilidade universal, que pode ser definida como <math>2^{-K(x)}</math>, porque ela domina toda probabilidade previa semi-computable concebible. Isto constituise no núcleo dos métodos de intelixencia artificial MDL (minimum description length) e MML (minimum message length).
-A complexidade <math>K(x|y)</math> induce un conceito de distancia (ou similaridade), chamada distancia de información, que é unha medida a priori e absoluta sobre o conxunto das cadeas binarias. Esta distancia pode ser aplicada en diversos e diferentes contextos de forma moito similar a outras medidas de distancia definidas na matemática. O interesante é que podemos aproximar esta medida usando un programa compresor de dados e efetuar medicións empíricas. Destácanse como aplicacións desta distancia o recoñecimento dos xenomas, a clasificación automática de música, e o establecimento dunha hierarquía de linguaxes humanas.
+A complexidade <math>K(x|y)</math> induce un concepto de distancia (ou similaridade), chamada distancia de información, que é unha medida a priori e absoluta sobre o conxunto das cadeas binarias. Esta distancia pode ser aplicada en diversos e diferentes contextos de forma moito similar a outras medidas de distancia definidas na matemática. O interesante é que podemos aproximar esta medida usando un programa compresor de dados e efetuar medicións empíricas. Destácanse como aplicacións desta distancia o recoñecimento dos xenomas, a clasificación automática de música, e o establecimento dunha hierarquía de linguaxes humanas.
 Chaitin construíu un paradoxo co tamaño dos programas que constituise nunha proba alternativa ao que ficou coñecido como proba de [[Kurt Gödel|Gödel]] (ou [[Teorema da incompletude de Gödel]]). Chaitin baseouse no paradoxo de Berry que supón considerar o menor número enteiro positivo que non pode ser definido por unha frase con menos de 1.000.000.000 de caracteres. Sen embargo, a propria definición do problema define o número e ten menos de 1.000.000.000 de caracteres, o que é unha contradicción. Isto resulta que as cadeas non se poden producir por programas que teñan menos complexidade que a propria cadea, sendo isto un limite dos sistemas formais.