Minimum point ตอนที่ 4: Sequential model-based optimization (SMBO)

หนทางการหาจุดต่ำสุดก็เริ่มริบหรี่ลงทุกที ๆ เพราะว่าตอนนี้ไม่รู้ว่าฟังก์ชันจะหน้าตาแบบไหน แถมการคำนวณค่าในแต่ละจุดของฟังก์ชันก็ยังใช้เวลานานอีก จนในบางครั้งก็อาจจะท้อจนถอดใจ ไม่หาจุดต่ำสุดแล้ว เลิก!

แต่ถ้าใจเย็น ๆ แล้วลองดูเงื่อนไขต่าง ๆ อีกที จะพบว่าปัญหาหลักเลยก็คือตัวของฟังก์ชันที่จะใช้เวลานานไปไหนไม่รู้ในการคำนวณแต่ละจุด ซึ่งถ้าจะฝืนใช้เพื่อคำนวณค่าจากแต่ละ grid หรือจะสุ่มจุดมา กว่าจะได้ response surface ที่ครอบคลุมทั้งโดเมนก็คงนานเกินรอจนไม่แน่ใจว่าระหว่างจะได้เป็นประชาธิปไตยหรือพล็อต response surface เสร็จ อันไหนจะเกิดขึ้นก่อนกัน (อ๋อ response surface สิครับ)

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

ในเมื่อตัวฟังก์ชันที่จะหาจุดต่ำสุดมันมีปัญหามากนัก ก็ไม่ต้องใช้มันแล้วกัน! แต่ว่า..ถ้าเราจะหาฟังก์ชันเพื่อมาแทนฟังก์ชันเดิม แสดงว่าฟังก์ชันใหม่จะต้องมี response surface ที่คล้ายเดิมอยู่ด้วย และยังต้องเป็นฟังก์ชันง่าย ๆ ที่คำนวณเร็ว ๆ คำถามคือมันมีฟังก์ชันแบบนี้อยู่ด้วยหรอ เพราะดูดีจนเหลือเชื่อเลย และมากกว่านั้น ถ้ามีอยู่จริงแล้วเราจะหามันเจอได้ยังไง

เป็นไปไม่ได้นั่นแหล่ะที่เป็นไปไม่ได้

ด้วยไอเดียอันชาญฉลาดบวกกับความสามารถทางคณิตศาสตร์ก็ได้เปิดโอกาสให้กับอีกทางเลือกหนึ่งที่พอจะเอาชนะข้อจำกัดที่เข้าใกล้กับคำว่าเป็นไปไม่ได้แบบนี้ และมีวี่แววว่าเราจะยังคงสามารถหาจุดต่ำสุดได้อยู่ เพียงแต่จะมีลูกเล่นบางอย่างที่เพิ่มเข้ามา โดยวิธีที่จะพูดถึงมีชื่อเรียกว่า sequential model-based optimization (SMBO) ซึ่งเป็นวิธีที่ต่อยอดมาจากมาจาก Bayesian seach นั่นเอง

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

1. สุ่มค่าบางมาจุด และนำไปคำนวณในฟังก์ชันดั้งเดิม
2. สร้าง/อัปเดตฟังก์ชันใหม่ที่ตั้งใจว่าจะมาทดแทนฟังก์ชันเดิม
3. หาตำแหน่งของจุดที่มีแววว่าจะเป็นจุดต่ำสุด
4. นำค่าในตำแหน่งจากข้อ 3 ไปคำนวณในฟังก์ชันเดิม
5. ทำซ้ำข้อ 2–4 จนกว่าจะครบตามจำนวนรอบที่กำหนดไว้ในการคำนวณ

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

เพื่อให้เห็นภาพ ขอหยิบยกภาพจากบทความนี้ประกอบการอธิบาย SMBO แต่ในภาพนี้จะเป็นการหาจุดสูงสุดแทน โดยสมมติว่าฟังก์ชันดั้งเดิมจะเป็นเส้นประสีแดงในรูปที่ 1 ส่วนฟังก์ชันที่กำลังสร้างขึ้นมาใหม่ในขั้นตอนที่ 2 จะเป็นเส้นสีน้ำเงิน โดยเฉดสีน้ำเงินจาง ๆ จะแสดงถึงความไม่มั่นใจว่าตรงนั้นจะมีจุดต่ำสุดอยู่รึเปล่า นั่นหมายความว่ายิ่งเฉดกว้างมากแสดงว่าความเป็นไปได้ที่จุดต่ำสุดจะอยู่ตรงนั้นมีเยอะ

รูปที่ 1: ตัวอย่างขั้นตอนของ SMBO แต่ในภาพเป็นการหาจุดสูงสุดแทน (ที่มาภาพ: https://arxiv.org/pdf/1012.2599.pdf)

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

SMBO in the multiverse of madness

โดยขั้นตอนในขั้นที่ 2 และ ขั้นที่ 3 ของ SMBO จะมีความหลากหลายมาก ๆ เนื่องจากในปัจจุบันก็มีหลายวิธีที่ถูกเสนอมาเป็นทางเลือกใหม่ ๆ ให้ไม่ต้องจำเจ ยกตัวอย่างเช่น ในขั้นตอนที่ 2 ก็มีสมมติให้ตัวฟังก์ชันใหม่ที่สร้างมาต้องอยู่ในรูปของ Gaussian process หรือไม่ก็ Parzen window แล้วแต่ละรอบก็ค่อย ๆ อัปเดตฟังก์ชันตัวนี้ให้มีหน้าตาใกล้เคียงกับฟังก์ชันเดิมให้ได้มากเท่าที่จะเป็นไปได้

ในวงการ ตัวฟังก์ชันใหม่นี้ — ฟังก์ชันที่เรากำลังสร้างใหม่ที่สามารถเลียนแบบฟังก์ชันเดิมได้แต่คำนวณเร็วกว่า — จะถูกเรียกว่า surrogate function

รูปที่ 2: ตัวอย่างของ Gaussian process (ที่มาภาพ: https://distill.pub/2019/visual-exploration-gaussian-processes/)

รูปที่ 3: ตัวอย่างของ Parzen window (ที่มาภาพ: https://en.wikipedia.org/wiki/Kernel_density_estimation)

หรืออย่างในขั้นตอนที่ 3 ที่เป็นการหาตำแหน่งที่มีแววว่าจะเป็นจุดต่ำสุด ก็มีหลายวิธีที่ต่างเคลมกันว่าเป็นวิธีที่ดีและมีประสิทธิภาพมากที่สุดในการหาตำแหน่งจุดต่ำสุด ไม่ว่าจะเป็น Probability of improvement, Expected improvement, หรือ Upper confidence bound (สำหรับจุดต่ำสุด อาจเรียกว่า Lower confidence bound แทน) โดยเราจะเรียกรูปแบบต่าง ๆ ในขั้นตอนนี้ว่า acquisition function

รูปที่ 4: ตัวอย่างวิธีการหาตำแหน่งที่มีทีท่าว่าจะเป็นจุดสูงสุด (ที่มาภาพ: https://en.wikipedia.org/wiki/Bayesian_optimization#/media/File:GpParBayesAnimationSmall.gif)

ปาฏิหาริย์มีจริง

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