TY - GEN
T1 - Geometric problems in machine learning
AU - Dobkin, David
AU - Gunopulos, Dimitrios
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1996.
PY - 1995
Y1 - 1995
N2 - We present some problems with geometric characterizations that arise naturally in practical applications of machine learning. Our motivation comes from a well known machine learning problem, the problem of computing decision trees. Typically one is given a dataset of positive and negative points, and has to compute a decision tree that fits it. The points are in a low dimensional space, and the data are collected experimentally. Most practical solutions use heuristic algorithms. To compute decision trees quickly, one has to solve optimization problems in one or more dimensions efficiently. In this paper we give geometric characterizations for these problems. We present a selection of algorithms for some of them. These algorithms are motivated from practice, and have been in many cases implemented and used as well. In addition, they are theoretically interesting, and typically employ sophisticated geometric techniques. Finally we present future research directions.
AB - We present some problems with geometric characterizations that arise naturally in practical applications of machine learning. Our motivation comes from a well known machine learning problem, the problem of computing decision trees. Typically one is given a dataset of positive and negative points, and has to compute a decision tree that fits it. The points are in a low dimensional space, and the data are collected experimentally. Most practical solutions use heuristic algorithms. To compute decision trees quickly, one has to solve optimization problems in one or more dimensions efficiently. In this paper we give geometric characterizations for these problems. We present a selection of algorithms for some of them. These algorithms are motivated from practice, and have been in many cases implemented and used as well. In addition, they are theoretically interesting, and typically employ sophisticated geometric techniques. Finally we present future research directions.
UR - http://www.scopus.com/inward/record.url?scp=84947925111&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84947925111&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84947925111
SN - 354061785X
SN - 9783540617853
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 121
EP - 132
BT - Applied Computational Geometry
A2 - Manocha, Dinesh
A2 - Lin, Ming C.
A2 - Lin, Ming C.
PB - Springer Verlag
T2 - 1st ACM Workshop on Applied Computational Geometry, WACG 1996 held as part of 2nd Federated Computing Research Conference, FCRC 1996
Y2 - 27 May 1996 through 28 May 1996
ER -