คลังเก็บหมวดหมู่: Computation

โม้เกี่ยวกับการหาคำตอบของปัญหา จากข้อมูลป้อนเข้า โดยการใช้อัลกอริทึมเข้าช่วย

วิธีค้นหาคำตอบที่ดีที่สุดโดยคอมพิวเตอร์

เราจะเห็นว่าทุกวันนี้เครื่องจักรที่คิดหรือตัดสินใจอะไรเองได้ เริ่มเข้ามามีบทบาทในชีวิตประจำวันเรามากขึ้นเรื่อย ๆ และการที่มันทำพฤติกรรมแบบนี้ได้ เราก็มักจะมีคำจำกัดความให้มัน เรามักจะเรียกมันว่า “ปัญญาประดิษฐ์” บ้าง หรือไม่ก็เรียกว่า “ระบบอัจฉริยะ” บ้าง อะไรประมาณนั้น

จริง ๆ แล้วเบื้องหลังของการที่มันคิดหรือตัดสินใจได้ เกิดจากปัจจัยเพียง 2 สิ่งเท่านั้น นั่นก็คือ “การคำนวณ” และ “ข้อมูล”

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

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

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

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

ดังนั้น ในปัจจุบันจึงมีแนวทางอยู่ 3 ประการในการค้นหาคำตอบที่ดีที่สุดโดยคอมพิวเตอร์ครับ ซึ่งได้แก่

1.  การค้นหาด้วยเทคนิคปรกติ

การค้นหาด้วยเทคนิคปรกติ ก็คือการค้นหาตามหลักการพื้น ๆ ในทางคอมพิวเตอร์ทั่วไป ไม่ว่าจะเป็น

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

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

2.  การค้นหาด้วยเทคนิคการเดาอย่างมีเหตุผล

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

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

  • การเดาโดยเลียนแบบพฤติกรรมของธรรมชาติ เช่น เลียนแบบการวิวัฒนาการของสิ่งมีชีวิต การเลียนแบบแรงดึงดูดโน้มถ่วง
  • การเดาโดยเลียนแบบพฤติกรรมของสัตว์หรือแมลง เช่น เลียนแบบการค้นหาเหยื่อของฝูกนก เลียนแบบการหาอาหารของฝูงมด
  • การเดาโดยเลียนแบบสิ่งประดิษฐ์ที่เกิดจากมนุษย์ เช่น เลียนแบบพฤติกรรมของโลหะเมื่อร้อนแดงแล้วค่อย ๆ เย็นตัวลง

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

3.  การค้นหาโดยเทคนิคให้คอมพิวเตอร์เรียนรู้

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

การค้นหาคำตอบที่ดีที่สุดโดยเทคนิคนี้ จะคล้าย ๆ กับเทคนิคการเดาอย่างมีเหตุผลในแง่ของคำตอบ คือคำตอบที่ได้จะไม่ใช่คำตอบที่ดีที่สุดจริง ๆ แต่มันก็ดีพอที่จะยอมรับได้

ดังนั้น โดยสรุปแล้ว ความมีปัญญาของคอมพิวเตอร์ ก็คือการที่คอมพิวเตอร์มันคำนวณ (ด้วยวิธีอันแสนจะซับซ้อน) โดยอิงกับข้อมูล (เท่าที่มี) เพื่อค้นหาคำตอบที่ดีที่สุด ในเวลาที่จำกัดบนทรัพยากรที่จำกัดนั่นเอง

คงอีกนานครับกว่าคอมพิวเตอร์มันจะมีชีวิตจิตใจขึ้นมาได้

ปัญหาการจัดหมู่คลาส Factorial เชิงสังคมศาสตร์

ทุกวันนี้คอมพิวเตอร์มันเก่งมากในการประมวลผลซอฟต์แวร์ แต่มันยังไม่ถึงจุดที่มันจะสร้างซอฟต์แวร์เองได้ ดังนั้น มนุษย์เลยยังคงต้องรับผิดชอบเป็นผู้สร้างซอฟต์แวร์อยู่

ในงานสร้างซอฟต์แวร์โดยเฉพาะซอฟต์แวร์ขนาดใหญ่ มักจะต้องแบ่งงานกันทำ เพราะทำคนเดียวไม่ได้ มันเสร็จช้า และก็อาจจะไม่ประณีตในหลาย ๆ เรื่อง ดังนั้น แบ่งกันทำดีกว่า

ปรกติแล้วการสร้างซอฟต์แวร์ถ้ามีคนพอ จะแบ่งงานออกเป็น 3 ส่วนใหญ่ ๆ คืองาน Management งาน Functional และงาน Technical

ทีนี้เรามาสมมติว่าเราเป็นผู้อำนวยการสร้างกันดีกว่า โดยสมมติให้เราคิดคำนวณตัดสินใจแบบคอมพิวเตอร์ คือสมมติว่าเรามีโครงการสร้างซอฟต์แวร์อยู่โครงการนึง ตั้งงบประมาณไว้ที่ 2,100,000.00 บาท จุดประสงค์ของงบประมาณ คือเอามาจ่ายให้กับคนที่ทำงาน ซึ่งโครงการนี้ต้องการทำให้เสร็จภายใน 30 วัน โดยให้ใช้คนเพียง 3 คนแบ่งกันทำงานทุกวัน ตามตำแหน่ง Management, Functional และ Technical และแต่ล่ะคนทำงานได้เพียงหน้าที่เดียวเท่านั้นตลอดทั้งโครงการ

ในฐานะเราเป็นผู้อำนวยการสร้าง เราก็หวังว่าเราจะใช้คนให้เหมาะสมกับงาน เพื่อให้ได้ประสิทธิผลที่สูงสุด โดยพิจารณาจากคะแนนรวมของตำแหน่ง Management, Functional และ Technical ซึ่งคะแนนของแต่ล่ะตำแหน่ง ก็ได้จากคะแนนทักษะแต่ล่ะแบบของคนทำงานทั้ง 3 คนอีกทอดหนึ่ง

พอดีว่าคนทำงานที่มีให้เลือกมันน้อย ก็เลยมีให้เลือกมาแค่ 3 คนซึ่งมีอายุไล่เลี่ยกัน และแต่ล่ะคนก็มีทักษะ Management, Functional และ Technical แตกต่างกันไปตามภาพข้างล่างนี้ ดังนั้น ลองมาคิดดูกันดีกว่าว่า คนไหนควรจะทำตำแหน่งอะไร เพื่อให้ผลรวมของคะแนนในการคัดเลือกมีมากที่สุด ซึ่งผลรวมมากสุดที่เป็นไปได้ คือ  30 คะแนน

และที่สำคัญ คนไหนที่ได้ทำตำแหน่ง Management เราจะให้เป็นหัวหน้าผู้ควบคุมโครงการในครั้งนี้

คะแนนทักษะ
คะแนนทักษะ

จากภาพจะเห็นว่านาย กอ มีทักษะแยกประเภทและทักษะโดยรวมมากกว่า นาย ขอ และ นาย คอ!!!

จะเห็นว่าปัญหานี้เป็นปัญหาที่ต้องใช้เวลาในการคำนวณซึ่งอยู่ในคลาส Factorial คือถ้าเราจะเลือกคนมาทำ Management ก็จะมีตัวเลือก 3 คน พอต้องมาเลือกคนทำ Functional ก็จะเหลือตัวเลือกแค่ 2 คน เพราะเลือก Management ไปแล้วคนนึง และสุดท้ายก็จะเหลือคนมาทำ Technical แค่คนเดียว เพราะอีก 2 คนถูกเลือกให้ทำ Management กับ Functional ไปแล้ว

ดังนั้น ถ้าเราจะต้องหาว่าผลรวมไหนดีที่สุด เราก็ต้องคำนวณหาในทุกกรณี ซึ่งก็ต้องใช้เวลาในการคำนวณเท่ากับ 3 x 2 x 1 = 3! = 6 รูปแบบนั่นเอง

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

Skill Matrix
Skill Matrix

จากภาพข้างบนจะเห็นว่า การจัดหมู่ที่ดีที่สุดสำหรับโจทย์นี้คือ การให้นาย ขอ เป็นหัวหน้าทำตำแหน่ง Management ให้นาย คอ ทำตำแหน่ง Functional และนาย กอ ทำตำแหน่ง Technical เหตุผลเพราะการจัดหมู่รูปแบบนี้ ให้ผลคะแนนที่ดีที่สุดคือ 20 คะแนน

โดยปรกติแล้วตามราคาตลาด ผลตอบแทนของ Management จะต้องคูณ 2.3 เท่า ส่วนของ Functional จะต้องคูณ 1.2 เท่า และของ Technical ไม่คูณอะไรเลย

ดังนั้น ถ้าให้ค่าตอบแทนวันล่ะ 15,000 บาท ด้วยการจัดหมู่แบบนี้นาย ขอ จะได้ค่าตอบแทนวันล่ะ 15,000 x 2.3 บาท ส่วนนาย คอ จะได้ค่าตอบแทนวันล่ะ 15,000 x  1.2 บาทและส่วนนาย กอ จะได้ค่าตอบแทนวันล่ะ 15,000 บาท

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

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

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

ปัญหาความซับซ้อนในการคำนวณ

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

โดย N คือจำนวนของขนาดปัญหาที่เป็นไปได้

อย่างแบบแรก ยกตัวอย่างให้เห็นง่าย ๆ ก็คือ ถ้าเรามีเสื้อ 2 ตัว กางเกง 2 ตัว รองเท้า 2 คู่ เราจะเลือกใส่ เสื้อ กางเกง และ รองเท้า ยังไงให้หล่อที่สุด ซึ่งจากโจทย์ C ก็คือ 2 เพราะบังเอิญว่าแต่ล่ะตัวแปรมี 2 กรณีให้เลือก ในขณะที่ N คือ 3 เพราะขนาดปัญหา คือ 3 ตัวแปร คือ 1) เสื้อ 2) กางเกง 3) รองเท้า ดังนั้น ถ้าจะหาคำตอบที่ดีที่สุด เราก็ต้องลอง เสื้อ กางเกง รองเท้า ให้มันหมดเลย ซึ่งต้องใช้เวลาเท่ากับ C ยกกำลัง N หรือ 2 ยกกำลัง 3 ซึ่งก็คือ {1, 1, 1}, {1, 1, 2}, {1, 2, 1}, {1, 2, 2}, {2, 1, 1}, {2, 1, 2}, {2, 2, 1} และ {2, 2, 2} หรือก็คือใช้เวลาไป 8 รอบ

ส่วนแบบสอง ยกตัวอย่างให้เห็นง่าย ๆ ก็คือ ถ้าในร้านค้ามีสินค้าเพียง 3 ชิ้นที่แตกต่างกัน แล้วเรามีเงินอยู่แค่ 100 บาท เราจะซื้อสินค้าได้กี่่ชิ้น ซึ่งจากโจทย์ N ก็คือ 3 เพราะขนาดปัญหา คือ 3 ดังนั้น ถ้าจะหาคำตอบที่ดีที่สุด เราก็ต้องเอาราคาสินค้ามาเทียบกันให้หมดเลย เพื่อดูว่ารวมเงินแล้วจะซื้อชิ้นไหนได้บ้างโดยใช้เงินไม่เกิน 100 บาท ซึ่งต้องใช้เวลาคำนวณเท่ากับ 2 ยกกำลัง 3 แล้วจึงลบ 1 ซึ่งน้อย ๆ แบบนี้ยังพอยกตัวอย่างให้ดูได้ ก็ประมาณนี้คือ {1}, {2}, {3}, {1,2}, {1,3}, {2,3} และ {1,2,3} หรือก็คือใช้เวลาไป 7 รอบ

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

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

การปรับปรุงประสิทธิภาพของ 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) การปรับค่าพารามิเตอร์ในโมเดล เพื่อให้โมเดลมีผลรวมสุทธิของความน่าจะเป็นเพิ่มขึ้น

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

Taxonomy ของ Genetic Algorithm

Taxonomy หรือ อนุกรมวิทธาน เป็นอะไรซักอย่างที่ถูกใช้เพื่อการจัดหมวดหมู่ครับ ที่เห็นเยอะ ๆ ก็ใช้ในการจัดหมวดหมู่ของสิ่งมีชีวิต เพื่อแบ่งชั้นแบ่งกลุ่มว่าอะไรพวกเดียวกับอะไร แล้วแต่ล่ะพวกนั้นมันไปเกี่ยวกับอะไรที่อยู่ในชั้นก่อนหน้านั้น เป็นต้น

ในทางทฤษฎีการคำนวณสำหรับคอมพิวเตอร์ ก็มี Taxonomy กับเขาเหมือนกันครับ เพราะเดี๋ยวนี้ทฤษฎีการคำนวณสำหรับคอมพิวเตอร์มันแตกสาย แตกลูกแตกหลานกันเยอะ บางทีได้ยินคุยกันก็รำคาญใจ จัดหมวดหมู่ชั้นช่วงกันผิด ๆ ถูก ๆ เหมือนกับมีคนมาบอกเราว่า กรุงเทพฯ, พระประแดง, นนทบุรี และ ปทุมธานี เป็นปริมณฑล (เห็นใช่มั้ยว่าพระประแดงมันไม่เข้าพวกเพราะมันเป็นอำเภอ?) หรือบอกเราว่าปริมณฑลภาคกลางที่ติดทะเล ได้แก่ สมุทรปราการ, พระประแดง, สมุทรสาคร และ สมุทรสงคราม (พระประแดงเป็นอำเภอของสมุทรปราการ)

ไอ้เจ้า Genetic Algorithm เองก็ถูกอ้างผิดเหมือนกันครับ เพราะเวลาถูกจัดหมวดหมู่อ้างถึง มันมักจะถูกอ้างให้อยู่ในระดับเดียวกับชั้นที่สูงกว่า 1 ช่วงบ้าง 2 ช่วงบ้าง หรือบางครั้งก็ถูกอ้างอิงกับ Class อื่นที่อยู่ในระดับที่ไม่เท่ากัน ดังนั้น เพื่อให้เข้าใจ Taxonomy ของมัน ผมก็เลยทำให้ดูตามภาพข้างล่างนี้แล้ว

Taxonomy ของ Genetic Algorithm
Taxonomy ของ Genetic Algorithm

จริง ๆ แล้วแต่ล่ะชั้นก็มีลูกหลานแตกสายออกไปเยอะครับ แต่ที่ทำให้ดูในภาพนี้เป็นการลำดับ Taxonomy ของ Genetic Algorithm ว่าสืบสายตรงจากอะไรลงมาอ่ะครับ ก็ประมาณนี้ครับ