January 12, 2024

Feature Selection
Data Mining 11 (データマイニング)

Mahito Sugiyama (杉山麿人)

Today’s Outline• Today’s topic is feature selection– Find relevant variables from datasets• Feature selection detects variables, or features, that are associatedwith the target variable from the set of all variables in a given
dataset– The target variable can be binary (0 and 1 for cases and controls)
in a case-control study or continuous

1/25

Variable Ranking (Filter Method)
1. Measure the degree of association between the target variable
and each variable by some scoring method– Pearson’s correlation coefficient– Mutual information

2. Rank variables using the score• The above two-step procedure is called the filter method

2/25

Pearson’s Correlation Coefficient• (Pearson’s) correlation coefficient 𝜌 measures the linearassociation between two variables– The larger the absolute value |𝜌| is, the stronger the association is– 𝜌 > 0 means the positive correlation, 𝜌 < 0 the negative correlation• 𝜌 between two random variables 𝑋 and 𝑌 is defined as[]𝐄 (𝑋 − 𝐄[𝑋])(𝑌 − 𝐄[𝑌])𝜎𝑋𝑌𝜌==√ [] []𝜎𝑋 𝜎𝑌𝐄 (𝑋 − 𝐸[𝑋])2 𝐄 (𝑌 − 𝐸[𝑌])2– 𝜎𝑋𝑌 is the covariance, 𝜎𝑋 is the standard deviation– 𝐄[𝑋] is the expectation
3/25

Sample Correlation Coefficient• Given a dataset (sample) 𝐷 = {(𝑥1 , 𝑦1 ), (𝑥2 , 𝑦2 ), … , (𝑥𝑁 , 𝑦𝑁 )},the sample correlation coefficient 𝑟 is computed as∑𝑁(𝑥 − 𝑥)(𝑦𝑖 − 𝑦)𝑖=1 𝑖𝑟= √,∑𝑁∑𝑁2𝑥)(𝑥−(𝑦 − 𝑦)2𝑖=1 𝑖
𝑖=1 𝑖
𝑥=𝑁∑1𝑁 𝑖=1𝑥𝑖 ,𝑦=𝑁∑1𝑦𝑁 𝑖=1 𝑖

4/25

Properties of Correlation Coefficient• −1 ≤ 𝜌 ≤ 1 and 1, −1 are the strongest correlation• 𝑋 and 𝑌 are independent ⇐⇒ 𝜌(𝑥) = 0– 𝑋 and 𝑌 are (statistically) independent if
𝑃(𝑋 ∪ 𝑌) = 𝑃(𝑋)𝑃(𝑌)and denoted by 𝑋 ⫫ 𝑌• However, [𝜌(𝑥) = 0 ⇐⇒ 𝑋 and 𝑌 are independent] does not hold– 𝜌(𝑥) can be 0 for nonlinear association

5/25

Mutual Information• For a pair of discrete random variables 𝑋 and 𝑌, the mutual
information is defined as∑ ∑𝑝(𝑥, 𝑦)𝐼(𝑋, 𝑌) =𝑝(𝑥, 𝑦) log ()𝑝(𝑥)𝑝(𝑦)𝑥∈𝑋 𝑦∈𝑌– 𝑝(𝑥, 𝑦): joint probability, 𝑝(𝑥) and 𝑝(𝑦): marginal probability• Properties:– 𝐼(𝑋, 𝑌) ≥ 0– 𝐼(𝑋, 𝑌) = 𝐻(𝑋) + 𝐻(𝑌) − 𝐻(𝑋, 𝑌) = 𝐻(𝑋) − 𝐻(𝑌 | 𝑋)∑◦ 𝐻(𝑋) is the entropy: − 𝑥∈𝑋 𝑝(𝑥) log 𝑝(𝑥)∑∑◦ 𝐻(𝑋, 𝑌) is the joint entropy: − 𝑥∈𝑋 𝑦∈𝑌 𝑝(𝑥, 𝑦) log 𝑝(𝑥, 𝑦)

6/25

Properties of Mutual Information• Pros:– The mutual information can measure both linear and nonlinear
associations◦ 𝑋 and 𝑌 are independent ⇐⇒ 𝐼(𝑋, 𝑌) = 0• Cons:– Additional discretization is needed to estimate the mutual information
for continuous variables– Not normalized in the original form, but can be normalized by𝐼(𝑋, 𝑌)𝐼 ∗ (𝑋, 𝑌) = √𝐻(𝑋)𝐻(𝑌)7/25

Computing the p-value• 𝑝-value shows the probability of getting the dataset with assumingthat there is no association between variables– Often used in science, e.g. biology• Permutation test can be used to compute the 𝑝-value(i) Compute the association score 𝑠 of the given dataset(ii) Repeat the following ℎ times and get ℎ scores 𝑠1 , 𝑠2 , … , 𝑠ℎ :a. Fix 𝑥 and permute indices of 𝑦b. Compute the score using the permuted indices(iii) The 𝑝-value = |{𝑖 ∈ [ℎ] ∣ 𝑠𝑖 > 𝑠}| ∕ ℎ
8/25

Manhattan Plot for Visualization
8–log10(p-value)

64

20

12

34

5678

9 10 11 12 13 14 15 16 17 18 19 20 21 22
Variables

9/25

Properties of Filter Method• Pros:– Easy to use– Easy to understand• Cons:– Redundant features might be selected as interactions between
variables are not considered◦ If a dataset contains exactly the same variables that have thestrong association with the target variable, both variables are
selected

10/25

Wrapper Method• A wrapper method repeats to construct a classifier for each subsetof variables(i) Given a dataset with 𝑛 variables 𝑋 1 , 𝑋 2 , … , 𝑋 𝑛 and a target variable 𝑌(ii) Repeat the following for every subset 𝐼 ⊆ [𝑛]a. Construct a subset of the dataset using only variables in 𝐼
b. Apply classification and measure the goodness (e.g. MSE)(i) Choose the best subset• It is computationally too expensive if 𝑛 is large

11/25

Embedded Method• Variables are automatically selected during the process of learninga prediction model from a dataset• The representative method: the Lasso– It learns a linear prediction model, where a set of variables, which
receive nonzero coefficients, is automatically selected in the learning
process by regularizing the number of variables– The joint additive effect of selected variables maximizes the prediction
accuracy of the model

12/25

The Lasso• The Lasso is the following optimization problem𝑁)21 ∑(min𝑦𝑖 − ⟨𝒘, 𝒙𝑖 ⟩ − 𝑤0𝒘,𝒘0 𝑁
𝑖=1s.t. ‖𝒘‖1 ≤ 𝑡∑𝑛– ‖𝒘‖1 = 𝑗=1 |𝑤𝑗 | (𝓁1 -norm)– Minimizing squared error loss with the constraint• The solution typically has many of the 𝑤 𝑗 equal to zero– {𝑗 ∈ [𝑛] ∣ 𝑤 𝑗 ≠ 0}, called the active set, is considered to be the set ofselected variables
13/25

The Lasso• More convenient Lagrange form of the Lasso;𝑁)2
1 ∑(min𝑦𝑖 − ⟨𝒘, 𝒙𝑖 ⟩ − 𝑤0 + 𝜆‖𝒘‖1𝒘,𝑤0 2𝑁
𝑖=1• If we center the dataset beforehand, it can be written as𝑁()2∑1𝑦𝑖 − ⟨𝒘, 𝒙𝑖 ⟩ + 𝜆‖𝒘‖1 ,min𝒘 2𝑁
𝑖=1min𝒘

1‖𝒚 − 𝑋𝒘‖22 + 𝜆‖𝒘‖1 ,2𝑁
14/25

Lasso Constraint
w2w2
ŵ

ŵ

squared-loss
solutionw1

squared-loss
solution
w1

L1 constraint

L2 constraint
15/25

Regularization Path (𝑁 = 1000, 𝑛 = 100)1305

Number of nonzero variables
5280

99

15

20

0.5
0.0
−1.5 −1.0 −0.5

Coefficients

1.0

1.5010L1 Norm

16/25

MSE (𝑁 = 1000, 𝑛 = 100)
Number of nonzero variables

30
2826
24

Mean−Squared Error

32

99 99 99 98 98 96 95 95 95 93 81 78 69 60 52 40 21 16 12 10 8 3 2 2 2 1 0−6−5−4−3−2log(Lambda)−1017/25

Fitting of the Lasso• Solution of the Lasso problem satisfies the subgradient condition:
1− ⟨𝒙𝑗 , 𝒚 − 𝑋 𝒘⟩
̂ + 𝜆𝑠𝑗 = 0, 𝑗 = 1, 2, … , 𝑛𝑛
– 𝒙𝑗 = (𝑥1 , 𝑥2 , … , 𝑥𝑁 ) ∈ ℝ𝑁
– 𝑠𝑗 = sign(𝑤̂ 𝑗 ) if 𝑤̂ 𝑗 ≠ 0 and 𝑠𝑗 ∈ [−1, 1] if 𝑤̂ 𝑗 = 0𝑗𝑗𝑗

• Thus we have||𝑗 ≠ 0,
⎧ − 1 |||⟨𝒙𝑗 , 𝒚 − 𝑋 𝒘⟩
̂=𝜆,if𝑤||𝑛 |||𝑗 = 0,
⎨ − 1 |||⟨𝒙𝑗 , 𝒚 − 𝑋 𝒘⟩
≤𝜆,if𝑤̂|||⎩ 𝑛• 𝒘
̂ is a piecewise-linear function w.r.t. 𝜆 → LAR algorithm

18/25

Algorithm 1: Least Angle Regression
LAR(𝑋, 𝒚)2Standardize 𝑋 (mean zero, unit 𝓁2 norm)
3
𝒓0 = 𝒚 − 𝒚, 𝒘0 ← (0, 0, … , 0)
4
Find 𝒙𝑗 which has the largest correlation |⟨𝒙𝑗 , 𝒓0 ⟩|5
𝜆0 ← (1∕𝑁)|⟨𝒙𝑗 , 𝒓0 ⟩|; 𝐴 ← {𝑗}; 𝑋𝐴 ← 𝑋 with only 𝐴 = {𝑗}6foreach 𝑘 ∈ {1, 2, … , 𝐾 = min{𝑁 − 1, 𝑛}} do
7
LAREACH(𝑋, 𝒚, 𝐴, 𝜆𝑘−1 , 𝒓𝑘−1 , 𝒘𝑘−1 )119/25

Algorithm 2: Least Angle Regression
LAREACH(𝑋, 𝒚, 𝐴, 𝜆𝑘−1 , 𝒓𝑘−1 , 𝒘𝑘−1 )2𝛿 ← (1∕𝑛𝜆𝑘−1 )(𝑋𝐴𝑇 𝑋)−1 𝑋𝐴𝑇 𝒓𝑘−13∆ ← (0, 0, … , 0); ∆𝐴 ← 𝛿
4Decrease 𝜆 (0 < 𝜆 ≤ 𝜆𝑘−1 ) and find 𝓁 ∉ 𝐴 that first achieves(1∕𝑁)|⟨𝒙𝓁 , 𝒓(𝜆)⟩| = 𝜆, where𝒓(𝜆) = 𝒚 − 𝑋𝒘(𝜆) = 𝒓𝑘−1 − (𝜆𝑘−1 − 𝜆)𝑋𝐴 𝛿,𝒘(𝜆) = 𝒘𝑘−1 + (𝜆𝑘−1 − 𝜆)∆5𝐴 ← 𝐴 ∪ {𝓁}; 𝒘𝑘 ← 𝒘(𝜆); 𝒓𝑘 ← 𝒚 − 𝑋𝒘(𝑘)120/25

Dimension Reduction• Dimension reduction also reduces the number of variables• Variables are not directly selected but transformed into principal
variables• t-SNE (t-distributed stochastic neighbor embedding) is recently
becoming a popular method and often used to visualize amulti-dimensional dataset (van der Maaten and Hinton, 2008)– This can be used for visualization

21/25

t-SNE• Given a dataset 𝐷 = {𝒙1 , 𝒙2 , … , 𝒙𝑁 }, define 𝑝𝑗|𝑖 for each 𝑖, 𝑗 ∈ [𝑁] as()22exp −‖𝒙𝑖 − 𝒙𝑗 ‖ ∕2𝜎𝑖𝑝𝑗|𝑖 = ∑()22exp −‖𝒙𝑖 − 𝒙𝑘 ‖ ∕2𝜎𝑖𝑘≠𝑖– 𝜎𝑖 is the variance of the Gaussian– 𝑝𝑖|𝑖 = 0– We also use 𝑝𝑖𝑗 = (𝑝𝑗|𝑖 + 𝑝𝑖|𝑗 )∕2𝑁

• Goal: Find low-dimensional 𝒚1 , 𝒚2 , … , 𝒚𝑁 of the original
𝒙1 , 𝒙2 , … , 𝒙𝑁 with keeping the proxy between points
22/25

How to Set Variance• Given the perplexity as a parameter, which is defined as
Perp(𝑃𝑖 ) = 2𝐻(𝑃𝑖 )for a distribution 𝑃𝑖 and its entropy 𝐻(𝑃𝑖 ) such that∑
𝐻(𝑃𝑖 ) = − 𝑝𝑗|𝑖 log 𝑝𝑗|𝑖𝑗• For each 𝑖 ∈ [𝑁], find 𝜎𝑖2 that satisfies the given perplexity• In practice, the perplexity from 5 to 50 is recommended

23/25

t-SNE Formulation• For low-dimensional 𝒚𝑖 , 𝒚𝑗 of 𝒙𝑖 , 𝒙𝑗 ,()−121 + ‖𝒚𝑖 − 𝒚𝑗 ‖𝑞𝑖𝑗 = ∑ ∑ ()−12
1 + ‖𝒚𝑘 − 𝒚𝑙 ‖𝑘𝑙≠𝑘• The cost 𝐶 is the KL divergence: 𝐶 = 𝐷KL (𝑃, 𝑄) =∑ ∑𝑖𝑝 log
𝑗 𝑖𝑗

𝑝𝑖𝑗𝑞𝑖𝑗• t-SNE finds low-dimensional 𝒚1 , 𝒚2 , … , 𝒚𝑁 that minimizes the cost 𝐶– The gradient descent can be used for optimization)−1(∑𝜕𝐶2= 4 (𝑝𝑖𝑗 − 𝑞𝑖𝑗 )(𝒚𝑖 − 𝒚𝑗 ) 1 + ‖𝒚𝑖 − 𝒚𝑗 ‖𝜕𝒚𝑖𝑗

24/25

Summary• Feature selection can find relevant variables (features)– Filter method, wrapper method, embedded method• The Lasso is the representative embedded method• t-SNE is the representative dimension reduction method

25/25