《A system hierarchy for brain-inspired computing》笔记一:类脑计算完备性和POG
# 通用逼近器(Universal Approximator)和通用逼近理论(Universal Approximation Theorem)
通用逼近理论:对于足够大的、由两层的神经网络和一个ReLU非线性层组成的网络(即y=ReLU(wTx+b,0)),可以通过合理设定参数矩阵来近似所有的连续函数或者各种其他函数 [Hornik et al., 1989, Cybenko, 1992,Barron, 1993]。
对比高等数学在讲无穷级数之前引入的Stone-Weierstrass第一定理:
- 闭区间上的连续函数可用多项式级数一致逼近
和讲傅里叶级数之前引入的Stone-Weierstrass第二定理:
- 闭区间上周期为2π的连续函数可用三角函数级数一致逼近
它们分别证明了多项式函数和三角函数在函数空间内的稠密性;而通用逼近理论则证明了类似ReLU的阶梯函数在函数空间内的稠密性。基于这种稠密性构建的通用逼近器计算式y=ReLU(wTx+b)就是现在所有神经网络的基础。
# Neuromorphic Computing Capability 类脑计算能力
通用逼近器y=ReLU(wTx+b)的核心目标是“逼近”,它的计算能力由它的逼近精度决定。
若存在两个可以生成函数的系统A和B,将A能生成的所有函数的集合记为SA、将B能生成的所有函数的集合记为SB,即:
SASB={f(x)∣f(x)是由A产生的函数}={f(x)∣f(x)是由B产生的函数}
若以D(f)表示函数的定义域,则类脑计算的计算能力可以表述为:
A系统的类脑计算能力等于或强于B系统:=(∀ε≥0)(∀fA∈SA)(∃fB∈SB)(∀x∈D(fA))∣∣fA(x)−fB(x)∣∣≤ε
# Neuromorphic Complete 类脑计算完备性
A系统是类脑计算完备的:=A系统的类脑计算能力等于或强于图灵完备系统
# 图灵完备系统和通用逼近器的类脑计算完备性
- 证明图灵完备系统是类脑计算完备的:
- 图灵完备系统的系统的类脑计算能力等于它自身
- 因此图灵完备系统是类脑计算完备的
- 证明通用逼近器是类脑计算完备的:
- 图灵完备系统所能生成的函数是图灵可计算函数
- 通用逼近器生成的函数能以任意精度逼近任意函数
- 通用逼近器生成的函数能以任意精度逼近图灵可计算函数
- 通用逼近器的类脑计算能力大于或等于图灵完备系统
- 因此通用逼近器是类脑计算完备的
# 图灵完备系统和通用逼近器的可组合性
In computer science, function composition is an act or mechanism to combine simple functions to build more complicated ones. Like the usual composition of functions in mathematics, the result of each function is passed as the argument of the next, and the result of the last one is the result of the whole. ——Wikipedia
可组合性是指将两个简单的函数f(x)、g(x)组合成f(g(x))就能表示更加复杂的函数的过程。
对于图灵可计算函数的组合相当于将一个图灵机停机后的字符串作为另一个图灵机开始的字符串,这样的组合可以产生更加复杂的函数(相当于增加了图灵机的规则,使图灵机的计算能力更强)。
而对于通用逼近器,想要逼近更加复杂的函数或提高逼近的精度,则需要增加层中的神经元数量(即在y=ReLU(wTx+b)中扩展w的长度);而f(g(x))是增加了神经网络的层数。因此,通用逼近器组合无法产生更加复杂的函数,不具备可组合性。
# Programming Operator Graph (POG)
# FSOG(Finite State Operator Graph, 有限状态操作图)形式定义
FSOG为一个五元组ψ:
ψ=(G,T,δ,q0,F)
- G:操作图,G=(V,E)
- 边ev1,v2∈E表示Operator v1的一个或多个数据事件需要传递给v2,也可以看作是v1和v2间的数据依赖关系
- 点v∈V表示一个Operator,当v和其他所有点的依赖关系被满足时,就可以开始计算
- T:事件集合
- 数据事件td:i=v∈T:用于传输计算所需的输入数据,v表示一个字符串
- 触发事件ts∈T:不包含数据,仅用于表征Operator间的依赖关系
- δ:状态转移函数,δ:2T×E→2T×E
- q0:初始状态,q0∈2T×E
- F:终结状态集(接受状态集),F⊆2T×E
# FSOG的瞬时描述(状态详解)
按照自动机理论的一般视角,FSOG的有限状态集Q=2T×E,其中的每一个状态(也即瞬时描述):
q={(t,e)∣t∈T∧e∈E}∈Q
表示一系列事件与操作图中边的对应关系,状态中的对应关系(t,ev1,v2)∈q表示事件t在边ev1,v2上被触发了,也同时表明v1和v2之间执行的依赖关系已经满足。
# 定义FSOG的动作(状态转移函数详解)
FSOG状态转移函数可以看作是操作图中所有Operator的状态转移函数的集合:
δ={fv∣fv:2T×{evi,v∈E∣vi∈V}→2T×{ev,vo∈E∣vo∈V},v∈V}
其中每个Operator v的状态转移函数fv就是一个输入边上的状态(事件-边元组的集合)Iv⊆T×{evi,v∈E∣vi∈V}到输出边上的状态Ov⊆T×{ev,vo∈E∣vo∈V}的映射Ov=fv(Iv)。由于fv是离散的状态转移函数,因此它也可以看成是一系列状态转移规则的集合Δv:
Δv={Iv→Ov∣Ov=fv(Iv)}
在状态转移过程中,只有所有输入条件全部满足(即每个相连的输入边上都有事件触发)的Operator才能进行状态转移,这些Operator称为“使能”的Operator。在某个状态q中所有使能Operator的集合可以表示为:
Venabled(q)={v∣(∀vi∈V∧evi,v∈E)(∃t∈T)(t,evi,v)∈q}
进而可以将状态转移函数δ表达为:
δ(q)=v∈Venabled(q)⋃fv({(t,evi,v)∣vi∈V∧(t,evi,v)∈q})
# POG 扩展操作
除上文所述的 POG 的状态转移操作外,POG 还提供了一些扩展操作,这些操作可以由基本操作组合而来,因此包含这些扩展操作的POG与原始POG是等价的。
使用 POG 扩展操作可以帮助开发人员更快速有效地构造 POG。
# 带参数更新器(Parameter Updater)的POG
带参数更新器的FSOG为一个五元组ψ:
ψ=(G,T,δ,q0,F)
- G:操作图,G=(V,E,P)
- 点v∈V和边ev1,v2∈E含义同上
- P是Operator的参数列表,v的参数P[v]表示一个只有Operator v才能访问和修改的符号串
- 设P所有可能的取值情况集合为P,P∈P
- 设参数符号集为ΣP,P[v]∈ΣP∗
- T:事件集合
- 数据事件td:i=v含义同上
- 参数更新事件tu:p=x表示将该边所连接的点的参数修改为x
- δ:状态转移函数,δ:2T×E×P→2T×E×P
- q0:初始状态,q0∈2T×E×P
- F:终结状态集(接受状态集),F⊆2T×E×P
# 带参数更新器的FSOG的瞬时描述(状态详解)
显然,加入参数更新器后,每个Operator都是有状态的了,每个Operator与一个状态对应,表示为一个二元组(v,p)∈P,进而FSOG的状态可以表示为:
q=2T×E×P
# 定义带参数更新器的FSOG的动作(状态转移函数详解)
加入参数更新器后,状态转移函数不仅需要更新边上触发的事件,还需要更新Operator中的状态符号串,因此Operator状态转移函数的集合定义为:
δ={fv∣fv:2T×{evi,v∈E∣vi∈V}×ΣP∗→2T×{ev,vo∈E∣vo∈V}×ΣP∗,v∈V}
同理,其中的fv可以看成是转移规则的集合Δv:
Δv={(Iv,p)→(Ov,p′)∣(Ov,p′)=fv(Iv,p)}
使能Operator的集合Venabled(q)的定义不变,状态转移函数δ表达为:
δ(q)(qt,e(v),P′[v])=(v∈Venabled(q)⋃qt,e(v),P′)其中,=fv({(t,evi,v)∣vi∈V∧(t,evi,v)∈q},P[v])
# 证明包含参数更新器的POG与原始POG等价
可以使用仅包含状态转移操作的Operator v模拟具有参数更新器的Operator:
- v有一条指向自身的边ev,v,将需要更新的参数作为数据事件td:i=x其上传递
- v有一条用于更新参数的状态转移规则:
{(tu:p=x,ev′,v),(td:i=p,ev,v)}→{(td:i=x,ev,v)}∈Δv
其中,v′是通过ev′,v向v发送参数更新事件的Operator。
显然,此Operator v等价于一个带有参数更新器的Operator。因此包含参数更新器的POG与原始POG等价。
# Control-Flow Operator 流程控制Operator
流程控制Operator是用于模拟一般编程语言中的IF操作,它包三种Operator:Decider、Conditional Merger和True/False gates
# Decider
Decider根据情况选择将输入的数据输出到哪条边。它有两条输入边和两条输出边:
- 输入边evi,v用于接收数据
- 输入边evc,v用于接收True/False
- 当evc,v收到事件td:condition=True时,将收到的数据输出到输出边ev,vt
- 当evc,v收到事件td:condition=False时,将收到的数据输出到输出边ev,vf
使用基础Operator模拟Decider时,其状态转移规则形式化表述为:
Δv={{(td:i=x,evi,v),(td:condition=True,evc,v)}{(td:i=x,evi,v),(td:condition=False,evc,v)}→{(td:i=x,ev,vt),(ts,ev,vf)},→{(ts,ev,vt),(td:i=x,ev,vf)}}
# Conditional Merger
Conditional Merger根据情况选择将哪条边的输入数据输出到输出边。它有三条输入边和一条输出边:
- 输入边evt,v、evf,v用于接收数据
- 输入边evc,v用于接收True/False
- 当evc,v收到事件td:condition=True时,将evt,v收到的数据输出到输出边ev,vo
- 当evc,v收到事件td:condition=False时,将evf,v收到的数据输出到输出边ev,vo
使用基础Operator模拟Conditional Merger时,其状态转移规则形式化表述为:
Δv={{(td:i=xt,evt,v),(td:i=xf,evf,v),(td:condition=True,evc,v)}{(td:i=xt,evt,v),(td:i=xf,evf,v),(td:condition=False,evc,v)}→{(td:i=xt,ev,vo)},→{(td:i=xf,ev,vo)}}
# True/False gates
True/False gates根据情况选择是否让输入数据通过。它有两条输入边和一条输出边:
- 输入边evi,v用于接收数据
- 输入边evc,v用于接收True/False
- 对于True gate:当evi,v收到事件td:condition=True时,将收到的数据输出到输出边ev,vo,否则输出ts
- 对于False gate:当evi,v收到事件td:condition=False时,将收到的数据输出到输出边ev,vo,否则输出ts
使用基础Operator模拟True gate时,其状态转移规则形式化表述为:
Δv={{(td:i=x,evi,v),(td:condition=True,evc,v)}{(td:i=x,evi,v),(td:condition=False,evc,v)}→{(td:i=x,ev,vo)},→{(ts,ev,vo)}}
使用基础Operator模拟False gate时,其状态转移规则形式化表述为:
Δv={{(td:i=x,evi,v),(td:condition=True,evc,v)}{(td:i=x,evi,v),(td:condition=False,evc,v)}→{(ts,ev,vo)},→{(td:i=x,ev,vo)}}
# Synapse 突触操作器
In POG, typical operators are enabled when all the input tokens are satisfied. But in most neuromorphic models, the neuron may have input connections from many other neurons and its internal states should be updated every time a spike arrives.
因此,为了更好地表示这些操作,我们需要一个能执行类似操作的Operator,称为Synapse:
- Synapse v有n个输入边evi,v,i∈[1,n]
- Synapse是一个带参数更新器的Operator,其参数P[v]是一个长度等于输入边数量n的列表
- Synapse的输出为所有输入边的有效输入td:i=xi的数据xi与边对应参数P[v]的加权和
状态转移规则形式化表述为:
Δv={{(ti,evi,v)∣i∈[1,n],evi,v∈E}→{(td:i=∑i∈[1,n]ti=tsxiP[v]i,ev,vo)}}
# Composability 可组合性
As the operator of the POG may contain complicated instructions or even a whole algorithm, a sub-OG can be viewed as an operator.
此功能称为可组合性,对于编程便利性很重要,因为不同的硬件实现可能会为硬件操作员提供多粒度的功能:可以将神经网络应用描述为 一个仅包含基本计算和控制流运算符的OG,然后将该OG的某些子图组成新的运算符,以适应多粒度硬件操作。 因此,描述为POG的应用程序可以不经修改就适合不同的硬件。
从软硬件协同设计的角度来看,此属性也非常有用:我们可以根据底层硬件提供的特定操作来自定义编程操作员集,反之亦然。 由于可组合性,这些修改只能出现到POG级别,而不会影响上层编程范例。
# POG 图灵完备性
要证POG图灵完备性,只要构造一个模拟图灵机的POG即可:
其中各部分详解如下:
# 模拟图灵机输入带
使用一个带参数更新器的Operator vtape模拟图灵机的输入带T,该Operator包含一个模拟输入带的无限长字符串T和记录读头位置的整数i:P[vtape]=(T,i),T∈Γ∗,i∈Z,其输入边有两个:
- evTMhead,vtape上传递的事件为图灵机的读头位置移动方向td:head=m,m=±1。输入读头位置返回移动后对应位置处的参数值Ti
- evTMupdate,vtape上传递的事件为更新图灵机输入带上当前位置的值tu:p=c。输入当前参数的修改事件修改参数Ti=c
综合得其状态转移规则为:
({(td:head=m,evTMhead,vtape),(tu:p=c,evTMupdate,vtape)},(T,i))→({(td:data=Ti+m′,evtape,vTM)},(T′,i+m))其中Ti′=c
# 模拟图灵机
使用一个带参数更新器的Operator vTM模拟图灵机,该Operator包含一个模拟状态的参数P[vtape]=q∈Q,其输入边是与输入带Operator相连的evtape,vTM,用于接收输入带上的值。其输出边就是控制输入带活动的evTMhead,vtape和evTMupdate,vtape。
对于图灵机状态转移规则集合Δ中的每个规则(q,X)→(q′,X′,D),都可以写出对应的POG状态转移规则:
D=L时:
({(td:data=X,evtape,vTM)},q)→({(tu:p=X′,evTMupdate,vtape),(td:head=+1,evTMhead,vtape)},q′)
D=R时:
({(td:data=X,evtape,vTM)},q)→({(tu:p=X′,evTMupdate,vtape),(td:head=−1,evTMhead,vtape)},q′)
# 接受状态
为了模拟接受状态F,还需要给vtape和vTM各加一条出边连到一个用于判断接受状态的Operator vF中,如果vTM进入接受状态,则输出vtape中的参数T,否则不输出。因此有状态转移规则:
{(td:state=q∈F,evTM,vF),(td:tape=T,evtape,vF)}→{(td:tape=T,eo)}