論文の概要: Certifiable Robustness for Nearest Neighbor Classifiers

• arxiv url: http://arxiv.org/abs/2201.04770v1
• Date: Thu, 13 Jan 2022 02:55:10 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-14 15:13:34.731412
• Title: Certifiable Robustness for Nearest Neighbor Classifiers
• Title（参考訳）: 最近近傍分類器の認証ロバスト性
• Authors: Austen Z. Fan and Paraschos Koutris
• Abstract要約: 単純で広くデプロイされた分類アルゴリズム、$k$-Nearest Neighbors(k$-NN)の認証の複雑さについて検討する。 制約が関数依存(FD)である場合には、一貫性のないデータセットに重点を置いています。 そこでは、あるラベルを予測する可能性のある世界の数を数えることが目的である。
• 参考スコア（独自算出の注目度）: 6.487663563916903
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: ML models are typically trained using large datasets of high quality. However, training datasets often contain inconsistent or incomplete data. To tackle this issue, one solution is to develop algorithms that can check whether a prediction of a model is certifiably robust. Given a learning algorithm that produces a classifier and given an example at test time, a classification outcome is certifiably robust if it is predicted by every model trained across all possible worlds (repairs) of the uncertain (inconsistent) dataset. This notion of robustness falls naturally under the framework of certain answers. In this paper, we study the complexity of certifying robustness for a simple but widely deployed classification algorithm, $k$-Nearest Neighbors ($k$-NN). Our main focus is on inconsistent datasets when the integrity constraints are functional dependencies (FDs). For this setting, we establish a dichotomy in the complexity of certifying robustness w.r.t. the set of FDs: the problem either admits a polynomial time algorithm, or it is coNP-hard. Additionally, we exhibit a similar dichotomy for the counting version of the problem, where the goal is to count the number of possible worlds that predict a certain label. As a byproduct of our study, we also establish the complexity of a problem related to finding an optimal subset repair that may be of independent interest.
• Abstract（参考訳）: mlモデルは通常、高品質の大規模データセットを使用してトレーニングされる。 しかし、トレーニングデータセットには一貫性のないデータや不完全なデータが含まれることが多い。 この問題に対処する一つの解決策は、モデルの予測が確実に堅牢かどうかを確認するアルゴリズムを開発することである。 分類器を生成し、テスト時に例を与える学習アルゴリズムが与えられると、不確定な(一貫性のない)データセットのすべての可能な世界(repairs)で訓練されたすべてのモデルによって予測された場合、分類結果が証明可能ロバストとなる。 この頑健性の概念は、ある答えの枠組みに自然に当てはまる。 本稿では,単純かつ広くデプロイされた分類アルゴリズムである$k$-Nearest Neighbors(k$-NN)のロバスト性証明の複雑さについて検討する。 当社の主な焦点は、整合性制約が関数依存(fds)である場合の一貫性のないデータセットにあります。 この設定のために、FDの集合として堅牢性を証明する複雑さを二分する:問題は多項式時間アルゴリズムを認めるか、coNPハードである。 さらに、あるラベルを予測できる可能性のある世界の数を数えることを目的として、問題の計数バージョンの同様の二分法を示す。 また,本研究の副産物として,独立した関心を持つ可能性のある最適部分修復の発見に関わる問題の複雑性を確立する。

関連論文リスト

• Who Should Predict? Exact Algorithms For Learning to Defer to Humans [40.22768241509553]
  従来の手法では,誤分類誤りの少ない人間-AIシステムを見つけることができなかった。 線形設定における問題を最適に解くことができるMILP(mixed-integer-linear-gramming)の定式化について述べる。 実現可能で,実証的にも良好に機能する新規な代理損失関数を提供する。
  論文  参考訳（メタデータ） (2023-01-15T21:57:36Z)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  我々は、従来のEMベースのアルゴリズムを拡張するための全体的なデータの特徴付けを導出する。 新しいアルゴリズムは、そのような混合データソースからモデルパラメータの(不特定性)領域を近似することを学ぶ。 反実的な結果に間隔近似を与え、それが特定可能な場合の点に崩壊する。
  論文  参考訳（メタデータ） (2022-12-06T12:42:11Z)
• Ensemble Methods for Robust Support Vector Machines using Integer Programming [0.0]
  我々は、トレーニングデータが不確実性にさらされていると仮定する二項分類問題について検討する。 この問題を解決するために、堅牢な機械学習の分野では、トレーニングデータの小さな摂動に対して堅牢なモデルを開発することが目的である。
  論文  参考訳（メタデータ） (2022-03-03T10:03:54Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。 本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。 他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。 驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
  論文  参考訳（メタデータ） (2021-10-21T07:28:11Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Robust Estimation of Tree Structured Ising Models [20.224160348675422]
  我々は、異なる確率変数の符号が、おそらく不等で未知の確率で独立に反転するときに、イジングモデルを学習するタスクを考える。 しかし, この不同一性は, 葉ノードが近傍と位置を交換して形成する小さな同値類に限られる。
  論文  参考訳（メタデータ） (2020-06-10T01:32:45Z)
• Distributionally Robust Weighted $k$-Nearest Neighbors [21.537952410507483]
  少数のサンプルから堅牢な分類器を学ぶことは、マシンラーニングにおける重要な課題である。 本稿では, 重み付き$k$-アネレスト近傍のミニマックス分布に頑健な定式化について検討する。 我々は,この関数最適化問題を効率的に解くアルゴリズムである textttDr.k-NN を開発した。
  論文  参考訳（メタデータ） (2020-06-07T00:34:33Z)
• Establishing strong imputation performance of a denoising autoencoder in a wide range of missing data problems [0.0]
  トレーニングと計算の両方に一貫したフレームワークを開発します。 結果と最先端の計算手法を比較検討した。 開発されたオートエンコーダは、初期データ破損のあらゆる範囲において最小の誤差を得た。
  論文  参考訳（メタデータ） (2020-04-06T12:00:30Z)

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

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