Technical Papers

A new algorithm, called Hamming clustering (HC), for the solution of classification problems with binary inputs is proposed. It builds a logical network containing only AND, OR, and NOT ports which, in addition to satisfying all the input–output pairs included in a given finite consistent training set, is able to reconstruct the underlying Boolean function.

In this paper a general constructive approach for training neural networks in classification problems is presented. This approach is used to construct a particular connectionist model, named Switching Neural Network (SNN), based on the conversion of the original problem in a Boolean lattice domain.

The universal approximation property is an important characteristic of models employed in the solution of machine learning problems. The possibility of approximating within a desired precision any Borel measurable function guarantees the generality of the considered approach.

A new connectionist model, called Switching Neural Network (SNN), for the solution of classification problems is presented. SNN includes a first layer containing a particular kind of A/D converters, called latticizers, that suitably transform input vectors into binary strings. Then, the subsequent two layers of an SNN realize a positive Boolean function that solve in a lattice domain the original classification problem.

The problem of reconstructing the AND-OR expression of a partially defined positive Boolean function (pdpBf) is solved by adopting a novel algorithm, denoted by LSC, which combines the advantages of two efficient techniques, Logical Analysis of Data (LAD) and Shadow Clustering (SC). The kernel of the approach followed by LAD consists in a breadth-first enumeration of all the prime implicants whose degree is not greater than a fixed maximum d. In contrast, SC adopts an effective heuristic procedure for retrieving the most promising logical products to be included in the resulting AND-OR expression. Since the computational cost required by LAD prevents its application even for relatively small dimensions of the input domain, LSC employs a depth-first approach, with asymptotically linear memory occupation, to analyze the prime implicants having degree not greater than d. In addition, the theoretical analysis proves that LSC presents almost the same asymptotic time complexity as LAD. Extensive simulations on artificial benchmarks validate the good behavior of the computational cost exhibited by LSC, in agreement with the theoretical analysis. Furthermore, the pdpBf retrieved by LSC always shows a better performance, in terms of complexity and accuracy, with respect to those obtained by LAD.