Computação Probabilística

Origem: Wikipédia, a enciclopédia livre.

Este artigo precisa ser wikificado.

Por favor formate este artigo de acordo com as diretrizes estabelecidas no livro de estilo. Remova este aviso somente depois de todo o texto estar wikificado.

Esta página precisa ser reciclada.
Sinta-se livre para editá-la para que esta possa atingir um nível de qualidade superior.

Índice

1 Definição
2 Motivação
3 Programação
4 Modelos
- 4.1 Autômatos Finitos Probabilísticos
  - 4.1.1 No caso do AF
  - 4.1.2 No caso do AF Probabilístico
- 4.2 Máquinas de Turing Probabilísticas
5 Ganhos (Complexidade)
6 Aplicações
7 Links Externos
8 Referências

[editar] Definição

Em linhas gerais, pode-se dizer que a computação probabilística surge quando se adiciona probabilidade (ou randomicidade) nos passos dos modelos computacionais clássicos. Como isso acontece, quais as conseqüências e analisar alguns casos de uso, são algumas das propostas deste artigo.

Para se falar sobre computação como ciência, geralmente se faz necessário o uso de modelos. Para definir melhor o tema deste artigo, precisamos imaginar um primeiro modelo muito simples. Um computador inicia seu trabalho sempre num estado inicial Q0 e, dado uma seqüência de símbolos de entrada (input), esta máquina passará a outros estados. Numa máquina clássica não-probabilística, as transições dependem apenas da seqüência de símbolos, ou seja, dado um estado Qn, a transição deste para um outro estado é sempre a mesma dado o recebimento do mesmo símbolo.

Por fim, na computação probabilística, uma mesma seqüência de entrada não leva sempre a um mesmo estado final de computação. Isso acontece porque as transições entre estados dependem além do estado atual e do símbolo recebido, também de uma escolha randômica. Imagine, num caso simplificado que, além de ler um símbolo para decidir o próximo passo de computação, a máquina ainda "lance uma moeda" para decidir se passa ou não ao próximo estado.

Esta máquina pode parecer inicialmente muito ilógica, mas tentaremos deixar claro aqui os ganhos do seu uso em alguns casos muito importantes.

[editar] Motivação

O estudo de Algoritmos Computacionais, geralmente busca soluções baseadas nos resultados do pior caso. Isso significa que uma solução é classificada, dado o seu desempenho na execução de uma tarefa no seu pior caso. Mas em vários outros problemas, o estudo do desempenho no caso médio já é o suficiente. Ou seja, quando um algoritmo geralmente resolve um problema melhor que qualquer outro. Estas soluções podem até mesmo ter uma probabilidade pequena de dar respostas erradas. A computação probabilística pode ajudar bastante nestes casos.

Para ilustrar esta motivação vejamos um exemplo de busca. Dado um array de tamanho n preenchido metade com a's e metade com b's. O problema consiste em encontrar um a dentro do mesmo. A forma mais obvia de executar tal busca é checar cada uma das posições do array. Usando este algoritmo checaremos, no pior caso da entrada (ordenação do array), n/2 posições. A verdade é que nenhum algoritmo determinístico termina esta tarefa mais rápido que isso para todos os casos de entrada.

Neste mesmo problema, pode-se fazer uso de um algoritmo probabilístico muito simples para melhorar este resultado. Caso pesquisemos randomicamente as posições do array, teremos uma alta probabilidade de encontrar rapidamente o valor desejado para qualquer que seja a entrada. Resta apenas uma pequena probabilidade de que a randomicidade demore para terminar a busca, mas isso independe da entrada.

[editar] Programação

Nesta seção iremos aprender um pouco mais sobre a construção de programas probabilísticos. Aqui, faremos um estudo da randomicidade, uma ferramenta de fundamental importância para a computação e mais especificamente, para os algoritmos probabilísticos(APs).

Uma máquina probabilística pode ser vista como uma particularidade das máquinas não determinísticas. O não-determinismo implica que a máquina pode seguir vários caminhos dados o par: estado Sn e símbolo de entrada X. A diferença deste modelo para o da máquina probabilística(MP) é que este último escolhe randomicamente o caminho a seguir, enquanto aquele, ao menos teoricamente, busca o melhor caminho dentro de todas as possibilidades.

Para a implementação de APs uma importante definição é a da instrução de atribuição randômica: x := random(S). Esta instrução diz respeito a escolha aleatória de um elemento do conjunto S para a atribuição da variável x.

[editar] Modelos

[editar] Autômatos Finitos Probabilísticos

Não existe apenas uma representação para a teoria de Autômato Finito(AF). Uma delas apresenta um modelo baseado em matrizes que é particularmente interessante, neste caso, pois a evolução da representação de AFs para AFPs é muito clara. Seguem as 3 principais características:

Para cada símbolo x do alfabeto existe uma matriz de transição Mx que expressa as probabilidades(/possibilidades) de transição entre estados dado a leitura do símbolo x;

Os estados são representados através de vetores coluna;

Pode-se calcular a aceitabilidade de uma palavra xyz com a seguinte fórmula: $P_{(xyz)} = q_{inicial}^T \cdot M_x \cdot M_y \cdot M_z \cdot q_{final}$ .

Uma questão que deve estar bem clara aqui, é que os AFs tornam-se um caso particular dos AFPs para transições com probabilidade 0 (para transição não possível) ou 1 (para transição possível), ou seja, a decisão é executada com 100% de certeza. Vejamos um exemplo:

[editar] No caso do AF

Um autômato que reconhece as palavras binárias com o formato 00*11*00* pode ser escrito assim:

Os estados: $q_0 = q_{inicial} = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} ; q_1 = \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix} ; q_2 = \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix} ; q_3 = q_{final} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}$

As matrizes de transição: $M_0 = \begin{bmatrix} 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 1\\ \end{bmatrix} ; M_1 = \begin{bmatrix} 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0\\ \end{bmatrix}$

Um exemplo de aceitação e rejeição:

ACEITAÇÃO:

$P_{(010)} = \begin{pmatrix}1 & 0 & 0 & 0\end{pmatrix} \cdot M_0M_1M_0 \cdot \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = \begin{pmatrix}0 & 1 & 0 & 0\end{pmatrix} \cdot M_1M_0 \cdot \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = \begin{pmatrix}0 & 0 & 1 & 0\end{pmatrix} \cdot M_0 \cdot \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = \begin{pmatrix}0 & 0 & 0 & 1\end{pmatrix} \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = 1$

REJEIÇÃO:

$P_{(10)} = \begin{pmatrix}1 & 0 & 0 & 0\end{pmatrix} \cdot M_1M_0 \cdot \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = \begin{pmatrix}0 & 0 & 0 & 0\end{pmatrix} \cdot M_0 \cdot \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = \begin{pmatrix}0 & 0 & 0 & 0\end{pmatrix} \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = 0$

[editar] No caso do AF Probabilístico

O mesmo modelo acima pode ser modificado para um AFP mudando apenas as matrizes de possibilidades para que seja de probabilidades. Com isso queremos dizer que, ao invés de receber apenas os valores 0 e 1, podem existir valores no intervalo [0,1] desde que as linhas somem sempre 1, ou seja, as probabilidades de execução em um dado estado e recebido um símbolo é sempre 1.

Podemos modificar as matrizes de transição da seguinte forma:

$M_0 = \begin{bmatrix} 0.2 & 0.8 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0.1 & 0.9\\ 0 & 0 & 0 & 1\\ \end{bmatrix} ; M_1 = \begin{bmatrix} 0 & 0 & 0 & 0\\ 0 & 0.15 & 0.85 & 0\\ 0 & 0 & 0.95 & 0.05\\ 0 & 0 & 0 & 0\\ \end{bmatrix}$

Os exemplo de aceitação e rejeição passam a não ser mais exatos, mas sim, a retornar uma probabilidade de aceitação:

PROBABILIDADE DE ACEITAÇÃO:

$P_{(010)} = \begin{pmatrix}1 & 0 & 0 & 0\end{pmatrix} \cdot M_0 M_1 M_0 \cdot \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = \begin{pmatrix}0.2 & 0.8 & 0 & 0\end{pmatrix} \cdot M_1 M_0 \cdot \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = \begin{pmatrix}0 & 0.12 & 0.68 & 0\end{pmatrix} \cdot M_0 \cdot \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = \begin{pmatrix}0 & 0.12 & 0.068 & 0.612\end{pmatrix} \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = 0.612$

PROBABILIDADE DE ACEITAÇÃO:

E agora passamos a ter uma possibilidade de erro na aceitação da linguagem inicialmente descrita 00*11*00*: ......

[editar] Máquinas de Turing Probabilísticas

Uma Máquina de Turing Probabilística (MTP) M é um tipo de Máquina de Turing não-determinística que possui passos de transição chamados de lançamento-de-moeda (plm) dando a máquina duas possibilidades a cada transição.

Se na computação de uma entrada w é gerado o caminho de execução (branch) b, e neste, foram dados k plm's, então a probabilidade do caminho é dada por: $P [b] = 2 - k$ . Já a probabilidade de aceitação da entrada w é dada por: $P[M aceita w] = \sum P[b]$ , ou seja, a soma de todos os caminhos de execução que aceitam a palavra w. Complementariamente temos que: $P [M r e j e i t a w] = 1 - P [M a c e i t a w]$ .

A máquina M continua reconhecendo linguagens apenas quando aceita todas as palavras da mesma e rejeita no caso contrario. Mas a uma MTP é permitido uma pequena probabilidade de erro: $0 \le \epsilon < \frac{1}{2}$ . Desta forma, diz-se que M reconhece uma uma linguagem A com probabilidade de erro $ε$ se:

$w \in A \to P[M aceita w] \ge 1 - \epsilon$ , e
$w \notin A \to P[M rejeita w] \ge 1 - \epsilon$

[editar] Ganhos (Complexidade)

BPP: a classe das linguagens que são reconhecidas por uma MTP (em tempo polinomial) com um erro entre 0 e 1/2. Este erro pode ser diminuído exponencialmente fazendo a utilização do Lema da aplicaficação. Este lema diz que para toda MTP (em tempo polinomial = polin(n)) M1 que opera com erro ε, existe uma máquina equivalente M2 que opera com uma probabilidade de erro de 2 ^{− polin(n)}. Isto pode ser provado dado que M2 pode simular a máquina M1, executá-la um número polinomial de vezes e fazer uma escolha majoritária entre as respostas computadas.
- Existe um algoritmo probabilístico para teste de primalidade pertencente a BPP.

RP: a classe das linguagens que são reconhecidas por uma MTP (em tempo polinomial) onde as entradas pertencentes a linguagem são aceitas com probabilidade de no mínimo 1/2 e entradas não pertencentes a linguagem são rejeitadas com probabilidade 1. Este tipo de erro, denominado erro de um único lado (one-sided error) é muito comum nos algoritmos probabilísticos. Nesta classe também é possível a redução exponencial do erro cometido.

ZPP: engloba os problemas que possuem algoritmos que resolvem em tempo polinomial (no caso médio) e dão sempre uma resposta correta, mesmo que possam não parar em alguns casos.

[editar] Aplicações

Sistemas
- Redes Neurais
- Algoritmos Genéticos

Problemas
- Aprendizagem Computacional
  - Em inglês: [[1]]
- Reconhecimento de Padrões
  - Em inglês: [[2]]

[editar] Links Externos

[editar] Referências

Machine, Logic and Quantum Physics - Por David Deutsch & Artur Ekert. Apesar de ultrapassar em muito o escopo deste artigo, algumas idéias discutidas foram retiradas deste paper escrito por estes dois grandes nomes da Computação Quântica.

An Introduction to the Theory of Computation - Por Eitan Gurari. Este é um tutorial bastante amplo à Teoria da Computação onde a seção mais utilizada foi a de computação probabilística.

Introduction to the Theory of Computation - Por Michael Sipser. Livro texto adotado em grande parte dos cursos de teoria da computação.

[3] - Página correlata na WIKIPEDIA em inglês.

Retirado de "http://pt.wikipedia.org../../../c/o/m/Computa%C3%A7%C3%A3o_Probabil%C3%ADstica_8a0e.html"

Categorias: !Artigos precisando de ligações internas | !Páginas a reciclar | Teoria da computação | Ciência da computação