Rectifying Binary Classifiers
Sylvie Coste-Marquis, Pierre Marquis · Frontiers in artificial intelligence and applications · 2023
We elaborate on the notion of rectification of a classifier Σ based on Boolean features, introduced in [10]. The purpose is to determine how to modify Σ when the way it classifies a given instance is considered incorrect since it conflicts with some expert knowledge T. Given Σ and T, postulates characterizing the way Σ must be changed into a new classifier Σ ⋆ T that complies with T were presented. We focus here on the specific case of binary 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 ⋆ satisfying the postulates, and (2) when Σ and T are Boolean circuits, we show how a classification circuit equivalent to Σ ⋆ T can be computed in time linear in the size of Σ and T; when Σ is a decision tree (resp. a random forest, a boosted tree) and T is a decision tree, a decision tree (resp. a random forest, a boosted tree) equivalent to Σ ⋆ T can be computed in time polynomial in the size of Σ and T.