লেসলি ভ্যালিয়ান্টের সসীম পিএসি মডেল তাত্ত্বিকভাবে অনবদ্য হলেও বাস্তব মেশিন লার্নিং কাজ করে অবিচ্ছিন্ন এবং অসীম হাইপোথিসিস স্পেসে: যেমন $mathbb{R}^d$ স্পেসের হাইপারপ্লেন, সাপোর্ট ভেক্টর মেশিন বা অসীম প্যারামিটার সমন্বিত নিউরাল নেটওয়ার্ক। অসীম হাইপোথিসিস স্পেসের ক্ষেত্রে $|mathcal{H}| = infty$, ফলে সসীম সূত্রের $frac{1}{epsilon} ln |mathcal{H}|$ অসীমে বিস্ফোরিত হয়। অবিচ্ছিন্ন ফাংশন স্পেসের প্রকৃত প্রকাশক্ষমতা পরিমাপের জন্য সোভিয়েত গণিতবিদ ভ্লাদিমির ভ্যাপনিক এবং আলেক্সি চেরভোনেনকিস উদ্ভাবন করেন ভিসি ডাইমেনশন তত্ত্ব (VC Dimension Theory)।
১. শ্যাটারিং (Shattering)-এর ধারণা
ধরা যাক $mathcal{H}$ হলো একটি বাইনারি ক্লাসিফায়ার ক্লাস $h: mathcal{X} to {-1, +1}$। $mathcal{X}$ স্পেসের $m$ সংখ্যক বিন্দুর একটি সেট $C = {x_1, dots, x_m}$-এর ওপর $mathcal{H}$ সম্ভাব্য যতগুলো লেবেল বিন্যাস তৈরি করতে পারে তা হলো:
$$mathcal{H}_{|C} = {(h(x_1), dots, h(x_m)) : h in mathcal{H}} subseteq {-1, +1}^m$$
যদি হাইপোথিসিস ক্লাস $mathcal{H}$ এই $m$ সংখ্যক বিন্দুর সম্ভাব্য সকল $2^m$ ধরণের ধনাত্মক ও ঋণাত্মক লেবেলিং তৈরি করতে সক্ষম হয়, তবে বলা হয় যে $mathcal{H}$ ওই বিন্দু সেটটিকে শ্যাটার (Shatter) করেছে:
$$|mathcal{H}_{|C}| = 2^m$$
কোনো সেটকে শ্যাটার করার অর্থ হলো—মডেলটির ওই বিন্দুগুলোর ওপর সম্পূর্ণ নিয়ন্ত্রণ রয়েছে; যেকোনো কম্বিনেশন সে জ্যামিতিকভাবে আলাদা করতে পারে।
২. ভিসি ডাইমেনশনের সংজ্ঞা
একটি হাইপোথিসিস ক্লাস $mathcal{H}$-এর ভিসি ডাইমেনশন ($d_{text{VC}}$) হলো সর্বোচ্চ যতগুলো বিন্দুর সেটকে $mathcal{H}$ শ্যাটার করতে পারে তার আকার:
$$d_{text{VC}}(mathcal{H}) = max {m in mathbb{N} : exists C subset mathcal{X}, |C| = m, |mathcal{H}_{|C}| = 2^m}$$
যদি ক্লাসটি যেকোনো আকারের বিন্দু সেটকে শ্যাটার করতে পারে, তবে তার ভিসি ডাইমেনশন অসীম।
উদাহরণ: $mathbb{R}^d$-তে রৈখিক হাইপারপ্লেন
দ্বিমাত্রিক তলে ($d = 2$) সরলরেখার মাধ্যমে ক্লাসিফিকেশন বিবেচনা করি: $h(x) = text{sign}(w cdot x + b)$।
- দ্বিমাত্রিক তলে যেকোনো ৩টি অসমরেখ বিন্দুকে একটি সরলরেখা দিয়ে সম্ভাব্য সকল $2^3 = 8$ উপায়ে পৃথক করা সম্ভব। সুতরাং $d_{text{VC}} ge 3$।
- কিন্তু র্যাডনের উপপাদ্য (Radon’s Theorem) অনুযায়ী, তলের যেকোনো ৪টি বিন্দুকে সরলরেখা দিয়ে শ্যাটার করা অসম্ভব (এক্সওআর সমস্যা—যেখানে বিপরীত কোণায় একই রঙের বিন্দু থাকলে একটি সরলরেখা তা আলাদা করতে পারে না)।
সাধারণভাবে, $d$-মাত্রিক স্পেসে রৈখিক হাইপারপ্লেনের ভিসি ডাইমেনশন হলো:
$$d_{text{VC}}(text{Hyperplanes in } mathbb{R}^d) = d + 1$$
৩. সাউয়ারের লেমা: সূচকীয় থেকে বহুপদী রূপান্তর
গ্রোথ ফাংশন $Pi_{mathcal{H}}(m)$ পরিমাপ করে $m$ সংখ্যক বিন্দুতে মডেলটি সর্বোচ্চ কতগুলো লেবেল তৈরি করতে পারে। $m le d_{text{VC}}$ পর্যন্ত এটি সূচকীয় গতিতে বৃদ্ধি পায়: $Pi_{mathcal{H}}(m) = 2^m$। কিন্তু যখনই বিন্দুর সংখ্যা ভিসি সীমা অতিক্রম করে ($m > d_{text{VC}}$), তখনই এক অবিশ্বাস্য রূপান্তর ঘটে:
সাউয়ার-শেলাহ লেমা (Sauer’s Lemma): যদি $d_{text{VC}}(mathcal{H}) = d < infty$ হয়, তবে $m ge d$-এর জন্য:
$$Pi_{mathcal{H}}(m) le sum_{i=0}^d binom{m}{i} le left(frac{em}{d}right)^d$$
এই সূত্রটি প্রমাণ করে যে ভিসি সীমা অতিক্রম করার পর হাইপোথিসিসের সক্ষমতা হঠাৎ সূচকীয় ($2^m$) থেকে বহুপদীতে ($m^d$) নেমে আসে। এই আকস্মিক সীমাবদ্ধতাই মডেলকে অন্ধের মতো নয়েজ মুখস্থ করা থেকে বিরত রেখে সাধারণ জ্ঞান শিখতে বাধ্য করে।
৪. মৌলিক ভিসি জেনারেলাইজেশন বাউন্ড
সাউয়ারের লেমা প্রয়োগ করে ভ্যাপনিক ও চেরভোনেনকিস আধুনিক পরিসংখ্যানিক শিখনের সবচেয়ে গুরুত্বপূর্ণ বাউন্ড প্রমাণ করেন:
$$R(h) le R_{text{emp}}(h) + sqrt{frac{8 d_{text{VC}} ln(2en / d_{text{VC}}) + 8 ln(4/delta)}{n}}$$
এই সমীকরণটি দেখায় যে নতুন তথ্যে মডেলের আসল ভুল ট্রেনিং ভুলের সাথে একটি ক্যাপাসিটি পেনাল্টির যোগফল দ্বারা নির্ধারিত হয়, যা $mathcal{O}left(sqrt{frac{d_{text{VC}}}{n}}right)$ হারে হ্রাস পায়। সবচেয়ে বিস্ময়কর বিষয় হলো—মডেল কতটা ভালো জেনারেলাইজ করবে তা ইনপুট স্পেসের ডাইমেনশনের ওপর নয়, বরং মডেলের নিজস্ব ভিসি ডাইমেনশনের ওপর নির্ভর করে।
