Learning from approximate data

Abstract

We give an algorithm to PAC learn the coefficients of a multivariate polynomial from the signs of its values, over a sample of real points which are only known approximately. While there are several papers dealing with PAC learning polynomials (e.g. [3, II]), they mainly only consider variables over finite fields or real variables with no round-off error. In particular, to the best of our knowledge, the only other work considering rounded-off real data is that of Dennis Cheung [6]. There, multivariate polynomials are learned under the assumption that the coefficients are independent, eventually leading to a linear programming problem. In this thesis we consider the other extreme: namely, we consider the case where the coefficients of the polynomial are (polynomial) functions of a single parameter. As we shall see, this leads to solving a non-linear system of polynomial inequalities in one variable. Our algorithm does so in a number of operations which is polynomial in the data size and the logarithm of the condition of the sample.

Date of Award	31 Jul 2001
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Felipe CUCKER (Supervisor)