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

ทบทวนวรรณกรรมทางด้านการวิจัยทางคอมพิวเตอร์

การรวมปัญญาประดิษฐ์และความมั่นคงของคอมพิวเตอร์เข้าไว้ด้วยกัน

ผมได้รับการบ้านมาครับ คือต้องนำงานวิจัยในหัวข้อเกี่ยวกับความมั่นคงของคอมพิวเตอร์มาสรุปความ ผมเลยเลือกทำอันนี้ครับ มันคือโครงร่างซอฟต์แวร์ ConXsense ซึ่งมันเป็นงานวิจัยที่ได้รางวัลชนะเลิศในงานประชุมวิชาการ ASIACCS’14 จัดขึ้นที่ญี่ปุ่นเมื่อช่วงเดือนมิถุนายน 2557 ที่ผ่านมา ลองอ่านดูแล้วกันครับว่างานวิจัยนี้เขาทำอะไร …

ConXsense – Automated Context Classification for Context-Aware Access Control

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

อ่านเพิ่มเติม การรวมปัญญาประดิษฐ์และความมั่นคงของคอมพิวเตอร์เข้าไว้ด้วยกัน

การปรับปรุงประสิทธิภาพของ 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

จดหมายเหตุควอนตัมคอมพิวเตอร์

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

เอาเป็นว่าเริ่มเลยก็แล้วกันนะครับ …

บทนำ

ปัจจุบันโลกยังอยู่ในยุคของสถาปัตยกรรมดิจิทัลคอมพิวเตอร์ ซึ่งเป็นสถาปัตยกรรมที่พึ่งพาปรากฎการณ์ทางด้านอิเลกทรอนิกส์ในการขับเคลื่อน นั่นคือ ยังคงประมวลผลโดยพึ่งพาสัญญาณไฟฟ้ากระแสตรงแบบ 0 และ 1 ซึ่งทิศทางของสัญญาณไฟฟ้าเกิดจากการที่อิเล็กตรอนกระโดดออกจากอะตอมหนึ่งข้ามไปยังอีกอะตอมหนึ่งในทิศทางตรงข้ามกัน ในขณะเดียวกัน ปริมาณของทรานซิสเตอร์บนวงจรรวม ก็เพิ่มขึ้นเป็นเท่าตัวประมาณทุก ๆ สองปี ตามกฎของ Gordon E.  Moore

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

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

อ่านเพิ่มเติม จดหมายเหตุควอนตัมคอมพิวเตอร์

ปัญหา P กับ NP

ผมต้องส่งการบ้านในหัวข้อ “งานวิจัย NP ในปัจจุบัน” พอค้น ๆ ไปในอินเทอร์เน็ตถึงได้พบว่า อย่าว่าแต่ของคนไทยเลย ขนาดของพวกฝรั่งก็ยังเขียนลำดับให้เข้าใจไม่ค่อยได้ คือ เขาจะเขียนข้าม ๆ เป็นห้วง ๆ ไม่ลำดัีบเป็นขั้น ๆ เขาจะถือว่ารู้แล้ว (ซึ่งจริง ๆ เราไม่รู้) ดังนั้น ผมก็เลยต้องอ่านจากหลาย ๆ ที่ แล้วเอามาประมวลเป็นลำดับขั้นตอนเพื่อส่งการบ้าน ทีนี้เห็นว่ามันน่าจะเอามาเผยแพร่ได้ ให้คนทั่วไปเข้าใจได้ง่าย ๆ (เอ๊ะ หรือจะไม่ง่าย?) ก็เลยคิดว่าเอามาลงในบล็อกของตัวเองดีกว่า

งั้นเริ่มเลยล่ะกัน …

1.  บทคัดย่อ

ในวงการวิทยาการคอมพิวเตอร์ หากเรากล่าวถึง “ปัญหา” จะมีสิ่งให้ขบคิดอยู่สองประเด็น นั่นคือ เราจะหาคำตอบของปัญหานั้น ๆ อย่างมีประสิทธิภาพได้อย่างไร และ หากมีการเฉลยคำตอบของปัญหานั้น ๆ แล้ว เราจะหาวิธียืนยันคำตอบนั้น ๆ อย่างมีประสิทธิภาพได้อย่างไร ว่ามันเป็นคำตอบที่ “ใช่” หรือ “ไม่ใช่” ซึ่งกลุ่มของปัญหาที่ต้องการ ๆ ยืนยันคำตอบอย่างมีประสิทธิภาพหากคำตอบคือ “ใช่” จะถูกเรียกในทางทฤษฎีว่าเป็นกลุ่มปัญหา NP หรือ Non-deterministic polynomial time ซึ่งในบทความนี้จะนำเสนอถึงการวิจัย NP ในปัจจุบัน ว่ามีความก้าวหน้าไปอย่างไรบ้าง

2.  บทนำ

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

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

ด้วยรูปแบบของการวนรอบเพื่อนับ จึงทำให้สามารถมองได้ว่าปัญหาส่วนใหญ่ในทางวิทยาการคอมพิวเตอร์ สามารถแก้ได้ในเวลา Polynomial Time แต่การแก้ปัญหาจะไม่ถือว่ามีประสิทธิภาพ หากใช้เวลาในการแก้ปัญหาเกินกว่าจะยอมรับได้ เช่นในการแก้ปัญหา Travelling Salesman Problem ที่กำหนดให้พนักงานขายเลือกเส้นทางที่สั้นที่สุด เพื่อเดินทางไปทีล่ะเมืองให้ครบทุกเมืองโดยไม่ซ้ำ แล้วย้อนกลับมายังเมืองที่ตั้งต้น ซึ่งการหาผลเฉลยที่ถูกต้องที่สุดก็คือการตรวจในทุก ๆ เส้นทางที่เป็นไปได้ แล้วเลือกเส้นทางที่สั้นที่สุดจากการตรวจสอบทั้งหมด โดยต้องใช้จำนวนรอบเพื่อหาผลเฉลยเท่ากับ n! ซึ่งหากมีจำนวนของเมือง 100 เมืองให้เดินทาง ก็หมายถึงการที่ต้องค้นหาผลเฉลยด้วยจำนวนรอบเท่ากับ 100! ซึ่งใช้เวลาที่มากเกินกว่าจะยอมรับได้

ดังนั้น ในทางทฤษฎีจึงเกิดแนวความคิดว่า ถ้ายังคงต้องการแก้ปัญหาที่ใช้เวลามาก ๆ ใน Polynomial Time ได้อย่างมีประสิทธิภาพ (และเราก็เชื่อว่ายังไงก็ต้องแก้แบบ Polynomial Time จนกว่ามันจะมีวิธีอื่นมาแทนที่ เช่น Quantum อะไรประมาณนั้น) จำเป็นอย่างยิ่งที่จะต้องเปลี่ยนแนวคิดของเครื่องจักรทางทฤษฎีที่ใช้ขับเคลื่อนการแก้ปัญหา จากเดิมที่ใช้เครื่องจักรทางทฤษฎีในการแก้ปัญหาที่มีกลไกเคลื่อนที่ 1 State เกิด 1 Action หรือที่เรียกว่า Deterministic Turing Machine ให้กลายเป็นเครื่องจักรทางทฤษฎีในการแก้ปัญหา ที่มีกลไกเคลื่อนที่ 1 State เกิดได้หลาย Action หรือที่เรียกว่า Non-deterministic Turing Machine

ซึ่งการแก้ปัญหาใน Polynomial Time บนเครื่องจักรทางทฤษฎีแบบ Non-deterministic Turing Machine จึงเรียกว่าเป็นการแก้ปัญหาแบบ Non-deterministic Polynomial Time หรือ NP และปัจจุบันก็มีงานวิจัยในหลากหลายแขนงวิชา ที่กำลังค้นคว้าวิจัยกลุ่มปัญหา NP อยู่ในขณะนี้ ดังจะกล่าวในหัวข้อถัดไป

อ่านเพิ่มเติม ปัญหา P กับ NP