Intuição na divergência de Kullback-Leibler (KL)

47

Eu aprendi sobre a intuição por trás da divergência KL quanto o quanto uma função de distribuição de modelo difere da distribuição teórica / verdadeira dos dados. A fonte Estou lendo continua a dizer que a compreensão intuitiva de 'distância' entre estas duas distribuições é útil, mas não deve ser tomada literalmente porque para duas distribuições e , o KL divergência não é simétrica em e .PQPQ

Não sei ao certo como entender a última afirmação, ou é aí que a intuição da 'distância' se desintegra?

Eu apreciaria um exemplo simples, mas perspicaz.

cgo
fonte
3
Eu acho que você precisa dar um passo atrás e entender que você normalmente tem uma assimetria nas estatísticas entre a verdadeira distribuição da população e a amostra (ou verdadeiro e modelo), etc., e é isso que o KL Divergence reflete ... 't essa distinção normalmente e uma simétricas marcas métricas mais sentido
seanv507
1
Qual "fonte" você estava lendo?
Nbro 16/11

Respostas:

34

A distância (métrica) deve ser simétrica, ou seja, . Mas, por definição, não é.DD(P,Q)=D(Q,P)KL

Exemplo: , , .Ω={A,B}P(A)=0.2,P(B)=0.8Q(A)=Q(B)=0.5

Nós temos:

KL(P,Q)=P(A)logP(A)Q(A)+P(B)logP(B)Q(B)0.19

e

KL(Q,P)=Q(A)logQ(A)P(A)+Q(B)logQ(B)P(B)0.22

portanto, e, portanto, não é uma distância (métrica).K LKL(P,Q)KL(Q,P)KL

microfone
fonte
50

Adicionando às outras excelentes respostas, uma resposta com outro ponto de vista que talvez possa acrescentar mais intuição, que foi solicitada.

A divergência Kullback-Leibler é Se você tiver duas hipóteses sobre qual distribuição está gerando os dados , e , então é a razão de probabilidade para testar contra . Vemos que a divergência de Kullback-Leibler acima é o valor esperado da razão de probabilidade de logon sob a hipótese alternativa. Portanto, é uma medida da dificuldade desse problema de teste, quando é a hipótese nula. Então a assimetriaX P Q p ( x )

KL(P||Q)=p(x)logp(x)q(x)dx
XPQ H0:QH1:PKL(P||Q)QKL(P||Q)KL(Q||P)p(x)q(x)H0:QH1:PKL(P||Q)QKL(P||Q)KL(Q||P) reflete simplesmente a assimetria entre a hipótese nula e a alternativa.

Vejamos isso em um exemplo particular. Seja a distribuição e a distribuição normal padrão (no exemplo numérico abaixo ). A integral que define a divergência parece complicada, então vamos simplesmente usar a integração numérica em R:t ν Q ν = 1PtνQν=1

> lLR_1  <-  function(x) {dt(x, 1, log=TRUE)-dnorm(x, log=TRUE)}  
> integrate(function(x) dt(x, 1)*lLR_1(x), lower=-Inf, upper=Inf)
Error in integrate(function(x) dt(x, 1) * lLR_1(x), lower = -Inf, upper = Inf) : 
  the integral is probably divergent

> lLR_2  <-  function(x) {-dt(x, 1, log=TRUE)+dnorm(x, log=TRUE)}  
> integrate(function(x) dnorm(x)*lLR_2(x), lower=-Inf, upper=Inf)
0.2592445 with absolute error < 1e-07

No primeiro caso, a integral parece divergir numericamente, indicando que a divergência é muito grande ou infinita; no segundo, é pequena, resumindo: O primeiro caso é verificado pela integração simbólica analítica em resposta por @ Xi'an aqui: Qual é o valor máximo da divergência Kullback-Leibler (KL) .

KL(P||Q)KL(Q||P)0.26

O que isso nos diz, em termos práticos? Se o modelo nulo é uma distribuição normal padrão, mas os dados são gerados a partir de uma distribuição , é muito fácil rejeitar o nulo! Os dados de uma distribuição não se parecem com dados distribuídos normais. No outro caso, as funções são trocadas. O nulo é o mas os dados são normais. Porém, dados distribuídos normais podem parecer , então esse problema é muito mais difícil! Aqui temos o tamanho da amostra e todos os dados que podem vir de uma distribuição normal também podem ter vindo de um ! Mudando os papéis, não, a diferença vem principalmente dos papéis dos discrepantes.t1t1t1t1n=1t1

Sob a distribuição alternativa existe uma probabilidade bastante grande de obter uma amostra que tem uma probabilidade muito pequena no modelo nulo (normal), dando uma enorme divergência. Mas quando a distribuição alternativa é normal, praticamente todos os dados que podemos obter terão uma probabilidade moderada (realmente, densidade ...) sob o modelo nulo , portanto a divergência é pequena.t1t1

Isso está relacionado à minha resposta aqui: Por que devemos usar erros t em vez de erros normais?

kjetil b halvorsen
fonte
22

Primeiro, a violação da condição de simetria é o menor problema com a divergência de Kullback-Leibler. também viola a desigualdade de triângulo. Você pode simplesmente introduzir a versão simétrica como , mas isso ainda não é métrico, porque e viola a desigualdade do triângulo. Para provar que basta pegar três moedas tendenciosas A, B e C que produzem muito menos cara do que coroa, por exemplo, moedas com probabilidade de cara de: A = 0,1, B = 0,2 e C = 0,3. Em ambos os casos, a divergência KL regular D ou sua versão simétrica SKL, verifique se não estão preenchendo a desigualdade do triângulo D(P||Q)

SKL(P,Q)=D(P||Q)+D(Q||P)
D(P||Q)SKL(P,Q)
D(A||B)+D(B||C)D(A||C)
SKL(A,B)+SKL(B,C)SKL(A,C)
Simplesmente use estas fórmulas:
D(P||Q)=ipilog(piqi)
SKL(P,Q)=i(piqi)log(piqi)

D(A||B)=0.1log(0.10.2)+0.9log(0.90.8)0.0159
D(B||C)0.0112
D(A||C)0.0505
0.0159+0.01120.0505
SKL(A,B)0.0352
SKL(B,C)0.0234
SKL(A,C)0.1173
0.0352+0.02340.1173

Eu introduzi este exemplo de propósito. Vamos imaginar que você está jogando algumas moedas, por exemplo, 100 vezes. Desde que essas moedas sejam imparciais, você simplesmente codificaria os resultados do lançamento com uma sequência de 0-1 bits (1 cabeça, 0 cauda). Em uma situação em que a probabilidade de cabeça é igual à probabilidade de cauda e igual a 0,5, é uma codificação bastante eficaz. Agora, como temos algumas moedas tendenciosas, preferimos codificar resultados mais prováveis ​​com código mais curto, por exemplo, mesclar grupos de cara e coroa e representar sequências de k cabeças com código mais longo do que a sequência de k coroa (elas são mais prováveis). E aqui ocorre a divergência Kullback-Leibler . Se P representa a verdadeira distribuição dos resultados, e Q é apenas uma aproximação de P, entãoD(P||Q)D(P||Q) denota a penalidade que você paga quando codifica resultados que realmente vêm de P distrib com codificação destinada a Q (penalidade no sentido dos bits extras que você precisa usar).

Se você simplesmente precisar de métrica, use a distância de Bhattacharyya (é claro que a versão modificada )1[xp(x)q(x)]

Adam Przedniczek
fonte
7
Se alguém estiver realmente preocupado em ter uma métrica com uma conexão mais próxima à divergência KL, poderá considerar a raiz quadrada da divergência Jensen-Shannon no lugar de Bhattacharyya.
cardeal
5

Sou tentado aqui a dar uma resposta puramente intuitiva à sua pergunta. Reformulando o que você diz, a divergência KL é uma maneira de medir a distância entre duas distribuições, pois você calcularia a distância entre dois conjuntos de dados em um espaço de Hilbert, mas é preciso ter cuidado.

Por quê? A divergência KL não é uma distância que você pode usar normalmente, como por exemplo a norma . De fato, é positivo e igual a zero se, e somente se, as duas distribuições forem iguais (como nos axiomas para definir uma distância). Mas, como mencionado, não é simétrico. Existem maneiras de contornar isso, mas faz sentido que não seja simétrico.L2

De fato, a divergência KL define a distância entre uma distribuição de modelo (que você realmente conhece) e uma teórica tal modo que faz sentido lidar de maneira diferente com (a distância "teórica" ​​de a assumindo a modelo ) e (a distância "empírica" ​​de a assumindo os dados ), pois significam medidas bastante diferentes.QPKL(P,Q)PQPKL(Q,P)PQQ

meduz
fonte
4

O livro Elementos da teoria da informação nos dá um exemplo:

Por exemplo, se soubéssemos a verdadeira distribuição p da variável aleatória, poderíamos construir um código com o comprimento médio da descrição H (p). Se, em vez disso, usamos o código para uma distribuição q, precisaríamos de H (p) + D (p || q) bits, em média, para descrever a variável aleatória.

Parafraseando a afirmação acima, podemos dizer que, se alterarmos a distribuição de informações (de q para p), precisaremos de D (p || q) bits extras, em média, para codificar a nova distribuição.

Uma ilustração

Deixe-me ilustrar isso usando um aplicativo no processamento de linguagem natural.

Considere que um grande grupo de pessoas, rotulado B, são mediadores e cada um deles é atribuída uma tarefa de escolher um nome de turkey, animale booke transmiti-lo para C. Não é um nome de cara Um que pode enviar a cada um deles um e-mail para dar eles algumas dicas. Se ninguém no grupo recebeu o e-mail, eles podem levantar as sobrancelhas e hesitar um pouco, considerando o que C precisa. E a probabilidade de cada opção escolhida é 1/3. Distribuição uniforme uniforme (se não, pode estar relacionada à sua própria preferência e simplesmente ignoramos esses casos).

Mas se eles receberem um verbo, como baste3/4 deles podem escolher turkeye 3/16 animale 1/16 book. Então, quanta informação em bits cada mediador obteve em média depois de conhecer o verbo? Isto é:

D(p(nouns|baste)||p(nouns))=x{turkey,animal,book}p(x|baste)log2p(x|baste)p(x)=34log23413+316log231613+116log211613=0.5709  bits

Mas e se o verbo dado for read? Podemos imaginar que todos eles escolheriam booksem hesitar, então o ganho médio de informações para cada mediador do verbo readé:

D(p(nouns|read)||p(nouns))=x{book}p(x|read)log2p(x|read)p(x)=1log2113=1.5849  bits
Podemos ver que o verbo readpode fornecer mais informações aos mediadores. E é isso que a entropia relativa pode medir.

Vamos continuar nossa história. Se C suspeitar que o substantivo possa estar errado, porque A lhe disse que ele pode ter cometido um erro enviando o verbo errado aos mediadores. Então, quanta informação em bits uma notícia tão ruim pode dar a C?

1) se o verbo dado por A for baste:

D(p(nouns)||p(nouns|baste))=x{turkey,animal,book}p(x)log2p(x)p(x|baste)=13log21334+13log213316+13log213116=0.69172  bits

2) mas e se o verbo fosse read?

D(p(nouns)||p(nouns|baste))=x{book,,}p(x)log2p(x)p(x|baste)=13log2131+13log2130+13log2130=  bits

Como C nunca sabe o que seriam os outros dois substantivos e qualquer palavra no vocabulário seria possível.

Podemos ver que a divergência KL é assimétrica.

Espero estar certo e, se não, por favor, comente e ajude a me corrigir. Desde já, obrigado.

Lerner Zhang
fonte