論文の概要: Des-q: a quantum algorithm to provably speedup retraining of decision trees
- arxiv url: http://arxiv.org/abs/2309.09976v4
- Date: Thu, 23 May 2024 19:09:22 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-28 00:05:56.698654
- Title: Des-q: a quantum algorithm to provably speedup retraining of decision trees
- Title(参考訳): Des-q:決定木の再学習を確実に高速化する量子アルゴリズム
- Authors: Niraj Kumar, Romina Yalovetzky, Changhao Li, Pierre Minssen, Marco Pistoia,
- Abstract要約: Des-qは、回帰および二分分類タスクのための決定木を構築し、再訓練するための新しい量子アルゴリズムである。
我々は,複数のデータセット上での最先端の古典的手法に対して,Des-qのシミュレーションバージョンをベンチマークする。
提案アルゴリズムは,最新の決定木に類似した性能を示しながら,周期木再学習を著しく高速化する。
- 参考スコア(独自算出の注目度): 2.7262923206583136
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Decision trees are widely adopted machine learning models due to their simplicity and explainability. However, as training data size grows, standard methods become increasingly slow, scaling polynomially with the number of training examples. In this work, we introduce Des-q, a novel quantum algorithm to construct and retrain decision trees for regression and binary classification tasks. Assuming the data stream produces small, periodic increments of new training examples, Des-q significantly reduces the tree retraining time, achieving a logarithmic complexity in the combined total number of old and new examples, even accounting for the time needed to load the new samples into quantum-accessible memory. Our approach to grow the tree from any given node involves performing piecewise linear splits to generate multiple hyperplanes, thus partitioning the input feature space into distinct regions. To determine the suitable anchor points for these splits, we develop an efficient quantum-supervised clustering method, building upon the q-means algorithm introduced by Kerenidis \etal We benchmark the simulated version of Des-q against the state-of-the-art classical methods on multiple data sets and observe that our algorithm exhibits similar performance to the state-of-the-art decision trees while significantly speeding up the periodic tree retraining.
- Abstract(参考訳): 決定木はその単純さと説明可能性のために広く採用されている機械学習モデルである。
しかし、トレーニングデータのサイズが大きくなるにつれて、標準手法は徐々に遅くなり、トレーニング例の数とともに多項式的にスケールする。
本研究では、回帰および二分分類タスクのための決定木の構築と再学習を行う新しい量子アルゴリズムであるDes-qを紹介する。
データストリームが新しいトレーニング例の小さな周期的なインクリメントを生成すると仮定すると、Des-qは、新しいサンプルを量子アクセス可能なメモリにロードするのに必要な時間でさえも、古いサンプルと新しいサンプルの合計数の対数的複雑さを達成して、ツリー再トレーニング時間を著しく削減する。
木を任意のノードから成長させるアプローチは、複数の超平面を生成するために分割的に線形分割を行い、入力特徴空間を異なる領域に分割する。
これらの分割に適したアンカーポイントを決定するために,Kerenidis \etal氏が導入したq-meansアルゴリズムに基づく効率的な量子教師付きクラスタリング手法を開発した。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。