論文の概要: Streaming Algorithms for Diversity Maximization with Fairness
Constraints
- arxiv url: http://arxiv.org/abs/2208.00194v1
- Date: Sat, 30 Jul 2022 11:47:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-02 14:47:37.043676
- Title: Streaming Algorithms for Diversity Maximization with Fairness
Constraints
- Title（参考訳）: 公平性制約による多様性最大化のためのストリーミングアルゴリズム
- Authors: Yanhao Wang and Francesco Fabbri and Michael Mathioudakis
- Abstract要約: ストリーミングアルゴリズムは、1回のパスで$X$をシーケンシャルに処理し、フェアネス制約を保証しながら最大emph順序で返却サブセットを処理すべきである。
多様性は一般にNPハードであるため、データストリームの公平な多様性のための2つのアルゴリズムを提案する。
実験の結果,両アルゴリズムは最先端のアルゴリズムに匹敵する品質の解を提供することがわかった。
- 参考スコア（独自算出の注目度）: 4.53279507109072
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Diversity maximization is a fundamental problem with wide applications in
data summarization, web search, and recommender systems. Given a set $X$ of $n$
elements, it asks to select a subset $S$ of $k \ll n$ elements with maximum
\emph{diversity}, as quantified by the dissimilarities among the elements in
$S$. In this paper, we focus on the diversity maximization problem with
fairness constraints in the streaming setting. Specifically, we consider the
max-min diversity objective, which selects a subset $S$ that maximizes the
minimum distance (dissimilarity) between any pair of distinct elements within
it. Assuming that the set $X$ is partitioned into $m$ disjoint groups by some
sensitive attribute, e.g., sex or race, ensuring \emph{fairness} requires that
the selected subset $S$ contains $k_i$ elements from each group $i \in [1,m]$.
A streaming algorithm should process $X$ sequentially in one pass and return a
subset with maximum \emph{diversity} while guaranteeing the fairness
constraint. Although diversity maximization has been extensively studied, the
only known algorithms that can work with the max-min diversity objective and
fairness constraints are very inefficient for data streams. Since diversity
maximization is NP-hard in general, we propose two approximation algorithms for
fair diversity maximization in data streams, the first of which is
$\frac{1-\varepsilon}{4}$-approximate and specific for $m=2$, where
$\varepsilon \in (0,1)$, and the second of which achieves a
$\frac{1-\varepsilon}{3m+2}$-approximation for an arbitrary $m$. Experimental
results on real-world and synthetic datasets show that both algorithms provide
solutions of comparable quality to the state-of-the-art algorithms while
running several orders of magnitude faster in the streaming setting.
- Abstract（参考訳）: 多様性の最大化は、データ要約、web検索、レコメンダシステムにおける幅広いアプリケーションにおいて根本的な問題である。
集合 $X$ of $n$ 要素が与えられたとき、$S$内の要素間の相違によって定量化されるように、最大 \emph{diversity} を持つ部分集合 $S$ of $k \ll n$ 要素を選択する。
本稿では,ストリーミング環境における公平性制約を伴う多様性の最大化問題に着目する。
具体的には、その中の任意の異なる要素の対の間の最小距離(相似性)を最大化する部分集合$S$を選択する極小多様性目的を考える。
集合 $X$ が $m$ disjoint group に分割されていると仮定すると、例えば、セックスやレース、保証 \emph{fairness} は、選択されたサブセット $S$ は、各グループ $i \in [1,m]$ の $k_i$ 要素を含む必要がある。
ストリーミングアルゴリズムは、1回のパスで$x$を順次処理し、フェアネス制約を保証しながら最大値 \emph{diversity} のサブセットを返す必要がある。
多様性の最大化は広く研究されているが、最大限の多様性目標と公正性制約を扱える唯一の既知のアルゴリズムは、データストリームにとって非常に非効率である。
ダイバーシティの最大化は一般にnpハードであるため、データストリームにおける公平な多様性の最大化のための2つの近似アルゴリズムを提案する。1つは$\frac{1-\varepsilon}{4}$-approximateで、$m=2$、$\varepsilon \in (0,1)$、そしてもう1つは$\frac{1-\varepsilon}{3m+2}$-approximationである。
実世界および合成データセットでの実験的結果は、両方のアルゴリズムがストリーミング環境で数桁の高速化を実行しながら、最先端のアルゴリズムに匹敵する品質のソリューションを提供することを示している。
関連論文リスト
- GIST: Greedy Independent Set Thresholding for Diverse Data Summarization [21.69260104523751]
我々は、min-distance various data summarization(textsfMDDS$)と呼ばれる新しいサブセット選択タスクを提案する。
目的は、各点のトータルユーティリティと、選択された任意の点間の最小距離をキャプチャする多様性項を組み合わせた目的を最大化することである。
この作業は、$textttGIST$アルゴリズムを示し、$textsfMDDS$の$frac23$-approximation保証を達成する。
論文 参考訳（メタデータ） (2024-05-29T04:39:24Z) - Diversity-aware clustering: Computational Complexity and Approximation
Algorithms [19.67390261007849]
本稿では,データポイントが複数の属性に関連付けられ,グループ間の交差が生じている,多様性を考慮したクラスタリング問題について検討する。
クラスタリングソリューションは、各グループから最小数のクラスタセンターが選択されることを保証する必要がある。
近似比が1+ frac2e$, $1+frac8e$, 3,$のパラメータ化近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-01-10T19:01:05Z) - Core-sets for Fair and Diverse Data Summarization [5.424775372322808]
フェアネス/パーティション制約下での多様性最大化処理のコアセット構築アルゴリズムについて検討する。
本論文では,データセットのサイズとアスペクト比によらずに大きさが依存する,第1の定数係数コアセットw.r.t.和対ペアワイズ距離を示す。
特に、制約付き多様性を適用して、メッセージの正確性を考慮に入れた時間付きメッセージの集合を要約する。
論文 参考訳（メタデータ） (2023-10-12T08:24:02Z) - Composable Coresets for Determinant Maximization: Greedy is Almost
Optimal [2.849878266188877]
a set of $n$ in $mathbbRd$, the emphdeterminant problem of the emphdeterminant problem to pick $k$ vectors with the maximum volume。
広く使われているGreedyアルゴリズムは、O(k)3k$の近似係数がほぼ最適である構成可能なコアセットも提供する。
論文 参考訳（メタデータ） (2023-09-26T21:46:44Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - The Power of Subsampling in Submodular Maximization [51.629656762796564]
このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。
我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
論文 参考訳（メタデータ） (2021-04-06T20:25:57Z) - Fair and Representative Subset Selection from Data Streams [4.53279507109072]
ストリーム内のデータ項目が複数の不随意群に属する設定について検討する。
ストリーミングサブモジュラー問題の公平性を考慮した変種に対する効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-09T07:49:13Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。