유한한 VC 차원을 갖는 신경망: 장점과 단점
Networks with Finite VC Dimension: Pro and Contra
한국어 초록
고차원 기하학 및 통계적 학습 이론 관점에서 신경망을 통한 대규모 데이터셋 분류기의 근사와 학습을 연구한다. 신경망의 입출력 함수 집합이 지닌 VC 차원이 근사 능력에 미치는 영향을, 데이터 표본으로부터의 학습 일관성(consistency)에 미치는 영향과 비교한다. 유한한 VC 차원은 경험적 오차의 균등 수렴(uniform convergence)에 바람직하지만, 주어진 유형의 응용 분야에서 함수가 나타날 가능도(likelihood)를 모델링하는 확률 분포로부터 추출된 함수를 근사하는 데는 바람직하지 않을 수 있음을 보인다. 고차원 기하학의 측도 집중(concentration of measure) 특성을 바탕으로, 대규모 데이터셋을 처리할 때 유한한 VC 차원을 갖는 입출력 함수 집합을 구현하는 신경망에서는 근사 오차와 경험적 오차 모두 거의 결정론적으로 동작함을 증명한다. 보편 근사 특성(universal approximation property)의 실질적 한계, 근사 정확도와 데이터 학습 일관성 사이의 상충 관계(trade-off), 그리고 렐루(ReLU) 유닛을 사용하는 신경망의 깊이가 정확도와 일관성에 미치는 영향에 대해 논의한다.
원문 초록
Approximation and learning of classifiers of large data sets by neural networks in terms of high-dimensional geometry and statistical learning theory are investigated. The influence of the VC dimension of sets of input-output functions of networks on approximation capabilities is compared with its influence on consistency in learning from samples of data. It is shown that, whereas finite VC dimension is desirable for uniform convergence of empirical errors, it may not be desirable for approximation of functions drawn from a probability distribution modeling the likelihood that they occur in a given type of application. Based on the concentration-of-measure properties of high dimensional geometry, it is proven that both errors in approximation and empirical errors behave almost deterministically for networks implementing sets of input-output functions with finite VC dimensions in processing large data sets. Practical limitations of the universal approximation property, the trade-offs between the accuracy of approximation and consistency in learning from data, and the influence of depth of networks with ReLU units on their accuracy and consistency are discussed.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
VC 학습의 최적 정보 복잡도
The optimal information complexity of VC learning
Steinke와 Zakynthinou(2020)는 알고리즘 의존적 정보이론적 양에 기반하여 학습 알고리즘의 정보 복잡도를 분석하는 조건부 상호정보량(CMI) 프레임워크를 도입했습니다. 본 연구에서는 이러한 양 중 하나인 평가된 조건부 상호정보량(eCMI)을 연구합니다. CMI를 통한 알고리즘 의존적 분석으로부터 VC 클래스에 대한 최적의 PAC 보장을 복원할 수 있는지는 흥미로운 질문이었습니다. 본 논문에서는 개념 클래스의 VC 차원이 d일 때, 실현 가능(realizable)한 경우에서 eCMI가 O(d) 차수인 학습 알고리즘을 구축함으로써 이러한 보장을 복원할 수 있음을 보입니다. 구체적으로 본 알고리즘은 최적의 기댓값 일반화 보장을 갖는 5개 기반 학습기의 무작위화된 다수결(Majority-of-5) 방식입니다.
ERM 오라클을 활용한 표본 최적 다중 그룹 학습
Sample-Optimal Multi-Group Learning with an ERM Oracle
다중 그룹 학습(multi-group learning)에서는 단일 예측기가 풍부하며 잠재적으로 무한하고 중첩될 수 있는 하위 집단 모음의 모든 그룹에 대해 해당 클래스 내 최적의 가설만큼 우수한 성능을 보여야 합니다. 최적의 표본 복잡도(sample complexity)를 갖는 기존 알고리즘들은 그룹과 가설의 모든 쌍을 추적하는데, 이는 관심 대상인 대규모 클래스에서는 불가능하며, 알려진 오라클 기반 알고리즘들은 더 열등한 수렴 속도를 갖습니다. 본 연구에서는 경험적 위험 최소화(ERM) 오라클을 통해서만 클래스에 접근하는 학습자가 최적의 수렴 속도를 달성할 수 있는지 질문을 던집니다. 본 논문에서는 그룹과 가설 쌍에 대한 가중치 적용 ERM 오라클을 다항 횟수만큼 호출하고 $\tilde{O}((d_G+d_H)/\varepsilon^2)$개의 표본을 사용하는 알고리즘을 제시합니다. 여기서 $d_G$와 $d_H$는 그룹 및 가설 클래스의 VC 차원이며, $\varepsilon$은 확률로 가중치가 부여된 모든 그룹에서의 초과 위험(excess risk)을 제한합니다. 또한 무제한의 계산 능력을 가진 모든 학습자에 대해서도 일치하는 하한인 $\Omega((d_G+d_H)/\varepsilon^2)$개의 표본을 보여줌으로써, 오라클 효율성을 위해 추가적인 표본이 소모되지 않음을 입증합니다. 아울러 모든 입력이 최대 $k$개의 그룹에 속하고 이러한 그룹들을 나열할 수 있는 자연스러운 특수 경우도 고려합니다. 이 경우 가설 클래스에 대한 ERM 오라클만으로 충분하며, 애그노스틱(agnostic) 설정에서는 $\tilde{O}((d_H+\log k)/\varepsilon^2)$개의 표본이, 모든 그룹에 대해 해당 그룹에서 올바른 가설이 존재하는 경우에는 $\tilde{O}((d_H+\log k)/\varepsilon)$개의 표본이 필요합니다.
압축을 통한 학습: 위험 추정치가 큰 수의 법칙 수렴 속도를 달성하다
Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate
압축 스키마(compression schemes)는 학습 알고리즘에 대한 데이터 의존적 위험 상한(risk bound)을 유도하기 위한 일반적인 프레임워크를 제공합니다. 선호 압축(preferent compression) 기반 학습 규칙의 경우, 기존 연구 결과들은 복원된 가설이 부적절한 학습(training) 예제들이 더해진 압축 집합의 크기로 정의되는 샘플 의존적 복잡도 $\boldsymbol{k}$를 바탕으로 위험의 상한을 설정합니다. 그러나 이러한 결과들은 $\boldsymbol{k}/N$ 위에 $O(\sqrt{\ln N/N})$ 차수의 마진(margin)을 유발합니다. 본 논문에서는 이 로그 팩터가 본질적인 것이 아님을 규명합니다. 우리는 모든 고정된 신뢰 수준 $1-δ$에 대해, 위험이 적어도 $1-δ$의 확률로 모든 가능한 $\boldsymbol{k}$ 값에 걸쳐 균일하게 다음과 같이 제한됨을 증명합니다: $$ \frac{\boldsymbol{k}}{N} + O\left(\frac{1}{\sqrt{N}}\right) $$ 따라서 선호 압축 기반 학습 알고리즘의 위험 추정치는 고정된 사건 확률의 경험적 추정치와 동일한 큰 수의 법칙 수렴 속도를 달성합니다. 또한 우리는 주요 항인 $\boldsymbol{k}/N$이 필수적임을 보이고, 이것과 경험적 위험(empirical risk) 간의 관계를 조사합니다. 특히, 경험적 위험이 $O(1/\sqrt{N})$ 수렴(convergence) 속도를 유지하는 체계뿐만 아니라, 복잡도 기반 추정기가 $O(1/\sqrt{N})$ 속도를 보존하는 반면 경험적 위험은 더 느리게 수렴하거나 일치성(consistency)을 잃는 체계를 규명합니다.
완전 이산 조건부 확산 모델에 대한 유한 표본 보장
Finite-Sample Guarantees for Fully Discrete Conditional Diffusion Models
본 연구에서는 데이터로부터 학습(training)되고 유한한 수의 노이즈 제거 단계를 통해 구현되는 조건부 확산 모델(conditional diffusion models)에 대한 유한 표본 보장(finite-sample guarantees)을 정립합니다. 제안하는 접근법은 스코어 학습 목적식을 샘플링 그리드와 일치시켜 통계적 추정 오차와 수치적 이산화 오차를 함께 분석할 수 있도록 합니다. 매끄러운 조건부 밀도 모델 하에서 생성된 분포의 오차에 대한 높은 확률의 한계(high-probability bounds)를 도출하고 필요한 스코어 평가 횟수를 정량화합니다. 모든 매끄러움 지수 $β>0$에 대해, 적절한 그리드는 조기 종료(early stopping) 여부와 관계없이 원래 타깃 대비 $\widetilde O_p(n^{-2β/(d_x+d_y+2β)})$의 평균 조건부 쿨백-라이블러(KL) 발산을 산출합니다. 전체 샘플러와 조기 종료 샘플러 모두 $\widetilde O_p(n^{-β/(d_x+d_y+2β)})$의 평균 타깃 총변동(TV) 오차를 달성합니다. 여기서 $n$은 표본 크기이고, $d_x, d_y$는 데이터 및 조건부 변수의 차원이며, 오차는 조건부 변수에 대해 평균화됩니다. 이 총변동 한계는 로그 인자를 제외하면 기존 조건부 분포 추정 이론에서 확립된 수렴율과 일치합니다.
비선형 작용소와 그 도함수의 보편 근사
Universal Approximation of Nonlinear Operators and Their Derivatives
본 논문에서는 작용소 학습(OL) 아키텍처를 통한 비선형 작용소 및 그 도함수의 보편 근사(UA)가 ${C^k_F}$(Fréchet) 콤팩트-오픈 위상 및 Fréchet-Sobolev 노름(즉, 작용소 노름 하에서)에서 성립하지 않음을 보인다. 우리는 보다 자연스러운 약한 위상인 $C^k_B$(Bastiani) 콤팩트-오픈 위상 및 일반적인 유한 입력 측도에 대한 (새로운) 가중 Bastiani-Sobolev 공간에서 UA를 복원함으로써 이러한 난점을 해결한다. 완전한 바나흐 공간(Banach space)의 일반성 하에서, 이는 [Hornik, 1991]의 영향력 있는 고전적 결과를 무한차원 공간 및 OL로 완전히 확장한 최초의 일반화이다. 우리는 자체적인 UAT에 기반하여 DIOL에서 Bastiani-Sobolev 학습(training)을 정식화한다. 이러한 결과는 일반 바나흐 공간에서 도함수 정보 기반 작용소 학습(DIOL)(즉, 비선형 작용소와 그 도함수 학습)의 시초를 연다. 비선형 작용소는 일반 바나흐 공간에서 사용 가능한 고전적 OL 아키텍처인 인코더-디코더 아키텍처를 통해 매개변수화되며, 여기에는 우리 UAT가 다루는 DeepONet, Deep-H-ONet, PCA-Net이 포함된다. 핵심적인 수학적 결과로서, 우리가 제안하는 새로운 가중 Bastiani-Sobolev 공간은 바나흐 공간상의 고전적 가우스(Malliavin) Sobolev 공간을 일반화한다. DIOL과 우리 UAT가 응용될 수 있는 미개척 분야로는 OL에서의 고차 정확도 달성, Learn-Then-Optimize를 통한 바나흐 공간에서의 빠른 제약 최적화(예: 편미분방정식(PDE)의 최적 제어, 역문제), 무한차원 PDE를 위한 수치적 기법(예: PDE, SPDE, 경로 의존 시스템, 부분 관측 시스템, 평균장 제어의 최적 제어 등 Optimize-Then-Learn을 통한 무한차원 최적 제어 기반 바나흐 공간상 HJB PDE) 등이 있다.
실수값 함수에 순서와 트리를 부호화하기
Encoding orders and trees in real-valued functions
우리는 이진 관계에 부호화된 충분히 큰 2-트리로부터 순서 속성(order property)을 추출하는 Hodges의 정량적 결과에 대한 함수론적 대응(analogue)을 증명한다. 함수에 대한 유사한 대응은 이전에 Daskalakis와 Golowich, 그리고 Anderson과 Benedikt에 의해 얻어졌다. 이러한 결과들은 통계적 학습 이론(statistical learning theory)에서 비롯되며, 여기서 2-트리는 순차 fat-shattering 차원(sequential fat-shattering dimension)으로 포착되고, 순서 속성은 다양한 "임계값(threshold)" 개념들에 의해 제어된다. 우리의 첫 번째 주요 결과(정리 1.11)는 트리로부터 덜 제한적인 종류의 임계값을 추출하는 데 초점을 맞추며, 더 제한적인 버전에 초점을 맞춘 이전 결과들로부터 얻을 수 있는 것보다 훨씬 더 나은 상계를 제공한다. 정리 1.11에 대한 동기의 일부는 동반 논문에 있으며, 그 논문에서 이 정리는 "안정 함수(stable functions)"에 대한 정량적 regularity lemma에서 효율적인 상계를 얻는 데 사용된다. 여기서는 정리 1.11을 사용하여 Anderson과 Benedikt의 결과를 더 강한 형태와 개선된 상계로 재증명한다. 또한 정리 1.11을 사용하여 dual sequential fat-shattering에 대한 최대 이중 지수 상계를 증명하며, 이는 미해결 문제를 해결한다. 두 번째 주요 결과(정리 1.14)에서는 큰 순차 fat-shattering 차원으로부터 "tight threshold"를 추출하는 Daskalakis와 Golowich의 결과에 대한 새로운 증명을 개선된 상계와 함께 제시한다. 이는 Jung, Kim, Tewari가 주장한 결과의 증명을 수정하는 것과 관련된 또 다른 미해결 문제를 해결한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.