Two directions of relevance · Rényi mRMR: which direction of Arimoto information?

Why the side of Arimoto information you pick decides how rare features are treated.

Throughout, $f$ is a binary feature (a word present or absent), $C$ the class, $q_c = P(f=1\mid C=c)$ the word’s rate in class $c$, and $q$ its overall rate.

Definition (two relevances). Feature side $I_\alpha(f;C)$: how much knowing the class tells you about whether the word appears. Class side $I_\alpha(C;f)$: how much seeing the word tells you about the class. Shannon ($\alpha=1$) cannot tell them apart; Rényi can.

Why feature-side min-entropy relevance vanishes

Rare wordPresent in at most half of every class.
Same best guess“Absent” is the best guess of f, whatever the class.
Zero relevanceI∞(f;C) = 0, by Proposition 1.
Ties at 0Almost every candidate scores exactly 0.
Index walkThe argmax returns features in file order.

How a rare word ends up with zero relevance and the selector falls back to file order.

At $\alpha=\infty$, Lemma 1 gives

I_\infty(X;Y) = \log \frac{\sum_y \max_x P(x,y)}{\max_x P(x)},

Read this equation

The bottom is your chance of guessing $X$ with no help: always say its most likely value. The top is your chance when you see $Y$ first and pick the best $X$ for each $Y$. The log of their ratio is how much seeing $Y$ improves the guess. If the best guess never changes, top and bottom are equal and the information is $0$.

the gain in the probability of guessing $X$ correctly after seeing $Y$. It is zero exactly when the best guess of $X$ is the same whatever $Y$ is (Proposition 1)[2].

If every $q_c \le \tfrac12$, the best guess of $f$ is “absent” in every class and before knowing the class. The numerator is $\sum_c \pi_c(1-q_c) = 1-q$, the denominator is $1-q$, so the relevance is $0$.

Example (BASEHOCK word 2004). BASEHOCK word 2004 occurs in 0.9% of one class and 39% of the other: strongly informative, yet $I_\infty(f;C)=0$. On the class side, $I_\infty(C;f) = \log_2(1+|q_1-q_2|) = \log_2(1.382) \approx 0.47$ bits.

The scaling law

For a rare word ($q\to 0$) with fixed lifts $\lambda_c = q_c/q$ (Theorem 1), feature-side relevance shrinks like $q^\alpha$ and class-side like $q$:

I_\alpha(f;C) \approx q^\alpha\,\frac{\sum_c \pi_c\lambda_c^\alpha - 1}{(\alpha-1)\ln 2}, \qquad I_\alpha(C;f) \approx \text{const}\cdot q.

Read this equation

Keep each class’s lift fixed and let the word get rarer. The feature side carries a factor $q^\alpha$, so at $\alpha = 2$ halving $q$ cuts it by four; the class side only halves. The fraction on the left depends on the lifts, not on $q$: it measures how unevenly the word is spread across classes.

So their ratio is about $q^{\alpha-1}$. On BASEHOCK the median rate is $q \approx 0.0057$, and the observed medians follow the prediction across nine orders of magnitude.

Rényi order α 2Word rate q 0.57%

At α = 2, a word in 0.57% of documents keeps only 0.0057 of its class-side relevance on the feature side.

Feature-side ÷ class-side relevance

Predicted, q^(α−1)
Observed median, BASEHOCK

Drag α to see how far feature-side relevance falls behind the class side for a word as rare as BASEHOCK's median. The dots are the observed medians.

Show the data

Rényi order α	Predicted, q^(α−1)	Observed median, BASEHOCK
0.5	13.2	12.1
2	0.0057	0.0068
5	1.1 × 10⁻⁹	3.1 × 10⁻⁹

Ratio of feature-side to class-side relevance on BASEHOCK, predicted as about $q^{\alpha-1}$.

α	Predicted ratio (q ≈ 0.0057)	Observed median ratio
0.5	≈ 13	12.1
2	5.7 × 10⁻³	6.8 × 10⁻³
5	1.1 × 10⁻⁹	3.1 × 10⁻⁹

Non-asymptotic bounds for α > 1

If every $q_c \le \rho < 1$ (Proposition 2):

0 \le I_\alpha(f;C) \le \frac{1}{(\alpha-1)\ln 2}\cdot\frac{q}{1-q}\cdot\Big(\frac{\rho}{1-\rho}\Big)^{\alpha-1}.

Read this equation

This holds for any $q$, not only in the limit. The bound is the rate odds $q/(1-q)$ times a factor that shrinks geometrically in $\alpha$ whenever $\rho < \tfrac12$, so for rare words the feature side is small at every order above 1.

Why the selector walks in index order

At $\alpha=\infty$ on the feature side almost every relevance and redundancy is exactly $0$. After the few informative features (two on BASEHOCK, one on RELATHE, none on PCMAC), every candidate ties at score $0$, and the argmax returns the lowest indexPython’s max and NumPy’s argmax both return the first of equal values.: features 0, 1, 2, 3… in file order (Proposition 3). This was checked at all 2920 such steps across 20 splits of the three text sets; every pick matched.

If a reviewer asks “why not break ties at random?”

It doesn’t help: none of the tied features carries any class information under this measure. On GISETTE the walk never starts, because about 121 features with non-zero relevance outnumber the 50 selections.