Learning real polynomials with a turing machine

Dennis Cheung

doi:10.1007/3-540-46769-6_19

Learning real polynomials with a turing machine

Dennis Cheung

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

1 Citation (Scopus)

Abstract

We provide an algorithm to PAC learn multivariate polynomials with real coefficients. The instance space from which labeled samples are drawn is IRN but the coordinates of such samples are known only approximately. The algorithm is iterative and the main ingredient of its complexity, the number of iterations it performs, is estimated using the condition number of a linear programming problem associated to the sample. To the best of our knowledge, this is the first study of PAC learning concepts parameterized by real numbers from approximate data. © Springer-Verlag Berlin Heidelberg 1999.

Original language	English
Title of host publication	Algorithmic Learning Theory - 10th International Conference, ALT 1999, Proceedings
Publisher	Springer Verlag
Pages	231-240
Volume	1720
ISBN (Print)	3540667482, 9783540667483
DOIs	https://doi.org/10.1007/3-540-46769-6_19
Publication status	Published - 1999
Externally published	Yes
Event	10th International Conference on Algorithmic Learning Theory, ALT 1999 - Tokyo, Japan Duration: 6 Dec 1999 → 8 Dec 1999

Publication series

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

Conference

Conference	10th International Conference on Algorithmic Learning Theory, ALT 1999
Place	Japan
City	Tokyo
Period	6/12/99 → 8/12/99

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Access Output

10.1007/3-540-46769-6_19

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Cheung, D. (1999). Learning real polynomials with a turing machine. In Algorithmic Learning Theory - 10th International Conference, ALT 1999, Proceedings (Vol. 1720, pp. 231-240). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1720). Springer Verlag. https://doi.org/10.1007/3-540-46769-6_19

@inproceedings{c46f82cc6101411fa8e1670a284e35ad,

title = "Learning real polynomials with a turing machine",

abstract = "We provide an algorithm to PAC learn multivariate polynomials with real coefficients. The instance space from which labeled samples are drawn is IRN but the coordinates of such samples are known only approximately. The algorithm is iterative and the main ingredient of its complexity, the number of iterations it performs, is estimated using the condition number of a linear programming problem associated to the sample. To the best of our knowledge, this is the first study of PAC learning concepts parameterized by real numbers from approximate data. {\textcopyright} Springer-Verlag Berlin Heidelberg 1999.",

author = "Dennis Cheung",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].; 10th International Conference on Algorithmic Learning Theory, ALT 1999 ; Conference date: 06-12-1999 Through 08-12-1999",

year = "1999",

doi = "10.1007/3-540-46769-6\_19",

language = "English",

isbn = "3540667482",

volume = "1720",

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

publisher = "Springer Verlag",

pages = "231--240",

booktitle = "Algorithmic Learning Theory - 10th International Conference, ALT 1999, Proceedings",

address = "Germany",

}

Cheung, D 1999, Learning real polynomials with a turing machine. in Algorithmic Learning Theory - 10th International Conference, ALT 1999, Proceedings. vol. 1720, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1720, Springer Verlag, pp. 231-240, 10th International Conference on Algorithmic Learning Theory, ALT 1999, Tokyo, Japan, 6/12/99. https://doi.org/10.1007/3-540-46769-6_19

Learning real polynomials with a turing machine. / Cheung, Dennis.
Algorithmic Learning Theory - 10th International Conference, ALT 1999, Proceedings. Vol. 1720 Springer Verlag, 1999. p. 231-240 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1720).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Learning real polynomials with a turing machine

AU - Cheung, Dennis

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 1999

Y1 - 1999

N2 - We provide an algorithm to PAC learn multivariate polynomials with real coefficients. The instance space from which labeled samples are drawn is IRN but the coordinates of such samples are known only approximately. The algorithm is iterative and the main ingredient of its complexity, the number of iterations it performs, is estimated using the condition number of a linear programming problem associated to the sample. To the best of our knowledge, this is the first study of PAC learning concepts parameterized by real numbers from approximate data. © Springer-Verlag Berlin Heidelberg 1999.

AB - We provide an algorithm to PAC learn multivariate polynomials with real coefficients. The instance space from which labeled samples are drawn is IRN but the coordinates of such samples are known only approximately. The algorithm is iterative and the main ingredient of its complexity, the number of iterations it performs, is estimated using the condition number of a linear programming problem associated to the sample. To the best of our knowledge, this is the first study of PAC learning concepts parameterized by real numbers from approximate data. © Springer-Verlag Berlin Heidelberg 1999.

UR - https://www.scopus.com/pages/publications/84957060172

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84957060172&origin=recordpage

U2 - 10.1007/3-540-46769-6_19

DO - 10.1007/3-540-46769-6_19

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 3540667482

SN - 9783540667483

VL - 1720

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

SP - 231

EP - 240

BT - Algorithmic Learning Theory - 10th International Conference, ALT 1999, Proceedings

PB - Springer Verlag

T2 - 10th International Conference on Algorithmic Learning Theory, ALT 1999

Y2 - 6 December 1999 through 8 December 1999

ER -

Learning real polynomials with a turing machine

Abstract

Publication series

Conference

Bibliographical note

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this