論文の概要: Improved Quantum Query Upper Bounds Based on Classical Decision Trees
- arxiv url: http://arxiv.org/abs/2203.02968v1
- Date: Sun, 6 Mar 2022 14:04:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-22 23:57:41.859918
- Title: Improved Quantum Query Upper Bounds Based on Classical Decision Trees
- Title（参考訳）: 古典的決定木に基づく量子クエリ上界の改良
- Authors: Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro
- Abstract要約: 古典的なクエリアルゴリズムが決定木として与えられると、古典的なクエリアルゴリズムよりも高速な量子クエリアルゴリズムはいつ存在するのか?
我々は、下層の決定木の構造に基づく一般的な構成を提供し、これが上から四進的な量子スピードアップをもたらすことを証明している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given a classical query algorithm as a decision tree, when does there exist a
quantum query algorithm with a speed-up over the classical one? We provide a
general construction based on the structure of the underlying decision tree,
and prove that this can give us an up-to-quadratic quantum speed-up. In
particular, we obtain a bounded-error quantum query algorithm of cost
$O(\sqrt{s})$ to compute a Boolean function (more generally, a relation) that
can be computed by a classical (even randomized) decision tree of size $s$.
Lin and Lin [ToC'16] and Beigi and Taghavi [Quantum'20] showed results of a
similar flavor, and gave upper bounds in terms of a quantity which we call the
"guessing complexity" of a decision tree. We identify that the guessing
complexity of a decision tree equals its rank, a notion introduced by
Ehrenfeucht and Haussler [Inf. Comp.'89] in the context of learning theory.
This answers a question posed by Lin and Lin, who asked whether the guessing
complexity of a decision tree is related to any complexity-theoretic measure.
We also show a polynomial separation between rank and randomized rank for the
complete binary AND-OR tree.
Beigi and Taghavi constructed span programs and dual adversary solutions for
Boolean functions given classical decision trees computing them and an
assignment of non-negative weights to its edges. We explore the effect of
changing these weights on the resulting span program complexity and objective
value of the dual adversary bound, and capture the best possible weighting
scheme by an optimization program. We exhibit a solution to this program and
argue its optimality from first principles. We also exhibit decision trees for
which our bounds are asymptotically stronger than those of Lin and Lin, and
Beigi and Taghavi. This answers a question of Beigi and Taghavi, who asked
whether different weighting schemes could yield better upper bounds.
- Abstract（参考訳）: 決定木として古典的問合せアルゴリズムが与えられたとき、古典的問合せよりも高速化した量子問合せアルゴリズムはいつ存在するのか?
基礎となる決定木の構造に基づく一般的な構成を提供し、それが量子速度アップをもたらすことを証明します。
特に、サイズ$s$の古典的な(ランダム化された)決定木によって計算できるブール関数(より一般的には関係)を計算するために、コスト$o(\sqrt{s})$の有界エラー量子クエリアルゴリズムを得る。
lin と lin [toc'16] と beigi と taghavi [quantum'20] は同様のフレーバーの結果を示し、決定木の「ゲッシング複雑性」と呼ばれる量の上限を与えた。
決定木の推測複雑性はその階数と等しく、学習理論の文脈において ehrenfeucht と haussler [inf. comp.'89] によって導入された概念である。
これはlinとlinが提起した疑問に答え、彼は決定木の推測複雑性が任意の複雑性理論的な尺度と関係しているかどうかを問うた。
また,完全二進木および-or木に対するランクとランダムランクの多項式分離も示す。
Beigi と Taghavi は、古典的な決定木を計算し、そのエッジに負の重みを割り当てることによって、ブール関数のスパンプログラムと双対逆解を構築した。
これらの重み付けの変更が,双対境界のスパンプログラムの複雑性と客観的値に及ぼす影響について検討し,最適化プログラムによる最善の重み付けスキームを捉える。
我々はこのプログラムの解決策を示し、その最適性を第一原理から議論する。
境界がlinやlinやbeigiやtaghaviよりも漸近的に強い決定木も示しています。
これは、BeigiとTaghaviの質問に答え、彼は異なる重み付けスキームがより良い上限をもたらすかどうか尋ねた。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
メタ学習によってトレーニングされたトランスフォーマーベースのモデルであるMetaTreeを導入し、強力な決定木を直接生成する。
我々は、多くのデータセットに欲求決定木とグローバルに最適化された決定木の両方を適合させ、MetaTreeを訓練して、強力な一般化性能を実現する木のみを生成する。
論文 参考訳（メタデータ） (2024-02-06T07:40:53Z) - 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) - Efficient Quantum Agnostic Improper Learning of Decision Trees [0.18416014644193066]
我々は、インスタンス上の一様境界を持つ決定木を学習するためのポリアグノスティック(n,t,frac1varepsilon)$量子アルゴリズムを提供する。
我々のアルゴリズムは、メンバーシップクエリなしで決定木を学習するための最初のアルゴリズム(古典的または量子的)である。
論文 参考訳（メタデータ） (2022-10-01T07:11:19Z) - How Smart Guessing Strategies Can Yield Massive Scalability Improvements
for Sparse Decision Tree Optimization [18.294573939199438]
現在のアルゴリズムは、いくつかの実世界のデータセットに対して最適な木またはほぼ最適な木を見つけるために、しばしば非現実的な時間とメモリを必要とする。
本稿では,任意の分岐とバウンダリに基づく決定木アルゴリズムに適用可能なスマート推測手法を用いてこの問題に対処する。
提案手法では, 連続的特徴量, 木の大きさ, 最適決定木に対する誤差の下位境界を推定できる。
論文 参考訳（メタデータ） (2021-12-01T19:39:28Z) - Properly learning decision trees in almost polynomial time [25.763690981846125]
我々は,決定木を適切に,不可知的に学習するための$nO(loglog n)$-timeメンバシップクエリアルゴリズムを提案する。
我々のアルゴリズムは、決定木を学習するための実践と類似点を共有している。
すべての決定木がどのようにして「刈り取られる」かを示し、結果のツリーのすべての変数が影響を受けます。
論文 参考訳（メタデータ） (2021-09-01T22:12:47Z) - Simple is better: Making Decision Trees faster using random sampling [4.284674689172996]
近年,ビッグデータ上での堅牢な機械学習モデル構築において,勾配向上決定木が普及している。
理論的および実験的に、ランダムに分割点を均一に選択することは、精度と計算効率の点で、同じあるいはさらに優れた性能を提供することを示す。
論文 参考訳（メタデータ） (2021-08-19T17:00:21Z) - Convex Polytope Trees [57.56078843831244]
コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。
木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
論文 参考訳（メタデータ） (2020-10-21T19:38:57Z) - MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。
当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
論文 参考訳（メタデータ） (2020-07-24T17:06:55Z) - Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
様々な目的に対して最適な決定木を生成する手法を提案する。
また,連続変数が存在する場合に最適な結果が得られるスケーラブルなアルゴリズムも導入する。
論文 参考訳（メタデータ） (2020-06-15T19:00:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。