論文の概要: Literati: Towards Anytime Optimal Shape Generalized Trees via AO*

• arxiv url: http://arxiv.org/abs/2609.09299v1
• Date: Tue, 08 Sep 2026 18:00:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-10 19:44:08.771724
• Title: Literati: Towards Anytime Optimal Shape Generalized Trees via AO*
• Title（参考訳）: Literati: AO*による任意の最適形状一般化ツリーを目指して
• Abstract要約: 形状一般化木(SGT)は、形状関数を一般化し、表現性を改善し、よりコンパクトな木を可能にする。 既存のSGT誘導アルゴリズムは欲張りであり、最適性を保証するものではない。 最適SGT誘導のための最初のアルゴリズムであるLiteratiを紹介する。
• 参考スコア（独自算出の注目度）: 3.469167914196103
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Decision trees are prized for their interpretability and strong performance on tabular data, but popular greedy top-down induction algorithms can yield suboptimal and unnecessarily complex structures. Optimal decision tree methods address this through global optimization, yet remain restricted to axis-aligned threshold splits, which limit the expressivity of each node and often force deep, complex trees to capture non-linear feature effects. Shape Generalized Trees (SGTs) generalize threshold splits to learnable univariate shape functions, improving expressivity and enabling more compact trees. However, existing SGT induction algorithms are greedy and offer no optimality guarantees. In this work, we introduce Literati, the first algorithm for optimal SGT induction. We propose a novel AND/OR graph formulation of the problem that jointly optimizes tree structure and shape function complexity. To solve this AND/OR graph, we develop an AO*-based algorithm with two enhancements that improve anytime performance while preserving optimality: a secondary heuristic for OR-node selection and a round-robin policy for AND-node exploration. Across 24 real-world datasets, Literati achieves higher training and test accuracy than state-of-the-art tree approaches.
• Abstract（参考訳）: 決定木は、表形式のデータに対する解釈性と強い性能で評価されているが、一般的なグリーディなトップダウン誘導アルゴリズムは、最適かつ不要な複雑な構造を生み出すことができる。 最適決定木法は、グローバルな最適化を通じてこの問題に対処するが、各ノードの表現性を制限し、しばしば深い複雑な木を強制的に非線型特徴効果を捕捉する軸方向の閾値分割に制限される。 形状一般化木(SGT)は、しきい値分割を学習可能な単変量形状関数に一般化し、表現性を向上し、よりコンパクトな木を可能にする。 しかし、既存のSGT誘導アルゴリズムは欲張りであり、最適性を保証するものではない。 本稿では,最適SGT誘導のためのアルゴリズムLiteratiを紹介する。 本稿では,木構造と形状関数の複雑さを協調的に最適化する,新しいAND/ORグラフ定式化法を提案する。 ORノード選択のための二次ヒューリスティックと、ANDノード探索のためのラウンドロビンポリシーの2つの拡張を加えたAO*ベースのアルゴリズムを開発した。 24の現実世界のデータセットに対して、Literatiは最先端のツリーアプローチよりも高いトレーニングとテストの精度を実現している。

関連論文リスト

• Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction [16.87091101554527]
  我々はSTreeDに基づく特徴空間とサンプル空間の合同計算フレームワークを開発した。 重み付きSTreeDは、固定された候補に投影後に生成された重複レコードを重み付き代表にマージする。 Adaptive STreeDは、境界付き候補集合を何度も洗練し、既存のツリーで使われる特徴を保持し、重み付き表現を再構築し、結果として生じる問題を解く。
  論文  参考訳（メタデータ） (2026-09-05T02:42:53Z)
• TreeGrad-Ranker: Feature Ranking via $O(L)$-Time Gradients for Decision Trees [73.0940890296463]
  確率値は、決定木の局所的な予測値を説明する特徴のランク付けに使用される。 TreeGradは、共同目的の多重線型拡張の勾配を$O(L)$時間で計算する。 TreeGrad-Rankerは、機能ランキングを生成するために共同目標を最適化しながら、勾配を集約する。 TreeGrad-Shapは、積分パラメータを持つベータシェープ値を計算するための数値的に安定なアルゴリズムである。
  論文  参考訳（メタデータ） (2026-02-12T06:17:12Z)
• Foundational theory for optimal decision tree problems. II. Optimal hypersurface decision tree algorithm [1.972521190983547]
  このシリーズのパート1では、4つの公理を通して適切な決定木モデルを厳格に定義した。 第2部では,第1次超曲面決定木(HODT)アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2025-09-15T15:38:44Z)
• TreePO: Bridging the Gap of Policy Optimization and Efficacy and Inference Efficiency with Heuristic Tree-based Modeling [65.46347858249295]
  TreePOは自己誘導型ロールアウトアルゴリズムで、シーケンス生成を木構造検索プロセスとして見る。 TreePOは基本的に、探索の多様性を保存または強化しながら、更新毎の計算負担を削減します。
  論文  参考訳（メタデータ） (2025-08-24T16:52:37Z)
• Near Optimal Decision Trees in a SPLIT Second [16.99892407039875]
  決定木最適化は、解釈可能な機械学習の基本である。 最近のアプローチでは、分岐と動的プログラミングとのバウンドを使って、グローバルな最適化が見つかる。 我々はSPLITと呼ばれるアルゴリズムのファミリーを導入し、この理想的なバランスを達成するために私たちをかなり前進させます。
  論文  参考訳（メタデータ） (2025-02-21T22:57:17Z)
• Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound [1.3654846342364308]
  与えられたサイズ制限内でのトレーニング性能を最大化する最適な分類木はNPハードであり、実際にはほとんどの最先端手法は、深さ3の最適木を計算できない。 本稿では,分岐とバウンドを持つ動的プログラミングを用いて,連続的な特徴データに基づいて木を直接最適化する新しいアルゴリズムを提案する。 実験により、これらの手法は、最先端の最適手法よりも1桁以上の実行時間を改善するとともに、グレディよりもテスト精度を5%向上することを示した。
  論文  参考訳（メタデータ） (2025-01-14T07:46:33Z)
• Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
  メタ学習によってトレーニングされたトランスフォーマーベースのモデルであるMetaTreeを導入し、強力な決定木を直接生成する。 我々は、多くのデータセットに欲求決定木とグローバルに最適化された決定木の両方を適合させ、MetaTreeを訓練して、強力な一般化性能を実現する木のみを生成する。
  論文  参考訳（メタデータ） (2024-02-06T07:40:53Z)
• Convex Polytope Trees [57.56078843831244]
  コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。 木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
  論文  参考訳（メタデータ） (2020-10-21T19:38:57Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。 当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
  論文  参考訳（メタデータ） (2020-07-24T17:06:55Z)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  様々な目的に対して最適な決定木を生成する手法を提案する。 また,連続変数が存在する場合に最適な結果が得られるスケーラブルなアルゴリズムも導入する。
  論文  参考訳（メタデータ） (2020-06-15T19:00:11Z)

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

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