論文の概要: Parallel Tree Kernel Computation
- arxiv url: http://arxiv.org/abs/2305.07717v1
- Date: Fri, 12 May 2023 18:16:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-16 20:06:43.464076
- Title: Parallel Tree Kernel Computation
- Title(参考訳): 並列木核計算
- Authors: Souad Taouti, Hadda Cherroun and Djelloul Ziadi
- Abstract要約: 2つの有限木からなる木核の計算のための逐次アルゴリズムの並列実装を考案する。
その結果,提案した並列アルゴリズムは遅延の点で逐次アルゴリズムよりも優れていることがわかった。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Tree kernels are fundamental tools that have been leveraged in many
applications, particularly those based on machine learning for Natural Language
Processing tasks. In this paper, we devise a parallel implementation of the
sequential algorithm for the computation of some tree kernels of two finite
sets of trees (Ouali-Sebti, 2015). Our comparison is narrowed on a sequential
implementation of SubTree kernel computation. This latter is mainly reduced to
an intersection of weighted tree automata. Our approach relies on the nature of
the data parallelism source inherent in this computation by deploying the
MapReduce paradigm. One of the key benefits of our approach is its versatility
in being adaptable to a wide range of substructure tree kernel-based learning
methods. To evaluate the efficacy of our parallel approach, we conducted a
series of experiments that compared it against the sequential version using a
diverse set of synthetic tree language datasets that were manually crafted for
our analysis. The reached results clearly demonstrate that the proposed
parallel algorithm outperforms the sequential one in terms of latency.
- Abstract(参考訳): ツリーカーネルは多くのアプリケーション、特に自然言語処理タスクのための機械学習に基づくツールで活用されている。
本稿では,二つの有限木集合の木核計算のための逐次アルゴリズムの並列的実装を考案する(ouali-sebti, 2015)。
比較対象はサブツリーカーネル計算の逐次実装である。
後者は、主に加重木オートマトンとの交点に還元される。
我々のアプローチは、MapReduceパラダイムをデプロイすることで、この計算に固有のデータ並列性源の性質に依存します。
このアプローチの重要な利点の1つは、幅広いサブ構造木カーネルベースの学習手法に適応できることの汎用性である。
並列手法の有効性を評価するために,手作業で解析を行った多種多様な合成木言語データセットを用いて,逐次バージョンと比較した一連の実験を行った。
その結果,提案した並列アルゴリズムは遅延の点で逐次アルゴリズムよりも優れていることが示された。
関連論文リスト
- Optimal estimation of Gaussian (poly)trees [25.02920605955238]
分布学習(KL距離)と構造学習(正確な回復)の両問題を考察する。
最初のアプローチはChow-Liuアルゴリズムに基づいており、最適な木構造分布を効率的に学習する。
第2のアプローチは、制約に基づく構造学習のための条件付き独立試験器として部分相関を用いたポリツリーに対するPCアルゴリズムの修正である。
論文 参考訳(メタデータ) (2024-02-09T12:58:36Z) - Learning a Decision Tree Algorithm with Transformers [80.49817544396379]
本稿では,従来のアルゴリズムから出力されたフィルタを用いてトランスフォーマーモデルを用いて,分類のための強力な決定木を生成するメタトレーについて紹介する。
次にMetaTreeをトレーニングして、強力な一般化パフォーマンスを実現するツリーを生成します。
論文 参考訳(メタデータ) (2024-02-06T07:40:53Z) - New Linear-time Algorithm for SubTree Kernel Computation based on
Root-Weighted Tree Automata [0.0]
本稿では,SubTreeカーネル計算のための重み付き木オートマトンの概念に基づく線形時間アルゴリズムを提案する。
提案アルゴリズムの主な考え方は、DAGの削減とノードのソートを置き換えることである。
我々のアプローチには3つの大きな利点がある:それは出力に敏感であり、木の種類(順序のない木と順序のない木)に敏感であり、インクリメンタルな木カーネルベースの学習手法によく適応している。
論文 参考訳(メタデータ) (2023-02-02T13:37:48Z) - Single MCMC Chain Parallelisation on Decision Trees [0.9137554315375919]
本稿では,平均的なラップトップやパソコン上でMCMC決定ツリーチェーンを並列化する手法を提案する。
実験の結果,シリアルと並列実装が統計的に同一である場合,実行時間を18倍に向上できることがわかった。
論文 参考訳(メタデータ) (2022-07-26T07:07:51Z) - Tree ensemble kernels for Bayesian optimization with known constraints
over mixed-feature spaces [54.58348769621782]
木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。
ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。
我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
論文 参考訳(メタデータ) (2022-07-02T16:59:37Z) - Reinforcement Learning for Branch-and-Bound Optimisation using
Retrospective Trajectories [72.15369769265398]
機械学習は分岐のための有望なパラダイムとして登場した。
分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。
我々は現在最先端のRL分岐アルゴリズムを3~5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
論文 参考訳(メタデータ) (2022-05-28T06:08:07Z) - Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and
Hierarchical Spatial Clustering [6.4805900740861]
HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。
我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。
48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
論文 参考訳(メタデータ) (2021-04-02T16:05:00Z) - Learning Binary Decision Trees by Argmin Differentiation [34.9154848754842]
ダウンストリームタスクのためにデータを分割するバイナリ決定木を学びます。
離散パラメータの混合整数プログラムを緩和する。
我々は、前方と後方のパスを効率的に計算するアルゴリズムを考案した。
論文 参考訳(メタデータ) (2020-10-09T15:11:28Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳(メタデータ) (2020-08-29T14:58:26Z) - MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。
当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
論文 参考訳(メタデータ) (2020-07-24T17:06:55Z) - On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
モンテカルロ木探索(MCTS)は、探索木を構築するためにかなりの数のロールアウトを必要とするため、計算コストがかかる。
効果的な並列MCTSアルゴリズムを設計する方法は、体系的に研究されておらず、まだよく分かっていない。
我々は,より効率的な並列MCTSアルゴリズムの設計に,提案する必要条件をどのように適用できるかを実証する。
論文 参考訳(メタデータ) (2020-06-15T21:36:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。