arXiv:2003.03517

An Active Learning Framework for Constructing High-fidelity Mobility Maps

Gary R. Marple, David Gorsich, Paramsothy Jayakumar, Shravan Veerapaneni

제출 2020-03-07

원문 초록

A mobility map, which provides maximum achievable speed on a given terrain, is essential for path planning of autonomous ground vehicles in off-road settings. While physics-based simulations play a central role in creating next-generation, high-fidelity mobility maps, they are cumbersome and expensive. For instance, a typical simulation can take weeks to run on a supercomputer and each map requires thousands of such simulations. Recent work at the U.S. Army CCDC Ground Vehicle Systems Center has shown that trained machine learning classifiers can greatly improve the efficiency of this process. However, deciding which simulations to run in order to train the classifier efficiently is still an open problem. According to PAC learning theory, data that can be separated by a classifier is expected to require $\mathcal{O}(1/\epsilon)$ randomly selected points (simulations) to train the classifier with error less than $\epsilon$. In this paper, building on existing algorithms, we introduce an active learning paradigm that substantially reduces the number of simulations needed to train a machine learning classifier without sacrificing accuracy. Experimental results suggest that our sampling algorithm can train a neural network, with higher accuracy, using less than half the number of simulations when compared to random sampling.

함께 살펴볼 논문

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

arXiv:2609.27241v1stat.ML공통 태그 Active Learning, Learning Theory

멤버십 쿼리를 활용한 능동 학습의 샘플 복잡도에 관하여

On the Sample Complexity of Active Learning with Membership Queries

본 연구는 능동 학습(active learning)의 근본적인 질문, 즉 임의의 쿼리를 합성할 수 있는 능력이 얼마나 강력한가라는 문제를 다시 살펴본다. 학습자가 주어진 레이블 없는 풀(pool)에서만 쿼리를 선택하는 풀 기반 능동 학습과 비교할 때, 쿼리 능력에서의 이처럼 사소해 보이는 변화가 통계적 학습의 난이도를 극적으로 바꿀 수 있음을 발견하였다. 특히 풀 기반 설정에서는 본질적으로 학습이 느려 샘플 수에 대해 다항식 수준의 오차 감소만을 달성하는 일부 가설 클래스(hypothesis class)가, 합성된 쿼리가 허용되면 지수적으로 학습 가능해진다. 이러한 두드러진 격차는 멤버십 쿼리 합성(membership query synthesis)이 근본적으로 다른 학습 방식을 유도하며, 이는 기존 능동 학습 이론으로는 충분히 설명되지 않아 그 복잡도를 규명하기 위한 새로운 분석 도구가 필요함을 시사한다. 이러한 현상에 착안하여, 본 연구는 몇 가지 충분 조건을 개발하고 흥미로운 예시들을 제시하며, 어떤 가설 클래스가 합성된 쿼리를 통해 효율적인 학습을 허용하는지 이해하기 위한 추측적 관점을 제안한다.

arXiv:2607.10751v1cs.LG공통 태그 Learning Theory, PAC learning

라동 정리를 통한 부분 개념 클래스의 VC 차원

The VC dimension of partial concept classes via Radon's theorem

Alon, Hanneke, Holzman, Moran(FOCS 2021)을 따라, 우리는 부분 개념 클래스(PCC)를 부분 함수 $f: V\to\{0,1,\ast\}$의 집합족으로 정의한다. 이는 동등하게 각 개념이 기반 집합을 흑색($f^{-1}(1)$), 회색($f^{-1}(\ast)$), 백색($f^{-1}(0)$) 부분으로 분할하는 것을 의미한다. PCC의 VC 차원은 값 $\ast$가 취해지지 않는 집합들을 분쇄(shattering)함으로써 정의된다. 우리는 실수 바나흐 공간(Banach space)에서 마진 $\delta>0$을 가진 두 가지 기하학적 PCC를 연구한다: 확장된 반공간(expanded half-spaces)은 회색 부분이 반공간에 인접한 너비 최소 $\delta$인 띠이며, 확장된 공(expanded balls)은 회색 부분이 단위 반지름 공 주위의 너비 $\delta$인 환형(annulus)이다. 우리의 주요 결과는 $L_p(\mu)$, $1\le p<\infty$에서 확장된 공의 PCC에 대한 VC 차원의 차원 독립적 상한이며, 여기에는 비유클리드적이고 알고리즘적으로 특히 중요한 $\ell^d_1$ 경우가 포함된다. 이 상한들은 마진과 반지름에 의존하지만, 주변 차원이나 기저 측도 공간에는 의존하지 않는다. 이는 유클리드 공간, 즉 $\ell^d_2$에서 확장된 공의 PCC를 연구한 Bourneuf, Charbit, Thomassé(FOCS 2025)의 연구를 확장한 것이다. 또한 마진 매개변수 $\delta$ 측면에서 상한과 일치하는 VC 차원의 하한도 증명한다. 마지막으로, 기존 유클리드 결과를 확장하여 $L_p$ 공간에서 조밀 이웃 보조정리(Dense Neighborhood Lemma)를 유도한다. 우리의 방법은 비자명한 라데마허(Rademacher) 타입의 공간으로의 사상을 통한 거리의 선형화(linearization)와, 균형 잡힌 부호 합 추정 또는 무차원 라동 정리(no-dimensional Radon theorem)의 활용에 의존한다. 이 논증은 해당 분야 비전문가를 위해 명확하게 설명된 함수 해석학(functional analysis)의 아이디어에 기반한다.

arXiv:2604.04535v2cs.LG공통 태그 Active Learning, Learning Theory

동치 쿼리로부터의 학습, 재고찰

Learning from Equivalence Queries, Revisited

생성 모델과 추천 시스템 같은 현대 기계학습 시스템은 배포, 사용자 상호작용, 주기적 모델 업데이트의 순환을 통해 발전하는 경우가 많다. 이는 고정된 예측 과제 시퀀스에 대한 손실 또는 후회 최소화에 초점을 맞추는 표준 지도학습 프레임워크와 다르다. 이러한 설정에 착안하여, 우리는 Angluin(1988)이 도입한 동치 쿼리로부터의 학습이라는 고전적 모델을 재고찰한다. 이 모델에서 학습자는 반복적으로 가설을 제안하고, 배포된 가설이 부적절할 경우 반례를 받는다. 그러나 완전 적대적 반례 생성 하에서는 모델이 지나치게 비관적일 수 있다. 또한 대부분의 선행 연구는 학습자가 반례의 올바른 레이블도 관찰하는 완전 정보(full-information) 설정을 가정하는데, 이는 항상 자연스러운 가정이 아니다. 우리는 환경을 덜 적대적인 반례 생성기의 광범위한 부류로 제한함으로써 이러한 문제를 해결하며, 이를 대칭적(symmetric) 생성기라 부른다. 비형식적으로, 이러한 생성기는 가설과 타깃 사이의 대칭 차집합만을 기반으로 반례를 선택한다. 이 부류는 무작위 반례(Angluin and Dohrn, 2017; Bhatia, 2021; Chase, Freitag, and Reyzin, 2024)와 같은 자연스러운 메커니즘뿐 아니라, 주어진 복잡도 척도에 따라 가장 단순한 반례를 반환하는 생성기도 포괄한다. 이 프레임워크 내에서 완전 정보 피드백과 밴딧(bandit) 피드백 양쪽 설정 하에 동치 쿼리로부터의 학습을 연구한다. 두 설정 모두에서 학습 라운드 수에 대한 타이트한 경계를 도출하고, 향후 연구 방향을 제시한다. 우리의 분석은 대칭적 적대자에 대한 게임 이론적 관점과 적응적 가중치 기법, 그리고 미니맥스(minimax) 논증을 결합한다.

arXiv:2606.13576v1cs.LG공통 태그 Learning Theory, PAC learning

시뮬레이터를 활용한 학습: 계산적으로 제한된 세계에서의 후회 없음

Learning with Simulators: No Regret in a Computationally Bounded World

일반화에 필요한 최소한의 가정을 이해하는 것은 학습 이론의 근본적인 질문입니다. 불행히도 대부분의 결과는 데이터 생성 과정의 독립성(또는 그 대리 수단)에 크게 의존하는 반면, 강하게 의존적인 데이터에 대한 결과는 훨씬 제한적입니다. 이러한 격차를 해소하기 위해, 우리는 시뮬레이션 가능한 프로세스(simulatable processes)의 프레임워크를 도입합니다. 여기서 학습자는 데이터를 생성하는 분포(임의로 복잡하고 의존적인 프로세스일 수 있음)를 근사하는 시뮬레이터에 접근할 수 있습니다. 놀랍게도, 이러한 시뮬레이터에 대한 접근 권한이 주어지면 독립적인 데이터가 있는 고전적인 설정과 동일한 학습 보장, 즉 VC 차원(VC dimension)에 의존하는 오차 한계를 회복할 수 있음을 보여줍니다. 또한, 우리는 이 프레임워크를 사용하여 조건부 샘플링(conditional sampling)의 힘을 연구하고, 이 설정에서 엄격한 통계적 및 계산적 이점이 있음을 보여줍니다. 우리 프레임워크의 하이라이트로, 우리는 제한된 다항식 시간 내에 샘플링 가능한 모든 프로세스에서 주어진 VC 클래스를 동시에 학습하는 단일 알고리즘을 제시합니다. 이때 후회(regret)는 프로세스의 시간 제한 콜모고로프 복잡도에 의해 제어됩니다. 이는 고전적인 PAC 모델의 개념적 범위를 크게 확장하는 것입니다.

토론

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