Concept learning with geometric hypotheses

David P. Dobkin; Dimitrios Gunopulos

doi:10.1145/225298.225338

Concept learning with geometric hypotheses

David P. Dobkin, Dimitrios Gunopulos

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 Scopus citations

Abstract

We present a general approach to solving the minimizing disagreement problem for geometric hypotheses with finite VC-dimension. These results also imply efficient agnostic-PAC learning of these hypotheses classes. In particular we give an O(n^{min(α-1,2κ-1)}log n) algorithm that solves the m.d.p. for two-dimensional convex κ-gon hypotheses (α is the VC dimension of the implied set system, κ is constant), and an O(n^3κ-1 log n) algorithm for convex κ-hedra hypotheses in three dimensions. We also give an O(κ²n² logn) algorithm that solves the m.d. p. for planar κ-stripes, and give an approach to approximation algorithms.

Original language	English (US)
Title of host publication	Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995
Publisher	Association for Computing Machinery, Inc
Pages	329-336
Number of pages	8
ISBN (Electronic)	0897917235, 9780897917230
DOIs	https://doi.org/10.1145/225298.225338
State	Published - Jul 5 1995
Event	8th Annual Conference on Computational Learning Theory, COLT 1995 - Santa Cruz, United States Duration: Jul 5 1995 → Jul 8 1995

Publication series

Name	Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995
Volume	1995-January

Other

Other	8th Annual Conference on Computational Learning Theory, COLT 1995
Country/Territory	United States
City	Santa Cruz
Period	7/5/95 → 7/8/95

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Artificial Intelligence
Software

Access to Document

10.1145/225298.225338

Cite this

Dobkin, D. P., & Gunopulos, D. (1995). Concept learning with geometric hypotheses. In Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995 (pp. 329-336). (Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995; Vol. 1995-January). Association for Computing Machinery, Inc. https://doi.org/10.1145/225298.225338

@inproceedings{a5aff3b0b7894c8c8eba5b06acf04b2f,

title = "Concept learning with geometric hypotheses",

abstract = "We present a general approach to solving the minimizing disagreement problem for geometric hypotheses with finite VC-dimension. These results also imply efficient agnostic-PAC learning of these hypotheses classes. In particular we give an O(nmin(α-1,2κ-1)log n) algorithm that solves the m.d.p. for two-dimensional convex κ-gon hypotheses (α is the VC dimension of the implied set system, κ is constant), and an O(n3κ-1 log n) algorithm for convex κ-hedra hypotheses in three dimensions. We also give an O(κ2n2 logn) algorithm that solves the m.d. p. for planar κ-stripes, and give an approach to approximation algorithms.",

author = "Dobkin, {David P.} and Dimitrios Gunopulos",

note = "Funding Information: sity, 35 Olden St., Princeton, NJ 08.540, USA, e-mail: dg@cs.princeton. edu. The research work of this author was supported by NSF Grant CCR93-01254 and by DIMACS, an NSF Science and Technology Center. Publisher Copyright: {\textcopyright} 1995 ACM.; 8th Annual Conference on Computational Learning Theory, COLT 1995 ; Conference date: 05-07-1995 Through 08-07-1995",

year = "1995",

month = jul,

day = "5",

doi = "10.1145/225298.225338",

language = "English (US)",

series = "Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995",

publisher = "Association for Computing Machinery, Inc",

pages = "329--336",

booktitle = "Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995",

}

Dobkin, DP & Gunopulos, D 1995, Concept learning with geometric hypotheses. in Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995. Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995, vol. 1995-January, Association for Computing Machinery, Inc, pp. 329-336, 8th Annual Conference on Computational Learning Theory, COLT 1995, Santa Cruz, United States, 7/5/95. https://doi.org/10.1145/225298.225338

Concept learning with geometric hypotheses. / Dobkin, David P.; Gunopulos, Dimitrios.
Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995. Association for Computing Machinery, Inc, 1995. p. 329-336 (Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995; Vol. 1995-January).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Concept learning with geometric hypotheses

AU - Dobkin, David P.

AU - Gunopulos, Dimitrios

N1 - Funding Information: sity, 35 Olden St., Princeton, NJ 08.540, USA, e-mail: dg@cs.princeton. edu. The research work of this author was supported by NSF Grant CCR93-01254 and by DIMACS, an NSF Science and Technology Center. Publisher Copyright: © 1995 ACM.

PY - 1995/7/5

Y1 - 1995/7/5

N2 - We present a general approach to solving the minimizing disagreement problem for geometric hypotheses with finite VC-dimension. These results also imply efficient agnostic-PAC learning of these hypotheses classes. In particular we give an O(nmin(α-1,2κ-1)log n) algorithm that solves the m.d.p. for two-dimensional convex κ-gon hypotheses (α is the VC dimension of the implied set system, κ is constant), and an O(n3κ-1 log n) algorithm for convex κ-hedra hypotheses in three dimensions. We also give an O(κ2n2 logn) algorithm that solves the m.d. p. for planar κ-stripes, and give an approach to approximation algorithms.

AB - We present a general approach to solving the minimizing disagreement problem for geometric hypotheses with finite VC-dimension. These results also imply efficient agnostic-PAC learning of these hypotheses classes. In particular we give an O(nmin(α-1,2κ-1)log n) algorithm that solves the m.d.p. for two-dimensional convex κ-gon hypotheses (α is the VC dimension of the implied set system, κ is constant), and an O(n3κ-1 log n) algorithm for convex κ-hedra hypotheses in three dimensions. We also give an O(κ2n2 logn) algorithm that solves the m.d. p. for planar κ-stripes, and give an approach to approximation algorithms.

UR - http://www.scopus.com/inward/record.url?scp=84961365937&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84961365937&partnerID=8YFLogxK

U2 - 10.1145/225298.225338

DO - 10.1145/225298.225338

M3 - Conference contribution

AN - SCOPUS:84961365937

T3 - Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995

SP - 329

EP - 336

BT - Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995

PB - Association for Computing Machinery, Inc

T2 - 8th Annual Conference on Computational Learning Theory, COLT 1995

Y2 - 5 July 1995 through 8 July 1995

ER -

Concept learning with geometric hypotheses

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this