Draft:Infinite Feature Selection (Inf-FS)

Infinite Feature Selection

Infinite Feature Selection (Inf-FS) is an unsupervised algorithm for ranking features by their global importance, using a graph-based representation of pairwise feature affinities. It was first introduced by Giorgio Roffo and colleagues at the IEEE International Conference on Computer Vision in 2015.

While originally designed for feature filtering in classical machine learning pipelines, Inf-FS has since been recognized as an early mathematical formulation of the attention mechanism used in deep learning models such as Transformers. Recent work shows that the structure and computation in Inf-FS is mathematically equivalent to self-attention under specific parameterizations.

Method

Inf-FS models each feature as a node in a fully connected undirected graph. The edge weights between nodes represent pairwise affinity, typically computed based on correlation or mutual information. These relationships are encoded in an affinity matrix $A\in \mathbb {R} ^{N\times N}$, where $N$ is the number of features.

The algorithm computes feature importance through an infinite sum over powers of $A$, capturing all multi-hop interactions:

$S=\sum _{k=1}^{\infty }\alpha ^{k}A^{k}=(I-\alpha A)^{-1}-I$

Here, $\alpha$ is a regularization parameter such that $0<\alpha <1/\rho (A)$, where $\rho (A)$ is the spectral radius of $A$.

Feature scores are derived by summing the rows of $S$:

$s(i)=[S\cdot \mathbf {1} ]_{i}$

This yields a global relevance score for each feature, reflecting its contextual influence across the graph.

Variants

A probabilistic extension called Infinite Latent Feature Selection (ILFS) was proposed in 2017, which infers a latent distribution over affinities using data-driven modeling. This approach allows the affinity matrix to be learned rather than manually defined.

Relationship to Self-Attention

Inf-FS has been shown to share the same underlying structure as self-attention mechanisms. Both compute contextual weights based on an affinity matrix $A$ between elements (features or tokens). The key difference lies in how $A$ is constructed:

• In Inf-FS, $A$ can be handcrafted or probabilistically inferred.
• In Transformers, $A=QK^{\top }/{\sqrt {d_{k}}}$, where $Q$ and $K$ are learned projections of the input.

Importantly, when the infinite power series in Inf-FS is truncated to just one term (i.e., $A$), the resulting computation mirrors the dot-product attention used in Transformers. This establishes Inf-FS as a superset of self-attention, generalizing the mechanism to arbitrary affinity structures and multi-hop propagation.

Theoretical Foundations

A 2024 study by Teo and Nguyen demonstrated that self-attention can be derived as a projection operation from kernel principal component analysis (kernel PCA). In this framework, the attention output corresponds to projecting query vectors onto the eigenvectors of the Gram matrix of the key vectors, in an implicitly defined kernel space:

$h_{i}=\sum _{j=1}^{N}{\text{softmax}}\left({\frac {q_{i}^{\top }k_{j}}{\sqrt {d_{k}}}}\right)v_{j}$

This matches the original Inf-FS power series when kernel affinity matrices are used, further validating the shared mathematical foundation between the two mechanisms.

Historical Context

The use of affinity matrices in machine learning predates Inf-FS. Notable precursors include the bilateral filter (1998), PageRank (1998), and non-local means (2005), all of which rely on propagating influence over graphs.

Inf-FS was the first to formalize the idea of using infinite-path propagation over an affinity graph for feature relevance. The connection to attention mechanisms became more explicit after the advent of the Transformer architecture in 2017.

Applications

Inf-FS has been used in:

• Feature selection for high-dimensional biomedical data
• Visual tracking and object detection
• Text and document classification
• Dimensionality reduction prior to clustering

Its unsupervised nature makes it useful in low-label settings or where model interpretability is critical.

See also

• Self-attention
• Transformer (machine learning model)
• Feature selection
• Graph-based learning
• Kernel methods