論文の概要: Coresets for Decision Trees of Signals
- arxiv url: http://arxiv.org/abs/2110.03195v1
- Date: Thu, 7 Oct 2021 05:49:55 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-08 15:26:57.911801
- Title: Coresets for Decision Trees of Signals
- Title（参考訳）: 信号の決定木に対するコアセット
- Authors: Ibrahim Jubran, Ernesto Evgeniy Sanches Shayda, Ilan Newman, Dan
Feldman
- Abstract要約: 仮にそのような行列に対して$(k,varepsilon)$-coresetを出力する最初のアルゴリズムを提供する。
これは、決定木と -- 機械学習から -- 計算幾何学における分割木の間のリンクをフォージすることで実現している。
- 参考スコア（独自算出の注目度）: 19.537354146654845
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A $k$-decision tree $t$ (or $k$-tree) is a recursive partition of a matrix
(2D-signal) into $k\geq 1$ block matrices (axis-parallel rectangles, leaves)
where each rectangle is assigned a real label. Its regression or classification
loss to a given matrix $D$ of $N$ entries (labels) is the sum of squared
differences over every label in $D$ and its assigned label by $t$. Given an
error parameter $\varepsilon\in(0,1)$, a $(k,\varepsilon)$-coreset $C$ of $D$
is a small summarization that provably approximates this loss to \emph{every}
such tree, up to a multiplicative factor of $1\pm\varepsilon$. In particular,
the optimal $k$-tree of $C$ is a $(1+\varepsilon)$-approximation to the optimal
$k$-tree of $D$.
We provide the first algorithm that outputs such a $(k,\varepsilon)$-coreset
for \emph{every} such matrix $D$. The size $|C|$ of the coreset is polynomial
in $k\log(N)/\varepsilon$, and its construction takes $O(Nk)$ time. This is by
forging a link between decision trees from machine learning -- to partition
trees in computational geometry.
Experimental results on \texttt{sklearn} and \texttt{lightGBM} show that
applying our coresets on real-world data-sets boosts the computation time of
random forests and their parameter tuning by up to x$10$, while keeping similar
accuracy. Full open source code is provided.
- Abstract（参考訳）: $k$-decision tree $t$ (または$k$-tree) は行列 (2D-signal) から$k\geq 1$ブロック行列 (軸平行長方形、葉) への再帰的分割である。
与えられた行列の$D$の$N$エントリ(ラベル)への回帰または分類損失は、$D$のすべてのラベルと割り当てられたラベルの$t$の2乗差の和である。
エラーパラメータ $\varepsilon\in(0,1)$ が与えられると、$(k,\varepsilon)$-coreset $c$ of $d$ は小さな要約であり、この損失を \emph{every} に近似し、乗算係数は 1\pm\varepsilon$ となる。
特に、$C$の最適$k$-treeは$(1+\varepsilon)$-approximation to the optimal $k$-tree of $D$である。
我々は、行列 $d$ のような \emph{every} に対して、そのような$(k,\varepsilon)$-coreset を出力する最初のアルゴリズムを提供する。
コアセットのサイズ$|C|$は$k\log(N)/\varepsilon$の多項式であり、その構成は$O(Nk)$時間を要する。
これは、機械学習から計算幾何学の分割木への決定木間のリンクを鍛えることによって実現される。
texttt{sklearn} と \texttt{lightgbm} の実験結果は、実世界のデータセットに我々のコアセットを適用することで、ランダムフォレストの計算時間とパラメータチューニングを最大で x$10$ で向上させ、同じ精度を維持していることを示している。
完全なオープンソースコードが提供されている。
関連論文リスト
- LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。
我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
論文 参考訳（メタデータ） (2024-10-07T19:47:13Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Optimal Embedding Dimension for Sparse Subspace Embeddings [4.042707434058959]
ランダム$mtimes n$ matrix $S$は、忘れられない部分空間埋め込み(OSE)である。
mtimes n$ random matrix $S$ with $mgeq (1+theta)d$ is an oblivious subspace embedding with $epsilon = O_theta(1)$。
これを使用すれば、現在の行列乗算時間よりも早く適用できる$O(d)$埋め込み次元で、最初の難解な部分空間埋め込みを構築することができる。
論文 参考訳（メタデータ） (2023-11-17T18:01:58Z) - A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文 参考訳（メタデータ） (2022-09-06T23:37:31Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z) - Tree density estimation [12.831051269764115]
確率密度 $f(boldsymbol x)$ を持つランダムベクトル $boldsymbol X$ in $mathbb Rd$ の密度推定。
有界なサポートを持つリプシッツ連続 $f$ に対して、$mathbb E int |f_n(boldsymbol x)-fT*(boldsymbol x)|dboldsymbol x=0$ a.s である。
有界なサポートを持つリプシッツ連続$f$に対して、$mathbb E int |f_n(boldsymbol x)-f
論文 参考訳（メタデータ） (2021-11-23T16:05:59Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Self-training Converts Weak Learners to Strong Learners in Mixture
Models [86.7137362125503]
擬似ラベルの $boldsymbolbeta_mathrmpl$ が,最大$C_mathrmerr$ の分類誤差を達成可能であることを示す。
さらに、ロジスティックな損失に対して勾配降下を実行することで、ラベル付き例のみを使用して、分類誤差が$C_mathrmerr$で擬ラベルの $boldsymbolbeta_mathrmpl$ が得られることを示す。
論文 参考訳（メタデータ） (2021-06-25T17:59:16Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu [14.298220510927695]
古典的ChowLiuアルゴリズム(IEEE Trans.Inform.Theory, 1968)に対する有限サンプル保証を提供する。
特定の木の$T$に対して、$widetildeO (|Sigma|2nvarepsilon-1)$の分布からのサンプルを$P$ over $Sigman$とすると、最も近いKL分岐を効率的に学習できる。
論文 参考訳（メタデータ） (2020-11-09T02:08:56Z) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳（メタデータ） (2020-08-15T11:06:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。