Linear regression is a popular machine learning approach to learn and predict real valued outputs or dependent variables from independent variables or features. In many real world problems, its beneficial to perform sparse linear regression to identify important features helpful in predicting the dependent variable. It not only helps in getting interpretable results but also avoids overfitting when the number of features is large, and the amount of data is small. The most natural way to achieve this is by using `best subset selection' which penalizes non-zero model parameters by adding $\ell_0$ norm over parameters to the least squares loss. However, this makes the objective function non-convex and intractable even for a small number of features. This paper aims to address the intractability of sparse linear regression with $\ell_0$ norm using adiabatic quantum computing, a quantum computing paradigm that is particularly useful for solving optimization problems faster. We formulate the $\ell_0$ optimization problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem and solve it using the D-Wave adiabatic quantum computer. We study and compare the quality of QUBO solution on synthetic and real world datasets. The results demonstrate the effectiveness of the proposed adiabatic quantum computing approach in finding the optimal solution. The QUBO solution matches the optimal solution for a wide range of sparsity penalty values across the datasets.
翻译:线性回归是一种流行的机器学习方法,用于学习和预测独立变量或特征中真实价值产出或依赖变量。在许多现实世界问题中,它有利于执行细线性回归,以找出有助于预测依赖变量的重要特征。它不仅有助于获得可解释的结果,而且避免在功能数量大时过度适应,数据数量小。实现这一点的最自然方法是使用“最佳子选择”,通过在最小方块损失的参数上增加$\ell_0美元标准来惩罚非零模式参数。然而,这使得目标功能不凝固,即使是对少量功能来说也是难以解决的。本文旨在用半径量计算解决微线性回归的不易易性,而使用$\ell_0美元标准,这是一个量性计算模式,对于更快地解决优化问题特别有用。我们把$\ell_0美元的最优化问题设计成一种不易受限制的平方块优化平方块优化(QUBO) 问题,并且用D-Wave 量性量性计算机来解决这个问题。我们研究并比较了Q-BO 最佳解决方案的质量。我们提议的最佳方法的合成结果。