論文の概要: An A*-algorithm for the Unordered Tree Edit Distance with Custom Costs

• arxiv url: http://arxiv.org/abs/2108.00953v1
• Date: Mon, 26 Jul 2021 12:57:27 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-08 11:08:01.830290
• Title: An A*-algorithm for the Unordered Tree Edit Distance with Custom Costs
• Title（参考訳）: A*-algorithm for the Unordered Tree Edit Distance with Custom Costs
• Authors: Benjamin Paa{\ss}en
• Abstract要約: 順序のない木編集距離は、固有の子順序なしで木間の距離を計算する指標である。 本稿では,A*アルゴリズムに対して,カスタムコスト関数を扱う3つの新しい計算手法を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The unordered tree edit distance is a natural metric to compute distances between trees without intrinsic child order, such as representations of chemical molecules. While the unordered tree edit distance is MAX SNP-hard in principle, it is feasible for small cases, e.g. via an A* algorithm. Unfortunately, current heuristics for the A* algorithm assume unit costs for deletions, insertions, and replacements, which limits our ability to inject domain knowledge. In this paper, we present three novel heuristics for the A* algorithm that work with custom cost functions. In experiments on two chemical data sets, we show that custom costs make the A* computation faster and improve the error of a 5-nearest neighbor regressor, predicting chemical properties. We also show that, on these data, polynomial edit distances can achieve similar results as the unordered tree edit distance.
• Abstract（参考訳）: 非順序木編集距離は、化学分子の表現のような固有の子秩序を持たない木間の距離を計算する自然な計量である。 非順序木編集距離は原則として MAX SNP-hard であるが、小さな場合、例えば、実現可能である。 A*アルゴリズムによる。 残念ながら、現在のA*アルゴリズムのヒューリスティックスは、削除、挿入、置換の単位コストを前提としており、ドメイン知識を注入する能力を制限する。 本稿では,A*アルゴリズムに対して,カスタムコスト関数を扱う3つの新しいヒューリスティックスを提案する。 2つの化学データセットの実験において、A*計算を高速化し、化学特性を予測して隣り合う5熱抵抗の誤差を改善するためのカスタムコストが示されている。 また,これらのデータから,多項式編集距離は木編集距離と同じ結果が得られることを示した。

関連論文リスト

• 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)
• 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)
• New Linear-time Algorithm for SubTree Kernel Computation based on Root-Weighted Tree Automata [0.0]
  本稿では,SubTreeカーネル計算のための重み付き木オートマトンの概念に基づく線形時間アルゴリズムを提案する。 提案アルゴリズムの主な考え方は、DAGの削減とノードのソートを置き換えることである。 我々のアプローチには3つの大きな利点がある:それは出力に敏感であり、木の種類(順序のない木と順序のない木)に敏感であり、インクリメンタルな木カーネルベースの学習手法によく適応している。
  論文  参考訳（メタデータ） (2023-02-02T13:37:48Z)
• Properly learning decision trees in almost polynomial time [25.763690981846125]
  我々は,決定木を適切に,不可知的に学習するための$nO(loglog n)$-timeメンバシップクエリアルゴリズムを提案する。 我々のアルゴリズムは、決定木を学習するための実践と類似点を共有している。 すべての決定木がどのようにして「刈り取られる」かを示し、結果のツリーのすべての変数が影響を受けます。
  論文  参考訳（メタデータ） (2021-09-01T22:12:47Z)
• Solving the Steiner Tree Problem with few Terminals [8.024778381207128]
  動的プログラミングによるスタイナーツリー問題の解法として、Dijkstra-Steinerアルゴリズムがある。 我々はDijkstra-Steinerアルゴリズムを強化し、DS*と呼ばれる再検討アルゴリズムを確立する。 そこで本研究では,DS* アルゴリズムの適合性は整合性よりも弱いことを示し,許容関数を用いた場合の正当性を確立する。
  論文  参考訳（メタデータ） (2020-11-09T17:46:02Z)
• An Efficient Adversarial Attack for Tree Ensembles [91.05779257472675]
  傾斜促進決定木(DT)や無作為林(RF)などの木に基づくアンサンブルに対する敵対的攻撃 提案手法は,従来のMILP (Mixed-integer linear programming) よりも数千倍高速であることを示す。 私たちのコードはhttps://chong-z/tree-ensemble- attackで利用可能です。
  論文  参考訳（メタデータ） (2020-10-22T10:59:49Z)
• 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)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)

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

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