論文の概要: On the Structure of Game Provenance and its Applications
- arxiv url: http://arxiv.org/abs/2410.05094v1
- Date: Mon, 7 Oct 2024 14:48:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-02 00:28:18.646656
- Title: On the Structure of Game Provenance and its Applications
- Title（参考訳）: ゲームプロヴァンスの構造とその応用について
- Authors: Shawn Bowers, Yilin Xia, Bertram Ludäscher,
- Abstract要約: ゲーム前駆体の微細粒構造について検討する。
我々は、新しい種類の証明をもたらす7つのエッジタイプ、すなわちポテンシャル、現実、プライマリを識別する。
- 参考スコア（独自算出の注目度）: 1.4064491732635236
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Provenance in databases has been thoroughly studied for positive and for recursive queries, then for first-order (FO) queries, i.e., having negation but no recursion. Query evaluation can be understood as a two-player game where the opponents argue whether or not a tuple is in the query answer. This game-theoretic approach yields a natural provenance model for FO queries, unifying how and why-not provenance. Here, we study the fine-grain structure of game provenance. A game $G=(V,E)$ consists of positions $V$ and moves $E$ and can be solved by computing the well-founded model of a single, unstratifiable rule: \[ \text{win}(X) \leftarrow \text{move}(X, Y), \neg \, \text{win}(Y). \] In the solved game $G^{\lambda}$, the value of a position $x\,{\in}\,V$ is either won, lost, or drawn. This value is explained by the provenance $\mathscr{P}$(x), i.e., certain (annotated) edges reachable from $x$. We identify seven edge types that give rise to new kinds of provenance, i.e., potential, actual, and primary, and demonstrate that "not all moves are created equal". We describe the new provenance types, show how they can be computed while solving games, and discuss applications, e.g., for abstract argumentation frameworks.
- Abstract（参考訳）: データベースの出現は、肯定的および再帰的なクエリのために徹底的に研究され、その後、一階述語(FO)クエリ、すなわち、否定するが再帰しないクエリに対して研究されている。
クエリ評価は、タプルがクエリ応答に含まれるかどうかを議論する2人プレイヤゲームとして理解することができる。
このゲーム理論のアプローチは、FOクエリの自然なプロファイランスモデルをもたらし、どのようにして、なぜプロファイランスではないのかを統一する。
本稿では,ゲーム前駆体の微細粒構造について検討する。
ゲーム $G=(V, E)$ は、位置 $V$ と移動 $E$ で構成され、単一で不安定な規則の確立したモデルを計算することで解決できる: \[ \text{win}(X) \leftarrow \text{move}(X, Y) \neg \, \text{win}(Y) 。
解決されたゲーム $G^{\lambda}$ では、位置 $x\,{\in}\,V$ の値は、勝ち、負け、引き分けのいずれかである。
この値は前置詞 $\mathscr{P}$(x) で説明され、すなわち、ある(注釈付き)エッジが$x$から到達可能である。
我々は、新しい種類の証明をもたらす7つのエッジタイプ、すなわちポテンシャル、現実、プライマリを識別し、「すべての動きが等しくなるわけではない」ことを示す。
本稿では,新しい証明型について述べるとともに,ゲーム解決時にどのように計算可能かを示し,抽象的な議論フレームワークのためのアプリケーション,例えばアプリケーションについて議論する。
関連論文リスト
- The Aldous--Lyons Conjecture II: Undecidability [3.8370118222043694]
調整された非局所ゲームである$G$が与えられた場合、$G$が特別な種類の完全戦略を持つ場合と、$G$のすべての戦略が完璧ではない場合とを区別することは決定不可能である。
共役紙 [BCLV24] に導入された還元を用いて、この不決定性の結果はアルドゥス=リヨン予想に対する負の答えを意味する。
論文 参考訳（メタデータ） (2024-12-30T22:59:56Z) - Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。
SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
論文 参考訳（メタデータ） (2024-06-03T17:56:58Z) - Distribution-Independent Regression for Generalized Linear Models with
Oblivious Corruptions [49.69852011882769]
一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。
本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。
これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
論文 参考訳（メタデータ） (2023-09-20T21:41:59Z) - Higher rank antipodality [2.7309692684728617]
一般確率論に動機づけられて、集合 $S$ in $mathbbRd$ はランク $k$ のエンファンティポッドであると言う。
この問題は, コンピュータ科学において, 完全ハッシュの発見に関する古典的な問題と結びつくことができることを示す。
論文 参考訳（メタデータ） (2023-07-31T17:15:46Z) - On Computing Probabilistic Explanations for Decision Trees [4.406418914680962]
十分な理由は、決定木を$T$とインスタンスを$x$とすると、決定を$T(x)$とします。
本稿では,決定木に対する$delta$sufficient-reasonsの計算複雑性について検討する。
決定木の構造的制約を識別し,SATソルバがこれらの問題に実際にどのように対処できるかを示す。
論文 参考訳（メタデータ） (2022-06-30T21:58:31Z) - Repeated Averages on Graphs [2.363388546004777]
我々は$frac(1-epsilon)2log2nlog n-O(n)$が$n$ノード上のすべての連結グラフに対する一般的な下界であることを証明する。
また、星、膨張星、ダンベル、サイクルなど、いくつかの重要なグラフの族に対して、$t_epsilon,1$の急激な等級も得られる。
論文 参考訳（メタデータ） (2022-05-09T20:18:31Z) - Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。
これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
論文 参考訳（メタデータ） (2022-02-03T18:18:28Z) - Nonlocal games with noisy maximally entangled states are decidable [5.076419064097734]
本稿では,非ローカルゲームの特別なクラスである$(G,psi)$について考察する。
ゲーム $(G,psi)$ では、プレイヤーは任意の数の $psi$ のコピーを共有することができる。
任意の精度で$omega*(G,psi)$を計算できる。
論文 参考訳（メタデータ） (2021-08-20T12:25:55Z) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-09T05:39:05Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。
このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文 参考訳（メタデータ） (2020-02-17T10:53:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。