เครื่องเวกเตอร์ค้ำยัน

ตัวอย่างข้อมูลสองชั้นที่มีเส้นแบ่งได้หลายเส้น เส้น A เว้นระยะขอบว่างระหว่างชั้นข้อมูลกว้างกว่าเส้น B

เครื่องเวกเตอร์ค้ำยัน (อังกฤษ: support-vector machine; SVM) หรือ โครงข่ายเวกเตอร์ค้ำยัน (support-vector network) เป็นโมเดลการเรียนรู้แบบมีผู้สอนสำหรับการจำแนกประเภทข้อมูลและการถดถอย โมเดลดั้งเดิมสำหรับการจำแนกสองชั้นจะหาไฮเปอร์เพลนที่แบ่งตัวอย่างฝึกสองกลุ่ม โดยเลือกเส้นแบ่งที่มีระยะขอบ (margin) ถึงตัวอย่างใกล้ที่สุดกว้างที่สุด ตัวอย่างฝึกที่กำหนดตำแหน่งของเส้นแบ่งเรียกว่าเวกเตอร์ค้ำยัน (support vector)

SVM เชิงเส้นใช้เส้นตรงในสองมิติ ระนาบในสามมิติ หรือไฮเปอร์เพลนในมิติที่สูงกว่าเป็นขอบเขตการตัดสินใจ เมื่อเส้นแบ่งเชิงเส้นไม่เพียงพอ SVM สามารถใช้ฟังก์ชันเคอร์เนลคำนวณผลคูณภายในเสมือนอยู่ในปริภูมิคุณลักษณะอีกปริภูมิหนึ่ง จึงสร้างขอบเขตการตัดสินใจไม่เป็นเชิงเส้นได้โดยไม่ต้องสร้างพิกัดในปริภูมินั้นโดยตรง วิธีนี้เรียกว่าเคล็ดลับเคอร์เนล (kernel trick) SVM เป็นตระกูลวิธี ไม่ใช่คำรับรองว่าวิธีนี้ให้ผลดีที่สุดกับทุกชุดข้อมูล; ผลขึ้นกับลักษณะเด่น การปรับพารามิเตอร์ วิธีประเมิน และโจทย์ที่นำไปใช้

หลักการ

การจำแนกสองชั้นและไฮเปอร์เพลน

พิจารณาชุดข้อมูลฝึก $\{(\mathbf {x} _{i},y_{i})\}_{i=1}^{n}$ ซึ่ง $\mathbf {x} _{i}$ เป็นเวกเตอร์คุณลักษณะ และกำหนดป้ายกำกับของการจำแนกสองชั้นเป็น $y_{i}\in \{-1,+1\}$ SVM เชิงเส้นเรียนรู้เวกเตอร์น้ำหนัก $\mathbf {w}$ และค่าคงที่ $b$ เพื่อสร้างฟังก์ชันตัดสินใจ

$f(\mathbf {x} )=\mathbf {w} ^{\mathsf {T}}\mathbf {x} +b$

จุดที่ทำให้ $f(\mathbf {x} )=0$ คือไฮเปอร์เพลน แผนการจำแนกพื้นฐานให้ผลเป็น ${\hat {y}}=\operatorname {sign} (f(\mathbf {x} ))$ จึงใช้เครื่องหมายของคะแนนตัดสินว่าตัวอย่างอยู่คนละด้านของไฮเปอร์เพลน ไม่ได้หมายความว่าค่าสัมบูรณ์ของคะแนนเป็นความน่าจะเป็นของชั้นข้อมูล

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

หากตัวอย่างฝึกแยกเชิงเส้นได้ มีไฮเปอร์เพลนที่แบ่งข้อมูลถูกต้องได้หลายอัน SVM เลือกไฮเปอร์เพลนที่เพิ่มระยะห่างจากเส้นแบ่งถึงตัวอย่างฝึกที่ใกล้ที่สุดของทั้งสองด้านให้มากที่สุด เมื่อปรับมาตราส่วนของ $\mathbf {w}$ และ $b$ ให้ขอบเขตของระยะขอบเป็น $\mathbf {w} ^{\mathsf {T}}\mathbf {x} +b=\pm 1$ ความกว้างระหว่างขอบเขตทั้งสองคือ $2/\lVert \mathbf {w} \rVert$ ดังนั้นปัญหาแบบระยะขอบแข็ง (hard margin) เขียนได้ว่า

${\underset {\mathbf {w} ,b}{\operatorname {minimize} }}\quad {\frac {1}{2}}\lVert \mathbf {w} \rVert ^{2}$

$y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}+b)\geq 1\quad \forall {i}$ (สำหรับทุก $i$)

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

ระยะขอบแบบอ่อน

ข้อมูลจริงมักมีสัญญาณรบกวน ชั้นข้อมูลซ้อนทับกัน หรือป้ายกำกับคลาดเคลื่อน จึงอาจไม่มีเส้นแบ่งที่จัดทุกตัวอย่างถูกต้อง SVM แบบระยะขอบแบบอ่อน (soft margin) เพิ่มตัวแปรผ่อนปรน $\xi _{i}\geq 0$ เพื่ออนุญาตให้ละเมิดระยะขอบได้ แล้วแก้ปัญหาต่อไปนี้ภายใต้เงื่อนไขบรรทัดที่สอง

${\underset {\mathbf {w} ,b,{\boldsymbol {\xi }}}{\operatorname {minimize} }}\quad {\frac {1}{2}}\lVert \mathbf {w} \rVert ^{2}+C\sum _{i=1}^{n}\xi _{i}$

$y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}+b)\geq 1-\xi _{i},\quad \xi _{i}\geq 0$

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

เวกเตอร์ค้ำยันและรูปแบบทวิภาค

เมื่อตั้งปัญหาในรูปทวิภาค (dual form) ตัวอย่างแต่ละตัวมีสัมประสิทธิ์ $\alpha _{i}$ และฟังก์ชันตัดสินใจเชิงเส้นเขียนได้เป็น

$f(\mathbf {x} )=\sum _{i=1}^{n}\alpha _{i}y_{i}\,\mathbf {x} _{i}^{\mathsf {T}}\mathbf {x} +b$

ตัวอย่างที่มี $\alpha _{i}\neq 0$ คือเวกเตอร์ค้ำยัน จึงมีเพียงตัวอย่างส่วนหนึ่งที่ปรากฏโดยตรงในฟังก์ชันตัดสินใจ สำหรับระยะขอบแบบแข็ง เวกเตอร์ค้ำยันอยู่บนขอบของระยะขอบ; สำหรับระยะขอบแบบอ่อน เวกเตอร์ค้ำยันอาจอยู่บนหรือภายในระยะขอบ และบางตัวอาจถูกจำแนกผิดได้ คำว่า “ค้ำยัน” จึงไม่ได้หมายถึงตัวอย่างที่เป็นตัวแทนทุกตัวของชั้นข้อมูล แต่หมายถึงตัวอย่างที่มีผลต่อเส้นแบ่งที่เรียนรู้ได้

เคล็ดลับเคอร์เนล

แนวคิดของวิธีเคอร์เนล: สร้างตัวจำแนกเชิงเส้นในปริภูมิคุณลักษณะ แล้วได้ขอบเขตการตัดสินใจไม่เป็นเชิงเส้นเมื่อมองในปริภูมิข้อมูลเดิม

ให้ $\phi (\mathbf {x} )$ แทนการแปลงข้อมูลสู่ปริภูมิคุณลักษณะ หากคำนวณได้ว่า

$K(\mathbf {x} ,\mathbf {z} )=\langle \phi (\mathbf {x} ),\phi (\mathbf {z} )\rangle$

ก็ไม่จำเป็นต้องสร้าง $\phi (\mathbf {x} )$ อย่างชัดแจ้ง เพราะแทนผลคูณภายในในรูปทวิภาคด้วย $K$ ได้โดยตรง ฟังก์ชันตัดสินใจจึงเป็น

$f(\mathbf {x} )=\sum _{i=1}^{n}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x} )+b$

ฟังก์ชันที่ใช้บ่อยได้แก่เคอร์เนลเชิงเส้น $K(\mathbf {x} ,\mathbf {z} )=\mathbf {x} ^{\mathsf {T}}\mathbf {z}$, เคอร์เนลพหุนาม และเคอร์เนลฐานรัศมีแบบเกาส์เซียน (radial basis function: RBF) $K(\mathbf {x} ,\mathbf {z} )=\exp(-\gamma \lVert \mathbf {x} -\mathbf {z} \rVert ^{2})$ โดย $\gamma$ เป็นพารามิเตอร์ความกว้างของเคอร์เนล เคอร์เนลที่ใช้กับ SVM ต้องสอดคล้องกับผลคูณภายในของปริภูมิคุณลักษณะ (ในทางปฏิบัติมักตรวจด้วยเงื่อนไขเมทริกซ์กึ่งกำหนดบวก) มิฉะนั้นคุณสมบัติของปัญหาการหาค่าเหมาะที่สุดมาตรฐานอาจไม่คงอยู่

เคอร์เนลไม่ได้ทำให้ข้อมูล “แยกได้เสมอ” และมิติที่สูงขึ้นไม่ได้ทำให้โมเดลดีกว่าโดยตัวมันเอง การเลือกเคอร์เนลและค่าของ $C$, $\gamma$ หรือดีกรีของพหุนามเป็นส่วนหนึ่งของการเลือกโมเดล จึงต้องทำภายในกระบวนการตรวจสอบไขว้ (cross-validation) โดยกันชุดทดสอบสุดท้ายไว้ต่างหาก

การฝึกและการประเมินผล

การฝึก SVM คือการแก้ปัญหาการหาค่าเหมาะที่สุด ไม่ใช่เพียงวาดเส้นแบ่งผ่านข้อมูล สำหรับ SVM เชิงเส้นอาจแก้ปัญหาในรูปปฐมภูมิ (primal form) ได้โดยตรง; SVM เคอร์เนลมักใช้รูปทวิภาคหรืออัลกอริทึมแยกปัญหาเป็นส่วนย่อย เช่น sequential minimal optimization (SMO) เพื่อไม่ต้องแก้ปัญหากำลังสองขนาดใหญ่ในคราวเดียว ซอฟต์แวร์ SVM จึงต่างกันที่ชนิดของโมเดล ตัวแก้ปัญหา และการรองรับข้อมูลขนาดใหญ่ ไม่ใช่เพียงต่างกันที่ชื่อคำสั่ง

ก่อนฝึก มักปรับมาตราส่วนของคุณลักษณะเชิงตัวเลขโดยอาศัยเฉพาะข้อมูลฝึก เพราะระยะห่างและเคอร์เนล RBF ไวต่อหน่วยวัดของตัวแปร ตัวอย่างเช่น คุณลักษณะที่วัดเป็นหลักล้านอาจครอบงำคุณลักษณะที่อยู่ระหว่างศูนย์ถึงหนึ่ง หากปรับมาตราส่วนด้วยข้อมูลทั้งชุดก่อนแยกทดสอบจะทำให้ข้อมูลจากชุดทดสอบรั่วไหลเข้าสู่ขั้นตอนฝึกได้ สำหรับข้อมูลไม่สมดุล ควรรายงานตัวชี้วัดที่สะท้อนเป้าหมายของโจทย์ เช่น precision, recall, F1 score หรือพื้นที่ใต้เส้นโค้ง ROC ร่วมกับการกำหนดน้ำหนักชั้นข้อมูลหรือเกณฑ์ตัดสินใจอย่างชัดเจน แทนการรายงานความถูกต้องโดยรวมเพียงค่าเดียว

รูปแบบและส่วนขยาย

รูปแบบสำคัญของเครื่องเวกเตอร์ค้ำยัน

รูปแบบ	งานหรือแนวคิด	ข้อสังเกต
SVM เชิงเส้น	การจำแนกด้วยไฮเปอร์เพลนในปริภูมิข้อมูลเดิม	เหมาะเป็นจุดเริ่มต้นที่ตีความน้ำหนักได้ง่ายกว่าในบางบริบท และหลีกเลี่ยงการสร้างเมทริกซ์เคอร์เนลเต็ม
SVM เคอร์เนล	การจำแนกไม่เป็นเชิงเส้นผ่านฟังก์ชันเคอร์เนล	ต้องเลือกเคอร์เนลและไฮเปอร์พารามิเตอร์; ต้นทุนการคำนวณอาจสูงเมื่อจำนวนตัวอย่างหรือจำนวนเวกเตอร์ค้ำยันมาก
SVM หลายชั้นข้อมูล	การจำแนกตั้งแต่สามชั้นขึ้นไป	มักลดเป็นปัญหาสองชั้นหลายปัญหา เช่น one-versus-rest หรือ one-versus-one; ยังมีสูตรที่แก้หลายชั้นพร้อมกัน
การถดถอยเวกเตอร์ค้ำยัน (support-vector regression: SVR)	ทำนายค่าต่อเนื่อง	ใช้การสูญเสียแบบ $\varepsilon$-insensitive ซึ่งไม่ลงโทษความคลาดเคลื่อนภายในท่อกว้าง $\varepsilon$
SVM ชั้นเดียว (one-class SVM)	ตรวจจับความแปลกใหม่หรือค่านอกกลุ่มจากข้อมูลของชั้นเดียว	เรียนรู้ขอบเขตของข้อมูลปกติ ไม่ใช่การจำแนกสองชั้นที่มีตัวอย่างของทั้งสองชั้น

การจำแนกหลายชั้นข้อมูล

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

การถดถอยเวกเตอร์ค้ำยัน

ตัวอย่าง SVR: ท่อ $\varepsilon$ กว้างขึ้นทำให้โมเดลไม่ลงโทษความคลาดเคลื่อนขนาดเล็กมากนัก

ในการถดถอยเวกเตอร์ค้ำยัน (SVR) เป้าหมายไม่ใช่เลือกป้ายกำกับ แต่เป็นหาฟังก์ชันที่คลาดจากค่าจริงไม่เกิน $\varepsilon$ ให้มากที่สุด พร้อมควบคุมความซับซ้อนของฟังก์ชัน จุดข้อมูลที่อยู่นอกท่อ $\varepsilon$ หรือแตะขอบท่อมีบทบาทเป็นเวกเตอร์ค้ำยันได้ SVR มีทั้งรุ่นเชิงเส้นและรุ่นใช้เคอร์เนล จึงใช้กับความสัมพันธ์ไม่เป็นเชิงเส้นได้เช่นเดียวกับ SVM สำหรับการจำแนก

การตรวจจับความแปลกใหม่

SVM ชั้นเดียวเรียนรู้บริเวณของปริภูมิคุณลักษณะที่รองรับข้อมูลตัวอย่างชุดเดียว แล้วใช้ตรวจว่าตัวอย่างใหม่อยู่ภายในบริเวณนั้นหรือไม่ จึงมักใช้ในบริบทการตรวจจับความแปลกใหม่ (novelty detection) โดยต้องระวังว่าผลลัพธ์ขึ้นกับนิยามของ “ปกติ” ในข้อมูลฝึก ตลอดจนเคอร์เนลและพารามิเตอร์ที่เลือก

จุดเด่นและข้อจำกัด

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

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

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

ประวัติ

รากฐานทางทฤษฎีของ SVM อยู่ในทฤษฎีการเรียนรู้เชิงสถิติและงานของวลาดีมีร์ วัปนิกกับอเล็กเซย์ เชอร์โวนเยนคิส (Alexey Chervonenkis) ว่าด้วยความสามารถของตัวจำแนกและการวางนัยทั่วไป ค.ศ. 1992 เบิร์นฮาร์ด โบเซอร์ อิซาแบล กียง และวัปนิกเสนออัลกอริทึมฝึกตัวจำแนกระยะขอบสูงสุดและการใช้เคอร์เนลในงานนี้ ต่อมาโครินนา กอร์เตสและวัปนิกเผยแพร่ support-vector networks ใน ค.ศ. 1995 ซึ่งกำหนดรูปแบบระยะขอบแบบอ่อนที่กลายเป็นแกนสำคัญของ SVM ในการใช้งานจริง

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

การประยุกต์

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

ซอฟต์แวร์

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

ดูเพิ่ม

• การเรียนรู้ของเครื่อง
• การเรียนรู้แบบมีผู้สอน
• การแบ่งประเภทข้อมูล
• การวิเคราะห์การถดถอย
• ตัวจำแนกเชิงเส้น
• เคอร์เนล (การเรียนรู้ของเครื่อง)
• การตรวจสอบไขว้
• การหาค่าเหมาะที่สุด

อ่านเพิ่มเติม

• Cristianini, Nello; Shawe-Taylor, John (2000). An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press. ISBN 978-0-521-78019-3. ตำราบทนำที่อธิบาย SVM และวิธีเคอร์เนลอย่างเป็นระบบ
• Schölkopf, Bernhard; Smola, Alexander J. (2002). Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press. ISBN 978-0-262-19475-4. ครอบคลุมทฤษฎีเคอร์เนล การทำให้เป็นระเบียบ และการหาค่าเหมาะที่สุด
• Steinwart, Ingo; Christmann, Andreas (2008). Support Vector Machines. Springer. doi:10.1007/978-0-387-77242-4. ISBN 978-0-387-77242-4. ตำราเชิงทฤษฎีละเอียดเรื่องความสอดคล้องและอัตราการวางนัยทั่วไป