While considerable theoretical progress has been devoted to the study of metric and similarity learning, the generalization mystery is still missing. In this paper, we study the generalization performance of metric and similarity learning by leveraging the specific structure of the true metric (the target function). Specifically, by deriving the explicit form of the true metric for metric and similarity learning with the hinge loss, we construct a structured deep ReLU neural network as an approximation of the true metric, whose approximation ability relies on the network complexity. Here, the network complexity corresponds to the depth, the number of nonzero weights and the computation units of the network. Consider the hypothesis space which consists of the structured deep ReLU networks, we develop the excess generalization error bounds for a metric and similarity learning problem by estimating the approximation error and the estimation error carefully. An optimal excess risk rate is derived by choosing the proper capacity of the constructed hypothesis space. To the best of our knowledge, this is the first-ever-known generalization analysis providing the excess generalization error for metric and similarity learning. In addition, we investigate the properties of the true metric of metric and similarity learning with general losses.

我们通过利用真实度量（目标函数）的特定结构，构建了一个近似真实度量的结构化深层ReLU神经网络，从而研究了度量和相似性学习的泛化性能，推导了度量和相似性学习问题的过度泛化误差界限，并通过仔细估计逼近误差和估计误差，得出了一个最佳的过度风险率，这是首次的度量和相似性学习的过度泛化错误分析，此外，我们还研究了具有一般损失的度量和相似性学习的真实度量的属性。

深度ReLU网络的度量学习和相似性学习的泛化分析