Feature Selection

Let’s think about some data that doesn’t make a whole lot of sense. Say we want to measure weather data and want to be able to predict temperature given three variables: “Matt’s Coffee Consumption,” “Ice Cream Consumption,” and “Season” (see Table 10-1 and Figure 10-1).

Figure 10-1. A graph comparing my consumption of ice cream (in scoops) and coffee (in cups) with the temperature

Obviously you can see that I generally drink about 4 cups of coffee a day. I tend to eat more ice cream in the summertime and it’s generally hotter around that time.

But what can we do with this data? There are at most N choose K solutions to any data set, so given N dimensions, we can find an enormous number of combinations of various-sized subsets.

At this point we want to reduce the amount of dimensions we are looking at but don’t know where to start. In general we want to minimize the redundancy of our data while maximizing the relevancy. As you can imagine this is a tradeoff: if we keep all the data, then we’ll know 100% that we have relevant data whereas if we reduce some number of dimensions we might have redundancy—especially if we have lots and lots of dimensions.

We have talked about this before as being an entanglement problem with having too many data points that point to the same thing.

In general, redundancy and relevancy are calculated using the same metrics and on a spectrum:

• Correlation

• Mutual information

• Distance from some point (Euclidean distance from reference)

So they actually end up measuring the same thing. How do we solve this?

Let’s first take a step back and think about what would happen if we just looked at all possibilities.

Exhaustive Search

Let’s imagine that in this case we want to find the best possible dimensions to train on. We could realistically just search through all possibilities. In this case we have three dimensions which would equate to seven models (123, 12, 13, 23, 1, 2, 3). From here we could say that we want to find the model that has the highest accuracy (Figure 10-2).

Figure 10-2. Exhaustive search for best features

This unfortunately doesn’t work as well as you go up in dimensions. If for instance you have 10 dimensions, the possibilities from selecting 10 dimensions, to 1 dimension would be 2¹⁰ – 1. This can be denoted in Pascal’s triangle (Figure 10-3) as a sum of combinations where:

Figure 10-3. Pascal’s triangle

Pascal’s triangle shows all combinations for a given row. Since each row sums up to 2ⁿ, all we need to do is subtract 1, so we don’t account for zero dimensions.

So as you add dimensions you would have to account for 2ⁿ – 1 possible data sets. If you had 3,000 dimensions (which would be a good reason to use feature selection), you would have roughly a trecentillion (10⁹⁰³) models to run through!

Surely there is a better way. We don’t need to try every model. Instead, what if we just randomly selected features?

Random Feature Selection

A lot of the time random feature selection will be useful enough for our purposes. Reducing the features by half or a certain amount is an excellent way of improving data overfitting. The added benefit is that you really don’t have to think about it much and instead try out a random feature selection of a certain percent.

Say for instance you want to reduce the features by 25%. You could randomly see how it performs for accuracy, precision, or recall. This is a simple way of selecting features, but there is one major downside: what if training the model is slow? You are still brute-forcing your way to finding features. This means that you are arbitrarily picking a number and hoping for the best. Surely there is a better way.

A Better Feature Selection Algorithm

Instead of relying on random feature selection, let’s think a little more in terms of what we want to improve with our model. We want to increase relevancy while reducing redundancy. Relevancy is a measure of how relevant the dimension in question is versus the classification whereas redundancy is a measure of how redundant the dimension is compared to all the other dimensions. Usually for relevancy and redundancy you either use correlation or mutual information.

Correlation is useful for data that is continuous in nature and not nominal. By contrast, mutual information gives us a discrete measure of the mutual information shared between the two dimensions in question.

Using our earlier example, correlation would look like the results in Table 10-2 for relevancy and Table 10-3 for redundancy.

As you can see from these two tables, ice cream is highly correlated with temperature and my coffee consumption is somewhat negatively correlated with temperature; the month seems irrelevant. Intuitively we would think month would make a huge difference, but since it runs on a modular clock it’s hard to model using linear approximations. The redundancy is more interesting. Taken out of context my coffee consumption and month seem to have low redundancy, while coffee and ice cream seem more redundant.

So what can we do with this data? Next I’m going to introduce a significant algorithm that brings this all together.

Minimum Redundancy Maximum Relevance Feature Selection

To bring all of these competing ideas together into one unified algorithm there is minimum redundancy maximum relevance (mRMR) feature selection, which aims to maximize relevancy while minimizing redundancy. We can do this using a maximization (minimization) problem using NumPy and SciPy.

In this formulation we can just minimize the following function:

More importantly in code we have:

from scipy.optimize import minimize
import numpy as np

matrix = np.array([
  [47, 4.1, 2, 1],
  [50, 4, 2, 2],
  [54,4,3,3],
  [58,4,3,4],
  [65,4,3,5],
  [70,4,3,6],
  [76,4,4,7],
  [76,4,4,8],
  [71,4,4,9],
  [60,4,3,10],
  [51,4,2,11],
  [46,4.1,2,12]
])

corrcoef = np.corrcoef(np.transpose(matrix))
relevancy = np.transpose(corrcoef)[0][1:]

# Set initial to all dimensions on
x0 = [1,1,1]

# Minimize the redundancy minus relevancy

fun = lambda x: sum([corrcoef[i+1, j+1] * x[i] * x[j] for i in range(len(x)) 
                     for j in range(len(x))])/ 
                     (sum(x) ** 2) - 
                     (sum(relevancy * x) / sum(x))

res = minimize(fun, x0, bounds=((0,1), (0,1), (0,1)))

res.x

array([ 0.29820206,  1.        ,  0.1621906 ])

This gives us almost exactly what we expected: my ice cream consumption models the temperature quite well. For bonus points you could use an integer programming method to get the values to be either 0 or 1, but for these purposes it’s obvious which features should be selected to improve the model.

Principal Component Analysis

Principal component analysis (PCA) has been around for a long time. This algorithm simply looks at the direction with the most variance and then determines that as the first principal component. This is very similar to how regression works in that it determines the best direction to map data to. Imagine you have a noisy data set that looks like Figure 10-4.

Figure 10-4. Graphical PCA from Gaussian

As you can see, the data has a definite direction: up and to the right. If we were to determine the principal component, it would be that direction because the data is in maximal variance that way. The second principal component would end up being orthogonal to that, and then over iterations we would reduce our dimensions by transforming them into these principal directions.

Another way of thinking about PCA is how it relates to faces. When you apply PCA to a set of faces, an odd result happens known as the Eigenfaces (see Figure 10-5).

Figure 10-5. Eigenfaces (Source: AT&T Laboratories)

While these look quite odd, it is fascinating that what comes out is really an average face summed up over all of the training data. Instead of implementing PCA now, we’ll wait until the next section where we implement an algorithm known as independent component analysis (ICA), which actually relies on PCA as well.

Independent Component Analysis

Imagine you are at a party and your friend is coming over to talk to you. Near you is someone you hate who won’t shut up, and on the other side of the room is a washing machine that keeps making noise (see Figure 10-6).

Figure 10-6. Cocktail party example

You want to know what your friend has been up to, so you listen to her closely. Being human, you are adept at separating out sounds like the washing machine and that loudmouth you hate. But how could we do that with data?

Let’s say that instead of listening to your friend, you only had a recording and wanted to filter out all of the noise in the background. How would you do something like that? You’d use an algorithm called ICA.

Technically, ICA minimizes mutual information, or the information shared between the two variables. This makes intuitive sense: find me the signals in the aggregate that are different.

Compared to our face recognition example in Figure 10-5, what does ICA extract? Well, unlike Eigenfaces, it extracts features of a face, like noses, eyes, and hair.

PCA and ICA are useful for transforming data and can analyze information even better (see Figure 10-7). Then we can use this more succinct data to feed our models more useful and relevant information, which will improve our models beyond just cross-validation.

Figure 10-7. ICA extraction example

Now that we know about feature transformation and feature selection, let’s discuss what we can do in terms of better arguing for a classiciation or regression point.

Bagging

Bagging or bootstrap aggregation has been a very useful technique. The idea is simple: take a training set and generate new training sets off of it.

Let’s say we have a training set of data that is 1,000 items long and we split that into 50 training sets of 100 a piece. (Because we sample with replacement, these 50 training sets will overlap, which is okay as long as they are unique.) From here we could feed this into 50 different models.

Now at this point we have 50 different models telling us 50 different answers. Like the weather report just mentioned, we can either find the one we like the most or do something simpler, like average all of them.

This is what bootstrap aggregating does: it averages all of the models to yield the average result off of the same training set. The amazing thing about bagging is that in practice it ends up improving models substantially because it has a tendency to remove some of the outliers.

But should we stop here? Bagging seems like a bit of a lucky trick and also not very elegant. Another ensemble learning tool is even more powerful: boosting.

Boosting

Instead of splitting training data into multiple data models, we can use another method like boosting to optimize the best weighting scheme for a training set.

Given a binary classification model like SVMs, decision trees, Naive Bayesian Classifiers, or others, we can boost the training data to actually improve the results.

Assuming that you have a similar training set to what we just described with 1,000 data points, we usually operate under the premise that all data points are important or that they are of equal importance. Boosting takes the same idea and starts with the assumption that all data points are equal. But we intuitively know that not all training points are the same. What if we were able to optimally weight each input based on what is most relevant?

That is what boosting aims to do. Many algorithms can do boosting but the most popular is AdaBoost.

To use AdaBoost we first need to fix up the training data just a bit. There is a requirement that all training data answers are either 1 or –1. So, for instance, with spam classification we would say that spam is 1 and not spam is –1. Once we have changed our data to reflect that, we can introduce a special error function:

This function is quite interesting. Table 10-4 shows all four cases.

As you can see, when f(x) and y equal, the error rate is minimal, but when they are not the same it is much higher.

From here we can iterate through a number of iterations and descend on a better weighting scheme using this algorithm:

• Choose a hypothesis function (either SVMs, Naive Bayesian Classifiers, or something else)

  • Using that hypothesis, sum up the weights of points that were missclassified:

    $ϵ={\sum }_{h\left(x\right)\ne y}w$

  • Choose a learning rate based on the error rate:

    $\alpha =\frac{1}{2}ln\left(\frac{1-ϵ}{ϵ}\right)$

• Add to the ensemble:

  $F\left(x\right)=F_{t-1}\left(x\right)+\alpha h_t\left(x\right)$

• Update weights:

  $w_{i,t+1}=w_{i,t}{e}^{-y_i{\alpha }_t{h}_t\left(x_i\right)}$

  for all weights

• Renormalize weights by making sure they add up to 1

What this does is converge on the best possible weighting scheme for the training data. It can be shown that this is a minimization problem over a convex set of functions.

This meta-heuristic can be excellent at improving results that are mediocre from any weak classifier like Naive Bayesian Classification or others like decision trees.