Global vs Local Optima

สวัสดีครับ

วันนี้นั่งคุยกับรุ่นพี่คนนึง เรื่องหางาน เพราะว่าพี่เขาเก่งมากแต่เนื่องจากมีครอบครัวแล้ว การหางานก็เลยทำให้มีข้อจำกัดบางอย่าง เพราะว่าพี่เขาอยากไปทำงานที่บริษัทเอ แต่เพราะครอบครัวก็เลยอาจจะต้องจำใจไปทำที่บริษัทบี แล้วทั้งผมและพี่เขาก็เลยพากันไปพูดถึงglobal กับ local optima กันไปซะงั้น

ถ้าคุณเคยเรียนแคลคูลัสกันมาแล้ว ก็คงจะรู้จักกับคำว่า optimal กันดีนะครับ เพราะมันคือจุดที่ diff แล้วเท่ากับ 0 ซึ่งเงื่อนไขนี้ถือเป็น necessary condition ครับ แต่ไม่ใช่ทุกจุดที่ diff แล้วเท่ากับ 0 จะเป็น global หรือ local optima นะครับ

เอาล่ะครับ แล้วอะไรคือ global หรือ local optima ก่อนจะพูดถึง optimal points มาพูดกันถึง search space กันก่อนครับ search space ก็คือ ค่าคำตอบที่เป็นไปได้ทั้งหมดครับ  

มองกันง่ายๆนะครับ ถ้าปัญหาของผมคือ ผมต้องการหายอดเขาที่สูงที่สุดในโลก search space ของผมก็คือ โลกใช่ไหมครับ แล้ว optimum ก็คือยอดเขาครับ

ยอดเขาทุกลูก คือ optimal solution แต่จะเป็นแบบไหน จะเป็นแบบ global หรือ local ถ้าเป็นแบบ global นั่นก็คือที่สุดของที่สุด ซึ่งก็ต้องเป็นยอดเขาเอเวอเรสครับ เพราะเอเวอเรส คือยอดเขาที่สูงที่สุดในโลก ถูกไหมครับ

ส่วนยอดเขาอย่างอินทนนท์นั้น ก็เป็นได้แค่ local optima เท่านั้นครับ เพราะมันไม่ใช่ยอดเขาที่สูงที่สุดในโลก แต่ก็เป็นยอดเขาอยู่ดี

ถ้าจะให้สรุปง่ายๆ global optima ก็คือ จุด (ยอดเขา) ที่ให้ ค่าที่ดีที่สุดของปัญหา (ความสูงจากระดับน้ำทะเล) ส่วน local optima นั้นก็แค่ยอดเขาเฉยๆครับ หรือก็คือจุดที่มันดีกว่าจุดอื่นๆในละแวกนั้นครับ

แล้วทำไม เราถึงต้องสนใจ global optima ที่เราสนใจ global optima ก็เพราะว่าเราต้องการเป็นเป็ปซี่ครับ เราต้องค่าที่ดีที่สุด ทำอะไรให้ดีที่สุด

แต่ปัญหาของ global optima ก็คือ สำหรับปัญหาคณิตศาสตร์บางปัญหา โดยเฉพาะที่เรียกกันว่า NP problem นั้นมันยากมากครับที่จะหา global optima ได้ บางปัญหานั้น กว่าจะหา global optima ได้ อาจจะต้องใช้เวลาเป็นปีแสงกันเลยทีเดียว เพราะว่า การที่เราจะรู้ว่า ค่าคำตอบที่เราหามาได้นั้นคือ global optima มันต้องประกอบด้วยสองส่วนครับ

ส่วนแรกก็คือการหา ถูกไหมครับ ส่วนที่สองก็คือการพิสูจน์ครับว่า มันเป็น global optima จริง ซึ่งการพิสูจน์นี่แหละครับ บางทีมันยาก ดังนั้น หลายครั้งในหลายๆปัญหาโดยเฉพาะพวกปัญหาที่ต้องการเวลาในการแก้เยอะๆ เราก็เลยอาจจะได้แค่คำว่า local optima เท่านั้น แต่ปัญหาของ local optima ก็คือแล้วเราจะรู้ได้ไงว่าดีหรือไม่ดี

อันนี้จะรู้ได้ก็ต้องเทียบกับขอบเขต หรือที่เรียกกันว่า bound ครับ bound หาได้ยังไง อันนี้ก็แล้วแต่ปัญหาครับ แต่ bound นั้น ส่วนมากก็จะหามาจากการแก้ปัญหาแบบง่าย ที่เราอาจจะไม่สนใจสมมติฐานบางประการครับ

จะว่าไปมันก็เหมือนชีวิตคนแหละครับ ไม่ว่าจะเป็นเรื่องการเลือกแฟน หรือเลือกงาน เรานั้นคาดหวังที่จะได้ global optima ทั้งนั้น แต่เนื่องจาก solution space (หรือก็คือคนทั้งโลก หรืองานทั้งหลาย) นั้นมันเยอะมากของมากของมากแล้วก็ของมาก แล้วเราจะรู้ได้ยังไงว่าเราเลือกได้ global optima จริง จะให้ลองเป็นแฟนกับผู้หญิงทั้งโลก หรือผู้ชายทุกคน หรือจะให้เปลี่ยนงานกันซะหมดเลยหรอ มันก็ยากใช่ไหมครับ ในเมื่อมันยาก เราก็เปลี่ยนจาก global optima มาเป็น local optima ที่อาจจะเรียกว่า ใกล้กับ global optima ซะหน่อย

ซึ่งนั่นหมายความว่าเรา limit search space ของเราครับ เช่น เป็นแฟนกับแค่คนไทยล่ะกัน หรือว่าหางานในสาขาที่เราเรียนจบมาล่ะกัน แต่ในเมื่อเราจำกัด search space ของเราเรียบร้อยแล้ว แต่ถ้ายังหายากอยู่ (อันนี้หมายถึงเวลาในการหานะครับ) เราก็อาจจะจำเป็นต้องจำกัด search space ของเราต่อไปครับ

แต่ทั้งนี้ทั้งนั้น ผมไม่ได้หมายความว่าเราจำกัด search space ไปเรื่อยๆแล้วจะไม่ได้คำตอบที่สุดที่สุดของที่สุดหรือ global optima นะครับ เราอาจจะได้ครับ เพียงแต่เราไม่สามารถพิสูจน์ได้ว่า มันใช่คำตอบที่ดีที่สุดของที่สุด เราก็เลยเรียกมันได้แค่ local optima เท่านั้นครับ

เห็นไหมครับ จริงๆแล้ว เลขนั้นมันสัมพันธ์กับชีวิตของเราจริงๆซะด้วย ใครจะสร้าง search algorithm หาแฟน ก็เชิญได้ตามสบายนะครับ สวัสดีครับ

 

 

[wwibul]

• น้องต้นเล่นจบปุบปับ น่าจะมีต่อซะหน่อย กำลังอ่านเพลินเชียว ว่าจะบอกอะไร (นอกเหนือจาก search space เรื่องหาคู่...)

 

[นิตา]

สวัสดีค่ะ ขอบคุณสำหรับข้อมูลที่ทำให้เห็นชัดเจนมากขึ้นค่ะ

จะขอรบกวนถามเรื่อง Subspace น่ะค่ะว่ามันคืออะไร

Subspace ของ local optima คืออะไรน่ะค่ะ

เพราะว่าอ่านเจอในตัว Memetic algorithms ว่า มันจะทำการ reduce ให้อยู่ใน subspace ของ local optima น่ะค่ะ

รบกวนช่วยตอบด้วยนะคะ

ขอบคุณมากๆค่ะ

[moobacon]

ขอบคุณนะคะ ช่วยได้มากเลยค่