가변 순서 마르코프 모델

Variable-order Markov model

확률 과정의 수학 이론에서 가변 순서 마코프(VOM) 모델은 잘 알려진 마코프 체인 모델을 확장하는 중요한 모델 등급이다.마르코프 속성이 있는 시퀀스의 각 랜덤 변수가 정해진 수의 랜덤 변수에 의존하는 마르코프 체인 모델과 대조적으로, VOM 모델에서 이 수의 조건화 랜덤 변수는 관찰된 특정 실현에 따라 달라질 수 있다.

이 실현 순서는 흔히 컨텍스트라고 불린다. 따라서 VOM 모델은 컨텍스트 트리라고도 불린다.[1]VOM 모델은 컬러화된 확률론적 접미사 트리(PST)에 의해 잘 렌더링된다.[2]조건화 랜덤 변수 수의 유연성은 통계 분석, 분류 및 예측과 같은 많은 응용 분야에서 실질적인 이점이 되고 있다.[3][4][5]

예

예를 들어, 각 변수가 3번째 알파벳 {a, b, c}에서 값을 가져오는 랜덤 변수의 순서를 생각해 보십시오.구체적으로, AAABCAABCAABC...라는 문자열을 고려하십시오.하위 문자열 AABC의 무한 연결로 구성된 AABC.

최대 순서 2의 VOM 모델은 다음과 같은 다섯 가지 조건부 확률 성분만을 사용하여 위의 문자열과 근사할 수 있다: {Pr(a aa) = 0.5, Pr(b aa) = 0.5, Pr(c b) = 1.0, Pr(a) = 1.0.

이 예에서 Pr(c ab) = Pr(c b) = 1.0이므로, 짧은 컨텍스트 b는 다음 문자를 결정하기에 충분하다.마찬가지로 최대 순서 3의 VOM 모델은 모두 1.0과 동일한 5개의 조건부 확률 성분만을 사용하여 정확히 문자열을 생성할 수 있다.

해당 문자열의 다음 문자에 대한 순서 1의 마르코프 체인을 구성하려면 다음과 같은 9가지 조건부 확률 성분을 추정해야 한다: {Pr(a a), Pr(a b), Pr(a c), Pr(b a), Pr(b c), Pr(c), Pr(c).다음 문자를 위한 순서 2의 마르코프 체인을 구성하려면 조건부 확률 성분인 {Pr(aa), Pr(a ab), ..., Pr(c)} 27개를 추정해야 한다.그리고 다음 문자에 대한 순서 3의 마르코프 체인을 구성하기 위해서는 다음과 같은 81개의 조건부 확률 성분을 추정해야 한다: {Pr(aaa), Pr(aab), ..., Pr(ccc).

실제 환경에서는 마르코프 체인의 순서가 증가함에 따라 기하급수적으로 증가하는 조건부 확률 요소의 수를 정확하게 추정하기에 충분한 데이터가 거의 없다.

가변 순서 마르코프 모델은 현실적인 설정에서 일부 과거 상태가 미래 상태로부터 독립된 상태(문맥으로 표현됨)의 특정 실현이 있다고 가정하고, 따라서 "모델 매개변수의 수를 크게 줄일 수 있다"[1]고 가정한다.

정의

A를 크기 의 상태 공간(마침표 )으로 설정하십시오

Consider a sequence with the Markov property of n realizations of random variables, where is the state (symbol) at position i , and the con상태 및 + 1 의 catenation은 + 1 로 표시된다

관찰된 상태의 훈련 집합인 을 주어진 과거(이전 관찰된 기호) 또는 미래 상태 순서로 각 상태에[3][4][5] 대한 확률 할당을 제공하는 모델 P를 학습한다

Specifically, the learner generates a conditional probability distribution for a symbol given a context , where the * sign represents a sequence of states of any length, including the empty context.

VOM 모델은 사용 가능한 통계량에 따라 컨텍스트 길이 s D 이(가 달라지는 형식의 조건부 분포를 추정하려고 시도한다.이와는 대조적으로, 기존의 마르코프 모델은 고정된 의 s = D s =를 가정하여 이러한 조건부 분포를 추정하려고 시도하며, 따라서 VOM 모델의 특별한 사례로 간주할 수 있다.

효과적으로, 주어진 훈련 순서에 대해, VOM 모델은 학습된 모델의 더 나은 분산-바이어스 트레이드오프로 이어지는 고정 순서 마르코프 모델보다 더 나은 모델 매개변수화를 얻는 것으로 확인된다.[3][4][5]

응용 영역

VOM 모델의 파라미터를 추정하기 위해 다양한 효율적인 알고리즘이 고안되었다.[4]

VOM 모델 성공적으로 기계, 정보 이론과 생물 정보학 학습 지역으로[1][3]통계적 프로세스 스팸 filtering,[7]haplotyping, control,[5]코딩과 데이터 compression,[1]문서 compression,[4]분류 및 DNA식별과 단백질 sequences,[6] 같은 특정한 애플리케이션을 포함하여 적용되었다.[8]연설 recognition,[9] 사회과학 분야에서의 시퀀스 분석 [2]등.

참고 항목

참조

  1. ^ a b c Rissanen, J. (Sep 1983). "A Universal Data Compression System". IEEE Transactions on Information Theory. 29 (5): 656–664. doi:10.1109/TIT.1983.1056741.
  2. ^ a b Gabadinho, Alexis; Ritschard, Gilbert (2016). "Analyzing State Sequences with Probabilistic Suffix Trees: The PST R Package". Journal of Statistical Software. 72 (3). doi:10.18637/jss.v072.i03. ISSN 1548-7660.
  3. ^ a b c d Shmilovici, A.; Ben-Gal, I. (2007). "Using a VOM Model for Reconstructing Potential Coding Regions in EST Sequences". Computational Statistics. 22 (1): 49–69. doi:10.1007/s00180-007-0021-8.
  4. ^ a b c d e Begleiter, R.; El-Yaniv, R.; Yona, G. (2004). "On Prediction Using Variable Order Markov models" (PDF). Journal of Artificial Intelligence Research. 22: 385–421. doi:10.1613/jair.1491. Archived from the original (PDF) on 2007-09-28. Retrieved 2007-04-22.
  5. ^ a b c d Ben-Gal, I.; Morag, G.; Shmilovici, A. (2003). "Context-Based Statistical Process Control: A Monitoring Procedure for State-Dependent Processes" (PDF). Technometrics. 45 (4): 293–311. doi:10.1198/004017003000000122. ISSN 0040-1706.
  6. ^ Grau J.; Ben-Gal I.; Posch S.; Grosse I. (2006). "VOMBAT: Prediction of Transcription Factor Binding Sites using Variable Order Bayesian Trees" (PDF). Nucleic Acids Research, vol. 34, issue W529–W533. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  7. ^ Bratko, A.; Cormack, G. V.; Filipic, B.; Lynam, T.; Zupan, B. (2006). "Spam Filtering Using Statistical Data Compression Models" (PDF). Journal of Machine Learning Research. 7: 2673–2698.
  8. ^ 브라우닝, 샤론 R. "변수 길이 마르코프 체인을 사용한 멀티로쿠스 연결 매핑"미국 인간 유전학 저널 78.6 (2006년) : 903–913.
  9. ^ Smith, A.; Denenberg, J.; Slack, T.; Tan, C.; Wohlford, R. (1985). "Application of a sequential pattern learning system to connected speech recognition". ICASSP '85. IEEE International Conference on Acoustics, Speech, and Signal Processing. Tampa, FL, USA: Institute of Electrical and Electronics Engineers. 10: 1201–1204. doi:10.1109/ICASSP.1985.1168282.