กลยุทธ์เชิงวิวัฒนาการ (CMA-ES) — การปรับเมทริกซ์ความแปรปรวนร่วม (Evolutionary Strategy: Covariance Matrix Adaptation)
- ผู้เสนอ
- Nikolaus Hansen & Andreas Ostermeier
- ปี
- 2001
- ประเภท
- Derivative-free continuous black-box optimizer
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
CMA-ES ซึ่งย่อมาจาก Covariance Matrix Adaptation Evolution Strategy เป็นตัวหาค่าเหมาะที่สุดแบบไม่ใช้อนุพันธ์ (derivative-free optimizer) สำหรับฟังก์ชันกล่องดำแบบต่อเนื่อง (continuous black-box functions) ที่พัฒนาขึ้นโดย Hansen และ Ostermeier ในปี 2001 โดยจะรักษาประชากรของคำตอบที่เป็นไปได้ซึ่งสุ่มมาจาก การแจกแจงแบบปกติหลายตัวแปร (multivariate normal distribution) และปรับปรุงค่าเฉลี่ย ขนาดก้าว (step size) และเมทริกซ์ความแปรปรวนร่วม (covariance matrix) ทั้งหมดอย่างต่อเนื่อง เพื่อนำทางการค้นหาไปยังบริเวณที่ดีขึ้นของปริภูมิพารามิเตอร์ (parameter space) ปัจจุบัน CMA-ES ได้กลายเป็นมาตรฐานโดยพฤตินัย (de-facto standard) สำหรับการหาค่าเหมาะที่สุดของฟังก์ชันกล่องดำแบบต่อเนื่อง และถูกนำไปใช้อย่างแพร่หลายในการค้นหาโครงสร้างสถาปัตยกรรมประสาท (neural architecture search) และการหาค่าเหมาะที่สุดของนโยบายในการเรียนรู้แบบเสริมกำลัง (reinforcement-learning policy optimization)
แนวคิดเบื้องหลังวิธีการ
ลองจินตนาการว่าคุณกำลังค้นหาจุดที่ต่ำที่สุดในภูมิประเทศที่เป็นภูเขา แต่คุณไม่สามารถมองเห็นภูมิประเทศได้ คุณทำได้เพียงสำรวจตำแหน่งต่างๆ และทราบระดับความสูงของแต่ละตำแหน่ง CMA-ES ทำงานเหมือนฝูงที่ถูกนำทาง: มันจะปล่อยกลุ่มของจุดสำรวจรอบๆ การประมาณค่าที่ดีที่สุดในปัจจุบัน วัดว่าแต่ละจุดสำรวจดีเพียงใด จากนั้นจึงปรับรูปร่างของกลุ่มสำหรับการดำเนินการรอบถัดไป กลุ่มนี้ไม่ใช่ทรงกลมธรรมดา แต่จะเรียนรู้รูปร่างที่ยาวและเอียงของหุบเขาที่กำลังลงไป โดยจดจำทิศทางที่นำไปสู่การปรับปรุง เมื่อเวลาผ่านไปหลายรุ่น กลุ่มจะแคบลงและเอียงเพื่อจัดแนวกับความโค้งของพื้นผิวฟังก์ชันสูญเสีย (loss surface) ทำให้ขั้นตอนวิธีสามารถนำทางในหุบเขาที่ยาวและแคบซึ่งจะทำให้วิธีการที่ง่ายกว่าติดขัดได้
ประวัติศาสตร์
กลยุทธ์วิวัฒนาการ (Evolution strategies) ถูกนำเสนอในช่วงทศวรรษ 1960 และ 1970 ในฐานะกลุ่มของตัวหาค่าเหมาะที่สุดแบบอิงประชากรที่ได้รับแรงบันดาลใจจากวิวัฒนาการทางชีววิทยา กลไกการปรับเมทริกซ์ความแปรปรวนร่วมได้รับการพัฒนาโดย Hansen และ Ostermeier และอธิบายไว้อย่างสมบูรณ์ในบทความ Evolutionary Computation ปี 2001 ซึ่งแสดงให้เห็นว่าการปรับตัวเองแบบสมบูรณ์โดยไม่มีการสุ่ม (completely derandomized self-adaptation) — การเรียนรู้เรขาคณิตอันดับสองเต็มรูปแบบของภูมิประเทศการค้นหาจากประวัติของขั้นตอนที่ประสบความสำเร็จ — มีประสิทธิภาพเหนือกว่ากลยุทธ์วิวัฒนาการก่อนหน้านี้อย่างมากในปัญหาที่มีเงื่อนไขไม่ดีและไม่สามารถแยกได้ (non-separable problems) บทแนะนำในปี 2016 ของ Hansen ได้รวบรวมขั้นตอนวิธีและคุณสมบัติทางทฤษฎี ทำให้ CMA-ES เป็นวิธีการอ้างอิงมาตรฐานสำหรับการวัดประสิทธิภาพการหาค่าเหมาะที่สุดของฟังก์ชันกล่องดำแบบต่อเนื่อง
ควรใช้เมื่อใด
CMA-ES เหมาะสมเมื่อฟังก์ชันวัตถุประสงค์เป็นแบบต่อเนื่อง (continuous) อาจไม่เป็นนูน (non-convex) มีหลายค่าเหมาะสม (multimodal) หรือมีสัญญาณรบกวน (noisy) และเมื่อข้อมูลอนุพันธ์ไม่พร้อมใช้งานหรือมีค่าใช้จ่ายสูงเกินไปในการคำนวณ ช่วงมิติที่เหมาะสมคือประมาณ 10 ถึง 1000 พารามิเตอร์ ต่ำกว่า 10 มิติ วิธีการที่ง่ายกว่ามักจะเพียงพอ และสูงกว่า 1000 มิติ ค่าใช้จ่ายหน่วยความจำแบบกำลังสองของเมทริกซ์ความแปรปรวนร่วมอาจกลายเป็นข้อจำกัด ไม่มีความต้องการขนาดตัวอย่างขั้นต่ำในเชิงสถิติ ขั้นตอนวิธีจะสร้างจุดประเมินของตนเอง CMA-ES เหมาะสมโดยธรรมชาติสำหรับการปรับแต่งไฮเปอร์พารามิเตอร์ (hyperparameter tuning) การค้นหาโครงสร้างสถาปัตยกรรมประสาท การหาค่าเหมาะที่สุดของนโยบายในการเรียนรู้แบบเสริมกำลัง และปัญหาการออกแบบทางวิศวกรรมที่ตัวจำลองให้ผลลัพธ์แบบกล่องดำเท่านั้น
ข้อจำกัดและข้อควรพิจารณา
- ต้นทุนหน่วยความจำแบบกำลังสองและต้นทุนการคำนวณต่อรุ่นตามจำนวนมิติ จำกัดการใช้งานเกินกว่าประมาณ 1000 พารามิเตอร์โดยไม่มีรูปแบบการลดมิติ (dimensionality-reduction variants)
- ลู่เข้าสู่ค่าเหมาะสมเฉพาะที่ (local optimum) หากไม่มีการเริ่มต้นใหม่ สำหรับภูมิประเทศที่มีหลายค่าเหมาะสม (highly multimodal landscapes) จำเป็นต้องมีการเริ่มต้นใหม่หลายครั้ง (IPOP-CMA-ES หรือ BIPOP-CMA-ES)
- ไม่เหมาะสำหรับปริภูมิการค้นหาแบบไม่ต่อเนื่อง (discrete) หรือแบบผสม (combinatorial) — วิธีการนี้ถูกกำหนดโดยธรรมชาติบนเวกเตอร์ค่าจริงแบบต่อเนื่อง
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ไม่ต้องการข้อมูลอนุพันธ์ — ทำงานได้กับฟังก์ชันวัตถุประสงค์ที่เรียกใช้ได้ทุกประเภท รวมถึงฟังก์ชันที่มีสัญญาณรบกวนหรืออิงจากการจำลอง
- เรียนรู้ความโค้งเฉพาะที่ของภูมิประเทศการค้นหาผ่านการปรับเมทริกซ์ความแปรปรวนร่วม ทำให้สามารถนำทางในปริภูมิการค้นหาที่ยาวและมีเงื่อนไขไม่ดี (ill-conditioned) ซึ่งวิธีการแบบไม่มีอนุพันธ์ที่มีการแจกแจงการค้นหาคงที่ (fixed search distributions) ไม่สามารถทำได้
- ไม่เปลี่ยนแปลงตามการแปลงฟังก์ชันวัตถุประสงค์ที่รักษาลำดับ (order-preserving transformations) และการหมุนของปริภูมิการค้นหา ทำให้มีความทนทานต่อรูปทรงปัญหาที่หลากหลาย
- เหมาะสมสำหรับปัญหาแบบต่อเนื่องที่มีมิติปานกลางถึงสูง (10–1000 พารามิเตอร์) โดยมีไฮเปอร์พารามิเตอร์ที่ปรับได้เพียงตัวเดียว คือ ขนาดก้าวเริ่มต้น
การประยุกต์ใช้
- การปรับแต่งไฮเปอร์พารามิเตอร์สำหรับแบบจำลองการเรียนรู้ของเครื่อง (machine-learning models) รวมถึงสถาปัตยกรรมโครงข่ายประสาทเทียม (neural network architectures) และตัวแทนการเรียนรู้แบบเสริมกำลัง (reinforcement-learning agents)
- การค้นหาโครงสร้างสถาปัตยกรรมประสาท — การหาค่าเหมาะที่สุดของพารามิเตอร์สถาปัตยกรรมที่เข้ารหัสแบบไม่ต่อเนื่อง (discrete-encoded architecture parameters) ผ่านการคลายเงื่อนไขให้เป็นแบบต่อเนื่อง (continuous relaxation)
- การหาค่าเหมาะที่สุดของนโยบายในการเรียนรู้แบบเสริมกำลัง เมื่อนโยบายถูกกำหนดโดยเวกเตอร์แบบต่อเนื่อง
- การหาค่าเหมาะที่สุดในการออกแบบทางวิศวกรรม เช่น การหาค่าเหมาะที่สุดของรูปทรงอากาศพลศาสตร์ (aerodynamic shape optimization) และการปรับพารามิเตอร์โครงสร้าง (structural parameter fitting) ซึ่งมีเพียงผลลัพธ์จากตัวจำลองเท่านั้นที่พร้อมใช้งาน
- การปรับเทียบแบบจำลองทางวิทยาศาสตร์ — การปรับแบบจำลองการจำลองให้เข้ากับข้อมูลจากการทดลอง เมื่อฟังก์ชันความควรจะเป็น (likelihood) ไม่สามารถหาอนุพันธ์ได้ หรือมีค่าใช้จ่ายในการคำนวณสูง
วิธีการทำงาน
วิธีการทำงาน
ขั้นตอนวิธีเริ่มต้นด้วยเวกเตอร์คำตอบเริ่มต้น (initial solution vector) และขนาดก้าวเริ่มต้น (initial step size) (sigma) เมทริกซ์ความแปรปรวนร่วมเริ่มต้นด้วยเมทริกซ์เอกลักษณ์ (identity matrix) ซึ่งเปรียบเสมือนกลุ่มการค้นหาที่เป็นทรงกลมสมบูรณ์ ขนาดประชากร (population size) ถูกกำหนด โดยทั่วไปจะอยู่ที่ประมาณ 4 + floor(3 * ln(dimension))
ในแต่ละรุ่น จะมีการสุ่มตัวอย่างประชากรของคำตอบที่เป็นไปได้จากการแจกแจงแบบปกติหลายตัวแปรในปัจจุบัน ซึ่งกำหนดโดยเวกเตอร์ค่าเฉลี่ย ขนาดก้าว และเมทริกซ์ความแปรปรวนร่วม เนื่องจากเป็นการแจกแจงแบบปกติหลายตัวแปร ตัวอย่างที่สุ่มได้จะสะท้อนทั้งค่าประมาณที่ดีที่สุดในปัจจุบันและรูปร่างที่เรียนรู้ของปริภูมิการค้นหา
คำตอบที่เป็นไปได้แต่ละรายการจะถูกส่งไปยังฟังก์ชันวัตถุประสงค์ (objective function) และได้รับคะแนนความเหมาะสม (fitness score) ไม่จำเป็นต้องใช้ข้อมูลอนุพันธ์ (gradient information) เพียงแค่ค่าของฟังก์ชันตามสเกล ณ จุดที่สุ่มแต่ละจุดเท่านั้น ทำให้ CMA-ES เหมาะสำหรับวัตถุประสงค์ที่มีสัญญาณรบกวน (noisy) ไม่สามารถหาอนุพันธ์ได้ (non-differentiable) และอิงจากการจำลอง (simulation-based)
ค่าเฉลี่ยจะถูกเลื่อนไปยังคำตอบที่มีอันดับดีกว่า เมทริกซ์ความแปรปรวนร่วมและขนาดก้าวจะถูกปรับปรุงโดยใช้สองเส้นทางการปรับปรุงที่เสริมกัน ได้แก่ การปรับปรุงแบบอันดับหนึ่ง (rank-one) และอันดับมิว (rank-mu) เพื่อให้ทิศทางที่ให้ผลลัพธ์ที่ดีมีแนวโน้มที่จะเกิดขึ้นมากขึ้นในรุ่นถัดไป นี่คือกลไกหลักที่ CMA-ES เรียนรู้เรขาคณิตเฉพาะที่ของภูมิประเทศการค้นหา
ขั้นตอนวิธีจะทำซ้ำวงจรการสุ่ม-ประเมิน-ปรับปรุง จนกว่าจะถึงเกณฑ์การหยุด: จำนวนการประเมินฟังก์ชันสูงสุด (maximum number of function evaluations) ค่าความคลาดเคลื่อนของการเปลี่ยนแปลงค่าเฉลี่ยหรือขนาดก้าว หรือการตรวจพบการเสื่อมสภาพของเมทริกซ์ความแปรปรวนร่วม คำตอบที่ดีที่สุดที่พบตลอดทุกรุ่นจะถูกส่งคืน
ข้อผิดพลาดที่พบบ่อย
- การตั้งค่าขนาดก้าวเริ่มต้น (sigma) ให้เล็กเกินไปจะทำให้การค้นหาติดอยู่ในบริเวณใกล้เคียงที่แคบและขัดขวางการสำรวจ หากใหญ่เกินไป รุ่นแรกๆ จะสิ้นเปลืองการประเมินผลที่ห่างไกลจากค่าที่เหมาะสม กฎทั่วไปที่ใช้กันคือการตั้งค่า sigma เพื่อให้ค่าที่เหมาะสมที่คาดหวังอยู่ภายในระยะประมาณสาม sigma ของจุดเริ่มต้น
- การใช้ CMA-ES กับปัญหาที่มีมิติต่ำมาก (น้อยกว่าห้าพารามิเตอร์) มักเป็นการสิ้นเปลือง — การค้นหาแบบตาราง (grid search) หรือ Nelder-Mead ที่ง่ายกว่าก็เพียงพอแล้ว และค่าใช้จ่ายในการจัดการประชากรของ CMA-ES ก็ไม่ก่อให้เกิดประโยชน์
- การรัน CMA-ES เพียงครั้งเดียวบนภูมิประเทศที่มีหลายค่าเหมาะสม มีความเสี่ยงที่จะพลาดค่าเหมาะสมที่สุดโดยรวม (global optimum) ควรใช้กลยุทธ์การเริ่มต้นใหม่หลายครั้ง (multi-start) หรือกลยุทธ์การเริ่มต้นใหม่แบบอิงประชากร (population-based restart strategies) (IPOP/BIPOP) เมื่อทราบว่าภูมิประเทศมีหลายค่าเหมาะสมสูง
- การถือว่าคำตอบที่ดีที่สุดที่ได้เป็นค่าเหมาะสมที่สุดโดยรวมที่แท้จริงโดยไม่มีการตรวจสอบการเริ่มต้นใหม่เป็นข้อผิดพลาดทั่วไป — ควรยืนยันเสมอด้วยการรันอิสระหลายครั้งเมื่อฟังก์ชันวัตถุประสงค์ไม่เป็นนูนสูง (highly non-convex)
คำถามที่พบบ่อย
CMA-ES แตกต่างจากอัลกอริทึมพันธุกรรม (genetic algorithm) แบบง่ายอย่างไร?
อัลกอริทึมพันธุกรรมแบบคลาสสิกจะรักษาประชากรและใช้การผสมข้าม (crossover) และการกลายพันธุ์ (mutation) ด้วยตัวดำเนินการคงที่ ในทางกลับกัน CMA-ES จะจำลองประชากรเป็นตัวอย่างจากการแจกแจงแบบปกติหลายตัวแปร และปรับการแจกแจงนั้นอย่างต่อเนื่อง — ค่าเฉลี่ย ขนาดก้าว และเมทริกซ์ความแปรปรวนร่วมทั้งหมด — โดยอิงตามคำตอบที่ประสบความสำเร็จ สิ่งนี้ช่วยให้ CMA-ES เรียนรู้รูปร่างของพื้นผิวฟังก์ชันวัตถุประสงค์ และนำทางในปริภูมิที่มีความสัมพันธ์กันและมีเงื่อนไขไม่ดีได้อย่างมีประสิทธิภาพมากกว่าอัลกอริทึมพันธุกรรมที่มีตัวดำเนินการคงที่
CMA-ES รับประกันว่าจะพบค่าเหมาะสมที่สุดโดยรวมหรือไม่?
ไม่ CMA-ES เป็นวิธีการค้นหาเฉพาะที่ (local search method) ในแง่ที่ว่าการรันเพียงครั้งเดียวสามารถลู่เข้าสู่ค่าเหมาะสมเฉพาะที่ได้ สำหรับภูมิประเทศที่มีหลายค่าเหมาะสม ขอแนะนำให้ทำการเริ่มต้นใหม่หลายครั้งอย่างอิสระ — อาจมีการเพิ่มขนาดประชากร (IPOP-CMA-ES) — เพื่อปรับปรุงการครอบคลุมปริภูมิการค้นหา
ไฮเปอร์พารามิเตอร์ใดที่สำคัญที่สุดในการตั้งค่า?
ขนาดก้าวเริ่มต้น sigma เป็นไฮเปอร์พารามิเตอร์ที่มีอิทธิพลมากที่สุดเพียงตัวเดียว หลักการทั่วไปที่ดีคือการตั้งค่า sigma เพื่อให้ค่าที่เหมาะสมที่คาดหวังอยู่ภายในระยะประมาณสาม sigma ของจุดเริ่มต้น ขนาดประชากรและจำนวนการประเมินสูงสุดเป็นการควบคุมรอง สูตรขนาดประชากรเริ่มต้น (4 + floor(3 * ln(dimension))) ทำงานได้ดีในทางปฏิบัติ
CMA-ES สามารถจัดการกับฟังก์ชันวัตถุประสงค์ที่มีสัญญาณรบกวนได้หรือไม่?
ได้ เนื่องจาก CMA-ES ใช้เฉพาะข้อมูลอันดับ (rank-order information) จากประชากร — ไม่ใช่ค่าฟังก์ชันสัมบูรณ์ — จึงมีความทนทานต่อสัญญาณรบกวนค่อนข้างดี สำหรับการประเมินที่มีสัญญาณรบกวนสูง การเพิ่มขนาดประชากรหรือการหาค่าเฉลี่ยของการประเมินหลายครั้งต่อคำตอบหนึ่งรายการสามารถเพิ่มความทนทานได้อีก
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Hansen, N. & Ostermeier, A. (2001). Completely Derandomized Self-Adaptation in Evolutionary Strategies. Evolutionary Computation, 9(2), 159-195.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วHansen, N. (2016). The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้ว