terça-feira, 2 de fevereiro de 2010

Data-Processing Inequality

O teorema de processamento de dados mostra que não existe processamento algum que possa ser feito sobre algum dado de forma a melhorar as inferências que possam ser feitas sobre o dado.

teorema: (desigualdade no processamento de dados)
Se X -> Y -> Z, então I(X;Y) >= I(X;Z).

As variáveis aleatórias X, Y e Z formam uma cadeia de Markov nesta ordem (X -> Y -> Z) se a distribuição condicional de Z depende apenas de Y e é condicionalmente independente de X, ou seja, a função de densidade de probabilidade conjunta poderá ser escrita da seguinte forma:

p(x,y,z) = p(x)p(y|x)p(z|y).

Temos uma cadeia de Markov se e somente se X e Z são independentes dado Y. O fato de ser uma cadeia de Markov implica em independencia condicional pois:
p(x,z|y) = p(x,y,z) / p(y)
= p(x,y)p(z|y) / p(y)
= p(x|y)p(z|y).

Para demostrar o teorema de processamento de dados, basta expandir a informação mútua das seguintes formas:
I(X;Y,Z) = I(X;Z) + I(X;Y|Z)
= I(X;Y) + I(X;Z|Y)
Por ser uma cadeia de Markov, X e Z são condicionalmente independentes, dado Y, e assim I(X;Z|Y) = 0. Como I(X;Y|Z) >= 0, temos:
I(X;Y) >= I(X;Z).

A igualdade será apenas quando I(X;Y|Z) = 0 (i.e., quando também for uma cadeia de Markov X -> Z -> Y). De forma similar mostra-se que I(Y;Z) >= I(X;Z).

Se Z = g(Y), X -> Y -> g(Y) forma uma cadeia de Markov, então I(X;Y) >= I(X;g(Y)). Uma função do dado Y não consegue melhorar a informação a cerca de X.

Sendo X o sinal transmitido, como Y o sinal recebido. Não existe processamento que possa ser feito sobre Y de forma a obter mais informação a cerca de X. Qualquer processamento que seja feito sobre Y resultará em um Z cuja a informação mútua com X será igual ou menor à informação mútua de Y com X.

Nenhum comentário:

Postar um comentário