論文の概要: Active causal structure learning with advice
- arxiv url: http://arxiv.org/abs/2305.19588v1
- Date: Wed, 31 May 2023 06:15:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-01 18:20:34.544887
- Title: Active causal structure learning with advice
- Title（参考訳）: アドバイスによるアクティブ因果構造学習
- Authors: Davin Choo, Themis Gouleakis, Arnab Bhattacharyya
- Abstract要約: 本稿では,積極的な因果構造学習の課題をアドバイスとともに紹介する。
我々は、介入コストが最大$O(max1, log psi)$である$G*$を復元する適応探索アルゴリズムを設計する。
- 参考スコア（独自算出の注目度）: 10.680060759322364
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce the problem of active causal structure learning with advice. In
the typical well-studied setting, the learning algorithm is given the essential
graph for the observational distribution and is asked to recover the underlying
causal directed acyclic graph (DAG) $G^*$ while minimizing the number of
interventions made. In our setting, we are additionally given side information
about $G^*$ as advice, e.g. a DAG $G$ purported to be $G^*$. We ask whether the
learning algorithm can benefit from the advice when it is close to being
correct, while still having worst-case guarantees even when the advice is
arbitrarily bad. Our work is in the same space as the growing body of research
on algorithms with predictions. When the advice is a DAG $G$, we design an
adaptive search algorithm to recover $G^*$ whose intervention cost is at most
$O(\max\{1, \log \psi\})$ times the cost for verifying $G^*$; here, $\psi$ is a
distance measure between $G$ and $G^*$ that is upper bounded by the number of
variables $n$, and is exactly 0 when $G=G^*$. Our approximation factor matches
the state-of-the-art for the advice-less setting.
- Abstract（参考訳）: 我々は,能動因果構造学習の問題点をアドバイスで紹介する。
典型的なよく研究された環境では、学習アルゴリズムは観測分布に不可欠なグラフを与え、基礎となる因果有向非巡回グラフ(DAG)$G^*$を最小化しながら復元するよう要求される。
私たちの設定では、アドバイスとして$g^*$に関するサイド情報(例えば$g^*$と仮定されたdag $g$)が与えられます。
我々は、学習アルゴリズムが正しいときにアドバイスの恩恵を受けることができるかどうかを問うとともに、アドバイスが任意に悪い場合でも最悪の場合を保証する。
私たちの研究は、予測を伴うアルゴリズムの研究の活発化と同じ領域にあります。
アドバイスがDAG$G$であれば、介入コストが最大$O(\max\{1, \log \psi\})$倍の$O(\max\{1, \log \psi\})$を回復する適応探索アルゴリズムを設計する。
私たちの近似係数はアドバイスレス設定の最先端と一致します。
関連論文リスト
- Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。
複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
論文 参考訳（メタデータ） (2023-06-05T15:35:00Z) - On the Unlikelihood of D-Separation [69.62839677485087]
解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。
PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。
UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
論文 参考訳（メタデータ） (2023-03-10T00:11:18Z) - Streaming Algorithms for Learning with Experts: Deterministic Versus
Robust [62.98860182111096]
エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。
目標は最小限のコストで予測を行うことだ。
最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
論文 参考訳（メタデータ） (2023-03-03T04:39:53Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Beyond Bandit Feedback in Online Multiclass Classification [17.07011090727996]
学習者のフィードバックが任意の有向グラフによって決定されるような環境で,オンライン多クラス分類の問題について検討する。
任意のフィードバックグラフで動作する,初のオンラインマルチクラスアルゴリズムであるGappletronを紹介する。
論文 参考訳（メタデータ） (2021-06-07T13:22:30Z) - An Analysis of Frame-skipping in Reinforcement Learning [13.680685626360903]
多くのAtariコンソールゲームでは、強化学習アルゴリズムが$d > 1$で実行する場合、かなり優れたポリシーを提供する。
我々は、同じアクションの$d$長のシーケンスに対するこの選択の一般的な制限である「アクション-繰り返し」に焦点を当てる。
この損失は、より小さなタスクの地平線によって学習がもたらされた利益によって相殺される可能性がある。
論文 参考訳（メタデータ） (2021-02-07T04:59:09Z) - Intervention Efficient Algorithms for Approximate Learning of Causal
Graphs [22.401163479802094]
我々は、潜時の存在下で観察された変数の集合間の因果関係を学習する問題を研究する。
我々の目標は、介入の最小限の費用で、すべての因果関係や祖先関係の方向性を$G$で回収することです。
我々のアルゴリズムは効率的な介入設計と低コストな分離集合系の設計を組み合わせる。
論文 参考訳（メタデータ） (2020-12-27T17:08:46Z) - Contextual Bandits with Side-Observations [10.248045133793287]
ソーシャルネットワークを介して接続されたユーザの推薦アルゴリズムを設計するために,両腕にサイドオブザーブメントが存在する場合のコンテキスト帯について検討する。
既存の学習アルゴリズムの素直な応用は、$Oleft(Nlog Tright)$ regretとなり、そこでは$N$がユーザ数であることを示す。
論文 参考訳（メタデータ） (2020-06-06T19:34:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。