Fugu-MT 論文翻訳(概要): Computational Complexity of Three Central Problems in Itemset Mining

論文の概要: Computational Complexity of Three Central Problems in Itemset Mining

arxiv url: http://arxiv.org/abs/2012.02619v3
Date: Tue, 8 Dec 2020 11:17:14 GMT
ステータス: 処理完了
システム内更新日: 2021-05-22 20:36:04.366429
Title: Computational Complexity of Three Central Problems in Itemset Mining
Title（参考訳）: アイテムセットマイニングにおける3つの中心問題の計算複雑性
Authors: Christian Bessiere, Mohamed-Bachir Belaid, Nadjib Lazaar
Abstract要約: 我々は、ある項目の先頭で確実なルールをマイニングすることがNPハードであることを証明した。我々は高ユーティリティアイテムセットのマイニングがNPハードであることを証明する。ユーザが関心のあるアイテムセットの種類に関する制約を指定できれば,最大あるいはクローズドなアイテムセットのマイニングがcoNPハードであることは,最終的に証明できる。
参考スコア（独自算出の注目度）: 11.718110118100048
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Itemset mining is one of the most studied tasks in knowledge discovery. In this paper we analyze the computational complexity of three central itemset mining problems. We prove that mining confident rules with a given item in the head is NP-hard. We prove that mining high utility itemsets is NP-hard. We finally prove that mining maximal or closed itemsets is coNP-hard as soon as the users can specify constraints on the kind of itemsets they are interested in.
Abstract（参考訳）: アイテムセットマイニングは、知識発見において最も研究されているタスクの1つである。本稿では,3つの中央項目のマイニング問題の計算複雑性を解析する。我々は、ある項目の先頭で確実なルールをマイニングすることがNPハードであることを証明する。高ユーティリティアイテムセットのマイニングがNPハードであることを証明する。ユーザが関心のあるアイテムセットの種類に関する制約を指定できれば,最大あるいはクローズドなアイテムセットのマイニングがcoNPハードであることは,最終的に証明できる。

関連論文リスト

Gaussian Prior Reinforcement Learning for Nested Named Entity Recognition [52.46740830977898]
GPRLと呼ばれる新しいSeq2seqモデルを提案し、ネストしたNERタスクをエンティティ三重項列生成プロセスとして定式化する。 3つのネストされたNERデータセットの実験では、GPRLが以前のネストされたNERモデルより優れていることが示されている。
論文参考訳（メタデータ） (2023-05-12T05:55:34Z)
Exceeding Computational Complexity Trial-and-Error Dynamic Action and Intelligence [0.0]
計算複雑性 (Computational complexity) は、計算の難易度を規定する計算機科学のコア理論である。本稿では,概念を明確にし,不特定型コンピューティング,特化型コンピューティング,コンピュータエージェント,動的検索などの定義を提案する。また,このフレームワーク,すなわちトライアル・アンド・エラー+動的検索を提案し,議論する。
論文参考訳（メタデータ） (2022-12-22T21:23:27Z)
Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文参考訳（メタデータ） (2022-09-28T17:53:25Z)
Diversity Over Size: On the Effect of Sample and Topic Sizes for Topic-Dependent Argument Mining Datasets [49.65208986436848]
本研究では,アーギュメント・マイニング・データセットの構成が,少数・ゼロショット設定における影響について検討する。実験結果から, モデル性能の達成には微調整が必須であるが, 慎重に構成したトレーニングサンプルを用いることで, トレーニングサンプルサイズを最大90%まで下げることで, 最大性能の95%を達成できることがわかった。
論文参考訳（メタデータ） (2022-05-23T17:14:32Z)
A Collaboration Strategy in the Mining Pool for Proof-of-Neural-Architecture Consensus [16.372941299296652]
一般に普及している暗号通貨システムでは、マイニングプールが重要な役割を担っている。最近の多くの新しいブロックチェーンコンセンサスにおいて、ディープラーニングトレーニング手順は、マイナーが自身のワークロードを証明するタスクになる。鉱山労働者のインセンティブはトークンを得ることであるが、個々の鉱山労働者はより競争力を高めるために鉱山プールに参加する動機がある。
論文参考訳（メタデータ） (2022-05-05T17:08:02Z)
HDCoin: A Proof-of-Useful-Work Based Blockchain for Hyperdimensional Computing [2.7462881838152913]
本稿では、新しい機械学習スキームのためのブロックチェーンベースのフレームワークであるHDCoinを紹介する。 HDCのシナリオでは、マイナーは与えられたデータセット上で最も高いテスト精度を得るために競争している。勝者のモデルはブロックチェーンに記録されており、信頼できるHDCモデルとして一般に公開されている。
論文参考訳（メタデータ） (2022-02-07T06:21:29Z)
On Theoretical Complexity and Boolean Satisfiability [0.0]
この論文は、コンピューティング理論において最も中心的な概念をいくつか導入している。次に,Hhorn-SAT や 3-SAT などの抽出可能な変種を探索する。最後に,3-SATから有名なNP完全グラフ問題への還元を確立する。
論文参考訳（メタデータ） (2021-12-22T10:13:34Z)
Decomposition algorithms for solving NP-hard problems on a quantum annealer [0.0]
NPハード問題は、計算化学、生化学、コンピュータネットワークセキュリティに応用されている。 Adaabatic quantum annealers can search the optimum value of such NP-hard optimization problem, because the problem can be embedded on their hardware。本稿ではNP-hardグラフ問題に対する分解アルゴリズムの一般的な枠組みについて検討する。
論文参考訳（メタデータ） (2020-09-10T15:59:06Z)
The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
論文参考訳（メタデータ） (2020-07-30T04:18:51Z)
Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
論文参考訳（メタデータ） (2020-06-25T19:59:24Z)
Faster Secure Data Mining via Distributed Homomorphic Encryption [108.77460689459247]
ホモモルフィック暗号化(HE)は、最近、暗号化されたフィールド上で計算を行う能力により、ますます注目を集めている。本稿では,スケーリング問題の解決に向けて,新しい分散HEベースのデータマイニングフレームワークを提案する。各種データマイニングアルゴリズムとベンチマークデータセットを用いて,新しいフレームワークの有効性と有効性を検証する。
論文参考訳（メタデータ） (2020-06-17T18:14:30Z)

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