Information Gain and Entropy in Learning Models, Explained

UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 7.4 Free with a free account

Information Gain and Entropy in Learning Models

Introduction to Artificial Intelligence · Chapter 7: Machine Learning, NLP, and PerceptionSection 7.4 · lesson 52 of 6911 min · free with a free account

← Combining Natural Language Processing with Deep LearningNext lesson: Making Choices with Decision Networks →

Earn 3 college credits for Introduction to Artificial IntelligenceRecommended for credit by NCCRS · Computer Science 373 · self-paced · one payment, lifetime access
Enroll in Introduction to Artificial Intelligence · $250 →Download the syllabus (PDF)

In this lesson

How entropy, information gain and cross-entropy score splits and train models.

  • Calculate entropy in bits for a group of labeled items
  • Compute information gain, Gini impurity and gain ratio for a split
  • Explain cross-entropy and KL divergence and their role as training losses
  • Identify common mistakes when using entropy-based measures

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,397 words). Read along, or search it.

Opening Question

When the Simple Score Ties

In Section 5.3, a decision tree scored each question by a simple number: the share of items that disagree with their group's most common label. Take a node of eight items, four of each label, and two possible splits. Split P makes groups of three and one, and one and three. Split Q makes groups of two and four, and two and zero. The simple score gives both splits exactly 0.25. Yet Q isolates a perfectly pure group of two. Isn't that worth something? We need a score that notices.

Information

Rare Outcomes Carry More Bits

Start with information. If an outcome was almost certain, learning it tells you very little. If it was surprising, it tells you a lot. An outcome with probability p carries minus log base two of p bits. Probability one half carries one bit. One quarter carries two bits. One eighth carries three. Rarer outcomes carry more information. The logs used here, base two, are reviewed in Section 1.5, and only a few values are needed.

Entropy

Average Uncertainty in a Group

Entropy is the average information in a group: how uncertain the label of a randomly chosen item is. It's minus the sum, over the labels, of p times log base two of p. A label that never occurs adds nothing. A group where every item has the same label has entropy zero: no uncertainty. With two labels, entropy peaks at one bit, at fifty-fifty. Three and three gives 1.000. Four and two gives 0.918. Three and one, 0.811. Five and one, 0.650. Nine and one, 0.469. And six and zero, zero.

Worked Example

Entropy of Three and One

Here's one worked out. Three items of one label, one of the other: proportions three quarters and one quarter. Three quarters, times log base two of three quarters, minus 0.415, gives minus 0.311. One quarter, times minus two, gives minus 0.5. Add them, flip the sign, and the entropy is 0.811 bits.

Information Gain

Conditional Entropy and Weighted Groups

A split asks a question about a feature, and divides the items into groups, one per answer. Conditional entropy is the uncertainty left once we know the answer: the average of the groups' entropies, each weighted by its share of the items. The weights matter. A tiny group that happens to be pure shouldn't make a poor split look good. Information gain is the uncertainty removed: the entropy before the split, minus the conditional entropy after. It's never negative, and the best question has the highest gain.

Worked Example

Entropy Prefers Split Q

Back to P and Q. The node itself, four and four, has entropy one. Split P: both groups are three and one, entropy 0.811 each. That's the conditional entropy, and the gain is 0.189. Split Q: the group of six, two and four, has entropy 0.918, weighted six eighths. The pure pair adds zero. So 0.689 is left, and the gain is 0.311. Entropy ranks Q higher, exactly as it should.

Gini Impurity

A Log-Free Alternative Score

A second score, Gini impurity, needs no logarithms: one minus the sum of the squared proportions. It's the chance that two items, picked at random with replacement, carry different labels. A pure group scores zero, and a fifty-fifty group scores one half. A split's Gini is the weighted average of its groups. For P it's 0.375, and for Q 0.333, so Gini also prefers Q. Plotted for two labels, entropy and Gini are both curves that peak at fifty-fifty, while the simple score is a straight-sided triangle. That's why it can't see a pure group. Classic algorithms differ. ID3 and C4.5 use information gain, and C4.5 refines it into gain ratio. CART uses Gini. In practice, they usually choose the same question.

Worked Example

Choosing the Root for Twelve Customers

Now the twelve customers from Section 5.3: six renewed and six canceled, so the root has entropy one, and Gini one half. Usage splits them into Often, five renew and one cancel, and Rarely, one and five. Each group has entropy 0.650, so the gain is 0.350. Its groups have Gini 0.278 each, a Gini gain of 0.222. Complaints gives four and two, and two and four: entropy 0.918 each, a gain of only 0.082. And Plan gives Basic, five and five, and Premium, one and one. Both groups stay exactly as mixed as the whole, so the gain is zero. All the measures agree: Usage first, Complaints a weak second, and Plan useless at the root. That confirms the choice in Section 5.3.

Quick Check

Plan Gains All 0.650 Bits

Quick check. The tree splits on Usage, and moves inside the Often customers: five who renew, one who cancels. Within that group, Plan puts the five renewers in Basic, and the one who canceled in Premium. How much information does that question gain? Pause, and decide. All of it: 0.650 bits. The group starts with the entropy of five and one, 0.650, and both of Plan's groups are pure, so nothing is left. A gain can't exceed the uncertainty that's there, so a full bit is impossible here. The question that was worthless at the root is now the best one.

Gain Ratio

Fixing the Bias Toward Many Values

Information gain has a known bias: it favors features with many values. Add a column holding a unique ID for each customer. Splitting on it makes twelve groups of one, every one pure, so the gain is the maximum, one full bit. Yet the question is useless for any new customer. Gain ratio fixes this. It divides the gain by the split information: the entropy of the group sizes themselves. For the ID column, that's log base two of twelve, 3.585 bits, so the ratio falls to 0.279. Usage, two groups of six, has split information one, and keeps its 0.350. Usage wins.

Cross-Entropy

Bits Wasted by a Model's Probabilities

Entropy also drives how models are trained. Say the true label proportions are p, and a model predicts proportions q. Cross-entropy is minus the sum of p times log base two of q: the bits needed to describe the data using the model's probabilities. If q equals p, cross-entropy is just the data's entropy. Any mismatch makes it bigger, and the extra is the KL divergence, the bits wasted by believing q. Take data where 75 percent have label one: entropy 0.811. A model that matches it pays exactly 0.811. Too confident, at ninety-ten, pays 0.944: a KL of 0.133. Fifty-fifty pays 1.000. Backing the wrong label pays 1.604.

KL Divergence

Never Negative, Not Symmetric

KL divergence is never negative, and it's zero only when q matches p. But it isn't a true distance, because it isn't symmetric. Swap the roles of p and q in the ninety-ten case, and the divergence is 0.105, not 0.133. For a single example with a known label, cross-entropy is just minus log base two of the probability the model gave the right answer. Give it 0.9, and the loss is only 0.152 bits. Give it 0.5: one bit. Give it 0.1: 3.322 bits. The loss climbs steeply as a model becomes confidently wrong, so training fixes those mistakes first. Many libraries use the natural log, which only rescales every value.

Quick Check

Each Halving Adds One Bit

Quick check. On one example, model A gives the right label a probability of one half. Model B gives it one eighth. How much bigger is model B's loss? Pause, and predict. Two bits more. Minus log base two of one half is one bit. Minus log base two of one eighth is three bits. Three minus one is two. The tempting four comes from the ratio of the probabilities, but the loss is a logarithm: each halving adds just one bit.

Common Mistakes

Misreading Entropy and Gain

Common mistakes. Wanting high entropy after a split: a good split leaves low entropy, which means high gain. Using one group's entropy instead of the weighted average. Trusting gain on a feature with many values, like an ID. Treating KL divergence as a distance, when the order of p and q matters. And forgetting that a label with probability zero adds nothing to any sum.

Key Takeaways

Entropy, Gain and Cross-Entropy

To sum up. Entropy measures uncertainty in bits: zero for a pure group, one for a fifty-fifty pair of labels. Information gain is the entropy before a split, minus the weighted entropy after. The best question has the highest gain. Gini is a log-free alternative that usually agrees, and gain ratio stops many-valued features from winning unfairly. Cross-entropy is the data's entropy plus the KL divergence, and it's the loss many classifiers minimize.

Think About It

One Huge Group, One Tiny Pure Group

Here's something to think about. A feature splits a node into one huge group and one tiny pure group. Its information gain looks decent. Would you trust it? What would the split information, and a fresh test set, tell you?

About Introduction to Artificial Intelligence at UPI Study

Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: AI vs Current Trends in CS and IT

Why take it here

Why students take Introduction to Artificial Intelligence with UPI Study

How machines search, reason and learnIntroduction to Artificial Intelligence covers how AI systems are built: intelligent agents, search and heuristics, game strategy, logic, neural networks, machine learning, language and perception, and the ethics of AI. It is a common upper-level course in computer science degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Introduction to Artificial Intelligence carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Information Gain and Entropy in Learning Models

What is entropy in a decision tree?
Entropy measures how uncertain the label of a randomly chosen item in a group is, computed as minus the sum, over the labels, of p times log base 2 of p. A pure group has entropy 0, and a fifty-fifty group with two labels has 1 bit. A group with three items of one label and one of the other has entropy of about 0.811 bits.
How do you calculate information gain?
Information gain is the entropy before a split minus the weighted average entropy of the groups after it, each group weighted by its share of the items. A node with four items of each label has entropy 1. Splitting it into a group of six, with two and four, and a pure group of two leaves 6/8 times 0.918, about 0.689, so the gain is about 0.311 bits.
What is the difference between information gain and Gini impurity?
Information gain scores a split by how much entropy it removes, while Gini impurity measures how mixed a group is without logarithms, as one minus the sum of the squared proportions. Gini is the chance that two items drawn at random with replacement carry different labels, and a split is judged by the weighted Gini of its groups. ID3 and C4.5 use information gain, and CART uses Gini. In practice, they usually choose the same question.
Why is information gain biased toward features with many values?
Information gain favors many-valued features because splitting into many tiny groups makes each group pure. A unique customer ID splits twelve customers into twelve groups of one, giving the maximum gain of 1 bit, yet it is useless for new customers. Gain ratio fixes this by dividing by the split information, here log base 2 of 12, about 3.585 bits, which cuts the ratio to about 0.279.

About the Introduction to Artificial Intelligence course

How many college credits is Introduction to Artificial Intelligence?
Introduction to Artificial Intelligence (Computer Science 373) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Introduction to Artificial Intelligence cost and what is included?
$250, paid once, with lifetime access: all 69 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Introduction to Artificial Intelligence take?
It is self-paced with no deadlines. The 69 lessons total about 16 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Introduction to Artificial Intelligence.

69 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Introduction to Artificial Intelligence →Download the syllabusEvery course with PRO →
Introduction to Artificial Intelligence
3 credits · NCCRSEnroll →