龐善臣，郝少華，宋 弢*，宮法明，潘林強(qiáng)

(1.中國(guó)石油大學(xué)(華東) 計(jì)算機(jī)與通信工程學(xué)院，山東 青島 266580；2.華中科技大學(xué) 自動(dòng)化學(xué)院，湖北 武漢 430074)

1998年，P?un[1]首次提出了膜計(jì)算 (membrane computing)的概念，旨在將細(xì)胞中經(jīng)過億萬年演化沉淀的計(jì)算智能抽象成為能夠執(zhí)行計(jì)算的模型.膜計(jì)算研究的計(jì)算模型是分布式并行計(jì)算模型，統(tǒng)稱為膜系統(tǒng).膜計(jì)算系統(tǒng)結(jié)構(gòu)分類有3類：細(xì)胞型膜系統(tǒng)[1]、組織型膜系統(tǒng)[2]、脈沖神經(jīng)膜系統(tǒng)[3]，其在求解NP(non-deterministic polynomial)問題[4]、聚類分析[5-6]以及關(guān)聯(lián)規(guī)則挖掘[7]等問題中均得到了廣泛應(yīng)用.膜計(jì)算屬于生物啟發(fā)的計(jì)算模型(bio-inspired computing model)[8].該綜述評(píng)述時(shí)間因素對(duì)脈沖神經(jīng)膜系統(tǒng)計(jì)算能力的影響.

2006年，受大腦神經(jīng)元利用激發(fā)和脈沖傳遞進(jìn)行通訊的生物機(jī)理啟發(fā)，Ionescu等[3]提出了脈沖神經(jīng)膜系統(tǒng)計(jì)算模型.該系統(tǒng)是一類分布式、并行計(jì)算模型.第3代神經(jīng)網(wǎng)絡(luò)具有以下幾個(gè)特點(diǎn)：(1)神經(jīng)元的激發(fā)與時(shí)間相關(guān)聯(lián)；(2)神經(jīng)元只有在脈沖數(shù)目達(dá)到一定程度的時(shí)候才激發(fā)；(3)利用不同的脈沖編碼方式表示系統(tǒng)內(nèi)的信息.因此，從模型設(shè)計(jì)的出發(fā)點(diǎn)來看，脈沖神經(jīng)膜系統(tǒng)屬于脈沖神經(jīng)網(wǎng)絡(luò)的范疇[9].

與傳統(tǒng)的人工神經(jīng)網(wǎng)絡(luò)不同，脈沖神經(jīng)膜系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)為多重集，并且使用形式語言與自動(dòng)機(jī)理論中的文法產(chǎn)生式來描述神經(jīng)元的激發(fā)行為.由于使用文法能夠更好地以“語義”的方法描述生物神經(jīng)元的激發(fā)行為，而且文法作為較“底層”的數(shù)據(jù)結(jié)構(gòu)具有較為豐富的數(shù)據(jù)處理方式，這些優(yōu)點(diǎn)使得脈沖神經(jīng)膜系統(tǒng)展現(xiàn)出良好的計(jì)算特性.Siegelmann等[10]在研究人工神經(jīng)網(wǎng)絡(luò)的計(jì)算能力時(shí)發(fā)現(xiàn)，人工神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)圖靈機(jī)的計(jì)算能力需要886個(gè)“processer”.這一結(jié)果被認(rèn)為是神經(jīng)網(wǎng)絡(luò)模型具有解決實(shí)際問題能力的理論依據(jù).針對(duì)這一問題，P?un等[11]在2007年構(gòu)造了與圖靈機(jī)等價(jià)的脈沖神經(jīng)膜系統(tǒng)，并且使用的神經(jīng)元數(shù)目為49個(gè)，隨后發(fā)展出了模塊組合優(yōu)化策略[12]，神經(jīng)元的數(shù)目減少到37個(gè).通過引入神經(jīng)元容量增加策略，Pan等[13]構(gòu)建了具有10個(gè)神經(jīng)元的通用脈沖神經(jīng)膜系統(tǒng).2016年，這一結(jié)果被Song等[14]通過引入request rule，將這一結(jié)果進(jìn)一步改進(jìn)到4個(gè)神經(jīng)元.與人工神經(jīng)網(wǎng)絡(luò)所需的886個(gè)“processer”的結(jié)果比較，脈沖神經(jīng)膜系統(tǒng)具有使用較少神經(jīng)元實(shí)現(xiàn)圖靈計(jì)算能力的良好計(jì)算特性.許多學(xué)者將脈沖神經(jīng)膜系統(tǒng)應(yīng)用到實(shí)際問題，如求解組合優(yōu)化問題[15]、自然語言處理[16]、圖形圖像處理[17]、電力系統(tǒng)故障診斷[18]、生物信息學(xué)[19]等.這使得脈沖神經(jīng)膜系統(tǒng)迅速成為膜計(jì)算研究的熱點(diǎn).歐洲科學(xué)院院士Mario J Perez-Jimenez評(píng)價(jià)脈沖神經(jīng)膜系統(tǒng)的研究為“膜計(jì)算具有活力和前景的分支之一”[15].

生物神經(jīng)系統(tǒng)中，信息以脈沖發(fā)送的時(shí)間間隔進(jìn)行編碼，并且在神經(jīng)元之間進(jìn)行傳遞以實(shí)現(xiàn)神經(jīng)元之間的信息交互.神經(jīng)元之間按照特定時(shí)間策略進(jìn)行信息處理.脈沖神經(jīng)膜系統(tǒng)中的時(shí)間因素主要體現(xiàn)在以下4個(gè)方面：

(1) 激發(fā)時(shí)延.神經(jīng)元在使用激發(fā)規(guī)則激發(fā)時(shí)，產(chǎn)生的脈沖將在一定時(shí)間延遲后到達(dá)目標(biāo)神經(jīng)元.這對(duì)應(yīng)于生物神經(jīng)元在向臨近神經(jīng)元發(fā)送脈沖時(shí)，脈沖需要經(jīng)過突觸傳遞到目標(biāo)神經(jīng)元，這一過程所消耗的時(shí)間與突觸連接的長(zhǎng)度密切相關(guān).

(2) 基于時(shí)間間隔的信息編碼方式.脈沖神經(jīng)膜系統(tǒng)通過讀取脈沖串的方式從環(huán)境中讀取信息.讀取數(shù)字時(shí)，相鄰兩個(gè)脈沖之間的時(shí)間間隔即為讀取的數(shù)字.系統(tǒng)作為數(shù)字集族計(jì)算裝置時(shí)，每次計(jì)算終止時(shí)，系統(tǒng)內(nèi)的輸出神經(jīng)元發(fā)送至環(huán)境的第一個(gè)和第二個(gè)脈沖的時(shí)間間隔定義為系統(tǒng)計(jì)算的數(shù)字.

(3) 基于全局時(shí)鐘的神經(jīng)元協(xié)作方式.脈沖神經(jīng)膜系統(tǒng)中有一個(gè)標(biāo)記計(jì)算時(shí)刻的全局時(shí)鐘.在某個(gè)時(shí)刻下，系統(tǒng)中的神經(jīng)元將并行地執(zhí)行信息處理，向臨近神經(jīng)元發(fā)送脈沖或者保持緘默.神經(jīng)元之間相互獨(dú)立的執(zhí)行信息處理的工作模式，稱為同步工作模式.

(4) 規(guī)則執(zhí)行所消耗時(shí)間.在全局時(shí)鐘標(biāo)注的時(shí)刻下，每條激發(fā)規(guī)則和遺忘規(guī)則的執(zhí)行和使用都將消耗一個(gè)時(shí)間單元，稱為規(guī)則執(zhí)行時(shí)間，這一時(shí)間對(duì)應(yīng)于生化反應(yīng)完成所需要的時(shí)長(zhǎng).經(jīng)典脈沖神經(jīng)膜系統(tǒng)中將所有規(guī)則的執(zhí)行時(shí)間無差別地假設(shè)為一個(gè)時(shí)間單元.

針對(duì)上述4個(gè)時(shí)間因素，人們圍繞脈沖神經(jīng)膜系統(tǒng)展開了研究，發(fā)展了若干具有圖靈計(jì)算能力的脈沖神經(jīng)膜系統(tǒng)的范式[20-22].采用不同的信息編碼方式來編碼系統(tǒng)計(jì)算的結(jié)果，如語言、字符串以及系統(tǒng)讀取信息的方式[23-25]，建立了若干神經(jīng)元不同協(xié)作工作模式下的脈沖神經(jīng)膜系統(tǒng)[26-34]、時(shí)間無關(guān)脈沖神經(jīng)膜系統(tǒng)[34]等.通過不同的時(shí)間協(xié)作策略，脈沖神經(jīng)膜系統(tǒng)展現(xiàn)出了良好的計(jì)算性能，具有圖靈通用性.

目前，具有圖靈計(jì)算能力的脈沖神經(jīng)膜系統(tǒng)及其變型系統(tǒng)中，幾乎都使用了上述的4個(gè)時(shí)間因素.論文通過分析近十年的研究結(jié)果，評(píng)述分析時(shí)間因素對(duì)于脈沖神經(jīng)膜系統(tǒng)計(jì)算能力的影響.通過分析發(fā)現(xiàn)，神經(jīng)元之間的協(xié)作是脈沖神經(jīng)膜系統(tǒng)實(shí)現(xiàn)圖靈通用計(jì)算能力不可獲取的因素，而激發(fā)時(shí)延和基于時(shí)間間隔的信息編碼方式對(duì)于系統(tǒng)的計(jì)算能力沒有顯著的影響.這表明神經(jīng)元的協(xié)同工作策略是該系統(tǒng)解決實(shí)際問題時(shí)不可或缺的時(shí)間因素.

1 脈沖神經(jīng)膜系統(tǒng)

先給出脈沖神經(jīng)膜系統(tǒng)的定義，主要介紹激發(fā)時(shí)延、基于時(shí)間間隔的信息編碼方式和基于全局時(shí)鐘的神經(jīng)元協(xié)作方式的定義[3].

一個(gè)度為m的脈沖神經(jīng)膜系統(tǒng)Π定義為如下形式的多元組

Π=(O,σ1,σ2,…,syn,in,out)，

其中：O={a}表示單字母集，字母a被稱為脈沖；σ1,σ2,…,σm表示構(gòu)成系統(tǒng)的m個(gè)神經(jīng)元，神經(jīng)元σi=(ni,Ri)表示該神經(jīng)元初始包含ni個(gè)脈沖和有限規(guī)則集合Ri.

Ri包含兩類規(guī)則：

(1) 激發(fā)規(guī)則E/ac→ap;d，其中E表示字母表O上的正則表達(dá)式，c≥p>0，d≥0.

(2) 遺忘規(guī)則as→λ，其中s≥1.

syn?{1,2,…,m}×{1,2,…,m}表示突觸集合，且滿足(i,i)?syn，表示沒有指向自身神經(jīng)元的突觸.

in,out∈{1,2,…,m}分別表示輸入神經(jīng)元和輸出神經(jīng)元.輸入神經(jīng)元可以從環(huán)境中讀取信息(編碼為脈沖串的形式)，輸出神經(jīng)元可以向環(huán)境中發(fā)送脈沖.

激發(fā)規(guī)則使用方式如下：如果某個(gè)神經(jīng)元包含k個(gè)脈沖(表示為ak)并且ak∈L(E)(正則表達(dá)式E關(guān)聯(lián)的語言集合)，那么激發(fā)規(guī)則E/ac→ap;d被使用，神經(jīng)元消耗c個(gè)脈沖，向鄰接神經(jīng)元發(fā)送出p個(gè)脈沖.這p個(gè)脈沖經(jīng)過d步到達(dá)目標(biāo)神經(jīng)元.參數(shù)d被稱為激發(fā)時(shí)延.如果神經(jīng)元中恰好有s個(gè)脈沖，那么通過使用遺忘規(guī)則as→λ，這些脈沖將被移出系統(tǒng).系統(tǒng)中有一個(gè)全局時(shí)鐘，用于為每個(gè)神經(jīng)元標(biāo)注運(yùn)行時(shí)間.系統(tǒng)開始計(jì)算時(shí)，記為時(shí)刻1，以此類推.系統(tǒng)運(yùn)行的第t步則表示從時(shí)刻t-1到時(shí)刻t的時(shí)間片段.系統(tǒng)中的神經(jīng)元在某一時(shí)刻t都將并行進(jìn)行信息處理，即能激發(fā)的神經(jīng)元都將激發(fā)，通過激發(fā)消耗一定數(shù)目的脈沖，并向其臨近神經(jīng)元發(fā)送一定數(shù)目的脈沖.這一基于全局時(shí)鐘的神經(jīng)元之間協(xié)作進(jìn)行信息處理的方式被稱為同步工作模式.

脈沖神經(jīng)膜系統(tǒng)的輸入和輸出都是以脈沖串的形式編碼.對(duì)于數(shù)字，則是表示為脈沖串的第一個(gè)和第二個(gè)脈沖的時(shí)間間隔.例如，系統(tǒng)讀取數(shù)字n的方式是神經(jīng)元讀取脈沖串10n-11，其中1表示輸入神經(jīng)元讀取1個(gè)脈沖的時(shí)刻，0表示輸入神經(jīng)元不讀取任何脈沖的時(shí)刻，兩個(gè)讀取脈沖的時(shí)刻間隔恰好為數(shù)字n.類似地，系統(tǒng)產(chǎn)生數(shù)字n的方式如下：輸出神經(jīng)元在某一時(shí)刻t向環(huán)境發(fā)送1個(gè)脈沖，第二次發(fā)送脈沖的時(shí)刻為t+n.兩次發(fā)送脈沖的時(shí)間間隔為(t+n)-t，表示系統(tǒng)計(jì)算/產(chǎn)生數(shù)字n.從上述定義不難看出，脈沖神經(jīng)膜系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)屬于離散的字符多重集，這為脈沖神經(jīng)膜系統(tǒng)進(jìn)行自然語言處理提供了很好的支持.

2 時(shí)間因素對(duì)系統(tǒng)計(jì)算能力的影響

分別針對(duì)脈沖神經(jīng)膜系統(tǒng)的4個(gè)時(shí)間因素：激發(fā)時(shí)延、基于時(shí)間間隔的信息編碼策略、基于全局時(shí)鐘的神經(jīng)元協(xié)作方式、規(guī)則執(zhí)行所消耗時(shí)間，分析對(duì)系統(tǒng)計(jì)算能力的影響.

2.1 激發(fā)時(shí)延對(duì)系統(tǒng)計(jì)算能力的影響

激發(fā)時(shí)延，即參數(shù)d，與脈沖神經(jīng)膜系統(tǒng)的神經(jīng)元中包含的激發(fā)規(guī)則相關(guān)聯(lián)，它的設(shè)計(jì)靈感源于人類大腦神經(jīng)元中脈沖沿突觸傳遞到目標(biāo)神經(jīng)元產(chǎn)生的時(shí)間消耗.激發(fā)時(shí)延在脈沖神經(jīng)膜系統(tǒng)中的作用是在鄰接神經(jīng)元之間發(fā)送脈沖時(shí)，調(diào)控脈沖到達(dá)的時(shí)間.

在脈沖神經(jīng)膜系統(tǒng)提出之后，針對(duì)這一時(shí)間因素得到了很多計(jì)算結(jié)果，其中比較有說服力的是脈沖神經(jīng)膜系統(tǒng)的范式[16]、脈沖神經(jīng)膜系統(tǒng)[17]的改進(jìn)范式和脈沖神經(jīng)膜系統(tǒng)的強(qiáng)范式.對(duì)于計(jì)算模型范式的研究旨在不減弱計(jì)算模型計(jì)算能力的前提下，使用較少或者簡(jiǎn)化的元素.計(jì)算模型范式研究是計(jì)算機(jī)科學(xué)研究的經(jīng)典問題之一.P?un等[16]通過加強(qiáng)神經(jīng)元之間的協(xié)作，提出了脈沖神經(jīng)膜系統(tǒng)的范式，即在不使用遺忘規(guī)則或者激發(fā)時(shí)延的情況下，證明了脈沖神經(jīng)膜系統(tǒng)依然具有圖靈等價(jià)的數(shù)字集合的計(jì)算和識(shí)別能力.通過增加神經(jīng)元之間的協(xié)作，在對(duì)脈沖到達(dá)的時(shí)間不進(jìn)行任何調(diào)控的條件下，實(shí)現(xiàn)了具有脈沖“即發(fā)即到”特性的圖靈等價(jià)的脈沖神經(jīng)膜系統(tǒng).由此不難看出，激發(fā)時(shí)延調(diào)控系統(tǒng)執(zhí)行計(jì)算的功能，可由系統(tǒng)中神經(jīng)元之間的協(xié)作實(shí)現(xiàn)，因此激發(fā)時(shí)延對(duì)于系統(tǒng)的計(jì)算能力并不是不可或缺的因素.Garcia等[21]提出了脈沖神經(jīng)膜系統(tǒng)的強(qiáng)范式，通過進(jìn)一步增加神經(jīng)元之間的協(xié)作，構(gòu)造了計(jì)算通用的脈沖神經(jīng)膜系統(tǒng)，而系統(tǒng)中沒有任何的激發(fā)時(shí)延和遺忘規(guī)則.雖然該結(jié)果使用了較少的元素，但是系統(tǒng)的結(jié)構(gòu)變得異常繁瑣，較之使用激發(fā)時(shí)延和遺忘規(guī)則時(shí)，復(fù)雜程度大大提升.Wang等[18]提出了脈沖神經(jīng)膜系統(tǒng)的改進(jìn)范式.通過增加2個(gè)神經(jīng)元的容量(在神經(jīng)元中包含3n+1和3n+2個(gè)脈沖時(shí)都可以激發(fā))和擴(kuò)展激發(fā)規(guī)則的形式，構(gòu)造了結(jié)構(gòu)簡(jiǎn)單且不使用激發(fā)時(shí)延和遺忘規(guī)則的圖靈等價(jià)的脈沖神經(jīng)膜系統(tǒng).該范式是目前已知的、不使用激發(fā)時(shí)延和遺忘規(guī)則的圖靈等價(jià)脈沖神經(jīng)膜系統(tǒng)的較簡(jiǎn)范式.

根據(jù)上述結(jié)果的分析不難發(fā)現(xiàn)，神經(jīng)元的激發(fā)時(shí)延對(duì)于系統(tǒng)的計(jì)算能力并不是一個(gè)不可或缺的因素，可以通過增加神經(jīng)元之間的協(xié)作和擴(kuò)展神經(jīng)元的容量的方法，在不使用激發(fā)時(shí)延的情況下構(gòu)造具有圖靈等價(jià)計(jì)算能力的脈沖神經(jīng)膜系統(tǒng).這一結(jié)論在很多結(jié)果中得到了側(cè)面驗(yàn)證：許多計(jì)算通用的脈沖神經(jīng)膜系統(tǒng)的變型系統(tǒng)的構(gòu)造中都沒有使用激發(fā)時(shí)延，如帶反脈沖的脈沖神經(jīng)膜系統(tǒng)[30-33]、突觸上有激發(fā)規(guī)則的脈沖神經(jīng)膜系統(tǒng)[34-37]、帶激發(fā)權(quán)值的脈沖神經(jīng)膜系統(tǒng)[38]、帶星細(xì)胞的脈沖神經(jīng)膜系統(tǒng)[39-40]等.

相關(guān)問題：文獻(xiàn)[18]中提出的脈沖神經(jīng)膜系統(tǒng)的范式是否是最簡(jiǎn)范式，是脈沖神經(jīng)膜系統(tǒng)的一個(gè)公開研究問題.另外，該范式中容量神經(jīng)元脈沖數(shù)目在計(jì)算過程中不斷增加，直至計(jì)算終止.這將造成神經(jīng)元中脈沖的大量堆砌和冗余.如何在不使用激發(fā)時(shí)延的前提下，構(gòu)造結(jié)構(gòu)簡(jiǎn)單、神經(jīng)元容量合理增加的圖靈等價(jià)脈沖神經(jīng)膜系統(tǒng)的范式也是一個(gè)亟待解決的問題.

Chen等[41]針對(duì)只包含一條激發(fā)規(guī)則的神經(jīng)元，給出了利用神經(jīng)元級(jí)聯(lián)實(shí)現(xiàn)脈沖時(shí)延的功能模塊，如圖1所示.但是，對(duì)于多條規(guī)則的神經(jīng)元，如何構(gòu)建與其等價(jià)的無激發(fā)時(shí)延的模塊也是一個(gè)未解決的公開問題.

圖1 利用神經(jīng)元級(jí)聯(lián)實(shí)現(xiàn)脈沖時(shí)延的模塊

2.2 基于時(shí)間間隔編碼方式對(duì)系統(tǒng)計(jì)算能力影響

在大腦神經(jīng)系統(tǒng)中，由于信息是以脈沖堆砌的方式編碼的，這使得神經(jīng)元發(fā)送脈沖和接受脈沖的時(shí)間對(duì)于信息的表示具有很重要的影響.例如，當(dāng)一個(gè)神經(jīng)元處于緘默和積累脈沖的階段，接受新脈沖的時(shí)刻將決定神經(jīng)元激發(fā)的時(shí)刻，不同時(shí)刻接受不同的脈沖會(huì)引起神經(jīng)元以完全不同的方式激發(fā)，從而實(shí)現(xiàn)對(duì)于不同信息的處理.

受這一生物現(xiàn)實(shí)的啟發(fā)，脈沖神經(jīng)膜系統(tǒng)以基于時(shí)間間隔編碼方式通過輸入/輸出神經(jīng)元，從環(huán)境中讀取/向環(huán)境發(fā)送信息.系統(tǒng)通過讀取時(shí)間間隔為n的2個(gè)脈沖，表示向系統(tǒng)輸入數(shù)字n；系統(tǒng)以時(shí)間間隔n向環(huán)境發(fā)送2個(gè)脈沖，表示系統(tǒng)計(jì)算數(shù)字n.以這樣方式編碼輸入/輸出信息的情況下，Ionescu等[3]證明了脈沖神經(jīng)膜系統(tǒng)能夠計(jì)算圖靈可計(jì)算的數(shù)字集族，即具有圖靈通用性.

通過改變脈沖神經(jīng)膜系統(tǒng)讀取輸入和計(jì)算輸出的編碼策略，該系統(tǒng)可以計(jì)算和識(shí)別串(string)、語言(language).這方面研究的主要結(jié)果包括：Ibarra等[41]提出將脈沖神經(jīng)膜系統(tǒng)計(jì)算的脈沖串直接定義為系統(tǒng)計(jì)算的二進(jìn)制語言、Chen等[41]提出的基于脈沖神經(jīng)膜系統(tǒng)的字符語言產(chǎn)生和識(shí)別方法和軌跡語言產(chǎn)生方法[43]、Wang等[44]提出的基于脈沖神經(jīng)膜系統(tǒng)的控制語言產(chǎn)生方式等.

Ibarra等[41]提出了將脈沖神經(jīng)膜系統(tǒng)的計(jì)算結(jié)果直接定義為其產(chǎn)生的脈沖串，即二進(jìn)制串：當(dāng)時(shí)刻t輸出神經(jīng)元向外發(fā)送1個(gè)脈沖，此時(shí)將二進(jìn)制串的第t位記為1；否則記為0.據(jù)此可以根據(jù)脈沖神經(jīng)膜系統(tǒng)的計(jì)算過程，產(chǎn)生二進(jìn)制串的集合，稱為脈沖神經(jīng)膜系統(tǒng)產(chǎn)生的二進(jìn)制語言[39].以這一方式產(chǎn)生語言時(shí)，脈沖神經(jīng)膜系統(tǒng)能夠刻畫正則語言，其計(jì)算能力與有限狀態(tài)自動(dòng)機(jī)等價(jià)，不再具有圖靈等價(jià)的計(jì)算能力.

Chen等[42]提出的基于反轉(zhuǎn)映射策略的產(chǎn)生語言的脈沖神經(jīng)膜系統(tǒng).通過對(duì)系統(tǒng)生成的二進(jìn)制串進(jìn)行反轉(zhuǎn)映射，使每個(gè)二進(jìn)制串對(duì)應(yīng)于某個(gè)字母表上的字符串，并且證明了利用這種對(duì)應(yīng)關(guān)系，脈沖神經(jīng)膜系統(tǒng)具有產(chǎn)生遞歸可枚舉語言集族.因此，實(shí)現(xiàn)了圖靈等價(jià)的計(jì)算能力.同樣，脈沖神經(jīng)膜系統(tǒng)可以通過反轉(zhuǎn)映射識(shí)別任意字母表上的遞歸可枚舉語言.

隨后，Chen等[43]又提出了脈沖神經(jīng)膜系統(tǒng)產(chǎn)生語言的策略——計(jì)算過程中特定脈沖的移動(dòng)軌跡，即計(jì)算初始時(shí)指定追蹤軌跡的脈沖后，將其計(jì)算過程中到達(dá)的神經(jīng)元的標(biāo)記進(jìn)行連接，形成的字符串構(gòu)成的集合即為脈沖移動(dòng)的軌跡語言.且證明了利用這種產(chǎn)生語言的方式，正則語言和遞歸可枚舉語言都可以刻畫為脈沖神經(jīng)膜系統(tǒng)產(chǎn)生軌跡語言的映射語言，即這一產(chǎn)生語言的方式下，脈沖神經(jīng)膜系統(tǒng)具有與圖靈機(jī)等價(jià)的語言計(jì)算能力.

Ramanujan等[44]提出了基于脈沖神經(jīng)膜系統(tǒng)的控制語言產(chǎn)生方式.在該方法中，每條激發(fā)規(guī)則都關(guān)聯(lián)一個(gè)標(biāo)簽，而將系統(tǒng)從計(jì)算開始到終止時(shí)，使用的規(guī)則標(biāo)簽連接得到的字符串定義為系統(tǒng)產(chǎn)生的控制語言.證明了不使用空標(biāo)號(hào)λ的情況下，脈沖神經(jīng)膜系統(tǒng)以此方式接受的語言屬于上下文有關(guān)語言集族；而使用空標(biāo)號(hào)λ的情況，脈沖神經(jīng)膜系統(tǒng)可以刻畫遞歸可枚舉語言，實(shí)現(xiàn)了圖靈等價(jià)性.

根據(jù)上述成果分析不難看出，在不使用時(shí)間間隔定義系統(tǒng)計(jì)算結(jié)果的幾種情況下，脈沖神經(jīng)膜系統(tǒng)可以通過利用語言映射等方法實(shí)現(xiàn)圖靈等價(jià)的計(jì)算能力.因此，在使用反轉(zhuǎn)映射等輔助策略的條件下，基于時(shí)間間隔編碼方式對(duì)系統(tǒng)計(jì)算能力并未有顯著的影響.若無其他輔助策略，基于脈沖神經(jīng)膜系統(tǒng)甚至無法產(chǎn)生很多簡(jiǎn)單語言[41]，其計(jì)算能力有明顯的減弱.

相關(guān)問題：脈沖神經(jīng)膜系統(tǒng)作為語言產(chǎn)生和識(shí)別裝置在理論上具有與圖靈機(jī)等價(jià)的計(jì)算能力，但是如何將這些理論研究成果轉(zhuǎn)化用于解決實(shí)際問題，是脈沖神經(jīng)膜系統(tǒng)研究中的重要研究方向之一.具體來看，如何將脈沖神經(jīng)膜系統(tǒng)應(yīng)用于自然語言處理，包括語言/語音識(shí)別、機(jī)器翻譯、圖語言識(shí)別等，都是值得深入研究的課題.

2.3 神經(jīng)元協(xié)作方式對(duì)系統(tǒng)計(jì)算能力影響

脈沖神經(jīng)膜系統(tǒng)中有一個(gè)假設(shè)的全局時(shí)鐘，它的作用是對(duì)每個(gè)神經(jīng)元的時(shí)間進(jìn)行標(biāo)注，將系統(tǒng)執(zhí)行計(jì)算的時(shí)間劃分成若干時(shí)間單元，標(biāo)注為有限時(shí)間時(shí)刻，分別標(biāo)記為1,2,…,t,…,n,….經(jīng)典的脈沖神經(jīng)膜系統(tǒng)中，系統(tǒng)中的所有神經(jīng)元在任意時(shí)刻t都各自并行執(zhí)行信息處理和脈沖的傳遞，從而實(shí)現(xiàn)神經(jīng)元之間的協(xié)作.這一方式也被稱為基于全局時(shí)鐘的神經(jīng)元的同步協(xié)作方式.同步協(xié)作工作模式下的脈沖神經(jīng)膜系統(tǒng)具有圖靈通用性，即能夠計(jì)算/識(shí)別圖靈可計(jì)算的數(shù)字集合[3].隨后，人們開始研究不同工作模式下脈沖神經(jīng)膜系統(tǒng)的計(jì)算特性，包括異步工作模式[30]、局部同步工作模式[31]、有限異步工作模式[32].

異步工作模式下，使用擴(kuò)展激發(fā)規(guī)則(神經(jīng)元的每次激發(fā)可以向其鄰近神經(jīng)元發(fā)送多個(gè)脈沖)的脈沖神經(jīng)膜系統(tǒng)具有圖靈機(jī)等價(jià)的數(shù)字計(jì)算能力和語言產(chǎn)生/識(shí)別能力.但是，使用標(biāo)準(zhǔn)激發(fā)規(guī)則時(shí)，異步工作模式下的脈沖神經(jīng)膜系統(tǒng)的計(jì)算能力是一個(gè)尚未解決的公開問題.值得一提的是，同步工作模式下的脈沖神經(jīng)膜系統(tǒng)的計(jì)算能力是與圖靈機(jī)等價(jià)的[30].

Chen等[41]提出了限制的異步工作模式下的脈沖神經(jīng)膜系統(tǒng).該系統(tǒng)中，神經(jīng)元被限制在一定的時(shí)間內(nèi)以異步的方式執(zhí)行，一旦超出時(shí)限，神經(jīng)元將以同步的方式執(zhí)行信息處理.這一具有限制的異步工作模式的脈沖神經(jīng)膜系統(tǒng)，在使用標(biāo)準(zhǔn)激發(fā)規(guī)則時(shí)具有圖靈等價(jià)的計(jì)算能力.

Song等[27]提出了帶有局部同步神經(jīng)元集合的異步工作模式下的脈沖神經(jīng)膜系統(tǒng).在這類系統(tǒng)中，系統(tǒng)中存在多個(gè)神經(jīng)元同步集合，而屬于同一個(gè)同步集合的神經(jīng)元在同步工作模式下進(jìn)行信息處理.其他神經(jīng)元均以異步工作模式進(jìn)行信息處理.局部同步工作模式下，使用標(biāo)準(zhǔn)激發(fā)規(guī)則的脈沖神經(jīng)膜系統(tǒng)具有圖靈機(jī)等價(jià)的計(jì)算能力.根據(jù)上述分析不難看出，若使用擴(kuò)展激發(fā)規(guī)則，即允許神經(jīng)元發(fā)送多個(gè)脈沖，異步工作模式下的脈沖神經(jīng)膜系統(tǒng)具有圖靈機(jī)等價(jià)的計(jì)算能力.若限制神經(jīng)元每次激發(fā)只能發(fā)送1個(gè)脈沖，通過增加局部同步集合和激發(fā)時(shí)延可以實(shí)現(xiàn)圖靈機(jī)等價(jià)的計(jì)算能力.由此可得結(jié)論，隨著神經(jīng)元發(fā)送脈沖數(shù)目能力的增加，異步工作模式下的脈沖神經(jīng)膜系統(tǒng)的計(jì)算能力不會(huì)減弱，即具有圖靈通用性.使用標(biāo)準(zhǔn)激發(fā)規(guī)則的異步工作模式下的脈沖神經(jīng)膜系統(tǒng)的計(jì)算能力是一個(gè)亟待解決的公開問題.Song等[31]提出一個(gè)猜想，局部同步集合中至多需要2個(gè)神經(jīng)元，局部同步脈沖神經(jīng)膜系統(tǒng)就可以實(shí)現(xiàn)圖靈通用性.這一猜想的數(shù)學(xué)證明也是尚未解決的公開問題.

2.4 規(guī)則執(zhí)行所消耗時(shí)間對(duì)系統(tǒng)計(jì)算能力的影響

脈沖神經(jīng)膜系統(tǒng)中有一個(gè)全局時(shí)鐘，其功能是標(biāo)注系統(tǒng)中每一個(gè)神經(jīng)元的運(yùn)行時(shí)間.系統(tǒng)中定義神經(jīng)元執(zhí)行規(guī)則的時(shí)間消耗為一個(gè)時(shí)間單元，即規(guī)則在時(shí)刻t開始執(zhí)行，那么其使用將在時(shí)刻t+1結(jié)束.這一過程對(duì)應(yīng)于生物過程中產(chǎn)生脈沖所執(zhí)行生化反應(yīng)的時(shí)間消耗.

2010年，Pan等[39]通過在系統(tǒng)中引入規(guī)則集合的時(shí)間映射e:R→N，用來標(biāo)注規(guī)則集合R中的每條規(guī)則的執(zhí)行時(shí)間.為了研究規(guī)則執(zhí)行時(shí)間對(duì)脈沖神經(jīng)膜系統(tǒng)計(jì)算能力的影響，Pan等[46]證明了對(duì)于任意的時(shí)間映射R(稱為時(shí)間無關(guān))，脈沖神經(jīng)膜系統(tǒng)在使用擴(kuò)展激發(fā)規(guī)則的情況下，具有與圖靈機(jī)等價(jià)的計(jì)算能力，并且構(gòu)造了由10個(gè)神經(jīng)元構(gòu)成的計(jì)算通用的脈沖神經(jīng)膜系統(tǒng).這一結(jié)果說明，規(guī)則的執(zhí)行時(shí)間對(duì)于脈沖神經(jīng)膜系統(tǒng)的計(jì)算能力沒有顯著影響.

相關(guān)問題：對(duì)于任意的時(shí)間映射R，脈沖神經(jīng)膜系統(tǒng)在使用標(biāo)準(zhǔn)激發(fā)規(guī)則的情況下，是否具有圖靈等價(jià)的計(jì)算能力是尚未解決的公開問題.另外，時(shí)間無關(guān)脈沖神經(jīng)膜系統(tǒng)產(chǎn)生/識(shí)別語言的能力尚未可知.

3 結(jié)束語

分析評(píng)述了脈沖神經(jīng)膜系統(tǒng)中時(shí)間因素對(duì)其計(jì)算能力的影響，通過分析比較不同時(shí)間因素下脈沖神經(jīng)膜系統(tǒng)計(jì)算能力的結(jié)果表明：神經(jīng)元的激發(fā)時(shí)延對(duì)于系統(tǒng)的計(jì)算能力并不是一個(gè)不可或缺的因素，可以通過增加神經(jīng)元之間的協(xié)作和擴(kuò)展神經(jīng)元容量的方法實(shí)現(xiàn)系統(tǒng)的圖靈等價(jià)計(jì)算能力.通過使用反轉(zhuǎn)映射等輔助策略，基于時(shí)間間隔編碼信息的方式對(duì)系統(tǒng)計(jì)算能力并未有顯著的影響；若無其他輔助策略，其計(jì)算能力有明顯的減弱.通過增加神經(jīng)元發(fā)送脈沖數(shù)目能力，異步工作模式下的脈沖神經(jīng)膜系統(tǒng)的計(jì)算能力不會(huì)減弱，即具有圖靈通用性.而使用標(biāo)準(zhǔn)規(guī)則時(shí)，系統(tǒng)的計(jì)算能力尚屬公開問題.規(guī)則的執(zhí)行時(shí)間對(duì)于脈沖神經(jīng)膜系統(tǒng)的計(jì)算能力沒有顯著影響.

有關(guān)時(shí)間因素對(duì)于脈沖神經(jīng)膜系統(tǒng)計(jì)算能力的影響公開問題在每一部分中進(jìn)行了介紹.這里討論一下脈沖神經(jīng)膜系統(tǒng)中的時(shí)間因素在系統(tǒng)應(yīng)用中的影響.模糊脈沖神經(jīng)膜系統(tǒng)被證明是故障診斷系統(tǒng)建模分析的有效工具[45-47].如何結(jié)合脈沖神經(jīng)膜系統(tǒng)中對(duì)系統(tǒng)計(jì)算能力沒有顯著影響的時(shí)間因素，對(duì)多發(fā)系統(tǒng)、多時(shí)間尺度系統(tǒng)等復(fù)雜系統(tǒng)進(jìn)行建模分析是一個(gè)具有前景的研究方向.

小通用系統(tǒng)研究是計(jì)算機(jī)科學(xué)領(lǐng)域中的經(jīng)典問題，旨在使用較少的計(jì)算資源達(dá)到客觀的計(jì)算能力.脈沖神經(jīng)膜系統(tǒng)具有良好的計(jì)算性能，即具有與圖靈機(jī)等價(jià)的數(shù)字計(jì)算、數(shù)字識(shí)別、函數(shù)計(jì)算、語言產(chǎn)生和識(shí)別的能力.如何使用較少的計(jì)算資源(這里計(jì)算資源可以是神經(jīng)元數(shù)目、神經(jīng)元種類、規(guī)則種類和數(shù)目、突觸數(shù)目等)實(shí)現(xiàn)客觀的計(jì)算能力是一個(gè)值得深入研究的方向.

脈沖神經(jīng)膜系統(tǒng)是離散的計(jì)算模型，其數(shù)據(jù)結(jié)構(gòu)是字符多重集，信息處理方式是基于形式語言的“規(guī)則”，這為基于脈沖神經(jīng)膜系統(tǒng)進(jìn)行自然語言處理包括語言識(shí)別和語言產(chǎn)生等，提供了很好的天然特性，是脈沖神經(jīng)膜系統(tǒng)未來研究中具有活力的研究分支.

近年來，隨著信息化程度的不斷加深，信息科學(xué)迎來了大數(shù)據(jù)時(shí)代.深度學(xué)習(xí)是大數(shù)據(jù)處理中的關(guān)鍵技術(shù).如何在脈沖神經(jīng)膜系統(tǒng)的框架下發(fā)展學(xué)習(xí)方法，是脈沖神經(jīng)膜系統(tǒng)探究的熱點(diǎn)問題.在脈沖神經(jīng)膜系統(tǒng)的框架下發(fā)展深度學(xué)習(xí)的方法，是系統(tǒng)在實(shí)際應(yīng)用中的重要研究課題.

參考文獻(xiàn)：

[2] MARTIN-VIDE C, PUN G, PAZOS J, et al. Tissue P systems[J]. Theoretical Computer Science, 2003, 296 (2): 295-326.

[3] IONESCU M, PUN G, YOKOMORI T. Spiking neural P systems[J]. Fundamenta Informaticae, 2006, 71 (2/3): 279-308.

[4] ZHAO Y, LIU X, WANG W. Spiking neural P systems with neuron division and dissolution[J]. PloS One, 2016, 11 (9): 262-282.

[5] LIU X, XUE J. A cluster splitting technique by hopfield networks and P systems on simplices[J]. Neural Processing Letters, 2017 (5): 1-24.

[6] LIU X, XUE A. Communication P systems on simplicial complexes with applications in cluster analysis[J]. Discrete Dynamics in Nature and Society, 2012, 16 (3): 4-17.

[7] LIU X, ZHAO Y, SUN M. An improved apriori algorithm based on an evolution-communication tissue-like P system with promoters and inhibitors[J]. Discrete Dynamics in Nature and Society, 2017 (1): 1-11.

[8] ZHANG G, PAN L. A new branch in natural computing-membrane computing[J]. Chinese Journal of Computers, 2010, 33 (2): 208-214 (in Chinese).

[9] MAASS W. Networks of spiking neurons: the third generation of neural network models[J]. Neural Networks, 1997, 10 (9): 1659-1671.

[10] SIEGELMANN H T, SONTAG E D. On the computational power of neural nets[J]. Journal of Computer and System Sciences, 1995, 50 (1): 132-150.

[12] ZHANG X, ZENG X, PAN L. Smaller universal spiking neural P systems[J]. Fundamenta Informaticae, 2008, 87 (1): 117-136.

[13] PAN L, ZENG X. A note on small universal spiking neural P systems[C]//Workshop on Membrane Computing， 2009: 436-447.

[14] SONG T, PAN L. Spiking neural P systems with request rules[J]. Neurocomputing, 2016, 193: 193-200.

[15] ZHANG G, RONG H, NERI F, et al. An optimization spiking neural P system for approximately solving combinatorial optimization problems[J]. International Journal of Neural Systems, 2014, 24 (5): 144-146.

[17] DIAZ-PERNIL D, PENA-CANTILLANA F, GUTIERREZ-NARANJO M A. A parallel algorithm for skeletonizing images by using spiking neural P systems[J]. Neurocomputing, 2013, 115: 81-91.

[18] WANG T, ZHANG G, ZHAO J, et al. Fault diagnosis of electric power systems based on fuzzy reasoning spiking neural P systems[J]. IEEE Transactions on Power Systems, 2015, 30 (3): 1182-1194.

[19] CHEN Z, ZHANG P, WANG X, et al. A computational approach for nuclear export signals identification using spiking neural P systems[J]. Neural Computing and Applications, 2016 (5): 1-11.

[20] IBARRA O H, PUN A, PUN G, et al. Normal forms for spiking neural P systems[J]. Theoretical Computer Science, 2007, 372 (2/3): 196-217.

[21] GARCIA A M, PEREZ D, RODRIGUEZ-P A, et al. Spiking neural P systems: stronger normal forms[J]. Proceedings of the Fifth Brainstorming Week on Membrane Computing, 2007, 5 (5):411-425.

[23] ZHANG X, ZENG X, PAN L. On languages generated by asynchronous spiking neural P systems[J]. Theoretical Computer Science, 2009, 410 (26): 2478-2488.

[24] CHEN H, FREUND R, IONESCU M, et al. On string languages generated by spiking neural P systems[J]. Fundamenta Informaticae, 2007, 75 (3/4): 141-162.

[25] NISHIDA T Y. Computing k-block morphisms by spiking neural P systems[J]. Fundamenta Informaticae, 2011, 111 (4): 453-464.

[26] SONG T, PAN L. Spiking neural P systems with rules on synapses working in maximum spikes consumption strategy[J]. IEEE Transactions on NanoBioscience, 2015, 14 (1): 38-44.

[27] SONG T, PAN L. Spiking neural P systems with rules on synapses working in maximum spiking strategy[J]. IEEE Transactions on NanoBioscience, 2015, 14 (4): 465-477.

[28] IBARRA O H, PUN A, RODRIGUEZ-PATON A. Sequential SNP systems based on min/max spike number[J]. Theoretical Computer Science, 2009, 410 (30/31/32): 2982-2991.

[29] SONG T, PAN L, JIANG K, et al. Normal forms for some classes of sequential spiking neural P systems[J]. IEEE Transactions on NanoBioscience, 2013, 12 (3): 255-264.

[30] CAVALIERE M, IBARRA O H, PUN G, et al. Asynchronous spiking neural P systems[J]. Theoretical Computer Science, 2009, 410 (24/25): 2352-2364.

[31] SONG T, PAN L, PUN G. Asynchronous spiking neural P systems with local synchronization[J]. Information Sciences, 2013, 219: 197-207.

[32] WANG X, SONG T, GONG F, et al. On the computational power of spiking neural P systems with self-organization[J]. Scientific Reports, 2016, 6: 27624.

[33] PAN L, ZHANG X, ZENG X, et al. A survey to spiking neural P system[J]. Chinese Journal of Computers, 2008, 12: 2090-2096 (in Chinese).

[34] PAN L, ZENG X, ZHANG X. Time-free spiking neural P systems[J]. Neural Computation, 2011, 23 (5): 1320-1342.

[36] SONG T, WANG X, ZHANG Z, et al. Homogenous spiking neural P systems with anti-spikes[J]. Neural Computing and Applications, 2014, 24 (7/8): 1833-1841.

[37] METTA V P, KELEMENOVA A. Universality of spiking neural p systems with anti-spikes[C]//TAMC, 2014: 352-365.

[38] SONG T, XU J, PAN L. On the universality and non-universality of spiking neural P systems with rules on synapses[J]. IEEE Transactions on NanoBioscience, 2015, 14 (8): 960-966.

[39] PAN L, WANG J, HOOGEBOOM H J. Spiking neural P systems with astrocytes[J]. Neural Computation, 2012, 24 (3): 805-825.

[40] MACIAS-RAMOS L F, PEREZ-JIMENEZ M J. Spiking neural P systems with functional astrocytes[C]//International Conference on Membrane Computing, 2012: 228-242.

[41] IBARRA O H, WOODWORTH S. Characterizing regular languages by spiking neural P systems[J]. International Journal of Foundations of Computer Science, 2007, 18 (6): 1247-1256.

[42] CHEN H, IONESCU M, ISHDORJ T O, et al. Spiking neural P systems with extended rules: universality and languages[J]. Natural Computing, 2008, 7 (2): 147-166.

[43] CHEN H, IONESCU M, PUN A, et al. On trace languages generated by (small) spiking neural P systems[C]// International Workshop on Descriptional Complexity of Formal Systems - Dcfs, 2006: 94-105.

[44] RAMANUJAN A, KRITHIVASAN K. Control languages associated with spiking neural P systems[J]. Romanian Journal of Information Science and Technology, 2012, 15 (4): 301-318.

[45] PAN L, WANG J, HOOGEBOOM H J. Limited asynchronous spiking neural P systems[J]. Fundamenta Informaticae, 2011, 110 (3/4): 271-293.

[46] SONG T, PAN L, JIANG K, et al. Normal forms for some classes of sequential spiking neural P systems[J]. IEEE Trans NanoBioscience, 2013, 12 (3): 255-264.

[47] WANG J, SHI P, PENG H, et al. Weighted fuzzy spiking neural P systems[J]. IEEE Transactions on Fuzzy Systems, 2013, 21 (2): 209-220.