6 ms·

An Idiot’s guide to Support vector machines (2003) [pdf]

145 points by headalgorithm 6y ago

ejanus 6y ago
Looking for simple implementation of primal and dual algorithms.
cageface 6y ago
Are support vector machines still used much or have they been supplanted by deep learning methods?
- fnbr 6y ago
  They’re really useful (and arguably state of the art) in situations with small amounts of data. Deep learning is really hard to productionize, so classical techniques like SVMs and random forests are widely used in production. Deep learning is too, but not as much as you’d think.
  - Ozzie_osman 6y ago
    I graduated in 2006 (undergrad CS degree), and at the time, we were told SVMs were a lot more practical than something like neural nets. Neural nets were framed as "we will teach you this thing because it's fun to code back-prop and it kind of works in a way we think your brain does too, but no one really uses them in real-life, except for classifying digits". Funny how times have changed.
    - frequentnapper 6y ago
      Even in 2014 (grad cs degree), my data mining professor said SVM were advantageous over neural nets due to local maxima problem, so we never learned neural nets in class.
      - hikarudo 6y ago
        That's a bit weird. Sure it's an advantage if you can optimize the object function more easily. But the end goal is generalization, i.e. performance on new data. The objective function is only a proxy for that.
    - dimatura 6y ago
      Funny how that happens. In 2006 I was taken a grad-level Intro to ML course. After the first (and only) lecture on neural nets, I asked the prof on recommendations for learning more - since I had mostly a cogsci background, I was pretty interested because of the "neural" part. The prof essentially said the same as yours (I don't blame him -- it was a common sentiment of the time). And of course, these days he's doing deep learning!
- ganstyles 6y ago
  Yeah they're still used. When approaching a new problem I reach for linear methods first if it seems like they could work. DNNs are amazing, but can be very heavy handed and use significantly more resources, which isn't desirable unless needed or one is working with a complex problem. I've even used DNNs when I couldn't make SVMs work, but someone more experienced came along and showed me a kernel method that for the trick with an SVM. In short, it's a great tool if it works.
- blululu 6y ago
  For large data yes. For small data sets feature engineering is often more important than the machine learning model used. (Kaggle contests are frequently are won by Random Forrests + Feature Engineering) Another important thing to consider is that a lot of the actual work in setting up a machine learning pipeline has nothing to do with machine learning (making sure that data is clean, exceptions are handled, etc). On a small data set an SVM can achieve good performance out of the box. Starting with an SVM can be a really helpful in validating the basic approach and understand the nature of the problem before you sink in a bunch to time/money collecting data and training a complicated model.
- hivacruz 6y ago
  I still use them. I had to make a few binary and multi class classification models in NLP and while Transformers models gave nice results, it was impossible for me to use them long term. Why? Because data were confidential, I could not use the Cloud to get a nice GPU, and I needed almost one model per enterprise. Training DistilBert for 3 epochs was like 12 hours and it was a domain where data/concept drift happen often which means re-training was mandatory on weekly basis, at least. After some feature engineering, I was able to get almost the same performance (<1% difference) with a model that was able to train in less than 5 minutes and could be use in production easily. I love the fact that SVM, at least in scikit-learn, have a built-in early stopping mechanism. Really handy.
- lerax 6y ago
  I used at work as part of a NLP system to extract valid relations between named entities on context of politics. Since I didn't have labeled data before, I annotated some hundreds by myself, and because was not much label data SVM outperforms other models (compared with ANN, Gaussian Process, KNN, Naive Bayes, and others that I forgot). The best kernel for this approach was a Linear one. The system has a compound set of machine learning models and parsers to finally extract from the government official public news (http://in.gov.br http://in.gov.br) documents with the following structured info: - who was/will hired and fired (PERSON entity) - which job role it will/did have. (JOB entity) - when will happens¹ (DATE entity) Each entity is extracted individually using a custom trained NER and each sentence is passed to the Relation Extraction system, which is built using SVM. Features are concatenated word vectors² compound by the slices of the text in the form (entity1, entity2, before, between, after). The system is being alive for almost two years. It produces great results. Just did need retrain the entity recognizer twice in all that time (built using spacy which uses a averaged perceptron). The SVM part (Relation Extraction) was not retrained since the first day deployed and it still works gracefully :D ¹this info is on the text as natural lang, sometimes is different from the post date ²gensim.Word2Vec custom model trained on this corpus.
  - ejanus 6y ago
    I would like to under how you solved your feature engineering issues?
    - lerax 6y ago
      In general I used a custom word vector model with a fixed dimension of n=100. As you should now, this feature transformer only maps word to vectors, but I have a more complex structure than just words to work on. The model works sentence wise and preparsing of text is made, let's say I have the following sentence: "Hire Bill Gates as Front-End Developer at 05/05/2020" Suppose the NER extracts the following entities from it: - Bill Gates (PERSON) - Front-End Developer (JOB) - 05/05/2020 (DATE) In my domain problem, I need the relation PERSON-JOB-DATE, which can be decomposed in two binary relations: PERSON-JOB and JOB-DATE. Each binary relation it's a model by itself with the following class outcomes: invalid, hiring, firing. If two binary relations has the same job and outcome classes, I build the triple PERSON-JOB-DATE. At feature engineering level, which is you asked for, I build a tuple of local attention from entities perspective based on slices of the text: (entity1, entity2, before, between, after). Each part it's transformed into a vector by using average word vector and finally each part it's concatenated in a final vector that will be used by SVM. Since word vector dimension I choose in my experiments was n=100, my model will have n=500 features. An example about the slices for PERSON-JOB it will be: ("Bill Gates", "Front-End Developer", "Hire", "as", "at 05/05/2020") 1. Each element of the tuple is tokenized 2. With tokens available, use word vector model to transform each one. 3. For each element of the tuple take the average of the vectors. 4. Concatenate each averaged vector into a final vector. Using that structure the model is biased strongly by how the sentence is written with the words around of the entities. For my domain where the sentences are very regular it worked well. I am not sure if will work in more general domain, like social media. I hope this clarify your question in some level.
dang 6y ago
See also from 2018: https://news.ycombinator.com/item?id=18794545 https://news.ycombinator.com/item?id=18794545
zmmmmm 6y ago
I've been through SVM explanations before and I always get to the part where they start talking about kernels and the logic seems recursive. ie: if your data isn't linearly separable, let's choose a kernel that matches the shape of the data, and like magic it's now separable. But guess what, the reason I'm doing machine learning is I don't know the shape of my data. If I knew that, and if there was actually a simple transformation, I would just transform it in the first place and use a linear model. So it seems like a bit of a bait and switch. Is there some part of this that can automatically select a transformation in a similar manner to tuning hyper parameters in a neural net? Would love it if anybody would explain this to me :-)
- blackbear_ 6y ago
  The RBF kernel nakes any dataset linearly separable, as long as the bandwidth is small enough (but then you might be overfitting). And certainly you can automatically select the kernel, it is just a hyperparameter after all: try different kernels and are what works best. You can even create a composite kernel as a weighted sum of several simpler kernels, and find the best weights while fitting the model.
  - ethelward 6y ago
    > The RBF kernel nakes any dataset linearly separable, as long as the bandwidth is small enough That's very interesting, would you happen to have the paper proving that somewhere?
    - blackbear_ 6y ago
      > would you happen to have the paper proving that somewhere? Actually no I don't, but here's the intuition. Consider what happens in the limit when the bandwidth goes to zero: the kernel collapses to a delta function, i.e. K(x_i, x_j)=1 when i=j and 0 otherwise. The kernel matrix approaches the identity. The optimal coefficients solving the quadratic program approach zero. The SVM predicts zero almost everywhere except in a smaller and smaller surrounding of the training points, where the prediction equals the label of that point.
nathell 6y ago
I wish people stopped using disparaging terms, especially in titles. I skimmed through the presentation and initially felt overwhelmed by the amount of heavy linear algebra going on in there. Now, that's not a criticism of the document itself – there's probably no way around that – but if I were to give up because of failing to understand the content, the corollary would be "I'm not even an idiot", and that really doesn't help anyone. If the title were "A guide to SVMs", it would be just as descriptive, while avoiding calling people names.
- mayankkaizen 6y ago
  OTOH, these kind of titles actually attract me to the articles in the areas I have very little clue about. They give me the impression that authors have introduced the subject matter in the most accessible ELI5 style.
- therealcamino 6y ago
  I had the same reaction, and then I remembered that series of books "The Complete Idiot's Guide To..." that was popular at the time. It's probably a reference to that, and intended as a joke given the background needed to understand the presentation. https://apnews.com/dd0d4d10c6ce8f698cb325a72ee82b97 https://apnews.com/dd0d4d10c6ce8f698cb325a72ee82b97
- mumblemumble 6y ago
  I've never liked the "idiot's guide" or "for dummies" thing, either. But, FWIW, keep in mind that this is a slide deck taken out of context. In context, it was probably being presented to an audience where a certain level of background knowledge could be more safely assumed. And, in context, it was probably being presented by a real live human. That means that there was a whole lot of more detailed explanation that is not available if you're just reading the deck. And also a human face to make any tongue-in-cheek bits (I'm guessing the title was meant to be at least a little bit irreverent) more apparent.
dijksterhuis 6y ago
I've always used https://www.svm-tutorial.com/ https://www.svm-tutorial.com/ as my go-to suggestion for reading up on SVMs as it starts easy and progressively adds the complexity as needed. > This tutorial series is intended to give you all the necessary tools to really understand the math behind SVM. It starts softly and then get more complicated. But my goal here is to keep everybody on board, especially people who do not have a strong mathematical background. Emphasis mine.
- rubyfan 6y ago
  i appreciate the practical usage focus here with software tutorials
frumiousirc 6y ago
This gives a very helpful geometrical description which finally let SVMs make sense to me. The weights are a vector normal to a family of planes and the optimization finds the two parallel planes that most separate two categories of data. Solving the optimization is performed in terms of the inner product of data vectors. This inner product can be replaced by a function of the inner product (the kernel) in order to transform the data which may otherwise overlap into a space where a separating plane may be found.
ajflores1604 6y ago
This video on svm has helped me grok it more than any other resource to date. Actually the whole channel is full of great breakdowns https://youtu.be/efR1C6CvhmE https://youtu.be/efR1C6CvhmE

145 points by headalgorithm 6y ago

ejanus 6y ago

Looking for simple implementation of primal and dual algorithms.

cageface 6y ago

Are support vector machines still used much or have they been supplanted by deep learning methods?

fnbr 6y ago
They’re really useful (and arguably state of the art) in situations with small amounts of data. Deep learning is really hard to productionize, so classical techniques like SVMs and random forests are widely used in production. Deep learning is too, but not as much as you’d think.
- Ozzie_osman 6y ago
  I graduated in 2006 (undergrad CS degree), and at the time, we were told SVMs were a lot more practical than something like neural nets. Neural nets were framed as "we will teach you this thing because it's fun to code back-prop and it kind of works in a way we think your brain does too, but no one really uses them in real-life, except for classifying digits". Funny how times have changed.
  - frequentnapper 6y ago
    Even in 2014 (grad cs degree), my data mining professor said SVM were advantageous over neural nets due to local maxima problem, so we never learned neural nets in class.
    - hikarudo 6y ago
      That's a bit weird. Sure it's an advantage if you can optimize the object function more easily. But the end goal is generalization, i.e. performance on new data. The objective function is only a proxy for that.
  - dimatura 6y ago
    Funny how that happens. In 2006 I was taken a grad-level Intro to ML course. After the first (and only) lecture on neural nets, I asked the prof on recommendations for learning more - since I had mostly a cogsci background, I was pretty interested because of the "neural" part. The prof essentially said the same as yours (I don't blame him -- it was a common sentiment of the time). And of course, these days he's doing deep learning!
ganstyles 6y ago
Yeah they're still used. When approaching a new problem I reach for linear methods first if it seems like they could work. DNNs are amazing, but can be very heavy handed and use significantly more resources, which isn't desirable unless needed or one is working with a complex problem. I've even used DNNs when I couldn't make SVMs work, but someone more experienced came along and showed me a kernel method that for the trick with an SVM. In short, it's a great tool if it works.
blululu 6y ago
For large data yes. For small data sets feature engineering is often more important than the machine learning model used. (Kaggle contests are frequently are won by Random Forrests + Feature Engineering) Another important thing to consider is that a lot of the actual work in setting up a machine learning pipeline has nothing to do with machine learning (making sure that data is clean, exceptions are handled, etc). On a small data set an SVM can achieve good performance out of the box. Starting with an SVM can be a really helpful in validating the basic approach and understand the nature of the problem before you sink in a bunch to time/money collecting data and training a complicated model.
hivacruz 6y ago
I still use them. I had to make a few binary and multi class classification models in NLP and while Transformers models gave nice results, it was impossible for me to use them long term. Why? Because data were confidential, I could not use the Cloud to get a nice GPU, and I needed almost one model per enterprise. Training DistilBert for 3 epochs was like 12 hours and it was a domain where data/concept drift happen often which means re-training was mandatory on weekly basis, at least. After some feature engineering, I was able to get almost the same performance (<1% difference) with a model that was able to train in less than 5 minutes and could be use in production easily. I love the fact that SVM, at least in scikit-learn, have a built-in early stopping mechanism. Really handy.
lerax 6y ago
I used at work as part of a NLP system to extract valid relations between named entities on context of politics. Since I didn't have labeled data before, I annotated some hundreds by myself, and because was not much label data SVM outperforms other models (compared with ANN, Gaussian Process, KNN, Naive Bayes, and others that I forgot). The best kernel for this approach was a Linear one. The system has a compound set of machine learning models and parsers to finally extract from the government official public news (http://in.gov.br http://in.gov.br) documents with the following structured info: - who was/will hired and fired (PERSON entity) - which job role it will/did have. (JOB entity) - when will happens¹ (DATE entity) Each entity is extracted individually using a custom trained NER and each sentence is passed to the Relation Extraction system, which is built using SVM. Features are concatenated word vectors² compound by the slices of the text in the form (entity1, entity2, before, between, after). The system is being alive for almost two years. It produces great results. Just did need retrain the entity recognizer twice in all that time (built using spacy which uses a averaged perceptron). The SVM part (Relation Extraction) was not retrained since the first day deployed and it still works gracefully :D ¹this info is on the text as natural lang, sometimes is different from the post date ²gensim.Word2Vec custom model trained on this corpus.
- ejanus 6y ago
  I would like to under how you solved your feature engineering issues?
  - lerax 6y ago
    In general I used a custom word vector model with a fixed dimension of n=100. As you should now, this feature transformer only maps word to vectors, but I have a more complex structure than just words to work on. The model works sentence wise and preparsing of text is made, let's say I have the following sentence: "Hire Bill Gates as Front-End Developer at 05/05/2020" Suppose the NER extracts the following entities from it: - Bill Gates (PERSON) - Front-End Developer (JOB) - 05/05/2020 (DATE) In my domain problem, I need the relation PERSON-JOB-DATE, which can be decomposed in two binary relations: PERSON-JOB and JOB-DATE. Each binary relation it's a model by itself with the following class outcomes: invalid, hiring, firing. If two binary relations has the same job and outcome classes, I build the triple PERSON-JOB-DATE. At feature engineering level, which is you asked for, I build a tuple of local attention from entities perspective based on slices of the text: (entity1, entity2, before, between, after). Each part it's transformed into a vector by using average word vector and finally each part it's concatenated in a final vector that will be used by SVM. Since word vector dimension I choose in my experiments was n=100, my model will have n=500 features. An example about the slices for PERSON-JOB it will be: ("Bill Gates", "Front-End Developer", "Hire", "as", "at 05/05/2020") 1. Each element of the tuple is tokenized 2. With tokens available, use word vector model to transform each one. 3. For each element of the tuple take the average of the vectors. 4. Concatenate each averaged vector into a final vector. Using that structure the model is biased strongly by how the sentence is written with the words around of the entities. For my domain where the sentences are very regular it worked well. I am not sure if will work in more general domain, like social media. I hope this clarify your question in some level.

dang 6y ago

See also from 2018: https://news.ycombinator.com/item?id=18794545 https://news.ycombinator.com/item?id=18794545

zmmmmm 6y ago

I've been through SVM explanations before and I always get to the part where they start talking about kernels and the logic seems recursive. ie: if your data isn't linearly separable, let's choose a kernel that matches the shape of the data, and like magic it's now separable. But guess what, the reason I'm doing machine learning is I don't know the shape of my data. If I knew that, and if there was actually a simple transformation, I would just transform it in the first place and use a linear model. So it seems like a bit of a bait and switch. Is there some part of this that can automatically select a transformation in a similar manner to tuning hyper parameters in a neural net? Would love it if anybody would explain this to me :-)

blackbear_ 6y ago
The RBF kernel nakes any dataset linearly separable, as long as the bandwidth is small enough (but then you might be overfitting). And certainly you can automatically select the kernel, it is just a hyperparameter after all: try different kernels and are what works best. You can even create a composite kernel as a weighted sum of several simpler kernels, and find the best weights while fitting the model.
- ethelward 6y ago
  > The RBF kernel nakes any dataset linearly separable, as long as the bandwidth is small enough That's very interesting, would you happen to have the paper proving that somewhere?
  - blackbear_ 6y ago
    > would you happen to have the paper proving that somewhere? Actually no I don't, but here's the intuition. Consider what happens in the limit when the bandwidth goes to zero: the kernel collapses to a delta function, i.e. K(x_i, x_j)=1 when i=j and 0 otherwise. The kernel matrix approaches the identity. The optimal coefficients solving the quadratic program approach zero. The SVM predicts zero almost everywhere except in a smaller and smaller surrounding of the training points, where the prediction equals the label of that point.

nathell 6y ago

I wish people stopped using disparaging terms, especially in titles. I skimmed through the presentation and initially felt overwhelmed by the amount of heavy linear algebra going on in there. Now, that's not a criticism of the document itself – there's probably no way around that – but if I were to give up because of failing to understand the content, the corollary would be "I'm not even an idiot", and that really doesn't help anyone. If the title were "A guide to SVMs", it would be just as descriptive, while avoiding calling people names.

mayankkaizen 6y ago
OTOH, these kind of titles actually attract me to the articles in the areas I have very little clue about. They give me the impression that authors have introduced the subject matter in the most accessible ELI5 style.
therealcamino 6y ago
I had the same reaction, and then I remembered that series of books "The Complete Idiot's Guide To..." that was popular at the time. It's probably a reference to that, and intended as a joke given the background needed to understand the presentation. https://apnews.com/dd0d4d10c6ce8f698cb325a72ee82b97 https://apnews.com/dd0d4d10c6ce8f698cb325a72ee82b97
mumblemumble 6y ago
I've never liked the "idiot's guide" or "for dummies" thing, either. But, FWIW, keep in mind that this is a slide deck taken out of context. In context, it was probably being presented to an audience where a certain level of background knowledge could be more safely assumed. And, in context, it was probably being presented by a real live human. That means that there was a whole lot of more detailed explanation that is not available if you're just reading the deck. And also a human face to make any tongue-in-cheek bits (I'm guessing the title was meant to be at least a little bit irreverent) more apparent.

dijksterhuis 6y ago

I've always used https://www.svm-tutorial.com/ https://www.svm-tutorial.com/ as my go-to suggestion for reading up on SVMs as it starts easy and progressively adds the complexity as needed. > This tutorial series is intended to give you all the necessary tools to really understand the math behind SVM. It starts softly and then get more complicated. But my goal here is to keep everybody on board, especially people who do not have a strong mathematical background. Emphasis mine.

rubyfan 6y ago
i appreciate the practical usage focus here with software tutorials

frumiousirc 6y ago

This gives a very helpful geometrical description which finally let SVMs make sense to me. The weights are a vector normal to a family of planes and the optimization finds the two parallel planes that most separate two categories of data. Solving the optimization is performed in terms of the inner product of data vectors. This inner product can be replaced by a function of the inner product (the kernel) in order to transform the data which may otherwise overlap into a space where a separating plane may be found.

ajflores1604 6y ago

This video on svm has helped me grok it more than any other resource to date. Actually the whole channel is full of great breakdowns https://youtu.be/efR1C6CvhmE https://youtu.be/efR1C6CvhmE