Is Out-of-Distribution Detection Learnable?
원문 초록
Supervised learning aims to train a classifier under the assumption that training and test data are from the same distribution. To ease the above assumption, researchers have studied a more realistic setting: out-of-distribution (OOD) detection, where test data may come from classes that are unknown during training (i.e., OOD data). Due to the unavailability and diversity of OOD data, good generalization ability is crucial for effective OOD detection algorithms. To study the generalization of OOD detection, in this paper, we investigate the probably approximately correct (PAC) learning theory of OOD detection, which is proposed by researchers as an open problem. First, we find a necessary condition for the learnability of OOD detection. Then, using this condition, we prove several impossibility theorems for the learnability of OOD detection under some scenarios. Although the impossibility theorems are frustrating, we find that some conditions of these impossibility theorems may not hold in some practical scenarios. Based on this observation, we next give several necessary and sufficient conditions to characterize the learnability of OOD detection in some practical scenarios. Lastly, we also offer theoretical supports for several representative OOD detection works based on our OOD theory.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
라동 정리를 통한 부분 개념 클래스의 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)의 아이디어에 기반한다.
시뮬레이터를 활용한 학습: 계산적으로 제한된 세계에서의 후회 없음
Learning with Simulators: No Regret in a Computationally Bounded World
일반화에 필요한 최소한의 가정을 이해하는 것은 학습 이론의 근본적인 질문입니다. 불행히도 대부분의 결과는 데이터 생성 과정의 독립성(또는 그 대리 수단)에 크게 의존하는 반면, 강하게 의존적인 데이터에 대한 결과는 훨씬 제한적입니다. 이러한 격차를 해소하기 위해, 우리는 시뮬레이션 가능한 프로세스(simulatable processes)의 프레임워크를 도입합니다. 여기서 학습자는 데이터를 생성하는 분포(임의로 복잡하고 의존적인 프로세스일 수 있음)를 근사하는 시뮬레이터에 접근할 수 있습니다. 놀랍게도, 이러한 시뮬레이터에 대한 접근 권한이 주어지면 독립적인 데이터가 있는 고전적인 설정과 동일한 학습 보장, 즉 VC 차원(VC dimension)에 의존하는 오차 한계를 회복할 수 있음을 보여줍니다. 또한, 우리는 이 프레임워크를 사용하여 조건부 샘플링(conditional sampling)의 힘을 연구하고, 이 설정에서 엄격한 통계적 및 계산적 이점이 있음을 보여줍니다. 우리 프레임워크의 하이라이트로, 우리는 제한된 다항식 시간 내에 샘플링 가능한 모든 프로세스에서 주어진 VC 클래스를 동시에 학습하는 단일 알고리즘을 제시합니다. 이때 후회(regret)는 프로세스의 시간 제한 콜모고로프 복잡도에 의해 제어됩니다. 이는 고전적인 PAC 모델의 개념적 범위를 크게 확장하는 것입니다.
SAMark: 단락 수준 패러프레이즈 견고성을 갖춘 자기 고정(self-anchored) 텍스트 워터마킹
SAMark: A Self-Anchored Text Watermarking with Paragraph-Level Paraphrase Robustness
의미 수준 워터마킹(SWM)은 문장을 기본 단위로 취급하여 텍스트 수정에 대한 견고성을 향상시킨다. 그러나 단락 수준 패러프레이즈(paraphrasing)에 대한 견고성은 여전히 어려운 문제로 남아 있다. 이러한 공격은 문장 순서를 변경함으로써 워터마크 신호를 전역적으로 교란하기 때문이다. 본 연구에서는 SAMark를 제안한다. 이는 의미 공간(semantic space)에 단계 독립적(step-independent) green region을 설정함으로써 문장 순서에 대한 의존성을 제거하는 자기 고정(self-anchored) 워터마킹 프레임워크이다. 탐지성(detectability)을 향상시키기 위해, 워터마크 신호를 증폭하면서 약하게 정렬(aligned)된 후보에서 발생하는 노이즈를 억제하는 다채널 쌍곡(hyperbolic) 스코어링 메커니즘을 도입한다. 또한 단순 n-gram 반복 필터를 넘어 의미적 중복(semantic redundancy)을 다루기 위해 hard filtering과 soft 정규화(regularization)를 결합한 다양성 인식(diversity-aware) 필터링 전략을 제안한다. 실험 결과, SAMark는 일반적인 단락 수준 패러프레이즈 공격 하에서 최대 90.2% TP@FP1%를 달성하며, 평균적으로 가장 강력한 선행 기준선(baseline)보다 30% 이상 우수한 성능을 보인다. 동시에 워터마크가 없는 텍스트와 경쟁할 만한 생성 품질을 유지하며, 기존 방법을 제한하던 견고성-품질 트레이드오프(robustness-quality trade-off)를 깬다. 코드는 https://github.com/Z1zs/SAMark 에서 공개될 예정이다.
3인칭 감사를 넘어서: 사용자 중심 LLM 바이어스 연구를 위한 상황화된 상호작용 감사
Beyond Third-Person Audits: Situated Interaction Auditing for User-Centered LLM Bias Research
대규모 언어 모델(LLM)의 편향 연구는 모델이 인구 집단을 외부 대상으로서 어떻게 표상하거나 평가하는지를 연구하는 3인칭 감사에 주로 초점을 맞추어 왔다. 그러나 이 패러다임은 감사에 사용자가 부재하다는 구조적 사각지대를 간과한다. 실제로 LLM은 개방적이고 개인적인 상호작용에서 사용되며, 이때 모델은 사용자를 암묵적으로 표상하고 그에 맞춰 응답을 조정한다. 동일한 요청이 누가 묻느냐에 따라 다른 응답을 낳는다면, 편향은 모델이 타인을 서술하는 방식이 아니라 대화 상대를 대하는 방식에서 나타난다. 1인칭 편향에 대한 실증 연구가 늘고 있으나, 서로 다른 단서, 결과 지표, 타당화 방식을 사용하여 결과를 비교하기 어렵다. 본 논문은 이러한 문헌을 위한 공통 진단 프레임워크인 상황 기반 상호작용 감사(SIA)를 제안한다. SIA는 이름과 표면적 표지, 글쓰기 스타일과 방언, 명시된 정체성이라는 사용자 프로필 신호의 유형론을 설계 원칙 및 결과 지표와 함께 도입하여 연구를 비교하고 누적할 수 있게 한다. 우리는 이 프레임워크를 아홉 개 과업 영역과 세 가지 모델에 걸친 칠레인의 이름과 성에 대한 사례 연구로 구현하고, 실무자를 위한 지침과 연구자를 위한 미해결 질문으로 마무리한다.
LLM 추론을 위한 힌트 유도 다양화 정책 최적화
Hint-Guided Diversified Policy Optimization for LLM Reasoning
최근 대규모 언어 모델(LLM)의 발전은 인상적인 추론 능력을 보여주었으며, 검증 가능한 보상을 활용한 강화학습(RLVR)은 유망한 성능 향상 전략으로 주목받고 있다. 그러나 기존 보상 메커니즘은 결과 수준의 정확성에 국한되어 있어, 모델이 다양한 해법을 고려하도록 유도하는 명시적인 신호가 부족하다. 대조적으로, 인간의 문제 해결은 일반적으로 여러 잠재적 접근법을 평가하고 가장 신뢰할 수 있는 해법을 선택하는 과정을 거치지만, 현재의 RLVR 프레임워크는 이러한 인지 과정을 명시적으로 유도하지 않는다. 이에 영감을 받아, 본 연구에서는 모델이 먼저 모든 잠재적 후보 해법의 개요를 힌트로 나열한 다음 추가 추론을 위해 가장 신뢰할 수 있는 해법을 선택하도록 하는 힌트 유도 다양화 정책 최적화(HDPO)를 제안한다. HDPO는 구조화된 추론을 위한 콜드 스타트(Cold Start for Structured Reasoning)와 힌트 유도 다양화 강화학습(Hint-Guided Diversified Reinforcement Learning)의 두 단계로 구성되어, 모델이 '제안-선택-사고(propose-select-think)' 궤적을 따라 다양하고 신뢰할 수 있는 해법을 생성하도록 장려한다. 실험 결과는 HDPO가 LLM의 추론 성능을 효과적으로 향상시키고, 후보 해법의 다양성뿐만 아니라 신뢰할 수 있는 해법을 식별하는 LLM의 능력 또한 향상시킴을 보여준다.
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) 방식입니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.