লিনিয়ার রিগ্রেশন ও লজিস্টিক মডেল থেকে সাপোর্ট ভেক্টর মেশিন পর্যন্ত প্রায় প্রতিটি ক্লাসিক্যাল মেশিন লার্নিং সমস্যা মূলত একটি অপ্টিমাইজেশন বা অবমূল্যায়ন সমস্যা। যখন লক্ষ্য লস ফাংশনটি উত্তল বা কনভেক্স (Convex) হয়, তখন স্থানীয় ফাঁদ (Local Minima), স্যাডল পয়েন্ট এবং বিভ্রান্তিকর মালভূমির জটিলতা উবে যায়। বহু-মাত্রিক উত্তল জ্যামিতিতে যেকোনো স্থানীয় ন্যূনতম মানই হলো পরম বৈশ্বিক ন্যূনতম মান (Global Minimum), এবং অ্যালগরিদমের গতি নির্ধারিত হয় কঠোর গাণিতিক নিয়মে।
১. উত্তল সেট ও ফাংশনের জ্যামিতি
একটি সেট $mathcal{C} subseteq mathbb{R}^d$-কে উত্তল (Convex) বলা হয় যদি সেটের যেকোনো দুটি বিন্দু $x, y in mathcal{C}$-এর সংযোগকারী সরলরেখাংশ সম্পূর্ণভাবে সেটের ভেতরে অবস্থান করে:
$$theta x + (1 – theta) y in mathcal{C} quad forall theta in [0, 1]$$
একটি ফাংশন $f(x)$ উত্তল হবে যদি তার এপিগ্রাফ (ফাংশনের গ্রাফের ওপরের অংশ) একটি উত্তল সেট হয়। ডিফারেনশিয়েবল ফাংশনের ক্ষেত্রে এর অর্থ হলো—ফাংশনের যেকোনো বিন্দুতে অঙ্কিত স্পর্শক বা ফার্স্ট-অর্ডার টেলর সিরিজ সর্বদা মূল ফাংশনের নিচে অবস্থান করে:
$$f(y) ge f(x) + nabla f(x)^T (y – x)$$
২. লিপশিৎস মসৃণতা ও স্ট্রং কনভেক্সিটি
অপ্টিমাইজেশন অ্যালগরিদম কত দ্রুত লক্ষ্যে পৌঁছাবে তা পরিমাপ করতে ফাংশনের বক্রতাকে দুটি মানদণ্ডে বিভক্ত করা হয়:
- $L$-লিপশিৎস মসৃণতা (Lipschitz Smoothness): গ্রেডিয়েন্টের পরিবর্তনের গতি সীমাবদ্ধ। এর ফলে ফাংশনটি যেকোনো বিন্দুতে একটি নির্দিষ্ট প্যারাবোলয়েড বা দ্বিঘাত বাটির ($L$) নিচে আবদ্ধ থাকে:
$$f(y) le f(x) + nabla f(x)^T (y – x) + frac{L}{2} |y – x|^2$$
- $mu$-স্ট্রং কনভেক্সিটি (Strong Convexity): ফাংশনটি কেবল উত্তল নয়, বরং এটি কমপক্ষে $mu$ বক্রতা বিশিষ্ট একটি দ্বিঘাত বাটির চেয়ে দ্রুত বৃদ্ধি পায়:
$$f(y) ge f(x) + nabla f(x)^T (y – x) + frac{mu}{2} |y – x|^2$$
এটি প্রমাণ করে যে ফাংশনের একটিই অনন্য গ্লোবাল মিনিমাম $w^*$ আছে এবং মিনিমামের বাইরে গ্রেডিয়েন্ট কখনোই শূন্য হতে পারে না।
৩. গ্রেডিয়েন্ট ডিসেন্টের রূপান্তর সূত্র
স্ট্যান্ডার্ড গ্রেডিয়েন্ট ডিসেন্ট প্রতি ধাপে লার্নিং রেট $eta$ অনুযায়ী নেগেটিভ গ্রেডিয়েন্টের দিকে অগ্রসর হয়:
$$w_{t+1} = w_t – eta nabla f(w_t)$$
গাণিতিক বিশ্লেষণ থেকে দুটি ভিন্ন গতির রূপান্তর পাওয়া যায়:
- সাধারণ উত্তল ও মসৃণ ফাংশনে: ত্রুটি হ্রাস পায় সাব-লিনিয়ার $mathcal{O}(1/T)$ হারে:
$$f(w_T) – f(w^*) le frac{L |w_0 – w^*|^2}{2T}$$
- স্ট্রং কনভেক্স ও মসৃণ ফাংশনে: দূরত্ব হ্রাস পায় জ্যামিতিক প্রগমনে দ্রুত গতিতে (Linear Convergence):
$$|w_T – w^*|^2 le left( frac{kappa – 1}{kappa + 1} right)^{2T} |w_0 – w^*|^2$$
৪. কন্ডিশন নম্বর $kappa$ ও আঁকাবাঁকা গতি
হেসিয়ান ম্যাট্রিক্সের বৃহত্তম ও ক্ষুদ্রতম আইগেনভ্যালুর অনুপাত হলো কন্ডিশন নম্বর ($kappa = L / mu$)।
- যখন $kappa approx 1$, তখন লেভেল কার্ভগুলো বৃত্তাকার হয় এবং গ্রেডিয়েন্ট সরাসরি কেন্দ্রের দিকে নির্দেশ করে, ফলে রূপান্তর হয় চোখের পলকে।
- যখন $kappa gg 1$, তখন লেভেল কার্ভগুলো সরু দীর্ঘ উপবৃত্তাকার গিরিখাত তৈরি করে। গ্রেডিয়েন্ট সর্বনিম্ন বিন্দুর দিকে না গিয়ে খাতের দুই দেয়ালে এলোমেলোভাবে আছড়ে পড়ে (Zig-zagging), যার ফলে অ্যালগরিদমের গতি অত্যন্ত ধীর হয়ে যায়।
৫. সাব-গ্রেডিয়েন্ট ক্যালকুলাস
ল্যাসোর $L_1$ রেগুলারাইজেশন বা এসভিএম-এর হিঞ্জ লসের মতো ফাংশনগুলো কোণায় ডিফারেনশিয়েবল নয়। এই সমস্যা সমাধানে ব্যবহৃত হয় সাব-গ্রেডিয়েন্ট (Subgradient) ধারণা:
$$partial f(x) = {g in mathbb{R}^d : f(y) ge f(x) + g^T (y – x) quad forall y}$$
কোণার বিন্দুতে একটি স্পর্শকের বদলে সম্ভাব্য বহু স্পর্শকের একটি সেট তৈরি হয়। যেকোনো একটি বৈধ সাব-গ্রেডিয়েন্ট $g_t$ অনুসরণ করে সাব-গ্রেডিয়েন্ট ডিসেন্ট $mathcal{O}(1/sqrt{T})$ হারে সফলভাবে বৈশ্বিক অনুকূল মানে পৌঁছাতে সক্ষম হয়।
