information-theoryমাঝারি⏱ 8 মিনিট

Information Gain — তথ্য লাভ

Information Gain

❓

নাহিদের ২০ প্রশ্ন গেম

ধর তুই আর তোর বন্ধু নাহিদ ধানমন্ডি লেকের পাশে বইসা '20 Questions' গেম খেলতেছিস। নাহিদ একটা প্রাণী ভাবছে। তুই জিজ্ঞেস করলি 'এইটা কি পানিতে থাকে?' নাহিদ বলল 'হ্যাঁ!' — একটা প্রশ্নেই তুই অর্ধেকেরও বেশি প্রাণী বাদ দিলি! এইটা ভালো প্রশ্ন। কিন্তু যদি জিজ্ঞেস করতি 'এইটার নাম কি ক দিয়া শুরু?' — এইটা বাজে প্রশ্ন, কারণ অল্প কিছু বাদ যায়।

একটা প্রশ্ন জিজ্ঞেস করার পর uncertainty কতটুকু কমলো — এইটাই Information Gain! গুরু বলে — 'ভালো প্রশ্ন = বেশি information gain = বেশি uncertainty কমানো!'

সংজ্ঞা

Information Gain হইল কোনো feature বা attribute জানার আগে আর পরে entropy-র পার্থক্য। যেই feature-এ information gain বেশি, সেইটা সবচেয়ে informative — decision tree-তে সেইটাই আগে split হয়।

Information Gain — split-এর আগে আর পরে entropy-র পার্থক্য

\[IG(S, A) = H(S) - \sum_{v \in \text{Values}(A)} \frac{|S_v|}{|S|} H(S_v)\]

ব্যাখ্যা

আগে Entropy, পরে Entropy

Information Gain = Parent node-এর entropy - Children nodes-এর weighted average entropy। প্রশ্ন করার আগে uncertainty ছিল বেশি, প্রশ্নের পরে কমলো — এই difference-ই IG।

\[IG = H(\text{before}) - H(\text{after})\]

Decision Tree-তে Best Split

Decision tree algorithm সব feature-এর information gain calculate করে। সবচেয়ে বেশি IG যেই feature-এর, সেইটা root node বা current split-এ use হয়। নাহিদের গেমে 'পানিতে থাকে?' এর IG > 'নাম ক দিয়া শুরু?' এর IG।

IG আর KL Divergence-র সম্পর্ক

Information Gain আসলে joint distribution আর marginal distributions-এর product-এর মধ্যে KL Divergence-ই! Mutual Information-ও basically সব features-এর average Information Gain।

\[IG(S, A) = D_{KL}(P(S,A) \| P(S) \cdot P(A))\]

ঢাকার ট্রাফিক জ্যাম Prediction

১০টা দিনের data: ৬ দিন জ্যাম আছে, ৪ দিন নাই। Feature 'বৃষ্টি হইছে?' — বৃষ্টির ৪ দিনে ৩ জ্যাম + ১ নো-জ্যাম, শুকনা ৬ দিনে ৩ জ্যাম + ৩ নো-জ্যাম। 'বৃষ্টি' feature-এর IG কত?

Step 1: Parent entropy

পুরা dataset-এ 6/10 জ্যাম, 4/10 নো-জ্যাম

\[H(S) = -\frac{6}{10}\log_2\frac{6}{10} - \frac{4}{10}\log_2\frac{4}{10} = 0.971\]

Step 2: Children entropy

বৃষ্টি (4 দিন): 3/4 জ্যাম, 1/4 নো-জ্যাম। শুকনা (6 দিন): 3/6 জ্যাম, 3/6 নো-জ্যাম।

\[H(\text{rain}) = -\frac{3}{4}\log_2\frac{3}{4} - \frac{1}{4}\log_2\frac{1}{4} = 0.811\]

Step 3: Weighted average

শুকনা দিনের entropy = 1.0 (50-50 split), weighted average বের করো

\[H_{\text{after}} = \frac{4}{10}(0.811) + \frac{6}{10}(1.0) = 0.924\]

Step 4: Information Gain

IG = আগে - পরে

\[IG = 0.971 - 0.924 = 0.047 \text{ bits}\]

উত্তর:

বৃষ্টি feature-এর IG = 0.047 bits। এইটা কম — মানে বৃষ্টি alone জ্যাম predict করতে খুব helpful না ঢাকায়। কারণ বৃষ্টি ছাড়াও জ্যাম থাকে! 😅

ML-এ কোথায় লাগে?

💡

মনে রাখার ট্রিক

Information Gain = নাহিদের 20 Questions গেমে ভালো প্রশ্ন করলে কত uncertainty কমলো। 'পানিতে থাকে?' = বেশি IG, 'নাম ক দিয়া শুরু?' = কম IG!

#information-gain#decision-tree#feature-selection#entropy#id3#c45