論文の概要: MCRapper: Monte-Carlo Rademacher Averages for Poset Families and
Approximate Pattern Mining
- arxiv url: http://arxiv.org/abs/2006.09085v1
- Date: Tue, 16 Jun 2020 11:42:56 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-20 20:02:00.936967
- Title: MCRapper: Monte-Carlo Rademacher Averages for Poset Families and
Approximate Pattern Mining
- Title（参考訳）: MCRapper:Monte-Carlo Rademacher平均値と近似パターンマイニング
- Authors: Leonardo Pellegrina, Cyrus Cousins, Fabio Vandin, Matteo Riondato
- Abstract要約: モンテカルロ実験ラデマチャー平均値(MCERA)の効率的な計算アルゴリズムであるMCRapperを提案する。
MCRapperは、利用可能なデータが未知の分布からのサンプルと見なされるときの統計的に重要な関数(パターンなど)と、利用可能なデータが大きなデータセットからの小さなサンプルであるときの高次関数(頻繁なパターンなど)の集合の近似の両方を計算する。
- 参考スコア（独自算出の注目度）: 22.88915237311897
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present MCRapper, an algorithm for efficient computation of Monte-Carlo
Empirical Rademacher Averages (MCERA) for families of functions exhibiting
poset (e.g., lattice) structure, such as those that arise in many pattern
mining tasks. The MCERA allows us to compute upper bounds to the maximum
deviation of sample means from their expectations, thus it can be used to find
both statistically-significant functions (i.e., patterns) when the available
data is seen as a sample from an unknown distribution, and approximations of
collections of high-expectation functions (e.g., frequent patterns) when the
available data is a small sample from a large dataset. This feature is a strong
improvement over previously proposed solutions that could only achieve one of
the two. MCRapper uses upper bounds to the discrepancy of the functions to
efficiently explore and prune the search space, a technique borrowed from
pattern mining itself. To show the practical use of MCRapper, we employ it to
develop an algorithm TFP-R for the task of True Frequent Pattern (TFP) mining.
TFP-R gives guarantees on the probability of including any false positives
(precision) and exhibits higher statistical power (recall) than existing
methods offering the same guarantees. We evaluate MCRapper and TFP-R and show
that they outperform the state-of-the-art for their respective tasks.
- Abstract（参考訳）: MCRapperは,多くのパターンマイニングタスクで発生するような,ポーズ(格子)構造を示す関数群に対して,MCERA(Monte-Carlo Empirical Rademacher Averages)の効率的な計算アルゴリズムである。
MCERAは、期待値からサンプル平均の最大偏差に対する上限を計算することができるので、利用可能なデータが未知の分布からサンプルと見なされるとき、統計学的に重要な関数(パターン)と、利用可能なデータが大きなデータセットからの小さなサンプルであるとき、高観測関数(頻繁なパターン)の集合の近似の両方を見つけることができる。
この機能は、以前提案された2つのソリューションのうちの1つしか達成できないような、強力な改善である。
MCRapperは、パターンマイニング自体から借用された手法である探索空間を効率的に探索し、熟成するために、関数の相違に上限を用いる。
MCRapperの実用性を示すため,真周波数パターン(TFP)マイニングのためのアルゴリズムTFP-Rを開発した。
TFP-Rは偽陽性(精度)を含む確率を保証し、同じ保証を提供する既存の方法よりも高い統計的パワー(リコール)を示す。
mcrapper と tfp-r を評価し,各タスクの最先端を上回っていることを示す。
関連論文リスト
- A distribution-guided Mapper algorithm [0.3683202928838613]
本稿ではD-Mapperという分布誘導型Mapperアルゴリズムを提案する。
提案アルゴリズムは確率的モデルに基づく手法であり,非確率的手法の代替となる可能性がある。
数値実験により,D-Mapperは様々なシナリオにおいて従来のMapperアルゴリズムより優れていることが示された。
論文 参考訳（メタデータ） (2024-01-19T17:07:05Z) - Provably Efficient Representation Learning with Tractable Planning in
Low-Rank POMDP [81.00800920928621]
部分的に観測可能なマルコフ決定過程(POMDP)における表現学習の研究
まず,不確実性(OFU)に直面した最大推定(MLE)と楽観性を組み合わせた復調性POMDPのアルゴリズムを提案する。
次に、このアルゴリズムをより広範な$gamma$-observable POMDPのクラスで機能させる方法を示す。
論文 参考訳（メタデータ） (2023-06-21T16:04:03Z) - Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。
まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。
次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
論文 参考訳（メタデータ） (2022-08-17T18:49:53Z) - Low-variance estimation in the Plackett-Luce model via quasi-Monte Carlo
sampling [58.14878401145309]
PLモデルにおいて,より標本効率の高い予測値を生成するための新しい手法を開発した。
Amazon MusicのリアルなレコメンデーションデータとYahooの学習からランクへの挑戦を理論的にも実証的にも使用しています。
論文 参考訳（メタデータ） (2022-05-12T11:15:47Z) - Flexible Pattern Discovery and Analysis [2.075126998649103]
フレキシブルな高ユーティリティ占有パターンのマイニングのためのアルゴリズムを導入する。
提案アルゴリズムは,実世界のデータセットと合成データセットの両方に対して,抽出したパターンの長さを効果的に制御することができる。
論文 参考訳（メタデータ） (2021-11-24T01:25:15Z) - GFlowNet Foundations [66.69854262276391]
Generative Flow Networks (GFlowNets) は、多様な候補をアクティブな学習コンテキストでサンプリングする方法として導入された。
GFlowNetのさらなる理論的性質について述べる。
論文 参考訳（メタデータ） (2021-11-17T17:59:54Z) - Leverage Score Sampling for Complete Mode Coverage in Generative
Adversarial Networks [11.595070613477548]
生成モデルは、経験的データ分布の頻度が低い、表現不足のモードを見落とすことができる。
リッジレバレッジスコアに基づくサンプリング手順を提案し、標準手法と比較してモードカバレッジを大幅に向上させます。
論文 参考訳（メタデータ） (2021-04-06T09:00:38Z) - Efficient semidefinite-programming-based inference for binary and
multi-class MRFs [83.09715052229782]
分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。
一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
論文 参考訳（メタデータ） (2020-12-04T15:36:29Z) - Particle-Gibbs Sampling For Bayesian Feature Allocation Models [77.57285768500225]
最も広く使われているMCMC戦略は、特徴割り当て行列のギブス更新に頼っている。
単一移動で特徴割り当て行列の全行を更新できるギブスサンプリング器を開発した。
このサンプルは、計算複雑性が特徴数で指数関数的にスケールするにつれて、多数の特徴を持つモデルにとって実用的ではない。
我々は,行ワイズギブズ更新と同じ分布を目標としたパーティクルギブズサンプルの開発を行うが,特徴数でのみ線形に増大する計算複雑性を有する。
論文 参考訳（メタデータ） (2020-01-25T22:11:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。