論文の概要: Lazy and Fast Greedy MAP Inference for Determinantal Point Process

• arxiv url: http://arxiv.org/abs/2206.05947v1
• Date: Mon, 13 Jun 2022 07:33:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-14 17:56:56.764444
• Title: Lazy and Fast Greedy MAP Inference for Determinantal Point Process
• Title（参考訳）: 決定点過程に対する遅延および高速グリーディMAP推論
• Authors: Shinichi Hemmi, Taihei Oki, Shinsaku Sakaue, Kaito Fujii, Satoru Iwata
• Abstract要約: 本稿では,「怠慢」と「速さ」を両立させる手法について述べる。 我々の遅延で高速な欲求アルゴリズムは、現在の最高のアルゴリズムとほぼ同時期に達成し、実際に高速に動作します。
• 参考スコア（独自算出の注目度）: 17.50810164319995
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The maximum a posteriori (MAP) inference for determinantal point processes (DPPs) is crucial for selecting diverse items in many machine learning applications. Although DPP MAP inference is NP-hard, the greedy algorithm often finds high-quality solutions, and many researchers have studied its efficient implementation. One classical and practical method is the lazy greedy algorithm, which is applicable to general submodular function maximization, while a recent fast greedy algorithm based on the Cholesky factorization is more efficient for DPP MAP inference. This paper presents how to combine the ideas of "lazy" and "fast", which have been considered incompatible in the literature. Our lazy and fast greedy algorithm achieves almost the same time complexity as the current best one and runs faster in practice. The idea of "lazy + fast" is extendable to other greedy-type algorithms. We also give a fast version of the double greedy algorithm for unconstrained DPP MAP inference. Experiments validate the effectiveness of our acceleration ideas.
• Abstract（参考訳）: 決定点プロセス(DPP)に対するMAP推論は、多くの機械学習アプリケーションにおいて多様な項目を選択する上で重要である。 DPP MAP推論はNPハードであるが、グリードアルゴリズムはしばしば高品質な解を見つけ、多くの研究者がその効率的な実装を研究している。 古典的かつ実用的な方法の一つが遅延グリーディアルゴリズムであり、これは一般的な部分モジュラー関数の最大化に適用できるが、コレスキー因子分解に基づく最近の高速グリーディアルゴリズムはdpp写像推論より効率的である。 本稿では,文献において相容れないと考えられる「怠け者」と「速い者」の考え方を組み合わせる方法について述べる。 私たちの怠け者で高速な欲望アルゴリズムは、現在の最良のアルゴリズムとほぼ同じ時間複雑性を達成し、実際より速く実行します。 Lazy + fast"というアイデアは他のグリーディ型アルゴリズムにも拡張可能である。 また、制約のない DPP MAP 推論のための二重欲求アルゴリズムの高速版も提供する。 実験は加速アイデアの有効性を検証する。

関連論文リスト

• Optimizing Tensor Contraction Paths: A Greedy Algorithm Approach With Improved Cost Functions [1.3812010983144802]
  より少ない時間で効率的な収縮経路を計算できる opt_einsum による欲求アルゴリズムに基づく新しい手法を提案する。 我々のアプローチでは、現代のアルゴリズムが失敗する大きな問題に対するパスを計算できる。
  論文  参考訳（メタデータ） (2024-05-08T09:25:39Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• FastDiagP: An Algorithm for Parallelized Direct Diagnosis [64.65251961564606]
  FastDiagは、競合を事前に決定せずに診断計算をサポートする典型的な直接診断アルゴリズムである。 本稿では,投機的プログラミングのアイデアに基づく新しいアルゴリズムであるFastDiagPを提案する。 このメカニズムは、高速な回答で一貫性チェックを提供し、アルゴリズムのランタイムパフォーマンスを高めるのに役立つ。
  論文  参考訳（メタデータ） (2023-05-11T16:26:23Z)
• Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
  我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。 我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-11-09T02:33:36Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Waypoint Planning Networks [66.72790309889432]
  本稿では,ローカルカーネル(A*のような古典的アルゴリズム)と学習アルゴリズムを用いたグローバルカーネルを用いたLSTMに基づくハイブリッドアルゴリズムを提案する。 我々は、WPNとA*を比較し、動き計画ネットワーク(MPNet)やバリューネットワーク(VIN)を含む関連する作業と比較する。 WPN の探索空間は A* よりもかなり小さいが、ほぼ最適な結果が得られることが示されている。
  論文  参考訳（メタデータ） (2021-05-01T18:02:01Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Faster Person Re-Identification [68.22203008760269]
  本稿では,新しいハッシュコード検索戦略を定式化することによって,高速ReIDのための新しいソリューションを提案する。 より短いコードを使用して、より正確なReIDのいくつかのトップ候補を洗練するために、より広い一致の類似性を粗くランク付けし、より長いコードを使用する。 2つのデータセットに対する実験結果から,提案手法(CtF)は現在のハッシュReID法よりも8%精度が高いだけでなく,5倍高速であることがわかった。
  論文  参考訳（メタデータ） (2020-08-16T03:02:49Z)
• Performance Analysis of Meta-heuristic Algorithms for a Quadratic Assignment Problem [6.555180412600522]
  二次代入問題 (QAP) はNPハード問題に属する最適化問題である。 ヒューリスティックスとメタヒューリスティックスアルゴリズムはこの問題の一般的な解法である。 本稿では,QAPの解法に異なるメタヒューリスティックアルゴリズムを適用するための比較研究の1つである。
  論文  参考訳（メタデータ） (2020-07-29T15:02:07Z)

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

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