疎にエンコードされた条件付き分布の互換性問題の複雑性について

Succinctlyエンコードされた条件付き分布における互換性問題の計算複雑性を調査。2つの条件付き分布から、それらと互換性のある結合分布が存在するかどうかを判定する問題の難しさを解析する。

• 機械学習における確率モデルのトレードオフを調査し、条件付き分布の互換性問題の計算複雑性を研究。
• 離散変数で確率テーブルとしてエンコードされた場合の互換性問題は計算可能だが、算術回路による簡潔なエンコードではINTRACTABLE（計算困難）であることを示す。
• 確率が全て非ゼロの場合、問題はco-NP完全であり、確率がゼロの場合、複数の互換性概念が存在し、PSPACE完全となるバージョンがある。
• 多項式階層が崩壊しないと仮定すると、互換性のある簡潔な条件付き分布でも、その同時分布が簡潔に表現できない例が存在する。
• これらの結果は、高次元設定（ニューラルネットワークモデルを含む）における確率的モデリングへの影響を議論する。