From binary features to Non-Reducible Descriptors in supervised pattern recognition problems

•Supervised pattern recognition problem in case of binary features is solved.•The approach is based on machine learning of Non-Reducible Descriptors.•Combinatorial and decision-tree computational procedures are presented.•Binary feature selection and combining classifiers problems are discussed and solved.•Applications for recognition of Arabic numerals and recognition of ECG are given.

The present paper explores the supervised pattern recognition problem when binary features are used in pattern descriptions. The concept of Non-Reducible Descriptors (NRDs) for binary features is introduced. NRDs are descriptors of patterns that do not contain any redundant information. They correspond to syndromes in medical diagnosis and are represented as conjunctions. The proposed approach is based on learning Boolean formulas. Combinatorial and decision-tree computational procedures for construction of all NRDs for a pattern are presented. The computational complexity of the proposed approach is discussed. The process of construction of all NRDs and the obtained NRDs are used for solving the binary feature selection problem. A procedure for combining classifiers is presented. The proposed approach is illustrated with applications for recognition of Arabic numerals in different graphical representations and recognition of QRS complexes in electrocardiograms. The obtained results are discussed.