論文の概要: Fast Feature Selection with Fairness Constraints
- arxiv url: http://arxiv.org/abs/2202.13718v2
- Date: Fri, 3 Feb 2023 13:03:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-19 15:18:29.383532
- Title: Fast Feature Selection with Fairness Constraints
- Title(参考訳): フェアネス制約付き高速特徴選択
- Authors: Francesco Quinzan, Rajiv Khanna, Moshik Hershcovitch, Sarel Cohen,
Daniel G. Waddington, Tobias Friedrich, Michael W. Mahoney
- Abstract要約: モデル構築における最適特徴の選択に関する基礎的問題について検討する。
この問題は、greedyアルゴリズムの変種を使用しても、大規模なデータセットで計算的に困難である。
適応クエリモデルは,最近提案された非モジュラー関数に対する直交整合探索のより高速なパラダイムに拡張する。
提案アルゴリズムは、適応型クエリモデルにおいて指数関数的に高速な並列実行を実現する。
- 参考スコア(独自算出の注目度): 49.142308856826396
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We study the fundamental problem of selecting optimal features for model
construction. This problem is computationally challenging on large datasets,
even with the use of greedy algorithm variants. To address this challenge, we
extend the adaptive query model, recently proposed for the greedy forward
selection for submodular functions, to the faster paradigm of Orthogonal
Matching Pursuit for non-submodular functions. The proposed algorithm achieves
exponentially fast parallel run time in the adaptive query model, scaling much
better than prior work. Furthermore, our extension allows the use of
downward-closed constraints, which can be used to encode certain fairness
criteria into the feature selection process. We prove strong approximation
guarantees for the algorithm based on standard assumptions. These guarantees
are applicable to many parametric models, including Generalized Linear Models.
Finally, we demonstrate empirically that the proposed algorithm competes
favorably with state-of-the-art techniques for feature selection, on real-world
and synthetic datasets.
- Abstract(参考訳): モデル構築における最適特徴の選択に関する基礎的問題について検討する。
この問題は、greedyアルゴリズムの変種を使用しても、大規模なデータセットで計算的に困難である。
この課題に対処するために,最近提案された部分モジュラ関数のグリーディフォワード選択のための適応クエリモデルを拡張し,非部分モジュラ関数の直交マッチング追跡のより高速なパラダイムに拡張する。
提案アルゴリズムは、適応型クエリモデルにおいて指数関数的に高速な並列実行を実現する。
さらに,本拡張では,特定のフェアネス基準を特徴選択プロセスにエンコードするために使用可能な,下向きの制約の利用が可能となった。
我々は,標準仮定に基づくアルゴリズムの強い近似保証を証明した。
これらの保証は一般化線型モデルを含む多くのパラメトリックモデルに適用できる。
最後に,提案アルゴリズムは実世界および合成データセット上で,特徴選択のための最先端技術と良好に競合することを示す。
関連論文リスト
- Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。
このような問題は医学、物理学、機械学習で発生する。
両種類の雑音下で提案アルゴリズムの収束保証を行う。
論文 参考訳(メタデータ) (2024-11-21T10:26:17Z) - An incremental preference elicitation-based approach to learning potentially non-monotonic preferences in multi-criteria sorting [53.36437745983783]
まず最適化モデルを構築し,非単調な選好をモデル化する。
本稿では,情報量測定手法と質問選択戦略を考案し,各イテレーションにおいて最も情報に富む選択肢を特定する。
2つのインクリメンタルな選好に基づくアルゴリズムは、潜在的に単調な選好を学習するために開発された。
論文 参考訳(メタデータ) (2024-09-04T14:36:20Z) - Stop Relying on No-Choice and Do not Repeat the Moves: Optimal,
Efficient and Practical Algorithms for Assortment Optimization [38.57171985309975]
本研究では,emphPlackett Luce (PL) を用いたコンソーシアム選択問題に対する効率的なアルゴリズムを開発した。
提案手法は,既存の手法の限界を無視し,実用的かつ確実に最適である。
論文 参考訳(メタデータ) (2024-02-29T07:17:04Z) - Best-Subset Selection in Generalized Linear Models: A Fast and
Consistent Algorithm via Splicing Technique [0.6338047104436422]
ベストサブセットセクションは、このタイプの問題の聖杯として広く見なされている。
軽度条件下での最適部分集合回復のためのアルゴリズムを提案し,提案した。
我々の実装は、一般的な変数選択ツールキットと比較して約4倍のスピードアップを実現している。
論文 参考訳(メタデータ) (2023-08-01T03:11:31Z) - Universal and data-adaptive algorithms for model selection in linear
contextual bandits [52.47796554359261]
モデル選択の最も単純な非自明な例を考える: 単純な多重武装バンディット問題と線形文脈バンディット問題とを区別する。
データ適応的な方法で探索する新しいアルゴリズムを導入し、$mathcalO(dalpha T1- alpha)$という形式の保証を提供する。
我々のアプローチは、いくつかの仮定の下で、ネストされた線形文脈包帯のモデル選択に拡張する。
論文 参考訳(メタデータ) (2021-11-08T18:05:35Z) - Near Instance Optimal Model Selection for Pure Exploration Linear
Bandits [20.67688737534517]
純探索線形帯域設定におけるモデル選択問題について検討する。
私たちのゴールは、最小の仮説クラスのインスタンス依存の複雑性尺度に自動的に適応することです。
提案アルゴリズムは,実験設計に基づく新しい最適化問題を定義する。
論文 参考訳(メタデータ) (2021-09-10T22:56:58Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳(メタデータ) (2020-11-19T10:00:54Z) - Joint Adaptive Graph and Structured Sparsity Regularization for
Unsupervised Feature Selection [6.41804410246642]
本稿では,共同適応グラフと構造付き空間正規化unsupervised feature selection (JASFS)法を提案する。
最適な機能のサブセットがグループで選択され、選択された機能の数が自動的に決定される。
8つのベンチマーク実験の結果,提案手法の有効性と有効性を示した。
論文 参考訳(メタデータ) (2020-10-09T08:17:04Z) - Adaptive Sampling of Pareto Frontiers with Binary Constraints Using
Regression and Classification [0.0]
本稿では,二項制約を持つブラックボックス多目的最適化問題に対する適応最適化アルゴリズムを提案する。
本手法は確率的回帰モデルと分類モデルに基づいており,最適化目標のサロゲートとして機能する。
また,予想される超体積計算を高速化するために,新しい楕円形トランケーション法を提案する。
論文 参考訳(メタデータ) (2020-08-27T09:15:02Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳(メタデータ) (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。