【文摘】数学家俱乐部

一个数学家俱乐部中有有限位数学家,他们中有些人相互是朋友。他们每周聚会一次,每人会喝一杯茶或一杯咖啡。第一次聚会时,他们都会选择自己喜欢的那一种,从第二个星期开始,他们会按照以下的规则选择自己的饮料:
(1)他能准确回忆起上次聚会他的朋友们分别喝的是什么饮料,他会选择多数朋友选取的那种饮料。
(2)如果选择两种饮料的朋友人数相同,他会挑自己喜欢的那种饮料。

证明:所有人的选择都最终会是周期循环,且循环周期为1或2。

数学趣题汇编
牛顿:在海边寻找贝壳的人
凯尔文:是上帝创造了生命,并且掌管一切
陆地动物能变成鲸吗
数学界的奇人妙事

Conway: 游戏人生
有关孪生素数的一个有趣猜想
素数之恋-伯恩哈德·黎曼
等分布理论简介
数学家波利亚
物理学之神奇的数
鸟和青蛙

数学家俱乐部问题的解答:

这个问题的来源其实是神经网络理论中的一个命题
问题等价于下述命题:
用加权无向图表示离散hopfield神经网络(DHNN),图的每一边都附有一权值,图的每个节
点(神经元)都附有一阈值,网络的阶数相应于图中结点的个数。设N是一n阶神经网络,
则N由(W,θ)唯一的定义,其中:
W是一n*n对称零矩阵,其中W(i,j)为附加给边(i,j)的权;
θ是一n维向量,θ(i)表示节点i的阈值。
每个节点可处于两个可能的状态之一即1或-1,以X(i,t)表示t时刻节点i的状态,
向量X(t)是神经网络N在t时刻的状态,节点的下一状态由下列规则决定:
1 若H(i.t)>=0
X(i,t+1)=sgn(H(i,t))={ (4.1)
-1 若其它
     n
这里H(i.t)=Σ W(i,j)X(j,t)-θ(i) (4.2)
j=1
由上述可知,整个网络的状态是向量X(t)∈{1,-1}^n
若W(i,i)=0 (i=1,2,3……,n) 称相应的模型为无自反馈的网络,否则称其为有自反馈的。
神经网络(4.1)有如下两种工作方式:
(1)串行(异步)方式:
在任意时刻t,只有某一个神经元i(随机或确定的选择)依(4.1)式变化,而其余n-1
个神经元保持不变 即:
X(i,t+1)=sgn(H(i,t)) (4.3)
X(j,t+1)=X(j,t) 对于任意的j不等于i (4.4)
(2)并行(同步)工作方式:
在任意时刻t,部分神经元依(4.1)式改变状态,其中最重要的一种特殊情况为:在任意
时刻t,所有神经元同时依照(4.1)式改变状态,即
X(i,t+1)=sgn(H(i,t)) 对于任意的i
这种重要类型我们称为全并行模式
若神经网络从t=0的任一个初始状态X(0)开始,而在某一个有限时刻t,从此刻以后神经网络
不再发生变化,即
X(t+Δt)=X(t) Δt>0
则称网络(4.1)是稳定的,并称串行方式下的稳定性为串行稳定性,并行方式下的稳定性为并
行稳定性。
下面证明下列定理
1.Hopfield:如果N工作在串行模式,W的对角元素非负(包括为0的情况),则网络4.1总是
收敛于稳定状态(即在状态空间没有极限环存在);
2.Goles 如果N工作在全并行模式,网络(4.1)总是收敛于稳定状态或是Hamming距离小
于2的极限环
证明:对应于串行工作方式和全并行工作方式,分别定义其能量函数为
E(1,t)=(X^T(t))WX(t)-((X(t)+X(t))^T)θ (4.8)
E(2,t)=(X^T(t))WX(t-1)-((X(t)+X(t-1))^T)θ (4.9)
由(4.1)和(4.8)式,令
ΔE(1)=E(1,t+1)-E(1,t) (4.10)
ΔX(k)=X(k,t+1)-X(k,t) (4.11)
显然
0 X(k,t)=sgn(H(k,t))
ΔX(k)={ -2 X(k,t)=1,sgn(H(k,t)=-1 (4.12)
2 X(k,t)=-1,sgn(H(k,t)=1
对于任一节点k(即任一神经元k)
ΔE(1)=ΔX(k)(Σ W(k,j)X(j)+Σ W(i,k)X(i))+W(k,k)ΔX(k)^2-2ΔX(k)θ(k)
j i
(4.13)
由W的对称性和(4.2)式有
ΔE(1)=W(k,k)ΔX(k)^2+2ΔX(k)H(k)
因为 ΔX(k)H(k)>=0和W(k,k)>=0

ΔE(1)>=0 对每一k
因此E(1)是有上界的,能量函数(4.8)将收敛。
1.如果ΔX(k)=0,则有ΔE(1)=0
2.如果ΔX(k)不等于0,仅当X(k)从-1变到1且H(k)=0时有ΔE(1)=0。
从而网络(4.1)式至多进行n^2次时间迭代即可收敛到稳态。
类似的,可以由(4.9)给出的能量函数证明全并行工作时的稳定性。

其他参考解答

扫码关注<博物思源>公众号,更多期待,更多精彩…
此条目发表在数学, 游戏, 程序开发分类目录,贴了, , , , , 标签。将固定链接加入收藏夹。