論文の概要: Separation and Collapse of Equilibria Inequalities on AND-OR Trees without Shape Constraints

• arxiv url: http://arxiv.org/abs/2405.20138v2
• Date: Tue, 01 Oct 2024 09:11:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-02 16:32:50.519590
• Title: Separation and Collapse of Equilibria Inequalities on AND-OR Trees without Shape Constraints
• Title（参考訳）: 形状制約のないAND-OR木上の平衡不等式の分離と崩壊
• Authors: Fuki Ito, Toshio Suzuki,
• Abstract要約: 本稿では,AND-OR木計算の最悪の入力に対して最小のコストであるゼロエラーランダム化複雑性について検討する。 指向性アルゴリズムは、ランダム化された複雑さを達成することが知られている。 任意のAND-OR木に対して、ランダム化深度優先アルゴリズムは、方向性アルゴリズムと同じ平衡を持つことを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Herein, we investigate the zero-error randomized complexity, which is the least cost against the worst input, of AND-OR tree computation by imposing various restrictions on the algorithm to find the Boolean value of the root of that tree and no restrictions on the tree shape. When a tree satisfies a certain condition regarding its symmetry, directional algorithms proposed by Saks and Wigderson (1986), special randomized algorithms, are known to achieve the randomized complexity. Furthermore, there is a known example of a tree that is so unbalanced that no directional algorithm achieves the randomized complexity (Vereshchagin 1998). In this study, we aim to identify where deviations arise between the general randomized Boolean decision tree and its special case, directional algorithms. In this paper, we show that for any AND-OR tree, randomized depth-first algorithms, which form a broader class compared with directional algorithms, have the same equilibrium as that of the directional algorithms. Thus, we get the collapse result on equilibria inequalities that holds for an arbitrary AND-OR tree. This implies that there exists a case where even depth-first algorithms cannot be the fastest, leading to the separation result on equilibria inequality. Additionally, a new algorithm is introduced as a key concept for proof of the separation result.
• Abstract（参考訳）: 本稿では,その木根のブール値を求めるアルゴリズムに様々な制約を課し,木形に制約を加えることなく,最悪の入力に対して最小のコストであるゼロエラーランダム化複雑性について検討する。 木がその対称性に関する一定の条件を満たすとき、Saks and Wigderson (1986) によって提唱された方向アルゴリズム、特別なランダム化アルゴリズムはランダム化複雑性を達成するために知られている。 さらに、不均衡な木の例が知られているので、無作為化複雑性を達成する指向性アルゴリズムは存在しない(Vereshchagin 1998)。 本研究では,一般的なランダム化ブール決定木と,その特別な場合である指向性アルゴリズムとの偏差が生じるかを明らかにすることを目的とする。 本稿では,任意のAND-OR木に対して,指向性アルゴリズムと比較して広いクラスを形成するランダム化深度優先アルゴリズムが,指向性アルゴリズムと同じ平衡を持つことを示す。 したがって、任意のAND-OR木を保持する平衡不等式で崩壊結果を得る。 これは、たとえ深さ優先のアルゴリズムでも最も速くならない場合があり、平衡不等式における分離結果をもたらすことを意味する。 さらに,分離結果を証明するための重要な概念として,新しいアルゴリズムが導入された。

関連論文リスト

• On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
  ベルヌーイ報奨を伴う多腕バンディットにおける固定予算によるベストアーム識別の問題について検討する。 A/Bテスト問題としても知られる2つのアームの問題に対して,各アームを等しくサンプリングするアルゴリズムが存在しないことを証明した。
  論文  参考訳（メタデータ） (2023-08-23T08:38:53Z)
• HARRIS: Hybrid Ranking and Regression Forests for Algorithm Selection [75.84584400866254]
  両アプローチの強みを両アプローチの弱さを緩和しつつ組み合わせ, 特殊林を利用した新しいアルゴリズムセレクタを提案する。 HARRISの決定は、ハイブリッドランキングと回帰損失関数に基づいて最適化された木を作成する森林モデルに基づいている。
  論文  参考訳（メタデータ） (2022-10-31T14:06:11Z)
• Regularized impurity reduction: Accurate decision trees with complexity guarantees [20.170305081348328]
  本稿では,木複雑性の対数近似を保証する木推論アルゴリズムを提案する。 改良されたアルゴリズムは予測精度と木の複雑さのバランスが良好である。
  論文  参考訳（メタデータ） (2022-08-23T13:15:19Z)
• Unbiased and Efficient Sampling of Dependency Trees [0.0]
  ほとんどのツリーバンクは、すべての有効な依存ツリーがROOTノードから出てくる単一のエッジを持つ必要がある。 Zmigrodらは最近、単一ルート依存ツリーの分布から置き換えることなくサンプリングするアルゴリズムを提案している。 我々は、Wilson-RCを置換したサンプリングアルゴリズムが実際にバイアスを受けていることを示す。
  論文  参考訳（メタデータ） (2022-05-25T09:57:28Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples [75.32013242448151]
  ノードからの観測が独立しているが非識別的に分散ノイズによって破損した場合、Ising Treeモデルの学習を検討する。 Katiyarら。 (2020) は, 正確な木構造は復元できないが, 部分木構造を復元できることを示した。 統計的に堅牢な部分木回復アルゴリズムであるSymmetrized Geometric Averaging(SGA)を提案する。
  論文  参考訳（メタデータ） (2021-01-22T01:57:35Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Robust Estimation of Tree Structured Ising Models [20.224160348675422]
  我々は、異なる確率変数の符号が、おそらく不等で未知の確率で独立に反転するときに、イジングモデルを学習するタスクを考える。 しかし, この不同一性は, 葉ノードが近傍と位置を交換して形成する小さな同値類に限られる。
  論文  参考訳（メタデータ） (2020-06-10T01:32:45Z)
• Born-Again Tree Ensembles [9.307453801175177]
  ツリーアンサンブルは、様々な領域で優れた予測品質を提供するが、複数のツリーの同時使用により、アンサンブルの解釈可能性が低下する。 本研究では,その特徴空間全体において,与えられたツリーのアンサンブルと全く同じ振る舞いを再現する,最小サイズの1つの決定木を構築する過程について検討する。 このアルゴリズムは、実践的な関心のある多くのデータセットに対して最適な生長木を生成する。
  論文  参考訳（メタデータ） (2020-03-24T22:17:21Z)

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

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