Comments

2 responses to “hidden Markov models”

1. 

   trax

   October 16, 2004

   음… 그거 보던 생각이 나네요. 이해도 안되면서 연속적인 수식들의 압박속에서 보았던 알고리즘 책이었었는데…
   HMM말고… Hidden Markov Chain Model이라는 것도 있지 않았나… 기억이 안나… 내 머린 썩고 있는게야…
   학점 3.0안되고, 전공 바꾸려니 취직도 안돼.. 대학원도 짤려… 욱욱…(연세대도 내는데… 짤리던 재수생이려나..)

   근데, 공업수학 쪽에서도 HMM이 나오는데… 어차피 행렬로 식을 쭈욱 풀기 때문에…
   즉, 초기의 행렬 시드 값을 통해서 현재 시간 이후로 행해지는 결과들에 대한 연쇄적인 반응들을 모델링하기 위한 것. 정도라고 하면 정확한 정의가 될까? ㅎㅎ
   복잡한 확률을 따질 필요없이 정해진 대로 행렬 돌려서 나오면 그 결과만 보면 되니까 편하겠다라는 생각…
   (방정식 푸는 것보단 편하니까….) 라고 생각하지만…

   확률분포에서도 Markov와 Chernoff의 한계 부등식…

   논문에선 대충 어떤 쪽일까…

   하지만, 그 수학 문제를 풀면서도, 답을 써내면서도 품는 의문은 하나.
   토지 이용률의 변화(주거지, 공장지, 상업지)를 추적하는데 있어 이런 것들을 푸는 건 한다고 할 수 있지만, 현실에서는 그게 얼마나 적용되는걸까? 라는 것.

   음… 이름만 Markov이고… 전혀 다른 분야를 바라보는 걸까? 아니라면 답을~~

2. 

   민구

   October 16, 2004

   Markov chain 이 있고, hidden Markov models 가 있어요. 용어는 좀 제각각인거 같은데 (Markov process라던가.)..

   생물학에서는 생물학적 현상의 비밀을 며느리도 모르기때문에 이런 확률 모델에 많이 의존을 하죠. 어차피 모르니까 잘 모델링 해보자 이런 것이예요..

   사실은 제가 하고자하는걸 쓰면 안되는데.. ㅋㅋㅋ (confidential이잖아요.)

   어차피 이루지 못할 거 같으니까 그냥 말하자면, 단백질 family 를 구분짓는 모티프/프로파일을 작성할때 hidden markov model(HMM)이 사용되요. 그럼 임의의 단백질(DNA도 상관없음) 시퀀스가 왔을때 얘가 어떤 family에 속하는지를 결정해야겠죠. 이걸 하기 위해서 HMM 상에서 그 시퀀스가 나올 확률 P(x)를 구하면, x 가 그 family를 나타내는 HMM과 매치되는 정도가 나오죠. 즉 x가 그 family에 속하는 정도가 나오는 거죠.

   그리고 P(x) 를 구하는 방법은 2가지로 forward algorithm 과 viterbi algorithm 이 있어요. Intel 등에서는 viterbi를 parallelize 해서 2-fold speed up 했다고 하지만 이건 어디까지나 하드웨어 상의 이야기이고..

   제가 하고자 하는 건, 단백질 sequence의 데이터베이스가 주어져 있을 때, 임의의 HMM 이 주어졌을 때 모든 시퀀스를 이 HMM에 넣어서 P(x) desc 순서대로 정렬하는 게 있어요..
   그러니까 HMM을 넣으면 이 HMM에 가장 잘 맞는 순서대로 시퀀스를 출력하는 거죠.

   이걸 해주는 프로그램이 HMMER 내에 hmmsw 이라고 있는데, 생물학에서 hidden Markov model 쪽 논문을 많이 쓴 사람이 개발했어요. (이름도 특이해서 안잊어버림 Eddy – 철권 캐릭터랑 동명 -_-;)

   하지만 제가 생각하기엔 아마 hmmsw이란게 굉장히 솔직하게 viterbi 나 forward algorithm을 일일히 적용해서 P(x)를 구하는 것 같아요. (정확한건 소스 열어봐야 알겠지만..)

   그렇다면, 그렇게 솔직히 구하지 말고 미리 모든 시퀀스에 대한 어떤 종류의 인덱스를 사전에 구축함으로써 hmmsw 보다 더 빠르게 P(x) desc 한 결과를 구할 수 있지 않을까 하는게 goal 이예요..

   이건 쉽지가 않죠.. 왜냐하면 P(x)를 구하는 방법중 viterbi의 경우 P(x|best path) 를 구하는데, 이 best path 라는게 시퀀스 x와 HMM자체에 의존하므로 질의인 HMM이 결정되지 않은 상태에서 미리 best path를 구할 수는 없죠.

   forward algorithm 역시 마찬가지로 모든 path에 대해서 시퀀스 x를 따져가면서 P(x)를 구하는데 모든 path 를 나열하는 것 자체가 exponential time이 걸리고, 구해야할 모든 HMM의 path 역시 사전에 결정할 수가 없죠. 왜냐면 질의가 HMM으로 주어지는거니까, 질의에 대해서 미리 인덱스를 만들수는 없잖아요…..

   이래저래 쉽게 할 수는 없을거라고 생각하지만, 이와 유사한 문제를 다른 도메인에서 풀어놓은걸 찾았기 때문에 일단은 다른 도메인에서 풀어놓은걸 공부해볼 생각입니다..

   제가 참고하는 책은 Biological Sequence Analysis: Probablistic Models of Proteins and Nucleic Acids 이고요.. MIT에서도 마찬가지로 확률 모델을 사용한 생물학 시퀀스 분석 책을 펴냈는데 (부제가 machine learning approach임) yes24에서 12만원이고 해외주문해도 8만원가량 되서 돈없어서 못사겠네요.. ㅠㅠ

   이 부분에 흥미를 느끼는 이유는, 일단 HMM이라는게 제가 neural network(NN)을 잘 몰라서일수도 있지만, NN 보다는 쉬운거 같고 (기본은 결국 조건부 확률일뿐이니까..), 앞으로 써먹을 곳이 많을거 같아서임다.. 가령 IR(Information Retrieval) 같은 쪽에.. 사실 석사 진학하면 아무래도 IR하게 될 것 같아서 내친김에 확률이나 통계 관련된 쪽을 하려고 계획적으로(?) 이런 토픽을 선택했어요.