7 concepts22 worked examples30 exercises4 exam-level7 figures
What are you here for?
11 Feature selection: ranking by correlation and mutual information, mRMR, best subset and forward stepwise
Start with this
One question before you read anything. Getting it wrong is the point: it shows you what this section is for.
§11.1 — two measurements to keep for a solar panel
A solar installation can keep only two of four measurements to predict daily energy $y$ with a straight-line model. Over 30 days their sample correlations with $y$ were computed.
Find(a) Which two measurements should be kept?
Givencloud cover $-0.9$, air temperature $0.3$, hours of daylight $0.6$, panel serial number $0.1$
Hint 1/4
Decide what makes a correlation strong before comparing the four numbers.
Hint 2/4
The strength of a straight-line trend is $\lvert\hat R_j\rvert$, or equally $\hat R_j^2$; the sign is only its direction.
Hint 3/4
Here the sizes are $0.9$, $0.3$, $0.6$ and $0.1$ for cloud cover, air temperature, daylight and serial number.
Hint 4/4
The two largest are cloud cover and daylight.
Show solution
For a straight-line model a feature's fit alone depends only on $\hat R_j^2$, so squaring is the whole method.
Answer $$\boxed{\text{cloud cover and daylight}}$$
Check
Each alone leaves the fraction $1-\hat R_j^2$ of the spread of $y$ unexplained: $0.19$ and $0.64$ for the two kept, $0.91$ and $0.99$ for the others.
A negative correlation is a direction, not a weakness.
A wafer fab can afford to log only two of its four sensors. The furnace thermometer and a backup thermometer are each the best single predictor of a defective wafer, so keeping both looks safe. Yet together they predict no better than one of them, while one thermometer and the humidity sensor explain every one of the 16 wafers.
By the end you can score features by correlation and by , pick $k$ of them with in a few subtractions, and choose a model size by cross-validation instead of by training error.
In 60 seconds
keeps $k$ of the $p$ original features. Ranking scores each feature from the data alone, mRMR adds features by relevance minus redundancy, and best subset and forward stepwise train the model on subsets and let cross-validation choose the size.
choosing between the two; the size is then picked by cross-validation
Three most common mistakes
Ranking by the signed correlation: $-0.9$ is a strong feature. Score by $\hat R_j^2$.
Adding relevances or keeping near copies: two thermometers tell no more than one. Use mRMR or a joint score.
Choosing the model size by training RSS or $R^2$, which always favour the largest model. Use cross-validation.
Two course documents give different weights:
Chapter 1 slides, undergraduate line: midterm 25, final 25, four quizzes 20, two-phase project 30.
STARS syllabus page printed on 21 September 2026: midterm 30, final 30, problem sets and quizzes 20, project 20. It is the later document; confirm which split applies.
The STARS weekly list has feature extraction and feature selection as its ninth item; the lecture slides make feature selection chapter 11.
How much time do you have?
10 minutes
The squared-correlation score, mRMR on the wafer sensors, and the rule that cross-validation, not RSS, picks the size.
The 60-second card · Ranking features by a score, with correlation as the score · Minimum redundancy, maximum relevance (mRMR) · Best subset selection, with the size chosen by cross-validation · Formula card
45 minutes
Every method once with a worked example, then mRMR by hand from a full solution down to a bare problem.
The 60-second card · Ranking features by a score, with correlation as the score · Mutual information · Maximum relevance · Maximum dependency, exhaustively and by incremental search · Minimum redundancy, maximum relevance (mRMR) · Best subset selection, with the size chosen by cross-validation · Forward stepwise selection · Scaffolding comes off · Formula card
full read
Adds the proofs, the look-alike pairs, a full exam-style question and mixed practice where you pick the method yourself.
The opening pages · Recall first · Ranking features by a score, with correlation as the score · Mutual information · Maximum relevance · Maximum dependency, exhaustively and by incremental search · Minimum redundancy, maximum relevance (mRMR) · Best subset selection, with the size chosen by cross-validation · Forward stepwise selection · Method boxes · Look-alike pairs · Scaffolding comes off · Full exam-style question · Practice set · Check yourself
By the end of this section
Rank features by a score and build the reduced data set; compute $\hat R_j$ from data and score by $\hat R_j^2$.
Compute , and mutual information from a table, by the definition and by $H(Y)-H(Y\mid X)$.
Explain why maximum relevance fails on near copies and on features that only work together.
Run maximum dependency exhaustively and by incremental search, count their evaluations, and judge when a joint estimate can be trusted.
Apply mRMR step by step from tables of relevance and pairwise mutual information.
Select a model by best subset selection and choose its size by cross-validation, not by RSS or $R^2$.
Compare forward stepwise with best subset selection: the path, the number of fits, and when the greedy path misses.
Syllabus coverage
covered
Feature selection — covered
Selecting k of the p original features
and the reduced data set
the correlation score
entropy and mutual information
maximum relevance
maximum dependency and its incremental search
minimum redundancy maximum relevance (mRMR)
best subset selection with the size chosen by cross-validation
forward stepwise selection
Both halves of the weekly line name it: the lecturer's chapter title and the ninth item of the official list. The blocks follow the lecture's order.
covered
Feature extraction — covered
Building new features out of the old ones, as PCA does, set against keeping a subset of the original ones.
The extraction method itself, PCA, was taught with ICA in the section on blind source separation. Here it is the contrast the lecture draws at the start of the chapter, and it returns in an interleaved practice question.
covered
The lecture's comparison on gene data — covered
Maximum dependency against mRMR on a gene expression data set with 60 samples, 9703 genes and 9 cancer classes: mRMR selects features faster, and with many selected features it classifies more accurately, measured by leave-one-out cross-validation with a naive Bayes classifier, because joint mutual information is hard to estimate from 60 samples.
The lecture's plots are not reproduced. The estimation problem behind them is shown by a simulation in the maximum dependency block, and the choice of method at this scale is an exam-level practice question.
off syllabus
Selecting features inside each cross-validation fold — off syllabus
Any selection step that looks at the labels has to be repeated inside each fold, or the error estimate comes out too low.
Further reading, not in the lecture: it appears in one interleaved practice question only.
Recall first
Covariance and centered sums
$\operatorname{Cov}(X,Y)=E[(X-E[X])(Y-E[Y])]$. From data, $S_{xy}=\sum_i(x_i-\bar x)(y_i-\bar y)$ and $S_{xx}=\sum_i(x_i-\bar x)^2$.
The correlation score is built from these sums.
Least squares with one feature
$\hat\beta_1=S_{xy}/S_{xx}$, $\hat\beta_0=\bar y-\hat\beta_1\bar x$, and the residual sum of squares is $\mathrm{RSS}=S_{yy}-S_{xy}^2/S_{xx}$.
It shows that ranking by $\hat R_j^2$ is ranking by one-feature fit.
Joint, marginal and conditional pmf; independence
$p(x)=\sum_yp(x,y)$ and $p(y\mid x)=p(x,y)/p(x)$. $X$ and $Y$ are independent when $p(x,y)=p(x)p(y)$ for every $x$ and $y$; zero covariance does not imply it.
Mutual information is built from these three pmfs and is zero exactly at independence.
Least squares with several features
$\hat\beta$ minimizes $\mathrm{RSS}(\beta)=\sum_i\big(y_i-\beta_0-\sum_jx_{ij}\beta_j\big)^2$ over all coefficient vectors; the model with no features predicts $\bar y$.
Best subset and forward stepwise compare these fits across subsets.
Cross-validation
Leave-one-out: $\mathrm{CV}(n)=\frac1n\sum_i\big(y_i-\hat f_{D_i}(x_i)\big)^2$, each point predicted by a fit that never saw it; $k$-fold does the same with $k$ folds. Training error falls with flexibility, cross-validation error need not.
It is the fair judge between models of different sizes.
Lasso and PCA
Lasso minimizes $\mathrm{RSS}+\lambda\sum_j\lvert\beta_j\rvert$ and sets some coefficients of one linear model exactly to $0$. PCA builds scores $z_{im}=x_i^Tu_m$, each a combination of all $p$ features, without looking at $y$.
They are the two tools the chapter starts from, and the contrast for feature ranking.
Try it yourself first (2 questions)
1§11.2 — uncorrelated but dependent
A variable $x$ takes the values $-1$, $0$ and $1$ with probability $\tfrac13$ each, and $y=x^2$. A classmate computes $\operatorname{Cov}(x,y)=0$ and concludes that $x$ and $y$ are independent.
Find(a) Are $x$ and $y$ independent?
Given
$P(x=-1)=P(x=0)=P(x=1)=\tfrac13$
$y=x^2$
$\operatorname{Cov}(x,y)=E[x^3]-E[x]E[x^2]=0$
Hint 1/4
Independence is a statement about every pair of values, not about one summary number.
Hint 2/4
$x$ and $y$ are independent only if $P(y\mid x)=P(y)$ for every $x$ and $y$.
Hint 3/4
Here $P(y=0)=\frac13$, since only $x=0$ gives $y=0$, while $P(y=0\mid x=0)=1$.
Hint 4/4
The two differ, so $x$ and $y$ are dependent although uncorrelated.
Show solution
One cell where the product rule fails is enough to refute independence.
Edge case: if the new column copies an old feature or the constant, the fit cannot change and RSS stays at $40.0$; the bound is reached, never exceeded.
Training error can only fall as features are added, so it cannot decide how many to keep.
Notation
symbol
reads as
means
watch out
$D=\{(x_i,y_i)\}_{i=1}^n,\ \ x_i\in\mathbb R^p$
the data set
$n$ labelled samples with $p$ features
$y_i$ may be a class label or a number.
$X=(X_1,\dots,X_p),\ \ Y$
the random features, the random label
$(X,Y)\sim P$, sampled independently
Capital letters for random variables, small ones for observed values.
$s_j,\ \ (j)$
the score of feature j; the feature ranked j-th
$s_{(1)}\ge s_{(2)}\ge\dots\ge s_{(p)}$
$(j)$ is a place in the ranking, $j$ a feature's index.
$\tilde D$
D tilde
the data restricted to the $k$ kept features
Same samples and labels, fewer columns.
$\hat R_j$
R hat j
the sample correlation of feature $j$ with $y$
Between $-1$ and $1$; the score is its square.
$H(Y),\ \ H(Y\mid X)$
entropy of Y; conditional entropy of Y given X
the uncertainty about $Y$ before and after $X$ is seen, in bits
$H(Y\mid X)$ averages over $x$ with weights $p(x)$.
$I(X;Y)$
mutual information of X and Y
$H(Y)-H(Y\mid X)$
Symmetric and never negative; at most $\min(H(X),H(Y))$.
$S,\ \ I(S;Y)$
a feature subset; its joint information with Y
the features in $S$ taken as one random vector
Needs the joint pmf of $\lvert S\rvert+1$ variables.
$\mathcal A,\ \ S^*$
all k-subsets; the maximum dependency subset
$\lvert\mathcal A\rvert=\binom pk$
Exhaustive search visits every member of it.
$S_l,\ \ X_l^*$
the set after step l; the feature added at step l
$S_l=S_{l-1}\cup\{X_l^*\}$ with $S_0=\emptyset$
Used by incremental search, mRMR and forward stepwise.
$M_0,\ \ M_k$
the ; the best model with k features
$M_0$ predicts $\bar y$; $M_k$ has the smallest RSS among models with $k$ features
The lecture's slides write $m_k^*$ for $M_k$.
$\mathrm{RSS},\ \ \mathrm{TSS},\ \ R^2$
residual and total sums of squares; R squared
$R^2=1-\mathrm{RSS}/\mathrm{TSS}$
Training quantities: they improve with every added feature.
$\mathrm{CV}(n),\ \ \mathrm{CV}(k)$
leave-one-out and k-fold errors
estimates of test error
The fair judge between model sizes.
Conventions used here
Logarithms and units.
$\log$ is base 2, so entropy and mutual information are in bits; $0\log0=0$.
The lecture writes log without a base. Natural logs give nats, 1 nat = 1.443 bits; rankings do not change, but never mix the two in one table.
.
Probabilities are replaced by counts over $n$; every mutual information computed from data on this page is a plug-in estimate.
It is the simplest estimate, and the one the lecture's warning about small samples applies to.
Ties.
When two features have the same score, the one with the lower index is taken.
The lecture does not fix a rule; a fixed one makes answers comparable.
Rounded tables.
Mutual information tables are given to two decimals, and mRMR is run on the rounded values.
In every worked example the winner beats the runner-up by more than the rounding, so the path does not depend on it.
Relevance and redundancy.
Relevance is $I(X;Y)$; the redundancy of a candidate is the average of $I(X;X')$ over the features already chosen.
This is the lecture's mRMR penalty; other texts use other penalties.
Least squares models.
Every model in the last two blocks is least squares with an intercept, and $M_0$ predicts $\bar y$.
RSS values are comparable only within one family of models.
Choosing the size.
Models of different sizes are compared by cross-validation error, never by training RSS or $R^2$.
Training fit improves with every added feature.
Correlation score.
$s_j=\hat R_j^2$, as in the lecture; ranking by $\lvert\hat R_j\rvert$ gives the same order.
Squaring removes only the sign; the order of the sizes is kept.
Counting evaluations.
An evaluation is one estimate of a mutual information or one least squares fit; the null model counts as a fit.
The counts on this page, such as $1+p(p+1)/2$, use this convention.
11.1Ranking features by a score, with correlation as the score
Keeps the $k$ original features with the largest scores; with correlation the score is $\hat R_j^2$, so strong negative features stay.
Lasso picked features inside one linear model, and PCA replaced all $p$ features by mixtures; here we keep $k$ of the original columns and let the label choose them.
Solvable with what we have
Fit least squares on all $p$ features, as long as $n>p$.
Let lasso set some coefficients of one linear model to $0$, for one $\lambda$.
Compress the features into $k$ principal components, each a mixture of all $p$.
Compute each feature's sample correlation with $y$.
Not solvable yet
Choose $k$ original features once, before any model is trained, and hand them to any learner.
Keep the measurements readable: a doctor can act on two gene readings, not on a mixture of 9703.
Turn four correlations into a keep or drop decision that the sign does not distort.
Rank by $\hat R_j$ itself. The solar data give $\hat R=(-0.9,\ \textcolor{#8250df}{0.3},\ \textcolor{#8250df}{0.6},\ 0.1)$, so the top two are daylight ($0.6$) and air temperature ($0.3$), and cloud cover comes last.
Why it fails
The sign says which way $y$ moves, not how well $x_j$ predicts it: cloud cover at $-0.9$ is the strongest of the four. Squaring gives $0.81,\ \allowbreak 0.09,\ \allowbreak 0.36,\ \allowbreak 0.01$ and keeps cloud cover and daylight.
MethodMethod 11.1: Feature ranking with the correlation score
Conditions
$D=\{(x_i,y_i)\}_{i=1}^n$ with $x_i\in\mathbb R^p$ and a label $y_i$
$(j)$ is the index of the feature with the $j$-th largest score, as in the lecture
Score every feature, sort the scores, and keep the columns with the $k$ largest; the reduced data set $\tilde D$ goes to any learner. With correlation the score is the square of the sample correlation, so a feature that moves against $y$ counts as much as one that moves with it.
Why the square is the right score
One feature, one line. The least squares line of $y$ on $x_j$ alone has slope $S_{jy}/S_{jj}$ and leaves $\mathrm{RSS}_j=S_{yy}-S_{jy}^2/S_{jj}$.
The same number, rescaled. Dividing by $S_{yy}$ gives $\mathrm{RSS}_j/S_{yy}=1-\hat R_j^2$.
So the ranking is by fit. A larger $\hat R_j^2$ means a smaller one-feature RSS, whatever the sign of $\hat R_j$; ranking by $\lvert\hat R_j\rvert$ gives the same order.
The four correlations of the first worked example. The purple dashed outlines mark the two largest signed values; the blue bars are the two largest squares, $\textcolor{#1f6feb}{0.81}$ and $\textcolor{#1f6feb}{0.36}$. Cloud cover points down because more cloud means less energy, not because it says less about $y$.
Looks like this, but is not
A feature with $\hat R_j=0$ looks useless, and a correlation screen would drop it.
Correlation sees straight-line trends only. For $x=-1, \allowbreak -1, \allowbreak 0, \allowbreak 0, \allowbreak 1, \allowbreak 1$ and $y=x^2$ the correlation is exactly $0$, yet $x$ fixes $y$. The next block's score catches this.
feature
correlation
score
RSS alone
$x_1$ cloud
$-0.9$
$0.81$
$19$
$x_2$ air temp.
$0.3$
$0.09$
$91$
$x_3$ daylight
$0.6$
$0.36$
$64$
$x_4$ serial no.
$0.1$
$0.01$
$99$
Sorting by the score and sorting by the one-feature RSS give the same order: $x_1$, $x_3$, $x_2$, $x_4$.
Ranking four solar panel measurements by squared correlation
A solar installation logs 30 days. For the daily energy $y$ (kWh), $S_{yy}=100$. The sums for four measurements are listed below. Keep the best two by the correlation score.
Find$\hat R_j$ for each feature, the scores, and the two features kept.
Given
$x_1$ cloud cover: $S_{11}=25$, $S_{1y}=-45$
$x_2$ air temperature: $S_{22}=16$, $S_{2y}=12$
$x_3$ hours of daylight: $S_{33}=4$, $S_{3y}=12$
$x_4$ panel serial number: $S_{44}=9$, $S_{4y}=3$
$S_{yy}=100$
Solution
Three sums per feature are all the score needs, so no model is fitted; the sign is dropped on purpose by squaring.
One-feature least squares agrees: $\mathrm{RSS}_j=S_{yy}(1-\hat R_j^2)$ gives $19,\ 91,\ 64,\ 99$, and the two smallest belong to $x_1$ and $x_3$.
This answers the solar question that opens the page: square first, then sort. Cloud cover stays because its trend is strong, not because it points up.
Sample correlation of one feature from five raw readings
Five days of a sensor $x$ and an output $y$ were recorded: $x=(1,2,3,4,5)$ and $y=(5,3,4,2,1)$. Find $\hat R$ and the score $s=\hat R^2$.
Find$\hat R$ and $s$.
Given
$x=(1,2,3,4,5)$
$y=(5,3,4,2,1)$
Solution
Centering first keeps all three sums small and exact; the shortcut $\sum_ix_iy_i-n\bar x\bar y$ gives the same numbers with larger intermediate values.
The largest possible $\lvert S_{xy}\rvert$ is $\sqrt{S_{xx}S_{yy}}=10$, so $-9$ is close to a perfect downhill line.
Answer $$\boxed{\hat R=-0.9,\qquad s=0.81}$$
Check
The least squares slope is $S_{xy}/S_{xx}=-0.9$ and $\mathrm{RSS}=S_{yy}-S_{xy}^2/S_{xx}=10-8.1=1.9$, so $1-\mathrm{RSS}/S_{yy}=0.81$ matches the score.
Center, then three sums: the score never needs the slope, but the slope checks it.
Checkpoint
§11.1 — keeping two features by correlation
A screen of four features for a regression gives their sample correlations with $y$.
Entropy is the uncertainty in $Y$, in bits: one fair yes or no is one bit. Mutual information compares every cell of the joint table with the product of its margins; it equals the uncertainty about $Y$ that disappears, on average, once $X$ is known, and the same amount the other way round.
Why the four properties hold
Zero at independence. If $p(x,y)=p(x)p(y)$ in every cell, every ratio is $1$ and every logarithm is $0$.
Symmetric. Swapping the roles of $x$ and $y$ leaves the double sum unchanged.
The entropy form.$\log\frac{p(x,y)}{p(x)p(y)}=\log p(y\mid x)-\log p(y)$; summing against $p(x,y)$ gives $-H(Y\mid X)+H(Y)$.
Never negative. With $\ln t\le t-1$: $-I\ln2=\sum p(x,y)\ln\frac{p(x)p(y)}{p(x,y)}\le\sum p(x)p(y)-1\le0$, the sums running over cells with $p(x,y)>0$. Equality forces every ratio to be $1$, which is independence.
At most $H(Y)$. $H(Y\mid X)\ge0$, so $I(X;Y)\le H(Y)$: no feature tells more than the label's own uncertainty.
The one bit of uncertainty about a wafer's defect label, split for three sensors. The blue part is what the sensor removes, $\textcolor{#1f6feb}{I(X;Y)}$; the orange part is what is left, $\textcolor{#d1690a}{H(Y\mid X)}$. The furnace band removes half a bit, humidity $0.19$ bit, the shift nothing.
Looks like this, but is not
A column of wafer serial numbers gets the largest possible estimate: each number appears once, so every cell holds one wafer, $H(Y\mid X)=0$ and the estimate is $H(Y)=1$ bit.
Frequencies from one wafer per cell only memorize the labels; for a new wafer the serial number predicts nothing. Mutual information belongs to the distribution, and such a table does not estimate it. The problem returns with sets of features.
band X₁
humidity X₃
wafers
defective
low
dry
2
0
low
humid
2
0
normal
dry
4
0
normal
humid
4
4
high
dry
2
2
high
humid
2
2
Low bands never fail and high bands always do; a normal band fails exactly when the room is humid. The shift is spread evenly, so it carries no information about defects.
Mutual information between humidity and defects, from the definition
Of 16 wafers, 8 were processed dry and 8 humid. Among the dry ones 2 are defective; among the humid ones 6 are. Compute $I(X_3;Y)$ in bits from the definition.
Find$I(X_3;Y)$.
Given
counts: dry and good $6$, dry and defective $2$, humid and good $2$, humid and defective $6$
$n=16$
Solution
Four cells with simple ratios make the definition quick here; the entropy route is kept for the check.
Entropy route: $H(Y)=1$ bit, and each humidity group splits $3:1$, so $H(Y\mid X_3)=-\frac34\log\frac34-\frac14\log\frac14=0.811$ and $1-0.811=0.189$.
Plug-in mutual information is counts, margins, ratios and logs; the entropy route is the independent check.
Mutual information of the furnace band, by the entropy route
The furnace band $X_1$ is low for 4 wafers (all good), normal for 8 (4 good, 4 defective) and high for 4 (all defective). Compute $H(Y)$, $H(Y\mid X_1)$ and $I(X_1;Y)$.
Find$H(Y)$, $H(Y\mid X_1)$ and $I(X_1;Y)$.
Given
16 wafers: furnace band $X_1$ low for 4 (all good), normal for 8 (4 defective), high for 4 (all defective)
8 of the 16 wafers are defective
Solution
Two of the three bands are pure and one is split evenly, so every conditional entropy is $0$ or $1$ and the route needs no logarithm tables.
Definition route: only the two pure cells contribute, each $\frac4{16}\log\frac{4/16}{(4/16)(8/16)}=\frac14\log2=\frac14$; the normal cells have ratio $1$. The total is $\frac12$.
When groups are pure or evenly split, the entropy route is mental arithmetic.
Zero correlation but 0.918 bit of information: y equals x squared
Six readings have $x=-1, \allowbreak -1, \allowbreak 0, \allowbreak 0, \allowbreak 1, \allowbreak 1$ and $y=x^2$. Compute the sample correlation and $I(X;Y)$.
Definition route: the cells $(-1,1)$, $(0,0)$, $(1,1)$ each have probability $\frac13$, and $\frac13\log\frac32+\frac13\log3+\frac13\log\frac32=\log3-\frac23=0.918$.
Correlation measures straight-line trends; mutual information measures any dependence, so it is the safer screen when the shape is unknown.
Checkpoint
§11.2 — a feature that copies the label
A binary feature $X$ equals a balanced binary label $Y$ on every sample.
Find(a) What is $I(X;Y)$?
Given$p(0,0)=p(1,1)=\tfrac12$, $p(0,1)=p(1,0)=0$
Hint 1/4
Compare the uncertainty about $Y$ before and after $X$ is seen.
Hint 2/4
$I(X;Y)=H(Y)-H(Y\mid X)$.
Hint 3/4
Here $Y$ is a fair bit, so $H(Y)=1$, and $X=Y$ leaves nothing to guess, so $H(Y\mid X)=0$.
Hint 4/4
$I(X;Y)=1$ bit.
Show solution
The entropy route is one line here, because knowing $X$ leaves nothing about $Y$.
Before and after
$$H(Y)=1,\qquad H(Y\mid X)=0$$
A fair bit is one bit; a copy settles it completely.
$$I(X;Y)=1-0=1\ \text{bit}$$
The information is the uncertainty removed.
Answer $$\boxed{I(X;Y)=1\ \text{bit}}$$
Check
Definition route: two cells, each $\frac12\log\frac{1/2}{1/4}=\frac12$; the empty cells contribute nothing.
A copy of $Y$ reaches the ceiling $I(X;Y)=H(Y)$; no feature can tell more than the label's own uncertainty.
⚠ Mixing logarithm bases
Calculators default to $\ln$, and a table in bits with one value in nats still looks consistent.
11.3Maximum relevance: ranking by mutual information, and what it misses
Ranks features by $I(X_j;Y)$ and keeps the top $k$: cheap, but blind to features that repeat each other or only work together.
Put $s_j=I(X_j;Y)$ into the ranking recipe of the first block and you have the lecture's maximum relevance rule.
RuleRule 11.3: Maximum relevance
Conditions
$I(X_j;Y)$ estimated from $D$ for every $j$: $p$ two-variable estimates
ties broken by the lower index, a convention of this page
$$\boxed{\begin{aligned}&s_j=I(X_j;Y)\\&\text{keep the }k\text{ largest scores}\end{aligned}}$$
Score each feature by what it alone tells about the label, and keep the top $k$. Each score looks at one feature at a time, so it cannot see what two features share, or what they can do only together.
Why a copy adds nothing
Same groups. If $X_2=g(X_1)$ for a function $g$, knowing $X_1$ fixes $X_2$, so the pair $(X_1,X_2)$ splits the data into the same groups as $X_1$ alone.
Same uncertainty left. Then $H(Y\mid X_1,X_2)=H(Y\mid X_1)$ and $I(\{X_1,X_2\};Y)=I(X_1;Y)$, while the sum of relevances counts it twice.
Each row groups the 16 wafers by the features named on the left; filled squares are defective. The furnace band leaves one $\textcolor{#d1690a}{\text{mixed}}$ group, the normal band. The backup thermometer draws the same lines, so nothing changes; humidity cuts the mixed group into a good half and a defective half, and $\textcolor{#1f6feb}{H(Y\mid X_1,X_3)=0}$.
Looks like this, but is not
Features with zero relevance look safe to drop. In a stairwell the lamp is on exactly when two switches disagree, and each switch alone has $I=0$ with the lamp.
Together the two switches decide the lamp: $I(\{A,B\};Y)=1$ bit. Relevance scores one feature at a time and cannot see features that work only as a team.
Maximum relevance on the four wafer sensors keeps the two thermometers
The relevances of the four sensors are $I(X_1;Y)=0.5$, $I(X_2;Y)=0.5$, $I(X_3;Y)=0.189$ and $I(X_4;Y)=0$ bit, where the backup thermometer $X_2$ shows the same band as $X_1$ on every wafer. Keep $k=2$ by maximum relevance and find how much the kept pair tells about $Y$.
FindThe kept pair and $I(\{X_1,X_2\};Y)$.
Given
relevances $0.5,\ \allowbreak 0.5,\ \allowbreak 0.189,\ \allowbreak 0$ bit for $X_1$ to $X_4$
$X_2=X_1$ on all 16 wafers
16 wafers: furnace band $X_1$ low for 4 (all good), normal for 8 (4 defective), high for 4 (all defective)
Solution
The ranking needs only the four relevances; the joint value then needs only the groups the pair forms, which the copy makes easy.
Humidity with $X_1$ does better: the pair $(X_1,X_3)$ leaves only pure groups, so $I(\{X_1,X_3\};Y)=H(Y)=1$ bit.
Relevances do not add, and a copy adds nothing; the next two blocks repair exactly this.
Two stairwell switches: relevance ranks the useful pair last
A stairwell lamp $Y$ is on exactly when switch $A$ at the bottom and switch $B$ at the top are in different positions. A cheap light sensor $L$ reports the lamp correctly 3 times in 4. Sixteen logged evenings show each setting of $(A,B)$ four times, with $L$ wrong once in each setting. Rank the three features by relevance with $k=2$.
Find$I(A;Y)$, $I(B;Y)$, $I(L;Y)$, the kept pair, and what the two switches tell together.
Given
$Y=1$ exactly when $A\ne B$; each setting of $(A,B)$ appears 4 times
$L=Y$ on 12 of the 16 evenings, wrong once in each setting
Solution
Every group splits evenly or $3:1$, so the only logarithm needed is $H$ of a $3:1$ split, $0.811$ bit, from the humidity example.
Each switch alone
$$A=0:\ Y=1\text{ on }4\text{ of }8;\qquad A=1:\ Y=1\text{ on }4\text{ of }8\ \Rightarrow\ I(A;Y)=0$$
Knowing one switch leaves the other a coin flip, so the lamp stays $50:50$; the same holds for $B$.
The sensor
$$L=1:\ Y=1\text{ on }6\text{ of }8;\quad L=0:\ Y=0\text{ on }6\text{ of }8\ \Rightarrow\ I(L;Y)=1-0.811=0.189$$
Given $L$, the lamp matches it $3:1$ in both groups.
Rank and compare
$$\text{keep }L\text{ and }A:\quad I(\{L,A\};Y)=I(L;Y)=0.189$$
The tie between $A$ and $B$ goes to the lower letter; $A$ is spread evenly over every $(L,Y)$ group, so it adds nothing to $L$.
Maximum dependency tries every $k$-subset and keeps the one whose features, taken together, tell the most about $Y$. Incremental search grows the set one feature at a time, each time adding the feature that makes the enlarged set most informative, and it never undoes a step.
Counting the evaluations
Exhaustive. One joint estimate per $k$-subset: $\binom pk$ of them.
Incremental. Step $l$ tries each of the $p-l+1$ features not yet chosen, so the total is $p+(p-1)+\dots+(p-k+1)=kp-\frac{k(k-1)}2$.
What is not saved. The last step still scores sets of $k$ features with $Y$: a joint table over $k+1$ variables.
Every feature here is an independent coin flip, unrelated to a balanced label, so the true $\textcolor{#1f6feb}{I(S;Y)}$ is $0$ for every $k$. The orange curve is the average plug-in estimate over 1,000 simulated data sets of $n=60$: once the $2^k$ cells outnumber the samples, most samples sit alone in a cell and the estimate climbs toward $\textcolor{#d1690a}{H(Y)=1}$ bit.
Looks like this, but is not
Incremental search looks as if it must end at the best subset, since every step takes the best step available.
In the stairwell data, step 1 must take the sensor $L$, the only feature with nonzero relevance. Every pair containing $L$ then scores $0.189$, while $\{A,B\}$, now out of reach, scores $1$ bit. A greedy first step cannot be undone.
Incremental search on the four wafer sensors finds a thermometer and humidity
Run incremental search with $k=2$ on the wafer sensors, using the relevances and the pair values listed.
Find$S_1$, $S_2$ and $I(S_2;Y)$.
Given
relevances $0.5,\ \allowbreak 0.5,\ \allowbreak 0.189,\ \allowbreak 0$ bit for $X_1$ to $X_4$
Exhaustive search over all $\binom42=6$ pairs agrees: the values are $0.5,\ \allowbreak 1,\ \allowbreak 0.5,\ \allowbreak 1,\ \allowbreak 0.5,\ \allowbreak 0.189$, and the maximum $1$ is reached by $\{X_1,X_3\}$ and $\{X_2,X_3\}$.
That settles the wafer puzzle from the opening: a thermometer and the hygrometer, not two thermometers. Scoring the set is what sees the copy.
Counting subsets: exhaustive search against incremental search
A sensor bank has $p=20$ features and we want $k=5$. How many joint mutual informations does each search compute? Repeat for the lecture's gene data, $p=9703$, with $k=3$.
Find$\binom pk$ and $kp-\frac{k(k-1)}2$ in both cases.
Given
$p=20,\ k=5$
$p=9703,\ k=3$
Solution
Both counts are closed forms, so no search has to be run.
Answer $$\boxed{\begin{aligned}&p=20:\ 15504\text{ against }90\\&p=9703:\ 1.52\times10^{11}\\&\qquad\text{against }29106\end{aligned}}$$
Check
For tiny problems the order flips: with $p=4$ and $k=3$ exhaustive search needs $\binom43=4$ subsets and incremental search $4+3+2=9$; the saving comes with large $p$.
Incremental search removes the combinatorial count, not the estimation problem: its last step still needs a table over $k+1$ variables.
Eight wafers and three coin-flip sensors: the estimate reaches one bit
Eight new wafers were logged with three extra sensors $b_1,b_2,b_3$ that are coin flips, unrelated to the label. On these wafers the three sensors happen to show each of the eight patterns once. Estimate $I(S;Y)$ from the counts for $S=\{b_1\}$, $\{b_1,b_2\}$ and $\{b_1,b_2,b_3\}$.
Relabel the wafers in any way with four defective: the three-sensor estimate stays $1$ bit, because each cell still holds one wafer. The number measures the sample size, not the sensors.
A joint estimate is only as good as the samples per cell: with more cells than samples, do not trust it.
Checkpoint
§11.4 — exhaustive or incremental within a budget
A team with $p=10$ candidate features wants $k=3$ and can afford about 50 joint mutual information estimates.
Find(a) Which search fits the budget, and how many estimates does it need?
Given
$p=10$, $k=3$
budget: about 50 estimates
Hint 1/4
Count the joint estimates of each search before comparing with the budget.
right$$\text{cells}\gg n:\ \ \hat I(S;Y)\to H(Y)\ \text{even for coin flips}$$
11.5Minimum redundancy, maximum relevance (mRMR)
Adds one feature at a time by relevance minus average redundancy; only two-variable estimates, so it scales to thousands of features.
Incremental search removed the $\binom pk$ count but still needs a $(k+1)$-variable table at its last step; mRMR replaces the joint score by two-variable pieces.
RuleRule 11.5: Minimum redundancy, maximum relevance
Conditions
$S_0=\emptyset$; at $l=1$ there is no redundancy term, so the first pick is the most relevant feature
every term is a two-variable mutual information, $I(X;Y)$ or $I(X;X')$
At each step a candidate earns what it tells about the label and pays the average of what it shares with the features already chosen. The best net score joins the set, and the cost per step is one new two-variable estimate for each remaining candidate.
Counting the two-variable estimates
Relevance. $p$ values $I(X_j;Y)$, computed once.
Redundancy. At step $l\ge2$ each of the $p-l+1$ candidates needs one new value, its mutual information with the feature added at step $l-1$; the older ones are reused.
Total. $p+\sum_{l=2}^k(p-l+1)$, the same order as incremental search, but no estimate involves more than two variables.
Step 2 of mRMR on the wafer sensors, after $X_1$ was chosen. Each candidate's blue bar is its relevance, the orange bar its redundancy with $X_1$, and the diamond the difference. The backup thermometer repeats $\textcolor{#d1690a}{1.5}$ bits of $X_1$ and ends at $-1$; humidity shares nothing with $X_1$ and wins with $\textcolor{#1f6feb}{0.19}$.
Looks like this, but is not
mRMR looks as if it should find the stairwell's two switches, since they share nothing with each other.
Pairwise terms cannot see teamwork. Step 1 takes the sensor $L$ ($0.189$); at step 2 each switch scores $0-0=0$, so mRMR ends with $\{L,A\}$ and $0.189$ bit, exactly like maximum relevance.
mRMR on the four wafer sensors
Run mRMR with $k=2$ on the wafer sensors, using the relevances and the redundancies with $X_1$ listed.
Find$S_2$ and the score of each candidate.
Given
relevances $0.5,\ \allowbreak 0.5,\ \allowbreak 0.189,\ \allowbreak 0$ bit for $X_1$ to $X_4$
$I(X_2;X_1)=1.5$, $I(X_3;X_1)=0$, $I(X_4;X_1)=0$ bit
ties broken by the lower index
Solution
Only two-variable values are needed and all of them are listed; no three-variable table is built.
Incremental search reached the same pair from three-variable values: $I(\{X_1,X_3\};Y)=1$ against $0.5$ for $X_2$ or $X_4$ with $X_1$.
The penalty charged the copy for the $1.5$ bits it repeats, and that alone fixed the choice.
A third mRMR step: the redundancy is an average
A condition-monitoring study estimated from 40 pumps the relevances and pairwise mutual informations below. Run mRMR with $k=3$ and compare with the top three by relevance.
Find$S_3$, and the set the relevance ranking would keep.
Each winner beats the runner-up by at least $0.045$ ($0.14$ against $0.09$, then $0.145$ against $0.10$), so two-decimal rounding of the table cannot change the path.
Five relevances and seven pairwise values, four at step 2 and three at step 3; no table over three or more variables.
Always divide by $l-1$: summing the two redundancies would give $X_5$ only $0.02$ and hand the third place to $X_1$.
Checkpoint
§11.5 — one mRMR score at step three
At step 3 of mRMR two features, $X_a$ and $X_b$, are already chosen. A candidate $X$ has relevance $0.40$ bit and shares $0.30$ bit with $X_a$ and $0.10$ bit with $X_b$.
Find(a) What is its mRMR score?
Given
$I(X;Y)=0.40$
$I(X;X_a)=0.30$, $I(X;X_b)=0.10$
Hint 1/4
The score is relevance minus a penalty; decide how the penalty combines the two shared values.
Hint 2/4
Score $=I(X;Y)-\frac1{l-1}\sum_{X'\in S_{l-1}}I(X;X')$, with $l=3$.
Hint 3/4
Here $0.40-\frac{0.30+0.10}2$.
Hint 4/4
The score is $0.20$.
Show solution
The rule is a single formula; the only choice is the divisor, $l-1=2$.
11.6Best subset selection, with the size chosen by cross-validation
Fits all $2^p$ least squares models, keeps the lowest-RSS model of each size, and lets cross-validation pick the size.
Every score so far ignored the learner; now the learner itself judges each subset, here least squares judged by its RSS.
MethodMethod 11.6: Best subset selection
Conditions
least squares with an intercept; $M_0$ is the null model, $\hat y=\bar y$ for every $x$
there are $\binom pk$ models with exactly $k$ features, $2^p$ in all
$\mathrm{TSS}=\sum_i(y_i-\bar y)^2$ is the RSS of $M_0$
RSS only falls and $R^2$ only rises as $k$ grows, so neither may pick the size
$$\boxed{\begin{aligned}&M_k=\arg\min_{m:\ k\text{ features}}\mathrm{RSS}(m)\\&k=1,\dots,p\\&\text{choose among }M_0,M_1,\dots,M_p\\&\qquad\text{by cross-validation}\\&R^2=1-\frac{\mathrm{RSS}}{\mathrm{TSS}}\ \text{rises with }k\end{aligned}}$$
For every size, find the subset whose least squares fit leaves the smallest residual sum of squares. The $p+1$ winners cannot be compared by RSS or $R^2$, which only improve as the size grows, so cross-validation picks among them.
Why training fit cannot choose the size
Nested fits. Add one feature to $M_k$; setting its coefficient to $0$ reproduces the fit of $M_k$, so least squares on the larger set does at least as well.
So the winners only improve. $\mathrm{RSS}(M_{k+1})\le\mathrm{RSS}(M_k)$ and $R^2$ never falls: training fit always prefers $M_p$.
Within one size the comparison is fair. Models of the same size have the same number of coefficients, so their RSS values can be compared directly, as the lecture does.
The workshop data. Left: training RSS of all eight fits; the best of each size, in $\textcolor{#8250df}{\text{purple}}$, can only fall. Right: leave-one-out error of those four models; it turns up after $k=2$, and the lowest value, $\textcolor{#1f6feb}{0.93}$, picks $M_2=\{x_1,x_2\}$.
Looks like this, but is not
The model with the largest $R^2$ looks like the best model: $M_3$ has $R^2=0.984$, more than any other fit.
$R^2$ can only rise as features are added. The leave-one-out error, which predicts each run from a fit that never saw it, is $1.53$ for $M_3$ against $0.93$ for $M_2$: the third feature fits noise.
run
x₁ (kW)
x₂ (kW)
x₃ (kW)
y (kWh)
1
2
3
4
10
2
3
4
5
14
3
3
6
11
18
4
1
3
5
7
5
3
3
7
13
6
0
5
3
10
7
2
4
5
12
8
2
2
2
8
The clamp meter reads the total $x_1+x_2$ with an error of 1 or 2 kW, and $y$ stays within 1 kWh of $2(x_1+x_2)$: two hours at the total load.
Best subset selection for the workshop's three meters
Eight two-hour runs of a workshop record the energy $y$ (kWh), the loads $x_1$ and $x_2$ of two presses (kW), and a clamp meter reading $x_3$ of the total load (kW). The RSS of all eight least squares fits, each with an intercept, are listed. Find $M_1$, $M_2$, $M_3$ and the number of fits.
Find$M_1$, $M_2$, $M_3$ and the number of fits.
Given
eight two-hour runs: $x_1$, $x_2$ loads of two presses (kW), $x_3$ a clamp meter reading of the total load (kW), $y$ energy used (kWh)
$R^2=1-\mathrm{RSS}/88$ gives $0.690$, $0.983$ and $0.984$ for $M_1$, $M_2$, $M_3$: rising with $k$, as the nesting argument says.
The best single feature need not belong to the best pair: $x_3$ wins alone and is absent from $M_2$.
Choosing the size by leave-one-out error
For the workshop data the leave-one-out errors $\mathrm{CV}(n)$ of the four winners are listed, with the least squares fit of $M_2$. Choose the model and predict the energy of a run with $x_1=2$ and $x_2=4$ kW.
Physical check: two hours at a total load of $2+4=6$ kW is $12$ kWh, and the coefficients $2.25$ and $2$ are close to the two hours in $y\approx2(x_1+x_2)$.
Choose the size by cross-validation, then refit the chosen subset on all the data.
Checkpoint
§11.6 — picking a size from two error lists
Best subset selection on $p=4$ features gives two lists for the winners $M_0$ to $M_4$.
Find(a) Which model should be chosen?
Given
training RSS of $M_0,\dots,M_4$: $120,\ \allowbreak 60,\ \allowbreak 35,\ \allowbreak 33,\ \allowbreak 32.5$
A model with no features does not look like a candidate, yet sometimes no feature helps.
wrong$$\text{choose among }M_1,\dots,M_p$$
right$$\text{choose among }M_0,M_1,\dots,M_p$$
11.7Forward stepwise selection
Adds the feature with the largest RSS drop at each step: far fewer fits than $2^p$, but it can miss the best subset.
Best subset needs $2^p$ fits; forward stepwise applies the incremental search idea with RSS as the score.
MethodMethod 11.7: Forward stepwise selection
Conditions
$S_0=\emptyset$, and $M_0$ is the null model
each step adds one feature and never removes one
the size is again chosen by cross-validation
$$\boxed{\begin{aligned}&X^*=\arg\min_{X\notin S_k}\mathrm{RSS}(S_k\cup\{X\})\\&S_{k+1}=S_k\cup\{X^*\}\\&k=0,\dots,p-1\\&\text{size: }M_0,\dots,M_p\text{ by CV}\\&\text{fits: }1+\sum_{k=0}^{p-1}(p-k)\\&\qquad=1+\frac{p(p+1)}2\end{aligned}}$$
Start from the mean. At each step try adding every unused feature, keep the one that lowers RSS the most, and never go back. After $p$ steps there is one model per size, and cross-validation picks the size.
Counting the fits
Step $k$. With $k$ features in, $p-k$ candidates remain, and each is one least squares fit.
Sum.$p+(p-1)+\dots+1=\frac{p(p+1)}2$, plus the null model.
Compare. For $p=20$ that is $211$ fits against $2^{20}=1{,}048{,}576$.
All eight subsets of the workshop's three meters with their training RSS. The $\textcolor{#8250df}{\text{purple}}$ arrows are forward stepwise: it takes $x_3$ first, and from then on only sets containing $x_3$ are open to it. The $\textcolor{#1f6feb}{\text{blue}}$ boxes are the best model of each size; the best pair, $\{x_1,x_2\}$ with RSS $1.50$, is off the forward path.
Looks like this, but is not
Each forward step is the best step available, so the forward model of size 2 looks like the best model of size 2.
Forward commits to $x_3$ first. The best pair containing $x_3$ has RSS $21.27$, while $\{x_1,x_2\}$, which forward can no longer reach at size 2, has $1.50$.
Forward stepwise on the workshop data, and what cross-validation then picks
Run forward stepwise selection on the workshop data using the RSS list, then choose the size with the leave-one-out errors of the forward models.
FindThe forward path, the number of fits, and the chosen model.
Best subset reached $\{x_1,x_2\}$ with leave-one-out error $0.93$; forward ends at $1.53$, higher, because its size-2 model is the wrong pair.
Forward stepwise is cheap because it never revisits a choice, and that is also why it can end with a worse model.
Fits needed for twenty features, and for 9703
A lab has $p=20$ candidate features. How many least squares fits do best subset and forward stepwise need? Repeat for the lecture's gene data, $p=9703$.
Too large to write out, so we count its digits with a logarithm.
$$1+\tfrac{9703\cdot9704}2=47{,}078{,}957$$
The forward count is a quadratic in $p$.
Answer $$\boxed{\begin{aligned}&p=20:\ 1{,}048{,}576\text{ against }211\\&p=9703:\ 7.8\times10^{2920}\\&\qquad\text{against }47{,}078{,}957\end{aligned}}$$
Check
For $p=3$ the formulas give $8$ and $7$, the counts found by hand on the workshop data.
Past a few dozen features best subset is out of reach, and even forward stepwise is heavy at 9703; that is where the cheap mRMR screen earns its place.
Checkpoint
§11.7 — counting forward stepwise fits
Forward stepwise selection is run on $p=5$ candidate features.
Find(a) How many least squares fits does it make?
Given
$p=5$
the null model counts as one fit
Hint 1/4
Count the candidates tried at each step, then add the null model.
Hint 2/4
$1+\sum_{k=0}^{p-1}(p-k)=1+\frac{p(p+1)}2$.
Hint 3/4
Here $p=5$: $1+(5+4+3+2+1)$.
Hint 4/4
$16$ fits.
Show solution
Summing the candidates step by step makes the formula visible.
Step by step
$$1+(5+4+3+2+1)=1+15=16$$
The null model, then $5-k$ candidates at step $k$.
Against best subset
$$2^5=32$$
Every subset once.
Answer $$\boxed{16\ \text{fits}}$$
Check
The formula $1+\frac{p(p+1)}2=1+\frac{5\cdot6}2=16$ agrees.
For small $p$ the saving is modest; it grows fast with $p$.
⚠ Assuming the forward path holds the best model of each size
Every step is locally best, which sounds like globally best.
The best pair contains $x_1$, so forward stepwise sees it.
Answer $$\boxed{\text{they agree at size 2}}$$
Check
$M_2=\{x_1,x_2\}$ contains $M_1=\{x_1\}$; when every winner contains the one before, forward stepwise finds all of them.
Nested winners are what make the greedy path safe.
Forward stepwise matches best subset when each best model contains the one before it, and misses when it does not.
How to tell them apart
Check whether best subset's $M_{k+1}$ contains $M_k$; if every step nests, forward stepwise finds the same models with far fewer fits.
Scaffolding comes off
The common skeleton
List the relevance $I(X_j;Y)$ of every candidate, computing in bits any value given only as counts.
Take the most relevant feature as $X_1^*$.
For each remaining candidate, average its mutual information with the features already chosen.
Score = relevance minus that average; add the largest score.
Repeat the last two steps until $k$ features are in.
1 · fully worked
mRMR by hand on five motor sensors
A maintenance team estimated from 40 motors the table below. $X_1$ and $X_2$ are two vibration sensors on the same bearing, $X_3$ and $X_4$ two temperature probes on the same housing, and $X_5$ an acoustic sensor. Select $k=3$ features by mRMR.
Find$S_3$, with the score of every candidate at every step.
The acoustic sensor shares little with either chosen feature.
Answer $$\boxed{S_3=\{X_1,X_3,X_5\}}$$
Check
Joint values estimated from the motors: $I(\{X_1,X_3,X_5\};Y)=0.67$ bit against $0.60$ for the top three by relevance, $\{X_1,X_2,X_3\}$.
One feature from each near-copy pair plus the independent sensor: that is what mRMR is built to find.
2 · you write the reasoning
Easier, and this time you write the reasons. From 32 recordings: relevances $X_1\ 0.36$, $X_2\ 0.29$, $X_3\ 0.19$, $X_4\ 0.13$ bit; $I(X_1;X_2)=0.80$, $I(X_1;X_3)=0.07$, $I(X_1;X_4)=0.16$. Select $k=2$ by mRMR, and for each line write why it is allowed.
$X_1^*=X_1\ (0.36)$
reasoning
With nothing chosen yet, the score is relevance alone, and $0.36$ is the largest.
$X_2:\ 0.29-0.80=-0.51$
reasoning
At $l=2$ the average runs over one chosen feature, $X_1$, and $X_2$ repeats most of it.
$X_3:\ 0.19-0.07=0.12$
reasoning
$X_3$ shares only $0.07$ bit with $X_1$, so it keeps most of its relevance.
$X_4:\ 0.13-0.16=-0.03$
reasoning
$X_4$ shares more with $X_1$ than it tells about the label.
$S_2=\{X_1,X_3\}$
reasoning
$0.12$ is the only positive score.
3 · find the buried error
Harder, with two errors buried in the solution. A student selects $k=3$ by mRMR from 40 recordings. Which two steps are wrong?
relevances: $X_2\ 0.23$, $X_3\ 0.59$, $X_4\ 0.00$, $X_5\ 0.41$ bit
$X_1$ only as counts: when $X_1=0$, 21 recordings have $Y=0$ and 3 have $Y=1$; when $X_1=1$, 4 have $Y=0$ and 12 have $Y=1$
pairwise: $I(X_3;X_5)=0.72$, $I(X_2;X_3)=0.18$, $I(X_1;X_3)=0.17$, $I(X_1;X_2)=I(X_2;X_5)=0.11$, $I(X_1;X_5)=0.10$, $I(X_2;X_4)=0.01$, and $0.00$ for $X_4$ with $X_1$, $X_3$ and $X_5$
Step 1. From the counts, $I(X_1;Y)=0.525\ln1.4+0.075\ln\frac13+0.1\ln0.4+0.3\ln2=0.21$.
Step 2. The largest relevance is $0.59$, so $X_3$ is chosen first.
Step 4. With $X_3$ and $X_2$ chosen: $X_1$ scores $0.21-(0.17+0.11)=-0.07$, $X_4$ scores $0-(0+0.01)=-0.01$, $X_5$ scores $0.41-(0.72+0.11)=-0.42$. $X_4$ joins.
Step 5. $S_3=\{X_3,X_2,X_4\}$.
the two buried errors (2)
⚠ step 1
The logarithms are natural, so $0.21$ is in nats while every other value in the table is in bits.
Calculators default to $\ln$, and a table with one value in nats still looks consistent.
right
In bits, $I(X_1;Y)=0.21/\ln2=0.30$; with it, Step 3 gives $X_1$ the score $0.30-0.17=0.13$, and $X_1$ joins instead of $X_2$.
⚠ step 4
At step $l=3$ the two redundancies are added, not averaged: each candidate should pay half of the sum.
The factor $\frac1{l-1}$ equals $1$ at step 2, so it is easy to forget that it matters at step 3.
right
With both errors fixed, $S_2=\{X_3,X_1\}$ and step 3 gives $X_2:\ 0.23-\frac{0.18+0.11}2=0.085$, $X_4:\ 0.00$, $X_5:\ 0.41-\frac{0.72+0.10}2=0.00$, so $S_3=\{X_3,X_1,X_2\}$.
4 · the bare problem
§11.5 — mRMR on five wind turbine features
From 40 wind turbines, five features were scored against a gearbox fault label, and their pairwise mutual informations were estimated.
Joint values estimated from the turbines: $I(\{X_1,X_3,X_5\};Y)=0.83$ bit against $0.70$ for $\{X_1,X_4,X_5\}$, where $X_4$ repeats $0.48$ bit of $X_1$.
The second most relevant feature is often the first one's echo; check its overlap before keeping it.
Full exam-style question
Three signals for transformer overheating: relevance, redundancy and the pair to keepexam format
A utility logged 32 overload events on distribution transformers. For each it recorded the load level $A$ (low, medium or high), an older meter's flag $B$ ($1$ when the load is not low), and whether the cooling fan had failed, $C$. $Y=1$ if the transformer overheated.
Low load: 8 events, fan failed in 4, none overheated.
Medium load: 16 events, fan failed in 8; overheated exactly when the fan failed.
High load: 8 events, fan failed in 4, all overheated.
(a) Compute $I(A;Y)$, $I(B;Y)$ and $I(C;Y)$ in bits.
(b) Which two signals does maximum relevance keep, and what is their joint information with $Y$?
(c) Compute $I(A;B)$ and $I(A;C)$, and run mRMR with $k=2$.
(d) Which pair maximizes $I(S;Y)$?
(e) With $p=120$ binary signals and $k=4$, how many joint estimates would exhaustive and incremental search need, and why would either be doubtful with 32 events?
FindThree relevances; maximum relevance's pair and its value; $I(A;B)$, $I(A;C)$ and mRMR's pair; the best pair; two counts and a verdict.
Given
low load: 8 events, fan failed in 4, none overheated
medium load: 16 events, fan failed in 8, overheated exactly when the fan failed
high load: 8 events, fan failed in 4, all overheated
$B=1$ exactly when the load is medium or high
Solution
Every group is pure, evenly split, or split $1:2$ or $1:3$, so the entropy route with $H(Y)=1$ bit handles every part and needs only two logarithm values, $0.918$ and $0.811$.
The pair $\{A,C\}$ predicts every event: low load never overheats, high load always does, and medium load overheats exactly when the fan failed. A perfect rule means $H(Y\mid A,C)=0$ and $I=H(Y)=1$ bit.
Score the pair, not the signals one by one: the coarse copy $B$ looked second best and added nothing.
Practice
A · concept 4 questions
1§11.1 — zero correlation and usefulness
A correlation screen reports $\hat R_j=0$ for one feature, and a teammate proposes to drop it because it can carry no information about $y$.
Find(a) True or false: if $\hat R_j=0$, feature $j$ carries no information about $y$.
Given$\hat R_j=0$ on the training data
Hint 1/4
Ask what kind of relation a correlation can detect.
Hint 2/4
$\hat R_j$ measures the straight-line trend; information is any dependence.
Hint 3/4
Here try $x=-1, \allowbreak -1, \allowbreak 0, \allowbreak 0, \allowbreak 1, \allowbreak 1$ with $y=x^2$: the cross-product $\sum_ix_i(y_i-\bar y)=\sum_ix_i^3$ is $0$.
Hint 4/4
So $\hat R=0$ while $x$ determines $y$: the statement is false.
Show solution
One counterexample settles a claim about every feature.
Correlation
$$S_{xy}=\sum_ix_i^3=0\ \Rightarrow\ \hat R=0$$
$\bar x=0$ and the cubes cancel in pairs.
Information
$$H(Y\mid X)=0\ \Rightarrow\ I(X;Y)=H(Y)=0.918$$
Each $x$ gives a single $y$.
Answer $$\boxed{\text{False}}$$
Check
A straight-line fit of $y$ on $x$ has slope $0$ and explains none of the spread, while a fit of $y$ on $x^2$ explains all of it.
Before dropping a zero-correlation feature, ask whether the relation could be curved.
2§11.2 — can mutual information be negative?
A feature $X$ is $1$ exactly when a binary label $Y$ is $0$: it moves opposite to the label, and its correlation with $Y$ is $-1$.
Find(a) True or false: $I(X;Y)$ is negative for such a feature.
Given
$X=1-Y$ on every sample
$Y$ is a fair bit
Hint 1/4
Ask what mutual information measures: a direction or an amount.
Hint 2/4
$I(X;Y)=H(Y)-H(Y\mid X)\ge0$.
Hint 3/4
Here $Y$ is a fair bit, so $H(Y)=1$, and $X=1-Y$ settles $Y$, so $H(Y\mid X)=0$.
Hint 4/4
$I(X;Y)=1$ bit, the largest possible value: false.
Show solution
The entropy route needs two facts: $H(Y)$, and whether $X$ settles $Y$.
Definition route: the two nonzero cells $(1,0)$ and $(0,1)$ each give $\frac12\log\frac{1/2}{1/4}=\frac12$.
Correlation has a sign; mutual information does not, because it measures how much, not which way.
3§11.3 — when the top two by relevance make a poor pair
Maximum relevance keeps the two features with the largest $I(X_j;Y)$. The pair it keeps can still be a poor choice.
Find(a) In which situation is the kept pair poor?
Given$k=2$, score $s_j=I(X_j;Y)$
Hint 1/4
Ask what the second feature adds once the first one is known.
Hint 2/4
$I(\{X_1,X_2\};Y)=I(X_1;Y)$ when $X_2$ is a function of $X_1$.
Hint 3/4
Here the pair is the top two by relevance; if $X_2$ is close to a copy of $X_1$, the pair tells about as much as $X_1$ alone.
Hint 4/4
The pair is poor when the two features are near copies.
Show solution
Each option is tested against the question the score answers: one feature at a time.
What the score sees
$$\begin{aligned}&s_j=I(X_j;Y)\\&\text{one feature at a time}\end{aligned}$$
Overlap between features never enters it.
When the overlap is total
$$X_2=g(X_1):\quad I(\{X_1,X_2\};Y)=I(X_1;Y)$$
The second feature adds nothing.
Answer $$\boxed{\text{near copies}}$$
Check
The wafer data: the two thermometers score $0.5$ bit each, and together they still give $0.5$ bit.
High relevance and low overlap are two separate requirements; mRMR asks for both.
4§11.7 — does forward stepwise find the best pair?
A classmate says that forward stepwise and best subset selection always give the same model of size 2, since both pick the smallest RSS.
Find(a) True or false: forward stepwise always finds the same size-2 model as best subset selection.
Given
least squares with an intercept
any data set with $p\ge3$ features
Hint 1/4
Ask which pairs each method actually compares.
Hint 2/4
Best subset compares all $\binom p2$ pairs; forward stepwise only the $p-1$ pairs that contain its first pick.
Hint 3/4
Here, on the workshop data, the best single is $\{x_3\}$ ($27.27$), and the pairs have RSS $\{x_1,x_2\}$ $1.50$, $\{x_2,x_3\}$ $21.27$, $\{x_1,x_3\}$ $22.15$.
Hint 4/4
Forward reaches $\{x_2,x_3\}$, not $\{x_1,x_2\}$: false.
Show solution
One data set where the two differ refutes "always".
Forward stepwise
$$\{x_3\}\ \to\ \{x_2,x_3\}\quad(21.27<22.15)$$
Only pairs containing $x_3$ are compared.
Best subset
$$\{x_1,x_2\}:\ 1.50$$
All three pairs are compared.
Answer $$\boxed{\text{False}}$$
Check
The two agree whenever the best pair contains the best single feature; here $x_3$ is not in $\{x_1,x_2\}$, so they cannot agree.
A greedy path is fast and often good, but "always" is exactly what it cannot promise.
B · computation 7 questions
1§11.1 — correlation scores from five raw days
Two candidate features were logged with an output $y$ on five days. Only one feature can be kept.
Find
(a) Compute $\hat R_1$ and $\hat R_2$.
(b) Which feature does the correlation score keep for $k=1$?
Given
$x_1=(5,4,3,2,1)$
$x_2=(2,2,3,4,4)$
$y=(1,3,2,5,4)$
Hint 1/4
Each correlation needs three centered sums; each score then needs one square.
Hint 2/4
$\hat R_j=S_{jy}/\sqrt{S_{jj}S_{yy}}$ and $s_j=\hat R_j^2$.
Definition route: the cell ratios are $\frac12$, $1$ and $\frac32$ with their mirror images, and $2\cdot\frac2{24}\log\frac12+2\cdot\frac6{24}\log\frac32=-0.167+0.292=0.126$.
A feature whose groups are only mildly tilted carries little information, however steady the tilt.
3§11.2 — the two entropy routes give the same number
A traffic camera labels vehicles as car, van or truck, with probabilities $\tfrac12$, $\tfrac14$ and $\tfrac14$. A length sensor gives $X=1$ for every van and truck and $X=0$ for every car.
Find
(a) Compute $H(Y)$ and $H(Y\mid X)$, and from them $I(X;Y)$.
(b) Compute $H(X)$ and $H(X\mid Y)$, and check that they give the same $I(X;Y)$.
Incremental search always scores the current set plus one candidate; start from the empty set.
Hint 2/4
$X_l^*=\arg\max_{X\notin S_{l-1}}I(S_{l-1}\cup\{X\};Y)$, with $p+(p-1)+\dots+(p-k+1)$ evaluations.
Hint 3/4
Here the singles are $0.46$, $0.28$, $0.03$, $0.13$; the pairs with $X_1$ give $0.55$, $0.51$, $0.62$ for $X_2$, $X_3$, $X_4$; the triples with $\{X_1,X_4\}$ give $0.71$ with $X_3$ and $0.62$ with $X_2$.
Hint 4/4
$S_3=\{X_1,X_3,X_4\}$ with $0.71$; maximum relevance keeps $\{X_1,X_2,X_4\}$ with $0.62$; $9$ evaluations against $4$.
Show solution
Each step needs only the values of the current set plus one feature, all of which the table lists.
Joint values estimated from the recordings: $I(\{X_1,X_5,X_6\};Y)=0.65$ bit against $0.43$ for $\{X_1,X_3,X_4\}$.
When several top features measure the same thing, relevance ranking fills the set with them; mRMR takes one and moves on.
6§11.6 — when one feature is enough
A chemistry lab predicts the yield $y$ (g) of 10 batches from the catalyst mass $x_1$ (g), the stirring setting $x_2$ and a room humidity reading $x_3$. Least squares fits with an intercept gave these values.
Find
(a) Find $M_1$, $M_2$ and $M_3$.
(b) Compute $R^2$ for each and say which model is chosen.
Each added feature buys less than $0.001$ of $R^2$ while the leave-one-out error grows by a third or more at each step, $1.07\to1.43\to1.96$.
When one feature carries almost all the signal, cross-validation keeps the model small although $R^2$ keeps creeping up.
7§11.7 — forward stepwise with four features
Ten production runs record an output $y$, two machine settings $x_1$ and $x_2$, a combined gauge $x_3$ and the ambient temperature $x_4$. Forward stepwise selection is run with least squares (intercept included); the RSS values it needs are listed.
Find
(a) Find the forward path and count its fits, the null model included.
size 2 with $x_3$: $\{x_1,x_3\}$ $43.28$, $\{x_2,x_3\}$ $23.91$, $\{x_3,x_4\}$ $43.16$
size 3 with $x_2,x_3$: $\{x_1,x_2,x_3\}$ $3.38$, $\{x_2,x_3,x_4\}$ $23.53$; all four $3.32$
for comparison: $\mathrm{RSS}(\{x_1,x_2\})=3.40$
Hint 1/4
Forward stepwise keeps its choices; at each step only the current set plus one feature is tried.
Hint 2/4
At step $k$, $X^*=\arg\min_{X\notin S_k}\mathrm{RSS}(S_k\cup\{X\})$; the fits number $1+p(p+1)/2$.
Hint 3/4
Here size 1: $127.60$, $63.75$, $44.09$, $196.51$; size 2 with $x_3$: $43.28$, $23.91$, $43.16$; size 3 with $x_2,x_3$: $3.38$, $23.53$.
Hint 4/4
$\{x_3\}\to\{x_2,x_3\}\to\{x_1,x_2,x_3\}\to$ all four, with $11$ fits; no, $\{x_1,x_2\}$ has RSS $3.40<23.91$.
Show solution
Each step is a minimum over the listed extensions of the current set; nothing else is needed.
Step 1: the best single feature
$$\{x_3\}:\ 44.09<63.75<127.60<196.51$$
The combined gauge is the best single feature.
Step 2: only pairs containing $x_3$
$$\{x_2,x_3\}:\ 23.91<43.16<43.28$$
Only pairs containing $x_3$ are tried.
Steps 3 and 4: the last two additions
$$\{x_1,x_2,x_3\}:\ 3.38<23.53;\qquad \text{then all four: }3.32$$
The size-3 step adds $x_1$, the last step adds $x_4$.
Count and compare
$$1+4+3+2+1=11;\qquad 3.40<23.91$$
The null model plus the candidates at each step; the best pair beats the forward pair.
Answer $$\boxed{\begin{aligned}&\emptyset\to\{x_3\}\to\{x_2,x_3\}\\&\to\{x_1,x_2,x_3\}\to\text{all four}\\&11\ \text{fits; not the best pair}\end{aligned}}$$
Check
Formula check: $1+\frac{4\cdot5}2=11$, against $2^4=16$ fits for best subset.
A gauge that summarizes two settings is a typical first pick that later locks the settings themselves out.
C · exam level 4 questions
1§11.5 — a method for 9703 genes and 60 samples
A cancer study has $n=60$ tissue samples, $p=9703$ gene expression features and 9 tumour classes, the size of the lecture's example, and it needs about 50 genes for a classifier.
Find(a) Which selection method is feasible and gives trustworthy scores?
Given
$n=60$, $p=9703$, 9 classes
target: about 50 genes
Hint 1/4
Check two things for each method: how many scores it computes, and how many variables each score involves.
Hint 2/4
Exhaustive: $\binom pk$ scores of $k+1$ variables; incremental: about $kp$ scores of up to $k+1$ variables; mRMR: about $kp$ scores of two variables; best subset: $2^p$ fits.
Hint 3/4
Here $p=9703$, $k=50$ and $n=60$: $\binom{9703}{50}\approx10^{135}$, $2^{9703}\approx10^{2921}$, and late incremental steps need tables over dozens of variables from 60 samples.
Hint 4/4
Only mRMR is both feasible and built from small tables.
Show solution
Two quick counts per method, the number of scores and the variables per score, decide the question without running anything.
Exhaustive search and best subset are out; incremental search and mRMR need about $4.8\times10^5$ scores.
Variables per score
$$\begin{aligned}&\text{incremental: up to }51\\&\text{mRMR: }2\end{aligned}$$
With 60 samples only small tables can be estimated.
Answer $$\boxed{\text{mRMR}}$$
Check
The lecture's comparison on data of this size points the same way: mRMR selects features faster, and with many selected features it classifies more accurately than maximum dependency.
At large $p$ and small $n$, prefer scores built from small tables, even when they are only heuristics.
2§11.6 — two wrong steps in a best subset solution
A student applied best subset selection to eight runs with three meters; the data are listed under Given. Two of the four steps are wrong.
$M_1=\{x_3\}$, the smallest single RSS, $23.50$.
The best pair must contain $x_3$, so $M_2=\{x_2,x_3\}$, since $21.48<21.71$.
$M_3=\{x_1,x_2,x_3\}$, the only model of size 3.
$M_3$ has the smallest RSS of the four winners, so $M_3$ is chosen.
Check each step against the rule it claims to apply, not against the final answer.
Hint 2/4
Within a size, $M_k$ is the smallest RSS over all models of that size; across sizes, the choice is by CV error.
Hint 3/4
Here the pairs have RSS $1.714$, $21.71$ and $21.48$ for $\{x_1,x_2\}$, $\{x_1,x_3\}$ and $\{x_2,x_3\}$; the CV errors are $23.84$, $4.43$, $1.12$ and $4.47$.
Hint 4/4
Steps 2 and 4 are wrong: $M_2=\{x_1,x_2\}$, and CV chooses it.
Show solution
Only the two faulty steps need redoing; Steps 1 and 3 follow the rule.
The best pair
$$M_2=\{x_1,x_2\}:\ 1.714<21.48<21.71$$
All three pairs compete; nothing forces the best single feature into the best pair.
Sizes are compared by cross-validation, not by training RSS.
Answer $$\boxed{\begin{aligned}&\text{Steps 2 and 4}\\&\text{chosen: }M_2=\{x_1,x_2\}\end{aligned}}$$
Check
$M_3$'s RSS, $1.705$, is only $0.009$ below $M_2$'s, while its leave-one-out error is four times larger, $4.47$ against $1.12$.
Two classic slips: assuming the winners are nested, and letting training error compare sizes.
3§11.4 — a joint estimate with more cells than samples
Twelve patients, six with the disease ($Y=1$), were tested with three yes or no markers that, in truth, are unrelated to the disease. The 12 patients fall into 8 marker patterns.
Find
(a) Compute the plug-in $H(Y\mid S)$ and $\hat I(S;Y)$ for the three markers.
(b) Suppose more coin-flip markers are added until every patient has a pattern of their own. What is the estimate then, and what is the true value?
Given
$n=12$, six with $Y=1$
4 patterns hold one patient each; 2 patterns hold two patients with different labels; 2 patterns hold two patients with the same label
Hint 1/4
Only patterns that contain both labels leave any uncertainty; count the patients in them.
Hint 2/4
$\hat I=H(Y)-\sum_sp(s)H(Y\mid S=s)$, where a cell with one patient, or with one label only, has $H=0$.
Hint 3/4
Here $H(Y)=1$ bit, and the mixed patterns hold $2+2=4$ of the 12 patients, each with $H=1$.
Hint 4/4
$H(Y\mid S)=\frac4{12}$ and $\hat I=0.667$ bit; one patient per pattern would give $1$ bit, while the truth is $0$.
Show solution
Cells with one label contribute nothing, so only the two mixed cells need counting.
Twelve pure cells of one patient; the markers were generated independently of the disease.
Answer $$\boxed{\begin{aligned}&\hat I=0.667\ \text{bit}\\&\text{one per pattern: }1\ \text{bit}\\&\text{true value: }0\end{aligned}}$$
Check
Bound check: the estimate can never exceed $H(Y)=1$ bit, reached when every cell holds one patient; $0.667$ sits two thirds of the way there with 12 patients in 8 cells.
Before trusting a joint estimate, compare the number of cells with the number of samples.
4§11.4 — incremental search against mRMR on 40 pumps
The pump study estimated joint mutual informations as well as pairwise ones; mRMR with $k=3$ chose $\{X_2,X_4,X_5\}$, whose joint value is $0.81$ bit.
Find
(a) Run incremental search with $k=3$.
(b) Compare its set with mRMR's. How many cells does a three-feature score use, and what does that say about the difference?
triples with $X_2$ and $X_4$: $X_1\ 0.85$, $X_3\ 0.74$, $X_5\ 0.81$
40 pumps; features and fault label are binary
Hint 1/4
Run the search on the joint values first; then ask how reliable a table over four binary variables is when 40 pumps fill it.
Hint 2/4
$X_l^*=\arg\max_{X\notin S_{l-1}}I(S_{l-1}\cup\{X\};Y)$; three binary features with a binary label form $2^3\cdot2=16$ cells.
Hint 3/4
Here step 1 compares $0.13$, $0.58$, $0.32$, $0.24$, $0.27$; step 2 the pairs with $X_2$, $0.71$, $0.58$, $0.74$, $0.66$; step 3 the triples with $X_2,X_4$, $0.85$, $0.74$, $0.81$.
Hint 4/4
$S_3=\{X_2,X_4,X_1\}$ with $0.85$ against mRMR's $0.81$. Both are read from the same thin 16-cell tables, so a shared upward bias shifts both and cannot explain the $0.04$ gap; sampling noise can, and with 2.5 pumps per cell it is of that size.
Show solution
The search itself is three maxima over listed values; the judgement needs one count of cells.
$$\begin{aligned}&2^3\cdot2=16\ \text{cells}\\&\tfrac{40}{16}=2.5\ \text{pumps per cell}\end{aligned}$$
Both scores come from tables this thin, so a shared upward bias cancels in their difference; what remains is sampling noise, and with 2.5 pumps per cell it is several hundredths of a bit.
Answer $$\boxed{\begin{aligned}&S_3=\{X_2,X_4,X_1\}:\ 0.85\\&\text{mRMR set: }0.81\\&\text{a gap within the sampling noise}\end{aligned}}$$
Check
A separate size check: a three-feature table has $2^3=8$ feature cells for 40 pumps, 5 per cell, so moving one pump to another cell changes a joint estimate by about $0.03$ to $0.05$ bit, the size of the gap itself.
A small edge in an estimated joint information is not evidence when the tables are thin; mRMR trades a little of that edge for estimates you can trust.
D · interleaved 4 questions
1§11.6 — four uncorrelated inputs, keep two
Four standardized features are uncorrelated on the training set, with $X^TX=nI$ and $n=50$; $y$ is centered. Least squares and lasso are both available.
Find
(a) Which two features give the smallest training RSS among all two-feature models, and with which coefficients?
(b) Which coefficients does the penalized rule in the data return with $\lambda=100$, and which feature does it drop?
(c) By how much does the RSS of the pair in (a) exceed that of the full model?
lasso rule for this design: $\hat\beta^L_j=\operatorname{sign}(b_j)\,\big(\lvert b_j\rvert-\tfrac{\lambda}{2n}\big)_+$ with $b_j=\hat\beta^{\mathrm{LS}}_j$
$\lambda=100$
Hint 1/4
With orthogonal features each coefficient can be handled on its own, for both methods.
Hint 2/4
$\mathrm{RSS}(S)=\lVert y\rVert^2-n\sum_{j\in S}(\hat\beta^{\mathrm{LS}}_j)^2$, and lasso soft-thresholds each coefficient by $\frac{\lambda}{2n}$.
Hint 3/4
Here $n=50$, $\hat\beta^{\mathrm{LS}}=(3.0,\ -1.2,\ 0.5,\ 2.0)$ and $\frac{\lambda}{2n}=\frac{100}{100}=1$.
Hint 4/4
Best pair $x_1,x_4$ at $(3.0,\ 2.0)$; lasso $(2.0,\ -0.2,\ 0,\ 1.0)$; the RSS gap is $84.5$.
Show solution
Orthogonality splits both problems into one-coefficient problems, so no matrix has to be inverted.
$0.5<1$ is set to $0$; the others shrink by $1$ toward $0$.
RSS gap
$$50\,(1.44+0.25)=84.5$$
The share of the fit carried by the two dropped coefficients.
Answer $$\boxed{\begin{aligned}&\{x_1,x_4\}\text{ at }(3.0,\ 2.0)\\&\hat\beta^L=(2.0,\ -0.2,\ 0,\ 1.0)\\&\text{RSS gap: }84.5\end{aligned}}$$
Check
Both methods drop $x_3$ first; lasso keeps $x_2$ with a small coefficient where best subset of size 2 drops it, and best subset keeps full-size coefficients where lasso shrinks them.
With orthogonal features best subset is hard thresholding and lasso is soft thresholding of the same least squares coefficients.
2§11.1 — four points, keep one direction
Four centered points have two features and a label. The first feature spreads widely but has nothing to do with the label.
Find
(a) Which single direction in the feature plane keeps the most spread of the features, and what fraction of the total variance does it keep?
(b) How strongly is each feature correlated with $y$, and which one feature would you keep to predict $y$?
(c) Regress $y$ on the points' coordinates along the direction from (a), then on the feature from (b). Compare the two RSS values.
Given
$x_1=(-3,-3,3,3)$
$x_2=(-1,1,-1,1)$
$y=(4,6,4,6)$
$\Sigma=\frac14X^TX$
Hint 1/4
PCA looks only at the features; the correlation score looks at the label. Compute each and compare what they keep.
Hint 2/4
PCA: the top eigenvector of $\Sigma$, with $\mathrm{PVE}=\lambda_1/(\lambda_1+\lambda_2)$. Ranking: $s_j=\hat R_j^2$. One-feature fit: $\mathrm{RSS}=S_{yy}(1-\hat R^2)$.
Hint 3/4
Here $\Sigma=\frac14\begin{bmatrix}36&0\\0&4\end{bmatrix}$, and the deviations of $y$ from its mean $5$ are $(-1,1,-1,1)$, equal to $x_2$.
Hint 4/4
The first component is $(1,0)$ with $\mathrm{PVE}=0.9$; $\hat R_1=0$ and $\hat R_2=1$; RSS $4$ on the component, $0$ on $x_2$.
Show solution
$\Sigma$ turns out diagonal, so both methods reduce to reading off numbers.
Answer $$\boxed{\begin{aligned}&u_1=(1,0),\quad \mathrm{PVE}=0.9\\&\text{keep }x_2\\&\mathrm{RSS}:\ 4\text{ against }0\end{aligned}}$$
Check
The component keeps 9 of the 10 units of feature variance and none of the label's; $x_2$ keeps 1 unit of feature variance and all of the label's.
PCA keeps what varies; selection with the label keeps what predicts. They agree only when the large directions happen to be the useful ones.
3§11.6 — fifty images and five thousand pixels
A student has $n=50$ labelled images and $p=5000$ pixel features that, in truth, are unrelated to the label. She ranks the features by $\hat R_j^2$ on all 50 images, keeps the top 20, and then runs 5-fold cross-validation of least squares on those 20.
Find(a) What will the CV error look like, and what should she do instead?
Given
$n=50$; $p=5000$ features unrelated to $y$
ranking done once, on all 50 images
then 5-fold CV on the 20 kept features
Hint 1/4
Ask whether the held-out images in each fold were really unseen by everything that used the labels.
Hint 2/4
Every step that looks at the labels, feature selection included, must be done on the training part of each fold only.
Hint 3/4
Here the ranking used all 50 labels, so in every fold the 20 kept features were chosen partly for how well they fit the held-out images.
Hint 4/4
The error is too low; the ranking must be repeated inside every fold.
Show solution
The question is not arithmetic but which data each step has seen; following one held-out image through the steps answers it.
Follow one held-out image
$$\text{its label helped rank the features}$$
The ranking of all 5000 features ran before the folds were formed.
$$\text{the kept }20\text{ fit it too well}$$
Out of 5000 unrelated features, the top 20 are the ones that happen to match all 50 labels, this one included.
Consequence and fix
$$\begin{aligned}&\mathrm{CV}\ \text{too low}\\&\text{rank again inside each fold}\end{aligned}$$
Then the held-out images play no part in choosing the features.
Answer $$\boxed{\begin{aligned}&\text{too low: redo the ranking}\\&\text{inside every fold}\end{aligned}}$$
Check
Truth check: the features are unrelated to the label, so no model can beat predicting the mean; a CV error clearly below the null model's error exposes the leak.
Whatever uses the labels belongs inside the cross-validation loop.
4§11.2 — an alarm that never misses
A fault occurs in 1 of every 4 units. A test always fires on a faulty unit, and it also fires on 1 in 3 good units.
Find
(a) How often does the test fire, and when it fires, how likely is a fault?
(b) How many bits does one test result tell about the fault?
Given
$P(Y=1)=\tfrac14$
$P(X=1\mid Y=1)=1$, $P(X=1\mid Y=0)=\tfrac13$
Hint 1/4
Build the joint table of test and fault first; the information then follows by the entropy route.
the steps of feature ranking and the correlation score;
the definition of mutual information and its entropy form;
the two things maximum relevance cannot see;
the maximum dependency rule, its incremental version and both counts;
the mRMR step;
best subset selection, and why RSS cannot choose the size;
forward stepwise selection and its number of fits.
Then reopen the page and compare; whatever is missing is your reread list.
Compute $\hat R_j$ from data, score by $\hat R_j^2$ and build $\tilde D$?
c-ranking
Compute $I(X;Y)$ from a table of counts by both routes, in bits?
c-mutual-info
Show with numbers why two copies or two team-mates fool maximum relevance?
c-max-relevance
Run incremental search from a table, count its evaluations, and say when a joint estimate is not to be trusted?
c-max-dependency
Run mRMR for three steps, averaging the redundancies correctly?
c-mrmr
Find $M_0,\dots,M_p$ from an RSS table and choose the size by cross-validation?
c-best-subset
Trace forward stepwise, count its fits, and spot when it misses the best subset?
c-forward
Glossary (20 terms)
feature selectionöznitelik seçimi
Keeping a subset of the original features, instead of building new ones as PCA does.
feature rankingöznitelik sıralama
Scoring every feature from the data, sorting the scores and keeping the top $k$.
Pearson korelasyon katsayısı
$\operatorname{Cov}(X_j,Y)/\sqrt{\operatorname{Var}(X_j)\operatorname{Var}(Y)}$, between $-1$ and $1$; it measures straight-line association.
entropyentropi
$H(Y)=-\sum_yp(y)\log p(y)$: the uncertainty about $Y$, in bits with base-2 logarithms.
conditional entropykoşullu entropi
$H(Y\mid X)=\sum_xp(x)H(Y\mid X=x)$: the uncertainty about $Y$ left once $X$ is seen.
mutual informationkarşılıklı bilgi
$I(X;Y)=H(Y)-H(Y\mid X)$: how much knowing $X$ reduces the uncertainty about $Y$; zero exactly when they are independent.
relevance
In feature selection, $I(X;Y)$: how much a feature alone tells about the label.
redundancy
In mRMR, the average mutual information between a candidate and the features already chosen.
maximum relevance
Keeping the $k$ features with the largest $I(X_j;Y)$.
maximum dependency
Keeping the $k$-subset $S$ with the largest joint $I(S;Y)$.
incremental search
Growing a feature set one feature at a time, each time adding the feature that most increases the score of the enlarged set.
açgözlü algoritma
An algorithm that takes the best-looking step each time and never revisits it: fast, but it can miss the overall best answer.
mRMR
Minimum redundancy maximum relevance: add the feature with the largest relevance minus average redundancy.
boyut laneti
The number of cells, and of samples needed to fill them, grows exponentially with the number of variables.
plug-in estimate
An estimate that replaces probabilities by relative frequencies from the data.
best subset selectionen iyi alt küme seçimi
Fitting all $2^p$ models, keeping the lowest-RSS model of each size, and choosing the size by cross-validation.
forward stepwise selectionileriye doğru seçim
Adding one feature at a time, the one that lowers RSS most, and choosing the size by cross-validation.
null model
The model with no features, which predicts $\bar y$ for every input.
belirlilik katsayısı
$R^2=1-\mathrm{RSS}/\mathrm{TSS}$: the share of the label's variation a fit explains on the training data.
toplam kareler toplamı
$\mathrm{TSS}=\sum_i(y_i-\bar y)^2$, the RSS of the null model.
What comes next
§12 · Probabilistic graphical models
Here the question was which variables to keep. Next, many variables are kept together, and the dependence between them is drawn as a graph.
Sources
textbookT. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning, Springer (course textbook) The weekly line names no chapter of the book, so no section numbers are cited here.
course materialEEE 485 lecture slides and lecture notes, chapter 11: Feature selection Scope, order of topics and notation (D, the scores and the ranked indices, the reduced data set, R and its estimate, I, H, S, the set of k-subsets, S*, S_l, the added feature, M_0, M_k, RSS) follow these materials; the explanations, data sets, figures and exercises here are original.
course materialEEE 485 syllabus page on STARS, Fall 2026-27, printed 21 September 2026 Assessment weights and the weekly topic list.
standard resultEntropy, mutual information, least squares and cross-validation Standard results used in the derivations. The data sets, numbers and figures were made or computed for this page; the gene data sizes quoted are the lecture's.