Por que otimizar a probabilidade máxima de log em vez da probabilidade

66

Na maioria das tarefas de aprendizado de máquina, nas quais é possível formular alguma probabilidade que deve ser maximizada, na verdade, otimizaríamos a probabilidade do log vez da probabilidade para alguns parâmetros . Por exemplo, no treinamento de probabilidade máxima, geralmente é a probabilidade de log. Ao fazer isso com algum método de gradiente, isso envolve um fator:pregistropθ

registropθ=1 1ppθ

Veja aqui ou aqui para alguns exemplos.

Obviamente, a otimização é equivalente, mas o gradiente será diferente, portanto, qualquer método baseado em gradiente se comportará diferente (especialmente métodos de gradiente estocástico). Existe alguma justificativa para que o gradiente funcione melhor que o gradiente ?registropp

Albert
fonte
3
você precisa observar que geralmente maximizamos a probabilidade usando derivativos. Por outro lado, em muitos casos, a condição de independência é aplicada, o que significa que a probabilidade é o produto de algumas funções de densidade de probabilidade iid. Além disso, o produto de muitos valores pequenos (no intervalo [0,1]) resulta em um valor muito pequeno. Isso resulta em uma dificuldade de computação.
TPArrow
@AlejandroRodriguez confira minha resposta aqui para obter mais detalhes.
Paul

Respostas:

65

Os métodos de gradiente geralmente funcionam melhor com a otimização de que porque o gradiente de geralmente é mais bem dimensionado . Ou seja, ele tem um tamanho que reflete de forma consistente e útil a geometria da função objetivo, facilitando a seleção de um tamanho de etapa apropriado e a otimização em menos etapas.p ( x ) log p ( x )registrop(x)p(x)registrop(x)

Para ver o que quer dizer, comparar o processo de optimização gradiente para e . Em qualquer ponto , o gradiente de éSe multiplicarmos por , obteremos o tamanho exato da etapa necessária para atingir o ideal global na origem, não importa o quef ( x ) = log p ( x ) = - x 2 x f ( x ) f ' ( x ) = - 2 x . 1 / 2 xp(x)=exp(-x2)f(x)=registrop(x)=-x2xf(x)

f(x)=-2x.
1 1/2xé. Isso significa que não precisamos trabalhar muito para obter um bom tamanho da etapa (ou "taxa de aprendizado" no jargão da ML). Não importa onde esteja nosso ponto inicial, basta definir nosso passo para metade do gradiente e estaremos na origem em um único passo. E se não soubermos o fator exato necessário, podemos escolher um tamanho de etapa em torno de 1, fazer uma pesquisa de linha e encontraremos um ótimo tamanho de etapa muito rapidamente, que funcione bem, não importa onde é. Essa propriedade é robusta para conversão e dimensionamento de f ( x ) . Embora a escala f ( x ) faça com que a escala ideal de etapas seja diferente de 1/2, pelo menos a escala de etapas será a mesma, independentemente de xxf(x)f(x)xé, portanto, precisamos encontrar apenas um parâmetro para obter um esquema de otimização baseado em gradiente eficiente.

Por outro lado, o gradiente de possui propriedades globais muito ruins para otimização. Temos p ( x ) = f ( x ) p ( x ) = - 2 x exp ( - x 2 ) . Isso multiplica o gradiente perfeitamente agradável e bem comportado - 2 x com um fator exp ( - x 2 ) que decai (mais rápido que) exponencialmente como xp(x)

p(x)=f(x)p(x)=-2xexp(-x2).
-2xexp(-x2)xaumenta. No , já temos exp ( - x 2 ) = 1,4 10 - 11 , de modo que um passo ao longo do gradiente de vector é de cerca de 10 - 11 vezes demasiado pequena. Para obter um tamanho de passo razoável em direção ao ótimo, teríamos que escalar o gradiente pelo inverso disso, uma constante enorme 10 11 . Um gradiente tão mal dimensionado é pior do que inútil para fins de otimização - seria melhor tentar apenas uma etapa unitária na direção da subida do que definir nossa etapa escalando contra p ( x )x=5exp(-x2)=1.410-1110-111011p(x)! (Em muitas variáveis, se torna um pouco mais útil, pois pelo menos obtemos informações direcionais do gradiente, mas o problema de dimensionamento permanece.)p(x)

Em geral, não há garantia de que o tenha excelentes propriedades de escala de gradiente como este exemplo de brinquedo, especialmente quando tivermos mais de uma variável. No entanto, para praticamente qualquer problema não trivial, o log p ( x ) será muito, muito melhor que o p ( x ) . Isso ocorre porque a probabilidade é de um grande produto com vários termos, e o log transforma esse produto em uma soma, conforme observado em várias outras respostas. Desde que os termos de probabilidade sejam bem comportados do ponto de vista da otimização, seu log geralmente é bem comportado e a soma de funções bem comportadas é bem comportada. Porregistrop(x)registrop(x)p(x)f(x)

Paulo
fonte
4
+1 Esta resposta traz à tona e enfatiza pontos que chegam ao cerne da questão.
whuber
47

Underflow

O computador usa uma representação de frações de ponto flutuante de dígito limitado, multiplicando tantas probabilidades que é garantida uma proximidade muito próxima de zero.

Com o , não temos esse problema.euog

Uri Goren
fonte
3
+1 para estabilidade numérica - essa e a resposta do Yuril devem ser uma!
Alec Teal
11
Você pode calcular o produto no espaço de log, tornando-o uma soma e depois transferi-lo de volta. Ou você calcula que é igual a . Portanto, a estabilidade numérica não é a questão. pregistropθppθ
Albert Albert
11
Lembre-se de que você mencionou é a multiplicação das probabilidades de todos os eventos da amostra é o elemento sujeito ao fluxo insuficiente. ppp
Uri Goren
5
@Filip A terminologia deste tópico é um pouco desaconselhada. Estamos discutindo densidades de probabilidade , não probabilidades. As densidades são arbitrárias: elas dependem das unidades de medida. Além disso, para tamanhos de amostra suficientes, a densidade de probabilidade de qualquer amostra simples de um modelo paramétrico será eventualmente menor que . Em grandes problemas (com milhões de dados), as densidades de probabilidade são rotineiramente ou menores. Mesmo uma amostra do tamanho da distribuição normal padrão é quase certa de ter uma densidade de probabilidade menor que . 2 - 1000000 80 2 - 1272-1272-1000000802-127
whuber
4
@FilipHaglund: whuber está correto, no entanto, o fato de suas densidades não serem a observação crucial aqui. Poderíamos estar discutindo um processo discreto e discutindo probabilidades reais (e, de fato, o OP não disse nada que excluísse este caso). Mas estamos falando de probabilidades de resultados muito específicos (por exemplo, um milhão de observações em um determinado sentido). Um único resultado específico é improvável, mas na inferência bayesiana as razões de probabilidades são importantes, portanto, precisamos saber quanto maior é uma probabilidade minúscula da outra.
Meni Rosenfeld 10/10
34
  1. O logaritmo da probabilidade de múltiplas probabilidades conjuntas simplifica a soma dos logaritmos das probabilidades individuais (e a regra da soma é mais fácil do que a regra do produto para diferenciação)

    registro(EuP(xEu))=Euregistro(P(xEu))

  2. O logaritmo de um membro da família de distribuições de probabilidade exponencial (que inclui o normal onipresente) é polinomial nos parâmetros (ou seja, a probabilidade máxima reduz os mínimos quadrados para distribuições normais)

    registro(exp(-1 12x2))=-1 12x2

  3. A última forma é mais numericamente estável e simbolicamente mais fácil de diferenciar do que a anterior.

  4. Por último, mas não menos importante, o logaritmo é uma transformação monotônica que preserva as localizações dos extremos (em particular, os parâmetros estimados em probabilidade máxima são idênticos para a formulação original e a transformação transformada em log)

TemplateRex
fonte
5
A razão 2 não pode ser estressada o suficiente. Para maximizar a probabilidade de log para um modelo linear com ruído gaussiano, basta resolver um problema de mínimos quadrados, o que equivale a resolver um sistema linear de equações.
Paul
ppθregistrop
@Albert o derivado de um polinómio é um polinómio de um grau inferior (em particular, quadrática vai para linear), ao passo que exponenciais não simplesmente sob diferenciação
TemplateRex
@TemplateRex: Sim, está claro. Mas estou perguntando sobre as propriedades de convergência em um método de gradiente estocástico.
Albert Albert
25

É muito mais fácil usar uma derivada da soma dos logaritmos do que usar uma derivada do produto, que contém, digamos, 100 multiplicadores.

Yurii
fonte
10
Além disso, você reduz possíveis problemas numéricos quando os termos se tornam muito pequenos ou grandes.
Björn
8
Pelo contrário, o OP implicitamente fornece uma excelente maneira de calcular a derivada de qualquer produto de funções não-negativas: multiplique a soma das derivadas dos logs pelo próprio produto. (Essa multiplicação é melhor realizada em termos de logaritmos, o que elimina também os problemas numéricos mencionados no comentário de @ Björn.) Assim, a "facilidade" não oferece nenhum poder explicativo real, nem aborda a questão mais significativa sobre a comparação dos gradientes. .
whuber
10

Como regra geral, o problema de otimização mais básico e fácil é otimizar uma função quadrática. Você pode encontrar facilmente o melhor de uma função, não importa por onde começar. Como isso se manifesta depende do método específico, mas quanto mais próxima sua função de uma quadrática, melhor.

Conforme observado por TemplateRex, em uma ampla variedade de problemas, as probabilidades que entram no cálculo da função de probabilidade provêm da distribuição normal ou são aproximadas por ela. Portanto, se você trabalha no log, obtém uma boa função quadrática. Considerando que, se você trabalha com as probabilidades, tem uma função que

  1. Não é convexo (a desgraça dos algoritmos de otimização em todos os lugares)
  2. Atravessa várias escalas rapidamente e, portanto, possui um intervalo muito estreito, onde os valores das funções são indicativos de onde direcionar sua pesquisa.

Qual função você prefere otimizar, isso ou aquilo ?

(Na verdade, foi fácil; em aplicações práticas, sua pesquisa pode começar tão longe do ideal que os valores e gradientes da função, mesmo que você possa calculá-los numericamente, sejam indistinguíveis de 0 e inúteis para os propósitos da otimização. Mas a transformação para uma função quadrática torna isso um pedaço de bolo.)

Observe que isso é completamente consistente com os problemas de estabilidade numérica já mencionados. O motivo pelo qual a escala do log é necessária para trabalhar com essa função é exatamente o mesmo motivo pelo qual a probabilidade do log é muito melhor comportada (para otimização e outros fins) do que a original.

Você também pode abordar isso de outra maneira. Mesmo se não houvesse vantagem no log (o que existe) - usaremos a escala de log de qualquer maneira para derivações e cálculos; então, por que motivo aplicar a transformação exp apenas para calcular o gradiente? Também podemos permanecer consistentes com o registro.

Meni Rosenfeld
fonte
@TemplateRex: o log de uma função positiva convexa (para baixo) é convexo, mas o inverso não é verdadeiro. As probabilidades não são convexas, portanto não têm nada a preservar, mas o log é convexo. Veja os gráficos que vinculei - exp (-10x ^ 2) obviamente não é convexa, mas -10x ^ 2 é.
Meni Rosenfeld
4

emppL(x|θ)=Πi=1nf(xi|θ)f(.)

nL(.)euf(.)n

Ao fazer um log, simplesmente melhoramos a faixa dinâmica de qualquer algoritmo de otimização, permitindo que ele trabalhe com valores extremamente grandes ou pequenos da mesma maneira.

Aksakal
fonte
0

Algumas respostas legais já foram dadas. Mas eu encontrei recentemente um novo:

Xp(x|θ)xX

p(X|θ)=xXp(x|θ).
eueu(X|θ)XX
θ: =θ-xXeu(x|θ)θ.
eu(X|θ)=xXeu(x|θ).
eu(x|θ)=-registrop(x|θ).

Albert
fonte