Fugu-MT 論文翻訳(概要): Some Complexity Results for Robustness Verification for Binarized Neural Networks

論文の概要: Some Complexity Results for Robustness Verification for Binarized Neural Networks

arxiv url: http://arxiv.org/abs/2606.18918v1
Date: Wed, 17 Jun 2026 10:48:11 GMT
ステータス: 翻訳完了
システム内更新日: 2026-06-18 17:16:51.119923
Title: Some Complexity Results for Robustness Verification for Binarized Neural Networks
Title（参考訳）: 二元化ニューラルネットワークのロバスト性検証のための複雑度解析結果
Authors: Harshit Goyal, Sudakshina Dutta,
Abstract要約: 本稿では,二元化ニューラルネットワーク(BNN)における検証問題の計算複雑性について検討する。我々は, BNN の満足度が NP 完全であることを示す。
参考スコア（独自算出の注目度）: 1.7188280334580195
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This paper studies the computational complexity of verification problems for Binarized Neural Networks (BNNs), where activations (and sometimes weights) are binary. We analyze two problems: satisfiability and robustness under uniform image occlusion. We show that BNN satisfiability is NP-complete via a reduction from Boolean satisfiability problem (SAT), and that uniform occlusion induces a piecewise-constant structure in the network output, enabling a polynomial-time robustness-checking algorithm.
Abstract（参考訳）: 本稿では、活性化(時には重み付け)が二元化される二元化ニューラルネットワーク(BNN)の検証問題の計算複雑性について検討する。我々は,一様画像閉塞下での満足度と堅牢性という2つの問題を解析した。我々は,BNN の満足度は Boolean satisfiability problem (SAT) からの還元によりNP完全であることが示し,一様閉塞はネットワーク出力に一括整合構造を誘導し,多項式時間ロバストネスチェックアルゴリズムを実現することを示した。

関連論文リスト

On Integer Programming for the Binarized Neural Network Verification Problem [3.342097413151171]
バイナリ化ニューラルネットワーク(BNN)は、バイナリウェイトとアクティベーション機能を備えたフィードフォワードニューラルネットワークである。検証問題は、与えられた入力の小さな摂動がBNNによって誤って分類される可能性があるかどうかを判断しようとする。
論文参考訳（メタデータ） (2025-10-01T23:43:18Z)
LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
論文参考訳（メタデータ） (2024-07-18T22:05:21Z)
On the Intrinsic Structures of Spiking Neural Networks [66.57589494713515]
近年、時間依存データやイベント駆動データを扱う大きな可能性から、SNNへの関心が高まっている。スパイキング計算における本質的な構造の影響を総合的に調査する研究が数多く行われている。この研究はSNNの本質的な構造を深く掘り下げ、SNNの表現性への影響を解明する。
論文参考訳（メタデータ） (2022-06-21T09:42:30Z)
Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
我々は、勾配降下訓練におけるディープニューラルネットワーク(DNN)の収束に対する接続パターンの影響を理論的に特徴づける。接続パターンの単純なフィルタリングによって、評価対象のモデルの数を削減できることが示される。
論文参考訳（メタデータ） (2022-05-11T17:43:54Z)
Comparative Analysis of Interval Reachability for Robust Implicit and Feedforward Neural Networks [64.23331120621118]
我々は、暗黙的ニューラルネットワーク(INN)の堅牢性を保証するために、区間到達可能性分析を用いる。 INNは暗黙の方程式をレイヤとして使用する暗黙の学習モデルのクラスである。提案手法は, INNに最先端の区間境界伝搬法を適用するよりも, 少なくとも, 一般的には, 有効であることを示す。
論文参考訳（メタデータ） (2022-04-01T03:31:27Z)
A Mixed Integer Programming Approach for Verifying Properties of Binarized Neural Networks [44.44006029119672]
BNN検証のための混合整数計画法を提案する。我々は,MNISTデータセットと航空機衝突回避制御器を用いて訓練したBNNの特性を検証することによって,我々のアプローチを実証する。
論文参考訳（メタデータ） (2022-03-11T01:11:29Z)
Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
論文参考訳（メタデータ） (2021-10-21T07:28:11Z)
Stability of Neural Networks on Manifolds to Relative Perturbations [118.84154142918214]
グラフニューラルネットワーク(GNN)は多くの実践シナリオにおいて素晴らしいパフォーマンスを示している。 GNNは大規模グラフ上でうまくスケールすることができるが、これは既存の安定性がノード数とともに増加するという事実に矛盾する。
論文参考訳（メタデータ） (2021-10-10T04:37:19Z)
Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming [0.0]
離散データからベイズネットワーク(BNSL)の構造を学習することはNPハードタスクであることが知られている。本研究では,可能なクラスタカットのサブセットを発見するための新しい時間アルゴリズムを提案する。最適ではないにもかかわらず、性能は桁違いに向上することを示す。結果として得られる解法は、BNSL問題に対する最先端の解法である GOBNILP と好意的に比較できる。
論文参考訳（メタデータ） (2021-06-23T09:46:11Z)
Bounding the Complexity of Formally Verifying Neural Networks: A Geometric Approach [1.9493449206135296]
ReLUニューラルネットワーク(NN)の複雑さを正式に検証することを検討する。本稿では,2つの異なるNNに対して,検証問題は2種類の制約を満たすことを示す。両方のアルゴリズムは、NNパラメータをハイパープレーンを用いてNNアーキテクチャの効果に効率的に変換する。
論文参考訳（メタデータ） (2020-12-22T00:29:54Z)
Abstraction based Output Range Analysis for Neural Networks [10.051309746913512]
本稿では,ReLUアクティベーション機能を備えたフィードフォワードニューラルネットワークにおける出力範囲解析の問題点について考察する。既存の手法は、出力範囲解析問題を満足度と最適化の解決に還元する。より少ないニューロンで単純なニューラルネットワークを構築する新しい抽象化手法を提案する。
論文参考訳（メタデータ） (2020-07-18T22:24:54Z)

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