http://dahua.spaces.live.com/blog/cns!28AF4251DF30CA42!2489.entry

7月9日

Learning中的代數(shù)結(jié)構(gòu)的建立

Learning是一個融會多種數(shù)學(xué)于一體的領(lǐng)域。說起與此有關(guān)的數(shù)學(xué)學(xué)科，我們可能會迅速聯(lián)想到線性代數(shù)以及建立在向量空間基礎(chǔ)上的統(tǒng)計(jì)模型——事實(shí)上，主流的論文中確實(shí)在很大程度上基于它們。

R^n (n-維實(shí)向量空間) 是我們在paper中見到最多的空間，它確實(shí)非常重要和實(shí)用，但是，僅僅依靠它來描述我們的世界并不足夠。事實(shí)上，數(shù)學(xué)家們給我們提供了豐富得多的工具。

“空間”(space)，這是一個很有意思的名詞，幾乎出現(xiàn)在所有的數(shù)學(xué)分支的基礎(chǔ)定義之中。歸納起來，所謂空間就是指一個集合以及在上面定義的某種數(shù)學(xué)結(jié)構(gòu)。關(guān)于這個數(shù)學(xué)結(jié)構(gòu)的定義或者公理，就成為這個數(shù)學(xué)分支的基礎(chǔ)，一切由此而展開。

還是從我們最熟悉的空間——R^n 說起吧。大家平常使用這個空間的時候，除了線性運(yùn)算，其實(shí)還用到了別的數(shù)學(xué)結(jié)構(gòu)，包括度量結(jié)構(gòu)和內(nèi)積結(jié)構(gòu)。

第 一，它是一個拓?fù)淇臻g(Topological space)。而且從拓?fù)鋵W(xué)的角度看，具有非常優(yōu)良的性質(zhì)：Normal (implying Hausdorff and Regular), Locally Compact, Paracompact, with Countable basis, Simply connected (implying connected and path connected), Metrizable. 

第二，它是一個度量空間(Metric space)。我們可以計(jì)算上面任意兩點(diǎn)的距離。

第三，它是一個有限維向量空間(Finite dimensional space)。因此，我們可以對里面的元素進(jìn)行代數(shù)運(yùn)算（加法和數(shù)乘），我們還可以賦予它一組有限的基，從而可以用有限維坐標(biāo)表達(dá)每個元素。

第四，基于度量結(jié)構(gòu)和線性運(yùn)算結(jié)構(gòu)，可以建立起分析(Analysis)體系。我們可以對連續(xù)函數(shù)進(jìn)行微分，積分，建立和求解微分方程，以及進(jìn)行傅立葉變換和小波分析。

第 五，它是一個希爾伯特空間（也就是完備的內(nèi)積空間）(Hilbert space, Complete inner product space)。它有一套很方便計(jì)算的內(nèi)積(inner product)結(jié)構(gòu)——這個空間的度量結(jié)構(gòu)其實(shí)就是從其內(nèi)積結(jié)構(gòu)誘導(dǎo)出來。更重要的，它是完備的(Complete)——代表任何一個柯西序列 (Cauchy sequence)都有極限——很多人有意無意中其實(shí)用到了這個特性，不過習(xí)慣性地認(rèn)為是理所當(dāng)然了。

第六，它上面的線性映射構(gòu)成的算子空間仍舊是有限維的——一個非常重要的好處就是，所有的線性映射都可以用矩陣唯一表示。特別的，因?yàn)樗怯邢蘧S完備空間，它的泛函空間和它本身是同構(gòu)的，也是R^n。因而，它們的譜結(jié)構(gòu)，也就可以通過矩陣的特征值和特征向量獲得。

第七，它是一個測度空間——可以計(jì)算子集的大小（面積/體積）。正因?yàn)榇耍覀儾趴赡茉谏厦娼⒏怕史植?distribution)——這是我們接觸的絕大多數(shù)連續(xù)統(tǒng)計(jì)模型的基礎(chǔ)。

我 們可以看到，這是一個非常完美的空間，為我們的應(yīng)用在數(shù)學(xué)上提供了一切的方便，在上面，我們可以理所當(dāng)然地認(rèn)為它具有我們希望的各種良好性質(zhì)，而無須特別 的證明；我們可以直接使用它的各種運(yùn)算結(jié)構(gòu)，而不需要從頭建立；而且很多本來不一樣的概念在這里變成等價(jià)的了，我們因此不再需要辨明它們的區(qū)別。

以此為界，Learning的主要工作分成兩個大的范疇：

1. 建立一種表達(dá)形式，讓它處于上面討論的R^n空間里面。
2. 獲得了有限維向量表達(dá)后，建立各種代數(shù)算法或者統(tǒng)計(jì)模型進(jìn)行分析和處理。

這里只討論第一個范疇。先看看，目前用得比較廣泛的一些方法：

1. 直 接基于原始數(shù)據(jù)建立表達(dá)。我們關(guān)心的最終目標(biāo)是一個個現(xiàn)實(shí)世界中的對象：一幅圖片，一段語音，一篇文章，一條交易記錄，等等。這些東西大部分本身沒有附著 一個數(shù)值向量的。為了構(gòu)造一個向量表達(dá)，我們可以把傳感器中記錄的數(shù)值，或者別的什么方式收集的數(shù)值數(shù)據(jù)按照一定的順序羅列出來，就形成一個向量了。如果 有n個數(shù)字，就認(rèn)為它們在R^n里面。

不過，這在數(shù)學(xué)上有一點(diǎn)小問題，在大部分情況下，根據(jù)數(shù)據(jù)產(chǎn)生的物理原理，這些向量的值域并不能 充滿整個空間。比如圖像的像素值一般是正值，而且在一個有界閉集之中。這帶來的問題是，對它們進(jìn)行線性運(yùn)算很可能得到的結(jié)果會溢出正常的范圍——在大部分 paper中，可能只是采用某些heuristics的手段進(jìn)行簡單處理，或者根本不管，很少見到在數(shù)學(xué)上對此進(jìn)行深入探討的——不過如果能解決實(shí)際問 題，這也是無可厚非的，畢竟不是所有的工作都需要像純數(shù)學(xué)那樣追求嚴(yán)謹(jǐn)。

2. 量化(quantization)。這是 在處理連續(xù)信號時被廣泛采用的方式。只是習(xí)以為常，一般不提名字而已。比如一個空間信號（Vision中的image）或者時間信號，它們的domain 中的值是不可數(shù)無限大的(uncountably infinite)，不要說表示為有限維向量，即使表達(dá)為無限序列也是不可能的。在這種情況下，一般在有限域內(nèi)，按照一定順序每隔一定距離取一個點(diǎn)來代表 其周圍的點(diǎn)，從而形成有限維的表達(dá)。這就是信號在時域或空域的量化。

這樣做不可避免要丟失信息。但是，由于小鄰域內(nèi)信號的高度相關(guān)，信息丟失的程度往往并不顯著。而且，從理論上說，這相當(dāng)于在頻域中的低通過率。對于有限能量的連續(xù)信號，不可能在無限高的頻域中依然保持足夠的強(qiáng)度，只要采樣密度足夠，丟失的東西可以任意的少。

除了表示信號，對于幾何形體的表達(dá)也經(jīng)常使用量化，比如表示curve和surface。

3. 找 出有限個數(shù)充分表達(dá)一個對象也許不是最困難的。不過,在其上面建立數(shù)學(xué)結(jié)構(gòu)卻未必了。一般來說，我們要對其進(jìn)行處理，首先需要一個拓?fù)浣Y(jié)構(gòu)用以描述空間上 的點(diǎn)是如何聯(lián)系在一起。直接建立拓?fù)浣Y(jié)構(gòu)在數(shù)學(xué)上往往非常困難，也未必實(shí)用。因此，絕大部分工作采取的方式是首先建立度量結(jié)構(gòu)。一個度量空間，其度量會自 然地誘導(dǎo)出一個拓?fù)浣Y(jié)構(gòu)——不過，很多情況下我們似乎會無視它的存在。

最簡單的情況，就是使用原始向量表達(dá)的歐氏距離 (Euclidean distance)作為metric。不過，由于原始表達(dá)數(shù)值的不同特性，這種方式效果一般不是特別好，未必能有效表達(dá)實(shí)際對象的相似性（或者不相似 性）。因此，很多工作會有再此基礎(chǔ)上進(jìn)行度量的二次建立。方式是多種多樣的，一種是尋求一個映射，把原空間的元素變換到一個新的空間，在那里歐氏距離變得 更加合適。這個映射發(fā)揮的作用包括對信息進(jìn)行篩選，整合，對某些部分進(jìn)行加強(qiáng)或者抑制。這就是大部分關(guān)于feature selection，feature extraction，或者subspace learning的文章所要做的。另外一種方式，就是直接調(diào)節(jié)距離的計(jì)算方式（有些文章稱之為metric learning）。

這兩種方式未必是不同的。如果映射是單射，那么它相當(dāng)于在原空間建立了一個不同的度量。反過來，通過改變距離計(jì)算方式建立的度量在特定的條件下對應(yīng)于某種映射。

4. 大 家可能注意到，上面提到的度量建立方法，比如歐氏距離，它需要對元素進(jìn)行代數(shù)運(yùn)算。對于普通的向量空間，線性運(yùn)算是天然賦予的，我們無須專門建立，所以可 以直接進(jìn)行度量的構(gòu)造——這也是大部分工作的基礎(chǔ)。可是，有些事物其原始表達(dá)不是一個n-tuple，它可能是一個set，一個graph，或者別的什么 特別的object。怎么建立代數(shù)運(yùn)算呢？

一種方法是直接建立。就是給這些東西定義自己的加法和數(shù)乘。這往往不是那么直接（能很容易建 立的線性運(yùn)算結(jié)構(gòu)早已經(jīng)被建立好并廣泛應(yīng)用了），可能需要涉及很深的數(shù)學(xué)知識，并且要有對問題本身的深入了解和數(shù)學(xué)上的洞察力。不過，一個新的代數(shù)結(jié)構(gòu)一 旦建立起來，其它的數(shù)學(xué)結(jié)構(gòu)，包括拓?fù)洌攘浚治觯约皟?nèi)積結(jié)構(gòu)也隨之能被自然地誘導(dǎo)出來，我們也就具有了對這個對象空間進(jìn)行各種數(shù)學(xué)運(yùn)算和操作的基 礎(chǔ)。加法和數(shù)乘看上去簡單，但是如果我們對于本來不知道如何進(jìn)行加法和數(shù)乘的空間建立了這兩樣?xùn)|西，其理論上的貢獻(xiàn)是非常大的。

（一個 小問題：大家常用各種graphical model，但是，每次這些model都是分別formulate，然后推導(dǎo)出estimation和evaluation的步驟方法。是否可能 對"the space of graphical model"或者它的某個特定子集建立某種代數(shù)結(jié)構(gòu)呢？（不一定是線性空間，比如群，環(huán)，廣群， etc）從而使得它們在代數(shù)意義上統(tǒng)一起來，而相應(yīng)的estimation或者evaluation也可以用過代數(shù)運(yùn)算derive。這不是我的研究范 圍，也超出了我目前的能力和知識水平，只是我相信它在理論上的重要意義，留作一個遠(yuǎn)景的問題。事實(shí)上，數(shù)學(xué)中確實(shí)有一個分支叫做 Algebraic statistics 可能在探討類似的問題，不過我現(xiàn)在對此了解非常有限。）

5. 回到我們的正題，除了直接建立運(yùn)算 定義，另外一種方式就是嵌入(embedding)到某個向量空間，從而繼承其運(yùn)算結(jié)構(gòu)為我所用。當(dāng)然這種嵌入也不是亂來，它需要保持原來這些對象的某種 關(guān)系。最常見的就是保距嵌入(isometric embedding)，我們首先建立度量結(jié)構(gòu)（繞過向量表達(dá)，直接對兩個對象的距離通過某種方法進(jìn)行計(jì)算），然后把這個空間嵌入到目標(biāo)空間，通常是有限維 向量空間，要求保持度量不變。

“嵌入”是一種在數(shù)學(xué)上應(yīng)用廣泛的手段，其主要目標(biāo)就是通過嵌入到一個屬性良好，結(jié)構(gòu)豐富的空間，從而利 用其某種結(jié)構(gòu)或者運(yùn)算體系。在拓?fù)鋵W(xué)中，嵌入到metric space是對某個拓?fù)淇臻g建立度量的重要手段。而在這里，我們是已有度量的情況下，通過嵌入獲取線性運(yùn)算的結(jié)構(gòu)。除此以來，還有一種就是前些年比較熱的 manifold embedding，這個是通過保持局部結(jié)構(gòu)的嵌入，獲取全局結(jié)構(gòu)，后面還會提到。

6. 接下來的一 個重要的代數(shù)結(jié)構(gòu)，就是內(nèi)積(inner product)結(jié)構(gòu)。內(nèi)積結(jié)構(gòu)一旦建立，會直接誘導(dǎo)出一種性質(zhì)良好的度量，就是范數(shù)(norm)，并且進(jìn)而誘導(dǎo)出拓?fù)浣Y(jié)構(gòu)。一般來說，內(nèi)積需要建立在線 性空間的基礎(chǔ)上，否則連一個二元運(yùn)算是否是內(nèi)積都無法驗(yàn)證。不過，kernel理論指出，對于一個空間，只要定義一個正定核(positive kernel)——一個符合正定條件的二元運(yùn)算，就必然存在一個希爾伯特空間，其內(nèi)積運(yùn)算等效于核運(yùn)算。這個結(jié)論的重要意義在于，我們可以繞開線性空間， 通過首先定義kernel的方式，誘導(dǎo)出一個線性空間(叫做再生核希爾伯特空間 Reproducing Kernel Hilbert Space)，從而我們就自然獲得我們所需要的度量結(jié)構(gòu)和線性運(yùn)算結(jié)構(gòu)。這是kernel theory的基礎(chǔ)。

在很多教科書中，以二 次核為例子，把二維空間變成三維，然后告訴大家kernel用于升維。對于這種說法，我一直認(rèn)為在一定程度上是誤導(dǎo)的。事實(shí)上，kernel的最首要意義 是內(nèi)積的建立（或者改造），從而誘導(dǎo)出更利于表達(dá)的度量和運(yùn)算結(jié)構(gòu)。對于一個問題而言，選擇一個切合問題的kernel比起關(guān)注“升維”來得更為重要。

kernel被視為非線性化的重要手段，用于處理非高斯的數(shù)據(jù)分布。這是有道理的。通過nonlinear kernel改造的內(nèi)積空間，其結(jié)構(gòu)和原空間的結(jié)構(gòu)確實(shí)不是線性關(guān)聯(lián)，從這個意義上說，它實(shí)施了非線性化。不過，我們還應(yīng)該明白，它的最終目標(biāo)還是要回到 線性空間，新的內(nèi)積空間仍舊是一個線性空間，它一旦建立，其后的運(yùn)算都是線性的，因此，kernel的使用就是為了尋求一個新的線性空間，使得線性運(yùn)算更 加合理——非線性化的改造最終仍舊是要為線性運(yùn)算服務(wù)。

值得一提的是，kernelization本質(zhì)上說還是一種嵌入過程：對于一個空間先建立內(nèi)積結(jié)構(gòu)，并且以保持內(nèi)積結(jié)構(gòu)不變的方式嵌入到一個高維的線性空間，從而繼承其線性運(yùn)算體系。

7. 上 面說到的都是從全局的方式建立代數(shù)結(jié)構(gòu)的過程，但是那必須以某種全局結(jié)構(gòu)為基礎(chǔ)（無論預(yù)先定義的是運(yùn)算，度量還是內(nèi)積，都必須適用于全空間。）但是，全局 結(jié)構(gòu)未必存在或者適合，而局部結(jié)構(gòu)往往簡單方便得多。這里就形成一種策略，以局部而達(dá)全局——這就是流形(manifold)的思想，而其則根源于拓?fù)?學(xué)。

從拓?fù)鋵W(xué)的角度說，流形就是一個非常優(yōu)良的拓?fù)淇臻g：符合Hausdorff分離公理（任何不同的兩點(diǎn)都可以通過不相交的鄰域分 離），符合第二可數(shù)公理（具有可數(shù)的拓?fù)浠⑶腋匾氖牵植客哂赗^n。因此，一個正則(Regular)流形基本就具有了各種最良好的拓?fù)涮?性。而局部同胚于R^n，代表了它至少在局部上可以繼承R^n的各種結(jié)構(gòu)，比如線性運(yùn)算和內(nèi)積，從而建立分析體系。事實(shí)上，拓?fù)淞餍卫^承這些結(jié)構(gòu)后形成的 體系，正是現(xiàn)代流形理論研究的重點(diǎn)。繼承了分析體系的流形，就形成了微分流形(Differential manifold)，這是現(xiàn)代微分幾何的核心。而微分流形各點(diǎn)上的切空間(Tangent Space)，則獲得了線性運(yùn)算的體系。而進(jìn)一步繼承了局部內(nèi)積結(jié)構(gòu)的流形，則形成黎曼流形(Riemann manifold)，而流形的全局度量體系——測地距離(geodesics)正是通過對局部度量的延伸來獲得。進(jìn)一步的，當(dāng)流行本身的拓?fù)浣Y(jié)構(gòu)和切空間 上的線性結(jié)構(gòu)發(fā)生關(guān)系——也就獲得一簇拓?fù)潢P(guān)聯(lián)的線性空間——向量叢(Vector bundle)。

雖然manifold theory作為現(xiàn)代幾何學(xué)的核心，是一個博大精深的領(lǐng)域，但是它在learning中的應(yīng)用則顯得非常狹窄。事實(shí)上，對于manifold，很多做 learning的朋友首先反應(yīng)的是ISOMAP, LLE, eigenmap之類的算法。這些都屬于embedding。當(dāng)然，這確實(shí)是流形理論的一個重要方面。嚴(yán)格來說，這要求是從原空間到其映像的微分同胚映 射，因此，嵌入后的空間在局部上具有相同的分析結(jié)構(gòu)，同時也獲得了各種好處——全局的線性運(yùn)算和度量。不過，這個概念在learning的應(yīng)用中被相當(dāng)程 度的放寬了——微分同胚并不能被完全保證，而整個分析結(jié)構(gòu)也不能被完全保持。大家更關(guān)注的是保持局部結(jié)構(gòu)中的某個方面——不過這在實(shí)際應(yīng)用中的折衷方案也 是可以理解的。事實(shí)表明，當(dāng)原空間中的數(shù)據(jù)足夠密集的情況下，這些算法工作良好。

Learning中流形應(yīng)用的真正問題在于它被過濫地 運(yùn)用于稀疏空間(Sparse space)，事實(shí)上在高維空間中撒進(jìn)去幾千乃至幾十萬點(diǎn)，即使最相鄰的幾點(diǎn)也難稱為局部了，局部的范圍和全局的范圍其實(shí)已經(jīng)沒有了根本差別，連局部的概 念都立不住腳的時候，后面基于其展開的一切工作也都沒有太大的意義。事實(shí)上，稀疏空間有其本身的規(guī)律和法則，通過局部形成全局的流形思想從本質(zhì)上是不適合 于此的。雖然，流形是一種非常美的理論，但是再漂亮的理論也需要用得其所——它應(yīng)該用于解決具有密集數(shù)據(jù)分布的低維空間。至于，一些paper所報(bào)告的在 高維空間（比如人臉）運(yùn)用流形方法獲得性能提升，其實(shí)未必是因?yàn)?#8220;流形”本身所起的作用，而很可能是其它方面的因素。

8. 流 形在實(shí)際應(yīng)用中起重要作用的還有兩個方面：一個是研究幾何形體的性質(zhì)（我們暫且不談這個），還有就是它和代數(shù)結(jié)構(gòu)的結(jié)合形成的李群(Lie group)和李代數(shù)(Lie algebra)。 當(dāng)我們研究的對象是變換本身的時候，它們構(gòu)成的空間是有其特殊性的，比如所有子空間投影形成了Grassmann流形，所有的可逆線性算子，或者仿射算 子，也形成各自的流形。對他們的最重要操作是變換的結(jié)合，而不是加法數(shù)乘，因此，它們上面定義的更合適的代數(shù)結(jié)構(gòu)應(yīng)該是群和不是線性空間。而群和微分流形 的結(jié)合體——李群則成為它們最合適的描述體系——而其切空間則構(gòu)成了一種加強(qiáng)的線性空間：李代數(shù)，用于描述其局部變化特性。

李代數(shù)和李 群的關(guān)系是非常漂亮的。它把變換的微變化轉(zhuǎn)換成了線性空間的代數(shù)運(yùn)算，使得移植傳統(tǒng)的基于線性空間的模型和算法到李空間變得可能。而且李代數(shù)中的矩陣比起 變換本身的矩陣甚至更能反映變換的特性。幾何變換的李代數(shù)矩陣的譜結(jié)構(gòu)就能非常方便地用于分析變換的幾何特性。

最后，回頭總結(jié)一下關(guān)于 嵌入這個應(yīng)用廣泛的策略，在learning中的isometry, kernel和manifold embedding都屬于此范疇，它們分別通過保持原空間的度量結(jié)構(gòu)，內(nèi)積結(jié)構(gòu)和局部結(jié)構(gòu)來獲得到目標(biāo)（通常是向量空間）的嵌入，從而獲得全局的坐標(biāo)表 達(dá)，線性運(yùn)算和度量，進(jìn)而能被各種線性算法和模型所應(yīng)用。

在獲得這一系列好處的同時，也有值得我們注意的地方。首先，嵌入只是一種數(shù)學(xué) 手段，并不能取代對問題本身的研究和分析。一種不恰當(dāng)?shù)脑冀Y(jié)構(gòu)或者嵌入策略，很多時候甚至適得其反——比如稀疏空間的流形嵌入，或者選取不恰當(dāng)?shù)?kernel。另外，嵌入適合于分析，而未必適合于重建或者合成。這是因?yàn)榍度胧且粋€單射(injection)，目標(biāo)空間不是每一個點(diǎn)都和原空間能有效 對應(yīng)的。嵌入之后的運(yùn)算往往就打破了原空間施加的限制。比如兩個元素即使都是從原空間映射過來，它們的和卻未必有原像，這時就不能直接地回到原空間了。當(dāng) 然可以考慮在原空間找一個點(diǎn)它的映射與之最近，不過這在實(shí)際中的有效性是值得商榷的。

和Learning有關(guān)的數(shù)學(xué) 世界是非常廣博的，我隨著學(xué)習(xí)和研究的深入，越來越發(fā)現(xiàn)在一些我平常不注意的數(shù)學(xué)分支中有著適合于問題的結(jié)構(gòu)和方法。比如，廣群(groupoid)和廣 代數(shù)(algebroid)能克服李群和李代數(shù)在表示連續(xù)變換過程中的一些困難——這些困難困擾了我很長時間。解決問題和建立數(shù)學(xué)模型是相輔相成的，一方 面，一個清晰的問題將使我們有明確的目標(biāo)去尋求合適的數(shù)學(xué)結(jié)構(gòu)，另一方面，對數(shù)學(xué)結(jié)構(gòu)的深入理解對于指導(dǎo)問題的解決也是有重要作用的。對于解決一個問題來 說，數(shù)學(xué)工具的選擇最重要的是適合，而不是高深，但是如果在現(xiàn)有數(shù)學(xué)方法陷入困難的時候，尋求更高級別的數(shù)學(xué)的幫助，往往能柳暗花明。數(shù)學(xué)家長時間的努力 解決的很多問題，并不都是理論游戲，他們的解決方案中很多時候蘊(yùn)含著我們需要的東西，而且可能導(dǎo)致對更多問題的解決——但是我們需要時間去學(xué)習(xí)和發(fā)現(xiàn)它 們。