تخمین پارامترهای یک مدل رگرسیون خطی با توسعه روش حداقل مربعات خطا بر اساس محاسبات کوانتومی

رمضانی, مهدی; کلانتری, صادق; مددی, علی

doi:10.22052/scj.2024.253276.1169

تخمین پارامترهای یک مدل رگرسیون خطی با توسعه روش حداقل مربعات خطا بر اساس محاسبات کوانتومی

نوع مقاله : مقاله پژوهشی

نویسندگان

¹ گروه ریاضی، دانشکده ریاضی، دانشگاه تفرش، تفرش، ایران

² گروه کنترل، دانشکده مهندسی برق، دانشگاه تفرش، تفرش، ایران

10.22052/scj.2024.253276.1169

چکیده

روش حداقل مربعات خطا با وجود سادگی دارای نتایج قابل قبولی در شناسایی سیستمها میباشد. فرآیند تخمین پارامترها در شناسایی سیستم منجر به حل معادله خطی Ax=b میشود. نکته حائز اهمیت این است که روش عادی حل مسئله فوق دارای پیچیدگی محاسباتی از مرتبه O(n^3) برای یک ماتریس n×n میباشد. در حل این مسئله، پیچیدگی محاسباتی با افزایش n (سایز ماتریس داده) افزایش مییابد. از طرفی تعداد نمونههای بیشتر سبب مدلسازی بهتر سیستم میگردد. در مسائل عملی شناسایی سیستم، هنگامی که تعداد دادههای ورودی زیاد است بار محاسباتی به شدت افزایش می‌یابد. اخیرا در حوزه محاسبات کوانتومی الگوریتمهایی ارائه شده است که سبب کاهش چشمگیر بار محاسباتی میگردند. ازجمله مهمترین آنها الگوریتم HHL میباشد که معادله خطی فوق را در زمانO(κ^2 s^2 logn) حل میکند که κ عدد شرط و s میزان تنکی ماتریس میباشد. در این مقاله هدف این است که الگوریتم کوانتومی توسعه یافتهای برای حل مسئله شناسایی حداقل مربعات خطا (روش GLS) ارائه نماییم. در این مقاله دو روش کلاسیک-کوانتومی و تمام کوانتومی ارائه میگردد. روشهای ارائه شده در این مقاله قادر هستند برخلاف روش مرسوم HHL با ماتریسهای غیرهرمیتی، بدحال و با وجود نویز رنگی، پارامترهای بدون بایاس را محاسبه نمایند. روش پیشنهادی کلاسیک-کوانتومی، دارای پیچیدگی محاسباتی از مرتبه O(n^2 logn) و روش تمام کوانتومی از مرتبه O(polylogn) نسبت به سایز ماتریس داده میباشند. نتایج و مقایسه‌های انجام شده نشان می‌دهند که روشهای پیشنهادی مقاله نسبت به روشهای کلاسیک همچون شبه معکوس( با پیچیدگیO(n^3) ) دارای پیچیدگی و محدودیت کمتری میباشند.

کلیدواژه‌ها

موضوعات

الگوریتم های تکاملی

عنوان مقاله [English]

Parameter Estimation of a Linear Regression Model By Extending Least Square Method Based on Quantum Computing

نویسندگان [English]

Mehdi Ramezani ¹
Sadegh Kalantari ²
Ali Madadi ²

¹ Department of Mathematics, Tafresh University, Tafresh, Iran

² Department of Electrical Engineering, Tafresh University, Tafresh, Iran

چکیده [English]

The least square error method yields acceptable results in system identification. The process of parameter estimation helps solve the linear equation . The important point is that the normal method of solving the above problem has a computational complexity for an matrix. In solving this problem, the computational complexity increases with the increase of (the size of the data matrix). On the other hand, availability of more samples leads to better modeling of the system. In the practical problems of system identification, when the number of input data is large the computational complexity increases greatly. Recently, in the field of quantum computing, some algorithms have been presented that significantly reduce the computational complexity. Among the most important of them is the HHL algorithm, which solves the above linear equation in time, where is the condition number and s is the sparsity of the matrix. In this article, the goal is to present the developed quantum algorithm for solving the problem of least square error identification (GLS method). In this article, two classical-quantum and all-quantum methods are presented. Unlike conventional HHL methods, the proposed methods in this article are able to calculate unbiased parameters with non-Hermitian matrices, and color noise. The proposed classical-quantum method has a computational complexity of of and the all-quantum method has an order of in relation to the size of the data matrix. The results and comparisons show that the methods proposed in the article have less complexity and limitations than classical methods such as psudeo-inverse complexity).

کلیدواژه‌ها [English]

System identification
least squares error
quantum computing
computational complexity
quantum algorithm

مراجع

[1] P. Eykhoff, “Identification theory: Practical implications and limitations,” Measurement, vol. 2, no. 2, pp. 75-85, 1984, doi: 10.1016/0263-2241(84)90036-8.
[2] L. Ljung, “System Identification,” Signal Anal. Predict., pp. 163-173, 1998, doi: 10.1007/978-1-4612-1768-8_11.
[3] A. Ghanbari Sorkhi, H. Hassanpour, and M. Fateh, “Regions Proposal Selection in Objects Detection and Recogntion Systems,” Soft Comput. J., vol. 5, no. 2, pp. 34-47, 2016, dor: 20.1001.1.23223707.1395.5.2.4.1 [In Persian]
[4] J.J. Vyas, B. Gopalsamy, and H. Joshi, “System Identification,” SpringerBriefs Appl. Sci. Technol., pp. 47-51, 2018, doi: 10.1007/978-981-13-2547-2_4.
[5] M. Karari, System Identification, 4th ed., Amirkabir University of Technology Press, 2013 [In Persian].
[6] M. Mohagheghi, “An approach to accelerate policy iteration for probabilistic model checking of Markov decision processes using machine learning,” Soft Comput. J., vol. 11, no. 2, pp. 134-148, 2023, doi: 10.22052/scj.2023.243360.1029 [In Persian]
[7] S. Kalantari and M.J. Abdollahifard, “Optimization-based multiple-point geostatistics: A sparse way,” Comput. Geosci., vol. 95, pp. 85-98, 2016, doi: 10.1016/j.cageo.2016.07.006.
[8] S. Kalantari, A. Madadi, M. Ramezani, and A. Hajati, “Controlling the Ground Particle Size and Ball Mill Load Based on Acoustic Signal, Quantum Computation Basis, and Least Squares Regression, Case Study: Lakan Lead-Zinc Processing Plant,” Int. J. Ind. Electron. Control Optim., vol. 6, no. 3, pp. 205-218, Sep. 2023, doi: 10.22111/ieco.2023.45981.1488.
[9] S. Kalantari, A. Madadi, and M. Ramezani, “Reconstruction of geological images based on an adaptive spatial domain filter: an example to introduce quantum computation to geosciences,” Int. J. Min. Geo-Eng., vol. 57, no. 2, pp. 183-194, 2023, doi: 10.22059/IJMGE.2023.352048.595007.
[10] M. Khosravi and M. Zekri, “A review of quantum neural networks,” Soft Comput. J., vol. 1, no. 1, pp. 46-55, 2012, dor: 20.1001.1.23223707.1391.1.1.113.0 [In Persian].
[11] Y. Liu and S. Zhang, “Fast quantum algorithms for least squares regression and statistic leverage scores,” Theor. Comput. Sci., vol. 657, pp. 38-47, 2017, doi: 10.1016/j.tcs.2016.05.044.
[12] A.W. Harrow, A. Hassidim, and S. Lloyd, “Quantum algorithm for linear systems of equations,” Phys. Rev. Lett., vol. 103, no. 15, 2009, doi: 10.1103/physrevlett.103.150502.
[13] I. Kerenidis and A. Prakash, “Quantum Recommendation Systems,” 2016, arXiv:1603.08675, [Online]. Available: https://arxiv.org/abs/1603.08675.
[14] K. Li et al., “Quantum Linear System Algorithm for General Matrices in System Identification,” Entropy, vol. 24, no. 7, p. 893, 2022, doi: 10.3390/e24070893.
[15] M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Information. Cambridge, U.K.: Cambridge Univ. Press, 2010, doi: 10.1017/CBO9780511976667.
[16] S. Kalantari, M. Ramezani, and A. Madadi, “Introducing a New Hybrid Adaptive Local Optimal Low Rank Approximation Method for Denoising Images,” Int. J. Ind. Electron. Control Optim., vol. 3, no. 2, pp. 173-185, 2020, doi: 10.22111/ieco.2019.31245.1199.
[17] S. Kalantari, M. Ramezani, A. Madadi, and V.V. Estrela, “Reduction AWGN from Digital Images Using a New Local Optimal Low-Rank Approximation Method,” Smart Innov. Syst. Technol., 2020, doi: 10.1007/978-3-030-57548-9_5.
[18] G.H. Golub, A. Hoffman, and G.W. Stewart, “A generalization of the Eckart-Young-Mirsky matrix approximation theorem,” Linear Algebra Appl., vol. 88-89, pp. 317-327, 1987, doi: 10.1016/0024-3795(87)90114-5.
[19] S.A. Goreinov, I. Oseledets, D. Savostyanov, E.E. Tyrtyshnikov, and N.L. Zamarashkin, “How to Find a Good Submatrix,” Matrix Methods Theory Alg. Appl., pp. 247-256, 2010, doi: 10.1142/9789812836021_0015.
[20] N.K. Kumar and J. Schneider, “Literature survey on low rank approximation of matrices,” Linear Multilinear Algebra, vol. 65, no. 11, pp. 2212-2244, 2016, doi: 10.1080/03081087.2016.1267104.
[21] L. Grover and T. Rudolph, “Creating superpositions that correspond to efficiently integrable probability distributions,” 2002, arXiv:quant-ph/0208112, [Online]. Available: https://arxiv.org/abs/quant-ph/0208112
[22] L. Wossnig, Z. Zhao, and A. Prakash, “Quantum Linear System Algorithm for Dense Matrices,” Phys. Rev. Lett., vol. 120, no. 5, 2018, doi: 10.1103/physrevlett.120.050502.
[23] Y. Cao, A. Daskin, S. Frankel, and S. Kais, “Quantum Circuit Design for Solving Linear Systems of Equations,” Mol. Phys., vol. 110, no. 15-16, pp. 1675-1680, 2012, doi: 10.1080/00268976.2012.668289.