Rectifying Mono-Label Boolean Classifiers

We elaborate on the notion of rectification of a Boolean classifier Sigma. Given Sigma and some background knowledge T, postulates characterizing the way Sigma must be changed into a new classifier Sigma star T that complies with T have already been presented. We focus here on the specific case of mono-label Boolean classifiers, i.e., there is a single target concept and any instance is classified either as positive (an element of the concept), or as negative (an element of the complementary concept). In this specific case, our main contribution is twofold: (1) we show that there is a unique rectification operator star satisfying the postulates, and (2) when Sigma and T are Boolean circuits, we show how a classification circuit equivalent to Sigma star T can be computed in time linear in the size of Sigma and T; when Sigma and T are decision trees, a decision tree equivalent to Sigma star T can be computed in time polynomial in the size of Sigma and T.