論文の概要: Boosting-based Construction of BDDs for Linear Threshold Functions and
Its Application to Verification of Neural Networks
- arxiv url: http://arxiv.org/abs/2306.05211v1
- Date: Thu, 8 Jun 2023 14:09:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-09 14:06:44.949451
- Title: Boosting-based Construction of BDDs for Linear Threshold Functions and
Its Application to Verification of Neural Networks
- Title（参考訳）: 線形閾値関数のためのブースティングに基づくBDDの構築とニューラルネットワークの検証への応用
- Authors: Yiping Tang, Kohei Hatano, Eiji Takimoto
- Abstract要約: 本稿では,線形しきい値関数を2値決定図(BDD)の特定の形式に変換する手法を提案する。
線形しきい値関数のマージンが大きい場合, 優れた変数順序を求める必要はなく, より小さな式を生成する。
- 参考スコア（独自算出の注目度）: 0.6875312133832078
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Understanding the characteristics of neural networks is important but
difficult due to their complex structures and behaviors. Some previous work
proposes to transform neural networks into equivalent Boolean expressions and
apply verification techniques for characteristics of interest. This approach is
promising since rich results of verification techniques for circuits and other
Boolean expressions can be readily applied. The bottleneck is the time
complexity of the transformation. More precisely, (i) each neuron of the
network, i.e., a linear threshold function, is converted to a Binary Decision
Diagram (BDD), and (ii) they are further combined into some final form, such as
Boolean circuits. For a linear threshold function with $n$ variables, an
existing method takes $O(n2^{\frac{n}{2}})$ time to construct an ordered BDD of
size $O(2^{\frac{n}{2}})$ consistent with some variable ordering. However, it
is non-trivial to choose a variable ordering producing a small BDD among $n!$
candidates.
We propose a method to convert a linear threshold function to a specific form
of a BDD based on the boosting approach in the machine learning literature. Our
method takes $O(2^n \text{poly}(1/\rho))$ time and outputs BDD of size
$O(\frac{n^2}{\rho^4}\ln{\frac{1}{\rho}})$, where $\rho$ is the margin of some
consistent linear threshold function. Our method does not need to search for
good variable orderings and produces a smaller expression when the margin of
the linear threshold function is large. More precisely, our method is based on
our new boosting algorithm, which is of independent interest. We also propose a
method to combine them into the final Boolean expression representing the
neural network.
- Abstract（参考訳）: ニューラルネットワークの特徴を理解することは重要であるが、複雑な構造や振る舞いのために難しい。
従来の研究では、ニューラルネットワークを等価ブール表現に変換し、興味のある特性に検証技術を適用することを提案した。
このアプローチは、回路や他のブール式に対する検証技術の豊富な結果が容易に適用できるため、有望である。
ボトルネックは、トランスフォーメーションの時間的複雑性です。
より正確には
(i)ネットワークの各ニューロン、すなわち線形しきい値関数は、バイナリ決定図(bdd)に変換され、
(ii)さらにブール回路などいくつかの最終形式に結合される。
n$変数を持つ線形しきい値関数に対して、既存のメソッドは$o(n2^{\frac{n}{2}})$を使って、いくつかの変数順序付けと一致するサイズ$o(2^{\frac{n}{2}})$の順序付けbddを構築する。
しかし、$nの中で小さなBDDを生み出す変数の順序を選択するのは簡単ではない。
候補者は$
本稿では,機械学習の文献における強化アプローチに基づいて,線形しきい値関数をBDDの特定の形式に変換する手法を提案する。
この方法では、$o(2^n \text{poly}(1/\rho))$の時間をとり、サイズ$o(\frac{n^2}{\rho^4}\ln{\frac{1}{\rho}})$のbddを出力する。
本手法では,線形しきい値関数のマージンが大きい場合には,良好な変数順序を求める必要はなく,より少ない式を生成する。
より正確には、我々の新しいブースティングアルゴリズムに基づいており、これは独立した関心事である。
また,これらをニューラルネットワークを表す最後のブール式に結合する手法を提案する。
関連論文リスト
- Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Solving multiscale elliptic problems by sparse radial basis function
neural networks [3.5297361401370044]
楕円偏微分方程式 (PDE) を多スケール係数で解くために, スパースラジアル基底関数ニューラルネットワーク法を提案する。
深層混合残差法に着想を得て,2次問題を1次システムに書き換え,複数の放射基底関数ニューラルネットワーク(RBFNN)を用いて未知の関数を近似する。
提案手法の精度と有効性は,1次元から3次元までのスケール分離,不連続性,複数スケールのマルチスケール問題の集合を通して実証される。
論文 参考訳（メタデータ） (2023-09-01T15:11:34Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Training Overparametrized Neural Networks in Sublinear Time [14.918404733024332]
ディープラーニングには膨大な計算とエネルギーのコストが伴う。
探索木の小さな部分集合として、二分ニューラルネットワークの新しいサブセットを示し、それぞれが探索木のサブセット(Ds)に対応する。
我々はこの見解が深層ネットワーク(Ds)の分析解析にさらに応用できると考えている。
論文 参考訳（メタデータ） (2022-08-09T02:29:42Z) - Neural Greedy Pursuit for Feature Selection [72.4121881681861]
我々は,非線形予測問題に対する$P$入力機能のうち,$N$重要な特徴を選択するための欲求アルゴリズムを提案する。
ニューラルネットワークをアルゴリズムの予測子として使用し、損失を計算します。
論文 参考訳（メタデータ） (2022-07-19T16:39:16Z) - Efficient and robust high-dimensional sparse logistic regression via
nonlinear primal-dual hybrid gradient algorithms [0.0]
弾性ネットペナルティによって正規化されるロジスティック回帰問題に対する解を確実に計算する反復アルゴリズムを提案する。
この結果は、一階最適化法に対して$O(min(m2n,mn2)log (1/epsilon))$の既知の複雑性境界を改善する。
論文 参考訳（メタデータ） (2021-11-30T14:16:48Z) - Analysis of One-Hidden-Layer Neural Networks via the Resolvent Method [0.0]
ランダムニューラルネットワークによって動機づけられた確率行列 $M = Y Yast$ と $Y = f(WX)$ を考える。
制限スペクトル分布のStieltjes変換は、いくつかの誤差項まで準自己整合方程式を満たすことを証明している。
さらに、前回の結果を加法バイアス $Y=f(WX+B)$ の場合に拡張し、$B$ は独立なランク1のガウス確率行列である。
論文 参考訳（メタデータ） (2021-05-11T15:17:39Z) - Efficient estimation of the ANOVA mean dimension, with an application to
neural net classification [0.0]
ブラックボックス関数の$d$変数の平均次元は、$d$ Sobol'のインデックスの和として記述される。
筆者らは, ウインド・階段と呼ばれるギブス・サンプルラー, ベースラインから各変数を一度に変化させるラジアル・サンプルラー, 関数評価を再利用しないナイーブ・サンプルラーを比較した。
論文 参考訳（メタデータ） (2020-07-02T17:44:10Z) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳（メタデータ） (2020-06-15T21:55:34Z) - On the Modularity of Hypernetworks [103.1147622394852]
構造化対象関数の場合、ハイパーネットワークにおけるトレーニング可能なパラメータの総数は、標準ニューラルネットワークのトレーニング可能なパラメータの数や埋め込み法よりも桁違いに小さいことを示す。
論文 参考訳（メタデータ） (2020-02-23T22:51:52Z) - Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query
Complexity [109.54166127479093]
ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。
本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。
我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。
同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
論文 参考訳（メタデータ） (2019-07-30T02:21:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。