Abstract | ||
---|---|---|
Metric learning has become a widespreadly used tool in machine learning. To reduce expensive costs brought in by increasing dimensionality, low-rank metric learning arises as it can be more economical in storage and computation. However, existing low-rank metric learning algorithms usually adopt nonconvex objectives, and are hence sensitive to the choice of a heuristic low-rank basis. In this paper, we propose a novel low-rank metric learning algorithm to yield bilinear similarity functions. This algorithm scales linearly with input dimensionality in both space and time, therefore applicable to high-dimensional data domains. A convex objective free of heuristics is formulated by leveraging trace norm regularization to promote low-rankness. Crucially, we prove that all globally optimal metric solutions must retain a certain low-rank structure, which enables our algorithm to decompose the high-dimensional learning task into two steps: an SVD-based projection and a metric learning problem with reduced dimensionality. The latter step can be tackled efficiently through employing a linearized Alternating Direction Method of Multipliers. The efficacy of the proposed algorithm is demonstrated through experiments performed on four benchmark datasets with tens of thousands of dimensions. |
Year | Venue | Keywords |
---|---|---|
2015 | PROCEEDINGS OF THE TWENTY-NINTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE | similarity |
Field | DocType | Citations |
Singular value decomposition,Mathematical optimization,Heuristic,Semi-supervised learning,Active learning (machine learning),Computer science,Wake-sleep algorithm,Curse of dimensionality,Heuristics,Regularization (mathematics),Artificial intelligence,Machine learning | Conference | 13 |
PageRank | References | Authors |
0.52 | 39 | 6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Wei Liu | 1 | 4041 | 204.19 |
Cun Mu | 2 | 205 | 8.83 |
Rongrong Ji | 3 | 3616 | 189.98 |
Shiqian Ma | 4 | 1068 | 63.48 |
John R. Smith | 5 | 4939 | 487.88 |
Shih-Fu Chang | 6 | 13015 | 1101.53 |