Chapter 4. Models – Learning from Information

So far in this book, we have examined a range of tasks and techniques. We introduced the basics of data types, structures, and properties, and we familiarized ourselves with some of the machine learning tools that are available.

In this chapter, we will look at three broad types of model:

• Logical models

• Tree models

• Rule models

The next chapter will be devoted to another important type of model—the linear model. Much of the material in this chapter is theoretical, and its purpose is to introduce some of the mathematical and logical tools needed for machine learning tasks. I encourage you to work through these ideas and formulate them in ways that may help solve problems that we come across.

Logical models

Logical models divide the instance space, that is the set of all possible or allowable, instances, into segments. The goal is to ensure that the data in each segment is homogeneous with respect to a particular task. For example, if the task is classification, then we aim to ensure that each segment contains a majority of instances of the same class.

Logical models use logical expressions to explain a particular concept. The simplest and most general logical expressions are literals, and the most common of these is equality. The equality expression can be applied to all types—nominative, numerical, and ordinal. For numerical and ordinal types, we can include the inequality literals: greater than or less than. From here, we can build more complex expressions using four logical connectives. These are conjunction (logical AND), which is denoted by ∧; disjunction (logical OR), which is denoted by ∨; implication, which is denoted by →; and negation, which is denoted by ┌. This provides...

Tree models

Tree models are ubiquitous in machine learning. They are naturally suited to divide and conquer iterative algorithms. One of the main advantages of decision tree models is that they are naturally easy to visualize and conceptualize. They allow inspection and do not just give an answer. For example, if we have to predict a category, we can also expose the logical steps that give rise to a particular result. Also tree models generally require less data preparation than other models and can handle numerical and categorical data. On the down side, tree models can create overly complex models that do not generalize to new data very well. Another potential problem with tree models is that they can become very sensitive to changes in the input data and, as we will see later, this problem can be mitigated against using them as ensemble learners.

An important difference between decision trees and the hypothesis mapping used in the previous section is that the tree model does not use internal...

Rule models

We can best understand rule models using the principles of discrete mathematics. Let's review some of these principles.

Let X be a set of features, the feature space, and C be a set of classes. We can define the ideal classifier for X as follows:

c: X → C

A set of examples in the feature space with class c is defined as follows:

D = {(x₁, c( x₁)), ... , (x_n, c( x_n)) ⊆ X × C

A splitting of X is partitioning X into a set of mutually exclusive subsets X₁....X_s, so we can say the following:

X = X1 ∪ .. ∪ Xs

This induces a splitting of D into D₁,...D_s. We define Dj where j = 1,...,s and is {(x,c(x) ∈ D | x ∈ Xj)}.

This is just defining a subset in X called Xj where all the members of Xj are perfectly classified.

In the following table we define a number of measurements using sums of indicator functions. An indicator function uses the notation where I[...] is equal to one if the statement between the square brackets is true and zero if it is false. Here τc(x) is the estimate of c(x)...

Summary

We began this chapter by exploring a logical language and creating a hypothesis space mapping for a simple example. We discussed the idea of least general generalizations and how to find a path through this space from the most general to the least general hypothesis. We briefly looked at the concept of learnability. Next, we looked at tree models and found that they can be applied to a wide range of tasks and are both descriptive and easy to interpret. Trees by themselves, however, are prone to overfitting and the greedy algorithms employed by most tree models can be prone to over-sensitivity to initial conditions. Finally, we discussed both ordered rule lists and unordered rule set-based models. The two different rule models are distinguished by how they handle rule overlaps. The ordered approach is to find a combination of literals that will separate the samples into more homogeneous groups. The unordered approach searches for a hypotheses one class at a time.

In the next chapter...