論文の概要: Unbiased Binning: Fairness-aware Attribute Representation

• arxiv url: http://arxiv.org/abs/2509.21785v1
• Date: Fri, 26 Sep 2025 02:42:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-29 20:57:54.132518
• Title: Unbiased Binning: Fairness-aware Attribute Representation
• Title（参考訳）: Unbiased Binning: Fairness-aware Attribute Representation
• Authors: Abolfazl Asudeh, Zeinab, Asoodeh, Bita Asoodeh, Omid Asudeh,
• Abstract要約: 我々は、バケット化が与えられた場合、等サイズのビン化に最も近い離散化を求める不偏のビン化問題を導入する。 偏見のない双生児を見つけることは、しばしば高い公正さをもたらすか、あるいは存在すらしないかもしれない。 そこで我々は,epsilon-biased binningのための局所探索(LS)に基づく,実用的なスケーラブルなアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 8.049009134050705
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Discretizing raw features into bucketized attribute representations is a popular step before sharing a dataset. It is, however, evident that this step can cause significant bias in data and amplify unfairness in downstream tasks. In this paper, we address this issue by introducing the unbiased binning problem that, given an attribute to bucketize, finds its closest discretization to equal-size binning that satisfies group parity across different buckets. Defining a small set of boundary candidates, we prove that unbiased binning must select its boundaries from this set. We then develop an efficient dynamic programming algorithm on top of the boundary candidates to solve the unbiased binning problem. Finding an unbiased binning may sometimes result in a high price of fairness, or it may not even exist, especially when group values follow different distributions. Considering that a small bias in the group ratios may be tolerable in such settings, we introduce the epsilon-biased binning problem that bounds the group disparities across buckets to a small value epsilon. We first develop a dynamic programming solution, DP, that finds the optimal binning in quadratic time. The DP algorithm, while polynomial, does not scale to very large settings. Therefore, we propose a practically scalable algorithm, based on local search (LS), for epsilon-biased binning. The key component of the LS algorithm is a divide-and-conquer (D&C) algorithm that finds a near-optimal solution for the problem in near-linear time. We prove that D&C finds a valid solution for the problem unless none exists. The LS algorithm then initiates a local search, using the D&C solution as the upper bound, to find the optimal solution.
• Abstract（参考訳）: 生の機能をバケット化された属性表現に識別することは、データセットを共有するための一般的なステップである。 しかし、このステップがデータに大きなバイアスを引き起こし、下流タスクの不正性を増幅することは明らかである。 本稿では, この問題に対して, バケット化の属性を与えられた場合, 異なるバケット間のグループパリティを満たす等サイズのバケット化に最も近い離散化を求めるアンバイアス化ビン化問題を導入することにより, この問題に対処する。 境界候補の小さな集合を定義することで、偏りのない双対は、この集合から境界を選ばなければならないことを証明できる。 次に、境界候補上に効率的な動的プログラミングアルゴリズムを開発し、偏りのない双対問題の解法を提案する。 偏見のない双対を見つけることは、しばしば高い公正さをもたらすか、特に群値が異なる分布に従えば、それが存在しないかもしれない。 このような設定では、群比の小さなバイアスが許容可能であることを考慮し、小値のエプシロンに群差を束ねるエプシロンバイアス双対問題を導入する。 まず,2次時間で最適結合を求める動的プログラミングソリューションDPを開発する。 DPアルゴリズムは多項式であるが、非常に大きな設定にはスケールしない。 そこで我々は,epsilon-biased binningのための局所探索(LS)に基づく,実用的なスケーラブルなアルゴリズムを提案する。 LSアルゴリズムの鍵となるコンポーネントはディビジョン・アンド・コンカー(D&C)アルゴリズムであり、ほぼ直線時間で問題の最適解を見つける。 我々は、D&Cが存在しない限り、問題に対する有効な解を見つけることを証明している。 LSアルゴリズムは、D&C溶液を上限として局所探索を開始し、最適解を求める。

関連論文リスト

• On Socially Fair Low-Rank Approximation and Column Subset Selection [62.44413238556872]
  低ランク近似と列サブセット選択は、豊富な機械学習アプリケーションに適用される2つの基本的および関連する問題である。 驚くべきことに、一定要素の近似であっても、特定の標準複雑性仮説の下では指数時間を必要とすることが示される。 一定の数の群と一定要素の精度で、na"ive $ntextpoly(k)$ではなく2textpoly(k)$ timeで実行されるような、公平な低ランク近似のアルゴリズムを与える。
  論文  参考訳（メタデータ） (2024-12-08T20:34:16Z)
• Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
  我々は, 局所曲率をサンプルで探索し, 周辺面積を適応的に定義する適応型$k$-nearest(kK$-NN)アルゴリズムを提案する。 多くの実世界のデータセットから、新しい$kK$-NNアルゴリズムは、確立された$k$-NN法と比較してバランスの取れた精度が優れていることが示されている。
  論文  参考訳（メタデータ） (2024-09-08T13:08:45Z)
• Approximate Algorithms For $k$-Sparse Wasserstein Barycenter With Outliers [10.259254824702555]
  我々は、外乱が存在する場合に、$k$-sparse Wasserstein Barycenter問題を研究する。 既存のWBアルゴリズムは、ケースを外れ値で処理するために直接拡張することはできない。 本稿では,外乱問題のある$k$sparse WBに対して定数近似係数を求めるクラスタリングに基づくLP法を提案する。
  論文  参考訳（メタデータ） (2024-04-20T15:01:35Z)
• On Distributed Larger-Than-Memory Subset Selection With Pairwise Submodular Functions [31.334053253182795]
  証明可能な近似保証付き分散バウンディングアルゴリズムを提案する。 CIFAR-100 と ImageNet の高品質なサブセットは,集中型手法と比較して,品質が損なわれるか,あるいは損なわれない。
  論文  参考訳（メタデータ） (2024-02-26T09:38:39Z)
• Approximation Algorithms for Preference Aggregation Using CP-Nets [3.337244446073836]
  本稿では,条件付き選好ネットワーク(CP-nets)上での選好を集約する近似アルゴリズムの設計と解析について述べる。 その焦点は、一般に最適な解が指数関数的な大きさであることが知られている、いわゆる「エンフスワップ」よりも、優先的な選好を集約することである。
  論文  参考訳（メタデータ） (2023-12-14T17:31:38Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• Happiness Maximizing Sets under Group Fairness Constraints (Technical Report) [16.763245893227758]
  データベースから幸福セット(HMS)を見つけることは、多条件意思決定において重要な問題である。 我々は,最小幸福度を最大化するだけでなく,各グループから選択した数値が予め定義された下限と上限に収まることを保証するHMS(FairHMS)の公平な変種を提案し,検討する。
  論文  参考訳（メタデータ） (2022-08-13T02:54:29Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)

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

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