การแนะนำ
ในบทความนี้ ผมจะพูดถึง Support Vector Machine (SVM) ซึ่งเป็นอัลกอริธึมการเรียนรู้ภายใต้การดูแลสำหรับการจำแนกข้อมูล โดยทั่วไป SVM ใช้สำหรับแยกจุดข้อมูลหลายมิติออกเป็นสองคลาสที่แตกต่างกัน เพื่อความง่าย เราจะพิจารณาเฉพาะกรณีสองมิติเท่านั้น (แนวคิดสำหรับมิติที่สูงกว่าก็เหมือนกัน) ขั้นแรก เราจะกำหนดฟังก์ชันวัตถุประสงค์ภายใต้ข้อจำกัด แล้วพิจารณาฟังก์ชันคู่ลากรองจ์เพื่อแก้ไขปัญหาการหาค่าเหมาะที่สุดนี้ นอกจากนี้ ผมจะพิสูจน์ว่าการแก้ปัญหาแบบคู่นั้นเทียบเท่ากับการแก้ปัญหาเบื้องต้น
รองรับเครื่องเวกเตอร์
สมมติว่าเรามีชุดข้อมูลต่อไปนี้ และเราต้องค้นหาบรรทัดที่ดีที่สุดที่แยกข้อมูลออกเป็นสองคลาส:
ตามที่ระบุในรูปที่ 1 มีหลายบรรทัดที่สามารถทำงานได้ อย่างไรก็ตาม เกณฑ์ของเราสำหรับบรรทัดที่ดีที่สุดจะเป็นดังนี้:
ระยะห่างจากเส้นL1 ถึง L2 เท่ากับระยะทางจาก L2 ถึง L3 เวกเตอร์ W ตั้งฉากกับเส้นทั้งหมด ซึ่งก็คือ L1, L2 และ L3 วัตถุประสงค์คือเพื่อเพิ่มระยะขอบระหว่างบรรทัด L1 และ L3 ให้สูงสุด นอกจากนี้ ควรสังเกตว่าบรรทัด L1 และ L3 ต้องมีอย่างน้อยหนึ่งจุดจากคลาสที่เหมาะสม หลังจากได้รับสมการสำหรับเส้น L2 แล้ว ก็สามารถจำแนกจุดข้อมูลใหม่ได้อย่างง่ายดาย
ตามที่เห็นได้ชัดเจนจากรูปภาพ มีการพึ่งพาการทำงานระหว่างเวกเตอร์ W และระยะขอบ เราจะสร้างการพึ่งพานี้อย่างเป็นระบบแล้วพยายามแก้ไขปัญหา
จากรูปที่ 2 สามารถสรุปได้หลายประการ ประการแรก ผลคูณดอทของเวกเตอร์ W โดยมีเวกเตอร์ X ใดๆ อยู่บนเส้นตรง L2 ไม่ขึ้นอยู่กับ ตำแหน่งของจุดบนเส้นและสามารถเขียนแทนด้วยค่าคงที่ C
สมมติว่าค่าคงที่ B =-C เราสามารถเขียนสูตรข้างต้นใหม่ได้เป็น:
จริงๆ แล้วนี่คือสมการของ L2
เราสามารถมองสมการ 1.1 เป็นเส้นโค้งระดับของ
เมื่อฟังก์ชันถูกตั้งค่าให้เท่ากับศูนย์
เห็นได้ชัดว่าเวกเตอร์ W คือการไล่ระดับสีของ F (X) ซึ่งบอกเป็นนัยว่าฟังก์ชันนั้นเพิ่มขึ้นในทิศทางของ W ตอนนี้เราสามารถสรุปได้ว่าสำหรับจุดที่อยู่เหนือ L2 ค่าของฟังก์ชันจะเป็นค่าบวก และสำหรับจุดที่ต่ำกว่าจะเป็นลบ เราต้องการให้ F (X) เป็นฟังก์ชันที่เส้นโค้งระดับที่ F (X) = 1และF (X) =-1 สร้างเส้น L1 และ L3 ตามลำดับ
คล้ายกับ L2 สำหรับเส้น L1และ L3 ผลคูณดอทของ W ที่มีเวกเตอร์ใดๆ X นอนอยู่บนบรรทัดนั้นสามารถแสดงเป็น:
เมื่อใช้ประโยชน์จากข้อเท็จจริงที่ว่าฟังก์ชันเพิ่มขึ้นตามความชัน เราสามารถพูดได้ว่าสำหรับจุดที่สูงกว่า L1 ความไม่เท่าเทียมกันต่อไปนี้ยังคงอยู่:
และสำหรับผู้ที่อยู่บรรทัดล่าง L3:
ตามที่ระบุไว้ในรูปที่ 1 เรารู้ว่าคะแนนที่เราให้มานั้นอยู่ในคลาสใด (ระบุด้วยสีดำและสีส้ม) ให้เรากำหนดตัวแปรสเกลาร์ yi สำหรับจุด 2D xi สำหรับจุดที่เป็นไปตามความไม่เท่าเทียมกัน 1.1 ให้ตัวแปร yi เป็น +1 เพื่อระบุคลาสหนึ่ง และสำหรับจุดที่ตรงตามความไม่เท่าเทียมกัน 1.2 yi คือ -1 เพื่อระบุคลาสอื่น .
ในทั้งสองกรณี ความไม่เท่าเทียมกันดังต่อไปนี้:
จากนี้ไปความไม่เท่าเทียมกัน 1.3 ที่ยึดถือทุกประเด็นจะเป็นข้อจำกัดของเรา
ตอนนี้ให้เราพิจารณารูปภาพต่อไปนี้เพื่อหาสูตรสำหรับมาร์จิ้นของเรา:
อัตรากำไรขั้นต้นสามารถคำนวณเป็นผลคูณดอทของ X1-X3 โดยมีเวกเตอร์หน่วยไปในทิศทางของ W
จากสมการสำหรับL1 และ L3:
ดังนั้นมาร์จิ้นก็จะเป็น
ในที่สุดเราก็สามารถระบุปัญหาได้เช่นการเพิ่มระยะขอบนี้ให้สูงสุดภายใต้ข้อจำกัดของความไม่เท่าเทียมกัน 1.3
เพื่อความสะดวกทางคณิตศาสตร์ เราจะย่อให้เล็กสุด
ขึ้นอยู่กับความไม่เท่าเทียมกัน 1.3 ซึ่งสามารถเขียนใหม่ได้เป็น:
ในตอนนี้ ให้เราทิ้งปัญหานี้ไว้ที่นี่และแนะนำฟังก์ชันคู่ลากรองจ์สำหรับการแก้ปัญหาการหาค่าเหมาะที่สุดด้วยข้อจำกัดของความไม่เท่าเทียมกัน
ความเป็นคู่แบบลากรองจ์
เพื่อให้เข้าใจแนวคิดเรื่องความเป็นคู่ ก่อนอื่นให้เราสรุปปัญหาโดยกล่าวซ้ำดังนี้:
ย่อเล็กสุด
ขึ้นอยู่กับข้อจำกัดความไม่เท่าเทียมกันดังต่อไปนี้:
โดยที่ x เป็นจุดในปริภูมิหลายมิติ
นี่คือปัญหาหลักของเรา ผมขอแสดงปัญหานี้ด้วย P1 จากนี้ไป ฉันจะเรียกมันว่า P1 ในที่สุด เราจะมาแนะนำฟังก์ชันคู่ลากรองจ์ ซึ่งแปลง P1 ดังนี้:
ปัญหาคู่เขียนไว้ดังนี้:
จากนี้ไปเราจะพูดถึงปัญหานี้โดยใช้ชื่อว่า "ปัญหาคู่" อันดับแรก เราจะแสดงให้เห็นว่าวิธีแก้ไขปัญหาแบบคู่นั้นน้อยกว่าหรือเท่ากับวิธีแก้ไขปัญหาเบื้องต้น สิ่งนี้เรียกว่า “ความเป็นคู่ที่อ่อนแอ" และสามารถแสดงทางคณิตศาสตร์ได้ดังต่อไปนี้:
ข้อพิสูจน์ความเป็นคู่ที่อ่อนแอ
ใน P1 ถ้าสำหรับ x บางส่วน มีการละเมิดข้อจำกัดอย่างน้อยหนึ่งข้อ ดังนั้นค่าสูงสุดของ L เทียบกับ lambda จะเป็นค่าบวก อนันต์ ในรูปแบบทางคณิตศาสตร์สามารถแสดงได้ดังนี้
ใน P1 ถ้า x ละเมิดข้อจำกัดอย่างน้อยหนึ่งข้อ
มิฉะนั้น (หากไม่มีการละเมิดข้อจำกัด):
เราสามารถสรุปได้ดังนี้ โดยสมมติว่า P* เป็นคำตอบของ P1 และ x* คือจุดที่ F(x*) = P*
ดังนั้นเราจึงสามารถเขียนความเป็นคู่ที่อ่อนแอใหม่ได้เป็น:
(โปรดทราบว่าค่าสูงสุดหรือต่ำสุดของฟังก์ชันเป็นจำนวนจำกัด ในขณะที่ค่าสูงสุดและค่าต่ำสุดสามารถเป็นจำนวนอนันต์ได้)
เพื่อพิสูจน์ความไม่เท่าเทียมกันสำหรับความเป็นคู่ที่อ่อนแอ ให้เราแสดงให้เห็นก่อนว่าความไม่เท่าเทียมกันยังคงอยู่
ในรูปแบบขยาย:
เพียงแทนที่ x* ไปทางซ้าย เราก็สามารถพิสูจน์ได้ว่า:
อสมการนี้ถือเป็น x* เนื่องจากเงื่อนไขต่อไปนี้:
เนื่องจากความไม่เท่าเทียมกันมีอยู่ที่ x*ค่าที่น้อยที่สุดจะน้อยกว่า P* อย่างแน่นอน
เมื่อประเมินค่าต่ำสุดของ L สำหรับ x เราถือว่าแลมบ์ดาคงที่และ x แปรผัน ดังนั้น สำหรับแลมบ์ดาที่ไม่ติดลบทั้งหมด ความเป็นคู่ที่อ่อนแอจะได้รับการตอบสนอง ซึ่งรวมถึงค่าของแลมบ์ดาที่ทำให้เกิดค่าน้อยที่สุดนี้ด้วย สามารถกำหนดได้ดังนี้:
ความเป็นคู่ที่แข็งแกร่ง
ในกรณีพิเศษ เมื่อฟังก์ชันวัตถุประสงค์และข้อจำกัดทั้งหมดนูนออกมา(ดังเช่นในปัญหา SVM ของเรา) ความเป็นคู่ที่แข็งแกร่งอาจคงอยู่ ซึ่งบอกว่า:
เราสามารถเขียนความเป็นคู่ที่แข็งแกร่งใหม่ได้ดังต่อไปนี้โดยแสดงค่า infimum ของ L สำหรับ xด้วยฟังก์ชันของ lambda:
ตอนนี้ให้เราแสดงคำตอบทางด้านซ้ายด้วย D*, ซึ่งฟังก์ชัน q ประเมินที่ดาวแลมบ์ดา
เราก็รู้เช่นกัน
เพราะจากนิยามของค่า infimum มันคือค่าต่ำสุดที่เป็นไปได้และสามารถเท่ากับด้านขวามือของอสมการข้างต้นได้มากที่สุด เมื่อพิจารณาข้อเท็จจริงนี้แล้ว
เพียงลดความซับซ้อนของอสมการข้างต้น เราก็จะได้:
และเป็นไปได้ก็ต่อเมื่อ:
ฉันอยากจะย้ำว่าแต่ละเทอมของการบวกสามารถเป็นจำนวนลบหรือศูนย์ได้ ดังนั้น เงื่อนไขที่จำเป็น (เรียกว่าความหย่อนเสริม) เพื่อให้ผลรวมทั้งหมดเป็นศูนย์ก็คือ ที่จริงแล้ว เงื่อนไขทั้งหมดต้องเป็นศูนย์ ดังที่แสดงด้านล่าง:
เราสามารถอนุมานได้ว่าค่าแลมบ์ดาที่เกี่ยวข้องกับข้อจำกัดด้านค่าลบจะต้องเป็นศูนย์ ในแง่ของ SVM ค่าแลมบ์ดาที่เกี่ยวข้องกับจุดที่ไม่อยู่บนบรรทัด L1 และ L3 ต้องเป็นศูนย์ ตามหลักการแล้ว การเพิ่มหรือลบจุดเหล่านี้ไม่ควรเปลี่ยนระยะขอบ
ปัญหา SVM
ตอนนี้ให้เรากลับมาที่ปัญหาเดิมของเราและพยายามแก้ไขโดยแนะนำปัญหาคู่
ย่อเล็กสุด
ขึ้นอยู่กับข้อจำกัดดังต่อไปนี้
ส่วนขยายลากรองจ์จะเป็น
และปัญหาคู่:
เราต้องเริ่มต้นด้วยการค้นหาค่า infimum ซึ่งทำได้โดยการค้นหาอนุพันธ์ย่อยที่เกี่ยวข้องกับ W และ B และตั้งค่าให้เท่ากับศูนย์:
เมื่อแทนสมการเหล่านี้กลับไปสู่ปัญหาคู่ ปัญหาคู่จะเป็น:
โดยมีข้อจำกัดดังนี้
บทสรุป
ในบทความนี้ ฉันอธิบายว่าปัญหาการปรับให้เหมาะสมที่มีข้อจำกัดสามารถเปลี่ยนเป็นปัญหาคู่ได้อย่างไรด้วยการแนะนำส่วนขยาย Lagrangian นอกจากนี้เรายังได้รับเงื่อนไขที่จำเป็นที่เรียกว่า “ความหย่อนคล้อยเสริม”โดยสมมติว่าความเป็นคู่ที่แข็งแกร่งยังคงอยู่ สุดท้ายนี้ เราสามารถพูดได้ว่าถ้าเรามีวิธีแก้ปัญหาที่ดีที่สุดสำหรับปัญหาสองข้อ เราก็มีวิธีแก้ปัญหาที่ดีที่สุดสำหรับปัญหาหลักด้วย หรือในทางกลับกัน ทางออกที่ดีที่สุดสำหรับปัญหาข้อใดข้อหนึ่งพิสูจน์ได้ว่าสมมติฐานของเราถูกต้อง (ความเป็นคู่ที่แข็งแกร่ง) กล่าวอีกนัยหนึ่ง ช่องว่างความเป็นคู่ระหว่างปัญหาปฐมภูมิและปัญหาคู่คือศูนย์ ฉันหวังว่าตัวอย่าง SVM จะเป็นตัวอย่างที่ดีในการแสดงให้เห็นว่าปัญหาคู่สามารถนำไปใช้ในการแก้ปัญหาการจำแนกประเภทที่แท้จริงได้อย่างไร ท้ายที่สุด ผมอยากจะเน้นย้ำว่าสามารถใช้แนวทางเดียวกันนี้ในการค้นหาสมการของไฮเปอร์เพลนเพื่อแยกจุดข้อมูลหลายมิติออกเป็นสองคลาสได้
