Binary separation and training support vector machines

Roger Fletcher, Gaetano Zanghirati

    Research output: Contribution to journalArticle

    1 Citation (Scopus)

    Abstract

    We introduce basic ideas of binary separation by a linear hyperplane, which is a technique exploited in the support vector machine (SVM) concept. This is a decision-making tool for pattern recognition and related problems. We describe a fundamental standard problem (SP) and show how this is used in most existing research to develop a dual-based algorithm for its solution. This algorithm is shown to be deficient in certain aspects, and we develop a new primal-based SQP-like algorithm, which has some interesting features. Most practical SVM problems are not adequately handled by a linear hyperplane. We describe the nonlinear SVM technique, which enables a nonlinear separating surface to be computed, and we propose a new primal algorithm based on the use of low-rank Cholesky factors. It may be, however, that exact separation is not desirable due to the presence of uncertain or mislabelled data. Dealing with this situation is the main challenge in developing suitable algorithms. Existing dual-based algorithms use the idea of L1 penalties, which has merit. We suggest how penalties can be incorporated into a primal-based algorithm. Another aspect of practical SVM problems is often the huge size of the data set, which poses severe challenges both for software package development and for control of ill-conditioning. We illustrate some of these issues with numerical experiments on a range of problems.
    Original languageEnglish
    Pages (from-to)121-158
    Number of pages38
    JournalActa Numerica
    Volume19
    DOIs
    Publication statusPublished - May 2010

    Fingerprint

    Support vector machines
    Support Vector Machine
    Binary
    Hyperplane
    Penalty
    Cholesky
    Ill-conditioning
    Training
    Software Package
    Software packages
    Pattern Recognition
    Pattern recognition
    Decision making
    Decision Making
    Numerical Experiment
    Range of data
    Experiments

    Cite this

    Fletcher, Roger ; Zanghirati, Gaetano. / Binary separation and training support vector machines. In: Acta Numerica. 2010 ; Vol. 19. pp. 121-158.
    @article{36aebae101ac4f30b93585267405c36a,
    title = "Binary separation and training support vector machines",
    abstract = "We introduce basic ideas of binary separation by a linear hyperplane, which is a technique exploited in the support vector machine (SVM) concept. This is a decision-making tool for pattern recognition and related problems. We describe a fundamental standard problem (SP) and show how this is used in most existing research to develop a dual-based algorithm for its solution. This algorithm is shown to be deficient in certain aspects, and we develop a new primal-based SQP-like algorithm, which has some interesting features. Most practical SVM problems are not adequately handled by a linear hyperplane. We describe the nonlinear SVM technique, which enables a nonlinear separating surface to be computed, and we propose a new primal algorithm based on the use of low-rank Cholesky factors. It may be, however, that exact separation is not desirable due to the presence of uncertain or mislabelled data. Dealing with this situation is the main challenge in developing suitable algorithms. Existing dual-based algorithms use the idea of L1 penalties, which has merit. We suggest how penalties can be incorporated into a primal-based algorithm. Another aspect of practical SVM problems is often the huge size of the data set, which poses severe challenges both for software package development and for control of ill-conditioning. We illustrate some of these issues with numerical experiments on a range of problems.",
    author = "Roger Fletcher and Gaetano Zanghirati",
    note = "Copyright 2011 Elsevier B.V., All rights reserved.",
    year = "2010",
    month = "5",
    doi = "10.1017/S0962492910000024",
    language = "English",
    volume = "19",
    pages = "121--158",
    journal = "Acta Numerica",
    issn = "0962-4929",
    publisher = "Cambridge University Press",

    }

    Binary separation and training support vector machines. / Fletcher, Roger; Zanghirati, Gaetano.

    In: Acta Numerica, Vol. 19, 05.2010, p. 121-158.

    Research output: Contribution to journalArticle

    TY - JOUR

    T1 - Binary separation and training support vector machines

    AU - Fletcher, Roger

    AU - Zanghirati, Gaetano

    N1 - Copyright 2011 Elsevier B.V., All rights reserved.

    PY - 2010/5

    Y1 - 2010/5

    N2 - We introduce basic ideas of binary separation by a linear hyperplane, which is a technique exploited in the support vector machine (SVM) concept. This is a decision-making tool for pattern recognition and related problems. We describe a fundamental standard problem (SP) and show how this is used in most existing research to develop a dual-based algorithm for its solution. This algorithm is shown to be deficient in certain aspects, and we develop a new primal-based SQP-like algorithm, which has some interesting features. Most practical SVM problems are not adequately handled by a linear hyperplane. We describe the nonlinear SVM technique, which enables a nonlinear separating surface to be computed, and we propose a new primal algorithm based on the use of low-rank Cholesky factors. It may be, however, that exact separation is not desirable due to the presence of uncertain or mislabelled data. Dealing with this situation is the main challenge in developing suitable algorithms. Existing dual-based algorithms use the idea of L1 penalties, which has merit. We suggest how penalties can be incorporated into a primal-based algorithm. Another aspect of practical SVM problems is often the huge size of the data set, which poses severe challenges both for software package development and for control of ill-conditioning. We illustrate some of these issues with numerical experiments on a range of problems.

    AB - We introduce basic ideas of binary separation by a linear hyperplane, which is a technique exploited in the support vector machine (SVM) concept. This is a decision-making tool for pattern recognition and related problems. We describe a fundamental standard problem (SP) and show how this is used in most existing research to develop a dual-based algorithm for its solution. This algorithm is shown to be deficient in certain aspects, and we develop a new primal-based SQP-like algorithm, which has some interesting features. Most practical SVM problems are not adequately handled by a linear hyperplane. We describe the nonlinear SVM technique, which enables a nonlinear separating surface to be computed, and we propose a new primal algorithm based on the use of low-rank Cholesky factors. It may be, however, that exact separation is not desirable due to the presence of uncertain or mislabelled data. Dealing with this situation is the main challenge in developing suitable algorithms. Existing dual-based algorithms use the idea of L1 penalties, which has merit. We suggest how penalties can be incorporated into a primal-based algorithm. Another aspect of practical SVM problems is often the huge size of the data set, which poses severe challenges both for software package development and for control of ill-conditioning. We illustrate some of these issues with numerical experiments on a range of problems.

    UR - http://www.scopus.com/inward/record.url?scp=79957448484&partnerID=8YFLogxK

    U2 - 10.1017/S0962492910000024

    DO - 10.1017/S0962492910000024

    M3 - Article

    VL - 19

    SP - 121

    EP - 158

    JO - Acta Numerica

    JF - Acta Numerica

    SN - 0962-4929

    ER -