了解HTM理论中的SDR

$SDR$概念

        $SDR$全称为Sparse Distributed Representations(中文可翻译为“稀疏分布表征”)。
        一条$SDR$由数千个比特组成,在任何时刻有一小部分的比特是为 $1$ 的,其余为 $0$ 的。$SDR$中的比特对应于大脑中的神经元,置1的是相对激活的神经元,置 $0$ 的是相对抑制的神经元。这些比特没被指定其含义,但是如果两条或以上的$SDR$在相同的位置上有激活比特,那么它们共享由这些比特表示的语义属性。通过确定两条$SDR$的重叠部分,我们可以很快理解两个表征是如何在语义上相似,以及它们如何不同。由于这种特征,基于$SDR$的系统能够自然而然地以语义相似性为基础推而广之。
        HTM理论规定了如何创建、存储、回忆$SDR$和$SDR$序列。$SDR$不像计算机的数据那样在内存中来来去去,它更像在固定的神经元群中的激活神经元,随着时间而变化。在某一时刻,一组神经元代表某个意思;在下一个时刻,它代表其它意思。在某个时刻的$SDR$可以关联地链接紧接着要出现的$SDR$,这样$SDR$的序列就被学习到了。关联链接也出现在不同的细胞群之间(层次之间或区域之间)。
        任何类型的数据都可以编码到一条$SDR$中,包括不类型的传感数据,比如字符、位置、行为。只要输入信息采用了适当的$SDR$格式,HTM算法就可以工作。

$SDR$表示

        在计算机世界中,信息是用比特字表示的,置 $0$ 和置 $1$ 的所有组合都用上了,从全部置 $1$ 到全部置 $0$ ,这种方式称为向稠密表征。例如,字母表中的 $m$ 用ASCII码表示为 $01100101$ ;这里单独的比特不表示任何意思,如果改变任何一个比特所表示的意思完全变了。稠密表征的含义必须存储在其它某个地方。
        在$SDR$中,每个比特都有意义,第个比特的含义是学习得来的而非指定的。$SDR$通过一组激活比特来表示其含义。所以,如果两个不同表征在相同位置上都为 $1$ ,我们可以确定这两个表征共享了这个属性。因为表征是稀疏的,它们不会偶然地共享某个属性;
        $SDR$的一些数学特征是计算机的传统数据结构所不具备的。比如要把一条$SDR$存储到内存中,我们不需要像处理稠密表征那样存储所有比特。我们只要存储置 $1$ 比特的位置,而且只要存储少量的置 $1$ 比特(占该条$SDR$比特的2%)的位置。随机挑选的$SDR$共享2%个比特的概率非常低;这种情况不会偶然发生,所以存储这2%个比特就够了。但是如果两条 $SDR$ 确实都在这2%个相同的位置上有置 $1$ 比特,那么这两个$SDR$在语义上是相似的。
        $SDR$中的数学特征是计算机的传统数据结构所不具备的。比如要把一条$SDR$存储到内存中,我们不需要像处理稠密表征那样存储所有比特。我们只要存储置 $1$ 比特的位置,换句话说只要存储少量的置 $1$ 比特的位置。
        $SDR$还有一个合并特征。只要让所有的$SDR$共同做逻辑$OR$操作,得到的合并$SDR$和原先的每条$SDR$都有一样数目的比特,但是它不那么稀疏。形成合并是一种单向操作,就是说你无法根据形成的合并$SDR$得 知是用哪些$SDR$来形成它的。但是可以用一条新的$SDR$和这个合并$SDR$比较,来确定新的$SDR$是否是参与合并的某条$SDR$。因为$SDR$的稀疏性,所以判断失误的概率很低。

$SDR$的数学特征

以下是$SDR$的数学特征,着重推导根本的标度律和误差界:

  • $SDR$的容量和错误匹配概率
  • $SDR$的健壮性和噪声误差概率
  • $SDR$向量的可靠分类
  • $SDR$的合并
  • $SDR$的合并在噪声环境下的健壮性

数学定义和符号

  • 二进制向量:我们把$SDR$看作是二进制向量,用 $x$ 作为$SDR$的定义,每个元素的值为 $0$ 或 $1$ ,分别表示offon
  • 向量模:在$SDR$ $x$ 中,$n$ 指向量的长度,我们用 $n$ 表示向量中元素的总数、向量的维数或比特总数。
  • 稀疏度:在任何时刻,向量 $x$ 中的 $n$ 个比特是on,其余为off;用 $s$ 表示on比特所占的比例。一般在稀疏表征中,$s$ 要远远低于50%。
  • 向量势:用 $w$ 表示向量的基数,如果向量 $x$ 中的on比特占的比重是 $s$ ,那么向量势为:
  • 重叠:我们通过重叠来确定两个$SDR$的相似程度。如果 $x$ 和 $y$ 表示两个$SDR$,那么重叠计算公式为:
  • 匹配: 通过检查两个$SDR$是否充分重叠来确定匹配。对 $x$ 和 $y$ 而言         如果 $x$ 和 $y$ 有相同的 $w$,我们可以通过设定阈值 $\theta = w$ 来确定一个精确匹配。如果 $\theta < w$ 表明这是一个非精确匹配。
    假设有两个$SDR$向量:
    $x = [1000000000000000000100000000000110000000]$
    $y = [0100000000000000000100000000000110000000]$
            两个向量都具有相同的参数,向量模 $n = 40$,稀疏度 $s = 0.1$,向量势 $w = 4$。向量$x$和$y$的重叠评分是$3$;因此当设定 $\theta = 3$ 时这两个向量是匹配的,此时它们非精确匹配。如果当设定 $\theta > w$ 时,任何匹配都不可能发生。

$SDR$的容量和错误匹配的概率

        在实际应用中$SDR$应该有很大容量。给定一个 $n$ 和 $w$ 的向量,对它们编码不同的$SDR$的数目,可用下面的公式求出共有多少个$SDR$数目:

        上面公式我们假设 $n = 2048$,$w = 40$;$SDR$的表征空间就有天文数字那么大,它可以有 $2.37 \times 10^{84}$ 个编码,而可观测宇宙中的原子数估计为 ${\sim}10^{80}$。
        要让SDR能够表示信息,我们需要可靠地区分出编码;也就是说,SDR应该相互区别,这样我们才不会混淆信息。只有这样,接下来理解两个随机SDR的相同概率才有意义。给定两个有着同样参数的随机SDR x 和 y ,它们相同的概率是:$P(x=y)=1/\binom{n}{w}$
        假设向量模 $n=1024$ 且向量势为 $w=2$ 时,会有 $523776$ 种可能的编码,任意两个随机编码相同的可能性非常高;如果当 $w=4$ 时,这个概率下降到不足 $\frac{1}{45000000000}$;如果是 $n=2048$ $w=40$ (这是HTM的典型值),相同的概率基本为 $0$。
上述的等式说明了,$SDR$具备足够大的尺寸和密度时,会有超乎寻常的容量满足不同编码,不同的表征几乎不可能用上相同的编码。

重叠集

        重叠集是用来帮助我们分析不同条件下的匹配效果。假设 $x$ 是一个大小为 $n$ 且有 $w_x$个比特为on的$SDR$编码。向量 $x$ 关于参数 $b$ 的重叠集是 $\Omega_x (n,w,b)$,定义为大小为 $n$ 且有 $w$ 个比特为on,与向量 $x$ 恰好有 $b$ 个比特重叠的向量集合。这些向量的数目用 $\mid\Omega_x(n,w,b)\mid$ 来表示。如果 $b \leq w_x$ 且 $b \leq w$,那么就有以下公式:

        等式中乘积的第一个因数表示向量 $x$ 中的 $w_x$个on比特对应的位置出现 $b$ 个on比特的组合数,第二个因数表示向量 $x$ 中的 $n-w_x$ 个off比特对应的位置出现 $w-b$个on比特的组合数。其中前者体现的是重集中的微量与向量 $x$ 重叠的部分。

非精确匹配

        如果我们要求两个$SDR$做精确匹配( $\theta = w$ ),那么只要任意两条中的on比特有一个噪声比特就会不匹配。所以一般而言,我们要系统能够容忍输入信息中的变动或噪声。也就是说我们很少需要精确匹配。
        在精确匹配场景中 $\theta = w$,当减少 $\theta$ 时,潜在匹配的集合会增大,同时会有更大可能性随机发生错误匹配。也就是说减少 $\theta$ 会增强健壮性,但同时也会增加错误匹配率;但如果再增大 $n$ 可以减轻这种不利影响。
        给定一个$SDR$编码 $x$ 和另一个随机$SDR$编码 y ,两者有相同的向量模 $n$ 和向量势 $w$ ,发生错误匹配的概率是多少?也就是 $overlap(x,y)\leq\theta$ 的可能性是多少?匹配定义为有 $\theta$ 个或者更多个比特重叠,最多是 w 个。总共有 (nw) 个不同的编码方式,发生误报的概率是:

        为了更直观地感觉一下这个等式,可以参照下图:

        这张图说明了等式参数间的作用关系。三条实曲线表示了当你增大$SDR$的模 $n$ 时,误差率会快速下降。每条曲线代表不同数目的on比特,即向量势 $w$ 的情况,它们都有恒定为50%的匹配阈值 $\theta$。当 $n$ 增大时,这三条曲线的误差下降速度比指数级下降还要快,当 $n>2000$ 时误差基本为 $0$。虚线表示当$SDR$中的半数比特是on时的误差率。注意,这条线保持着相对较高的误差率(大约为50%),意味着如果采用非稀疏表征,不可能获得抵抗噪声的健壮性。要实现低误差率,稀疏性和高维度都是必要的。

子采样

        $SDR$能够可靠地对比向量的子采样描述。也就是通过匹配大尺寸模式中激活比特的较小子集识别大尺寸的分布模式。假设 $x$ 是一条$SDR$, $x′$ 是 $x$ 的子采样描述,这样有 $wx′\leq wx$。不言而喻,只要满足 $\theta \leq wx′$,子采样描述 $x′$ 总会匹配 $x$。但是如果你增大子采样,误报概率也会增大。同理给定 $\theta \leq w_{x′}$,那么错误率为:

        子采样仅仅只是之前讨论的非精确匹配特征的变体。同样我们用图表直观地感受一下

        三条实曲线代表几个特定的维度和稀疏度,表示了随着子采样比特数目的增大,误差率产生指数级的改善。如果有充分高的维度和稀疏度,采用$15$到$25$的子采样值可以达到非常低的误差率。相反虚线代表的是一个相对稠密的表征($25%$的on比特)所对应的误差率;尽管维度很高但是误差也很高。

对$SDR$分类

        假设 $X$ 是包含 $M$ 个向量的集合,$X=\{x_1, x_2,…,x_M\}$,其中每个向量 $x_i$ 都是一条$SDR$。给定随机的$SDR$ $y$,我们判断其是否属于该集合的依据如下:

        我们对被噪声污染了的向量进行分类的可靠性如何呢?更具体来说,如果我们从向量 $x_i$ 的 $n$ 个比特中随机选出 $t$ 个并且切换它们的onoff来引入噪声,那么发生误报分类的似然是多少?假设 $t \leq w−\theta$ ,并且这里没有漏报,只有误报。那么这个问题就变成了“对随机向量 $y$ 的分类是误报的概率是多少?”。因为相对于匹配来讲, $X$ 中的所有向量都是独特的,所以发生误报的概率是:

        发生单个重叠的误报概率非常小,所以使用以下的约束条件更加实用:

        如果所有向量的模 $n=64$ 并且势 $w=3$ 。如果 $\theta = 2$ ,你的列表里存储了$10$个向量,误报率大约是$\frac{1}{22}$。增大 $w$ 到$12$并且增大 $\theta$ 到$8$,保持比值 $\frac{\theta}{w} = \frac{2}{3}$ 不变,误报率会下降到大约$\frac{1}{2363}$。现在把参数增大到更实际的取值: $n=1024$ 和 $w=21$ ,并且 $\theta=14$ (也就是 $w$ 值的$\frac{2}{3}$)。在这种情况下,这$10$个向量的误报率会骤降至 $\frac{1}{10^{20}}$。实际上,采用这些参数值,存储十亿个向量的误报率要比 $\frac{1}{10^{12}}$更低!
        这个结果说明了$SDR$的一个显著特征:假设一个大的模式集合都是用$SDR$编码的,并且存储在列表里。那么其中很大数目的模式都可以接近完美地检索出来,甚至有大量噪声的情况下。当然前提是 $n$、$w$、$t$ 需要充分的大。正如上面的例子说明的,如果取较小的值比如 $n=64$ 和 $w=3$ ,那么$SDR$不能很好地利用这些特征。

$SDR$的合并

        通过对所有的向量做$OR$操作从而把一组模式可靠地存储到一个固定的表征,称之为合并特征。合并特征的优势在于一个固定大小的$SDR$向量可以存储一个动态的集合。像这样,细胞的固定集合及其连接运作于一个动态列表。它也提供了分类操作的替补方案。在HTM中,$SDR$的合并被广泛用于时序预测,以便进行时序池化、表现不变性以及创造高效的层次结构。但是能够可靠地存储在一个集合中的向量的数目是有限的。
        合并特征有多可靠?没有漏报的风险;如果给定的向量在集合中,它的所有对应位置的比特都会是on,无论其他模式是什么样的,重叠是完美的。如果向量的数目 $M$ 充分地大,那么集合的合并向量的on比特会趋于饱和,判断任意的随机向量几乎都会得到误报匹配。理解这种关系是很很有必要的,这样我们可以规避合并特征的局限。
        让我们先来计算精确匹配时的误报概率。这种情况下,如果一个随机模式 $y$ 的所有比特都与合并向量 $X$ 重叠,就发生了误报。当 $M=1$ 时,合并向量中任意给定的比特是off的概率是 $1−s$。当 $M$ 增大时,误报概率是:$p_0 = (1-s)^M$
        经过 $M$ 次合并操作,合并向量 $X$ 中任意给定的比特是on的概率是 $1−p_0$ 。所以误报概率,也就是随机模式 $y$ 中所有 $w$ 个比特是on的概率是:

        上面的推导过程让我们搞清楚了,在某些条件下,不用担心发生误报。比如,考虑设置$SDR$的参数为 $n=1024$ 和 $w=2$ 。存储$20$个向量也就是 $M=20$,发生误报的概率大约是$1/680$。但是,如果 $w$ 增大到$20$,概率会急剧地下降到大约$\frac{1}{5500000000}$。这是合并特征的一个显著特征。让我们用图表感受一下实际数值

        这三条线表现了SDR的几个维度在 w=200 时的计算值。我们看到随着存储模式的数目的变化,误差率单调增大。更重要的是,本图说明了SDR的大小是关键因素:少量的比特(1000个比特)导致相对较高的误差率,而更大的向量(10000以上的比特)更加健壮。

$SDR$的合并在噪声环境下的健壮性

        正如上面提到的,合并向量 $X$ 中on比特的准确数目是 $\widetilde{w_x} = n(1-p_0)$ ,这里我们使用了波浪线表示法来代表合并向量。假设 $n \geq \widetilde{w_x} \geq w$ ,我们可以计算出重叠集合的期望大小:

        如果发生匹配,我们需要大小为 $\theta$ 个或者更多比特(最多是 $w$ 个)的重叠。所以发生错误匹配的概率是:

        正如你所预料的,误差率会随着阈值降低而增大,但是这种折衷的影响可以通过增大 n 来减轻。假设向量模 n=1024 并且向量势 w=20 。如果存储20个向量也就是 M=20 ,精确匹配时的误报概率大约是50亿分之1。当阈值 θ=19 时误报率会增大到$1/123000000$。当阈值 $\theta=18$ 时误报率会增大到$1/4000000$。但是当阈值 $\theta=18$ 保持不变,如果你增大 $n$ 到$2048$,误报率会急剧地下降到$1/223000000000$!这个例子说明了$SDR$的合并特征对噪声的健壮性,而且它还是我们另一个更大的主题的例子:$SDR$长度的细微线性变化可以对误差率产生超指数的改善。

运算效率

        尽管$SDR$向量很大,但是运算复杂度依赖于on比特的数目 $w$ ,而不是向量的模 $n$ 。另外,因为向量是二进制的,所以可以在大多数CPU上快速运算。但是实际情况没有这么理想,因为采用了更标准的距离度量,复杂度通常是 $O(n)$ ,此外还要包括浮点运算。

大脑和HTM系统中的$SDR$

神经元的激活形式是$SDR$

        如果你观察新皮质中的部分神经元,你会发现它们的活动会是稀疏的,其中有很低比重的神经元是处于高度激活(传递脉冲)的状态,剩余的神经元是抑制的或者很缓慢地传递脉冲。$SDR$代表了一组神经元的活动,置$1$和置$0$比特分别表示激活和相对抑制的神经元。HTM系统的所有功能都是基于神经元和$SDR$之间的这个基本关联。
HTM认为神经元会处于数个状态之一:

  • 激活(传递脉冲)
  • 抑制(没有传递脉冲或者很缓慢地传递脉冲)
  • 预测(去极化后和传递脉冲前)
  • 预测后激活(传递脉冲之前的“微爆”)

神经网络预测是$SDR$的合并

        HTM序列记忆会对将要发生的情况作出多个同步的预测。这种能力是$SDR$合并特征的一个实例。对应到生物学是多组神经元细胞($SDR$)同时去极化。因为每个表征都是稀疏的,所以很多预测可以同步进行。比如,考虑实现HTM序列记忆的一层神经元。如果其中的1%是激活状态并且产生$20$个不同的预测,那么会有大约$20%$的神经元进入去极化/预测状态。即使有$20%$的神经元去极化,系统仍然能够可靠地排查是否有预测发生了。作为人而言,你不会意识到那些预测,因为预测状态的细胞没有传递脉冲。但是,如果发生了意外的输入信息,网络可以侦查它,你就会察觉到有什么不对劲。

突触是一种存储$SDR$的方式

        脑中的存储器称作“联想存储器”。在联想存储器中,一条$SDR$与另一条$SDR$相连,相连的这一条还会与其他的相连,联系会一直持续下去。$SDR$通过与其他$SDR$的联系会回忆起来。没有中心化的存储器或者随机存取。每个神经元都会参与形成$SDR$和学习关联。
        考虑一个神经元,如果我们想要识别一个特定的活动模式。为了达到这个目的,神经元会与模式中的激活细胞形成突触。一个神经元只需要形成少量的突触,通常会小于二十个,以便在大量细胞中准确地识别出模式,只要模式是稀疏的。形成新突触是脑中的几乎所有记忆的基础。
        但是我们不是只想要一个神经元来识别一个模式;我们想要一组神经元来识别一个模式。这样,一条$SDR$会唤起另一条$SDR$。我们想要$SDR$模式$A$唤起$SDR$模式$B$。只要模式B中的每个激活细胞组成二十个突触连接上模式$A$中任意的一些细胞,这就可以实现。
        如果$A$和$B$两种模式是在同一个神经元群体中前后相继的模式,那么习得的从模式$A$到模式$B$的关联是一个过渡,形成了序列记忆的基础。如果模式$A$和模式$B$在不同的神经元群体中,那么模式$A$会同时激活模式$B$。如果模式$A$中的神经元连接到模式$B$中的远端突触,那么模式$B$就是预测的模式。如果模式$A$中的神经元连接到模式$B$中的近端突触,那么模式$B$就是激活神经元组成的激活模式。
        所有的联想存储器的操作都使用相同的基本记忆机制,也就是在神经元的树突段形成新突触。因为所有的神经元都有数十个树突段和数以千计的突触,每个神经元不仅仅识别一种模式,而是数十种独立的模式。每个神经元都会参与形成很多不同的$SDR$。

总结

        $SDR$是脑的语言,同时HTM理论规定了如何创建、存储、回忆$SDR$和$SDR$序列。本章我们学习了$SDR$强大的数学特征,以及这些特征是如何让脑和HTM能够学习和归纳序列的。
        关于这部分内容以后会添中上官方使用的可视化工具展示$SDR$数值之间的变化因素,上面的一些概念需要结合整个HTM理论体系才能更好地理解,希望有时间也一并添加上来,关于该文摘自官方文档和youtube视频,翻译整理真费力….