ซัพพอร์ตเวกเตอร์แมชชิน (Support Vector Machine: SVM)

ตัวจำแนกเชิงเส้น

สำหรับตัวจำแนกเชิงเส้น f แสดงดังสมการ (1) จะจำแนกข้อมูลไปยังคลาส Ο หรือ คลาส Δ  เมื่อฟังก์ชัน sign คืนค่า Ο หรือ Δ  ดังภาพที่ 1

f(x,w,b) = sign(wx – b)  ———–(1)

เมื่อ x คือข้อมูล w แทนเวกเตอร์น้ำหนัก และ b  เป็นค่าคงที่ จะเห็นได้ว่าถ้าต้องการแยกข้อมูลในระนาบ 2 มิติ ออกเป็น 2 กลุ่ม ได้แก่ Ο และคลาส Δ จะสามารถใช้เส้นตรงแยกได้ดังภาพ 1(ก)

         

(ก)                                                                        (ข)

ภาพที่ 1 ตัวจำแนกเชิงเส้น

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

 

Support Vector Machine: SVM

ซัพพอร์ตเวกเตอร์แมชชิน (Support Vector Machine: SVM) เป็นตัวจำแนกเชิงเส้น (Linear Classifier) แบบ 2 คลาส ซึ่งเป็นที่ยอมรับถึงประสิทธิภาพของการจำแนกที่เหนือว่าวิธีการจำแนกอื่นๆ ข้อได้เปรียบของ SVM คือมีประสิทธิภาพในการจำแนกข้อมูลที่มีมิติจำนวนมากได้ นอกจากนี้การใช้ฟังก์ชันเคอร์เนล (Kernel Function) เพื่อแปลงข้อมูลไปยังมิติที่สูงขึ้นในปริภูมิคุณลักษณะ (Feature Space) สามารถจำแนกข้อมูลที่มีความคลุมเครือได้อย่างมีประสิทธิภาพ หลักการของ SVM คือการหาเส้นตรงที่มีมาร์จินที่โตที่สุด (Maximum Margin) ที่สามารถแบ่งข้อมูลออกเป็น 2 คลาส ดังตัวอย่างในภาพที่ 2 เป็นข้อมูลขนาด 2 มิติ โดนถูกจำแนกออกเป็น 2 คลาส ได้แก่ + (Ο) และคลาส – (Δ) โดยเส้นตรงที่ใช้แบ่งข้อมูลมีมาร์จินเท่ากับ M=2w ซึ่ง  เป็นความกว้างระหว่างเส้นตรงกับซัพพอร์เวคเตอร์ (Support vector) ของข้อมูลทั้ง 2 คลาส (  และ )

ภาพที่ 2 ตัวอย่างของตัวแบบจำแนก SVM บนข้อมูลขนาด 2 มิติ

 

การจำแนกเชิงเส้นด้วยมาร์จินที่โตที่สุด 

การใช้เส้นตรงสำหรับแบ่งข้อมูลเป็น 2 กลุ่มด้วยมาร์จินที่โตที่สุด (Maximum Margin) เป็นวิธีที่การันตีได้ว่าจะสามารถแยกข้อมูลได้โดยมีความผิดพลาดน้อยที่สุด โดยมี support vector เป็นตัวกำหนดขนาดของ Margin ดังนั้นถ้าข้อมูลมีการเปลี่ยนแปลงใดๆ เส้นตรงจำแนกก็ยังขึ้นอยู่กับ support vector ซึ่งจะยังเป็น Maximum Margin อยู่ ในภาพที่ 3 เป็นการหา Maximum Margin ในเชิงคณิตศาสตร์ จากภาพที่ 3 จะเห็นได้ว่าข้อมูล x จะถูกแบ่งเป็นระนาบบวก และระนาบลบ โดยมีสมการคือ w·x+b>=1 สำหรับคลาส+ และ w·x+b<=-1 สำหรับคลาส- ดังนั้นจะสามารจำแนกข้อมูลได้โดย

+1 ถ้า w·x + b >= +1

-1 ถ้า w·x + b <= -1

ถ้า -1 < w·x+b < +1

 

ภาพที่ 3 การคำนวณ Maximum Margin

 

ในการหาความกว้างมาร์จิน (margin width)   กำหนดให้  x-  เป็นจุดอยู่บนระนาบลบ และให้ x+   เป็นจุดอยู่บนระนาบบวก และทั้งสองจุดใกล้กันมากที่สุด ดังภาพที่ 4  จะมีเวกเตอร์ u บนระนาบบวกและทำนองเดียวกันเวกเตอร์ v บนระนาบลบ และมีเวกเตอร์ w ที่เป็นเวกเตอรน้ำหนักของเส้นจำแนก ดังนั้นจะเกิดเวกเตอร์ตั้งฉากกันจะได้ (u-v)·w = 0 การคำนวณหาความกว้างของมาร์จินในรูปที่  3  ในเทอมของ w และ b  สามารถหาได้จากระบบสมการต่อไปนี้

 

ภาพที่ 4 การหาค่า Margin

 

w·x+ + b = +1   ———–(2)

w·x + b  = -1    ———–(3)

x+ = x + δw      ———–(4)

|x+ – x| = M      ————(5)

เมื่อ δ เป็นขนาดของเวกเตอร์ w จะได้ว่า จาก (2) และ (4)

w·(x + δw) + b = +1

w·x + b +  δw·w  = +1

-1 + δw·w = 1

ดังนั้น δ = 2/(w.w)     ————–(6)

จากสมการที่ (4) และ (5) จะได้

M = |x+ – x| = |δw| = δ sqrt(w·w)    ————–(7)

จากสมการที่ (6) และ (7) จะได้

M = (2/(w.w)) sqrt(w·w)  = 2/(sqrt(w·w))    —————(8)

เนื่องจากเราสามารถทราบค่าของเวกเตอร์ w และ ค่าคงที่ b จะทำให้สามารถคำนวณค่า margin M ได้จากสมการที่ 8 จากนั้นใช้วิธีการค้นหาค่า M ที่มากที่สุดด้วยวิธีต่างๆ เช่น Gradient Descent, Simulated Annealing, Newton method, EM เป็นต้น เพื่อให้ได้ค่าคำตอบที่เหมาะสม (optimal solution) ต่อไป

อ้างอิง

รศ. ดร. ศาสตรา วงศ์ธนวสุ, ปัญญาประดิษฐ์ ทฤษฎี โปรแกรม และการประยุกต์, สำนักพิมพ์มหาวิทยาลัยขอนแก่น, 2560.