arXiv:2502.02861

Algorithms with Calibrated Machine Learning Predictions

Judy Hanwen Shen, Ellen Vitercik, Anders Wikum

제출 2025-02-05

원문 초록

The field of algorithms with predictions incorporates machine learning advice in the design of online algorithms to improve real-world performance. A central consideration is the extent to which predictions can be trusted -- while existing approaches often require users to specify an aggregate trust level, modern machine learning models can provide estimates of prediction-level uncertainty. In this paper, we propose calibration as a principled and practical tool to bridge this gap, demonstrating the benefits of calibrated advice through two case studies: the ski rental and online job scheduling problems. For ski rental, we design an algorithm that achieves near-optimal prediction-dependent performance and prove that, in high-variance settings, calibrated advice offers more effective guidance than alternative methods for uncertainty quantification. For job scheduling, we demonstrate that using a calibrated predictor leads to significant performance improvements over existing methods. Evaluations on real-world data validate our theoretical findings, highlighting the practical impact of calibration for algorithms with predictions.

함께 살펴볼 논문

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

arXiv:2607.23942v1cs.AI공통 태그 Uncertainty Quantification, Scheduling

인지 아키텍처에서 언어 에이전트로: 계보, 수렴, 이전 격차에 대한 메커니즘 수준 리뷰

From Cognitive Architectures to Language Agents: A Mechanism-Level Review of Lineage, Convergence, and Migration Gaps

메모리, 계획, 반성(reflection), 도구 사용은 종종 특징 라벨로 비교되어, 에이전트가 실제로 어떻게 실행되는지를 결정하는 제어 의미론(control semantics)을 가려 버린다. 이 리뷰는 10개의 역사적 인지 아키텍처, 8개의 언어 에이전트 런타임 계열, 42개의 메커니즘 중심 현대 시스템을 연결한다. 각 메커니즘을 상태, 제어, 전이, 지속성, 실패, 학습, 자원 거버넌스를 통해 재구성한 뒤, 증거 관계(E1–E4)와 이전 깊이(D0–D4)를 별도로 코딩한다. 그 결과로 드러난 지형은 고르지 않다. 현대 에이전트는 적응형 메모리, 실패 복구, 동적 팀 선택, 워크플로우 탐색, 스킬 유도(skill induction), 자원 스케줄링, 불확실성 조건 행동(uncertainty-conditioned action)의 상당 부분을 실현화했지만, 종종 문서화된 계승(inheritance)보다는 독립적인 수렴을 통해 이루어졌다. 가장 큰 남은 기회는 메커니즘 간 결합(couplings)에 있다. 가장 근접한 기준선 스크리닝은 제안된 격차 중 하나를 메운다: GraSP는 이미 보정된 다중 스킬 선택, 타입화된 컴파일, 검증, 경계(bounded) 수리, 재계획 또는 ReAct 폴백을 결합한다. 5개의 잔여 번들이 남아 있다: 지연(latency)과 행동 유틸리티(action utility)를 갖춘 활성화(activation); 격리된 하위 상태(isolated substates)와 해결 컴파일(resolution compilation)을 갖춘 타입화된 교착 상태(typed impasse); 브로드캐스트와 승인 학습(admission learning)을 갖춘 경계 내 콘텐츠 경쟁(bounded content competition); 재고(reconsideration)와 실시간 방법 권한(live method authority)을 갖춘 지속적 의도(persistent intention); 자원 할당, 중단(interruption), 정지(stopping)를 갖춘 불확실성. 우리는 독특한 메커니즘 카탈로그, 감사 가능한 증거 깊이 프레임워크, 이 번들들을 조합 가능한 런타임 불변량(composable runtime invariants)으로 검증하기 위한 반증 가능한(falsifiable) 의제를 기여한다.

arXiv:2610.02975v2cs.AI공통 태그 Uncertainty Quantification

불완전한 프록시 보상을 활용한 신뢰할 수 있는 자기 진화

Reliable Self-Evolution with Imperfect Proxy Rewards

대규모 언어 모델(LLM) 기반의 자기 진화 탐색은 과학적 발견을 위한 유망한 접근법입니다. 그러나 일부 영역에서는 모든 후보에 대해 고충실도(high-fidelity) 평가를 수행하는 데 엄청난 비용이 듭니다. 따라서 이러한 환경의 자기 진화 시스템은 비용이 저렴하지만 불완전한 프록시 보상(proxy reward)에 의존하며, 이는 실현 불가능한 후보에 높은 점수를 부여할 수 있습니다. 이러한 위양성(false positive)은 최종 출력뿐만 아니라 후속 세대를 유도하는 데 사용되는 피드백까지 오염시킬 수 있습니다. 이는 보다 신뢰할 수 있는 자기 진화 탐색을 위해 통계적으로 보정된 보상 구간을 도입하는 동기가 됩니다. 본 논문에서는 조건부 등분산 추론(conditional conformal inference)과 반복(iteration)별 온라인 밀도비 추정을 사용하여 후보별 보상 구간을 구성하는 CISE(Conformal Interval-Driven Self-Evolution)를 제안합니다. CISE는 진화적 피드백을 위해 보수적인 구간 기반 보상을 사용하며, 요구되는 모든 속성 구간이 각자의 실행 가능한 영역 내에 완전히 포함될 때만 후보를 반환합니다. 본 연구는 독립성 및 공변량 변화(covariate shift)에 대한 명시적 가정 하에서 고정 반복 커버리지 결과를 도출합니다. 또한 재료과학 분야의 세 가지 자기 진화 탐색 작업에서 CISE를 평가합니다. 실험 결과, 고충실도 평가에서 CISE가 반환한 모든 후보는 진양성(true positive)이었던 반면, 베이스라인들은 더 많은 후보를 반환하지만 위양성을 포함했습니다. 이러한 결과는 다운스트림 검증 예산이 제한적일 때 더 작지만 더 정밀한 후보 목록이 갖는 가치를 강조합니다. 연구 저장소는 https://github.com/MLAI-Yonsei/CISE.git 에서 확인할 수 있습니다.

arXiv:2608.23986v4math.OC공통 태그 Scheduling

지능의 그림자 가격: LLM 추론에서의 품질 저하와 재시도 피드백

The Shadow Price of Intelligence: Quality Degradation and Retry Feedback in LLM Inference

대규모 언어 모델 제공자는 연산 자원이 제약되어 있으며, 혼잡에 대한 일반적인 대응은 서비스를 저하시키는 것이다. 즉, 질의를 더 작은 모델로 라우팅하거나, 추론 예산을 줄이거나, 컨텍스트 윈도를 단축한다. 만족스럽지 못한 답을 받은 사용자는 재시도하여 시스템이 바쁜 동안 부하를 늘리거나, 이탈하여 잠재적으로 고객 이탈로 이어진다. 우리는 추론 서비스를 서비스 품질이 제공자의 의사결정인 제어 문제로 모델링한다. 재시도를 서비스율에 포함한 2국면 유체 근사는 닫힌 형태의 궤적과 교차 시간을 제공하므로, 품질 등급에 대한 동적 계획법에 시뮬레이션이 필요하지 않다. 우리는 더 약한 등급이 작업당 에너지는 덜 쓰지만 작업당 용량은 더 쓰는 영역을 규명하고, 유체 모델에서 그러한 등급으로의 반응적 스로틀링이 큐가 해소되지 못하게 할 수 있음을 보인다. 이질적인 고객이 있는 경우 이 문제는 재시도로 부풀려진 용량 계수를 갖는 수송 문제가 되며, 최적 라우팅은 $c\mu$ 유형의 지수를 따르고, 용량 제약의 쌍대는 클래스와 시간별로 질의 하나를 더 처리하는 한계 비용을 제공한다. 우리는 공개 벤치마크 데이터로 보정한 다섯 가지 사례에서 이 방법을 예시한다.

arXiv:2609.26683v2astro-ph.SR공통 태그 Uncertainty Quantification

PROSWIN: 태양 영상을 이용한 심층 분포 회귀 기반의 확률론적 태양풍 속도 예측

PROSWIN: Probabilistic Solar Wind Speed Forecasting Using Deep Distributional Regression From Solar Images

빠른 태양풍 조건을 정확하게 예측하는 것은 불확실성이 크고 기존의 단일값 예측 모델로는 이를 정량화할 수 없기 때문에 어려운 과제입니다. 특히 기술적 인프라에 피해를 줄 수 있는 고속 태양풍 스트림(HSS)의 위험은 확률론적 예측 없이는 신뢰성 있게 평가될 수 없습니다. 본 연구에서는 4일의 리드 타임으로 지구에서의 시간별 태양풍 속도(SWS)를 예측하는 확률론적 머신러닝 모델인 PROSWIN을 제시합니다. 이 접근 방식은 심층 신경망(deep neural network)과 분포 회귀(distributional regression) 알고리즘을 결합하여 태양 영상과 자기장 지도(magnetogram)를 통합합니다. 표준 오차 지표는 HSS 피크의 중요성을 과소평가하므로, 타임라인과 HSS 피크 정확도를 함께 보상하는 모델 선택 지표인 예측 점수(prediction score)를 추가로 도입합니다. 14년간의 데이터에서 본 연구의 예측은 매우 잘 보정된 불확실성(평균 편차 <1%)을 달성합니다. 분포 정확도를 평가하는 지표인 연속 순위 확률 점수(CRPS)를 사용하여 타임라인 CRPS 41.0 km/s, HSS 피크 CRPS 45.3 km/s, 예측 점수 42.3 km/s를 얻었습니다. 또한 171 Å 채널이 일반적으로 사용되는 193 Å 및 211 Å 채널에 중요한 보완 요소가 되며, 모델 선택을 위한 예측 점수가 모델의 적용 가능성을 향상시킨다는 점을 확인했습니다. 기존 문헌에서 선정된 모델들과 비교했을 때, 본 모델은 둘 중 하나를 희생하지 않고 타임라인과 HSS 피크 값 모두에서 정확한 유일한 모델입니다. 이러한 결과는 단일값 태양풍 모델 대비 확률론적 모델의 이점을 뒷받침합니다. 도입된 방법론은 다른 예측 문제에도 전이 가능합니다.

arXiv:2609.27179v2math.ST공통 태그 Uncertainty Quantification

컨포멀 마팅게일을 이용한 분포 무관 순차적 변화 탐지의 최적성

Optimal distribution-free sequential change detection with conformal martingales

본 연구는 변화 전후의 분포가 알려져 있지 않으며 \emph{전혀 제한되지 않은} 독립 관측치에 대한 분포 무관 순차적 변화점 탐지라는 어려운 문제를 다룬다. 20년 넘게 이 문제의 주된 기존 해법은 Vovk의 컨포멀 검정 마팅게일과 이에 연관된 e-탐지기를 사용해 왔으며, 이들은 각각 오경보 확률(PFA)과 평균 실행 길이(ARL)를 제어한다. 이러한 연구 대부분은 타당성에 초점을 맞추고 있으며, 통계적 효율성은 대체로 시뮬레이션에 맡겨져 왔다. 본 논문은 알려지지 않은 시점 $T$에 변화점이 있는 비교환 가능 데이터에서 컨포멀 p-값이 어떻게 거동하는지에 대한 포괄적인 이론을 전개한다. 이를 이용해 변화 후 성장과 그에 따른 탐지 지연을 분석하였고, 기존의 표준 방법이 PFA 및 ARL 제어에 대해 증명 가능하게 최적이 아니며 각각 $\Omega(T)$와 $\Omega(\sqrt{\text{ARL}})$ 수준의 지연을 초래할 수 있음을 발견하였다. 우리는 학습된 점수와 고정된 분포 독립적 베팅 사전(dictionary)을 사용하는 새로운 컨포멀 e-프로세스와 e-탐지기를 구성한다. KL 발산이 양의 유한값인 모든 분포 쌍에 대해, 제안한 방법은 PFA 제어에서 $\log T/\mathrm{KL}$ 지연을, ARL 제어에서 $\log\mathrm{ARL}/\mathrm{KL}$ 지연(선도 상수 1로 엄밀함)을 점근적으로 달성하며, 이 둘은 적절한 이중 배열 프레임워크에서 미니맥스 최적임이 증명된다. 시뮬레이션은 새로운 접근법의 큰 경험적 이점을 보여 준다.

arXiv:2609.27144v2cs.LG공통 태그 Uncertainty Quantification

미관측 교란 변수에 강건한 위험 점수 학습

Learning Risk Scores Robust to Unobserved Confounders

미관측 교란의 영향을 받는 역사적 관찰 데이터로부터, 희소 자원이나 개입 대상 개인의 우선순위를 정하기 위한 위험 점수를 학습하는 문제를 다룬다. 누가 희소 자원을 받을지에 대한 결정은 설문 응답과 같이 기록된 특성에 기반한 위험 점수에 의해 종종 안내된다. 이러한 위험 점수는 개인의 특성, 배분 결정, 결과에 대한 역사적 기록인 관찰 데이터로부터 직접 학습되는 경우가 점점 늘고 있다. 역사적 배분 정책이 도입한 바이어스를 보정하는 역 성향 가중치(inverse propensity weighting, IPW)와 같은 표준 방법은, 역사적 결정 과정이 기록된 특성으로 완전히 설명될 수 있다면 정확한 위험 점수를 학습하는 데 사용될 수 있다. 그러나 실무에서는 역사적 결정이 종종 기록되지 않은 정보에 의존하여, 학습된 위험 점수가 과거 우선순위를 이끌었던 기록되지 않은 상황을 가진 개인들을 정확히 체계적으로 과소 우선순위화하게 만든다. IPW를 기반으로, 이러한 종류의 미관측 교란에 강건한 위험 점수를 학습하는 방법을 제안한다. 미관측 교란 하에서는 성향 가중치를 신뢰할 수 있게 추정할 수 없으므로, 대신 관측 가능한 데이터와 교란 정도에 대한 도메인 정보 기반 추정치로 결정되는 불확실성 집합에 속하는 것으로 취급하며, 인과 추론(causal inference)의 민감도 분석(sensitivity analysis)과 Wasserstein 분포적 강건 최적화(Wasserstein distributionally robust optimization)를 결합한다. 그 결과 강건 위험 점수 학습 문제는 표본 기반 근사를 허용하며, 이를 기성 솔버와 호환되는 지수 원뿔 프로그램(exponential cone program)으로 재공식화한다. UCI Machine Learning Repository의 데이터셋에서 파생된 반합성(semi-synthetic) 데이터에서 접근법의 효과를 입증한다. 제안 방법은 다른 지표를 손상하지 않으면서, 전통적 벤치마크 대비 보정(calibration)을 최대 29.2%까지, 최신(state of the art) 대비 최대 11.1%까지 개선한다.

토론

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