Geometric problems in machine learning

David Paul Dobkin, Dimitrios Gunopulos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationApplied Computational Geometry
Subtitle of host publicationTowards Geometric Engineering - FCRC 1996 Workshop, WACG 1996, Selected Papers
PublisherSpringer Verlag
Pages121-132
Number of pages12
ISBN (Print)354061785X, 9783540617853
StatePublished - Jan 1 1995
Event1st ACM Workshop on Applied Computational Geometry, WACG 1996 held as part of 2nd Federated Computing Research Conference, FCRC 1996 - Philadelphia, United States
Duration: May 27 1996May 28 1996

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1148
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other1st ACM Workshop on Applied Computational Geometry, WACG 1996 held as part of 2nd Federated Computing Research Conference, FCRC 1996
CountryUnited States
CityPhiladelphia
Period5/27/965/28/96

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Geometric problems in machine learning'. Together they form a unique fingerprint.

  • Cite this

    Dobkin, D. P., & Gunopulos, D. (1995). Geometric problems in machine learning. In Applied Computational Geometry: Towards Geometric Engineering - FCRC 1996 Workshop, WACG 1996, Selected Papers (pp. 121-132). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1148). Springer Verlag.