論文の概要: Des-q: a quantum algorithm to construct and efficiently retrain decision trees for regression and binary classification

• arxiv url: http://arxiv.org/abs/2309.09976v3
• Date: Fri, 22 Sep 2023 09:03:15 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-25 17:46:04.556293
• 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 Minssen, and Marco Pistoia
• Abstract要約: 回帰および二分分類タスクにおける決定木の構築と再学習のための新しい量子アルゴリズムDes-qを導入する。 Des-qアルゴリズムは木の再学習に要する時間を大幅に短縮することを示した。
• 参考スコア（独自算出の注目度）: 2.7262923206583136
• 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 constructing 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個の非結合領域にトレーニングサンプルをクラスタ化し,同じ手順で木を拡大する。 数値的特徴を持つ複数データセットの回帰と二項分類のための古典的決定木に対して,本アルゴリズムのシミュレーション版の性能をベンチマークした。 さらに,提案アルゴリズムは,周期木再学習を著しく高速化しつつ,最先端の決定木と同等の性能を示すことを示す。

関連論文リスト

• Quantum-inspired attribute selection algorithm: A Fidelity-based Quantum Decision Tree [1.6190746208019742]
  古典的な決定木は、そのクラスラベルに対応するランダムな事象の発生を利用する分割措置に完全に基づいている。 本稿では、量子分割基準として忠実度を用いて、効率よくバランスの取れた量子決定木を構築することを提案する。
  論文  参考訳（メタデータ） (2023-10-27T16:29:42Z)
• TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
  Branch-and-Boundは、Mixed Linear Programsという形で最適化タスクを解決するための便利なアプローチである。 解法の効率は、分割する変数を選択するのに使用される分岐に依存する。 分岐を効率的に学習できる強化学習法を提案する。
  論文  参考訳（メタデータ） (2023-06-09T14:01:26Z)
• A Recursively Recurrent Neural Network (R2N2) Architecture for Learning Iterative Algorithms [64.3064050603721]
  本研究では,リカレントニューラルネットワーク (R2N2) にランゲ・クッタニューラルネットワークを一般化し,リカレントニューラルネットワークを最適化した反復アルゴリズムの設計を行う。 本稿では, 線形方程式系に対するクリロフ解法, 非線形方程式系に対するニュートン・クリロフ解法, 常微分方程式に対するルンゲ・クッタ解法と類似の繰り返しを計算問題クラスの入力・出力データに対して提案した超構造内における重みパラメータの正規化について述べる。
  論文  参考訳（メタデータ） (2022-11-22T16:30:33Z)
• 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)
• Simple is better: Making Decision Trees faster using random sampling [4.284674689172996]
  近年,ビッグデータ上での堅牢な機械学習モデル構築において,勾配向上決定木が普及している。 理論的および実験的に、ランダムに分割点を均一に選択することは、精度と計算効率の点で、同じあるいはさらに優れた性能を提供することを示す。
  論文  参考訳（メタデータ） (2021-08-19T17:00:21Z)
• 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)

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

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