Minimum point ตอนที่ 3: Search and research
มันจะมีบางเหตุการณ์ที่เราไม่สามารถรับรู้ได้ว่าฟังก์ชันที่กำลังหาจุดต่ำสุดนั้นมีหน้าตาเป็นอย่างไร แต่เราจำเป็นและต้องการหาจุดต่ำสุดอยู่ดี ยกตัวอย่างเช่น กำลังสร้างโมเดลแล้วต้องการหาค่า hyperparameters ที่เหมาะสมที่สุดสำหรับชุดข้อมูลนั้น ๆ แต่ในขณะนั้นเองก็ไม่รู้ว่าหน้าตาของ loss function เป็นยังไง รู้แต่เพียงว่าขอตัวที่ให้ loss มีค่าต่ำสุดเท่านั้น ซึ่งการที่ไม่รู้ว่าฟังก์ชันมีหน้าตายังไงนั่นหมายความว่าในเคสนี้เราไม่สามารถใช้วิธีตามที่ได้อธิบายในบทความนี้ ได้อีกต่อไปแล้ว
ทุกปัญหาแก้ได้ด้วยเงิน
ก็มีหลายความพยายามในการหาจุดต่ำสุดให้ได้ แต่จะอยู่ภายใต้เงื่อนไขที่ว่าเรายังคงสามารถหาค่าของฟังก์ชัน (evaluate) ที่ต้องการหาจุดต่ำสุดได้อยู่ถึงแม้ว่าจะไม่รู้หน้าตาจริง ๆ (explicit form) ของฟังก์ชันนั้นก็ตาม ซึ่งหมายความว่า เราใส่ input, x ไปในฟังก์ชันตัวนี้จะยังคงได้ output, y ออกมาได้เสมอ
ซึ่งการสมมติแบบนี้นำมาซึ่งวิธีการที่เป็นขวัญใจสายเปย์ที่เรียกว่า grid search โดยการแทนทุกค่าที่เป็นไปได้ของ x แล้วคำนวณค่าของฟังก์ชันที่สอดคล้องกับแต่ละค่า x ที่ใส่เข้าไป วิธีการนี้จะช่วยให้เราเห็นกราฟของฟังก์ชันว่ามีหน้าตาเป็นอย่างไร และจะได้ตำแหน่งของจุดต่ำสุดของฟังก์ชันออกมาได้ทันที
ในกรณีที่ input มีหลาย dimension กราฟของฟังก์ชันที่ออกมานี้จะไม่ใช่กราฟเส้น ๆ อีกต่อไปแล้ว แต่จะออกมาเป็น surface แทน อาการคล้าย ๆ กับเป็นภูเขา ๆ ในรูปที่ 1 ซึ่งเราสามารถเรียกสิ่งที่ได้จากการแทนแต่ละค่าของ x เข้าไปในฟังก์ชันว่า response surface
แต่แทบทุกครั้งที่ใช้วิธีนี้ ก็ไม่ได้คำนวณทุกค่าที่เป็นไปได้ของ x จริง ๆ แต่มีการตัดเป็นช่วง ๆ อย่างเช่น ค่า x ที่สนใจอยู่ในช่วง -10 ถึง 10 ก็อาจจะเลือกมาเฉพาะ x ที่เป็นจำนวนคู่มาคำนวณ (-10, -8, -6, -4, -2, 0, 2, 4, 6, 8, 10) ให้อารมณ์ประมาณว่าแบ่งทั้ง space ออกมาเป็น grid แล้วก็ใช้ค่าที่แต่ละ grid ซึ่งก็จะลดจำนวนครั้งที่ต้องคำนวณค่าของฟังก์ชันได้ไปพอสมควร
อย่างไรก็ตามการลดจำนวนครั้งที่ต้องคำนวณ หรือว่าการที่แต่ละ grid ห่างกันมากขึ้น ทำให้ข้อมูลที่เราได้จาก response surface ก็จะหยาบมากยิ่งขึ้น และถ้าหากโชคร้าย จุดต่ำสุดจริง ๆ อาจเกิดขึ้นบริเวณที่ค่าที่เราไม่ได้คำนวณก็เป็นได้ ซึ่งตรงนี้ก็เป็นสิ่งที่ต้องแลกกันระหว่างความไวในการคำนวณและความละเอียดของผลลัพธ์ที่ได้
ความยากลำบากของวิธีการนี้มีเพียงว่าต้องการใช้ทรัพยากรในการคำนวณที่สูงมาก เนื่องจากการคำนวณค่าฟังก์ชันในแต่ละจุดที่ใส่เข้าไปนั้นใช้เวลานาน จนบางครั้งนานเป็นวันก็ยังไม่เสร็จ จึงเป็นวิธีของสายเปย์เนื่องจากปัญหาเหล่านี้จะหมดไปหากมีทรัพยากรในการคำนวณที่พร้อมมาก เครื่องอย่างแรง ก็สามารถลุยด้วยวิธีนี้ได้ตามสไตล์ทุกปัญหาแก้ได้ด้วยเงิน
เงินซื้อทุกอย่างไม่ได้
วิธีของ grid search ว่าดีแล้ว แต่ในกรณีที่ตัว input มีหลายมิติมากขึ้น การหาความเป็นไปได้ทั้งหมดเพื่อคำนวณค่าฟังก์ชันแต่ละจุดอาจจะกลายเป็นหายนะได้ ยกตัวอย่างเช่น ในฟังก์ชันของความเจริญของประเทศ มีตัวแปร 2 ตัว คือ ระยะเวลาการดำรงตำแหน่งของนายก (เรียกสั้น ๆ ว่า t) และจำนวนประชากรของผู้คนที่ไม่ศรัทธาในประชาธิปไตย (เรียกสั้น ๆ ว่า n) การจะหาจุดต่ำสุดตามวิธีของ grid search จะต้องคัดเลือก t และ n มาจำนวนหนึ่งเพื่อใช้ในการคำนวณค่าของฟังก์ชัน สมมติว่าเลือกมาอย่างละ 10 จุด นั่นแปลว่าในการทำ grid search ครั้งนี้จะต้องใช้ถึง 10 x 10 = 100 ครั้งในการคำนวณ เพื่อรองรับความเป็นไปได้ทุกรูปแบบที่เกิดขึ้นของ input ทั่วทั้งขอบเขตที่สนใจ
ซึ่งถ้าหากจินตนาการในกรณีที่ input มีมากกว่านี้ สมมติว่ามี 5 ตัว และสมมติว่าเอาแต่ละตัวของ input มาแค่ 10 ค่าเท่านั้น ก็จะได้ว่าต้องมีถึง 10 ^ 5 = 100,000 ครั้งในการคำนวณเพื่อให้ครอบคลุมความเป็นไปได้ทั้งหมด ซึ่งปริมาณนี้สามารถเพิ่มขึ้นได้อีกตามจำนวนตัวแปร (จำนวน dimension) ของ input ที่เรามี ซึ่งมันจะเพิ่มหรือลดแบบเท่าตัว (exponentially) เลย
หายนะนี้ ในวงการจะเรียกว่า curse of dimensionality
ข้อกังวลในจุดนี้นี่เองจึงเป็นเหตุให้มีผู้คิดค้นทางเลือกอื่น ๆ ที่ไม่ต้องใช้ทรัพยากรมากและ/หรือไม่ต้องคำนวณมากถึงขนาดนี้ โดยวิธีหนึ่งที่สามารถป้องกันหายนะนี้ก็คือ random search
สุ่มกาลีกาลีสุ่ม
แทนที่จะต้องเลือกค่าตามแต่ละ grid เหมือนอย่างใน grid search สำหรับในมุมมองของ random search จะไม่สนใจว่าตรงนั้นมี grid หรือไม่มี จะสุ่มมาสักค่าในความเป็นไปได้ที่มากมายเหล่านั้น เพื่อมาคำนวณค่าของฟังก์ชันที่สอดคล้องกับจุดที่ถูกสุ่มมา แล้วก็วนรอบการสุ่มเพื่อคำนวณไปเรื่อย ๆ จนกว่าเราจะพอใจ
อาจเกิดความสงสัยว่าแบบนี้มันต้องใช้แต้มบุญเท่าไหร่ถึงจะสุ่มโดนจุดต่ำสุดจริง ๆ เพราะในขอบเขตที่สนใจนั้นน่าจะมีจุดต่ำสุดอยู่ไม่กี่ที่ แล้วโอกาสที่ค่าที่สุ่มมานั้นจะเป็นจุดต่ำสุดจริง ๆ มันน่าจะแทบเป็นไปไม่ได้เลย
ซึ่งต้องยอมรับว่าวิธีการของ random search แบบต้นตำรับนี้ยังต้องอาศัยบุญและวาสนาพอสมควร แต่ข้อดีคือมันจะช่วยลดความเป็นไปได้ที่มากเกินความจำเป็นที่มาจาก curse of dimensionality ของ grid search ได้
อีกขั้นของ random search
ด้วยความสามารถในการรับมือกับ curse of dimensionality ที่ดีกว่า grid search จึงมีการศึกษาและพัฒนา random search มามากพอสมควร ซึ่งหนึ่งในนั้นคือการดูผลของค่าฟังก์ชันเมื่อลองเปลี่ยนค่าที่ dimension หนึ่งของ input โดยที่ dimension อื่นยังคงเป็นค่าเดิมอยู่ เพื่อดูว่าที่ dimension นั้นมันสร้างผลกระทบมากน้อยขนาดไหนต่อค่าของฟังก์ชัน เพราะว่าเกือบทุกครั้งจะมีอย่างน้อย 1 dimension ที่ถึงแม้ว่าจะเปลี่ยนค่าเป็นอะไรก็ตาม ค่าของฟังก์ชันก็แทบจะเป็นค่าเดียวกันหมดเลย ซึ่งลักษณะของ dimension แบบนี้จะถูกเรียกว่า low effective dimension (สามารถอ่านต่อในบทความนี้)
ลองจินตนาการว่าถ้าเราทำ grid search โดยที่มี dimension ตัวอ่อนที่ค่าที่เปลี่ยนไปไม่ได้ทำให้ค่าของฟังก์ชันเปลี่ยนไปด้วย (ค่าในแกนแนวตั้งสีเหลืองในรูปที่ 2) ทำให้การทำ grid search เหมือนจะไม่ค่อยเป็นประโยชน์สักเท่าไหร่นัก อย่างเช่นในรูปที่ 2 ด้านซ้าย การทำ grid search ที่ต้องคำนวณ 9 รอบนี้จะให้ผลลัพธ์ไม่ต่างจากการคำนวณแค่ 3 รอบตามค่าสีเขียวที่แตกต่างกัน เนื่องจากค่าจาก dimension สีเหลืองไม่ได้ทำให้ค่าฟังก์ชันเปลี่ยนแปลงไปมากนัก
ในทางกลับกัน เมื่อเราทำ random search แทนจะพบว่าโอกาสที่จะทดสอบความเป็นไปได้ของจุดต่ำสุดมีมากถึง 9 ครั้ง ตามจำนวนครั้งที่ได้ทำการคำนวณค่าของฟังก์ชัน หรือก็คือทุกครั้งที่ทำการคำนวณจะมีความหมายเสมอ ไม่ได้เสียเปล่าไปเหมือนกับ grid search
ลองวัดกันหน่อยมั้ย
ในบทความนี้ ได้มีการเปรียบเทียบประสิทธิภาพของการหาจุดต่ำสุดทั้งแบบ grid search และ random search ซึ่งพบว่า random search ใช้เวลาน้อยกว่า grid search ถึง 8 เท่าทั้งจำนวนครั้งและระยะเวลาที่คำนวณค่าฟังก์ชัน ในขณะที่ได้ผลลัพธ์ของจุดต่ำสุดที่ต่างกันเพียง 0.5% เท่านั้น จึงดูเหมือนว่า random search จะมีประสิทธิภาพกว่า grid search เพราะว่าสามารถค้นหาจุดต่ำสุดได้เร็วกว่าแถมใช้ทรัพยากรน้อยกว่า
แต่นั่นก็ไม่ได้หมายความว่า grid search จะอ่อนอยู่อย่างนี้และจะอ่อนตลอดไป จุดเด่นของ grid search จะเป็นการค้นหาที่ครบถ้วนและครอบคลุมทั่วทั้งขอบเขตที่สนใจ จึงเหมาะสำหรับฟังก์ชันที่ต้องการหาจุดต่ำสุดที่ input มี dimension น้อย ๆ
แต่ก็ต้องไม่ลืมว่าเงื่อนไขสำคัญของการที่จะนำ grid search หรือ random search ไปใช้ นั่นก็คือจะฟังก์ชันนั้นจะต้องสามารถหาค่าได้ที่จุดใด ๆ ที่ถูกเลือกขึ้นมาได้ ถึงแม้ว่าการคำนวณค่าของฟังก์ชันในแต่ละจุดจะต้องใช้ทรัพยากรมหาศาลแค่ไหนก็ตาม
ซึ่ง painpoint นี้เองได้กลายเป็นจุดสำคัญในการพัฒนาต่อยอดไปว่าในการค้นหาจุดต่ำสุดของฟังก์ชันที่เราไม่รู้ว่าหน้าตาของมันเป็นยังไง แถมการคำนวณค่าฟังก์ชันในแต่ละจุดก็ต้องใช้การคำนวณมหาศาลแถมใช้เวลานาน มันจะมีวิธีการแก้ไขข้อจำกัดนี้อย่างไร ติดตามต่อได้ในบทความนี้ครับ
