การลดตามเกรเดียนต์แบบสุ่ม (Stochastic Gradient Descent: SGD)
- ผู้เสนอ
- Robbins, H. & Monro, S.
- ปี
- 1951
- ประเภท
- First-order iterative optimization algorithm
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
Stochastic Gradient Descent (SGD) คืออัลกอริทึมการหาค่าเหมาะที่สุดแบบวนซ้ำลำดับที่หนึ่ง ซึ่งมีรากฐานมาจากกรอบการทำงานการประมาณค่าแบบสุ่ม (stochastic approximation) ที่พัฒนาโดย Robbins และ Monro ในปี 1951 โดยมีเป้าหมายเพื่อทำให้ฟังก์ชันวัตถุประสงค์ (objective function) มีค่าต่ำที่สุด ด้วยการอัปเดตพารามิเตอร์ของโมเดลโดยใช้เกรเดียนต์ (gradient) ที่คำนวณจากข้อมูลฝึกที่สุ่มเลือกมาเพียงตัวอย่างเดียว (หรือกลุ่มตัวอย่างขนาดเล็กที่เรียกว่า mini-batch) ในแต่ละขั้น เป็นกลไกการหาค่าเหมาะที่สุดหลักที่อยู่เบื้องหลังการเรียนรู้ของเครื่อง (machine learning) และการเรียนรู้เชิงลึก (deep learning) ในปัจจุบัน ซึ่งช่วยให้สามารถฝึกโมเดลบนชุดข้อมูลที่มีขนาดใหญ่เกินกว่าจะบรรจุในหน่วยความจำได้
แนวคิดเบื้องหลังวิธีการ
Ordinary gradient descent คำนวณเกรเดียนต์ที่แม่นยำของฟังก์ชันความสูญเสีย (loss function) จากข้อมูลฝึกทั้งหมดก่อนที่จะอัปเดตพารามิเตอร์เพียงครั้งเดียว ซึ่งถูกต้องแต่ช้ามากจนเป็นไปไม่ได้ในทางปฏิบัติสำหรับชุดข้อมูลขนาดใหญ่ SGD แลกเปลี่ยนความแม่นยำกับความเร็ว โดยจะสุ่มเลือกข้อมูลหนึ่งตัวอย่าง (หรือกลุ่มตัวอย่างขนาดเล็ก) คำนวณค่าประมาณของเกรเดียนต์ที่มีสัญญาณรบกวน (noisy estimate) และอัปเดตพารามิเตอร์ทันที สัญญาณรบกวนนี้ไม่ใช่แค่ปัญหา แต่ทำหน้าที่เป็นเรกูลาไรเซชันโดยนัย (implicit regularization) ช่วยให้ตัวหาค่าเหมาะที่สุด (optimizer) หลุดพ้นจากค่าต่ำสุดเฉพาะที่ (local minima) ที่ตื้นและจุดอานม้า (saddle points) เมื่อผ่านการวนซ้ำหลายครั้ง ขั้นตอนที่มีสัญญาณรบกวนเหล่านี้จะเฉลี่ยกันไป และพารามิเตอร์จะลู่เข้าสู่ค่าต่ำสุดของฟังก์ชันความสูญเสีย คล้ายกับการเดินของคนเมาที่ยังคงไปถึงจุดหมายปลายทางได้
ประวัติศาสตร์
รากฐานทางทฤษฎีสำหรับ SGD วางไว้โดย Herbert Robbins และ Sutton Monro ในบทความปี 1951 เรื่อง 'A Stochastic Approximation Method' ซึ่งพิสูจน์ว่าการอัปเดตแบบสุ่มที่มีการลดขนาดก้าว (step size) จะลู่เข้าสู่รากของฟังก์ชันการถดถอย การเชื่อมโยงกับการหาค่าเหมาะที่สุดโดยใช้เกรเดียนต์ได้รับการทำให้ชัดเจนโดย Kiefer และ Wolfowitz (1952) และต่อมาโดยกฎ LMS ของ Widrow และ Hoff (1960) สำหรับการกรองแบบปรับตัวได้ (adaptive filtering) SGD ได้รับความนิยมในการเรียนรู้ของเครื่องผ่านงานของ LeCun และคณะในช่วงปลายทศวรรษ 1980 และ 1990 สำหรับการฝึกโครงข่ายประสาทเทียมโดยใช้ backpropagation การตีพิมพ์การทดลองขนาดใหญ่โดย Bottou และคณะในช่วงปี 2000 แสดงให้เห็นถึงความเหนือกว่าของ SGD เมื่อเทียบกับวิธี batch บนชุดข้อมูลอุตสาหกรรม รูปแบบ mini-batch SGD สมัยใหม่กลายเป็นที่แพร่หลายพร้อมกับการกลับมาโด่งดังของการเรียนรู้เชิงลึกราวปี 2012 (AlexNet) และอัลกอริทึมยังคงเป็นตัวหาค่าเหมาะที่สุดที่โดดเด่นในสาขานี้ โดยมีรูปแบบต่างๆ เช่น Adam (Kingma & Ba, 2014) สร้างขึ้นโดยตรงจากกฎการอัปเดตของมัน
ควรใช้เมื่อใด
SGD เป็นวิธีการที่เลือกใช้เมื่อชุดข้อมูลฝึกมีขนาดใหญ่พอที่การคำนวณเกรเดียนต์เต็มรูปแบบต่อการอัปเดตหนึ่งครั้งมีค่าใช้จ่ายสูงเกินไป ซึ่งครอบคลุมการฝึกโครงข่ายประสาทเทียมสมัยใหม่เกือบทั้งหมดและการฟิตโมเดลเชิงเส้นขนาดใหญ่ สามารถนำไปใช้กับฟังก์ชันความสูญเสียที่หาอนุพันธ์ได้ทุกรูปแบบ ข้อสมมติหลักคือ ฟังก์ชันความสูญเสียสามารถหาอนุพันธ์ได้ (หรือหาอนุพันธ์ย่อยได้) เทียบกับพารามิเตอร์ จุดข้อมูลถูกสุ่มมาอย่างอิสระ และค่าประมาณของเกรเดียนต์ไม่เอนเอียง สำหรับฟังก์ชันวัตถุประสงค์แบบนูนอย่างยิ่ง (strongly convex) SGD ให้การลู่เข้าที่ O(1/T) สำหรับฟังก์ชันวัตถุประสงค์ทั่วไปที่ไม่ใช่นูน (non-convex objectives) (เช่น โครงข่ายประสาทเทียมเชิงลึก) ในทางปฏิบัติจะพบจุดคงที่ (stationary points) แม้ว่าจะไม่มีการรับประกันความเหมาะที่สุดระดับรวม (global optimality) Mini-batch SGD (ขนาด batch 32–512) มักจะถูกเลือกใช้มากกว่า pure single-example SGD เนื่องจากให้ค่าประมาณเกรเดียนต์ที่มีความแปรปรวนต่ำกว่าและใช้ประโยชน์จากการประมวลผลแบบขนานบนฮาร์ดแวร์สมัยใหม่ได้ เมื่อชุดข้อมูลมีขนาดเล็กพอสำหรับการทำ full-batch gradient descent และฟังก์ชันวัตถุประสงค์มีสภาพดี (well-conditioned) วิธีการอันดับสอง (second-order methods) เช่น L-BFGS อาจลู่เข้าได้เร็วกว่า
ข้อจำกัดและข้อควรพิจารณา
- ค่าประมาณเกรเดียนต์มีสัญญาณรบกวน ซึ่งทำให้ฟังก์ชันความสูญเสียผันผวนแทนที่จะลดลงอย่างต่อเนื่อง ทำให้การวินิจฉัยการลู่เข้าทำได้ยากขึ้น
- มีความอ่อนไหวสูงต่ออัตราการเรียนรู้: หากมากเกินไปจะทำให้เกิดการลู่ออก (divergence) หากน้อยเกินไปจะทำให้การฝึกช้ามากจนเป็นไปไม่ได้ในทางปฏิบัติ
- ไม่รับประกันว่าจะหาค่าต่ำสุดระดับรวม (global minimum) สำหรับฟังก์ชันวัตถุประสงค์ที่ไม่ใช่นูน (non-convex objectives) เช่น โครงข่ายประสาทเทียมเชิงลึก
- การอัปเดตแบบไอโซโทรปิก (isotropic updates) ให้น้ำหนักทุกมิติของพารามิเตอร์เท่ากัน ทำให้ไม่เหมาะกับพื้นผิวความสูญเสียที่มีความโค้งแตกต่างกันอย่างมากในแกนที่ต่างกัน — ซึ่งเป็นแรงจูงใจให้เกิดรูปแบบที่ปรับอัตราเรียนรู้ได้เอง (adaptive-rate variants)
- ต้องการการปรับอัตราการเรียนรู้ (learning rate schedule) อย่างระมัดระวัง ตารางเวลาที่ไม่ดีจะลดทอนประสิทธิภาพสุดท้ายลงอย่างมาก
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ปรับขนาดได้กับชุดข้อมูลขนาดใหญ่ได้อย่างไม่จำกัด เนื่องจากแต่ละการอัปเดตต้องการเพียงข้อมูลตัวอย่างเดียวหรือ mini-batch ทำให้หน่วยความจำและทรัพยากรในการประมวลผลต่อขั้นคงที่
- สัญญาณรบกวนที่เกิดขึ้นโดยธรรมชาติให้เรกูลาไรเซชันโดยนัย (implicit regularization) และช่วยให้หลุดพ้นจากค่าต่ำสุดเฉพาะที่ที่ตื้นและจุดอานม้าในพื้นที่ที่ไม่ใช่นูน (non-convex landscapes)
- มีความยืดหยุ่นสูงมาก: สามารถนำไปใช้กับฟังก์ชันความสูญเสียที่หาอนุพันธ์ได้ทุกรูปแบบ รวมถึง cross-entropy, mean squared error, hinge loss และฟังก์ชันวัตถุประสงค์ที่กำหนดเอง
- เป็นรากฐานของตัวหาค่าเหมาะที่สุดสมัยใหม่เกือบทั้งหมด (Adam, RMSProp, AdaGrad, Nesterov momentum) — การทำความเข้าใจ SGD เป็นสิ่งจำเป็นก่อนที่จะเข้าใจตัวอื่นๆ
- ง่ายต่อการนำไปใช้และประมวลผลแบบขนานบน GPU โดยใช้ mini-batches
การประยุกต์ใช้
- การฝึกโครงข่ายประสาทเทียมเชิงลึกสำหรับการจำแนกรูปภาพ การรู้จำเสียงพูด และการประมวลผลภาษาธรรมชาติ
- การฟิตโมเดล logistic regression และ linear SVM ขนาดใหญ่ในงานจำแนกข้อความและระบบแนะนำ
- การตั้งค่าการเรียนรู้แบบออนไลน์ (online learning) ที่ตัวอย่างข้อมูลมาถึงตามลำดับและโมเดลต้องอัปเดตแบบเรียลไทม์
- วิธีการหาค่าเหมาะที่สุดของนโยบาย (policy gradient methods) ในการเรียนรู้แบบเสริมกำลัง (reinforcement learning) ซึ่งผลตอบแทนที่คาดหวังจะถูกหาค่าเหมาะที่สุดโดยใช้เส้นทางที่สุ่มมา
- การแยกตัวประกอบเมทริกซ์ (Matrix factorization) สำหรับการกรองแบบร่วมมือ (collaborative filtering) ในระบบแนะนำ
วิธีการทำงาน
วิธีการทำงาน
วัตถุประสงค์ของการฝึกคือค่าเฉลี่ยของฟังก์ชันความสูญเสียจากข้อมูลทั้งหมด n ตัวอย่าง สำหรับงานต่างๆ เช่น การจำแนกประเภท (classification) ด้วย cross-entropy หรือการถดถอย (regression) ด้วย squared error ผลรวมนี้อาจมีเทอมนับพันล้าน ทำให้การประเมินค่าเต็มรูปแบบในแต่ละขั้นเป็นไปไม่ได้ในทางปฏิบัติ
สูตร
L(\theta) = \frac{1}{n} \sum_{i=1}^{n} \ell(f(x_i; \theta),\, y_i)ในขั้นที่ t จะมีการสุ่มเลือกข้อมูลฝึกหนึ่งตัวอย่าง (หรือ mini-batch) อย่างสม่ำเสมอ เกรเดียนต์ของฟังก์ชันความสูญเสียจากตัวอย่างนั้นเป็นค่าประมาณที่ไม่เอนเอียง (unbiased estimator) ของเกรเดียนต์ที่แท้จริง ดังนั้นโดยเฉลี่ยแล้ว การอัปเดตจะดำเนินไปในทิศทางที่ถูกต้อง แม้ว่าจะมีสัญญาณรบกวนในแต่ละขั้นก็ตาม
สูตร
\hat{g}_t = \nabla_\theta \ell(f(x_{i_t}; \theta_t),\, y_{i_t})เวกเตอร์พารามิเตอร์จะถูกเคลื่อนที่ไปในทิศทางตรงกันข้ามกับค่าประมาณของเกรเดียนต์ โดยมีอัตราการเรียนรู้ (learning rate) eta_t เป็นตัวปรับขนาด อัตราการเรียนรู้ที่น้อยลงทำให้การอัปเดตระมัดระวังแต่ช้า ในขณะที่อัตราที่มากขึ้นจะเร่งการลู่เข้าแต่มีความเสี่ยงที่จะพุ่งเลยค่าต่ำสุด บรรทัดเดียวนี้ — การอัปเดตแบบ Robbins–Monro — เป็นหัวใจสำคัญของตัวหาค่าเหมาะที่สุดเกือบทั้งหมดในปัจจุบัน
สูตร
\theta_{t+1} = \theta_t - \eta_t \, \hat{g}_tเงื่อนไขของ Robbins–Monro (ผลรวมของอัตราการเรียนรู้ลู่ออก แต่ผลรวมของอัตราการเรียนรู้ยกกำลังสองลู่เข้า) รับประกันการลู่เข้าสำหรับฟังก์ชันวัตถุประสงค์แบบนูน (convex objectives) ในทางปฏิบัติ ตารางเวลาที่ใช้กันทั่วไป ได้แก่ การลดอัตราแบบขั้นบันได (step decay), การลดอัตราแบบโคไซน์ (cosine annealing) และการเริ่มต้นใหม่ (warm restarts) เงื่อนไขเหล่านี้ให้พื้นฐานทางทฤษฎีว่าทำไมตารางเวลาที่ลดลงจึงจำเป็น
สูตร
\sum_{t=1}^{\infty} \eta_t = \infty, \quad \sum_{t=1}^{\infty} \eta_t^2 < \inftyข้อผิดพลาดที่พบบ่อย
- การใช้อัตราการเรียนรู้คงที่ตลอดการฝึกโดยไม่มีตารางเวลาการลดลงใดๆ ทำให้ตัวหาค่าเหมาะที่สุดแกว่งไปมารอบๆ ค่าต่ำสุด แทนที่จะเข้าไปสู่ค่าต่ำสุดนั้น
- การเลือกขนาด batch โดยไม่คำนึงถึงผลของเรกูลาไรเซชันโดยนัย: batch ที่ใหญ่มากจะลดสัญญาณรบกวนและอาจส่งผลเสียต่อ generalization เมื่อเทียบกับ batch ที่เล็กกว่าในจำนวน epoch เท่ากัน
- การลืมสับเปลี่ยน (shuffle) ข้อมูลฝึกก่อนแต่ละ epoch ซึ่งอาจนำไปสู่ความเอนเอียงที่เป็นระบบเมื่อข้อมูลถูกจัดเรียงตามคลาสหรือเวลา
- การปรับอัตราการเรียนรู้โดยพิจารณาจากฟังก์ชันความสูญเสียบนชุดข้อมูลตรวจสอบ (validation loss) เพียงครั้งเดียว แทนที่จะติดตามเส้นโค้งการฝึก ซึ่งอาจพลาดสัญญาณของการลู่ออกหรือการถึงจุดคงที่ (plateau) ก่อนเวลาอันควร
- การมอง SGD เป็นกล่องดำ (black-box optimizer) โดยไม่เข้าใจคุณสมบัติการลู่เข้า จากนั้นจึงเปลี่ยนไปใช้ Adam อย่างไม่ไตร่ตรองเมื่อการลู่เข้าดูเหมือนจะช้า โดยไม่ได้วินิจฉัยสาเหตุที่แท้จริง
คำถามที่พบบ่อย
ความแตกต่างระหว่าง SGD, mini-batch SGD และ full-batch gradient descent คืออะไร?
Full-batch gradient descent คำนวณเกรเดียนต์ที่แม่นยำจากข้อมูลฝึกทั้งหมด n ตัวอย่างต่อการอัปเดตหนึ่งครั้ง — มีค่าใช้จ่าย O(n) ต่อขั้น แต่แม่นยำ Pure SGD ใช้ข้อมูลที่สุ่มเลือกเพียงตัวอย่างเดียวต่อการอัปเดต — มีค่าใช้จ่าย O(1) แต่มีสัญญาณรบกวนสูง Mini-batch SGD ใช้ชุดข้อมูลย่อยแบบสุ่มขนาดเล็ก (โดยทั่วไปคือ 32–512 ตัวอย่าง) — เป็นการประนีประนอมที่ใช้งานได้จริง ซึ่งช่วยลดสัญญาณรบกวนในขณะที่ยังคงรักษาค่าใช้จ่ายให้อยู่ในระดับที่จัดการได้และใช้ประโยชน์จากการประมวลผลแบบขนานของ GPU ได้ ในการใช้งานสมัยใหม่ 'SGD' เกือบจะหมายถึง mini-batch SGD เสมอ
ควรตั้งค่าอัตราการเรียนรู้ (learning rate) อย่างไร?
ไม่มีคำตอบที่เป็นสากล แต่วิธีปฏิบัติทั่วไปคือการเริ่มต้นด้วยค่าปานกลาง (เช่น 0.01 หรือ 0.1) ติดตามเส้นโค้งฟังก์ชันความสูญเสียระหว่างการฝึก และใช้ตารางเวลาการลดลง (decay schedule) เช่น step decay, cosine annealing หรือ warm restarts เครื่องมือค้นหาอัตราการเรียนรู้ (learning rate finders) (โดยการทดสอบอัตราต่างๆ กับ batch จำนวนเล็กน้อยและสังเกตฟังก์ชันความสูญเสีย) สามารถช่วยระบุค่าเริ่มต้นที่ดีได้ ทฤษฎี Robbins–Monro ต้องการให้อัตราการเรียนรู้ลดลงจนเป็นศูนย์ แต่ในทางปฏิบัติมักจะใช้การลดลงอย่างนุ่มนวลเพื่อหลีกเลี่ยงการช้าลงก่อนเวลาอันควร
เหตุใด SGD จึงสามารถgeneralize ได้ดีกว่า Adam ในบางครั้ง?
ตัวหาค่าเหมาะที่สุดที่ปรับอัตราเรียนรู้ได้เอง (adaptive-rate optimizers) เช่น Adam มักจะลู่เข้าได้เร็วกว่า แต่ก็อาจเกิดการเรียนรู้เกิน (overfitting) ได้ง่ายกว่า โดยเฉพาะอย่างยิ่งในงานจำแนกรูปภาพ สัญญาณรบกวนที่สูงขึ้นใน SGD — โดยเฉพาะอย่างยิ่งเมื่อใช้ batch ขนาดเล็ก — ทำหน้าที่เป็นเรกูลาไรเซชันโดยนัย (implicit regularization) ช่วยให้โมเดลพบค่าต่ำสุดที่ราบเรียบกว่าซึ่ง generalize ได้ดีกว่า การศึกษาเชิงประจักษ์หลายชิ้น (เช่น Wilson et al., 2017) ได้บันทึกปรากฏการณ์นี้ ซึ่งเป็นเหตุผลว่าทำไม SGD พร้อมโมเมนตัม (momentum) จึงยังคงเป็นที่นิยมในการฝึกโมเดลคอมพิวเตอร์วิทัศน์ เช่น ResNet
SGD รับประกันว่าจะหาค่าต่ำสุดระดับรวม (global minimum) หรือไม่?
เฉพาะสำหรับฟังก์ชันวัตถุประสงค์แบบนูนอย่างยิ่ง (strictly convex objectives) ภายใต้เงื่อนไขอัตราการเรียนรู้แบบ Robbins–Monro สำหรับฟังก์ชันวัตถุประสงค์ที่ไม่ใช่นูน (non-convex objectives) (ซึ่งแทบจะเป็นโครงข่ายประสาทเทียมเชิงลึกทั้งหมด) SGD จะให้การลู่เข้าสู่จุดคงที่ (stationary point) (ที่ซึ่งเกรเดียนต์เป็นศูนย์) ซึ่งในทางปฏิบัติมักจะเป็นค่าต่ำสุดเฉพาะที่ที่ดี แทนที่จะเป็นจุดอานม้าหรือค่าต่ำสุดระดับรวม ในเชิงประจักษ์ ผลลัพธ์ที่ได้มักจะดีพอสำหรับประสิทธิภาพระดับ State-of-the-art
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Robbins, H. & Monro, S. (1951). A Stochastic Approximation Method. The Annals of Mathematical Statistics, 22(3), 400–407.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วGoodfellow, I., Bengio, Y. & Courville, A. (2016). Deep Learning (Ch. 8). MIT Press.
ISBN: 978-0-262-03561-3คัดลอกแล้ว