学术文献库

The need for recognition/approximation of functions in terms of elementary functions/operations emerges in many areas of experimental mathematics, numerical analysis, computer algebra systems, model building, machine learning, approximation and data compression. One of the most underestimated methods is the symbolic regression. In the article, reductionist approach is applied, reducing full problem to constant functions, i.e, pure numbers (decimal, floating-point). However, existing solutions are plagued by lack of solid criteria distinguishing between random formula, matching approximately or literally decimal expansion and probable ''exact'' (the best) expression match in the sense of Occam's razor. In particular, convincing STOP criteria for search were never developed. In the article, such a criteria, working in statistical sense, are provided. Recognition process can be viewed as (1) enumeration of all formulas in order of increasing Kolmogorov complexity K (2) random process with appropriate statistical distribution (3) compression of a decimal string. All three approaches are remarkably consistent, and provide essentially the same limit for practical depth of search. Tested unique formulas count must not exceed 1/sigma, where sigma is relative numerical error of the target constant. Beyond that, further search is pointless, because, in the view of approach (1), number of equivalent expressions within error bounds grows exponentially; in view of (2), probability of random match approaches 1; in view of (3) compression ratio much smaller than 1.