Technical Report CS0700

Authors: S. Ben-David
PDF - RevisedCS0700.revised.pdf
Abstract: Consider the following type of problem: There is an unknown function, $f:R^n \rightarrow R^m$, there is also a black-box that on query $x\ (\in R^n)$ returns $f(x)$. Is there an algorithm that, using probes to the black-box, can figure out analytic information about $f$? (For an example: ``Is $f$ a polynomial?'', ``Is $f$ a second order differentiable at $x = (0,0,...,0)$?'' etc.). Clearly, for example as these, if we bound the number of probes an algorithm has to settle for, no algorithm can carry the task. On the other hand, if one allows an infinite iteration of a `probe computer and guess' process, then, (quite surprisingly) for many such questions, there are algorithms that are guaranteed to be correct in all but finitely many of their guesses. We call such questions {\em Decidable In the Limit, (DIL)}. We analyze the class of {\em DIL} problems and provide a necessary and sufficient condition for the membership of a decision problem in this class. We offer an algorithm for any {\em DIL} problem, and apply it to several types of learning tasks. Furthermore, if an a-priori probability distribution $P$, according to which $f$ is being chosen, is available to the algorithm, then it can be strengthened into a finite algorithm. More precisely, for many distributions $P$, there exists a polynomial function, $l$, such that for every $0 < \delta < 1$, there is an algorithm using at most $l(\log(\delta))$ many probes that succeed on more than $(1-\delta)$ of the $f$'s (as measured by $P$). We believe that the new approach presented here will be found useful for many further applications.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1991
To the main CS technical reports page

Computer science department, Technion