TY - GEN

T1 - Geometric problems in machine learning

AU - Dobkin, David Paul

AU - Gunopulos, Dimitrios

PY - 1995/1/1

Y1 - 1995/1/1

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

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 -