AdaBoost Algorithm

5 min readSep 28, 2019

Introduction

AdaBoost หรือ Adaptive Boosting เป็น sequential ensemble method ที่มีการ combine weak learner หลายๆตัวเข้าด้วยกัน แล้วสร้างเป็น strong learner ทำให้ performance ของ final prediction เพิ่มขึ้น

แนวคิดหลักคือการ reweighting ซึ่งจะให้ความสำคัญกับ data point ที่ misclassified เพื่อให้มีโอกาสที่จะถูก classify ในรอบถัดไป โดยจะมีการปรับเพิ่ม weight ของ data point ที่ misclassified และปรับลด weight ของ data point ที่ correctly classified แล้วนำ data points เหล่านี้ไป train และสร้าง weak learner ตัวใหม่ ขั้นตอนเหล่านี้จะทำแบบ sequential และจะมีการปรับค่า weight ในทุกๆรอบ

Concept

Figure 1 : Visualization of AdaBoost Algorithm

เพื่อให้เข้าใจ concept ของการทำ AdaBoost เรามาดูรูปตัวอย่างใน Figure 1 เป้าหมายคือเราจะสร้าง classifier รูปแบบ binary classification สำหรับการแยกสีออกเป็น 2 กลุ่ม คือ สีน้ำเงิน และสีแดง เนื่องจาก AdaBoost เป็น sequential ensemble method หรือการ combine weak learner หลายๆตัว ให้ได้เป็น strong learner โดยในแต่ละรอบของการสร้าง weak learner จะมีการปรับ weight ของ data points ที่นำมา train ดังนั้นจะขออธิบายในแต่ละ iteration ว่า ข้อมูลมีการปรับ weight อย่างไร

Iteration 1

เริ่มต้นจะ assign ให้ data points มี weight เท่ากันทุกตัว หลังจากนั้นจะสร้าง decision stump (decision tree with depth 1) ที่แสดงด้วยเส้นประตามรูป และทำการหาค่า weight ของทุก data point สำหรับใช้ในรอบถัดไป โดยจะทำการเพิ่ม weight สำหรับ misclassified data point และทำการลด weight ในส่วนที่ correctly classified
จากรูปจะเห็นว่า ด้านบนเส้นประมี data points สีน้ำเงิน 2 จุดที่ classify ผิด และด้านล่างเส้นประ จะมี data point สีแดง 1 จุดที่ classify ผิด โดย data points เหล่านี้จะถูกเพิ่ม weight สำหรับการ สร้าง classifier ในรอบถัดไป

Iteration 2

จะเห็นว่า data point สีน้ำเงินและสีแดงที่ถูก classify ผิดในรอบที่แล้ว จะมีขนาดใหญ่ขึ้น (เพิ่ม weight)
ในรอบนี้ weak classifier มีการแบ่ง data point สีน้ำเงิน ผิด 2 จุด ดังนั้นจะมีเพิ่ม weight ใน 2 จุดนี้

ไล่ทำ iteration ไปเรื่อยๆ จนสุดท้ายได้ final classifier ซึ่งมาจาก combination of weak classifiers

Algorithm

หลังจากอธิบาย concept ของ AdaBoost ไปแล้ว เรามาลงรายละเอียดสำหรับสูตรที่ใช้ในการคำนวนกันดีกว่า

Figure 2 แสดงขั้นตอนและการคำนวณใน AdaBoost algorithm เพื่อที่จะให้เข้าใจได้ง่ายจะขอแยกอธิบายทีละส่วน

Algorithm จะนำข้อมูล input (𝑥_1,𝑦_1),…,(𝑥_m,𝑦_m) เข้ามาเป็น training set โดยที่

𝑥_i คือ ข้อมูลที่อยู่ใน some domain หรือ instance space X
𝑦_i คือ label ที่อยู่ใน set Y โดยเรา assume ว่า Y = {-1,+1} (binary classification)

Initialize weight โดยเริ่มต้นให้ทุก data point มีค่า weight เท่ากันหมดคือ D_1(i) = 1/m

m คือ จำนวน data point ทั้งหมด

สร้าง weak learner/hypothesis ในแต่ละรอบ (𝑡 = 1,…,T) โดยแต่ละรอบจะมีการเพิ่ม weight ของ data point ที่ incorrectly classified เพื่อที่จะบังคับให้ weak learner เรียนรู้ตัวที่ classify ผิด

ทำการสร้าง weak learner จากข้อมูลทุก data point โดยใช้ decision stump (decision tree with depth 1)

ทำการเลือก weak learner ที่มี weighted error ต่ำที่สุด จาก decision stump ที่สร้างขึ้นหลายๆต้น โดย weighted error คำนวนจากการทำ summation ของ weight ของ data point ทุกตัวที่ weak learner classify ผิด

โดย I(h_t(x_i) ≠ y_i) แปลความหมายได้ว่า ถ้า classifier ไม่เท่ากับ actual value จะมีค่าเป็น 1 แต่ในทางกลับกันจะมีค่าเป็น 0

คำนวน voting power ของ weak learner ใน รอบนั้นๆ เพื่อนำไปใส่ในสมการตอนสุดท้าย

Figure 3 : Relationship between alpha and error rate

จาก Figure 3 เราสามารถสรุปความสัมพันธ์ของ voting power (alpha) กับ error rate หลักๆได้ 3 ข้อ

Voting power ของ classifier h_t จะเพิ่มขึ้นแบบ exponential เมื่อ error rate เข้าใกล้ 0 (α > 0 if ε <= 0.5)
Classifier h_t ที่มี error rate เท่ากับ 0.5 จะส่งผลให้ voting power มีค่าเป็น 0 ( เหมือนกับ random guessing predict ) เราจะ ignore classifier นี้ใน final classifier
Voting power ของ classifier h_t จะเพิ่มขึ้นแบบ exponential ในทิศ negative เมื่อ error rate เข้าใกล้ 1 โดย classifier จะมี voting power เป็นลบเมื่อ error rate มีค่ามากกว่า 0.5

Update ค่า weight ของแต่ละ data point ในขั้นตอนนี้ เราสามารถแบ่งประเภทของการ update weight ได้ 2 แบบคือ

เราสามารถใช้ exponential graph เพื่อดูความสัมพันธ์ของตัวแปร x และ ค่า exp(x)

จาก Figure 4 ถ้า x มีค่ามากกว่า 0 จะทำให้ exp(x) มีค่ามากกว่า 1 และในทางตรงกันข้าม ถ้า x มีค่าน้อยกว่า 0 (ติดลบ) จะทำให้ exp(x) มีค่าน้อยกว่า 1 (เป็นเศษส่วน)

ในส่วนของ normalization factor นั้น หลักการคือ เอาค่า weight ที่คำนวนได้ใหม่มาบวกกันทั้งหมด และนำไปเป็นตัวหารของ weight ในแต่ละ data points เพื่อให้ผลรวมของ weight ในรอบถัดไปมีค่าเท่ากับ 1

ตัวอย่างการหา normalization factor เราวัดน้ำหนักของคน 3 คนโดย คนที่ 1 หนัก 70 kg คนที่ 2 หนัก 80 kg คนที่ 3 หนัก 50 kg

normalization factor คือ 70+80+50 = 200
normalized weights ของคนที่ 1 คือ 70÷200 = 0.35 คนที่ 2 คือ 80÷200 = 0.40 คนที่ 3 คือ 50÷200 = 0.25
โดยถ้าบวก normalized weights ทั้งหมดจะมีค่าเท่ากับ 1

เราจะทำการ repeat process นี้ตั้งแต่ train weak learner จนถึงการ update weight ตั้งแต่ t = 1 ไปจนถึง t = T หรือ จนกระทั่ง error rate มากกว่า 0.5

ในขั้นตอนสุดท้ายเราจะคำนวน output classifier โดยนำ classifier คูณกับ voting power ในแต่ละรอบ มาทำ summation แล้วเอาแค่ sign ว่าเป็น + หรือ -

Limitation

AdaBoost algorithm สามารถใช้ได้กับทั้ง classification and regression problem สิ่งที่ได้อธิบายไปแล้วเป็น classification problem ยังไม่ได้พูดถึงขั้นตอนในการทำในรูปแบบ regression

และในส่วนของ classification problem ในบทความนี้จะเป็นแบบ binary classification จะยังไม่ได้พูดถึง multi-classification

ดังนั้นหากมีจำนวนผู้อ่านสนใจในเรื่องที่ผมยังไม่ได้กล่าวถึงเป็นจำนวนมาก ผมจะไปหาข้อมูลเพิ่มเติมมาสรุปให้ในบทถัดไป

AdaBoost Algorithm

Introduction

Concept

Algorithm

Limitation

References

Written by Sirawich Jaichuen