論文の概要: Optimal Sampling Gaps for Adaptive Submodular Maximization
- arxiv url: http://arxiv.org/abs/2104.01750v1
- Date: Mon, 5 Apr 2021 03:21:32 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-07 00:13:57.591623
- Title: Optimal Sampling Gaps for Adaptive Submodular Maximization
- Title（参考訳）: 適応サブモジュラー最大化のための最適サンプリングギャップ
- Authors: Shaojie Tang, Jing Yuan
- Abstract要約: アダプティブサブモジュラの文脈における確率サンプリングによる性能損失について検討する。
ポリシワイズ・サブモジュラの性質は、現実世界の幅広いアプリケーションで見つけることができることを示しています。
- 参考スコア（独自算出の注目度）: 28.24164217929491
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Running machine learning algorithms on large and rapidly growing volumes of
data are often computationally expensive, one common trick to reduce the size
of a data set, and thus reduce the computational cost of machine learning
algorithms, is \emph{probability sampling}. It creates a sampled data set by
including each data point from the original data set with a known probability.
Although the benefit of running machine learning algorithms on the reduced data
set is obvious, one major concern is that the performance of the solution
obtained from samples might be much worse than that of the optimal solution
when using the full data set. In this paper, we examine the performance loss
caused by probability sampling in the context of adaptive submodular
maximization. We consider a easiest probability sampling method which selects
each data point independently with probability $r\in[0,1]$. We define sampling
gap as the largest ratio of the optimal solution obtained from the full data
set and the optimal solution obtained from the samples, over independence
systems. Our main contribution is to show that if the utility function is
policywise submodular, then for a given sampling rate $r$, the sampling gap is
both upper bounded and lower bounded by $1/r$. One immediate implication of our
result is that if we can find an $\alpha$-approximation solution based on a
sampled data set (which is sampled at sampling rate $r$), then this solution
achieves an $\alpha r$ approximation ratio for the original problem when using
the full data set. We also show that the property of policywise submodular can
be found in a wide range of real-world applications, including pool-based
active learning and adaptive viral marketing.
- Abstract（参考訳）: 大規模で急速に増加するデータで機械学習アルゴリズムを実行することは、しばしば計算コストが高く、データセットのサイズを小さくし、機械学習アルゴリズムの計算コストを削減しようとする一般的なトリックは、 \emph{probability sampling}である。
既知の確率で、元のデータセットから各データポイントを含むことで、サンプルデータセットを作成する。
削減データセット上で機械学習アルゴリズムを実行するメリットは明らかだが、サンプルから得られたソリューションのパフォーマンスが、完全なデータセットを使用する際の最適ソリューションよりもはるかに悪い可能性がある、という大きな懸念がある。
本稿では,適応サブモジュラー最大化の文脈における確率サンプリングによる性能損失について検討する。
確率$r\in[0,1]$と独立に各データポイントを選択する最も簡単な確率サンプリング法を考える。
我々は,サンプリングギャップを,全データセットから得られる最適解と,サンプルから得られる最適解の最大比として独立系上で定義する。
我々の主な貢献は、ユーティリティ関数がポリシー的に部分モジュラーならば、与えられたサンプリングレート$r$に対して、サンプリングギャップは上界と下界の両方が1/r$であることを示すことである。
結果の直接的な意味は、サンプルデータセット(サンプリングレート$r$でサンプリングされる)に基づいて$\alpha$-approximationソリューションを見つけることができれば、このソリューションは、全データセットを使用する際の元の問題に対する$\alpha r$ approximation比を達成できるということである。
また,プールベースのアクティブラーニングや適応型バイラルマーケティングなど,多岐にわたる実世界の応用において,政策的に準モジュラーの性質が見いだせることを示す。
関連論文リスト
- Data-Efficient Learning via Clustering-Based Sensitivity Sampling:
Foundation Models and Beyond [28.651041302245538]
我々は$k$-meansクラスタリングとサンプリング感度に基づく新しいデータ選択手法を提案する。
線形回帰にどのように適用できるかを示すとともに,レバレッジスコアサンプリングの性能と驚くほど一致した新しいサンプリング戦略がもたらされる。
論文 参考訳（メタデータ） (2024-02-27T09:03:43Z) - Optimize-via-Predict: Realizing out-of-sample optimality in data-driven
optimization [0.0]
本稿では,データ駆動最適化の定式化について検討する。
我々は、規範的なソリューションを、そのようなデータセットを意思決定にマッピングする意思決定者ルールとして定義する。
本稿では,このようなサンプル外最適解に対して,サンプリングアルゴリズムと2分割探索アルゴリズムを組み合わせることで効率よく解ける最適化問題を提案する。
論文 参考訳（メタデータ） (2023-09-20T08:48:50Z) - Multisample Flow Matching: Straightening Flows with Minibatch Couplings [38.82598694134521]
連続時間生成モデルを訓練するためのシミュレーション不要な手法は、ノイズ分布と個々のデータサンプルの間の確率経路を構築する。
データとノイズサンプル間の非自明な結合を利用するより一般的なフレームワークであるMultisample Flow Matchingを提案する。
提案手法は,イメージネットデータセットのサンプル一貫性を向上し,低コストなサンプル生成に繋がることを示す。
論文 参考訳（メタデータ） (2023-04-28T11:33:08Z) - Towards Automated Imbalanced Learning with Deep Hierarchical
Reinforcement Learning [57.163525407022966]
不均衡学習はデータマイニングにおいて基本的な課題であり、各クラスにトレーニングサンプルの不均等な比率が存在する。
オーバーサンプリングは、少数民族のための合成サンプルを生成することによって、不均衡な学習に取り組む効果的な手法である。
我々は,異なるレベルの意思決定を共同で最適化できる自動オーバーサンプリングアルゴリズムであるAutoSMOTEを提案する。
論文 参考訳（メタデータ） (2022-08-26T04:28:01Z) - Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
我々は、勾配降下(SGD)による頑健な回帰を解くためのデータ構造を導入する。
我々のアルゴリズムは、サブ線形空間を使用し、データに1回パスするだけで、SGDの$T$ステップを重要サンプリングで効果的に実行します。
論文 参考訳（メタデータ） (2022-07-16T03:09:30Z) - Local policy search with Bayesian optimization [73.0364959221845]
強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。
局所探索のための政策勾配は、しばしばランダムな摂動から得られる。
目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-06-22T16:07:02Z) - Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature
Selection [138.97647716793333]
再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。
提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
論文 参考訳（メタデータ） (2020-12-29T04:08:38Z) - Sampling from a $k$-DPP without looking at all items [58.30573872035083]
カーネル関数とサブセットサイズ$k$が与えられた場合、我々のゴールは、サブセットによって誘導されるカーネル行列の行列式に比例する確率を持つ$n$アイテムから$k$をサンプリングすることである(つまり$k$-DPP)。
既存の$k$-DPPサンプリングアルゴリズムは、すべての$n$アイテムを複数回パスする高価な前処理ステップを必要とするため、大規模なデータセットでは利用できない。
そこで我々は, 十分大きなデータの均一なサンプルを適応的に構築し, より小さな$k$のアイテムを効率よく生成するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2020-06-30T16:40:44Z) - Optimal Distributed Subsampling for Maximum Quasi-Likelihood Estimators
with Massive Data [20.79270369203348]
既存の手法は主に高い計算効率のために置換されたサブサンプリングに焦点を当てている。
まず,準類似度推定の文脈で最適なサブサンプリング確率を導出する。
我々は,分散サブサンプリングフレームワークを開発し,全データの小さなパーティションで統計を同時に計算する。
論文 参考訳（メタデータ） (2020-05-21T02:46:56Z) - Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。
我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文 参考訳（メタデータ） (2020-04-23T05:00:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。