論文の概要: $Des$-$q$: a quantum algorithm to construct and efficiently retrain
decision trees for regression and binary classification
- arxiv url: http://arxiv.org/abs/2309.09976v1
- Date: Mon, 18 Sep 2023 17:56:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-19 12:01:48.288261
- Title: $Des$-$q$: a quantum algorithm to construct and efficiently retrain
decision trees for regression and binary classification
- Title（参考訳）: $des$-$q$:回帰と二分分類のための決定木を構築し、効率的に再訓練する量子アルゴリズム
- Authors: Niraj Kumar, Romina Yalovetzky, Changhao Li, Pierre Minnsen, and Marco
Pistoia
- Abstract要約: 回帰二分問題における決定木の構築と再学習のために,$Des$-$q$という新しい量子アルゴリズムを導入する。
提案手法では,各内部ノードで k 個の線形木分割を行う決定木アルゴリズムを構築する。
我々は、回帰と二分分類のための最先端の古典的決定木に対して、アルゴリズムのシミュレーション版の性能をベンチマークする。
- 参考スコア（独自算出の注目度）: 2.464148828287322
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Decision trees are widely used in machine learning due to their simplicity in
construction and interpretability. However, as data sizes grow, traditional
methods for construction and retraining decision trees become increasingly
slow, scaling polynomially with the number of training examples. In this work,
we introduce a novel quantum algorithm, named $Des$-$q$, for constructing and
retraining decision trees in regression and binary classification tasks.
Assuming the data stream produces small increments of new training examples, we
demonstrate that our $Des$-$q$ algorithm significantly reduces the time
required for tree retraining, achieving a poly-logarithmic time complexity in
the number of training examples, even accounting for the time needed to load
the new examples into quantum-accessible memory. Our approach involves building
a decision tree algorithm to perform k-piecewise linear tree splits at each
internal node. These splits simultaneously generate multiple hyperplanes,
dividing the feature space into k distinct regions. To determine the k suitable
anchor points for these splits, we develop an efficient quantum-supervised
clustering method, building upon the q-means algorithm of Kerenidis $et$ $al$.
$Des$-$q$ first efficiently estimates each feature weight using a novel quantum
technique to estimate the Pearson correlation. Subsequently, we employ weighted
distance estimation to cluster the training examples in k disjoint regions and
then proceed to expand the tree using the same procedure. We benchmark the
performance of the simulated version of our algorithm against the
state-of-the-art classical decision tree for regression and binary
classification on multiple data sets with numerical features. Further, we
showcase that the proposed algorithm exhibits similar performance to the
state-of-the-art decision tree while significantly speeding up the periodic
tree retraining.
- Abstract（参考訳）: 決定木は、構築と解釈性の単純さのために機械学習で広く使われている。
しかしながら,データサイズが大きくなるにつれて,従来型の意思決定木の構築と再訓練の手法が徐々に遅くなり,トレーニング例の数で多項式的にスケーリングされるようになっている。
本研究では,回帰および二分分類タスクにおける決定木の構築と再訓練を行うための,新しい量子アルゴリズムである$des$-$q$を導入する。
データストリームが新たなトレーニングサンプルの小さなインクリメントを生成すると仮定すると、我々の$des$-$q$アルゴリズムは、ツリーリトレーニングに必要な時間を大幅に削減し、トレーニングサンプル数における多対数時間の複雑さを実現し、新しいサンプルを量子アクセス可能なメモリにロードするのに必要な時間も考慮している。
提案手法では,各内部ノードで k 個の線形木分割を行う決定木アルゴリズムを構築する。
これらの分割は同時に複数の超平面を生成し、特徴空間を k 個の異なる領域に分割する。
これらの分割に適したk個のアンカーポイントを決定するために、kerenidis $et$$al$のq-meansアルゴリズムに基づく効率的な量子教師付きクラスタリング法を開発した。
第一に$des$-$q$ は、ピアソン相関を推定するために新しい量子技術を用いて各特徴量を効率的に見積もる。
その後,重み付き距離推定を用いて,k個の非結合領域にトレーニングサンプルをクラスタ化し,同じ手順で木を拡大する。
数値的特徴を持つ複数データセットの回帰と二項分類のための古典的決定木に対して,本アルゴリズムのシミュレーション版の性能をベンチマークした。
さらに,提案アルゴリズムは,周期木再学習を著しく高速化しつつ,最先端の決定木と同等の性能を示すことを示す。
関連論文リスト
- QC-Forest: a Classical-Quantum Algorithm to Provably Speedup Retraining of Random Forest [2.6436521007616114]
ランダムフォレスト(Random Forest, RF)は、教師あり学習法として人気があり、使いやすさと柔軟性で評価されている。
オンラインRFモデルは、モデルの精度を維持するために、新しいトレーニングデータを考慮する必要がある。
ストリーミング環境でのRFモデルの時間効率向上を目的とした古典量子アルゴリズムQC-Forestを提案する。
論文 参考訳（メタデータ） (2024-06-17T18:21:03Z) - Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。
最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。
シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
論文 参考訳（メタデータ） (2023-10-05T07:10:40Z) - A Recursively Recurrent Neural Network (R2N2) Architecture for Learning
Iterative Algorithms [64.3064050603721]
本研究では,リカレントニューラルネットワーク (R2N2) にランゲ・クッタニューラルネットワークを一般化し,リカレントニューラルネットワークを最適化した反復アルゴリズムの設計を行う。
本稿では, 線形方程式系に対するクリロフ解法, 非線形方程式系に対するニュートン・クリロフ解法, 常微分方程式に対するルンゲ・クッタ解法と類似の繰り返しを計算問題クラスの入力・出力データに対して提案した超構造内における重みパラメータの正規化について述べる。
論文 参考訳（メタデータ） (2022-11-22T16:30:33Z) - Constructing Optimal Contraction Trees for Tensor Network Quantum
Circuit Simulation [1.2704529528199062]
量子回路シミュレーションにおける重要な問題の1つは、縮退木の構築である。
本稿では,最適な縮尺木を構築するための新しい時間アルゴリズムを提案する。
提案手法は、試験された量子回路の大部分において、優れた結果が得られることを示す。
論文 参考訳（メタデータ） (2022-09-07T02:50:30Z) - Discrete Tree Flows via Tree-Structured Permutations [5.929956715430168]
離散フローベースモデルは、離散関数の勾配が未定義あるいはゼロであるため、従来のディープラーニング手法では直接最適化できない。
提案手法は,決定木に基づく離散フローを開発することにより,計算負担を低減し,擬似勾配の必要性を解消することを目的としている。
論文 参考訳（メタデータ） (2022-07-04T23:11:04Z) - Scaling Structured Inference with Randomization [64.18063627155128]
本稿では、構造化されたモデルを数万の潜在状態に拡張するためにランダム化された動的プログラミング(RDP)のファミリを提案する。
我々の手法は古典的DPベースの推論に広く適用できる。
また、自動微分とも互換性があり、ニューラルネットワークとシームレスに統合できる。
論文 参考訳（メタデータ） (2021-12-07T11:26:41Z) - Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
Recursive Grouping (RG) と Chow-Liu Recursive Grouping (CLRG) のサンプル複雑性について述べる。
RG,CLRG,Neighbor Joining (NJ) およびSpectral NJ (SNJ) をトラッピングした内積を用いて強化する。
我々は、潜在木の構造学習において、最初の既知のインスタンス依存の不合理性の結果を導出する。
論文 参考訳（メタデータ） (2021-06-02T01:37:52Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2020-08-29T14:58:26Z) - MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。
当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
論文 参考訳（メタデータ） (2020-07-24T17:06:55Z) - Quantum Ensemble for Classification [2.064612766965483]
機械学習のパフォーマンスを改善する強力な方法は、複数のモデルの予測を組み合わせたアンサンブルを構築することである。
量子重ね合わせ,絡み合い,干渉を利用して分類モデルのアンサンブルを構築する新しい量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-07-02T11:26:54Z) - Stochastic tree ensembles for regularized nonlinear regression [0.913755431537592]
本稿では,非線形回帰のための新しいツリーアンサンブル法を開発し,これをXBARTと呼ぶ。
ベイズモデルからの正規化と探索戦略と計算効率のよい手法を組み合わせることで、新しい手法は最先端の性能を達成できる。
論文 参考訳（メタデータ） (2020-02-09T14:37:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。