Comprimento mínimo da mensagem - Minimum message length
O comprimento mínimo da mensagem (MML) é um método da teoria da informação bayesiana para comparação e seleção de modelos estatísticos. Ele fornece uma reformulação da teoria da informação formal da Navalha de Occam : mesmo quando os modelos são iguais em sua medida de precisão de ajuste aos dados observados, aquele que gera a explicação mais concisa dos dados é mais provável de ser correto (onde a explicação consiste no declaração do modelo, seguida pela codificação sem perdas dos dados usando o modelo declarado). O MML foi inventado por Chris Wallace , aparecendo pela primeira vez no artigo seminal "Uma medida de informação para classificação". O MML pretende ser não apenas uma construção teórica, mas uma técnica que pode ser implantada na prática. Ele difere do conceito relacionado de complexidade de Kolmogorov porque não requer o uso de uma linguagem de Turing-completa para modelar dados.
Definição
Shannon 's uma teoria matemática de Comunicação (1948) afirma que um código óptimo, o comprimento da mensagem (em binário) de um evento , onde tem probabilidade , é dada por .
O teorema de Bayes afirma que a probabilidade de uma hipótese (variável) dada evidência fixa é proporcional a , que, pela definição de probabilidade condicional , é igual a . Queremos o modelo (hipótese) com a maior probabilidade posterior . Suponha que codifiquemos uma mensagem que representa (descreve) o modelo e os dados em conjunto. Desde então , o modelo mais provável terá a mensagem mais curta. A mensagem quebra em duas partes: . A primeira parte codifica o próprio modelo. A segunda parte contém informações (por exemplo, valores de parâmetros ou condições iniciais, etc.) que, quando processadas pelo modelo, produzem os dados observados.
A MML troca de maneira natural e precisa a complexidade do modelo pela qualidade do ajuste. Um modelo mais complicado leva mais tempo para ser declarado (primeira parte mais longa), mas provavelmente se ajusta melhor aos dados (segunda parte mais curta). Portanto, uma métrica MML não escolherá um modelo complicado, a menos que esse modelo se pague.
Parâmetros de valor contínuo
Uma razão pela qual um modelo pode ser mais longo seria simplesmente porque seus vários parâmetros são declarados com maior precisão, exigindo assim a transmissão de mais dígitos. Muito do poder do MML deriva de sua manipulação de quão acuradamente os parâmetros de estado em um modelo e uma variedade de aproximações que tornam isso viável na prática. Isso permite comparar de forma útil, digamos, um modelo com muitos parâmetros declarados de forma imprecisa em relação a um modelo com menos parâmetros declarados de forma mais precisa.
Principais recursos do MML
- O MML pode ser usado para comparar modelos de estruturas diferentes. Por exemplo, sua primeira aplicação foi encontrar modelos de mistura com o número ideal de classes. Adicionar classes extras a um modelo de mistura sempre permitirá que os dados sejam ajustados com maior precisão, mas de acordo com o MML, isso deve ser pesado em relação aos bits extras necessários para codificar os parâmetros que definem essas classes.
- MML é um método de comparação de modelos bayesianos . Dá uma pontuação a cada modelo.
- MML é invariável em escala e estatisticamente invariante. Ao contrário de muitos métodos de seleção Bayesianos, o MML não se importa se você muda da medição do comprimento para o volume ou das coordenadas cartesianas para as coordenadas polares.
- MML é estatisticamente consistente. Para problemas como o problema de Neyman-Scott (1948) ou análise fatorial em que a quantidade de dados por parâmetro é limitada acima, o MML pode estimar todos os parâmetros com consistência estatística .
- O MML é responsável pela precisão da medição. Ele usa a informação de Fisher (na aproximação de Wallace-Freeman 1987, ou outros hipervolumes em outras aproximações ) para discretizar parâmetros contínuos de forma otimizada. Portanto, a posterior é sempre uma probabilidade, não uma densidade de probabilidade.
- MML está em uso desde 1968. Esquemas de codificação MML foram desenvolvidos para várias distribuições e muitos tipos de alunos de máquina, incluindo classificação não supervisionada, árvores de decisão e gráficos, sequências de DNA, redes Bayesianas , redes neurais (uma camada apenas até agora), compressão de imagem, segmentação de imagem e função, etc.
Veja também
- Probabilidade algorítmica
- Teoria da Informação Algorítmica
- Indução gramatical
- Inferência indutiva
- Probabilidade indutiva
- Complexidade de Kolmogorov - complexidade absoluta (dentro de uma constante, dependendo da escolha particular da Máquina de Turing Universal ); MML é normalmente uma aproximação computável (consulte)
- Comprimento mínimo da descrição - uma alternativa com uma motivação possivelmente diferente (não bayesiana), desenvolvida 10 anos após o MML.
- Navalha de Occam
Referências
links externos
Publicação Original:
- Wallace; Boulton (agosto de 1968). "Uma medida de informação para classificação" . Computer Journal . 11 (2): 185–194. doi : 10.1093 / comjnl / 11.2.185 .
Livros:
- Wallace, CS (maio de 2005). Inferência estatística e indutiva por comprimento mínimo de mensagem . Ciência da Informação e Estatística. Springer-Verlag. ISBN 978-0-387-23795-4 . CS1 maint: parâmetro desencorajado ( link )
- Allison, L. (2018). Codificando a Navalha de Ockham . Springer. doi : 10.1007 / 978-3-319-76433-7 . ISBN 978-3319764320 . S2CID 19136282 . , na implementação de MML e código-fonte .
Links Relacionados:
- Links para todas as publicações conhecidas de Chris Wallace .
- Um banco de dados pesquisável das publicações de Chris Wallace .
- Wallace, CS; Dowe, DL (1999). "Comprimento mínimo da mensagem e complexidade de Kolmogorov". Computer Journal . 42 (4): 270–283. CiteSeerX 10.1.1.17.321 . doi : 10.1093 / comjnl / 42.4.270 .
- "Edição especial sobre a complexidade de Kolmogorov" . Computer Journal . 42 (4). 1999.
- Dowe, DL; Wallace, CS (1997). Resolvendo o problema de Neyman-Scott pelo comprimento mínimo da mensagem . 28º Simpósio sobre a interface, Sydney, Austrália. Ciência da computação e estatística . 28 . pp. 614–618.
- História do MML, a última palestra de CSW .
- Needham, S .; Dowe, D. (2001). O comprimento da mensagem como uma navalha de Ockham eficaz na indução da árvore de decisão (PDF) . Proc. 8º Workshop Internacional de IA e Estatística . pp. 253–260. (Mostra como a navalha de Occam funciona bem quando interpretada como MML.)
- Allison, L. (janeiro de 2005). “Modelos para aprendizado de máquina e mineração de dados em programação funcional”. Journal of Functional Programming . 15 (1): 15–32. doi : 10.1017 / S0956796804005301 . S2CID 5218889 . ( Código MML, FP e Haskell ).
- Comley, JW; Dowe, DL (abril de 2005). "Capítulo 11: Comprimento mínimo da mensagem, MDL e redes bayesianas generalizadas com linguagens assimétricas" . Em Grunwald, P .; Pitt, MA; Myung, IJ (eds.). Avanços no comprimento mínimo de descrição: teoria e aplicações . MIT Press. pp. 265–294. ISBN 978-0-262-07262-5 .
- Comley, Joshua W .; Dowe, DL (5–8 de junho de 2003). Redes Bayesianas Gerais e Linguagens Assimétricas . Proc. 2ª Conferência Internacional do Havaí sobre Estatística e Campos Relacionados. , .pdf . Comley & Dowe ( 2003 , 2005 ) são os primeiros dois artigos sobre redes MML Bayesianas usando parâmetros de valor discretos e contínuos.
- Dowe, David L. (2010). "MML, modelos gráficos de rede Bayesiana híbrida, consistência estatística, invariância e exclusividade" (PDF) . Handbook of Philosophy of Science (Volume 7: Handbook of Philosophy of Statistics) . Elsevier. pp. 901–982. ISBN 978-0-444-51862-0 .
- Comprimento mínimo da mensagem (MML) , introdução ao MML de LA, (MML alt.) .
- Comprimento mínimo da mensagem (MML), pesquisadores e links .
- "Outro site de pesquisa do MML" . Arquivado do original em 12 de abril de 2017.
- Página Snob para modelagem de mistura MML .
- MITECS : Chris Wallace escreveu uma entrada no MML para MITECS. (Requer conta)
- mikko.ps : Pequenos slides introdutórios de Mikko Koivisto em Helsinque
- Método de seleção de modelo de critério de informação de Akaike ( AIC ) e uma comparação com MML: Dowe, DL; Gardner, S .; Oppy, G. (dezembro de 2007). "Bayes não rebenta! Porque a simplicidade não é problema para os bayesianos". Br. J. Philos. Sci . 58 (4): 709–754. doi : 10.1093 / bjps / axm033 .