Fugu-MT 論文翻訳(概要): Computing a partition function of a generalized pattern-based energy over a semiring

論文の概要: Computing a partition function of a generalized pattern-based energy over a semiring

arxiv url: http://arxiv.org/abs/2305.17526v1
Date: Sat, 27 May 2023 16:53:10 GMT
ステータス: 処理完了
システム内更新日: 2023-05-30 18:38:04.243907
Title: Computing a partition function of a generalized pattern-based energy over a semiring
Title（参考訳）: 半環上の一般化パターンベースエネルギーの分配関数の計算
Authors: Rustem Takhanov
Abstract要約: 制約言語 $Gamma$ は述語の特徴関数 0,1$ の値を持つ。一般化されたパターンベースポテンシャルの最小化は $mathcal O(|V|cdot |D|2 cdot |overlineGammacap|2 )$ time で実現できることを示す。
参考スコア（独自算出の注目度）: 6.028247638616059
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Valued constraint satisfaction problems with ordered variables (VCSPO) are a special case of Valued CSPs in which variables are totally ordered and soft constraints are imposed on tuples of variables that do not violate the order. We study a restriction of VCSPO, in which soft constraints are imposed on a segment of adjacent variables and a constraint language $\Gamma$ consists of $\{0,1\}$-valued characteristic functions of predicates. This kind of potentials generalizes the so-called pattern-based potentials, which were applied in many tasks of structured prediction. For a constraint language $\Gamma$ we introduce a closure operator, $ \overline{\Gamma^{\cap}}\supseteq \Gamma$, and give examples of constraint languages for which $|\overline{\Gamma^{\cap}}|$ is small. If all predicates in $\Gamma$ are cartesian products, we show that the minimization of a generalized pattern-based potential (or, the computation of its partition function) can be made in ${\mathcal O}(|V|\cdot |D|^2 \cdot |\overline{\Gamma^{\cap}}|^2 )$ time, where $V$ is a set of variables, $D$ is a domain set. If, additionally, only non-positive weights of constraints are allowed, the complexity of the minimization task drops to ${\mathcal O}(|V|\cdot |\overline{\Gamma^{\cap}}| \cdot |D| \cdot \max_{\rho\in \Gamma}\|\rho\|^2 )$ where $\|\rho\|$ is the arity of $\rho\in \Gamma$. For a general language $\Gamma$ and non-positive weights, the minimization task can be carried out in ${\mathcal O}(|V|\cdot |\overline{\Gamma^{\cap}}|^2)$ time. We argue that in many natural cases $\overline{\Gamma^{\cap}}$ is of moderate size, though in the worst case $|\overline{\Gamma^{\cap}}|$ can blow up and depend exponentially on $\max_{\rho\in \Gamma}\|\rho\|$.
Abstract（参考訳）: 順序変数(VCSPO)による値制約満足問題は、変数が完全に順序づけられ、順序に反しない変数のタプルにソフト制約が課される特別なケースである。本稿では、隣接する変数のセグメントにソフト制約を課し、制約言語$\Gamma$は述語の特徴関数の$\{0,1\}$値を持つVCSPOの制限について検討する。この種のポテンシャルは、構造化予測の多くのタスクで適用されたいわゆるパターンベースポテンシャルを一般化する。制約言語$\Gamma$に対して、クロージャ演算子、$ \overline{\Gamma^{\cap}}\supseteq \Gamma$を導入し、$|\overline{\Gamma^{\cap}}|$が小さい制約言語の例を示します。もし$\gamma$ の全ての述語がデカルト積であれば、一般化されたパターンベースのポテンシャル(あるいはその分割関数の計算)の最小化は${\mathcal o}(|v|\cdot |d|^2 \cdot |\overline{\gamma^{\cap}}|^2 )$ time、ただし $v$ は変数の集合であり、$d$ は整域集合である。さらに、制約の非正の重みのみを許せば、最小化タスクの複雑さは${\mathcal O}(|V|\cdot |\overline{\Gamma^{\cap}}| \cdot |D| \cdot \max_{\rho\in \Gamma}\|\rho\|^2 )$に減少する。一般言語 $\Gamma$ および非正重みに対して、最小化タスクは ${\mathcal O}(|V|\cdot |\overline{\Gamma^{\cap}}|^2)$ time で実行することができる。多くの自然の場合、$\overline{\Gamma^{\cap}}$は適度の大きさであるが、最悪の場合は$|\overline{\Gamma^{\cap}}|$は爆発し、指数関数的に$\max_{\rho\in \Gamma}\|\rho\|$に依存する。

関連論文リスト

The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
Partially Unitary Learning [0.0]
ヒルベルト空間の最適写像 $IN$ of $left|psirightrangle$ と $OUT$ of $left|phirightrangle$ が提示される。この最適化問題の大域的な最大値を求める反復アルゴリズムを開発した。
論文参考訳（メタデータ） (2024-05-16T17:13:55Z)
On the quantum Guerra-Morato Action Functional [0.0]
トーラス上のmathbbR$に対して滑らかなポテンシャル W:mathrmTn が与えられたとき、量子ゲラ・モラート作用函数はスモールスキップによって与えられる。臨界解の第二変量に対する表現は、スモールスキップによって与えられることを示す。
論文参考訳（メタデータ） (2024-03-09T10:30:21Z)
Ground state solution of a Kirchhoff type equation with singular potentials [0.0]
E(b)=infBigmathcalE_b(u),|, uin H1(R2), |u|_L2=1Big,$ here $mathcalE_b(u)$は$mathcalE_b(u)= int_R2で定義されるキルヒホフエネルギー関数である。
論文参考訳（メタデータ） (2022-12-15T16:40:48Z)
Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文参考訳（メタデータ） (2022-02-10T16:10:41Z)
Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
論文参考訳（メタデータ） (2022-01-24T17:33:19Z)
Simplest non-additive measures of quantum resources [77.34726150561087]
我々は $cal E(rhootimes N) = E(e;N) ne Ne$ で説明できる測度について研究する。
論文参考訳（メタデータ） (2021-06-23T20:27:04Z)
Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文参考訳（メタデータ） (2021-05-17T16:40:48Z)
Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文参考訳（メタデータ） (2021-02-15T08:16:51Z)
Optimal Strategies for Graph-Structured Bandits [0.0]
Bernoulli $!=!(nu_a,b)_a in mathcalA, b in mathcalB$ with means $(mu_a,b)_a in mathcalA, b in mathcalB$ with means $(mu_a,b)_a
論文参考訳（メタデータ） (2020-07-07T06:27:51Z)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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