{
  "id": "1810.09828",
  "version": "v1",
  "published": "2018-10-23T13:07:48.000Z",
  "updated": "2018-10-23T13:07:48.000Z",
  "title": "DCSVM: Fast Multi-class Classification using Support Vector Machines",
  "authors": [
    "Duleep Rathgamage Don",
    "Ionut E. Iacob"
  ],
  "categories": [
    "cs.LG",
    "stat.ML"
  ],
  "abstract": "We present DCSVM, an efficient algorithm for multi-class classification using Support Vector Machines. DCSVM is a divide and conquer algorithm which relies on data sparsity in high dimensional space and performs a smart partitioning of the whole training data set into disjoint subsets that are easily separable. A single prediction performed between two partitions eliminates at once one or more classes in one partition, leaving only a reduced number of candidate classes for subsequent steps. The algorithm continues recursively, reducing the number of classes at each step, until a final binary decision is made between the last two classes left in the competition. In the best case scenario, our algorithm makes a final decision between $k$ classes in $O(\\log k)$ decision steps and in the worst case scenario DCSVM makes a final decision in $k-1$ steps, which is not worse than the existent techniques.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-10-23T13:07:48.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "support vector machines",
      "fast multi-class classification",
      "worst case scenario dcsvm",
      "final decision",
      "final binary decision"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}