許道云

(貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州省公共大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室，貴州貴陽550025)

大數(shù)據(jù)計(jì)算的基礎(chǔ)理論探究?

許道云?

(貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州省公共大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室，貴州貴陽550025)

在經(jīng)典計(jì)算中，對(duì)前端輸入數(shù)據(jù)的復(fù)雜性不做分析。在大數(shù)據(jù)計(jì)算中，前端輸入數(shù)據(jù)的復(fù)雜性分析反而成為大數(shù)據(jù)計(jì)算和分析的重點(diǎn)。本文討論大數(shù)據(jù)計(jì)算的基礎(chǔ)理論問題，將大數(shù)據(jù)計(jì)算問題分為目標(biāo)任務(wù)型和內(nèi)容認(rèn)知型。大數(shù)據(jù)計(jì)算形式上依賴于一個(gè)外部信息源，從計(jì)算的有效性，將大數(shù)據(jù)計(jì)算的討論限制在對(duì)數(shù)空間復(fù)雜類，涵蓋了并行計(jì)算復(fù)雜類。基于帶Oracle的圖靈計(jì)算模型，限制在對(duì)數(shù)空間內(nèi)圖靈可計(jì)算，并且外部信息源能夠用一個(gè)對(duì)數(shù)空間可計(jì)算的遞歸函數(shù)枚舉，引入了大數(shù)據(jù)可計(jì)算的計(jì)算模型和大數(shù)據(jù)可計(jì)算性、可判定問題等概念。

大數(shù)據(jù)計(jì)算;對(duì)數(shù)空間可計(jì)算性;并行可計(jì)算性;帶Oracle圖靈機(jī);大數(shù)據(jù)可計(jì)算性

阿蘭.圖靈(A.Turing)在1936年提出計(jì)算機(jī)的數(shù)學(xué)模型——圖靈機(jī)以后，20世紀(jì)40年代，數(shù)理邏輯學(xué)家馮.諾依曼以通用圖靈機(jī)為原型，設(shè)計(jì)了第一臺(tái)現(xiàn)代通用計(jì)算機(jī)EDVAC(電子離散變量自動(dòng)計(jì)算機(jī))。隨著現(xiàn)代計(jì)算機(jī)的出現(xiàn)，計(jì)算機(jī)可以解決的問題越來越多，計(jì)算量越來越大，同時(shí)對(duì)于科學(xué)計(jì)算的要求也越來越高(如:高效、正確、安全等)。

一個(gè)問題是可解的，是指存在求解該問題的一個(gè)算法。根據(jù)丘奇(Church)論題，一個(gè)可以用算法描述求解的問題，都有一臺(tái)圖靈機(jī)(Turing Machine)求解。在計(jì)算理論中，計(jì)算機(jī)器和程序是等同的。因此，一個(gè)問題是可解的，通常是指存在一臺(tái)圖靈機(jī)求解[1-4]。

研究發(fā)現(xiàn)，諸多的計(jì)算模型尚未突破圖靈計(jì)算模型，很多經(jīng)典的計(jì)算模型從“計(jì)算能力”來講，與圖靈計(jì)算模型等價(jià)[1-4]。如:隨機(jī)存取機(jī)器模型(RAM)，也稱無窮寄存器機(jī)器(URM)，RAM模型是算法分析與計(jì)算復(fù)雜性理論中重要的串行計(jì)算模型，引進(jìn)RAM是為了便于從理論上分析計(jì)算機(jī)串行程序所耗費(fèi)的時(shí)間、空間等資源，現(xiàn)代計(jì)算機(jī)高級(jí)語言設(shè)計(jì)的數(shù)學(xué)原型來自于RAM。

在RAM計(jì)算模型中，只用到如下4類基礎(chǔ)指令[1]:

1.置零Z(n):將第n個(gè)寄存器中的內(nèi)容置為0；

2.后繼S(n):將第n個(gè)寄存器中的內(nèi)容加1；

3.變換T(m，n):將第m個(gè)寄存器中的內(nèi)容替換第n個(gè)寄存器中的內(nèi)容；

4.轉(zhuǎn)移J(m，n，q):如果第m個(gè)寄存器中的內(nèi)容與第n個(gè)寄存器中的內(nèi)容相同，則轉(zhuǎn)向第q條指令，否則順序執(zhí)行下一條指令。

在可計(jì)算性與計(jì)算復(fù)雜性中，關(guān)注兩個(gè)基礎(chǔ)問題:一是判定問題是否可交給機(jī)器來完成(即是否可解)?二是如果可以用機(jī)器判定，則計(jì)算代價(jià)(時(shí)間和空間復(fù)雜性)如何估計(jì)?

希爾伯特(Hilbert)曾經(jīng)想建立一個(gè)大一統(tǒng)的數(shù)學(xué)理論(稱為Hilbert計(jì)劃)，使一切事物和問題都可以數(shù)學(xué)地認(rèn)知和求解。Hilbert計(jì)劃企圖完成一個(gè)宏偉藍(lán)圖，任何算術(shù)問題都是可解的。但是，后來的情況不是這樣。哥德爾(G?del)證明了:在含有一階謂詞邏輯和初等算術(shù)(Peano算術(shù))的形式系統(tǒng)中，存在這樣的命題，在該系統(tǒng)中，既不能證明該命題為真，也不能證明它為假。這就是著名的哥德爾不完全第一定理[1]。哥德爾不完全定理否定了Hilbert計(jì)劃，從而人們開始關(guān)注問題的可解與不可解。

實(shí)際上，問題的可解是相對(duì)的，不可解是絕對(duì)的。意思是指:問題的可解性依賴于形式規(guī)則，沒有通用的規(guī)則系統(tǒng)求解一切問題?；蛘哒f，給定的形式規(guī)則系統(tǒng)下，都存在不可解問題。例如:僅用直尺和圓規(guī)不能三等分任一個(gè)角[5，6]。但是，如果適當(dāng)修改規(guī)則是可以做到的[6]。

一個(gè)問題(命題)是可判定的，是指存在一臺(tái)圖靈機(jī)判定它是真還是假。哥德爾不完全定理解釋了不可判定問題的存在性。在可計(jì)算性理論中，由通用圖靈機(jī)的存在性，借助康托(Cantor)對(duì)角線方法，證明了著名的停機(jī)問題是不可解問題[1-4]。以此為種子，利用歸約技術(shù)，構(gòu)造了許多不可判定問題，其中包括著名的Hilbert第十問題(整系數(shù)多項(xiàng)式是否有整數(shù)根)[3，4]。

一個(gè)問題(命題)是半可判定的，是指存在一臺(tái)圖靈機(jī)，如果該問題為真命題，則機(jī)器在有限步內(nèi)停機(jī)并輸出“真”；如果命題為假，則機(jī)器可能不停機(jī)。在可計(jì)算性理論中，允許機(jī)器計(jì)算不停機(jī)(從而無輸出)。

計(jì)算復(fù)雜性理論只考慮可判定問題的計(jì)算時(shí)間和空間復(fù)雜性，由于空間可重復(fù)使用，而時(shí)間是不能重復(fù)的。因此，復(fù)雜性理論中，重點(diǎn)研究時(shí)間復(fù)雜性。

在可判定問題的計(jì)算復(fù)雜性研究中，P類和NP類是兩個(gè)核心研究對(duì)象[7，8]。NP類以外的問題統(tǒng)稱為NP難問題。

一個(gè)可判定問題在P類中(簡(jiǎn)稱P-問題)，如果存在一臺(tái)確定型圖靈機(jī)，在多項(xiàng)式時(shí)間內(nèi)停機(jī)，并輸出結(jié)果。一個(gè)可判定問題在NP類中(簡(jiǎn)稱NP-問題)，如果存在一臺(tái)非確定型圖靈機(jī)，在多項(xiàng)式時(shí)間內(nèi)停機(jī)，并輸出結(jié)果。顯然P類是NP類的一個(gè)子類。著名的“P與NP問題”是指:P是否等于NP。該問題至今是計(jì)算機(jī)科學(xué)中尚未解決的問題。

1 經(jīng)典有效計(jì)算下看大數(shù)據(jù)計(jì)算

在計(jì)算復(fù)雜性理論和算法設(shè)計(jì)中，一般認(rèn)為:如果一個(gè)問題有多項(xiàng)式時(shí)間算法求解，就認(rèn)為該問題是易解的(tractable)。這里多項(xiàng)式時(shí)間是指:相對(duì)于輸入問題實(shí)例的規(guī)模大小n，算法能在多項(xiàng)式p(n)時(shí)間內(nèi)停機(jī)，并有結(jié)果輸出。

多項(xiàng)式時(shí)間的算法被認(rèn)為是“有效”算法。但是，這里對(duì)n的大小卻沒有計(jì)較，也不考慮輸入的結(jié)構(gòu)!

在大數(shù)據(jù)計(jì)算中，輸入實(shí)例的規(guī)模大小n和結(jié)構(gòu)表示變成了主要問題。從算法的角度講，無論是什么樣的算法，總要閱讀完輸入實(shí)例。問題就在這里:如果實(shí)例的規(guī)模大小n很大，實(shí)例的結(jié)構(gòu)很復(fù)雜，這勢(shì)必給計(jì)算帶來了額外的開銷。

按1個(gè)字節(jié)(Byte)具有8位(bit)，(1千字節(jié)) 1 KB＝1024 B，(1兆字節(jié))1 MB＝1024 KB，(1千兆字節(jié))1 GB＝1024 MB，(1太字節(jié))1 TB＝1024 GB，(1拍字節(jié))1 PB＝1024 TB，(1艾字節(jié)) 1 EB＝1024 PB。按這樣的1024級(jí)指數(shù)遞增，1 EB＝9.2234e+18位?？梢钥闯?，數(shù)據(jù)的描述開銷是驚人的。

在經(jīng)典的計(jì)算復(fù)雜性中，數(shù)據(jù)的度量單位是以“位”為單位。計(jì)算對(duì)象的0、1碼字符串長(zhǎng)度n作為計(jì)算對(duì)象的規(guī)模大小。大數(shù)據(jù)如果以PB級(jí)計(jì)量，由前面的換算關(guān)系，1 PB 具有 n＝8796093022208位。因此，對(duì)于大數(shù)據(jù)的計(jì)算，除了要考慮算法本身的計(jì)算復(fù)雜性外，更大的挑戰(zhàn)要考慮數(shù)據(jù)本身的描述復(fù)雜性，簡(jiǎn)稱數(shù)據(jù)復(fù)雜性。如果將問題限制在多項(xiàng)式算法的可解類(即P類)，對(duì)于大數(shù)據(jù)計(jì)算問題，主要的任務(wù)是將“壓縮”大數(shù)據(jù)到整個(gè)求解問題的時(shí)間能夠承認(rèn)的范圍內(nèi)。否則，理論上算法有效，但實(shí)際上無效。

在大數(shù)據(jù)計(jì)算中，數(shù)據(jù)的復(fù)雜性變成了主要問題!

大數(shù)據(jù)本身遠(yuǎn)比經(jīng)典的計(jì)算對(duì)象復(fù)雜，雖然至今沒有給出大數(shù)據(jù)的標(biāo)準(zhǔn)數(shù)學(xué)定義，但從公認(rèn)的表象上看具有如下4個(gè)特征(簡(jiǎn)稱4V特征):第一，數(shù)量(Volume)，即數(shù)據(jù)量巨大，從TB級(jí)別躍升到PB級(jí)別；第二，多樣性(Variety)，即數(shù)據(jù)類型繁多，結(jié)構(gòu)復(fù)雜，不僅包括傳統(tǒng)的結(jié)構(gòu)化數(shù)據(jù)，還包括來自互聯(lián)網(wǎng)的網(wǎng)絡(luò)日志、視頻、圖片、地理位置信息等非結(jié)構(gòu)化數(shù)據(jù)；第三，速度(Velocity)，即處理速度要求快，數(shù)據(jù)動(dòng)態(tài)變化大；第四，真實(shí)性(Veracity)，即追求高質(zhì)量的數(shù)據(jù)。

鑒于大數(shù)據(jù)的4V特征，我們得考慮如下基本問題:

(1)如何規(guī)定大數(shù)據(jù)可計(jì)算?

(2)如何處理量“大”的問題?

(3)如何處理“非結(jié)構(gòu)化”問題?

(4)如何處理動(dòng)態(tài)數(shù)據(jù)流的在線和離線計(jì)算問題?

(5)既要兼顧可計(jì)算，又要保證真實(shí)性，這一對(duì)矛盾如何處理?

當(dāng)然，單從計(jì)算上講，重點(diǎn)是在處理大數(shù)據(jù)的表示(數(shù)據(jù)結(jié)構(gòu))問題、以及對(duì)量的壓縮處理。對(duì)量的壓縮處理使得計(jì)算時(shí)間可承受，大數(shù)據(jù)的表示主要用于分析壓縮處理計(jì)算后的誤差承受。

從計(jì)算的角度看，經(jīng)典的問題求解形式上是設(shè)計(jì)一個(gè)算法，將需要求解的問題按一定的數(shù)據(jù)結(jié)構(gòu)進(jìn)行編碼后作為算法的輸入，算法的輸出作為問題的求解結(jié)果。

大數(shù)據(jù)計(jì)算問題與經(jīng)典算法形式上有所不同。粗略地說，大數(shù)據(jù)計(jì)算問題是依賴于一個(gè)外部信息源Q的計(jì)算。

需要求解的問題可以分為兩類:

目標(biāo)任務(wù)型:給定一個(gè)任務(wù)x，依賴數(shù)據(jù)集Q，尋求問題x的目標(biāo)對(duì)象y，或解決問題x的目標(biāo)方案。這類計(jì)算問題的目標(biāo)是:基于數(shù)據(jù)集Q，給定一個(gè)任務(wù)描述x，算法輸出任務(wù)x的目標(biāo)方案(或結(jié)果)y。如:數(shù)據(jù)庫查詢問題。

內(nèi)容認(rèn)知型:算法本身無任務(wù)輸入，僅依賴數(shù)據(jù)集Q，通過機(jī)器學(xué)習(xí)方式，在數(shù)據(jù)集中尋求知識(shí)和知識(shí)關(guān)聯(lián)。這類計(jì)算問題的目標(biāo)是:分析數(shù)據(jù)集Q的整體(或局部)數(shù)據(jù)關(guān)聯(lián)特征，以某種知識(shí)表示的方式給出數(shù)據(jù)集Q所蘊(yùn)含知識(shí)的抽象描述。

實(shí)際應(yīng)用中，大數(shù)據(jù)的計(jì)算并不是將整個(gè)數(shù)據(jù)集Q作為算法的輸入，在計(jì)算中只需要對(duì)Q進(jìn)行局部訪問。因此，這樣的Q實(shí)際上是算法的外部信息源。

一般，靜態(tài)的大數(shù)據(jù)的計(jì)算依賴于一個(gè)龐大的數(shù)據(jù)集Q。這個(gè)數(shù)據(jù)集Q可以是虛擬的(指:數(shù)據(jù)集邊緣用戶不需要知道，或無法知道。如:互聯(lián)網(wǎng)數(shù)據(jù)，云端數(shù)據(jù)等)，也可以是現(xiàn)實(shí)存在的(指:數(shù)據(jù)集邊緣用戶可知道。如:已知數(shù)據(jù)庫)；可以是當(dāng)?shù)氐?，也可以是異地?/p>

鑒于此，我們有理由引入一種帶Oracle的圖靈機(jī)作為大數(shù)據(jù)計(jì)算的計(jì)算模型。其中，Oracle譯文為“神諭”。意指:有一個(gè)超強(qiáng)的外部裝置在協(xié)助機(jī)器進(jìn)行計(jì)算。

本文研究大數(shù)據(jù)計(jì)算的基礎(chǔ)理論，分析了大數(shù)據(jù)計(jì)算的基本問題:

(1)大數(shù)據(jù)計(jì)算問題實(shí)質(zhì)上是“基于某個(gè)外部數(shù)據(jù)源Q”的計(jì)算問題；大數(shù)據(jù)分析問題是對(duì)“外部數(shù)據(jù)源Q”的認(rèn)知問題。

(2)經(jīng)典算法對(duì)輸入x只計(jì)大小n，不計(jì)算x的結(jié)構(gòu)，有效算法是指關(guān)于n的多項(xiàng)式時(shí)間算法，多項(xiàng)式時(shí)間可解問題類稱為P類。大數(shù)據(jù)計(jì)算中，算法的輸入x是任務(wù)的描述，x的大小n可能很大(如:指數(shù)級(jí))。因此，大數(shù)據(jù)可計(jì)算問題限制在P的子類中討論，P類以外的計(jì)算問題“大數(shù)據(jù)不可計(jì)算”。

(3)并行計(jì)算是大數(shù)據(jù)計(jì)算的自然選擇。從理論上講，作為并行計(jì)算模型的NC電路可以作為大數(shù)據(jù)可計(jì)算的計(jì)算模型，NC類作為P的一個(gè)子類。對(duì)數(shù)空間可計(jì)算類作為NC的子類，對(duì)數(shù)空間可計(jì)算函數(shù)作為NC歸約的轉(zhuǎn)換器。

(4)從實(shí)際計(jì)算和應(yīng)用選擇上講，將帶Oracle的圖靈機(jī)限制在對(duì)數(shù)空間可計(jì)算，對(duì)應(yīng)到帶外部信息源的并行算法。鑒于整個(gè)計(jì)算有效性的要求，外部數(shù)據(jù)源Q被假設(shè)為用一個(gè)對(duì)數(shù)空間可計(jì)算的遞歸函數(shù)枚舉。

本文引入的大數(shù)據(jù)可計(jì)算的計(jì)算模型是帶Oracle(外部信息源)的圖靈計(jì)算模型。其中要求: (a)圖靈機(jī)本身是對(duì)數(shù)空間可計(jì)算；(b)對(duì)外部信息源的訪問可以在對(duì)數(shù)空間可計(jì)算內(nèi)完成。即，對(duì)外部信息源集Q可以用一個(gè)對(duì)數(shù)空間可計(jì)算的遞歸函數(shù)枚舉。這種計(jì)算模型稱為“雙對(duì)數(shù)”計(jì)算圖靈計(jì)算模型。簡(jiǎn)稱為L(zhǎng)L-型圖靈計(jì)算模型。

2 大數(shù)據(jù)計(jì)算的基本問題

從數(shù)學(xué)的角度說，談到計(jì)算必須弄清楚兩個(gè)基本問題:一是計(jì)算對(duì)象，即對(duì)什么進(jìn)行計(jì)算?二是計(jì)算的任務(wù)，即計(jì)算的目的是什么?

大數(shù)據(jù)的計(jì)算是依賴于一個(gè)龐大的數(shù)據(jù)集Q，計(jì)算并非將整個(gè)數(shù)據(jù)集Q作為算法的輸入，在計(jì)算過程中只需要對(duì)Q進(jìn)行局部訪問。這樣的Q實(shí)際上是算法的外部信息源。因此，大數(shù)據(jù)計(jì)算本質(zhì)上歸類為帶外部信息源的計(jì)算問題類。

大數(shù)據(jù)指的是這個(gè)龐大的數(shù)據(jù)集Q，而不是一個(gè)單一的數(shù)據(jù)對(duì)象。早期的數(shù)據(jù)庫Q關(guān)注的是“存儲(chǔ)”、“查詢”、以及某些應(yīng)用統(tǒng)計(jì)。這里的Q一般是靜態(tài)的，或動(dòng)態(tài)變化(維護(hù))頻率不是那么高。

大數(shù)據(jù)計(jì)算問題與經(jīng)典算法形式上有所不同。一般，靜態(tài)的大數(shù)據(jù)的計(jì)算依賴于一個(gè)龐大的數(shù)據(jù)集Q。這個(gè)數(shù)據(jù)集Q可以是虛擬的，也可以是現(xiàn)實(shí)存在的；可以是當(dāng)?shù)氐?，也可以是異地?/p>

除了量的變化和數(shù)據(jù)元素的結(jié)構(gòu)類型上異構(gòu)以外，大數(shù)據(jù)計(jì)算更加注重:

(1)給定一個(gè)計(jì)算任務(wù)，依賴于數(shù)據(jù)集Q尋求問題的解(或解決方案)；

(2)數(shù)據(jù)集Q本身內(nèi)部蘊(yùn)藏的數(shù)據(jù)之間的關(guān)聯(lián)性所提供的額外信息(知識(shí))；

(3)數(shù)據(jù)集Q不再是“靜”的，這種動(dòng)態(tài)變化形成的數(shù)據(jù)流所提供的額外信息；

(4)面對(duì)數(shù)據(jù)量大和時(shí)間效率要求的矛盾沖突，尋求解決方案。

因此，我們將大數(shù)據(jù)計(jì)算歸為兩類:目標(biāo)任務(wù)型和內(nèi)容認(rèn)知型。

如果大數(shù)據(jù)按行業(yè)分類，目標(biāo)任務(wù)按應(yīng)用類型劃分，我們可以直觀用地用二維座標(biāo)表示:其中，橫座標(biāo)表示行業(yè)x，縱座標(biāo)表示任務(wù)y，交叉點(diǎn)代表(x，y)表示任務(wù)y基于數(shù)據(jù)集x的計(jì)算。

(1)用y＝0代表不帶任務(wù)輸入的計(jì)算。此時(shí)(x，0)表示對(duì)數(shù)據(jù)集x的內(nèi)部關(guān)聯(lián)結(jié)構(gòu)的分析和計(jì)算。

(2)對(duì)于固定的y，集合{(x1，y)，……，(xn，y)}代表任務(wù)y依賴于多個(gè)行業(yè)數(shù)據(jù)集x1，……，xn的計(jì)算。

(3)對(duì)于固定的x，集合{(x，y1)，……，(x，ym)}依賴于行業(yè)數(shù)據(jù)集x對(duì)多個(gè)任務(wù)y1，……，ym的計(jì)算。

(4)所謂塊數(shù)據(jù)計(jì)算是指:多個(gè)任務(wù)y1，……，ym依賴于多個(gè)行業(yè)數(shù)據(jù)集x1，……，xn的計(jì)算。有關(guān)塊數(shù)據(jù)的介紹，請(qǐng)參考文獻(xiàn)[9，10]。

我們需要注意的是:在大數(shù)據(jù)計(jì)算中，我們并不需要(也不可能)完全知道外部信息源Q。我們只需要知道面對(duì)給定任務(wù)x，如何去訪問Q，使之基于Q下，得到問題的解。另一類問題是從整體(或局部)分析Q能提供什么樣的關(guān)聯(lián)信息。

由于大數(shù)據(jù)的計(jì)算并不是將整個(gè)數(shù)據(jù)集Q作為算法的輸入，在計(jì)算中只需要對(duì)Q進(jìn)行局部訪問，這樣的Q它并不是算法規(guī)則部分。因此，我們稱其為算法的外部信息源。

我們認(rèn)為:大數(shù)據(jù)計(jì)算問題實(shí)質(zhì)上是“基于某個(gè)外部數(shù)據(jù)源Q”的計(jì)算問題；大數(shù)據(jù)分析問題是對(duì)“外部數(shù)據(jù)源Q”的認(rèn)知問題。

本文重點(diǎn)考慮前者的計(jì)算理論問題。

3 可計(jì)算性與計(jì)算復(fù)雜性基本概念

設(shè)Σ為一個(gè)有窮字母表(如:Σ＝{0，1})，用Σ?表示Σ上有窮字符串集合(含空串)。對(duì)于一個(gè)可有限描述的對(duì)象(如:自然數(shù)，有理數(shù)等)，在某種編碼方式下，可以用Σ?中的元素編碼表示?；谕ǔD靈計(jì)算模型引入的能行計(jì)算理論只能處理Σ?上串函數(shù)的可計(jì)算性，由此建立了自然數(shù)集上能行計(jì)算理論——遞歸論[1，2]。

形式上，一個(gè)函數(shù)f:Σ?→Σ?是可計(jì)算函數(shù)，如果存在一臺(tái)圖靈機(jī)M，對(duì)于任意一個(gè)輸入x∈Σ?，在有限步內(nèi)，機(jī)器M輸出函數(shù)值y＝f(x)。Σ?的一個(gè)子集A稱為一個(gè)語言，A的特征函數(shù)χA: Σ?→{0，1}定義為χA(x)＝1?x∈Σ?。一個(gè)語言A(作為集合)對(duì)應(yīng)一個(gè)判定問題:對(duì)任意給定的x∈Σ?，判定x是否在A中?因此，稱一個(gè)判定問題是可判定的(或稱可解的)，如果函數(shù) χA: Σ?→{0，1}是一個(gè)可計(jì)算函數(shù)。這等價(jià)于:存在一臺(tái)圖靈機(jī)M計(jì)算χA。直觀上，存在一個(gè)算法，對(duì)任意一個(gè)輸入x∈Σ?，在有限步內(nèi)給出判定結(jié)果(Yes/No)。例如，整系數(shù)線性方程組是否有整數(shù)解是一個(gè)可判定問題。因?yàn)橐粋€(gè)整系數(shù)線性方程組可以有限編碼成一個(gè)0、1串，將有解整系數(shù)線性方程組對(duì)應(yīng)的編碼串構(gòu)成集合A。因此，對(duì)于任意一個(gè)輸入x∈Σ?，如果x不是某個(gè)整系數(shù)線性方程組的編碼，則直接回答No；如果是，則解碼還原出該整系數(shù)線性方程組，然后利用消元法(或其它方法)求解，最終可以確定該方程是否有整數(shù)解。如果有解，則回答Yes，否則回答No.可以看出，上述過程在有限步內(nèi)能完成。

在具體判定問題的描述過程中，可以不考慮編碼、解碼，并且將程序用算法替代。例如，整系數(shù)線性方程組判定問題可以描述為:是否存在一個(gè)算法，判定任意給定的一個(gè)整系數(shù)線性方程組是否有整數(shù)解?如果有整數(shù)解，算法輸出Yes，否則輸出No。

著名的停機(jī)問題是指:是否存在一個(gè)算法A，判定“對(duì)于任意給定的一個(gè)算法B及一個(gè)輸入x，B對(duì)x的計(jì)算在有限步內(nèi)是否停止?”由引言中的陳述，停機(jī)問題是不可判定問題。即，這樣的算法A不存在。

計(jì)算復(fù)雜性理論只研究可判定問題。即對(duì)于可判定問題，只對(duì)判定算法的時(shí)間和空間復(fù)雜進(jìn)行研究。從分類上看，主要研究P類，NP類，NP難類。

對(duì)于Σ?的一個(gè)子集A，規(guī)定一個(gè)問題。對(duì)于x∈Σ?，用x的串長(zhǎng)度|x|度量x的規(guī)模大小。

一臺(tái)確定型圖靈機(jī)M稱為多項(xiàng)式時(shí)間圖靈機(jī)，如果存在一個(gè)多項(xiàng)式p:N→N，對(duì)任意的x∈Σ?，M關(guān)于x的計(jì)算，在p(|x|)時(shí)間步內(nèi)停機(jī)并有輸出。這里N是自然數(shù)集。圖靈機(jī)的確定型是指機(jī)器只帶一個(gè)變遷函數(shù)，由上一步到下一步的計(jì)算由此變遷函數(shù)唯一確定，計(jì)算過程是唯一路徑。非確定型圖靈機(jī)所帶的變遷函數(shù)有兩個(gè)，上一步到下一步的計(jì)算選擇其中一個(gè)變遷函數(shù)決定，所有計(jì)算可能的過程展開表現(xiàn)為一棵樹，從樹根到葉的一條路徑代表一種計(jì)算可能，只要有一種計(jì)算完成對(duì)x的計(jì)算，則稱對(duì)x可計(jì)算。

從現(xiàn)在開始，我們所指的問題都是可判定問題，重點(diǎn)關(guān)注計(jì)算時(shí)間。

一個(gè)問題A在P類中(記為A∈P)，如果存在一臺(tái)多項(xiàng)式時(shí)間圖靈機(jī)M計(jì)算A的特征函數(shù)。一個(gè)問題A在NP類中(A∈NP)，如果存在一臺(tái)非確定型圖靈機(jī)，在多項(xiàng)式時(shí)間內(nèi)停機(jī)，并輸出結(jié)果。問題A在NP類中等價(jià)定義是:存在一臺(tái)帶兩個(gè)串變量的多項(xiàng)式時(shí)間圖靈機(jī)M(x，y)、以及一個(gè)應(yīng)該證據(jù)長(zhǎng)度控制多項(xiàng)式q(m)，使得:對(duì)任意的x∈Σ?，x∈A?(?y∈{0，1}q(|x|))(M(x，y)＝ 1)。其中y稱為支持x∈A的證據(jù)，且證據(jù)y的長(zhǎng)度受一個(gè)多項(xiàng)式q控制，M稱為驗(yàn)證機(jī)。

多項(xiàng)式歸約是經(jīng)典計(jì)算復(fù)雜性理論中作為問題轉(zhuǎn)換分析的一種重要而基礎(chǔ)的技術(shù)。問題A可以多項(xiàng)式歸約問題B(記為A≤PB)是指:存在一個(gè)多項(xiàng)式時(shí)間可計(jì)算的轉(zhuǎn)換函數(shù)f:Σ?→Σ?，滿足關(guān)系:對(duì)任意的x∈Σ?，x∈A?f(x)∈B。直觀上，判定x是否在A中，可以先將x在多項(xiàng)式時(shí)間內(nèi)轉(zhuǎn)換為y＝f(x)，則用y是否在B中來回答x是否在A中。

顯然，我們有這樣的關(guān)系:如果A≤PB，并且B∈P，則A∈P。

例如1:路徑問題PATH是一個(gè)P問題。所謂路徑問題是指:給定一個(gè)圖G，以及兩個(gè)結(jié)點(diǎn)s，t，判定在圖G中是否有一條從s到t的路徑。

例如2:歐拉(Euler)問題是P問題。即判定一個(gè)無向圖是否為Euler圖是多項(xiàng)式時(shí)間可以判定的。因?yàn)橛蓤D論知識(shí)知道，一個(gè)無向圖G是Euler圖的充分必要條件是圖G連通，并且每個(gè)結(jié)點(diǎn)的度數(shù)為偶數(shù)[11]。這兩個(gè)條件的驗(yàn)證可以在多項(xiàng)式時(shí)間內(nèi)完成，其中以圖G中的結(jié)點(diǎn)數(shù)n度量G的大小。

一個(gè)問題B稱為NP-難的，如果對(duì)于任意的A∈NP，有A≤PB。一個(gè)問題B稱為NP-完全的(簡(jiǎn)稱NPC問題)，如果B是NP-難的，并且B∈NP。

合取范式公式的可滿足問題簡(jiǎn)稱可滿足性(SAT)問題，自Cook證明著名的SAT問題是NPC問題以來，以此為種子，發(fā)現(xiàn)很多NPC問題。如，哈密爾頓(Hamilton)問題是NPC問題[3]。(注: Hamilton問題是判定一個(gè)無向圖是否為Hamilton圖?)

對(duì)于大數(shù)據(jù)計(jì)算問題，一個(gè)自然假設(shè)是在“有效”時(shí)間內(nèi)可計(jì)算。如果用多項(xiàng)式時(shí)間刻畫“有效”，那么，對(duì)于大數(shù)據(jù)可計(jì)算問題自然限制在P類問題中討論。

另一方面，對(duì)于NPC或NP難以上的可判定問題，在計(jì)算復(fù)雜性中，處理有效性的辦法是尋求近似算法。近似算法主要對(duì)付求優(yōu)問題中的NP難類，近似算法本身自然要求是多項(xiàng)式時(shí)間算法，刻畫近似算法的優(yōu)劣是靠算法的近似度。即，問題本身的最優(yōu)解的代價(jià)函數(shù)與近似算法產(chǎn)生的解的代價(jià)函數(shù)之間的比值界[12]。

因此，我們可以對(duì)判定問題作如下簡(jiǎn)單分類[13]:

判定問題:分為可判定與不可判定；

可判定問題:分為NP難以上問題(簡(jiǎn)稱難解問題)與多項(xiàng)式時(shí)間可解問題(簡(jiǎn)稱易解問題，對(duì)應(yīng)P類問題)；

難解問題:分為可近似問題與不可近似問題[7，8，12]；

可見，對(duì)于大數(shù)據(jù)計(jì)算問題，基于算法本身多項(xiàng)式時(shí)間的要求，我們只能考慮如下兩個(gè)類中的大數(shù)據(jù)可計(jì)算與不可計(jì)算問題:一類是P類，另一類是可近似問題類。

以下，我們重點(diǎn)討論P(yáng)類中大數(shù)據(jù)的可計(jì)算與不可計(jì)算問題。

對(duì)數(shù)空間可計(jì)算在本文中是一個(gè)基本假設(shè)。對(duì)數(shù)空間可計(jì)算類涵蓋有效并行可計(jì)算類，它是P類的一個(gè)子類。

4 對(duì)數(shù)空間復(fù)雜類與對(duì)數(shù)空間歸約

度量一個(gè)算法的計(jì)算代價(jià)從時(shí)間復(fù)雜性和空間復(fù)雜性加以考慮。在上一節(jié)中，我們簡(jiǎn)單介紹了時(shí)間復(fù)雜性的一些基本概念。對(duì)于時(shí)間復(fù)雜性，時(shí)間是不可重用的，“確定”與“非確定”有本質(zhì)區(qū)別，因此才有P與NP問題的討論。

在圖靈計(jì)算模型中，“空間”計(jì)量為計(jì)算過程中所用到的工作磁帶上的方格數(shù)，在隨機(jī)存取計(jì)算模型(RAM)中，用計(jì)算過程中所用到的寄存器數(shù)計(jì)量。

對(duì)于空間復(fù)雜性而言，由于空間是可重復(fù)使用，“確定”與“非確定”對(duì)于多項(xiàng)式的限制顯得不重要。薩維奇(Savitch)定理告訴我們[3，7，8]:用非確定性圖靈機(jī)判定的問題可以用一臺(tái)確定型圖靈機(jī)來完成，其空間代價(jià)級(jí)別只差一個(gè)平方關(guān)系。因此，如果限制在多項(xiàng)式空間下分類，“確定”與“非確定”沒有本質(zhì)區(qū)別。

基于上述理由，我們考慮對(duì)數(shù)空間復(fù)雜類[7，8]。

一個(gè)問題A在對(duì)數(shù)空間L＝Space(log(n))類中(記為A∈L)，如果存在一臺(tái)對(duì)數(shù)空間確定型圖靈機(jī)M計(jì)算A的特征函數(shù)。即，對(duì)于任意的x∈Σ?，機(jī)器M在計(jì)算過程中，其工作帶上至多用到O(log|x|)個(gè)方格數(shù)。類似地，一個(gè)問題A在NL＝NSpace(log(n))類中(記為A∈NL)，如果存在一臺(tái)對(duì)數(shù)空間非確定型圖靈機(jī)M計(jì)算A的特征函數(shù)?？梢宰C明:NL類是P的一個(gè)子類。

對(duì)數(shù)空間足以求解許多有趣計(jì)算問題，而且其數(shù)學(xué)性質(zhì)具有豐富的吸引力。如:當(dāng)機(jī)器模型和輸入的編碼方法改變時(shí)保持穩(wěn)健性。此外，指向輸入的指針可以在對(duì)數(shù)空間內(nèi)表示，所以考慮對(duì)數(shù)空間算法計(jì)算能力的一種方式是考慮固定數(shù)目的輸入指針的計(jì)算能力[4]。

限制在對(duì)數(shù)空間可計(jì)算，類似引入對(duì)數(shù)空間歸約[3，7]:

問題A可以對(duì)數(shù)空間歸約問題B記為(A≤LB)，是指:存在一個(gè)對(duì)數(shù)空間可計(jì)算的轉(zhuǎn)換函數(shù)f: Σ?→Σ?，滿足關(guān)系:對(duì)任意的x∈Σ?，x∈A?f(x)∈B。

可以想象一個(gè)對(duì)數(shù)空間轉(zhuǎn)換器M是這樣的一臺(tái)圖靈機(jī):它帶有一條只讀輸入帶，一條只寫輸出帶，一條工作帶。將x放在輸入帶上，機(jī)器計(jì)算的結(jié)果寫入輸出帶。設(shè)n＝|x|，計(jì)算過程只用到工作帶上O(log(n))個(gè)方格。

同樣，如果A≤LB，并且B∈L，則A∈L。類似可以定義NL完全。一個(gè)問題B稱為NL-完全的，簡(jiǎn)稱為NLC問題，如果B∈NL，并且對(duì)于任意的A∈NL，有A≤LB。

在文獻(xiàn)[3]中己經(jīng)證明:路徑問題PATH是NLC問題。一個(gè)自然的推論是NL?P。即，NL類是P的一個(gè)子類。

注意:多項(xiàng)式歸約與對(duì)數(shù)空間歸約不一樣?？梢宰C明:A≤LB?A≤pB(因此得到NL?P)。反之不一定成立。

我們?cè)?jīng)假設(shè):在大數(shù)據(jù)計(jì)算中只考慮P類問題。現(xiàn)在考慮以布爾電路作為計(jì)算模型下P的子類。

5 多項(xiàng)式時(shí)間產(chǎn)生的一致電路族與P語言類的關(guān)系

我們現(xiàn)在考慮布爾電路作為計(jì)算模型下P類問題的另一個(gè)可計(jì)算特征。本節(jié)的主要概念和結(jié)論來自于文獻(xiàn)[7]。

定義5.1(布爾電路) 對(duì)于任意給定的n，一個(gè)具有n-輸入，單輸出的布爾電路C是帶有n個(gè)源點(diǎn)(sources)、1個(gè)沉點(diǎn)(sink)的有向無環(huán)圖。所有的其它非源點(diǎn)稱為門(gates)，并以三種邏輯運(yùn)算符∨，∧，?之一分別標(biāo)記每一個(gè)非源點(diǎn)，分別對(duì)應(yīng)邏輯或、邏輯與，邏輯非運(yùn)算，其中∨，∧的扇入為2，?的扇入為1。

電路C的規(guī)模大小以它所含的結(jié)點(diǎn)數(shù)定義，記為|C|。如果C為一個(gè)電路，x∈{0，1}n是一個(gè)輸入，則C關(guān)于x的輸出記為C(x)。

注意:對(duì)∨，∧的扇入量的無界和有界限制，對(duì)計(jì)算復(fù)雜性計(jì)量有本質(zhì)差異。本文只考慮有界扇入。

定義5.2(電路族與語言識(shí)別) 設(shè)T:N→N是一個(gè)規(guī)?？刂坪瘮?shù)，一個(gè)T(n)-規(guī)模的電路族是一列布爾電路{Cn}n∈N，其中Cn帶有n個(gè)輸入和一個(gè)輸出，并且|Cn|≤T(n)。

一個(gè)語言A∈SIZE(T(n))(可判定語言類)，如果存在一個(gè)T(n)-規(guī)模的電路族{Cn}n∈N，使得對(duì)于任意的x∈{0，1}n，x∈A?Cn(x)＝1。

直觀上，不同長(zhǎng)度的輸入調(diào)用不同電路，同一長(zhǎng)度的不同輸入利用同一個(gè)電路Cn，且電路規(guī)模受一個(gè)函數(shù)控制(|Cn|≤T(n))。自然，T(n)取不同的函數(shù)類(如:n的多項(xiàng)式)就可以定義不同語言類。

自然想到，這樣的電路族{Cn}n∈N能否用一臺(tái)加工機(jī)器一致地統(tǒng)一加工生成。

定義5.3(多項(xiàng)式一致生成電路族，P-一致電路族)

一個(gè)電路族{Cn}n∈N稱為多項(xiàng)式一致的，簡(jiǎn)稱P -一致，如果存在一臺(tái)多項(xiàng)式時(shí)間圖靈機(jī)M，對(duì)于每一個(gè)給定的自然數(shù)n，以串1n作為M的輸入，機(jī)器M輸出Cn的描述編碼(即用機(jī)器M生產(chǎn)布爾電路)。

注:通過適當(dāng)?shù)木幋a機(jī)制，一個(gè)電路Cn可以用0、1串編碼，稱為Cn的描述編碼，記為 ＜Cn＞。定理5.4[7]一個(gè)語言A由一個(gè)P-一致電路族{Cn}n∈N可計(jì)算當(dāng)且僅當(dāng)A∈P(即A在P類中)。

在大數(shù)據(jù)計(jì)算中，并行計(jì)算是一種常見處理方式。我們現(xiàn)在考慮與并行計(jì)算相關(guān)聯(lián)的問題類。

6 NC類與并行算法

我們現(xiàn)在開始觸及到與大數(shù)據(jù)計(jì)算緊密相聯(lián)的計(jì)算模型和問題類。將并行計(jì)算與布爾電路相關(guān)聯(lián)。類似于定義樹的高度，一個(gè)電路C的深度(記為depth(C))，是指從輸入結(jié)點(diǎn)到輸出結(jié)點(diǎn)的最長(zhǎng)有向路徑的長(zhǎng)度。

定義6.1(NC類) 對(duì)于一個(gè)自然數(shù)d，一個(gè)語言A在NCd類中，如果A可以由一個(gè)電路族{Cn}n∈N判定，其中Cn的規(guī)模受n的一個(gè)多項(xiàng)式界(即存在某個(gè)自然類k，|Cn|＝O(nk))，并且depth(Cn)＝O(logd(n))。

定義語言類NC＝∪d≥1NCd。一個(gè)語言A∈NC是指:存在一個(gè)自然數(shù)d，A∈NCd。

類似地，我們可以定義一致的NCd類，但對(duì)應(yīng)的是對(duì)數(shù)空間一致性:一個(gè)電路族{Cn}n∈N稱為對(duì)數(shù)空間一致的(簡(jiǎn)稱Log S一致)，如果存在一臺(tái)對(duì)數(shù)空間圖靈機(jī)M及一個(gè)自然數(shù)d，對(duì)于每一個(gè)給定的自然數(shù)n，以串1n作為M的輸入，機(jī)器M輸出Cn的描述編碼。其中，Cn的規(guī)模受n的一個(gè)多項(xiàng)式界，并且depth(Cn)＝O(logd(n))。

更一般地，一個(gè)Log S-一致的NC電路是指:一臺(tái)對(duì)數(shù)空間圖靈機(jī)M，輸入串1m＝1＜n，k，d＞，機(jī)器M輸出 Cn的描述編碼，其中 |Cn|＝O(nk)，depth(Cn)＝O(logd(n))，這里m＝＜n，k，d＞為三個(gè)自然數(shù)n，k，d的編碼。有關(guān)自然數(shù)組編碼為一個(gè)整數(shù)、一個(gè)整數(shù)解碼為一個(gè)給定維數(shù)的自然數(shù)組的編碼和解碼函數(shù)，參見文獻(xiàn)[1]。

我們有類似于定理5.4的結(jié)論。

定理6.1 一個(gè)語言A由一個(gè)LogS-一致電路族{Cn}n∈N可計(jì)算，當(dāng)且僅當(dāng)A∈NC。

基于此，可以仿定義5.1定義一個(gè)并行計(jì)算模型:

一個(gè)帶有n個(gè)輸入節(jié)點(diǎn)的并行計(jì)算機(jī)是由O(nk)節(jié)點(diǎn)組成的有向網(wǎng)絡(luò)圖N，每個(gè)非源節(jié)點(diǎn)對(duì)應(yīng)一個(gè)處理器(一個(gè)處理器可以視為具有常數(shù)界的小型布爾子電路)，每個(gè)處理器只有常數(shù)個(gè)扇入，除沉點(diǎn)外的每個(gè)處理器的輸出端連接到另一個(gè)處理器的輸入端，對(duì)某個(gè)自然數(shù)d，depth(N)＝O(logd(n))。

我們有如下結(jié)論:

定理6.2[7]一個(gè)語言A可以由一個(gè)有效并行算法判定，當(dāng)且僅當(dāng)A在NC類中。

一個(gè)語言B是P-完全的，簡(jiǎn)稱PC語言，如果B在P語言類中，并且對(duì)于任意的P語言A，A≤LB(對(duì)數(shù)空間歸約)。

由于一個(gè)對(duì)數(shù)空間可計(jì)算的函數(shù)f:Σ?→{0，1}可以由一個(gè)Log S-一致的NC電路模擬計(jì)算。因此，計(jì)算對(duì)數(shù)空間歸約又稱為NC歸約。記為A≤NCB。

NC電路形式上是具有多項(xiàng)式級(jí)個(gè)數(shù)的并行處理器，對(duì)數(shù)多項(xiàng)式級(jí)的深度，深度刻畫了并行機(jī)的計(jì)算步數(shù)(作為時(shí)間復(fù)雜性)。因此，NC語言類是P的一個(gè)子類。

大數(shù)據(jù)計(jì)算離不開并行計(jì)算。因此，NC機(jī)可以作為大數(shù)據(jù)計(jì)算的一個(gè)基本模型。

但是，實(shí)際計(jì)算中，并行處理器的個(gè)數(shù)是一個(gè)常數(shù)c，即使除去計(jì)算過程中的通信時(shí)間代價(jià)，c臺(tái)處理器的并行計(jì)算系統(tǒng)比串行計(jì)算至多提高常數(shù)倍效率。

基于這樣的分析，我們認(rèn)為:大數(shù)據(jù)計(jì)算的核心問題是數(shù)據(jù)復(fù)雜性。如何處理數(shù)據(jù)體量大、結(jié)構(gòu)復(fù)雜的問題才是至關(guān)重要的環(huán)節(jié)。

7 帶外部信息源的圖靈計(jì)算模型

經(jīng)典的問題求解形式上是設(shè)計(jì)一個(gè)算法，將需要求解的問題按一定的數(shù)據(jù)結(jié)構(gòu)進(jìn)行編碼后作為算法的輸入，算法的輸出作為問題的求解結(jié)果。

在第一節(jié)中，我們對(duì)大數(shù)據(jù)計(jì)算的基本問題作過簡(jiǎn)要介紹。對(duì)于大數(shù)據(jù)計(jì)算問題，需要求解的問題可以分為兩類:任務(wù)型和認(rèn)知型。

大數(shù)據(jù)的計(jì)算是數(shù)據(jù)集Q作為算法的外部信息源。

鑒于此，我們有理由引入一種帶Oracle的圖靈機(jī)作為大數(shù)據(jù)計(jì)算的計(jì)算模型。其中，Oracle譯文為“神諭”。意指:有一個(gè)超強(qiáng)的外部裝置在協(xié)助機(jī)器進(jìn)行計(jì)算。

形式上，帶Oracle的圖靈機(jī)可由一臺(tái)圖靈機(jī)M改造:

(1)在圖靈機(jī)M上增加一條磁帶(稱為Oracle帶)，將外部信息B置放在Oracle帶上；

(2)在圖靈機(jī)M中允許使用“詢問”狀態(tài)，當(dāng)計(jì)算進(jìn)入詢問狀態(tài)時(shí)，機(jī)器向外部信息源B詢問形如“y∈B?”這樣的問題，機(jī)器根據(jù)給出的回答結(jié)果1(Yes)或0(No)進(jìn)入下一步計(jì)算。

改造后的圖靈機(jī)稱為帶Oracle的圖靈機(jī)。

具體一點(diǎn)，如果B被固化在機(jī)器上，這樣的機(jī)器記為MB。注意:B的位置是可以用其它集合替換的。好比一臺(tái)計(jì)算機(jī)外掛一個(gè)數(shù)據(jù)庫，機(jī)器在計(jì)算時(shí)可以訪問數(shù)據(jù)庫。

顯然，在實(shí)際計(jì)算中，對(duì)于具體的計(jì)算任務(wù)x，我們并不需要整個(gè)數(shù)據(jù)庫參與計(jì)算，只需要訪問數(shù)據(jù)庫，根據(jù)訪問結(jié)果參與計(jì)算。計(jì)算過程中，我們只需要訪問方法和地址計(jì)算就可以完成計(jì)算。

不難理解，這類機(jī)器的能力與如下兩個(gè)因素密切相關(guān):

(1)所帶的Oracle B；

(2)計(jì)算過程中詢問次數(shù)控制。

在經(jīng)典的帶Oracle圖靈機(jī)的計(jì)算復(fù)雜性中，一次詢問“y∈B?”只計(jì)一個(gè)單位時(shí)間。然而，在大數(shù)據(jù)計(jì)算中，這才是真正耗費(fèi)時(shí)間的地方!

因此，如果將大數(shù)據(jù)計(jì)算問題類限制在P類(多項(xiàng)式時(shí)間類)中討論，詢問次數(shù)自然是多項(xiàng)式界的。對(duì)詢問“y∈B?”的計(jì)算時(shí)間度量才是真正要考慮的主要問題。

對(duì)于大數(shù)據(jù)計(jì)算問題，目標(biāo)放在對(duì)外部信息源Q的訪問和如何訪問上。

基本方法和思路:

(1)假想存在一個(gè)映射f，將外部信息源Q映射到一個(gè)壓縮空間Q'；

(2)設(shè)計(jì)訪問Q'的方法和計(jì)算訪問地址；

(3)評(píng)價(jià)訪問代價(jià)和誤差代價(jià)；

(4)評(píng)價(jià)算法的可靠性。

對(duì)于外部信息源Q如何映射到一個(gè)壓縮空間Q'，稀疏表示和特征提取是一種有效途徑。原因在于:大數(shù)據(jù)中真正能為目標(biāo)任務(wù)服務(wù)的部分所占比例非常低。如:在壓縮感知識(shí)中，圖像數(shù)據(jù)在Fourier變換下，較大值座標(biāo)系數(shù)所占比例不到5%[14]。

這里，我們?cè)俅沃厣?大數(shù)據(jù)是指外部信息源Q。因此，大數(shù)據(jù)計(jì)算問題實(shí)質(zhì)上是“基于某個(gè)數(shù)據(jù)源Q”計(jì)算問題。

8 大數(shù)據(jù)的稀疏表示與特征提取

大數(shù)據(jù)計(jì)算對(duì)象數(shù)字化編碼后表現(xiàn)為一個(gè)高維向量x，壓縮表示形式上是一個(gè)函數(shù)f:Rn→Rk，其目的是將高維空間中的對(duì)象映射到低維空間，通過映像在研究低維空間中的關(guān)系、特征、性質(zhì)等，去推斷原始對(duì)象在高維空間中的關(guān)系、特征和性質(zhì)。

一個(gè)n維向量是稀疏的，如果它的分量中非零元個(gè)數(shù)相對(duì)于n而言非常小。如:只有O(log(n))個(gè)非零元。具體地說，一個(gè)高維向量稱為k-稀疏的，如果它的非零分量個(gè)數(shù)不超過 k個(gè)，其中k＜＜n。稀疏向量通常用于近似表示高維向量，直觀上是高維向量的特征提取。

對(duì)于一個(gè)n維向量x→，可以引入不同范數(shù)‖x→‖，常用的范數(shù)有如下幾類:

假定A為m×n矩陣(m＜＜n)，b為m維非零向量。如果方程Ax＝b有解，則必為非零解。直觀上，矩陣A定義一個(gè)線性算子A:Rn→Rm(Ax＝y(tǒng))，對(duì)于b∈Rm，b的一個(gè)原像x稱為b的一個(gè)表示。如果‖x‖0≤m+O(1)，則稱x為b的一個(gè)稀疏表示。

對(duì)于矩陣A，定義Spark(A)為滿足齊次線性方程組Ax＝0非零解中最小l0-范數(shù)值，即

Spark(A)＝min{‖x‖0:Ax＝0，x≠0}。

其實(shí)，Spark(A)為A中列向量最小線性相關(guān)向量集的大小。事實(shí)上，設(shè)A＝(A1，……，An)，如果{Ai1，……，Aik}為A中列向量最小線性相關(guān)向量集，由線性相關(guān)性，存在一組不全為0的數(shù)c1，……，ck，使c1Ai1+……+ckAik＝0。由最小性，c1，……，ck均不為0。由c1，……，ck可以生成Ax＝0的一個(gè)解c，且‖c‖0＝k。

容易驗(yàn)證:如果A為一個(gè)m×n矩陣A(m＜＜n)，則Spark(A)≤m+1。事實(shí)上，設(shè)A＝(A1，……，An)，A中列向量集中任意m+1個(gè)向量必定線性相關(guān)。從而，Spark(A)≤m+1。

定理8.1 對(duì)于給定的A，b，假定x為b的一個(gè)稀疏表示，且‖x‖0＜，則x為b的唯一稀疏表示。

事實(shí)上，假定存在兩個(gè)b的一個(gè)稀疏表示X1，X2(X1≠X2)，則A(X1-X2)＝AX1-AX2＝0。但是，‖X1-X2‖0≤‖X1‖0+‖X2‖0＜Spark(A)。此與最小性矛盾。

定理8.2 設(shè)A為一個(gè)m×n矩陣A(m＜＜n)，b為一個(gè)m維向量，如果存在b的表示，則必有稀疏表示存在。

證明:假定b的表示存在，即，方程Ax＝b有解。從而，Rank(A，b)＝Rank(A)≤m。于是，A中任意m列向量與b構(gòu)成的向量集必線性相關(guān)。設(shè)A＝(A1，……，An)，不妨假定A1，……，Am，b線性相關(guān)，則必有m+1個(gè)不全為0的數(shù)c1，……，cm，cm+1使c1A1+…… +cmAm+cm+1b＝0。

進(jìn)一步，由Rank(A，b)＝Rank(A)，可以假定cm+1≠0，再由b為非零向量，c1，……，cm中至少有一個(gè)不為0。于是，取(c1，……，cm，0，.....， 0)，x為b的一個(gè)表示，且x為b的一個(gè)稀疏表示。

注:定理8.2提供了一個(gè)尋找稀疏表示的一種方法。

定理8.3 設(shè)A為一個(gè)m×n矩陣A(m＜＜n)，b為一個(gè)m維向量，如果Rank(A)＝m，則存在b的稀疏表示。

證明:設(shè)Rank(A)＝m，則m維向量集中(A1，……，An)有 m個(gè)向量線性無關(guān)。不妨設(shè) (A1，……，Am)線性無關(guān)，則(A1，……，Am，b)必定線性相關(guān)，并且b可由(A1，……，Am)線性表示。即，方程Bx＝b有非零解c，其中B＝(A1，……，Am)。由c生成b的一個(gè)解x，且‖x‖0≤m。從而x為b的一個(gè)稀疏表示。

經(jīng)典的稀疏向量的求優(yōu)問題有三兩類:

稀疏問題(Sparse Problem)(簡(jiǎn)稱SP問題): min‖x‖0subject to Ax＝b。

基追蹤(Basis Pursuit)(簡(jiǎn)稱BP問題):

min‖x‖1subject to Ax＝b。

Lasso問題:

min‖Ax-b‖1subject to‖x‖1＜λ。

SP問題是一個(gè)NP難問題，有關(guān)稀疏表示的基礎(chǔ)理論和應(yīng)用，請(qǐng)參見文獻(xiàn)[14，15]。

大數(shù)據(jù)滿足稀疏表示的假設(shè):利用少量分量足以表示(或近似表示)原始對(duì)象。如何獲取這部分少量的“有用”分量具有很多成熟的方法。如:統(tǒng)計(jì)學(xué)習(xí)方法[16]，深度學(xué)習(xí)方法[17]等。

大數(shù)據(jù)特征提取的目標(biāo)是想用少量數(shù)據(jù)表達(dá)復(fù)雜數(shù)據(jù)，數(shù)據(jù)挖掘則是尋求數(shù)據(jù)間的特征關(guān)聯(lián)性。無論出于什么樣的目的，都是在為計(jì)算和分析提供小數(shù)據(jù)表達(dá)。

大數(shù)據(jù)計(jì)算的前期預(yù)處理必須解決如下兩個(gè)基本問題:

(1)數(shù)據(jù)從“大”到“小”的預(yù)處理；

(2)數(shù)據(jù)的“非結(jié)構(gòu)”到“結(jié)構(gòu)”的預(yù)處理。

對(duì)于問題(2)主要是給出一種規(guī)范的數(shù)字編碼技術(shù)。從計(jì)算的角度而言，主要針對(duì)問題(1)。

因此，大數(shù)據(jù)可計(jì)算的核心問題是:如何將數(shù)據(jù)從“大”到“小”進(jìn)行處理，使得算法在時(shí)間上可承受，而又不丟失原始數(shù)據(jù)所表達(dá)的信息。

定義8.4 設(shè)x為一個(gè)n維向量，0＜ε＜1，k＜＜n，如果‖x-x'‖p≤ε，x'是一個(gè)k-稀疏的n維向量，則稱x'是在p-范數(shù)下x的(k，ε)-稀疏。

一個(gè)n維向量x在p-范數(shù)下可以(k，ε)-稀疏的，如果存在一個(gè)k-稀疏的n維向量x'，使得‖x-x'‖p≤ε。

特別，取p＝2，簡(jiǎn)稱向量x是可以(k，ε)-稀疏的。更進(jìn)一步，如果k＝O(logi(n))(對(duì)某個(gè)正整數(shù)i)，ε是某個(gè)約定的充分小的數(shù)。我們簡(jiǎn)稱x是可對(duì)數(shù)稀疏的。

定義8.5 設(shè)Q為一個(gè)n維向量的數(shù)據(jù)集，如果Q中任一個(gè)向量都是可對(duì)數(shù)稀疏的，則稱Q是可對(duì)數(shù)稀疏的。

有關(guān)高維數(shù)據(jù)處理與分析的理論和方法，請(qǐng)參見文獻(xiàn)[18]。

9 大數(shù)據(jù)的可計(jì)算性

我們現(xiàn)在開始觸及大數(shù)據(jù)的可計(jì)算性問題，并回答什么才叫大數(shù)據(jù)可計(jì)算?

從計(jì)算理論的角度，可計(jì)算性依賴于一個(gè)給定的計(jì)算模型。由于我們己經(jīng)界定大數(shù)據(jù)的可計(jì)算限制在P類中討論。因此，大數(shù)據(jù)的可計(jì)算性還與復(fù)雜類選擇相關(guān)。

基于前面幾節(jié)中對(duì)大數(shù)據(jù)計(jì)算的特點(diǎn)討論。我們引入“帶Oracle的圖靈機(jī)，對(duì)數(shù)空間可計(jì)算”作為大數(shù)據(jù)的計(jì)算模型。

本節(jié)從引入任務(wù)型大數(shù)據(jù)計(jì)算的概念出發(fā)，引入大數(shù)據(jù)可計(jì)算和大數(shù)據(jù)可判定問題。直觀上，我們要求對(duì)外部信息源Q(Q?Σ?)的訪問必須滿足兩個(gè)條件:

(1)對(duì)Q的訪問是能行的。

(2)對(duì)Q的訪問能在對(duì)數(shù)空間可計(jì)算內(nèi)完成。

為此，對(duì)于條件(1)，假定Q是一個(gè)遞歸可枚舉集[1]，即有一個(gè)遞歸函數(shù)q(·)枚舉Q中的元素；對(duì)于條件(2)，還要求枚舉函數(shù)q(·)在對(duì)數(shù)空間內(nèi)可計(jì)算。

我們稱滿足條件(1)(2)的外部信息源Q為對(duì)數(shù)空間可枚舉集。記為:LogS.r.e.集。

本節(jié)的Q均假設(shè)為L(zhǎng)ogS.r.e.集。

定義9.1 設(shè)Q(Q?Σ?)為一個(gè)LogS.r.e.數(shù)據(jù)集，x∈Σ?(|x|＝n)，如果存在一臺(tái)帶Oracle的圖靈機(jī)M，以Q作為Oracle(外部信息源)附著在M上，以x為輸入，機(jī)器MQ在n的對(duì)數(shù)空間內(nèi)能夠完成對(duì)x的計(jì)算，則稱任務(wù)型實(shí)例 ＜Q，x＞大數(shù)據(jù)可計(jì)算。簡(jiǎn)稱 ＜Q，x＞為BD可計(jì)算。

基于定義9.1，對(duì)一個(gè)任務(wù)描述x，可以引入“對(duì)x的大數(shù)據(jù)可計(jì)算”概念如下:

定義9.2 設(shè)x∈Σ?，如果存在一個(gè)LogS.r.e.數(shù)據(jù)集Q?Σ?，使得 ＜Q，x＞BD可計(jì)算，則稱x大數(shù)據(jù)可計(jì)算。簡(jiǎn)稱x為BD可計(jì)算。

基于定義9.2中BD可計(jì)算概念，對(duì)一個(gè)任務(wù)集A，引入“對(duì)A的大數(shù)據(jù)可計(jì)算”概念。

定義9.3 設(shè)A?Σ?為一個(gè)語言(用于描述一個(gè)任務(wù)集)，如果對(duì)任意的x∈A，x大數(shù)據(jù)可計(jì)算，則稱A大數(shù)據(jù)可計(jì)算。

請(qǐng)注意，在定義9.3中，不同的x可能關(guān)聯(lián)調(diào)用不同的外部信息源Q，也有可能啟用不同的圖靈機(jī)M。為此，我們引入如下一致計(jì)算概念。

定義9.4(外部信息源一致的大數(shù)據(jù)可計(jì)算) 設(shè)A?Σ?為一個(gè)語言(用于描述一個(gè)任務(wù)集)，Q?Σ?為一個(gè)LogS.r.e.數(shù)據(jù)集，如果對(duì)任意的x∈A，＜Q，x＞大數(shù)據(jù)可計(jì)算，則稱A關(guān)于外部信息源Q是一致大數(shù)據(jù)可計(jì)算。簡(jiǎn)稱A是Q一致大數(shù)據(jù)可計(jì)算。

此隱含:即使外部信息源Q是公用的，但不同的x還有可能調(diào)用不同的機(jī)器M(算法，軟件)。

進(jìn)一步，我們引入一個(gè)更強(qiáng)的一致性。不但關(guān)于外部信息源一致，而且要求關(guān)于機(jī)器M(算法，軟件)一致。

定義9.5(一致的大數(shù)據(jù)可計(jì)算) 設(shè)A?Σ?為一個(gè)語言(用于描述一個(gè)任務(wù)集)，如果存在一個(gè)公共的LogS.r.e.數(shù)據(jù)集Q，以及一臺(tái)帶Oracle的圖靈機(jī)M，使得對(duì)任意的x∈A，＜Q，x＞在公共圖靈機(jī)M下大數(shù)據(jù)可計(jì)算，則稱A是一致的大數(shù)據(jù)可計(jì)算。

至此，我們可以引入大數(shù)據(jù)可判定問題。

一個(gè)函數(shù)f:Σ?→Σ?是大數(shù)據(jù)可計(jì)算函數(shù)，如果存在一臺(tái)帶Oracle的圖靈機(jī)M，以及一個(gè)LogS. r.e.外部信息源Q，對(duì)于任意一個(gè)輸入x∈Σ?，機(jī)器MQ在對(duì)數(shù)空間內(nèi)對(duì)x進(jìn)行計(jì)算，并輸出函數(shù)值y＝f(x)。特別注意:這里的對(duì)數(shù)空間只計(jì)圖靈機(jī)的工作帶上的空間。

定義9.6(大數(shù)據(jù)可判定問題) 設(shè)A?Σ?為一個(gè)語言(對(duì)應(yīng)一個(gè)判定問題)，如果其特征函數(shù)χA: Σ?→{0，1}是大數(shù)據(jù)可計(jì)算函數(shù)，則稱語言A是大數(shù)據(jù)可判定的。

換言之，如果存在一臺(tái)公共的帶Oracle的圖靈機(jī)M和一個(gè)公共的對(duì)數(shù)空間可枚舉的外部信息源Q，機(jī)器MQ在對(duì)數(shù)空間內(nèi)對(duì)x進(jìn)行計(jì)算，并對(duì)x是否在A中作出回答。

在本文中，我們以“對(duì)數(shù)空間可計(jì)算的帶Oracle的圖靈機(jī)”作為模型給出了大數(shù)據(jù)可計(jì)算和大數(shù)據(jù)可判定概念。

在實(shí)際應(yīng)用中，為處理輸入端的描述、以及對(duì)外部信息源的訪問計(jì)算，可以對(duì)圖靈機(jī)加以改造、變形，以適應(yīng)實(shí)際問題的解決。如:概率計(jì)算模型(BPP機(jī)，RP機(jī))，概率可驗(yàn)證模型PCP機(jī)計(jì)算模型等，對(duì)其加以“對(duì)數(shù)空間計(jì)算”的限制，都可以得到應(yīng)用。有興趣的讀者可以參見文獻(xiàn)[7，8]。

此外，可以將對(duì)數(shù)空間可枚舉的外部信息源Q區(qū)分為靜態(tài)數(shù)據(jù)源和動(dòng)態(tài)數(shù)據(jù)流，考慮大數(shù)據(jù)的離線計(jì)算和在線計(jì)算等問題。

10 結(jié)語

本文從計(jì)算理論的角度討論了大數(shù)據(jù)計(jì)算的某些基礎(chǔ)理論問題。大數(shù)據(jù)計(jì)算遠(yuǎn)比經(jīng)典計(jì)算復(fù)雜，在經(jīng)典計(jì)算中，重點(diǎn)是在研究算法及其時(shí)間復(fù)雜性，對(duì)前端輸入的數(shù)據(jù)復(fù)雜性不做分析，而大數(shù)據(jù)計(jì)算中，前端輸入的數(shù)據(jù)復(fù)雜性反而成為大數(shù)據(jù)計(jì)算的主要問題。

追加數(shù)據(jù)復(fù)雜性帶來的額外時(shí)間開銷，考慮整個(gè)算法時(shí)間上的承認(rèn)能力，大數(shù)據(jù)計(jì)算限制在經(jīng)典計(jì)算復(fù)雜性意義下的多項(xiàng)式時(shí)間復(fù)雜類中考慮。對(duì)數(shù)空間復(fù)雜類作為成為多項(xiàng)式時(shí)間復(fù)雜類的一個(gè)重要子類，它涵蓋了并行計(jì)算復(fù)雜類，從而大數(shù)據(jù)計(jì)算體現(xiàn)的并行計(jì)算要求自然也在其中。

大數(shù)據(jù)計(jì)算問題實(shí)質(zhì)上是依賴于一個(gè)對(duì)數(shù)空間可枚舉(LogS.r.e.)外部信息源Q的計(jì)算，我們將需要求解的問題分為兩類:目標(biāo)任務(wù)型和內(nèi)容認(rèn)知型。本文重點(diǎn)討論了前者，并引入了大數(shù)據(jù)可計(jì)算概念:基于帶外部數(shù)據(jù)源，并在對(duì)數(shù)空間內(nèi)的圖靈可計(jì)算。

本文引入的大數(shù)據(jù)可計(jì)算的計(jì)算模型是帶Oracle(外部信息源)的圖靈計(jì)算模型。其中要求:

(1)圖靈機(jī)本身是對(duì)數(shù)空間可計(jì)算；

(2)對(duì)外部信息源的訪問可以在對(duì)數(shù)空間可計(jì)算內(nèi)完成。形式上，外部信息源集Q可以用一個(gè)對(duì)數(shù)空間可計(jì)算的遞歸函數(shù)枚舉。

這種計(jì)算模型稱為“雙對(duì)數(shù)”圖靈計(jì)算模型，簡(jiǎn)稱為L(zhǎng)L-型圖靈計(jì)算模型。

基于大數(shù)據(jù)可計(jì)算的基本概念，我們引入了大數(shù)據(jù)可計(jì)算性和大數(shù)據(jù)可判定問題。當(dāng)然，更多的工作還需要更深入細(xì)致的研究，特別是“指數(shù)級(jí)壓縮、對(duì)數(shù)級(jí)算法”方面的具體算法的設(shè)計(jì)與分析是我們下一步的努力方向，部分?jǐn)?shù)學(xué)工具可能會(huì)用到量子計(jì)算的理論和方法[19，20]。

[1]N Cutland.Computability——An Introduction to Recursive Function Theory[M].Cambridge:Cambridge University Press，1980.

[2]R ISoare.Recursively Enumerable Sets and Degrees——A Study of Computable Functions and Computably Generated Sets[M].Berlin Heidelberg:Springer-Verlag，1987.

[3]M Sipser.可計(jì)算理論導(dǎo)引[M].張立昂，等譯.北京:機(jī)械工業(yè)出版社，2000.

[4]M Davis.可計(jì)算性與不可計(jì)算性[M].沈泓，等譯.北京:北京大學(xué)出版社，1984.

[5]E Artin.Galois理論[M].李同孚，譯.哈爾濱:哈爾濱工業(yè)大學(xué)出版社，2011.

[6]R柯朗，H羅賓.什么是數(shù)學(xué)(第三版)[M].左平，等譯.上海:復(fù)旦大學(xué)出版社，2012.

[7]S Arora，B Barak.Computational Complexity——A Modern Approach[M].Cambridge:Cambridge University Press，2009.

[8]堵丁柱，葛可一，王浩.計(jì)算機(jī)復(fù)雜性導(dǎo)論[M].北京:高等教育出版社，2002.

[9]連玉明.塊數(shù)據(jù)[M].北京:中信出版集團(tuán)，2015.

[10]連玉明.塊數(shù)據(jù)2.0[M].北京:中信出版集團(tuán)，2016.

[11]耿素云，屈婉玲.離散數(shù)學(xué)[M].北京:高等教育出版社，2004.

[12]D PWilliamson，D B Shmoys.The Design of Approximation Algorithms[M].Cambridge:Cambridge University Press，2011.

[13]陳國良，陸克中，毛睿.大數(shù)據(jù)計(jì)算理論基礎(chǔ)(PPT報(bào)告) [EB/OL].http://wenku.baidu.com，2014.

[14]SFoucart，H Rauhut.AMathematical Introduction to Compressive Sensing[M].Heidelberg，Dordrecht London:Springer New York，2010.

[15]徐勇，范自柱，張大鵬.基于稀疏算法的人臉表示[M].北京:國防工業(yè)出版社，2014.

[16]T Hastie，R Tibshirani，JFriedman.統(tǒng)計(jì)學(xué)習(xí)基礎(chǔ)[M].范明，等譯.北京:電子工業(yè)出版社，2007.

[17]IGoodfellow，Y Bengio，A Courville.Deep Learning[EB/OL]. http://www.deeplarningbook.org.

[18]JHopcroft，R Kannan.Computer Science Theory for the Information Age[M].上海:上海交通大學(xué)出版社，2013.

[19]M A Nielsen，IL Chuang.量子信息與量子信息[M].趙千川，譯.北京:清華大學(xué)出版社，2004.

[20]李士勇，李盼池.量子計(jì)算與量子優(yōu)化算法[M].哈爾濱:哈爾濱工業(yè)大學(xué)出版社，2009.

(責(zé)任編輯:周曉南)

Investigation of Basic Theory in Big-Data Computations

XU Daoyun?

(College of Computer Science and Technology，Key Lab of Public Big Data of Guizhou Province，Guizhou University，Guiyang 550025，China)

In classical computations，it don'tneed to analyze the data complexity of inputs in algorithms，butanalyzing data complexity of inputs in big-data computations becomes key problems.Some basic theories of big-data computationswere investigated，and computations were classified into objective-task and context-recognition types.The big-data computations depend formally on some external information sources.For effectiveness of computations，restrict complexity of big-data computations was restricted to classes of computable problems in logspace，which contains the class of parallel computations.The computationmodel，big-data computability and decidability were introduced based on Turingmachine with oracles in log-space，where the information sources as oracle is a recursive enumerable set that is computable in log-space.

big-data computation；computability in log-space；parallel computability；turingmachine with oracles；computability for big-data

O171

A

1000-5269(2016)04-0001-11

10.15958/j.cnki.gdxbzrb.2016.04.01

2016-06-08

國家自然科學(xué)基金項(xiàng)目資助(61262006)

許道云(1959-)，男，教授，博士生導(dǎo)師，研究方向:可計(jì)算性與計(jì)算復(fù)雜性，分析中的可計(jì)算性，算法設(shè)計(jì)與分析，Email:dyxu＠gzu.edu.cn.

?通訊作者:許道云，Email:dyxu＠gzu.edu.cn.