SSAKG 2.0：一个用于结构关联序列记忆和基于上下文检索的开源软件包

# SSAKG 2.0：一个用于结构联想序列记忆和基于上下文检索的开源软件包
来源：https://arxiv.org/html/2609.01849
普热梅斯瓦夫·斯托克沃萨（Przemysław Stokłiosa）单位：管理与信息技术研究所单位：波兰别尔斯科-比亚瓦邮箱：[[email protected]](mailto:[email protected])雅努什·A·斯塔尔齐克（Janusz A. Starzyk）单位：信息与技术管理大学单位：波兰热舒夫邮箱：[[email protected]](mailto:[email protected])帕维乌·雷夫（Paweł Raif）单位：西里西亚理工大学单位：波兰格利维采邮箱：[[email protected]](mailto:[email protected])

###### 摘要
本文介绍了SSAKG 2.0，一个用于构建和操作结构化序列联想知识图（SSAKG）的开源软件包。SSAKG将对象表示为图的顶点，将有序序列表示为图连接的结构模式。由此产生的稀疏图被用作联想记忆，其中可以从部分、无序的上下文重构完整的序列。2.0版本引入了新的算法，利用计算机内存的单个比特来高效地搜索图连接。该软件包在Python中实现，而性能关键的图操作则在C中实现并通过Python接口暴露。这种混合实现提供了一个灵活的高级编程环境，同时减少了与大规模稀疏图相关的内存和计算开销。算法使用随机生成的数值序列、源自NLTK语料库句子的序列和mRNA序列进行了评估。实验表明，该软件包能够从部分上下文中存储和重构序列，并为评估图密度、序列长度和内存大小对检索性能的影响提供了基础。SSAKG 2.0基于Apache 2.0开源许可分发。该软件包包含文档和可复现的示例，并可通过GitHub和Python包索引（PyPI）公开获取。

关键词序列检索⋅\\cdot基于上下文的联想⋅\\cdot联想知识图⋅\\cdot图密度⋅\\cdotssakg软件包

## 1引言
联想记忆提供了一种机制，用于从部分、不完整或有噪声的线索中检索存储的信息，而不是从显式地址中检索。这一思想在神经计算和认知建模中发挥了重要作用，催生了多种按内容寻址的存储器架构，包括早期的基于相关性的联想记忆、Hopfield网络和稀疏分布式记忆[1 (https://arxiv.org/html/2609.01849#bib.bib5),2 (https://arxiv.org/html/2609.01849#bib.bib4),3 (https://arxiv.org/html/2609.01849#bib.bib6),4 (https://arxiv.org/html/2609.01849#bib.bib10),5 (https://arxiv.org/html/2609.01849#bib.bib11)]。稀疏分布式记忆与本工作特别相关，因为它展示了如何利用稀疏连接来获得联想召回，同时保持存储容量与记忆连接数量之间的关系[6 (https://arxiv.org/html/2609.01849#bib.bib9),3 (https://arxiv.org/html/2609.01849#bib.bib6)]。尽管这些方法在表示和检索机制上存在显著差异，但它们共享一个总体目标，即基于内容或部分上下文信息恢复存储的信息。一个相关但不同的问题是有序序列的联想存储和检索[7 (https://arxiv.org/html/2609.01849#bib.bib16),8 (https://arxiv.org/html/2609.01849#bib.bib17),9 (https://arxiv.org/html/2609.01849#bib.bib18),10 (https://arxiv.org/html/2609.01849#bib.bib15)]。在许多应用中，需要回忆的信息不是单个静态模式，而是元素的有序集合，其时间或位置关系至关重要。例子包括符号和数值序列、自然语言表达式、生物序列、行为轨迹和时间事件流。在这种情况下，联想记忆必须解决两个相关任务：识别与部分上下文相关的元素，并在需要时重构它们的原始顺序。因此，序列存储和检索一直使用各种循环神经网络、联想记忆和外部存储器架构进行研究。

结构化联想知识图（SSAKG）使用基于图的表示方法来解决这个问题，其中对象由顶点表示，序列通过它们之间的结构关系进行编码。不是将每个序列作为独立的记录存储，而是将多个序列叠加在一个公共图中，并可能共享顶点和连接。因此，存储的序列可以表示为嵌入在图中的结构模式，而检索则由包含其元素子集的上下文触发。该上下文可能是不完整的，并且不一定需要保留元素的原始顺序。

SSAKG模型及其基本序列重构算法在我们之前的工作中已有介绍[11 (https://arxiv.org/html/2609.01849#bib.bib3)]。该研究探讨了图密度、记忆容量和检索准确率之间的关系，并证明了结构化的图表示可以在不将每个序列作为单独记录存储的情况下支持基于上下文的序列重构。后续工作进一步[12 (https://arxiv.org/html/2609.01849#bib.bib14)]研究了基于稀疏图的联想记忆的可扩展性，并将此方法与现代Hopfield型架构[13 (https://arxiv.org/html/2609.01849#bib.bib7)]进行了比较。我们证明，与MHN相比，我们的方法显著提高了联想记忆容量和搜索准确性，同时对于非常大的记忆需要更少的计算机存储。

当前工作的目标不同。本文不是介绍一个新的联想记忆模型，而是介绍了SSAKG 2.0，一个开源且可重用的SSAKG框架及其相关算法的软件实现。该软件包为构建、修改和查询结构化联想记忆，以及尝试替代的序列表示和检索过程提供了实用的环境。从这个意义上说，当前工作的主要贡献不仅在于算法描述，还在于将先前开发的模型转化为一个有文档记录、可扩展且可复现的软件框架。

SSAKG 2.0的一个特别关注点是稀疏图连接的高效表示和处理。由于图连接由二进制信息表示，计算机内存的单个比特可以用于高效地编码和搜索多个结构关系。该软件包结合了高级Python接口和用C实现的性能关键操作。这种设计允许用户通过相对简单的编程接口构建和操作联想记忆，同时在比特级别执行选定的图操作。

由此产生的方法不同于将记忆实现为通过寻址机制访问的外部可微分资源的架构，例如神经图灵机[14 (https://arxiv.org/html/2609.01849#bib.bib8)]和可微分神经计算机[15 (https://arxiv.org/html/2609.01849#bib.bib12),16 (https://arxiv.org/html/2609.01849#bib.bib13)]是一个很好的对比点：记忆是通过网络访问的外部资源，通过寻址机制；而在SSAKG中，图本身构成了联想记忆：存储的信息由连接结构直接表示，检索是通过利用上下文元素和候选序列组件之间的结构关系来执行的。

该软件包旨在作为通用的研究和实验工具，而不是特定领域的应用程序。存储的元素可以表示任意符号、数值标识符、单词或其他离散对象。这允许相同的基础实现应用于不同类别的序列数据。在本研究中，SSAKG主要通过受控实验进行评估，旨在检查记忆大小、图密度、序列长度和上下文大小对检索性能的影响。我们在SSAKG的GitHub页面[17 (https://arxiv.org/html/2609.01849#bib.bib1)]上提供了额外的示例，以说明如何将相同的表示应用于各种符号数据，使用语言和生物序列。

本工作的主要贡献如下：

1. (i)一个用于从部分上下文信息存储和检索有序序列的结构化联想知识图记忆的开源实现。
2. (ii)一个可重用的软件架构，将高级Python接口与性能关键的低级图操作分离。
3. (iii)用于表示和搜索图连接的比特级算法，通过C扩展实现并与Python包集成。
4. (iv)支持基于上下文的检索和有序序列重构的算法，包括处理重复序列元素。
5. (v)在不同记忆和序列条件下，对该软件包及其检索算法的实验评估。
6. (vi)一个可复现且可扩展的软件分发，包括文档、示例、源代码以及通过公共仓库可用的软件包。

论文的其余部分组织如下。第2节介绍了SSAKG记忆的基本概念和符号。第3-7节描述了序列表示、存储过程、检索算法和软件实现。第8节介绍了实验评估。第9节讨论了该软件包的计算特性、局限性以及可能的未来扩展。最后，第10节总结了主要结论。

## 2预备知识
经典联想记忆通常关注模式检索，而SSAKG则设计用于检索有序序列。SSAKG解决的问题不仅仅是模式补全，而是从部分且可能无序的元素子集中重构有序序列。SSAKG不是将序列作为单独的记录存储，而是将它们编码在共享图的拓扑结构中。几个序列可能共享共同元素，因此无需独立存储每个序列。共享对象成为图中的共享节点，连接结构编码了对象在序列中出现所形成的关系[11 (https://arxiv.org/html/2609.01849#bib.bib3)]。

### 2.1符号、序列和上下文
联想记忆SAMSAM支持存储称为序列的有序符号串。可以通过提供其片段来检索一个序列。该片段可以是无序的。这样的无序片段称为上下文C。最初，我们选择一个符号集N。SSAKG记忆存储符号对象的有序序列。设N=\{n_1,n_2,...,n_k\}N=\\{n_{1},n_{2},\\dots,n_{k}\\}表示可用符号的集合。序列S是一个有序元组：为了从记忆中读取一个序列，我们需要指定它的一个片段，即所谓的上下文：例如，长度为5的序列可以采取以下形式：S=(n_2,n_1,n_3,n_10,n_1)S=(n_{2},n_{1},n_{3},n_{10},n_{1})而读取该序列所需的上下文可以是一组符号：C=\{n_10,n_1,n_3\}C=\\{n_{10},n_{1},n_{3}\\}

### 2.2序列的图表示
联想记忆由图G_{sam}=(V,E)G_{sam}=(V,E)表示，其中k=|N|k=|N|个顶点。每个顶点v∈Vv\\in V与相应的符号n∈Nn\\in N相关联。该图构成了联想记忆的基础。其邻接矩阵A_{sam}A_{sam}存储在计算机内存中。

当存储一个序列时，其元素被映射到顶点，并将表示其顺序所需的关系添加到联想图中。

设G_{s}G_{s}表示与序列S相关的图结构，G_{sam}G_{sam}表示表示完整联想记忆的图。存储S包括将G_{s}G_{s}的结构关系合并到G_{sam}G_{sam}中：G_{sam}←G_{sam}∪G_{s}G_{sam}\\leftarrow G_{sam}\\cup G_{s}。G_{s}G_{s}的确切结构决定了检索期间可用的信息，因此直接影响联想记忆的效率、鲁棒性和容量。该图可以由邻接矩阵A_{sam}A_{sam}表示。最初，图不包含边；矩阵用零填充。当存储序列时，会创建适当的边。一个序列由相应的图G_{s}G_{s}表示。序列的元素是图的顶点，按给定顺序排列。关键元素是选择代表序列的图G_{s}G_{s}。正是这个图的结构使得构建快速高效的序列读取算法成为可能。将适当的顶点连同图G_{s}G_{s}的边插入到图G_{sam}G_{sam}中。A_{sam}A_{sam}矩阵修改如下：A_{sam}[\{v_1,v_2,...,v_i\}]=A_{s}A_{sam}[\\{v_{1},v_{2},\\cdots,v_{i}\\}]=A_{s}(1)，其中A_{sam}[\{v_1,v_2,...,v_i\}]A_{sam}[\\{v_{1},v_{2},\\cdots,v_{i}\\}]表示对应于顶点集\{v_1,v_2,...,v_i\}\\{v_{1},v_{2},\\cdots,v_{i}\\}的矩阵A_{sam}A_{sam}的子矩阵。考虑的最简单情况是使用完全图。这在[18 (https://arxiv.org/html/2609.01849#bib.bib2)]中有更详细的描述。如果序列包含重复的符号，则在图中为其创建新的顶点。矩阵A_{sam}A_{sam}被动态扩展。

## 3序列存储
### 3.1SSAKG 2.0的动机
先前的工作建立了SSAKG模型并评估了其序列重构算法[11 (https://arxiv.org/html/2609.01849#bib.bib3),12 (https://arxiv.org/html/2609.01849#bib.bib14)]。SSAKG 2.0的目标不同：提供一个高效、可重用且可扩展的软件实现，以实现该模型及其相关算法。

SSAKG软件包实现了一个基于稀疏图表示的联想记忆。序列通过建立对应于其元素的图顶点之间的结构关系来存储。由此产生的图被所有存储的序列共享，允许从部分上下文信息中检索序列。该实现的一个重要特点是它在保留序列元素顺序的同时，还支持包含重复符号的序列。

以下示例说明了该软件包中实现的序列存储基本原理。它还为后续章节中描述的检索算法所使用的记忆结构提供了一个简单的表示。

### 3.2基本序列表示
考虑一个联想记忆图G_{sam}G_{sam}，包含6个顶点\{1,2,3,4,5,6\}\\{1,2,3,4,5,6\\}，初始时没有边。因此，它的邻接矩阵是一个6×66×6的全零矩阵。包含三个元素的序列可以用一个具有三个顶点的完全图G_{s}G_{s}来表示，其邻接矩阵是A_{s}=K_{3}A_{s}=K_{3}。

需要注意的是，