論文の概要: 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)$ の場合、定数係数まで厳密であることを示す。 次に、同様の不等式が任意の離散回路に対して成り立つことを示す。 したがって、非ゼロ値を出力するゲートの数をスパースアクティビティの指標とすると、より深い深さがニューラルネットワークのスパースアクティビティ獲得に役立つことが示唆される。

関連論文リスト

• Low-degree approximation of QAC$^0$ circuits [0.0]
  パリティ関数はQAC$0$で計算できないことを示す。 また、$n$ビットのパリティをおよそ計算する深さ$d$のQAC回路には、$2widetildeOmega(n1/d)$が必要であることも示している。
  論文  参考訳（メタデータ） (2024-11-01T19:04:13Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• On the Computational Power of QAC0 with Barely Superlinear Ancillae [10.737102385599169]
  深さ$$d$$mathrmQAC0$回路は、近似次数$ta(n)$の関数を計算するために$n1+3-d$アンシラを必要とする。 これは超線形サイズの$mathrmQAC0$上の最初の超線形下界である。
  論文  参考訳（メタデータ） (2024-10-09T02:55:57Z)
• Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [8.66267734067296]
  制限しきい値関数を演算する境界を持つ定数深さ回路のクラスについて検討する。 十分大きな$mathsfbPTFC0[k]$の場合、$mathsfbPTFC0[k]は$mathsfTC0[k]を含む。
  論文  参考訳（メタデータ） (2024-08-29T09:40:55Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。 SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• 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)
• 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)
• 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)

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

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