An Improved Quantum Algorithm for Ridge Regression
An Improved Quantum Algorithm for Ridge Regression
复制标题
DOI：
10.1109/tkde.2019.2937491
复制
发表时间：
2017-07
影响因子：
8.9
通讯作者：
Chao-Hua Yu;F. Gao;Q. Wen
中科院分区：
文献类型：
--
作者：
Chao-Hua Yu;F. Gao;Q. Wen
岭回归（Ridge Regression，RR）是一种重要的机器学习方法，它在普通的多元线性回归中引入正则化超参数$\alpha$α，用于分析存在多重共线性的数据。在本文中，我们提出了一个量子算法的RR，其中并行哈密顿模拟的技术，提出了并行模拟的埃尔米特矩阵的数量，并用于开发一个量子版本的$K$K折交叉验证方法，它可以有效地估计的预测性能的RR。我们的算法包括两个阶段：（1）使用量子$K$K折交叉验证来有效地确定一个好的$\alpha$α，从而RR可以实现良好的预测性能，然后（2）生成一个量子态编码的最佳拟合参数的RR与这样的$\alpha$α，它可以进一步用于预测新的数据。由于采用了不确定稠密哈密顿模拟作为关键子程序，我们的算法可以有效地处理非稀疏数据矩阵。结果表明，我们的算法可以实现指数加速比（低秩）的数据矩阵与低条件数的经典对应。但当数据矩阵的条件数很大时，可以服从满秩或近似满秩的数据矩阵，只能实现多项式加速。
Ridge regression (RR) is an important machine learning technique which introduces a regularization hyperparameter $\alpha$α to ordinary multiple linear regression for analyzing data suffering from multicollinearity. In this paper, we present a quantum algorithm for RR, where the technique of parallel Hamiltonian simulation to simulate a number of Hermitian matrices in parallel is proposed and used to develop a quantum version of $K$K-fold cross-validation approach, which can efficiently estimate the predictive performance of RR. Our algorithm consists of two phases: (1) using quantum $K$K-fold cross-validation to efficiently determine a good $\alpha$α with which RR can achieve good predictive performance, and then (2) generating a quantum state encoding the optimal fitting parameters of RR with such $\alpha$α, which can be further utilized to predict new data. Since indefinite dense Hamiltonian simulation has been adopted as a key subroutine, our algorithm can efficiently handle non-sparse data matrices. It is shown that our algorithm can achieve exponential speedup over the classical counterpart for (low-rank) data matrices with low condition numbers. But when the condition numbers of data matrices are large to be amenable to full or approximately full ranks of data matrices, only polynomial speedup can be achieved.