論文の概要: Very Fast Streaming Submodular Function Maximization

• arxiv url: http://arxiv.org/abs/2010.10059v5
• Date: Sat, 8 May 2021 21:11:53 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-05 06:36:28.224246
• Title: Very Fast Streaming Submodular Function Maximization
• Title（参考訳）: 超高速ストリーミングサブモジュール関数最大化
• Authors: Sebastian Buschj\"ager, Philipp-Jan Honysz, Lukas Pfahler, Katharina Morik
• Abstract要約: サブモジュール関数アルゴリズムは、より高い計算とメモリ要求を犠牲にして最悪のケース近似を提供する。 我々は,最悪のケースを無視するが,高い確率で優れた解を提供する3-Sievesと呼ばれる新しい部分モジュラ関数アルゴリズムを提案する。 我々のアルゴリズムは現在の最先端のアルゴリズムよりも優れており、同時にリソースが少ないことも示している。
• 参考スコア（独自算出の注目度）: 6.734843312980923
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Data summarization has become a valuable tool in understanding even terabytes of data. Due to their compelling theoretical properties, submodular functions have been in the focus of summarization algorithms. These algorithms offer worst-case approximations guarantees to the expense of higher computation and memory requirements. However, many practical applications do not fall under this worst-case, but are usually much more well-behaved. In this paper, we propose a new submodular function maximization algorithm called ThreeSieves, which ignores the worst-case, but delivers a good solution in high probability. It selects the most informative items from a data-stream on the fly and maintains a provable performance on a fixed memory budget. In an extensive evaluation, we compare our method against $6$ other methods on $8$ different datasets with and without concept drift. We show that our algorithm outperforms current state-of-the-art algorithms and, at the same time, uses fewer resources. Last, we highlight a real-world use-case of our algorithm for data summarization in gamma-ray astronomy. We make our code publicly available at https://github.com/sbuschjaeger/SubmodularStreamingMaximization.
• Abstract（参考訳）: データ要約はテラバイト単位のデータを理解する上で貴重なツールになっている。 その説得力のある理論的な性質から、サブモジュラー関数は要約アルゴリズムの焦点となっている。 これらのアルゴリズムは、より高い計算とメモリ要求を犠牲にして最悪の近似を提供する。 しかし、多くの実用的アプリケーションは、この最悪のケースに該当しないが、通常、ずっとうまく機能している。 本稿では,最悪のケースを無視するが,高い確率で優れた解を提供する3-Sievesという,新しい部分モジュラ関数最大化アルゴリズムを提案する。 オンザフライでデータストリームから最も有用な項目を選択し、固定メモリ予算で証明可能なパフォーマンスを維持する。 広範な評価では,8ドルの異なるデータセット上の6ドルの他の手法と,概念ドリフトの有無を比較した。 我々のアルゴリズムは現在の最先端のアルゴリズムよりも優れており、同時にリソースが少ないことも示している。 最後に,ガンマ線天文学におけるデータ要約のための実例を紹介する。 コードをhttps://github.com/sbuschjaeger/SubmodularStreamingMaximizationで公開しています。

関連論文リスト

• Linear Submodular Maximization with Bandit Feedback [7.926559636438099]
  準モジュラー目的関数 $f:2UtomathbbR_geq 0$, ここでは $f=sum_i=1dw_iF_i$ に対する近似アルゴリズムの開発を検討する。 F_i$ 関数へのオラクルアクセスが期待できるが、係数 $w_i$ は未知であり、$f$ はノイズの多いクエリによってのみアクセス可能である。 我々のアルゴリズムは、$fの線形構造を利用していないアルゴリズムと比較して、サンプル効率の点で大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2024-07-02T18:40:52Z)
• Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint [18.290666675596984]
  非単調制約部分モジュラー・サブアニメーションは、様々な機械学習応用において重要な役割を果たす。 既存のアルゴリズムは、近似保証と実用効率のトレードオフにしばしば苦労する。 我々は,$0.385$-approximationの保証と$O(n+k2)$の低い,実用的なクエリ複雑性を組み合わせた新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-22T20:56:57Z)
• Fast Submodular Function Maximization [15.090593955414137]
  部分モジュラ関数の最大値を効率的に計算する方法を検討する。 各イテレーションでは、データセットは漸進的に変更されるか変更されない。 本稿では,新しい探索木データ構造に基づく新しい手法を提案する。本アルゴリズムでは,$widetildeO(nk + kd2 + nd)$時間のみを要している。
  論文  参考訳（メタデータ） (2023-05-15T06:00:02Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
  論文  参考訳（メタデータ） (2023-02-22T20:21:25Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Providing Meaningful Data Summarizations Using Examplar-based Clustering in Industry 4.0 [67.80123919697971]
  我々は,従来のCPUアルゴリズムと比較して,一精度で最大72倍,半精度で最大452倍の高速化を実現していることを示す。 提案アルゴリズムは射出成形プロセスから得られた実世界のデータに適用し, 得られたサマリーが, コスト削減と不良部品製造の削減のために, この特定のプロセスのステアリングにどのように役立つかについて議論する。
  論文  参考訳（メタデータ） (2021-05-25T15:55:14Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。 本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。 これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
  論文  参考訳（メタデータ） (2021-04-19T17:22:11Z)
• Fair and Representative Subset Selection from Data Streams [4.53279507109072]
  ストリーム内のデータ項目が複数の不随意群に属する設定について検討する。 ストリーミングサブモジュラー問題の公平性を考慮した変種に対する効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-09T07:49:13Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)
• New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
  微分プライベートな合成データを構築するための3つの新しいアルゴリズムを提案する。 アルゴリズムは最悪の場合でも差分プライバシーを満たす。 現状の手法である高次元行列機構 citeMcKennaMHM18 と比較すると,我々のアルゴリズムは大規模作業負荷の精度が向上する。
  論文  参考訳（メタデータ） (2020-07-10T15:46:05Z)
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint [13.357957711519134]
  制約されたサブモジュール問題には、パーソナライズされたレコメンデーション、チーム形成、バイラルマーケティングによる収益化など、さまざまな応用が含まれている。 我々は5.83のランダム化近似を達成し、O(n log n)$禁断時間、すなわち少なくとも$n$を他の最先端アルゴリズムよりも高速に実行する単純なグリーディアルゴリズムを提案する。 そこで我々は,非単調な目的に対する最初の定数近似である9-近似を求め,実データと合成データに改良された性能を示すアルゴリズムの実験評価を行った。
  論文  参考訳（メタデータ） (2020-07-09T18:15:01Z)

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

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