Chapter 6 of 16

Search Algorithms

From exhaustive grid search to intelligent Bayesian optimization

45 min read

Created ৬ আগ, ২০২৬

ভূমিকা

Hyperparameter কী, কোনগুলো গুরুত্বপূর্ণ, আর performance কীভাবে মাপতে হয় — এতক্ষণে সেটা জানা হয়ে গেছে। এবার আসল প্রশ্ন: একটা search space আর একটা expensive objective function হাতে থাকলে, পরের বার কোন configuration try করবেন সেটা কীভাবে ঠিক করবেন? এই chapter-এর প্রতিটা algorithm আসলে একই প্রশ্নের উত্তর দেয় — এখন পর্যন্ত যা শেখা হয়েছে তার ভিত্তিতে পরের configuration কী হওয়া উচিত? পার্থক্য শুধু এইখানে — কেউ কিছুই মনে রাখে না (grid আর random search), আর কেউ পুরো search space-এর একটা probabilistic মডেল বানিয়ে ফেলে (Bayesian optimization)।

Manual Search

সবার আগে আসে manual search — একজন practitioner একটা configuration বেছে নেন, evaluate করেন, ফলাফল দেখে বুঝে-শুনে পরের configuration ঠিক করেন।

Manual search: শক্তি, দুর্বলতা, আর প্রস্তাবিত ব্যবহার
	Manual Search
শক্তি	Domain expertise সরাসরি কাজে লাগানো যায়; আলাদা implementation লাগে না; সংখ্যায় প্রকাশ করা কঠিন এমন গুণগত বিচারও (যেমন 'এই configuration deploy করার জন্য খুব ধীর') বিবেচনায় নেওয়া যায়।
দুর্বলতা	২-৩টার বেশি hyperparameter-এ scale করে না; reproducible নয়; cognitive bias-এর শিকার হয় (প্রথম ভালো ফলাফলের ওপর বেশি ভরসা); unattended চালানো যায় না।
সেরা ব্যবহার	কোনো automated algorithm-এর হাতে তুলে দেওয়ার আগে model-এর sanity-check করা আর search space সংকীর্ণ করা — কোনো automated algorithm-এর বিকল্প হিসেবে নয়।

Grid Search

ধরুন একটা রেসিপি টেস্ট করছেন — ৩টা oven temperature আর ৪টা baking time-এর প্রতিটা combination try করে দেখছেন, মানে ১২টা রুটি। Grid search ঠিক এটাই করে — প্রতিটা hyperparameter-এর একটা fixed discrete value set থাকে, আর তাদের সব combination exhaustively evaluate করা হয়। এই exhaustiveness-ই এর শক্তি আর একই সাথে দুর্বলতা — একটা তৃতীয় dimension (ধরুন ২ রকম yeast) যোগ করলেই সংখ্যাটা দ্বিগুণ হয়ে যায়, যদিও হয়তো শুধু baking time-টাই আসলে গুরুত্বপূর্ণ ছিল।

$d$ টা hyperparameter $\lambda_1, \dots, \lambda_d$ -এর প্রতিটার discrete candidate set $V_1, \dots, V_d$ হলে, grid search $V_1 \times V_2 \times \cdots \times V_d$ -এর প্রতিটা বিন্দু evaluate করে।

Grid Search-এর Complexity

|\text{Grid}| = \prod_{i=1}^{d} |V_i|

scikit-learn-এ GridSearchCV-তে param_grid-এ প্রতিটা hyperparameter-এর জন্য একটা তালিকা দিয়ে দিলেই সব combination cross-validation দিয়ে evaluate হয়ে যায়, শেষে best_params_-এ সেরা configuration আর cv_results_-এ কতগুলো configuration evaluate হলো তার হিসাব পাওয়া যায়।

Grid search-এর মূল সমস্যা

আপনার ৬টা hyperparameter-এর মধ্যে যদি মাত্র ২টাই আসলে গুরুত্বপূর্ণ হয়, তাহলেও grid search বাকি ৪টার প্রতিটা combination evaluate করবে। বেশিরভাগ HPO সমস্যায় এই typical structure-টা (কিছু hyperparameter অন্যদের চেয়ে অনেক বেশি গুরুত্বপূর্ণ) কাজে লাগিয়ে random search প্রায় সবসময়ই বেশি efficient হয়।

Random Search

Random search প্রতিটা hyperparameter তার distribution থেকে independently randomly sample করে — নিয়মমাফিক enumerate করার বদলে ভাগ্যের ওপর ছেড়ে দেয়। শুনতে কম systematic মনে হলেও এর একটা বড় সুবিধা আছে — প্রতিটা trial-ই সব hyperparameter সম্পর্কে নতুন তথ্য দেয়।

কেন Random Search, Grid Search-কে হারায়

Bergstra আর Bengio-র ২০১২ সালের বিখ্যাত গবেষণা দেখিয়েছিল, hyperparameter-এর একটা ছোট অংশই যদি আসলে গুরুত্বপূর্ণ হয় (যেটা প্রায়ই সত্যি), তাহলে random search grid search-এর চেয়ে exponentially দ্রুত ভালো configuration খুঁজে পায়। $d$ টা hyperparameter-এর মধ্যে $k$ টা গুরুত্বপূর্ণ হলে grid search প্রতিটা trial-এর $(d - k)$ টা dimension অকারণে "নষ্ট" করে, যেখানে random search সেই গুরুত্বপূর্ণ dimension-গুলোর independent coverage দেয়।

ভালো Configuration পাওয়ার সম্ভাবনা

T

scikit-learn-এ RandomizedSearchCV-তে param_distributions-এ প্রতিটা hyperparameter-এর জন্য একটা distribution দিয়ে দেওয়া হয় (যেমন randint(50, 500) বা loguniform), আর n_iter দিয়ে কতগুলো random configuration try করা হবে সেটা ঠিক করা হয়।

Continuous distribution ব্যবহার করুন, তালিকা নয়

Random search-এর আসল শক্তি আসে continuous distribution থেকে sample করা থেকে (যেমন learning rate-এর জন্য loguniform(1e-4, 1e-1)) কতগুলো নির্দিষ্ট value-এর তালিকা থেকে নয়। ৫টা value-এর একটা তালিকা কার্যত একটা ছোট গ্রিড হয়ে যায়; continuous sampling পুরো range-এর কভারেজ দেয়।

Bayesian Optimization

Grid আর random search-এর কোনো স্মৃতি নেই — আগের evaluation থেকে কিছু শেখে না, পরের configuration বাছাই করার সময়। Bayesian optimization এইখানে ভিন্ন — এটা search space জুড়ে validation performance কীভাবে পাল্টায় তার একটা probabilistic model (surrogate model) তৈরি করে, সেটা দিয়ে পরের সবচেয়ে সম্ভাবনাময় configuration বাছাই করে, evaluate করে, আর model আপডেট করে।

একজন ভালো ডাক্তারের কথা ভাবুন — প্রতিটা টেস্ট রিপোর্টের পর তিনি এলোমেলোভাবে পরের টেস্ট বাছাই করেন না, বরং যা এখন পর্যন্ত জানা গেছে সেটার ভিত্তিতে সবচেয়ে informative টেস্টটাই বেছে নেন। Bayesian optimization hyperparameter configuration-এর ক্ষেত্রে ঠিক এটাই করে।

Surrogate model

একটা সস্তা probabilistic model (সাধারণত Gaussian Process) যেটা search space-এর যেকোনো বিন্দুতে objective function-এর মান কী হতে পারে predict করে, uncertainty estimate-সহ।

Acquisition function

Surrogate model ব্যবহার করে candidate configuration-গুলোকে score দেয়, পরে try করা কতটা লাভজনক হতে পারে সেই অনুযায়ী।

Acquisition-এর optimization

Acquisition function যেই configuration-এ maximum হয়, সেটাই পরের বাস্তব trial।

Gaussian Process Surrogate

সবচেয়ে বেশি ব্যবহৃত surrogate model হলো Gaussian Process (GP) — এটা search space-এর প্রতিটা বিন্দুতে objective function-এর একটা Gaussian distribution (mean + variance) বসিয়ে দেয়। আগে evaluate করা বিন্দুতে variance খুব কম (মান জানা আছে); অজানা অঞ্চলে variance বেশি (uncertainty বেশি)।

Gaussian Process Prediction

\lambda

Acquisition Function

Acquisition function GP-র prediction-কে "এই configuration-টা পরে try করা কতটা ভালো?" — এই স্কোরে রূপান্তর করে, exploitation (predicted-good বিন্দু try করা) আর exploration (uncertain অঞ্চল try করা)-এর মধ্যে ভারসাম্য রেখে।

Bayesian optimization-এর সাধারণ acquisition function
Acquisition function	Formula	আচরণ
Expected Improvement (EI)	E[max(f(λ) − f*, 0)]	বর্তমান সেরাকে এই configuration কতটা ছাড়িয়ে যাবে তার প্রত্যাশিত পরিমাণ। বাস্তবে সবচেয়ে বেশি ব্যবহৃত acquisition function।
Upper Confidence Bound (UCB)	μ(λ) + κσ(λ)	আশাবাদী estimate: predicted mean আর κ গুণ standard deviation যোগ। κ exploration-exploitation ভারসাম্য নিয়ন্ত্রণ করে।
Probability of Improvement (PI)	P(f(λ) > f* + ε)	বর্তমান সেরাকে অন্তত ε দিয়ে হারানোর সম্ভাবনা। EI-এর চেয়ে বেশি exploitative।

Tree-Structured Parzen Estimators (TPE)

GP-ভিত্তিক Bayesian optimization উচ্চ-মাত্রিক আর conditional search space-এ (যেখানে একটা hyperparameter-এর মান আরেকটার ওপর নির্ভর করে) সমস্যায় পড়ে। TPE — যা Hyperopt আর Optuna ব্যবহার করে — এই সমস্যা সমাধান করে ভিন্নভাবে ভেবে: পুরো joint space-এ একটা GP fit করার বদলে, ভালো ফলাফল আর খারাপ ফলাফলের দিকে নিয়ে যাওয়া configuration-এর distribution আলাদা আলাদাভাবে মডেল করে। Optuna-তে trial.suggest_int, trial.suggest_float(..., log=True)-এর মতো call দিয়ে search space সংজ্ঞায়িত করে study.optimize(objective, n_trials=100) চালালেই TPE ব্যবহার হয়।

Bayesian Optimization কখন কাজে লাগে (আর কখন লাগে না)

Bayesian optimization তখনই random search-কে ছাড়িয়ে যায় যখন প্রতিটা trial expensive (মিনিট থেকে ঘণ্টা লাগে) আর hyperparameter সংখ্যা মাঝারি (২ থেকে ১৫টার মতো)। Trial যদি সস্তা হয় (কয়েক সেকেন্ড) বা dimension অনেক বেশি (৫০+), তাহলে random search প্রতি ঘণ্টার হিসেবে প্রায়ই বেশি প্রতিযোগিতামূলক।

Successive Halving আর Hyperband

Bayesian optimization একটা ভিন্ন ধরনের অপচয় সমাধান করে না — একটা স্পষ্টতই খারাপ configuration-কেও পুরো সময় ধরে train হতে দেওয়া। যদি একটা configuration-এর validation accuracy খারাপ হতেই যাচ্ছে, তাহলে সেটাকে ১০০ epoch ধরে train হতে দেওয়ার কী দরকার?

Successive Halving অনেকগুলো random configuration-কে অল্প compute বরাদ্দ দেয় (যেমন ৫ epoch), সেরাদের রেখে বাকিদের বাদ দেয়, বরাদ্দ দ্বিগুণ করে, আবার একই কাজ করে।

রাউন্ড ১

N-টা configuration-এর প্রতিটা B/N compute পায়। সবগুলো evaluate করে র‍্যাংক করা হয়।

রাউন্ড ২

সেরা N/η-টা configuration প্রতিটা ηB/N compute পায়। বেঁচে থাকাদের আবার র‍্যাংক করা হয়।

রাউন্ড ৩

সেরা N/η²-টা configuration প্রতিটা η²B/N compute পায়। একজন বিজয়ী না পাওয়া পর্যন্ত চলতে থাকে।

Hyperband ভিন্ন ভিন্ন শুরুর configuration নিয়ে একাধিক successive halving bracket চালায়, early-stopping-এর efficiency আর search space-এর কভারেজের মধ্যে ভারসাম্য রাখে। Ray Tune-এর মতো টুলে HyperBandScheduler-এ max_t (প্রতি config-এ সর্বোচ্চ training iteration) আর reduction_factor (প্রতি রাউন্ডে কতভাগ টিকে থাকবে) দিয়ে এটা কনফিগার করা হয়।

কোন Algorithm কখন

Hyperparameter search-এর জন্য algorithm বাছাইয়ের গাইড
Algorithm	কখন ব্যবহার করবেন
Grid search	Hyperparameter সংখ্যা ≤ ২ হলে, অথবা reproducibility-র জন্য একটা ছোট, আগে থেকে ঠিক করা grid-এর exhaustive coverage দরকার হলে।
Random search	বেশিরভাগ সমস্যার জন্য default choice। Trial সস্তা হলে, search space-এ dimension বেশি হলে, বা কোন hyperparameter সবচেয়ে গুরুত্বপূর্ণ তা নিশ্চিত না হলে।
Bayesian optimization (GP)	প্রতিটা trial ব্যয়বহুল হলে (মিনিট-ঘণ্টা) আর search space মাঝারি (২–১৫টা hyperparameter, সহজ, non-conditional গঠন)।
TPE (Optuna/Hyperopt)	Search space conditional বা categorical হলে, অথবা প্রতি step-এ surrogate model fit করার overhead-এর কারণে GP-based Bayesian optimization খুব ধীর হলে।
Hyperband/ASHA	Trial আগেভাগে থামানো সম্ভব হলে (যেমন validation checkpoint-সহ NN training) আর fixed compute budget-এ অনেক configuration evaluate করতে চাইলে।
BOHB	Hyperband-এর early termination আর Bayesian optimization-এর model-based proposal — দুটোই একসাথে চাইলে — neural architecture search-এর জন্য বর্তমানে state-of-the-art।

মূল বিষয়গুলো

Key Takeaways

Grid search প্রতিটা combination evaluate করে; hyperparameter সংখ্যার সাথে exponentially বাড়ে; ২-৩টার বেশি dimension-এ প্রায় কখনোই সঠিক choice নয়।
Random search গুরুত্বপূর্ণ hyperparameter-গুলোর independent coverage দেয়; একই বাজেটে প্রায়ই grid search-এর সমান বা তার চেয়ে ভালো।
Bayesian optimization objective-এর একটা surrogate model রাখে আর সেটা দিয়ে বুদ্ধিমত্তার সাথে পরের trial বেছে নেয়; trial expensive হলে সবচেয়ে বেশি কাজে লাগে।
TPE conditional আর categorical search space GP-based Bayesian optimization-এর চেয়ে ভালোভাবে সামলায়।
Hyperband আর Successive Halving খারাপ configuration আগেই বাদ দিয়ে compute-এর efficiency নাটকীয়ভাবে বাড়ায়।
BOHB model-based proposal আর early termination — দুটো একসাথে ব্যবহার করে, expensive neural network HPO-র জন্য প্রায়ই সেরা choice।

Interview Corner

Quick Check

1. Grid search বেশি systematic হওয়া সত্ত্বেও random search প্রায়ই HPO-তে ভালো ফল দেয় কেন?

2. Bayesian optimization-এ acquisition function কী, আর এটা কোন trade-off সামলায়?