論文の概要: A New Algorithm based on Extent Bit-array for Computing Formal Concepts
- arxiv url: http://arxiv.org/abs/2111.00003v1
- Date: Fri, 29 Oct 2021 01:45:41 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-05 05:29:37.005057
- Title: A New Algorithm based on Extent Bit-array for Computing Formal Concepts
- Title（参考訳）: 正規概念計算のための拡張ビットアレイに基づく新しいアルゴリズム
- Authors: Jianqin Zhou, Sichun Yang, Xifeng Wang and Wanquan Liu
- Abstract要約: 本稿では,In-Close5と呼ばれるコンテキストの垂直記憶に基づく新しいアルゴリズムIn-Close4を提案する。
新しいアルゴリズムは、コンセプトのコンテキストと範囲を垂直ビットアレイとして格納する一方、In-Close4アルゴリズムでは、コンテキストは水平ビットアレイとしてのみ格納する。
実験の結果,提案アルゴリズムはIn-Close4アルゴリズムよりもはるかに有効であり,また形式的概念の計算にも適用範囲が広いことがわかった。
- 参考スコア（独自算出の注目度）: 5.657202839641533
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The emergence of Formal Concept Analysis (FCA) as a data analysis technique
has increased the need for developing algorithms which can compute formal
concepts quickly. The current efficient algorithms for FCA are variants of the
Close-By-One (CbO) algorithm, such as In-Close2, In-Close3 and In-Close4, which
are all based on horizontal storage of contexts. In this paper, based on
algorithm In-Close4, a new algorithm based on the vertical storage of contexts,
called In-Close5, is proposed, which can significantly reduce both the time
complexity and space complexity of algorithm In-Close4. Technically, the new
algorithm stores both context and extent of a concept as a vertical bit-array,
while within In-Close4 algorithm the context is stored only as a horizontal
bit-array, which is very slow in finding the intersection of two extent sets.
Experimental results demonstrate that the proposed algorithm is much more
effective than In-Close4 algorithm, and it also has a broader scope of
applicability in computing formal concept in which one can solve the problems
that cannot be solved by the In-Close4 algorithm.
- Abstract（参考訳）: データ解析手法としての形式概念解析(FCA)の出現により,形式概念を迅速に計算できるアルゴリズムの開発の必要性が高まっている。
現在のfcaの効率的なアルゴリズムは、in-close2、in-close3、in-close4などのcbo(close-by-one)アルゴリズムの変種である。
本稿では,in-close4アルゴリズムに基づいて,in-close5と呼ばれるコンテキストの垂直記憶に基づく新しいアルゴリズムを提案し,in-close4アルゴリズムの時間的複雑さと空間的複雑さの両方を著しく低減する。
技術的には、新しいアルゴリズムは概念のコンテキストと範囲の両方を垂直ビットアレイとして保存するが、in-close4アルゴリズムではコンテキストは水平ビットアレイとしてのみ保存される。
実験の結果,提案アルゴリズムはin-close4アルゴリズムよりもはるかに有効であること,およびin-close4アルゴリズムでは解決できない問題を解くことができる形式概念の計算における適用範囲が広いことが判明した。
関連論文リスト
- Approximation Algorithms for Preference Aggregation Using CP-Nets [3.337244446073836]
本稿では,条件付き選好ネットワーク(CP-nets)上での選好を集約する近似アルゴリズムの設計と解析について述べる。
その焦点は、一般に最適な解が指数関数的な大きさであることが知られている、いわゆる「エンフスワップ」よりも、優先的な選好を集約することである。
論文 参考訳（メタデータ） (2023-12-14T17:31:38Z) - From Optimization to Control: Quasi Policy Iteration [3.4376560669160394]
準政治反復(QPI)と呼ばれる新しい制御アルゴリズムを提案する。
QPIは、政策反復アルゴリズムにおける「ヘシアン」行列の新たな近似に基づいて、MDPに特有の2つの線形構造制約を利用する。
これは、割引係数に対する感度が極めて低い政策反復と同様の実証的な収束挙動を示す。
論文 参考訳（メタデータ） (2023-11-18T21:00:14Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - A Fully Single Loop Algorithm for Bilevel Optimization without Hessian
Inverse [121.54116938140754]
両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。
我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
論文 参考訳（メタデータ） (2021-12-09T02:27:52Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Approximation Algorithms for Sparse Best Rank-1 Approximation to
Higher-Order Tensors [1.827510863075184]
スパーステンソル最高ランク1近似(英: Sparse tensor best rank-1 approximation, BR1Approx)は、密度テンソルBR1Approxの空間一般化である。
低計算量で容易に実装できる4つの近似アルゴリズムが提案されている。
提案手法の有効性を示すために,合成および実データに関する数値実験を行った。
論文 参考訳（メタデータ） (2020-12-05T18:13:14Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳（メタデータ） (2020-07-01T18:43:32Z) - SONIA: A Symmetric Blockwise Truncated Optimization Algorithm [2.9923891863939938]
本研究は, 経験的リスクに対する新しいアルゴリズムを提案する。
このアルゴリズムは、一部分空間における二階探索型更新を計算し、1階探索法と2階探索法の間のギャップを埋める。
論文 参考訳（メタデータ） (2020-06-06T19:28:14Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。