Reduction: A Practical Mechanism of Searching for Regularity in Data

Abstract

A polynomial algorithm, called Reduction, is presented to discover natural laws by analysing a set of experimental data as an attemp to improve the early discovery systems. A complex law with multiple variables involved can be discovered by reducing it to a primitive function–-a non-divisible part of the original law. Discovering a primitive function is efficiently accomplished by a generate and test serach which does not need any backtracking. A set of data are matched with a prototype in the prototype base to generate a constant function as a candidate of the primitive function. A simple calculation will verify if the the constant function generated is a primitive function. A reduction-based discovery system, called DISCOVER 2.0, was developed with a flexible prototype base and an ability of dealing with imperfect data. The system has been verified to be valid practically and theoretically by discovering a great number of complex laws, and can be also viewed as a learning engine embodied in intelligent systems to improve their performance by obtaining a general rule from the accumulated data.