Computational Complexity

ভূমিকা (Motivation)

"এই মডেলটি কি আমার জিপিউ (GPU) মেমরিতে ধরবে?" এবং "ট্রেনিং হতে এটি ঠিক কতক্ষণ সময় নেবে?" — এগুলো এমন কিছু প্রশ্ন যা ট্রেনিংয়ের কোড রান করার আগেই মাথায় আসে। এগুলোর উত্তর অনুমান বা আন্দাজের বিষয় নয় — প্রতিটি কনভোলিউশন লেয়ারের একটি সুনির্দিষ্ট ও হিসাবযোগ্য মাল্টিপ্লাই-অ্যাকুমুলেট বা MAC (multiply-accumulate) অপারেশন থাকে, প্রতিটি প্যারামিটার মেমরিতে নির্দিষ্ট পরিমাণ বাইট দখল করে, এবং প্রতিটি ইন্টারমিডিয়েট ফিচার ম্যাপ ব্যাকপ্রোপাগেশনের সময় মেমরিতে অবস্থান করে। এই চ্যাপ্টারটি মূলত সেই হিসাব-নিকাশ বা পাটিগণিত নিয়ে তৈরি, এবং জানাবে ইমেজ ডেটার জন্য সাধারণ fully-connected বা MLP আর্কিটেকচারের তুলনায় CNN কেন অবাস্তব রকমের সাশ্রয়ী ও দক্ষ।

মূল ধারণা তৈরি করা (Building the Intuition)

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

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

পেছনের মূল গণিত (The Math Behind It)

একটি একক কনভোলিউশন লেয়ারের FLOPs (FLOPs of a Single Conv Layer)

$$\text{MACs} = H' \times W' \times C_{out} \times (F_h \times F_w \times C_{in})$$

যেখানে: $H', W'$ হলো আউটপুট ফিচার ম্যাপের উচ্চতা ও প্রস্থ, $C_{out}$ হলো ফিল্টারের সংখ্যা বা আউটপুট চ্যানেলের সংখ্যা, $F_h, F_w$ হলো কার্নেলের উচ্চতা ও প্রস্থ, এবং $C_{in}$ হলো ইনপুট চ্যানেলের সংখ্যা।

সহজ কথা: এটি ডান থেকে বামে পড়ুন। $(F_h \times F_w \times C_{in})$ হলো একটিমাত্র আউটপুট নোড বা মান তৈরি করার খরচ — যেখানে একটি ফিল্টার ইনপুটের একটি প্যাচের ওপর স্লাইড করে সবগুলো ইনপুট চ্যানেল জুড়ে সমষ্টি হিসাব করে। $C_{out}$ বলে যে আপনি প্রতিটি ফিল্টারের জন্য এই কাজটি পুনরাবৃত্তি করবেন। আর $H' \times W'$ বলে যে আপনি আউটপুটের প্রতিটি স্থানিক বা স্পেশাল পজিশনে এই সম্পূর্ণ কাজটি বারবার রান করবেন। একটি MAC (multiply-accumulate) অপারেশন বলতে একটি গুণ ও একটি যোগফলকে বোঝায়, তাই FLOPs $\approx 2 \times$ MACs।

ট্রেনিংয়ের কম্পিউটেশনাল জটিলতা (Training Complexity)

ট্রেনিংয়ের কম্পিউটেশনাল খরচ হলো মূলত ফরওয়ার্ড পাসের MACs-কে আরও কয়েকটি ফ্যাক্টর বা গুণক দিয়ে গুণ করা:

$$\text{Total Compute} \approx \text{MACs}_{\text{forward}} \times 3 \times \text{Batches} \times \text{Epochs}$$

যেখানে: ৩ গুণকটি ফরওয়ার্ড পাসের সাথে ব্যাকওয়ার্ড পাসকে যুক্ত করে (ওজন ও ইনপুট উভয়ের সাপেক্ষে গ্রেডিয়েন্ট ক্যালকুলেট করার কম্পিউটেশনাল খরচ ফরওয়ার্ড পাসের দ্বিগুণের কাছাকাছি, এবং বেশিরভাগ লেয়ারেই এই দুটি backward হিসাব করতে হয়), Batches হলো প্রতি ইপকের মোট মিনি-ব্যাচ সংখ্যা, এবং Epochs হলো training কত ইপক ধরে চলবে তার সংখ্যা।

সহজ কথা: training-এ ইনফ্যারেন্স বা ইভালুয়েশনের তুলনায় বহুগুণ বেশি কাজ করতে হয় — এর জন্য ফরওয়ার্ড পাসের অ্যাক্টিভেশনগুলোর পাশাপাশি গ্রেডিয়েন্ট হিসাবের জন্য একটি সম্পূর্ণ ব্যাকওয়ার্ড পাসের প্রয়োজন হয়, যা প্রতি ব্যাচে ও প্রতি ইপকে পুনরাবৃত্ত হয়। ঠিক এই কারণেই জিপিউ ক্লাস্টারে একটি বড় CNN ট্রেইন করতে যেখানে কয়েক দিন লেগে যেতে পারে, সেই একই মডেল ইনফ্যারেন্স করার সময় একটি একক ইমেজে মাত্র কয়েক মিলিসেকেন্ডে সিদ্ধান্ত দিতে পারে।

ইনফ্যারেন্সের কম্পিউটেশনাল জটিলতা (Inference Complexity)

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

মেমরির জটিলতা (Memory Complexity)

মোট ট্রেনিং মেমরি $\approx$ Parameter memory + Activation memory + Gradient memory + Optimizer state memory

যেখানে:

• Parameter memory নেটওয়ার্কের প্রতিটি ওজন ও বায়াস সংরক্ষণ করে — ব্যাচ সাইজ বা ইমেজ রেজোলিউশন নির্বিশেষে এটি স্থির থাকে।
• Activation memory ফরওয়ার্ড পাসের সময় তৈরি হওয়া প্রতিটি ইন্টারমিডিয়েট ফিচার ম্যাপ সংরক্ষণ করে, কারণ গ্রেডিয়েন্ট হিসাবের জন্য ব্যাকপ্রোপাগেশনের এগুলো প্রয়োজন হয়। এটি ব্যাচ সাইজ, ইমেজ রেজোলিউশন ও নেটওয়ার্কের গভীরতার সাথে সাথে বাড়ে, এবং প্রায়ই এটিই সবচেয়ে বেশি মেমরি দখলকারী উপাদান।
• Gradient memory প্রতিটি প্যারামিটারের জন্য একটি করে গ্রেডিয়েন্ট মান সংরক্ষণ করে — যা প্যারামিটার মেমরির সমান আকারের।
• Optimizer state memory অপটিমাইজার প্রতিটি প্যারামিটারের জন্য যে বাড়তি হিসাব-নিকাশ রাখে তা কভার করে। যেমন Adam প্রতিটি প্যারামিটারের জন্য দুটি অতিরিক্ত মুভিং-অ্যাভারেজ এস্টিমেট (প্রথম ও দ্বিতীয় মোমেন্ট) ট্র্যাক করে, ফলে সাধারণ SGD-র তুলনায় (যা অতিরিক্ত কিছুই ট্র্যাক করে না) অপটিমাইজারের মেমরি ফুটপ্রিন্ট প্রায় তিনগুণ বেড়ে যায়।

সহজ কথা: ওজনের প্যারামিটার ও তাদের গ্রেডিয়েন্ট মেমরি শুধুমাত্র মডেলের আকারের ওপর নির্ভর করে, ব্যাচ সাইজের ওপর নয়। কিন্তু অ্যাক্টিভেশন মেমরি ব্যাচ সাইজ ও ইমেজের রেজোলিউশনের সাথে সাথে জ্যামিতিক হারে বাড়ে — ঠিক এই কারণেই মেমরি লিমিট বা Out-Of-Memory (OOM) এরর আসলে আমরা সবার আগে ব্যাচ সাইজ কমাই, এবং খুব গভীর নেটওয়ার্কের জন্য gradient checkpointing (মেমরিতে না রেখে রান-টাইমে আবার অ্যাক্টিভেশন হিসাব করা) কৌশল ব্যবহার করা হয়।

বাস্তব তুলনা: CNN বনাম MLP প্যারামিটার কাউন্ট

নিচের গাণিতিক হিসাবটিই মূলত প্রমাণ করে কেন ইমেজ ডেটার ক্ষেত্রে CNN জয়ী হয়েছে। একটি সাধারণ $224 \times 224 \times 3$ সাইজের রঙিন (RGB) ছবিকে প্রসেস করার জন্য দুটি ভিন্ন আর্কিটেকচারের একদম প্রথম লেয়ারের ওজনের তুলনায় নজর দেওয়া যাক:

১,০০০টি নিউরন বিশিষ্ট একটি ডেন্স (fully connected) লেয়ার এই ছবির প্রতিটি পিক্সেলকে প্রতিটি নিউরনের সাথে সরাসরি যুক্ত করে, যার ফলে মোট ইনপুট নোড সংখ্যা $224 \times 224 \times 3 = 150{,}528$।

$$\text{Params}_{\text{MLP}} = 150{,}528 \times 1{,}000 \approx 150.5 \text{ million}$$

এর বিপরীতে, প্রতিটি $3\times3$ সাইজের ৬৪টি ফিল্টার বিশিষ্ট একটি কনভোলিউশন লেয়ার ছবির এক একটি ছোট $3\times3$ লোকাল প্যাচের ওপর কাজ করে এবং সেই একই ৬৪টি ফিল্টার পুরো ছবির সব জায়গায় বারবার ব্যবহার বা ওজন শেয়ার করে:

$$\text{Params}_{\text{CNN}} = (3 \times 3 \times 3 + 1) \times 64 = 28 \times 64 = 1{,}792$$

যেখানে: $3\times3$ হলো কার্নেলের স্থানিক সাইজ, ৩ হলো ইনপুট চ্যানেলের সংখ্যা (RGB), $+1$ হলো প্রতি ফিল্টারে একটি করে বায়াস, এবং $64$ হলো ফিল্টারের সংখ্যা।

এটি প্রায় ৮৪,০০০ গুণ প্যারামিটার হ্রাস করার সমান, এবং এটি কোনো জাদু নয় — এটি সরাসরি এসেছে কনভোলিউশনের দুটি মূল বৈশিষ্ট্য থেকে: লোকাল কানেক্টিভিটি বা local connectivity (প্রতিটি ফিল্টার শুধু একটি ছোট লোকাল প্যাচ দেখে, পুরো ছবি নয়) এবং ওজন শেয়ারিং বা weight sharing (ছবির প্রতিটি পজিশনে নতুন ওজনের সেট না শিখে একই ১,৭৯২টি ওজনকে সব জায়গায় বারবার ব্যবহার করা)। CNN শুধুমাত্র প্যারামিটারের দিক থেকে সাশ্রয়ী নয় — এটি ছবির ক্ষেত্রে MLP-র চেয়ে বেশি অ্যাকুরেসি বা সঠিক সিদ্ধান্ত দেয়, কারণ এই লোকাল কানেক্টিভিটি ও ট্রান্সলেশন ইনভ্যারিয়েন্স ছবির বাস্তব রূপের সাথে হুবহু মিলে যায়: একটি বিড়ালের কান ছবির উপরে-বামে থাকুক আর নিচে-ডানে থাকুক, এর আকৃতি ও গঠন একই থাকে।

মূল বিষয়গুলো (Key Takeaways)

সাধারণ ভুল ধারণা (Common Mistakes)

ইন্টারভিউ কর্নার

বাস্তবে এর ব্যবহার

যখনই আপনি একটি ব্যাচ সাইজ বেছে নেন, ল্যাপটপ GPU বা ডেটা-সেন্টার ক্লাস্টারে ট্রেইন করার মধ্যে সিদ্ধান্ত নেন, অথবা একটি মডেল ফোনে রিয়েল টাইমে চলতে পারবে কিনা তা ঠিক করেন, তখন আপনি প্রকারান্তরে এই সূত্রগুলোই প্রয়োগ করছেন। torchinfo বা keras.Model.summary()-এর মতো ফ্রেমওয়ার্ক প্রোফাইলাররা ঠিক এই সংখ্যাগুলোই আপনার জন্য হিসাব করে দেয় — কিন্তু নিজে হাতে এগুলো বের করতে জানাই আপনাকে কোনো কোড লেখার আগেই একটি প্রস্তাবিত আর্কিটেকচার আপনার হার্ডওয়্যারে আদৌ সম্ভব কিনা তা অনুমান করতে সাহায্য করে।