১৯৮৪ সালে কম্পিউটার বিজ্ঞানী লেসলি ভ্যালিয়ান্ট একটি যুগান্তকারী গবেষণাপত্র প্রকাশ করেন যা কৃত্রিম বুদ্ধিমত্তার তাত্ত্বিক ভিত্তি স্থাপন করেছিল: “A Theory of the Learnable”। ভ্যালিয়ান্ট শিখনের অস্পষ্ট অনুমানগুলোকে সরিয়ে এক সুনির্দিষ্ট, ডিস্ট্রিবিউশন-মুক্ত গাণিতিক কাঠামোর জন্ম দেন, যার নাম পিএসি শিখন (PAC Learning — Probably Approximately Correct)। প্রথমবারের মতো শিখন কেবল ট্রায়াল-অ্যান্ড-এরর বা কারিগরি কৌশল না থেকে পলিনমিয়াল নমুনা জটিলতা এবং নির্ভুলতার সুনির্দিষ্ট বিজ্ঞানে পরিণত হয়।
১. পিএসি-র দর্শন: কেন “Probably” এবং কেন “Approximately”?
যেকোনো বাস্তব শিখন প্রক্রিয়ায় দুটি অপরিবর্তনীয় সত্য বিদ্যমান:
- আনুমানিক নির্ভুলতা ($epsilon$ — Approximately Correct): যেহেতু ট্রেনিং ডেটা হলো অসীম বাস্তবতার এক ক্ষুদ্র নমুনা, তাই নতুন ডেটায় শতভাগ নির্ভুলতা ($R(h) = 0$) দাবি করা গাণিতিকভাবে অসম্ভব। অ্যালগরিদম কেবল এই নিশ্চয়তা দিতে পারে যে তার ভুল একটি ক্ষুদ্র সীমা $epsilon > 0$-এর মধ্যে থাকবে:
$$R(h) le epsilon$$
- উচ্চ সম্ভাব্যতা ($1 – delta$ — Probably): ট্রেনিং ডেটাসেট $S sim mathcal{D}^n$ দৈবভাবে সংগৃহীত হয়। তাত্ত্বিকভাবে সবসময় একটি সম্ভাবনা থাকে যে সংগৃহীত নমুনাগুলো চরম বিভ্রান্তিকর ছিল। তাই আমরা নিশ্চিত করি যে শিখন ব্যর্থ হওয়ার সম্ভাবনা $delta in (0, 1)$-এর কম থাকবে, অর্থাৎ সফলতার সম্ভাব্যতা হবে অন্তত $1 – delta$:
$$mathbb{P}_{S sim mathcal{D}^n}(R(h_S) le epsilon) ge 1 – delta$$
২. পিএসি শিখনযোগ্যতার আনুষ্ঠানিক সংজ্ঞা
একটি কনসেপ্ট ক্লাস $mathcal{C}$-কে পিএসি-শিখনযোগ্য বলা হবে যদি এমন একটি অ্যালগরিদম $mathcal{A}$ থাকে যা যেকোনো অজানা বণ্টন $mathcal{D}$ এবং যেকোনো কাঙ্ক্ষিত নির্ভুলতা $epsilon$ ও আত্মবিশ্বাস $1 – delta$-এর জন্য:
$n$ আকারের ট্রেনিং নমুনা $S$ গ্রহণ করে এমন একটি হাইপোথিসিস $h in mathcal{H}$ তৈরি করতে পারে যা অন্তত $1 – delta$ নিশ্চয়তায় $epsilon$-এর কম ভুল প্রদর্শন করে:
$$mathbb{P}_{S sim mathcal{D}^n}left[ R(h) le epsilon right] ge 1 – delta$$
সবচেয়ে গুরুত্বপূর্ণ শর্ত হলো—এই অ্যালগরিদমের প্রয়োজনীয় নমুনা সংখ্যা $n = m(epsilon, delta)$ এবং রানটাইমকে $1/epsilon$, $1/delta$ এবং ডাইমেনশন $d$-এর পলিনমিয়াল বহুপদী হতে হবে।
৩. সসীম হাইপোথিসিস স্পেসে নমুনা জটিলতা (Sample Complexity)
ধরা যাক হাইপোথিসিস স্পেস $mathcal{H}$ সসীম এবং এর উপাদান সংখ্যা $|mathcal{H}|$। ডেটাসেটে এমন একটি হাইপোথিসিস আছে যার আসল ভুল অনেক বেশি ($R(h) > epsilon$), কিন্তু ট্রেনিং ডেটায় দৈবক্রমে সে কোনো ভুল করেনি ($R_{text{emp}}(h) = 0$)।
একটি খারাপ হাইপোথিসিসের একটি দৈব নমুনাকে সঠিকভাবে অনুমান করার সম্ভাবনা সর্বোচ্চ $1 – epsilon$। সুতরাং পরপর $n$ টি স্বাধীন নমুনায় তার ভুল না করার সম্ভাবনা হলো:
$$mathbb{P}(R_{text{emp}}(h) = 0 mid R(h) > epsilon) le (1 – epsilon)^n le e^{-nepsilon}$$
এখন স্পেসের সকল খারাপ হাইপোথিসিসের ওপর ইউনিয়ন বাউন্ড (Union Bound) প্রয়োগ করলে পাই:
$$mathbb{P}left(exists h in mathcal{H} : R_{text{emp}}(h) = 0 text{ এবং } R(h) > epsilonright) le |mathcal{H}| e^{-nepsilon}$$
আমরা চাই এই বিপর্যয়ের সম্ভাবনা যেন সর্বোচ্চ $delta$ হয়:
$$|mathcal{H}| e^{-nepsilon} le delta implies n ge frac{1}{epsilon} left( ln |mathcal{H}| + ln frac{1}{delta} right)$$
এটিই হলো বিখ্যাত সসীম পিএসি স্যাম্পল কমপ্লেক্সিটি সূত্র।
৪. ওকামের ক্ষুরের গাণিতিক প্রমাণ
চতুর্দশ শতাব্দীর দার্শনিক উইলিয়াম অব ওকামের সুবিখ্যাত নীতি—”প্রয়োজনের অতিরিক্ত সত্ত্বা অনুমান কোরো না” (Occam’s Razor)—এই সূত্রের মাধ্যমে প্রথমবার গাণিতিক ভিত্তি পায়।
লক্ষ করুন, প্রয়োজনীয় নমুনা সংখ্যা নির্ভর করে $ln |mathcal{H}|$-এর ওপর। তথ্য তত্ত্বে $ln_2 |mathcal{H}|$ হলো একটি হাইপোথিসিসকে এনকোড করার জন্য প্রয়োজনীয় ন্যূনতম বিট সংখ্যা (মডেলের বিবরণী দৈর্ঘ্য বা Description Length)। সুতরাং:
ওকামের উপপাদ্য: যদি কোনো সংক্ষিপ্ত এবং সরল মডেল (কম $ln |mathcal{H}|$) পর্যাপ্ত পরিমাণের ট্রেনিং ডেটায় শূন্য ভুল প্রদর্শন করে, তবে গাণিতিকভাবে নিশ্চিত যে সে নতুন অদেখা তথ্যেও সফলভাবে জেনারেলাইজ করবে।
সরলতা কেবল বিজ্ঞানের নান্দনিক আকাঙ্ক্ষা নয়—এটি পরিসংখ্যানিক শিখনের এক অকাট্য গাণিতিক শর্ত।
