Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds
원문 초록
Recent work of Klivans, Stavropoulos, and Vasilyan initiated the study of testable learning with distribution shift (TDS learning), where a learner is given labeled samples from training distribution $\mathcal{D}$, unlabeled samples from test distribution $\mathcal{D}'$, and the goal is to output a classifier with low error on $\mathcal{D}'$ whenever the training samples pass a corresponding test. Their model deviates from all prior work in that no assumptions are made on $\mathcal{D}'$. Instead, the test must accept (with high probability) when the marginals of the training and test distributions are equal. Here we focus on the fundamental case of intersections of halfspaces with respect to Gaussian training distributions and prove a variety of new upper bounds including a $2^{(k/\epsilon)^{O(1)}} \mathsf{poly}(d)$-time algorithm for TDS learning intersections of $k$ homogeneous halfspaces to accuracy $\epsilon$ (prior work achieved $d^{(k/\epsilon)^{O(1)}}$). We work under the mild assumption that the Gaussian training distribution contains at least an $\epsilon$ fraction of both positive and negative examples ($\epsilon$-balanced). We also prove the first set of SQ lower-bounds for any TDS learning problem and show (1) the $\epsilon$-balanced assumption is necessary for $\mathsf{poly}(d,1/\epsilon)$-time TDS learning for a single halfspace and (2) a $d^{\tilde{\Omega}(\log 1/\epsilon)}$ lower bound for the intersection of two general halfspaces, even with the $\epsilon$-balanced assumption. Our techniques significantly expand the toolkit for TDS learning. We use dimension reduction and coverings to give efficient algorithms for computing a localized version of discrepancy distance, a key metric from the domain adaptation literature.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
과제 조건 잠재 정렬을 통한 뇌-기계 인터페이스의 세션 간 안정적 신경 디코딩
Stable Neural Decoding Across Sessions via Task-Conditioned Latent Alignment for Brain-Machine Interfaces
침습적 뇌-기계 인터페이스(BMI)에서 안정적인 장기 신경 디코딩을 달성하는 것은 세션마다 기록된 신경 집단의 변동 때문에 여전히 어렵다. 현재의 잠재 정렬(latent alignment) 접근법은 세션 간 적응 과정에서 과제 의존적 구조를 간과할 수 있다. 우리는 공유 잠재 공간을 학습하여 신경 디코딩을 안정화하는 프레임워크인 과제 조건 잠재 정렬(TCLA, Task-Conditioned Latent Alignment)을 제안한다. TCLA는 신경 재구성(neural reconstruction)과 연속적 행동 감독(continuous behavioral supervision)을 이용해 저차원 source 표현을 학습한다. 대상 세션 적응 시 공유 표현은 고정되며, 각 과제 조건에 대해 source와 target 분포를 따로 정렬함으로써 대상 신경 활동을 source 잠재 공간에 매핑한다. 우리는 여러 과제를 아우르는 7개의 비인간 영장류 데이터셋에서 TCLA를 평가했다. 장기 세션 간 평가에서 TCLA는 평균 $R^2$ $0.476\pm0.014$를 달성했으며, 음의 $R^2$ 실패율은 6.8%에 불과했다. 피험자 내 1,356개 세션 쌍에서 TCLA는 평균 $R^2$ $0.371\pm0.009$와 6.8%의 실패율을 기록했다. 피험자 간 2,134개 세션 쌍에서 TCLA는 평균 $R^2$ $0.218\pm0.004$와 12.9%의 실패율을 달성해 비교 방법들보다 현저히 우수했다. 이 결과는 행동적으로 관련 있고 과제 의존적인 잠재 구조를 보존함으로써 TCLA가 기록 세션과 피험자에 걸친 신경 디코딩의 견고성을 향상시킴을 보여준다. 소스 코드는 \href{https://github.com/FAMD-CASIA/TCLA}{https://github.com/FAMD-CASIA/TCLA}에서 공개되어 있다.
KeySI: 인간 피드백 기반 텍스트 임베딩 튜닝을 위한 상호작용 프레임워크
KeySI: An Interaction Framework for Tuning Text Embeddings Based on Human Feedback
대규모 텍스트 분석 작업에서는 하류 분석을 위해 텍스트 코퍼스를 임베딩하는 데 사전학습된 언어 모델이 자주 사용된다. 그러나 이러한 모델은 도메인 특화 의미를 포착하는 데 어려움을 겪을 수 있으며, 이를 적응시키려면 일반적으로 대량의 라벨 데이터와 학습 파이프라인 구현에 필요한 기술적 전문성이 요구된다. 최근 접근법들은 문서 투영에서의 시각적 상호작용이 모델 튜닝을 위한 학습 신호로 인간 피드백을 포착할 수 있음을 보여주었다. 그러나 이러한 방법들은 문서 수준 피드백을 기반으로 동작하며, 효과적인 피드백을 제공하려면 사용자가 개별 문서를 열어 평가해야 한다. 본 논문에서는 키워드 기반 개념 명세를 통해 특징 수준 피드백을 가능하게 하는 상호작용 프레임워크 KeySI를 제안한다. 사용자는 추출된 키워드를 개념을 나타내는 그룹으로 구성하여 피드백을 지정하며, KeySI는 이를 후속 튜닝을 위한 문서 수준 지도 신호로 변환한다. 키워드를 주요 상호작용 매체로 사용함으로써 KeySI는 수동 문서 검토 및 라벨링의 필요성을 줄이고 임베딩 모델 적응의 진입 장벽을 낮춘다. 우리는 코퍼스가 주어졌을 때 대표 키워드를 선별하고, 차원 축소를 통해 키워드와 문서 임베딩을 시각화하며, 키워드 그룹의 대화형 명세를 허용하고, 시스템 피드백을 통한 반복적 정제를 지원하는 프로토타입 구현을 제시한다. 사용자 연구, 사용 시나리오, 정량 실험을 통해 KeySI를 평가하며, 사용자 의도 포착 및 임베딩 정렬 개선에서의 효과를 입증한다.
위에서 본 프롬프트 기반 개념 분할: 원격 탐사에서 SAM 3의 제로샷 텍스트 및 시각 프롬프팅 평가
Promptable Concept Segmentation from Above: Evaluating Zero-Shot Textual and Visual Prompting of SAM 3 in Remote Sensing
Segment Anything Model 3(SAM 3)와 같은 대규모 파운데이션 모델은 개방형 어휘와 무학습 컴퓨터 비전으로의 전환을 약속한다. 그러나 이러한 모델이 지구 관측 영상의 하향식 기하 구조라는 분포 외 영역으로 일반화하는 능력은 아직 거의 정량화되지 않았다. 우리는 미세 조정 없이 원격 탐사 장면 분류, 객체 탐지, 인스턴스 분할에 걸쳐 SAM 3를 다중 과제로 경험적으로 평가한다. 장면 분류에서는 분리된 이진 존재 헤드(binary presence head)를 독립적인 제로샷 분류기로 재활용한다. 탐지와 분할에서는 텍스트 프롬프트와 시각 프롬프트를 비교하며, 여기서 시각 프롬프트는 분할 대상 이미지 안에 있는 목표 클래스의 실제 인스턴스 하나를 제시한다. 텍스트만 사용하면 성능이 낮고, 시각 프롬프트를 추가하면 정확도가 크게 오르며, 둘을 결합하면 과제에 따라 정확도가 오르기도 하고 내리기도 한다. 또한 동일한 평가 프로토콜에서 SAM 3의 텍스트 전용 성능을 여러 일반 도메인 개방형 어휘 탐지 및 분할 모델과 비교한 결과, 두 벤치마크 모두에서 모든 모델을 앞선다. 그럼에도 시각 프롬프트가 없을 때의 정확도는 여전히 제한적이며, 이는 향후 연구 방향으로서 매개변수 효율적 미세 조정의 필요성을 시사한다.
scTrilemma: 단일 세포 표현 학습에서 정체성, 불변성, 충실도의 균형 잡기
scTrilemma: Balancing Identity, Invariance, and Fidelity in Single-Cell Representation Learning
단일 세포 RNA 시퀀싱(single-cell RNA-seq) 표현 학습은 근본적으로 레이블이 없습니다(label-free). 즉, 세포 정체성(cell identity), 상태(state), 맥락(context)이 고정된 학습(training) 목표가 아니므로, 무엇이 신호(signal)이고 방해 요인(nuisance)인지는 분석 목적에 따라 달라집니다. 따라서 단일 표현은 생물학적 정체성과 상태를 보존하고, 방해 요인이 되는 맥락에 강건해야 하며, 유전자 발현 분석에 필요한 유전자 수준의 변이를 유지해야 합니다. 본 연구에서는 이 세 가지 요구 사항을 '표현 트릴레마(representation trilemma)'라고 부릅니다. 이 문제를 해결하기 위해, 모든 발현 기반 변이를 하나의 임베딩(embedding)으로 강제 통과시키는 대신 임베딩, 디코더, 사전 분포(prior)로 라우팅하는 잠재 병목 VAE인 scTrilemma를 소개합니다. scTrilemma는 단일 재구성 목표 아래에서 대상 어노테이션이나 보조 표현 손실 없이, 발현량에 따라 유전자 토큰을 게이팅하고, 세포 표현을 디코더로 라우팅하며, 레이블이 지정되지 않은 유사 벌크(pseudo-bulk) 맥락에 따라 사전 분포를 조건화합니다. 연속적인 CZ CELLxGENE Census 릴리스에 대한 릴리스 기반 제로샷(zero-shot) 평가에서, scTrilemma는 세 가지 요구 사항을 동시에 모두 선도하며 여러 질병 환경 전반에 걸쳐 생물학적 상태, 차등 발현(differential-expression) 및 경로(pathway) 구조를 보존합니다. 잠재 변수 개입(latent intervention) 실험은 다른 요구 사항에 거의 영향을 주지 않고 맥락을 제거할 수 있음을 추가로 보여주며, 정체성과 충실도 간의 관계만이 상충 관계(tension)로 남음을 입증합니다. 코드는 https://github.com/yunhak0/scTrilemma 에서 공개적으로 이용 가능합니다.
타원형 마할라노비스 판별 분석을 위한 폐형식 분수 방사형 링크
Closed-form fractional radial links for elliptical Mahalanobis discriminant analysis
우리는 두 클래스가 공유된 반경 생성자 $g$를 갖는 타원형 분포일 때의 이진 분류를 연구한다. 이때 로그 우도비는 두 제곱 마할라노비스 반경의 가법 함수이며, 반경 링크는 $\varphi=\log g$이다. 가우시안 클래스에서는 $\varphi$가 아핀이며 규칙은 이차 판별분석(QDA)으로 환원되고, 그렇지 않으면 베이즈 링크는 항등이 아니다. 이 링크를 스플라인 평활기로 적합하는 대신, 우리는 반경의 클래스 내 분포로부터 그 족을 유도하고 유한 분수 거듭제곱 사영을 추정한다. 반경 분포로부터 링크가 식별 가능하며, 플러그인 추정량이 유한 적률 조건에서 $\sqrt{n}$-일치성과 점근 정규성을 가지고, 유도된 분류기가 반복된 시브(sieve) 극한에서 점근적으로 베이즈 최적임을 증명한다. $d\ge2$이고 비중첩 클래스 모수인 경우, 항등 링크는 아핀(가우시안) 생성자에서만 충분하다. 이 브리지, GAM 소속, 그리고 이 이분법의 아핀 방향은 Lean 4에서 검증되었다. 우리는 Ghosh et al. (2025)의 전역 마할라노비스-GAM을 동일한 입력 예산으로 mgcv REML 스플라인을 사용해 재구현하여 비교한다. 두 UCI 벤치마크에서 유도된 링크는 적합된 GAM과 대등하다. 세 자산군의 금융 시계열 여섯 개에서, 시간 의존성을 존중하는 검증을 사용하면 적합된 GAM보다 유의하게 나쁜 경우가 없으며, CAD/USD에서는 더 낫고 나머지 다섯 개에서는 대등하다. 꼬리가 가장 두꺼운 세 시계열(원유 $[+0.023,+0.069]$, S&P 500 $[+0.039,+0.125]$, JPY/USD $[+0.009,+0.047]$)에서는 QDA를 능가하고 나머지에서는 대등하다. 닫힌 형태의 기준값을 갖는 속도 시뮬레이션은 $\sqrt{n}$ 속도를 재현하며, 공분산 이질성 하에서 QDA의 위험 하한과 유도된 링크의 소멸하는 초과 위험을 대비하여 보여 준다. 따라서 유도된 링크는 평활 모수 선택 없이도 조정된 GAM에 필적하며, 생성자가 가우시안에서 벗어나는 경우 QDA를 개선한다.
인공 신경망에서 표현 학습을 통한 창발적 일반화
Emergent Generalization by Representation Learning in Artificial Neural Networks
차원 축소는 고차원 신경 활동의 기저에 있는 저차원 구조인 신경 다양체를 식별하는 데 강력한 것으로 입증되었다. 이러한 저차원 표현은 집단 수준 부호화의 해석 가능성을 높여 왔다. 그러나 이러한 저차원 표현이 생물학적으로 의미가 있고 학습 시스템에서 기능적 이점을 제공하는지, 아니면 단지 뉴런 수준의 활동을 반영할 뿐인지는 신경과학에서 여전히 논쟁 중이다. 우리는 순환 신경망이 저차원 표현을 학습하도록 강제하는 명시적 정보 병목이 시계열 예측 과제에서 회전 일반화와 분포 외 일반화에 필수적임을 보인다. 인과적 창발에 대한 정보 이론적 측정치를 사용하여 암기에서 일반화로의 전이 전반에 걸친 이 표현의 동역학을 규명한 결과, 예측 손실이 단조롭게 감소하는 동안에도 초기 감소, 최소값, 이후 최대값까지의 상승을 보이는 비단조적 궤적을 발견했다. 이 궤적은 과제 복잡도에 따라 변하며, 창발적 구조의 크기는 일반화 성능을 신뢰할 수 있게 예측한다. 교대 미로 과제를 학습하는 쥐의 해마 CA1과 내측 전전두엽 활동을 분석하면 행동 수행을 따라가는 유사한 비단조적 창발 동역학이 나타난다. 이러한 결과는 종합하면 신경망이 간결하고 분산되며 창발적인 표현을 학습하는 능력이 일반화에 기능적 이점을 제공함을 시사하며, 인지에서 학습된 표현이 인과적 역할을 한다는 주장을 뒷받침한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.