روش‌های آنسامبل در یادگیری ماشین: از بگینگ و بوستینگ تا XGBoost

در پروژه‌های واقعی یادگیری ماشین، رسیدن به دقت بالا با یک مدل منفرد دشوار است. یک درخت تصمیم ساده به‌سرعت دچار بیش‌برازش می‌شود و مدل‌های خطی هم پیچیدگی داده‌های جدولی را تاب نمی‌آورند. روش‌های آنسامبل (Ensemble Methods) با ادغام هوشمندانه‌ی چند مدل ضعیف، سیستمی قوی می‌سازند که خطاهای اعضای خود را خنثی می‌کند.

این روش‌ها شالوده‌ی اصلی سامانه‌های عملیاتی هوش مصنوعی و راه‌حل برتر در داده‌های جدولی هستند. در این درس، سازوکار بگینگ (کاهش واریانس)، بوستینگ (کاهش بایاس) و استکینگ را بررسی می‌کنید و الگوریتم‌های پرکاربردی مثل AdaBoost و Gradient Boosting را از صفر پیاده‌سازی خواهید کرد.

پیاده‌سازی‌ها و کدهای این درس کاملاً متکی به پایتون استاندارد و محاسبات سبک CPU هستند؛ بنابراین بدون نیاز به زیرساخت‌های ابری گران‌قیمت یا GPUهای اختصاصی، به‌سادگی روی سیستم شخصی قابل اجرا خواهند بود.

گروهی از یادگیرنده‌های ضعیف، اگر به‌درستی ترکیب شوند، به یک یادگیرنده‌ی قوی تبدیل می‌شوند. این یک استعاره نیست؛ یک قضیه‌ی ریاضی است.

اهداف یادگیری

• پیاده‌سازی AdaBoost و گرادیان بوستینگ (gradient boosting) از صفر و توضیح چگونگی کاهش ترتیبی بایاس (bias) به‌کمک بوستینگ
• ساخت یک آنسامبل بگینگ (bagging) و نمایش کاهش واریانس از طریق میانگین‌گیری از مدل‌های ناهمبسته، بدون افزایش محسوس بایاس
• مقایسه‌ی بگینگ، بوستینگ و استکینگ (stacking) از نظر مؤلفه‌ای از خطا که هر روش هدف قرار می‌دهد
• ارزیابی تنوع آنسامبل و تبیین چرایی بهبود دقت رأی‌گیری اکثریت با افزایش یادگیرنده‌های ضعیفِ مستقل

صورت مسئله

یک درخت تصمیم تکی سریع آموزش می‌بیند و تفسیر آن آسان است، اما دچار بیش‌برازش (overfitting) می‌شود. یک مدل خطی ساده هم روی مرزهای پیچیده دچار کم‌برازش (underfitting) خواهد شد. می‌توانید روزها وقت بگذارید تا معماری یک مدل بی‌نقص را طراحی کنید، یا این‌که چند مدل نه‌چندان بی‌عیب را کنار هم بگذارید و به نتیجه‌ای برسید که از تک‌تک آن‌ها بهتر کار کند.

روش‌های آنسامبل (ensemble methods) دقیقاً همین کار را می‌کنند. این روش‌ها مطمئن‌ترین تکنیک برای بردن مسابقات کگل روی داده‌های جدولی (tabular data) هستند، به بیشتر سیستم‌های یادگیری ماشین در محیط پروداکشن نیرو می‌بخشند و تعادل بایاس-واریانس (bias-variance tradeoff) را در عمل به تصویر می‌کشند. بگینگ واریانس را کاهش می‌دهد؛ بوستینگ بایاس را پایین می‌آورد؛ استکینگ هم یاد می‌گیرد در هر ورودی، به کدام مدل اعتماد کند.

مفاهیم پایه

چرا آنسامبل‌ها کار می‌کنند؟

فرض کنید $N$ کلاسیفایر مستقل دارید که دقت هر کدام $p > 0.5$ است. دقت رأی‌گیری اکثریت (majority vote) از این رابطه به دست می‌آید:

$$P(\text{majority correct}) = \sum_{k > N/2} \binom{N}{k} p^k (1-p)^{N-k}$$

برای 21 کلاسیفایر که دقت هر کدام 60% است، دقت رأی‌گیری اکثریت حدود 74% خواهد بود. با 101 کلاسیفایر، این دقت به 84% می‌رسد. وقتی مدل‌ها اشتباهات متفاوتی مرتکب شوند، خطاهایشان همدیگر را خنثی می‌کنند.

پیش‌شرط کلیدی این ماجرا تنوع است. اگر همه‌ی مدل‌ها خطاهای مشابهی داشته باشند، ترکیب آن‌ها دردی را دوا نمی‌کند. آنسامبل‌ها با ایجاد تنوع میان مدل‌ها به کارایی می‌رسند؛ آن هم از مسیرهای زیر:

• زیرمجموعه‌های متفاوتی از داده‌های آموزش (بگینگ)
• زیرمجموعه‌های متفاوتی از ویژگی‌ها (جنگل‌های تصادفی)
• اصلاح ترتیبی خطاها (بوستینگ)
• خانواده‌های متفاوتی از مدل‌ها (استکینگ)

بگینگ (Bootstrap Aggregating)

بگینگ با آموزش هر مدل روی یک نمونه‌ی بوت‌استرپ (bootstrap sample) از داده‌های آموزشی، تنوع می‌سازد.

یک نمونه‌ی بوت‌استرپ به‌صورت باجایگذاری از داده‌های اصلی و دقیقاً هم‌اندازه‌ی آن‌ها برداشته می‌شود. حدود 63.2% از نمونه‌های یکتا در هر بوت‌استرپ حضور دارند. 36.8% باقی‌مانده (نمونه‌های خارج از کیسه یا out-of-bag) یک مجموعه‌ی اعتبارسنجی رایگان در اختیارتان می‌گذارند.

بگینگ بدون افزایش چشمگیر بایاس، واریانس را کم می‌کند. تک‌تک درخت‌ها روی نمونه‌ی بوت‌استرپ اختصاصی خود بیش‌برازش می‌کنند، اما ازآنجاکه این بیش‌برازش در هر درخت متفاوت است، میانگین‌گیری نویز را خنثی خواهد کرد.

جنگل‌های تصادفی (Random Forests) همان بگینگ هستند اما با یک چاشنی اضافه: در هر شکست (split)، تنها یک زیرمجموعه‌ی تصادفی از ویژگی‌ها در نظر گرفته می‌شود. این کار تنوع میان درخت‌ها را دوچندان می‌کند. تعداد معمول ویژگی‌های کاندید، sqrt(n_features) برای کلاسیفیکیشن و n_features / 3 برای رگرسیون است.

بوستینگ (اصلاح ترتیبی خطا)

بوستینگ مدل‌ها را پی‌درپی و پشت‌سرهم آموزش می‌دهد. هر مدل جدید تمرکز خود را روی نمونه‌هایی می‌گذارد که مدل‌های قبلی در پیش‌بینی آن‌ها اشتباه کرده‌اند.

بوستینگ بایاس را کاهش می‌دهد. هر مدل جدید، خطاهای سیستماتیک آنسامبل را تا آن مرحله تصحیح می‌کند. پیش‌بینی نهایی حاصل جمع وزن‌دار همه‌ی مدل‌هاست؛ به‌طوری‌که مدل‌های بهتر، وزن بالاتری دریافت می‌کنند.

بهای این مزیت: اجرای دورهای بیش از حد در بوستینگ می‌تواند به بیش‌برازش منجر شود، زیرا مدل مدام برای یادگیری نمونه‌های دشوارتر تلاش می‌کند؛ نمونه‌هایی که بعضی از آن‌ها ممکن است صرفاً نویز باشند.

AdaBoost

الگوریتم AdaBoost (کوتاه‌شده‌ی Adaptive Boosting) نخستین الگوریتم بوستینگ کاربردی بود. این روش با هر یادگیرنده‌ی پایه‌ای کار می‌کند، اما معمولاً از استامپ تصمیم (decision stump یا درخت‌های با عمق 1) استفاده می‌شود.

مراحل الگوریتم:

1. Initialize sample weights: w_i = 1/N for all i

2. For t = 1 to T:
   a. Train weak learner h_t on weighted data
   b. Compute weighted error:
      err_t = sum(w_i * I(h_t(x_i) != y_i)) / sum(w_i)
   c. Compute model weight:
      alpha_t = 0.5 * ln((1 - err_t) / err_t)
   d. Update sample weights:
      w_i = w_i * exp(-alpha_t * y_i * h_t(x_i))
   e. Normalize weights to sum to 1

3. Final prediction: H(x) = sign(sum(alpha_t * h_t(x)))

مدل‌هایی با خطای کمتر، آلفای بالاتری می‌گیرند. به نمونه‌های نادرست دسته‌بندی‌شده هم وزن بیشتری تخصیص می‌یابد تا مدل بعدی تمام توجهش را روی آن‌ها بگذارد.

گرادیان بوستینگ

گرادیان بوستینگ ایده‌ی بوستینگ را به هر تابع زیان (loss) دلخواهی تعمیم می‌دهد. به‌جای وزن‌دهی مجدد به نمونه‌ها، هر مدل جدید روی باقیمانده‌ها (residuals یا همان منفی گرادیان تابع زیانِ) آنسامبل فعلی فیت می‌شود.

1. Initialize: F_0(x) = argmin_c sum(L(y_i, c))

2. For t = 1 to T:
   a. Compute pseudo-residuals:
      r_i = -dL(y_i, F_{t-1}(x_i)) / dF_{t-1}(x_i)
   b. Fit a tree h_t to the residuals r_i
   c. Find optimal step size:
      gamma_t = argmin_gamma sum(L(y_i, F_{t-1}(x_i) + gamma * h_t(x_i)))
   d. Update:
      F_t(x) = F_{t-1}(x) + learning_rate * gamma_t * h_t(x)

3. Final prediction: F_T(x)

برای تابع زیان مربعات خطا، شبه‌باقیمانده‌ها دقیقاً همان باقیمانده‌های واقعی هستند: $r_i = y_i - F_{t-1}(x_i)$. یعنی هر درخت عیناً روی خطاهای آنسامبل قبلی فیت می‌شود.

نرخ یادگیری (learning rate یا shrinkage) تعیین می‌کند هر درخت چه میزان در پیش‌بینی نهایی سهم داشته باشد. نرخ‌های یادگیری کوچک‌تر به درخت‌های بیشتری نیاز دارند، اما قدرت تعمیم بالاتری به دست می‌دهند. مقادیر معمول بین 0.01 تا 0.3 است.

XGBoost: چرا روی داده‌های جدولی فرمانروایی می‌کند؟

الگوریتم XGBoost (کوتاه‌شده‌ی eXtreme Gradient Boosting) همان گرادیان بوستینگ است اما همراه با بهینه‌سازی‌های مهندسی که آن را فوق‌العاده سریع، دقیق و در برابر بیش‌برازش مقاوم می‌سازد:

• تابع هدف منظم‌سازی‌شده (Regularized objective): اعمال جریمه‌های L1 و L2 روی وزن برگ‌ها مانع از بیش‌ازحد مطمئن شدن درخت‌ها می‌شود
• تقریب مرتبه دوم (Second-order approximation): استفاده‌ی هم‌زمان از مشتق‌های اول و دوم تابع زیان، تصمیم‌گیری‌های بهتری برای شکست گره‌ها فراهم می‌آورد
• شکست‌های آگاه به تنک بودن (Sparsity-aware splits): مدیریت خودکار داده‌های گم‌شده با یادگیری بهترین مسیر برای داده‌های مفقود در هر شکست
• زیرنمونه‌گیری ستونی (Column subsampling): مشابه جنگل‌های تصادفی، در هر شکست ویژگی‌ها را به‌صورت تصادفی انتخاب می‌کند تا تنوع افزایش یابد
• طرح چندک وزن‌دار (Weighted quantile sketch): یافتن کارآمد نقاط شکست برای ویژگی‌های پیوسته روی داده‌های توزیع‌شده
• ساختار بلوکی آگاه به کَش (Cache-aware block structure): چیدمان حافظه متناسب با خطوط کَش CPU بهینه‌سازی شده است

برای داده‌های جدولی، XGBoost (و جانشین آن LightGBM) مرتباً شبکه‌های عصبی را پشت سر می‌گذارند. این برتری به این زودی‌ها تغییر نخواهد کرد. اگر داده‌هایتان در قالب سطری-ستونی یک جدول جای می‌گیرند، بی‌معطلی کار را با گرادیان بوستینگ آغاز کنید.

استکینگ (فرایادگیری)

استکینگ از پیش‌بینی‌های چند مدل پایه به‌عنوان ویژگی‌های ورودی برای یک فرایادگیرنده (meta-learner) استفاده می‌کند.

فرایادگیرنده تشخیص می‌دهد برای کدام ورودی‌ها به کدام مدل پایه تکیه کند. اگر جنگل تصادفی در نواحی مشخصی عملکرد بهتری دارد و SVM در نواحی دیگری می‌درخشد، فرایادگیرنده یاد می‌گیرد ورودی‌ها را متناسب با همین نقاط قوت ارجاع دهد.

برای جلوگیری از نشت داده (Data Leakage)، پیش‌بینی‌های مدل پایه حتماً باید با اعتبارسنجی متقاطع روی داده‌های آموزشی تولید شوند. هیچ‌وقت مدل‌های پایه را روی همان داده‌هایی که ویژگی‌های فرا را با آن‌ها می‌سازید آموزش ندهید.

رأی‌گیری

ساده‌ترین نوع آنسامبل؛ ترکیب مستقیم پیش‌بینی‌ها:

• رأی‌گیری سخت (Hard voting): رأی اکثریت روی برچسب کلاس‌ها.
• رأی‌گیری نرم (Soft voting): میانگین‌گیری از احتمالات پیش‌بینی‌شده و انتخاب کلاسی با بالاترین میانگین احتمال. این حالت معمولاً نتیجه‌ی بهتری دارد، چون از میزان اطمینان مدل‌ها هم استفاده می‌کند.

پیاده‌سازی

گام 1: استامپ تصمیم (یادگیرنده‌ی پایه)

کد موجود در فایل code/ensembles.py همه‌چیز را از صفر پیاده کرده است. کار را با یک استامپ تصمیم شروع می‌کنیم: درختی که فقط یک شکست دارد.

class DecisionStump:
    def __init__(self):
        self.feature_idx = None
        self.threshold = None
        self.polarity = 1
        self.alpha = None

    def fit(self, X, y, weights):
        n_samples, n_features = X.shape
        best_error = float("inf")

        for f in range(n_features):
            thresholds = np.unique(X[:, f])
            for thresh in thresholds:
                for polarity in [1, -1]:
                    pred = np.ones(n_samples)
                    pred[polarity * X[:, f] < polarity * thresh] = -1
                    error = np.sum(weights[pred != y])
                    if error < best_error:
                        best_error = error
                        self.feature_idx = f
                        self.threshold = thresh
                        self.polarity = polarity

    def predict(self, X):
        n = X.shape[0]
        pred = np.ones(n)
        idx = self.polarity * X[:, self.feature_idx] < self.polarity * self.threshold
        pred[idx] = -1
        return pred

گام 2: پیاده‌سازی AdaBoost از صفر

class AdaBoostScratch:
    def __init__(self, n_estimators=50):
        self.n_estimators = n_estimators
        self.stumps = []
        self.alphas = []

    def fit(self, X, y):
        n = X.shape[0]
        weights = np.full(n, 1 / n)

        for _ in range(self.n_estimators):
            stump = DecisionStump()
            stump.fit(X, y, weights)
            pred = stump.predict(X)

            err = np.sum(weights[pred != y])
            err = np.clip(err, 1e-10, 1 - 1e-10)

            alpha = 0.5 * np.log((1 - err) / err)
            weights *= np.exp(-alpha * y * pred)
            weights /= weights.sum()

            stump.alpha = alpha
            self.stumps.append(stump)
            self.alphas.append(alpha)

    def predict(self, X):
        total = sum(a * s.predict(X) for a, s in zip(self.alphas, self.stumps))
        return np.sign(total)

گام 3: پیاده‌سازی گرادیان بوستینگ از صفر

class GradientBoostingScratch:
    def __init__(self, n_estimators=100, learning_rate=0.1, max_depth=3):
        self.n_estimators = n_estimators
        self.lr = learning_rate
        self.max_depth = max_depth
        self.trees = []
        self.initial_pred = None

    def fit(self, X, y):
        self.initial_pred = np.mean(y)
        current_pred = np.full(len(y), self.initial_pred)

        for _ in range(self.n_estimators):
            residuals = y - current_pred
            tree = SimpleRegressionTree(max_depth=self.max_depth)
            tree.fit(X, residuals)
            update = tree.predict(X)
            current_pred += self.lr * update
            self.trees.append(tree)

    def predict(self, X):
        pred = np.full(X.shape[0], self.initial_pred)
        for tree in self.trees:
            pred += self.lr * tree.predict(X)
        return pred

گام 4: مقایسه با sklearn

در این بخش تأیید می‌کنیم که پیاده‌سازی‌های صفر تا صدی ما دقتی هم‌تراز با AdaBoostClassifier و GradientBoostingClassifier در کتابخانه‌ی sklearn ارائه می‌دهند و سپس همه‌ی روش‌ها را روبه‌روی هم مقایسه می‌کنیم.

کاربرد عملی

چه زمانی از کدام روش استفاده کنیم؟

استک پروداکشن برای داده‌های جدولی

برای اغلب مسائل پیش‌بینی روی داده‌های جدولی، ترتیب آزمایش‌ها بهتر است به این صورت باشد:

1. LightGBM یا XGBoost با پارامترهای پیش‌فرض
2. تیونینگ پارامترهای n_estimators، learning_rate، max_depth و min_child_weight
3. اگر به آن 0.5% دقت نهایی نیاز دارید، ساخت یک آنسامبل استکینگ متشکل از 3 تا 5 مدل متنوع
4. استفاده‌ی مداوم از اعتبارسنجی متقاطع در سراسر کار

روی داده‌های جدولی، شبکه‌های عصبی با وجود تحقیقات و تلاش‌های مستمر تقریباً همیشه ضعیف‌تر از گرادیان بوستینگ عمل می‌کنند. معماری‌هایی نظیر TabNet یا NODE گهگاه شانه به شانه‌ی آن حرکت می‌کنند، ولی به‌ندرت می‌توانند یک مدل XGBoost تنظیم‌شده را شکست دهند.

ارائه‌ی نهایی

خروجی این درس فایل outputs/prompt-ensemble-selector.md است -- پرامپتی که به انتخاب روش آنسامبل مناسب برای یک دیتاست معین کمک می‌کند. داده‌هایتان را توصیف کنید (ابعاد، انواع ویژگی‌ها، سطح نویز، تعادل کلاس‌ها) و هدفی را که دنبال می‌کنید شرح دهید. این پرامپت با یک چک‌لیست تصمیم‌گیری همراهتان می‌شود، روش مناسب را پیشنهاد می‌دهد، هایپرپارامترهای آغازی را معرفی می‌کند و درباره‌ی اشتباهات رایج هشدار می‌دهد. همچنین فایل outputs/skill-ensemble-builder.md حاوی راهنمای جامع انتخاب روش‌ها در اختیارتان قرار می‌گیرد.

تمرین‌ها

1. پیاده‌سازی AdaBoost را به‌شکلی تغییر دهید که دقت آموزش را بعد از هر دور بسنجد. نمودار دقت بر حسب تعداد تخمین‌زننده‌ها (estimators) را رسم کنید. مدل چه زمانی همگرا می‌شود؟

2. با افزودن زیرنمونه‌گیری تصادفی از ویژگی‌ها به درخت رگرسیون، یک جنگل تصادفی از صفر پیاده‌سازی کنید. 100 درخت را با پارامتر max_features=sqrt(n_features) آموزش دهید و میانگین پیش‌بینی‌ها را بگیرید. میزان کاهش واریانس را با یک تک‌درخت بسنجید.

3. در پیاده‌سازی گرادیان بوستینگ، قابلیت توقف زودهنگام (early stopping) را اضافه کنید: تابع زیانِ اعتبارسنجی را بعد از هر راند زیر نظر بگیرید و اگر در 10 راند متوالی بهبودی حاصل نشد، کار را متوقف کنید. مدل در واقعیت به چند درخت نیاز دارد؟

4. یک آنسامبل استکینگ بسازید که از سه مدل پایه (رگرسیون لجستیک، درخت تصمیم، k-نزدیک‌ترین همسایه) و یک فرایادگیرنده‌ی رگرسیون لجستیک تشکیل شده باشد. برای تولید فراویژگی‌ها از اعتبارسنجی متقاطع 5-fold استفاده کنید. عملکرد کل سیستم را با هر کدام از مدل‌های پایه به‌تنهایی مقایسه کنید.

5. مدل XGBoost را با هایپرپارامترهای پیش‌فرض روی همان دیتاست اجرا کنید. دقت آن را با گرادیان بوستینگی که خودتان پیاده کرده‌اید بسنجید. زمان اجرای هر دو را ثبت کنید. تفاوت سرعت چقدر است؟

اصطلاحات کلیدی

برای مطالعه‌ی بیشتر

• Schapire & Freund: Boosting: Foundations and Algorithms -- کتابی به قلم خالقان AdaBoost
• Friedman: Greedy Function Approximation: A Gradient Boosting Machine (2001) -- مقاله‌ی اصلی معرفی گرادیان بوستینگ
• Chen & Guestrin: XGBoost (2016) -- مقاله‌ی معرفی XGBoost
• Wolpert: Stacked Generalization (1992) -- مقاله‌ی بنیادین استکینگ
• scikit-learn Ensemble Methods -- مرجع کاربردی در مستندات scikit-learn