文の決定図

人工知能において、文決定図（SDD ）は、知識コンパイルでブール関数を表現するために使用される知識表現の一種です。SDDは、複数の変数に対する決定を一度に行えるようにすることで、影響力のある順序付き二分決定図（OBDD）表現の一般化と見なすことができます。OBDDと同様に、SDDは扱いやすいブール演算を可能にしながら、指数関数的に簡潔です。このため、SDDは知識コンパイルにおいて重要な表現となっています。^{[ 1 ]}

SDDは、変数ツリー（ vtree ）として知られる変数順序の一般化に関して定義されます。^{[ 2 ]}

SDDは、圧縮とトリミング（ ROBDDに類似）と呼ばれる追加の特性を満たす限り、ブール関数の標準的な表現であり、vtreeが与えられた場合に一意になります。^{[ 2 ]}

OBDDと同様に、論理積、論理和、否定などの演算を表現上で直接多項式時間で計算できるだけでなく、よりコンパクトになる可能性もある。^{[ 2 ]}また、多項式時間でのモデルカウントも可能になる。^{[ 3 ] [ 4 ]}

SDDはOBDDよりも指数関数的に簡潔であることが知られています。^{[ 5 ]}

SDD は、BDD よりも簡潔でありながら扱いやすい (重み付き) モデルカウント、扱いやすい否定、論理積、論理和をサポートしているため、ProbLog 2 システムでは確率論理プログラムのコンパイル対象として使用されています。 ^{[ 3 ]} SDD は確率分布のモデル化にも拡張されており、その文脈では確率的文決定図 (PSDD) として知られています。^{[ 6 ]}