Skip to content
กลับไปยังผลการค้นหา

Online Bagging

ผู้เสนอ
Oza, N. C. & Russell, S.
ปี
2001
ประเภท
Online ensemble (streaming bagging)
กลุ่มวิธี
Machine learning

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

Online Bagging เป็นวิธีการเรียนรู้แบบกลุ่ม (ensemble method) สำหรับข้อมูลแบบสตรีม (streaming data) ที่ Oza และ Russell นำเสนอในปี 2001 โดยปรับกรอบการทำงานของ bootstrap aggregating (Bagging) แบบดั้งเดิมให้เข้ากับการเรียนรู้แบบออนไลน์ แทนที่จะสุ่มตัวอย่างจากชุดข้อมูลที่คงที่ แต่ละอินสแตนซ์ที่เข้ามาจะถูกป้อนให้กับผู้เรียนแต่ละราย (base learner) เป็นจำนวนครั้งที่สุ่มมาจาก การแจกแจงแบบปัวซง (Poisson(1)) ซึ่งเป็นการประมาณการสุ่มตัวอย่างแบบ bootstrap ได้อย่างแม่นยำเมื่อสตรีมข้อมูลมีการเปลี่ยนแปลง ผลลัพธ์ที่ได้คือกลุ่มผู้เรียนที่มีความทนทานและอัปเดตแบบเพิ่มพูน (incrementally updated) ซึ่งสามารถจัดการกับการเปลี่ยนแปลงของแนวคิด (concept drift) และการมาถึงของข้อมูลอย่างต่อเนื่องได้โดยไม่ต้องจัดเก็บชุดข้อมูลทั้งหมด

แนวคิดเบื้องหลังวิธีการ

Bagging แบบดั้งเดิมจะสุ่มตัวอย่างแบบ bootstrap จากชุดข้อมูลที่คงที่และฝึกต้นไม้ (tree) หนึ่งต้นต่อหนึ่งตัวอย่าง Online Bagging เลียนแบบกระบวนการนี้โดยไม่ต้องเห็นข้อมูลทั้งหมดในคราวเดียว: เมื่ออินสแตนซ์ใหม่มาถึง จะถูกส่งไปยังผู้เรียนแต่ละรายเป็นจำนวนครั้งแบบสุ่มที่ดึงมาจาก การแจกแจงแบบปัวซงที่มีค่าเฉลี่ยเท่ากับ 1 โดยเฉลี่ยแล้ว ผู้เรียนแต่ละรายจะเห็นอินสแตนซ์นั้นหนึ่งครั้ง ซึ่งเป็นสิ่งที่การสุ่มตัวอย่างแบบ bootstrap ทำได้ในโหมด batch แต่ความเป็นสุ่มจะช่วยลดความสัมพันธ์ระหว่างผู้เรียน เนื่องจากไม่จำเป็นต้องจัดเก็บข้อมูล กลุ่มผู้เรียนจึงสามารถเติบโตได้อย่างไม่จำกัดตามสตรีมข้อมูลและปรับตัวเข้ากับการเปลี่ยนแปลงของการแจกแจงตามเวลาได้อย่างเป็นธรรมชาติ

ประวัติศาสตร์

Online Bagging ถูกนำเสนอโดย Nitesh Oza และ Stuart Russell ในงาน AISTATS 2001 ในฐานะส่วนขยายเชิงทฤษฎีและเชิงปฏิบัติของอัลกอริทึม Bagging ปี 1996 ของ Breiman ไปสู่การเรียนรู้แบบออนไลน์ แนวคิดสำคัญ — การแทนที่การสุ่มตัวอย่างแบบ bootstrap ด้วยการกำหนดน้ำหนักแบบปัวซง(1) ต่ออินสแตนซ์ — ทำให้การประมาณการมีความแม่นยำทางคณิตศาสตร์ กลายเป็นอัลกอริทึมพื้นฐานในวรรณกรรมเกี่ยวกับการเรียนรู้ของเครื่องแบบสตรีม และเป็นกลุ่มผู้เรียนพื้นฐานในแพลตฟอร์มต่างๆ เช่น MOA (Massive Online Analysis) ซึ่งเป็นตัวขับเคลื่อนการประเมินเชิงประจักษ์ส่วนใหญ่ของตัวจำแนกประเภทสตรีมตั้งแต่ปี 2010

ควรใช้เมื่อใด

ควรใช้ Online Bagging เมื่อข้อมูลมาถึงในรูปแบบสตรีมต่อเนื่อง และการจัดเก็บชุดข้อมูลทั้งหมดเป็นไปไม่ได้หรือไม่ได้รับอนุญาต (เช่น บันทึกเซ็นเซอร์, clickstreams, ข้อมูล tick ทางการเงิน, การตรวจสอบแบบเรียลไทม์) เหมาะสมเมื่อคุณต้องการการจำแนกประเภทหรือการถดถอยที่อัปเดตทุกครั้งที่มีการสังเกตใหม่ ทนทานต่อการเปลี่ยนแปลงแนวคิดเล็กน้อย และมีประสิทธิภาพด้านหน่วยความจำ อย่าใช้ Online Bagging เป็นตัวทดแทนโดยตรงสำหรับ Random Forest แบบ batch บนชุดข้อมูลคงที่ขนาดเล็กถึงปานกลาง — กลุ่มผู้เรียนแบบ batch ที่มีการตรวจสอบไขว้ (cross-validation) จะทำงานได้ดีกว่าในกรณีนั้น หลีกเลี่ยงการใช้งานเมื่อสตรีมข้อมูลมีการเปลี่ยนแปลงอย่างรุนแรงและฉับพลันโดยไม่มีกลไกตรวจจับการเปลี่ยนแปลง (drift detection) เพิ่มเติม

ข้อจำกัดและข้อควรพิจารณา

  • บนชุดข้อมูลแบบคงที่ วิธีการแบบ batch เช่น Random Forest หรือ XGBoost ทำงานได้ดีกว่า Online Bagging อย่างสม่ำเสมอ เนื่องจากสามารถใช้ cross-validation เต็มรูปแบบและการแบ่งแยก (split) ที่เหมาะสมที่สุดได้
  • Online Bagging แบบพื้นฐานมีความทนทานต่อการเปลี่ยนแปลงแนวคิดที่รุนแรงจำกัด ควรเพิ่มตัวตรวจจับการเปลี่ยนแปลง (drift detector) ที่ออกแบบมาเฉพาะ (เช่น ADWIN) จากภายนอก
  • การกำหนดน้ำหนักแบบปัวซงเพิ่มความแปรปรวนต่ออินสแตนซ์ ซึ่งอาจทำให้การลู่เข้า (convergence) ช้าลงในสตรีมข้อมูลสั้นๆ
  • ความสามารถในการตีความ (interpretability) ต่ำ: กลุ่มต้นไม้ที่เติบโตแบบเพิ่มพูนจำนวนมากนั้นตรวจสอบได้ยากกว่าต้นไม้ตัดสินใจเดี่ยว

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • ประมวลผลข้อมูลทีละอินสแตนซ์ด้วยหน่วยความจำคงที่ ทำให้สามารถรองรับสตรีมข้อมูลที่ยาวนานได้อย่างแท้จริง
  • การกำหนดน้ำหนักแบบปัวซงเป็นการประมาณการสุ่มตัวอย่างแบบ bootstrap ที่พิสูจน์ได้ทางทฤษฎี ทำให้การลดความแปรปรวนของกลุ่มผู้เรียนเทียบเท่ากับ Bagging แบบ batch
  • สามารถประมวลผลแบบขนานได้อย่างเป็นธรรมชาติ: ผู้เรียนแต่ละรายอัปเดตอย่างอิสระ ทำให้เหมาะสำหรับสถาปัตยกรรมสตรีมแบบกระจาย
  • ไม่มีพารามิเตอร์ที่สำคัญเท่ากับความลึกของต้นไม้ — กลุ่มผู้เรียนจะปรับตัวเองผ่านความหลากหลาย (diversity)
  • สามารถขยายไปยังการจำแนกประเภทหลายคลาส (multi-class classification) และการถดถอยได้โดยตรงโดยไม่มีการเปลี่ยนแปลงโครงสร้าง

การประยุกต์ใช้

  • การตรวจจับการฉ้อโกงแบบเรียลไทม์บนสตรีมธุรกรรมต่อเนื่อง
  • การบำรุงรักษาเชิงคาดการณ์จากสตรีมข้อมูลเซ็นเซอร์ในสภาพแวดล้อม IoT อุตสาหกรรม
  • การคาดการณ์อัตราการคลิก (click-through rate) ในการโฆษณาออนไลน์ที่พฤติกรรมผู้ใช้มีการเปลี่ยนแปลงอย่างต่อเนื่อง
  • การตรวจจับการบุกรุกเครือข่ายบนสตรีมแพ็กเก็ตที่มีปริมาณงานสูง
  • การตรวจสอบสิ่งแวดล้อม: การจำแนกประเภทแบบเพิ่มพูนของข้อมูลเซ็นเซอร์คุณภาพอากาศหรือสภาพอากาศ

วิธีการทำงาน

วิธีการทำงาน

1

สำหรับแต่ละอินสแตนซ์ที่เข้ามา จะมีการสุ่มค่าน้ำหนัก k จากการแจกแจงแบบปัวซง(1) อย่างอิสระสำหรับผู้เรียนแต่ละราย ค่าน้ำหนัก 0 หมายความว่าผู้เรียนจะข้ามอินสแตนซ์นี้ไปโดยสิ้นเชิง ค่าน้ำหนัก 2 หมายความว่าผู้เรียนจะเรียนรู้จากอินสแตนซ์นั้นสองครั้ง การกำหนดน้ำหนักแบบสุ่มนี้เป็นการจำลองการสุ่มตัวอย่างแบบ bootstrap ในโหมดออนไลน์ และเป็นแกนหลักทางคณิตศาสตร์ของอัลกอริทึม

สูตร
k \sim \text{Poisson}(1)
2

ผู้เรียนแต่ละราย — โดยทั่วไปคือต้นไม้ตัดสินใจแบบเพิ่มพูน (incremental decision tree) เช่น Hoeffding Tree — จะได้รับอินสแตนซ์ปัจจุบันพร้อมน้ำหนักที่กำหนด และอัปเดตโมเดลภายในทันที จะไม่มีการจัดเก็บอินสแตนซ์ใดๆ หลังจากการประมวลผล คุณสมบัติการประมวลผลครั้งเดียว (single-pass) นี้ช่วยให้หน่วยความจำคงที่และทำให้กลุ่มผู้เรียนสามารถปรับขนาดให้รองรับสตรีมข้อมูลที่ยาวนานได้อย่างไม่จำกัด

3

เมื่อต้องการการทำนาย ผู้เรียนทั้ง M รายจะสร้างผลลัพธ์ของตนเองสำหรับอินสแตนซ์ที่ถูกสอบถาม กลุ่มผู้เรียนจะรวมผลลัพธ์เหล่านี้โดยการโหวตเสียงข้างมาก (majority vote) สำหรับการจำแนกประเภท (classification) หรือค่าเฉลี่ยเลขคณิต (arithmetic mean) สำหรับการถดถอย (regression) ซึ่งให้ตรรกะการรวมผลลัพธ์เช่นเดียวกับ Bagging แบบ batch แต่คำนวณจากโมเดลที่ฝึกแบบเพิ่มพูน

สูตร
\hat{y} = \text{mode/mean of } M \text{ base learners}

ข้อผิดพลาดที่พบบ่อย

  • การประเมิน Online Bagging ด้วยชุดข้อมูลทดสอบที่แยกไว้ซึ่งสร้างขึ้นก่อนเริ่มการฝึก — ควรใช้การประเมินแบบ prequential (ทดสอบ-แล้ว-ฝึก) แทน ซึ่งเป็นมาตรฐานในการเรียนรู้ของเครื่องแบบสตรีม
  • การสมมติว่าจำนวนผู้เรียนพื้นฐานเริ่มต้น (มักจะเป็น 10) เพียงพอแล้ว โดยทั่วไปจำเป็นต้องใช้ผู้เรียนอย่างน้อย 50–100 รายเพื่อให้ได้การทำนายที่เสถียร
  • การละเลยการเปลี่ยนแปลงแนวคิด: การนำ Online Bagging ไปใช้กับสตรีมที่มีการเปลี่ยนแปลงโดยไม่มีการตรวจจับการเปลี่ยนแปลงจะนำไปสู่การเสื่อมถอยของความแม่นยำอย่างเงียบๆ
  • การเปรียบเทียบความแม่นยำบนชุดข้อมูลมาตรฐานแบบคงที่กับวิธีการแบบ batch และสรุปว่า Online Bagging ด้อยกว่า — การเปรียบเทียบที่ถูกต้องคือความแม่นยำต่ออินสแตนซ์ที่เห็นบนชุดข้อมูลสตรีม
  • การใช้ผู้เรียนพื้นฐานที่ไม่ใช่แบบเพิ่มพูนอย่างแท้จริง (เช่น ต้นไม้แบบ batch ที่ฝึกใหม่) ซึ่งจะทำให้เสียข้อได้เปรียบด้านหน่วยความจำและความเร็วของกรอบการทำงานแบบออนไลน์

คำถามที่พบบ่อย

ทำไมต้องใช้ Poisson(1) โดยเฉพาะ?

การแจกแจงแบบปัวซงที่มีค่าเฉลี่ยเท่ากับ 1 จะประมาณจำนวนครั้งที่การสังเกตปรากฏในตัวอย่าง bootstrap ขนาด n เมื่อ n เข้าใกล้อนันต์ การใช้ Poisson(1) ต่ออินสแตนซ์ต่อผู้เรียนเป็นการจำลองพฤติกรรมขีดจำกัดนี้ได้อย่างแม่นยำ ทำให้การประมาณการแบบออนไลน์มีความสมเหตุสมผลทางทฤษฎี

Online Bagging แตกต่างจาก Adaptive Random Forest อย่างไร?

Adaptive Random Forest (Gomes et al., 2017) เป็นส่วนขยายของ Online Bagging โดยการเพิ่มการสุ่มตัวอย่างคุณลักษณะแบบสุ่ม (random feature subsampling) ที่แต่ละจุดแยก (split) (เช่นเดียวกับ Random Forest แบบ batch) และการรวมตัวตรวจจับการเปลี่ยนแปลงต่อต้นไม้ (per-tree drift detectors) ที่จะรีเซ็ตผู้เรียนแต่ละรายเมื่อตรวจพบการเปลี่ยนแปลงแนวคิด Online Bagging เป็นพื้นฐานที่เรียบง่ายกว่า Adaptive Random Forest เป็นกลุ่มผู้เรียนแบบสตรีมที่ทันสมัยที่สุดซึ่งสร้างขึ้นบนพื้นฐานนี้

ควรใช้ผู้เรียนพื้นฐานใด?

ตัวเลือกที่พบบ่อยที่สุดคือ Hoeffding Tree (หรือเรียกว่า VFDT) ซึ่งเป็นต้นไม้ตัดสินใจแบบเพิ่มพูนที่เป็นแบบฉบับ มันใช้ Hoeffding bounds เพื่อตัดสินใจว่าเมื่อใดที่มีข้อมูลเพียงพอที่โหนดหนึ่งๆ จะทำการแยก (split) ซึ่งทำให้ต้นไม้สามารถอัปเดตได้โดยไม่ต้องจัดเก็บอินสแตนซ์ก่อนหน้า

ต้องใช้ผู้เรียนพื้นฐานกี่ราย?

การประเมินเชิงประจักษ์ในกรอบการทำงาน MOA แนะนำให้ใช้ผู้เรียนพื้นฐาน 50–100 รายสำหรับประสิทธิภาพของกลุ่มผู้เรียนที่เสถียรในงานสตรีมส่วนใหญ่ ผู้เรียนจำนวนน้อยลงจะลดต้นทุนการคำนวณ แต่จะเพิ่มความแปรปรวนของการทำนาย โดยเฉพาะอย่างยิ่งในช่วงต้นของสตรีม

ควรประเมินตัวจำแนกประเภท Online Bagging อย่างไร?

ใช้การประเมินแบบ prequential: สำหรับแต่ละอินสแตนซ์ที่เข้ามา ให้ทำนายป้ายกำกับ (label) ของอินสแตนซ์นั้นก่อน จากนั้นจึงอัปเดตโมเดล ความแม่นยำจะคำนวณเป็นค่าเฉลี่ยสะสมของการทำนายที่ถูกต้อง วิธีนี้จะหลีกเลี่ยงความเอนเอียงจากการมองไปข้างหน้า (look-ahead bias) และสะท้อนเงื่อนไขการใช้งานจริง

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Oza, N. C., & Russell, S. (2001). Online bagging and boosting. In Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics (AISTATS 2001), pp. 105–112.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว
  2. Bifet, A., Holmes, G., Kirkby, R., & Pfahringer, B. (2010). MOA: Massive Online Analysis. Journal of Machine Learning Research, 11, 1601–1604.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว