Approximation Algorithms for Decision Trees
Resumo
Decision trees are a central structure in computer science, having applications in many areas. This thesis contributes to the understanding of this important structure by proving by proving theoretical bounds on its behavior and also providing algorithms to construct decision trees with much stronger guarantee and that can cope with more general situations than the solutions available in the literature.
Referências
Adler, M. and Heeringa, B. (2008). Approximating optimal binary decision trees. APPROX ’08 / RANDOM ’08, pages 1–9.
Bellala, G., Bhavnani, S. K., and Scott, C. (2012). Group-based active query selection for rapid diagnosis in time-critical situations. IEEE Trans. Inf. Theor., 58(1):459–478.
Chakaravarthy, V. T., Pandit, V., Roy, S., and Sabharwal, Y. (2009). Approximating decision trees with multiway branches. ICALP, pages 210–221.
Golovin, D., Krause, A., and Ray, D. (2010). Near-optimal bayesian active learning with noisy observations. In NIPS 2010.
Guillory, A. and Bilmes, J. (2009). Average-case active learning with costs. In ALT’09, pages 141–155.
Guillory, A. and Bilmes, J. (2010). Interactive submodular set cover. In ICML, pages 415–422.
Gupta, A., Nagarajan, V., and Ravi, R. (2010). Approximation algorithms for optimal decision trees and adaptive tsp problems. In ICALP’10, pages 690–701.
Kohavi, R. and Li, C.-H. (1995). Oblivious decision trees, graphs, and top-down pruning. In IJCAI, pages 1071–1079.
Kosaraju, Przytycka, and Borgstrom (1999). On an optimal split tree problem. In WADS: 6th Workshop on Algorithms and Data Structures.
Laber, E. S. and Nogueira, L. T. (2004). On the hardness of the minimum height decision tree problem. Discrete Applied Mathematics, 144(1):209–212.
P. Kelle, H. Schneider, H. Y. (2014). Decision alternatives between expected cost minimization and worst case scenario in emergency supply second revision. International Journal of Production Economics, pages 250–260.
Bellala, G., Bhavnani, S. K., and Scott, C. (2012). Group-based active query selection for rapid diagnosis in time-critical situations. IEEE Trans. Inf. Theor., 58(1):459–478.
Chakaravarthy, V. T., Pandit, V., Roy, S., and Sabharwal, Y. (2009). Approximating decision trees with multiway branches. ICALP, pages 210–221.
Golovin, D., Krause, A., and Ray, D. (2010). Near-optimal bayesian active learning with noisy observations. In NIPS 2010.
Guillory, A. and Bilmes, J. (2009). Average-case active learning with costs. In ALT’09, pages 141–155.
Guillory, A. and Bilmes, J. (2010). Interactive submodular set cover. In ICML, pages 415–422.
Gupta, A., Nagarajan, V., and Ravi, R. (2010). Approximation algorithms for optimal decision trees and adaptive tsp problems. In ICALP’10, pages 690–701.
Kohavi, R. and Li, C.-H. (1995). Oblivious decision trees, graphs, and top-down pruning. In IJCAI, pages 1071–1079.
Kosaraju, Przytycka, and Borgstrom (1999). On an optimal split tree problem. In WADS: 6th Workshop on Algorithms and Data Structures.
Laber, E. S. and Nogueira, L. T. (2004). On the hardness of the minimum height decision tree problem. Discrete Applied Mathematics, 144(1):209–212.
P. Kelle, H. Schneider, H. Y. (2014). Decision alternatives between expected cost minimization and worst case scenario in emergency supply second revision. International Journal of Production Economics, pages 250–260.
Publicado
26/07/2018
Como Citar
SAETTLER, Aline; LABER, Eduardo S..
Approximation Algorithms for Decision Trees. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 31. , 2018, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 55-60.
ISSN 2763-8820.
DOI: https://doi.org/10.5753/ctd.2018.3649.
