গ্রেডিয়েন্ট বুস্টিং

**গ্রেডিয়েন্ট বুস্টিং** (Gradient boosting) একটি মেশিন লার্নিং কৌশল যা এটি ফাংশন স্পেসভিত্তিক একটি বুস্টিং পদ্ধতি, যেখানে প্রচলিত বুস্টিংয়ের মতো শুধু অবশিষ্ট ত্রুটি নয়, বরং লস ফাংশনের গ্রেডিয়েন্ট ব্যবহার করে মডেল উন্নত করা হয়। এটি দুর্বল পূর্বাভাস মডেলগুলোর (যেগুলো এককভাবে খুব নির্ভুল নয়) একাধিক মডেল মিলিয়ে একটি সমন্বিত মডেল (ensemble) তৈরি করে। এই দুর্বল মডেলগুলি সাধারণত সহজ সিদ্ধান্ত গাছ হয়ে থাকে। যখন দুর্বল শিক্ষার্থী হিসেবে একটি সিদ্ধান্ত গাছ ব্যবহার করা হয়, তখন ফলাফলপ্রাপ্ত অ্যালগরিদমকে গ্রেডিয়েন্ট-বুস্টেড ট্রিস (gradient-boosted trees) বলা হয়; এটি সাধারণত র্যান্ডম ফরেস্ট-এর চেয়ে ভালো কর্মক্ষমতা প্রদর্শন করে। অন্যান্য বুস্টিং পদ্ধতির মতো, গ্রেডিয়েন্ট-বুস্টেড ট্রিস মডেলটি ধাপে ধাপে তৈরি করা হয়, কিন্তু এটি একটি ইচ্ছামত ডিফারেনশিয়েভযোগ্য লস ফাংশনের (loss function) অপ্টিমাইজেশন অনুমতি দিয়ে অন্যান্য পদ্ধতিগুলোকে আরও সাধারণ রূপ দেয়।

## ইতিহাস

গ্রেডিয়েন্ট বুস্টিং-এর ধারণার উৎপত্তি হয়েছিল লিও ব্রেইম্যানের পর্যবেক্ষণ থেকে, যেখানে তিনি দেখান যে বুস্টিংকে একটি উপযুক্ত কস্ট ফাংশনের (cost function) উপর অপ্টিমাইজেশন অ্যালগরিদম হিসেবে ব্যাখ্যা করা যেতে পারে। এরপর জেরোম এইচ. ফ্রিডম্যানের মাধ্যমে সুনির্দিষ্ট রিগ্রেশন গ্রেডিয়েন্ট বুস্টিং অ্যালগরিদম তৈরি করা হয় (১৯৯৯ সালে এবং পরে ২০০১ সালে)। একই সময়ে, লিউ ম্যাসন, জোনাথন ব্যাক্সটার, পিটার বার্টলেট এবং মার্কাস ফ্রিন আরও সাধারণ কার্যগত গ্রেডিয়েন্ট বুস্টিং (functional gradient boosting) দৃষ্টিভঙ্গি উপস্থাপন করেন।

পরবর্তীতে উল্লিখিত দুটি গবেষণাপত্রে বুস্টিং অ্যালগরিদমকে ফাংশন স্পেসে ধাপে ধাপে গ্রেডিয়েন্ট ডিসেন্ট প্রয়োগের মাধ্যমে অ্যালগরিদম হিসেবে ব্যাখ্যা করা হয়। অর্থাৎ, এই অ্যালগরিদমগুলি একটি ফাংশন স্পেসের ওপর কস্ট ফাংশনকে অপ্টিমাইজ করে, যেখানে পুনরাবৃত্তির প্রতিটি ধাপে একটি ফাংশন (দুর্বল হাইপোথিসিস) নির্বাচন করা হয় যা নেগেটিভ গ্রেডিয়েন্ট দিকে নির্দেশ করে। বুস্টিং-এর এই ফাংশন স্পেস ভিত্তিক গ্রেডিয়েন্ট দৃষ্টিভঙ্গি পরবর্তীতে রিগ্রেশন এবং ক্লাসিফিকেশন ছাড়াও মেশিন লার্নিং ও পরিসংখ্যানের বিভিন্ন ক্ষেত্রে বুস্টিং অ্যালগরিদমের বিকাশ ঘটিয়েছে।

## প্রাসঙ্গিক ব্যাখ্যা

(এই অংশটি চেং লি-এর লেখা একটি সহজ ব্যাখ্যা অনুসরণ করে রচিত।)

অন্যান্য বুস্টিং পদ্ধতির মতোই, গ্রেডিয়েন্ট বুস্টিং-ও দুর্বল "লার্নার"গুলিকে পুনরাবৃত্তির মাধ্যমে একত্রিত করে একটি শক্তিশালী লার্নার তৈরি করে। ধারণাটি সবচেয়ে সহজভাবে বোঝা যায় সর্বনিম্ন-বর্গ রিগ্রেশন এর উদাহরণ দিয়ে।   এখানে মডেলটি F-কে প্রশিক্ষণ দেওয়া হয় যাতে এটি \hat{y} = F(x) ইনপুট থেকে সঠিক পূর্বাভাস দিতে পারে। এর জন্য মিন স্কোয়ার্ড এরর (mean squared error) \tfrac{1}{n}\sum_i(\hat{y}_i - y_i)^2-কে ন্যূনতম করা হয়। এখানে  i  প্রশিক্ষণ সেটের (training set) প্রতিটি ডেটা বিন্দু নির্দেশ করে, প্রশিক্ষণ সেটের মোট আকার  n  এবং আউটপুট ভেরিয়েবল y-এর প্রকৃত মান নিম্নরূপে সংজ্ঞায়িত:

· \hat{y}_i =  ভবিষ্যদ্বাণীকৃত মান F(x_i)
· y_i = প্রকৃত মান
· n =  নমুনার আকার; অর্থাৎ, y-তে থাকা পর্যবেক্ষণের সংখ্যা

যদি অ্যালগরিদমটিতে Mটি ধাপ থাকে, তবে প্রতিটি m-তম ধাপে (1 \le m \le M) ধরা যাক, আমাদের কাছে কিছু অসম্পূর্ণ মডেল F_m আছে (প্রথম দিকের m-এর জন্য, এই মডেলটি সম্ভবত সকল \hat y_i-এর মান \bar y (অর্থাৎ y-এর গড়) হিসেবে ভবিষ্যদ্বাণী করতে পারে)। F_m-কে উন্নত করার জন্য, আমাদের অ্যালগরিদমে একটি নতুন অনুমানক (estimator) h_m(x) যোগ করতে হবে। অর্থাৎ,

:
F_{m+1}(x_i) = F_m(x_i) + h_m(x_i) = y_i


বা, একইভাবে বলা যায়,

:
h_m(x_i) = y_i - F_m(x_i).


সুতরাং, গ্রেডিয়েন্ট বুস্টিং h_m-কে *[[Errors and residuals|অবশিষ্টাংশের]]* (residual) সাথে মানানসই হবে, যেখানে অবশিষ্টাংশ হল y_i - F_m(x_i)। বুস্টিং-এর অন্যান্য রূপগুলোর মতোই, প্রতিটি F_{m+1} তার পূর্ববর্তী মডেল F_m-এর ত্রুটিগুলো সংশোধন করার চেষ্টা করে। এই ধারণাটি শুধু বর্গ ত্রুটি নয়, বরং অন্যান্য লস ফাংশন এবং ক্লাসিফিকেশন ও র্যাঙ্কিং সমস্যার জন্য আরও সাধারণ রূপ দেওয়া সম্ভব। এটি লক্ষ্য করলে বোঝা যায় যে, একটি নির্দিষ্ট মডেলের জন্য অবশিষ্টাংশ h_m(x_i), মিন স্কোয়ার্ড এরর (MSE) লস ফাংশনের নেগেটিভ গ্রেডিয়েন্টের সমানুপাতিক (যেখানে গ্রেডিয়েন্ট F(x_i)-এর সাপেক্ষে নির্ণয় করা হয়):

:
L_{\rm MSE} = \frac{1}{n} \sum_{i=1}^n \left(y_i - F(x_i)\right)^2


:
- \frac{\partial L_{\rm MSE}}{\partial F(x_i)} = \frac{2}{n}(y_i - F(x_i)) = \frac{2}{n}h_m(x_i).


সুতরাং, গ্রেডিয়েন্ট বুস্টিং-কে আরও সাধারণ একটি গ্রেডিয়েন্ট ডিসেন্ট অ্যালগরিদম হিসেবে গণ্য করা যেতে পারে, যেখানে শুধু MSE নয়, বরং ভিন্ন কোনো লস ফাংশন এবং তার গ্রেডিয়েন্ট ব্যবহার করে অপ্টিমাইজেশন প্রক্রিয়া চালানো যায়।

## অ্যালগরিদম

অনেক তত্ত্বাবধানাধীন শিখন সমস্যায় একটি আউটপুট ভেরিয়েবল  এবং ইনপুট ভেরিয়েবলের একটি ভেক্টর  থাকে, যা কিছু সম্ভাব্যতাভিত্তিক বণ্টনের মাধ্যমে পরস্পরের সাথে সম্পর্কিত। লক্ষ্য হল এমন একটি ফাংশন \hat{F}(x) খুঁজে বের করা যা ইনপুট ভেরিয়েবলের মান থেকে আউটপুট ভেরিয়েবলের সর্বোত্তম অনুমান প্রদান করে। এটি করার জন্য কিছু লস ফাংশন L(y, F(x)) সংজ্ঞায়িত করা হয় এবং এর প্রত্যাশিত মান (expectation) ন্যূনতম করা হয়:

: \hat{F} = \underset{F}{\operatorname{argmin}} \, \mathbb{E}_{x,y}[L(y, F(x))]. 

গ্রেডিয়েন্ট বুস্টিং পদ্ধতি ধরে নেয় যে  বাস্তব-মানের (real-valued)। এটি \hat{F}(x)-এর একটি অনুমান নির্ভর মান খোঁজে, যা \mathcal{H} শ্রেণীভুক্ত কিছু বেস (বা দুর্বল) লার্নার ফাংশন h_m (x)-এর Mটি ফাংশনের একটি ওজনযুক্ত সমষ্টি হিসেবে প্রকাশ পায়:

: \hat{F}(x) = \sum_{m=1}^M \gamma_m h_m(x) + \text{const}, 

এখানে \gamma_m হলো m-তম ধাপের ওজন। সাধারণত আমাদের কাছে একটি প্রশিক্ষণ সেট (training set) থাকে: \{ (x_1,y_1), \dots , (x_n,y_n) \} , যেখানে -এর মান এবং সংশ্লিষ্ট -এর মান জানা আছে। অভিজ্ঞতাভিত্তিক ঝুঁকি ন্যূনতমকরণ (empirical risk minimization) নীতি অনুসারে, এই পদ্ধতি এমন একটি অনুমান \hat{F}(x) খোঁজার চেষ্টা করে যা প্রশিক্ষণ সেটের ওপর লস ফাংশনের গড় মান (অর্থাৎ অভিজ্ঞতাভিত্তিক ঝুঁকি) ন্যূনতম করে। এটি একটি ধ্রুবক ফাংশন F_0(x) দিয়ে শুরু করে এবং ধাপে ধাপে তা গ্রিডি পদ্ধতিতে (greedy fashion) সম্প্রসারিত হয়:

:F_0(x) = \underset{h_m \in \mathcal{H}}{\arg\min} \sum_{i=1}^n {L(y_i, h_m(x_i))},
:F_m(x) = F_{m-1}(x) + \left( \underset{h_m \in \mathcal{H}}{\operatorname{arg\,min}} \left[ \sum_{i=1}^n L(y_i, F_{m-1}(x_i) + h_m(x_i)) \right] \right)(x),

যেখানে m \geq 1 এবং  h_m \in \mathcal{H}  একটি বেস লার্নার ফাংশন।

দুর্ভাগ্যবশত, যেকোনো লস ফাংশন -এর জন্য প্রতিটি ধাপে সর্বোত্তম ফাংশন h_m নির্বাচন করা সাধারণভাবে একটি গণনার দিক থেকে অত্যন্ত জটিল একটি অপ্টিমাইজেশন সমস্যা। তাই আমরা সমস্যার একটি সরলীকৃত সংস্করণে আমাদের পদ্ধতি সীমাবদ্ধ রাখি। মূল ধারণা হল এই ন্যূনতমকরণ সমস্যায় একটি *স্টিপেস্ট ডিসেন্ট* (steepest descent) ধাপ প্রয়োগ করা, যাকে *ফাংশন স্পেসে গ্রেডিয়েন্ট ডিসেন্ট*-ও বলা হয়। মূল কথা হল, F_{m-1}(x)-এর পুনরাবৃত্তির মাধ্যমে লস ফাংশনের একটি স্থানীয় ন্যূনতম মান খুঁজে বের করা। প্রকৃতপক্ষে, লস ফাংশনের সর্বোচ্চ নিম্নগামী অভিমুখ (local maximum-descent direction) হল নেগেটিভ গ্রেডিয়েন্ট। সুতরাং, অল্প পরিমাণ  \gamma  দ্বারা নিম্নলিখিতভাবে অগ্রসর হলে রৈখিক অনুমান (linear approximation) বৈধ থাকে:

: F_m(x) = F_{m-1}(x) - \gamma \sum_{i=1}^n \nabla_{F_{m-1}} L(y_i, F_{m-1}(x_i))

যেখানে \gamma > 0। ছোট \gamma-এর জন্য, এটি নিশ্চিত করে যে L(y_i, F_{m}(x_i)) \le L(y_i, F_{m-1}(x_i))।

নিচের বিষয়টি প্রমাণ করার জন্য, নিচের লক্ষ্য ফাংশনটি বিবেচনা করুন:
:  O = \sum_{i=1}^n L(y_i, F_{m-1}(x_i) + h_m(x_i)) 

স্থির বিন্দু  F_{m-1}(x_i) -এর সাপেক্ষে প্রথম ক্রম পর্যন্ত টেলর সম্প্রসারণ (Taylor expansion) করে পাই:
:  O = \sum_{i=1}^n L(y_i, F_{m-1}(x_i) + h_m(x_i)) \approx  \sum_{i=1}^n \left[ L(y_i, F_{m-1}(x_i)) + h_m(x_i) \nabla_{F_{m-1}} L(y_i, F_{m-1}(x_i)) \right] + \cdots

এখন h_m(x_i)-এর সাপেক্ষে অন্তরীকরণ করলে, দ্বিতীয় পদটির অন্তরীকরণ থেকে শুধু \nabla_{F_{m-1}}L(y_i, F_{m-1}(x_i)) পাওয়া যায়। এটি *সর্বোচ্চ ঊর্ধ্বগামী* (steepest ascent) দিক নির্দেশ করে। তাই *সর্বোচ্চ নিম্নগামী* (steepest descent) দিকে অগ্রসর হতে হলে আমাদের বিপরীত (অর্থাৎ নেগেটিভ) দিকে যেতে হবে।

তাছাড়া, আমরা \gamma-এর মানও অপ্টিমাইজ করতে পারি, যাতে লস ফাংশনটি ন্যূনতম হয়:

: \gamma_m = \underset{\gamma}{\operatorname{argmin}} \sum_{i=1}^n L(y_i, F_m(x_i)) = \underset{\gamma}{\arg\min} \sum_{i=1}^n L\left(y_i, F_{m-1}(x_i) -
\gamma \nabla_{F_{m-1}} L(y_i, F_{m-1}(x_i)) \right).

যদি আমরা ধারাবাহিক (continuous) ক্ষেত্রে বিবেচনা করি, অর্থাৎ \mathcal{H} যদি \R-এর ওপর সংজ্ঞায়িত সকল অন্তরীকরণযোগ্য ফাংশনের সেট হয়, তাহলে আমরা নিচের সমীকরণ অনুসারে মডেলটি হালনাগাদ করব:
:F_m(x) = F_{m-1}(x) - \gamma_m \sum_{i=1}^n {\nabla_{F_{m-1}} L(y_i, F_{m-1}(x_i))}
এখানে \gamma_m হল পদক্ষেপের দৈর্ঘ্য (step length), যা নিম্নরূপে সংজ্ঞায়িত:
\gamma_m = \underset{\gamma}{\arg\min} \sum_{i=1}^n L\left(y_i, F_{m-1}(x_i) - \gamma \nabla_{F_{m-1}} L(y_i, F_{m-1}(x_i)) \right).
কিন্তু বিচ্ছিন্ন (discrete) ক্ষেত্রে, অর্থাৎ যখন \mathcal{H} সেটটি সসীম হয়, আমরা -এর গ্রেডিয়েন্টের সবচেয়ে কাছাকাছি অবস্থানকারী ফাংশন -কে নির্বাচন করি। এরপর সহগ -এর মান উপরিউক্ত সমীকরণগুলোর সাহায্যে লাইন সার্চ (line search) পদ্ধতিতে নির্ণয় করা যায়। মনে রাখতে হবে, 

সিউডোকোডে, সাধারণ গ্রেডিয়েন্ট বুস্টিং পদ্ধতিটি নিম্নরূপ:

ইনপুট: প্রশিক্ষণ সেট \{(x_i, y_i)\}_{i=1}^n, একটি অন্তরীকরণযোগ্য লস ফাংশন L(y, F(x)), পুনরাবৃত্তির সংখ্যা ।

অ্যালগরিদম:

একটি ধ্রুবক মান দিয়ে মডেল শুরু কর:

#: F_0(x) = \underset{\gamma}{\arg\min} \sum_{i=1}^n L(y_i, \gamma).

 = 1 থেকে  পর্যন্ত:

*ছদ্ম-অবশিষ্টাংশ* (pseudo-residuals) গণনা কর:

##: r_{im} = -\left[\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}\right]{F(x)=F{m-1}(x)} \quad \text{for } i=1,\ldots,n.

একটি বেস লার্নার (বা দুর্বল শিক্ষার্থী, যেমন গাছ) h_m(x) ছদ্ম-অবশিষ্টাংশের সাথে খাপ খাওয়াও (fit); অর্থাৎ প্রশিক্ষণ সেট \{(x_i, r_{im})\}_{i=1}^n ব্যবহার করে সেটিকে প্রশিক্ষণ দাও।

গুণক \gamma_m নির্ণয় কর নিচের এক-মাত্রিক অপ্টিমাইজেশন সমস্যা সমাধানের মাধ্যমে:

##: \gamma_m = \underset{\gamma}{\operatorname{argmin}} \sum_{i=1}^n L\left(y_i, F_{m-1}(x_i) + \gamma h_m(x_i)\right).

মডেল হালনাগাদ কর:

##: F_m(x) = F_{m-1}(x) + \gamma_m h_m(x).

আউটপুট F_M(x).

## গ্রেডিয়েন্ট ট্রি বুস্টিং

গ্রেডিয়েন্ট বুস্টিং সাধারণত নির্দিষ্ট আকারের ডিসিশন ট্রি লার্নিং (বিশেষত CART) বেস লার্নার হিসেবে ব্যবহার করে। এই বিশেষ ক্ষেত্রটির জন্য, ফ্রিডম্যান গ্রেডিয়েন্ট বুস্টিং পদ্ধতিতে একটি পরিবর্তন প্রস্তাব করেন যা প্রতিটি বেস লার্নারের ফিটের গুণমান উন্নত করে।

*m*-তম ধাপে সাধারণ গ্রেডিয়েন্ট বুস্টিং ছদ্ম-অবশিষ্টাংশের সাথে একটি সিদ্ধান্ত গাছ h_m(x) খাপ খাওয়াবে। ধরি J_{m} হলো গাছটির পাতার সংখ্যা। গাছটি ইনপুট স্পেসকে J_{m}টি বিচ্ছিন্ন অঞ্চলে R_{1m}, \ldots, R_{J_{m}m} ভাগ করে এবং প্রতিটি অঞ্চলে একটি ধ্রুবক মান পূর্বাভাস দেয়। নির্দেশক নোটেশন (indicator notation) ব্যবহার করে, ইনপুট *x*-এর জন্য h_m(x)-এর আউটপুট নিম্নরূপে লেখা যেতে পারে:
: h_m(x) = \sum_{j=1}^{J_{m}} b_{jm} \mathbf {1}{R{jm}}(x),
যেখানে b_{jm} হল R_{jm} অঞ্চলে পূর্বাভাসকৃত মান।

তারপর b_{jm} সহগগুলিকে কিছু মান \gamma_m দ্বারা গুণ করা হয়, যা লস ফাংশনটি ন্যূনতম করার জন্য লাইন সার্চ ব্যবহার করে নির্বাচন করা হয়, এবং মডেলটি নিম্নরূপে হালনাগাদ করা হয়:

: 
F_m(x) = F_{m-1}(x) + \gamma_m h_m(x), \quad
\gamma_m = \underset{\gamma}{\operatorname{arg\,min}} \sum_{i=1}^n L(y_i, F_{m-1}(x_i) + \gamma h_m(x_i)).


ফ্রিডম্যান এই অ্যালগরিদমটি পরিবর্তন করার প্রস্তাব দেন যাতে এটি পুরো গাছের জন্য একটি মাত্র \gamma_m ব্যবহার না করে, বরং গাছের প্রতিটি অঞ্চলের জন্য পৃথক পৃথক সর্বোত্তম মান \gamma_{jm} নির্বাচন করে। তিনি পরিবর্তিত এই অ্যালগরিদমটির নাম দেন "TreeBoost"। ট্রি ফিট করার পদ্ধতি থেকে প্রাপ্ত b_{jm} সহগগুলি তখন সরাসরি বাতিল করা যায় এবং মডেল হালনাগাদের নিয়মটি নিম্নরূপ হয়:

: 
F_m(x) = F_{m-1}(x) + \sum_{j=1}^{J_{m}} \gamma_{jm} \mathbf {1}{R{jm}}(x), \quad
\gamma_{jm} = \underset{\gamma}{\operatorname{arg\,min}} \sum_{x_i \in R_{jm}} L(y_i, F_{m-1}(x_i) + \gamma).


যখন লস ফাংশন L(\cdot, \cdot) মিন স্কোয়ার্ড এরর (MSE) হয়, তখন \gamma_{jm} সহগগুলি ট্রি ফিট করার পদ্ধতি থেকে প্রাপ্ত b_{jm} সহগগুলির সাথে মিলে যায়।

### গাছের আকার

গাছের টার্মিনাল নোডের সংখ্যা J একটি প্যারামিটার যা মডেলে ভেরিয়েবলগুলির মধ্যে অনুমোদিত সর্বোচ্চ মিথস্ক্রিয়ার (interaction) মাত্রা নিয়ন্ত্রণ করে। J = 2 (ডিসিশন স্টাম্প) হলে, ভেরিয়েবলগুলির মধ্যে কোনো মিথস্ক্রিয়া অনুমোদিত নয়। J = 3 হলে মডেলটি সর্বোচ্চ দুটি ভেরিয়েবলের মধ্যে মিথস্ক্রিয়ার প্রভাব অন্তর্ভুক্ত করতে পারে, ইত্যাদি। হাতে থাকা ডেটাসেটের জন্য J-এর মান সামঞ্জস্য করা যেতে পারে।

হাস্টি এট আল. মন্তব্য করেন যে সাধারণত 4 \leq J \leq 8 বুস্টিং-এর জন্য ভালো কাজ করে এবং এই সীমার মধ্যে J-এর পছন্দের ক্ষেত্রে ফলাফলগুলি মোটামুটি অপরিবর্তনশীল। J = 2 অনেক প্রয়োগের জন্য অপর্যাপ্ত, এবং J > 10 প্রয়োজন হওয়ার সম্ভাবনা খুব কম।

## নিয়মিতকরণ

প্রশিক্ষণ সেটের সাথে খুব ঘনিষ্ঠভাবে ফিট করালে মডেলের সাধারণীকরণ ক্ষমতা (অর্থাৎ অদেখা উদাহরণের উপর কর্মক্ষমতা) হ্রাস পেতে পারে। ফিটিং প্রক্রিয়ায় সীমাবদ্ধতা আরোপ করে এই অতিমাত্রায় ফিটিং কমানোর জন্য বেশ কয়েকটি তথাকথিত নিয়মিতকরণ কৌশল ব্যবহার করা হয়।

একটি স্বাভাবিক নিয়মিতকরণ প্যারামিটার হলো গ্রেডিয়েন্ট বুস্টিং পুনরাবৃত্তির সংখ্যা *M* (অর্থাৎ বেস মডেলের সংখ্যা)। *M* বাড়ালে প্রশিক্ষণ সেটের ত্রুটি কমে, কিন্তু অতিমাত্রায় ফিটিং-এর ঝুঁকি বাড়ে। *M*-এর একটি সর্বোত্তম মান প্রায়শই একটি পৃথক বৈধতা ডেটা সেটে পূর্বাভাস ত্রুটি পর্যবেক্ষণ করে নির্বাচন করা হয়।

ট্রি বুস্টিং-এর আরেকটি নিয়মিতকরণ প্যারামিটার হলো গাছের গভীরতা। এই মান যত বেশি হবে, মডেলটির প্রশিক্ষণ ডেটাতে অতিমাত্রায় ফিট করার সম্ভাবনা তত বেশি।

### সংকোচন

গ্রেডিয়েন্ট বুস্টিং-এর একটি গুরুত্বপূর্ণ অংশ হলো সংকোচনের মাধ্যমে নিয়মিতকরণ, যা একটি পরিবর্তিত হালনাগাদ নিয়ম ব্যবহার করে:

: F_m(x) = F_{m-1}(x) + \nu \cdot \gamma_m h_m(x), \quad 0 

এখানে প্যারামিটার \nu-কে "শিখন হার" (learning rate) বলা হয়।

অভিজ্ঞতালব্ধ ফলাফলে দেখা গেছে যে ছোট শিখন হার (যেমন \nu ) ব্যবহার করলে সংকোচন ছাড়া গ্রেডিয়েন্ট বুস্টিং-এর (\nu = 1) তুলনায় মডেলের সাধারণীকরণ ক্ষমতার ক্ষেত্রে উল্লেখযোগ্য উন্নতি হয়। তবে, এর বিনিময়ে প্রশিক্ষণ এবং কোয়েরি উভয় সময়েই গণনামূলক সময় বৃদ্ধি পায়: কম শিখন হারের জন্য বেশি পুনরাবৃত্তির প্রয়োজন হয়।

### স্টোকাস্টিক গ্রেডিয়েন্ট বুস্টিং

গ্রেডিয়েন্ট বুস্টিং প্রবর্তনের অল্প সময়ের মধ্যেই, ফ্রিডম্যান ব্রেইম্যানের বুটস্ট্র্যাপ অ্যাগ্রিগেশন ("ব্যাগিং") পদ্ধতি দ্বারা অনুপ্রাণিত হয়ে অ্যালগরিদমে একটি ছোটখাটো পরিবর্তনের প্রস্তাব করেন। বিশেষ করে, তিনি প্রস্তাব করেন যে অ্যালগরিদমের প্রতিটি পুনরাবৃত্তিতে, প্রশিক্ষণ সেট থেকে এলোমেলোভাবে (প্রতিস্থাপন ব্যতীত) নেওয়া একটি উপ-নমুনার উপর বেস লার্নারটিকে ফিট করানো উচিত। ফ্রিডম্যান এই পরিবর্তনের সাথে গ্রেডিয়েন্ট বুস্টিং-এর নির্ভুলতার ক্ষেত্রে যথেষ্ট উন্নতি লক্ষ্য করেন।

উপ-নমুনার আকার হল প্রশিক্ষণ সেটের আকারের একটি ধ্রুবক ভগ্নাংশ f। যখন f = 1, অ্যালগরিদমটি সুনির্দিষ্ট (deterministic) এবং উপরে বর্ণিতটির অনুরূপ। f-এর ছোট মান অ্যালগরিদমে এলোমেলোভাব আনে এবং এক ধরণের নিয়মিতকরণ হিসেবে কাজ করে অতিমাত্রায় ফিটিং প্রতিরোধে সহায়তা করে। অ্যালগরিদমটি আরও দ্রুত হয়ে ওঠে, কারণ প্রতিটি পুনরাবৃত্তিতে ছোট ডেটাসেটের সাথে রিগ্রেশন ট্রি ফিট করতে হয়। ফ্রিডম্যান দেখতে পান যে ছোট ও মাঝারি আকারের প্রশিক্ষণ সেটের জন্য 0.5 \leq f \leq 0.8  ভালো ফলাফল দেয়। তাই, f সাধারণত 0.5 নির্ধারণ করা হয়, অর্থাৎ প্রশিক্ষণ সেটের অর্ধেক অংশ প্রতিটি বেস লার্নার তৈরিতে ব্যবহৃত হয়।

এছাড়াও, ব্যাগিং-এর মতো, উপ-নমুনায়ন পরবর্তী বেস লার্নার তৈরিতে ব্যবহৃত হয়নি এমন পর্যবেক্ষণগুলির উপর পূর্বাভাস মূল্যায়ন করে পূর্বাভাস কর্মক্ষমতা উন্নতির একটি *আউট-অফ-ব্যাগ ত্রুটি* (out-of-bag error) সংজ্ঞায়িত করতে সাহায্য করে। আউট-অফ-ব্যাগ অনুমান একটি স্বাধীন বৈধতা ডেটাসেটের প্রয়োজন এড়াতে সহায়তা করে, তবে এটি প্রায়শই প্রকৃত কর্মক্ষমতা উন্নতি এবং সর্বোত্তম পুনরাবৃত্তির সংখ্যা underestimated করে থাকে।

### পাতায় পর্যবেক্ষণের সংখ্যা

গ্রেডিয়েন্ট ট্রি বুস্টিং বাস্তবায়নগুলি প্রায়শই গাছের টার্মিনাল নোডে পর্যবেক্ষণের ন্যূনতম সংখ্যা সীমিত করেও নিয়মিতকরণ ব্যবহার করে। গাছ নির্মাণ প্রক্রিয়ায় এই সীমা আরোপ করা হয় এমন যেকোনো বিভাজন উপেক্ষা করে যা এই সংখ্যার চেয়ে কম প্রশিক্ষণ সেট উদাহরণ ধারণকারী নোড তৈরি করে।

এই সীমা আরোপ করা পাতায় পূর্বাভাসের ভেদাঙ্ক কমাতে সাহায্য করে।

### জটিলতার উপর জরিমানা

গ্রেডিয়েন্ট বুস্টেড মডেলের জন্য আরেকটি দরকারী নিয়মিতকরণ কৌশল হল এর জটিলতার উপর জরিমানা আরোপ করা। গ্রেডিয়েন্ট বুস্টেড ট্রির জন্য, মডেল জটিলতাকে গাছের পাতার সমানুপাতিক সংখ্যা হিসেবে সংজ্ঞায়িত করা যেতে পারে। লস এবং মডেল জটিলতার যৌথ অপ্টিমাইজেশন একটি পোস্ট-প্রুনিং অ্যালগরিদমের সাথে মিলে যায় যা এমন শাখাগুলি সরিয়ে দেয় যা লসকে একটি নির্দিষ্ট সীমার নিচে কমাতে ব্যর্থ হয়।

পাতার মানের উপর \ell_2 জরিমানার মতো অন্যান্য ধরণের নিয়মিতকরণও অতিমাত্রায় ফিটিং এড়াতে ব্যবহার করা যেতে পারে।

## ব্যবহার
গ্রেডিয়েন্ট বুস্টিং র‍্যাঙ্ক শেখার ক্ষেত্রে ব্যবহার করা যেতে পারে। বাণিজ্যিক ওয়েব সার্চ ইঞ্জিন Yahoo এবং Yandex তাদের মেশিন-লার্নড  র‍্যাঙ্কিং ইঞ্জিনে গ্রেডিয়েন্ট বুস্টিং-এর বিভিন্ন সংস্করণ ব্যবহার করে। উচ্চ-শক্তি পদার্থবিজ্ঞানেও ডেটা বিশ্লেষণে গ্রেডিয়েন্ট বুস্টিং ব্যবহৃত হয়। লার্জ হ্যাড্রন কলাইডারে (LHC), গ্রেডিয়েন্ট বুস্টিং ডিপ নিউরাল নেটওয়ার্কের (DNN) বিভিন্ন রূপ হিগস বোসন আবিষ্কারে ব্যবহৃত ডেটাসেটগুলিতে বিশ্লেষণের নন-মেশিন লার্নিং পদ্ধতির ফলাফল পুনরুত্পাদনে সফল হয়েছে। গ্রেডিয়েন্ট বুস্টিং ডিসিশন ট্রি পৃথিবী ও ভূতাত্ত্বিক গবেষণায়ও প্রয়োগ করা হয়েছে – যেমন বেলেপাথরের জলাধারের গুণমান মূল্যায়ন।

## নাম সমূহ

পদ্ধতিটি বিভিন্ন নামে পরিচিত। ফ্রিডম্যান তার রিগ্রেশন কৌশলটি প্রবর্তন করেন "গ্রেডিয়েন্ট বুস্টিং মেশিন" (GBM) নামে। ম্যাসন, ব্যাক্সটার এট আল. অ্যালগরিদমের সাধারণীকৃত বিমূর্ত শ্রেণিটিকে "ফাংশনাল গ্রেডিয়েন্ট বুস্টিং" বলে অভিহিত করেন। ফ্রিডম্যান এট আল. গ্রেডিয়েন্ট বুস্টেড মডেলের একটি উন্নত সংস্করণ বর্ণনা করেন "মাল্টিপল অ্যাডিটিভ রিগ্রেশন ট্রিস" (MART) নামে; এলিথ এট আল. এই পদ্ধতিটিকে "বুস্টেড রিগ্রেশন ট্রিস" (BRT) হিসেবে বর্ণনা করেন।

R-এর জন্য একটি জনপ্রিয় ওপেন-সোর্স বাস্তবায়ন একে "জেনারেলাইজড বুস্টিং মডেল" (Generalized Boosting Model) বলে ডাকে, তবে এই কাজটি সম্প্রসারিত প্যাকেজগুলি BRT নাম ব্যবহার করে। আরেকটি নাম হল ট্রিনেট (TreeNet), যা স্যালফোর্ড সিস্টেমের ড্যান স্টেইনবার্গের একটি প্রাথমিক বাণিজ্যিক বাস্তবায়নের নামানুসারে। স্টেইনবার্গ সেই গবেষকদের একজন যারা ট্রি-ভিত্তিক পদ্ধতির ব্যবহারে পথিকৃৎ।

## ফিচার গুরুত্ব ক্রমায়ন

গ্রেডিয়েন্ট বুস্টিং ফিচার গুরুত্ব ক্রমায়নের জন্য ব্যবহার করা যেতে পারে, যা সাধারণত বেস লার্নারদের গুরুত্ব ফাংশন একত্রিত করার উপর ভিত্তি করে তৈরি হয়। উদাহরণস্বরূপ, যদি এনট্রপি-ভিত্তিক সিদ্ধান্ত ট্রি ব্যবহার করে একটি গ্রেডিয়েন্ট বুস্টেড ট্রি অ্যালগরিদম তৈরি করা হয়, তাহলে একত্রিত অ্যালগরিদমটি এনট্রপির উপর ভিত্তি করেও ফিচারগুলোর গুরুত্ব ক্রমায়ন করে। তবে এই ক্ষেত্রে গুরুত্বটি সকল বেস লার্নারের উপর গড় হিসেবে নির্ণয় করা হয়।

## অসুবিধাসমূহ

বুস্টিং পদ্ধতি যদিও সিদ্ধান্ত গাছ বা লিনিয়ার রিগ্রেশনের মতো বেস লার্নারগুলোর নির্ভুলতা বাড়াতে পারে, তবে এর জন্য মূল্য দিতে হয় মডেলটির স্বচ্ছতা ও ব্যাখ্যাযোগ্যতা বিসর্জন দিয়ে।

একটি একক সিদ্ধান্ত ট্রি কীভাবে কোনো সিদ্ধান্তে পৌঁছায়, সেটি অনুসরণ করা সহজ এবং স্বয়ংসম্পূর্ণভাবে ব্যাখ্যা করা যায়—কোন শর্ত পরীক্ষা করে, কোন পথ ধরে শেষ পর্যন্ত কোন ফলে পৌঁছাল, সেটি চোখে দেখা যায়। কিন্তু যখন শত শত বা হাজার হাজার ট্রি এর সমষ্টি নিয়ে কাজ করতে হয়, তখন তাদের সিদ্ধান্তপ্রক্রিয়ার পথ অনুসরণ করা অনেকটাই অসম্ভব হয়ে ওঠে।

তবে শুধু কর্মক্ষমতা নয়, ব্যাখ্যাযোগ্যতাও যদি প্রয়োজন হয়, তাহলে কিছু মডেল সংকোচন কৌশল (model compression techniques) আছে। এগুলোর সাহায্যে একটি জটিল XGBoost মডেলকে এমন একটি "পুনর্জন্মপ্রাপ্ত" (born-again) সিদ্ধান্ত ট্রিতে রূপান্তরিত করা যায়, যা আসল মডেলের প্রায় কাছাকাছি সিদ্ধান্ত নিতে পারে, কিন্তু একটি মাত্র ট্রি হওয়ায় সহজে ব্যাখ্যা করা যায়।

আরেকটি বিষয় হলো, গ্রেডিয়েন্ট বুস্টিং বাস্তবায়ন করা তুলনামূলকভাবে কঠিন, কারণ এতে প্রচুর গণনা ও সময়ের প্রয়োজন হয়।

## আরও দেখুন
* র‍্যান্ডম ফরেস্ট
* লাইটজিবিএম
* এক্সজিবুস্ট
* ডিসিশন ট্রি লার্নিং

## তথ্যসূত্র