O que significa uma distribuição 'tratável'?

13

Por exemplo, em redes contraditórias generativas, geralmente ouvimos que a inferência é fácil porque a distribuição condicional de x dada a variável latente z é 'tratável'. Além disso, li em algum lugar que a máquina Boltzmann e o autoencoder variacional são usados ​​onde a distribuição posterior não é tratável, portanto é necessário aplicar algum tipo de aproximação. Alguém poderia me dizer o que significa 'tratável', em uma definição rigorosa? Ou alguém poderia explicar em qualquer um dos exemplos que eu dei acima, o que tratável significa exatamente nesse contexto?

sirius27
fonte
Isso é relevante.
Greenparker
11
Significa simplesmente que você é capaz de lidar com os cálculos relevantes com a distribuição. Então, o que é "tratável" se expande com o tempo!
Kjetil b halvorsen

Respostas:

10

Para minha melhor memória, nunca encontrei uma definição formal para isso em um texto estatístico, mas acho que você pode costurar uma em algumas leituras contextuais. Comece com a análise de dados bayesiana , p. 261:

A computação bayesiana gira em torno de duas etapas: computação da distribuição posterior, , e computação da distribuição preditiva posterior, . Até agora, consideramos exemplos em que estes poderiam ser computados analiticamente de forma fechada [.]p(θ|y)p(y^|y)

O obstáculo é geralmente a probabilidade marginal, o denominador no lado direito da regra de Bayes, que pode envolver uma integral que não pode ser expressa analiticamente. Para mais, acho que você achará o artigo do wiki sobre expressão de formulário fechado útil para o contexto (ênfase minha):

Em matemática, uma expressão de forma fechada é uma expressão matemática que pode ser avaliada em um número finito de operações. Pode conter constantes, variáveis, certas operações "conhecidas" (por exemplo, + - × ÷) e funções (por exemplo, enésima raiz, expoente, logaritmo, funções trigonométricas e funções hiperbólicas inversas), mas geralmente sem limite. O conjunto de operações e funções admitidas em uma expressão de forma fechada pode variar de acordo com o autor e o contexto .

Diz- se que os problemas são tratáveis ​​se puderem ser resolvidos em termos de uma expressão de forma fechada .

Se você continuar lendo, verá uma tabela de classes de expressões e "Expressões analíticas" inclui várias envolvidas nas constantes de normalização das distribuições exponenciais da família. Por exemplo, a função gama na distribuição gama e a função Bessel no von-Mises Fisher.

Ou seja, estamos dispostos a admitir pelo menos isso em nossa definição de "tratabilidade". (Pode haver outras distribuições que envolvam as classes de operações classificadas como "expressões analíticas"; confesso que não estou familiarizado.)

Sean Easter
fonte
11
Esta é uma ótima resposta, +1. Para alguma indicação do que "tratável" poderia significar mais de um século atrás, navegue pela segunda metade de Whittaker & Watson, Um curso de análise moderna . As funções Gamma e Bessel são apenas a ponta do iceberg.
whuber
11
@ whuber On Whittaker e Watson: GN Watson tem um pequeno lugar na história das estatísticas como derivado de uma obrigação de curtose em nome de Karl Pearson. ET Whittaker tem um maior como pai de suavizar splines avant la lettre .
Nick Cox
@whuber Muito obrigado! Este post recebeu vários votos positivos na época do seu comentário, que tomo como evidência anedótica de um "Huber Bump".
Sean Páscoa
3

Além da resposta de Sean Easter, tentarei lançar alguma luz da perspectiva do custo computacional.

Primeiro, vamos definir o que são problemas tratáveis ​​e intratáveis ​​(Referência: http://www.cs.ucc.ie/~dgb/courses/toc/handout29.pdf ).

Problema tratável: um problema solucionável por um algoritmo de tempo polinomial. O limite superior é polinomial.

Problema intratável: um problema que não pode ser resolvido por um algoritmo de tempo polinomial. O limite inferior é exponencial.

Nesta perspectiva, uma definição para distribuição tratável é que leva tempo polinomial para calcular a probabilidade dessa distribuição em qualquer ponto.

Se uma distribuição está em uma expressão de forma fechada, a probabilidade dessa distribuição pode definitivamente ser calculada em tempo polinomial, o que, no mundo da academia, significa que a distribuição é tratável. Distribuições intratáveis ​​levam tempo igual ou superior ao tempo exponencial, o que geralmente significa que, com os recursos computacionais existentes, nunca podemos calcular a probabilidade em um determinado ponto com tempo relativamente "curto" (qualquer tempo maior que o tempo polinomial é longo ... )

aysljc
fonte
0

Uma distribuição é chamada tratável se qualquer probabilidade marginal induzida por ela puder ser calculada em tempo linear

malocho
fonte
11
Você está citando alguma referência ou autoridade? Essa é uma caracterização intrigante, mas surpreendente, portanto, alguma indicação de onde ela vem e seu escopo de aplicabilidade seria interessante.
whuber
2
Eu encontrei a fonte onde eu tê-lo de "On Usando Soma-Product Networks Para Multi-etiqueta de classificação" por Julissa Villanueva Llerena e Denis Deratani Mauá
malocho