Entropia (teoria da informação)

AjustarCompartirImprimirCitar

Quantidade esperada de informações necessárias para especificar a saída de uma fonte de dados estocástico

Na teoria da informação, o - Sim. de uma variável aleatória é o nível médio de "informação", "surpresa", ou "incerteza" inerente aos resultados possíveis da variável. Dada uma variável aleatória discreta $X$ , que leva valores no alfabeto ${mathcal {X}}$ e é distribuído de acordo com ${displaystyle p:{mathcal {X}}to [0,1]}$ :

{displaystyle mathrm {H} (X):=-sum _{xin {mathcal {X}}}p(x)log p(x)=mathbb {E} [-log p(X)],}

Sigma

log

Dois bits de entropia: No caso de dois tosses de moeda justa, a entropia de informações em bits é o logaritmo base-2 do número de resultados possíveis; com duas moedas existem quatro resultados possíveis, e dois bits de entropia. Geralmente, a entropia da informação é a quantidade média de informações transmitidas por um evento, ao considerar todos os resultados possíveis.

O conceito de entropia de informação foi introduzido por Claude Shannon em seu artigo de 1948 "A Mathematical Theory of Communication", e também é conhecido como entropia de Shannon. A teoria de Shannon define um sistema de comunicação de dados composto por três elementos: uma fonte de dados, um canal de comunicação e um receptor. O "problema fundamental da comunicação" – como expressa Shannon – é para que o receptor consiga identificar quais dados foram gerados pela fonte, a partir do sinal que recebe pelo canal. Shannon considerou várias maneiras de codificar, compactar e transmitir mensagens de uma fonte de dados e provou em seu famoso teorema de codificação de fonte que a entropia representa um limite matemático absoluto sobre o quão bem os dados da fonte podem ser compactados sem perdas em um canal perfeitamente silencioso. Shannon reforçou consideravelmente esse resultado para canais ruidosos em seu teorema de codificação de canal ruidoso.

A entropia na teoria da informação é diretamente análoga à entropia na termodinâmica estatística. A analogia resulta quando os valores da variável aleatória designam energias de microestados, então a fórmula de Gibbs para a entropia é formalmente idêntica à fórmula de Shannon. A entropia tem relevância para outras áreas da matemática, como combinatória e aprendizado de máquina. A definição pode ser derivada de um conjunto de axiomas estabelecendo que a entropia deve ser uma medida de quão informativo é o resultado médio de uma variável. Para uma variável aleatória contínua, a entropia diferencial é análoga à entropia.

Introdução

A ideia central da teoria da informação é que o "valor informacional" de uma mensagem comunicada depende do grau em que o conteúdo da mensagem é surpreendente. Se ocorrer um evento altamente provável, a mensagem carrega muito pouca informação. Por outro lado, se ocorrer um evento altamente improvável, a mensagem é muito mais informativa. Por exemplo, o conhecimento de que um determinado número não será o número vencedor de uma loteria fornece muito pouca informação, porque qualquer número específico escolhido quase certamente não ganhará. No entanto, o conhecimento de que um determinado número irá ganhar na loteria tem alto valor informativo porque comunica o resultado de um evento de probabilidade muito baixa.

O conteúdo da informação, também chamado de em geral ou auto-informação, de um evento $E$ é uma função que aumenta à medida que a probabilidade ${displaystyle p(E)}$ de um evento diminui. Quando ${displaystyle p(E)}$ está perto de 1, o surprisal do evento é baixo, mas se ${displaystyle p(E)}$ está perto de 0, o surprisal do evento é alto. Esta relação é descrita pela função

{displaystyle log left({frac {1}{p(E)}}right),}

log

log

Assim, podemos definir a informação, ou surprisal, de um evento $E$ por

{displaystyle I(E)=-log _{2}(p(E)),}

{displaystyle I(E)=log _{2}left({frac {1}{p(E)}}right).}

A entropia mede a quantidade esperada (ou seja, média) de informação transmitida pela identificação do resultado de um julgamento aleatório. Isso implica que a fundição de uma matriz tem maior entropia do que lançar uma moeda porque cada resultado de um murro tem menor probabilidade (sobre ${displaystyle p=1/6}$ ) do que cada resultado de um toss de moeda ( $p=1/2$ ).

Considere uma moeda com probabilidade $p$ desembarque em cabeças e probabilidade $1 - p$ de pousar em caudas. A surpresa máxima é quando $p = 1/2$ , para o qual um resultado não é esperado sobre o outro. Neste caso um flip de moeda tem uma entropia de um pouco. (Similarly, uma trit com valores equiprobable contém $log _{2}3$ (cerca de 1.58496) bits de informação porque pode ter um dos três valores.) A surpresa mínima é quando $p = 0$ ou $p = 1$ , quando o resultado do evento é conhecido antes do tempo, e a entropia é zero bits. Quando a entropia é zero bits, isso é às vezes referido como unidade, onde não há nenhuma incerteza - nenhuma liberdade de escolha - nenhuma informação. Outros valores de p dar entropias entre zero e um bits.

A teoria da informação é útil para calcular a menor quantidade de informação necessária para transmitir uma mensagem, como na compressão de dados. Por exemplo, considere a transmissão de sequências compostas pelos 4 caracteres 'A', 'B', 'C' e 'D' através de um canal binário. Se todas as 4 letras forem igualmente prováveis (25%), não se pode fazer melhor do que usar dois bits para codificar cada letra. 'A' pode codificar como '00', 'B' como '01', 'C' como '10', e 'D' como '11'. No entanto, se as probabilidades de cada letra forem desiguais, diga 'A' ocorre com 70% de probabilidade, 'B' com 26%, e 'C' e 'D' com 2% cada, pode-se atribuir códigos de comprimento variável. Neste caso, 'A' seria codificado como '0', 'B' como '10', 'C' como '110', e D como '111'. Com esta representação, 70% das vezes apenas um bit precisa ser enviado, 26% das vezes dois bits e apenas 4% das vezes 3 bits. Em média, menos de 2 bits são necessários, pois a entropia é menor (devido à alta prevalência de 'A' seguido de 'B' – juntos 96% dos caracteres). O cálculo da soma das probabilidades de log ponderadas pela probabilidade mede e captura esse efeito. O texto em inglês, tratado como uma sequência de caracteres, tem entropia bastante baixa, ou seja, é bastante previsível. Podemos estar bastante certos de que, por exemplo, 'e' será muito mais comum do que 'z', que a combinação 'qu' será muito mais comum do que qualquer outra combinação com um 'q' nele, e que a combinação 'th' será mais comum do que 'z', 'q' ou 'qu'. Após as primeiras letras, muitas vezes é possível adivinhar o restante da palavra. O texto em inglês tem entre 0,6 e 1,3 bits de entropia por caractere da mensagem.

Definição

Nomeado após o teorema de Boltzmann, Shannon definiu a entropia $Olá.$ (Carta de capital grega eta) de uma variável aleatória discreta ${textstyle X}$ , que leva valores no alfabeto ${mathcal {X}}$ e é distribuído de acordo com ${displaystyle p:{mathcal {X}}to [0,1]}$ tal que ${displaystyle p(x):=mathbb {P} [X=x]}$ :

{displaystyle mathrm {H} (X)=mathbb {E} [operatorname {I} (X)]=mathbb {E} [-log p(X)].}

Aqui. $mathbb {E}$ é o operador de valor esperado, e $Eu...$ é o conteúdo da informação $X$ . ${displaystyle operatorname {I} (X)}$ é em si uma variável aleatória.

A entropia pode ser explicitamente escrita como:

{displaystyle mathrm {H} (X)=-sum _{xin {mathcal {X}}}p(x)log _{b}p(x),}

b)

b)

b) = 2

b) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = e

b) = 10

No caso de $p(x) = 0$ para alguns $xin {mathcal {X}}$ , o valor da soma correspondente $0 registo b) (0)$ é levado a ser $0$ , que é consistente com o limite:

{displaystyle lim _{pto 0^{+}}plog(p)=0.}

Pode-se também definir a entropia condicional de duas variáveis $X$ e $Y$ tomando valores de conjuntos ${mathcal {X}}$ e ${mathcal {Y}}$ respectivamente, como:

{displaystyle mathrm {H} (X|Y)=-sum _{x,yin {mathcal {X}}times {mathcal {Y}}}p_{X,Y}(x,y)log {frac {p_{X,Y}(x,y)}{p_{Y}(y)}},}

{displaystyle p_{X,Y}(x,y):=mathbb {P} [X=x,Y=y]}

{displaystyle p_{Y}(y)=mathbb {P} [Y=y]}

X

Y

Medir a teoria

A entropia pode ser formalmente definida na linguagem da teoria da medida da seguinte forma: Vamos. ${displaystyle (X,Sigmamu)}$ ser um espaço de probabilidade. Vamos. $A in Sigma$ ser um evento. O surprisal de $A$ o

{displaystyle sigma _{mu }(A)=-ln mu (A).}

O esperado surprisal de $A$ o

{displaystyle h_{mu }(A)=mu (A)sigma _{mu }(A).}

A $mu$ -quase partição é um conjunto de família ${displaystyle Psubseteq {mathcal {P}}(X)}$ tal que ${displaystyle mu (mathop {cup } P)=1}$ e ${displaystyle mu (Acap B)=0}$ para todos os distintos ${displaystyle A,Bin P}$ . (Este é um relaxamento das condições habituais para uma partição.) A entropia de $P$ o

{displaystyle mathrm {H} _{mu }(P)=sum _{Ain P}h_{mu }(A).}

Vamos. $M$ ser um sigma-algebra em $X$ . A entropia de $M$ o

{displaystyle mathrm {H} _{mu }(M)=sup _{Psubseteq M}mathrm {H} _{mu }(P).}

{displaystyle mathrm {H} _{mu }(Sigma)}

mu

Todos

X

Definição de Ellerman

David Ellerman queria explicar por que a entropia condicional e outras funções tinham propriedades semelhantes às funções na teoria da probabilidade. Ele afirma que as definições anteriores baseadas na teoria da medida só funcionavam com potências de 2.

Ellerman criou uma "lógica de partições" que é o dual de subconjuntos de um conjunto universal. As informações são quantificadas como "dits" (distinções), uma medida em partições. "Dits" podem ser convertidos em bits de Shannon, para obter as fórmulas de entropia condicional, etc.

Exemplo

Entropia

H... X)

(ou seja, o surprisal esperado) de um flip de moeda, medido em pedaços, gravado versus o viés da moeda

Pr(X = 1)

, onde

X = 1

representa um resultado de cabeças.

Aqui, a entropia é no máximo 1 bit, e para comunicar o resultado de um flip de moeda (2 valores possíveis) exigirá uma média de no máximo 1 bit (exatamente 1 bit para uma moeda justa). O resultado de uma morte justa (6 valores possíveis) teria log entropy₂6 bits.

Considere lançar uma moeda com probabilidades conhecidas, não necessariamente justas, de dar cara ou coroa; isso pode ser modelado como um processo de Bernoulli.

A entropia do resultado desconhecido do próximo lançamento da moeda é maximizada se a moeda for honesta (isto é, se cara e coroa tiverem probabilidade igual de 1/2). Esta é a situação de máxima incerteza, pois é mais difícil prever o resultado do próximo lançamento; o resultado de cada lançamento da moeda fornece um bit completo de informação. Isto é porque

{displaystyle {begin{aligned}mathrm {H} (X)&=-sum _{i=1}^{n}{p(x_{i})log _{b}p(x_{i})}\&=-sum _{i=1}^{2}{{frac {1}{2}}log _{2}{frac {1}{2}}}\&=-sum _{i=1}^{2}{{frac {1}{2}}cdot (-1)}=1end{aligned}}}

No entanto, se sabemos que a moeda não é honesta, mas dá cara ou coroa com probabilidades $p$ e $q$ , onde $p \neq q$ , então há menos incerteza. Cada vez que é lançado, é mais provável que um lado apareça do que o outro. A incerteza reduzida é quantificada em uma entropia mais baixa: em média, cada lançamento da moeda fornece menos de um bit completo de informação. Por exemplo, se $p$ = 0,7, então

<math alttext="{displaystyle {begin{aligned}mathrm {H} (X)&=-plog _{2}(p)-qlog _{2}(q)\&=-0.7log _{2}(0.7)-0.3log _{2}(0.3)\&approx -0.7cdot (-0.515)-0.3cdot (-1.737)\&=0.8816H. H. H.(X)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =- Sim. - Sim. plog2⁡ ⁡ (p)- Sim. - Sim. qlog2⁡ ⁡ (q)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =- Sim. - Sim. 0log2⁡ ⁡ (0)- Sim. - Sim. 0log2⁡ ⁡ (0)? ? - Sim. - Sim. 0)) (- Sim. - Sim. 0,515)- Sim. - Sim. 0)) (- Sim. - Sim. 1.737)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0,816<1{displaystyle {begin{aligned}mathrm {H} (X)&=-plog _{2}(p)-qlog _{2}(q)&=-0.7log _{2}(0.7)-0.3log _{2}(0.3)&approx -0.7cdot (-0.515)-0.3cdot (-1.737)&=0.88ign1al}<img alt="{displaystyle {begin{aligned}mathrm {H} (X)&=-plog _{2}(p)-qlog _{2}(q)\&=-0.7log _{2}(0.7)-0.3log _{2}(0.3)\&approx -0.7cdot (-0.515)-0.3cdot (-1.737)\&=0.8816

Probabilidade uniforme produz incerteza máxima e, portanto, entropia máxima. A entropia, então, só pode diminuir do valor associado à probabilidade uniforme. O caso extremo é o de uma moeda de duas caras que nunca dá coroa, ou uma moeda de duas caras que nunca dá cara. Então não há incerteza. A entropia é zero: cada lançamento da moeda não fornece nenhuma informação nova, pois o resultado de cada lançamento da moeda é sempre certo.

A entropia pode ser normalizada dividindo-a pelo comprimento da informação. Essa razão é chamada de entropia métrica e é uma medida da aleatoriedade da informação.

Caracterização

Para entender o significado de $-Σ p i log(p i)$ , primeiro defina uma função de informação $I$ em termos de um evento $i$ com probabilidade $p i . A quantidade de informação adquirida devido à observação do evento i segue da solução de Shannon das propriedades fundamentais da informação:$

$Eu... p)$ está diminuindo monotonicamente $p$ : um aumento na probabilidade de um evento diminui a informação de um evento observado, e vice-versa.
$I(1) = 0$ : eventos que ocorrem sempre não comunicam informações.
$Eu... p 1 \cdot p 2) = I(p 1) + I(p 2)$ : a informação aprendida com eventos independentes é a soma das informações aprendidas de cada evento.

Dados dois eventos independentes, se o primeiro evento pode produzir um dos $n$ resultados equiprováveis e outro tem um dos $m$ resultados equiprováveis, então existem $mn$ resultados equiprováveis do evento conjunto. Isso significa que se forem necessários $log 2 (n)$ bits para codificar o primeiro valor e $log 2 (m)$ para codificar o segundo, é necessário $log 2 (mn) = log 2 (m) + log 2 (n)$ para codificar ambos.

Shannon descobriu que uma escolha adequada de ${displaystyle operatorname {I} }$ é dado por:

{displaystyle operatorname {I} (p)=log left({tfrac {1}{p}}right)=-log(p)}

De fato, os únicos valores possíveis de ${displaystyle operatorname {I} }$ são ${displaystyle operatorname {I} (u)=klog u}$ para $<math alttext="{displaystyle kk<0- Sim. <img alt="k$ . Além disso, escolher um valor para $k$ é equivalente a escolher um valor $1}" xmlns="http://www.w3.org/1998/Math/MathML">x>1- Sim. 1" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0549e1fb7ee2023519833093c6e3b60236e7d09f" style="vertical-align: -0.338ex; width:5.591ex; height:2.176ex;"/>$ para ${displaystyle k=-1/log x}$ , para que $x$ corresponde à base do logaritmo. Assim, a entropia é caracterizada pelas quatro propriedades acima.

Prova

Vamos.

{textstyle operatorname {I} }

ser a função de informação que se assume ser duas vezes continuamente diferenciável, um tem:

{displaystyle {begin{aligned}&operatorname {I} (p_{1}p_{2})&= &operatorname {I} (p_{1})+operatorname {I} (p_{2})&&quad {text{Starting from property 3}}\&p_{2}operatorname {I} '(p_{1}p_{2})&= &operatorname {I} '(p_{1})&&quad {text{taking the derivative w.r.t}} p_{1}\&operatorname {I} '(p_{1}p_{2})+p_{1}p_{2}operatorname {I} ''(p_{1}p_{2})&= &0&&quad {text{taking the derivative w.r.t}} p_{2}\&operatorname {I} '(u)+uoperatorname {I} ''(u)&= &0&&quad {text{introducing}},u=p_{1}p_{2}\&(umapsto uoperatorname {I} '(u))'&= &0end{aligned}}}

Esta equação diferencial leva à solução ${displaystyle operatorname {I} (u)=klog u+c}$ para alguns ${displaystyle k,cin mathbb {R} }$ . Propriedade 2 dá $c=0$ . Propriedade 1 e 2 dão isso ${displaystyle operatorname {I} (p)geq 0}$ para todos ${displaystyle pin [0,1]}$ , para que $<math alttext="{displaystyle kk<0- Sim. <img alt="k$ .

As diferentes unidades de informação (bits para o logaritmo binário $log 2$ , nats para o logaritmo natural $ln$ , proibições para o logaritmo decimal $log 10$ e assim por diante) são múltiplos constantes um do outro. Por exemplo, no caso de um sorteio justo, cara fornece $log 2 (2) = 1$ bit de informação, que é aproximadamente 0,693 nats ou 0,301 dígitos decimais. Por causa da aditividade, $n$ lançamentos fornecem $n$ bits de informação, que é aproximadamente $0,693 n$ nats ou $0,301 n$ dígitos decimais.

O significado dos eventos observados (o significado das mensagens) não importa na definição de entropia. A entropia leva em consideração apenas a probabilidade de observar um evento específico, portanto, a informação que ela encapsula é a informação sobre a distribuição de probabilidade subjacente, não o significado dos próprios eventos.

Caracterização alternativa

Outra caracterização da entropia usa as seguintes propriedades. Denotamos $p i = Pr(X = x i)$ e $Η n (p 1,..., p n) = Η(X)$ .

Continuidade: $H. H. H.$ deve ser contínuo, de modo que a mudança dos valores das probabilidades por uma quantidade muito pequena só deve mudar a entropia por uma pequena quantidade.
Simetria: $H. H. H.$ deve ser inalterado se os resultados $x Eu...$ são re-ordenados. Isso é, ${displaystyle mathrm {H} _{n}left(p_{1},p_{2},ldots p_{n}right)=mathrm {H} _{n}left(p_{i_{1}},p_{i_{2}},ldotsp_{i_{n}}right)}$ para qualquer permutação ${displaystyle {i_{1},...,i_{n}}}$ de ${1,...,n}$ .
Máximo: ${displaystyle mathrm {H} _{n}}$ deve ser máxima se todos os resultados são igualmente prováveis, ou seja,. ${displaystyle mathrm {H} _{n}(p_{1},ldotsp_{n})leq mathrm {H} _{n}left({frac {1}{n}},ldots{frac {1}{n}}right)}$ .
Aumento do número de resultados: para eventos equiprobable, a entropia deve aumentar com o número de resultados, ou seja,. $<math alttext="{displaystyle mathrm {H} _{n}{bigg (}underbrace {{frac {1}{n}},ldots{frac {1}{n}}} _{n}{bigg)}H. H. H.n(1n,...... ,1n? ? n)<H. H. H.n+1(1n+1,...... ,1n+1? ? n+1).{displaystyle mathrm {H} _{n}{bigg (}underbrace {{frac {1}{n}},ldots{frac {1}{n}}} _{n}{bigg)}<mathrm {H} _{n+1}{bigg (}underbrace {{frac {1}{n+1}},ldots{frac {1}{n+1}}} _{n+1}{bigg)}<img alt="{displaystyle mathrm {H} _{n}{bigg (}underbrace {{frac {1}{n}},ldots{frac {1}{n}}} _{n}{bigg)}$
Aditividade: dado um conjunto de $n$ elementos uniformemente distribuídos que são divididos em $k$ caixas (subsistemas) com $b) 1, b) k$ elementos cada, a entropia de todo o conjunto deve ser igual à soma da entropia do sistema de caixas e as entropias individuais das caixas, cada um ponderado com a probabilidade de estar nessa caixa particular.

A regra da aditividade tem as seguintes consequências: para inteiros positivos $b i$ onde $b 1 +... + b k = n$ ,

mathrm {H} _{n}left({frac {1}{n}},ldots{frac {1}{n}}right)=mathrm {H} _{k}left({frac {b_{1}}{n}},ldots{frac {b_{k}}{n}}right)+sum _{i=1}^{k}{frac {b_{i}}{n}},mathrm {H} _{b_{i}}left({frac {1}{b_{i}}},ldots{frac {1}{b_{i}}}right).

Escolhendo $k = n$ , $b 1 =... = b n = 1$ isso implica que a entropia de um certo resultado é zero: $Η 1 (1) = 0$ . Isso implica que a eficiência de um alfabeto de origem com símbolos $n$ pode ser definida simplesmente como sendo igual ao seu $n$ entropia-ária. Veja também Redundância (teoria da informação).

Caracterização alternativa via aditividade e subaditividade

Outra caracterização axiomática sucinta da entropia de Shannon foi dada por Aczél, Forte e Ng, através das seguintes propriedades:

Subaditividade: ${displaystyle mathrm {H} (X,Y)leq mathrm {H} (X)+mathrm {H} (Y)}$ para variáveis aleatórias distribuídas em conjunto $X,Y$ .
Aditividade: ${displaystyle mathrm {H} (X,Y)=mathrm {H} (X)+mathrm {H} (Y)}$ quando as variáveis aleatórias $X,Y$ são independentes.
Expansibilidade: ${displaystyle mathrm {H} _{n+1}(p_{1},ldotsp_{n},0)=mathrm {H} _{n}(p_{1},ldotsp_{n})}$ , ou seja, adicionar um resultado com probabilidade zero não muda a entropia.
Simetria: ${displaystyle mathrm {H} _{n}(p_{1},ldotsp_{n})}$ é invariante sob permutação de $p_1, ldots, p_n$ .
Pequeno para pequenas probabilidades: ${displaystyle lim _{qto 0^{+}}mathrm {H} _{2}(1-q,q)=0}$ .

Foi mostrado que qualquer função $mathrm{H}$ satisfazer as propriedades acima deve ser um múltiplo constante da entropia de Shannon, com uma constante não negativa. Em comparação com as caracterizações anteriormente mencionadas de entropia, esta caracterização se concentra nas propriedades da entropia como uma função de variáveis aleatórias (subadditivity e aditividade), em vez das propriedades da entropia como uma função do vetor de probabilidade ${displaystyle p_{1},ldotsp_{n}}$ .

Vale a pena notar que se deixarmos cair a propriedade "pequena para pequenas probabilidades", então $mathrm{H}$ deve ser uma combinação linear não negativa da entropia de Shannon e da entropia Hartley.

Outras propriedades

A entropia de Shannon satisfaz as seguintes propriedades, para algumas das quais é útil interpretar a entropia como a quantidade esperada de informação aprendida (ou incerteza eliminada) revelando o valor de uma variável aleatória $X$ :

Adicionar ou remover um evento com probabilidade zero não contribui para a entropia:

mathrm {H} _{n+1}(p_{1},ldotsp_{n},0)=mathrm {H} _{n}(p_{1},ldotsp_{n})

Pode ser confirmado usando a desigualdade Jensen e, em seguida, a desigualdade de Sedrakyan que

{displaystyle mathrm {H} (X)=mathbb {E} [-log _{b}p(X)]leq -log _{b}left(mathbb {E} [p(X)]right)leq log _{b}n}

Esta entropia máxima de

log b) (n)

é efetivamente atingido por um alfabeto fonte com uma distribuição de probabilidade uniforme: a incerteza é máxima quando todos os eventos possíveis são equiprobable.

A entropia ou a quantidade de informação revelada pela avaliação $(X, Y)$ (isto é, avaliar $X$ e $Y$ simultaneamente) é igual às informações reveladas através da realização de dois experimentos consecutivos: primeiro avaliar o valor de $Y$ , então revelando o valor de $X$ dado que você sabe o valor de $Y$ . Isto pode ser escrito como:

mathrm {H} (X,Y)=mathrm {H} (X|Y)+mathrm {H} (Y)=mathrm {H} (Y|X)+mathrm {H} (X).

Se $Y=f(X)$ Onde? $f$ é uma função, então ${displaystyle mathrm {H} (f(X)|X)=0}$ . Aplicando a fórmula anterior para ${displaystyle mathrm {H} (X,f(X))}$ produção

mathrm {H} (X)+mathrm {H} (f(X)|X)=mathrm {H} (f(X))+mathrm {H} (X|f(X)),

Então...

{displaystyle mathrm {H} (f(X))leq mathrm {H} (X)}

, a entropia de uma variável só pode diminuir quando a última é passada através de uma função.

Se $X$ e $Y$ são duas variáveis aleatórias independentes, então sabendo o valor de $Y$ não influencia nosso conhecimento do valor de $X$ (uma vez que os dois não influenciam um ao outro pela independência):

mathrm {H} (X|Y)=mathrm {H} (X).

Mais geralmente, para qualquer variável aleatória $X$ e $Y$ nós temos

{displaystyle mathrm {H} (X|Y)leq mathrm {H} (X)}

A entropia de dois eventos simultâneos não é mais do que a soma das entropias de cada evento individual ou seja, ${displaystyle mathrm {H} (X,Y)leq mathrm {H} (X)+mathrm {H} (Y)}$ , com igualdade se e somente se os dois eventos são independentes.
A entropia ${displaystyle mathrm {H} (p)}$ é côncavo na função de massa de probabilidade $p$ , i.e.

{displaystyle mathrm {H} (lambda p_{1}+(1-lambda)p_{2})geq lambda mathrm {H} (p_{1})+(1-lambda)mathrm {H} (p_{2})}

para todas as funções de massa de probabilidade

{displaystyle p_{1},p_{2}}

{displaystyle 0leq lambda leq 1}

Assim, a função de entropia negativa (negentropy) é convexa, e sua conjugação convexa é LogSumExp.

Aspectos

Relação com a entropia termodinâmica

A inspiração para adotar a palavra entropia na teoria da informação veio da estreita semelhança entre a fórmula de Shannon e fórmulas conhecidas muito semelhantes da mecânica estatística.

Em termodinâmica estatística, a fórmula mais geral para a entropia termodinâmica $S$ de um sistema termodinâmico é a entropia de Gibbs,

{displaystyle S=-k_{text{B}}sum p_{i}ln p_{i},}

onde $k B$ é a constante de Boltzmann e $p i$ é a probabilidade de um microestado. A entropia de Gibbs foi definida por J. Willard Gibbs em 1878 após o trabalho anterior de Boltzmann (1872).

A entropia de Gibbs se traduz quase inalterada no mundo da física quântica para dar a entropia de von Neumann, introduzida por John von Neumann em 1927,

{displaystyle S=-k_{text{B}},{rm {Tr}}(rho ln rho),}

onde ρ é a matriz de densidade do sistema mecânico quântico e Tr é o traço.

A nível prático quotidiano, as ligações entre a entropia da informação e a entropia termodinâmica não são evidentes. Físicos e químicos tendem a se interessar mais por mudanças na entropia à medida que um sistema evolui espontaneamente para longe de suas condições iniciais, de acordo com a segunda lei da termodinâmica, em vez de uma distribuição de probabilidade imutável. Como a pequenez da constante de Boltzmann $k B$ indica, as mudanças em $S / k B$ mesmo para pequenas quantidades de substâncias em processos químicos e físicos representam quantidades de entropia que são extremamente grandes em comparação com qualquer coisa em compressão de dados ou processamento de sinal. Na termodinâmica clássica, a entropia é definida em termos de medições macroscópicas e não faz referência a qualquer distribuição de probabilidade, que é central para a definição de entropia de informação.

A conexão entre a termodinâmica e o que hoje é conhecido como teoria da informação foi feita pela primeira vez por Ludwig Boltzmann e expressa por sua famosa equação:

{displaystyle S=k_{text{B}}ln W}

Onde? $S$ é a entropia termodinâmica de um macrostate particular (definido por parâmetros termodinâmicos, como temperatura, volume, energia, etc.), $W$ é o número de microestados (várias combinações de partículas em vários estados de energia) que podem produzir o macroestado dado, e $k B$ é a constante de Boltzmann. Assume-se que cada microestado é igualmente provável, de modo que a probabilidade de um microestado dado é $p Eu... = 1/ W$ . Quando essas probabilidades são substituídas na expressão acima para a entropia de Gibbs (ou equivalentemente) $k B$ vezes a entropia de Shannon), resultado da equação de Boltzmann. Em termos teóricos da informação, a entropia da informação de um sistema é a quantidade de informação necessária para determinar um microestado, dada a macrostate.

Na visão de Jaynes (1957), a entropia termodinâmica, explicada pela mecânica estatística, deve ser vista como uma aplicação da teoria da informação de Shannon: a entropia termodinâmica é interpretada como sendo proporcional à quantidade de informações adicionais de Shannon necessárias para definir o estado microscópico detalhado do sistema, que permanece não comunicado por uma descrição apenas em termos das variáveis macroscópicas da termodinâmica clássica, com a constante de proporcionalidade sendo apenas a constante de Boltzmann. Adicionar calor a um sistema aumenta sua entropia termodinâmica porque aumenta o número de possíveis estados microscópicos do sistema que são consistentes com os valores mensuráveis de suas variáveis macroscópicas, tornando qualquer descrição de estado completa mais longa. (Veja o artigo: termodinâmica de entropia máxima). O demônio de Maxwell pode (hipoteticamente) reduzir a entropia termodinâmica de um sistema usando informações sobre os estados de moléculas individuais; mas, como Landauer (de 1961) e colegas de trabalho mostraram, para funcionar, o próprio demônio deve aumentar a entropia termodinâmica no processo, pelo menos na quantidade de informações de Shannon que ele se propõe a adquirir e armazenar primeiro; e assim a entropia termodinâmica total não diminui (o que resolve o paradoxo). O princípio de Landauer impõe um limite inferior na quantidade de calor que um computador deve gerar para processar uma determinada quantidade de informação, embora os computadores modernos sejam muito menos eficientes.

Compressão de dados

A definição de entropia de Shannon, quando aplicada a uma fonte de informação, pode determinar a capacidade mínima do canal necessária para transmitir de forma confiável a fonte como dígitos binários codificados. A entropia de Shannon mede a informação contida em uma mensagem em oposição à parte da mensagem que é determinada (ou previsível). Exemplos deste último incluem redundância na estrutura da linguagem ou propriedades estatísticas relativas às frequências de ocorrência de pares de letras ou palavras, trigêmeos, etc. codificação aritmética. (Consulte também Complexidade de Kolmogorov.) Na prática, os algoritmos de compressão incluem deliberadamente alguma redundância criteriosa na forma de somas de verificação para proteção contra erros. A taxa de entropia de uma fonte de dados é o número médio de bits por símbolo necessários para codificá-la. Os experimentos de Shannon com preditores humanos mostram uma taxa de informação entre 0,6 e 1,3 bits por caractere em inglês; o algoritmo de compactação PPM pode atingir uma taxa de compactação de 1,5 bits por caractere em texto em inglês.

Se um esquema de compactação é sem perdas – aquele no qual você sempre pode recuperar toda a mensagem original por descompactação – então uma mensagem compactada tem a mesma quantidade de informações que a original, mas comunicada em menos caracteres. Possui mais informações (maior entropia) por caractere. Uma mensagem compactada tem menos redundância. O teorema de código-fonte de Shannon afirma que um esquema de compactação sem perdas não pode compactar mensagens, em média, para ter mais do que um bit de informação por bit de mensagem, mas que qualquer valor menos</ Mais de um bit de informação por bit de mensagem pode ser obtido empregando um esquema de codificação adequado. A entropia de uma mensagem por bit multiplicada pelo comprimento dessa mensagem é uma medida de quanta informação total a mensagem contém. O teorema de Shannon também implica que nenhum esquema de compactação sem perdas pode encurtar todas as mensagens. Se algumas mensagens saem mais curtas, pelo menos uma deve sair mais longa devido ao princípio da casa dos pombos. Na prática, isso geralmente não é um problema, porque normalmente só se está interessado em compactar certos tipos de mensagens, como um documento em inglês, em vez de texto sem sentido, ou fotografias digitais em vez de ruído, e não é importante se um o algoritmo de compressão torna algumas sequências improváveis ou desinteressantes maiores.

Um estudo de 2011 na Science estima a capacidade tecnológica do mundo para armazenar e comunicar informações comprimidas de forma otimizada normalizadas nos algoritmos de compressão mais eficazes disponíveis no ano de 2007, estimando assim a entropia do fontes tecnologicamente disponíveis.

Todas as figuras em exabytes entropicamente comprimido
Tipo de informação	1986	2007
Armazenamento	2.	295
Transmissão	432	1900
Telecomunicações	0,281	65

Os autores estimam a capacidade tecnológica da humanidade para armazenar informações (totalmente compactadas entropicamente) em 1986 e novamente em 2007. Eles dividem as informações em três categorias - armazenar informações em um meio, receber informações por meio de redes de transmissão unidirecional ou para trocar informações através de redes de telecomunicações bidirecionais.

Entropia como medida de diversidade

A entropia é uma das várias formas de medir a biodiversidade e é aplicada na forma do índice de Shannon. Um índice de diversidade é uma medida estatística quantitativa de quantos tipos diferentes existem em um conjunto de dados, como espécies em uma comunidade, representando riqueza ecológica, uniformidade e dominância. Especificamente, a entropia de Shannon é o logaritmo de $1 D$ , o verdadeiro índice de diversidade com parâmetro igual a 1. O índice de Shannon está relacionado às abundâncias proporcionais de tipos.

Limitações de entropia

Existem vários conceitos relacionados à entropia que quantificam matematicamente o conteúdo da informação de alguma forma:

o auto-informação de uma mensagem individual ou símbolo retirado de uma determinada distribuição de probabilidade,
o - Sim. de uma dada distribuição de probabilidade de mensagens ou símbolos, e
o taxa de entropia de um processo estocástico.

(A "taxa de auto-informação" também pode ser definida para uma determinada sequência de mensagens ou símbolos gerados por um determinado processo estocástico: será sempre igual à taxa de entropia no caso de um processo estacionário.) Outras quantidades de informação também são usadas para comparar ou relacionar diferentes fontes de informação.

É importante não confundir os conceitos acima. Freqüentemente, só fica claro a partir do contexto a qual deles se refere. Por exemplo, quando alguém diz que a "entropia" da língua inglesa é cerca de 1 bit por caractere, eles estão, na verdade, modelando a língua inglesa como um processo estocástico e falando sobre sua taxa de entropia. O próprio Shannon usou o termo dessa maneira.

Se blocos muito grandes forem usados, a estimativa da taxa de entropia por caractere pode se tornar artificialmente baixa porque a distribuição de probabilidade da sequência não é conhecida com exatidão; é apenas uma estimativa. Se considerarmos o texto de cada livro já publicado como uma sequência, sendo cada símbolo o texto de um livro completo, e se houver $N$ publicados livros, e cada livro é publicado apenas uma vez, a estimativa da probabilidade de cada livro é $1/ N$ , e a entropia (em bits) é $-log 2 (1/ N) = log 2 (N)$ . Como um código prático, isso corresponde a atribuir a cada livro um identificador único e usá-lo no lugar do texto do livro sempre que se quiser fazer referência ao livro. Isso é extremamente útil para falar de livros, mas não é tão útil para caracterizar o conteúdo de informação de um livro individual ou da linguagem em geral: não é possível reconstruir o livro a partir de seu identificador sem conhecer a distribuição de probabilidade, ou seja, o texto completo de todos os livros. A ideia-chave é que a complexidade do modelo probabilístico deve ser considerada. A complexidade de Kolmogorov é uma generalização teórica desta ideia que permite a consideração do conteúdo de informação de uma sequência independente de qualquer modelo de probabilidade particular; ele considera o programa mais curto para um computador universal que gera a sequência. Um código que atinge a taxa de entropia de uma sequência para um determinado modelo, mais o livro de códigos (ou seja, o modelo probabilístico), é um desses programas, mas pode não ser o mais curto.

A sequência de Fibonacci é 1, 1, 2, 3, 5, 8, 13,.... tratando a sequência como uma mensagem e cada número como um símbolo, existem quase tantos símbolos quanto caracteres no mensagem, dando uma entropia de aproximadamente $log 2 (n)$ . Os primeiros 128 símbolos da sequência de Fibonacci têm uma entropia de aproximadamente 7 bits/símbolo, mas a sequência pode ser expressa usando uma fórmula [ $F(n) = F(n -1) + F(n -2)$ para $n = 3, 4, 5,...$ , $F(1) =1$ , $F(2) = 1$ ] e esta fórmula tem uma entropia muito menor e se aplica a qualquer comprimento da sequência de Fibonacci.

Limitações de entropia na criptografia

Na criptoanálise, a entropia é frequentemente usada como medida da imprevisibilidade de uma chave criptográfica, embora sua verdadeira incerteza seja incontestável. Por exemplo, uma chave de 128 bits que é uniforme e aleatoriamente gerada tem 128 bits de entropia. Também leva (em média) ${displaystyle 2^{127}}$ suposições para quebrar pela força bruta. Entropy não consegue capturar o número de suposições necessárias se as chaves possíveis não forem escolhidas uniformemente. Em vez disso, uma medida chamada trabalho de adivinhação pode ser usado para medir o esforço necessário para um ataque de força bruta.

Outros problemas podem surgir de distribuições não uniformes usadas em criptografia. Por exemplo, um preenchimento único binário de 1.000.000 dígitos usando ou exclusivo. Se o bloco tiver 1.000.000 de bits de entropia, está perfeito. Se o bloco tiver 999.999 bits de entropia, distribuídos uniformemente (cada bit individual do bloco com 0,999999 bits de entropia), pode fornecer boa segurança. Mas se o bloco tiver 999.999 bits de entropia, onde o primeiro bit é fixo e os 999.999 bits restantes são perfeitamente aleatórios, o primeiro bit do texto cifrado não será criptografado.

Dados como um processo de Markov

Uma maneira comum de definir entropia para texto é baseada no modelo de texto de Markov. Para uma fonte de ordem 0 (cada caractere é selecionado independentemente dos últimos caracteres), a entropia binária é:

${displaystyle mathrm {H} ({mathcal {S}})=-sum p_{i}log p_{i},}$

onde $p i$ é a probabilidade de $e$ . Para uma fonte de Markov de primeira ordem (na qual a probabilidade de selecionar um caractere depende apenas do caractere imediatamente anterior), a taxa de entropia é:

${displaystyle mathrm {H} ({mathcal {S}})=-sum _{i}p_{i}sum _{j} p_{i}(j)log p_{i}(j),}$

Onde? $Eu...$ é um Estado (certas personagens anteriores) e $p_{i}(j)$ é a probabilidade de $JJ$ dados $Eu...$ como o personagem anterior.

Para uma fonte de Markov de segunda ordem, a taxa de entropia é

${displaystyle mathrm {H} ({mathcal {S}})=-sum _{i}p_{i}sum _{j}p_{i}(j)sum _{k}p_{i,j}(k) log p_{i,j}(k).}$

Eficiência (entropia normalizada)

Um alfabeto de origem com distribuição não uniforme terá menos entropia do que se esses símbolos tivessem distribuição uniforme (ou seja, o "alfabeto otimizado"). Essa deficiência na entropia pode ser expressa como uma razão chamada eficiência:

${displaystyle eta (X)={frac {H}{H_{max}}}=-sum _{i=1}^{n}{frac {p(x_{i})log _{b}(p(x_{i}))}{log _{b}(n)}}}$

Aplicando as propriedades básicas do logaritmo, esta quantidade também pode ser expressa como:

${displaystyle eta (X)=-sum _{i=1}^{n}{frac {p(x_{i})log _{b}(p(x_{i}))}{log _{b}(n)}}=sum _{i=1}^{n}{frac {log _{b}(p(x_{i})^{-p(x_{i})})}{log _{b}(n)}}=sum _{i=1}^{n}log _{n}(p(x_{i})^{-p(x_{i})})=log _{n}(prod _{i=1}^{n}p(x_{i})^{-p(x_{i})})}$

A eficiência tem utilidade na quantificação do uso efetivo de um canal de comunicação. Esta formulação também é referida como a entropia normalizada, como a entropia é dividida pela entropia máxima ${log _{b}(n)}$ . Além disso, a eficiência é indiferente à escolha da base (positiva) $b)$ , como indicado pela insensibilidade dentro do logaritmo final acima para.

Entropia para variáveis aleatórias contínuas

Entropia diferencial

A entropia de Shannon é restrita a variáveis aleatórias que tomam valores discretos. A fórmula correspondente para uma variável aleatória contínua com função de densidade de probabilidade $f (x)$ com suporte finito ou infinito $mathbb {X}$ na linha real é definida por analogia, usando a forma acima da entropia como uma expectativa:

${displaystyle mathrm {H} (X)=mathbb {E} [-log f(X)]=-int _{mathbb {X} }f(x)log f(x),mathrm {d} x.}$

Esta é a entropia diferencial (ou entropia contínua). Um precursor da entropia contínua $h [f]$ é a expressão para o funcional $Η$ no teorema H de Boltzmann.

Embora a analogia entre as duas funções seja sugestiva, a seguinte questão deve ser colocada: a entropia diferencial é uma extensão válida da entropia discreta de Shannon? A entropia diferencial carece de várias propriedades que a entropia discreta de Shannon possui - pode até ser negativa - e correções foram sugeridas, limitando notavelmente a densidade de pontos discretos.

Para responder a esta pergunta, uma conexão deve ser estabelecida entre as duas funções:

A fim de obter uma medida geralmente finita quando o tamanho do bin vai para zero. No caso discreto, o tamanho da caixa é a largura (implícita) de cada uma das $n$ (finitas ou infinitas) caixas cujas probabilidades são denotadas por $p n$ . Como o domínio contínuo é generalizado, a largura deve ser explicitada.

Para fazer isso, comece com uma função contínua $f$ discreta em caixas de tamanho $Delta$ . Pelo teorema de valor médio existe um valor $x Eu...$ em cada caixa tal que

{displaystyle f(x_{i})Delta =int _{iDelta }^{(i+1)Delta }f(x),dx}

$f$ ${displaystyle int _{-infty }^{infty }f(x),dx=lim _{Delta to 0}sum _{i=-infty }^{infty }f(x_{i})Delta}$
Vamos denotar
${displaystyle mathrm {H} ^{Delta }:=-sum _{i=-infty }^{infty }f(x_{i})Delta log left(f(x_{i})Delta right)}$ ${displaystyle mathrm {H} ^{Delta }=-sum _{i=-infty }^{infty }f(x_{i})Delta log(f(x_{i}))-sum _{i=-infty }^{infty }f(x_{i})Delta log(Delta).}$
Como $Δ \to 0$ , temos
${begin{aligned}sum _{i=-infty }^{infty }f(x_{i})Delta &to int _{-infty }^{infty }f(x),dx=1\sum _{i=-infty }^{infty }f(x_{i})Delta log(f(x_{i}))&to int _{-infty }^{infty }f(x)log f(x),dx.end{aligned}}$
Nota; $log(Δ) \to -\infty$ como $Δ \to 0$ , requer uma definição especial da entropia diferencial ou contínua:
$h[f]=lim _{Delta to 0}left(mathrm {H} ^{Delta }+log Delta right)=-int _{-infty }^{infty }f(x)log f(x),dx,$
que é, como dito antes, chamado de entropia diferencial. Isso significa que a entropia diferencial não é um limite da entropia de Shannon para $n \to \infty$ . Em vez disso, difere do limite da entropia de Shannon por um deslocamento infinito (consulte também o artigo sobre a dimensão da informação).
Limitando a densidade de pontos discretos
Como resultado, ao contrário da entropia de Shannon, a entropia diferencial não é, em geral, uma boa medida de incerteza ou informação. Por exemplo, a entropia diferencial pode ser negativa; também não é invariante sob transformações de coordenadas contínuas. Este problema pode ser ilustrado por uma mudança de unidades quando $x$ é uma variável dimensionada. $f (x)$ terá então as unidades de $1/ x$ . O argumento do logaritmo deve ser adimensional, caso contrário é impróprio, de modo que a entropia diferencial dada acima será imprópria. Se $Δ$ for algum "padrão" valor de $x$ (ou seja, "tamanho da caixa") e, portanto, tem as mesmas unidades, então uma entropia diferencial modificada pode ser escrita em forma adequada como:
${displaystyle mathrm {H} =int _{-infty }^{infty }f(x)log(f(x),Delta),dx,}$
e o resultado será o mesmo para qualquer escolha de unidades para $x$ . Na verdade, o limite de entropia discreta como ${displaystyle Nrightarrow infty }$ também incluiria um termo de ${displaystyle log(N)}$ , que em geral seria infinito. Isto é esperado: variáveis contínuas normalmente teriam entropia infinita quando discreta. A densidade limite de pontos discretos é realmente uma medida de quanto mais fácil uma distribuição é descrever do que uma distribuição uniforme sobre seu esquema de quantificação.
Entropia relativa
Outra medida útil de entropia que funciona igualmente bem no caso discreto e contínuo é a entropia relativa de uma distribuição. É definido como a divergência de Kullback–Leibler da distribuição para uma medida de referência $m$ como segue. Assuma que uma distribuição de probabilidade $p$ é absolutamente contínua em relação a uma medida $m$ , ou seja, está na forma $p (dx) = f (x) m (dx)$ para algum $m$ -função integrável $f$ com $m$ -integral 1, então a entropia relativa pode ser definida como
$D_{mathrm {KL} }(p|m)=int log(f(x))p(dx)=int f(x)log(f(x))m(dx).$
Nesta forma, a entropia relativa generaliza (até a mudança de sinal) tanto a entropia discreta, onde a medida $m$ é a medida de contagem, e a entropia diferencial, onde a medida $m$ é a medida de Lebesgue. Se a medida $m$ for uma distribuição de probabilidade, a entropia relativa é não negativa e zero se $p = m$ como medidas. Ele é definido para qualquer espaço de medida, portanto independente coordenado e invariante sob reparametrizações coordenadas se levarmos em consideração a transformação da medida $m$ . A entropia relativa e (implicitamente) a entropia e a entropia diferencial dependem da "referência" medir $m$ .
Uso em combinatória
A entropia tornou-se uma quantidade útil em combinatória.
Desigualdade de Loomis–Whitney
Um exemplo simples disso é uma prova alternativa da desigualdade de Loomis–Whitney: para todo subconjunto $A \subseteq Z d$ , temos
$|A|^{d-1}leq prod _{i=1}^{d}|P_{i}(A)|$
onde $P i$ é a projeção ortogonal no $i$ ª coordenada:
$P_{i}(A)={(x_{1},ldotsx_{i-1},x_{i+1},ldotsx_{d}):(x_{1},ldotsx_{d})in A}.$
A prova segue como um corolário simples da desigualdade de Shearer: se $X 1,..., X d$ são variáveis aleatórias e $S 1,..., S n$ são subconjuntos de ${1,..., d$ } de forma que todo inteiro entre 1 e $d$ esteja exatamente em $r$ desses subconjuntos, então
$mathrm {H} [(X_{1},ldotsX_{d})]leq {frac {1}{r}}sum _{i=1}^{n}mathrm {H} [(X_{j})_{jin S_{i}}]$
Onde? $(X_{j})_{jin S_{i}}$ é o produto cartesiano de variáveis aleatórias $X JJ$ com índices $JJ$ em $S Eu...$ (assim, a dimensão deste vetor é igual ao tamanho de $S Eu...$ ).
Nós esboçamos como Loomis–Whitney segue a partir deste: De fato, deixe $X$ ser uma variável aleatória uniformemente distribuída com valores em $A$ e para que cada ponto em $A$ ocorre com probabilidade igual. Então (pelas propriedades adicionais da entropia mencionada acima) $H... X) = log| A |$ , onde $| A |$ denota a cardinalidade de $A$ . Vamos. $S Eu... = {1, 2,..., Eu... - Sim. Eu... +1,..., D$ } A gama de $(X_{j})_{jin S_{i}}$ está contido $P Eu... (A)$ e daí $mathrm {H} [(X_{j})_{jin S_{i}}]leq log |P_{i}(A)|$ . Agora use isso para amarrar o lado direito da desigualdade de Shearer e exponencializar os lados opostos da desigualdade resultante que você obter.
Aproximação do coeficiente binomial
Para números inteiros $0 < k < n$ deixe $q = k / n$ . Então
${frac {2^{nmathrm {H} (q)}}{n+1}}leq {tbinom {n}{k}}leq 2^{nmathrm {H} (q)},$
onde
$mathrm {H} (q)=-qlog _{2}(q)-(1-q)log _{2}(1-q).$
Prova (sketch)
Note que ${tbinom {n}{k}}q^{qn}(1-q)^{n-nq}$ é um termo da expressão
$sum _{i=0}^{n}{tbinom {n}{i}}q^{i}(1-q)^{n-i}=(q+(1-q))^{n}=1.$
Reorganizar dá o limite superior. Para o limite inferior um primeiro mostra, usando alguma álgebra, que é o maior termo na soma. Mas então,
${displaystyle {binom {n}{k}}q^{qn}(1-q)^{n-nq}geq {frac {1}{n+1}}}$
desde há $n + 1$ termos na soma. Reorganizar dá o limite inferior.
Uma boa interpretação disso é que o número de cadeias binárias de comprimento $n$ com exatamente $k$ muitos 1 é aproximadamente $2^{nmathrm {H} (k/n)}$ .
Uso em aprendizado de máquina
As técnicas de aprendizado de máquina surgem em grande parte da estatística e também da teoria da informação. Em geral, a entropia é uma medida de incerteza e o objetivo do aprendizado de máquina é minimizar a incerteza.
Os algoritmos de aprendizagem de árvores de decisão usam entropia relativa para determinar as regras de decisão que regem os dados em cada nó. O ganho de informação em árvores de decisão ${displaystyle IG(Y,X)}$ , que é igual à diferença entre a entropia de $Y$ e a entropia condicional de $Y$ dados $X$ , quantifica as informações esperadas, ou a redução da entropia, de conhecimento adicional do valor de um atributo $X$ . O ganho de informação é usado para identificar quais atributos do conjunto de dados fornecem mais informações e deve ser usado para dividir os nós da árvore de forma ideal.
Os modelos de inferência bayesiana geralmente aplicam o princípio da entropia máxima para obter distribuições de probabilidade prioritárias. A ideia é que a distribuição que melhor representa o estado atual de conhecimento de um sistema é aquela com maior entropia, sendo, portanto, adequada para ser a priori.
A classificação em aprendizado de máquina realizada por regressão logística ou redes neurais artificiais geralmente emprega uma função de perda padrão, chamada perda de entropia cruzada, que minimiza a entropia cruzada média entre a verdade absoluta e as distribuições previstas. Em geral, a entropia cruzada é uma medida das diferenças entre dois conjuntos de dados semelhantes à divergência KL (também conhecida como entropia relativa).

Contenido relacionado

GFDL (desambiguação)
GFDL, ou GNU Free Documentation License, é uma licença para documentação...
Problema de quadro
Na inteligência artificial, o problema do quadro descreve um problema com o uso da lógica de primeira ordem para expressar fatos sobre um robô no mundo....
Sequência de Fibonacci
Na matemática, a sequência de Fibonacci é uma sequência na qual cada número é a soma dos dois anteriores. Números individuais na sequência de...
Más resultados...