# Subset selection / feature selection with a categorical response variable

There are a number of helpful posts on subset selection (or feature selection) with continuous or binary response variables (i.e., here). However, I've not been able to find any posts on subset selection with categorical response variables.

Would discriminant function analysis be a promising starting point for subset selection with a categorical response variable? And are there any standard approaches?

You can train a classifier (e.g. multi-class SVM) with sparsity inducing regularization including $\ell_1$ or $\ell_1/\ell_2$ to ignore dimensions (or groups of dimensions) in the original feature vector that carry little information, as far as the classification task is concerned.

Let $\mathcal{D} = \{(x_i, y_i)\}_{i=1}^n$ denote a set of $n$ labeled training examples where $y_i \in \{1, \dots, K\}$. The training objective of an $\ell_1/\ell_2$ regularized max-margin classifier with hinge loss (multi-class SVM) can be defined as follows: $$O(w) = \lambda \sum_{g \in G} \sqrt{||w_g||^2} + \sum_{i=1}^n \left( \max_{y=1}^K \left( w \cdot \Phi(x_y, y) + \Delta(y, y_i) \right) - w \cdot \Phi(x_i, y_i) \right) \tag{1}$$ where $w = (w_1; w_2; \dots; w_K)$ is the classifier and $\Phi(x, y)$ is a $Kd$-dimensional feature vector with $K$ blocks of length $d$ each, where all the blocks are zero except for the $y$-th block which is some feature extracted from the image $\phi(x) \in \mathbb{R}^d$: $$\Phi(x, y) = \left( \overbrace{\underbrace{\mathbf{0}; \mathbf{0}; \dots}_{y-1 \text{ blocks}}; \phi(x); \mathbf{0}; \dots}^{K \text{ blocks}} \right) \in \mathbb{R}^{Kd}. \tag{2}$$ Also, $\Delta(y, y_i) = \mathbf{1}\{y \neq y_i\}$ is the $0/1$ loss function, and the second term in $(1)$ computes the hinge loss of the model on the training example $(x_i, y_i)$.

# References

• You can find more details on group sparsity regularization here.

• implementation of $\ell_1$ regularized multi-class SVM implementation in C++ with Python and Matlab interface can be found here (public source code).

• Thanks, wondering if you could help with two-follows ups: 1) are there implementations of SVM w/ sparsity inducing regularization in R / Python? and 2) would an approach like discriminant function analysis work (somewhat) similar / different? Dec 10, 2015 at 23:36
• I am not familiar with discriminant function analysis; I skimmed through the wikipedia page before writing my answer and it seemed to me that it is different from multi-class SVM with $\ell_1$ or $\ell_1 / \ell_2$ regularization. Sorry that I cannot provide more information at this time. If I find time I will read it more carefully and will get back to you if I have more to add. Regarding SVM implementations, here is a link to a C++ implementation of SVM with $\ell_1$ regularization: csie.ntu.edu.tw/~cjlin/liblinear. The code only does binary classification though!
– Sobi
Dec 11, 2015 at 0:06
• Here is another implementation that does multi-class classification, supports $\ell_1$ regularization, and also has a python wrapper (although the core code is implemented in C++). I am not aware of public (good) implementations of $\ell_1 / \ell_2$ regularization; instead, I refer you to Francis Bach and Julien Mairal as they are among the world's leaders in the field and may have (reference to) publicly available implementations of it on their webpages. I will add the references in my answer.
– Sobi
Dec 11, 2015 at 0:12