การสร้าง robustness certificate

หลังจากที่เราได้รู้จักการสร้าง adversarial example เพื่อใช้ในการโจมตีแบบจำลองทาง machine learning และการทำ adversarial training เพื่อเพิ่มความทนทานให้แก่แบบจำลองแล้ว ในหัวข้อนี้เราจะมาสนใจเกี่ยวกับการทดสอบความทนทานของแบบจำลองเมื่อเราพิจารณาที่จุด sample $x$ ใด ๆ กล่าวคือ เราอยากทราบว่าหาก sample $x$ ของเราถูกก่อกวนด้วยการก่อกวน $\delta$ ใด ๆ ในขอบเขต $\|\delta\|_\infty\leq\epsilon$ จะมีโอกาสที่แบบจำลองของเราเปลี่ยนผลการทำนายไปจากเดิมหรือไม่ หากเราสามารถรับประกันได้ว่าภายในขอบเขตการก่อกวนดังกล่าว ไม่มีการก่อกวนใด ๆ สามารถทำให้แบบจำลองของเราทำนายผิดไปจากเดิมได้เลย แสดงว่าแบบจำลองของเราได้รับการยืนยันแล้วว่ามีความทนทานต่อการก่อกวนภายในระยะห่าง $\epsilon$ ที่จุด $x$ แน่นอน เราอาจเรียกการยืนยันดังกล่าวว่าเป็น robustness certificate

constrained formulation ของการโจมตีแบบกำหนดเป้าหมาย

เพื่อสร้าง robustness certificate เราจะเริ่มจากการกลับมามองปัญหา maximization สำหรับการสร้าง adversarial example ใหม่ พิจารณาการคำนวณของแบบจำลอง deep ReLU network $d$ layer ของเราบน sample $x$ ดังนี้

โดย $f_i(z)=\text{ReLU}(z)=\max(0, z)$ สำหรับ $i=1,\dots,d-1$ และ $f_d(z)=z$

เมื่อเราได้ $h_\theta(x)$ มาเป็นเวกเตอร์ที่มีมิติเท่ากับจำนวนคลาสผลลัพธ์ แบบจำลองของเราก็จะเลือกตอบคลาส $y$ ที่มีค่า $h_\theta(x)_y$ มากที่สุด

จากตรงนี้จะเห็นว่า เราสามารถมองปัญหาการโจมตีแบบกำหนดเป้าหมายที่ sample $(x, y)$ เป็นการพยายามหา sample $x^{adv}$ ที่มีระยะห่างจาก $x$ ไม่เกิน $\epsilon$ ที่เวกเตอร์ $h_\theta(x^{adv})$ มีค่าในมิติของคลาสเป้าหมาย $y'$ เอาชนะมิติของคลาส $y$ ให้ได้สูงที่สุด นั่นคือ เราต้องการ maximize $(h_\theta(x^{adv})_{y'} - h_\theta(x^{adv})_y)$ นั่นเอง

ดังนั้น ถ้าเรากำหนดให้ $e_i$ เป็นเวกเตอร์ความยาวเท่ากับจำนวนคลาสผลลัพธ์ ที่มีค่าเป็น 1 ในมิติที่ $i$ และมิติที่เหลือมีค่าเป็น 0 ทั้งหมด เราจะสามารถเขียนปัญหาการโจมตีแบบกำหนดเป้าหมายในลักษณะของ constrained formulation ได้ดังนี้

การตรวจสอบความทนทาน

จากปัญหาการโจมตีแบบกำหนดเป้าหมายที่เขียนในรูป constrained formulation นี้ สังเกตว่าถ้าหากมีคลาส $y'$ คลาสหนึ่งที่ผลของ $\max (e_{y'}-e_y)^Tz_{d+1}$ นี้มีค่ามากกว่าหรือเท่ากับ 0 แสดงว่าเรามี adversarial example $x^{adv}$ ที่ในเวกเตอร์ $h_\theta(x^{adv})$ ค่าในมิติของคลาส $y'$ มีค่าไม่น้อยกว่ามิติของคลาส $y$ ซึ่งจะทำให้แบบจำลองของเราไม่เลือกทำนายคลาส $y$ เป็นผลลัพธ์ แสดงว่าแบบจำลองของเราถูกโจมตีได้ที่จุด $x$

ในทางกลับกัน หากเราพบว่าสำหรับคลาส $y'$ ใด ๆ ที่ไม่ใช่ $y$ ค่าของ $\max (e_{y'}-e_y)^Tz_{d+1}$ น้อยกว่า 0 ทั้งหมด นั่นหมายความว่าไม่ว่าเราจะพิจารณา sample $x'$ ใด ๆ ในบริเวณที่กำหนด เวกเตอร์ $h_\theta(x')$ ของเราจะมีค่าในมิติที่ $y$ มากที่สุดเสมอ ซึ่งจะทำให้แบบจำลองของเราตอบคลาส $y$ เสมอ นั่นคือเราสามารถรับประกันได้ว่า ที่จุด $x$ นี้ การโจมตีใด ๆ ภายในระยะห่าง $\epsilon$ ไม่สามารถทำให้แบบจำลองของเราทำนายผลเปลี่ยนไปจากเดิมได้เลย ดังนั้นเราจึงสรุปได้ว่าแบบจำลองของเรามีความทนทานต่อการโจมตีด้วยระยะ $\epsilon$ ที่จุด $x$ แน่นอน

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

สังเกตว่าหากเราทำการ relax ปัญหาโดยให้ขอบเขตของตัวแปรต่าง ๆ ที่เป็นไปได้ในปัญหาใหม่นั้นครอบคลุมขอบเขตของปัญหาตั้งต้นทั้งหมด แสดงว่าคำตอบที่ดีที่สุดของปัญหาตั้งต้นก็ต้องเป็น คำตอบที่เป็นไปได้ (feasible solution) ของปัญหาใหม่ด้วยเช่นกัน จากตรงนี้ เราจะรับประกันได้ว่า คำตอบที่ดีที่สุดของปัญหาใหม่นั้นจะต้องมีค่าไม่น้อยไปกว่าคำตอบที่ดีที่สุดของปัญหาตั้งต้น ซึ่งถ้าหากเราพิจารณาปัญหาใหม่แล้วพบว่าค่าของ $\max (e_{y'}-e_y)^Tz_{d+1}$ ในปัญหาใหม่นี้น้อยกว่า 0 ทั้งหมด แสดงว่าค่า $\max (e_{y'}-e_y)^Tz_{d+1}$ ของปัญหาเดิมนั้นก็ต้องน้อยว่า 0 ทั้งหมดด้วย ซึ่งก็ใช้รับประกันความทนทานได้่เช่นกัน

อย่างไรก็ดี ในกรณีที่เรา relax ปัญหาให้มีขอบเขตของตัวแปรต่าง ๆ กว้างขึ้นนั้น หากเราพบว่ามีคลาส $y'$ ที่ค่าของ $\max (e_{y'}-e_y)^Tz_{d+1}$ มากกว่าหรือเท่ากับ 0 ก็ไม่ได้แสดงว่าเราจะสามารถทำการก่อกวนให้แบบจำลองตอบคลาส $y'$ ได้สำเร็จเสมอไป เนื่องจากค่าที่ดีที่สุดนี้อาจเกิดจากการกำหนดค่าให้ตัวแปรต่าง ๆ ที่อยู่นอกขอบเขตของปัญหาเดิม นั่นคือ ในปัญหาตั้งต้นจริง ๆ แล้วอาจไม่สามารถโจมตีได้ก็ได้ เช่นจากภาพด้านล่างนี้ บริเวณที่แรเงาคือพื้นที่ที่สามารถทำการก่อกวนได้จริง และเส้นกรอบด้านนอกแสดงขอบเขตพื้นที่ที่สนใจเมื่อเรา relax เงื่อนไข หากเราพบว่าค่า $\max (e_{y'}-e_y)^Tz_{d+1}$ มากกว่าหรือเท่ากับ 0 เราบอกได้เพียงว่าภายในกรอบนอกจะต้องมีการก่อกวนที่ทำให้แบบจำลองตอบผิดได้ แต่เราไม่สามารถบอกได้ว่าสามารถทำได้ภายในบริเวณที่ก่อกวนได้จริงหรือไม่

จากตรงนี้จะเห็นว่า หากเรามีเทคนิคในการทำ relaxation สองแบบ โดยที่แบบแรกมีขอบเขตของตัวแปรต่าง ๆ เพิ่มขึ้นจากเดิมน้อยกว่าแบบหลัง ค่า $\max (e_{y'}-e_y)^Tz_{d+1}$ ที่ได้จากการ relax แบบแรกก็น่าจะใกล้เคียงคำตอบของปัญหาตั้งต้นที่เราต้องการมากกว่าค่าที่ได้จากแบบหลัง อย่างไรก็ดี การ relax แบบแรกอาจต้องใช้เวลาในการคำนวณผลลัพธ์มากกว่าแบบหลัง ดังนั้นในการเลือกใช้เราต้องคำนึงถึงสมดุลระหว่างผลลัพธ์ที่ได้กับเวลาที่ใช้ด้วย ในหัวข้อถัดไปเราจะมาดูตัวอย่างการทำ relaxation สองแบบได้แก่การ relax ปัญหาให้เป็น linear program และ semidefinite program

References

1. E. Wong, J.Z. Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope, In Proceedings of the International Conference on Machine Learning (ICML), 2018

Prev: Adversarial training

Next: Linear programming relaxation