Learning optimal classification trees using a binary linear program formulation

Sicco Verwer, Y. Zhang

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

Uittreksel

We provide a new formulation for the problem of learning the optimal classification tree of a given depth as a binary linear program. A limitation of previously proposed mathematical Optimization formulations is that they create constraints and variables for every row in the training data. As a result, the running time of the existing Integer Linear programming (ILP) formulations increases dramatically with the size of data. In our new binary formulation, we aim to circumvent this problem by making the formulation size largely independent from the training data size. We show experimentally that our formulation achieves better performance than existing formulations on both small and large problem instances within shorter running time.
TaalEngels
TitelThe Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19)
UitgeverijAAAI Press
Pagina's1625-1632
Volume33
DOI's
StatusGepubliceerd - 2019
Evenement33rd AAAI Conference on Artificial Intelligence - Hawaii, Honolulu, Verenigde Staten van Amerika
Duur: 27 jan 20191 feb 2019
Congresnummer: 33
https://aaai.org/Conferences/AAAI-19/

Congres

Congres33rd AAAI Conference on Artificial Intelligence
Verkorte titelAAAI-19
LandVerenigde Staten van Amerika
StadHonolulu
Periode27/01/191/02/19
Internet adres

Vingerafdruk

Linear programming

Trefwoorden

    Citeer dit

    Verwer, S., & Zhang, Y. (2019). Learning optimal classification trees using a binary linear program formulation. In The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19) (Vol. 33, blz. 1625-1632). AAAI Press. DOI: 10.1609/aaai.v33i01.33011624
    Verwer, Sicco ; Zhang, Y./ Learning optimal classification trees using a binary linear program formulation. The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19). Vol. 33 AAAI Press, 2019. blz. 1625-1632
    @inproceedings{366ce919deb0461bb7ab1393e06d731d,
    title = "Learning optimal classification trees using a binary linear program formulation",
    abstract = "We provide a new formulation for the problem of learning the optimal classification tree of a given depth as a binary linear program. A limitation of previously proposed mathematical Optimization formulations is that they create constraints and variables for every row in the training data. As a result, the running time of the existing Integer Linear programming (ILP) formulations increases dramatically with the size of data. In our new binary formulation, we aim to circumvent this problem by making the formulation size largely independent from the training data size. We show experimentally that our formulation achieves better performance than existing formulations on both small and large problem instances within shorter running time.",
    keywords = "Machine learning, decision tree, mathematical optimization",
    author = "Sicco Verwer and Y. Zhang",
    year = "2019",
    doi = "10.1609/aaai.v33i01.33011624",
    language = "English",
    volume = "33",
    pages = "1625--1632",
    booktitle = "The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19)",
    publisher = "AAAI Press",

    }

    Verwer, S & Zhang, Y 2019, Learning optimal classification trees using a binary linear program formulation. in The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19). vol. 33, AAAI Press, blz. 1625-1632, Honolulu, Verenigde Staten van Amerika, 27/01/19. DOI: 10.1609/aaai.v33i01.33011624

    Learning optimal classification trees using a binary linear program formulation. / Verwer, Sicco; Zhang, Y.

    The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19). Vol. 33 AAAI Press, 2019. blz. 1625-1632.

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    TY - GEN

    T1 - Learning optimal classification trees using a binary linear program formulation

    AU - Verwer,Sicco

    AU - Zhang,Y.

    PY - 2019

    Y1 - 2019

    N2 - We provide a new formulation for the problem of learning the optimal classification tree of a given depth as a binary linear program. A limitation of previously proposed mathematical Optimization formulations is that they create constraints and variables for every row in the training data. As a result, the running time of the existing Integer Linear programming (ILP) formulations increases dramatically with the size of data. In our new binary formulation, we aim to circumvent this problem by making the formulation size largely independent from the training data size. We show experimentally that our formulation achieves better performance than existing formulations on both small and large problem instances within shorter running time.

    AB - We provide a new formulation for the problem of learning the optimal classification tree of a given depth as a binary linear program. A limitation of previously proposed mathematical Optimization formulations is that they create constraints and variables for every row in the training data. As a result, the running time of the existing Integer Linear programming (ILP) formulations increases dramatically with the size of data. In our new binary formulation, we aim to circumvent this problem by making the formulation size largely independent from the training data size. We show experimentally that our formulation achieves better performance than existing formulations on both small and large problem instances within shorter running time.

    KW - Machine learning

    KW - decision tree

    KW - mathematical optimization

    UR - https://aaai.org/ojs/index.php/AAAI/article/view/3978

    U2 - 10.1609/aaai.v33i01.33011624

    DO - 10.1609/aaai.v33i01.33011624

    M3 - Conference contribution

    VL - 33

    SP - 1625

    EP - 1632

    BT - The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19)

    PB - AAAI Press

    ER -

    Verwer S, Zhang Y. Learning optimal classification trees using a binary linear program formulation. In The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19). Vol. 33. AAAI Press. 2019. blz. 1625-1632. Beschikbaar vanaf, DOI: 10.1609/aaai.v33i01.33011624