QCCNN量子类神经网路架构

QCCNN量子類神經網路架構蔡賢亮義守大學資訊管理系jimisu.edu.tw劉榕軒義守大學資訊管理系M9322020stmail.isu.edu.tw摘要到目前為止，已有各式各樣的量子類神經網路模型被提出了。但從研究中，我們發現到多數的模型只是個構想，並沒有提出明確而完整的量子學習法則；只有少數模型有提出量子學習法則，但是我們也發現到這些學習法則是不可行的，因為它們都不能真正的符合量子理論。而從目前已被提出的量子類神經網路的學習法則中，我們發現到Dan Ventura 和 Tony Martinez 提出的以量子搜尋演算法（quantum search algorithm）為基礎的學習法則是最可行的（在論文中，我們將稱此學習法則為量子搜尋學習法則）；但這個量子學習法則卻仍存在若干個缺陷，使得這個學習演算法仍有改進之處。為了解決量子搜尋學習法則的缺陷，我們提出一個新的量子類神經網路架構，它結合傳統的cascade correlation 類神經網路（CCNN）的自動建構概念及量子搜尋學習法則，我們稱這個新量子類神經網路架構為量子cascade correlation 類神經網路（QCCNN: quantum cascade correlation neural network）。這個新的架構不但解決了如何決定量子類神經網路大小的問題，也可以減少量子搜尋學習法則在訓練過程花費的時間及空間。從初步的實驗數據顯示，我們提出的QCCNN及其新學習法則確實更有效率、更可行。關鍵字：cascade correlation 類神經網路、量子類神經網路、量子搜尋演算法、錯誤嘗試法。壹、引言傳統領域的類神經網路（NN, neural networks）發展也已有一甲子的歲月了，由於它具有若干著越能力，使得類神經網路成為發展最快速的研究領域之一，而且它也已經被大量地應用在相當多的領域上；但就目前的電腦處理架構而言，實際上，我們並未把類神經網路的平行處理特性發揮出來，我們充其量只是在模擬而已，所以目前類神經網路的實際應用結果乃大大地受限於目前電腦技術。而超大型積體電路的發展也接近瓶頸，新的電腦架構（基因電腦、分子電腦及量子電腦等）研發將是勢在必行，而量子電腦（quantum computers）便是一個方向。如果量子電腦在未來果真的成為事實，那目前科學界上有若干難解或不可能解的問題都將可能不再是難題了（例如，密碼問題）！另外，量子電腦的量子平行處理能力對於類神經網路也將帶來革命性的突破，因為類神經網路的平行處理特性得以藉由量子平行計算技術而完全發揮。而以量子理論為基礎的類神經網路則稱為量子類神經網路（QNN, quantum neural networks）。到目前為止，已有若干量子類神經網路模型被提出了，但多數模型都沒有提出很明確的方法來訓練它們的量子類神經網路，甚至有些模型根本沒有提及要如何去訓練量子類神經網路。例如，Altaisky在2001年提出的模型中，他曾提到使用類似傳統類神經網路的gradient descent學習法則來訓練量子類神經網路，然而，這個訓練法則是否符合量子理論呢？我們曉得其答案是否定的。目前已提出的量子類神經網路類似於傳統類神經網路的論述有，其它的模型則與傳統類神經網路差異極大，例如，quantumdot 類神經網路。而這些被提出的量子類神經網路模型多數是不實用或跟本無法應用量子技術實做。但對於類神經網路而言，學習法則是它們的主要精髓之一，沒有可行的學習法則，它們便失去學習的能力，所以，量子類神經網路要能實現的話，那量子學習法則也是迫切需要的。而Dan Ventura 和 Tony Martinez在2000年首先提出將量子搜尋演算法（quantum search algorithm）應用在量子關連記憶學習上，利用量子搜尋演算法來訓練量子類神經網路。我們發現這是一個確實可行且合乎量子理論的量子學習法則。貳、量子搜尋學習法則傳統類神經網路都是藉由調整權重值來達到學習的目的，但是這種方式似乎是不適用於量子類神經網路；而要訓練量子類神經網路的另一個可行的方法是從所有可能的權重向量集合中，找出一組權重向量能使所有的訓練樣本能被正確地分類。在2000年，Dan Ventura 和 Tony Martinez 首先提出將量子搜尋演算法（quantum search algorithm）應用在量子關連記憶學習上，利用量子搜尋演算法在量子關連記憶學習上。又在2003年，Ricks和Ventura再次提出利用量子搜尋演算法來訓練量子類神經網路，並且實驗証明其方法的可行性。這也是我們目前發現最可行的量子學習法則。他們利用量子搜尋演算法從所有可能的權重集合中找出一組權重，這組權重需可以成功且正確地分類所有的訓練樣本，而它便是訓練完成後所得到的最後權重。這個作法的基礎想法是利用量子理論的狀態線性疊加（linear superposition）的特性，將所有可能的權重向量疊加在一起，然後使用量子搜尋演算法從中尋求得一組權重向量，使得所有的訓練樣本成功地被分類。到目前為止，量子搜尋演算法是少數已被認定為合乎量子計算領域的演算法之一，而以它為基礎的量子搜尋學習法則也完全合乎量子理論，所以，我們認為這個方法是可行的。他們也成功地將量子搜尋學習法則應用在若干的實際問題上，例如，他們已經成功地利用量子搜尋學習法則解決了 XOR 問題、iris 分類問題、lenses 分類問題及 hayes-roth 問題上。而且從實驗的數據上來看，這個學習法則是確實可行的，而且效能也是相當不錯。由這些實驗的數據更證明了量子搜尋學習法則的可行性。一、量子搜尋演算法Grover在1996年提出量子搜尋演算法，它是少數已被認定為合乎量子計算領域的演算法之一。在N個未排序過的資料中搜尋出給定的資料，若以傳統搜尋演算法需要 次比較，而量子搜尋演算法 次比較。Grover的量子搜尋演算法利用一個稱為quantum oracle call黑盒子，和一個稱為inversion about average量子運算子，來逐步增大給定資料的狀態被測量到的機率。在經過 次運算後，具有最高機率的資料便是我們的搜尋目標。二、量子搜尋學習法則的缺點雖然實驗的數據更證明了量子搜尋學習法則的可行性，但是我們仍發現到量子搜尋學習法則有以下的缺陷：第一，如果要符合全部訓練樣本要被成功分類的 oracle call，我們或許可以找到一組合適的權重向量，但這組權重向量很可能並不是我們需要的，因為它可能有過渡訓練（overfitting）了。若訓練樣本集合中含有若干的錯誤樣本，或訓練樣本含有雜訊時，過渡訓練的發生那就勢必會發生，因為我們很可能需要一個較大的量子類神經網路才有機會將這些有問題的訓練樣本百分之百地分類成功，而訓練完的量子類神經網路不僅記憶正確的樣本，同時也將錯誤的樣本留在記憶中，這對分類未知樣本會造成極嚴重的錯誤，所以讓全數的訓練樣本百分之百分類成功的oracle call是很不恰當的。作者Ricks和Ventura為了解決這個缺陷，他們將量子搜尋演算法中的oracle call做了些許的修改，將oracle call改為不再需要全數訓練樣本被正確分類，而將oracle call設定成訓練樣本正確分類率低於100%（例如，95%）。這個修改確實能解決這個問題，但是我們很難決定oracle call應該設多少才適當。若oracle call設太高的話，很可能沒有任何一組權重能通過它，這將造成每一組權重都擁有相同的機率，也就是沒有一組權重會超過0.5，所以，搜尋失敗！另外，這也可能造成overfitting的問題。第二，當量子搜尋學習法則在尋找一組權重向量時，我們所需花費的空間複雜度（space complexity）是指數成長的（例如，若要搜尋n-bits的資料空間，則所需的空間複雜度為），這對於較複雜的問題或架構較大的量子類神經網路將會是不可行的。作者也提出了片斷權重學習法則（piecewise weight learning rule）來改善此缺陷，它是以隨機選取某個神經元來訓練其權重（其它神經元的權重則凝結不動），所以每個神經元的權重分開獨立訓練，而不在將整個量子類神經網路的所有權重同時訓練。雖然這種方式可以降低空間複雜度的問題，但它卻大大地拉長訓練的時間，因為它必需持續地隨機訓練單一個神經元的權重，直到整個量子類神經網路達到我們的要求為止。第三，不管是傳統或是量子類神經網路，當我們要使用它們來解問題時，我們首先會遇到一個困難，那就是究竟要用多大的類神經網路才合適呢？這個問題其實對於類神經網路的表現是影響重大的，因為太大的架構通常會出現overfitting的現象。另外，對於量子搜尋學習法則來說，大的架構也是需要較多的訓練時間及相當龐大的空間複雜度（如第二點所述），所以，太大的類神經網路架構是不妥當的；然而，太小的架構則會有訓練不足或無法訓練的現象產生，它的訓練過程可能都無法收斂，所以訓練程序是無法結束，只能靠人為中止它，另外，這樣的類神經網路的分類品質必定也不高，所以，小架構的類神經網路也是不妥當的。在他們的實驗中，他們顯示出他們的量子搜尋學習法則的效能，但他們卻沒有告訴我們，實驗中所採用的類神經網路大小是如何制定的。其實，我們可以很容易地猜測到，他們應該是採用傳統類神經網路中的錯誤嘗試法（trial-and-error）來找出一個合適的量子類神經網路，這種作法是不可行的，因為這種做法使得他們將花更多的訓練時間及空間。雖然量子搜尋學習法則仍有上述的缺點存在，不過這個方法還是目前被提出的量子類神經學習法則中是較可行的，其實有些缺點也同樣存在於傳統的類神經網路，而且已經成功地被解決了，例如，類神經網路架構問題就有若干的演算法被提出，而我們也針對這個問題做了不少的研究，提出一系列的方法來讓類神經網路自動建構合適的類神經網路架構，並且獲得相當不錯的成果。所以，我們或許也可以將傳統的解決方法應用到量子類神經網路中，並解決上述的缺點。從這些已被提出的傳統類神經網路演算法中，我們發現傳統的cascade correlation 類神經網路（CCNN）有很多不錯的特性，它成功的解決了不少傳統類神經網路的問題，而某些相同的問題也同樣困擾著量子類神經網路，而且從它的若干特性中，我們發現這些特性可以應用到量子類神經網路上。參、Cascade Correlation類神經網路（CCNN）以下我們對cascade correlation 類神經網路做些簡略的介紹，並說明他的那些特性可以解決那些量子搜尋學習法則存在的缺陷。傳統類神經網路 cascade correlation 類神經網路是自動建構類神經網路架構的演算法之一，也具有令人稱讚的效能，它的效能也遠遠優於傳統的倒傳遞類神經網路（back-propagation neural networks），是一個相當有效率的類神經網路架構。它不像倒傳遞類神經網路是同時訓練整個類神經網路的權重值，它是可以依需求自動地動態建構出多階層（multilayer）的類神經網路，所以它比倒傳遞類神經網路具有快速的學習速率，它可以自己決定自己的網路大小及架構，而且當訓練樣本集合改變時，它不需重新再建構一個全新的網路架構，它可以以先前的網路架構為基礎，再繼續增建已訓練過的類神經網路架構。CCNN 類神經網路在尚未訓練時，它只包含輸入層及輸出層，而經由訓練的過程，它會依需要自動地加入新的隱藏神經元，直到訓練樣本的成功分類率達到我們的要求為止。新的隱藏神經元加入的方法是一個一個依序加入的，而且它每次只需訓練要加入的隱藏神經元（hidden neurons），而其它已存在之神經元及其所屬之權重則被凍結不變，所以 CCNN 類神經網路是可以解決量子搜尋學習法則的第二及第三個缺點。由於CCNN是一次只訓練一個隱藏神經元的權重，所以，每訓練一個隱藏神經元的所有可能權重集合會遠少於整個量子類神經網路的所有權重集合，所以，我們可以大大減少所需的訓練空間複雜度。而我們只要再對 CCNN 類神經網路的自動建構演算法做些修改的話，我們也可以將量子搜尋學習法則的第一個缺點也減到最低的程度。CCNN 類神經網路的學習法則是兩階段式的，第一個階段，是調整輸出層與所有隱藏層及輸入層之間的權重向量，藉由訓練的過程，可以慢慢地降低錯誤函式的值，而當錯誤值變化量小於某一預設門檻時，也就是訓練趨近於穩定時，此一個階段學習程序便中止，並判斷訓練樣本被正確辨識的準確率是否達到我們的要求，若是，則結束整個學習程序，整個類神經網路便建構完成了；否則，便加入一個新的隱藏神經元，並進入第二學習階段。這一階段的學習程序是要調整此新加入隱藏神經元與輸入層及所有已存在之隱藏神經元之間的權重向量，經由訓練的過程，可以慢慢地提升此新神經元輸出值與輸出層的錯誤值的相關值（correlation）。此相闗值愈大則代表此新加入的隱藏神經元可以更降低錯誤值。同樣地，當相關值增加緩慢時，第二階段學習程序便中止，並且把此隱藏神經元的權重凍結。然後便重回第一階段重複執行。這兩個學習階段會被重複地執行，直到訓練樣本的成功辨識率達到要求為止。肆、QCCNN量子類神經網路架構那要如何讓CCNN的自動建構特性融合Bob Ricks 和 Dan Ventura 提出的量子搜尋學習法則呢？我們利用二者的特性來建立量子類神經網路自動建構演算法，它具有CCNN的自動建構特性，也擁有Bob Ricks 和 Dan Ventura 提出的量子搜尋學習法則。用這種方式建構出來的量子類神經網路，我們稱它為quantum cascade correlation類神經網路，簡稱為QCCNN。QCCNN演算法如表一所示。QCCNN類神經網路建構過程如圖一所示。QCCNN 類神經網路在尚未訓練之初，它也同樣是只有輸入神經層和輸出神經層。在第一個階段中，我們是調整輸出層與所有隱藏層及輸入層之間的權重向量，藉由量子搜尋學習演算法的訓練過程，我們可以快速地找到一組權重向量，並使錯誤值為最小，所以第一階段便結束；接下來，我們要判斷訓練樣本被正確辨識的準確率是否達到要求，若是，則結束整個學習程序，量子類神經網路便建構完成了；否則，便加入一個新的隱藏量子神經元，並進入第二學習階段。這一階段的學習程序是要調整此新加入隱藏量子神經元與輸入層及所有已存在之隱藏量子神經元之間的權重向量。同樣地，我們是採用量子搜尋的技巧來調整權重向量，並可以很快地找到一組權重值，使此新神經元輸出值與輸出層的錯誤值的相關值為最大，第二階段學習程序便中止，並且把此新加入的隱藏量子神經元的權重凍結。然後便重回第一階段重複執行。這兩個學習階段會被重複地執行，直到訓練樣本的成功辨識率達到要求為止。每執行第二階段學習程序一次便代表新增一個隱藏量子神經元，換句話說，第二階段學習程式重複執行的次數便代表隱藏量子神經元的個數。我們的QCCNN架構中，由於學習法則是兩階段的，所以我們也需要有二個不同性質的oracle，這兩個oracle各負責不同的任務，所要逹到的目標也不相同。在第一階段中，我們是希望經由量子搜尋技巧找到介於輸出層和其它層間的權重向量，而這組權重向量能使得訓練樣本的正確辨識率最高，換句話說，就是使得輸出層的錯誤值最低；而在第二階段中，我們會新增一個隱藏量子神經元至量子類神經網路中，並希望同樣經由量子搜尋技術找到新隱藏量子神經元的權重向量，這組權重向量可以使得新神經元的輸出值和輸出層的錯誤值產生最大的相關；如果二者間的關連愈大，那代表這個新加入的神經元可以使得輸出層的錯誤可以降得更低。表一 QCCNN演算法Algorithm QCCNNLearning phase: S1: Begin with the minimal network with no hidden neuronsFirst phase: Training output neurons S2: Training Weights, , of output neurons by quantum search leaning rule with oracle call (1) where , , and are the error, the desired output value, and actual output value of output neuron o for training pattern p, respectively. S3: If then stop, where is the percentage of successful classification for training patterns and is a stop criterion for learning phase.Second phase: Training a new hidden neuron S4: Training weights, of a new hidden neuron by quantum search learning rule with oracle call (2) where is the output value of this new hidden neuron for training pattern p. S5: Add the selected hidden neuron to the network, then goto S2.Classification phase:For an unknown pattern X, it is classified to into class c,where 另外，我們也只要再對 CCNN 類神經網路做些修改的話，就可以將原量子搜尋學習法則的第一及第二缺點也減到最低的程度，使得overfitting的機會減少，也可以減少量子搜尋找不到符合oracle及同時有二個或二個以上狀態符合oracle的可能性。這是相當重要的改良，因為量子搜尋演算法中，若同時有二個或二個以上的狀態同時符合oracle的話，那麼量子搜尋演算法是會失敗的；若找不到任何一個能符合oracle的狀態的話，那麼它便表示搜尋失敗，所有狀態的機率會保持相同，所以我們無從得到解答，也可以說是失敗！原量子搜尋學習法則只要上述兩個其中一個情況成立時，它便無法訓練類神經網路，那麼就需要視情修改類神經網路的大小，然後再重新訓練類神經網路，直到找到一個類神經網路架構只含唯一一組權重向量符合oracle為止。事實上，他們的方法是非常不實際的，但我們則加入CCNN的概念並修改oracle的定義來解決它！由於我們的學習法則不同於原作者所提出的方法，以及我們的方法是可以自動建構類神經網路，而且一次只新增一個隱藏量子神經元，所以在建構出的類神經網路架構是完全不同於原方法的。我們的類神經網路，每個隱藏層只會含有一個隱藏神經元。伍、實驗結果我們同樣以XOR 問題、iris 分類問題、lenses 分類問題及 hayesroth 問題為例，我們的方法需要很少的訓練時間及空間，而且，它可以自動地建構量子類神經網路，不需使用者去決定！而在辨識效果上，二者則相差不遠。從目前已完成的初步實驗結果中，我們可以看出我們的方法確實比原量子搜尋學習法則要來得更有效率、更可行。陸、研究探討與未來工作為了解決Bob Ricks 和 Dan Ventura的量子搜尋學習法則的缺陷，我們將傳統的cascade correlation 類神經網路的概念加入至量子搜尋學習法則中。這個改良解決了量子類神經網路大小的問題，也解決了若干量子搜尋學習法則的缺點。從目前的實驗數據顯示，我們的新學習法則比原量子搜尋學習法則更有效率、更可行。然而，我們的方法仍有改進的地方。由於我們的學習法則是結合CCNN與量子搜尋演算法，所以愈上層的神經元擁有的神經連結數目也愈多，這也是會造成很嚴重的問題；另外若樣本的特徵維度很大時，也是會有可行性上的問題，所以，我們還在繼續相關的研究，希望能找出更可行的量子類神經網路模型及其學習法則。圖一 QCCNN類神經網路建構過程Wnew hiddenneuronnew hiddenneuronwwWinput neuronsoutput neurons(a)(b)W(c)(d)(e)weights under trainingfrozen weights柒、致謝本論文呈蒙國科會計畫NSC94-2213-E-214-007-經費補助，特此致謝。捌、參考文獻B. Ricks and D. Ventura, Training a Quantum Neural Network, Neural Information Processing Systems, pp. , December 2003.Alexandr Ezhov and Dan Ventura, Quantum Neural Networks, in Future Directions for Intelligent Systems and Information Science (Ed. N. Kasabov), Physica-Verlag, 2000.Dan Ventura and Tony Martinez, Quantum Associative Memory, Information Sciences, vol. 124 nos. 1-4, pp. 273-296, 2000.L. K. Grover, A fast Quantum mechanical algorithm for database search, in Proceedings of the 28th ACM STOC, pp. 212-219, 1996.L. K. Grover, Quantum mechanics helps in searching for a needle in a haystack, in Physical Review Letters, Vol. 78, pp. 325-328, 1997.L. Fei and Z. Baoyu, A study of Quantum Neural Networks, in IEEE international conference of Neural Networks & Signal Processing, pp. 539-542, 2003.S. E. Fahlman and C. Lebiere. “The cascade-correlation learning architecture,”Technical Report CMU-CS-90-100, School of Computer Science, Carnegie Mellon University, 1990.S. E. Fahlman and C. Lebiere. “The cascade-correlation learning architecture,”In Advances in Neural Information Processing Systems, D. S. Toouretzky, Ed., San Mateo, CA: Morgan Kaufmann, 2:524-532, 1990.S.-J. Lee and M.-T. Jone. “An extended procedure of constructing neural networks for supervised dichotomy.”IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics, 26(4):660-665, 1996.S.-J. Lee, M.-T. Jone, H.-L. Tsai. “Constructing neural networks for multi-class descretization based on information entropy.”IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics, 29(3):445-453, 1999.H.-L. Tsai and S.-J. Lee, Construction of Neural Networks on Structured Domains, Proceedings of 9th International Conference on Neural Information Processing, 1:50-54, Singapore, 2002.H.-L. Tsai and S.-J. Lee, “Entropy-based generation of supervised neural networks for classification of structured patterns, “IEEE Transactions on Neural Networks, 15(2):283-297，2004.M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information, Cambridge University Press, 2000.T. Pellizzari, S. A. Gardiner, J. I. Cirac and P. Zoller, Physical Review Letter, 75, 3788-3791 (1995) Decoherence, Continuous Observation, and Quantum Computing: A Cavity QED Model.P. W. Shor, Physical Review A, 52, 2493-2496 (1995) Scheme for Reducing Decoherence in Quantum Computer Memory.E. Behrman, L. Nash, J. Steck, V. Chandrashekar, and S. Skinner, Simulations of Quantum Neural networks, Information Sciences, 128(3-4):257-269, October 2000.E. Behrman, J. Niemel, and J. Steck, A Quantum Dot Neural Network, Technical report, www.engr.twsu.edu/me/faculty/steck/pubs/ieeenn96.ps, 1996.S. Gupta and R. Zia, Quantum Neural Networks, Technical report, http:/www.arxiv.org/PS_cache/quant-ph/pdf/0201/0201144.pdf, 2002.T. Menneer, Quantum Artificial Neural Networks, PhD thesis, University of Exeter, 1998.