Associative Memory Design via Path Embedding into a Graph

A graph theoretical procedure for storing a set of n-dimensional binary vectors as asymptotically stable equilibrium points of a discrete Hopfield neural network is presented. The method gives an auto-associative memory which stores an arbitrary memory set completely. Spurious memories might occur only in a small neighborhood of the original memory vectors, so cause small errors.     

An energy function-based design method for discrete hopfield associative memory with attractive fixed points

An energy function-based autoassociative memory design method to store a given set of unipolar binary memory vectors as attractive fixed points of an asynchronous discrete Hopfield network (DHN) is presented. The discrete quadratic energy function whose local minima correspond to the attractive fixed points of the network is constructed via solving a system of linear inequalities derived from the strict local minimality conditions. The weights and the thresholds are then calculated using this energy function. If the inequality system is infeasible, we conclude that no such asynchronous DHN exists, and extend the method to design a discrete piecewise quadratic energy function, which can be minimized by a generalized version of the conventional DHN, also proposed herein. In spite of its computational complexity, computer simulations indicate that the original method performs better than the conventional design methods in the sense that the memory can store, and provide the attractiveness for almost all memory sets whose cardinality is less than or equal to the dimension of its elements. The overall method, together with its extension, guarantees the storage of an arbitrary collection of memory vectors, which are mutually at least two Hamming distances away from each other, in the resulting network.     

Sparse stable systems

In the design of decentralized networked systems, it is important to know whether a given network topology can sustain stable dynamics. We consider a basic version of this problem here: given a vector space of sparse real matrices, does it contain a stable (Hurwitz) matrix? Said differently, is a feedback channel (corresponding to a non-zero entry) necessary for stabilization or can it be done without? We provide in this paper a set of necessary conditions and a set of sufficient conditions for the existence of stable matrices in a vector space of sparse matrices. We further prove some properties of the set of sparse matrix spaces that contain Hurwitz matrices. The conditions we exhibit are most easily stated in the language of graph theory, which we thus adopt in this paper.     

基于图划分抽样算法的图表示学习

在基于神经网络的图表示算法中,当节点属性维度过高、图的规模过大时,从内存到显存的数据传输会成为训练性能的瓶颈。针对这类问题,该方法将图划分算法应用于图表示学习中,降低了内存访问的I/O开销。该方法根据图节点的度数,将图划分成若干个块,使用显存缓存池存储若干个特征矩阵块。每一轮训练,使用缓存池中的特征矩阵块,以此来减少内存到显存的数据拷贝。针对这一思想,该方法使用基于图划分的抽样算法,设计显存的缓存池来降低内存的访问,运用多级负采样算法,降低训练中负样本采样的时间复杂度。在多个数据集上,与现有方法对比发现,该方法的下游机器学习准确率与原算法基本一致,训练效率可以提高2~ 7倍。实验结果表明,基于图划分的图表示学习能高效训练模型,同时保证节点表示向量的测试效果。今后的课题可以使用严谨的理论证明,阐明图划分模型与原模型的理论误差。     

Support Vector的几何解释及其在联想记忆中的应用

利用闭凸集上的投影解释support vector的几何意义，利用支持超平面讨论线性分类器的设计问题，对线性可分情形，Support vector由一类数据集合闭凸包在另一类数据集合闭凸包上投影的非零系数向量组成，SVM所决定的超平面位于两投影点关于各自数据集合支持超平面的中间，作为应用，文中给出一种设计理想联想记忆前馈神经网络的方法，它是FP算法的一般化。     

Nonlinear parameter estimation by weighted linear associativememory with nonzero interception

The method of linear associative memory (LAM) has recently been applied in nonlinear parameter estimation. In the method of LAM, a model response, nonlinear with respect to the parameters, is approximated linearly by a matrix, which maps inversely from a response vector to a parameter vector. This matrix is determined from a set of initial training parameter vectors and their response vectors according to a given cost function, and can be updated recursively and adaptively with a pair of newly generated parameter-response vector. The advantage of LAM is that it can yield good estimation of the true parameter from a given observed response even if the initial training parameter vectors are far from the true values. In a previous paper, we have significantly improved the LAM method by introducing a weighted linear associative memory (WLAM) approach for nonlinear parameter estimation. In the WLAM approach, the contribution of each pair of parameter-response vector to the cost function is weighted in a way such that if a response vector is closer to the observed one then its pair plays more important role in the cost function. However, in both LAM and WLAM, the linear association is introduced with zero interceptions, which would not give an exact association even if the model function is linear and so will affect the efficiency of the estimations. In this paper, we construct a theory which introduces a linear association memory with a nonzero interception (WLAMB). The results of our estimation tests on two quite different models, Van der Pol equation and somatic shunt cable model, suggest that WLAMB can still significantly improve on WLAM.     

用非线性存储方案设计SIMD计算机的一般方法

非线性存储方案能在处理单元数等于存储体数的情况下,使ＳＩＭＤ机实现多种访存模式无冲突,提高其整体性能,文中提出一种用线性存储方案设计ＳＩＭＤ 一般方法,在存储方案给定的前提下,针对有限的模板集设计出同时满足存储器访问无冲突和互联网的并行结构,首先,用布尔向量空间表示模板,并指出模板与ＬＣ置换的对应关系,在此基础上,提出设计局部地址生成逻辑和增强的间接二进制Ｎ方体网络的方法,由于板集中任意的访存方式     

Construction of a distributed associative memory on the basis of bayes discriminant rule

The purpose of this correspondence is to propose a new construction method of distributed associative memory which operates with discrete-valued signals. In this method, memorized pairs of vectors (cue vectors and data vectors) are recorded in the form of a matrix W and a vector T. From an input vector X, the data vector is recalled by an operation u(XW + T) where X is a cue vector or a noisy cue vector. and u is a quantizing function. The methods of memorization and recall are similar to the Associatron; however, the proposed model can recall the data vectors optimally in Bayesian sense even when noisy cue vectors are given as the input vectors.     

一种实现网络入侵检测的高效算法及其实现架构

为了实现网络入侵检测系统中的精确字符串匹配,本文提出了一种基于叶子-附加和二叉搜索树的字符串匹配算法及其实现架构;首先采用叶子-追加算法来对给定的模式集进行处理,以消除模式之间的重叠。然后采用二叉搜索树算法提取叶子模式及其匹配向量来构建二叉搜索树,并根据每个节点的比较结果,通过左遍历或右遍历来实现字符串的精确匹配;为了进一步提高字符串匹配算法的内存效率,提出了级联二叉搜索树;最后給出了实现精确字符串匹配的总体架构和各个功能模块的架构;实验结果表明,本文提出的设计不仅在内存效率和吞吐量方面优于目前先进的设计技术,而且具有灵活的可扩展性。     

Randomized projective methods for the construction of binary sparse vector representations

Properties of randomized binary vector representations with adjustable sparseness are investigated. Such representations are formed from input vectors by projecting them using a random matrix with ternary elements {-1, 0, +1}. The accuracy of estimating measures of similarity-difference between initial vectors composed of floating-point numbers and output binary vectors is analyzed. The vector representations obtained can be used to efficiently process large arrays of input multidimensional vectors in applications related to searching, classification, associative memory, etc.     

求解图的最大独立集的一种算法

如何寻找图的最大独立集这个问题是一个古老的难题。文章从图论的基本概念入手 ,得到了一种基于图的邻接矩阵的寻找图的极大独立集和最大独立集的算法 ,并得到其算法复杂度为 O(nn!/(m!(n - m) !) )     

构造通用简约验证测试集U(p,ω)矩阵的一般公式与程序实现

本文旨在解决伪穷举测试技术中的一个问题。文中通过递归方法产生一个描述二进制多维空间全部矢量的生成关系图。在研究该图性质的基础上,推导出构造最优通用简约验证测试集U(p,ω)矩阵的一般公式。最后,给出一个GCLISP的应用程序。     

采用线性不定方程组的Hamiltonian存在判定条件

本文基于{0，1}线性不定方程组和顶边关联矩阵．提出了一个基于无向Hamiltonian图的充要判定定理。并证明了满足该定理的不定方程组解向量对应给定圄的Hamiltonian回路中边的集合，本文还推导出两个可以基于矩阵秩的Hamiltonian回路存在的必要判据。     

The indirect k-ary n-cube for a vector processing environment

In an earlier paper we introduced an indirect binary n-cube memory server network which has adaptive properties making it useful in a parallel vector processing environment. The memory server network, due to a special choice in the design of the basic switch node, has the property that N vector processors issuing vector fetches with similar strides are forced into lock step after an initial startup investment.

In this paper we extend this work to the case of the indirect k-any n-cube. As this network has a more favorable memory latency scaling of log_kN, one expects that the short vector performance will be improved as k is increased for a given N. We find this to be the case. We also find that the cost of the memory server system scales in a manner which prefers modest values of k above 2.     

图数据连续发布中的隐私保护方法

随着互联网技术的发展和智能终端的普及,社交网络中产生了大量用户隐私数据,公开发布社交网络数据将提高用户隐私泄露的风险,需要对数据进行匿名化处理然后进行发布。传统社交网络k度匿名方法在图数据连续发布中的匿名方式,存在大量冗余计算及无法抵抗度时序推理攻击的问题,为此,提出一种连续发布图数据的改进k度匿名算法。通过定义度时序矩阵来一次性地构建满足k匿名性要求的k度时序矩阵,在k度时序矩阵的基础上提取不同时刻的k度向量,将其作为时刻图的匿名向量,通过图修改方法对前一时刻的匿名图进行处理,得到后续一系列的匿名图版本,从而缩短每一次重新匿名所消耗的时间,同时抵抗基于度变化实现的度时序背景知识攻击。在真实社交网络数据集上进行实验,结果表明,相对kDA算法,该算法的总体运行效率以及网络结构属性可用性均较优。     

The convergence of Hamming memory networks

The convergence properties of Hamming memory networks are studied. It is shown how to construct the network so that it probably converges to an appropriate result, and a tight bound is given on the convergence time. The bound on the convergence time is largest when several stored vectors are at the minimum distance from the input vector. For random binary vectors, the probability for such situations to occur is not small. With a specific choice of parameter values, the worst-case convergence time is on the order of p ln (pn), where p is the memory capacity and n is the vector length. By allowing the connection weights to change during the computation, the convergence time can be decreased considerably.     

On the design of dynamic associative neural memories

We consider the design problem for a class of discrete-time and continuous-time neural networks. We obtain a characterization of all connection weights that store a given set of vectors into the network, that is, each given vector becomes an equilibrium point of the network. We also give sufficient conditions that guarantee the asymptotic stability of these equilibrium points.     

A theoretical investigation into the performance of the Hopfieldmodel

An analysis is made of the behavior of the Hopfield model as a content-addressable memory (CAM) and as a method of solving the traveling salesman problem (TSP). The analysis is based on the geometry of the subspace set up by the degenerate eigenvalues of the connection matrix. The dynamic equation is shown to be equivalent to a projection of the input vector onto this subspace. In the case of content-addressable memory, it is shown that spurious fixed points can occur at any corner of the hypercube that is on or near the subspace spanned by the memory vectors. Analysed is why the network can frequently converge to an invalid solution when applied to the traveling salesman problem energy function. With these expressions, the network can be made robust and can reliably solve the traveling salesman problem with tour sizes of 50 cities or more.     

融合物品信息的社会化推荐算法

大多数社会化推荐算法仅考虑约束用户的特征向量并未限制物品的特征向量对推荐系统性能的影响,针对这一问题,提出了一种融合物品信息的社会化推荐算法。该算法先通过用户与物品的交互图构建物品相似性网络,在此基础上采用随机游走和SkipGram的方法构造出隐性物品相似性网络,再通过图神经网络的方法学习物品隐性相似性网络、社交网络和用户物品交互图,得到用户和物品编码的特征向量,最后在矩阵分解的基础上同时对用户和物品的特征向量做进一步约束,采用迭代更新的方式获取用户和物体最终的特征向量。为验证推荐算法的性能,在FilmTrust、Ciao和Douban数据集上进行实验验证。实验结果表明,所提出的ISGCF算法与经典的推荐算法相比,推荐效果更好,有效地缓解了冷启动问题。