낮은 내재 차원 개념 학습을 위한 스무딩 분석
Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
한국어 초록
전통적인 지도 학습 모델에서 학습자의 목표는—$\mathbb{R}^d \times \{\pm 1\}$ 위의 임의의 결합 분포로부터 주어진 예시에 대해—어떤 클래스에 속한 가장 잘 맞는 개념(concept)에 $ε$ 이내로 경쟁력 있는 가설을 출력하는 것이다. 단순한 개념 클래스조차 학습하기 어렵다는 강한 난이도 결과를 피하기 위해, 우리는 학습자가 작은 무작위 가우시안 perturbation에 견고한 최적 분류기와만 경쟁하도록 요구하는 스무딩 분석(smoothed-analysis) 프레임워크를 도입한다. 이 미묘한 변화를 통해 (1) 저차원 부분공간에 의존하는(일명 multi-index model) (2) 유계 가우시안 표면적(bounded Gaussian surface area)을 갖는 모든 개념에 대해 폭넓은 학습 결과를 제시할 수 있다. 이 클래스는 반공간(halfspace)의 함수와 (저차원) 볼록 집합을 포함하며, 후자는 비스무딩 설정에서는 가우시안과 같이 highly structured distribution에 대해서만 학습 가능한 것으로 알려져 있었다. 우리가 정의한 스무딩 비지도적 학습(smoothed agnostic learning)은 인스턴스 분포 $D$와 최적 분류기가 임의로 결합(coupled)될 수 있는 경우(비지도적 학습 및 $σ= 0$에 해당)와 완전히 분리(decoupled)된 경우($σ= \infty$) 사이를 보간한다. 이러한 분리를 통해 복잡도 이론적 원시 연산(complexity-theoretic primitives)을 인코딩할 수 있는 최악의 개념을 피할 수 있다. 놀랍게도 우리 분석은 마진(margin)을 이용한 학습과 같은 전통적인 비스무딩 프레임워크에도 새로운 결과를 제공한다. 특히 마진 매개변수 $γ$에 대해 $k^{\mathrm{poly}(\frac{\log k}{εγ}) }$ 시간에 $k$개 반공간의 교집합을 비지도적으로 학습하는 최초의 알고리즘을 얻는다. 우리 연구 이전에는 알려진 최선의 실행 시간이 $k$에 대해 지수적이었다(Arriaga and Vempala, FOCS' 99).
원문 초록
In traditional models of supervised learning, the goal of a learner-- given examples from an arbitrary joint distribution on $\mathbb{R}^d \times \{\pm 1\}$-- is to output a hypothesis that is competitive (to within $ε$) of the best fitting concept from some class. In order to escape strong hardness results for learning even simple concept classes, we introduce a smoothed-analysis framework that requires a learner to compete only with the best classifier that is robust to small random Gaussian perturbation. This subtle change allows us to give a wide array of learning results for any concept that (1) depends on a low-dimensional subspace (aka multi-index model) and (2) has a bounded Gaussian surface area. This class includes functions of halfspaces and (low-dimensional) convex sets, cases that are only known to be learnable in non-smoothed settings with respect to highly structured distributions such as Gaussians. Our definition of smoothed agnostic learning is an interpolation between the case where the instance distribution $D$ and the optimal classifier can be arbitrarily coupled (which corresponds to agnostic learning and $σ= 0$) and completely decoupled (when $σ= \infty$). This decoupling allows us to avoid worst-case concepts that can encode complexity-theoretic primitives. Surprisingly, our analysis also yields new results for traditional non-smoothed frameworks such as learning with margin. In particular, we obtain the first algorithm for agnostically learning intersections of $k$-halfspaces in time $k^{\mathrm{poly}(\frac{\log k}{εγ}) }$ where $γ$ is the margin parameter. Before our work, the best-known runtime was exponential in $k$ (Arriaga and Vempala, FOCS' 99).
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2407.00966v3제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.