論文の概要: Variable Shift SDD: A More Succinct Sentential Decision Diagram
- arxiv url: http://arxiv.org/abs/2004.02502v1
- Date: Mon, 6 Apr 2020 09:18:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-16 07:22:40.370487
- Title: Variable Shift SDD: A More Succinct Sentential Decision Diagram
- Title（参考訳）: 可変シフトSDD: より簡潔な意味決定図
- Authors: Kengo Nakamura, Shuhei Denzumi, Masaaki Nishino
- Abstract要約: Sentential Decision Diagram (SDD) はブール関数の抽出可能な表現である。
可変シフトSDD(VS-SDD)という,より簡潔なSDD変種を提案する。
我々は,VS-SDDがSDDよりも大きくなることはなく,VS-SDDのサイズがSDDよりも指数関数的に小さいケースがあることを示した。
- 参考スコア（独自算出の注目度）: 10.91026094237478
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Sentential Decision Diagram (SDD) is a tractable representation of
Boolean functions that subsumes the famous Ordered Binary Decision Diagram
(OBDD) as a strict subset. SDDs are attracting much attention because they are
more succinct than OBDDs, as well as having canonical forms and supporting many
useful queries and transformations such as model counting and Apply operation.
In this paper, we propose a more succinct variant of SDD named Variable Shift
SDD (VS-SDD). The key idea is to create a unique representation for Boolean
functions that are equivalent under a specific variable substitution. We show
that VS-SDDs are never larger than SDDs and there are cases in which the size
of a VS-SDD is exponentially smaller than that of an SDD. Moreover, despite
such succinctness, we show that numerous basic operations that are supported in
polytime with SDD are also supported in polytime with VS-SDD. Experiments
confirm that VS-SDDs are significantly more succinct than SDDs when applied to
classical planning instances, where inherent symmetry exists.
- Abstract（参考訳）: Sentential Decision Diagram (SDD) はブール関数の抽出可能な表現であり、有名な順序付き二項決定図(OBDD)を厳密な部分集合として仮定する。
SDDは、OBDDよりも簡潔で、標準形式を持ち、モデルカウントやApply操作といった多くの有用なクエリや変換をサポートするため、多くの注目を集めています。
本稿では,VS-SDD (Variable Shift SDD) と呼ばれるSDDのより簡潔なバリエーションを提案する。
重要なアイデアは、特定の変数置換の下で等価であるブール関数のユニークな表現を作ることである。
我々は,VS-SDDがSDDよりも大きくなることはなく,VS-SDDのサイズがSDDよりも指数関数的に小さいケースがあることを示した。
また,その簡潔さにも拘わらず,VS-SDDでポリ時間にサポートされた基本操作が,VS-SDDでサポートされた。
実験により、VS-SDDは、固有の対称性が存在する古典的な計画例に適用した場合、SDDよりもはるかに簡潔であることが確認された。
関連論文リスト
- Add-SD: Rational Generation without Manual Reference [83.01349699374524]
命令ベースのオブジェクト付加パイプラインであるAdd-SDを導入し、オブジェクトを合理的なサイズと位置でリアルなシーンに自動的に挿入する。
我々の研究は、多数の指示されたイメージペアを含むデータセットの提案、合理的な生成のための拡散モデルの微調整、下流タスクを増強するための合成データの生成の3つの側面に寄与する。
論文 参考訳（メタデータ） (2024-07-30T17:58:13Z) - Canonical Decision Diagrams Modulo Theories [0.19285000127136376]
決定図は命題公式を表現する強力なツールである。
いくつかの形式(例えば OBDD や SDD など)は標準的であり、(原子リスト上の与えられた条件の下では)公式の同値類を単項的に表す。
DDをSMTレベルに活用する新しい手法を提案する。
論文 参考訳（メタデータ） (2024-04-25T09:34:49Z) - VSCode: General Visual Salient and Camouflaged Object Detection with 2D Prompt Learning [104.74705190239119]
4つのSODタスクと3つのCODタスクに共同で対処する新しい2Dプロンプト学習モデルであるVSCodeを紹介する。
基礎モデルとしてVSTを利用し、エンコーダ・デコーダアーキテクチャ内で2Dプロンプトを導入し、ドメインとタスク固有の知識を学習する。
VSCodeは、6つのタスクで26のデータセットで最先端のメソッドのパフォーマンスを向上する。
論文 参考訳（メタデータ） (2023-11-25T12:34:02Z) - Variants of Tagged Sentential Decision Diagrams [6.891570850234007]
最近提案されたブール関数の標準形式、すなわちタグ付き逐次決定図(TSDD)は、標準およびゼロ抑圧トリミングルールの両方を利用する。
本稿では,トリミング規則の順序を逆転することで,標準TSDD(STSDD)と呼ぶTSDDの変種について述べる。
次に、STSDDの正準性を証明し、TSDD上でのバイナリ演算のアルゴリズムを示す。
論文 参考訳（メタデータ） (2023-11-16T12:29:25Z) - Exploiting Asymmetry in Logic Puzzles: Using ZDDs for Symbolic Model
Checking Dynamic Epistemic Logic [0.0]
我々は、動的疫学論理で使用されるクリプキモデルを象徴的に符号化するためにZDDを使用する。
BDDを適切なZDDに置き換えることで、メモリ使用量を大幅に削減できることを示す。
これはZDDがマルチエージェントシステムのモデル検査に有用なツールであることを示唆している。
論文 参考訳（メタデータ） (2023-07-11T07:13:09Z) - Weighted Context-Free-Language Ordered Binary Decision Diagrams [9.483290784772011]
本稿では,emphWeighted Context-Free-Language Ordered BDDs(WCFLOBDDs)と呼ばれる新しいデータ構造を提案する。
一部の関数では、WCFLOBDDはWBDDよりも指数関数的に簡潔である。
我々は、量子回路シミュレーションにWCFLOBDDを適用し、特定のベンチマークでWBDDよりも優れた性能を発揮することを発見した。
論文 参考訳（メタデータ） (2023-05-23T02:16:52Z) - Belief Revision in Sentential Decision Diagrams [126.94029917018733]
本研究では,Dalリビジョンの構文的特徴化に基づくSDDの一般的なリビジョンアルゴリズムを開発する。
ランダムに生成した知識ベースを用いた予備実験は、SDDフォーマリズム内で直接リビジョンを行う利点を示している。
論文 参考訳（メタデータ） (2022-01-20T11:01:41Z) - Meta-Learning with Variational Semantic Memory for Word Sense
Disambiguation [56.830395467247016]
メタ学習環境におけるWSDのセマンティックメモリモデルを提案する。
我々のモデルは階層的変動推論に基づいており、ハイパーネットワークを介して適応的なメモリ更新ルールを組み込んでいる。
極めて少ないシナリオでの効果的な学習を支援するために,本モデルがWSDで最先端の技術を数ショットで実現していることを示す。
論文 参考訳（メタデータ） (2021-06-05T20:40:01Z) - Simple and Effective Prevention of Mode Collapse in Deep One-Class
Classification [93.2334223970488]
深部SVDDにおける超球崩壊を防止するための2つの正則化器を提案する。
第1の正則化器は、標準のクロスエントロピー損失によるランダムノイズの注入に基づいている。
第2の正規化器は、小さすぎるとミニバッチ分散をペナライズする。
論文 参考訳（メタデータ） (2020-01-24T03:44:47Z) - From Open Set to Closed Set: Supervised Spatial Divide-and-Conquer for
Object Counting [84.23313278891568]
本研究では,空間分割コンカレントネットワーク(SS-DCNet)の概念を導入し,オープンセットカウントをクローズドセット問題に変換する。
SS-DCNetはクローズドセットからしか学べないが、S-DCを介してオープンセットシナリオにうまく一般化できる。
本稿では, 理論解析と玩具データの制御実験を行い, クローズド・セット・モデリングがなぜ意味を持つのかを実証する。
論文 参考訳（メタデータ） (2020-01-07T04:36:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。