# A Model-Agnostic Algorithm for Bayes Error Determination in Binary Classification
## 2 Mathematical Notation and Dataset Aggregation  
Let us consider a dataset with \(N\) categorical features, i.e., each feature can only assume a finite set of values. Let us suppose that the \(i\)th feature, denoted as \(F_{i}\), takes \(n_{i}\) possible values. For notational simplicity, it is assumed that the categorical feature is encoded in such a way that its possible values are integers from \(1\) to \(n_{i}\), with \(i=1,\ldots,N\) (note that each \(n_{i}\) can assume different integer values). Each possible combination of the features is called here a bucket. The idea is that the observations will be aggregated in buckets depending on their features. The number of observations present in the dataset are indicated with \(M\). All the observations with the same set of features are said to be in the same bucket. The problem is a binary classification one, aiming at predicting an event that can have only two possible outcomes, indicated here with class 0 and class 1. In general, in the \(j\)th bucket, there will be a certain number of observations (that we will indicate with \(m_{0}^{[j]}\)) with a class of 0, and a certain number of observations (that we will indicate with \(m_{1}^{[j]}\)) with a class of 1. The feature vector for each observation, denoted as \(x_{k}\) (with \(k=1,\ldots,M\)), is thus defined by an \(N\)-dimensional vector \((F_{1,k},F_{2,k},\ldots,F_{N,k})\in\mathbb{N}^{N}\), where \(F_{i,k}\) denotes the value of the \(i\)-th feature of the \(k\)-th sample. The following useful definitions are now introduced. **Definition 1**. : _A feature bucket \(B^{[j]}\) is a possible combination of the values of the \(N\) features, i.e.,_  
\[B^{[j]}=\{(F_{1}^{[j]},F_{2}^{[j]},\ldots,F_{N}^{[j]})\in\mathbb{N}^{N}|\,F_{i }^{[j]}\in\{0,1,\ldots,n_{i}-1\},i=1,\ldots,N\} \tag{1}\]  
In the rest of the paper, the feature bucket is indicated as  
\[B^{[j]}=(F_{1}^{[j]},F_{2}^{[j]},\ldots,F_{N}^{[j]})\]  
to explicitly mention the feature values characterizing the bucket \(B^{[j]}\). The total number \(N_{B}\) of feature buckets is thus equal to \(N_{B}=\prod_{i=1}^{N}n_{i}\). As an example, in the case of two binary features \(F_{1}\) and \(F_{2}\), four possible feature buckets can be constructed, namely, \(B^{[1]}=(0,0)\), \(B^{[2]}=(0,1)\), \(B^{[3]}=(1,0)\) and \(B^{[4]}=(1,1)\). **Definition 2**. : _The set \(M^{[j]}\) of the indices of observations belonging to the \(j\)-th feature bucket \(B^{[j]}\) is defined as_  
\[M^{[j]}=\{k\in[1,\;M]\,|\,F_{0,k}=F_{0}^{[j]}\;\text{and}\;F_{1,k}=F_{1}^{[j]} \;\text{and}\;\ldots\;F_{N,k}=F_{N}^{[j]}\} \tag{2}\]  
The cardinality of the set \(M^{[j]}\) will be denoted as \(|M^{[j]}|\). In a binary classification problem, the observations belonging to the feature bucket \(B^{[j]}\), denoted as  
\[O^{[j]}=\{x_{k}\,|\,k\in M^{[j]}\} \tag{3}\]  
will contain \(m_{0}^{[j]}\in\mathbb{N}_{0}\) observations with a target variable equal to 0 and \(m_{1}^{[j]}\in\mathbb{N}_{0}\) observations with a target variable equal to 1. Note that by definition  
\[|M^{[j]}|=m_{0}^{[j]}+m_{1}^{[j]} \tag{4}\]  
and  
\[M\equiv\sum_{j=1}^{N_{B}}|M^{[j]}|=\sum_{j=1}^{N_{B}}(m_{0}^{[j]}+m_{1}^{[j]}) \tag{5}\]  
Based on the definitions above, the original dataset can be equivalently represented by a new dataset of buckets, an aggregated dataset \(B\), each of which contains a certain number of samples \(|M^{[j]}|=m_{0}^{[j]}+m_{1}^{[j]}\). A visual representation of the previously described rearrangement of the original dataset is reported in Figure 1 for a dataset with two binary features. In the aggregated dataset \(B\), each record is thus a feature bucket \(B^{[i]}\), characterized by the number of observations of class 0 (\(m_{0}^{[j]}\)) and the number of observations of class 1 (\(m_{1}^{[j]}\)). In the previous example of a dataset with only two binary features, \(B\) would look like the one in Table 1. In this easy example a dataset with any number of observations \(M\) would be reduced to one with only 4 records, i.e., the number of possible buckets.