arXiv:2606.11235v1 cs.LG

확장 가능하고 통계적으로 건전한 데이터 마이닝을 위한 퓨샷 리샘플링

Few-Shot Resampling for Scalable Statistically-Sound Data Mining

Leonardo Pellegrina, Fabio Vandin

제출 2026-05-29

한국어 초록

지식 발견의 핵심 단계는 데이터 마이닝 결과의 평가이다. 패턴 마이닝, 그래프 분석 등 여러 응용 분야에서 이 단계는 데이터의 노이즈나 무작위 변동으로 인한 허위 발견을 방지하기 위해 결과의 통계적 유의성 평가를 포함한다. 일부 특정 응용 분야에는 전용 절차가 개발되어 있지만, 리샘플링 기반 접근법은 분석적 결과를 도출할 수 없는 복잡한 분석에서 특히 널리 사용된다. 그러나 현재의 리샘플링 기반 접근법은 수천 개의 리샘플링된 데이터셋을 생성하고 분석해야 하므로, 대규모 데이터셋이나 계산 집약적인 분석에서는 비현실적이다. 본 논문에서는 허위 발견 확률에 대한 엄격한 보장과 함께 데이터 마이닝 결과의 통계적 유의성을 평가하는 단순하고 효과적인 리샘플링 기반 접근법인 FewRS를 소개한다. 우리의 접근법은 리샘플링 기반 접근법이 적용되는 모든 상황에서 사용 가능하다. FewRS는 데이터 마이닝 결과의 품질을 나타내는 검정 통계량의 상한 편차(supremum deviation)에 대한 새로운 경계 유도에 기반한다. 우리는 FewRS가 극히 적은 수의 리샘플링된 데이터셋만 생성하고 분석하면 됨을 증명하며, 이는 광범위한 적용 가능성을 갖춘 고도로 확장 가능한 접근법으로 이어진다. 우리는 패턴 마이닝과 네트워크 분석 같은 일반적인 태스크에서 접근법을 테스트한다. 모든 경우에서 우리의 접근법은 높은 통계적 검정력을 유지하면서 최신 기술 대비 최대 두 자릿수의 실행 시간 단축을 달성하며, 대규모 실세계 데이터셋에서 데이터 마이닝 결과의 통계적 검증을 가능하게 한다.

원문 초록

A key step in knowledge discovery is the evaluation of data mining results. In several applications, including pattern mining, graph analysis, and others, this step includes the evaluation of the statistical significance of the results, to avoid spurious discoveries due only to noise or random fluctuations in the data. While specialized procedures have been developed for some specific applications, resampling-based approaches are widely used, in particular for complex analyses where analytical results cannot be derived. However, current resampling-based approaches require the generation and analysis of thousands of resampled datasets, and are therefore impractical for large datasets or computationally intensive analyses. In this paper, we introduce FewRS, a simple and effective resampling-based approach to assess the statistical significance of data mining results with rigorous guarantees on the probability of false discoveries. Our approach can be used in every situation where resampling-based approaches are applied. FewRS builds on our derivation of a novel bound to the supremum deviation of test statistics representing the quality of data mining results. We prove that FewRS needs to generate and analyze an extremely small number of resampled datasets, leading to a highly scalable approach with wide applicability. We test our approach on common tasks such as pattern mining and network analysis. In all cases, our approach results in a reduction of up to two orders of magnitude in running time compared to the state of the art, while preserving high statistical power, enabling the statistical validation of data mining results on large-scale real-world datasets.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2606.11235v1제출 시각 미확인

함께 살펴볼 논문

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

arXiv:2609.27633v2cs.LG공통 태그 Computational Efficiency, Graph Learning

Pheno-GS: Phenoscape 규모의 지오데식 싱크혼

Pheno-GS: Phenoscape-scale Geodesic Sinkhorn

고처리량 단일 세포 데이터는 이제 대규모 환자 코호트 전반에 걸쳐 수집되고 있다. 세포 수준 데이터로부터 환자 수준의 이질성을 이해하려는 동기에서 phenoscaping이 등장했는데, 이는 각 단일 세포 분포를 하나의 "데이터 포인트"로 임베딩(embedding)하고 그 사이의 거리를 최적 수송(optimal transport, OT)으로 정의하는 방식이다. 모든 환자 데이터셋 쌍 사이에서 이러한 규모로 기하 구조를 반영하는 OT를 계산하는 것은 여전히 해결되지 않은 과제로 남아 있다. 기존 방법은 매니폴드 구조를 왜곡하는 유클리드 그라운드 메트릭에 의존하거나, 희소하거나 불균등하게 샘플링된 데이터 또는 대규모 데이터에서 제대로 작동하지 않기 때문이다. 본 논문에서는 노이즈가 있고 불균형(unbalanced)하며 대규모인 환경에서도 정확하고 확장 가능한 지오데식 수송 거리를 계산하는 \textbf{Pheno-GS}(Phenoscape-scale Geodesic Sinkhorn)를 제안한다. Pheno-GS는 세 가지 구성 요소로 이루어진다. ($1$) 희소하거나 연결이 끊어진 매니폴드에서도 지오데식이 잘 정의되도록 하는 그래프 연결성 정규화(regularization), ($2$) KL 주변 분포(marginal) 페널티를 통한 불균형 OT 정식화, ($3$) 한 번의 열 확산(heat diffusion)으로 모든 쌍별 거리를 계산하는 배치 행렬 알고리즘(분포 $500$개 기준 Geodesic Sinkhorn보다 $200 \times$ 이상 빠름). 우리는 합성 벤치마크와 CyTOF 섭동(perturbation) 데이터셋(dataset)에서 Pheno-GS를 검증한다.

arXiv:2610.00017v1cs.CV공통 태그 Uncertainty Quantification, Computational Efficiency

조밀 예측(Dense Prediction)을 위한 Spatial Lifting

Spatial Lifting for Dense Prediction

우리는 조밀 예측(dense prediction) 작업을 위한 새로운 방법론인 Spatial Lifting(SL)을 제시한다. SL은 2D 이미지와 같은 표준 입력을 더 높은 차원의 공간으로 리프팅(lifting)한 후, 3D U-Net과 같이 해당 고차원에 맞게 설계된 네트워크를 사용하여 이를 처리하는 방식으로 동작한다. 직관에 반하게도, 이러한 차원 리프팅을 통해 기존 접근법 대비 벤치마크 작업에서 우수한 성능을 달성하는 동시에 추론(inference) 비용을 줄이고 모델(model) 파라미터 수를 대폭 줄일 수 있다. SL 프레임워크는 리프팅된 차원을 따라 본질적으로 구조화된 출력을 생성한다. 이러한 창발적(emergent) 구조는 학습(training) 중 조밀한 지도(supervision)를 가능하게 하고, 테스트 시점에 단일 순전파(forward pass)만으로 자기 일관성(self-consistency) 기반의 품질 및 불확실성 추정을 가능하게 한다. Spatial Lifting은 비전(vision) 분야의 조밀 예측 작업을 위해 더 효율적이고 정확하며 신뢰할 수 있는 딥 네트워크로 나아가는 유망한 경로를 제시하는 간단하고 일반적인 모델링 전략을 소개한다.

arXiv:2609.27765v1math.ST공통 태그 Uncertainty Quantification, hypothesis testing

테스트 수퍼마틴게일의 제2종 오류: e-파워 대 Chernoff-Stein 지수

The Type-II Error of Test Supermartingales: e-Power versus the Chernoff-Stein Exponent

테스트 수퍼마틴게일을 사용하는 안전한 가설 검정에서, wealth process가 처음 $1/\alpha$를 넘을 때 귀무가설을 기각하면 Ville 부등식은 모든 유의수준 $\alpha\in(0,1]$에 대해 anytime-valid 제1종 오류 보장을 제공한다. 내재된 비대칭성 때문에 제2종 오류는 다르게 거동한다. 단순 귀무 및 대립 가설에 대해 후자와 관련하여 두 가지를 증명한다. 첫째, Kelly betting과 성장률 최적 e-variable이 극대화하는 평균 성장률 $\mathbb{E}_{P_1}[\log E]$, 즉 e-파워는 그 자체로는 아무것도 제한하지 않는다. 모든 수준 $c>0$, 모든 $\alpha$ 및 horizon $t$에 대해 조건부 e-파워가 정확히 $c$인 e-variable을 구성할 수 있으며, 시점 $t$까지 기각하지 않을 확률을 임의로 1에 가깝게 만들 수 있다. 이는 결국 기각을 강제하지만 유한 horizon 보장은 따르지 않는다. 둘째, 제2종 오류를 실제로 제어하는 양은 e-variable의 Chernoff-Stein 지수 $\Lambda(E)=\sup_{s\ge0}\{-\log \mathbb{E}_{P_1}[E^{-s}]\}$이며, 그 범위는 정확히 결정된다: $\sup_E \Lambda(E)=\mathrm{KL}(P_0\|P_1)$, 고전적인 Chernoff-Stein 지수이며 e-variable별 형태 자체의 상한이다. 각 단계마다 Hölder 부등식을 한 번 조건부로 적용하면, 독립성이나 곱 구조 없이 임의의 필터링된 확률공간 위의 모든 테스트 수퍼마틴게일에 대해 이를 얻을 수 있다. i.i.d. 경우에는 더하여 그 상한이 정확히 맞으며, 어떤 것도 이를 달성하지 못한다. e-파워는 자체 상한 $\mathrm{KL}(P_1\|P_0)$을 갖으며, 이 상한은 가능도비 $R$에 의해 $P_0$-a.s. 유일하게 달성된다. 두 최적값은 인수 순서가 반대인 동일한 divergence이며, 평탄화된 family $R^{\beta}/\mathbb{E}_{P_0}[R^{\beta}]$의 양 끝에서 나타난다: $\beta\downarrow0$일 때 상한, $\beta=1$에서 $R$. 어떤 $\beta$가 최적인지는 horizon에 의해 정확히 결정된다. $R$은 $t=\log(1/\alpha)/\mathrm{KL}(P_1\|P_0)$에서만 최적이며, 그보다 작은 $t$에서는 sharpening $(\beta>1)$에, 그보다 큰 $t$에서는 flattening에 의해 능가된다.

arXiv:2609.27766v1math.ST공통 태그 Uncertainty Quantification, hypothesis testing

하위 꼬리 가설로부터 도출된 검정 슈퍼마팅게일의 2종 오류 한계

Type-II Error Bounds for Test Supermartingales from Lower-Tail Hypotheses

검정 슈퍼마팅게일(test supermartingale)을 이용한 안전한 가설 검정에서 빌의 부등식(Ville's inequality)은 자산 과정(wealth process)이 처음으로 $\frac{1}{\alpha}$을 초과할 때마다 귀무가설을 기각하는 경우, 모든 유의수준 $\alpha\in(0,1]$에 대해 언제나 유효한(anytime-valid) 1종 오류 보장을 제공합니다. 고유한 비대칭성으로 인해 2종 오류에는 이러한 보장이 존재하지 않습니다. 로그 증분의 하위 꼬리(lower tail)에 확률이 과도하게 집중되면 축적된 모든 증거를 무효화하는 단 한 번의 치명적인 베팅으로 이어질 수 있기 때문입니다. 본 논문은 이러한 하위 꼬리 확률에 대한 서로 다른 가설들이 순차적 검정의 2종 오류에 대한 서로 다른 한계로 어떻게 이어지는지 연구합니다. 이 한계들은 모두 하나의 마스터 부등식으로 귀결되며, 이는 축적된 e-거듭제곱의 하한이 $\log\frac{1}{\alpha}$을 초과하는 크기라는 단 하나의 값에서 평가된 e-변수들의 (역)적률생성함수의 단측 르장드르 변환(Legendre transform) 측면에서 고정된 시계 및 순차적으로 유의수준 $\alpha$에서의 2종 오류를 제한합니다. 또한 이 단계는 제약된 정보 투영(constrained information projection)을 정확히 추출한다는 의미에서 무손실(lossless)입니다. 본 논문에서 제시되는 모든 한계는 위 함수의 특정 우세 함수(majorant)를 통해 얻어지는 따름정리입니다. 고려된 가설들은 유한한 음의 적률, 승리 측의 적률을 동반한 지수적으로 작은 폭락 확률, 조건부 분산을 가진 자산 하한 및 분산에 의해 결정되는 가우시안 영역과 척도에 의해 결정되는 지수 영역 사이를 보간하는 번스타인(Bernstein) 변형, 서브-가우시안 또는 유계 기울기 하위 꼬리, 유계 로그 증분, 그리고 우세 함수가 참값이 되는 i.i.d. 증분입니다. 우리는 또한 경험적 번스타인 변형을 제공합니다. 각 가설은 보유한 e-변수에 대한 조건으로 해석되거나, 가장 약한 조건을 무상으로 만족하는 우도비 자체 대신 가능도(likelihood) 비의 근사치를 사용해 베팅할 때 발생하는 비용으로 해석될 수 있습니다.

arXiv:2609.27814v1cs.CL공통 태그 Uncertainty Quantification, Graph Learning

LabourCrew: 노동법에 대한 신뢰 가능한 적대적 심의 및 법령 추론을 위한 멀티 에이전트 RAG 프레임워크

LabourCrew: A Multi-Agent RAG Framework for Trustworthy Adversarial Deliberation and Statutory Reasoning over Labour Law

법령 기반 질의응답(statutory question answering)에서는 검증 불가능한 노동권 관련 답변이 심각한 법적 결과를 초래할 수 있으므로, 모든 주장이 단순한 관련성을 넘어 반드시 증거로 추적 가능해야 합니다. 기존 시스템은 이에 미치지 못합니다. 단일 패스(single-pass) 검색-증강 생성(RAG)은 증거 부족을 감지하지 못하며, 멀티 에이전트 법률 토론 시스템은 그라운딩(grounding)을 프롬프트 관례 수준으로 취급하여 에이전트가 검색되지 않은 증거를 인용하도록 허용합니다. 이러한 격차를 해결하기 위해, 세 가지 그라운딩 메커니즘을 중심으로 구축된 멀티 에이전트 RAG 프레임워크인 LabourCrew를 소개합니다. 첫째, 고정 길이 스팬 대신 장, 조항, 단서 조항, 상호 참조 구조를 명시적으로 연결하는 그래프 인덱스인 StatuteGraph, 둘째, 옹호인(advocate)과 해석인(interpreter)을 증거 원장에 국한하여 검색되지 않은 텍스트를 인용하는 것을 원천 차단하는 동시에, 개별 실패가 시스템 다운으로 이어지지 않고 점진적으로 저하되도록 옹호인을 병렬 실행하는 내결함성 감독 위원회로 구성된 증거 교환 프로토콜(Evidence Exchange Protocol), 셋째, 단정적인 수락/기각 결정을 신뢰 점수로 대체하고 오수락률(false-accept rate)에 대한 무분포 경계(distribution-free bound)를 확보하기 위해 등각 위험 제어(conformal risk control)로 임계값을 설정하는 보정된 신뢰 게이트(Calibrated Trust Gate)입니다. 7개 추론 범주와 3개 난이도 단계에 걸친 방글라데시 2006년 노동법 기반의 500개 벵골어 문항 세트인 LabourActQA에서 평가를 수행했습니다. 본 프레임워크는 실증적 오수락률을 목표치($\alpha = 0.10$) 이내인 0.081로 낮추고, HyDE RAG, Graph-RAG, Hierarchical RAG 대비 가장 높은 답변 관련성(Answer Relevancy)을 달성했으며(0.862 $>$ 0.839, 0.815, 0.828), 질문 난이도가 높아짐에 따라 급격한 성능 저하 없이 점진적으로 저하됩니다. 이러한 결과는 저자원 법령 도메인에서 법률 질의응답을 감사 가능하게 만드는 핵심이 검색 품질 단독이 아닌 보정된 기권(calibrated abstention)임을 보여줍니다.

arXiv:2609.27209v1cs.LG공통 태그 Computational Efficiency, Graph Learning

저항 곡률 기반 확장 가능한 서브그래프 샘플링

Scalable Subgraph Sampling via Resistance Curvature

서브그래프 샘플링은 대규모 그래프 신경망(GNN)의 학습 비용을 줄이지만, 샘플링 기준은 엣지의 기하학적 역할을 간과할 수 있다. 우리는 대규모 그래프용 곡률 근사 방법인 ERC-LG 위에 구축한 저항 곡률(resistance curvature) 유도 샘플링 프레임워크를 제안한다. ERC-LG는 Johnson-Lindenstrauss 투영과 정규화된 다중 GPU 배치 공액 그래디언트(conjugate gradient) 솔버를 결합하여, 명시적인 라플라시안 의사역행렬(pseudoinverse) 계산과 전체 임베딩 저장을 피한다. 이렇게 얻은 곡률은 GNN 학습 서브그래프를 구성하기 위한 노드 및 엣지 샘플링 확률을 결정하는 데 활용된다. 실험 결과, 의사역행렬 기반 곡률과 수치적으로 일치하며 CG만 사용한 계산 대비 실행 시간이 감소한다. ERC-LG 기반 샘플링 변형은 다운스트림 노드 분류에서 7개 실세계 데이터셋 중 6개에서 최고 평균 정확도를 달성한다.

토론

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