128
个编辑
更改
跳到导航
跳到搜索
第320行：
第320行： − + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
将从联合和条件熵翻译至定义十（ϵ-机制重构）
给定一个从可数集合中取值的随机变量X，X的熵是
给定一个从可数集合中取值的随机变量X，X的熵是
H[X]=-Σx属于AP(X=x)logxP(X=x), (5)
<math>
H [X] \equiv - \sum_{x \in \mathcal A } P(X = x)\log_{2}P(X = x). \tag {5}
</math>
加入 0log0 = 0。注意到H[X]是-log2P(X=x)的期望值，而且测量单位是信息比特。特别注意“当和收敛到有限值”的形式在所有状态中是隐性的，这些关于熵的状态出自可数集A。
加入 0log0 = 0。注意到H[X]是-log2P(X=x)的期望值，而且测量单位是信息比特。特别注意“当和收敛到有限值”的形式在所有状态中是隐性的，这些关于熵的状态出自可数集A。
香农将H[X]表示成X的不确定度。（这些对任何主观部分的猜疑，比如“不确定”的观念，可以就地读作“实现变量”。）他展示了，比如，H[X]是对和错问题数量的均值，这些问题需要在重复实验中能选定X的值，如果这些问题被选中去最小化这个平均值【55】。
香农将H[X]表示成X的不确定度。（这些对任何主观部分的猜疑，比如“不确定”的观念，可以就地读作“实现变量”。）他展示了，比如，H[X]是对和错问题数量的均值，这些问题需要在重复实验中能选定X的值，如果这些问题被选中去最小化这个平均值【55】。
2.联合和条件熵
2.联合和条件熵
我们以直观的方式定义两个变量X（从A中取值）和Y（从B从取值）的联合熵H(X, Y) ，
H[X, Y] = - ∑(x,y)属于A x B P（X = x, Y = y）log2 P(X = x, Y = y)。（6）
我们定义一个随机变量的条件熵H(X|Y)，是在已知Y值的情况下，得到的条件熵
H[X|Y] = H[X,Y] - H[Y]. (7)
这是从条件概率的定义自然衍生出来的，必竟P(X = x | Y = y) = P(X = x, Y = y) / P (Y = y)。H[X | Y] 测量一旦我们已知Y值时保留在X中的不确定性。
3. 互信息
两个变量之间的互信息I[X;Y]定义为
I[X;Y] = H[X] - H[X|Y]. (8)
这是固定Y时关于X产生的平均不确定性的减少量。它是非负的，如同这里所有的熵，而且在两个变量间是对称的。
D. 系统中的斑图
如果有一种讨论将来的不确定性将是十分方便地。直观地这将是H[S->]，但是在一般情况下数值是无限的，操作起来也是十分棘手的。（H[S->]是有限的特殊情形已经在附录F中处理过。）正常情况下，我们由考虑H[S->L]来回避这个问题，下L个符号的不确实性，由L的函数处理。在一些时候，我们将参考每一个符号的熵或熵速率【55，62】：
h[S->] \eqiv lim L->∞ 1/L H[S->L]，（9）
并且条件熵速率，
h[S->|X] \equiv lim L->∞ 1/L H[S->L | X], (10)
其中，X是一些随机变量，而且极限存在。对于统计随机过程，极限一直存在【62，定理 4.2.1，p. 64】。
这些熵速率也是一直存在H[S]的上限；特殊情况是等式（附录3）。更有，如果h[S->] = H[S]，过程对应到的无关变量，实际上，实际上我们在这里仅仅关心统计过程。
定义3（捕捉斑图）R捕获一个斑图当且仅当存在一个L，使得
H[S->L | R]<LH[S].（11）
这就是说R捕获一个斑图，当它能告诉我们影响彼此的过程，各部分的分布：R展示了它们的依赖关系。（我们也说η，关联于过于的函数，捕获了一个斑图，自从隐含了R获捉一个斑图。）假设这些部分不影响彼此，然后我们拥有IID随机变量，他们最接近直观的“斑图”的概念，因为它可以被数学化地陈述。注意到，因为在联合熵上的不相关界限（Eq.(A3）)，如果不相等条件由一些L所满足，它也为每个L'>L所满足。因此，我们可以考虑差值H[S] - H[S->L|R]/L，找到最短不是零的L，作为由R捕获的斑图的长度。我们将给斑图长度标记一个上界(引理1)；后续我们将展示如何取得这个上界（定理1）。
E.历史的课程
我们现在处在证明系统斑图结果的位置，可用于连接后续关于因果态的定理。
引理1（旧世界引理）对于所有的R和所有的L属于Z+，
H[S->L|R]>=H[S->L|S<-]. (12)
证明。由构造可知（等式4），对于所有L，
H[S->L|R] = H[S->L|η(S<-)]. (13)
但是
H[S->L|η(S<-)]>=H(S->L|S<-). (14)
因此在一个变量上的条件熵永不大于一个变量上的函数的条件熵（Eq.(A14)）. 证毕。
备注1。也就是说，在全部过去的条件下，最大程度地降地了在将来的不确定性。从全部准无限的过去中截取是笨重和不安以及前景有些灰暗的。用不同的方式来做：我们希望尽可能多忘掉过去，以致能减少负担。这个目标跟等式（12）的结果是相反的，所以引发我们叫它旧世界引理。
备注2。引理1如前所述建立了斑图强度的上界，也就是，斑图的强度最多就是H[S] - H[S->L | S<-]/Lpast，其中Lpast是满足H[S->L|S<-]<LH[S]的L的最小值。
F. 最小化和预测
让我们引用奥卡姆剃刀原则：“有些事情只需抓住关键点，做得太多的话就是徒劳”【63】。为了使用剃刀，我们需要修正什么是“完成”和什么是“更多”和“更少”的含义。我们希望完成的工作是准确地预测，比如，尽可以地降低条件熵H[S->L|R]。目标就变成了获取由引理1导出的界限。我们希望尽可能简单地完成它，尽可能使用最少的资源。在见识过这两个约束的道路上——最小化不确定性和最小化资源——我们需要有第二者的测量方法。因为P(S<- = s<-)是定义好的，这里有一个在η-状态之上的简化测量方法；比如，P(R = ρ)，处于任意单个实际状态的概率，也定义好了。对应地，我们定义资源的测量方法。
定义4（因果态的复杂度）状态类R的统计复杂度是
Cμ(R)=H[R] (15)
=- ∑ρ∈R P(R=ρ) log2 P(R=ρ),
当和收敛到一个有限值。
μ中Cμ中提示我们它有着量化理论的特性，并且最终依赖于过程序列的分布，能导出状态上的测量。
一个状态类的统计复杂度是平均不确定度（单位是比特），在此过程的当前状态。这个，换句话说，是跟平均存储数量（单位是比特）一样，过程看上去是在保持过去，在给定选定的状态类R的条件下。（我们晚一点，在定义12中，查看如果定义一个过程它自己的统计复杂度。）这个目标是在尽可能少的存储下完成。再次申明，我们希望最小化统计复杂度，并符合最大准确预测的限制。
之所以称呼S<-的所有划分为奥卡姆水池背后的想法也应当清楚了。一个原因就是想找到水池当中最浅层的地方。 这就是我们刚刚做的。
Ⅳ. 计算力学
那些擅长射箭运动的人，是从弓，而非从弋射手上习得。那些知道如何驾船的人，是从船，而非从倭人所习得。
——佚名参考文献【64】。
计算力学的最终目标是去识别过程内在的斑图。也就是说，最可能地，目标是让过程描述自己，用它自己的词语，不需要诉诸于一个关于过程结构的前提假设。这里我们简单地在这些目标中探寻一致性和规范定义。当然，实际约束或许让我们只需极度地多或少逼近这些想法，而无需做太多。更自然地，这些问题，在实现中总是会出现，如果我们开始于安全的基础，是很容易定位的。
A.因果态
定义5（一个过程的因果态）一个过程的因果态是一系列函数ε的成员，ε将S<-映射到2S<-——S<-的幂集：
ε(s<-) = {s<-'|P(S->=s->|S<-=s<-) = P(S->=s-> | S<- = s<-'), 对所有s->∈S->，s<-'∈S<-}, (16)
它将历史映射到历史集合，我们将第i个因果态写成Si，并将所有因果态的集合写成S；对应的随机变量描述成S，它的实现写为σ。
S的基数没有特别说明。S可以是有限的，可数无限的，一个连续体，一个康托集，或一些奇异定格。这些例子在参考文献【5】和【10】中给出；特别查阅那里给出的隐马尔可夫模型的例子。
可替换的也是等价的，我们可以定义等价关系〜ε如两段历史是等价的当且仅当它们拥有相同的未来条件分布，并且定义因果态为由〜ε生成的等价类。（实际上，这是文献【6】的原始方法。）不管什么方法，S<-的这种划分的切分由区域建成，这些区域使我们在不同条件下对未来有一些无知。
最后的陈述建议了另一种，仍然等价，对ε的描述：
ε(s<-) = {s<-'|P(S->L=s->L|S<-=s<-) = P(S->L=s->L | S<- = s<-'), 对所有s->L∈S->L，s<-'∈S<-, L∈Z+}, (17)
使用这个我们可以构建初始的定义，等式【16】，将所有在每个新划分的历史空间S<-划分成序列就更加直观了。使用L+1导出，是对使用L导出的细化。在最粗糙的级别上，最前面的划分（L = 1）组成了那些历史，对于每一个下个观测有相同分布。这些类就使用下两个观测值的分布做细分，然后是下三个，四个，以此类推。这些划分序列的极限——到那个点，点里每个类中的每个成员都有着对未来相同分布，不管长度如何，同那个类中的每个其它成员一样——是由∼ε导出的S<-的划分。参阅附录B以获取更详细的讨论并查看∼ε的等价关系。
虽然他们不会直接关心以下的部分，因为时间渐近的限制存在，有短暂的因果态添加到在等式【16】中定义的（循环）因果态。大致地说，短暂的因果态描述了怎样延长观测序列（一段历史）以使我们去用标识循环因果态并提升准确性。可查阅附录B和参考文献【10】和【65】中的发展，以了解瞬时因果态的详情。
因果态是实际状态的一种特殊种类，他们拥有对实际状态来说普遍的属性（第Ⅲ节B部分）。在特殊情况下，每个因果态Si拥有若干结构附加：
1. 索引i——状态的“名称”。
2.将过程带到Si的历史集合，我们视为{s<- ∈ Si}。
3.在未来的条件分布，表示为P(S->|Si)，并等于P(S->|s<-)，s<-∈Si。自从我们倾向于分布频率这一种，而且自从它是“未来的图景”，我们称它为状态的变换。
理想情况下，这些的每一个都应由不同的符号表示，而且应该是清晰的函数，链接每个结构到他们的因果态。为了保持术语增涨受控，尽管这样，我们还是战略性地模糊掉他们的区别。读者或许以各种方式绘制ε为映射历史到(i)简单索引，（ii）历史的子集，或（iii）索引、子集、和变体的有序三元组；或甚至某人让ε没有解释性，如同偏好所向，不干涉随后的发展。
图 2. 一个表示将所有历史的集合S<-划分到因果态Si ∈S的示意图。在每个因果态中所有的单独历史s<-拥有相同的变体——对将来对测相同的条件分布P(S->|s<-)。
1. 变体
每一个因果态拥有独特的变体，比如，没有两个因果态拥有对未来相同的条件分布。这条直接来自定义5，而且它一般不是实际状态。另一个定义的直接结果是
P(S->=s->|S=ε(s<-)) = P(S->=s->|S<- = s<-). (18)
(再一次，这点对实际状态通常不是真的。)这种观测让我们证明一个有用的引理，关于过去S<-和未来S->条件无关。
引理2 过去和未来是无关的，在因果态的分布上。
证明。回忆起两个随机变量X和Z是条件无关的，当且仅当有第三个变量Y符合
P(X = x, Y = y, Z = z) = P(X = x| Y = y)P(Z = z|Y = y)P(Y = y).（19）
也就是，所有Z在X上的依赖，已经被Y斡旋了。为了接下来的描述方便，我们提出，重构条件分布，等同于约束：
P(X = x, Y = y, Z = z) = P(Z = z|Y = y)P(Y = y|X = x)P(X = x). (20)
让我们考虑P(S<- = s<-, S = ρ, S-> = s->).
P(S<- = s<-, S = ρ, S-> = s->)
= P(S->=s->|S = ρ, S<- = s<-)P(S = ρ, S<- = s<-) (21)
= P(S->=s->|S = ρ, S<- = s<-)P(S = ρ|S<- = s<-)P(S<-=s<-).
现在，P(S = ρ|S<- = s<-) = 0, 直到ρ = ε(s<-), 在这种情况P(S = ρ| S<- = s<-) = 1. 每种情况，在等式(21)最后一行前面两个因子可以写成等式（18），
P(S->=s->|S=ρ, S<-=s<-)P(S=ρ|S<-=s<-)
=P(S->=s->|S=ρ)P(S=ρ|S<-=s<-), (22)
因此，将等式（22）替换回等式（21），
P(S<-=s<-, S=ρ, S->=s->)
=P(S->=s->|S = ρ)P(S = ρ| S<- = s<-) P(S<- = s<-). (23)
QED.
2.同质性
根据参考文献【58】，我们介绍两个新定义和一个引理，后面需要用到，尤其在证明引理7和依赖这个引理的定理过程中。
定义6 (强同质性）一个集合X是强同质性的，对应着一个指定的随机变量Y，当关于Y的条件分布P（Y|X）对所有X的子集都相同。
定义7（弱同质性）一个集合X是弱同质性的，如果对应Y不是强同质性，但X\X0(在X中将X0移除后的集合)是，当X0是测度为0的X的子集。
引理3 (因果态的强同质性) 一个过程的因果态是历史的最大子集，对应所有长度的未来是强同质性的。
证明. 我们必须展示，首先，因果态是强同质性，对应所有长度的未来，其次，没有做成更大的历史的强同质性子集。第一个要领，因果态的强同质性，证据来自等式（17）：由建造方法，因果态的所有元素有相同的变体，因此因果态的任意部分将拥有作为全部状态的相同变体。第二点就是同样根据等式（17），自从因果态自构造时包含了所有带有变体的历史。所有其他的集合对应未来的强同质性必然小于一个因果态，而且任何包含作为适当子集的因果态集合不能是强同质性。证毕。
备注。统计解释用语应该说因果态是“为因果解释的统计-关系基础”。这种基础的元素是，准确地说，无关变量的集合的最大类，对关联变量带有同质分布。参阅参考文献【58】以获取更多关于这些内容的讨论。
B. 因果状态到状态的转换
在任意给定时间的因果态和观测过程的下一个值共同决定新的因果态；这点在引理5中做了简短证明。因此，一段因果态继任者有自然联系。回忆第二节E部分关于原因的讨论。更多地，给定当前因果态，所有可能的下一个值已经定好定义了条件分布。实际上，由构建可知全部准无限未来也如此。因此，有良好定义的过程的分布Tij(s)生成的值s∈A并转换到因果态Sj，如果它在Si状态中。
定义8（因果转换）已经标记的转换概率Tij(s)是促成状态Si到Sj转换的概率，并发出符号s∈A:
Tij(s) \equiv P(S' = Sj, S->1 = s|S = Si),（24）
其中S是当前因果态，并且S'是它发出s的继任者。我们用T表示集合{Tij(s) : s∈A}。
引理4（转移概率）Tij(s)由下式给出
Tij(s) = P(S<s∈Sj|s<-∈Si) (25)
= P(s<-∈Si, s<-s∈Sj)/P(s<-∈Si)，（26）
其中s<-s读作准无限序列，由在s<-的末尾连接s∈A获得。
证明。
Tij(s) = P(S' = Sj, S->1 = s|S = Si) (27)
= P(S' = Sj, S->1 = s, S = Si) / P(S = Si). (28)
现在 S = Si当有仅当 s<-∈Si, 并且 S' = Sj当且仅当s<-'∈Sj，其中s<-'我们表示紧随s<-其后的历史；为了统一，s<-' = s<-s。所以我们可以重写等式（28）如
Tij(s) = P(S<-∈Si，S->1 = s, s<-'∈Sj) / P(S = Si) (29)
= P(s<-∈Si, S->1 = s, s<-s∈Sj) / P(S = Si) (30)
= P(s<-∈Si, s<-s∈Sj) / P(S = Si). (31)
在第三行我们使用S<-=s<-和S<-'=s<-s的事实联合表明S->1 = s，使得条件相同。证毕。
注意到Tij(λ) = δij；也就是，由空符号λ标志的转换是同一个。
C. ϵ-机制
从历史到因果态带有标记的转换概率Tij(s)的函数ϵ组合称作过程的ϵ-机制【5，6】。
定义9（一个ϵ-机制定义）
一个过程的ϵ-机制是有序对{ϵ，T}，其中ϵ是因果态函数而T是由ϵ定义的状态转换矩阵。
等同地，我们或许由{S, T}表示一个ϵ-机制。
为了符合第II节F代数要求，我们显式构造同半群理解的联系。
命题 1（ϵ-机制是幺半群）由ϵ-机制{ϵ, T}生成的代数是带单位元的半群, 也就是，它是幺半群。
证明。参看附录D。
备注。因为这个，ϵ-机制可以被解释为捕获一个过程的一般对称性。任意ϵ-机制的半群的子群是，其实，在更熟悉的意义上呈现对称。
引理 5（ϵ-机制是决定性的）对于每一个Si和s∈A，Tij(s)>0只对于那些Sj对于ϵ（s<-s)=Sj当且仅当ϵ（s<-）=Si，对于所有的过去s<-。
证明。这个引理是断言的等价，对所有s∈A和S<-,S<-'∈S<-，如果ϵ(s<-) = ϵ(s<-')，则ϵ(s<-s) = ϵ(s<-'s)。（s<-s是另一段历史且附属于这个或那个因果态。）
假设这点不对。就有存在至少一个将来的s->符合
P(S-> = s-> | S<- = s<-s) != P(S-> = s-> | S-> = s-> | S<- = s<-'s)，(32)
尽管ϵ(s<-) = ϵ(s<-')。等价地，我们应该有
P(S<-> = s<-ss->)/P(S<- = s<-s) != P(S<-> = S<-'ss->)/P(S<- = s<-'s)，（33）
其中我们将ss->读为准无限字符串，开始于s而由s->继续。（记住，我们打破随机过程的点从一个过去到一个未来是武断的。）尽管如此，在分母里的概率是等于P(S->1 = s | S<- = s<-P(S<- = s<-)和P(S->1 = s | S<- = s<-')P(S<- = s<-')，分别地，而且由假设P(S->1 = s | S<- = s<-') = P(S->1 = s | S<- = s<-)，由于ϵ(s<-') = ϵ(s<-)。因此，我们应该需要
P(S<-> = s<-ss->)/P(S<- = s<-) != P(S<-> = s<-'ss->)/P(S<- = s<-')。（34）
这也是一样的，然后，因为
P(S-> = ss-＞｜S<- = s<-) != P(S-> = ss-> | S<- = s<-')。（35）
这也是在说有一个未来ss->有不同的概率依赖于我们是用s<-还是s<-'的条件。但是这个对立面假设这两段历史附属于相同的因果态。因此，没有这样的未来s->，而引理替换的描述是真的。证毕。
备注1。在自动化理论【66】中，一个状态的集合和转换说是决定性的，如果当前的状态和下一个输入——在这里，是原始随机过程的下一个结果——一并修正下一个状态。这个用语“决定性”通常容易混淆，因为很多随机过程（例如，简单的马尔可夫链）在这种语境下是决定性的。
备注2。从固定状态开始，一个给定的符号总是导向最多一个单状态，但这会有多个从一个状态到另一个的转换，每一个被标记会不同的符号。
备注3。很清楚的是，如果Tij(s) >０，那么Tij(s) = P(S->1 = s|S = Si)。在自动化理论里这个“不允许”转换（Tij(s) = 0）有时候是明显存在的，并且导向一个“弹出”状态指示对应部分历史没有发生。
引理6（因果态是相互不依赖的）因果态上的概率分布在不同时间是条件无关的。
证明。我们想展示的是，将因果态序列在三个连续的时间步写成S, S'，S\'\'，在给定S'后，S和S\'\'是条件无关的。我们可以直接做到这样：
P(S = σ, S' = σ'，S\'\' = σ\'\')
= P(S\'\' = σ\'\' | S = σ, S' = σ')P(S = σ, S' = σ')
= P(S->1 ∈ a | S = σ, S' = σ')P(S = σ, S' = σ'), (36)
其中a是所有将σ'导向σ\'\'符号的子集。这是一个良好定义的子集，在引理5的即刻前述的铺垫里，也保证了我们使用过的条件概率相等。类似地，
P(S\'\' = σ\'\' | S' = σ') = P(S->1 ∈ a | S' = σ'）。（37）
但是，经构造式
P(S->1 ∈ a | S = σ, S' = σ') = P(S->1 ∈ a | S' = σ'), (38)
并且因此
P(S'' = σ'' | S' = σ) = P(S'' = σ'' | S = σ, S' = σ')。（39）
所以，可以继续，
P( S = σ, S' = σ', S\'\' = σ\'\')
= P(S\'\' = σ\'\' | S' = σ')P(S = σ, S' = σ')
= P(S\'\' = σ\'\' | S' = σ')P(S' = σ' | S = σ)P(S = σ). (40)
最后一行遵从了概率分布并等价地更容易由表达式给出
P(S\'\'|S')P(S|S')P(S')。（41）
因此，由等式（41）导出后应用数学方法，因果态在不同时间片是独立的，条件是在中间的因果态。证毕。
备注1。这个引理加强了申明，该申明说因果态是，实际上，因果上有效的状态：给定当前状态的知识，已经过去之前的些，改变不了什么。（再次，回忆下在第II节E中哲学性的预备内容。）
备注2。这个结果指示出因果态，考虑成一个过程，定义了一个马尔可夫链。因此，因果态可以被大约考虑成马尔可夫状态的生成。我们说“一种”是因为ϵ-机制是基本上更丰富的【5，10】，和通常附加在马尔可夫链上的那些相比。
定义10（ϵ-机制重构）
ϵ-机制重构是任意给定一个过程P(S<->)，或P(S<->)的一个近似，生成这个过程的ϵ-机制{S, T}的流程。
给定一个过程的数学描述，有人可以经常计算分析它的ϵ-机制。（例如，查阅参考文献【65】中旋转系统的计算力学分析。）这里也有很多宽泛的算法可以从P(S<->)的经验模拟重构ϵ-机制。一些，比如那些在参考文献【5-7，69】中使用到的，操作在“批量”模式，将原始数据一起处理然后生成ϵ-机制。其他的可以操作在增量，处于“在线”模式，将因果态和它们的转移概率集合单独的测量和重新评估。