Regression algorithm on [0,1] with lots of mislabeled data

Question

I have a training set mapping some Likert-scale variables (integers between 1 and 7, rescaled to real numbers between 0 and 1) to predict a continuous variable between 0 and 1. The data set is reasonable large ($10^4$-$10^5$ rows) but very noisy (5-20% has bogus labeling).

When applying regression algorithms to this dataset, the regression algorithm predicts scores only in a subinterval of [0,1], e.g. scores below 0.1 and above 0.9 are not reached for any input value of the columns. This is expected given the bogus labels; but also inacceptable, as the prediction for non-bogus rows is severely impacted. Moreover, since 0.0 and 1.0 are the most common target values in the training set (it is a 'How much ... are you?' type prediction) it is not appreciated by the users that 0.0 and/or 1.0 would be unreachable. (Simply stretching the result to cover [0,1] greatly increases the error, so is probably suboptimal.)

What method could I use to detect and remove these mislabeled/bogus rows, or at least a significant amount of them? Since they are a minority, I would think something with majority voting should be the answer, but it's not clear how to implement such an approach, since $7^{n_{cols}} > n_{rows}$.

Answer 1

Since you seem to have enough data, RANSAC could be a good option. That is, we treat the noisy data as outliers. The idea of RANSAC is to iteratively detect those outliers and discard them from the fitting. It is extensively used in image processing for tasks like camera calibration and segmenting primitives like planes in a 3D point cloud, with very good results, because it is able to handle a high rate of outliers, when there are enough data points (as it is your case).

For the sake of completeness, let me copy verbatim the description of the algorithm from Wikipedia (a more detailed though still accessible introduction can be found in RANSAC for dummies by M. Zuliani.

    Given:
        data – a set of observations
        model – a model to explain observed data points
        n – minimum number of data points required to estimate model parameters
        k – maximum number of iterations allowed in the algorithm
        t – threshold value to determine data points that are fit well by model 
        d – number of close data points required to assert that a model fits well to data

    Return:
        bestFit – model parameters which best fit the data (or nul if no good model is found)

    iterations = 0
    bestFit = nul
    bestErr = something really large
    while iterations < k {
        maybeInliers = n randomly selected values from data
        maybeModel = model parameters fitted to maybeInliers
        alsoInliers = empty set
        for every point in data not in maybeInliers {
            if point fits maybeModel with an error smaller than t
                add point to alsoInliers
        }
        if the number of elements in alsoInliers is > d {
            % this implies that we may have found a good model
            % now test how good it is
            betterModel = model parameters fitted to all points in maybeInliers and alsoInliers
            thisErr = a measure of how well betterModel fits these points
            if thisErr < bestErr {
                bestFit = betterModel
                bestErr = thisErr
            }
        }
        increment iterations
    }
    return bestFit

---

Answer 2

Considering the size of the Dataset Mentioned by you can use Heterogenous Ensemble, Homogenous Ensemble or Edited Nearest Neighbors for Filtering the noise in the Data.

The homogeneous ensemble is inspired by Cross-Validated Committees Filter[1]. At noise levels approximately more than 10% Heterogenous Ensemble performs worse than Homogenous Ensemble.

So you should use Homogenous Ensemble to filter the noise. You can use Apache-Spark to implement this model. Here is the algorithm for this method:

• Input: data consisting of labels and features
• Input: P= the number of partitions
• Input: n= Trees the number of trees for Random Forest
• Input: e= error tolerance (0<e<1)
• Output: the filtered data without noise
• partitions ← kFold(data, P)
• filteredData ← NULL
• for all train, test in partitions do
•       rfModel ← random Forest(train, n Trees)
•       rfPred ← predict(rfModel, test)
•       joinedData ← join(zipWithIndex(test), zipWithIndex(rfPred))
•       markedData ←
•       map original, prediction ∈ joinedData
•       if label(prediction)-(label(prediction)) *e < label(original) < label(prediction)+
       (label(prediction))*e then
•           original
•       else
•           (label = NULL, features(original))
•       end if
• end map
• filteredData ← union(filteredData, markedData)
• end for
• return(filter(filteredData, label != NULL))

[1]       [C.E. Brodley, M.A. Friedl. Identifying Mislabeled Training Data. Journal of Artificial Intelligence Research 11 (1999) 131-167 doi: 10.1613/jair.606]