半监督距离度量学习的内蕴加速投影梯度算法

运筹学学报

• 运筹学 •

半监督距离度量学习的内蕴加速投影梯度算法

仰迪¹,白延琴²

1. 上海大学
2. 上海大学理学院数学系

收稿日期:2018-01-12 修回日期:2018-09-28 发布日期:2019-03-05
通讯作者: 白延琴

An Intrinsic Accelerated Projection Gradient Algorithm for Semi-supervised Metric Learning

Received:2018-01-12 Revised:2018-09-28 Published:2019-03-05
Contact: yanqin BAi

摘要/Abstract

摘要： 本文考虑求解一类半监督距离度量学习问题. 由于样本集（数据库）的规模与复杂性的激增, 在考虑距离度量学习问题时, 我们必须考虑学习来的距离度量矩阵具有稀疏性的特点. 因此, 在现有的距离度量学习模型中, 增加了学习矩阵的稀疏约束. 为了便于模型求解, 稀疏约束应用了Frobenius范数约束. 进一步, 通过罚函数方法将Frobenius范数约束罚到目标函数, 使得具有稀疏约束的模型转化成无约束优化问题. 为了求解问题, 我们提出了正定矩阵群上加速投影梯度算法, 克服了矩阵群上不能直接进行线性组合的困难, 并分析了算法的收敛性. 最后通过UCI数据库的分类问题的例子, 进行了数值实验, 数值实验的结果说明了学习矩阵的稀疏性以及加速投影梯度算法的有效性.

关键词: 半监督距离度量学习, 加速投影梯度算法, 正定矩阵群

Abstract: In this paper, we consider a class of semi-supervised metric learning problems. Due to the explosion in size and complexity of datasets, it is increasingly important to consider the sparse of metric learning. We add the constraint of sparse for the model of semi-supervised metric learning. To be easy to deal with the sparse constraint, we apply the Frobenius norm to define the sparse and transform it into the objective function of model by using the penalty parameter. Next we present a accelerated projection gradient algorithm, which is originally designed for convex smooth optimization in Euclidean space, over a positive definite matrix group. We analyze the convergence of our algorithm. Finally, we show the numerical test to demonstrate the effectiveness of the proposed algorithm.

Key words: distance metric learning, intrinsic accelerated projection gradient algorithm, positive definite matrices groups

仰迪白延琴. 半监督距离度量学习的内蕴加速投影梯度算法[J]. 运筹学学报.

参考文献

\item{[1]}
E. Xing, A. Ng, and et al. Distance metric learning with application to
clustering with side-information [C]. {\it Adv. NIPS}, 2002, 505-512.

\item{[2]}
K. Weinberger, J. Blitzer and et al. Distance metric learning
for large margin nearest neighbor classification [J]. {\it Neural
Information Processing Systems}, 2005, 1473-1480.

\item{[3]}
K. Fukunaga. Introduction to Statistical Pattern
Recogniton [M]. {\it Academic}, 1990.

\item{[4]}
T. Cox and M. Cox. Multidimensional Scaling [M]. {\it Chapmanand Hall}, London, 2001.

\item{[5]}
Q. Wang, P. Yuen, and et al. Semi-supervised metric learning via topology
preserving multiple semi-supervised assumptions [J]. {\it Pattern
Recognition}, 2013, 2576-2587.

\item{[6]}
S. Ying, Z. Wen and et al. Manifold preserving:
an intrinsic approach for semi-supervised distance metric learning, {\it IEEE Transactions on Neural Networks and Learning Systems}, 2017.

\item{[7]}
Y. Nesterov. A method of solving a convex programming problem with convergence rate
O(1/k2) [J]. {\it Soviet Mathematics Doklady}, 1983,(27): 372-376.

\item{[8]}
T. Paul. On accelerated proximal gradient methods for convex-concave
Optimization [J]. {\it Siam Journal on Optimization}, 2008.

\item{[9]}
A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding
algorithm for linear inverse problems [J]. {\it Siam Journal Imaging Sciences}, 2009, 183-202.

\item{[10]}
李鑫, 白延琴. 半监督度量学习内蕴最速下降算法的收敛性分析 [J]. {\it 运筹学学报}, 2017.

\item{[11]}
高聪. 李群均值学习算法及其应用研究 [D]. {\it 兰州大学硕士学位论文}, 2012.

\item{[12]}
李春辉. 统计流形和矩阵流形上的几何结构及其应用[D]. {\it 北京理工大学博士学位论文}, 2014.

\item{[13]}
S. Hoi, W. Liu and et al. Semi-supervised distance metric learning
for collaborative image retrieval and clustering[J]. {\it ACM Trans. Mult. Comput}, 2010.

\item{[14]}
J. Davis, B. Kulis, and et al. Information-theoretic metric learning [J]. {\it Proc. ICML}, 2012, 3239-3247.

\item{[15]}
Andrew Baker. Matrix Groups: An Introduction to Lie Group Theory
[M]. {\it Springer Undergraduate Mathematics Series}, 2003.

\item{[16]}
N. Parikh and S. Boyd. Proxiaml Algorithm [M]. {\it Foundation and Trends in Optimization}, 2013, 123-231.

\item{[17]}
Y. Nesterov. Smooth minimization of nonsmooth functions [J]. {\it Mathematical Programming}, 2005,(103): 127-152.

半监督距离度量学习的内蕴加速投影梯度算法

An Intrinsic Accelerated Projection Gradient Algorithm for Semi-supervised Metric Learning

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	仰迪, 白延琴, 李倩. 半监督距离度量学习内蕴加速投影梯度算法[J]. 运筹学学报, 2018, 22(2): 66-78.
[2]	李鑫, 白延琴. 半监督度量学习内蕴最速下降算法的收敛性分析[J]. 运筹学学报, 2017, 21(3): 1-13.