Learning optimal classification trees using a binary linear program formulation

Sicco Verwer, Y. Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

13 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationProceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19)
Place of PublicationPalo Alto, California USA
PublisherAAAI Press
Pages1625-1632
ISBN (Print)978-1-57735-809-1
DOIs
Publication statusPublished - 2019
Event33rd AAAI Conference on Artificial Intelligence - Hawaii, Honolulu, United States
Duration: 27 Jan 20191 Feb 2019
Conference number: 33
https://aaai.org/Conferences/AAAI-19/

Conference

Conference33rd AAAI Conference on Artificial Intelligence
Abbreviated titleAAAI-19
CountryUnited States
CityHonolulu
Period27/01/191/02/19
Internet address

Fingerprint

Linear programming

Keywords

  • Machine learning
  • decision tree
  • mathematical optimization

Cite this

Verwer, S., & Zhang, Y. (2019). Learning optimal classification trees using a binary linear program formulation. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19) (pp. 1625-1632). Palo Alto, California USA: AAAI Press. https://doi.org/10.1609/aaai.v33i01.33011624
Verwer, Sicco ; Zhang, Y. / Learning optimal classification trees using a binary linear program formulation. Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19). Palo Alto, California USA : AAAI Press, 2019. pp. 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",
isbn = "978-1-57735-809-1",
pages = "1625--1632",
booktitle = "Proceedings of 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 Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19). AAAI Press, Palo Alto, California USA, pp. 1625-1632, 33rd AAAI Conference on Artificial Intelligence, Honolulu, United States, 27/01/19. https://doi.org/10.1609/aaai.v33i01.33011624

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

Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19). Palo Alto, California USA : AAAI Press, 2019. p. 1625-1632.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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

SN - 978-1-57735-809-1

SP - 1625

EP - 1632

BT - Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19)

PB - AAAI Press

CY - Palo Alto, California USA

ER -

Verwer S, Zhang Y. Learning optimal classification trees using a binary linear program formulation. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19). Palo Alto, California USA: AAAI Press. 2019. p. 1625-1632 https://doi.org/10.1609/aaai.v33i01.33011624