SVM ตอนที่ 3: KKT-Conditions ใน Convex Optimization
ในโพสนี้ก็จะมาพูดกันต่อเรื่อง Convex Optimization ซึ่งจะนำมาแก้ปัญหาของ SVM โดยจะเน้นไปที่ KKT-Conditions ค่ะ
สำหรับใครที่ยังไม่ได้อ่านบทความแรกๆ สามารถอ่านได้ที่
SVM ตอนที่ 1: Support Vector Machine โมเดลคลาสสิคที่น่าศึกษา
SVM ตอนที่ 2: Lagrange Duality
ในบทความนี้เรามาดูกันว่า ที่มาของเงื่อนไขแต่ละข้อ มันเป็นมาอย่างไร และถ้าหากเราเข้าใจ เราก็จะได้สกิลมองแบบคณิตศาสตร์เพิ่มเติมด้วย แต่ว่าก่อนอื่นนั้น เปิดใจกว้างๆ และท่องว่า ไม่ยาก ไม่ยาก แล้วไปต่อกันเลยค่ะ :)
จุดเริ่มต้นของ KKT-Conditions คือ ต้องการหาว่า ระบบสมการที่ทั้งคำตอบจาก primal และ dual มีค่าเท่ากัน ต้องมีเงื่อนไขอย่างไรบ้าง เราจะมาค่อยๆทำความเข้าใจในแต่ละตัวค่ะ
เริ่มต้นจาก ถ้าเราต้องการให้คำตอบของ primal และ dual เท่ากัน ฉะนั้น ระบบสมการจะต้องไม่ละเมิดเงื่อนไขของทั้ง primal และ dual ค่ะ
ณ จุดค่า x = x* และ x* แทนค่า x ที่ทำให้สมการ f₀(x) มีค่าต่ำสุด พร้อมทั้งอยู่ในเงื่อนไขอสมการและสมการทั้งหมด อสมการและสมการเงื่อนไขในระบบ primal จะต้องเป็นดังนี้ ซึ่งเงื่อนไขสองข้อนี้จะเรียกว่า primal feasibility
ณ จุดที่ค่า λᵢ จากสมการของ dual มีค่าดีที่สุดเป็น λᵢ* จะต้องเป็นดังนี้ ซึ่งเงื่อนไขข้อนี้จะเรียกว่า dual feasibiliy
สามข้อแรกเข้าใจได้ไม่ยากเท่าไหร่ เพราะว่าหากจะให้คำตอบทั้ง primal และ dual เท่ากัน สมการจากทั้งสองระบบ จะต้องเป็นไปตามเงื่อนไขของแต่ละระบบ นั่นก็แปลว่า มีคำตอบใน primal และก็มีคำตอบใน dual แน่ๆ ไม่ได้ละเมิดเงื่อนไขใดๆ
เงื่อนไขข้อถัดไป จะเรียกว่า complementary slackness กล่าวเอาไว้ว่า
โดย สมการ optimization ของระบบ primal และ dual เป็นดังนี้ (ฝั่งซ้ายคือ primal ฝั่งขวาคือ dual)
ถ้าเราต้องการให้คำตอบที่ได้จาก primal และ dual มีค่าเท่ากัน ง่ายๆเลยคือ จะต้องให้เทอมตรงกลางคูณแล้วเท่ากับ 0 ดังนี้
ถ้าต้องการให้เทอมตรงกลางคูณแล้วมีค่าเป็น 0 ก็จะต้องให้ค่า λᵢ* = 0 หรือ ค่า fᵢ(x*) = 0 และถ้าหากว่า ค่า λᵢ* = 0 ของอสมการที่ i ก็จะหมายความว่า อสมการนั้น inactive หรือไม่ได้ใช้นั่นเอง และเป็นในกรณีที่ ค่า fᵢ(x*) < 0 (แบบไม่มีเครื่องหมายเท่ากับ) เดี๋ยวจะพูดถึงเคสนี้ในรายละเอียดมากขึ้น
และเงื่อนไขข้อสุดท้ายจะยากนิดนึง แต่มาลุยกันเลยค่ะ ซึ่งในข้อนี้ ก็คือสิ่งเดียวกับ Lagrange Multiplier อันโด่งดังนั่นเอง
เงื่อนไขข้อสุดท้ายกล่าวไว้ว่า
ผลบวกของค่า derivative ของฟังก์ชั่น อสมการ และสมการทุกตัว ณ จุดคำตอบ x=x* จะต้องเท่ากับ 0 ภายใต้ค่าที่ดีที่สุดของพารามิเตอร์ของ λᵢ* และ νᵢ* ของสมการ dual และเงื่อนไขในข้อนี้มีชื่อเรียกว่า stationarity และเงื่อนไขในข้อนี้เอง ที่ทำให้ปัญหาที่จะสามารถนำเอา KKT conditions ไปใช้ได้นั้น ฟังก์ชั่นทั้งหมด รวมฟังก์ชั่นที่ต้องการหาค่าต่ำสุด อสมการ และสมการเงื่อนไข จะต้องหาค่า derivative ได้
เรื่องมันมีอยู่ว่า ยกตัวอย่างระบบสมการดังนี้
f₀(x, y) = x²+y
h₁(x, y) = x²+y²-1 = 0 (สมการวงกลมรัศมีเท่ากับ 1 หน่วยนั่นเอง)
ในระบบสมการนี้ มีฟังก์ชั่นที่ต้องการหาค่าต่ำสุด โดยขึ้นกับตัวแปร x, y และสมการเงื่อนไข 1 สมการ ซึ่งสามารถพล็อตออกมาได้เป็นกราฟ ดังภาพ
ภาพในด้านซ้าย ที่จุดสีเขียว คือค่าต่ำสุดของฟังก์ชั่น ที่ยังอยู่ในสมการเงื่อนไข ซึ่งจะเห็นได้ว่า ณ จุดนั้น จะมีค่า derivative ของ f₀(x, y) แสดงเป็นสีน้ำเงิน ทิศทางชี้ขึ้น และค่า derivative ของ h₁(x, y) แสดงเป็นสีแดง ทิศทางชี้ลง ทั้งคู่มีทิศตรงข้าม แต่มีขนาดไม่เท่ากัน ซึ่งเป็นไปตามเงื่อนไข stationarity ดังนี้
และนี่คือตัวอย่างของระบบที่มีเงื่อนไขเป็นสมการ เรามาดูตัวอย่างของระบบที่มีอสมการเป็นเงื่อนไขกันบ้าง
ยกตัวอย่างระบบสมการเป็น
f₀(x, y) = x²+2y²
f₁(x, y) = (x²/2)+y²-2y+(3/2) ≤ 0 (พื้นทีในสมการวงรี โชว์เป็นเส้นสีแดง)
ในระบบสมการนี้ มีฟังก์ชั่นที่ต้องการหาค่าต่ำสุด โดยขึ้นกับตัวแปร x, y และอสมการเงื่อนไข 1 สมการ ซึ่งสามารถพล็อตออกมาได้เป็นกราฟ ดังภาพ
จากภาพ จุดสีเขียวคือค่าต่ำสุดที่หาได้ ในที่นี้จุดสีเขียวอยู่บนเส้นสีแดงพอดี นั่นคือตำแหน่งค่า x, y ที่ได้ จะทำให้ f₁(x, y) มีค่าเท่ากับ 0 นั่นคือ
f₁(x, y) = (x²/2)+y²-2y+(3/2) = 0
ฉะนั้นในที่นี้ ค่า λ₁* จะเป็นค่าบวก ตามเงื่อนไข complementary slackness และค่าบวกนั้น ก็จะต้องเป็นไปตามเงื่อนไข stationarity ด้วยค่ะ และในที่นี้จะถือว่าอสมการ f₁(x, y) นั้น activate เพราะค่า λ₁* ไม่ได้เท่ากับ 0
หากไม่เข้าใจในภาษาคณิตศาสตร์ ให้ลองพิจารณาจากรูป ซึ่งเมื่อดูจากรูป ค่าต่ำสุดที่ได้ของ f₀(x, y) ที่ไม่มีอสมการนั้น จะไม่เท่ากับค่าต่ำสุดที่ได้ เมื่อเราเพิ่มอสมการเข้าไป ฉะนั้น เคสนี้จึงถือว่าเงื่อนไขอสมการนี้ได้ถูกใช้งาน หรือ activate นั่นเอง
ลองมาดูอีกเคสกันค่ะ ยกตัวอย่างระบบสมการเป็น
f₀(x, y) = x²+2y²
f₁(x, y) = x²+y²-1 ≤ 0 (พื้นที่ในสมการวงกลมรัศมี 1 หน่วย)
ในระบบสมการนี้ มีฟังก์ชั่นที่ต้องการหาค่าต่ำสุด โดยขึ้นกับตัวแปร x, y และอสมการเงื่อนไข 1 สมการ ซึ่งสามารถพล็อตออกมาได้เป็นกราฟ ดังภาพ
ในเคสนี้นั้น ค่าต่ำสุดของฟังก์ชั่นคือจุดสีแดงในภาพ ซึ่งจุดสีแดงนี้ อยู่ข้างในวงกลม ที่เป็นอสมการเงื่อนไข ฉะนั้นตำแหน่งค่า x, y ที่ได้นั้น จะทำให้ f₁(x, y) มีค่าน้อยกว่า 0 นั่นคือ
f₁(x, y) = x²+y²-1 < 0
ฉะนั้นในที่นี้ เนื่องจาก f₁(x, y) ไม่ได้มีค่าเท่ากับ 0 ค่า λ₁* จึงต้องเป็น 0 ตามเงื่อนไข complementary slackness และในที่นี้จะถือว่าอสมการ f₁(x, y) นั้น inactivate เพราะค่า λ₁* เท่ากับ 0
หากไม่เข้าใจในภาษาคณิตศาสตร์ ให้ลองพิจารณาจากรูป ซึ่งเมื่อดูจากรูป ค่าต่ำสุดที่ได้ของ f₀(x, y) ที่ไม่มีอสมการนั้น จะเท่ากับค่าต่ำสุดที่ได้ เมื่อเราเพิ่มอสมการเข้าไป ฉะนั้น เคสนี้จึงถือว่าเงื่อนไขอสมการนี้ไม่ได้ถูกใช้งาน หรือ inactivate นั่นเอง (มีหรือไม่มีก็ได้)
โดยทั้งสองเคส ก็ยังคงไม่ละเมิดเงื่อนไข stationarity
เพราะในเคสที่สอง แม้ว่าค่าของ λ₁* = 0 แต่ที่ ณ จุดที่ f₀(x, y) มีค่าต่ำสุดนั้น derivative ของ f₀(x, y) ก็จะมีค่าเป็น 0 พอดี
ในบทความหน้า เราจะนำเอาทุกอย่างมาพิจารณาในบริบทของ SVM กันค่ะ
สำหรับบทความนี้อย่างน้อยก็อยากให้ทุกท่านได้เห็นแง่มุมในการพิจารณาสมการ สมการนั้นมีข้อดีที่ว่า ทุกอย่างเป็นไปตามลอจิกหมดเป๊ะๆ ทุกสมการจะต้องมีความเป็นหนึ่ง ไม่มีสอง ไม่มีความขัดแย้ง ถ้าเขียนออกมาแล้วมีข้อไหนขัดแย้งกันถือว่าใช้ไม่ได้ แปลว่าระบบการคิดของเรายังไม่เป็นระบบระเบียบมากพอค่ะ
ถ้าใครไม่ได้มีโอกาสได้ใช้ KKT-Conditions ก็ถือว่าเป็นการฝึกสมอง ให้มีระบบการคิดที่เป็นลอจิกนะคะ และแน่นอนว่า ระบบการคิดแบบนี้ยิ่งชำนาญ ก็จะยิ่งเข้าใจในกลไกของโมเดลเอไอมากขึ้น และจะรู้ได้ว่า ไม่มีความมหัศจรรย์ใดๆทั้งนั้น ทุกอย่างเป็นเหตุเป็นผลกันหมด ไม่มีฟลุ๊ค ไม่มีกล่องดำที่ลึบลับ ที่อยู่ดีๆก็ฉลาดขึ้นมาได้ค่ะ
สำหรับตอนนี้ก็จบลงเพียงเท่านี้
ถ้ายังไม่เคลียร์ก็คอมเม้นถามกันเข้ามาได้ค่ะ
สามารถติดตามกันได้ที่
Facebook: AI แบบเคลียร์ ตีแผ่ทุกไอเดียเบื้องหลังสมการ
Tiktok: ai.beeying
Youtube: AI แบบเคลียร์ๆ
Reference
Convex Optimization, Stephen Boyd and Lieven Vandenberghe
