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?

  • 1
    $\begingroup$ 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? $\endgroup$
    – D.W.
    Aug 10 '16 at 14:58
  • 1
    $\begingroup$ 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. $\endgroup$
    – A.Dumas
    Aug 10 '16 at 17:43
  • $\begingroup$ 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. $\endgroup$
    – A.Dumas
    Aug 10 '16 at 18:16

I'll provide an example model using linear regression, however the idea translates to classification in a straightforward manner.

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$.


Sparsity implies that only a small portion of input variables are influencing classification. So sparse classifier's job is to find this small portion of variables. An example would be L1-norm based SVM.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.