# Histogram-Based Descriptor Subset Selection for Visual Recognition of Industrial Parts
## 2 Background
### Classifiers  
Descriptors are used to obtain features from images. Those features are then used by the classifiers to predict which object is on each image. Many machine learning algorithms are used for classifying images, but some of the most popular ones are K-Nearest Neighbors, Naive Bayes, Random Forest, Support Vector machine, Random Committee, Bagging, and Multiclass Classifier.  
The Nearest Neighbor Rule is a well-known algorithm and the simplest nonparametric decision procedure that assigns to the uncategorized object the label of the closest sample of the training set. In 1967, a modification of this algorithm led to one of the most used classification algorithms, the K-Nearest Neighbors (KNN) [28]. It is based on looking for closest points and classifying them as the majority class. For a given set of \(n\) pairs \((x_{1},\theta_{1}),...,(x_{n},\theta_{n})\), where \(x_{i}\) is in a metric space \(X\) and \(\theta_{i}\) is the category that \(x_{i}\) belongs to from a subset \(\{1,2,...,M\}\), a new arriving instance \(x\) is analyzed to estimate its corresponding class \(\theta\). This estimation is done by looking for the nearest neighbor \(X^{\prime}_{n}\in(x_{1},x_{2},...,x_{n})\):  
\[min\,d(x_{i},x)=d(x^{\prime}_{n},x)i=1,2,...,n\]  
where \(d\) is a distance metric according to the space \(X\). The new instance \(x\) will be assigned to the category \(\theta^{\prime}_{n}\). This is the basic 1-NN. In general, KNN rule decides \(x\) belongs to the category of majority vote of the nearest \(k\) neighbors.  
The Naive Bayes [29], the simplest Bayesian classifier, is another classification algorithm that is often used for its simplicity. It is based on the Bayesian Rule and assumes that variables are independent given the class. Despite this unrealistic assumption, it is successful in practice. The Bayesian rule states that the probability that a instance \(x\) belongs to class \(C_{k}\) is  
\[P(C_{k}|\mathbf{x})=\frac{P(C_{k})P(\mathbf{x}|C_{k})}{P(\mathbf{x})} \tag{1}\]  
where \(C_{k}\) is the class between the \(K\) possible classes and \(x\) the instance to be classified. Taking into account the independence assumption, the conditional distribution over the class variable C is  
\[p(C_{k}|x_{1},...,x_{n})=\frac{1}{Z}p(C_{k})\prod_{i=1}^{n}p(x_{i}|C_{k}) \tag{2}\]  
The instance is classified as the class with more \(p(C_{k}|x_{1},...,x_{n})\).  
The Random Forest (RF) [30] is a combination of decision trees that use random subsets of the features to be built. Figure 1 shows an example of RF.  
Support Vector Machines (SVM) [31] are supervised learning models that look for optimal hyperplanes that separates classes. An optimal hyperplane is defined as the linear decision function with maximal margin between the vectors of the two classes (Figure 2).  
Figure 1: Random Forest example where each tree classifies the new instance and the resulting class is decided by majority voting.  
Figure 2: Support vector machine: maximum separation between two classes.  
Random Committee (RC) [32] is a committee of random classifiers. The base randomizable classifiers (that form the committee members) are built using different random number seeds based in the same data. The final prediction is a straight average of the predictions generated by the individual base classifiers.  
The Bagging [33] technique is called after Bootstrap aggregating. This machine learning ensemble that can be used to improve the stability of a model by improving the accuracy and reducing variance in order to reduce overfitting.