Cost Functions

Welcome back to another instance of demystifying machine learning. Recently, we wrapped up the overarching logic associated with decision trees. We'll recall decision trees as just one of many machine learning algorithms, each type mapping to a specific type of problem. Thus, we ought to be able to articulate what a decision tree is in both classification and regression forms as well as what a simple classifier looks like in pseudocode. Furthermore, we'll remember that the essence, the secret sauce of decision trees exists in the splitting between options. How exactly is a split computed? Let's find out!

Overview of Split Costs

In my opinion, split cost computation is the harder part of decision trees compared to the ground we've covered so far. Let's build a little clarity first: just like how algorithms pair with problems, cost computations pair with algorithm types. That said, there are some common attributes across different cost functions. For instance, all cost functions seek to find the lowest cost associated with a given split. Therein, our algorithms will tend towards computing the cost of every split in the decision tree and then learning by mapping the connections between lowest cost nodes. As always, there are some critical differences too.

Let's start with classification and Gini functions. Gini functions are common split cost calculations in machine learning. Notice the plural? That's right- there is one form associated with binary decisions because it handles dichotomous decisions (e.g., yes or now, true or false, and so forth. Thus, splitting occurs at the junction of such decisions. There is another form associated with non-binary decisions of course.

The first, binary classification form is Gini coefficient. Related in name only, the non-binary form is Gini impurity and handles multi-class situations. It is important to know these forms are not equivalent or interchangeable.

By the way, Gini is pronounced liked genie.

Split Cost Illustrated

I claimed the split cost computation is the harder part of our machine learning work. I'm going to illustrate why that's not actually true despite involving...yes, that's right - math. Let's use a slightly modified table of student course preferences to illustrate the data.

|Student | Prior Experience | Course | Time | Liked |
Yes | Programming | Day | Yes | 2 |
| No | Programming | Day | No | 3 |
| Yes | Programming | Night | No | 4 |
| No | Programming | Night | Yes | 5 |
| Yes | Programming | Day | Yes | 6 |
| No | Programming | Day | No | 7 |
| Yes | Programming | Day | No | 8 |
| Yes | Programming | Night | Yes | 9 |
| Yes | Programming | Night | Yes | 10 |
| Yes | Programming | Night | No |

Broadly defined, the equation for a Gini function used in a classifier looks something like: Gini = 1 - [sum of ( objects in class / total - objects) ²]

To illustrate- we have 2 classes (liked) with two attributes (prior experience, time) and a total of ten samples. There are 5 instances of the yes class in the sample and 5 in the no class. Accordingly, we can encode this into the following.

1 - [(2 / 10)] ² + [(2 / 10)]² = ?

What do you think the result is here? What does the value represent? We'll look deeper into the answers next time as well as alternative cost functions.