Skip to content

Machine Learning #9 | Gradient Descent

โพสต์ที่แล้ว เรารู้อัลกอริทึมของ Linear Regression ไปแล้วว่ามันทำงานยังไงแต่มีอีก task ที่เราต้องสนใจคือการ optimize ค่า Cost function (J) ให้น้อยที่สุดเพื่อให้ได้ model ที่ fit กับ training set ที่สุด

ตัวอย่างที่แล้วผมกำหนดให้ \theta_0 = 0 เราเลยได้กราฟความสัมพันธ์ระหว่าง J(\theta_1) กับ \theta_1 เป็นเส้นโค้งหงายขึ้นเป็นรูปถ้วย (blow shape) ใน 2 มิติ แต่ในความเป็นจริง \theta_0 อาจเป็นค่าใดๆ ก็ได้ฉะนั้นความสัมพันธ์ระหว่างค่า J กับ \theta จะไม่ใช่ 2 มิติแต่จะเป็น 3 มิติดังรูปข้างล่างนี้Selection_109

สู่จุดต่ำสุด Global minimum

เป้าหมายของเราคือการหา [\theta_0, \theta_1] ที่ทำให้ค่า J น้อยที่สุดซึ่งก็คือก้นแอ่งกระทะนี้ เราจะเรียกว่าจุดต่ำสุดนี้ว่า Global Minimum ซึ่งการจะไปให้ถึงจุดต่ำสุดเราสามารถใช้วิธี optimize ทางคณิตศาสตร์ ซึ่งก็มีหลายวิธีเลือกใช้ตามแต่สะดวก แต่ละวิธีก็มีข้อดีข้อเสียแตกต่างกันไป วิธีที่เราจะเรียนรู้วันนี้เรียกว่า Gradient Descent

Gradient Descent เป็นการหา Partial Derivative ของ cost function (diff cost function เทียบกับ \theta) ถ้านึกไม่ออกให้ลองนึกภาพว่าเรามีไม้บรรทัดตรงๆ รูดตั้งฉากกับผิวของกระทะด้านนอกไปเรื่อยๆ จนแตะก้นกระทะ (คิดถึงหน้าอาจารย์สอนแคลคูลัสขึ้นมาเลยแหละ) ซึ่งมาได้ยังไงคงไม่ได้อธิบายตรงนี้นะครับเดี๋ยวจะนอกเรื่องไปไกลเกิน … พูดหล่อๆ ไปงั้น ความจริงคือผมกากเองแหละ ฮา ถ้าอยาก prove ก็หาอ่านเพิ่มเติมเองแล้วกันครับ

Gradient Descent Algorithm

อัลกอริทึมของ gradient descent เป็น iterative algorithm สามารถเขียนได้เป็น

repeat until convergence {

\indent \theta_j := \theta_j - \alpha \frac{\partial J(\theta)}{\partial \theta} (j = 0 และ j = 1)

}

เมื่อเราแทนค่า J ที่เป็น cost function ของ linear regression จะได้

repeat until convergence {

\indent \theta_0 := \theta_0 - \alpha\frac{1}{m}\sum_{i=1}^{m}(h(x^i) - y^i)
\indent \theta_1 := \theta_1 - \alpha\frac{1}{m}\sum_{i=1}^{m}(h(x^i) - y^i) x^i

}

การอัปเดต \theta เป็นการอัปเดตแบบ Simultaneously หมายความว่าคำนวณพจน์ทางขวาของเครื่องหมาย := ก่อนค่อย assign กลับคืนให้ตัวแปรทางซ้ายมือ หรือถ้ามีการใช้ตัวแปรก่อนหน้าก็ให้เอาค่าก่อนอัปเดตมาคำนวณได้เลยไม่ได้อัปเดตเป็น chain ต่อกันแต่เป็นการอัปเดตพร้อมๆ กัน ซึ่งการอัปเดตพร้อมๆ กันนี้บางครั้งเราจะเรียกว่า Batch Gradient Descent

จากอัลกอริทึมข้างบนเราจะเห็นตัวแปรเพิ่มขึ้นมาคือ \alpha (alpha) ซึ่งเรียกว่า Learning rate ตัวแปรนี้เป็นค่าคงที่ค่าหนึ่งซึ่งเป็นตัวกำหนดว่าแต่ละรอบค่า gradient จะขยับทีะเท่าไหร่ ถ้า \alpha น้อยเกินไปการคำนวณ gradient ก็จะช้า แต่ถ้า  \alpha มากเกินไปก็จะเกิดปัญหาที่เรียกว่า Overshoot คือแทนที่แต่ละรอบ const function จะลดลงเรื่อยๆ ถ้าเพิ่มขึ้นเรื่อยๆ ควรลดค่า \alpha ลง

ปัญหาของการ optimize

ในบางปัญหา ความสัมพันธ์ระหว่าง cost function และ parameter ที่เราต้องการ optimize (ในที่นี้คือ \theta) ไม่ได้เป็น blow shape แต่มีลักษณะพื้นผิวเป็นหลุมหลายๆ หลุมดังรูปข้างล่าง

Selection_110

บางครั้งเราไม่สามารถไปถึงจุดที่ต่ำที่สุดของ training set หรือ global minimum ได้ (ก้นหลุมที่ลึกที่สุด) แต่ไปถึงจุดที่ต่ำอีกที่ ซึ่งไม่ใช่จุดที่ต่ำที่สุดเราเรียกจุดนี้ว่า local minimum ยกตัวอย่างรูปข้างบนจะเห็นว่าหลุมซ้ายมือลึกว่าหลุมขวามือ (สีน้ำเงินเข้มกว่า) แสดงว่าการ optimize ครั้งนี้เราโชคดีที่ optimize ได้ค่า global minimum แต่ถ้ารันอีกครั้ง gradient ของเราอาจจะไปตกหลุมทางขวามือก็ได้ ไม่ได้การันตีว่าจะได้ global minimum เสมอไป

แต่สำหรับ linear regression ตัวแปรเดียว (\theta_1)  ความสัมพันธ์ระหว่าง cost function และ \theta นั้นเป็นแบบ blow shape เพราะฉะนั้นเราจึงการันตีได้ว่าเราจะได้ global minimum ค่อนข้างแน่นอน

 

One Comment

  1. Anonymous Anonymous

    ขอบคุณค่ะ

Leave a Reply

Your email address will not be published.