ซัพพอร์ตเวคเตอร์แมชชีน (Support Vector Machine: SVM)
อัลกอริทึมในการคัดแยกและรู้จำวัตถุ (object classification and recognition) จัดเป็นการเรียนรู้ของเครื่องประเภทแบบการเรียนรู้โดยอาศัยตัวอย่างประเภทหนึ่ง ซึ่งมีความสามารถในการจัดหมวดหมู่ และการทำนาย (Regression) โดยเอสวีเอ็ม มีพื้นฐานจะมีการคำนวณแบบเชิงเส้น (Linear) ซึ่งจัดอยู่ในประเภทมุ่งหาผลลัพธ์ที่ดีที่สุดของการเรียนรู้ (Discriminative Training) บนการเรียนรู้จากสถิติของข้อมูล ซึ่งทำงานโดยการหาค่าระยะขอบที่มากที่สุด (Maximum Margin) ของระนาบตัดสินใจ (Decision Hyper-plane) ในการแบ่งแยกกลุ่มข้อมูลที่ใช้ฝึกฝนออกจากกัน อัลกอริทึมในการคัดแยกและรู้จำวัตถุ (object classification and recognition) วิธีการนี้มีชื่อเรียกอีกชื่อหนึ่งว่า การจัดหมวดหมู่โดยค่าระยะขอบที่มากที่สุด (Maximum Margin Classifier)
หลักการทำงานของเอสวีเอ็ม ข้อมูลจะถูกเขียนในรูปสมาชิกคู่อันดับดังนี้
เมื่อ ci มีค่าเป็น 1 หรือ -1 ซึ่งกำหนดให้เป็นข้อมูลแบ่งกลุ่มของข้อมูล xi ที่มีค่า ci เป็น 1 และ xi ที่มีค่าเป็นci เป็น -1 โดยที่แต่ xi เป็นค่าข้อมูลมิติของเวกเตอร์จริง เมื่อกำหนดให้ข้อมูลนี้เป็นข้อมูล สำหรับฝึกฝน ซึ่งหมายความว่าการแบ่งกลุ่มของข้อมูลมีความถูกต้อง ดังนั้นเส้นแบ่งกลุ่มของข้อมูลที่ถูกสร้างขึ้นซึ่งเป็นสมการเส้นตรงทั่วไปคือ
y = mx + b โดยในที่นี้จะแทน m ด้วย wt เพื่อกำหนดเป็นสมการ
wt . x + b = 0
เมื่อ wt คือ เวกเตอร์ตั้งฉากของค่าความชัน m ของเส้นแบ่ง
b คือ ค่าคงที่ที่ได้จากค่าของแกน y ของแต่ละข้อมูล x
ในทางอุดมคติเส้นแบ่งกลุ่มที่ดีที่สุดคือเส้นแบ่งกลุ่มที่ทำให้มีระยะขอบ (Margin) มากที่สุดของเส้นคู่ขนานที่ขยายออกจากเส้นแบ่งไปสัมผัสจุดข้อมูลของทั้งสองกลุ่มที่ใกล้ที่สุด หรือกล่าวได้ว่าเป็นเส้นแบ่งที่มีระยะของกล่าวที่สุด
เมื่อข้อมูลที่ใช้ฝึกฝนเป็นข้อมูลที่สามารถแบ่งกลุ่มได้ด้วยเส้นตรงใด ๆ ระยะที่ที่กว้างที่สุดของไฮเปอร์แพลน (Hyper plane) ทั้งสองที่ขยายออกไปจนกว่าจะพบจุดข้อมูลของทั้งสองกลุ่ม คือ 2/IwI ค่าIwIมีค่าน้อยที่สุด
เนอีฟเบย์ (Naïve Bayes)
วิธีการเรียนรู้เบย์อย่างง่าย (Naïve Bayesian Learning) เป็นวิธีการจำแนกประเภทข้อมูลที่มีประสิทธิภาพวิธีหนึ่ง โดยที่ใช้งานได้ดี เหมาะกับกรณีของเซตตัวอย่างที่มีจำนวนมากและคุณสมบัติ (Attribute) ของตัวอย่างไม่ขึ้นต่อกัน มีการจำแนกประเภทเบย์อย่างง่ายไปประยุกต์ใช้งานในด้านการจำแนกประเภทข้อความ (Text Classification) การวินิจฉัย (Diagnosis) และพบว่าใช้งานได้ดีไม่ต่างจากการจำแนกประเภทวิธีการอื่น ทำให้ผู้วิจัยเลือกวิธีการนี้มาใช้ในงานวิจัย เนื่องจากเป็นวิธีการจำแนกข้อมูลได้อย่างมีประสิทธิภาพและมีอัลกอริทึมในการทำงานที่ไม่ซับซ้อนเหมือนวิธีการอื่น ๆ
การนำวิธีการเรียนรู้เบย์อย่างง่ายไปใช้ มีวิธีการดังต่อไปนี้คือ
1 หาค่าความน่าจะเป็นของคำที่พบในแต่ละกลุ่มโดยนำค่า มาคุณกับค่าความน่าจะเป็นของกลุ่มนั้น ๆ
2 นำค่าที่ได้มาเปรียบเทียบกัน กลุ่มที่มีค่าความน่าจะเป็นสูงสุด คือคำตอบ ดังนั้นจะได้ว่าวิธีการจำแนกประเภทแบบเบย์อย่างง่าย ดังสมการ
การจัดกลุ่มเอกสารเป็นเทคนิคสำคัญของการจำแนกประเภทข้อความ จุดประสงค์เพื่อจำแนกเอกสาร โดยอัตโนมัติ มีอัลกอริทึมมากมายที่ถูกพัฒนาขึ้นสำหรับการจัดกลุ่มเอกสารแบบอัตโนมัติอีกหนึ่งวิธีที่นิยมใช้ทั่วกัน ก็คือ เบย์อย่างง่าย ซึ่งมีงานวิจัยที่ศึกษาอัลกอริทึมแบบเบย์อย่างง่ายมากมาย ในการนำเอกสารมาเรียนรู้เพื่อให้ได้ผลลัพธ์ที่มีความถูกต้อง
ในการเรียนรู้เพื่อจำแนกประเภทเอกสารโดยใช้เบย์อย่างง่าย สมมติว่ามีข้อความที่สนใจกับไม่สนใจ เมื่อทำการเรียนรู้แล้วต้องการทำนายว่าเอกสารหนึ่ง ๆ จะเป็นเอกสารที่สนใจหรือไม่สามารถนำประยุกต์ใช้งาน เช่นการกรองข่าวสารเลือกเฉพาะข่าวที่สนใจ เป็นต้น
สมมติให้เอกสารหนึ่ง ๆ คือ ตัวอย่างหนึ่งตัว และแทนเอกสารแต่ละฉบับด้วยเวกเตอร์ของคำโดยใช้คำที่ปรากฏในเอกสารเป็นคุณสมบัติของเอกสาร กล่าวคือ คำที่หนึ่งในเอกสารเป็นคุณสมบัติตัวที่หนึ่ง คำที่สองในเอกสารเป็นคุณสมบัติตัวที่สอง ตามลำดับ ดังนั้นจะได้ว่า a1 คือคุณสมบัติของคำที่หนึ่ง a2 คือคุณสมบัติของคำที่สองตามลำดับ จากนั้นสร้างการเรียนรู้ข้อมูลโดยใช้ตัวอย่างสอนเพื่อประมาณค่าความน่าจะเป็นจากสมมติฐานเรื่องความไม่ขึ้นต่อกันของคุณสมบัติของเบย์อย่างง่ายทำให้ได้ สมการหาค่าความน่าจะเป็นของเอกสารตามสมการ
อัลกอริทึมสำหรับการจำแนกประเภทข้อความโดยใช้การเรียนรู้เบย์อย่างง่ายเป็นดังต่อไปนี้
จากอัลกอริทึมด้านบน สามารถอธิบายรายละเอียดได้ดังนี้
- นำค่าที่ผ่านการตัดคำจากเอกสารมาสร้างเป็นข้อมูลตัวอย่าง
- คำนวณหาค่าความน่าจะเป็นของกลุ่มคำนวณหาค่าความน่าจะเป็นขอบคำที่พบทั้งหมด
- ค่าความน่าจะเป็นของเอกสารในแต่ละกลุ่มเอกสาร คือ ผลคุณระหว่างค่าความน่าจะเป็นของกลุ่มเอกสารกับค่าความน่าจะเป็นของคำที่พบทั้งหมดในเอกสาร
- เลือกกลุ่มเอกสารที่มีค่าความน่าจะเป็นมากที่สุด เป็นคำตอบ
ต้นไม้ตัดสินใจ (Decision tree: C45)
ต้นไม้ตัดสินใจเป็นหนึ่งในวิธีที่ใช้อย่างกว้างขวาง โดยเป็นวิธีในการประเมินค่าที่ทนต่อข้อมูลรบกวนและเป็นวิธีในการประมาณผลลัพธ์ที่ได้ อัลกอริทึมในการสร้างต้นไม้ตัดสินใจมีหลายวิธีได้แก่ Classification and Regression Trees (CART), Induction of Decision Trees (ID3) และ C45 โดยการวิธีการสร้างต้นไม้ตัดสินใจเหล่านี้มุ่งไปที่การสร้างต้นไม้ที่มีขนาดเล็กที่ให้ผลลัพธ์ที่ดีกว่าหรือเท่ากับต้นไม้ที่มีขนาดใหญ่
รูปแบบของต้นไม้ตัดสินใจอยู่ในรูปแบบของการคาดเดาและการอธิบาย ซึ่งเหตุผลที่เรียกว่าต้นไม้ตัดสินใจเนื่องจากรูปแบบของผลลัพธ์ที่ได้อยู่ในรูปของแผลภูมิต้นไม้ที่ง่ายต่อการเรียนรู้และการทำความเข้าใจ ดังนั้นต้นไม้ในการตัดสินจึงเป็นที่นิยมในการนำไปประยุกต์ใช้
เนื่องจากสมการแสดงความสัมพันธ์ของข้อมูลและผลลัพธ์ ต้นไม้ในการตัดสินใจสามารถนำมาแปลงเป็นกฎต่าง ๆ เช่น
ถ้า อากาศ “ร้อน” และ อุณหภูมิ “สูง” และ ความชื้น “สูง” และ ลม “ไม่แรง ผลลัพธ์คือ ไม่เล่น
- การแทนต้นไม้ตัดสินใจ (Decision Tree Representation)
ในการจำแนกตัวอย่างโดยใช้ต้นไม้ตัดสินใจจะแสดงข้อมูลโดยเรียงจากส่วนรากของต้นไม้ตัดสินใจไปยังส่วนของใบไม้ (leaf node) ดังนั้นการคาดเดาผลลัพธ์ทำโดยเริ่มต้นจากรากของต้นไม้ตัดสินใจแล้วทำการย้ายไปตามกิ่งของต้นไม้ไปเรื่อย ๆ จนถึงส่วนของบัพสุดท้าย โดยการแทนค่าในต้นไม้มีลักษณะของคู่ (ค่าคุณลักษณะ, ค่าของค่าคุณลักษณะ) ดังนี้
– แต่ละบัพภาพในของต้นไม้คือ ค่าคุณลักษณะ (attribute)
– แต่ละกิ่งของต้นไม้สัมพันธ์กับค่าของค่าคุณลักษณะ (attribute value)
– แต่ละบัพใบให้ค่าคลาสของต้นไม้ตัดสินใจ
- อัลกอริทึมพื้นฐานของต้นไม้ตัดสินใจ
อัลกอริทึมในการสร้างต้นไม้ตัดสินใจมีหลายวิธีโดยการทำงานหลักเป็นแบบบนไปล่าง (Top-down) โดยวิธีการสร้างต้นไม้ได้แก่ Classification and Regression Trees (CART), Induction of Decision Trees (ID3) และ C45
- ปัญหาที่เหมาะสมกับต้นไม้ตัดสินใจ
ถึงแม้ว่าอัลกอริทึมในการสร้างต้นไม้ตัดสินใจมีหลายวิธีที่ถูกสร้างเพื่อสามารถรองรับการทำงานและความต้องการทำงานที่แตกต่างกัน แต่ต้นไม้ในการตัดสินใจก็เหมาะกับการใช้งานที่มีคุณสมบัติดังนี้
– ตัวอย่างของปัญหาถูกอธิบายโดยคู่ของค่าคุณลักษณะและค่าของค่าคุณลักษณะ ยกตัวอย่างเช่น ค่าคุณลักษณะ คือ Outlook และค่าของค่าคุณลักษณะได้แก่ มีแดด (Sunny), มีเมฆมาก (Overcast), ฝนตก (Rain)
– ผลลัพธ์ที่ต้องการเป็นค่าที่ไม่ต่อเนื่อง
– เราอาจจำเป็นต้องใช้สมมติฐานแบบเลือก (disjunctive hypothesis)
– ข้อมูลในการเรียนรู้อาจมีสิ่งรบกวน (noise) ได้ เนื่องจากต้นไม้ตัดสินใจทนต่อสิ่งรบกวนที่ทำให้เกิดข้อผิดพลาดที่เกิดจากค่าคุณลักษณะและคลาสของตัวอย่าง
– ข้อมูลในการเรียนรู้อาจจะไม่มีค่าของค่าคุณลักษณะได้
เคเนียเรสเนเบอร์ (K-Nearest Neighbor: K-NN)
หลักการของวิธีการนี้จะจำแนกประเภทข้อมูลโดยขึ้นกับข้อมูลที่มีคุณสมบัติใกล้เคียงที่สุด K ตัวจากข้อมูลบนชุดข้อมูลตัวอย่างทำงานโดยขึ้นกับระยะทางน้อยสุดจากสมาชิกใหม่ หรือข้อมูลที่ป้อนถาม (input query instance) กับข้อมูลตัวอย่างฝึกฝน จะคำนวณหาเพื่อนบ้านที่ใกล้ที่สุด K ตัว หลังจากนั้น เราจะรวบรวมสมาชิกที่ใกล้เคียงที่สุด K ตัวแล้วเลือกคลาสที่สมาชิกส่วนใหญ่ที่ในกลุ่ม K ดังกล่าวสังกัดอยู่มากที่สุดให้กับสมาชิกใหม่ ข้อมูลการจำแนกโดยใช้ข้อมูลข้างเคียง K ตัว ประกอบด้วยแอททริบิวต์หลายตัวแปร Xi ซึ่งจะนำมาใช้ในการแบ่งกลุ่ม Yi โดยระบุค่าตัวเลขจำนวนเต็มบวกให้กับ K ซึ่งค่านี้จะเป็นตัวบอกจำนวนของกรณี (case) ที่จะต้องค้นหาในการทำนายกรณีใหม่ อัลกอริทึมแบบ KNN ได้แก่ 1-NN , 2-NN , 3-NN , ………. K-NN ตัวอย่าง 2-KNN หมายถึง อัลกอริทึมนี้จะค้นหา 2 กรณีที่มีลักษณะใกล้เคียงกับกรณีใหม่ (2 Nearest Cases) การนำระยะทางที่หาได้จากสมาชิกใน ข้อมูลตัวอย่างฝึกฝน มาเรียงลำดับจากน้อยไปหามากแล้วเลือกสมาชิกที่มีระยะทาง (Distance) ใกล้เคียงที่สุดออกมา K ตัวโดยใช้การวัดระยะทางแบบ Euclidean distance มีหลักการคือ การวัดระยะทางระหว่างสองวัตถุ ถ้าวัตถุห่างกันมากแสดงว่าวัตถุนั้นมีความคล้ายกันน้อย ถ้ามีค่าน้อยก็แสดงว่ามีความคล้ายคลึงกันมาก
Ada boost cascade
ขั้นตอนวิธีการเรียนรู้แบบ Ada-Boost (Ada-Boost learning algorithm) เป็นขั้นตอนวิธีการเรียนรู้เพื่อค้นหาค่าของกลุ่มพิกเซลที่มีลักษณะใกล้เคียงกับภาพนำเข้า โดยที่ภาพ positive คือ ภาพตัวอย่างวัตถุที่ต้องการตรวจจับ ส่วนภาพ negative คือภาพทั่ว ๆ ไปที่ไม่ใช่วัตถุที่ต้องการตรวจจับ ซึ่งการจำแนกกลุ่มของพิกเซลจะทำภายในส่วนย่อย (sub window) ของภาพ โดยใช้ตำจำแนกอย่างอ่อนของ feature ที่ ที่จะหาได้จากสมการ
โดยที่ x คือภาพตัวอย่างและ Sum คือผลรวมของภาพอินทิกรัลในบริเวณพื้นที่สีขาวและดำของ x AdaBoost learning algorithm เป็นวิธีหาค่าตัวจำแนกอย่างอ่อน ที่มีความผิดพลาดของน้ำหนักน้อยที่สุด hj เพื่อนำไปปรับน้ำหนักในรอบถัดไป (t+1)เลือกส่งเสริม (boosting) น้ำหนักตัวที่ไม่ผ่านการจำแนก แต่ลดน้ำหนักตัวที่ผ่านการจำแนกตามขั้นตอนวิธี
Cascade classifiers เป็นวิธีการจำแนกรูปร่างที่ต้องการ โดยนำการจำแนกดังที่กล่าวมาแล้วมาทำซ้ำหลาย ๆ รอบ (stage) ซึ่งในแต่ละรอบก็จะตัดพื้นที่ ที่เป็นภาพ negative ออกไปในทุกรอบที่พบ เมื่อจบกระบวนการแล้ว จำนวนของ sub window ที่เป็น negative จะลดลง จนได้รูปร่างที่ต้องการ และในการจำแนกเพื่อหารูปร่างที่ต้องการนี้จะทำกับภาพอินทิกรัล
Bayesian
เป็นวิธีการเรียนรู้ที่ใช้หลักการของความน่าจะเป็น ซึ่งมีพื้นฐานมาจากทฤษฎีของเบย์ (Bayes theorem) เข้ามาช่วยในการเรียนรู้ จุดมุ่งหมายก็เพื่อต้องการสร้างโมเดลที่อยู่ในรูปของความน่าจะเป็น ซึ่งเป็นค่าที่บันทึกได้จากการสังเกต จากนั้นนำโมเดลมาหาว่าสมมติฐานใดถูกต้องที่สุด โดยใช้ความน่าจะเป็นเข้ามาช่วย ความรู้ก่อนหน้า หมายถึง ความรู้ที่เรามีเกี่ยวกับสมมติฐานแต่ละตัวก่อนที่เราจะเก็บข้อมูล เมื่อใช้งานเราจะนำความน่าจะเป็นของข้อมูลที่เก็บได้มาปรับสมมติฐานซ้ำอีกครั้ง ข้อดีของวิธีการเรียนรู้แบบนี้ก็คือเราสามารถใช้ข้อมูลและความรู้ก่อนหน้า (Prior knowledge) เข้ามาช่วยในการเรียนรู้ได้ซึ่งพบว่าวิธีนี้ให้ประสิทธิภาพในการเรียนรู้ได้ดีไม่ด้อยกว่าวิธีการเรียนรู้ประเภทอื่น
(Template Matching)
การนำภาพที่ต้องการหาไปเปรียบเทียบกับภาพแบบตัวอย่าง Template ซึ่งภาพแบบตัวอย่างนี้จะเก็บค่าและกำหนดลักษณะสำคัญต่าง ๆ ที่สามารถแยกความแตกต่างของภาพได้ และเมื่อนำภาพแบบตัวอย่าง Template มาเปรียบเทียบกับภาพจะสามารถคำนวณได้จากสมการ
