Information Theory for Feature Relevance and Interaction

Hello! Welcome to the third lesson in our course on advanced feature engineering.

Introduction

In our previous lesson, we diagnosed and treated multicollinearity, a problem concerning relationships between features. We learned to use tools like VIF and Principal Component Regression to handle redundant information.

Today, we pivot from feature-feature relationships to a more fundamental question: what is the relationship between a given feature and the target variable we are trying topredict? We'll move beyond simple correlation and explore this from a first-principles perspective using the powerful language of information theory.

The learning outcome for this lesson is to analyze the role of information theory (mutual information, entropy) in quantifying feature relevance and interaction. By the end of this lesson, you'll be able to precisely measure how much "information" a feature contains about the target, even if their relationship is highly non-linear, and understand how this forms the basis for sophisticated feature selection algorithms.

From Uncertainty to Information: Core Concepts

At the heart of information theory, developed by Claude Shannon, is the idea of quantifying uncertainty. Let's start with a foundational concept: entropy.

In the context of data science, entropy, denoted as $H(X)$, is a measure of the uncertainty or unpredictability associated with a random variable $X$.

• A variable with high entropy is very unpredictable. Think of a fair coin flip; the outcome is maximally uncertain. For a feature, this would be a near-uniform distribution.
• A variable with low entropy is very predictable. If a coin is biased to always land on heads, there is zero uncertainty and thus zero entropy.

The video below provides an excellent introduction to these core concepts and how they are applied in machine learning. It carefully builds the intuition from uncertainty to information, entropy, and mutual information.

As the video explains, entropy gives us a number to describe the "messiness" of a single variable. But feature engineering is about relationships. To quantify them, we need to extend this idea to multiple variables.

Quantifying Shared Information

Let's consider two variables, a feature $X$ and our target $Y$. Information theory gives us a toolkit to describe their relationship.

1. Joint Entropy, $H(X,Y)$: The total uncertainty contained in the pair of variables $(X,Y)$. If $X$ and $Y$ are independent, $H(X,Y)=H(X)+H(Y)$. If they are dependent, the total uncertainty is less than the sum of the parts.

2. Conditional Entropy, $H(Y|X)$: The uncertainty that remains about $Y$ after we have observed $X$. This is a crucial concept. If knowing feature $X$ makes target $Y$ very predictable, then $H(Y|X)$ will be low.

3. Mutual Information, $I(X;Y)$: This is the star of the show. It measures the reduction in uncertainty about $Y$ that results from knowing $X$. It's the information they share. It can be defined in several equivalent ways:

   $$I(X;Y)=H(Y)-H(Y|X)(\text{The original uncertainty minus the remaining uncertainty})$$ $$I(X;Y)=H(X)-H(X|Y)(\text{It’s symmetric!})$$ $$I(X;Y)=H(X)+H(Y)-H(X,Y)$$

The relationship between these quantities is beautifully illustrated by a Venn diagram.

Let's return to the video to see how these concepts are connected and calculated.

Mutual Information vs. Correlation

A critical advantage of mutual information over Pearson correlation is its ability to capture non-linear relationships. Correlation only measures the strength of a linear association. A U-shaped relationship would have a correlation near zero, but a high mutual information, as knowing the value of one variable significantly reduces the uncertainty about the other.

The video makes this exact comparison, which is essential for understanding why MI is a more general and powerful tool for assessing feature relevance.

A Principled Framework for Feature Selection

Now we can use these tools to formalize the goals of feature selection.

• Relevance: We want features that share a lot of information with the target. This can be measured by a high $I(X_i;Y)$.
• Redundancy: We don't want features that contain the same information. This can be measured by a high $I(X_i;X_j)$ between two features.
• Complementarity (or Synergy): This is a more advanced concept. Two features $X_i$ and $X_j$ might be weakly informative on their own, but highly informative when combined. This means they provide synergistic, or complementary, information. This is captured by conditional mutual information.

The following paper provides a superb review of these concepts and unifies many famous feature selection algorithms under a single theoretical framework. Given your interest in a deep understanding, this is a central resource for this lesson.

The Ideal vs. The Practical

Ideally, in a greedy forward search for the best feature set $S$, we would add the feature $X_k$ that maximizes the new information it brings, given what we already know. This is captured by the criterion:

$$J(X_k)=I(X_k;Y|S)$$

This term measures the mutual information between the candidate feature $X_k$ and the target $Y$, conditioned on the set of already selected features $S$.

However, estimating this high-dimensional conditional mutual information is computationally difficult and requires vast amounts of data. As a result, many popular feature selection algorithms are actually clever approximations of this ideal criterion.

A seminal paper by Brown et al. (2012), which we are providing as LINK and is the foundation for the review paper you just read, showed that $I(X_k;Y|S)$ can be expanded as:

$$I(X_k;Y|S)=\underset{\text{Relevance}}{\underbrace{I(X_k;Y)}}-\underset{\text{Redundancy}}{\underbrace{I(X_k;S)}}+\underset{\text{Synergy/Complementarity}}{\underbrace{I(X_k;S|Y)}}$$

This elegant formula shows that the ideal feature is one that is highly relevant, has low redundancy with existing features, and high synergy.

Different algorithms are born from how they approximate this equation:

• MIM (Mutual Information Maximization): Keeps only the relevance term, $I(X_k;Y)$. Fast but selects redundant features.
• MRMR (Max-Relevance Min-Redundancy): Approximates the redundancy term as an average of pairwise redundancies and ignores the synergy term. A very popular and effective trade-off. $$J_{mrmr}(X_k)=I(X_k;Y)-\frac{1}{|S|}\sum _{X_j\in S}I(X_k;X_j)$$
• JMI (Joint Mutual Information): Another approximation that tries to balance redundancy and synergy.

Understanding that these heuristics are principled approximations of an ideal objective function provides the deep insight you're looking for.

To see how these algorithms are used, let's look at the final part of our main video resource.

Interview & Business Context Alert

Question: "You have a dataset with hundreds of features. How would you select a smaller, more effective subset of features for your model in a way that is model-agnostic?"

Your Analysis: "My primary approach would be to use a filter method based on mutual information. Unlike correlation, mutual information can capture complex, non-linear dependencies between features and the target. I would start by calculating the mutual information between each feature and the target to measure relevance.

To avoid selecting a set of highly correlated features, I would use an algorithm like MRMR (Maximum Relevance, Minimum Redundancy). This method iteratively builds a feature set by selecting features that are highly relevant to the target while being minimally redundant with the features already selected.

This is a principled approach because MRMR is a practical approximation of the ideal, but computationally expensive, goal of maximizing the conditional mutual information $I(X_k;Y|S)$. It provides a robust, model-independent feature set that balances predictive power with compactness."

Conclusion

In this lesson, we ventured into information theory to build a model-agnostic framework for understanding feature value. We moved beyond simple correlations to a more fundamental measure of statistical dependence.

Key Takeaways:

• Entropy $H(X)$ quantifies the uncertainty of a variable.
• Mutual Information $I(X;Y)$ measures the information shared between two variables—or the reduction in uncertainty about one, given the other. It is a powerful tool that captures both linear and non-linear relationships.
• We can formalize feature selection goals using MI:
  • Relevance: $I(\text{feature};\text{target})$
  • Redundancy: $I({\text{feature}}_i;{\text{feature}}_j)$
  • Synergy: Captured by conditional mutual information.
• Many well-known feature selection algorithms like MRMR are practical approximations of an ideal information-theoretic objective, balancing the trade-off between maximizing relevance and minimizing redundancy.

What's Next?

We've now seen how to quantify statistical relationships using both linear models (multicollinearity) and information theory (mutual information). However, a strong statistical relationship does not imply a causal one. In our next lesson, we will confront this critical distinction head-on by exploring the difference between correlation and causation in the context of feature creation, a concept that is paramount for building interpretable and reliable models.