論文の概要: A Gap Between Decision Trees and Neural Networks

• arxiv url: http://arxiv.org/abs/2601.03919v1
• Date: Wed, 07 Jan 2026 13:40:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-08 18:12:46.2012
• Title: A Gap Between Decision Trees and Neural Networks
• Title（参考訳）: 決定木とニューラルネットワークのギャップ
• Authors: Akash Kumar,
• Abstract要約: ここでは、解釈可能性の概念として用いられる決定境界の幾何学的単純さが、浅いニューラルネットワークによる軸整列決定木の正確な近似と矛盾する場合について検討する。 分類するために、有限$mathrmRmathrmTV$で滑らかな障壁スコア$S_A$を構築し、その固定しきい値$=1$がボックスを正確に回復する。 長方形の合成結合の実験は、結果として生じる精度-複雑さのトレードオフを示している。
• 参考スコア（独自算出の注目度）: 2.4140387101794283
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study when geometric simplicity of decision boundaries, used here as a notion of interpretability, can conflict with accurate approximation of axis-aligned decision trees by shallow neural networks. Decision trees induce rule-based, axis-aligned decision regions (finite unions of boxes), whereas shallow ReLU networks are typically trained as score models whose predictions are obtained by thresholding. We analyze the infinite-width, bounded-norm, single-hidden-layer ReLU class through the Radon total variation ($\mathrm{R}\mathrm{TV}$) seminorm, which controls the geometric complexity of level sets. We first show that the hard tree indicator $1_A$ has infinite $\mathrm{R}\mathrm{TV}$. Moreover, two natural split-wise continuous surrogates--piecewise-linear ramp smoothing and sigmoidal (logistic) smoothing--also have infinite $\mathrm{R}\mathrm{TV}$ in dimensions $d>1$, while Gaussian convolution yields finite $\mathrm{R}\mathrm{TV}$ but with an explicit exponential dependence on $d$. We then separate two goals that are often conflated: classification after thresholding (recovering the decision set) versus score learning (learning a calibrated score close to $1_A$). For classification, we construct a smooth barrier score $S_A$ with finite $\mathrm{R}\mathrm{TV}$ whose fixed threshold $τ=1$ exactly recovers the box. Under a mild tube-mass condition near $\partial A$, we prove an $L_1(P)$ calibration bound that decays polynomially in a sharpness parameter, along with an explicit $\mathrm{R}\mathrm{TV}$ upper bound in terms of face measures. Experiments on synthetic unions of rectangles illustrate the resulting accuracy--complexity tradeoff and how threshold selection shifts where training lands along it.
• Abstract（参考訳）: ここでは、解釈可能性の概念として用いられる決定境界の幾何学的単純さが、浅いニューラルネットワークによる軸整列決定木の正確な近似と矛盾するかどうかを考察する。 決定木は規則に基づく軸整列決定領域(ボックスの有限結合)を誘導するのに対し、浅いReLUネットワークはしきい値によって予測されるスコアモデルとして訓練されるのが一般的である。 無限幅、有界ノルム、単層ReLUクラスをラドン全変量(\mathrm{R}\mathrm{TV}$)半ノルムで解析し、レベル集合の複雑性を制御する。 最初に、ハードツリー指標 $1_A$ が無限の$\mathrm{R}\mathrm{TV}$ を持つことを示す。 さらに、2つの自然なスプリットワイド連続サロゲート、-片方向線形ランプ滑らか化とシグモディカル(論理的)滑らか化も無限の$\mathrm{R}\mathrm{TV}$を次元$d>1$で有し、ガウスの畳み込みは有限$\mathrm{R}\mathrm{TV}$であるが、$d$に明示的な指数的依存を持つ。 次に、しばしば混ざり合った2つの目標を分けます: しきい値(決定セットの回復)の分類とスコアラーニング(校正スコアが1_A$に近いことを学ぶ)です。 分類するために、有限$\mathrm{R}\mathrm{TV}$で滑らかな障壁スコア$S_A$を構築し、その固定しきい値$τ=1$がボックスを正確に回復する。 約$\partial A$ に近い穏やかなチューブ質量条件の下では、表面測度に関して、明示的な $\mathrm{R}\mathrm{TV}$ 境界とともに、鋭度パラメータで多項式的に減衰する$L_1(P)$ キャリブレーション境界が証明される。 長方形の合成結合の実験は、結果として生じる精度-複雑さのトレードオフと、そのトレーニングに沿った場所にあるしきい値の選択がどのようにシフトするかを示している。

関連論文リスト

• Approximation Rates for Shallow ReLU$^k$ Neural Networks on Sobolev Spaces via the Radon Transform [12.171849953316192]
  我々は,ReLU$k$アクティベーション関数がソボレフ空間からの関数をいかに効率的に近似できるかという問題を考察する。 例えば、$qleq p$, $pgeq 2$, $s leq k + (d+1)/2$ などである。
  論文  参考訳（メタデータ） (2024-08-20T16:43:45Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。 SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Overparametrized linear dimensionality reductions: From projection pursuit to two-layer neural networks [8.74634652691576]
  我々は$mathbbRd$の$nデータポイントのクラウドを考え、$mathbbRd$の$m$次元部分空間上のすべての射影を考える。 この確率分布の集まりは、$n,d$が大きくなるとどのように見えるか? Kullback-Leibler の発散と R'enyi の情報次元の点で鋭い境界を証明している。
  論文  参考訳（メタデータ） (2022-06-14T00:07:33Z)
• On Submodular Contextual Bandits [92.45432756301231]
  作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
  論文  参考訳（メタデータ） (2021-12-03T21:42:33Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。 線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。 線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
  論文  参考訳（メタデータ） (2021-01-29T18:57:52Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)

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

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