# What is a sparse classifier?

Given a two-dimensional data set where each point is labeled $\{0,1\}$, I want to implement a sparse classifier with $L_p \ \text({ 0<p \leq 1) }$.

I have been reading on logistic regression and regularization. Let me give you an example of what I have been working on. The concrete example is: Let $\left((x^{(i)},y^{(i)} )\right)_{i\in \{1,\dots, m\}}$ be my data set with $y^{(i)}\in \{0,1\}$ and $x^{(i)}\in \mathbb{R}^2$. And the cost function I minimized is

$J(\theta) = - \frac{1}{m} \cdot \sum_{i=1}^m \large[ y^{(i)}\ \log (h_\theta (x^{(i)})) + (1 - y^{(i)})\ \log (1 - h_\theta(x^{(i)}))\large] + \frac{\lambda}{2m}\sum_{j=1}^n \theta_j^2$.

where $h_\theta(x) = \frac{1}{1+e^{-\theta^{T}x}}$. I thought that this would be a good introduction to sparse.
Currently I use a neural networks and was wondering if I am heading in the right direction in understanding sparse methods.

That leaves me with the question:

What is the definition of sparse classifiers? What would be an example?

• Is your question really "I want to build a sparse classifier. What is a sparse classifier?" If you don't know what a sparse classifier is, why do you think you want one? – D.W. Aug 10 '16 at 14:58
• Well I have an idea what it is. Namely a sparse classifier is just a classifier that tries to set most estimation parameter to zero. for example let $J(\theta) = |y - X\theta|_{2}^{2} + \lambda|\theta|_{2}^2$ be a cost function a sparse methods helps to approximate $\theta$ so that most entries are zero. And using the $L_p$ norm on sequences/vector spaces means that the $|.|_p$ norm. I assume that a sparse classifier will diminish the noise of non zero entries. However this might not be the right definition. I like to clarify and find concise definition. – A.Dumas Aug 10 '16 at 17:43
• But let answer your questions @D.W. the sparse classifier is a state of the art classifier that is worth researching and I like do it for a project. – A.Dumas Aug 10 '16 at 18:16

Sparse linear regression is used when we have a model $y = X\beta + \epsilon$ where $y \in \mathbb{R}^n$, $X \in \mathbb{R}^{n \times p}$, $\beta \in \mathbb{R}^p$ and $\epsilon \in \mathbb{R}^n$ when $n \ll p$. If we expect only a small number of columns in $X$ to actually contribute to $y$ then we can impose a penalty on $\beta$ such that "non-important" columns $X_i$ have their corresponding $\beta_i = 0$. We can formally write this as $$\arg \min_{\beta} \|y - X\beta \|^2_2 + \lambda\|\beta\|_0$$ where $\|\cdot\|_0$ is the $\ell_0$ norm that counts the number of non-zero entries. Unfortunately fitting this model exactly is difficult. We can approximate this objective by using the $\ell_1$ norm instead. That is we find $\beta$ for $$\arg \min_{\beta} \|y - X\beta \|^2_2 + \lambda\|\beta\|_1.$$ This model is known as LASSO in the context of linear regression and can be fit by a variety of methods in relatively little time.
All of this hinges on $n \ll p$. If your data are of the form when $n \approx p$ or $n > p$ I'm not sure if sparsity will help much, as you should have enough data to guide inference to true $\beta$ values (provided other assumptions hold, heteroskedasticity, independence, etc). The key takeaway is that you have a large number of predictors and you suspect a small amount of them to actually characterize $y$.