量子典型相關(guān)分析算法

王慶樂(lè), 薛雪, 李元誠(chéng)?

(1 華北電力大學(xué)控制與計(jì)算機(jī)工程學(xué)院, 北京 102206;2 北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室, 北京 100876;3 中國(guó)科學(xué)技術(shù)大學(xué)量子信息重點(diǎn)實(shí)驗(yàn)室, 安徽 合肥 230026)

0 引 言

量子計(jì)算在處理某些特定問(wèn)題時(shí)有比經(jīng)典計(jì)算更強(qiáng)的計(jì)算能力,如質(zhì)因數(shù)分解[1]、非結(jié)構(gòu)化數(shù)據(jù)搜索[2]和矩陣計(jì)算問(wèn)題[3?5]。近年來(lái),隨著量子計(jì)算機(jī)的發(fā)展,量子機(jī)器學(xué)習(xí)(QML)受到了廣泛關(guān)注。QML 研究的一個(gè)重要方向是設(shè)計(jì)量子算法來(lái)加速機(jī)器學(xué)習(xí),包括數(shù)據(jù)分類[6,7]和線性回歸等[8?10]。

嚴(yán)格來(lái)說(shuō),大部分機(jī)器學(xué)習(xí)算法實(shí)際上也是統(tǒng)計(jì)分析算法,統(tǒng)計(jì)分析中的一種重要方法為典型相關(guān)分析。實(shí)際上,當(dāng)需要分析和研究?jī)山M變量之間的關(guān)系時(shí),通常會(huì)用到典型相關(guān)分析。例如,為了研究財(cái)政政策實(shí)施以后對(duì)經(jīng)濟(jì)發(fā)展的影響,需要考察有關(guān)財(cái)政政策的一系列指標(biāo)(如財(cái)政支出總額、財(cái)政赤字、國(guó)債發(fā)行額、稅率等)與經(jīng)濟(jì)發(fā)展的一系列指標(biāo)(如國(guó)內(nèi)生產(chǎn)總值、就業(yè)率等兩組變量)之間的相關(guān)程度。典型相關(guān)分析方法最初由Hotelling[11]在1936 年提出。2004 年,Hardoon 等[12]對(duì)該方法進(jìn)行了綜述,并提出了其在學(xué)習(xí)方法上的應(yīng)用。2005 年,Sun 等[13]提出把典型相關(guān)分析用于特征融合。近年來(lái),典型相關(guān)分析研究不斷發(fā)展,其變體也相繼被提出,包括基于核理論的典型相關(guān)分析[14]、基于流形結(jié)構(gòu)的典型相關(guān)分析[15]、基于監(jiān)督學(xué)習(xí)的典型相關(guān)分析[16]、稀疏典型相關(guān)分析等[17,18]。當(dāng)數(shù)據(jù)量很大時(shí),典型相關(guān)分析算法運(yùn)算速度很慢,耗時(shí)嚴(yán)重,因此其不適用于大數(shù)據(jù)時(shí)代。

本文利用量子計(jì)算的優(yōu)勢(shì)降低典型相關(guān)分析算法的復(fù)雜度,并提出了量子典型相關(guān)分析算法。所提出量子算法在特定參數(shù)條件下,相對(duì)經(jīng)典典型相關(guān)分析在維度上有指數(shù)加速效果。

1 典型相關(guān)分析

1.1 典型相關(guān)分析的提出

典型相關(guān)分析的目的是尋求兩組變量中每一組變量的線性組合,使得兩組變量的線性組合之間的相關(guān)性最大化。一般的相關(guān)性分析依賴于變量的坐標(biāo)系,即使兩組多維變量之間本質(zhì)上存在非常強(qiáng)的線性關(guān)系,坐標(biāo)系選取不恰當(dāng)也會(huì)導(dǎo)致線性關(guān)系不可見(jiàn)[12]。典型相關(guān)分析通過(guò)研究?jī)山M綜合指標(biāo)之間的關(guān)系來(lái)研究變量之間的線性關(guān)系,可用于挖掘一般相關(guān)性分析中的不可見(jiàn)關(guān)系。

具體地,考慮兩組多變量隨機(jī)向量:X= [x0,x1,··· ,xn?1]和Y= [y0,y1,··· ,ym?1],其中xi和yj均為l維向量。定義一個(gè)線性組合wx,使得矩陣X列向量之間的一個(gè)線性組合為zx=Xwx。同理,可定義zy=Ywy。

典型相關(guān)分析通過(guò)選擇合適的wx和wy,使投影后的向量具有最大的相關(guān)性,即最大化函數(shù)

1.2 典型相關(guān)分析的求解及其復(fù)雜度

記[x,y]的協(xié)方差矩陣為C(x,y),則

經(jīng)典算法求解(4)式轉(zhuǎn)化為求一般特征值問(wèn)題,計(jì)算復(fù)雜度為O(poly(nml)),其中n、m分別是隨機(jī)向量X、Y中的隨機(jī)變量個(gè)數(shù),l是隨機(jī)變量xi和yj的維度。

2 量子典型相關(guān)分析

2.1 問(wèn)題轉(zhuǎn)化

2.2 量子典型相關(guān)分析算法設(shè)計(jì)

量子算法的輸入是矩陣X= [x0,x1,··· ,xn?1]和Y= [y1,y2,··· ,ym]。簡(jiǎn)單起見(jiàn),令n=m。實(shí)際上,如果n>m,可令Y= [y1,y2,··· ,ym,y1,y2,··· ,yn?m]。由于要找的是一個(gè)向量之間的線性組合,因此對(duì)Y進(jìn)行這樣的處理不會(huì)影響最終結(jié)果。

不妨假設(shè)向量xi和yj(i,j∈{0,1,··· ,n?1})均為歸一化向量,即

假設(shè)輸入存儲(chǔ)在一個(gè)經(jīng)典的數(shù)據(jù)結(jié)構(gòu)中,那么量子訪問(wèn)數(shù)據(jù)結(jié)構(gòu)可以高效創(chuàng)建矩陣X和Y的每一列對(duì)應(yīng)的量子態(tài)

以及每一列的二范數(shù)組成的向量對(duì)應(yīng)的量子態(tài)|?X〉和|?Y〉,創(chuàng)建這些量子態(tài)的復(fù)雜度均為O[polylog(mnl)]。

步驟2:對(duì)ρ 做主成分分析

根據(jù)定理1,可實(shí)現(xiàn)和ρ 相關(guān)的量子操作,根據(jù)量子主成分分析算法[19],可以在量子態(tài)ρ 上做相位估計(jì)。假設(shè)ρ 的特征分解為

那么,由文獻(xiàn)[20]可以得到

步驟3:計(jì)算

3 結(jié) 論

典型相關(guān)分析是一種在實(shí)際生活中有很多應(yīng)用的重要相關(guān)分析算法。利用量子算法的并行運(yùn)算特性,提出了一種量子典型相關(guān)分析。將經(jīng)典問(wèn)題轉(zhuǎn)化為求解一個(gè)矩陣的主成分問(wèn)題以及矩陣的冪與向量相乘問(wèn)題。在求矩陣的主成分問(wèn)題中,結(jié)合量子主成分分析和量子判別分析中的子算法設(shè)計(jì)了所提出算法;在求矩陣的冪和向量相乘的問(wèn)題中,應(yīng)用HHL 算法的思想并結(jié)合矩陣求冪算法,得到了很好的加速效果。在特定參數(shù)條件下,所提出算法相比經(jīng)典典型分析具有指數(shù)加速效果。