Function Decomposition

Function decomposition was originally developed in 50's and 60's - thanks to RL Ashenhurst and HA Curtis - to be used in the design of switching circuits, but it failed to raise much interest in mid decades of the last century.

Recently, the interest for the method reappeared, not only in the switching circuits design (due to FPGA devices) but also in the area of artificial intelligence. Why? The basic idea of function decomposition proved to be useful in solving some hard problems of Artificial Intelligence, and providing grounds for new machine learning, constructive induction and data mining algorithms.

As first, function decomposition can be seen as a new machine learning paradigm. The distinguishing capabilities of function decomposition are to discover new concepts from training data, organize them into a concept hierarchy, and induce concept descriptions by decomposing the original training set into smaller and less complex example sets.

Our experimental work shows that this approach may not only generalize well, but perhaps more importantly, may discover useful and interpretable concepts. We strongly believe, however, that decomposition should not be used alone and in the completely automatic fashion, but should rather be incorporated within interactive data mining systems to propose new concepts that are then reviewed and interpreted by experts.

In the past years we have been developing a particular implementation of function decomposition called HINT (Hierarchy Induction Tool). In addition to basic decomposition techniques as proposed in 1950's by Ashenhurst and Curtis HINT includes:

Handling of multi-valued attributes, discovery of multi-valued concepts;
Noise handling;
A technique to directly handle continuous attributes (without pre-discretization);
Mechanisms to use devised concepts in constructive-induction scheme.

HINT has been recently included and integrated within Orange, a data mining and machine learning framework. This is particularly important from the point of view of experimentation and interface, since Orange allows scripting and can use subcomponents of HINT, thus permitting a co-reuse and construction and testing of methods that include a combination of methods (like HINT for constructive induction and Naive Bayes for classifier construction).