The goal of supervised hashing is to train a hash code with classification and retrieval
capabilities. However, during the process of collecting training data, it is inevitable that
negative effects may occur, such as data contamination, missing values, or damaged data,
subsequently leading to the generation of outliers. These outliers can significantly bias the
training process and degrade classification and retrieval capabilities. This study focuses
on improving the robustness of supervised hashing methods. Typical supervised hashing
uses ℓ2 norms as the loss function, but previous research has shown that ℓ2 norms are
sensitive to outliers, making the hash code generated from contaminated training data
ineffective for classification and retrieval.
To enhance the robustness of supervised hashing, this study proposes Robust Semidefinite Relaxation Hashing (RSDRH) that uses a more robust loss function, instead of the
ℓ2 norm, including ℓ1 norm or nonconvex functions. However, these robust loss functions
are neither convex nor smooth, making them challenging to solve. To address this challenge, this study transforms the optimization problem into a semidefinite programming
(SDP) problem based on semidefinite relaxation (SDR). Then, the problem is reformulated into the standard form of low-rank semidefinite programming. The errors caused by
relaxation can be reduced due to the strong duality between semidefinite relaxation and
the original problem. To deal with nonconvex optimization problems, we utilize the majorization minimization (MM) algorithm to construct a convex surrogate function that is
easier to solve, and we obtain approximate solutions rapidly through the alternating direction method of multipliers (ADMM). This study conducted experiments on four publicly
available datasets with contaminated data. The results demonstrated that the proposed
method outperformed typical supervised hashing when dealing with data containing outliers.
論文審定書 i
摘要 ii
Abstract iii
目錄 v
圖目錄 vii
表目錄 viii
符號表 xii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的與方法 2
1.3 論文架構 3
第二章 文獻回顧 4
第三章 研究方法 7
3.1 問題描述 7
3.2 本研究提出的方法 9
3.2.1 半定鬆弛 9
3.2.2 使用 ℓ1 範數作為損失函數的半定鬆弛雜湊 12
3.2.3 使用非凸函數作為損失函數的半定鬆弛雜湊 17
第四章 研究結果 23
4.1 資料集 23
4.2 實驗設置 24
4.3 評估指標 32
4.4 實驗結果 34
第五章 結論 82
參考文獻 83
[1] T. Fawcett, “An introduction to ROC analysis,” Pattern Recognition Letters, vol. 27,
no. 8, pp. 861–874, Jun. 2006.
[2] R.-C. Tu, X.-L. Mao, B.-S. Feng, and S.-Y. Yu, “Object detection based deep unsu pervised hashing,” in Proc. International Joint Conference on Artificial Intelligence,
Macao, China, 2019, Aug. 10–16, pp. 3606–3612.
[3] C. Deng, E. Yang, T. Liu, J. Li, W. Liu, and D. Tao, “Unsupervised semantic preserving adversarial hashing for image search,” IEEE Transactions on Image Pro cessing, vol. 28, no. 8, pp. 4032–4044, Aug. 2019.
[4] W. Liu, J. Wang, R. Ji, Y.-G. Jiang, and S.-F. Chang, “Supervised hashing with
kernels,” in Proc. IEEE Conference on Computer Vision and Pattern Recognition,
Providence, Rhode Island, USA, 2012, Jun. 16–21, pp. 2074–2081.
[5] G. Lin, C. Shen, Q. Shi, A. van den Hengel, and D. Suter, “Fast supervised hashing
with decision trees for high-dimensional data,” in Proc. IEEE Conference on Com puter Vision and Pattern Recognition, Columbus, Ohio, USA, 2014, Jun. 23–28, pp.
1971–1978.
[6] F. Shen, C. Shen, W. Liu, and H. T. Shen, “Supervised discrete hashing,” in
Proc. IEEE Conference on Computer Vision and Pattern Recognition, Boston, Mas sachusetts, USA, 2015, Jun. 07–12, pp. 37–45.
[7] T. T. Do, A. D. Doan, D. T. Nguyen, and N. M. Cheung, “Binary hashing with
semidefinite relaxation and augmented Lagrangian,” in Proc. European Conference
on Computer Vision, Amsterdam, Netherlands, 2016, Oct. 11–14, pp. 802–817.
[8] W.-C. Kang, W.-J. Li, and Z.-H. Zhou, “Column sampling based discrete supervised
hashing,” in Proc. AAAI Conference on Artificial Intelligence, Phoenix, Arizona,
USA, 2016, Feb. 12–17, pp. 1230–1236.
[9] D. L. Woodruff and E. Zemel, “Hashing vectors for tabu search,” Annals of Opera tions Research, vol. 41, no. 2, pp. 123–137, Jun. 1993.
[10] X. Luo, Y. Wu, and X.-S. Xu, “Scalable supervised discrete hashing for large-scale
search,” in Proc. World Wide Web Conference, Lyon, France, 2018, Apr. 23–27, pp.
1603–1612.
[11] X. Luo, L. Nie, X. He, Y. Wu, Z.-D. Chen, and X.-S. Xu, “Fast scalable supervised
hashing,” in Proc. International ACM SIGIR Conference on Research and Develop ment in Information Retrieval, Ann Arbor, Michigan, USA, 2018, Apr. 08–12, pp.
735–744.
[12] Y. Chen, Z. Tian, H. Zhang, J. Wang, and D. Zhang, “Strongly constrained discrete
hashing,” IEEE Transactions on Image Processing, vol. 29, pp. 3596–3611, Jun.
2020.
[13] Y. He, F. Wang, Y. Li, J. Qin, and B. Chen, “Robust matrix completion via maximum
correntropy criterion and half-quadratic optimization,” IEEE Transactions on Signal
Processing, vol. 68, pp. 181–195, Nov. 2019.
[14] J. Tang, K. Wang, and L. Shao, “Supervised matrix factorization hashing for cross modal retrieval,” IEEE Transactions on Image Processing, vol. 25, no. 7, pp.
3157–3166, May 2016.
[15] P. Wang, C. Shen, A. van den Hengel, and P. H. Torr, “Large-scale binary quadratic
optimization using semidefinite relaxation and applications,” IEEE Transactions on
Pattern Analysis and Machine Intelligence, vol. 39, no. 3, pp. 470–485, Mar. 2016.
[16] Q. Yao, H. Yang, E.-L. Hu, and J. T. Kwok, “Efficient low-rank semidefinite pro gramming with robust loss functions,” IEEE Transactions on Pattern Analysis and
Machine Intelligence, vol. 44, no. 10, pp. 6153–6168, Oct. 2021.
[17] K. Lange, R. Hunter, and I. Yang, “Optimization transfer using surrogate objective
functions,” Journal of Computational and Graphical Statistics, vol. 9, no. 1, pp.
1–20, Mar. 2000.
[18] D. Hunter and K. Lange, “A tutorial on MM algorithms,” American Statistician,
vol. 58, no. 1, pp. 30–37, Feb. 2004.
[19] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Distributed optimization
and statistical learning via the alternating direction method of multipliers,” Founda tions and Trends® in Machine Learning, vol. 3, no. 1, pp. 1–122, Jul. 2011.
[20] B. He and X. Yuan, “On the O(1/n) convergence rate of the Douglas–Rachford alter nating direction method,” SIAM Journal on Numerical Analysis, vol. 50, no. 2, pp.
700–709, Jan. 2012.
[21] Y. Weiss, A. Torralba, and R. Fergus, “Spectral hashing,” in Proc. 21st Interna tional Conference on Neural Information Processing Systems, Vancouver, British
Columbia, Canada, 2008, Dec. 08–11, pp. 1753–1760.
[22] A. Gionis, P. Indyk, and R. Motwani, “Similarity search in high dimensions via
hashing,” in Proc. International Conference on Very Large Data Bases, Edinburgh,
Scotland, UK, 1999, Sep. 07–10, pp. 518–529.
[23] Y. Gong, S. Lazebnik, A. Gordo, and F. Perronnin, “Iterative quantization: A pro crustean approach to learning binary codes for large-scale image retrieval,” IEEE
Transactions on Pattern Analysis and Machine Intelligence, vol. 35, no. 12, pp.
2916–2929, Sep. 2012.
[24] J. Gui, T. Liu, Z. Sun, D. Tao, and T. Tan, “Fast supervised discrete hashing,”
IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 40, no. 2,
pp. 490–496, Mar. 2017.
[25] D. S. Hochba, “Approximation algorithms for NP-Hard problems,” ACM Sigact
News, vol. 28, no. 2, pp. 40–52, Jun. 1997.
[26] X. Luo, P.-F. Zhang, Z. Huang, L. Nie, and X.-S. Xu, “Discrete hashing with mul tiple supervision,” IEEE Transactions on Image Processing, vol. 28, no. 6, pp.
2962–2975, Jan. 2019.
[27] P. Belotti, C. Kirches, S. Leyffer, J. Linderoth, J. Luedtke, and A. Mahajan, “Mixed integer nonlinear optimization,” Acta Numerica, vol. 22, pp. 1–131, May 2013.
[28] S¸. Ozt ¨ urk, “Convolutional neural network based dictionary learning to create hash ¨
codes for content-based image retrieval,” Procedia Computer Science, vol. 183, pp.
624–629, Jan. 2021.
[29] Y. Chen, Z. Lai, Y. Ding, K. Lin, and W. K. Wong, “Deep supervised hashing with
anchor graph,” in Proc. IEEE International Conference on Computer Vision, Seoul,
Korea, 2019, Oct. 27–Nov. 02, pp. 9796–9804.
[30] Q.-Y. Jiang and W.-J. Li, “Asymmetric deep supervised hashing,” in Proc. AAAI
Conference on Artificial Intelligence, New Orleans, Louisiana, USA, 2018, Feb.
02–07.
[31] Y. Cao, M. Long, B. Liu, and J. Wang, “Deep Cauchy hashing for Hamming space
retrieval,” in Proc. IEEE Conference on Computer Vision and Pattern Recognition,
Salt Lake City, Utah, USA, 2018, Jun. 18–23, pp. 1229–1237.
[32] C. Zhang, “Nearly unbiased variable selection under minimax concave penalty,”
Annals of Statistics, vol. 38, no. 2, pp. 894–942, Apr. 2010.
[33] J. Trzasko and A. Manduca, “Highly undersampled magnetic resonance image re construction via homotopic ℓ0-minimization,” IEEE Transactions on Medical Imag ing, vol. 28, no. 1, pp. 106–121, Jul. 2008.
[34] S. Burer and R. Monteiro, “A nonlinear programming algorithm for solving semidef inite programs via low-rank factorization,” Mathematical Programming, vol. 95, pp.
329–357, 2003.
[35] S. Burer and R. D. Monteiro, “Local minima and convergence in low-rank semidefi nite programming,” Mathematical Programming, vol. 103, no. 3, pp. 427–444, 2005.
[36] M. Journe´e, F. Bach, P. Absil, and S. R., “Low-rank optimization on the cone
of positive semidefinite matrices,” SIAM Journal on Optimization, pp. 2327–2351,
2010.
[37] J. Gui, T. Liu, Z. Sun, D. Tao, and T. Tan, “Supervised discrete hashing with relax ation,” IEEE Transactions on Neural Networks and Learning Systems, vol. 29, no. 3,
pp. 608–617, Dec. 2016.
[38] J. Davis and M. Goadrich, “The relationship between precision-recall and ROC
curves,” in Proc. International Conference on Machine Learning, New York City,
New York, USA, 2006, Jun. 25–29, pp. 233–240.
電子全文 ( 網際網路公開日期：20260424 )