論文の概要: Algebraic Model Counting for Global Analysis of Optimal Decision Trees
- arxiv url: http://arxiv.org/abs/2607.02069v1
- Date: Thu, 02 Jul 2026 12:03:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-03 19:45:08.818419
- Title: Algebraic Model Counting for Global Analysis of Optimal Decision Trees
- Title（参考訳）: 最適決定木の大域的解析のための代数的モデルカウント
- Abstract要約: 本稿では,algebraic Decision Tree Counting (ADTC) と呼ばれる最適および準最適決定木の網羅的解析のための形式的枠組みを提案する。
Algebraic Model Counting (AMC) にインスパイアされたADTCは、最適化、カウント、サンプリングなどの多種多様な分析タスクを半額のR$上で統一された総和に再構成する。
我々は、ADTCが機密ドメインにおけるエビデンスベースのモデル選択をどのように促すかを示し、実世界のデータセットにエムツリーというソフトウェアの有用性を実証する。
- 参考スコア（独自算出の注目度）: 0.533024001730262
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Ensuring model reliability in Explainable AI requires a global assessment of the hypothesis space. We propose a formal framework for the exhaustive analysis of optimal and near-optimal decision trees, called Algebraic Decision Tree Counting (ADTC). Inspired by Algebraic Model Counting (AMC) in knowledge representation, ADTC reformulates diverse analytical tasks, such as optimization, counting, and sampling, into a unified sum-of-products computation over a semiring $R$. While the hypothesis space of decision trees is doubly exponential with respect to the maximum depth $Δ$, our dynamic programming algorithm achieves $O^*(n^{O(Δ)})$ time complexity in the number of features $n$, where $O^*$ suppresses polynomial factors. To handle complex constraints consisting of multiple tree metrics, we introduce model behavior tensors that aggregate semiring values via convolution products over a tensor semiring. This algebraic approach efficiently constructs a model profile that captures the global landscape and trade-offs between criteria such as accuracy, size, and fairness. We demonstrate the utility of our software, emtrees, on real-world datasets, illustrating how ADTC facilitates evidence-based model selection in sensitive domains.
- Abstract（参考訳）: 説明可能なAIにおけるモデルの信頼性を保証するには、仮説空間のグローバルな評価が必要である。
本稿では,algebraic Decision Tree Counting (ADTC) と呼ばれる最適および準最適決定木を網羅的に解析するための形式的枠組みを提案する。
知識表現における代数的モデルカウント(AMC)にインスパイアされたADTCは、最適化、カウント、サンプリングなどの多種多様な分析タスクを半値の$R$で統一された積和計算に変換する。
決定木の仮説空間は最大深さ$Δ$に対して2倍指数的であるが、我々の動的プログラミングアルゴリズムは$O^*(n^{O(Δ)})$時間複雑さを$n$で達成し、$O^*$は多項式因子を抑圧する。
複数の木のメトリクスからなる複雑な制約に対処するため、テンソル上の畳み込み積を介してセミリング値を集約するモデル挙動テンソルを導入する。
この代数的アプローチは、精度、サイズ、公平性といった基準の間の大域的な景観とトレードオフを捉えるモデルプロファイルを効率的に構築する。
我々は、ADTCが機密ドメインにおけるエビデンスベースのモデル選択をどのように促すかを示し、実世界のデータセット上で、ソフトウェア、エムツリーの有用性を実証する。
関連論文リスト
- SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。
我々は悲観的な収束分析を避ける分析を提供する。
我々の成果は、既存の最先端の体制を改善した。
論文 参考訳（メタデータ） (2026-06-14T14:11:07Z) - A Rigorous, Tractable Measure of Model Complexity [12.424687747519037]
本稿では,入力間のモデル間の類似性に基づいて,モデル複雑性の数学的に厳密かつパラメトリックな測度を示す。
複雑性の尺度は、カーネル長スケール、隣人数、木数などのモデル固有の複雑性尺度を一般化することを証明する。
我々はまた、ランダムな特徴、ランダムな森林、ニューラルネットワーク、勾配の上昇に対する二重降下現象に関する新たな洞察を得るために、我々の測定値を利用する。
論文 参考訳（メタデータ） (2026-05-20T13:37:38Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Optimal Decision Tree Pruning Revisited: Algorithms and Complexity [22.57063332430197]
我々は,サブツリーの更新と育成の基本的な作業に焦点をあてる。
サブツリー置換に間に合うように最適プルーニングを行うことができるが、サブツリーの更新にはNP完全である。
例えば、サブツリーの上昇は小さなドメインサイズでは難しいが、$D2d cdot |I|O(1)$timeでは、$|I|$が入力サイズである。
論文 参考訳（メタデータ） (2025-03-05T15:02:46Z) - On Computational Limits and Provably Efficient Criteria of Visual Autoregressive Models: A Fine-Grained Complexity Analysis [22.641550077885686]
我々は,Visual Autoregressive(mathsf/$)モデルの計算限界と効率基準を分析する。
より詳細な複雑性理論からStrong Exponential Time hypothesis(mathsfSETH$)を仮定すると、$mathsf/$モデルに対する準量子時間アルゴリズムは不可能である。
私たちの技術は、$mathsf/$フレームワークでスケーラブルで効率的な画像生成を推し進めることに重点を置いています。
論文 参考訳（メタデータ） (2025-01-08T09:34:15Z) - Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
一般関数近似の文脈において,無限水平平均逆マルコフ決定過程(AMDP)について検討する。
最適化最適化(LOOP)と呼ばれる新しいアルゴリズムフレームワークを提案する。
我々は LOOP がサブ線形 $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret を達成することを示す。
論文 参考訳（メタデータ） (2024-04-19T06:24:22Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - bsnsing: A decision tree induction method based on recursive optimal
boolean rule composition [2.28438857884398]
本稿では,決定木帰納過程における分割規則選択を最適化するMIP(Mixed-integer Programming)の定式化を提案する。
商用の解法よりも高速に実例を解くことができる効率的な探索解法を開発した。
論文 参考訳（メタデータ） (2022-05-30T17:13:57Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。