論文の概要: Understanding Generalization via Leave-One-Out Conditional Mutual Information

• arxiv url: http://arxiv.org/abs/2206.14800v1
• Date: Wed, 29 Jun 2022 17:57:37 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-30 21:09:18.405507
• Title: Understanding Generalization via Leave-One-Out Conditional Mutual Information
• Title（参考訳）: 条件付き相互情報による一般化の理解
• Authors: Mahdi Haghifam, Shay Moran, Daniel M. Roy, Gintare Karolina Dziugaite
• Abstract要約: アルゴリズムの条件付き相互情報(CMI)の退行変種は、有界損失関数を持つ学習アルゴリズムの平均一般化誤差を制御する。 0-1の損失でゼロ経験的リスクを達成するアルゴリズム(補間アルゴリズム)を学習するために、我々は、残余CMIと古典的残余誤差推定との明示的な接続を提供する。
• 参考スコア（独自算出の注目度）: 37.49575289458763
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the mutual information between (certain summaries of) the output of a learning algorithm and its $n$ training data, conditional on a supersample of $n+1$ i.i.d. data from which the training data is chosen at random without replacement. These leave-one-out variants of the conditional mutual information (CMI) of an algorithm (Steinke and Zakynthinou, 2020) are also seen to control the mean generalization error of learning algorithms with bounded loss functions. For learning algorithms achieving zero empirical risk under 0-1 loss (i.e., interpolating algorithms), we provide an explicit connection between leave-one-out CMI and the classical leave-one-out error estimate of the risk. Using this connection, we obtain upper and lower bounds on risk in terms of the (evaluated) leave-one-out CMI. When the limiting risk is constant or decays polynomially, the bounds converge to within a constant factor of two. As an application, we analyze the population risk of the one-inclusion graph algorithm, a general-purpose transductive learning algorithm for VC classes in the realizable setting. Using leave-one-out CMI, we match the optimal bound for learning VC classes in the realizable setting, answering an open challenge raised by Steinke and Zakynthinou (2020). Finally, in order to understand the role of leave-one-out CMI in studying generalization, we place leave-one-out CMI in a hierarchy of measures, with a novel unconditional mutual information at the root. For 0-1 loss and interpolating learning algorithms, this mutual information is observed to be precisely the risk.
• Abstract（参考訳）: 学習アルゴリズムの出力(特定の要約)とその$n$の訓練データとの相互情報、すなわち、訓練データが置換せずにランダムに選択される、$n+1$i.d.のデータについて検討する。 これらの条件付き相互情報(CMI)の退行変種(Steinke and Zakynthinou, 2020)も、有界損失関数を持つ学習アルゴリズムの平均一般化誤差を制御する。 0-1の損失でゼロ経験的リスクを達成するアルゴリズム(補間アルゴリズム)を学習するために、我々は、残余CMIと古典的残余誤差推定との明確な接続を提供する。 この接続を用いて、(評価された)残高CMIの観点から、リスクの上下境界を得る。 制限リスクが定数であるか多項式的に崩壊した場合、境界は2の定数係数内に収束する。 そこで本研究では,VC クラスを対象とした汎用的トランスダクティブ学習アルゴリズムである 1-inclusion graph アルゴリズムの集団リスクを,実現可能な環境で解析する。 残欠型cmiを用いて, steinke と zakynthinou (2020) が提起したオープンチャレンジに答えながら, 実現可能な設定で vc クラスを学習するための最適境界を一致させる。 最後に, 一般化研究における残余CMIの役割を理解するために, 残余CMIを指標の階層に配置し, 根元に新たな無条件相互情報を置く。 0-1損失と補間学習アルゴリズムでは、この相互情報は正確にリスクである。

関連論文リスト

• An Information-Theoretic Analysis for Transfer Learning: Error Bounds and Applications [5.081241420920605]
  本稿では,伝達学習アルゴリズムの一般化誤差と過剰リスクに関する情報理論解析を行う。 我々の結果は、おそらく予想通り、Kulback-Leiblerの発散$D(mu||mu')$がキャラクタリゼーションにおいて重要な役割を果たすことを示唆している。 そこで本研究では,ソースデータとターゲットデータの重み付けを適応的に調整するInfoBoostアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-07-12T08:20:41Z)
• On Leave-One-Out Conditional Mutual Information For Generalization [122.2734338600665]
  残余条件付き相互情報(loo-CMI)の新しい尺度に基づく教師付き学習アルゴリズムのための情報理論の一般化境界を導出する。 他のCMI境界とは対照的に、我々のloo-CMI境界は容易に計算でき、古典的なout-out-out-cross-validationのような他の概念と関連して解釈できる。 ディープラーニングのシナリオにおいて予測された一般化ギャップを評価することにより,境界の質を実証的に検証する。
  論文  参考訳（メタデータ） (2022-07-01T17:58:29Z)
• CIC: Contrastive Intrinsic Control for Unsupervised Skill Discovery [88.97076030698433]
  本稿では,教師なしスキル発見のためのアルゴリズムであるContrastive Intrinsic Control (CIC)を紹介する。 CICは、状態エントロピーを最大化することで、多様な振る舞いを明示的にインセンティブ化する。 CICは従来の教師なしスキル発見手法よりも大幅に改善されている。
  論文  参考訳（メタデータ） (2022-02-01T00:36:29Z)
• Local Learning Matters: Rethinking Data Heterogeneity in Federated Learning [61.488646649045215]
  フェデレートラーニング(FL)は、クライアントのネットワーク(エッジデバイス)でプライバシ保護、分散ラーニングを行うための有望な戦略である。
  論文  参考訳（メタデータ） (2021-11-28T19:03:39Z)
• Towards a Unified Information-Theoretic Framework for Generalization [43.23033319683591]
  まず、このフレームワークを用いて、任意の学習アルゴリズムに対して非自明な(しかし、準最適)境界を表現できることを実証する。 我々は、CMIフレームワークが、ハーフスペースを学習するためのSVM(Support Vector Machines)の予測されるリスクに最適な境界をもたらすことを証明した。
  論文  参考訳（メタデータ） (2021-11-09T17:09:40Z)
• Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning [57.88785630755165]
  経験的リスク最小化(Empirical Risk Minimization, ERM)は、機械学習のワークホースであるが、適応的に収集されたデータを使用すると、そのモデルに依存しない保証が失敗する可能性がある。 本研究では,仮説クラス上での損失関数の平均値を最小限に抑えるため,適応的に収集したデータを用いた一般的な重み付きERMアルゴリズムについて検討する。 政策学習では、探索がゼロになるたびに既存の文献のオープンギャップを埋める率-最適後悔保証を提供する。
  論文  参考訳（メタデータ） (2021-06-03T09:50:13Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。 我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。 標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
  論文  参考訳（メタデータ） (2020-07-06T15:20:17Z)
• Generalization Bounds via Information Density and Conditional Information Density [14.147617330278662]
  本稿では,指数関数的不等式に基づいてランダム化学習アルゴリズムの一般化誤差を導出する一般手法を提案する。 PAC-Bayesian と Single-draw の両方のシナリオに対して、平均一般化誤差のバウンダリと、そのテール確率のバウンダリを提供する。
  論文  参考訳（メタデータ） (2020-05-16T17:04:24Z)
• Reasoning About Generalization via Conditional Mutual Information [26.011933885798506]
  我々は、Mutual Information (CMI) を用いて、入力がどの程度の精度で認識できるかを定量化する。 CMIのバウンダリは,VC次元,圧縮スキーム,差分プライバシー,その他の手法から得られることを示す。 次に、有界な CMI は様々な種類の一般化を意味することを示す。
  論文  参考訳（メタデータ） (2020-01-24T18:13:04Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。