剑灵正太:神经网络中的约束满足，怎样才算是满足，怎么算是没有满足呢

约束满足神经网络
摘 要：针对一般人工神经网络不能用于求解包含矛盾的约束满足问题(CSP)的不足，本文依据神经网络的逻辑分析理论，提出了一个约束满足神经网络(CSNN).CSNN体现了生物神经系统中的突触的控制原理，它由一个基本神经网和一个控制系统组成；基本网的作用是提供必要的约束，控制系统的作用不但能使约束成为自适应的，而且依据具体问题能够动态地、自动地删除基本解中的矛盾.
关键词：神经网络；约束满足问题；约束满足神经网络；逻辑分析
A Constraint Satisfaction Neural Network
GUO Bao-long
（Dept.of Measurement Control and Instrument,Xidian University,Xi'an 710071,China;）
GUO Lei
（Dept.of Automatic Control,Northwest Polytechnic University,Xi'an 710072,China）
DAI Guan-Zhong
（Dept.of Automatic Control,Northwest Polytechnic University,Xi'an 710072,China）
Abstract：Although the operating of a general artificial neural network (NN) can eliminate the superior contradiction,its solution still contains the inferior contradiction〔8～11〕 which is unacceptable for actual problems such as the constraint satisfaction problems (CSPs) that contain contradictions.For this reason,a constraint satisfaction neural network (CSNN) based on the logical analytic theory of NNs is presented,which is composed of a general neural network named a basic network and a control system which has the adaptability to cope with complex problems.The former provides the necessary constraints and the latter gives the closed-open control for the constraints inside the basic network.Since contradictions in many natural problems are often inevitable,the property of the CSNN is of great significance for intelligent problems.
Key words：neural networks;constraint satisfaction problems;constraint satisfaction neural networks;logical analysis▲
1 引言
已知变量集合有N个变量，要求在限定的取值范围内给各变量赋值，使其满足N个变量之间存在的相互约束〔1，2〕.这是一个基本的约束满足问题(CSP)，求解CSP的约束满足网络(CSN)在人工智能中是十分重要的〔3〕，但CSN的解不能包含任何矛盾(否则无解).然而，很多智能问题是包含矛盾的CSP，因为这类问题中包含有大量的局部判决和弱约束，例如，运动判决问题〔4〕和边界检测问题〔5，6〕，局部判决的模糊性必然导致判决与约束产生矛盾〔5～8〕.虽然稳定神经网的运行能消除优势矛盾〔8～11〕，但基本解中包含的劣势矛盾对于实际问题往往是不可接受的(尤其是当矛盾的范围很大时).所以一般的神经网要经过改良成为约束满足神经网(CSNN)才能用于复杂问题的求解.改良的重要方法之一是：使约束对判决是否发挥作用成为可控制的.本文依据建立的神经网络逻辑分析理论〔8～11〕和生物突触的控制原理，提出了一个约束满足神经网，它由一个基本神经网和一个控制系统组成；控制系统不但能使约束成为自适应的，而且依据具体问题能够动态地、自动地删除基本解中的矛盾.CSNN的特点是适合于求解包含矛盾的智能问题.
2 神经网络的逻辑分析理论
设连续状态神经网络模型为
式中pi对应神经元i的模势叫作基本状态，si是输出状态(称作现实)：si=g(pi)，g(x)=tanh(ax),a＞0，wij(sj)=tijsj,tij是实数.
定义1 规则函数wij(sj)是规则类型函数rij、规则强度Aij(Aij≥0)和模糊状态函数Hij(sj)的乘积：
(2)
规则类型函数rij是一个逻辑函数，它的定义域是{On,Off}，值域是{Y,N}，有9种类型〔9，10〕.表1给出了4种基本规则的神经实现，其中
表1 四种规则的实现方案
sgn(x)=1,x＞0;sgn(x)=-1,x＜0
规则类型 类型函数r(x) 线性函数H(x) 状态值
Ⅰ r(x)=Sgn(x) H(x)=x 1≥x≥-1
Ⅱ r(x)=-Sgn(x) H(x)=x On=正值
Ⅲ r(x)=1 H(x)=(1+x)/2 Off=负值
Ⅳ r(x)=-1 H(x)=(1+x)/2 Y=1,N=-1
定理1 si的输出状态总是沿着删除动态矛盾的方向变化.
定理2 判决元输出状态的变化 总是为了减少该判决的优势逻辑矛盾.
定义2 定义CM和SC分别为网络的总矛盾测度和网络的优势矛盾测度：
(3)
式中阶跃函数U(x)=0,x＜0，U(x)=1,x≥0.
定理3 所有判决元的输出状态不再变化的必要条件是SC=0.
3 CSNN的控制原理和控制策略
引理(约束控制的基础) 若令规则强度是零，即：Aij=0，这等价于使连接断开，则该规则所有的一致和矛盾测度是零：DIij=0,DCij=0,LIij=0,和LCij=0.
令Aij=ρijaij，其中aij是实际的规则强度，Aij是等效的规则强度，且ρij是受控系数：如果连接wij被断开，那么ρij=0，否则ρij=1.
定义3 当给定一个外部输入后，约束满足神经网的解叫作特解，定义为当基本网的总矛盾测度CM=0时基本网内所有判决元给出的结论(逻辑状态On/Off).
假设基本网是一个稳定的网；那么，怎样实施连接的开关控制而不破坏该网的稳定性呢?下文将表明：矛盾分析是解决该问题的一个有效方法.
Shephered等人发现〔13，14〕真实神经系统中存在着突触受控机制.依据这种突触的受控机制，我们提出如下连接的控制结构模型(图1).
图1 连接的控制结构
定义4 (门限控制器CT，见图1)：假设v是CT的输出，u是CT的输入，p是控制信号，T是门限，则有V=u,p＞T，V=0，p?T.
约束的控制原理(假设检验)：
?在接收外部输入之前，一个约束是否合理是不清楚的.因此基本网中的所有连接最初是关闭的(ρij(0)=1).
?在神经网的运行过程中，如果一个推理与现实是矛盾的且网的运行不能删除该矛盾，那么这个推理被认为是不合理的，应被取消.
?在神经网的运行过程中，如果一个推理与现实是一致的且随着网的运行该一致性不会消失，那么这个推理被认为是合理的，应予以保留.
一致和矛盾均具有两种类型：动态的和逻辑的.为方便令BI=(DI,LI)表示一个规则的动态一致和逻辑一致的组合；令BC=(DC,LC)是一个规则的动态矛盾和逻辑矛盾的组合.用1和0分别表示一致或矛盾的存在与不存在.例如，BI=(0,1)和BC=(1,0)表示存在动态矛盾和逻辑一致.BI和BC共有如下4种可能的情况：
Case 1:BI=(0,0)且BC=(1,1)：存在动态矛盾的逻辑矛盾，且网的运行使该矛盾增强；
Case 2:BI=(0,1)且BC=(1,0)：存在动态矛盾和逻辑一致，且网的运行使逻辑矛盾出现；
Case 3:BI=(1,0)且BC=(0,1)：存在逻辑矛盾和动态一致，且网的运行将消除逻辑矛盾；
Case 4:BI=(1,1)且BC=(0,0)：存在逻辑一致和动态一致，且网的运行不会使任何矛盾出现.
上述各种情况是动态的，没有考虑dsi/dt=0的情况.
为了更清楚地解释上述4种情况，我们考虑判决元输出状态的所有可能的情况.
图2表示了4种情况，其中箭头表示输出状态的当前位置和变化的方向.不难看出：在b和c时，判决元现有的逻辑状态将改变；但在a和d时逻辑状态将不改变.
图2 输出状态的4种情况
表2给出了当rij分别为Y和N、si分别为图2的4种情况时，推理wij与现实si之间的一致和矛盾的优劣势状况.
依据上述讨论，给出如下的控制策略：
(1)如果BI=(0,0)且BC=(1,1)，即Case 1，则取消wij(令ρij=0)对si的贡献；
(2)如果BI=(0,1)且BC=(1,0),即Case 2，则不实施任何控制，因为推理wij正从Case 2向Case 1转换；
(3)如果BI=(1,0)且BC=(0,1)，即Case 3，则不实施任何控制，因为推理wij正从Case 3向Case 4转换；
(4)如果BI=(1,1)且BC=(0,0)：即Case 4,则保留或恢复wij(令ρij=1)对si的贡献.
表2 推理rij与现实si之间的关系
注：其中si分别为图2的4种情况，rij分别为Y和N时，S和N分别表示优势和劣势，1表示(一致和矛盾)存在.
定义5
(4)
是网络的逻辑关系测度.
LR的增加意味着逻辑一致测度j的增加或者逻辑矛盾测度的下降.
定理4 上述控制策略总是使基本网逻辑关系测度增加.
比较起来，当网中所有规则函数的形式均为wij(sj)=Aijsj，网络的逻辑关系测度恰好是Hopfield给出能量函数负值〔15〕：
(5)
由定理5可知这些控制策略总是使能量函数下降.类似地可得：
推论 这些控制策略总是使基本网的矛盾测度CM非增.
定理5 控制策略不改变基本网中判决元输出状态的变化方向.即控制策略不改变判决元当前的逻辑状态(即不破坏一个稳定网的稳定性).
4 CSNN的网络结构和数学描述
CSNN的计算结构如图3所示，由一个基本约束网(图中的下半部分)和控制系统(图的上半部分)组成.基本网包含N个单元(unit);每个单元在M个可能取值中完成一个选择，包含M个判决元(神经元)，每个判决元决定一个可能取值是否能够发生.因此基本网共有N×M个判决元.例如在视觉计算问题中，N表示边界(或运动)检测器的数目，M表示可能的边界定向(或运动参数)的数目〔4～7〕.图3中的一个圆表示一个判决元，一列圆组成一个单元.为简单，该图仅表示基本网的一部分.基本网接收外部输入，控制系统接收基本网的信息且将控制信号送回到基本网中.
图3 网络的基本结构
上部分为控制系统，下部分为基本网.圆圈表示神经元；连接表示推理；白色箭头表示类型Ⅰ，黑色箭头表示类型Ⅲ.
令dij表示基本网中第i个单元中的第j个判决元，pij、sij和eij分别表示它的基本状态、输出状态和逻辑变量.eij=On表示第i个单元的第j个可能发生，eij=Off表示不发生.该网的数学描述为：
(6)
sij=g(pij),wij,kj(skj)=wkj,ij(sij),fij,il(sil)=wil,ij(sij),Iij表示判决元dij接收的外部输入，wij,kj中的推理强度Aij,kl表示第i个和第k个单元之间的相关强度.
因为dij和dkj(k≠i)表示两个单元在同一取值的判决，在方程(6)中它们之间的双向推理wij,kj和wkj,ij的规则是类型Ⅰ，在图3中用白色箭头表示.因每个单元仅能选择一个取值，所以在dij和dil之间的双向推理fij,il和fil,ij(j≠1)的规则类型是Ⅳ，在图中用黑色箭头表示.
控制系统是为了取消单元之间引起矛盾的约束关系，其工作方式是：首先检测基本网中不同的单元之间的一致和矛盾，然后基于控制策略决定是否取消那些约束.
控制系统有N(N-1)/2个神经元(称为控制元)，qik,i=1,2,…,N,i＜k，其中i和k分别对应不同的单元，如图3所示.神经元qik接收第i个和第k个单元之间的一致和矛盾信息，一致关系是对qik的逻辑状态为On的贡献；矛盾关系是对qik的逻辑状态为Off的贡献.qik从基本网接收的输入为
(7)
其中Dij,kj和Cij,kj分别是dij和dkj之间的一致和矛盾测度，且i＜k.
依据控制策略(4)，一致测度是：如果wij,kj(skj)是动态一致推理，且dij和dkj的逻辑状态都是On，则 (8)

依据控制策略(1)，矛盾测度是：如果wij,kj(skj)是动态和逻辑矛盾推理，则
(9)

如果两个控制元是直接相邻的(见方程(10))，那么在它们之间存在对称的双向推理(见图3)，规则类型是Ⅳ.设uik和zik分别是qik的基本状态和输出状态，则 (10)

其中zik=g(uik),tik,kh=tkh,ik,i＜k,l＜k,k＜h,m＜i.
qik的状态作为直接的控制信号送回到基本网.控制规则是：
断开规则：如果zik＜-0.5，则第i个和第k个单元之间的所有连接被断开；
闭合规则：如果zik＞0.5，则第i个和第k个单元之间的所有连接被闭合.
在式(6)中，wij,kj(skj)=ρijαij,kjskj,fij,il(sil)=-(sil+1);在式(8)和(9)中，aij,kj=1;在式(10)中，tik,kh(zkh)=0.25(zkh+1),η=0.05，ζ=20；在式(6)和(10)中，g(x)=tanh(0.2x).我们以开会问题(时间判决)为例进行计算机模拟，验证了CSNN的原理.
5 讨论
矛盾分析能够引出这样的观点：神经系统应当是高度自适应的大规模控制系统；矛盾测量能够提供有用的控制信息；自适应控制使它具有动态结构，能够应付变化和复杂的外部环境.本文分析了CSNN的基本原理，给出了简单情况下的控制策略，表明了控制的目的是消除矛盾并求出问题的解.然而，控制策略除了开关控制外还有强度的控制，开关控制是最极端的强度控制，不能体现程度的变化，通常仅适用于比较简单的情况；强度控制可采用矛盾测度为控制源的模糊控制方法.另外，实际问题往往涉及多个因素，往往需要综合决策，既要求强度控制也要求在一定条件下的开关控制.此外，文中的绝对等量划分原则应结合实际情况加以改进，例如通过引入门限指标.
在传统人工神经网络的理论中，对连接的控制机制没有给予应有的重视；但是在生物系统中确实存在着突触的开关控制机制〔13，14〕，可它的逻辑意义是不清楚的，本文试图通过CSNN解释其逻辑意义.本文之所以强调动态控制是为了消除网内的矛盾，从而解决包含矛盾的实际问题.很明显，在多数自然问题中矛盾总是存在的，无矛盾仅是理想情况.CSNN的一个明显特征是：它是自己理解问题.■

基金项目：国家自然科学资助课题，国家高技术计划（863）资助课题
作者简介：郭宝龙 1984年毕业于西安电子科技大学，博士，教授，AAAS国际会员，中国电子学
会高级会员；主要研究领域：神经网络与模式识别，智能信息处理与智能系统，机器
人与智能计算机.
郭雷 见本期第38页.
戴冠中 1960年毕业于哈军工，西北工业大学教授，博士导师，目前为校长.主要研
究领域：复杂系统的控制与通信，计算机控制与智能控制，并行处理与并行计算机.
作者单位：郭宝龙（西安电子科技大学测控工程与仪器系，西安 710071）
郭雷（西北工业大学自动控制系，西安 710072）
戴冠中（西北工业大学自动控制系，西安 710072）

参考文献：

〔1〕L.M.Kirousis.Fast parallel constraint satisfaction.Artificial Intelligence,1993,64:147～160
〔2〕Thagard,K.J.Holyoak,G.Nelson,D.Gochfeld.Analog retrieval by constraint satisfaction.Artificial Intelligence,1990,46:259～310
〔3〕U.Montanari,F.Rossi.Constraint relaxation may be perfect.Artificial Intelligence,1991,48:143～170
〔4〕郭雷，郭宝龙.基于关联性神经推理的运动判决原理.计算机学报，1995，18(3)：225～230
〔5〕S.Grossberg,E.Mingolla,D.Todorovic.A neural network architecture for preattentive vision.IEEE Transactions on Biol.Med.Eng.,1989,BME-36:65～84
〔6〕郭宝龙，郭雷.用扩散集中神经网络区分图形与背景.科学通报，1994，39(19)：1805～1808
〔7〕郭雷，郭宝龙.视觉神经系统与分布式推理理论.西安电子科技大学出版社，1995
〔8〕B.L.Guo,L.Guo.Inference and contradictory analysis for binary neural networks.Science in China (Series E),1996,39(1):11～16
〔9〕郭宝龙，郭雷.神经网络稳定性的逻辑分析.电子学报，1996，24(11)：1～5
〔10〕郭宝龙.神经网络的分布式逻辑推理研究.博士学位论文.西安电子科技大学，1995
〔11〕郭宝龙，郭雷.神经网络的逻辑分析.电子科学学刊，1996，18(6)：11～16
〔12〕T.J.Sejnowski,P.K.Kienker,G.E.Hinton.Learning symmetry groups with hidden units:Beyond the perceptorn.Physica,1986,22D:260～275
〔13〕G.M.Shephered.The significance of real neuron architectures for neural network simulations.in Computational Neuraoscience,E.L.Schwartz (ed.),MIT Press,1990:82～95
〔14〕P.Greengard,F.Valtorta,A.J.Czernik,F.Benfenati.Synaptic vesicle phosphoproteins and regulation of synaptic function.Science,1993,259:780～785
〔15〕J.J.Hopfield.Neurons with graded response have collective computational properties like those of two-state neurons.Proc.Natl.Acad.Sci.USA,1984,81:3088～3092