論文の概要: Quantum Relief Algorithm
- arxiv url: http://arxiv.org/abs/2002.00184v1
- Date: Sat, 1 Feb 2020 10:18:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-05 00:36:46.325286
- Title: Quantum Relief Algorithm
- Title（参考訳）: 量子緩和アルゴリズム
- Authors: Wen-Jie Liu, Pei-Pei Gao, Wen-Bin Yu, Zhi-Guo Qu, Ching-Nung Yang
- Abstract要約: リリーフアルゴリズム(Relief algorithm)は、Kira と Rendell によって提案された二項分類における特徴選択アルゴリズムである。
Reliefアルゴリズム(quantum Relief algorithm)と呼ばれるReliefアルゴリズムに基づく量子特徴選択アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 12.599184944451833
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Relief algorithm is a feature selection algorithm used in binary
classification proposed by Kira and Rendell, and its computational complexity
remarkable increases with both the scale of samples and the number of features.
In order to reduce the complexity, a quantum feature selection algorithm based
on Relief algorithm, also called quantum Relief algorithm, is proposed. In the
algorithm, all features of each sample are superposed by a certain quantum
state through the \emph{CMP} and \emph{rotation} operations, then the
\emph{swap test} and measurement are applied on this state to get the
similarity between two samples. After that, \emph{Near-hit} and
\emph{Near-miss} are obtained by calculating the maximal similarity, and
further applied to update the feature weight vector $WT$ to get $WT'$ that
determine the relevant features with the threshold $\tau$. In order to verify
our algorithm, a simulation experiment based on IBM Q with a simple example is
performed. Efficiency analysis shows the computational complexity of our
proposed algorithm is \emph{O(M)}, while the complexity of the original Relief
algorithm is \emph{O(NM)}, where $N$ is the number of features for each sample,
and $M$ is the size of the sample set. Obviously, our quantum Relief algorithm
has superior acceleration than the classical one.
- Abstract（参考訳）: Reliefアルゴリズムは、Kira と Rendell によって提案された二項分類で使われる特徴選択アルゴリズムであり、その計算複雑性はサンプルの規模と特徴数の両方で顕著に増加する。
複雑性を低減するために、量子救済アルゴリズム(quantum relief algorithm)とも呼ばれる救済アルゴリズムに基づく量子特徴選択アルゴリズムを提案する。
アルゴリズムでは、各サンプルの全ての特徴は \emph{cmp} と \emph{rotation} 演算を通してある量子状態によって重ね合わされ、次に \emph{swap test} と測定は2つのサンプル間の類似性を得るためにこの状態に適用される。
その後、最大類似度を計算することで \emph{Near-hit} と \emph{Near-miss} を取得し、さらに特徴量ベクトル $WT$ を更新して、閾値 $\tau$ で関連する特徴を決定する $WT'$ を得る。
提案アルゴリズムを検証するため,簡単な例でIBM Qに基づくシミュレーション実験を行った。
効率解析により,提案アルゴリズムの計算複雑性は \emph{O(M)} であり,元のReliefアルゴリズムの複雑性は \emph{O(NM)} である。
もちろん、我々の量子リリーフアルゴリズムは古典的アルゴリズムよりも加速が優れている。
関連論文リスト
- Replicable Learning of Large-Margin Halfspaces [46.91303295440005]
我々は,大マージンハーフスペースを学習する問題に対して,効率的なアルゴリズムを提供する。
Impagliazzo, Lei, Pitassi, Sorrellによるアルゴリズム [STOC 2022] の改良を行った。
論文 参考訳（メタデータ） (2024-02-21T15:06:51Z) - Quantum-Based Feature Selection for Multi-classification Problem in
Complex Systems with Edge Computing [15.894122816099133]
マルチクラス化問題,すなわちQReliefFに対する量子ベースの特徴選択アルゴリズムを提案する。
我々のアルゴリズムは、O(M) から O(sqrt(M)) への複雑さを減らし、最も近い隣人を見つけるのに優れている。
論文 参考訳（メタデータ） (2023-10-01T03:57:13Z) - On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
ベルヌーイ報奨を伴う多腕バンディットにおける固定予算によるベストアーム識別の問題について検討する。
A/Bテスト問題としても知られる2つのアームの問題に対して,各アームを等しくサンプリングするアルゴリズムが存在しないことを証明した。
論文 参考訳（メタデータ） (2023-08-23T08:38:53Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Adaptive Algorithm for Quantum Amplitude Estimation [13.82667502131475]
振幅の間隔推定のための適応アルゴリズムを提案する。
提案アルゴリズムは、同じレベルの精度を達成するために、同じ数の量子クエリを使用する。
我々は,古典モンテカルロサンプリングに対する2次高速化として,オラクルクエリの数が$O(1/epsilon)$に達することを厳密に証明する。
論文 参考訳（メタデータ） (2022-06-16T21:11:15Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Low depth algorithms for quantum amplitude estimation [6.148105657815341]
振幅推定のための2つの新しい低深さアルゴリズムの設計と解析
これらのアルゴリズムはモンテカルロ法の量子スピードアップを実現に近づける。
論文 参考訳（メタデータ） (2020-12-06T18:39:20Z) - Stochastic Multi-level Composition Optimization Algorithms with
Level-Independent Convergence Rates [12.783783498844022]
目的関数が$T$関数のネスト合成であるような,スムーズな多層合成最適化問題について検討する。
citeGhaRuswan20を$T$のレベルで一般化した最初のアルゴリズムは、$mathcalO (1/epsilon$6) のサンプル複雑性を実現することができることを示す。
これは、(アン)マルチレベル設定のために設計されたオンラインアルゴリズムが、標準仮定の下で同じサンプル複雑性を得るのはこれが初めてである。
論文 参考訳（メタデータ） (2020-08-24T15:57:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。