An efficient PAC algorithm for reconstructing a mixture of lines

Sanjoy Dasgupta; Elan Pavlov; Yoram Singer

doi:10.1007/3-540-36169-3_28

An efficient PAC algorithm for reconstructing a mixture of lines

Sanjoy Dasgupta, Elan Pavlov, Yoram Singer

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

Abstract

In this paper we study the learnability of a mixture of lines model which is of great importance in machine vision, computer graphics, and computer aided design applications. The mixture of lines is a partially-probabilistic model for an image composed of line-segments. Observations are generated by choosing one of the lines at random and picking a point at random from the chosen line. Each point is contaminated with some noise whose distribution is unknown, but which is bounded in magnitude. Our goal is to discover efficiently and rather accurately the line-segments that generated the noisy observations. We describe and analyze an efficient probably approximately correct (PAC) algorithm for solving the problem. Our algorithm combines techniques from planar geometry with simple large deviation tools and is simple to implement.

Original language	English (US)
Title of host publication	Algorithmic Learning Theory - 13th International Conference, ALT 2002, Proceedings
Editors	Nicolò Cesa-Bianchi, Masayuki Numao, Rüdiger Reischuk
Publisher	Springer Verlag
Pages	351-364
Number of pages	14
ISBN (Print)	3540001700, 9783540001706
DOIs	https://doi.org/10.1007/3-540-36169-3_28
State	Published - 2002
Event	13th International Conference on Algorithmic Learning Theory, ALT 2002 - Lübeck, Germany Duration: Nov 24 2002 → Nov 26 2002

Publication series

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

Other

Other	13th International Conference on Algorithmic Learning Theory, ALT 2002
Country/Territory	Germany
City	Lübeck
Period	11/24/02 → 11/26/02

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-36169-3_28

Cite this

Dasgupta, S., Pavlov, E., & Singer, Y. (2002). An efficient PAC algorithm for reconstructing a mixture of lines. In N. Cesa-Bianchi, M. Numao, & R. Reischuk (Eds.), Algorithmic Learning Theory - 13th International Conference, ALT 2002, Proceedings (pp. 351-364). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2533). Springer Verlag. https://doi.org/10.1007/3-540-36169-3_28

Dasgupta, Sanjoy ; Pavlov, Elan ; Singer, Yoram. / An efficient PAC algorithm for reconstructing a mixture of lines. Algorithmic Learning Theory - 13th International Conference, ALT 2002, Proceedings. editor / Nicolò Cesa-Bianchi ; Masayuki Numao ; Rüdiger Reischuk. Springer Verlag, 2002. pp. 351-364 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8afc210bedd64f62954e07ec07b4c964,

title = "An efficient PAC algorithm for reconstructing a mixture of lines",

abstract = "In this paper we study the learnability of a mixture of lines model which is of great importance in machine vision, computer graphics, and computer aided design applications. The mixture of lines is a partially-probabilistic model for an image composed of line-segments. Observations are generated by choosing one of the lines at random and picking a point at random from the chosen line. Each point is contaminated with some noise whose distribution is unknown, but which is bounded in magnitude. Our goal is to discover efficiently and rather accurately the line-segments that generated the noisy observations. We describe and analyze an efficient probably approximately correct (PAC) algorithm for solving the problem. Our algorithm combines techniques from planar geometry with simple large deviation tools and is simple to implement.",

author = "Sanjoy Dasgupta and Elan Pavlov and Yoram Singer",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2002.; 13th International Conference on Algorithmic Learning Theory, ALT 2002 ; Conference date: 24-11-2002 Through 26-11-2002",

year = "2002",

doi = "10.1007/3-540-36169-3_28",

language = "English (US)",

isbn = "3540001700",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "351--364",

editor = "Nicol{\`o} Cesa-Bianchi and Masayuki Numao and R{\"u}diger Reischuk",

booktitle = "Algorithmic Learning Theory - 13th International Conference, ALT 2002, Proceedings",

address = "Germany",

}

Dasgupta, S, Pavlov, E & Singer, Y 2002, An efficient PAC algorithm for reconstructing a mixture of lines. in N Cesa-Bianchi, M Numao & R Reischuk (eds), Algorithmic Learning Theory - 13th International Conference, ALT 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2533, Springer Verlag, pp. 351-364, 13th International Conference on Algorithmic Learning Theory, ALT 2002, Lübeck, Germany, 11/24/02. https://doi.org/10.1007/3-540-36169-3_28

An efficient PAC algorithm for reconstructing a mixture of lines. / Dasgupta, Sanjoy; Pavlov, Elan; Singer, Yoram.
Algorithmic Learning Theory - 13th International Conference, ALT 2002, Proceedings. ed. / Nicolò Cesa-Bianchi; Masayuki Numao; Rüdiger Reischuk. Springer Verlag, 2002. p. 351-364 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2533).

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

TY - GEN

T1 - An efficient PAC algorithm for reconstructing a mixture of lines

AU - Dasgupta, Sanjoy

AU - Pavlov, Elan

AU - Singer, Yoram

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2002.

PY - 2002

Y1 - 2002

N2 - In this paper we study the learnability of a mixture of lines model which is of great importance in machine vision, computer graphics, and computer aided design applications. The mixture of lines is a partially-probabilistic model for an image composed of line-segments. Observations are generated by choosing one of the lines at random and picking a point at random from the chosen line. Each point is contaminated with some noise whose distribution is unknown, but which is bounded in magnitude. Our goal is to discover efficiently and rather accurately the line-segments that generated the noisy observations. We describe and analyze an efficient probably approximately correct (PAC) algorithm for solving the problem. Our algorithm combines techniques from planar geometry with simple large deviation tools and is simple to implement.

AB - In this paper we study the learnability of a mixture of lines model which is of great importance in machine vision, computer graphics, and computer aided design applications. The mixture of lines is a partially-probabilistic model for an image composed of line-segments. Observations are generated by choosing one of the lines at random and picking a point at random from the chosen line. Each point is contaminated with some noise whose distribution is unknown, but which is bounded in magnitude. Our goal is to discover efficiently and rather accurately the line-segments that generated the noisy observations. We describe and analyze an efficient probably approximately correct (PAC) algorithm for solving the problem. Our algorithm combines techniques from planar geometry with simple large deviation tools and is simple to implement.

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

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

U2 - 10.1007/3-540-36169-3_28

DO - 10.1007/3-540-36169-3_28

M3 - Conference contribution

AN - SCOPUS:84942749108

SN - 3540001700

SN - 9783540001706

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 351

EP - 364

BT - Algorithmic Learning Theory - 13th International Conference, ALT 2002, Proceedings

A2 - Cesa-Bianchi, Nicolò

A2 - Numao, Masayuki

A2 - Reischuk, Rüdiger

PB - Springer Verlag

T2 - 13th International Conference on Algorithmic Learning Theory, ALT 2002

Y2 - 24 November 2002 through 26 November 2002

ER -

Dasgupta S, Pavlov E, Singer Y. An efficient PAC algorithm for reconstructing a mixture of lines. In Cesa-Bianchi N, Numao M, Reischuk R, editors, Algorithmic Learning Theory - 13th International Conference, ALT 2002, Proceedings. Springer Verlag. 2002. p. 351-364. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-36169-3_28

An efficient PAC algorithm for reconstructing a mixture of lines

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this