Semidefinite programming relaxation
เมื่อเราเขียนปัญหาการโจมตีแบบกำหนดเป้าหมายให้อยู่ในรูปของ quadratic programming ได้แล้ว เราจะสามารถทำ relaxation ให้กลายเป็นปัญหาที่เรียกว่า semidefinite programming ซึ่งสามารถหาคำตอบได้ไม่ยาก อย่างไรก็ดีในปัญหา semidefinite programming นั้นเราจะมองตัวแปรที่ปรับค่าได้ในรูปของ matrix เราจึงควรจัดรูปปัญหาของเราให้เป็นปัญหาบน matrix ก่อน ซึ่งทำได้ง่ายเมื่อปัญหาที่เรามีอยู่ในรูป quadratic programming อยู่แล้ว
relaxation สำหรับแบบจำลอง deep learning ที่มี 1 hidden layer
เพื่อความง่ายเราจะเริ่มพิจารณากรณีที่แบบจำลองของเรามี hidden layer เพียง layer เดียวก่อน ซึ่งจะสามารถเขียนในรูปปัญหา quadratic programming ได้ดังนี้
ถ้าเรานิยามให้ และให้ เราจะใช้สัญลักษณ์ ในการระบุถึงสมาชิกของ ดังนี้
ถึงตรงนี้เราสามารถเขียนปัญหาของเราใหม่ในรูปของ ได้ดังนี้
เนื่องจากรูปแบบปัญหาล่าสุดนี้ยังคงเป็นปัญหาเดียวกับปัญหาตั้งต้นของเรา เราจึงยังไม่หวังว่าจะสามารถหาคำตอบได้อย่างมีประสิทธิภาพ อย่างไรก็ดี ปัญหาในรูปแบบล่าสุดนี้สามารถทำ relaxation ให้หาคำตอบได้ง่ายขึ้นโดยการเปลี่ยนเงื่อนไขที่กำหนดให้ สำหรับเวกเตอร์ บางตัว ให้กลายเป็น สามารถอยู่ในรูปของ เมื่อ เป็น matrix ที่มีจำนวน column เท่ากับจำนวนแถว เราเรียก symmetric matrix ที่มีคุณสมบัติดังกล่าวนี้ว่าเป็น positive semidefinite matrix ถ้า เป็น positive semidefinite เราจะเขียนแทนว่า ดังนั้นเมื่อเรา relax เงื่อนไขนี้ เราก็จะได้ปัญหาที่เป็น semidefinite programming ดังนี้
ซึ่งจะเห็นว่า กรณีที่มีเวกเตอร์ ที่ นั้นก็เป็นหนึ่งในคำตอบที่เป็นไปได้ในปัญหาใหม่นี่เช่นกัน ดังนั้นปัญหาใหม่ของเราจึงครอบคลุมทุกความเป็นไปได้ของปั ญหาตั้งต้น นั่นแสดงว่าค่า objective function ของปัญหาใหม่นี้ไม่มีทางน้อยกว่าค่า objective function ของปัญหาตั้งต้น แต่ปัญหา semidefinite programming นี้สามารถหาคำตอบที่ดีที่สุดได้ง่ายกว่ามาก การ relax เป็น semidefinite programming นี้จึงเป็นอีกเทคนิคที่น่าสนใจ
relaxation สำหรับกรณีทั่วไป
คราวนี้เรามาพิจารณาเมื่อแบบจำลอง deep learning ของเรามีจำนวน layer เท่ากับ ซึ่งสามารถเขียนเงื่อนไขความสัมพันธ์ระหว่าง กับ ใด ๆ ได้เช่นเดียวกับความสัมพันธ์ระหว่าง กับ ในตัวอย่างที่ผ่านมา สมมติให้ทราบทราบขอบเขตของ ใด ๆ ว่า เราก็จะได้ปัญหา semidefinite programming ดังนี้
โดยที่ขอบเขต และ ก็สามารถใช้วิธีเดียวกับตอนทำ linear programming relaxation ในการหาได้
References
Prev: Quadratic programming