부호 랭크, 지수, 리스트 재현성: 연결과 분리
Sign-Rank, Index, and List Replicability: Connections and Separations
한국어 초록
학습 이론에서 이진 개념 클래스(concept class)의 부호 랭크(sign rank)는 점과 반공간(halfspace)으로 표현할 수 있는 최소 차원을 포착한다. 엄청난 관심에도 불구하고 부호 랭크에 대한 하한(lower bound)을 구하는 것은 악명 높게 어렵다. 이 문제에 대한 두 가지 최근 접근법은 분석하기 더 쉬운 측도를 통해 부호 랭크의 하한을 확립한다: $\mathbb{Z}_2$-지수($\mathbb{Z}_2$-index)와 리스트 재현성 수(list replicability number)이다. 우리는 이 측도들의 순서를 밝히며, $\mathbb{Z}_2$-지수가 리스트 재현성 수의 선형 함수에 의해 상한(upper bound)된다는 것을 보인다. 주요 결과로서, 부호 랭크와 $\mathbb{Z}_2$-지수 사이의 강한 분리(separation)를 얻어 Frick, Hosseini, Vasileuski의 질문을 해결한다. 이는 두 하한 측도 중 더 강한 측도인 리스트 재현성에 대한 철저한 연구를 동기화한다. 우리는 높이(height)와 최소 스타 수(minimum star number)라는 두 가지 조합론적 측도에 의해 리스트 재현성 수의 상한을 확립한다. 또한 근본적인 합성(composition) 결과를 증명하여, 두 개념 클래스의 곱(product)의 리스트 재현성 수가 두 클래스 각각의 리스트 재현성 수의 합에 의해 상한된다는 것을 보인다.
원문 초록
In learning theory, the sign rank of a binary concept class captures the smallest dimension in which it can be represented by points and halfspaces. Despite tremendous interest, lower bounds on sign rank are notoriously difficult to come by. Two recent approaches to the problem establish lower bounds on sign rank by measures that are easier to analyze: the $\mathbb{Z}_2$-index and the list replicability number. We order these measures, showing that the $\mathbb{Z}_2$-index is upper-bounded by a linear function of the list replicability number. As a main consequence, we obtain a strong separation between sign rank and $\mathbb{Z}_2$-index, thereby resolving a question of Frick, Hosseini, and Vasileuski. This motivates a thorough study of list replicability, the stronger of the two lower-bounding measures. We establish upper bounds on the list replicability number by two combinatorial measures: height and minimum star number. We also prove a fundamental composition result, showing that the product of two concept classes has list replicability number bounded by the sum of the list replicability numbers of the two classes.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.18236v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Proxy OPD: 전이 가능한 상대적 프록시 업데이트를 이용한 대규모 언어 모델의 온-폴리시 증류
Proxy OPD: On-Policy Distillation with Transferable Relative Proxy Update for Large Language Models
보상 기반 강화학습(RL)은 대규모 언어 모델을 개선하지만, 여러 대상 모델에 대해 반복하면 상당한 비용이 발생한다. 온-폴리시 증류(OPD)는 대상 모델이 생성한 궤적에서 전문가 모델의 분포를 맞추도록 하여 전문가를 재사용하지만, 기반 정책이 서로 다르면 보상으로 유도된 업데이트가 기존의 정책 차이와 뒤섞여 전이되는 업데이트 방향이 왜곡될 수 있다. 우리는 대상 모델의 동결된 기반 정책을 기준으로 삼아 보상으로 유도된 상대적 정책 업데이트를 전이하는 사후 학습 방법인 Proxy OPD(P-OPD)를 제안한다. 프록시는 보상에 따른 탐색을 거치며, 초기 정책과 최적화된 정책 사이의 토큰 수준 로그 확률 변화를 산출한다. 이 신호는 대상 모델이 생성한 궤적에서의 학습을 안내하며, 보정(calibration)이 신호 흡수 정도를 조절함으로써 보상으로 유도된 개선을 여러 대상 모델에 걸쳐 재사용할 수 있게 한다. 수학적 추론, 코드 생성, 지시 따르기에서 Qwen3 계열 대상 모델을 이용한 실험 결과, P-OPD는 대상 모델을 개선하고 대부분의 설정에서 기존 OPD보다 우수한 성능을 보였다. 1.7B에서 8B로의 전이에서 평균 Math Mean@16 및 Code Mean@8 점수는 OPD보다 각각 8.3점과 3.4점 높았다. 메커니즘 분석은 보상으로 유도된 감독 신호가 더 충실하며 적응을 제어할 수 있음을 보여 준다. 규모 간 및 세대 간 실험은 신호의 전이 가능성과 재사용 가능성을 확인해 주며, 다중 도메인 증류는 상승 효과와 도메인 간 간섭을 함께 드러낸다. 측정된 4B에서 8B 설정에서 프록시 탐색 이후 대상 모델의 적응에는 대상 모델 RL을 직접 수행하는 시간의 약 15\%가 소요되며, 신호를 반복 재사용하면 호환되는 모델 전반에서 일회성 탐색 비용이 상각된다. 이러한 결과는 상대적 정책 업데이트가 "한 번 탐색하고 여러 번 전이한다"는 사후 학습 패러다임을 위한 효과적이고 전이 가능하며 조합 가능한 감독 신호임을 뒷받침한다.
LISA: 효율적 긴 컨텍스트 추론을 위한 Linear-Indexed Sparse Attention
LISA: Linear-Indexed Sparse Attention for Efficient Long-Context Reasoning
DeepSeek-R1과 같은 긴 사고 사슬(CoT) 추론 모델은 테스트 시점 스케일링 하에서 추론 사슬을 계속 늘리고 있으나, 표준 셀프 어텐션은 문맥 길이에 대해 이차 비용이 들어 긴 CoT의 실서비스 배포를 고비용으로 만든다. 이에 본 논문은 전체 사전학습이 필요 없는 셀프 어텐션의 플러그 앤 플레이 대체 방식인 LISA(Linear-Indexed Sparse Attention)를 제안한다. LISA는 장거리 메모리를 위한 선형 어텐션 분기와, 희소 셀프 어텐션 분기를 위해 가장 관련성 높은 토큰을 동적으로 선택하는 Lightning Indexer를 결합한다. 두 분기는 학습된 게이트를 통해 융합되어, 모델이 폭넓은 문맥을 유지하면서 연산을 정보량이 많은 토큰에 집중시킨다. LISA는 두 단계로 학습한다. 1단계에서는 선형 어텐션 분기를 슬라이딩 윈도 어텐션과 통합하고, 고정된 교사 모델의 전체 어텐션 분포로부터 증류한다. 2단계에서는 Lightning Indexer가 정적 윈도를 대체하며, 교사의 어텐션 패턴을 모방하도록 헤드별 KL 발산 목적함수로 학습된다. 그 결과 모델은 eager 모드 셀프 어텐션 연산을 시퀀스 길이에 대한 이차에서, 생성된 토큰 수와 선택된 문맥 예산에 대한 선형으로 줄인다. DeepSeek 증류 Qwen 모델에 대한 실험에서 LISA는 긴 문맥 추론 품질을 저하시키지 않으면서 16K 문맥에서 측정된 eager 모드 평균 샘플 지연 시간을 23.9% 줄인다. 9개의 수학 및 코드 추론 벤치마크 전반에서 게이트 방식 LISA-1.5B 모델은 전체 어텐션 기준 모델 대비 동일 가중 벤치마크 평균을 4.2%p 향상시킨다.
토큰이 아닌 턴 주입하기: 자기 수정을 위해 LLM 추론을 리디렉션할 위치 학습
Inject a Turn, Not a Token: Learning Where to Redirect LLM Reasoning for Self-Correction
대규모 언어 모델(LLM)은 자신의 추론 과정에서 발생한 오류를 안정적으로 식별하고 수정하는 데 어려움을 겪는다. 수정이나 피드백을 생성하도록 LLM을 미세조정하는 기존의 학습 기반 접근법과 달리, 우리는 실패한 롤아웃에서 어디에 개입할지를 학습하고 이를 어떻게 리디렉션할지를 결정한다. 개입 위치를 선택하기 위해, 우리는 최종 답안의 정답 여부만을 이용해 고정된 인코더 위에 130K개의 매개변수를 가진 MLP 헤드를 학습시킨다. 리디렉션의 경우, 고정된 생성 예산 하에서 테스트한 인라인 주입(inline injection)은 추론을 안정적으로 리디렉션하지 못하는 반면, 동일한 지시문을 새로운 사용자 턴(user turn)으로 제시하면 모델의 진행 방향이 바뀐다는 것을 발견했다. 그 결과로 만들어진 수정 프레임워크인 UPTURN(User-Prompt TURN injection at a learned position)은 LLM의 미세조정을 전혀 요구하지 않는다: 선택된 접두 문맥(prefix)을 유지하고, 지시문을 새로운 사용자 턴으로 주입한 뒤, 나머지 부분을 재생성한다. 네 가지 추론 모델과 여섯 가지 수학 벤치마크 전반에서, UPTURN은 32회 롤아웃 기준선(baseline) 대비 모든 설정에서 평균 정확도를 향상시킨다. 동일한 수정 예산 하에서 자기 수정(self-correction) 및 리플렉션 토큰(reflection-token) 주입 기준선을 능가하며, 재학습 없이도 다른 추론 모델과 GPQA-Diamond로 전이되고, GRPO 및 자기 수정 기법과도 상호보완적이다.
데이터셋 이동 하에서 갑상선 결절 초음파 분류를 위한 딥 앙상블 기반 보정된 선택적 예측
Calibrated selective prediction using deep ensembles for thyroid nodule ultrasound classification under dataset shift
배경: 딥러닝은 초음파에서 갑상선 결절을 분류할 수 있으나, 판별 성능만으로는 임상적 신뢰성이 확립되지 않는다. 우리는 불확실성 인지 선택적 예측과 보수적인 영상 기반 선별을 갖춘 보정된 딥 앙상블 프레임워크를 개발하였다. 방법: 3겹 내부 아키텍처 선택을 포함한 중첩 5겹 교차 검증으로 squeeze-and-excitation 블록을 갖춘 ConvNeXt-Tiny를 선택하였고, 이를 이용해 결정론적 5개 구성원 앙상블을 구축하였다. 각 폴드 내에서 학습, 조기 종료, 보정, 임계값 부분집합을 분리하였으며, 외부 테스트 데이터는 격리된 상태로 유지하였다. 상호 정보량(MI), 예측 분산, 최대 소프트맥스 확률(MSP) 불확실성을 위험-커버리지 및 선별 분석과, 가정한 악성 유병률 5%-70%에 걸친 예측값으로 비교하였다. 고정된 TN5000 앙상블을 재보정 없이 TN3K에 적용하였다. 결과: TN5000에서 풀링된 out-of-fold AUC-ROC는 0.9377, 평균 정밀도는 0.9708, 기대 보정 오차는 0.0138, Brier 점수는 0.0827이었다. MI 기반 주 정책에서 영상의 8.86%가 No-FNA 제안을, 60.00%가 FNA 권고를, 31.14%가 영상의학과 의사 검토를 받았으며, 악성 영상 3574건 중 14건(0.39%)이 No-FNA, 708건(19.81%)이 검토를 받았다. 예측 분산과 MSP가 MI보다 오류를 더 잘 순위화하였고(AURC, AUGRC), 모든 선별 결과를 최적화한 척도는 없었다. 유병률 5%-70% 전반에서 NPV는 99.95%-97.93%, PPV는 29.28%-94.75%였다. TN3K에서 AUC-ROC는 0.7870, 평균 정밀도는 0.7254, 기대 보정 오차는 0.1899, 영상의학과 의사 검토율은 83.7%였다. 결론: 앙상블은 내부적으로 강한 판별 및 보정 성능을 보였으나 TN3K에서는 성능이 크게 저하되어, 데이터셋 이동 하에서 이식성이 제한적임을 나타냈다. 임상 사용 전에 다기관 검증, 기관별 재보정, 임계값 검증, 전향적 평가가 필요하다.
PulseGuard: 토킹페이스 딥페이크 탐지를 위한 포렌식 모달리티로서의 rPPG 기반 시간 신호
PulseGuard: rPPG-Derived Temporal Signals as a Forensic Modality for Talking-Face Deepfake Detection
토킹페이스(TF) 딥페이크 생성은 정지된 원본 이미지와 음성 신호로부터 사실적인 얼굴 영상을 합성하며, 현재의 이미지 기반 탐지기가 일관되게 식별하지 못하는 위조물을 만들어 낸다. 얼굴 교체 조작과 달리 TF 합성에는 생리적 특성을 물려받을 기반 실제 영상이 없으므로, 이 위조 범주의 탐지 모달리티로 원격 광혈류측정(rPPG)이 동기화된다. 우리는 RhythmFormer로 윈도우별 rPPG 파형을 추출하고 경량 분류기 모음을 학습시켜 실제 신호와 합성 신호를 구분하는 탐지 프레임워크 PulseGuard를 제안한다. 테스트 신원이 학습 신원과 완전히 분리된 엄격한 피험자 독립 프로토콜로 Celeb-DF++의 TF 부분집합에서 평가한 결과, 우리의 1D ResNet은 추출된 시간 신호만으로 동작하면서 EER 25.1%에서 윈도우 수준 AUC 0.826(DeepFakesON-Phys가 평가되는 단위인 영상 수준으로 풀링 시 0.842)을 달성하며, 학습에서 완전히 제외된 생성기에 대해서도 AUC 0.754를 유지한다. 우리는 대표적인 기존 rPPG 탐지기인 DeepFakesON-Phys의 통제된 재현 연구를 제시하여, 기존 얼굴 교체 데이터에서의 AUC 0.999가 Celeb-DF++의 TF 부분집합에서는 0.576으로 저하됨을 보인다. 또한 탐지 난이도가 방법에 크게 의존함을 보이는데, 일곱 개의 TF 생성기에 걸쳐 AUC는 0.937(Real3DPortrait)에서 0.617(IP-LAP)까지 분포하며, 이 순서는 방법별 학습에서도 대체로 유지된다. 이 편차는 평가 잡음이 아니라 학습 방식 전반에 걸쳐 안정적이며, 본 연구의 주된 실증적 기여이다. 우리는 이를 실증적 기준선으로 보고하며, 판별 근거가 심장 기원임을 입증하지는 않는다.
AI 지원 수학적 발견을 위한 연속 그래프 메모리와 커뮤니티 인프라
Continual Graph Memory and Community Infrastructure for AI-Assisted Mathematical Discovery
수학적 발견에는 부분적인 아이디어와 그 재사용을 뒷받침하는 증거를 보존하는 것이 필요하다. 본 논문은 모델이 수용한 주장과 의존 관계를 선별된 탐색과 분리하는 연속 그래프 메모리를 갖춘 연구 하니스인 Ansatz와, 이러한 작업을 검사하고 안내하며 점검하기 위한 커뮤니티 플랫폼인 Ansatze를 제시한다. First Proof에서 Ansatz는 10문제씩 두 배치 각각에서 국소 검증기 종결 9건을 기록했으며, Second Batch의 부분 결과 하나도 연구의 기준에 따라 통과로 계산되었다. 이러한 모델 평가 결과에는 지속된 탐색이 포함되어 있으며 전문가 검증과는 다르다. 구성 요소 연구와 재검토는 불일치와 그 의존 관계의 파급 범위를 드러낸다. 미해결 문제 탐구에서는 후보 결과가 도출되었으며, 다섯 건의 Lean 형식화가 보고되었다. 이 플랫폼은 문제 발견, 연구 기록, 원고 분석, 형식 검증을 연결하면서 서로 구별되는 증거 상태를 보존한다. 이러한 시스템들은 지속적인 탐구와 검사 가능한 기여를 통해 인간-AI의 누적적 연구를 뒷받침한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.