การปรับปรุงประสิทธิภาพของ Hidden Markov Models

ผมใกล้ต้องส่งการบ้านอีกแล้วและคราวนี้เป็นการทบทวนวรรณกรรมครับ คือแบบว่า การจะทำวิจัยต้องมีการทบทวนวรรณกรรมก่อนครับ เพื่อตรวจสอบว่ามีนักวิจัยท่านอื่นได้วิจัยในหัวข้อที่เราสนใจไปบ้างหรือเปล่า และการวิจัยเหล่านั้นได้ก้าวหน้าไปถึงไหนแล้ว เพื่อให้เราได้วิจัยส่วนที่เป็นช่องโหว่ให้ครบถ้วนสมบูรณ์ต่อไป

ส่วนตัวผมเองก็รู้ทฤษฎีการคำนวณสำหรับคอมพิวเตอร์เพียงไม่กี่เรื่องครับ ดังนั้น ก็เลยต้องเลือกทบทวนวรรณกรรมในหัวข้อที่ตนเองถนัดที่สุด นั่นคือ แบบจำลองทางสถิติที่ชื่อว่า Hidden Markov Models และเพื่อให้ไม่เป็นการเสียเวลา มาลองอ่านงานทบทวนวรรณกรรมฉบับร่างของผมดูกันครับ

ทบทวนวรรณกรรม

นับตั้งแต่งานวิจัย Hidden Markov Model [1][2][3][4] ซึ่งเป็นโมเดลที่เหมาะกับการอนุมานความน่าจะเป็นของลำดับที่ซ่อนอยู่ โดยการวิเคราะห์จากลำดับที่สังเกตได้ ๆ ถูกตีพิมพ์เผยแพร่ออกสู่สาธารณชน และ มีงานวิจัย [5][6][7] ที่ได้บุกเบิกนำ Hidden Markov Models มาปรับใช้สำหรับงานด้าน Speech Recognition เพื่อเปรียบเทียบระหว่างเสียงพูดกับชุดข้อความอย่างมีประสิทธิภาพ ก็ได้ทำให้ Hidden Markov Models กลายเป็นโมเดลที่ถูกประยุกต์ใช้อย่างกว้างขวาง ในการแก้ปัญหาต่าง ๆ ที่เกี่ยวกับการอนุมานความน่าจะเป็นของลำดับที่ซ่อนอยู่ โดยการวิเคราะห์จากลำดับที่สังเกตได้ เช่น งานวิจัย [8] การจับคู่สายรหัสพันธุกรรม ซึ่งเป็นงานด้าน Bioinformatics, งานวิจัย [9] [10][11] การจับคู่ระหว่างข้อความกับรูปแบบของการวาดมือ ซึ่งเป็นงานด้าน Gesture Recognition, งานวิจัย [12] การหาทิศทางเดินให้กับหุ่นยนต์ในสภาพแวดล้อมปิดในอาคาร ซึ่งเป็นงานด้าน Robotics, งานวิจัย [13] [14] [15] ตรวจสอบการบุกรุกระบบคอมพิวเตอร์ ซึ่งเป็นงานด้าน Computer Security เป็นต้น

โดยพื้นฐานแล้วถ้าเราไม่สนใจประสิทธิภาพในการคำนวณ เราจะพบว่า Hidden Markov Models เป็นโมเดลที่ใช้ประโยชน์ได้ดีและไม่มีปัญหา แต่หากเราสนใจประสิทธิภาพในการคำนวณ เราจะพบว่า Hidden Markov Models มีปัญหาพื้นฐานอยู่ 3 ข้อ อันได้แก่ 1) การหาผลรวมสุทธิของความน่าจะเป็นของโมเดล เมื่อเทียบกับลำดับที่สังเกตได้, 2) การหาลำดับที่ถูกซ่อนในโมเดล ซึ่งให้ค่าความเป็นไปได้สูงสุด เมื่อเทียบกับลำดับที่สังเกตได้ และ 3) การปรับค่าพารามิเตอร์ในโมเดล เพื่อให้โมเดลมีผลรวมสุทธิของความน่าจะเป็นเพิ่มขึ้น

สำหรับปัญหาพื้นฐานข้อแรก คือ การหาผลรวมสุทธิของความน่าจะเป็นของโมเดล เมื่อเทียบกับลำดับที่สังเกตได้ ซึ่งโดยพื้นฐานแล้วสามารถใช้วิธีการ Brute Force เพื่อคำนวณหาได้ แต่มันเป็นการคำนวณที่ไม่มีประสิทธิภาพ เพราะใช้เวลาเป็น O(2TN^T) ดังนั้นจึงมีงานวิจัยหลายชิ้นที่นำเสนอวิธีการลดเวลาในการคำนวณ เช่น งานวิจัย [2][3] ที่เสนอให้ใช้เทคนิค Dynamic Programming มาช่วยลดเวลาในการคำนวณ เรียกว่า Forward-Backward Algorithm ซึ่งสามารถลดเวลาในการคำนวณลงเหลือ O(TN^2) และต้องเสียพื้นที่เพิ่มเติมเท่ากับ O(TN), งานวิจัย [16] ที่คิดค้นแปลง Hidden Markov Models ให้เป็น Probabilistic Independent Network เพื่อสะดวกในการคำนวณ ซึ่งสามารถลดเวลาในการคำนวณลงเหลือ O(TN) และต้องเสียพื้นที่เพิ่มเติมเท่ากับ O(TN), งานวิจัย [17] ที่ใช้เทคนิค Divide and Conquer ซึ่งลดเวลาในการคำนวณลงเหลือ O(TN log(N)) และต้องเสียพื้นที่เพิ่มเติมเท่ากับ O(T log (N)) เป็นต้น

สำหรับปัญหาพื้นฐานข้อที่สอง คือ การหาลำดับที่ถูกซ่อนในโมเดล ซึ่งให้ค่าความเป็นไปได้สูงสุด เมื่อเทียบกับลำดับที่สังเกตได้ ซึ่งเป็นปัญหาที่ไม่แตกต่างจากปัญหาแรก นั่นคือ หากคำนวณตรง ๆ ก็จะใช้เวลาเป็น O(2TN^T) เพราะต้องคำนวณให้ครบทุกลำดับที่ซ่อนอยู่ที่เป็นไปได้ จึงจะสามารถเลือกลำดับที่ให้ค่าความน่าจะเป็นสูงสุดมาเป็นผลลัพธ์สำหรับแก้ปัญหาที่สองนี้ และเนื่องจากการแก้ปัญหาแบบนี้ไม่มีประสิทธิภาพ จึงได้มีการประยุกต์ใช้เทคนิคอื่นเพื่อแก้ปัญหา เช่น งานวิจัย [18][19] ซึ่งจัดวางโมเดลให้อยู่ในรูปของ Trellis Diagram และใช้เทคนิค Dynamic Programming ซึ่งเรียกว่า Viterbi Algorithm โดยสามารถลดเวลาคำนวณลงเหลือ O(TN^2) และต้องเสียพื้นที่เพิ่มเติมเท่ากับ O(2TN), งานวิจัย [20][21] ที่นำ Viterbi Algorithm มาต่อยอด โดยการลดรูปของ Trellis Diagram ด้วยวิธีการจัดกลุ่ม State ที่คล้ายกัน ทำให้ลดเวลาการคำนวณลงเหลือ O(TN^2/G^2) และยังเพิ่มประสิทธิภาพเพิ่มเติมด้วยการกำหนด Threshold เพื่อข้ามการคำนวณบาง State ที่ไม่จำเป็น เป็นต้น

สำหรับปัญหาพื้นฐานข้อที่สาม คือ การปรับค่าพารามิเตอร์ในโมเดล เพื่อให้โมเดลมีผลรวมสุทธิของความน่าจะเป็นเพิ่มขึ้น ซึ่งเป็นปัญหาที่ยากที่สุดและไม่มีขั้นตอนวิธีตายตัว โดยนักวิจัยได้แบ่งการค้นคว้ากันไปใน 2 แนวทาง ได้แก่ 1) แบบที่ให้ผลลัพธ์เป็น Local Optimum เช่น งานวิจัย [4] ที่ใช้การประมาณการแบบ Iterative Method ด้วยเทคนิคแบบ Expectation Maximization [22] เรียกว่า Baum-Welch Algorithm, งานวิจัย [23] ที่ใช้เทคนิคการปรับตัวเลข เรียกว่า Gradient Descent Algorithm, งานวิจัย [24] ที่ใช้ Ant Colony Optimization ร่วมกับ Baum-Welch Algorithm และ 2) แบบที่ให้ผลลัพธ์เป็น Global Optimum โดยการใช้ขั้นตอนวิธี Metaheuristic เข้ามาช่วยคำนวณ เช่น งานวิจัย [25][26][27] ที่ใช้ Genetic Algorithm, งานวิจัย [28] ที่ใช้ Particle Swarm Optimization, งานวิจัย [29] ที่ใช้ Modified Gravitational Search Algorithm เป็นต้น

ผู้เขียนวิเคราะห์ว่าแนวโน้มในการแก้ปัญหาพื้นฐานข้อที่สามด้วยวิธี Metaheuristic เพื่อให้ได้ผลลัพธ์เป็น Global Optimum กำลังเป็นที่นิยมแพร่หลายมากขึ้นเรื่อย ๆ เนื่องจากเป็นวิธีการหาคำตอบโดยการสุ่มคำตอบที่ดีที่สุดจากค่าที่เป็นไปได้ทั้งหมดจริง ๆ แทนที่จะใช้วิธีการหาคำตอบที่ดีที่สุดแบบ Local Optimum จากชุดของตัวแทนที่ถูกเลือกมาด้วย Forward-Backward Algorithm ซึ่งคำตอบที่ได้จากตัวแทนอาจจะไม่ใช่คำตอบที่ดีที่สุด เมื่อเทียบกับการหาคำตอบจากค่าที่เป็นได้ทั้งหมด

นอกจากปัญหาในแง่การคำนวณเพื่อให้มีประสิทธิภาพสูงสุดแล้ว ยังมีปัญหาท้าทายอีกอย่างหนึ่งนั่นคือ ปัญหาการออกแบบ Topology ให้มีความเหมาะสม ดังนั้น จึงมีงานวิจัยหลายตัวที่ถูกคิดค้นขึ้น เพื่อการทำให้ Topology ของ Hidden Markov Model มีความหลากหลาย เช่น งานวิจัย [30][31] ที่คิดค้น Hierarchical Hidden Markov Model (HHMM) เพื่อสร้าง Topology ของ Hidden Markov Model ใหม่ โดยการจัดกลุ่มของลำดับที่ซ่อนอยู่ซึ่งมีรูปแบบวนซ้ำ ให้อยู่ในรูปโครงสร้างแบบต้นไม้ จุดประสงค์เพื่อนำไปใช้สำหรับแก้ปัญหาซับซ้อนเชิงโครงสร้างหลายระดับ ที่ Topology แบบเรียงลำดับไม่สามารถแก้ปัญหาได้อย่างมีประสิทธิภาพ หรืองานวิจัย [32] ที่คิดค้น variable-length Hidden Markov Model (VLHMM) ซึ่งเป็น Topology ที่เพิ่ม Context Set เข้ามาช่วยในการคำนวณการเชื่อมโยงของลำดับที่ซ่อนอยู่ จากเดิมที่เคยเชื่อมลำดับที่ซ่อนอยู่ปัจจุบันกับลำดับที่ซ่อนอยู่ก่อนหน้าแบบ First Order ก็ให้เปลี่ยนเป็นลำดับที่สูงกว่า First Order แทน โดยขึ้นกับการคำนวณเพื่อเปลี่ยนแปลงค่าความน่าจะเป็นในโมเดล เพื่อให้โมเดลมีผลรวมของความน่าจะเป็นเพิ่มขึ้น โดยอิงกับลำดับที่สังเกตได้

ผู้เขียนวิเคราะห์ว่าการออกแบบ Topology ให้เหมาะสม จะส่งผลทางอ้อม ทำให้ไม่ต้องแก้ปัญหาพื้นฐานของ Hidden Markov Models ให้ครบทั้ง 3 ข้อ หากแต่เลือกเพียงบางข้อเพื่อแก้ปัญหาก็ได้ เช่น ในงานแก้ปัญหา Speech Recognition ซึ่งมักจะใช้ Topology แบบ Left To Right นั้น ใช้เพียงวิธีแก้ปัญหาพื้นฐานของข้อที่หนึ่งกับข้อที่สามก็เพียงพอแล้ว เนื่องจากรูปแบบของ Topology แบบ Left To Right นั้น ได้บังคับทิศทางของลำดับที่ถูกซ่อนในโมเดลเอาไว้อยู่แล้ว จึงไม่จำเป็นต้องใช้วิธีแก้ปัญหาพื้นฐานของข้อที่สองเพื่อแก้ปัญหาเพิ่มเติมอีก

เอกสารอ้างอิง

1. L.  E.  Baum, T.  Pretrie.  “Statistical Inference For Probabilistic Functions Of Finite State Markov Chains.”  The Annals of Mathematical Statistics.  (April 1966) : 1554-1563.
2. L.  E.  Baum, J.  A.  Eagon.  “An inequality with applications to statistical estimation for probabilistic functions Markov processes and to a model for ecology.”  Bull. Amer. Math. Soc.  (1967) : 360-363.
3. L.  E.  Baum, G.  R.  Sell.  “Growth Transformations For Functions on Manifolds.”  Pacific Journal of Mathematics, vol.  27, No.  2.  (1968) : 211-227.
4. L.  E.  Baum, et al.  “A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chain.”  The Annals of Mathematical Statistics, vol. 41. No. 1.  (1970) : 164-171.
5. L.  R.  Rabiner, B.  H.  Juang.  “An Introduction to Hidden Markov Models.”  IEEE ASSP Magazine.  (January 1986) : 4-16.
6. L.  R.  Rabiner.  “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition.”  Proceeding of the IEEE, vol. 77, No. 2.  (February 1989) : 257-286.
7. L.  R.  Rabiner,  B.  H.  Juang.  Fundamentals of speech recognition.  New Jersey : Prentice-Hall Inc, 1993.
8. Richard Durbin, et al.  Biological sequence analysis: Probabilistic models of proteins and nucleic acids.  New York : Cambridge University Press, 1998.
9. T.  Starner, A.  Pentland.  “Real-time American Sign Language recognition from video using hidden Markov models.”  Proceeding of the International Symposium on Computer Vision.  (November 1995) : 265-270.
10. Hyeon-Kyu Lee, Jin H. Kim.  “An HMM-Based Threshold Model Approach for Gesture Recognition.”  IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 21, issue 10.  (October 1999) : 961-973.
11. Martin J.  “Automatic handwriting gestures recognition using hidden Markov models.”  Proceeding of IEEE International Conference.  (March 2000) : 403-409.
12. Aycard O.  “Place Learning and recognition using hidden Markov models.”  Proceeding of IEEE/RSJ International Conference, vol. 3.  (September 1997) : 1741-1747.
13. S.  B.  Cho, S.  J.  Han.  “Two Sophisticated Technique to Improve HMM-Based Intrusion Detection Systems.”  RAID2003, (2003) : 207-219.
14. T.  Lane, C.  E.  Brodley.  “An Empirical Study of Two Approaches to Sequence Learning for Anomaly Detection.”  Machine Learning, 51 (2003) : 73-107.
15. C.  Warrender, et al.  “Detecting Intrusions Using System Calls: Alternative Data Models.”  Proceedings of the IEEE Computer Society Symposium on Research in Security and Privacy, (1999) : 133–145.
16. P.  Smyth, D.  Heckerman, M.  Jordan.  “Probabilistic Independence Networks for Hidden Markov Probability Models.”  Technical Report MSR-TR-96-03, Microsoft Research, Redmond, Washington, (1996).
17. J.  Binder, K.  Murphy, S.  Russell.  “Space-efficient inference in dynamic probabilistic networks.”  Proceedings of 5^th IJCAI97, vol.  2, (1997) : 1292-1296.
18. J.  Viterbi.  “Error bounds for convolutional codes and anasymptotically optimal decoding algorithm.”  IEEE Trans.  Informat.  Theory, vol.  IT-13,  (April 1967) : 260-269.
19. G.  D.  Forney.  “The Viterbi algorithm.”  Proc.  IEEE, vol. 62.  (March 1973) : 268-278.
20. Y.  Fujiwara, Y.  Sakurai, M.  Yamamuro.  “SPIRAL: Efficient and Exact Model Identification for Hidden Markov Models.”  KDD’08, (August 2008) : 247-255.
21. Y.  Fujiwara, Y.  Sakurai, M.  Kitsuregawa.  “Fast Likelihood Search for Hidden Markov Models.”  ACM Transaction Knowledge Discovery from Data, vol.  3, no.  4, Article 18, (November 2009) : 1-37.
22. P.  Dempster, N.  M.  Laird and D.  B.  Rubin.  “Maximum Likelihood from incomplete data via the EM algorithm.”  J.  Roy.  Stat.  Soc., vol.  39, no.  1.  (1977) : 1-38.
23. S.  E.  Levinson, L.  R.  Rabiner, M.  M.  Sondhi.  “An introduction to the application of the theory of probabilistic functions of a Markov process to automatic speech recognition.”  Bell System Technical Journal.  62 (1983) : 1035-1074.
24. Q.  Wang, S.  Ju.  “ACO-based BW algorithm for parameter estimation of hidden Markov models.”  International Journal of Computer Applications in Technology, vol.  41, issue 3/4, (September 2011) : 281-286.
25. Fang Sun, Guangrui Hu.  “Speech recognition based on genetic algorithm for training HMM.”  Electronics Letters, vol.  34, 16 (August 1998) : 1563-1564.
26. C.  W.  Chau, et al.  “Optimization of HMM by a Genetic Algorithm.”  IEEE ICASSP-97, vol.  3, (1997) : 1727-1730.
27. Chan, S.  Kwong.  “Analysis of Parallel Genetic Algorithm on HMM based speech recognition system.”  IEEE Conf., (1997) : 1229-1233.
28. L.  Xue, et al.  “A Particle Swarm Optimization for Hidden Markov Model Training.”  Proceeding of 8th International Conference on Signal Processing, 1 (2006).
29. A.  R.  Hosseinabadi, M.  R.  Ghaleh, S.  E.  Hashemi.  “Application of Modified Gravitational Search Algorithm to Solve the Problem of Teaching Hidden Markov Model.”  IJCSI, vol.  10, issue 3, no.  2, (May 2013) : 1-8.
30. S.  Find, Y.  Singer, N.  Tishby.  “The Hierarchical Hidden Markov Model: Analysis and Applications.”  Machine Learning, 32 (1998) : 41-62.
31. Lin-Yi Chou.  “Techniques to incorporate the benefits of a Hierarchy in a modified hidden Markov model.”  Proceeding of the COLING/ACL06, (July 2006) : 120-127.
32. Y.  Wang, et al.  “Mining Complex Time-Series Data by Learning Markovian Models.”  Proceeding of the Sixth ICDM06, (2006) : 1136-1140.

ก็จบคร่าว ๆ ประมาณนี้ครับ ซึ่งถ้าใครสนใจแบบจำลองทางสถิติที่ชื่อว่า Hidden Markov Models ก็สามารถหาอ่านเพิ่มเติมได้ทางเว็บไซต์ต่าง ๆ ครับ แต่ก็เป็นอะไรที่น่าสับสนนิดนึงนะครับ ทางที่ดีถ้าอยากเรียนรู้เร็ว ก็คงต้องให้คนที่แตกฉานในแบบจำลองมาอธิบายนั่นแหล่ะครับถึงจะเข้าใจได้