論文の概要: New Linear-time Algorithm for SubTree Kernel Computation based on Root-Weighted Tree Automata

• arxiv url: http://arxiv.org/abs/2302.01097v1
• Date: Thu, 2 Feb 2023 13:37:48 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-03 13:53:54.393409
• Title: New Linear-time Algorithm for SubTree Kernel Computation based on Root-Weighted Tree Automata
• Title（参考訳）: 根重み付き木オートマトンによるサブツリーカーネル計算のための新しい線形時間アルゴリズム
• Authors: Ludovic Mignot, Faissal Ouardi and Djelloul Ziadi
• Abstract要約: 本稿では,SubTreeカーネル計算のための重み付き木オートマトンの概念に基づく線形時間アルゴリズムを提案する。 提案アルゴリズムの主な考え方は、DAGの削減とノードのソートを置き換えることである。 我々のアプローチには3つの大きな利点がある:それは出力に敏感であり、木の種類(順序のない木と順序のない木)に敏感であり、インクリメンタルな木カーネルベースの学習手法によく適応している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Tree kernels have been proposed to be used in many areas as the automatic learning of natural language applications. In this paper, we propose a new linear time algorithm based on the concept of weighted tree automata for SubTree kernel computation. First, we introduce a new class of weighted tree automata, called Root-Weighted Tree Automata, and their associated formal tree series. Then we define, from this class, the SubTree automata that represent compact computational models for finite tree languages. This allows us to design a theoretically guaranteed linear-time algorithm for computing the SubTree Kernel based on weighted tree automata intersection. The key idea behind the proposed algorithm is to replace DAG reduction and nodes sorting steps used in previous approaches by states equivalence classes computation allowed in the weighted tree automata approach. Our approach has three major advantages: it is output-sensitive, it is free sensitive from the tree types (ordered trees versus unordered trees), and it is well adapted to any incremental tree kernel based learning methods. Finally, we conduct a variety of comparative experiments on a wide range of synthetic tree languages datasets adapted for a deep algorithm analysis. The obtained results show that the proposed algorithm outperforms state-of-the-art methods.
• Abstract（参考訳）: 木カーネルは、自然言語アプリケーションの自動学習として多くの分野で使われることが提案されている。 本稿では,SubTreeカーネル計算のための重み付き木オートマトンの概念に基づく線形時間アルゴリズムを提案する。 まず、ルート重み付き木オートマタと呼ばれる新しい重み付き木オートマタとその関連形式木シリーズを紹介する。 そして、このクラスから有限木言語に対するコンパクトな計算モデルを表すSubTree Automaticaを定義する。 これにより、重み付き木オートマトン交叉に基づいてSubTreeカーネルを演算するための理論的に保証された線形時間アルゴリズムを設計できる。 提案アルゴリズムの背後にある重要なアイデアは、重み付き木オートマトンアプローチで許容される状態同値クラス計算によって前回のアプローチで使われたdag削減とノードソートステップを置き換えることである。 私たちのアプローチには3つの大きなメリットがあります – アウトプットに敏感で、ツリータイプ(順序付きツリー対非順序付きツリー)から自由で、インクリメンタルなツリーカーネルベースの学習方法にも適しています。 最後に,深層アルゴリズム解析に適応した多種多様な合成木言語データセットについて,様々な比較実験を行った。 その結果,提案アルゴリズムは最先端手法よりも優れていた。

関連論文リスト

• Terminating Differentiable Tree Experts [77.2443883991608]
  本稿では,変圧器と表現生成器の組み合わせを用いて木操作を学習するニューラルシンボリック微分木機械を提案する。 まず、専門家の混在を導入することで、各ステップで使用される一連の異なるトランスフォーマーレイヤを取り除きます。 また,モデルが自動生成するステップ数を選択するための新しい終端アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-07-02T08:45:38Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
  メタ学習によってトレーニングされたトランスフォーマーベースのモデルであるMetaTreeを導入し、強力な決定木を直接生成する。 我々は、多くのデータセットに欲求決定木とグローバルに最適化された決定木の両方を適合させ、MetaTreeを訓練して、強力な一般化性能を実現する木のみを生成する。
  論文  参考訳（メタデータ） (2024-02-06T07:40:53Z)
• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。 我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。 EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
  論文  参考訳（メタデータ） (2023-10-23T18:26:00Z)
• On Computing Optimal Tree Ensembles [7.424944196676223]
  ランダム林や、より一般的には(決定ノブレイクダッシュ-)ツリーアンサンブルは、分類と回帰の方法として広く使われている。 最近のアルゴリズムの進歩は、そのサイズや深さなどの様々な測定に最適な決定木を計算することができる。 2つの新しいアルゴリズムと対応する下位境界を提供する。
  論文  参考訳（メタデータ） (2023-06-07T13:30:43Z)
• Parallel Tree Kernel Computation [0.0]
  2つの有限木からなる木核の計算のための逐次アルゴリズムの並列実装を考案する。 その結果,提案した並列アルゴリズムは遅延の点で逐次アルゴリズムよりも優れていることがわかった。
  論文  参考訳（メタデータ） (2023-05-12T18:16:45Z)
• Structural Optimization Makes Graph Classification Simpler and Better [5.770986723520119]
  モデル学習プロセスを簡素化しつつ,グラフ分類性能の向上の可能性を検討する。 構造情報アセスメントの進歩に触発されて、グラフから木をコードするデータサンプルを最適化する。 本稿では,木カーネルと畳み込みネットワークにこのスキームを実装し,グラフ分類を行う。
  論文  参考訳（メタデータ） (2021-09-05T08:54:38Z)
• 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)

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

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