論文の概要: Core-sets for Fair and Diverse Data Summarization
- arxiv url: http://arxiv.org/abs/2310.08122v1
- Date: Thu, 12 Oct 2023 08:24:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-15 10:59:56.711025
- Title: Core-sets for Fair and Diverse Data Summarization
- Title（参考訳）: フェアおよびディバースデータ要約のためのコアセット
- Authors: Sepideh Mahabadi and Stojan Trajanovski
- Abstract要約: フェアネス/パーティション制約下での多様性最大化処理のコアセット構築アルゴリズムについて検討する。
本論文では,データセットのサイズとアスペクト比によらずに大きさが依存する,第1の定数係数コアセットw.r.t.和対ペアワイズ距離を示す。
特に、制約付き多様性を適用して、メッセージの正確性を考慮に入れた時間付きメッセージの集合を要約する。
- 参考スコア（独自算出の注目度）: 5.424775372322808
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study core-set construction algorithms for the task of Diversity
Maximization under fairness/partition constraint. Given a set of points $P$ in
a metric space partitioned into $m$ groups, and given $k_1,\ldots,k_m$, the
goal of this problem is to pick $k_i$ points from each group $i$ such that the
overall diversity of the $k=\sum_i k_i$ picked points is maximized. We consider
two natural diversity measures: sum-of-pairwise distances and
sum-of-nearest-neighbor distances, and show improved core-set construction
algorithms with respect to these measures. More precisely, we show the first
constant factor core-set w.r.t. sum-of-pairwise distances whose size is
independent of the size of the dataset and the aspect ratio. Second, we show
the first core-set w.r.t. the sum-of-nearest-neighbor distances. Finally, we
run several experiments showing the effectiveness of our core-set approach. In
particular, we apply constrained diversity maximization to summarize a set of
timed messages that takes into account the messages' recency. Specifically, the
summary should include more recent messages compared to older ones. This is a
real task in one of the largest communication platforms, affecting the
experience of hundreds of millions daily active users. By utilizing our
core-set method for this task, we achieve a 100x speed-up while losing the
diversity by only a few percent. Moreover, our approach allows us to improve
the space usage of the algorithm in the streaming setting.
- Abstract（参考訳）: フェアネス/パーティション制約下での多様性最大化処理のコアセット構築アルゴリズムについて検討する。
計量空間において、$m$群に分割され、$k_1,\ldots,k_m$が与えられる点の集合が与えられたとき、この問題の目標は、$k_i$を各群$i$から選ぶことであり、$k=\sum_i k_i$の選択点全体の多様性を最大化することである。
我々は,2つの自然多様性尺度について考察し,これらの尺度についてコアセット構築アルゴリズムの改善を示す。
より正確には、データセットのサイズとアスペクト比によらずに大きさが依存する第1の定数係数コアセットw.r.t.和対ペアワイズ距離を示す。
第二に、最初のコアセット w.r.t. のアレスト近傍距離を示す。
最後に,コアセットアプローチの有効性を示す実験をいくつか実施した。
特に,制約付き多様性の最大化を適用し,メッセージの相対性を考慮した時系列メッセージの集合を要約する。
特に要約には、古いものよりも最近のメッセージを含めるべきである。
これは、最大規模のコミュニケーションプラットフォームの1つで、数億人のアクティブユーザーの体験に影響を与える真のタスクである。
このタスクのコアセット手法を利用することで,多様性をわずかに損なうことなく,100倍の高速化を実現した。
さらに,このアプローチにより,ストリーミング環境におけるアルゴリズムの空間使用率の向上が期待できる。
関連論文リスト
- Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights [16.120911591795295]
一部のアプリケーションでは、すべてのデータポイントをセンターとして選択できるが、一般的な設定では、施設またはサプライヤーと呼ばれる一連のポイントからセンターを選択する必要がある。
そこで本研究では,複数のグループから構成されるデータに対して,各グループから最小限のセンタを選択する必要がある,公平な$k$-supplier問題としてモデル化された公平なデータ要約に焦点を当てる。
論文 参考訳（メタデータ） (2024-10-16T18:00:19Z) - A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
サブセット選択は、トレーニングデータの小さな部分を特定する上で重要な役割を果たす、基本的な問題である。
我々は,k中心および不確かさサンプリング目的関数の重み付け和に基づいて,サブセットを計算する新しい係数3近似アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-12-17T04:41:07Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - 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) - Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms [56.08144272945755]
我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。
使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。
我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
論文 参考訳（メタデータ） (2023-06-29T14:57:56Z) - Max-Min Diversification with Fairness Constraints: Exact and
Approximation Algorithms [17.57585822765145]
本稿では,小データセットに適した正確なアルゴリズムと,大データセットにスケールする任意の$varepsilon in (0, 1)$に対して$frac1-varepsilon integer 5$-approximationアルゴリズムを提案する。
実世界のデータセットに対する実験は、提案アルゴリズムが既存のデータセットよりも優れていることを示す。
論文 参考訳（メタデータ） (2023-01-05T13:02:35Z) - Robust Multi-Object Tracking by Marginal Inference [92.48078680697311]
ビデオにおける多目的追跡は、隣接するフレーム内のオブジェクト間の1対1の割り当てに関する根本的な問題を解決する必要がある。
本稿では,各オブジェクトの限界確率をリアルタイムに計算する効率的な手法を提案する。
MOT17とMOT20ベンチマークで競合する結果を得る。
論文 参考訳（メタデータ） (2022-08-07T14:04:45Z) - Streaming Algorithms for Diversity Maximization with Fairness
Constraints [4.53279507109072]
ストリーミングアルゴリズムは、1回のパスで$X$をシーケンシャルに処理し、フェアネス制約を保証しながら最大emph順序で返却サブセットを処理すべきである。
多様性は一般にNPハードであるため、データストリームの公平な多様性のための2つのアルゴリズムを提案する。
実験の結果,両アルゴリズムは最先端のアルゴリズムに匹敵する品質の解を提供することがわかった。
論文 参考訳（メタデータ） (2022-07-30T11:47:31Z) - Introduction to Core-sets: an Updated Survey [18.059360820527687]
機械学習問題では、ある候補解の空間上での目的関数の最小化または最大化が目的である。
従来のアルゴリズムは、無限分散ストリームの並列リアルタイム計算を必要とする現代のシステムを扱うことはできない。
この調査は、こうした構成をふりかえりとして要約し、最先端を統一し、単純化することを目的としている。
論文 参考訳（メタデータ） (2020-11-18T16:31:34Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。