Linear vs Non-Linear Separability

Linear Separability কী?

একটা দুই-মাত্রিক গ্রাফে ছড়ানো কিছু লেবেল করা বিন্দু কল্পনা করুন — অর্ধেক লেবেল "class A", অর্ধেক "class B"। একটা সহজ প্রশ্ন জিজ্ঞেস করুন: আপনি কি গ্রাফের মধ্য দিয়ে একটা মাত্র সরল রেখা আঁকতে পারবেন যাতে প্রতিটা class A বিন্দু একপাশে থাকে, আর প্রতিটা class B বিন্দু অন্যপাশে থাকে, কোনো ব্যতিক্রম ছাড়াই?

উত্তর হ্যাঁ হলে, ডেটা linearly separable। উত্তর না হলে — যতই রেখা ঘোরান, সরান, বা বাঁকান না কেন, অন্তত একটা বিন্দু সবসময় ভুল পাশে থেকে যায় — তাহলে ডেটা linearly separable না।

আগের চ্যাপ্টারের ফলের উদাহরণটা কল্পনা করুন: আপেল ওজন-বনাম-ব্যাস গ্রাফের একটা অংশে জড়ো, কমলা আরেকটা অংশে, দুইটার মাঝে একটা পরিষ্কার ফাঁক নিয়ে। সেই ফাঁকের মধ্য দিয়ে আঁকা একটা মাত্র সরল রেখা এদের নিখুঁতভাবে আলাদা করে দেয়। এটাই linear separability-এর সবচেয়ে সহজ, সবচেয়ে দৃশ্যমান রূপ।

$$w_1 x_1 + w_2 x_2 + b = 0$$

এই সূত্রটা দুই-ইনপুট স্পেসের প্রতিটা সম্ভাব্য সরল রেখা বর্ণনা করে — $w_1$, $w_2$, আর $b$-এর ভিন্ন ভিন্ন মান রেখাটাকে বিভিন্ন অবস্থানে কাত করে আর সরায়। ডেটা তখনই linearly separable যখন এই তিনটা সংখ্যার কোনো একটা বাছাই এমন একটা রেখা তৈরি করে যেখানে প্রতিটা class A বিন্দু একপাশে ($w_1 x_1 + w_2 x_2 + b > 0$) আর প্রতিটা class B বিন্দু অন্যপাশে ($w_1 x_1 + w_2 x_2 + b < 0$)।

দুইটার বেশি ইনপুট থাকলে, "রেখা" সাধারণীকরণ হয়ে "সমতল" (তিনটা ইনপুট) বা "hyperplane" (চার বা তার বেশি ইনপুট) হয়ে যায় — কিন্তু মূল আইডিয়া একই থাকে: একটা মাত্র সমতল কাট, প্রতিটা ক্লাসের প্রতিটা বিন্দু পরিষ্কারভাবে নিজের পাশে পড়ে।

Non-Linearly Separable ডেটা

অনেক বাস্তব ডেটাই একটা সরল রেখার সাথে সহযোগিতা করে না। কল্পনা করুন class A-এর বিন্দুগুলো class B-এর একটা কেন্দ্রীয় ক্লাস্টারের চারপাশে একটা বলয় তৈরি করেছে — যেমন একটা ডোনাট আকৃতি, যেখানে class B হলো মাঝের ফাঁকা অংশ আর class A হলো ডোনাটটা নিজেই। কোনো সরল রেখাই একটা বলয়কে এর ভেতরের জিনিস থেকে আলাদা করতে পারে না: আপনি যে রেখাই আঁকুন না কেন, হয় সেটা বলয়ের মধ্য দিয়ে কেটে যায়, এর কিছু অংশ মিস করে, নয়তো ভেতরের ক্লাস্টারটা মিস করে, অথবা দুটোই।

এটাই non-linearly separable ডেটা: এমন কোনো একটা সরল রেখা (বা সমতল hyperplane) নেই যা একটা ক্লাসের প্রতিটা বিন্দুকে একপাশে আর অন্য ক্লাসের প্রতিটা বিন্দুকে অন্যপাশে রাখে। দুইটা ক্লাস এমনভাবে জড়িয়ে আছে যা একটা সমতল কাট দিয়ে খোলা সম্ভব না।

Non-linear separability বাস্তবে সবসময়ই দেখা যায়: ইমেজ ডেটা যেখানে "বিড়াল" আর "কুকুর" পিক্সেল পরিপাটি আলাদা অংশে থাকে না, টেক্সট ডেটা যেখানে বিষয়গুলো মিশে যায়, বা এমনকি একটা বলয়ের ভেতরে বসানো একটা টার্গেট আকৃতির মতো সহজ কিছুও। যখনই ক্লাসগুলো একে অপরের চারপাশে মোড়ানো, ইন্টারলকড, বা বাঁকা হয়ে একে অপরকে পার হয়ে যায়, একটা সমতল কাট যথেষ্ট হবে না — আর মডেলের একটা বেশি ফ্লেক্সিবল বাউন্ডারি আঁকার উপায় দরকার।

XOR প্রবলেম

Non-linear separability-এর সবচেয়ে পরিষ্কার, সবচেয়ে ছোট সম্ভাব্য উদাহরণ হলো XOR প্রবলেম (XOR মানে "exclusive or")। এতে মাত্র চারটা বিন্দু আছে, প্রতিটাতে দুইটা বাইনারি ইনপুট:

এই চারটা বিন্দু একটা গ্রাফে প্লট করুন, $x_1$ একটা অক্ষে, $x_2$ আরেকটাতে। $1$ লেবেল করা দুইটা বিন্দু — $(0,1)$ আর $(1,0)$ — বিপরীত কোণায় বসে থাকে। $0$ লেবেল করা দুইটা বিন্দু — $(0,0)$ আর $(1,1)$ — অন্য দুইটা বিপরীত কোণায় বসে থাকে। ক্লাসগুলো বর্গক্ষেত্রের চারপাশে কোনাকুনি পালাক্রমে আসে।

$1$-গুলোকে $0$-গুলো থেকে আলাদা করে এমন একটা মাত্র সরল রেখা আঁকার চেষ্টা করুন। এটা শুধু কঠিনই না — এটা গাণিতিকভাবে অসম্ভব। যেকোনো সরল রেখা সমতলটাকে দুইটা অর্ধ-সমতলে ভাগ করে, আর রেখাটা যতই কাত করুন না কেন, $(0,1)$ আর $(1,0)$-কে একপাশে একসাথে রাখতে পারবেন না, আর একইসাথে $(0,0)$ আর $(1,1)$-কে অন্যপাশে একসাথে রাখতেও পারবেন না। একটা আনুভূমিক রেখা চেষ্টা করুন, একটা উলম্ব রেখা, যেকোনো কোণে একটা তির্যক রেখা — প্রত্যেকটাই অন্তত একটা বিন্দুতে ব্যর্থ হয়।

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

কেন Perceptron ব্যর্থ হয়

একটা সিঙ্গেল perceptron — একটা নিউরন যা একটা ওয়েটেড সাম প্লাস একটা bias হিসাব করে, তারপর ফলাফলকে থ্রেশহোল্ড করে — শুধু একটা linear decision boundaryই তৈরি করতে পারে, যেমনটা Decision Boundaries চ্যাপ্টারে দেখা হয়েছে। এটা কোনো ট্রেনিং বাগ বা যথেষ্ট প্র্যাকটিসের অভাব না; এটা মডেলের গাণিতিক আকৃতিতেই সরাসরি বেক করা।

$$\hat{y} = \text{step}(w_1 x_1 + w_2 x_2 + b)$$

$0$ প্রেডিক্ট করা আর $1$ প্রেডিক্ট করার মাঝের বাউন্ডারি ঠিক সেই রেখা যেখানে $w_1 x_1 + w_2 x_2 + b = 0$ — সবসময়ই একটা সরল রেখা, $w_1$, $w_2$, আর $b$ যাই মান নিক না কেন। XOR-এর উপর একটা perceptron ট্রেন করা মানে $w_1$, $w_2$, আর $b$-এর প্রতিটা সম্ভাব্য মানের মধ্য দিয়ে খুঁজে বের করা, চারটা বিন্দুকে সঠিকভাবে আলাদা করে এমন একটা রেখা খোঁজার চেষ্টা করা। এমন কোনো রেখা যেহেতু নেই, এই সার্চ কখনোই সফল হতে পারে না — আরও বেশি ট্রেনিং ডেটা দিয়ে না, আরও বেশি ট্রেনিং সময় দিয়ে না, আরও চালাক লার্নিং রেট দিয়ে না। Perceptron সবসময় চারটা XOR বিন্দুর অন্তত একটা ভুল ক্লাসিফাই করবে, স্থায়ীভাবে।

এই ঠিক এই সীমাবদ্ধতাটাই — ১৯৬৯ সালে Marvin Minsky আর Seymour Papert বিখ্যাতভাবে চিহ্নিত করেছিলেন — দেখিয়েছিল যে সিঙ্গেল-লেয়ার perceptron XOR-এর মতো সহজ non-linear প্রবলেমও সমাধান করতে পারে না, আর এটাই একটা বড় কারণ কেন নিউরাল নেটওয়ার্ক গবেষণা বছরের পর বছর ধীর হয়ে গিয়েছিল, যতক্ষণ না মানুষ হিডেন লেয়ারসহ নেটওয়ার্ক ট্রেন করার উপায় বের করে ফেলল।

কেন Hidden Layer এটা সমাধান করে

সমাধানটা একটা বেশি চালাক সিঙ্গেল নিউরন না — এটা একের বেশি নিউরন, লেয়ারে সাজানো। ইনপুট আর আউটপুটের মাঝে একটা হিডেন লেয়ার যোগ করুন, আর একাধিক লিনিয়ার কাটের সমন্বয় এমন একটা বাউন্ডারির কাছাকাছি যেতে পারে যা কোনো একটা মাত্র রেখা কখনোই আঁকতে পারত না।

XOR-এর একটা কনক্রিট, হাতে-বানানো সমাধান দুইটা হিডেন নিউরন আর একটা আউটপুট নিউরন দিয়ে, সবগুলো step অ্যাক্টিভেশন ব্যবহার করে:

• হিডেন নিউরন ১ হিসাব করে এরকম কিছু: $h_1 = \text{step}(x_1 + x_2 - 0.5)$ — এটা ফায়ার করে ($=1$) যখনই অন্তত একটা ইনপুট $1$ হয়। অন্যভাবে বললে, হিডেন নিউরন ১ OR-এর কাছাকাছি যায়।
• হিডেন নিউরন ২ হিসাব করে এরকম কিছু: $h_2 = \text{step}(x_1 + x_2 - 1.5)$ — এটা ফায়ার করে শুধু তখনই যখন দুইটা ইনপুটই $1$। হিডেন নিউরন ২ AND-এর কাছাকাছি যায়।
• আউটপুট নিউরন এদের মেলায়: $\hat{y} = \text{step}(h_1 - h_2 - 0.5)$ — এটা ফায়ার করে যখন $h_1$ $1$ কিন্তু $h_2$ $0$, মানে "অন্তত একটা ইনপুট 1, কিন্তু দুইটাই না।"

ট্রুথ টেবিলের সাথে মিলিয়ে দেখুন: $(0,0)$-এ, $h_1$ আর $h_2$ দুইটাই $0$, তাই আউটপুট $0$। $(1,1)$-এ, $h_1$ আর $h_2$ দুইটাই $1$, আর $h_1 - h_2 = 0$, তাই আউটপুট $0$। $(0,1)$ আর $(1,0)$-এ, $h_1 = 1$ কিন্তু $h_2 = 0$, তাই আউটপুট $1$। এটাই XOR, নিখুঁতভাবে হিসাব করা, দুইটা হিডেন নিউরন দুইটা আলাদা লিনিয়ার কাট করছে আর আউটপুট নিউরন তাদের ফলাফল মেলাচ্ছে।

এটাই মূল কারণ কেন মাল্টি-লেয়ার নেটওয়ার্ক আদৌ আছে: একটা সিঙ্গেল লেয়ার চিরকাল একটা সরল বাউন্ডারিতে আটকে থাকে, কিন্তু এদের মাঝে non-linear অ্যাক্টিভেশন ফাংশনসহ লেয়ার স্তূপ করলে একটা নেটওয়ার্ক যথেষ্ট নিউরন থাকলে যেকোনো আকৃতির বাউন্ডারি প্রতিনিধিত্ব করতে পারে — XOR-এর দরকার হওয়া ঠিক সেই বাঁকা বাউন্ডারিসহ।

Visualization

নিচের ইন্টারেক্টিভ ডেমোটা আগের চ্যাপ্টারের সেই একই XOR-ভিত্তিক decision boundary টুল — linear separability ব্যর্থ হতে আর non-linear separability সফল হতে পাশাপাশি দেখার একটা নিখুঁত উপায়। একটা সিঙ্গেল perceptron আর একটা ছোট 2-লেয়ার নেটওয়ার্কের মধ্যে টগল করুন।

বিশেষভাবে এটা খেয়াল করুন:

• পারসেপ্ট্রন মোডে, ছায়াযুক্ত অংশটা ঠিক একটা সরল প্রান্ত দিয়ে ভাগ করা, আর ডেমোর নিজস্ব কাউন্টার দেখাবে ৪-এর মধ্যে ৪-এর কম XOR বিন্দু সঠিকভাবে ক্লাসিফাই হয়েছে, অন্তর্নিহিত weight যেভাবেই সরান না কেন — এটাই বাস্তব সময়ে linear separability ব্যর্থ হচ্ছে।
• MLP মোডে, ছায়াযুক্ত অংশটা দুইটা আলাদা তির্যক অঞ্চলে বেঁকে যায়, ঠিক XOR ট্রুথ টেবিলের তির্যক প্যাটার্নের সাথে মিলে — আর কাউন্টার পুরো ৪-এর মধ্যে ৪-এ পৌঁছায়।
• MLP বাউন্ডারির বাঁকটাই হিডেন লেয়ারের কাজ করার দৃশ্যমান স্বাক্ষর: এটা আক্ষরিক অর্থেই দুইটা সরল কাট (প্রতিটা হিডেন নিউরনের একটা করে) একসাথে মিলে একটা সিঙ্গেল non-linear আকৃতি তৈরি করেছে।

শুধু একটা হিডেন লেয়ার যোগ করে বাউন্ডারিকে "অসম্ভব" থেকে "সমাধান হয়ে গেছে"-তে বদলে যেতে দেখাটাই সবচেয়ে স্পষ্ট দৃশ্যমান যুক্তি কেন হিডেন লেয়ার, আর সাধারণভাবে depth, নিউরাল নেটওয়ার্কে গুরুত্বপূর্ণ।

Summary