論文の概要: Efficient Quantum Agnostic Improper Learning of Decision Trees
- arxiv url: http://arxiv.org/abs/2210.00212v2
- Date: Sun, 21 May 2023 06:10:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-24 05:35:00.735536
- Title: Efficient Quantum Agnostic Improper Learning of Decision Trees
- Title（参考訳）: 決定木の効率的な量子非依存不適切な学習
- Authors: Sagnik Chatterjee, Tharrmashastha SAPV, Debajyoti Bera
- Abstract要約: 我々は、インスタンス上の一様境界を持つ決定木を学習するためのポリアグノスティック(n,t,frac1varepsilon)$量子アルゴリズムを提供する。
我々のアルゴリズムは、メンバーシップクエリなしで決定木を学習するための最初のアルゴリズム(古典的または量子的)である。
- 参考スコア（独自算出の注目度）: 0.47267770920095525
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The agnostic setting is the hardest generalization of the PAC model since it
is akin to learning with adversarial noise. In this paper, we give a
poly$(n,t,{\frac{1}{\varepsilon}})$ quantum algorithm for learning size $t$
decision trees with uniform marginal over instances, in the agnostic setting,
without membership queries. Our algorithm is the first algorithm (classical or
quantum) for learning decision trees in polynomial time without membership
queries. We show how to construct a quantum agnostic weak learner by designing
a quantum version of the classical Goldreich-Levin algorithm that works with
strongly biased function oracles. We show how to quantize the agnostic boosting
algorithm by Kalai and Kanade (NIPS 2009) to obtain the first efficient quantum
agnostic boosting algorithm. Our quantum boosting algorithm has a polynomial
improvement in the dependence of the bias of the weak learner over all adaptive
quantum boosting algorithms while retaining the standard speedup in the VC
dimension over classical boosting algorithms. We then use our quantum boosting
algorithm to boost the weak quantum learner we obtained in the previous step to
obtain a quantum agnostic learner for decision trees. Using the above
framework, we also give quantum decision tree learning algorithms for both the
realizable setting and random classification noise model, again without
membership queries.
- Abstract（参考訳）: 不可知的な設定は、対向雑音による学習に似ているため、PACモデルの最も難しい一般化である。
本稿では,インスタンスを一様に割った決定木を学習するためのpoly$(n,t,{\frac{1}{\varepsilon}})$量子アルゴリズムを提案する。
我々のアルゴリズムは多項式時間で決定木を学習するための最初のアルゴリズム(古典的あるいは量子的)である。
古典的goldreich-levinアルゴリズムの量子バージョンを設計すれば,強バイアス関数オラクルで動作する量子非依存な弱学習器を構築する方法を示す。
本稿では,Kalai and Kanade (NIPS 2009) によるAgnostic boostingアルゴリズムの量子化を行い,第1の効率的な量子Agnostic boostingアルゴリズムを提案する。
量子ブースティングアルゴリズムは,従来のブースティングアルゴリズムよりもvc次元の標準速度を維持しつつ,すべての適応量子ブースティングアルゴリズムに対する弱学習者のバイアスの依存度を多項式的に改善する。
次に、量子ブースティングアルゴリズムを用いて、前ステップで得た弱い量子学習者を強化し、決定木に対する量子非依存学習者を得る。
上記のフレームワークを使用して、メンバシップクエリを使わずに、実現可能な設定とランダム分類の両方のノイズモデルのための量子決定木学習アルゴリズムを提供する。
関連論文リスト
- An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Machine Learning [14.955338558971787]
証明可能な指数的量子スピードアップは、線形系を解くためのセミナルHHL量子アルゴリズム以来、中心的な研究目標となっている。
量子と量子に着想を得た古典的アルゴリズム間で、このような証明可能な指数的分離を初めて提示する。
論文 参考訳（メタデータ） (2024-11-04T13:49:26Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳（メタデータ） (2024-02-26T09:32:07Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - Quantum-Enhanced Greedy Combinatorial Optimization Solver [12.454028945013924]
最適化問題を解くために反復量子最適化アルゴリズムを導入する。
72量子ビット以下のプログラム可能な超伝導量子系に量子アルゴリズムを実装した。
量子アルゴリズムは古典的な欲求よりも体系的に優れており、量子エンハンスメントのシグナルとなる。
論文 参考訳（メタデータ） (2023-03-09T18:59:37Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum Bayes AI [1.7403133838762443]
量子ベイズAI(Quantum Bayesian AI, Q-B)は、量子コンピューティングで利用可能な計算ゲインを補う新興分野である。
我々は、古典的および量子的確率の双対性を提供して、後続の関心量の計算を行う。
本稿では,2つの単純な分類アルゴリズム上での量子アルゴリズムの挙動について述べる。
論文 参考訳（メタデータ） (2022-08-17T04:51:10Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Quantum Inspired Adaptive Boosting [0.0]
量子アンサンブル法は古典的アルゴリズムに勝らないことを示す。
本稿では,量子アンサンブル法と適応的なブースティングを組み合わせた手法を提案する。
アルゴリズムはテストされ、公開データセット上のAdaBoostアルゴリズムに匹敵することがわかった。
論文 参考訳（メタデータ） (2021-02-01T16:33:14Z) - Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
入力および出力システムへのブラックボックスアクセスを前提として,最初の効率的な量子因果順序探索アルゴリズムを開発した。
我々は、量子コムを用いて因果順序をモデル化し、我々のアルゴリズムは、与えられたプロセスと互換性のある入力と出力の順序を出力する。
我々のアルゴリズムは、量子通信ネットワークで利用可能な伝送経路を効率的に検出し、最適化する方法を提供する。
論文 参考訳（メタデータ） (2020-12-03T07:12:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。