Does More Features always mean Higher Accuracy ? [Bayesian Classifier MATLAB Code]

In machine learning, is it always true that you will achieve higher classification accuracy if you use more features ? In other words, does more features always mean higher accuracy ?

This is the question that I'm going to analyze and answer in this post. I hope you find it useful. Please let me know if you have any questions in the comments, I will be happy to answer. For that we will use the Skin Segmentation Dataset and the Naive Bayesian Classifier. I implement the Bayesian classifier, and no libraries or Toolboxes are used.

The code is here for you to download and play with.

The Skin Segmentation Dataset (Rajen Bhatt, Abhinav Dhall, UCI Machine Learning Repository) is collected by randomly sampling B,G,R values from face images of various age groups (young, middle, and old), race groups (white, black, and Asian), and genders obtained from FERET database and PAL database. Total learning sample size is 245057; out of which 50859 is the skin samples and 194198 is non-skin samples. The dataset is of the dimension 245057 * 4 where first three columns are B,G,R (x1,x2, and x3 features) values and fourth column is of the class labels (decision variable y).

The first 90% in each class samples are chosen to form the training data, while the remaining 10% of points in each class form the test data.

Data Set Characteristics:	Univariate	Number of Instances:	245057	Area:	Computer
Attribute Characteristics:	Real	Number of Attributes:	4	Date Donated	2012-07-17
Associated Tasks:	Classification	Missing Values?	N/A	Number of Web Hits:	66931

Figure 1 shows plots of the two classes likelihood, the fitted normal distribution (not used by the classifier and plotted for visualization only), and posterior probabilities built from the training data. The plot is for the best single designated feature which I found to the third one (the pixel red color feature). The prior for the first class W1 (skin class) is chosen to be 0.4 and the second class W2 (non-skin class) is chosen to be 0.6. These two values are chosen to reflect the fact that skin colors are really a smaller subset of all the possible colors, and this is the reason why these values achieves better Minimum Correct Classification Rate (MCCR).

Figure 1. Plots of the two classes’ likelihood and posterior probabilities for the best single feature (the red color feature)

Now, I pick two features together until identifying the best couple of features. Figure 2 shows plots of the likelihood and posterior for the best couple of features, which are the blue color and red color features. You have the code and you can try and you will come to the same result as I.

Figure 2. Plots of the two classes’ likelihood and posterior probabilities for the best couple of features (blue and red colors features)

The normal Bayes rule is applied for each test sample x, and the classification to class i is done such that:, where w1 means skin class and w2 means non-skin class. The priors are chosen such that P(w1)=0.4 and P(w1)=0.6 to reflect the fact that skin colors are really a smaller subset of all the possible colors, and this is the reason why these values achieves better Minimum Correct Classification Rate (MCCR). For fair comparison for the three cases of features space dimensionality, the histogram bins width is kept fixed in all the cases; a color value feature takes a range from 0 to 255, and the bin width is chosen to be equal to 10 (set empirically based on the database size).

For the best single feature, the best couple of features, and the three features combined, the resulted MCCR are equal to 0.8439, 0.9581, and 0.9128 respectively as shown in figure 3.

Figure 3. MCCR for different number of features

As stated earlier, the red feature is proven to be the best single feature. Also, my experiment indicated that if any two features out of the three colors features are combined, a better MCCR is achieved than the red color feature alone! The gain is maximized in the case of combining the red and blue colors features (best couple of features).

If the green feature is combined with the best couple of features to form combined three features, the MCCR is still better than the best single feature case. But it slightly decreases compared to the best couple of features case. In general, it is not always better to use more features for higher accuracy, but to use the right features. Any feature has some good aspects where a good representation of some aspects of the data is achieved, and some other bad aspects, where a noisy representation of some aspects of the data is achieved. If the good aspects of a feature are already correlated with the existing features in a system (more than the bad aspects), adding that feature will introduce more overall bad feature representation and reduces the MCCR. This is what happened when we added the green color feature to the best couple of features.

Note: On the other hand, the higher the number of features (especially when the number of training samples is small) the more probable to over-fit on the training data, and hence you achieve lower classification accuracy in test data. This is one reason why PCA is good. We will discuss it in detail in a coming post.

MLP Neural Network with Backpropagation [MATLAB Code]

This is an implementation for Multilayer Perceptron (MLP) Feed Forward Fully Connected Neural Network with a Sigmoid activation function. The training is done using the Backpropagation algorithm with options for Resilient Gradient Descent, Momentum Backpropagation, and Learning Rate Decrease. The training stops when the Mean Square Error (MSE) reaches zero or a predefined maximum number of epochs is reached.

Four example data for training and testing are included with the project. They are generated by SharkTime Sharky Neural Network.

1- Download Code
http://www.mathworks.com/matlabcentral/fileexchange/54076-mlp-neural-network-with-backpropagation

2- Network architecture & Training Parameters:
The code configuration parameters are as follows:

1- Numbers of hidden layers and neurons per hidden layer. It’s represented by the variable nbrOfNeuronsInEachHiddenLayer. To have a neural network with 3 hidden layers with number of neurons 4, 10, and 5 respectively; that variable is set to [4 10 5].
2- Number of output layer nits. Usually the number of output units is equal to the number of classes, but it still can be less (≤ log2(nbrOfClasses)). It’s represented by the variable nbrOfOutUnits. The number of input layer units is obtained from the training samples dimension.
3- The selection if the sigmoid activation function is unipolar or polar. It’s represented by the variable unipolarBipolarSelector.
4- The learning rate η.
5- The maximum number of epochs at which the training stops unless MSE reaches zero. It’s represented by the variable nbrOfEpochs_max.
6- Option to enable or disable Momentum Backpropagation. It’s represented by the variable enable_learningRate_momentum.
7- The Momentum Backpropagation rate α. It’s represented by the variable momentum_alpha.
8- Option to enable or disable Resilient Gradient Descent. It’s represented by the variable enable_resilient_gradient_descent.
9- The Resilient Gradient Descent parameters: η+, η-, Δmin, Δmax, represented by the variables learningRate_plus, learningRate_negative, deltas_min, and deltas_max.

10- Option to enable or disable Learning Rate Decrease. It’s represented by the variable enable_decrease_learningRate.
11- The Learning Rate Decrease parameters: and . It’s represented by the variables learningRate_decreaseValue and min_learningRate.

The code also contains a parameter for drawing the decision boundary separating the classes and the MSE curve. The number of epochs after which a figure is drawn and saved on the machine is specified. The figures are saved in a folder named Results besides the m files. This parameter is represented by the variable draw_each_nbrOfEpochs. The variable dataFileName takes the Sharky input points file name as string.

3- Results:
In all of the following four test cases, MCCR=1. The stop condition is that MSE reaches zero in all the cases. A unipolar sigmoid function is chosen.

A) Linear Points Case:

Figure 1. Network: 2-4-2 , Unipolar Sigmoid Activation, No Options, η=0.15.

B) Circle Points Case:

Figure2. Network: 2-10-2 , Unipolar Sigmoid Activation, Resilient Gradient Descent, η+=1.2, η-=0.5, Δmin=10^-6, Δmax=50.

C) Wave Points Case:

Figure 3. Network: 2-10-10-2 , Unipolar Sigmoid Activation, Resilient Gradient Descent, η+=1.2, η-=0.5, Δmin=10^-6, Δmax=50.

D) Spiral Points Case:

Figure 4. Network: 2-10-10-2 , Unipolar Sigmoid Activation, Resilient Gradient Descent, η+=1.2, η-=0.5, Δmin=10^-6, Δmax=50.

The following image shows a magnification for the decision boundary with better resolution.

Figure 5. Magnified decision boundary with better resolution for Spiral points case. 

The following video shows the solving of the Two Spirals problem.

Video 1. Solving the Two Spirals Problem.

A New Variant of Douglas–Peucker Algorithm (2/4) [Original Algo. MATLAB Implementation]

Previous Posts  

A New Variant of Douglas–Peucker Algorithm (1/4)

Original Douglas-Peucker Algorithm

The following algorithm description is taken from Wikipdeia [1] and CodeProject article by Elmar de Koning [2]. The Ramer–Douglas–Peucker algorithm (RDP) is an algorithm for reducing the number of points in a curve that is approximated by a series of points. This algorithm is also known under the names Douglas–Peucker algorithm, iterative end-point fit algorithm and split-and-merge algorithm.

The Douglas-Peucker algorithm uses a point-to-edge distance tolerance. The algorithm starts with a crude simplification that is the single edge joining the first and last vertices of the original polyline. It then computes the distance of all intermediate vertices to that edge. The vertex that is furthest away from that edge, and that has a computed distance that is larger than a specified tolerance, will be marked as a key and added to the simplification. This process will recurse for each edge in the current simplification, until all vertices of the original polyline are within tolerance of the simplification results. This process is illustrated below:

Initially, the simplification consists of a single edge. During the first step, the fourth vertex is marked as a key and the simplification is adjusted accordingly. During the second step, the first edge of the current simplification is processed. The maximum vertex distance to that edge falls below the tolerance threshold, and no new key is added. During the third step, a key is found for the second edge of the current simplification. This edge is split at the key and the simplification is updated. This process continues until no more keys can be found. Note that at each step, only one edge of the current simplification is processed.
This algorithm has a worst case running time of O(nm), and O(n log m) on average, where m is the size of the simplified polyline. As such, this is an output dependent algorithm, and will be very fast when m is small. To make it even faster, the Distance between points routine is applied as a pre-processing step.

MATLAB Implementation

function out_points = points_simplify_2d(points, epsilon)

  id_end = size(points,1);

  id_start = 1;

  % Indeces of points are not removed by Douglas-Peucker algorithm

  remaining_ids = true(id_end,1);

  % Call douglas_peucker_iteration (recursive function)

  [points remaining_ids] = douglas_peucker_iteration( ...
     points,epsilon,id_start,id_end, remaining_ids);

  out_points = points(remaining_ids,:);

end

function [points remaining_ids]  = douglas_peucker_iteration(points, epsilon, id_start, id_end, remaining_ids)

  % For the points (start + 1) to (end) -> next_points_relative is

  % relative coordinates from start point

  next_points_relative = bsxfun(@minus, points(id_start+1:id_end,:), 

     points(id_start,:));

  end_point_relative = next_points_relative(end,:)';

  % Efficient Method to get distances_from_start_end_line

  beta = (end_point_relative' *

     next_points_relative')./(end_point_relative'*end_point_relative);

  b = next_points_relative-bsxfun(@times,beta,end_point_relative)';

  distances_from_start_end_line = hypot(b(:,1),b(:,2));

  % Identify maximum distance and get its index

  [dmax dmax_id] = max(distances_from_start_end_line);

  dmax_id  = id_start + dmax_id; %ID of the edge point

  if dmax <= epsilon;
    remaining_ids(id_start+1:id_end-1) = false; 
  else  

    [points remaining_ids] = douglas_peucker_iteration( ...
       points,epsilon,id_start,dmax_id, remaining_ids);

    [points remaining_ids] = douglas_peucker_iteration( ...

       points,epsilon,dmax_id,id_end, remaining_ids);

  end

end

______________________________________________________________________
References:
[1] http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
[2] Polyline Simplification

A New Variant of Douglas–Peucker Algorithm (1/4) [Introduction]

The Ramer-Douglas-Peucker is a polyline simplification algorithm that uses a point-to-edge (point-to-line) distance tolerance “Epsilon”. The algorithm starts with a crude simplification that is the single edge (line) joining the first and last vertices (points) of the original polyline (polyline needed to be simplified). There is a variant of this algorithm already that allows it to produce a polyline with a fixed number of vertices “N”.

From software points of view, sometimes it’s preferred to have a fixed-size array to store a polyline vertices. Thus, the variant version of the Douglas-Peucker algorithm, that produces a fixed number of vertices “N”, is more convenient. However, from applications point of view, it doesn’t make sense to describe a simple polyline (rectangular area for example) with the same number of vertices that describe a complex-shaped one. This is why I’ve introduced my own version of the Douglas-Peucker algorithm, which I call a “Regularized” version.

My modified algorithm takes two pieces of data as inputs. The first is a predefined maximum number of vertices "N". The second is a tolerance "Epsilon". The algorithm returns n ≤ N vertices; it excludes the vertices that over-fit according to the predefined tolerance "Epsilon”. Those are the vertices that would have not been selected using the original Douglas-Peucker algorithm if it runs using the given "epsilon". A sample results of my variant of the Douglas–Peucker algorithm are shown in the coming table.

(A) N=50 , Epsilon=1.5 :	(B) N=50 , Epsilon=1.0 :
(C) N=100 , Epsilon=1.5 :	(D) N=10 , Epsilon=1.5 :

In the previous table, polyline (B) contains more vertices than polyline (A), because decreasing Epsilon allows more vertices to produce max edge distances higher than Epsilon, while these points still produce a polyline with number of vertices less than N. The resulted polyline in (C) is the same as (A), because increasing N, while having the same Epsilon will not produce new vertices that fits that Epsilon. Polyline in (D) contains fewer vertices than the polyline in (A), because the number of vertices in polyline (A) is greater than the N in (D).

In a coming posts, I will post the algorithms and MATLAB implementations for the three configurations:
- Original Douglas-Peucker algorithm.
- Variant of Douglas-Peucker algorithm (fixed number of simplified vertices "N").
- My Variant of Douglas-Peucker algorithm (with "N" and a tolerance "Epsilon").