12
$\begingroup$

I'm trying to classify messages into different categories using an SVM. I've compiled a list of desirable words/symbols from the training set.

For each vector, which represents a message, I set the corresponding row to 1 if the word is present:

"corpus" is: [mary, little, lamb, star, twinkle]

first message: "mary had a little lamb" -> [1 1 1 0 0]

second message: "twinkle little star" -> [0 1 0 1 1]

I think this is fairly common setup with SVM, but my question is, with thousands of words in the set, what if there's only 1-2 words per message that actually show up? Is the linear dependence of my set of training vectors going to adversely affect the ability of the algorithm to converge?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Do you have a lot of data, but little labeled data? If so you might wanna look into semi-supervised learning. Using some of your unlabeled data should both increase your accuracy and decrease the risk of overfitting. $\endgroup$ – neuron Feb 10 '12 at 9:17
  • $\begingroup$ @neuron I had thought about doing that. What is an example of a semi-supervised architecture? $\endgroup$ – jonsca Feb 10 '12 at 9:21
  • 1
    $\begingroup$ I've only used "hackish" methods of semi-supervised (aka train model on trainingset, use model to predict on data, pull all data with a prediction probability of > 0.5 and merge with trainingset, and create moel on new trainingset). But I've seen flexmix mentioned a few places (see cran.r-project.org/web/packages/flexmix ) $\endgroup$ – neuron Feb 11 '12 at 9:43
  • $\begingroup$ @neuron Okay, good, because the articles I saw (albeit with a quick wikipedia-like search) weren't very specific about architectures. I will check out flexmix -- though, I've had "Learn R" on my calendar for a couple of years now! $\endgroup$ – jonsca Feb 11 '12 at 9:46
  • $\begingroup$ Do it, R is AMAZING, the libraries that become available to you are just mind boggling. Things like caret, sqldf/rmysql, foreach (parallel for), ggplot2 and googlevis are just amazingly helpfull tools. I wasn't a fan of the language at first, but it's grown on me, and I absolutely love using it now. $\endgroup$ – neuron Feb 12 '12 at 12:31
9
$\begingroup$

Sparsity and linear dependence are two different things. Linear dependence implies that some of the feature vectors are simple multiples of other feature vectors (or the same applied to examples). In the setup you have described I think linear dependence is unlikely (it implies two terms have the same frequency (or multiples thereof) across all documents). Simply having sparse features does not present any problem for the SVM. One way to see this is that you could do a random rotation of the co-ordinate axes, which would leave the problem unchanged and give the same solution, but would make the data completely non-sparse (this is in part how random projections work).

Also it appears that you are talking about the SVM in the primal. Note that if you use the kernel SVM, just because you have a sparse dataset does not mean that the kernel matrix will be sparse. It may, however, be low rank. In that case you can actually take advantage of this fact for more efficient training (see for example Efficient svm training using low-rank kernel representations).

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ True, I was a bit fast and loose with my terminology. Makes sense. $\endgroup$ – jonsca Feb 10 '12 at 9:07

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.