Indeterminate Forms and L’Hospital’s Rule in Decision Trees

Machine learning puts theoretical concepts in daily life as fast as no other motivation does and raises math adoption day by day. Sometimes, practitioners apply some high level math concepts without noticing. Herein, indeterminate forms and L’Hospital’s rule from calculus often appear in building decision trees.

Decision tree algorithms such as ID3 and C4.5 use entropy and gain calculations for determining the most dominant feature. Typical entropy calculation is demonstrated below for n classes.

---

🙋‍♂️ You may consider to enroll my top-rated machine learning course on Udemy

---

Entropy = – Σ (i=0 to n) p(class_i) . log₂p(class_i) = – p(class₁) . log₂p(class₁) – p(class₂) . log₂p(class₂) – … – p(class_n) . log₂p(class_n)

For example, if decision class consists of 4 yes and 2 no instances, then there are 6 instances and binary classes. Entropy will be calculated as

Entropy(decision) = – p(no) . log₂p(no) – p(yes) . log₂p(yes) = – (2/6) . log₂(2/6) – (4/6) . log₂(4/6) = -0.333.log₂(0.333) – 0.667.log₂(0.667) = -0.333.(-1.585) – 0.667.(-0.585) = 0.918

Indeterminate cases

What if number of instances for a class is equal to 0? Let’s say decision class consists of 6 yes, and 0 no examples.

Entropy(decision) = – p(no) . log₂p(no) – p(yes) . log₂p(yes) = – (0/6) . log₂(0/6) – (6/6) . log₂(6/6) = – 0 . log₂(0) – 1 . log₂(1)

Here, log₂(1) is equal to 0, but the problem is log₂(0) is equal to – ∞. Additionally, we need 0 times ∞ in this calculation.

Let’s ask this question to python

import math

a = 0
b = math.log(0, 2) #log to the base 2 of 0, or log 0 to the base 2

print(a*b)

You will face with ValueError: math domain error if you run 0 times negative ∞ in python. Similarly, Java produces NaN exception and excel returns #NUM! error.

---

---

As seen, this operation cannot be performed, can it? But we are suspicious ones. What if even high level programming languages do not know how to compute?

Do programming languages know calculus?

The term we have trouble is x . log₂x for x is equal to 0. We can rearrange the equation as limit x goes to 0 for x times log x to the base 2. Moving x multiplier to the denominator as 1 over x would not change the result.

lim (x->0) x . log₂x = lim (x->0) log₂x / (1/x) = – ∞/∞

Yes, it is transformed to familiar indeterminate form of ∞/∞.

L’Hospital Rule

L’Hopital’s rule states that if f(x) and g(x) are both equal to 0 (or ∞) while limit goes to some point c

Condition: lim_(x->c) f(x) = lim_(x->c) g(x) = 0 (or ∞)

Then, function f over function g is equal to derivative of f and derivative of g.

lim_(x->c) f(x)/g(x) = lim_(x->c) f'(x)/g'(x)

Here, f(x) and g(x) must be must be differentiable at point c.

We can already transformed x . log₂x term to ∞/∞ indeterminate form. This means that we can apply L’Hopital.

---

---

lim_(x->0) x . log₂x = lim_(x->0) log₂x / (1/x) = lim_(x->0) (log₂x)’/(1/x)’ = (log₂x)’/(x^-1)’

Notice that derivative of log₂x is 1/(x.ln(2))

(1/(x.ln(2))) / (-1 . x^-2) = [1 / (x.ln(2))] / [-1 / x²] = – x² / x.ln(2) = x / ln(2)

This is L’Hospital applied version of lim (x->0) x . log₂x

lim_(x->0) x . log₂x = lim_(x->0) x / ln(2) = 0/0.693 = 0

Graph of x.log(x) is defined for [0, +∞) as illustrated below. Surprisingly, x = 0 is not undefined.

So, this case appears often when building entropy based decision trees. We can handle this trouble with calculus only. Even high level programming languages could not help to solve this case. To sum up, we can say that programming languages do not know calculus. They are designed to perform linear operations only.

You might rethink about takeover by some kind of evil AI or killer robots. They are not capable of applying a basic calculus. This is the basic answer why AI cannot takeover the human dominance on earth.

As an antithesis, None of the best predators in the earth orca, lion, white shark, siberian tiger, king cobra does not even known counting – Alper Ozpinar. But do not forget these species couldn’t takeover human dominance. Heavy-handed force might not put you at the top of food chain pyramid.

PS: Thanks to Valentin Cold to inform me and raise awareness about this subject

---

---

---

Support this blog if you do like!

    

---