量子譜回歸算法

潘世杰 高 飛 萬(wàn)林春 秦素娟 溫巧燕

1(網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室(北京郵電大學(xué)) 北京 100876) 2(密碼科學(xué)技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 北京 100878)

量子計(jì)算展示了其相對(duì)經(jīng)典計(jì)算的強(qiáng)大優(yōu)勢(shì)[1-2].在處理特定的問(wèn)題時(shí)，如大數(shù)質(zhì)因數(shù)分解[3]、無(wú)結(jié)構(gòu)數(shù)據(jù)搜索[4]、稀疏線性方程組求解[5]和低秩矩陣主成分分析[6]，采用量子計(jì)算的方式具有比經(jīng)典計(jì)算方式低得多的復(fù)雜度.近年來(lái)，一些研究人員將量子強(qiáng)大的計(jì)算能力用在處理經(jīng)典計(jì)算機(jī)上具有較高復(fù)雜度的機(jī)器學(xué)習(xí)問(wèn)題，取得了一系列成果，包括量子回歸算法[7]、量子支持向量機(jī)[8]、量子生成對(duì)抗網(wǎng)絡(luò)[9-10]、量子神經(jīng)網(wǎng)絡(luò)和量子數(shù)據(jù)挖掘[11]等.

子空間學(xué)習(xí)是機(jī)器學(xué)習(xí)的重要部分.現(xiàn)實(shí)世界的數(shù)據(jù)大多數(shù)是以高維的形式出現(xiàn)，而決定計(jì)算任務(wù)——例如分類和回歸——結(jié)果的有效維度往往很低.由于直接處理高維數(shù)據(jù)不僅需要消耗大量計(jì)算資源，還會(huì)導(dǎo)致維數(shù)災(zāi)難(the curse of dimensionality)問(wèn)題，因此子空間學(xué)習(xí)被提出，用來(lái)把數(shù)據(jù)集從高維降到低維，同時(shí)保持?jǐn)?shù)據(jù)潛在的結(jié)構(gòu).人臉識(shí)別的結(jié)果表明，通過(guò)子空間學(xué)習(xí)進(jìn)行降維，可以顯著地提高算法的性能[12].盡管子空間學(xué)習(xí)可以部分解決高維數(shù)據(jù)的學(xué)習(xí)問(wèn)題，但子空間學(xué)習(xí)本身通常也需要很高的復(fù)雜度，因此如何降低子空間學(xué)習(xí)的復(fù)雜度是一個(gè)很有實(shí)際意義的問(wèn)題.一個(gè)自然而然的想法是將量子計(jì)算應(yīng)用于子空間學(xué)習(xí)，以達(dá)到更低的算法復(fù)雜度.

常用的子空間學(xué)習(xí)算法包括主成分分析(principal components analysis,PCA)[13]、線性判別分析(linear discriminant analysis,LDA)[14]、局部保持投影(locality preserving projections,LPP)[12]和鄰域保持嵌入(neighborhood preserving embedding,NPE)[15]等.子空間學(xué)習(xí)算法如LDA,LPP和NPE，通常需要進(jìn)行稠密矩陣的特征分解，這往往需要消耗較高的計(jì)算資源.為了降低計(jì)算資源，2007年Cai等人[16]提出了譜回歸降維框架，該框架包含了很多現(xiàn)有的子空間學(xué)習(xí)算法，如LDA，LPP和NPE.在同一篇文章中，針對(duì)結(jié)合標(biāo)簽信息來(lái)構(gòu)造對(duì)應(yīng)圖的子空間學(xué)習(xí)，Cai等人提出了高效譜回歸.Cai等人提出可利用權(quán)重矩陣的特殊結(jié)構(gòu)，結(jié)合格拉姆-施密特正交化來(lái)得到稠密矩陣的特征向量，而不需要對(duì)稠密矩陣進(jìn)行特征分解，從而把復(fù)雜度從維數(shù)的立方降低為維數(shù)的一次方.另外，因?yàn)橐肓司€性回歸，所以譜回歸中也可以很自然地加入正則化參數(shù)，使得算法可用于數(shù)據(jù)矩陣是病態(tài)矩陣的情況.

在量子領(lǐng)域，Lloyd等人[6]率先提出了量子主成分分析算法(quantum principal component analysis algorithm,QPCA)，算法相對(duì)經(jīng)典算法具有指數(shù)加速效果.需要指出的是，盡管該算法被稱為QPCA算法，但實(shí)際上如果要維持量子算法的加速效果，該算法只能用來(lái)得到低秩(或者近似低秩)矩陣的較大的特征值，以及以量子態(tài)形式得到對(duì)應(yīng)的特征向量；另外，如果矩陣有重特征值，那么我們無(wú)法通過(guò)量子主成分分析得到重特征值對(duì)應(yīng)的一組特征向量，而只能得到特征向量的疊加態(tài).隨后，Yu等人基于量子PCA算法，提出了量子PCA降維算法，當(dāng)降維后數(shù)據(jù)的維數(shù)為訓(xùn)練數(shù)據(jù)維數(shù)的對(duì)數(shù)時(shí)，他們的量子算法相對(duì)經(jīng)典算法實(shí)現(xiàn)了指數(shù)級(jí)的加速[17].Cong等人實(shí)現(xiàn)了量子LDA算法，與經(jīng)典算法相比有指數(shù)級(jí)的加速效果[18].Meng等人基于譜回歸降維框架[16]，首次提出了正則化子空間學(xué)習(xí)的量子譜回歸算法(MYXZ算法，以作者姓名首字母命名)，并在降維數(shù)據(jù)的項(xiàng)數(shù)m和數(shù)據(jù)的特征數(shù)n滿足m=O(lbn)時(shí)，算法具有多項(xiàng)式加速效果[19].盡管如此，MYXZ算法仍然存在有待改進(jìn)的地方.首先，MYXZ算法在算法的第一步，即求一般特征值問(wèn)題時(shí)用了稀疏哈密頓量模擬，當(dāng)處理的矩陣是稀疏矩陣時(shí)，算法具有良好的加速效果，但實(shí)際應(yīng)用中存在很多矩陣不稀疏的例子，例如LDA，此時(shí)用稀疏哈密頓量模擬沒(méi)有加速效果.其次，如果算法第一步的解中有相同的特征值，也會(huì)導(dǎo)致MYXZ算法無(wú)法得到相應(yīng)的特征向量(只能得到特征向量的疊加態(tài))而導(dǎo)致后續(xù)步驟出錯(cuò).最后，MYXZ算法的加速基于假設(shè)m=O(lbn)，其中m為數(shù)據(jù)的項(xiàng)數(shù)，n為數(shù)據(jù)的特征數(shù).因?yàn)樽V回歸的原始文獻(xiàn)[16]的重點(diǎn)在于把算法復(fù)雜度中的因子m3降至m，而對(duì)于m=O(lbn)的情況，譜回歸本身只有很小的加速效果，因此我們認(rèn)為m=O(n)是更符合實(shí)際情況的假設(shè).

本文首先對(duì)MYXZ算法進(jìn)行了細(xì)致分析，并指出了算法的局限性.然后，我們提出了一個(gè)改進(jìn)算法，該算法采用了量子奇異值估計(jì)技術(shù)(quantum singular value estimation,QSVE)[20]，而不是稀疏量子主成分分析來(lái)求解一般特征值問(wèn)題，在處理稠密矩陣特征值問(wèn)題時(shí)，QSVE具有更低的復(fù)雜度.當(dāng)m=O(n)時(shí)，我們的改進(jìn)算法相對(duì)經(jīng)典算法有多項(xiàng)式加速效果；當(dāng)算法的第1步涉及的矩陣是稠密矩陣時(shí)，我們的改進(jìn)算法相對(duì)MYXZ算法有多項(xiàng)式加速效果.其次，針對(duì)結(jié)合標(biāo)簽信息來(lái)構(gòu)造對(duì)應(yīng)圖的子空間學(xué)習(xí)算法，例如LDA和帶標(biāo)簽的LPP,NPE，我們提出了相應(yīng)的量子算法.我們把文獻(xiàn)[16]中提出的高效算法中復(fù)雜度較高的嶺回歸部分設(shè)計(jì)成量子算法，并行得到多個(gè)嶺回歸結(jié)果；而復(fù)雜度較低的部分(即格拉姆施密特正交化)仍然采用原算法實(shí)現(xiàn).這樣做的好處在于既規(guī)避了稠密矩陣特征分解的問(wèn)題，也利用了量子的加速效果.另外，為了算法的完整性，我們給出了對(duì)新輸入數(shù)據(jù)進(jìn)行降維的實(shí)現(xiàn)方式.當(dāng)m=O(n)時(shí)，我們的算法相對(duì)經(jīng)典的高效譜回歸算法具有多項(xiàng)式加速效果.

1 正則化子空間學(xué)習(xí)的譜回歸

在本節(jié)中，我們將對(duì)正則化子空間學(xué)習(xí)的譜回歸進(jìn)行回顧，并介紹其復(fù)雜度.

1.1 譜回歸

令G表示由m個(gè)頂點(diǎn)構(gòu)成的圖，每個(gè)頂點(diǎn)對(duì)應(yīng)一張人臉圖像即xi，W為一個(gè)m×m的權(quán)重矩陣，其元素表示圖G中頂點(diǎn)i和頂點(diǎn)j之間的權(quán)重.譜回歸是一個(gè)降維算法的框架，通過(guò)W矩陣的不同選取方式，能得到不同的降維算法，如線性判別分析、局部保持投影和鄰域保持嵌入.譜回歸的提出是為了避免降維算法中復(fù)雜度較高的稠密矩陣特征分解.

譜回歸主要包含3個(gè)步驟：

1)求解最大特征向量問(wèn)題

Wy=λDy，

(1)

2)求解c-1個(gè)最小二乘問(wèn)題

(2)

3)對(duì)新數(shù)據(jù)x進(jìn)行降維，令A(yù)=(a1,a2,…,ac)，則降維后的坐標(biāo)為

yx=ATx.

當(dāng)樣本數(shù)m小于特征數(shù)n時(shí)，優(yōu)化問(wèn)題(2)是病態(tài)的，一種常見(jiàn)的做法是采用嶺回歸的方式，引入正則化參數(shù)α，即求解優(yōu)化問(wèn)題：

此時(shí)ai的解析解為

ai=(XXT+αI)-1Xy(i).

引入正則化參數(shù)的譜回歸被稱為正則化子空間學(xué)習(xí)的譜回歸.

在文獻(xiàn)[16]中，作者提出一種高效的譜回歸求解方法.對(duì)于結(jié)合標(biāo)簽信息來(lái)構(gòu)造對(duì)應(yīng)圖的降維算法，如LDA以及有監(jiān)督的LPP和NPE，其最大特征向量問(wèn)題(即式(1))的求解是平凡的.不妨假設(shè)數(shù)據(jù)是按標(biāo)簽信息排列的，則

其中W(t)是mt×mt的矩陣，mt為第t個(gè)類別的樣本數(shù)，此時(shí)可以直接給出式(1)的最大特征值1對(duì)應(yīng)的c個(gè)特征向量，即

另外，顯然全1向量1=(1,1,…,1)T也是式(1)中最大特征值1對(duì)應(yīng)的特征向量.因?yàn)閷?duì)所有的W，1都是式(1)中特征值1對(duì)應(yīng)的特征向量，因此1并不包含關(guān)于問(wèn)題的任何信息.為了去除和1相關(guān)的冗余信息，文獻(xiàn)[16]中提出的方法是取1為第1個(gè)正交向量，其余c-1個(gè)特征向量由y(i)通過(guò)格拉姆-施密特正交化得到.最后去掉1，就得到了我們想要的c-1個(gè)相互正交的特征向量，也即式(1)的解.

1.2 譜回歸的復(fù)雜度

2 正則化子空間學(xué)習(xí)的量子譜回歸

本節(jié)將對(duì)正則化子空間學(xué)習(xí)的量子譜回歸進(jìn)行回顧，并對(duì)算法進(jìn)行分析，給出算法復(fù)雜度.

2.1 量子譜回歸

2019年，Meng等人提出了正則化子空間學(xué)習(xí)的量子譜回歸算法[19](MYXZ算法).該算法沒(méi)有利用文獻(xiàn)[16]中的核心思想，即對(duì)于結(jié)合標(biāo)簽信息來(lái)構(gòu)造對(duì)應(yīng)圖的降維算法，其最大特征向量問(wèn)題的求解(式(1))是平凡的，而是直接用量子主成分分析[6]的方式來(lái)對(duì)矩陣進(jìn)行特征分解.

MYXZ算法主要包含2個(gè)步驟：

1)用稀疏矩陣量子主成分分析和量子矩陣向量乘法來(lái)求式(1)的解y(1),y(2),…,y(c-1).

2)用量子算法求

ai=(XXT+αI)-1Xy(i).

MYXZ算法假設(shè)矩陣X事先存儲(chǔ)在一個(gè)樹(shù)狀的QRAM中，基于量子稠密線性方程組求解技術(shù)[16]，設(shè)計(jì)出量子稠密矩陣嶺回歸技術(shù)，可直接用于求ai.

MYXZ算法沒(méi)有考慮算法的第3步，也即針對(duì)一個(gè)新輸入的數(shù)據(jù)x，輸出其降維后坐標(biāo)yx=Ax.

2.2 算法分析

本節(jié)將結(jié)合文獻(xiàn)[19]中的假設(shè)，對(duì)算法及其復(fù)雜度進(jìn)行分析.

3 改進(jìn)的量子譜回歸

在實(shí)際應(yīng)用中，往往樣本數(shù)量m和提取的特征個(gè)數(shù)n的規(guī)模是相差不大的，另外，在譜回歸的原始論文中[16]，譜回歸算法的優(yōu)勢(shì)在于降低了復(fù)雜度中參數(shù)m的次數(shù).如果m?n，譜回歸的加速效果并不明顯.因此在改進(jìn)的算法中，在其他參數(shù)假設(shè)不變的前提下，我們希望在m=O(n)時(shí)，量子算法相對(duì)經(jīng)典算法有顯著加速效果.

4 高效譜回歸的量子算法

在文獻(xiàn)[16]中，Cai等人針對(duì)結(jié)合標(biāo)簽信息來(lái)構(gòu)造對(duì)應(yīng)圖的降維算法，如有監(jiān)督的局部保持投影和鄰域保持嵌入，提出了一個(gè)高效的實(shí)現(xiàn)方式.對(duì)于這類降維算法，式(1)的最大特征值1是c重特征值，因而MYXZ算法無(wú)法進(jìn)行處理.我們提出了這類子空間學(xué)習(xí)問(wèn)題的量子譜回歸算法.我們的算法中也用到了MYXZ中的部分過(guò)程.

4.1 算法過(guò)程

考慮到量子主成分分析的局限性，我們直接采用經(jīng)典的方式來(lái)求式(1)的解.我們的算法步驟為：

1)令第1個(gè)特征向量為全1向量(1,1,…,1)T，通過(guò)對(duì)

進(jìn)行格拉姆-施密特正交化，得到c-1正交的特征向量，作為式(1)的解，記為y(1),y(2),…,y(c-1).

2)把y(1),y(2),…,y(c-1)存儲(chǔ)到QRAM中，制備量子態(tài)

3)對(duì)第2量子寄存器，執(zhí)行稠密矩陣嶺回歸量子算法，得

4)針對(duì)新輸入的量子態(tài)|x〉，用量子低秩矩陣向量乘法，來(lái)求其降維后量子態(tài)|y〉.

我們算法的第4步即對(duì)新輸入的數(shù)據(jù)進(jìn)行降維，這正是子空間學(xué)習(xí)的目的.MYXZ算法沒(méi)有給出算法的降維過(guò)程，為了算法的完整性，我們將給出降維過(guò)程以及其復(fù)雜度分析.

4.2 算法分析

為了方便對(duì)4.1節(jié)所述的步驟4的分析，我們定義對(duì)數(shù)據(jù)的量子訪問(wèn)[21]：

定義1[21].如果存在以下變換可以在復(fù)雜度T內(nèi)實(shí)現(xiàn)，那么稱我們可以通過(guò)量子訪問(wèn)矩陣A∈n×m：

其中,i∈{1,2,…,n}，Ai表示矩陣A的第i列構(gòu)成的向量.

綜上，算法的總復(fù)雜度為

相關(guān)算法的復(fù)雜度對(duì)比和適用條件如表1所示.需要注意的是，我們沒(méi)有把降維過(guò)程(即4.1節(jié)中的算法步驟4)的復(fù)雜度列在表中，因此表中量子高效譜回歸的總復(fù)雜度比上面算出來(lái)的復(fù)雜度稍低，但并不影響對(duì)比結(jié)果.

Table 1 Comparison of Complexity and Applicable Conditions of Classical and Quantum Spectral Regression Algorithms表1 經(jīng)典和量子譜回歸算法的復(fù)雜度和適用條件對(duì)比

5 結(jié) 論