論文の概要: Faster Lifting for Ordered Domains with Predecessor Relations

• arxiv url: http://arxiv.org/abs/2507.19182v1
• Date: Fri, 25 Jul 2025 11:43:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-28 16:16:48.935835
• Title: Faster Lifting for Ordered Domains with Predecessor Relations
• Title（参考訳）: 先行関係を持つ順序付き領域の高速リフティング
• Authors: Kuncheng Zou, Jiahao Mai, Yonggang Zhang, Yuyi Wang, Ondřej Kuželka, Yuanhong Wang, Yi Chang,
• Abstract要約: 我々は、先行関係のある順序付き藩の利上げ推論を調査する。 従来の研究は、重み付けされた一階モデルの数え上げを通じてこの問題を調査してきた。 我々はこれらの関係を本質的に支援する新しいアルゴリズムを考案する。
• 参考スコア（独自算出の注目度）: 18.987335996076556
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate lifted inference on ordered domains with predecessor relations, where the elements of the domain respect a total (cyclic) order, and every element has a distinct (clockwise) predecessor. Previous work has explored this problem through weighted first-order model counting (WFOMC), which computes the weighted sum of models for a given first-order logic sentence over a finite domain. In WFOMC, the order constraint is typically encoded by the linear order axiom introducing a binary predicate in the sentence to impose a linear ordering on the domain elements. The immediate and second predecessor relations are then encoded by the linear order predicate. Although WFOMC with the linear order axiom is theoretically tractable, existing algorithms struggle with practical applications, particularly when the predecessor relations are involved. In this paper, we treat predecessor relations as a native part of the axiom and devise a novel algorithm that inherently supports these relations. The proposed algorithm not only provides an exponential speedup for the immediate and second predecessor relations, which are known to be tractable, but also handles the general k-th predecessor relations. The extensive experiments on lifted inference tasks and combinatorics math problems demonstrate the efficiency of our algorithm, achieving speedups of a full order of magnitude.
• Abstract（参考訳）: 我々は、各領域の要素が全(周期的な)順序を尊重し、各要素が異なる(時計回りに)前駆体を持つような前駆的関係を持つ順序付き領域の昇降推論を調査する。 従来の研究は、与えられた一階述語論理文に対するモデルの重み付け和を有限領域上で計算する重み付けされた一階述語モデルカウント(WFOMC)を用いてこの問題を探索してきた。 WFOMCでは、順序制約は通常、文中に二項述語を導入して、ドメイン要素に線形順序を課す線形順序公理によって符号化される。 即時および第二前の関係は、線形順序述語によって符号化される。 線形順序公理を持つ WFOMC は理論上は計算可能であるが、既存のアルゴリズムは、特に前の関係が関係している場合、実践的な応用に苦慮している。 本稿では,先行関係を公理の原点として扱い,これらの関係を本質的に支持する新しいアルゴリズムを考案する。 提案したアルゴリズムは、抽出可能であることが知られている即時および第2前の関係に対して指数的な高速化を提供するだけでなく、一般的なk番目の前の関係も扱う。 昇降推論タスクとコンビネータ数学の数学問題に関する広範な実験は、我々のアルゴリズムの効率を実証し、全桁のスピードアップを達成した。

関連論文リスト

• Higher-Order Pattern Unification Modulo Similarity Relations [0.0]
  高階理論とファジィ論理の組み合わせは意思決定に有用である。 我々は、よく確立された2つのコンポーネントと計算に精通したコンポーネントを統合することを目的とした、より簡単なアプローチを採用する。 本稿では,これらの類似性関係を変調する高次パターンの統一アルゴリズムを提案し,その終了,健全性,完全性を証明した。
  論文  参考訳（メタデータ） (2025-07-17T15:18:22Z)
• Sequential-Parallel Duality in Prefix Scannable Models [68.39855814099997]
  近年では Gated Linear Attention (GLA) や Mamba など様々なモデルが開発されている。 ニアコンスタント時間並列評価と線形時間、定数空間シーケンシャル推論をサポートするニューラルネットワークモデルの全クラスを特徴付けることができるだろうか?
  論文  参考訳（メタデータ） (2025-06-12T17:32:02Z)
• Preordering: A hybrid of correlation clustering and partial ordering [2.7651063843287718]
  プレオーダーは、$-1,0,1$の値であってもNPハードのままであることを示す。 線形時間 4$-approximation アルゴリズムと局所探索手法を導入する。
  論文  参考訳（メタデータ） (2025-02-20T13:12:03Z)
• Synthesising Recursive Functions for First-Order Model Counting: Challenges, Progress, and Conjectures [12.47276164048813]
  1次モデルカウント(英: First-order model counting、FOMC)は、有限領域の1次論理において文のモデルを数えるように要求する計算問題である。 私たちは、典型的にドメイン再帰に伴う制限を緩和し、サイクルを含むかもしれない有向グラフを扱う。 これらの改良により、アルゴリズムはそれまで到達範囲を超えていた問題を数えるための効率的な解を見つけることができる。
  論文  参考訳（メタデータ） (2023-06-07T06:49:01Z)
• Weighted First Order Model Counting with Directed Acyclic Graph Axioms [7.766921168069532]
  多くのSRLにおける確率的推論と学習は、重み付き第一モデルカウント(WFOMC)に還元できる WFOMCは難解であることが知られている(mathrm#P$ complete)。 我々は,DAG(Directed Acyclic Graph)を除外したフラグメント$mathrmC2$,すなわち公理DAGを表す公理化グラフがドメインリフト可能であることを示す。
  論文  参考訳（メタデータ） (2023-02-20T08:35:13Z)
• General ordering theorem [0.0]
  一般順序理論(GOT)を証明し,任意の順序のペア間の関係を確立する。 一般(演算的)可換関係を満たす作用素に作用することを示す。 注目すべきことに、この定理はこれらの2つの定理の間の公式な関係を確立し、現在知られている悪名高い複雑な定理とは異なり、それらに対してコンパクトな表現を提供する。
  論文  参考訳（メタデータ） (2023-02-02T17:49:35Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。 マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。 本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
  論文  参考訳（メタデータ） (2022-01-25T00:10:03Z)
• Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time [46.31710224483631]
  既存の定数係数近似のスケッチ次元における対数的要素について、Nelson and Nguyen (FOCS, 2013) の主な開問題を回避する方法を示す。 私たちが使用している重要なテクニックは、不確実性原理と抽出子に基づくIndykの明示的なマッピングです。 ランク計算と列の線形独立部分集合の探索という基本的な問題に対して、我々のアルゴリズムはCheung, Kwok, Lau (JACM, 2013)を改良し、それぞれ定数係数と$log(n)$-factorの範囲内で最適である。
  論文  参考訳（メタデータ） (2021-07-16T19:34:10Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。 文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。 我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
  論文  参考訳（メタデータ） (2021-06-01T19:51:55Z)
• Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria [121.36609493711292]
  大規模2プレーヤワイドフォームゲームの計算平衡問題に対する反復的な一階法の適用について検討する。 正則化器を用いて一階法をインスタンス化することにより、相関平衡と元アンティー座標のチーム平衡を計算するための最初の加速一階法を開発する。
  論文  参考訳（メタデータ） (2021-05-27T06:10:24Z)
• Extracting N-ary Cross-sentence Relations using Constrained Subsequence Kernel [36.86738081453646]
  本稿では,関係が文内関係よりも一般的である関係抽出タスクの新たな定式化を提案する。 このような関係のインスタンスを特徴付ける新しいシーケンス表現を提案する。 バイオメディカルドメインとジェネラルドメインという2つの領域にまたがる3つのデータセットに対するアプローチを評価した。
  論文  参考訳（メタデータ） (2020-06-15T07:23:58Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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