論文の概要: Chordal Sparsity for SDP-based Neural Network Verification
- arxiv url: http://arxiv.org/abs/2206.03482v3
- Date: Mon, 8 Jan 2024 05:58:47 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-10 00:47:46.626012
- Title: Chordal Sparsity for SDP-based Neural Network Verification
- Title(参考訳): SDPに基づくニューラルネットワーク検証のための弦間距離
- Authors: Anton Xue, Lars Lindemann, Rajeev Alur
- Abstract要約: ニューラルネットワーク検証のための半定値プログラミング(SDP)に基づく手法の改善に焦点をあてる。
弦の間隔を利用して、DeepSDPの計算ボトルネックを、より小さなLMIの等価なコレクションに分解することができる。
また,Chordal-DeepSDPのさらなる解析により,LMIのコレクションを第2レベルの分解で書き直せることを示す。
- 参考スコア(独自算出の注目度): 1.9556053645976446
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Neural networks are central to many emerging technologies, but verifying
their correctness remains a major challenge. It is known that network outputs
can be sensitive and fragile to even small input perturbations, thereby
increasing the risk of unpredictable and undesirable behavior. Fast and
accurate verification of neural networks is therefore critical to their
widespread adoption, and in recent years, various methods have been developed
as a response to this problem. In this paper, we focus on improving
semidefinite programming (SDP) based techniques for neural network
verification. Such techniques offer the power of expressing complex geometric
constraints while retaining a convex problem formulation, but scalability
remains a major issue in practice. Our starting point is the DeepSDP framework
proposed by Fazlyab et al., which uses quadratic constraints to abstract the
verification problem into a large-scale SDP. However, solving this SDP quickly
becomes intractable when the network grows. Our key observation is that by
leveraging chordal sparsity, we can decompose the primary computational
bottleneck of DeepSDP -- a large linear matrix inequality (LMI) -- into an
equivalent collection of smaller LMIs. We call our chordally sparse
optimization program Chordal-DeepSDP and prove that its construction is
identically expressive as that of DeepSDP. Moreover, we show that additional
analysis of Chordal-DeepSDP allows us to further rewrite its collection of LMIs
in a second level of decomposition that we call Chordal-DeepSDP-2 -- which
results in another significant computational gain. Finally, we provide
numerical experiments on real networks of learned cart-pole dynamics,
showcasing the computational advantage of Chordal-DeepSDP and Chordal-DeepSDP-2
over DeepSDP.
- Abstract(参考訳): ニューラルネットワークは多くの新興技術の中心だが、その正確性を検証することは依然として大きな課題である。
ネットワーク出力は小さな入力摂動にも敏感で脆弱であり、予測不能で望ましくない行動のリスクを増大させることが知られている。
したがって、ニューラルネットワークの迅速かつ正確な検証は、その普及に不可欠であり、近年ではこの問題への対応として様々な手法が開発されている。
本稿では,半定義型プログラミング(sdp)に基づくニューラルネットワーク検証手法の改善に着目する。
このような手法は凸問題定式化を保ちながら複雑な幾何学的制約を表現できるが、スケーラビリティは依然として大きな問題である。
我々の出発点はfazlyabらによって提案されたdeepsdpフレームワークで、二次制約を使って検証問題を大規模sdpに抽象化する。
しかし、ネットワークが大きくなると、このSDPの解決はすぐに困難になる。
我々のキーとなる観察は、弦の間隔を利用することで、大きな線形行列不等式(LMI)であるDeepSDPの計算ボトルネックを、より小さなLMIの等価なコレクションに分解できるということである。
コードスパース最適化プログラムをchordal-DeepSDPと呼び、その構成がDeepSDPと同一表現であることを示す。
さらに、Chordal-DeepSDPのさらなる解析により、Chordal-DeepSDP-2と呼ばれる第2レベルの分解でLMIのコレクションをさらに書き直せることが示される。
最後に,Chordal-DeepSDPとChordal-DeepSDP-2によるDeepSDP上の計算優位性を示す。
関連論文リスト
- Node Centrality Approximation For Large Networks Based On Inductive
Graph Neural Networks [2.4012886591705738]
ネットワーク分析において、クローズネス中央度(CC)とブロードネス中央度(BC)が重要な指標である。
大規模なネットワーク上での実践的な実装は、その高速な複雑さのため、計算的に要求される。
本稿では,CNCA-IGEモデルを提案する。CNCA-IGEモデルは,CCやBCのメトリクスに基づいてノードをランク付けするインダクティブグラフエンコーダ・デコーダモデルである。
論文 参考訳(メタデータ) (2024-03-08T01:23:12Z) - Spike-and-slab shrinkage priors for structurally sparse Bayesian neural networks [0.16385815610837165]
スパースディープラーニングは、基礎となるターゲット関数のスパース表現を復元することで、課題に対処する。
構造化された空間によって圧縮されたディープニューラルアーキテクチャは、低レイテンシ推論、データスループットの向上、エネルギー消費の削減を提供する。
本研究では, (i) Spike-and-Slab Group Lasso (SS-GL) と (ii) Spike-and-Slab Group Horseshoe (SS-GHS) を併用した過剰ノードを誘発する構造的疎いベイズニューラルネットワークを提案する。
論文 参考訳(メタデータ) (2023-08-17T17:14:18Z) - Bayesian Interpolation with Deep Linear Networks [92.1721532941863]
ニューラルネットワークの深さ、幅、データセットサイズがモデル品質にどう影響するかを特徴付けることは、ディープラーニング理論における中心的な問題である。
線形ネットワークが無限深度で証明可能な最適予測を行うことを示す。
また、データに依存しない先行法により、広い線形ネットワークにおけるベイズ模型の証拠は無限の深さで最大化されることを示す。
論文 参考訳(メタデータ) (2022-12-29T20:57:46Z) - i-SpaSP: Structured Neural Pruning via Sparse Signal Recovery [11.119895959906085]
ニューラルネットワークのための新しい構造化プルーニングアルゴリズム - i-SpaSPと呼ばれる反復型スパース構造化プルーニングを提案する。
i-SpaSPはネットワーク内の重要なパラメータ群を識別することで動作し、プルーニングされたネットワーク出力と高密度なネットワーク出力の残差に最も寄与する。
高い性能のサブネットワークを発見し, 証明可能なベースライン手法のプルーニング効率を, 数桁の精度で向上させることが示されている。
論文 参考訳(メタデータ) (2021-12-07T05:26:45Z) - Mean-field Analysis of Piecewise Linear Solutions for Wide ReLU Networks [83.58049517083138]
勾配勾配勾配を用いた2層ReLUネットワークについて検討する。
SGDは単純な解に偏りがあることが示される。
また,データポイントと異なる場所で結び目が発生するという経験的証拠も提供する。
論文 参考訳(メタデータ) (2021-11-03T15:14:20Z) - Reduced-Order Neural Network Synthesis with Robustness Guarantees [0.0]
機械学習アルゴリズムは、デバイスがユーザのプライバシを改善し、レイテンシを低減し、エネルギー効率を高めるために、ローカルで実行するように適応されている。
この問題に対処するために、より大きなニューロンの入出力マッピングを近似する低次ニューラルネットワーク(ニューロンが少ない)を自動的に合成する手法を導入する。
この近似誤差に対する最悪の境界が得られ、このアプローチは幅広いニューラルネットワークアーキテクチャに適用することができる。
論文 参考訳(メタデータ) (2021-02-18T12:03:57Z) - Solving Sparse Linear Inverse Problems in Communication Systems: A Deep
Learning Approach With Adaptive Depth [51.40441097625201]
疎信号回復問題に対するエンドツーエンドの訓練可能なディープラーニングアーキテクチャを提案する。
提案手法は,出力するレイヤ数を学習し,各タスクのネットワーク深さを推論フェーズで動的に調整する。
論文 参考訳(メタデータ) (2020-10-29T06:32:53Z) - A Sequential Framework Towards an Exact SDP Verification of Neural
Networks [14.191310794366075]
ニューラルネットワークのロバスト性を研究するために,凸最適化に基づくいくつかの手法が文献で提案されている。
堅牢な認証アプローチの課題は、大きな緩和ギャップがあることです。
本研究では,このギャップをゼロに縮めるための逐次プログラミングフレームワークを開発することで,この問題に対処する。
論文 参考訳(メタデータ) (2020-10-16T19:45:11Z) - ESPN: Extremely Sparse Pruned Networks [50.436905934791035]
簡単な反復マスク探索法により,非常に深いネットワークの最先端の圧縮を実現することができることを示す。
本アルゴリズムは,シングルショット・ネットワーク・プルーニング法とロッテ・ティケット方式のハイブリッド・アプローチを示す。
論文 参考訳(メタデータ) (2020-06-28T23:09:27Z) - Binary Neural Networks: A Survey [126.67799882857656]
バイナリニューラルネットワークは、リソース制限されたデバイスにディープモデルをデプロイするための有望なテクニックとして機能する。
バイナライゼーションは必然的に深刻な情報損失を引き起こし、さらに悪いことに、その不連続性はディープネットワークの最適化に困難をもたらす。
本稿では,2項化を直接実施するネイティブソリューションと,量子化誤差の最小化,ネットワーク損失関数の改善,勾配誤差の低減といった手法を用いて,これらのアルゴリズムを探索する。
論文 参考訳(メタデータ) (2020-03-31T16:47:20Z) - Rectified Linear Postsynaptic Potential Function for Backpropagation in
Deep Spiking Neural Networks [55.0627904986664]
スパイキングニューラルネットワーク(SNN)は、時間的スパイクパターンを用いて情報を表現し、伝達する。
本稿では,情報符号化,シナプス可塑性,意思決定におけるスパイクタイミングダイナミクスの寄与について検討し,将来のDeepSNNやニューロモルフィックハードウェアシステムの設計への新たな視点を提供する。
論文 参考訳(メタデータ) (2020-03-26T11:13:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。