arXiv:1905.09989

Robust Mahalanobis Metric Learning via Geometric Approximation Algorithms

Diego Ihara, Neshat Mohammadi, Francesco Sgherzi, Anastasios Sidiropoulos

제출 2019-05-24

원문 초록

Learning Mahalanobis metric spaces is an important problem that has found numerous applications. Several algorithms have been designed for this problem, including Information Theoretic Metric Learning (ITML) [Davis et al. 2007] and Large Margin Nearest Neighbor (LMNN) classification [Weinberger and Saul 2009]. We study the problem of learning a Mahalanobis metric space in the presence of adversarial label noise. To that end, we consider a formulation of Mahalanobis metric learning as an optimization problem, where the objective is to minimize the number of violated similarity/dissimilarity constraints. We show that for any fixed ambient dimension, there exists a fully polynomial-time approximation scheme (FPTAS) with nearly-linear running time. This result is obtained using tools from the theory of linear programming in low dimensions. As a consequence, we obtain a fully-parallelizable algorithm that recovers a nearly-optimal metric space, even when a small fraction of the labels is corrupted adversarially. We also discuss improvements of the algorithm in practice, and present experimental results on real-world, synthetic, and poisoned data sets.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2502.00168stat.ML공통 태그 Metric Learning공식 코드 · Papers with Code

지도 2차 특징 분석: 차원 축소를 위한 정보 기하학 접근

Supervised Quadratic Feature Analysis: Information Geometry Approach for Dimensionality Reduction

지도 차원 축소는 클래스 분리를 유지하면서 레이블이 붙은 데이터를 저차원 특징 공간으로 매핑한다. 일반적인 전략은 클래스 조건부(class-conditional) 확률 분포 간 통계적 비유사성(dissimilarity) 측정을 최대화하는 특징을 학습하는 것이다. 리만 기하학(Riemannian geometry)에 뿌리를 둔 정보 기하학(information geometry)은 클래스 비유사성 측정을 위한 대안적 틀을 제공한다. 이는 확률 분포를 통계적 다양체(statistical manifold) 상의 점으로 취급하고, Fisher 정보 계량(Fisher information metric)을 사용하여 분포 간 측지 거리(geodesic distance)—Fisher-Rao 거리—를 정의한다. Fisher-Rao 거리는 Fisher 정보 계량이 국소적 변별력(discriminability)의 측도이고 기하학적 해석이 가능하기 때문에 클래스 분리 측정에 매력적인 후보이다. 본 논문에서는 가우시안 가정 하에서 클래스 조건부 분포 간 Fisher-Rao 거리를 최대화하는 선형 특징을 학습하는 지도 차원 축소 방법인 지도 2차 특징 분석(Supervised Quadratic Feature Analysis, SQFA)을 제안한다. 여러 실제 데이터셋에서 SQFA 특징은 더 널리 쓰이는 비유사성 측도를 최대화한 특징이나 다른 최신(state-of-the-art) 차원 축소 방법으로 학습된 특징과 경쟁력 있는 분류 정확도를 달성한다. 특히 차원 축소에서 드물게 사용되는 목적 함수인 Hellinger 거리를 최대화하는 SQFA 변형인 SQFA-H 특징이 최고의 분류 정확도를 달성한다. 이 결과는 지도 차원 축소 도구로서 정보 기하학의 잠재력을 보여준다. SQFA의 Python 구현은 https://github.com/dherrera1911/sqfa 에서 제공한다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.