論文の概要: Testing Calibration in Nearly-Linear Time
- arxiv url: http://arxiv.org/abs/2402.13187v2
- Date: Fri, 21 Jun 2024 17:27:22 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-24 19:46:30.058732
- Title: Testing Calibration in Nearly-Linear Time
- Title（参考訳）: ほぼ未熟な時間におけるテスト校正
- Authors: Lunjia Hu, Arun Jambulapati, Kevin Tian, Chutong Yang,
- Abstract要約: プロパティテストのレンズによるキャリブレーションのアルゴリズム的な研究に焦点をあてる。
実験的なスムーズなキャリブレーション線形プログラムは,高構造グラフ上の最小コストフローの例として再計算できる,という簡単な観察を行う。
我々は,キャリブレーションの標準概念を忠実に捉え,我々のアルゴリズムが大規模なサンプルサイズに対応するために効率的にスケールできることを実証する実験を行った。
- 参考スコア（独自算出の注目度）: 14.099477870728595
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the recent literature on machine learning and decision making, calibration has emerged as a desirable and widely-studied statistical property of the outputs of binary prediction models. However, the algorithmic aspects of measuring model calibration have remained relatively less well-explored. Motivated by [BGHN23], which proposed a rigorous framework for measuring distances to calibration, we initiate the algorithmic study of calibration through the lens of property testing. We define the problem of calibration testing from samples where given $n$ draws from a distribution $\mathcal{D}$ on $(predictions, binary outcomes)$, our goal is to distinguish between the case where $\mathcal{D}$ is perfectly calibrated, and the case where $\mathcal{D}$ is $\varepsilon$-far from calibration. We make the simple observation that the empirical smooth calibration linear program can be reformulated as an instance of minimum-cost flow on a highly-structured graph, and design an exact dynamic programming-based solver for it which runs in time $O(n\log^2(n))$, and solves the calibration testing problem information-theoretically optimally in the same time. This improves upon state-of-the-art black-box linear program solvers requiring $\Omega(n^\omega)$ time, where $\omega > 2$ is the exponent of matrix multiplication. We also develop algorithms for tolerant variants of our testing problem improving upon black-box linear program solvers, and give sample complexity lower bounds for alternative calibration measures to the one considered in this work. Finally, we present experiments showing the testing problem we define faithfully captures standard notions of calibration, and that our algorithms scale efficiently to accommodate large sample sizes.
- Abstract（参考訳）: 機械学習と意思決定に関する最近の文献において、キャリブレーションは二項予測モデルの出力の望ましい統計的特性として広く研究されている。
しかし, モデルキャリブレーションのアルゴリズム的側面は, 比較的よく研究されていない。
キャリブレーション距離を計測する厳密な枠組みを提案した[BGHN23] に動機付けられ, 特性試験のレンズによるキャリブレーションのアルゴリズム研究を開始した。
分布$\mathcal{D}$ on $(predictions, binary outcomes)$, 我々のゴールは、$\mathcal{D}$が完全に校正されている場合と、$\mathcal{D}$が$\varepsilon$-farである場合とを区別することである。
実験的なスムーズなキャリブレーション線形プログラムを,高構造グラフ上での最小コストフローの例として再計算し,時間$O(n\log^2(n))$で実行された正確な動的プログラムベースのソルバを設計し,同時に最適にキャリブレーションテスト問題を解く。
これにより、最先端のブラックボックス線形プログラムソルバは、$\Omega(n^\omega)$ time を必要とし、$\omega > 2$ は行列乗算の指数である。
また,ブラックボックス・リニア・プログラム・ソルバを改良したテスト問題の寛容な変種に対するアルゴリズムを開発し,本研究で検討した代替校正基準に対するサンプル複雑性の低いバウンダリを与える。
最後に、我々は、キャリブレーションの標準概念を忠実に捉え、我々のアルゴリズムが大規模なサンプルサイズに対応するために効率的にスケールすることを示す実験を示す。
関連論文リスト
- On the Distance from Calibration in Sequential Prediction [4.14360329494344]
キャリブレーション距離から予測器を評価可能な逐次二分予測条件について検討する。
キャリブレーション距離は、完全キャリブレーションから逸脱する自然で直感的な尺度である。
我々は,逆選択された$T$バイナリ結果の列に対して,予測において$O(sqrtT)$キャリブレーション距離を達成できる予測アルゴリズムが存在することを証明した。
論文 参考訳（メタデータ） (2024-02-12T07:37:19Z) - On Calibrating Semantic Segmentation Models: Analyses and An Algorithm [51.85289816613351]
セマンティックセグメンテーションキャリブレーションの問題について検討する。
モデルキャパシティ、作物サイズ、マルチスケールテスト、予測精度はキャリブレーションに影響を及ぼす。
我々は、単純で統一的で効果的なアプローチ、すなわち選択的スケーリングを提案する。
論文 参考訳（メタデータ） (2022-12-22T22:05:16Z) - A Consistent and Differentiable Lp Canonical Calibration Error Estimator [21.67616079217758]
ディープニューラルネットワークは校正が不十分で、自信過剰な予測を出力する傾向がある。
ディリクレ核密度推定に基づく低バイアス・トレーニング可能な校正誤差推定器を提案する。
提案手法はカーネルの自然な選択であり,他の量の一貫した推定値を生成するのに利用できる。
論文 参考訳（メタデータ） (2022-10-13T15:11:11Z) - Class-wise and reduced calibration methods [0.0]
キャリブレーションの削減により、元の問題をより単純なものに変換する方法を示す。
第2に,ニューラル崩壊という現象に基づいて,クラスワイドキャリブレーション手法を提案する。
この2つの手法を併用すると、予測とクラスごとの校正誤差を低減する強力なツールであるクラス単位での校正アルゴリズムが実現される。
論文 参考訳（メタデータ） (2022-10-07T17:13:17Z) - Modular Conformal Calibration [80.33410096908872]
回帰における再校正のためのアルゴリズムを多種多様なクラスで導入する。
このフレームワークは、任意の回帰モデルをキャリブレーションされた確率モデルに変換することを可能にする。
我々は17の回帰データセットに対するMCCの実証的研究を行った。
論文 参考訳（メタデータ） (2022-06-23T03:25:23Z) - T-Cal: An optimal test for the calibration of predictive models [49.11538724574202]
有限検証データセットを用いた予測モデルの誤校正を仮説検証問題として検討する。
誤校正の検出は、クラスの条件付き確率が予測の十分滑らかな関数である場合にのみ可能である。
我々は、$ell$-Expected Error(ECE)のデバイアスドプラグイン推定器に基づくキャリブレーションのためのミニマックステストであるT-Calを提案する。
論文 参考訳（メタデータ） (2022-03-03T16:58:54Z) - MBCT: Tree-Based Feature-Aware Binning for Individual Uncertainty
Calibration [29.780204566046503]
我々はMultiple Boosting Trees (MBCT)と呼ばれる特徴認識型バイナリフレームワークを提案する。
MBCTは非単調であり,学習可能なビンニング方式と個々のキャリブレーションにより,順序精度が向上する可能性がある。
その結果,本手法はキャリブレーション誤差と順序精度の両方で競合するモデルよりも優れていることがわかった。
論文 参考訳（メタデータ） (2022-02-09T08:59:16Z) - Top-label calibration [3.3504365823045044]
マルチクラス分類におけるポストホックキャリブレーションの問題点について検討し,ヒストグラム・バイニングに着目した。
信頼度キャリブレーションという一般的な概念は十分に強くはないことが分かっています -- 意味のある方法でキャリブレーションされていないが、完全に信頼度キャリブレーションされている予測器が存在するのです。
本稿では,信頼度キャリブレーションの直感と単純さを正確に捉えつつも,その欠点に対処する,密接に関連する(微妙に異なる)概念であるトップラベルキャリブレーションを提案する。
論文 参考訳（メタデータ） (2021-07-18T03:27:50Z) - Sample Complexity Bounds for Two Timescale Value-based Reinforcement
Learning Algorithms [65.09383385484007]
2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。
本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
論文 参考訳（メタデータ） (2020-11-10T11:36:30Z) - Uncertainty Quantification and Deep Ensembles [79.4957965474334]
ディープアンサンブルが必ずしもキャリブレーション特性の改善につながるとは限らないことを示す。
そこで本研究では,混成正規化などの現代的な手法と併用して標準アンサンブル法を用いることで,キャリブレーションの少ないモデルが得られることを示す。
このテキストは、データが不足しているときにディープラーニングを活用するために、最も単純で一般的な3つのアプローチの相互作用を調べる。
論文 参考訳（メタデータ） (2020-07-17T07:32:24Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。