Exploring Outliers in Crowdsourced Ranking for QoE

Qianqian Xu, Ming Yan, Chendi Huang, Jiechao Xiong, Qingming Huang, Yuan Yao

Abstract

Crowdsourced Quality of Experience (QoE) evaluations are essential for multimedia assessment but are frequently compromised by noisy data from unreliable or malicious raters. This paper introduces three iterative algorithms—iHT, iLTS, and aLTS—based on $l_0$-regularization to efficiently detect and remove outliers in paired comparison data. Our methods achieve up to a 90x speedup compared to traditional LASSO-based approaches while providing unbiased estimators and superior accuracy. These advancements enable highly scalable and robust ranking for large-scale crowdsourced datasets.

Introduction

Evaluating the Quality of Experience (QoE) for multimedia often involves large-scale paired comparisons, where users choose between two items (e.g., "Which video has better quality?"). Crowdsourcing platforms like Amazon Mechanical Turk facilitate the collection of the massive sample sizes required, but they also introduce significant noise. Raters may provide random or intentional incorrect feedback due to lack of supervision.

Existing outlier detection methods, such as the Huber-LASSO approach, rely on $l_1$-regularization. While effective, LASSO is computationally intensive and introduces bias by shrinking all sample weights rather than selectively removing outliers. This paper addresses these limitations by proposing faster, unbiased, and scalable $l_0$-regularization methods.

Methodology

The authors propose a shift from convex $l_1$-regularization to nonconvex $l_0$-regularization, which directly counts the number of non-zero entries (outliers). To overcome the NP-hard nature of $l_0$ optimization, three iterative algorithms were developed:

  1. Iterative Hard Thresholding (iHT): Alternates between solving a least squares ranking problem and applying hard thresholding to residuals to identify the top $K$ outliers.
  2. Iterative Least Trimmed Squares (iLTS): Similar to iHT but excludes the $K$ suspected outliers from the least squares fit in each iteration, ensuring the ranking score remains uninfluenced by noise.
  3. Adaptive Least Trimmed Squares (aLTS): A practical extension that automatically estimates the number of outliers ($K$) by monitoring preference direction violations and stabilizing the threshold.

Theoretical analysis confirms that these algorithms converge to the true outlier set under conditions similar to the Restricted Isometry Property (RIP).

Experimental Evaluation

The algorithms were tested on both simulated and real-world datasets:

  • Simulated Data: A ground-truth ranking of 16 items with varying percentages of reversed preference edges.
  • PC-VQA & PC-IQA: Real-world crowdsourced video and image quality datasets containing tens of thousands of comparisons from hundreds of raters.

Performance Results

The proposed algorithms demonstrated significant improvements in both efficiency and accuracy. iHT and iLTS were found to be 30 to 90 times faster than Huber-LASSO, while aLTS was 3 to 8 times faster despite its dynamic estimation overhead.

Precision of outlier detection across different sample sizes (SN) and outlier percentages.

As shown in Figure 1, the aLTS algorithm consistently maintains high precision even as the outlier percentage increases, outperforming LASSO and the fixed-$K$ iterative methods.

Recall of outlier detection across different sample sizes (SN) and outlier percentages.

Similarly, Figure 6 illustrates that the recall of the proposed methods remains robust across different sample sizes (SN), ensuring that a high percentage of true outliers are correctly identified.

Discussion and Conclusion

The transition to $l_0$-regularization provides a dual benefit: it eliminates the bias inherent in $l_1$ methods and drastically reduces computational costs. A key insight from the study is the behavioral difference in outlier classification; while LASSO focuses on the magnitude of deviation from a continuous score, aLTS effectively identifies minority votes that violate global preference trends.

While the adaptive algorithm (aLTS) requires a reasonably consistent initial estimator to succeed, its performance on real-world datasets like PC-VQA and PC-IQA proves its viability for cleaning noisy crowdsourced data. Future work will focus on extending these edge-based detection methods to subject-based analysis, allowing for the identification and exclusion of entire unreliable raters.

Summary updated

BibTeX
@inproceedings{xu2017exploring,
  author = {Qianqian Xu and Ming Yan and Chendi Huang and Jiechao Xiong and Qingming Huang and Yuan Yao},
  title = {{Exploring Outliers in Crowdsourced Ranking for QoE}},
  booktitle = {ACM Multimedia},
  year = {2017},
  url = {https://openreview.net/forum?id=EXsyxsnInv},
}
Figure