Relação entre complexidade computacional e informação

11

Trabalho em um laboratório de neurociência computacional que quantifica as informações mútuas entre pares ou grupos de neurônios. Recentemente, o chefe mudou seu foco para medir a "complexidade da dinâmica neural". Ao seguir essa linha de pesquisa, algumas pessoas no meu grupo parecem equiparar "complexo" a "tem uma alta entropia".

Alguém pode me orientar sobre qual é a relação entre complexidade computacional (no sentido do CS) e entropia no sentido da teoria da informação?

Para explicar um pouco mais, medidas como a complexidade de Lempel-Ziv, não me parecem medidas válidas de complexidade, porque confundem informativo (para o usuário) com o transporte de muitos bits. Outras medidas, como [Causal State Splitting Reconstruction][1]são muito menos conhecidas, mas têm a propriedade atraente de que processos aleatórios têm complexidade zero, porque zero estados ocultos são necessários para representar um processo aleatório estacionário.

mac389
fonte
11
Você poderia explicar o que significa "complexo" em seu campo? Isso significa que os neurônios estão disparando significativamente ou mais deles participam?
vs
@ VS: Existem muitas definições concorrentes para "complexo". Alguns dizem que o processo mais complexo é o de maior entropia. Isso, no entanto, implicaria que processos aleatórios são complexos, o que não parece biologicamente realista. Mesmo assim, "disparar de forma significativa" está mais próximo do que "participar mais ...", embora provavelmente "participar de forma significativa" seja ainda mais próximo.
mac389
11
Entendemos que complexo implica maior entropia em nosso campo. Fiz essa pergunta para entender o que seu campo significa por complexo. Então, "participar mais de maneira significativa" está mais próximo. Ok. Esse é o meu palpite. Para mim, "participar de forma significativa" implica que os neurônios estão se comunicando "de maneira inteligente" ou "respondendo a estímulos" para um "resultado desejado específico". está geralmente associada a uma maior entropia ou informações na teoria da informação.
vs
@ VS: Há uma questão de como duas entropia quantificam quando o esquema de codificação não é conhecido e provavelmente está mudando, como parece ser o caso no cérebro. As pessoas disseram que usaram as informações mútuas entre um neurônio e um estímulo para quantificar o quão seletivo esse neurônio é para esse estímulo. A questão fica mais confusa quando se considera o caso mais realista de muitos neurônios.
mac389
11
@ mac389 podemos significar várias coisas como a complexidade de um objeto. alguns exemplos são: complexidade de Kolmogorov (que você recebeu uma resposta) e várias noções de complexidade de Kolmogorov com prazo determinado; quando você tem uma família de objetos de tamanhos variados, analisamos quanto tempo / espaço (em função do tamanho do objeto) é necessário um algoritmo para reconhecer que um objeto pertence à classe. você tem um problema de modelagem bastante não trivial aqui, eu acho.
Sasho Nikolov

Respostas:

9

Existem conexões suficientes entre a teoria da informação e a complexidade computacional para merecer um curso de graduação, por exemplo, este: http://www.cs.princeton.edu/courses/archive/fall11/cos597D/

Sasho Nikolov
fonte
Obrigado, juntamente com uma discussão com pessoas mais informadas, é exatamente isso que eu estava procurando.
mac389
7

Muitas pessoas mencionaram a complexidade de Kolmogorov ou suas variantes limitadas por recursos, mas acho que algo mais próximo do que você está procurando é a noção de profundidade (lógica) . Existem várias variantes em profundidade, mas todas tentam entender algo do que você está falando. Em particular, nem cadeias puramente aleatórias nem cadeias muito ordenadas / repetitivas são profundas.

Uma noção de profundidade é intuitivamente: uma string é profunda se tiver uma descrição curta, mas a única maneira de reconstruí-la a partir dessa descrição curta leva uma quantidade excessiva de tempo. Esta é a noção de profundidade e várias outras são introduzidas e desenvolvidas em [1]. A outra referência padrão é [2]. Eu olhava para eles e depois fazia uma pesquisa de referência direta.

[1] L. Antunes, L. Fortnow, D. van Melkebeek, NV Vinodchandran. Profundidade computacional: conceito e aplicações . Theoret. Comp. Sci. 354 (3): 391--404. Também disponível gratuitamente na página do autor .

[2] CH Bennett. Profundidade lógica e complexidade física. Em R. Herken (Ed.), A Máquina Universal de Turing: Uma Pesquisa de Meio Século, Oxford University Press, Oxford (1988), 227–257.

Joshua Grochow
fonte
Muito obrigado por esta resposta. A profundidade lógica parece estar muito próxima do que eu quis dizer com complexidade.
mac389
3

A primeira coisa que vem à mente como algo que você pode achar fascinante é a complexidade de Kolmogorov; Certamente acho fascinante e, como você não mencionou, pensei que valeria a pena mencionar.

Dito isto, uma abordagem mais geral para responder a essa pergunta pode ser baseada na teoria das linguagens e dos autômatos. Autômatos finitos determinísticos são O (n) processadores de string. Ou seja, dada uma sequência de comprimento n, eles processam a sequência em precisamente n etapas (muito disso depende de como você define autômatos finitos determinísticos; no entanto, um DFA certamente não requer mais etapas). Autômatos finitos não determinísticos reconhecem os mesmos idiomas (conjuntos de cadeias) que os DFAs e podem ser transformados em DFAs. Para simular um NFA em uma máquina determinística seqüencial, você normalmente deve explorar um "espaço de pesquisa" em forma de árvore que possa aumentar a complexidade dramaticamente. As linguagens regulares não são muito "complexas" no sentido computacional,

Da mesma forma, é possível observar outros níveis da hierarquia de linguagens de Chomsky - livre de contexto determinístico, livre de contexto (incluindo idiomas livres de contexto não determinísticos, que não podem necessariamente ser reconhecidos por autômatos de empilhamento determinísticos), linguagens sensíveis ao contexto, recursivas e recursivas. idiomas enumeráveis ​​e os idiomas indecidíveis.

Autômatos diferentes diferem principalmente em seu armazenamento externo; ou seja, qual armazenamento externo é necessário para que os autômatos processem corretamente idiomas de um determinado tipo. Autômatos finitos não possuem armazenamento externo; Os PDAs têm uma pilha e as máquinas de Turing têm uma fita. Assim, você pode interpretar a complexidade de um problema de programação específico (que corresponde a uma linguagem) como relacionada à quantidade ou tipo de armazenamento necessário para reconhecê-lo. Se você não precisar de uma quantidade fixa ou fixa de armazenamento para reconhecer todas as seqüências de caracteres em um idioma, é um idioma comum. Se tudo que você precisa é uma pilha, você tem uma linguagem livre de contexto. Etc.

Em geral, eu não ficaria surpreso se as línguas mais altas na hierarquia de Chomsky (portanto, com maior complexidade) também tenderem a ter maior entropia no sentido teórico da informação. Dito isto, você provavelmente poderia encontrar muitos contra-exemplos para essa idéia, e eu não tenho idéia se há algum mérito nisso.

Além disso, isso pode ser melhor solicitado no StackExchange "cs teórico" (cstory).

Patrick87
fonte
Eu migrei e obrigado pela sua sugestão.
mac389
1

A complexidade computacional trata dos recursos necessários: dado um tipo específico de problema, de um determinado tamanho, quais são os recursos necessários (geralmente tempo, espaço ou ambos; e um tipo específico de dispositivo de computação) para resolvê-lo. Os problemas são então agrupados em "classes" de complexidade.

Alguns deles são bastante gerais e abstratos: o problema é solucionável, mesmo em princípio? Requer uma máquina desse tipo ou daquilo? A introdução dessas idéias ainda é um tópico de ciência da computação em nível de pós-graduação, e o material de introdução geralmente faz referência à hierarquia de Chomsky, que mapeia (e lindamente!) Mapeia alguns tipos de máquinas abstratas e alguns tipos abstratos, especificações de linguagem matemática.

Alguns deles, no nível inferior, são mais práticos no uso diário: esse problema é dimensionado como o quadrado do tamanho do problema, ou o cubo, ou alguma outra função? Curiosamente, eu sei que argumentos para a entropia de um determinado problema foram úteis para determinar alguns limites inferiores a alguns problemas computacionais. Um que se destaca em minha mente (embora eu provavelmente não pudesse repeti-lo sem consultar um livro didático) é um argumento baseado em entropia para o número mínimo necessário de comparações durante uma ordenação. A conexão com a entropia é através da teoria da informação.

Então, há algum mérito na ideia, eu acho.

Novak
fonte