scikit-learn/scikit-learn

More details about the Crammer-Singer method for LinearSVM

Open

#13556 opened on Apr 2, 2019

View on GitHub
 (4 comments) (2 reactions) (0 assignees)Python (66,084 stars) (27,020 forks)batch import
DocumentationNeeds Benchmarkshelp wantedmodule:svm

Description

Description

On the current page about the LinearSVC model, we are given the option to use either OVR or Crammer-Singer. Though the former is a well-known method, it seems that Crammer-Singer is a very specific algorithm developed for SVMs. The page talks about the nicer theoretical foundations of the method, as well as the longer training time. However, the information about the method is a bit sparse (more about it here, but it says basically the same thing). It would be nice to have:

  • A link to the original paper
  • A general overview of the differences between Crammer-Singer and OVR/OVO
  • A benchmark comparison between the methods above, in terms of computation time and accuracy, on varying dataset sizes
  • An explanation of the important formulas from the paper

Versions

scikit-learn 0.20.3

Contributor guide

Tech stack
python
Domain
documentation
Issue type
documentation
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
3
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
1-2 days
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
stale
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
clear
Prerequisites
understanding of SVMsfamiliarity with scikit learn documentation
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
60
Research direction
Start by reviewing the current documentation for LinearSVC in sklearn/svm/ classes.py and the user guide in doc/modules/svm.rst. Read the original paper by Crammer and Singer (http://jmlr.csail.mit.edu/papers/volume2/crammer01a/crammer01a.pdf). Then, write a clear overview comparing Crammer Singer to OVR/OVO, possibly including a benchmark script (e.g., using sklearn's built in datasets) to compare computation time and accuracy. Finally, explain the key formulas from the paper, referencing the relevant sections of the implementation.