Fugu-MT 論文翻訳(概要): Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes

論文の概要: Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes

arxiv url: http://arxiv.org/abs/2111.14148v1
Date: Sun, 28 Nov 2021 14:08:25 GMT
ステータス: 処理完了
システム内更新日: 2021-11-30 19:04:40.907157
Title: Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes
Title（参考訳）: 行列点過程の積に対する正規化定数の計算複雑性
Authors: Naoto Ohsaka and Tatsuya Matsuoka
Abstract要約: 正規化定数の計算における計算複雑性について検討する。例えば、$sum_Sdet(bf A_S,S)p$は、すべての(固定された)正の偶数に対して、$p$ が UP-hard で Mod$_3$P-hard であることを示す。
参考スコア（独自算出の注目度）: 12.640283469603357
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider the product of determinantal point processes (DPPs), a point process whose probability mass is proportional to the product of principal minors of multiple matrices, as a natural, promising generalization of DPPs. We study the computational complexity of computing its normalizing constant, which is among the most essential probabilistic inference tasks. Our complexity-theoretic results (almost) rule out the existence of efficient algorithms for this task unless the input matrices are forced to have favorable structures. In particular, we prove the following: (1) Computing $\sum_S\det({\bf A}_{S,S})^p$ exactly for every (fixed) positive even integer $p$ is UP-hard and Mod$_3$P-hard, which gives a negative answer to an open question posed by Kulesza and Taskar. (2) $\sum_S\det({\bf A}_{S,S})\det({\bf B}_{S,S})\det({\bf C}_{S,S})$ is NP-hard to approximate within a factor of $2^{O(|I|^{1-\epsilon})}$ or $2^{O(n^{1/\epsilon})}$ for any $\epsilon>0$, where $|I|$ is the input size and $n$ is the order of the input matrix. This result is stronger than the #P-hardness for the case of two matrices derived by Gillenwater. (3) There exists a $k^{O(k)}n^{O(1)}$-time algorithm for computing $\sum_S\det({\bf A}_{S,S})\det({\bf B}_{S,S})$, where $k$ is the maximum rank of $\bf A$ and $\bf B$ or the treewidth of the graph formed by nonzero entries of $\bf A$ and $\bf B$. Such parameterized algorithms are said to be fixed-parameter tractable. These results can be extended to the fixed-size case. Further, we present two applications of fixed-parameter tractable algorithms given a matrix $\bf A$ of treewidth $w$: (4) We can compute a $2^{\frac{n}{2p-1}}$-approximation to $\sum_S\det({\bf A}_{S,S})^p$ for any fractional number $p>1$ in $w^{O(wp)}n^{O(1)}$ time. (5) We can find a $2^{\sqrt n}$-approximation to unconstrained MAP inference in $w^{O(w\sqrt n)}n^{O(1)}$ time.
Abstract（参考訳）: 行列点過程(Determinantal point process, DPPs)の積は、確率質量が複数の行列の主部分の積に比例する点過程であり、DPPの自然な有望な一般化である。本稿では,その正規化定数を計算する計算複雑性について検討する。私たちの複雑性理論的な結果は(ほとんど)、入力行列が好ましい構造を強制されない限り、このタスクのための効率的なアルゴリズムの存在を除外します。特に、(1)すべての(固定)正の偶数整数$p$がアップハードで mod$_3$p-hard に対して、$\sum_s\det({\bf a}_{s,s})^p$を正確に計算すると、kulesza と taskar によってなされるオープン質問に対する否定的な答えが得られる。 2)$\sum_s\det({\bf a}_{s,s})\det({\bf b}_{s,s})\det({\bf c}_{s,s})$は$2^{o(|i|^{1-\epsilon})}$または$2^{o(n^{1/\epsilon})}$任意の$\epsilon>0$、ただし$|i|$は入力サイズ、$n$は入力行列の順序である。この結果は、ギレンウォーター由来の2つの行列の場合の#P硬度よりも強い。 (3) $\sum_s\det({\bf a}_{s,s})\det({\bf b}_{s,s})$を計算するための$k^{o(k)}n^{o(1)}$-timeアルゴリズムがあり、ここで$k$は$\bf a$と$\bf b$の最大ランクである。このようなパラメータ化アルゴリズムは固定パラメータ扱い可能であると言われている。これらの結果は固定サイズのケースに拡張できる。さらに、行列 $\bf A$ of treewidth $w$: (4)$2^{\frac{n}{2p-1}}$-approximation to $\sum_S\det({\bf A}_{S,S})^p$ for any fractional number $p>1$ in $w^{O(wp)}n^{O(1)}$ time を計算できる。 (5)$w^{o(w\sqrt n)}n^{o(1)}$ time で制約のない写像推論に近似する 2^{\sqrt n}$-approximation を見つけることができる。

論文の概要: Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes

関連論文リスト