Can finite samples detect singularities of real-valued functions?

ABSTRACT

Consider the following type of problem: There is an unknown function, f : Rn → Rm, there is also a black-box that on query x (&egr; Rn) 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 examples 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 compute 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 Decidable In the Limit, (DIL). We analyze the class of 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 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<&dgr;<1, there is an algorithm using at most l(log(&dgr;)) many probes that succeeds on more than (1–&dgr;) of the f's (as measured by P). We believe that the new approach presented here will be found useful for many further applications.

REFERENCES

• AS83: Dana Angluin , Carl H. Smith, Inductive Inference: Theory and Methods, ACM Computing Surveys (CSUR), v.15 n.3, p.237-269, Sept. 1983 [doi>10.1145/356914.356918]
• Be91: Ben-David S., and Halevi S., "On the Independence of P versus NP', Technical Report #714, Technion, Haifa, Israel.
• Bl72: Blum E.K., "Numerical Analysis and Computation: Theory and Practice" Addison- Wesley, 1972.
• CY87: Richard Cole , Chee K. Yap, Shape from probing, Journal of Algorithms, v.8 n.1, p.19-38, March 1987 [doi>10.1016/0196-6774(87)90025-3]
• Co73: Cover M. T.," On Determining the Rationality of the Mean of a Random Variable", The Annals of Statistics, Vol. 1, No. 5, 862-871 (1973).
• DP91: Dembo A,. and Peres Y., "A Topological Criteria for Hypothesis Testing" Unpublished manuscript, (1991).
• Ga: Ga# S.A., "Point - Set Topology", Academic Press, 1964.
• Go67: Gold E.M., "Language Identification in the Limit", Information and Control I0, 447-474 (1967).
• HW58: Hoeffding W., and Wolfowitz J., "Distingulshability of Sets of Distributions", Annals of Mathematical Statistic8 29, 700-718, (1958).
• KZ91: Kulkarni R.S., and Zeitouni O., "Can One Decide the Type of the Mean from the Empirical Measure?", Statistics and Probability Letters, ?? (1991).
• Ro70: Rogers C. A., "Hausdorff Measures" Cambridge University Press, 1970.
• ZK91: Zeitouni O., and Kulkarni R.S., "A General Classification Rule for ProbabiUty Measures", Submitted to Annals of Statistics.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields

Additional Classification:
  G. Mathematics of Computing

General Terms:
Algorithms, Theory