Online Gradient Boosting
- ผู้เสนอ
- Grubb, A. & Bagnell, J. A.; Beygelzimer, A. et al.
- ปี
- 2011–2015
- ประเภท
- Online ensemble (sequential boosting on streaming data)
- กลุ่มวิธี
- Machine learning
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
Online Gradient Boosting ปรับกรอบการทำงานของ gradient boosting สำหรับการตั้งค่าแบบสตรีมมิง ซึ่งข้อมูลจะเข้ามาทีละตัวอย่าง แทนที่จะเป็นชุดข้อมูลคงที่ ในแต่ละขั้นตอน โมเดลจะคำนวณค่า pseudo-residual สำหรับการสังเกตที่เข้ามา และอัปเดต weak learner ในตำแหน่งนั้นๆ โดยการสร้าง ensemble แบบเพิ่มพูนโดยไม่ต้องจัดเก็บหรือย้อนกลับไปดูข้อมูลเก่า ทำให้เหมาะสำหรับการทำนายแบบเรียลไทม์และไปป์ไลน์สตรีมมิงขนาดใหญ่ที่ไม่สามารถฝึกใหม่ทั้งหมดได้
แนวคิดเบื้องหลังวิธีการ
การทำ gradient boosting แบบมาตรฐานจะวนซ้ำชุดข้อมูลฝึกทั้งหมดเพื่อปรับต้นไม้ที่ตามมา ซึ่งต้องใช้ข้อมูลทั้งหมดที่มีอยู่ล่วงหน้า Online Gradient Boosting แทนที่การผ่านชุดข้อมูลแบบนั้นด้วยการอัปเดตทีละตัวอย่าง: เมื่อมีการสังเกตใหม่เข้ามา ensemble ปัจจุบันจะทำนายตัวอย่างนั้น สัญญาณข้อผิดพลาด (pseudo-residual) จะถูกคำนวณ และ weak learner ถัดไปในสายโซ่จะถูกผลักดันให้แก้ไขข้อผิดพลาดนั้น เนื่องจากมีการอัปเดตทีละน้อย โมเดลจึงสามารถติดตาม concept drift ได้ตลอดเวลา — หากการกระจายข้อมูลพื้นฐานเปลี่ยนแปลงไป ตัวอย่างล่าสุดจะมีอิทธิพลมากกว่าตัวอย่างเก่าโดยอัตโนมัติ
ประวัติศาสตร์
การ boosting ในการตั้งค่าแบบออนไลน์ได้รับการสำรวจครั้งแรกโดย Oza และ Russell (2001) สำหรับ bagging และ boosting ด้วยน้ำหนักที่สุ่มแบบ Poisson Grubb และ Bagnell (2011) ได้ทำให้ Online Gradient Boosting เป็นรูปธรรมผ่าน functional gradient descent สำหรับ convex losses Beygelzimer, Hazan, Langford และ Zheng (2015) ได้ให้ขอบเขตการแปลงจากออนไลน์ไปเป็นแบตช์ที่แม่นยำ ซึ่งเชื่อมโยงการรับประกันค่าเสียโอกาสในการตั้งค่าแบบออนไลน์กับข้อผิดพลาดในการสรุปผลในการตั้งค่าแบบแบตช์ ทำให้ Online Gradient Boosting มีพื้นฐานทางทฤษฎีที่มั่นคง
ควรใช้เมื่อใด
ใช้ Online Gradient Boosting เมื่อข้อมูลเข้ามาเป็นสตรีมต่อเนื่อง และการฝึกใหม่ทั้งหมดหลังจากแต่ละชุดข้อมูลใหม่ช้าเกินไปหรือไม่สามารถทำได้จริง เมื่อการจัดเก็บข้อมูลย้อนหลังไม่สามารถทำได้เนื่องจากปริมาณหรือข้อจำกัดด้านความเป็นส่วนตัว หรือเมื่อกระบวนการสร้างข้อมูลอาจเปลี่ยนแปลงไปตามกาลเวลา (concept drift) และโมเดลต้องปรับตัวทีละน้อย นอกจากนี้ยังเหมาะสมสำหรับชุดข้อมูลขนาดใหญ่มากซึ่งการผ่านชุดข้อมูลเดียวมีค่าใช้จ่ายสูงเกินไป **ห้าม**ใช้เมื่อชุดข้อมูลทั้งหมดพอดีกับหน่วยความจำและทรัพยากรคอมพิวเตอร์อนุญาตให้ใช้ standard batch gradient boosting — วิธีการแบบ batch เช่น XGBoost หรือ LightGBM โดยทั่วไปจะให้ความแม่นยำสูงกว่าภายใต้เงื่อนไขเหล่านั้น หลีกเลี่ยงเมื่อไม่สามารถกำหนดจำนวนรอบการ boosting ล่วงหน้าได้ หรือเมื่อความสามารถในการตีความของต้นไม้แต่ละต้นเป็นข้อกำหนดที่สำคัญ
ข้อจำกัดและข้อควรพิจารณา
- โดยทั่วไปให้ความแม่นยำต่ำกว่า batch gradient boosting (XGBoost, LightGBM) เมื่อมีข้อมูลทั้งหมด เนื่องจากแต่ละตัวอย่างจะถูกมองเห็นเพียงครั้งเดียว
- จำนวนรอบการ boosting ต้องถูกกำหนดไว้ล่วงหน้าก่อนเริ่มสตรีม จำกัดความยืดหยุ่นของโครงสร้าง
- ไวต่อลำดับของตัวอย่างที่เข้ามา: การสับเปลี่ยนหรือการเปลี่ยนแปลงการกระจายในสตรีมอาจทำให้การฝึกไม่เสถียร
- การรับประกันการลู่เข้าอ่อนแอกว่าในสถานการณ์แบบ batch และขึ้นอยู่กับ learning rate ที่เลือกเป็นอย่างมาก
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ประมวลผลข้อมูลในรอบเดียวโดยไม่ต้องจัดเก็บชุดข้อมูลทั้งหมด ทำให้ประหยัดหน่วยความจำสำหรับสตรีมขนาดใหญ่หรืออนันต์
- ปรับตัวเข้ากับ concept drift เนื่องจากตัวอย่างล่าสุดจะอัปเดต weak learners อย่างต่อเนื่อง
- รักษาพลังการทำนายที่แข็งแกร่งของ gradient boosting ในสถานการณ์ที่การฝึกแบบ batch ไม่สามารถทำได้
- สามารถให้บริการการทำนายแบบเรียลไทม์ในแต่ละขั้นตอน — โมเดลพร้อมเสมอสำหรับการทำนาย
- เข้ากันได้กับฟังก์ชัน loss ที่สามารถหาอนุพันธ์ได้ทุกรูปแบบ รองรับการถดถอย การจำแนกประเภทแบบสองกลุ่มและหลายกลุ่ม
การประยุกต์ใช้
- การทำนายอัตราการคลิกแบบเรียลไทม์ในระบบโฆษณาออนไลน์
- การตรวจจับการฉ้อโกงบนสตรีมธุรกรรมทางการเงินที่ต้องการการอัปเดตโมเดลทันที
- การจำแนกข้อมูลเซ็นเซอร์ในไปป์ไลน์ IoT ที่ไม่สามารถเก็บข้อมูลย้อนหลังได้
- การจัดอันดับและการแนะนำแบบปรับได้ในระบบที่ความชอบของผู้ใช้เปลี่ยนแปลงไปตามกาลเวลา
- การตรวจจับความผิดปกติของอนุกรมเวลาขนาดใหญ่ด้วยการปรับโมเดลอย่างต่อเนื่อง
วิธีการทำงาน
วิธีการทำงาน
มีการกำหนดจำนวน weak learners (โดยทั่วไปคือต้นไม้ตื้นๆ หรือโมเดลเชิงเส้น) ไว้ล่วงหน้า หนึ่งรายการสำหรับแต่ละรอบการ boosting ในการตั้งค่าแบบออนไลน์ จำนวนรอบจะต้องตัดสินใจก่อนเริ่มสตรีม เนื่องจากโครงสร้าง ensemble ไม่สามารถเติบโตได้ตามอำเภอใจในเวลาทำนาย
ตัวอย่างที่มีป้ายกำกับเดียว (x_t, y_t) เข้ามาจากสตรีม ensemble ปัจจุบัน F_t จะสร้างการทำนายสำหรับ x_t และป้ายกำกับจริง y_t จะถูกเปิดเผยทันทีหลังจากนั้น ทำให้สามารถคำนวณสัญญาณข้อผิดพลาดได้โดยไม่ต้องมองไปข้างหน้า
ค่า pseudo-residual r_t คือค่าลบของ gradient ของฟังก์ชัน loss เทียบกับการทำนายของ ensemble ปัจจุบัน สำหรับ squared error จะลดรูปเป็น r_t = y_t - F_t(x_t); สำหรับ log-loss ค่า residual จะเข้ารหัสข้อผิดพลาดของความน่าจะเป็น เป้าหมายนี้จะนำทาง weak learner ถัดไปเพื่อแก้ไขข้อผิดพลาดปัจจุบัน
สูตร
r_t = -\nabla_{F} L(y_t, F(x_t))weak learner ที่ใช้งานอยู่ h_t จะถูกอัปเดตโดยใช้ pseudo-residual เป็นเป้าหมาย โดยใช้กฎการเรียนรู้ออนไลน์ (เช่น stochastic gradient descent บนโมเดลเชิงเส้น หรือการอัปเดตการแบ่ง Hoeffding-tree-style) ดังนั้น weak learner แต่ละตัวจะสะสมการแก้ไขตลอดสตรีมโดยไม่ต้องจัดเก็บข้อมูลเก่า
ensemble จะถูกอัปเดตแบบเพิ่มพูน: ผลลัพธ์ของ weak learner ที่อัปเดตแล้ว h_t ซึ่งปรับขนาดด้วย learning rate eta จะถูกเพิ่มเข้าไปในการทำนายปัจจุบัน F_t ผลลัพธ์ F_{t+1} จะพร้อมใช้งานทันทีสำหรับการทำนายตัวอย่างที่เข้ามาถัดไป
สูตร
F_{t+1}(x) = F_t(x) + \eta \, h_t(x)ข้อผิดพลาดที่พบบ่อย
- การเลือก learning rate ที่ใหญ่เกินไปทำให้ ensemble เกิดการแกว่งและไม่สามารถลู่เข้าสู่ผลลัพธ์ที่เสถียรได้
- การปฏิบัติต่อเมตริกการตรวจสอบแบบออนไลน์เทียบเท่ากับผลการ cross-validation — ต้องใช้การประเมินแบบ prequential (test-then-train) แทน
- การละเลย concept drift: หากการกระจายสตรีมเปลี่ยนแปลงอย่างกะทันหัน weak learners เก่าอาจมีอิทธิพลและทำให้ประสิทธิภาพลดลง เว้นแต่จะมีกลไกตรวจจับ drift หรือกลยุทธ์การลืม
- การกำหนดจำนวนรอบการ boosting น้อยเกินไปก่อนเริ่มสตรีม ทำให้ ensemble ขาดความสามารถในการสร้างแบบจำลองรูปแบบที่ซับซ้อน
คำถามที่พบบ่อย
Online Gradient Boosting แตกต่างจาก XGBoost หรือ LightGBM มาตรฐานอย่างไร?
XGBoost และ LightGBM เป็นวิธีการแบบ batch ที่วนซ้ำชุดข้อมูลฝึกทั้งหมดหลายครั้งเพื่อปรับต้นไม้แบบ greedy Online Gradient Boosting จะอัปเดต weak learners หลังจากสังเกตแต่ละครั้งและไม่เคยย้อนกลับไปดูข้อมูลเก่า วิธีการแบบ Batch มีความแม่นยำมากกว่าเมื่อข้อมูลพอดีกับหน่วยความจำ ผู้ใช้แบบออนไลน์จะแลกความแม่นยำกับความสามารถในการปรับขนาดและการปรับตัวแบบเรียลไทม์
ฉันควรประเมินโมเดลออนไลน์อย่างยุติธรรมได้อย่างไร?
ใช้การประเมินแบบ prequential (test-then-train): สำหรับแต่ละตัวอย่างที่เข้ามา ให้บันทึกการทำนายของโมเดลก่อนที่จะอัปเดตด้วยป้ายกำกับของตัวอย่างนั้น วิธีนี้จะให้ค่าประมาณข้อผิดพลาดที่ไม่เอนเอียงและซื่อสัตย์ตามเวลา โดยไม่ต้องใช้ชุดข้อมูลทดสอบที่แยกไว้
ฉันจะจัดการกับ concept drift ได้อย่างไร?
จับคู่ Online Gradient Boosting กับอัลกอริทึมตรวจจับ drift (เช่น ADWIN หรือ DDM) ที่ส่งสัญญาณเมื่ออัตราข้อผิดพลาดเพิ่มขึ้นอย่างมีนัยสำคัญ เมื่อตรวจพบ ให้รีเซ็ตหรือเริ่มต้น weak learners ที่ได้รับผลกระทบใหม่ เพื่อให้ ensemble สามารถปรับตัวเข้ากับการกระจายใหม่ได้
Online Gradient Boosting เหมาะสำหรับปัญหา multiclass หรือไม่?
ใช่ ด้วยฟังก์ชัน loss แบบ multiclass ที่สามารถหาอนุพันธ์ได้ (เช่น softmax cross-entropy) ค่า pseudo-residual จะกลายเป็นเวกเตอร์ของข้อผิดพลาดเฉพาะคลาส และ weak learner แต่ละตัวจะถูกอัปเดตเพื่อแก้ไขผลลัพธ์ทุกคลาสพร้อมกัน เช่นเดียวกับการกำหนดค่า gradient boosting แบบ multiclass แบบ batch
weak learners แบบใดที่ทำงานได้ดีที่สุดในทางปฏิบัติ?
ต้นไม้ Hoeffding ที่ตื้น (ซึ่งรองรับการแบ่งแบบออนไลน์ด้วยตัวเอง) หรือโมเดลเชิงเส้นแบบออนไลน์เป็นตัวเลือกที่พบบ่อยที่สุด พวกมันอัปเดตได้อย่างมีประสิทธิภาพด้วยแต่ละตัวอย่างใหม่และหลีกเลี่ยงความจำเป็นในการจัดเก็บข้อมูลสำหรับการ refit แบบ batch ในแต่ละขั้นตอนการ boosting
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Grubb, A. & Bagnell, J. A. (2011). Generalized Boosting Algorithms for Convex Optimization. Proceedings of the 28th International Conference on Machine Learning (ICML 2011), 1209–1216.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้วBeygelzimer, A., Hazan, E., Langford, J. & Zheng, T. (2015). Online-to-Batch Conversions and Applications. Advances in Neural Information Processing Systems (NeurIPS), 28.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้ว