Estou lendo este livro ( NLTK ) e é confuso. Entropia é definida como :

Entropia é a soma da probabilidade de cada rótulo vezes a probabilidade de log desse mesmo rótulo

Como posso aplicar entropia e entropia máxima em termos de mineração de texto? Alguém pode me dar um exemplo fácil e simples (visual)?

Suponho que a entropia foi mencionada no contexto da construção de árvores de decisão .

Para ilustrar, imagine a tarefa de aprender a classificar os nomes em grupos de homens / mulheres. É fornecida uma lista de nomes, cada um com um mou outro f, queremos aprender um modelo que se ajuste aos dados e possa ser usado para prever o sexo de um novo nome invisível.

name       gender
-----------------        Now we want to predict 
Ashley        f              the gender of "Amro" (my name)
Brian         m
Caroline      f
David         m

O primeiro passo é decidir quais recursos dos dados são relevantes para a classe de destino que queremos prever. Alguns exemplos de recursos incluem: primeira / última letra, comprimento, número de vogais, termina com uma vogal, etc. Então, após a extração do recurso, nossos dados se parecem com:

# name    ends-vowel  num-vowels   length   gender
# ------------------------------------------------
Ashley        1         3           6        f
Brian         0         2           5        m
Caroline      1         4           8        f
David         0         2           5        m

O objetivo é construir uma árvore de decisão . Um exemplo de uma árvore seria:

length<7
|   num-vowels<3: male
|   num-vowels>=3
|   |   ends-vowel=1: female
|   |   ends-vowel=0: male
length>=7
|   length=5: male

basicamente, cada nó representa um teste realizado em um único atributo e vamos para a esquerda ou direita, dependendo do resultado do teste. Continuamos percorrendo a árvore até chegarmos a um nó folha que contém a previsão de classe ( mou f)

Portanto, se rodarmos o nome Amro nessa árvore, começamos testando " é o comprimento <7? " E a resposta é sim , então seguimos pelo ramo. Após a ramificação, o próximo teste " é o número de vogais <3? " Novamente avaliado como verdadeiro . Isso leva a um nó de folha rotulado me, portanto, a previsão é masculina (o que acontece, a árvore previu o resultado corretamente ).

A árvore de decisão é construída de forma descendente , mas a questão é como você escolhe qual atributo dividir em cada nó? A resposta é encontrar o recurso que melhor divide a classe de destino nos nós filhos mais puros possíveis (ou seja: nós que não contêm uma mistura de ambos, masculino e feminino, nós bastante puros, com apenas uma classe).

Essa medida de pureza é chamada de informação . Representa a quantidade esperada de informações que seriam necessárias para especificar se uma nova instância (primeiro nome) deve ser classificada como masculino ou feminino, dado o exemplo que atingiu o nó. Nós o calculamos com base no número de classes masculinas e femininas no nó.

Entropia, por outro lado, é uma medida de impureza (o oposto). É definido para uma classe binária com valoresa/bcomo:

Entropy = - p(a)*log(p(a)) - p(b)*log(p(b))

Esta função de entropia binária está representada na figura abaixo (a variável aleatória pode assumir um dos dois valores). Atinge seu máximo quando a probabilidade é p=1/2, o que significa que, p(X=a)=0.5ou similarmente, p(X=b)=0.5tem 50% / 50% de chance de ser um aou outro b(a incerteza é máxima). A função de entropia é no mínimo zero quando a probabilidade é p=1ou p=0com total certeza ( p(X=a)=1ou p(X=a)=0, respectivamente, o último implica p(X=b)=1).

Obviamente, a definição de entropia pode ser generalizada para uma variável aleatória discreta X com N resultados (não apenas dois):

(o logna fórmula geralmente é considerado o logaritmo da base 2 )

De volta à nossa tarefa de classificação de nomes, vamos ver um exemplo. Imagine que em algum momento do processo de construção da árvore, estávamos considerando a seguinte divisão:

     ends-vowel
      [9m,5f]          <--- the [..,..] notation represents the class
    /          \            distribution of instances that reached a node
   =1          =0
 -------     -------
 [3m,4f]     [6m,1f]

Como você pode ver, antes da divisão, tínhamos 9 machos e 5 fêmeas, ou seja, P(m)=9/14e P(f)=5/14. De acordo com a definição de entropia:

Entropy_before = - (5/14)*log2(5/14) - (9/14)*log2(9/14) = 0.9403

Em seguida, comparamos com a entropia calculada após considerar a divisão observando dois ramos filhos. No ramo esquerdo de ends-vowel=1, temos:

Entropy_left = - (3/7)*log2(3/7) - (4/7)*log2(4/7) = 0.9852

e o ramo direito de ends-vowel=0, temos:

Entropy_right = - (6/7)*log2(6/7) - (1/7)*log2(1/7) = 0.5917

Combinamos as entropias esquerda / direita usando o número de instâncias em cada ramificação como fator de peso (7 instâncias foram para a esquerda e 7 instâncias foram para a direita) e obtemos a entropia final após a divisão:

Entropy_after = 7/14*Entropy_left + 7/14*Entropy_right = 0.7885

Agora, comparando a entropia antes e depois da divisão, obtemos uma medida do ganho de informações ou quanta informação obtivemos ao fazer a divisão usando esse recurso específico:

Information_Gain = Entropy_before - Entropy_after = 0.1518

Você pode interpretar o cálculo acima da seguinte maneira: ao fazer a divisão com o end-vowelsrecurso, conseguimos reduzir a incerteza no resultado da previsão de subárvore em uma pequena quantidade de 0,1518 (medida em bits como unidades de informação ).

Em cada nó da árvore, esse cálculo é realizado para cada recurso, e o recurso com maior ganho de informação é escolhido para a divisão de maneira gananciosa (favorecendo recursos que produzem divisões puras com baixa incerteza / entropia). Esse processo é aplicado recursivamente do nó raiz para baixo e para quando um nó folha contém instâncias todas com a mesma classe (não é necessário dividi-lo mais).

Observe que pulei alguns detalhes que estão além do escopo deste post, incluindo como lidar com recursos numéricos , valores ausentes , árvores de sobreajuste e poda , etc.

Para começar, seria melhor entender the measure of information.

Como fazemos measurea informação?

Quando algo improvável acontece, dizemos que é uma grande notícia. Além disso, quando dizemos algo previsível, não é realmente interessante. Então, para quantificar isso interesting-ness, a função deve satisfazer

• se a probabilidade do evento for 1 (previsível), a função fornecerá 0
• se a probabilidade do evento for próxima de 0, a função deverá fornecer um número alto
• se ocorrer probabilidade de 0,5 eventos, fornecer one bitinformações.

Uma medida natural que satisfaz as restrições é

I(X) = -log_2(p)

onde p é a probabilidade do evento X. E a unidade está dentro bit, o mesmo bit que o computador usa. 0 ou 1.

Exemplo 1

Moeda justa:

Quanta informação podemos obter de uma moeda?

Responda : -log(p) = -log(1/2) = 1 (bit)

Exemplo 2

Se um meteoro p=2^{-22}atingir a Terra amanhã, podemos obter 22 bits de informação.

Se o sol nascer amanhã, p ~ 1será 0 bit de informação.

Entropia

Portanto, se considerarmos a expectativa interesting-nessde um evento Y, é a entropia. isto é, entropia é um valor esperado da interessanteidade de um evento.

H(Y) = E[ I(Y)]

Mais formalmente, a entropia é o número esperado de bits de um evento.

Exemplo

Y = 1: um evento X ocorre com probabilidade p

Y = 0: um evento X não ocorre com probabilidade 1-p

H(Y) = E[I(Y)] = p I(Y==1) + (1-p) I(Y==0) 
     = - p log p - (1-p) log (1-p)

Base de log 2 para todo o log.

Não posso fornecer gráficos, mas talvez eu possa dar uma explicação clara.

Suponha que tenhamos um canal de informações, como uma luz que pisca uma vez por dia, vermelha ou verde. Quanta informação ela transmite? O primeiro palpite pode ser um pouco por dia. Mas e se adicionarmos azul, para que o remetente tenha três opções? Gostaríamos de ter uma medida de informação que possa lidar com outras coisas além das potências de dois, mas ainda assim seja aditiva (a maneira como multiplicar o número de mensagens possíveis por dois adiciona um bit). Poderíamos fazer isso usando o log ₂ (número de mensagens possíveis), mas acontece que há uma maneira mais geral.

Suponha que voltemos ao vermelho / verde, mas a lâmpada vermelha queimou (isso é de conhecimento geral), de modo que a lâmpada sempre deve piscar em verde. O canal agora é inútil, sabemos qual será o próximo flashentão os flashes não transmitem informações, nem notícias. Agora, reparamos a lâmpada, mas impomos uma regra de que a lâmpada vermelha pode não piscar duas vezes seguidas. Quando a lâmpada pisca em vermelho, sabemos qual será o próximo flash. Se você tentar enviar um fluxo de bits por esse canal, descobrirá que deve codificá-lo com mais flashes do que com bits (50% a mais, na verdade). E se você quiser descrever uma sequência de flashes, poderá fazê-lo com menos bits. O mesmo se aplica se cada flash for independente (sem contexto), mas os flashes verdes forem mais comuns que o vermelho: quanto mais inclinada for a probabilidade, menos bits serão necessários para descrever a sequência e menos informações serão exibidas até o limite totalmente verde, queimado por lâmpada.

Acontece que há uma maneira de medir a quantidade de informação em um sinal, com base nas probabilidades dos diferentes símbolos. Se a probabilidade de receber o símbolo x _i for p _i , considere a quantidade

-log p i

Quanto menor p _i , maior esse valor. Se x _i torna-se duas vezes mais provável, este valor aumenta por um montante fixo (log (2)). Isso deve lembrá-lo de adicionar um bit a uma mensagem.

Se não sabemos qual será o símbolo (mas sabemos as probabilidades), podemos calcular a média desse valor, quanto obteremos, somando as diferentes possibilidades:

I = -Σ p i log (p i )

Este é o conteúdo da informação em um flash.

Lâmpada vermelha queimada: p vermelho = 0, p verde = 1, I = - (0 + 0) = 0
Equiprobável vermelho e verde: p vermelho = 1/2, p verde = 1/2 , I = - (2 * 1/2 * log (1/2)) = log (2)
Três cores, equivalentes: p i = 1/3, I = - (3 * 1/3 * log (1/3)) = log (3)
Verde e vermelho, verde duas vezes mais provável: p vermelho = 1/3 , p verde = 2/3, I = - (1/3 log (1/3) + 2/3 log (2/3)) = log ( 3) - 2/3 do log (2)

Este é o conteúdo da informação, ou entropia, da mensagem. É máximo quando os diferentes símbolos são equivalentes. Se você é físico, usa o log natural, se é um cientista da computação, usa o log ₂ e obtém bits.

Eu realmente recomendo que você leia sobre Teoria da Informação, métodos bayesianos e MaxEnt. O ponto de partida é este livro (disponível gratuitamente on-line) de David Mackay:

http://www.inference.phy.cam.ac.uk/mackay/itila/

Esses métodos de inferência são realmente muito mais gerais do que apenas a mineração de texto e não posso imaginar como alguém aprenderia como aplicar isso à PNL sem aprender alguns dos princípios gerais contidos neste livro ou em outros livros introdutórios sobre Machine Learning e MaxEnt bayesian métodos.

A conexão entre entropia e teoria das probabilidades com o processamento e armazenamento de informações é muito, muito profunda. Para provar, há um teorema devido a Shannon que afirma que a quantidade máxima de informações que você pode passar sem erros por um canal de comunicação barulhento é igual à entropia do processo de ruído. Há também um teorema que conecta o quanto você pode compactar um dado para ocupar o mínimo de memória possível em seu computador à entropia do processo que gerou os dados.

Não acho que seja realmente necessário que você aprenda todos esses teoremas da teoria da comunicação, mas não é possível aprender isso sem aprender o básico sobre o que é entropia, como é calculado, qual é o seu relacionamento com informações e inferência, etc. ...

Quando eu estava implementando um algoritmo para calcular a entropia de uma imagem, encontrei esses links, veja aqui e aqui .

Este é o pseudo-código que eu usei, você precisará adaptá-lo para trabalhar com texto em vez de imagens, mas os princípios devem ser os mesmos.

//Loop over image array elements and count occurrences of each possible
//pixel to pixel difference value. Store these values in prob_array
for j = 0, ysize-1 do $
    for i = 0, xsize-2 do begin
       diff = array(i+1,j) - array(i,j)
       if diff lt (array_size+1)/2 and diff gt -(array_size+1)/2 then begin
            prob_array(diff+(array_size-1)/2) = prob_array(diff+(array_size-1)/2) + 1
       endif
     endfor

//Convert values in prob_array to probabilities and compute entropy
n = total(prob_array)

entrop = 0
for i = 0, array_size-1 do begin
    prob_array(i) = prob_array(i)/n

    //Base 2 log of x is Ln(x)/Ln(2). Take Ln of array element
    //here and divide final sum by Ln(2)
    if prob_array(i) ne 0 then begin
        entrop = entrop - prob_array(i)*alog(prob_array(i))
    endif
endfor

entrop = entrop/alog(2)

Eu recebi esse código de algum lugar, mas não consigo extrair o link.

Informalmente

entropia é disponibilidade de informação ou conhecimento, a falta de informação leva a dificuldades na previsão do futuro, que é alta entropia (previsão da próxima palavra na mineração de texto) e a disponibilidade da informação / conhecimento nos ajudará a uma previsão mais realista do futuro (baixa entropia).

Informações relevantes de qualquer tipo reduzirão a entropia e nos ajudarão a prever um futuro mais realista; essas informações podem estar presentes na palavra "carne" na frase ou na palavra "carne". Isso é chamado de ganho de informação

Formalmente

entropia é falta de ordem de previsibilidade

Enquanto você lê um livro sobre NLTK, seria interessante ler sobre o MaxEnt Classifier Module http://www.nltk.org/api/nltk.classify.html#module-nltk.classify.maxent

Para a classificação de mineração de texto, as etapas podem ser: pré-processamento (tokenização, vapor, seleção de recursos com ganho de informação ...), transformação em numérico (frequência ou TF-IDF) (acho que este é o passo principal a ser entendido ao usar texto como entrada para um algoritmo que aceita apenas numérico) e, em seguida, classifique-o com MaxEnt, com certeza este é apenas um exemplo.