因果网络

对于初始标记的PFSAG=（Q，∑，δ，eπ，Q），符号特定的变换矩阵Γσ∈{0，1}| Q |×| Q |是：σi j=eπ（qi，σ），如果δ（qi，σ）=qj0，否则（25）变换矩阵每行有一个非零条目，反映了我们的生成规则，即给定一个状态和一个生成的符号，下一个状态是固定的。首先，我们注意到，给定一个初始标记的PFSA G，我们可以关联一个概率分布在G的每个状态上∈ Σ?在以下意义上：如果x=σr···σrm∈ Σ?, 然后我们有：x=σr··σrm=||λQmj=1Γσrj | | |{z}归一化因子λmYj=1Γσrj（26），其中λ是G态上的平稳分布。请注意，可能存在多个导致分布的字符串x、 从平稳分布开始λ. 因此x对应于字符串的等价类，即x不是唯一的。定义8（典型代表）。初始标记的PFSAG=（Q，∑，δ，eπ，Q）唯一地导出一个规范表示（QC，∑，δC，eπC），其中QC是Q上概率分布集合的子集，δC:QC×σ→ QC，eπC:QC×∑→ [0,1]的构造如下：1）使用由G诱导的马尔可夫链的转移概率，构造Q上的平稳分布，并将其作为第一个元素QC的λ。注意，G的传递矩阵是行随机矩阵M∈ [0,1]|Q |×|Q |，其中mi j=Pσ：δ（qi，σ）=qjeπ（qi，σ），因此λ满意度：λM=λ（27）2）定义δCπC(x、 σ）=||xΓσ||xΓσ，xσ（28）eπC(x、 σ）=xe∏（29）对于QSP H，正则表示被表示为CH引理5（正则表示的性质）。

给定一个初始标记的PFSA G=（Q，∑，δ，eπ，Q）：1），正则表示与初始状态无关。2） 正则表示（QC，∑，δC，eπC）包含一个g的副本，即存在一组状态Q QC，因此存在一对一映射ζ：Q→ Q、 与：Q∈ Qσ ∈ ∑，（eπ（q，σ）=eπC（ζ（q），σ）δ（q，σ）=δC（ζ（q），σ）（30）3）如果在施工期间（从λ） 我们遇到对于某些x，x=ζ（q）∈ Σ?, Q∈ Q和（2）中定义的任何映射ζ，那么我们将保持在初始标记的PFSA副本的图中，用于x的所有正确扩展。证明：（1）遵循QSP的遍历性，这使得λ与初始标记PFSA中的初始状态无关。（2） 正则表示包含了初始标记表示，即后者的状态本身可以被视为Q上的退化分布，即通过Letting=工程安装∈ [01]| Q |，i=1，···，| Q|（31）表示满足以下条件的分布集：ei | j=1，如果i=j0，否则（32）（3）来自G的强连通性。引理5暗示初始状态不重要；我们可以将QSP H诱导的初始标记PFSA（去除初始标记）表示为PH，并将其简称为“PFSA”。在E的CHas元素中，状态可以表示为状态。注意，我们总是会遇到一个状态，任意接近于从平稳分布开始的正则结构中的某个元素λ关于PH的状态。然而，在我们继续之前，我们建立了唯一极小实现的存在性。注意，即使初始标记的PFSA是强连接的，规范表示也可能不是。定义9（PFSA之间的结构同构）。

如果存在双射映射ξ：Q，则定义在同一字母表∑上的PFSA G=（Q，∑，δ，eπ）和G=（Q，∑，δ，eπ）在结构上同构→Qsuch表示：Q∈ Q、 σ∈ ∑，（ξ（δ（q，σ））=δ（ξ（q），σ）eπ（q，σ）=eπ（ξ（q），σ）（33）注意，ξ的双射性要求|q |=|q |。两个PFSA之间的结构同构意味着存在状态的置换，使得一个状态转换为另一个状态。因此，结构同构的PFSA编码相同的QSP。定理1（唯一强连通极小实现的存在性）。如果对应于概率空间（∑ω，B，u）的概率Nerode关系（代表平稳遍历QSP）有一个有限的指数，那么它有一个强连通的PFSA生成器唯一的结构同构。证明：首先，我们使用引理3中描述的构造来获得有限指数Neroderelation的PFSA生成器G=（Q，∑，δ，eπ）~n对应于概率空间（∑ω，B，u）。注意，由于概率空间代表的QSP是遍历的，我们可以从引理3的构造中得到初始状态。设G=（Q，∑，δ| Q，eπ| Q）是G的强连通分量，即我们有Qj Q，δ| Q，eπ| qa是对应函数对可能更小的状态集的限制，（Q，δ| Q）定义了一个强连通图，qa是节点集，并且有一个标记边qiσ-→ qji ffδ| Q（Q，σ）=qj。让q∈ Q、 以至于十、∈ Σ?, [x] =q，使得u（x∑ω）>0。设H是通过将Gwithqas扩充为初始状态而获得的初始标记PFSA，即H=（Q，∑，δ| Q，eπ| Q，Q）。让我们表示：EH={[xy]：y∈ Σ?} （34）设E为~N.直接的结果是：EHj E（35），因为H是强连通的，并且X的任何右扩张都在某个状态q上终止∈ Q、 直接存在目标映射H:Q→ 嗯。如果可能的话，让它存在∈ 这样E<EH。

让z∈ Σ?,以至于∈ E.那么，就这样Z∈ Σ?, xz/Nz（36），这与我们关于QSP是遍历的假设相矛盾。因此，我们得出结论E=EH，即H是~N.我们声称地图H:Q→ E是内射的。要看到这一点，假设可能的话，对于一些不同的q，q∈ Q:H（Q）=H（Q）=E∈ E（37）由于q，qa是不同的，所以存在字符串x，x∈ Σ?因此[xi]，[x]与式（37）相矛盾。因此，我们得出结论，他的观点是一种最低限度的认识。由于G是G的任意强连通分量，且上述论点对状态标签的任何排列都有效，我们得出结论，H在结构等价性上是唯一的。这就完成了证明。总之，对于任何固定的初始状态，每个PFSA G=（Q，∑，δ，eπ）代表一个概率空间（ω，B，u），并且始终存在对后者进行编码的最小实现；然而，G可能是潜在概率空间的非最小实现。因此，给定一个PFSA G=（Q，∑，δ，eπ）和一个初始状态Q的选择，我们在∑？上有两个相关的等价关系：1） 过渡等价~由PFSA图定义的Gde，即其过渡结构和状态：x~如果δ（q，x）=δ（q，y）（38）2）概率能量等效~Ngiven by:x~纽约如果Z∈ Σ?, u（xz∑ω）=u（yz∑ω）（39）我们有以下直接结果：引理6（跃迁等价）。给定PFSA G=（Q，∑，δ，eπ），并选择初始状态Q∈ Q、 过渡等效必然是相应的Nerode等效的一个补充。如果G是一个最小实现，那么这两个等价物是相同的。证明：紧接着注意到：x~Gy=> δ（q，x）=δ（q，y）=> Z∈ Σ?, δ（q，xz）=δ（q，yz）=> Z∈ Σ?, u（xz∑ω）=u（yz∑ω）（40）接下来我们介绍-probabilisticautomata的同步（见图3）。

自动机的同步是fixing或q0q1σ1 | 0.15σ0 | 0.85σ1 | 0.75σ0 | 0.25可同步q0q1σ1 | 0.15σ0 | 0.85σ0 | 0.25σ1 | 0.75不可同步图。3.可同步和不可同步的机器。识别上下文是估计随机信号源熵率的关键步骤；对于PFSA发电机，这就转化为一个状态同步问题。然而，并非所有PFSA都是可同步的，例如，虽然顶部机器是可同步的，但底部机器不是。请注意，只有一个符号的历史足以确定可同步机器（顶部）中的当前状态，而在不可同步机器（底部）中，没有一个完整的历史可以这样做。然而，我们表明-可同步字符串alwaysexists（定理2）。确定当前状态；因此，它类似于利萨宁的“上下文算法”[36]中的上下文。我们表明，虽然并非所有PFSA都是可同步的，但所有PFSA都是可同步的-可同步。定理2(-概率自动机的同步）。对于大于∑的任何qsp H，PFSA PHSaties：> 0, 十、∈ Σ?, θ ∈ E||十、- θ||∞5.（41）证明：我们证明了所有PFSA至少是近似可同步的[37]，[38]，这对于确定性自动机是不正确的。如果PH图（即，通过移除弧概率获得的确定性自动机）是可同步的，那么等式（41）对于= 0表示任何同步字符串x。因此，我们假设PHA的图形不可同步。从非同步性的定义来看，如下所示：齐，qj∈ Q、 与齐，qj，十、∈ Σ?, δ（qi，x），δ（qj，x）（42）如果PFSA只有一个状态，那么每个字符串都满足等式（41）中的条件。因此，我们假设PFSA有多个州。现在如果我们有：十、∈ Σ?,Pr（xx）Pr（x）=Pr（xx）Pr（x），其中[x]=qi，[x]=qj（43）。那么，根据定义5，我们有一个矛盾qi=qj。

因此xsuch thatPr（xx）Pr（x），Pr（xx）Pr（x）其中[x]=qi，[x]=qj（44）自：xx∈Σ?Pr（xx）Pr（x）=1，对于其中[x]=qi（45）的任何x，我们在不损失一般性的情况下得出结论齐，qj∈ Q、 有了qi，qj：xi j∈ Σ?,Pr（xxi j）Pr（x）>Pr（xxi j）Pr（x），其中[x]=qi，[x]=qjIt根据归纳得出，如果我们从一个分布开始 就这样我=j=0.5，则对于任何> 0我们可以构造一个有限的xi j，如果δ（qi，xi j）=qr，δ（qj，xi j）=qs，那么对于新分布执行xi协议后，将满足s> 一,-. 我们注意到，对于任何qt∈ Q、 存在一个字符串y∈ Σ?, 使得δ（qs，y）=qt。设置xi，j→t？=xi jy，我们可以确保分配执行xi j后获得？满足感t> 一,- 无论我们选择什么。对于任意初始分布Aon Q，我们必须考虑同时执行xi，j所产生的贡献→T来自其他州，而不仅仅是钱德qj。然而，不难看出，执行xi→T意味着在新的分布中A、 我们有在>Ai+Aj- . 接下来是执行字符串x1,2→|Q | x3,4→|Q |··xn-1，n→|Q |，在哪里=|如果| Q |是偶数| Q |- 1否则（46）将导致最终分布令人满意的A | Q |>1-N.适当缩放然后完成证明。定理2引出了-同步字符串，并保证它们在任意PFSA中的存在。定义10(-同步字符串）。字符串x∈ Σ?是在以下情况下同步PFSA：θ ∈ E||十、- θ||∞5. （47）定理2是一个存在的结果，并且不会产生计算同步字符串的算法（参见定理4）。我们可以估计这样一个搜索的渐近上界。推论1（定理2）。

最多0（1）/) 需要分析给定字母表上所有字符串的自由顺序集合中的字符串，以找到-同步字符串。证明：定理2将∏矩阵中的条目相乘，这些条目不可能完全相同（否则状态将崩溃）。设两个不相等条目之间的最小差值为η。然后，按照定理2中的构造，同步字符串的长度`，直到线性缩放，满足：η`=O(), 意味着`=O（log（1/). 因此，要分析的字符串的数量是atmost all strings of length`，其中∑| `=|∑| O（log（1/)= O（1）/).3.2符号导数计算-同步字符串需要符号导数的概念。PFSA状态不可见；我们观察隐藏状态产生的符号。给定字符串的符号导数指定了下一个符号在字母表上的分布。符号4。我们将一组基数k上的概率分布表示为D（k）。定义11（符号计数功能）。对于大于∑的字符串，计数函数#s:∑？→ N∪ {0}，统计特定子串在s中出现的次数。计数是重叠的，即在s=0001时，我们将00s的出现次数计为0001和0001，这意味着#s00=2。定义12（符号导数）。对于aQSP在∑上生成的字符串s，符号导数φs:∑？→ D（|∑|- 1） 定义为：φs（x）i=#sxσiPσi∈∑#sxσi（48）因此，十、∈ Σ?, φs（x）是∑上的概率分布。φs（x）被称为x处的符号导数气∈ Q、 eπ诱导∑上的概率分布为[eπ（qi，σ），··，eπ（qi，σ|∑|）]。我们表示这个aseπ（qi，·）。下一步，我们展示了x处的符号导数可以用来估计qi=[x]的这个分布，前提是x是-同步。定理3(-收敛）。

如果x∈ Σ?是-同步，然后： > 0，林| s|→∞||φs（x）-eπ（[x]，·）||∞a、 s （49）证明：我们使用Glivenko-Cantelli定理[39]研究经验分布的一致收敛性。因为x是-正在同步： > 0, θ ∈ E||十、- θ||∞5. （50）回想一下E=工程安装∈ [01]| Q |，i=1，···，| Q|表示满足Q:ei | j的分布集=1，如果i=j0，否则（51）让x-同步到q∈ Q.因此，当我们遇到x个whilereading s时，我们被保证分布在Q上x、 其中：||十、- θ||∞5. => x=αθ+（1- α） u（52）其中α∈ [0, 1], α = 1 - , u是q的未知分布。定义Aα=αeπ（q，·）+（1）- α） P | Q | j=1ujeπ（qj，·），我们注意到φs（x）是Aα的经验分布，这意味着：lim | s|→∞||φs（x）-eπ（q，·）||∞= 林氏|→∞||φs（x）- Aα+Aα-eπ（q，·）||∞a、 格里文科·坎特利兹|{lim | s |的s.0|→∞||φs（x）- Aα||∞+ 林氏|→∞||Aα-eπ（q，·）||∞a、 s（1）- α） （| | eπ（q，·）- u||∞)a、 s这就完成了证明。推论2（定理3的右延拓）-同步字符串）。如果x∈ Σ?是-那么同步呢σ ∈ ∑，这样xσ-与同步= C, 和Cis有限常数：C，maxqi，qj∈Q、 σ∈∑s.t.eπ（qj，σ）>0eπ（qi，σ）eπ（qj，σ）<∞ （53）证明：让x∈ Σ?是-同步。定义10意味着：θ ∈ E||十、- θ||∞5. （54）我们注意到，如果Nerode关系只有一个等价类（即，基本的最小PFSA只有一个状态），那么每个σ的结果都是真的∈ Σ. 因此，我们假设基本PFSA的最低实现有多个状态。在不失概括性的情况下，让θi？=1，暗示（定义10）：x|i？>1.-  （55）由于我们假设基础PFSA是强连接的，因此存在σ∈ ∑使得δ（qi？，σ），qi？，andeπ（qi？，σ）>0。Wecomputexσ显式，使用等式。

（26），注意如果δ（qi？，σ）=qj？，气？，然后我们有：xσ| j=eπ（qi？，σ）（1）- )eπ（qi？，σ）（1）- ) +Pqk∈Q\\{qi？}eπ（qk，σ）k（56）在哪里Kk=0和xqk∈Q\\{qi？}k==> xσ| j=1.- 1 + （C）- 1), 1 - （57）式中C=maxqk∈Q\\{qi？}eπ（qk，σ））eπ（qi？，σ）<∞=> = C1+（C）- 1)5 C5C（58）这就完成了证明。备注1（CAs A系统属性）。重要的是要注意，上述论点对于任何权利的延伸都是有效的同步字符串，只要从同步状态生成扩展的概率不为零。具体地说，注意推论2中的论点对任何σ都有效，只要从状态qi生成σ的概率？为非零（以确保c的完整性）。此外，请注意，Cis是基础QSP的一个属性，并且独立于x。这对于建立QSP的高效PAC可学习性非常重要，因为使用PFSA作为假设类别的因果状态数量有限。3.3计算-同步字符串下一步我们描述-同步字符串给定一个足够长的观察字符串（即样本路径）。定理2保证存在，推论1建立O（1/) 需要分析子字符串，直到遇到-同步字符串。这些并没有提供一个可执行的算法，该算法是通过检查∑上概率向量集的几何结构而产生的，该概率向量集是通过构造φs（x）来获得的，用于候选字符串x的不同选择。定义13（导数堆）。给定aQSP生成的字符串s，派生堆Ds:2∑？→ D（|∑|-1） 是为字符串L的子集计算的∑上的概率分布集 Σ?as:Ds（L）=φs（x）：x∈ L Σ?（59）引理7（极限几何）。

让我们定义一下：D∞= 林氏|→∞极限→Σ?Ds（L）（60）如果你∞是D的凸包∞, u是u的顶点∞, 然后Q∈ Q、 这样u=eπ（Q，·）（61）证明：回顾定理3，注意到D的任何元素，结果如下∞是集合{eπ（q，·），··，eπ（q | q |，·）}中元素的凸组合。引理7并没有说D的凸壳的顶点数∞等于状态数，但每个顶点对应一个状态。我们无法生成D∞因为我们有一个单元观测字符串s，我们可以计算φs（x）的有限个x。相反，我们表明，选择一个对应于堆凸壳顶点的字符串，通过考虑O（1）来构造/)弦，给我们一个-以高概率同步字符串。定理4（导数堆近似值）。对于由QSP生成的s，让Ds（L）用L=∑O（log（1）计算/)). 如果是x∈ ∑O（log（1）/)),φs（x）是Ds（L）的凸壳的顶点，那么pr（xis）不是-（3）5 e-|标准普尔（62）式中，pis是遇到xin s的概率。证明：结果来自概率分布凸集的Sanov定理[40]。如果| s |→ ∞, 那么xis肯定是-同步（定理2和推论1）。表示我们遇到xin s的次数为n（|s |），并且从D开始∞是一个凸分布集（允许我们在Sanov\'s Bound中去掉多项式因子），我们将Sanov定理应用于有限s:Pr的情况吉隆坡φs（x）kxe∏> 5 e-n（|s |）（63）其中KL（·|·）是库尔贝克-莱布勒散度[41]。