Introduction to Machine Learning

1. Introduction

More features are not more information. As dimensionality grows, data becomes sparse, distances lose their meaning, and models that rely on locality — KNN above all — degrade badly. This chapter opens with that problem, the curse of dimensionality, and then develops the first family of answers: choosing a subset of the features you already have.

We cover filter methods, which score features independently of any model using statistical tests — variance threshold, chi-square, ANOVA F-test, — and then wrapper methods, which judge a feature subset by the performance of an actual trained model. Forward selection and backward elimination illustrate the trade-off: wrappers capture feature interactions that filters cannot see, but pay for it with a combinatorial search. The companion chapter takes the other route, constructing new features rather than selecting old ones — for example, combining height and weight into a single new feature, BMI, rather than just picking one of the two original columns. Feature selection, by contrast, always keeps the original variables intact; it only decides which ones to keep.

2. Theory

2.1 Curse of Dimensionality

Adding more features to a dataset is not free. Beyond a certain point extra features stop helping, and for distance-based methods such as KNN they actively cause problems, for reasons that are geometric rather than statistical.

2.2 The Hypercube Thought Experiment

Consider the following concrete example. All features are uniformly distributed over [0, 1]. We want to classify a query at X = 0.6 using the 10% nearest neighbors rule (use only training samples whose features all fall within ±5% of the feature range, i.e., 10% of the axis length):

2.3 The Feature Selection Problem

The curse of dimensionality tells us that too many features cause problems, so the natural response is to keep only a useful subset of them. We first state that task precisely.

Given a feature matrix \(X \in \mathbb{R}^{n \times d}\) with \(n\) samples and \(d\) features, and target variable \(y \in \mathbb{R}^n\), our goal is to select a subset \(S \subseteq \{1, 2, ..., d\}\) such that features in \(S\) are most predictive of \(y\).

2.4 Filter vs Wrapper Methods

Because exhaustive search is impossible, practical methods fall into two families that differ in how they judge a feature. Filter methods score each feature with a statistical test, independently of any model. Wrapper methods judge a subset by training a model on it and measuring how well it performs.

Note: A third category called "Embedded Methods" (e.g., LASSO, Random Forest feature importance) exists where feature selection happens during model training.

2.5 How Filter Methods Work

All filter methods share the same three-step procedure, and they differ only in the statistical score used in the first step:

1. Calculate a statistical score for each feature independently
2. Rank features by their scores (higher = better)
3. Select top-k features or apply a threshold
4. Train the model on the selected features

2.6 Variance Threshold

The simplest filter method removes features with very low variance:

• Constant feature: All rows have the same value (variance = 0) — always dropped.
• Quasi-constant feature: Nearly all rows have the same value — dropped if variance < threshold. For example, a column where 995 out of 1,000 rows have value 1 and only 5 rows have value 0 is quasi-constant: it varies just barely, and that near-constant variance is exactly what the threshold is designed to catch.

Important: Standardization or normalization is required before applying variance threshold so that the same threshold works for all features. A threshold between 0.01 and 0.1 is generally effective.

from sklearn.feature_selection import VarianceThreshold

selector = VarianceThreshold(threshold=0.01)
X_selected = selector.fit_transform(X)

2.7 Chi-Square (\(\chi^2\)) Filter

The Chi-Square test measures the association between one input column and one output column. Both columns must be categorical. For example, is there a relationship between the "Gender" column and the "Education" column? The contingency table (also called a "crosstab") below shows the frequency of each combination of values between the two columns:

Where \(c\) is the degree of freedom, \(O_i\) is the observed frequency, and \(E_i\) is the expected frequency in cell \(i\).

The expected frequency is computed as:

from sklearn.feature_selection import SelectKBest, chi2

# Method 1: Select top-k features
selector = SelectKBest(score_func=chi2, k=5)
X_selected = selector.fit_transform(X_categorical, y)

# Method 2: Select features above threshold
selector_threshold = SelectKBest(score_func=chi2, k='all')
selector_threshold.fit(X_categorical, y)

# Filter by p-value threshold
significant_features = selector_threshold.pvalues_ < 0.05
X_significant = X_categorical.iloc[:, significant_features]

2.8 ANOVA F-Test

ANOVA (Analysis of Variance) is used when:

• Input features are continuous/numerical
• Target variable is categorical

Where \(K\) = number of classes, \(N\) = total samples.

Higher F-statistic indicates greater difference between class means, making the feature more informative.

from sklearn.feature_selection import SelectKBest, f_classif

# Apply ANOVA F-test to all numerical features
selector = SelectKBest(score_func=f_classif, k=5)
X_selected = selector.fit_transform(X_numerical, y)

# Get F-scores and p-values
f_scores = selector.scores_
p_values = selector.pvalues_

2.9 Comparison of Filter Methods

The four filter methods above apply to different combinations of feature and target type. The table below summarises when each one is appropriate.

2.10 Wrapper Methods

Filter methods score each feature on its own, so they cannot see that two features are useful only in combination. Wrapper methods address this by evaluating whole subsets.

Wrapper methods use a predictive model to evaluate feature subsets, using model performance as the selection criterion.

Common wrapper methods:

• Forward Selection
• Backward Elimination
• Recursive Feature Elimination (RFE)

2.11 Forward Selection

Forward Selection is a greedy algorithm that builds the feature set incrementally:

1. Start with an empty feature set (Null Model)
2. Iteratively add features that improve model performance the most
3. In essence, we fit p simple models (one for each feature) and record each case's accuracy. The feature that produces the best evaluation metric is locked in.
4. We then add the remaining p-1 features to this feature and select the combination that results in the best evaluation metric at stage 2.
5. This approach is continued until some stopping rule is satisfied (e.g., desired number of features, no improvement in performance)

2.12 Backward Selection

Backward Selection is the reverse of Forward Selection:

1. Start with all features (Full Model)
2. Iteratively remove features that hurt performance the least
3. In essence, we explore different (p - 1) feature combinations and retain the one with the best evaluation score.
4. From these (p - 1) features, we form pairs of (p - 2) variables, train the model and retain the one with the best evaluation score.
5. This procedure continues until a stopping rule is reached.

2.13 Computational Complexity

The computational cost of filter vs. wrapper methods:

2.14 Filter vs Wrapper Comparison

Having seen both families in detail, we can now summarise the trade-off between them:

3. Interactive Examples

Example 1: Understanding the Search Space

Example 2: Chi-Square Test in Action

Example 3: Curse of Dimensionality — Hypercube Neighborhood Size

Example 4: Forward vs Backward Selection

4. Numerical Solutions

Problem 1: Complete Chi-Square Calculation

Problem 2: Forward Selection Trace

Problem 3: KNN and Dimensionality

5. Try It Yourself

6. Interactive Quiz

Answer all 8 questions. Click an option for instant feedback.