Robust Mahalanobis Metric Learning via Geometric Approximation Algorithms
원문 초록
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.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Why and How: Knowledge-Guided Learning for Cross-Spectral Image Patch Matching
지도 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 에서 제공한다.
AbRank: A Benchmark Dataset and Metric-Learning Framework for Antibody-Antigen Affinity Ranking
Global Ground Metric Learning with Applications to scRNA data
Discrete Scale-invariant Metric Learning for Efficient Collaborative Filtering
DA-VPT: Semantic-Guided Visual Prompt Tuning for Vision Transformers
토론
이 논문과 연결된 포럼 글이 아직 없습니다.