論文の概要: Circuit Complexity of Visual Search
- arxiv url: http://arxiv.org/abs/2107.00223v1
- Date: Thu, 1 Jul 2021 05:37:53 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-03 00:57:51.719733
- Title: Circuit Complexity of Visual Search
- Title(参考訳): 視覚探索の回路複雑性
- Authors: Kei Uchizawa and Haruki Abe
- Abstract要約: 回路複雑性のレンズによる特徴の計算硬度と共同探索について検討する。
我々はニューラルネットワークのモデルとしてしきい値回路または離散回路を用いる。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study computational hardness of feature and conjunction search through the
lens of circuit complexity. Let $x = (x_1, ... , x_n)$ (resp., $y = (y_1, ... ,
y_n)$) be Boolean variables each of which takes the value one if and only if a
neuron at place $i$ detects a feature (resp., another feature). We then simply
formulate the feature and conjunction search as Boolean functions ${\rm
FTR}_n(x) = \bigvee_{i=1}^n x_i$ and ${\rm CONJ}_n(x, y) = \bigvee_{i=1}^n x_i
\wedge y_i$, respectively. We employ a threshold circuit or a discretized
circuit (such as a sigmoid circuit or a ReLU circuit with discretization) as
our models of neural networks, and consider the following four computational
resources: [i] the number of neurons (size), [ii] the number of levels (depth),
[iii] the number of active neurons outputting non-zero values (energy), and
[iv] synaptic weight resolution (weight).
We first prove that any threshold circuit $C$ of size $s$, depth $d$, energy
$e$ and weight $w$ satisfies $\log rk(M_C) \le ed (\log s + \log w + \log n)$,
where $rk(M_C)$ is the rank of the communication matrix $M_C$ of a
$2n$-variable Boolean function that $C$ computes. Since ${\rm CONJ}_n$ has rank
$2^n$, we have $n \le ed (\log s + \log w + \log n)$. Thus, an exponential
lower bound on the size of even sublinear-depth threshold circuits exists if
the energy and weight are sufficiently small. Since ${\rm FTR}_n$ is computable
independently of $n$, our result suggests that computational capacity for the
feature and conjunction search are different. We also show that the inequality
is tight up to a constant factor if $ed = o(n/ \log n)$. We next show that a
similar inequality holds for any discretized circuit. Thus, if we regard the
number of gates outputting non-zero values as a measure for sparse activity,
our results suggest that larger depth helps neural networks to acquire sparse
activity.
- Abstract(参考訳): 回路複雑性のレンズによる特徴の計算硬度と共同探索について検討する。
x = (x_1, ... , x_n)$ (resp., $y = (y_1, ... , y_n)$) をブール変数とする。
次に、ブール関数 ${\rm FTR}_n(x) = \bigvee_{i=1}^n x_i$ と ${\rm CONJ}_n(x, y) = \bigvee_{i=1}^n x_i \wedge y_i$ として特徴と共同探索を単純に定式化する。
我々は、ニューラルネットワークのモデルとして閾値回路または離散回路(シグミド回路やReLU回路など)を用い、[i]ニューロン数(サイズ)、[ii]レベル数(深さ)、[iii]非ゼロ値(エネルギー)を出力する活動ニューロン数(エネルギー)、[iv]シナプス重み分解(重み)の4つの計算資源を考察した。
まず、任意のしきい値回路$C$ of size $s$, depth $d$, energy $e$ and weight $w$ satisfies $\log rk(M_C) \le ed (\log s + \log w + \log n)$, where $rk(M_C)$ is the rank of the communication matrix $M_C$ of a $2n$-variable Boolean function that which $C$。
${\rm CONJ}_n$ のランクは 2^n$ であるため、$n \le ed (\log s + \log w + \log n)$ となる。
したがって、エネルギーと重量が十分に小さい場合、偶数直線深度しきい値回路のサイズに対する指数的な下界が存在する。
また,${\rm FTR}_n$は$n$とは独立に計算可能であることから,特徴量と協調探索の計算能力が異なることが示唆された。
また、不等式は$ed = o(n/ \log n)$ の場合、定数係数まで厳密であることを示す。
次に、同様の不等式が任意の離散回路に対して成り立つことを示す。
したがって、非ゼロ値を出力するゲートの数をスパースアクティビティの指標とすると、より深い深さがニューラルネットワークのスパースアクティビティ獲得に役立つことが示唆される。
関連論文リスト
- Polylogarithmic-depth controlled-NOT gates without ancilla qubits [0.0]
制御された演算は量子アルゴリズムの基本的な構成要素である。
n$-control-NOT ゲートを任意の単一量子ビットと CNOT ゲートに分解することは重要な作業である。
論文 参考訳(メタデータ) (2023-12-20T17:23:11Z) - On the Pauli Spectrum of QAC0 [2.5602836891933074]
我々は、$mathsfQAC0$のパウリスペクトルが低度濃度を満たすと推測する。
我々はこの予想を、少なくとも$nO(1/d)$補助量子ビットを持つ深さ-d$,-size $mathsfQAC0$回路のクラスで証明する。
我々は新しい回路の低境界と学習結果を応用として得る。
論文 参考訳(メタデータ) (2023-11-16T07:25:06Z) - Classical simulation of peaked shallow quantum circuits [2.6089354079273512]
準ポリノミカルランタイム$nO(logn)$のアルゴリズムについて述べる。
我々のアルゴリズムは、浅い回路の出力確率を、与えられた逆多項式加法誤差の範囲内で推定することができる。
論文 参考訳(メタデータ) (2023-09-15T14:01:13Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳(メタデータ) (2023-02-13T22:51:07Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳(メタデータ) (2022-06-17T17:55:43Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳(メタデータ) (2022-04-22T12:37:56Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳(メタデータ) (2022-01-31T22:19:49Z) - On the Optimal Memorization Power of ReLU Neural Networks [53.15475693468925]
フィードフォワードReLUニューラルネットワークは、軽度の分離可能性仮定を満たす任意のN$ポイントを記憶することができることを示す。
このような大きなビットの複雑性を持つことは、サブ線形数のパラメータを記憶するのに必要であり、十分であることを示す。
論文 参考訳(メタデータ) (2021-10-07T05:25:23Z) - Logarithmic Regret for Reinforcement Learning with Linear Function
Approximation [99.59319332864129]
最近提案された2つの線形MDP仮定で対数的後悔が達成可能であることを示す。
我々の知る限り、これらは線型関数近似を持つRLに対する最初の対数的後悔境界である。
論文 参考訳(メタデータ) (2020-11-23T17:25:00Z) - Bounds on the QAC$^0$ Complexity of Approximating Parity [0.0]
その結果,QAC回路はサイズに関係なくパリティを近似できることがわかった。
QAC回路は1/2 + exp(-o(n/d))$ perroximation of parityを達成するために少なくとも$Omega(n/d)$ multi-qubit gateを必要とする。
論文 参考訳(メタデータ) (2020-08-17T16:51:04Z) - Constant-Depth and Subcubic-Size Threshold Circuits for Matrix
Multiplication [1.9518237361775532]
大規模ニューラルネットワークハードウェアの最近の進歩は、その実践的実装を短期的可能性にしている。
しきい値ゲート論理を統合する2つの$N$を$N$行列に乗算する理論的アプローチについて述べる。
デンス行列乗算は畳み込みニューラルネットワークトレーニングにおけるコア演算である。
論文 参考訳(メタデータ) (2020-06-25T18:28:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。