論文の概要: Fair and Representative Subset Selection from Data Streams
- arxiv url: http://arxiv.org/abs/2010.04412v2
- Date: Fri, 12 Feb 2021 09:04:12 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-09 06:25:47.324476
- Title: Fair and Representative Subset Selection from Data Streams
- Title（参考訳）: データストリームからの公平かつ代表的なサブセット選択
- Authors: Yanhao Wang and Francesco Fabbri and Michael Mathioudakis
- Abstract要約: ストリーム内のデータ項目が複数の不随意群に属する設定について検討する。
ストリーミングサブモジュラー問題の公平性を考慮した変種に対する効率的なアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 4.53279507109072
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We study the problem of extracting a small subset of representative items
from a large data stream. In many data mining and machine learning applications
such as social network analysis and recommender systems, this problem can be
formulated as maximizing a monotone submodular function subject to a
cardinality constraint $k$. In this work, we consider the setting where data
items in the stream belong to one of several disjoint groups and investigate
the optimization problem with an additional \emph{fairness} constraint that
limits selection to a given number of items from each group. We then propose
efficient algorithms for the fairness-aware variant of the streaming submodular
maximization problem. In particular, we first give a $
(\frac{1}{2}-\varepsilon) $-approximation algorithm that requires $
O(\frac{1}{\varepsilon} \log \frac{k}{\varepsilon}) $ passes over the stream
for any constant $ \varepsilon>0 $. Moreover, we give a single-pass streaming
algorithm that has the same approximation ratio of $(\frac{1}{2}-\varepsilon)$
when unlimited buffer sizes and post-processing time are permitted, and discuss
how to adapt it to more practical settings where the buffer sizes are bounded.
Finally, we demonstrate the efficiency and effectiveness of our proposed
algorithms on two real-world applications, namely \emph{maximum coverage on
large graphs} and \emph{personalized recommendation}.
- Abstract（参考訳）: 大規模データストリームから代表項目の小さなサブセットを抽出する問題について検討する。
ソーシャルネットワーク分析やレコメンダシステムのような多くのデータマイニングや機械学習のアプリケーションでは、この問題は濃度制約$k$の単調部分モジュラー関数の最大化として定式化することができる。
本研究では,ストリーム内のデータ項目が複数の非結合群の1つに属する設定を考察し,各グループから与えられた項目数に選択を限定する追加の制約である \emph{fairness} を用いて最適化問題を検討する。
次に,ストリーミングサブモジュラー最大化問題のフェアネス認識型に対する効率的なアルゴリズムを提案する。
特に、まず、$ (\frac{1}{2}-\varepsilon) $-approximation algorithmを指定し、$ O(\frac{1}{\varepsilon} \log \frac{k}{\varepsilon}) $ は任意の定値 $ \varepsilon>0 $ に対してストリームを渡る。
さらに,バッファサイズと処理後時間が無制限である場合の近似比が$(\frac{1}{2}-\varepsilon)$となる単一パスストリーミングアルゴリズムを与え,バッファサイズが境界付けられたより実用的な設定にそれを適用する方法について検討する。
最後に,提案アルゴリズムの有効性を実世界の2つのアプリケーション,すなわち,大グラフ上での「emph{maximum coverage」と「emph{personalized recommendation」に示す。
関連論文リスト
- Differentially Private Clustering in Data Streams [65.78882209673885]
オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。
我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
論文 参考訳（メタデータ） (2023-07-14T16:11:22Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Streaming Algorithms for Diversity Maximization with Fairness
Constraints [4.53279507109072]
ストリーミングアルゴリズムは、1回のパスで$X$をシーケンシャルに処理し、フェアネス制約を保証しながら最大emph順序で返却サブセットを処理すべきである。
多様性は一般にNPハードであるため、データストリームの公平な多様性のための2つのアルゴリズムを提案する。
実験の結果,両アルゴリズムは最先端のアルゴリズムに匹敵する品質の解を提供することがわかった。
論文 参考訳（メタデータ） (2022-07-30T11:47:31Z) - The Power of Subsampling in Submodular Maximization [51.629656762796564]
このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。
我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
論文 参考訳（メタデータ） (2021-04-06T20:25:57Z) - Simultaenous Sieves: A Deterministic Streaming Algorithm for
Non-Monotone Submodular Maximization [16.346069386394703]
定性制約に関して、必ずしも単調ではない部分モジュラ函数を最大化する問題に対して、決定論的でシングルパスのストリーミングアルゴリズムを提案する。
単調でシングルパスのストリーミングアルゴリズムでは,従来の文献の1/9ドルから0.2689ドルまで,最高の近似係数の改善を実現している。
論文 参考訳（メタデータ） (2020-10-27T15:22:49Z) - Quick Streaming Algorithms for Maximization of Monotone Submodular
Functions in Linear Time [16.346069386394703]
単調な部分モジュラー(submodular)の問題を、濃度制約に従えば$n$の基底集合上で考える。
線形時間複雑性を持つ最初の決定論的アルゴリズムを導入し,これらのアルゴリズムはストリーミングアルゴリズムである。
我々のシングルパスアルゴリズムは任意の$c ge 1$に対して$lceil n / c rceil + c$ oracle クエリの定数比を得る。
論文 参考訳（メタデータ） (2020-09-10T16:35:54Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z) - Linear-Time Algorithms for Adaptive Submodular Maximization [17.19443570570189]
まず, 濃度制約を考慮した適応的部分モジュラー問題を提案する。
第二に、完全適応部分モジュラリティの概念を導入する。
提案アルゴリズムは,O(nlogfrac1epsilon)$関数の評価値のみを用いて,$frac1-1/e-epsilon4-2/e-2epsilon$近似比を実現する。
論文 参考訳（メタデータ） (2020-07-08T15:54:28Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Submodular Maximization in Clean Linear Time [42.51873363778082]
我々は,濃度(サイズ)制約下での部分モジュライメーションの厳密な1-1/e$近似を保証する,最初の決定論的アルゴリズムを提供する。
解に対して許容される濃度が一定であるとき、関数評価のサブ線形数を作るアルゴリズムは、任意の定数比を保証できないことを示す。
我々は,映画推薦,位置情報要約,twitterテキスト要約,ビデオ要約など,複数のリアルタイム機械学習アプリケーションにおいて,我々のアルゴリズムを広範囲に評価する。
論文 参考訳（メタデータ） (2020-06-16T17:06:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。