論文の概要: Adaptive Monte Carlo Search for Conjecture Refutation in Graph Theory

• arxiv url: http://arxiv.org/abs/2306.07956v2
• Date: Tue, 27 Jun 2023 21:20:41 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-29 17:22:15.536974
• Title: Adaptive Monte Carlo Search for Conjecture Refutation in Graph Theory
• Title（参考訳）: アダプティブモンテカルロ探索によるグラフ理論における予想の難解化
• Authors: Valentino Vito and Lim Yohanes Stefanus
• Abstract要約: 帰納的解法アルゴリズムは、これらの予想に対する反例を探すことによって、予想を否定しようとする。 本研究では,アダプティブモンテカルロ探索 (AMCS) アルゴリズムと呼ばれる新しい予測拡散アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph theory is an interdisciplinary field of study that has various applications in mathematical modeling and computer science. Research in graph theory depends on the creation of not only theorems but also conjectures. Conjecture-refuting algorithms attempt to refute conjectures by searching for counterexamples to those conjectures, often by maximizing certain score functions on graphs. This study proposes a novel conjecture-refuting algorithm, referred to as the adaptive Monte Carlo search (AMCS) algorithm, obtained by modifying the Monte Carlo tree search algorithm. Evaluated based on its success in finding counterexamples to several graph theory conjectures, AMCS outperforms existing conjecture-refuting algorithms. The algorithm is further utilized to refute six open conjectures, two of which were chemical graph theory conjectures formulated by Liu et al. in 2021 and four of which were formulated by the AutoGraphiX computer system in 2006. Finally, four of the open conjectures are strongly refuted by generalizing the counterexamples obtained by AMCS to produce a family of counterexamples. It is expected that the algorithm can help researchers test graph-theoretic conjectures more effectively.
• Abstract（参考訳）: グラフ理論は学際的な研究分野であり、数学のモデリングや計算機科学に様々な応用がある。 グラフ理論の研究は、定理だけでなく予想の作成にも依存する。 Conjecture-refutingアルゴリズムは、これらの予想に対する反例を探し、しばしばグラフ上の特定のスコア関数を最大化することによって、予想を否定しようとする。 本研究では,適応モンテカルロ探索法 (adaptive monte carlo search, amcs) と呼ばれる,モンテカルロ木探索法を改良した新しい予想再帰アルゴリズムを提案する。 いくつかのグラフ理論の予想に対する反例を見つけることに成功して評価され、AMCSは既存の予想拡散アルゴリズムより優れている。 このアルゴリズムは、2021年にLouらによって定式化された化学グラフ理論の予想と、2006年にAutoGraphiXコンピュータシステムによって定式化された4つの化学グラフ理論の予想である6つの開予想を論じるためにさらに利用された。 最後に、開予想のうち4つは、AMCSによって得られた反例を一般化して反例の族を生成することで強く反証される。 このアルゴリズムは、研究者がより効果的にグラフ理論予想をテストするのに役立つことが期待されている。

関連論文リスト

• Causal Discovery over High-Dimensional Structured Hypothesis Spaces with Causal Graph Partitioning [0.742246975663779]
  因果発見により、一般化された方法で因果関係と効果関係の集合として機構を推測することができる。 提案アルゴリズムは,生物学的に調整された合成ネットワークやネットワークに対して,最大104ドルの変数に対して,同等の精度と解法を実現できることを示す。
  論文  参考訳（メタデータ） (2024-06-10T15:08:14Z)
• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。 我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
  論文  参考訳（メタデータ） (2024-03-21T11:57:16Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。 グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。 低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
  論文  参考訳（メタデータ） (2023-03-10T21:18:34Z)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  本稿では,Robins と Monro のセミナル近似フレームワークを一般化し拡張するリーマンアルゴリズムの族を提案する。 ユークリッドのそれと比較すると、リーマンのアルゴリズムは多様体上の大域線型構造が欠如しているため、はるかに理解されていない。 ユークリッド・ロビンス=モンロスキームの既存の理論を反映し拡張するほぼ確実な収束結果の一般的なテンプレートを提供する。
  論文  参考訳（メタデータ） (2022-06-14T12:30:11Z)
• From Width-Based Model Checking to Width-Based Automated Theorem Proving [8.131328180219962]
  本稿では,ワイドベースモデルチェックアルゴリズムをグラフ理論の妥当性を検証できるアルゴリズムに変換するための一般的なフレームワークを提案する。 我々のフレームワークはモジュラーであり、木幅や斜め幅を含むグラフのいくつかのよく研究された幅測度に対して適用することができる。
  論文  参考訳（メタデータ） (2022-05-23T01:56:52Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。 我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
  論文  参考訳（メタデータ） (2021-10-12T02:21:30Z)
• Graphon based Clustering and Testing of Networks: Algorithms and Theory [11.3700474413248]
  ネットワークに価値のあるデータは、幅広いアプリケーションで遭遇し、学習の課題を提起する。 本稿では,2つのクラスタリングアルゴリズムについて述べる。 さらに、グラフ2サンプルテスト問題に対する提案した距離の適用性について検討する。
  論文  参考訳（メタデータ） (2021-10-06T13:14:44Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
  論文  参考訳（メタデータ） (2021-06-09T08:05:36Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
  直交群 $O(d)$ 上の幾何駆動最適化アルゴリズムの新しいクラスを示す。 提案手法は,深層,畳み込み,反復的なニューラルネットワーク,強化学習,フロー,メトリック学習など,機械学習のさまざまな分野に適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-03-30T15:37:50Z)

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

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