Fugu-MT 論文翻訳(概要): Learning Small Decision Trees with Few Outliers: A Parameterized Perspective

論文の概要: Learning Small Decision Trees with Few Outliers: A Parameterized Perspective

arxiv url: http://arxiv.org/abs/2505.15648v1
Date: Wed, 21 May 2025 15:25:57 GMT
ステータス: 翻訳完了
システム内更新日: 2025-05-22 15:42:59.741414
Title: Learning Small Decision Trees with Few Outliers: A Parameterized Perspective
Title（参考訳）: 僅かなアウトリーチを持つ小決定木を学習する:パラメータ化された視点
Authors: Harmender Gahlawat, Meirav Zehavi,
Abstract要約: 決定木は、データの表現、分類、一般化のための機械学習の基本的なツールである。 textitize$s$) か textitdepth $(d)$ のいずれかを最小化する(textscDT)。 textscDTSO と textscDTDO という2つの問題を考えます。
参考スコア（独自算出の注目度）: 7.225874126880465
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Decision trees are a fundamental tool in machine learning for representing, classifying, and generalizing data. It is desirable to construct ``small'' decision trees, by minimizing either the \textit{size} ($s$) or the \textit{depth} $(d)$ of the \textit{decision tree} (\textsc{DT}). Recently, the parameterized complexity of \textsc{Decision Tree Learning} has attracted a lot of attention. We consider a generalization of \textsc{Decision Tree Learning} where given a \textit{classification instance} $E$ and an integer $t$, the task is to find a ``small'' \textsc{DT} that disagrees with $E$ in at most $t$ examples. We consider two problems: \textsc{DTSO} and \textsc{DTDO}, where the goal is to construct a \textsc{DT} minimizing $s$ and $d$, respectively. We first establish that both \textsc{DTSO} and \textsc{DTDO} are W[1]-hard when parameterized by $s+\delta_{max}$ and $d+\delta_{max}$, respectively, where $\delta_{max}$ is the maximum number of features in which two differently labeled examples can differ. We complement this result by showing that these problems become \textsc{FPT} if we include the parameter $t$. We also consider the kernelization complexity of these problems and establish several positive and negative results for both \textsc{DTSO} and \textsc{DTDO}.
Abstract（参考訳）: 決定木は、データの表現、分類、一般化のための機械学習の基本的なツールである。 textit{size}$s$) と \textit{decision tree} (\textsc{DT}) の \textit{depth} $(d)$ のどちらかを最小化する。近年, <textsc{Decision Tree Learning} のパラメータ化複雑性が注目されている。ここでは \textit{classification instance} $E$ と integer $t$ が与えられたとき、そのタスクは、少なくとも $t$ の例では $E$ に反する ``small'' \textsc{DT} を見つけることである。目的は、それぞれ$s$と$d$を最小化する \textsc{DTDO} を構築することである。まず、それぞれ$s+\delta_{max}$ と $d+\delta_{max}$ でパラメータ化されると、 \textsc{DTSO} と \textsc{DTDO} の両方が W[1]-ハードであると仮定する。パラメータ $t$ を含む場合、これらの問題が \textsc{FPT} となることを示すことで、この結果を補完する。また、これらの問題のカーネル化の複雑さを考慮し、 \textsc{DTSO} と \textsc{DTDO} の両方に対して、いくつかの正および負の結果を確立する。

関連論文リスト

PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
合成データを生成する新しいフレームワークである$mathsfPREM$(Private Relative Error Multiplicative weight update)を紹介します。我々はアルゴリズムをほぼ一致する下界で補完する。
論文参考訳（メタデータ） (2025-02-20T18:32:02Z)
Fixed-point Grover Adaptive Search for Quadratic Binary Optimization Problems [0.6524460254566903]
擬似非拘束バイナリ最適化(QUBO)問題に対するGrover型手法について検討する。このような問題に対して、左[1, m right] の値 mathbbZ$ のチューナブルパラメータである $Lambda を用いてマーカーオラクルを構築する。 Lambda$のすべての値に対して、これらのオラクルの非クリフォードゲート数は厳格に低い。この結果のいくつかは新規であり、固定点探索に基づく任意の手法に有用である。
論文参考訳（メタデータ） (2023-11-09T18:49:01Z)
Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
論文参考訳（メタデータ） (2023-09-20T21:41:59Z)
$\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文参考訳（メタデータ） (2023-07-11T08:51:53Z)
Non-Autoregressive Math Word Problem Solver with Unified Tree Structure [62.869481432887106]
我々は,この問題を解析し,統一木に基づいて解表現を推論する,新しい非自己回帰解法であるtextitMWP-NAS を提案する。 Math23K と MAWPS を用いた大規模な実験の結果,提案したMWP-NAS の有効性が示された。
論文参考訳（メタデータ） (2023-05-08T08:53:37Z)
Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文参考訳（メタデータ） (2021-06-09T05:39:05Z)
On Computing Stable Extensions of Abstract Argumentation Frameworks [1.1251593386108185]
textitabstract argumentation framework (sc af) は有向グラフ $(A,R)$ であり、$A$ はtextitabstract arguments の集合であり、$Rsubseteq A times A$ は textit attack relation である。与えられた sc における全ての安定な拡張をリストアップするための、既知のバックトラックアルゴリズムの徹底的な形式的検証を示す。
論文参考訳（メタデータ） (2020-11-03T05:38:52Z)
Universal guarantees for decision tree induction via a higher-order splitting criterion [16.832966312395126]
本アルゴリズムは,全対象関数に対して,一様分布に対して, -1,1n から -1,1$ の証明可能な保証を実現する。我々の拡張の要点は、その属性の$f$と小さなサブセットの相関を考慮に入れた、新しい分割基準である。我々のアルゴリズムは以下の保証を満たす: すべての対象関数 $f : -1,1n to -1,1$, sizes $sin mathbbN$, error parameters $epsilon$ に対して、決定を構成する。
論文参考訳（メタデータ） (2020-10-16T21:20:45Z)
An Approximation Algorithm for Optimal Subarchitecture Extraction [0.0]
我々は、パラメータサイズ、推論速度、エラー率の3つの指標で最適である、選択されたディープニューラルネットワークのアーキテクチャパラメータセットを見つけることの問題を考察する。我々は,大規模なインスタンスに対して,近似誤差が$rho leq |1- epsilon|$のFPTASのように振る舞う近似アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-10-16T17:11:32Z)
An Algorithm for Learning Smaller Representations of Models With Scarce Data [0.0]
データセットが小さすぎるか、完全に代表的でない状況下で、二項分類問題を解くための欲求的アルゴリズムを提案する。それは、ゆるやかな精度の制約、反復的なハイパーパラメータプルーニング手順、新しいデータを生成するために使われる関数といった訓練されたモデルに依存している。
論文参考訳（メタデータ） (2020-10-15T19:17:51Z)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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