Semi-supervised Robust Dictionary Learning via Efficient l-Norms Minimization

Hua Wang, Feiping Nie, Weidong Cai, Heng HuangICCV 2013 · OpenReview

Abstract

Representing the raw input of a data set by a set of relevant codes is crucial to many computer vision applications. Due to the intrinsic sparse property of real-world data, dictionary learning, in which the linear decomposition of a data point uses a set of learned dictionary bases, i.e., codes, has demonstrated state-of-the-art performance. However, traditional dictionary learning methods suffer from three weaknesses: sensitivity to noisy and outlier samples, difficulty to determine the optimal dictionary size, and incapability to incorporate supervision information. In this paper, we address these weaknesses by learning a Semi-Supervised Robust Dictionary (SSR-D). Specifically, we use the $\ell_{2,0+}$-norm as the loss function to improve the robustness against outliers, and develop a new structured sparse regularization to incorporate the supervision information in dictionary learning, without incurring additional parameters. Moreover, the optimal dictionary size is automatically learned from the input data. Minimizing the derived objective function is challenging because it involves many non-smooth $\ell_{2,0+}$-norm terms. We present an efficient algorithm to solve the problem with a rigorous proof of the convergence of the algorithm. Extensive experiments are presented to show the superior performance of the proposed method.

Introduction

Dictionary learning is a cornerstone of computer vision, used to represent complex data like images as a sparse combination of basic "atoms." However, traditional methods have three major "Achilles' heels": sensitivity to outliers, the need for manual scaling of dictionary sizes, and the difficulty of integrating label information without complex hyperparameter tuning.

This paper introduces SSR-D, a dictionary learning framework that simultaneously tackles these hurdles. By using a novel $\ell_{2,0+}$-norm for both error measurement and regularization, the model automatically prunes redundant features and remains stable even when a significant portion of the training data is mislabeled.

Methods

The proposed Semi-Supervised Robust Dictionary Learning (SSR-D) utilizes the $\ell_{2,0+}$-norm, a generalization of the $\ell_{2,1}$-norm, to achieve three goals:

  1. Robust Loss Function: Instead of squaring the reconstruction error (which skews results in the presence of outliers), the model uses the $\ell_{2,p}$-norm with a very small $p$. This effectively ignores large errors from outliers.
  2. Adaptive Dictionary Size: By applying structured sparsity to representation coefficients, the model forces the coefficients of useless atoms to zero. This allows the model to start with a large "super-dictionary" and automatically shrink it to the natural size of the dataset.
  3. Seamless Supervision: The coefficient matrix is organized based on class labels, allowing the model to learn class-specific dictionaries naturally without extra penalty terms.
Table showing that the learned dictionary size |Dx| remains stable regardless of the initial size |D|.

Key Insights and Results

Adaptive Dictionary Pruning

A striking finding is that the learned dictionary size ($|D_X|$) remains remarkably stable regardless of the initial size. As shown in the experimental results, whether starting with 100 or 1,000 atoms, the model prunes down to a similar number of "essential" atoms that reflect the true underlying patterns of the data.

Performance and Robustness

The authors evaluated SSR-D across diverse benchmarks, including image data (AT&T, USPS), text data (Reuters, TDT2), and multi-label video data (TRECVID 2005).

Comparison of SSR-D against state-of-the-art methods under clean (top) and 20% noisy (bottom) label conditions.
  • Clustering: On the AT&T dataset, SSR-D achieved a clustering accuracy of 78.2%, outperforming ESC (77.6%) and K-means (69.1%).
  • Classification under Noise: In real-world scenarios where perfect labels are rare, SSR-D excels. When 20% of training labels were corrupted, SSR-D maintained high performance (e.g., 86.1% on Reuters), while standard methods like K-SVD saw massive drops (to 63.5%).
  • Multi-label Performance: On the TRECVID 2005 dataset, SSR-D consistently showed the lowest Hamming Loss and highest Average Precision compared to methods like D-K-SVD and Group Sparse Coding (GSC).

Conclusion

SSR-D provides a robust, self-scaling, and supervised dictionary learning framework. While it still requires selection of norm powers ($p, q$) and regularization weights, it eliminates the need for manual dictionary size tuning and complex supervision parameters. Future work may extend this iterative reweighted algorithm to deep learning architectures or online learning settings.

Summary updated

Abstract

Representing the raw input of a data set by a set of relevant codes is crucial to many computer vision applications. Due to the intrinsic sparse property of real-world data, dictionary learning, in which the linear decomposition of a data point uses a set of learned dictionary bases, i.e., codes, has demonstrated state-of-the-art performance. However, traditional dictionary learning methods suffer from three weaknesses: sensitivity to noisy and outlier samples, difficulty to determine the optimal dictionary size, and incapability to incorporate supervision information. In this paper, we address these weaknesses by learning a Semi-Supervised Robust Dictionary (SSR-D). Specifically, we use the l <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2,0+</sub> -norm as the loss function to improve the robustness against outliers, and develop a new structured sparse regularization to incorporate the supervision information in dictionary learning, without incurring additional parameters. Moreover, the optimal dictionary size is automatically learned from the input data. Minimizing the derived objective function is challenging because it involves many non-smooth l <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2,0+</sub> -norm terms. We present an efficient algorithm to solve the problem with a rigorous proof of the convergence of the algorithm. Extensive experiments are presented to show the superior performance of the proposed method.
BibTeX
@inproceedings{wang2013semi,
  author = {Hua Wang and Feiping Nie and Weidong Cai and Heng Huang},
  title = {{Semi-supervised Robust Dictionary Learning via Efficient l-Norms Minimization}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2013},
  url = {https://openreview.net/forum?id=rk-eCxGd-H},
}
Figure