১৯৮৮ সালে মাইকেল কার্নস এবং লেসলি ভ্যালিয়ান্ট একটি মৌলিক দার্শনিক প্রশ্ন তুলেছিলেন: এমন কিছু দুর্বল অনুমানকারী (Weak Learners)—যারা মুদ্রা টসের চেয়ে মাত্র সামান্য একটু ভালো কাজ করে ($text{Error} < 1/2 – gamma$)—তাদের কি সম্মিলিতভাবে যুক্ত করে যেকোনো কাঙ্ক্ষিত উচ্চ-মানের শক্তিশালী মডেলে রূপান্তর করা সম্ভব? ১৯৯০ সালে রবার্ট শ্যাপায়ার প্রমাণ করেন যে হ্যাঁ, এটি তাত্ত্বিকভাবে সত্য। জন্ম হয় বুস্টিং (Boosting) ধারণার। পরবর্তীতে জেরোম ফ্রিডম্যান বুস্টিংকে ফাংশনাল স্পেসে গ্রেডিয়েন্ট ডিসেন্টের রূপ দেন, যা আধুনিক ডেটা সায়েন্সের অবিসংবাদিত ভিত্তি তৈরি করে।
১. অ্যাডাবুস্ট (AdaBoost) অ্যালগরিদম
১৯৯৫ সালে ইয়োভ ফ্রয়েন্ড এবং রবার্ট শ্যাপায়ার তৈরি করেন অ্যাডাবুস্ট (Adaptive Boosting)। এর মূল কৌশল হলো ভুল করা ডেটা পয়েন্টের ওপর ক্রমান্বয়ে গুরুত্ব বৃদ্ধি করা:
- শুরুতে সকল ডেটা পয়েন্টের ওজন সমান থাকে ($D_1(i) = 1/n$)।
- প্রতি ধাপে একটি দুর্বল ডিসিশন ট্রি $h_t$ তৈরি করা হয় এবং তার ওজনযুক্ত ভুল $epsilon_t$ গণনা করা হয়।
- মডেলটির নির্ভুলতার ওপর ভিত্তি করে তার ভোটিং ক্ষমতা $alpha_t$ নির্ধারিত হয়:
$$alpha_t = frac{1}{2} ln left( frac{1 – epsilon_t}{epsilon_t} right)$$
- যেসব ডেটায় মডেলটি ভুল করেছে, পরবর্তী ধাপের জন্য তাদের গুরুত্ব সূচকীয় হারে বাড়িয়ে দেওয়া হয়:
$$D_{t+1}(i) propto D_t(i) exp(-alpha_t y_i h_t(x_i))$$
চূড়ান্ত সিদ্ধান্ত গৃহীত হয় সকল দুর্বল মডেলের ওজনযুক্ত ভোটের মাধ্যমে। ফ্রয়েন্ড এবং শ্যাপায়ার প্রমাণ করেন যে ট্রেনিং এরর প্রতি ধাপে সূচকীয় গতিতে শূন্যের দিকে ধাবিত হয়।
২. ওভারফিটিংয়ের বিরুদ্ধে মার্জিনের প্রাচীর
অ্যাডাবুস্টের প্রথমদিকের পরীক্ষায় গবেষকরা এক অবিশ্বাস্য রহস্যের মুখোমুখি হন: ট্রেনিং এরর শূন্য হয়ে যাওয়ার পরেও যদি মডেলকে শত শত অতিরিক্ত রাউন্ড প্রশিক্ষণ দেওয়া হতো, তবুও মডেলটি ওভারফিট করত না; বরং টেস্ট এরর আরও কমতে থাকত! ১৯৯৮ সালে শ্যাপায়ার ও বার্টলেট মার্জিন তত্ত্ব (Margin Theory) দিয়ে এই ধাঁধার সমাধান করেন।
তাঁরা দেখান যে ট্রেনিং এরর শূন্য হওয়াটাই শেষ কথা নয়। পরবর্তী রাউন্ডগুলোতে অ্যাডাবুস্ট সবচেয়ে কঠিন ডেটা পয়েন্টগুলোকে সিদ্ধান্ত রেখা থেকে অনেক দূরে ঠেলে দেয়, যার ফলে ডেটাগুলোর জ্যামিতিক মার্জিন বহুগুণ বৃদ্ধি পায়। এই বর্ধিত মার্জিন মডেলটিকে নয়েজের বিরুদ্ধে এক অভেদ্য সুরক্ষা দেয়।
৩. ফাংশনাল স্পেসে গ্রেডিয়েন্ট বুস্টিং
২০০১ সালে জেরোম ফ্রিডম্যান বুস্টিংকে এক নতুন দিগন্তে নিয়ে যান: গ্রেডিয়েন্ট বুস্টিং (Gradient Boosting)। প্যারামিটারের সাপেক্ষে গ্রেডিয়েন্ট না নিয়ে তিনি সরাসরি মডেলের পূর্বাভাসের সাপেক্ষে লস ফাংশনের নেগেটিভ গ্রেডিয়েন্ট গণনা করেন, যাকে বলা হয় সিউডো-রেসিডুয়াল (Pseudo-Residuals):
$$r_{im} = -left[ frac{partial L(y_i, F(x_i))}{partial F(x_i)} right]_{F=F_{m-1}}$$
প্রতি ধাপে নতুন একটি ট্রি তৈরি করা হয় যা পূর্ববর্তী মডেলের এই অবশিষ্ট ভুলের (Residuals) পূর্বাভাস দিতে চেষ্টা করে। এর ফলে যেকোনো ডিফারেনশিয়েবল লস ফাংশনে (MSE, Logistic, Huber) অনায়াসে বুস্টিং প্রয়োগ করা সম্ভব হয়।
৪. এক্সজিবিউস্ট (XGBoost): দ্বিতীয় ক্রমের জ্যামিতি
২০১৬ সালে তিয়ানকি চেন উদ্ভাবন করেন এক্সজিবিউস্ট (XGBoost)। তিনি কেবল প্রথম গ্রেডিয়েন্টেই থামেননি, বরং টেলর সিরিজের সাহায্যে হেসিয়ান বা দ্বিতীয় বক্রতা ($h_i = partial^2 L$) যুক্ত করেন:
$$mathcal{L} approx sum left[ g_i f_t(x_i) + frac{1}{2} h_i f_t^2(x_i) right] + Omega(f_t)$$
এর ফলে ট্রির প্রতিটি পাতার সর্বোত্তম ওজন এক নিখুঁত অ্যালজেব্রিক সূত্রে নির্ণয় করা সম্ভব হয়:
$$w_j^* = -frac{sum g_i}{sum h_i + lambda}$$
প্রথম গ্রেডিয়েন্টের গতি এবং দ্বিতীয় হেসিয়ানের বক্রতার এই সমন্বয় এক্সজিবিউস্টকে পরিণত করেছে আজকের মেশিন লার্নিং প্রতিযোগিতার সর্বাধিক বিজয়ী ইঞ্জিনে।
