<jupyter_start><jupyter_text>Handling mislabeled training data for classification TAMU 689-Stat Computing Course Project (https://longjp.github.io/statcomp/)  IntroductionIn this work, we discuss different ways of handling mislabeled data in classification problems. The techniques we discuss identify and eliminate mislabeled data from the training set, thereby improving its quality. We discuss two approaches in this paper1) a general filtering based technique 2) The rankpruning algorithm for removing noisy labels. As mentioned in the related papers, we were able to empirically verify the increased accuracy for the techniques discussed. Also, we provide two simple scripts that can be used (or referred) for using the technques with any dataset and model for classification.  What is mislabeled data?- Data for classification problems in supervised learning, usually consists of a set of feature attributes and a class attribute.Consider a tranining Data Point:  $(x_1, x_2, x_3, …, x_n, y)$A data point is considered *mislabeled* if class y is incorrect. Eg. lets say we want to classify a set of images as a dog or cat. If the image is of a cat, we say the class as 1. Following is the training data:![title](img/cat_classification.png)*Image source: https://www.deeplearning.ai/*In the above example, we can see that, there is one data point which is incorrectly labeled, i.e. the white puppy, 2nd from right, is labeled as cat.  Reasons for Mislabeling dataSome common reasons for mislabeling are as follows:- **Subjectivity**: It can arise when observations need to be ranked in some way such as disease severity or when the information used to classify object is different from information to which learning algorithm have access. Eg. experts labeling the images, they normally use their visual input rather than each pixel of the image. - **Data Entry Error**: It can arise when the training dataset is prepared due to manual error.- **Inadequate Information**: It can arise when the information used to label each datapoint is insufficient. Eg. in medical diagnosis, it is almost impossible to guarantee that a diagnosis is 100% accurate.  Methods for handling Mislabeling- **Noise Elimination**: In this approach, mislabeled data points are removed and then learning classifier is applied on the remaining dataset.- **Noise Tolerance**: In this approach, mislabeled data points are not removed and the learning classifier is applied on the original training data. Our ideas are based on Noise elimination approach. We discuss 2 ideas in our project to identify mislabeled instances. First one is a general approach and second one uses a specific algorithm called *RankPruning*.  General filtering approach This idea is taken from the paper ["Identifying Mislabeled Training Data" <NAME> and <NAME>, 1999 ](https://arxiv.org/abs/1106.0219). It describes the general procedure for identifying the mislabeled instances in a training set. It consists of following steps:1. Identify candidate instance by using m learning algorithms(or filters) to tag them as correctly or incorrectly labeled. This is done in following way:    -  Divide training data into n folds    -  Train a filtering model on (n-1) folds using m learning algorithms, and add a *mislabeled* class attribute to the examples in the nth fold using the same m classifiers.     -  Repeat this for n folds    -  In end, all instances have been tagged as mislabeled or not. 2. Now, on this mislabeled training dataset, apply the filtering approach to remove all the mislabeled instances. 3. Apply the final learning algorithm on the filtered training instances. This resulting classifier is end product of this approach.Figure below depicts this idea:![title](img/filtering.png)  Types of Filtering approachesThere are 3 types of filtering approaches we tried and compared them:- Single Algorithm Filter    -  Filtering is done by one algorithm    -  Instance is marked as mislabeled if this algorithm tagged it as mislabeled- Majority Vote Filter    -  Filtering is done by multiple algorithms    -  Instance is marked as mislabeled if more than half of the algorithms tagged it as mislabeled- Consensus Filter    -  Filtering is done by multiple algorithms    -  Instance is marked as mislabeled if all of the algorithms tagged it as mislabeled  Identification ErrorsIn identifying mislabeled instances, there are 2 types of errors that can be made:1. E1 - This occurs when a correct instances is incorrectly tagged as mislabeled and subsequently discarded. This is equivalent to throwing out the good data.2. E2 - This occurs when a mislabeled instance is tagged as correctly labeled. This is equivalent of keeping the bad data after filtering.Below is the figure showing E1 and E2 in the training instances space in form of Venn DiagramNow, we analyze the probability of each of these errors in majority and consensus filter. 1. Majority FilterIn case of Majority filter, E1 occurs when more than half of the m-base level classifiers tagged the instance as mislabeled. Let $P(E1_i)$ be the probability that classifier i makes an error E1 and assume that all the m-base level classifiers have equal probability to make an error E1. Then, the probability of the majority vote filter to make  an error E1 is given by:$P(E1) = \sum_{j>m/2}^{j=m} P(E1_i)^j (1 - P(E1_i))^{m-j}{m \choose j}$The error E2 occurs when more than half of the m-base level classifiers tagged the incorrect instance as correctly labeled and hence the instance is not removed. Let $P(E2_i)$ be the probability that classifier i makes an error E2 and assume errors are independent. Then, the probability that the majority vote filter would make an error E2 is given by:$P(E2) = \sum_{j>m/2}^{j=m} P(E2_i)^j (1 - P(E2_i))^{m-j}{m \choose j}$2. Consensus FilterFor a consensus filter, an E1 error occurs when all of the m base level classifiers fail to classify instance correctly. Let $P(E1_i)$ be the probability that classifier i makes error E1. Then, the probability of the consensus filter to make  an error E1 is given by:$P(E1) = \prod_{i=1}^{m} P(E1_i)$The error E2 in case of consensus filter occurs when a incorrect instance is tagged as correct by atleast one of m-base level classifiers. Let $P(E2_i)$ be the probability that classifier i makes error E2. Then, the probability of the consensus filter to make  an error E2 is given by:$P(E2) = 1 - \prod_{i=1}^{m} (1 - P(E2_i))$  E1 and E2 General Formula:A general formula to calculate the probability of throwing out good data(E1) is :$P(E1) = \frac{Discarded - Intersect}{Total-Corrupted} = \frac{D - M \cap D}{Total - M}$Similarly, general formula to calculate the probability of keeping bad data(E2) is :$P(E2) = \frac{Corrupted - Intersect}{Corrupted} = \frac{M - M \cap D}{M}$These are the formulas we have used in our code to calculate P(E1) and P(E2). These formulas are evident from the Venn diagram shown above.  Code Results & EvaluationWe have written the code in Python to evaluate the different types of filtering approach discussed above. First we implemented the approach ([see the runner function in main.py](https://github.com/shubham7jain/STAT689-Project/blob/master/main.pyL7)) and then we apply a wrapper on top of that to vary the inputs to that implementation which changes Noise level, classifiers and filtering types. We show the accuracy of different filtering approaches by varying noise levels in the training data. Also, we show the E1 and E2 errors by varying noise levels and filtering approaches. Evaluation is done on the MNIST dataset. The training is done on 10000 images and test data comprises of 1000 images. We add noise to training data and the test dataset is kept clean. We used different classifier algorithms for different filtering approaches. We always used Logistic Regression as the final classifier model to keep the results consistent among different filtering approaches. Below is the list of filtering algorithms used in each filtering approach:- **Single Algorithm Filter(SF)** : Logistic Regression- **Majority Filter(MF)** : Logistic Regression, Random Forest Classifier, MLP Classifier- **Consensus Filter(CF)** : Logistic Regression, Random Forest Classifier, MLP ClassifierNoise level used = [0%, 5%, 10%, 15%, 20%, 25%, 30%, 35%, 40%] Below is the result from the code showing accuracy and errors E1, E2 for different noise levels and different approaches:**Note** The MNIST dataset takes a while to run, for testing, we've also included a function to read the iris data set. You can change [this line](https://github.com/shubham7jain/STAT689-Project/blob/master/main.pyL17).<jupyter_code>%run -i 'script.py'<jupyter_output>Running for noise level =  0.0  and filtering =  False  and filtering type =  None
Running for noise level =  0.0  and filtering =  True  and filtering type =  SF
Running for noise level =  0.0  and filtering =  True  and filtering type =  MF
Running for noise level =  0.0  and filtering =  True  and filtering type =  CF
Running for noise level =  0.05  and filtering =  False  and filtering type =  None
Running for noise level =  0.05  and filtering =  True  and filtering type =  SF
Running for noise level =  0.05  and filtering =  True  and filtering type =  MF
Running for noise level =  0.05  and filtering =  True  and filtering type =  CF
Running for noise level =  0.1  and filtering =  False  and filtering type =  None
Running for noise level =  0.1  and filtering =  True  and filtering type =  SF
Running for noise level =  0.1  and filtering =  True  and filtering type =  MF
Running for noise level =  0.1  and filtering =  True  and filtering type =  CF
Running for noise level =  [...]
{'fraction_non_alphanumeric': 0.05693069306930693, 'fraction_numerical': 0.015573432343234323, 'mean_word_length': 4.399220489977728, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 8, 'https://': 5, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '375399', 'license': 'MIT', 'n_tokens_mistral': 2546, 'n_tokens_neox': 2343, 'n_words': 1427, 'path': 'Report.ipynb', 'repo_name': 'shubham7jain/STAT689-Project', 'size': '9708'}