최소 메시지 길이

최소 메시지 길이(MML)는 통계적 모델 비교 및 선택을 위한 베이지안 정보-이론적 방법이다.^[1] 그것은 Ocam's Razor의 형식 정보 이론 재작성을 제공한다: 모델이 관측된 데이터에 대한 적합성 측도에서 동일할 때에도, 데이터에 대한 가장 간결한 설명을 생성하는 것은 정확할 가능성이 더 높다(해설이 모델의 문장으로 구성되고, 그 다음에 데이터 usi의 무손실 인코딩이 뒤따른다).명시된 모델 ng). MML은 크리스 월리스에 의해 발명되었는데, 최초로 세미날 논문 "분류를 위한 정보 측정"에 실렸다.^[2] MML은 단순히 이론적 구성으로서가 아니라 실제로 배치될 수 있는 기법으로서 의도된 것이다.^[3] 데이터를 모델링하기 위해 튜링 완성 언어를 사용할 필요가 없다는 점에서 Kolmogorov 복잡성의 관련 개념과 다르다.^[4]

정의

Shannon's A Mathematical Theory of Communication (1948) states that in an optimal code, the message length (in binary) of an event ${\displaystyle E}$, ${\displaystyle \operatorname {length} (E)}$, where ${\displaystyle E}$ has probability ${\displaystyle P(E)}$, is given by ${\displaystyle \mathrm{length}(E)=-}$${\displaystyle {\mathrm{로그}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$⁡${\displaystyle }$(${\displaystyle P}$( ${\displaystyle E}$ )${\displaystyle \operatorname {length}(E)=-\log _{2}(P(E)})}$.

Bayes's theorem states that the probability of a (variable) hypothesis ${\displaystyle H}$ given fixed evidence ${\displaystyle E}$ is proportional to ${\displaystyle P(E H)P(H)}$, which, by the definition of conditional probability, is equal to ${\displaystyle P(H\land E)}$. We want the 그러한 가장 높은 후방 확률을 가진 모델(iii) 모델과 데이터 모두를 나타내는 메시지를 (설명) 인코딩한다고 가정합시다. ${\displaystyle \mathrm{길이}}$ ${\displaystyle }$(${\displaystyle H}$ ${\displaystyle \wedge }$ ${\displaystyle E}$)${\displaystyle }$=${\displaystyle }$- ${\displaystyle {\log }_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}}$(${\displaystyle P}$ (${\displaystyle H\wedge }$ ${\displaystyle E}$)${\displaystyle }$) ${\displaystyle \operatorname {length}(H\land E)=-\log _{2}(P(H\land$ E$)\})\},$ 가장 가능성이 높은 모델이 그러한 메시지를 가장 짧은 것으로 예상된다. The message breaks into two parts: ${\displaystyle -\log _{2}(P(H\land E))=-\log _{2}(P(H))+-\log _{2}(P(E H))}$. The first part encodes the model itself. 두 번째 부분에는 모델에 의해 처리되었을 때 관측된 데이터를 출력하는 정보(예: 매개변수 값 또는 초기 조건 등)가 수록되어 있다.

MML은 모델 복잡성을 적합도와 자연스럽고 정밀하게 교환한다. 더 복잡한 모델은 진술하는 데 더 오래 걸리지만(첫 번째 부분은 더 길다) 아마도 데이터에 더 잘 맞을 것이다(두 번째 부분). 따라서 MML 메트릭스는 그 모델이 스스로 비용을 지불하지 않는 한 복잡한 모델을 선택하지 않을 것이다.

연속 값 매개변수

모델이 더 길어질 수 있는 한 가지 이유는 단순히 다양한 매개변수가 더 정밀하게 명시되어 있어서 더 많은 숫자의 전송이 필요하기 때문일 것이다. MML의 힘은 모델에서 매개변수를 얼마나 정확하게 기술할 것인가와 이를 실현하는 다양한 근사치를 취급하는 데서 기인한다. 이를 통해 많은 매개변수가 부정확하게 기술된 모델을 보다 정확하게 기술된 매개변수가 적은 모델과 유용하게 비교할 수 있다.

MML의 주요 특징

• MML은 다른 구조의 모델을 비교하는 데 사용될 수 있다. 예를 들어, 그것의 초기 적용 분야는 최적의 클래스 수를 가진 혼합물 모델을 찾는 것이었다. 혼합물 모델에 추가 클래스를 추가하면 데이터가 항상 더 정확하게 적합될 수 있지만 MML에 따르면 이러한 클래스를 정의하는 파라미터를 인코딩하는 데 필요한 추가 비트에 대해 가중치를 적용해야 한다.
• MML은 베이시안 모델 비교의 방법이다. 그것은 모든 모델에게 점수를 준다.
• MML은 스케일 인바리어스, 통계적으로 불변한다. 많은 베이지안 선택 방법과 달리 MML은 측정 길이에서 부피로, 또는 데카르트 좌표에서 극좌표로 변경해도 상관하지 않는다.
• MML은 통계적으로 일관성이 있다. Neyman-Scott(1948) 문제나 매개변수당 데이터 양이 위의 경계를 이루는 요인 분석과 같은 문제에 대해 MML은 통계적 일관성을 가진 모든 매개변수를 추정할 수 있다.
• MML은 측정 정밀도를 설명한다. 연속 파라미터의 최적화를 위해 피셔 정보(Wallace-Freeman 1987 근사치 또는 기타 근사치의 하이퍼볼륨)를 사용한다. 따라서 후부는 확률밀도가 아니라 항상 확률이다.
• MML은 1968년부터 사용되어 왔다. MML 코딩 체계는 여러 배포에 대해 개발되었으며, 감독되지 않은 분류, 의사결정 나무와 그래프, DNA 시퀀스, 베이시안 네트워크, 신경 네트워크(현재까지 1계층만), 이미지 압축, 이미지 및 기능 분할 등을 포함한 많은 종류의 기계 학습자가 개발되었다.

참고 항목

• 알고리즘 확률
• 알고리즘 정보 이론
• 문법 유도
• 귀납적 추론
• 귀납 확률
• Kolmogorov 복잡성 – 절대적 복잡성(유니버설 튜링 머신의 특정 선택에 따라 상수 내); MML은 일반적으로 계산 가능한 근사치( 참조)이다.
• 최소 설명 길이 – MML 이후 10년 동안 개발된 (비 베이시안) 동기가 다를 수 있는 대안.
• 오캄 면도기

참조

외부 링크

원본 게시:

• Wallace; Boulton (August 1968). "An information measure for classification". Computer Journal. 11 (2): 185–194. doi:10.1093/comjnl/11.2.185.

책:

• Wallace, C.S. (May 2005). Statistical and Inductive Inference by Minimum Message Length. Information Science and Statistics. Springer-Verlag. ISBN 978-0-387-23795-4.
• Allison, L. (2018). Coding Ockham's Razor. Springer. doi:10.1007/978-3-319-76433-7. ISBN 978-3319764320. S2CID 19136282., MML 및 소스 코드 구현에 대해.

관련 링크:

• 크리스 월리스의 알려진 모든 출판물에 대한 링크.
• 크리스 월리스의 출판물에 대한 검색 가능한 데이터베이스.
• Wallace, C.S.; Dowe, D.L. (1999). "Minimum Message Length and Kolmogorov Complexity". Computer Journal. 42 (4): 270–283. CiteSeerX 10.1.1.17.321. doi:10.1093/comjnl/42.4.270.
• "Special Issue on Kolmogorov Complexity". Computer Journal. 42 (4). 1999.^{[데드링크]}
• Dowe, D.L.; Wallace, C.S. (1997). Resolving the Neyman-Scott Problem by Minimum Message Length. 28th Symposium on the interface, Sydney, Australia. Computing Science and Statistics. Vol. 28. pp. 614–618.
• MML의 역사, CSW의 마지막 대화.
• Needham, S.; Dowe, D. (2001). Message Length as an Effective Ockham's Razor in Decision Tree Induction (PDF). Proc. 8th International Workshop on AI and Statistics. pp. 253–260. (MML로 해석될 때 Occam의 면도기가 어떻게 잘 작동하는지를 보여준다.)
• Allison, L. (Jan 2005). "Models for machine learning and data mining in functional programming". Journal of Functional Programming. 15 (1): 15–32. doi:10.1017/S0956796804005301. S2CID 5218889. (MML, FP, Haskell 코드).
• Comley, J.W.; Dowe, D.L. (April 2005). "Chapter 11: Minimum Message Length, MDL and Generalised Bayesian Networks with Asymmetric Languages". In Grunwald, P.; Pitt, M. A.; Myung, I. J. (eds.). Advances in Minimum Description Length: Theory and Applications. M.I.T. Press. pp. 265–294. ISBN 978-0-262-07262-5.
• Comley, Joshua W.; Dowe, D.L. (5–8 June 2003). General Bayesian Networks and Asymmetric Languages. Proc. 2nd Hawaii International Conference on Statistics and Related Fields., .pdf. Comley & Dowe(2003, 2005년)는 이산 및 연속 가치 매개변수를 모두 사용하는 MML 베이지안 네트에 대한 최초의 두 개의 논문이다.

• Dowe, David L. (2010). "MML, hybrid Bayesian network graphical models, statistical consistency, invariance and uniqueness" (PDF). Handbook of Philosophy of Science (Volume 7: Handbook of Philosophy of Statistics). Elsevier. pp. 901–982. ISBN 978-0-444-51862-0.
• 최소 메시지 길이(MML), LA의 MML 소개(MML alt).
• 최소 메시지 길이(MML), 연구자 및 링크
• "Another MML research website". Archived from the original on 12 April 2017.
• MML 혼합물 모델링용 속물 페이지.
• MITECS: Chris Wallace가 MML에 MITECS에 대한 항목을 작성했다. (계정 필요)
• mikko.ps: Helsinki에 있는 Mikko Koivisto의 짧은 소개 슬라이드
• Akaike 정보 기준(AIC) 모델 선택 방법 및 MML과의 비교: