論文の概要: Interval Universal Approximation for Neural Networks
- arxiv url: http://arxiv.org/abs/2007.06093v5
- Date: Wed, 14 Jul 2021 05:51:30 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-11 05:38:24.541303
- Title: Interval Universal Approximation for Neural Networks
- Title（参考訳）: ニューラルネットワークのための区間普遍近似
- Authors: Zi Wang, Aws Albarghouthi, Gautam Prakriya, Somesh Jha
- Abstract要約: 区間普遍近似(IUA)定理を導入する。
IUAは、ニューラルネットワークが何十年にもわたって知られているような、あらゆる連続関数の$f$を近似できることを示している。
本稿では,精度の高い区間解析が可能なニューラルネットワークを構築する際の計算複雑性について検討する。
- 参考スコア（独自算出の注目度）: 47.767793120249095
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: To verify safety and robustness of neural networks, researchers have
successfully applied abstract interpretation, primarily using the interval
abstract domain. In this paper, we study the theoretical power and limits of
the interval domain for neural-network verification.
First, we introduce the interval universal approximation (IUA) theorem. IUA
shows that neural networks not only can approximate any continuous function $f$
(universal approximation) as we have known for decades, but we can find a
neural network, using any well-behaved activation function, whose interval
bounds are an arbitrarily close approximation of the set semantics of $f$ (the
result of applying $f$ to a set of inputs). We call this notion of
approximation interval approximation. Our theorem generalizes the recent result
of Baader et al. (2020) from ReLUs to a rich class of activation functions that
we call squashable functions. Additionally, the IUA theorem implies that we can
always construct provably robust neural networks under $\ell_\infty$-norm using
almost any practical activation function.
Second, we study the computational complexity of constructing neural networks
that are amenable to precise interval analysis. This is a crucial question, as
our constructive proof of IUA is exponential in the size of the approximation
domain. We boil this question down to the problem of approximating the range of
a neural network with squashable activation functions. We show that the range
approximation problem (RA) is a $\Delta_2$-intermediate problem, which is
strictly harder than $\mathsf{NP}$-complete problems, assuming
$\mathsf{coNP}\not\subset \mathsf{NP}$. As a result, IUA is an inherently hard
problem: No matter what abstract domain or computational tools we consider to
achieve interval approximation, there is no efficient construction of such a
universal approximator.
- Abstract（参考訳）: ニューラルネットワークの安全性と堅牢性を検証するため、研究者はインターバル抽象ドメインを用いて抽象解釈をうまく適用した。
本稿では,ニューラルネットワーク検証のための区間領域の理論的パワーと限界について検討する。
まず、区間普遍近似(IUA)定理を導入する。
IUAは、ニューラルネットワークが何十年にもわたって知られているような連続関数$f$(ユニバーサル近似)を近似できるだけでなく、その間隔境界が$f$(入力の集合に$f$を適用した結果)の任意の厳密な近似であるような活性化関数を用いてニューラルネットワークを見つけることができることを示している。
これを近似区間近似と呼ぶ。
我々の定理は、ReLUs からの Baader et al. (2020) の最近の結果を、squashable function と呼ばれるリッチなアクティベーション関数のクラスに一般化する。
さらに、IUA定理は、ほぼすべての実用的なアクティベーション関数を用いて、$\ell_\infty$-normの下で証明可能な堅牢なニューラルネットワークを常に構築できることを示唆している。
第2に,正確な区間解析が可能なニューラルネットワーク構築の計算複雑性について検討する。
IUA の構成的証明は近似領域のサイズで指数関数的であるので、これは重要な問題である。
この疑問を、スカッシュ可能なアクティベーション関数でニューラルネットワークの範囲を近似する問題に要約する。
距離近似問題 (ra) は$\delta_2$-中間問題であり、$\mathsf{np}$完全問題より厳密に難しく、$\mathsf{conp}\not\subset \mathsf{np}$と仮定している。
その結果、IUAは本質的に難しい問題である: インターバル近似を達成するための抽象的な領域や計算ツールが何であれ、そのような普遍近似器の効率的な構築は存在しない。
関連論文リスト
- Optimal Neural Network Approximation for High-Dimensional Continuous Functions [5.748690310135373]
我々は、その近似において任意の精度を達成するために、少なくとも幅$d$、従って少なくとも$d$固有のニューロンを必要とする連続関数の族を示す。
これは、$mathcalO(d)$内在ニューロンの要求が、入力次元$d$と線形に成長するという意味で最適であることを示している。
論文 参考訳（メタデータ） (2024-09-04T01:18:55Z) - Optimal approximation using complex-valued neural networks [0.0]
複雑評価ニューラルネットワーク(CVNN)は最近、有望な経験的成功を示している。
CVNNの表現性を近似特性を用いて解析する。
論文 参考訳（メタデータ） (2023-03-29T15:56:43Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - Neural Network Approximation of Continuous Functions in High Dimensions
with Applications to Inverse Problems [6.84380898679299]
現在の理論では、ネットワークは問題の次元で指数関数的にスケールすべきだと予測されている。
ニューラルネットワークがH"より古い(あるいは一様)連続関数を近似するのに要する複雑性を境界付ける一般的な方法を提案する。
論文 参考訳（メタデータ） (2022-08-28T22:44:07Z) - Deep neural network approximation of analytic functions [91.3755431537592]
ニューラルネットワークの空間に エントロピーバウンド 片方向の線形活性化関数を持つ
我々は、ペナル化深部ニューラルネットワーク推定器の予測誤差に対するオラクルの不等式を導出する。
論文 参考訳（メタデータ） (2021-04-05T18:02:04Z) - Size and Depth Separation in Approximating Natural Functions with Neural
Networks [52.73592689730044]
本稿では,ReLUネットワークを用いた自然関数の近似におけるサイズと深さの利点を示す。
我々は、そのような結果が$O(d)$を超えることを証明するための複雑性理論上の障壁を示す。
また、サイズ$O(d)$のネットワークで近似できる明示的な自然関数も示している。
論文 参考訳（メタデータ） (2021-01-30T21:30:11Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z) - Random Vector Functional Link Networks for Function Approximation on Manifolds [8.535815777849786]
ランダムな入力-隠蔽層重みとバイアスを持つ単一層ニューラルネットが実際に成功していることを示す。
さらに、このランダム化されたニューラルネットワークアーキテクチャをユークリッド空間の滑らかでコンパクトな部分多様体上の近似関数に適用する。
論文 参考訳（メタデータ） (2020-07-30T23:50:44Z) - Nonclosedness of Sets of Neural Networks in Sobolev Spaces [0.0]
実現されたニューラルネットワークは順序で閉じていないことを示す--(m-1)$ソボレフ空間$Wm-1,p$ for $p in [1,infty]$。
実解析的アクティベーション関数に対して、実現されたニューラルネットワークの集合は、mathbbN$の任意の$kに対して$Wk,p$で閉じていないことを示す。
論文 参考訳（メタデータ） (2020-07-23T00:57:25Z) - Reinforcement Learning with General Value Function Approximation:
Provably Efficient Approach via Bounded Eluder Dimension [124.7752517531109]
一般値関数近似を用いた効率の良い強化学習アルゴリズムを確立する。
我々のアルゴリズムは、$d$が複雑性測度である場合、$widetildeO(mathrmpoly(dH)sqrtT)$の後悔の限界を達成することを示す。
我々の理論は線形値関数近似によるRLの最近の進歩を一般化し、環境モデルに対する明示的な仮定をしない。
論文 参考訳（メタデータ） (2020-05-21T17:36:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。