(ProQuest: ... denotes non-US-ASCII text omitted.)
María Elena Acevedo 1 and Cornelio Yáñez-Márquez 2 and Marco Antonio Acevedo 1
Recommended by Wei-Chiang Hong
1, Department of Communications and Electronic Engineering at Superior School of Mechanical and Electrical Engineering, National Polytechnic Institute, Avenue IPN s/n, Col. Lindavista, C.P. 07738 Mexico City, Mexico
2, Artificial Intelligence Laboratory, Computation Research Center, National Polytechnic Institute, Avenue Juan de Dios Bátiz s/n, C.P. 07738 Mexico City, Mexico
Received 17 March 2010; Accepted 21 June 2010
1. Introduction
Concept Lattices is the common name for a specialized form of Hasse diagrams [1] that is used in conceptual data processing. Concept Lattices are a principled way of representing and visualizing the structure of symbolic data that emerged from Rudolf Wille efforts to restructure lattice and order theory in the 1980s. Conceptual data processing, also known as Formal Concept Analysis, has become a standard technique in data and knowledge processing that has given rise to applications in data visualization, data mining, information retrieval (using ontologies), and knowledge management. Organization of discovered concepts in the form of a lattice-structure has many advantages from the perspective of knowledge discovery. It facilitates insights into dependencies among different concepts mined from a dataset. Lattices of concepts have been implemented with a number of different algorithms [2-7]. Any of them can generate a very large number of concepts; therefore, a suitable method is required for an efficient storage and retrieval of parts of the lattice. The task of efficiently organizing and retrieving various nodes of a lattice is the focus of this work. A concept is a pair that consists of a set of objects and a particular set of attribute values shared by the objects. From an initial table, with rows representing the objects and columns representing the attributes, a concept lattice can be obtained. From this structure, we can retrieve an object from the attribute or vice versa, and these pairs form a concept.
The main goal of an Associative Memory is to associate pairs of patterns for recalling one pattern presenting its corresponding pattern; the recalling is done in one direction only. In the particular case of Bidirectional Associative Memories (BAM), we can recall any of the two patterns belonging to a pair just presenting one of them; therefore, the recalling is in both directions. This behavior allows BAM to be a suitable tool for storing and retrieving concepts which form a particular lattice concept. The first step for achieving this task is to apply any of the existing algorithms to obtain the lattice concept; in this work, we use the Linding's algorithm [5]; then we store each node (concept) associating the objects and attributes forming that concept. Once we stored all concepts, we are able to retrieve them by presenting an object or an attribute. The model of BAM used here is the Alpha-Beta Bidirectional Associative Memory [8]. The main reason for using this model is because it presents perfect recall of the training set; this means that it can recall every pair of patterns that it associated, no matter the size of the patterns or the number of these. This advantage is not presented by other BAM models which present stability and convergence problems or limit their use for a particular number of patterns or to the nature of them, such as, Hamming distance or linear dependency [9-19].
In Section 2, we present a brief discussion on Formal Context Analysis. In Section 3, we introduce the basic concepts of Associative Models, in particular the Alpha-Beta Model, because it is the base of Alpha-Beta BAM. Then, we present the theoretical foundations of our associative model which assure the perfect recall of the training set of patterns with no limits in the number or nature of patterns. We describe the software that implements our algorithm in Section 4 and we show an example.
2. Formal Concept Analysis
Formal Concept Analysis (FCA) was first proposed by Wille in 1982 [20] as a mathematical framework for performing data analysis. It provides a conceptual analytical tool for investigating and processing given information explicitly [21]. Such data is structured into units, which are formal abstractions of "concepts " of human thought allowing meaningful and comprehensible interpretation. FCA models the world as being composed of objects and attributes . It is assumed that an incident relation connects objects to attributes. The choice of what is an object and what is an attribute is dependent on the domain in which FCA is applied. Information about a domain is captured in a "formal context". A formal context is merely a formalization that encodes only a small portion of what is usually referred to as a "context ". The following definition is crucial to the theory of FCA.
Definition 2.1.
A formal context K=(G,M,I) is a triplet consisting of two sets G (set of objects) and M (set of attributes) and a relation I between G and M.
Definition 2.2.
A formal concept in a formal context is a pair (A,B) of sets A⊆G and B⊆M such that A[arrow up]=B and B[arrow down]=A (completeness constraint), where A[arrow up]={m∈M|"gIm for all g∈A} (i.e., the set of attributes common to all the objects in A ), and B[arrow down]={g∈G|"gIm for all m∈B} (i.e., the set of objects that have all attributes in B ). By gIm we denote the fact that object g has attribute m .
The set of all concepts of a context (G,M,I) is denoted by B(G,M,I) . This consists of all pairs (Ac ψB) such that A[arrow up] .........B and B[arrow down] .........A , where A⊆G and B⊆M .
Definition 2.3.
Specificity-generality order relationship. If (A1 ,B1 ) and (A2 ,B2 ) are concepts of a context, then (A1 ,B1 ) is called a subconcept of (A2 ,B2 ) if A1 ⊆A2 (or equivalently B1 ⊇B2 ). This sub-super concept relation is written as (A1 ,B1 )≤(A2 ,B2 ) . According to this definition, a subconcept always contains fewer objects and greater attributes than any of its super concepts.
2.1. Concept Lattice
A set of all concepts of the context (G,M,I) (denoted by B(G,M,I) ) when ordered with the order relation ≤ (a subsumption relation) defined above forms a concept lattice of the context and is denoted by B(G,M,I) .
A lattice is an ordered set V with an order relation in which for any given two elements x and y , the supremum and the infimum elements always exist in V . Furthermore, such a lattice is called a complete lattice if supremum and infimum elements exist for any subset X of V . The fundamental theorem of FCA states that the set of formal concepts of a formal context forms a complete lattice.
This complete lattice, which is composed by formal concepts, is called a concept lattice .
A Concept lattice can be visualized as a graph with nodes and edges/links. The concepts at the nodes from which two or more lines run up are called meet concepts (i.e., nodes with more than one parent) and the concepts at the nodes from which two or more lines run down are called join concepts (i.e., nodes with more than one child).
A join concept groups objects which share the same attributes and a meet concept separates out objects that have combined attributes from different parents (groups of objects). Each of these join and meet concepts creates a new sub- or super-category or class of a concept.
3. Alpha-Beta Bidirectional Associative Memories
In this section, the Alpha-Beta Bidirectional Associative Memory is presented. However, since it is based on the Alpha-Beta autoassociative memories, a summary of this model will be given before presenting our model of BAM.
3.1. Basic Concepts
Basic concepts about associative memories were established three decades ago in [22-24]; nonetheless, here we use the concepts, results, and notation introduced in [25]. An associative memory M is a system that relates input patterns and outputs patterns, as follows: x[arrow right]M[arrow right]y with x and y the input and output pattern vectors, respectively. Each input vector forms an association with a corresponding output vector. For k integer and positive, the corresponding association will be denoted as (xk ,yk ). Associative memory M is represented by a matrix whose ij th component is mij . Memory M is generated from an a priori finite set of known associations, known as the fundamental set of associations.
If μ is an index, the fundamental set is represented as {(xμ ,yμ )|"μ=1,2,...,p} with p being the cardinality of the set. The patterns that form the fundamental set are called fundamental patterns. If it holds that xμ =yμ , for all μ∈{1,2,...,p}, M is autoassociative , otherwise it is heteroassociative ; in this case, it is possible to establish that ∃μ∈{1,2,...,p} for which xμ ≠yμ . A distorted version of a pattern xk to be recovered will be denoted as x...k . If when feeding a distorted version of x[varpi] with [varpi]={1,2,...,p} to an associative memory M , it happens that the output corresponds exactly to the associated pattern y[varpi] , we say that recall is perfect.
3.2. Alpha-Beta Associative Memories
Among the variety of associative memory models described in the scientific literature, there are two models that, because of their relevance, it is important to emphasize: morphological associative memories which were introduced by Ritter et al. [18] and Alpha-Beta associative memories. Because of their excellent characteristics, which allow them to be superior in many aspects to other models for associative memories, morphological associative memories served as a starter point for the creation and development of the Alpha-Beta associative memories.
The Alpha-Beta associative memories [25] are of two kinds and are able to operate in two different modes. The operator α is useful at the learning phase, and the operator β is the basis for the pattern recall phase. The heart of the mathematical tools used in the Alpha-Beta model is two binary operators designed specifically for this model. These operators are defined as follows: first, we have the sets A={0,1} and B={0,1,2} ; then the operators α and β are defined in Tables 1 and 2, respectively.
Table 1: Alpha operator. α:A×A[arrow right]B .
x | y | α(x,y) |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 2 |
1 | 1 | 1 |
Table 2: Beta operator. β:B×A[arrow right]A .
x | y | β(x,y) |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
2 | 0 | 1 |
2 | 1 | 1 |
The sets A and B , the α and β operators, along with the usual ⋀ (minimum) and ⋁ (maximum) operators, form the algebraic system (A,B,α,β,⋀,⋁) which is the mathematical basis for the Alpha-Beta associative memories. Below are shown some characteristics of Alpha-Beta autoassociative memories.
(1) The fundamental set takes the form {(xμ ,xμ )|"μ=1,2,...,p} .
(2) Both input and output fundamental patterns are of the same dimension, denoted by n .
(3) The memory is a square matrix, for both modes, V and Λ . If xμ ∈An , then
[figure omitted; refer to PDF] And according to α:A×A[arrow right]B , we have that vij and λij ∈B , for all i∈{1,2,...,n} and for all j∈{1,2,...,n} .
In the recall phase, when a pattern xμ is presented to memories V and Λ , the i th components of recalled patterns are [figure omitted; refer to PDF] The next two theorems show that Alfa-Beta autoassociative memories max and min are immune to certain amount of additive and subtractive noise, respectively. These theorems have the original numbering presented in [25] and are an important part of the mathematical foundations for Alfa-Beta BAM theory.
Theorem 3.1.
Let {(xμ ,xμ )|"μ=1,2,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type ⋁ represented by V, and let x...∈ An be a pattern altered with additive noise with respect to some fundamental pattern xω , with ω∈{1,2,...,p} . If x... is presented to V as input, and also for every i∈{1,...,n} it holds that ∃j=j0 ∈{1,...,n} , which is dependent on ω and i such that vij0 ≤α(xω ,x...j0 ) , then recall VΔβ x... is perfect; that is, to say that VΔβ x...=xω .
Theorem 3.2.
Let {(xμ ,xμ )|"μ=1,2,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type ⋀ represented by Λ, and let x...∈An be a pattern altered with subtractive noise with respect to some fundamental pattern xω , with ω∈{1,2,...,p} . If x... is presented to memory Λ as input, and also for every i∈{1,...,n} it holds that ∃j=j0 ∈{1,...,n}, which is dependent on ω and i , such that λij0 ≤α(xω ,x...j0 ) , then recall Λ∇β x... is perfect; that is, to say that Λ∇β x...=xω .
With these bases we proceed to describe Alfa-Beta BAM model.
3.3. Alpha-Beta Bidirectional Associative Memories
Usually, any bidirectional associative memory model appearing in current scientific literature has the following scheme showed in Figure 1.
Figure 1: General scheme of a Bidirectional Associative Memory.
[figure omitted; refer to PDF]
A BAM is a "black box" operating in the following way: given a pattern x , associated pattern y is obtained, and given the pattern y , associated pattern x is recalled. Besides, if we assume that x... and y... are noisy versions of x and y , respectively, it is expected that BAM could recover all corresponding free noise patterns x and y .
The first bidirectional associative memory (BAM), introduced by Kosko [26], was the base of many models presented later. Some of these models substituted the learning rule for an exponential rule [9-11]; others used the method of multiple training and dummy addition in order to reach a greater number of stable states [12], trying to eliminate spurious states. With the same purpose, linear programming techniques [13] and the descending gradient method [14, 15] have been used, besides genetic algorithms [16] and BAM with delays [17, 27]. Other models of noniterative bidirectional associative memories exist, such as, morphological BAM [18] and Feedforward BAM [19]. All these models have arisen to solve the problem of low pattern recall capacity shown by the BAM of Kosko; however, none has been able to recall all the trained patterns. Also, these models demand the fulfillment of some specific conditions, such as a certain Hamming distance between patterns, solvability by linear programming, orthogonality between patterns, among other.
The model of bidirectional associative memory presented in this paper is Alpha-Beta BAM [28] and is based on the Alpha-Beta associative memories [25]; it is not an iterative process and does not present stability problems. Pattern recall capacity of the Alpha-Beta BAM is maximal, being 2min (n,m) , where m and n are the input and output patterns dimension, respectively. Also, it always shows perfect pattern recall without imposing any condition.
The model used in this paper has been named Alpha-Beta BAM since Alpha-Beta associative memories, both max and min, play a central role in the model design. However, before going into detail over the processing of an Alpha-Beta BAM, we will define the following.
In this work we will assume that Alpha-Beta associative memories have a fundamental set denoted by {(xμ ,yμ )|"μ=1,2,...,p}, xμ ∈An and yμ ∈Am , with A={0,1} , n∈Z+ , p∈Z+ , m∈Z+ and 1<p≤ min(2n ,2m ) . Also, it holds that all input patterns are different; M that is, xμ =xξ if and only if μ=ξ . If for all μ∈{1,2,...,p} it holds that xμ =yμ , the Alpha-Beta memory will be autoassociative ; if on the contrary, the former affirmation is negative, that is, ∃μ∈{1,2,...,p} for which it holds that xμ ≠yμ , then the Alpha-Beta memory will be heteroassociative .
Definition 3.3 (One-Hot).
Let the set A be A={0,1} and p∈Z+ , p>1 , k∈Z+ , such that 1≤k≤p. The k th one-hot vector of p bits is defined as vector hk ∈Ap for which it holds that the k th component is hkk =1 and the set of the components are hjk =0 , for all j≠k,1≤j≤p.
Remark 3.4.
In this definition, the value p=1 is excluded since a one-hot vector of dimension 1, given its essence, has no reason to be.
Definition 3.5 (Zero-Hot).
Let the set A be A={0,1} and p∈Z+ , p>1 , k∈Z+ , such that 1≤k≤p . The k th zero-hot vector of p bits is defined as vector h¯k ∈Ap for which it holds that the k th component is hkk =0 and the set of the components are hjk =1, for all j≠k, 1≤j≤p.
Remark 3.6.
In this definition, the value p=1 is excluded since a zero-hot vector of dimension 1, given its essence, has no reason to be.
Definition 3.7 (Expansion vectorial transform).
Let the set A be A={0,1} and n∈Z+ , ym∈Z+ . Given two arbitrary vectors x∈An and e∈Am , the expansion vectorial transform of order m, τe :An [arrow right]An+m , is defined as τe (x,e)=X∈An+m , a vector whose components are Xi =xi for 1≤i≤n and Xi =ei for n+1≤i≤n+m.
Definition 3.8 (Contraction vectorial transform).
Let the set A be A={0,1} and n∈Z+ , ym∈Z+ such that 1≤m<n. Given one arbitrary vector X∈An+m , the contraction vectorial transform of order m, τc :An+m [arrow right]Am , is defined as τc (X, m)=c∈Am , a vector whose components are ci =Xi+n for 1≤i<m.
In both directions, the model is made up by two stages, as shown in Figure 2.
Figure 2: Alpha-Beta BAM model scheme.
[figure omitted; refer to PDF]
For simplicity, first will be described the process necessary in one direction, in order to later present the complementary direction which will give bidirectionality to the model (see Figure 3).
Figure 3: Schematics of the process done in the direction from x to y . Here, only Stage 1 and Stage 2 are shown. Notice that hk k =1 , vi k =1 for all i≠k , 1≤i≤p , 1≤k≤p .
[figure omitted; refer to PDF]
The function of Stage 2 is to offer a yk as output (k=1,...,p) given an xk as input.
Now we assume that as input to Stage 2 we have one element of a set of p orthonormal vectors. Recall that the Linear Associator has perfect recall when it works with orthonormal vectors. In this work, we use a variation of the Linear Associator in order to obtain yk , parting from a one-hot vector hk in its k th coordinate.
For the construction of the modified Linear Associator, its learning phase is skipped and a matrix M representing the memory is built. Each column in this matrix corresponds to each output pattern yμ . In this way, when matrix M is operated with a one-hot vector hk , the corresponding yk will always be recalled.
The function of Stage 2 is to offer a yk as output (k=1,...,p) given an xk as input.
3.3.1. Theoretical Foundation of Stages 1 and 3
Below are presented 5 theorems and 9 lemmas with their respective proofs, as well as an illustrative example of each one. This mathematical foundation is the basis for the steps required by the complete algorithm, which is presented in Section 3.3.2. These theorems and lemmas numbering corresponds to the numeration used in [23].
By convention, the symbol [white square] will be used to indicate the end of a proof.
Theorem 3.9.
Let {(xμ ,xμ )|"μ=1,2,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type max represented by V , and let x... ∈An be a pattern altered with additive noise with respect to some fundamental pattern xω with ω∈{1,2,...,p} . Let us assume that during the recalling phase, x... is presented to memory V as input, and let us consider an index k∈{1,...,n} . The k th component recalled (VΔβ x...)k is precisely xkω if and only if it holds that ∃r∈{1,...,n} , dependant on ω and k , such that νkr ≤α(xkω ,x...r ) .
Proof.
[implies] ) By hypothesis we assume that (VΔβ x...)k =xkω . By contradiction, now suppose false that ∃r∈{1,...,n} such that νkr ≤α(xkω ,x...r ) . The former is equivalent to stating that for all r∈{1,...,n}, νkr >α(xkω ,x...r ) , which is the same to saying that for all r∈{1,...,n}, β(νkr ,x...r )>β[α(xkω ,x...r ),x...r ]=xkω . When we take minimums at both sides of the inequality with respect to index r , we have [figure omitted; refer to PDF] and this means that (VΔβ x...)k =...r=1n β(νkr ,x...r )>xkω , which contradicts the hypothesis.
[left double arrow] ) Since the conditions of Theorem 3.1 hold for every i ∈{1,...,n} , we have that VΔβ x...=xω ; that is, it holds that (VΔβ x...)i =xiω , for all i∈{1,...,n} . When we fix indexes i and j0 such that i=k yj0 =r (which depends on ω and k ), we obtain the desired result: (VΔβ x...)k =xkω .
Lemma 3.10.
Let {(Xk ,Xk )|"k=1,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type max represented by V , with Xk =τe (xk ,hk ) for k=1,...,p , and let F=τe (xk ,u)∈An+p be a version of a specific pattern Xk , altered with additive noise, being u∈Ap the vector defined as u=∑i=1phi . If during the recalling phase F is presented to memory V , then component Xn+kk will be recalled in a perfect manner; that is, (VΔβ F)n+k =Xn+kk =1 .
Proof.
This proof will be done for two mutually exclusive cases.
Case 1.
Pattern F has one component with value 0. This means that ∃j∈{1,...,n+p} such that Fj =0 ; also, due to the way vector Xk is built, it is clear that Xn+kk =1 . Then α(Xn+kk ,Fj )=α(1,0)=2 , and since the maximum allowed value for a component of memory V is 2, we have ν(n+k)j ≤α(Xn+kk ,Fj ) . According to Theorem 3.9, Xn+kk is perfectly recalled.
Case 2.
Pattern F does not contain a component with value 0. That is, Fj =1 for all j∈{1,...,n+p} . This means that it is not possible to guarantee the existence of a value j∈{1,...,n+p} such that ν(n+k)j ≤α(Xn+kk ,Fj ) , and therefore Theorem 3.9 cannot be applied. However, we will show the impossibility of (VΔβ F)n+k =0. The recalling phase of the autoassociative Alpha-Beta memory of type max V , when having vector F as input, takes the following form for the (n+k) th recalled component: [figure omitted; refer to PDF] Due to the way vector Xk is built, besides Xn+kk =1 , it is important to notice that Xn+kμ ≠1, for all μ≠k , and from here we can establish that the following [figure omitted; refer to PDF] is different from zero regardless of the value of Xjk . According to Fj =1 for all j∈{1,...,n+p} , we can conclude the impossibility of [figure omitted; refer to PDF] being zero. That is, (VΔβ F)n+k =1=Xn+kk .
Theorem 3.11.
Let {(Xk ,Xk )|"k=1,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type max represented by V , with Xk =τe (xk ,hk ) for k=1,...,p , and let F=τe (xk ,u)∈An+p be a pattern altered with additive noise with respect to some specific pattern Xk , with u∈Ap being the vector defined as u=∑i=1phi . Let us assume that during the recalling phase, F is presented to memory V as input, and the pattern R=VΔβ F∈An+p is obtained. If when taking vector R as argument, the contraction vectorial transform r=τc (R,n)∈Ap is done, the resulting vector r has two mutually exclusive possibilities: ∃k∈{1,...,p} such that r=hk , or r is not a one-hot vector.
Proof.
From the definition of contraction vectorial transform, we have that ri =Ri+n =(VΔβ F)i+n for 1≤i≤p , and in particular, by making i=k we have rk =Rk+n =(VΔβ F)k+n . However, by Lemma 3.10 (VΔβ F)n+k =Xn+kk , and since Xk =τe (xk ,hk ) , the value Xn+kk is equal to the value of component hkk =1 . That is, rk =1 . When considering that rk =1 , vector r has two mutually exclusive possibilities: it can be that rj =0 for all j≠k in which case r=hk , or happens that ∃j∈{1,...,p}, j≠k for which rj =1 , in which case it is not possible that r is a one-hot vector, given Definition 3.3.
Theorem 3.12.
Let {(xμ ,xμ )|"μ=1,2,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type min represented by Λ , and let x...∈An be a pattern altered with subtractive noise with respect to some fundamental pattern xω with ω∈{1,2,...,p} . Let us assume that during the recalling phase, xω is presented to memory Λ as input, and consider an index k∈{1,...,n} . The k th recalled component (Λ∇β x...)k is precisely xkω if and only if it holds that ∃r∈{1,...,n} , dependant on ω and k , such that λkr ≥α(xkω ,x...r ) .
Proof.
[implies] ) By hypothesis, it is assumed that (Λ∇β x...)k =xkω . By contradiction, now let suppose it is false that ∃r∈{1,...,n} such that λkr ≥α(xkω ,x...r ) . That is to say that for all r∈{1,...,n} , λkr <α(xkω ,x...r ) , which is in turn equivalent to for all r∈{1,...,n} , β(λkr ,x...r )<β[α(xkω ,x...r ),x...r ]=xkω . When taking the maximums at both sides of the inequality, with respect to index r , we have [figure omitted; refer to PDF] and this means that (Λ∇β x...)k =...r=1n β(λkr ,x...r )<xkω , an affirmation which contradicts the hypothesis.
[left double arrow] ) When conditions for Theorem 3.2 [19] are met for every i∈{1,...,n} , we have Λ∇β x...=xω . That is, it holds that (Λ∇β x...)i =xiω for all i∈{1,...,n} . When indexes i and j0 are fixed such that i=k and j0 =r , depending on ω and k , we obtain the desired result (Λ∇β x...)k =xkω .
Lemma 3.13.
Let {(X...k ,X...k )|"k=1,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type min represented by Λ , with X¯k =τe (xk , h¯k ) for k=1,...,p , and let G=τe (xk ,w)∈An+p be a pattern altered with subtractive noise with respect to some specific pattern Xk , being w∈Ap a vector whose components have values wi =ui -1 , and u∈Ap the vector defined as u=∑i=1phi . If during the recalling phase, G is presented to memory Λ , then component X¯n+kk is recalled in a perfect manner. That is, (Λ∇β G)n+k =X...n+kk =0 .
Proof.
This proof will be done for two mutually exclusive cases.
Case 1.
Pattern G has one component with value 1. This means that ∃j∈{1,...,n+p} such that Gj =1 . Also, due to the way vector X¯k is built, it is clear that X¯n+kk =0 . Because of this, α(X¯n+kk ,Gj )=α(0,1)=0 and, since the minimum allowed value for a component of memory Λ is 0, we have λ(n+k)j ≥α(X¯n+kk ,Gj ) . According to Theorem 3.12, X¯n+kk is perfectly recalled.
Case 2.
Pattern G has no component with value 1; that is, Gj =0 for all j∈{1,...,n+p} . This means that it is not possible to guarantee the existence of a value j∈{1,...,n+p} such that λ(n+k) j ≥α(X¯n+kk ,Gj ) , and therefore Theorem 3.12 cannot be applied. However, let us show the impossibility of (Λ∇β G)n+k =1 . Recalling the phase of the autoassociative Alpha-Beta memory of type min Λ with vector G as input takes the following form for the (n+k) th recalled component: [figure omitted; refer to PDF] Due to the way vector X¯k is built, besides that X¯n+kk =0 , it is important to notice that X¯n+kμ ≠0, for all μ≠k , and from here we can state that [figure omitted; refer to PDF] is different from 2 regardless of the value of X¯jk . Taking into account that Gj =0 for all j∈{1,...,n+p} , we can conclude that it is impossible for [figure omitted; refer to PDF] to be equal to 1. That is, (Λ∇β G)n+k =0=X...n+kk .
Theorem 3.14.
Let {(X...k ,X...k )|"k=1,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type min represented by Λ , with X¯k =τe (xk ,h¯k ) for k=1,...,p , and let G=τe (xk ,w)∈An+p be a pattern altered with subtractive noise with respect to some specific pattern Xk , with w∈Ap being a vector whose components have values wi =ui -1 , and u∈Ap the vector defined as u=∑i=1phi . Let us assume that during the recalling phase, G is presented to memory Λ as input, and the pattern S=Λ∇β G∈An+p is obtained as output. If when taking vector S as argument, the contraction vectorial transform s=τc (S,n)∈Ap is done, the resulting vector s has two mutually exclusive possibilities: ∃k∈{1,...,p} such that s=h¯k , or s is not a one-hot vector.
Proof.
From the definition of contraction vectorial transform, we have that si =Si+n =(Λ∇β G)i+n for 1≤i≤p , and in particular, by making i=k we have sk =Sk+n =(Λ∇β G)k+n . However, by Lemma 3.13 (Λ∇β G)n+k =X...n+kk , and since X¯k =τe (xk ,h¯k ) , the value X¯n+kk is equal to the value of component h¯kk =0 . That is, sk =0 . When considering that sk =0 , vector s has two mutually exclusive possibilities: it can be that sj =1 for all j≠k in which case s=h¯k ; or it holds that ∃j∈{1,...,p} , j≠k for which sj =0 , in which case it is not possible for s to be a zero-hot vector, given Definition 3.5.
Lemma 3.15.
Let {(X...k ,X...k )|"k=1,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type max represented by V , with Xk =τe (xk ,hk )∈An+p for all k∈{1,...,p} . If t is an index such that n+1≤t≤n+p , then νij ≠0 for all j∈{1,...,n+p} .
Proof.
In order to establish that νij ≠0 for all j∈{1,...,n+p} , given the definition of α , it is enough to find, for each for all t∈{n+1,...,n+p} , an index μ for which Xtμ =1 in the expression that produces the tj th component of memory V , which is νtj =...μ=1p α(Xtμ ,Xjμ ) . Due to the way each vector Xμ =τe (xμ , hμ ) for μ=1,...,p is built, and given the domain of index t∈{n+1,...,n+p} , for each t exists s∈{1,...,p} such that t=n+s . This is why two useful values to determine the result are μ=s and t=n+s , because Xn+ss =1 . Then, νtj =⋁μ=1p α(Xtμ ,Xjμ )=α(Xn+ss ,Xjs )=α(1,Xjs ) , a value which is different from 0. That is, νij ≠0 for all j∈{1,...,n+p} .
Lemma 3.16.
Let {(X...k ,X...k )|"k=1,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type max represented by V , with Xk =τe (xk ,hk ) for k=1,...,p , and let F=τe (xk ,u)∈An+p be an altered version, by additive noise, of a specific pattern Xk , with u∈Ap being the vector defined as u=∑i=1phi . Let us assume that during the recalling phase, F is presented to memory Λ as input. Given a fixed index t∈{n+1,...,n+p} such that t≠n+k , it holds that (VΔβ F)t =1 if and only if the following logic proposition is true: for all j∈{1,...,n+p}, (Fj =0[arrow right]νtj =2) .
Proof.
Due to the way vectors Xk =τe (xk ,hk ) and F=τe (xk ,u) are built, we have that Ft =1 is the component with additive noise with respect to component Xtk =0 .
[implies] ) There are two possible cases.
Case 1.
Pattern F does not contain components with value 0. That is, Fj =1, j∈{1,...,n+p} . This means that the antecedent of proposition Fj =0[arrow right]νtj =2 is false, and therefore, regardless of the truth value of consequence νtj =2 , the expression for all j∈{1,...,n+p} (Fj =0[arrow right]νtj =2) is true.
Case 2.
Pattern F contains at least one component with value 0. That is, ∃r∈{1,...,p} such that Fr =0 . By hypothesis, (VΔβ F)t =1 , which means that the condition for a perfect recall of Xtk =0 is not met. In other words, according to Theorem 3.9 expression ¬ [∃j∈{1,...,n+p} such that νtj ≤α(Xtk ,Fj ) ] is true, which is equivalent to [figure omitted; refer to PDF] In particular, for j=r , and taking into account that Xtk =0 , this inequality ends up like this: νtr >α(Xtk ,Fr )=α(0,0)=1 . That is, νtr =2 , and therefore the expression for all j∈{1,...,n+p} (Fj =0[arrow right]νtj =2 ) is true.
[left double arrow] ) Assuming the following expression is true for all j∈{1,...,n+p} (Fj =0[arrow right]νtj =2 ), there are two possible cases.
Case 1.
Pattern F does not contain components with value 0. That is, Fj =1 for all j∈{1,...,n+p} . When considering that (VΔβ F)t =...j=1n+p β(νtj ,Fj ) , according to the definition of β , it is enough to show that for all j∈{1,...,n+p}, νtj ≠0 , which is guaranteed by Lemma 3.15. Then, it has been proven that (VΔβ F)t =...j=1n+p β(νtj ,Fj )=...j=1n+p β(νtj ,1)=1 .
Case 2.
Pattern F contains at least one component with value 0. That is, ∃r∈{1,...,p} such that Fr =0 . By hypothesis we have that for all j∈{1,...,n+p} , (Fj =0[arrow right]νtj =2) and, in particular, for j=r and νtr =2 , which means that (VΔβ F)t =...j=1n+p β(νtj ,Fj )=β(νtr ,Fr )=β(2,1)=1 .
Corollary 3.17.
Let {(X...k ,X...k )|"k=1,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type max represented by V , with Xk =τe (xk , hk ) for k=1,...,p , and let F=τe (xk ,u)∈An+p be an altered version, by additive noise, of a specific pattern Xk , with u∈Ap being the vector defined as u=∑i=1phi . Let us assume that during the recalling phase, F is presented to memory Λ as input. Given a fixed index t∈{n+1,...,n+p} such that t≠n+k , it holds that (VΔβ F)t =0 if and only if the following logic proposition is true: for all j∈{1,...,n+p} , (Fj =0 AND νtj ≠2).
Proof.
In general, given two logical propositions P and Q , the proposition (P if and only if Q ) is equivalent to proposition (¬ P if and only if ¬ Q ). If P is identified with equality (VΔβ F)t =1 and Q with expression for all j∈{1,...,n+p} (Fj =0[arrow right]νtj =2 ), by Lemma 3.16 the following proposition is true: {¬ [(VΔβ F)t =1] if and only if ¬ [for all j∈{1,...,n+p} (Fj =0[arrow right]νtj=2 )]} . This expression transforms into the following equivalent propositions: [figure omitted; refer to PDF]
Lemma 3.18.
Let {(X...k ,X...k )|"k=1,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type min represented by Λ , with X¯k =τe (xk ,h¯k )∈An+p for all k∈{1,...,p} . If t is an index such that n+1≤t≤n+p , then λtj ≠2 for all j∈{1,...,n+p} .
Proof.
In order to establish that λtj ≠2 for all j∈{1,...,n+p} , given the definition of α , it is enough to find, for each t∈{n+1,...,n+p} , an index μ for which X¯tμ =0 in the expression leading to obtaining the tj th component of memory Λ , which is λtj =...μ=1p α(X¯tμ ,X¯jμ ) . In fact, due to the way each vector X¯k =τe (xk ,h¯k ) for μ=1,...,p is built, and given the domain of index t∈{n+1,...,n+p} , for each t exists s∈{1,...,p} such that t=n+s ; therefore two values useful to determine the result are μ=s and t=n+s , because X¯n+ss =0 , then λtj =...μ=1p α(X¯tμ ,X¯jμ )=α(X¯n+ss ,X¯js )=α(0,Xjμ ) , a value different from 2. That is, λtj ≠2 for all j∈{1,...,n+p} .
Lemma 3.19.
Let {(X...k ,X...k )|"k=1,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type min represented by Λ , with X¯k =τe (xk ,h¯k ) for k=1,...,p , and let G=τe (xk ,w)∈An+p be an altered version, by subtractive noise, of a specific pattern Xk , with w∈Ap being a vector whose components have values wi =ui -1 , and u∈Ap the vector defined as u=∑i=1phi . Let us assume that during the recalling phase, G is presented to memory Λ as input. Given a fixed index t∈{n+1,...,n+p} such that t≠n+k , it holds that (Λ∇β G)t =0 , if and only if the following logical proposition is true for all j∈{1,...,n+p} (Gj =1[arrow right]λtj =0) .
Proof.
Due to the way vectors X¯k =τe (xk ,h¯k ) and G=τe (xk ,w) are built, we have that Gt =1 is the component with subtractive noise with respect to component X¯tk =1 .
[implies] ) There are two possible cases.
Case 1.
Pattern G does not contain components with value 1. That is, Gj =0 for all j∈{1,...,n+p} . This means that the antecedent of logical proposition Gj =1[arrow right]λtj =0 is false and therefore, regardless of the truth value of consequent λtj =0 , the expression for all j∈{1,...,n+p} (Gj =1[arrow right]λtj =0 ) is true.
Case 2.
Pattern G contains at least one component with value 1. That is, ∃r∈{1,...,n+p} such that Gr =1 . By hypothesis, (Λ∇β G)t =0 , which means that the perfect recall condition of X¯tk =1 is not met. In other words, according to Theorem 3.12, expression ¬ [∃j∈{1,...,n+p} such that λtj ≥α(X¯tk ,Gj ) ] is true, which in turn is equivalent to [figure omitted; refer to PDF] In particular, for j=r and considering that X¯tk =1 , this inequality yields λtr <α(X¯tk ,Gr )=α(1,1)=1 . That is, λtr = 0, and therefore the expression for all j∈{1,...,n+p} (Gj =1[arrow right]λtj =0 ) is true.
[left double arrow] ) Assuming the following expression to be true, for all j∈{1,...,n+p} (Gj =1[arrow right]λtj =0 ), there are two possible cases.
Case 1.
Pattern G does not contain components with value 1. That is, Gj =0 for all j∈{1,...,n+p} . When considering that (Λ∇β G)t =...j=1n+p β(λtj ,Gj ) , according to the β definition, it is enough to show that for all j∈{1,...,n+p} , λtj ≠2 , which is guaranteed by Lemma 3.18. Then, it is proven that (Λ∇β G)t =...j=1n+p β(λtj ,Gj )=...j=1n+p β(λtj ,0)=0 .
Case 2.
Pattern G contains at least one component with value 1. That is, ∃r∈{1,...,n+p} such that Gr =1 . By hypothesis we have that for all j∈{1,...,n+p} (Gj =1[arrow right]λtj =0 ) and, in particular, for j=r and λtr =0 , which means that (Λ∇β G)t =...j=1n+p β(λtj ,Gj )=β(λtr ,Gr )=β(0,0)=0 .
Corollary 3.20.
Let {(X...k ,X...k )|"k=1,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type min represented by Λ , with X¯k =τe (xk ,h¯k ) for k=1,...,p , and let G=τe (xk ,w)∈An+p be an altered version, by substractive noise, of a specific pattern Xk , with w∈Ap being a vector whose components have values wi =ui -1 , and u the vector defined as u=∑i=1phi . Let us assume that during the recalling phase, G is presented to memory Λ as input. Given a fixed index t∈{n+1,...,n+p} such that t≠n+k , it holds that (Λ∇β G)t =1 if and only if the following logic proposition is true: ∃j∈{1,...,n+p} (Gj =1 AND λtj ≠0) .
Proof.
In general, given two logical propositions P and Q , the proposition (P if and only if Q ) is equivalent to proposition (P¬ if and only if ¬ Q ). If P is identified with equality (Λ∇β G)t =0 and Q with expression for all j∈{1,...,n+p} (Gj =1[arrow right]λtj =0) , by Lemma 3.19, the following proposition is true: {¬[(Λ∇β G)t =0] if and only if ¬[for all j∈{1,...,n+p} (Gj =1[arrow right]λtj =0)]} . This expression transforms into the following equivalent propositions: [figure omitted; refer to PDF]
Lemma 3.21.
Let {(X...k ,X...k )|"k=1,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type max represented by V , with Xk =τe (xk ,hk ) for k=1,...,p , and let {(X¯k ,X¯k )|"k=1,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type min represented by Λ , with X¯k =τe (xk ,h¯k ), for all k∈{1,...,p} . Then, for each i∈{n+1,...,n+p} such that i=n+r , with ri ∈{1,...,p} , it holds that νij =α(1,Xjri ) and λij =α(0,X¯jri ) for all j∈{1,...,n+p} .
Proof.
Due to the way vectors Xk =τe (xk ,hk ) and X¯k =τe (xk ,h¯k ) are built, we have that Xiri =1 and X¯iri =0 , besides Xiμ =0 and X¯iμ =1 for all μ≠ri such that μ∈{1,...,p} . Because of this, and using the definition of α , α(Xiri ,Xjri )=α(1,Xjri ) and α(Xiμ ,Xjμ )=α(0,Xjμ ) , which implies that, regardless of the values of Xjri and Xjμ , it holds that α(Xiri ,Xjri )≥α(Xiμ ,Xjμ ) , from whence [figure omitted; refer to PDF] We also have α(X¯iri ,X¯jri )=α(0,X¯jri ) and α(X¯iμ ,X¯jμ )=α(1,X¯jμ ) , which implies that, regardless of the values of X¯jri and X¯jμ , it holds that α(X¯iri ,X¯jri )≤α(X¯iμ ,X¯jμ ) , from whence [figure omitted; refer to PDF] μ∈{1,...,p} , for all j∈{1,...,n+p} .
Corollary 3.22.
Let {(X...k ,X...k )|"k=1,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type max represented by V , with Xk =τe (xk ,hk ) for all k∈{1,...,p} , and let {(X¯k ,X¯k )|"k=1,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type min represented by Λ , with X¯k =τe (xk ,h¯k ), for all k∈{1,...,p} . Then, νij =λij +1 , for all i∈{n+1,..., n+p} , i=n+ri , with ri ∈{1,...,p} and for all j∈{1,...,n} .
Proof.
Let i∈{n+1,...,n+p} and j∈{1,...,n} be two indexes arbitrarily selected. By Lemma 3.21, the expressions used to calculate the ij th components of memories V and Λ take the following values: [figure omitted; refer to PDF] Considering that for all j∈{1,...,n} , Xjri =X¯jri , there are two possible cases.
Case 1 (Xjri =0=X¯jri ).
We have the following values: νij =α(1,0)=2 and λij =α(0,0)=1 , therefore νij =λij +1 .
Case 2 (Xjri =1=X¯jri ).
We have the following values: νij =α(1,1)=1 and λij =α(0,1)=0 , therefore νij =λij +1 .
Since both indexes i and j were arbitrarily chosen inside their respective domains, the result νij =λij +1 is valid for all i∈{n+1,...,n+p} and for all j∈{1,...,n} .
Lemma 3.23.
Let {(X...k ,X...k )|"k=1,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type max represented by V , with Xk =τe (xk ,hk ) for all k∈{1,...,p} , and let {(X¯k ,X¯k )|"k=1,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type min represented by Λ , with X¯k =τe (xk ,h¯k ), for all k∈{1,...,p} . Also, if we define vector u∈Ap as u=∑i=1phi , and take a fixed index for all r∈{1,...,p} , let us consider two noisy versions of pattern Xr ∈An+p : vector F=τe (xr ,u)∈An+p which is an additive noise altered version of pattern Xr , and vector G=τe (xr ,w)∈An+p , which is a substractive noise altered version of pattern X¯r , with w∈Ap being a vector whose components take the values wi =ui -1 for all i∈{1,...,p} . If during the recalling phase, G is presented as input to memory Λ and F is presented as input to memory V , and if also it holds that (Λ∇β G)t =0 for an index t∈{n+1,...,n+p} , being fixed such that t≠n+r , then (VΔβ F)t =0 .
Proof.
Due to the way vectors Xr , F and G are built, we have that Ft =1 is the component in the vector with additive noise corresponding to component Xtr , and Gt =0 is the component in the vector with subtractive noise corresponding to component X¯tr . Also, since t≠n+r , we can see that Xtr ≠1, that is, Xtr =0 and X¯tr =1 . There are two possible cases.
Case 1.
Pattern F does not contain any component with value 0. That is, Fj =1 for all j∈{1,...,n+p} . By Lemma 3.15 νtj ≠0 for all j∈{1,...,n+p} , then β(νtj ,Fj ) for all j∈{1,...,n+p} , which means that (VΔβ F)t =...j=1n+p β(νtj ,Fj )=1 . In other words, expression (VΔβ F)t =0 is false. The only possibility for the theorem to hold is for expression (Λ∇β G)t =0 to be false too. That is, we need to show that (Λ∇β G)t =1 . According to Corollary 3.20, the latter is true if for every t∈{n+1,...,n+p} with t≠n+r , exists j∈{1,...,n+ p} such hat (Gj =1 AND λtj ≠0 ). Now, t≠n+r indicates that ∃s∈{1,...,p} , s≠r such that t=n +s , and by Lemma 3.21 α(X¯ts ,X¯js )≤α(X¯tμ ,X¯jμ ) for all μ∈{1,...,p} , for all j∈{1,...,n+p} , from where we have λtj =...j=1p α(X¯tμ ,X¯jμ )=α(X¯ts ,X¯js ) , and by noting the equality X¯ts =X¯n+ss =0 , it holds that [figure omitted; refer to PDF] On the other side, for all i∈{1,...,n} the following equalities hold: X¯ir =xir =1 and X¯is =xis and also, taking into account that xr ≠xs , it is clear that ∃h∈{1,...,p} such that xhs ≠xhr , meaning xhs =0=Xhs and therefore, [figure omitted; refer to PDF] Finally, since for all i∈{1,...,n} it holds that Gi =X¯ir =xir =1 , in particular Gh =1 , then we have proven that for every t∈{n+1,...,n+p} with t≠n+r , exists j∈{1,...,n+p} such that (Gj =1 and λtj ≠0 ), and by Corollary 3.20 it holds that (Λ∇β G)t =1 , thus making expression (Λ∇β G)t =1 be false.
Case 2.
Pattern F contains, besides the components with value of 1, at least one component with value 0. That is, ∃h∈{1,...,n+p} such that Fh =0 . Due to the way vectors G and F are built for all i∈{1,...,n} , Gi =Fi and, also, necessarily 1≤h≤n and thus Fh =Gh =0 . By hypothesis, ∃t∈{n+1,...,n+p} being fixed such that t≠n+r and (Λ∇β G)t =0 , and by Lemma 3.19 for all j∈{1,...,n+p} (Gj =1[arrow right]λtj =0) . Given the way vector G is built we have that for all j∈{n+1,...,n+p} , Gj =0 , thus making the former expression like this: for all j∈{1,...,n} (Gj =1[arrow right]λtj =0) . Let J be a set, proper subset of {1,...,n} , defined like this: J={j∈{1,...,n}|"Gj =1} . The fact that J is a proper subset of {1,...,n} is guaranteed by the existence of Gh =0 . Now, t≠n+r indicates that ∃s∈{1,...,p} , s≠r such that t=n+s , and by Lemma 3.21 νtj =α(1,Xjs ) and λtj =α(0,X¯js ) for all j∈{1,...,n+p} , from where we have that for all j∈J, X¯js =1 , because if this was not the case, λtj ≠0 . This means that for each j∈J , X¯js =1=Gj which in turn means that patterns Xr and Xs coincide with value 1 in all components with index j∈J . Let us now consider the complement of set J , which is defined as Jc ={j∈{1,...,n}|"Gj =0} . The existence of at least one value j0 ∈Jc for which Gj0 =0 and X¯j0 s =1 is guaranteed by the known fact that xr ≠xs . Let us see, if X¯js =0 for all j∈Jc then for all j∈{1,...,n} it holds that X¯js =Gj , which would mean that xr =xs . Since ∃j0 ∈Jc for which Gj0 =0 and X¯j0 s =1 , this means that ∃j0 ∈Jc for which Fj0 =0 and Xj0 s =1 . Now, β(νtj0 ,Fj0 )=β(α(1,Xj0 s ),0)=β(α(1,1),0)=β(1,0)=0 , and finally [figure omitted; refer to PDF]
Lemma 3.24.
Let {(X...k ,X...k )|"k=1,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type max represented by V , with Xk =τe (xk ,hk ) for all k∈{1,...,p} , and let {(X¯k ,X¯k )|"k=1,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type min represented by Λ , with X¯k =τe (xk ,h¯k ), for all k∈{1,...,p} . Also, if we define vector u∈Ap as u=∑i=1phi , and take a fixed index for all r∈{1,...,p} , let us consider two noisy versions of pattern Xr ∈An+p : vector F=τe (xr ,u)∈An+p which is an additive noise altered version of pattern Xr , and vector G=τe (xr ,w)∈An+p , which is a subtractive noise altered version of pattern X¯r , with w∈Ap being a vector whose components take the values wi =ui -1 for all i∈{1,...,p} . If during the recalling phase, G is presented as input to memory Λ and F is presented as input to memory V , and if also it holds that (VΔβ F)t =1 for an index t∈{n+1,...,n+p} , being fixed such that t≠n+r , then (Λ∇β G)t =1 .
Proof.
Due to the way vectors Xr , F and G are built, we have that Ft =1 is the component in the vector with additive noise corresponding to component Xtr , and Gt =0 is the component in the vector with subtractive noise corresponding to component X¯tr . Also, since t≠n+r , we can see that Xtr ≠1, that is, Xtr =0 and X¯tr =1 . There are two possible cases.
Case 1.
Pattern G does not contain any component with value 1. That is, Gj =0 for all j∈{1,...,n+p} . By Lemma 3.18 λtj ≠2 for all j∈{1,...,n+p} ; thus β(λtj ,Gj )=0 for all j∈{1,...,n+p} , which means that (Λ∇β G)t =...j=1n+p β(λtj ,Gj )=0 . In other words, expression (Λ∇β G)t =1 is false. The only possibility for the theorem to hold is for expression (VΔβ F)t =1 to be false too. That is, we need to show that (VΔβ F)t =0 . According to Corollary 3.17, the latter is true if for every t∈{n+1,...,n+p} with t≠n+r , exists j∈{1,...,n+p} such that (Fj =0 AND νtj ≠2 ). Now, t≠n+r indicates that ∃s∈{1,...,p} , s≠r such that t=n+s , and by Lemma 3.19 α(Xts ,Xjs )≥α(Xtμ ,Xjμ ) for all μ∈{1,...,p} , for all j∈{1,...,n+p} , from where we have νtj =...μ=1p α(Xtμ ,Xjμ )=α(Xts ,Xjs ) , and by noting the equality Xts =Xn+ss =1 , it holds that [figure omitted; refer to PDF] On the other side, for all i∈{1,...,n} the following equalities hold: Xir =xir =0 and Xis =xis and also, taking into account that xr ≠xs , it is clear that ∃h∈{1,...,p} such that xhs ≠xhr , meaning xhs =1=Xhs and therefore, [figure omitted; refer to PDF] Finally, since for all i∈{1,...,n} it holds that Fi =Xir =xir =0 , in particular Fh =0 , then we have proven that for every t∈{n+1,...,n+p} with t≠n+r , exists j∈{1,...,n+p} such that (Fj =0 AND νtj ≠2 ), and by Corollary 3.17 it holds that (VΔβ F)t =0 , thus making expression (VΔβ F)t =1 false.
Case 2.
Pattern G contains, besides the components with value of 0, at least one component with value 1. That is, ∃h∈{1,...,n+p} such that Gh =1 . Due to the way vectors G and F are built for all i∈{1,...,n} , Gi =Fi and, also, necessarily 1≤h≤n and thus Fh =Gh =0 . By hypothesis ∃t∈{n+1,...,n+p} , being fixed such that t≠n+r and (VΔβ F)t =1 , and by Lemma 3.16 for all j∈{1,...,n+p} (Fj =0[arrow right]νtj =2 ). Given the way vector F is built, we have that for all j∈{n+1,...,n+p} , Gj =1 , thus making the former expression like this: for all j∈{1,...,n+p} (Fj =0[arrow right]νtj =2 ). Let J be a set, a proper subset of {1,...,n} , defined like this: J={j∈{1,...,n}|"Fj =0} . The fact that J is a proper subset of {1,...,n} is guaranteed by the existence of Gh =1 . Now, t≠n+r indicates that ∃s∈{1,...,p} , s≠r such that t=n+s , and by Lemma 3.21 νtj =α(1,Xjs ) and λtj =α(0,X¯js ) for all j∈{1,...,n+p} , from where we have that for all j∈J , Xjs =0 , because if this was not the case, νtj ≠0 . This means that for each j∈J , Xjs =0=Fj which in turn means that patterns Xr and Xs coincide with value 0 in all components with index j∈J . Let us now consider the complement of set J , which is defined as Jc ={j∈{1,...,n}|"Fj =1} . The existence of at least one value j0 ∈Jc for which Fj0 =1 and Xj0 s =0 is guaranteed by the known fact that xr ≠xs . Let us see, if Xjs =1 for all j∈Jc then for all j∈{1,...,n} it holds that Xjs =Fj , which would mean that xr =xs . Since ∃j0 ∈Jc for which Fj0 =1 and Xj0 s =0 , this means that ∃j0 ∈Jc for which Gj0 =1 and X¯j0 s =0 . Now, β(λtj0 ,Gj0 )=β(α(0,X¯j0 s ),1)=β(α(0,0),1)=β(1,1)=1 , and finally [figure omitted; refer to PDF]
Theorem 3.25 (Main Theorem).
Let {(X...k ,X...k )|"k=1,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type max represented by V , with Xk =τe (xk ,hk ) for all k∈{1,...,p} , and let {(X¯k ,X¯k )|"k=1,...,p} be the fundamental set of an autoassociative Alpha-Beta memory of type min represented by Λ , with X¯k =τe (xk ,h¯k ), for all k∈{1,...,p} . Also, if we define vector u∈Ap as u=∑i=1phi , and take a fixed index r∈{1,...,p} , let us consider two noisy versions of pattern Xr ∈An+p : vector F=τe (xr ,u)∈An+p , which is an additive noise altered version of pattern Xr , and vector G=τe (xr ,w)∈An+p , which is a subtractive noise altered version of pattern X¯r , with w∈Ap being a vector whose components take the values wi =ui -1 for all i∈{1,...,p} . Now, let us assume that during the recalling phase, G is presented as input to memory Λ and F is presented as input to memory V , and patterns S=Λ∇β G∈An+p and R=VΔβ F∈An+p are obtained. If when taking vector R as argument the contraction vectorial transform r=τc (R,n)∈Ap is done, and when taking vector S as argument the contraction vectorial transform s=τc (S,n)∈Ap is done, then H=(r AND s...) will be the k th one-hot vector of p bits, where s... is the negated from of s .
Proof.
From the definition of contraction vectorial transform, we have that ri =Ri+n =(VΔβ F)i+n and si =Si+n =(Λ∇β G)i+n for 1≤i≤p , and in particular, by making i=k we have rk =Rk+n =(VΔβ F)k+n and sk =Sk+n =(Λ∇β G)k+n . By Lemmas 3.10 and 3.13 we have (VΔβ F)n+k =Xn+kk =1 and (Λ∇β G)n+k =X...n+kk =0 , and thus: Hk =rk AND s...k =1 AND ¬ 0=1 AND 1=1 .
Now, by Lemma 3.23 we know that if (Λ∇β G)t =0 such that t=i+n is a fixed index with t≠n+k , then (VΔβ F)t =0 ; thus, [figure omitted; refer to PDF] On the other side, by Lemma 3.24 it is known that if (VΔβ F)q =1 for a fixed index q=i+n such that q≠n+k , then (Λ∇β G)q =1 . According to the latter, [figure omitted; refer to PDF] Then Hi =1 for i=k and Hi =0 for i≠k . Therefore, and according to Definition 3.3, H will be the k th one-hot vector of p bits.
3.3.2. Theoretical Foundation of Stages 2 and 4
In this section is presented the theoretical foundation which serves as the basis for the design and operation of Stages 2 and 4, whose main element is an original variation of the Linear Associator .
Let {(xμ ,yμ )|"μ=1,2,...,p} with A={0,1} , xμ ∈An and yμ ∈Am be the fundamental set of the Linear Associator . The Learning Phase consists of two stages.
(i) For each of the p associations (xμ ,yμ ) find matrix yμ ·(xμ )t of dimensions m×n .
(ii) The p matrices are added together to obtain the memory
[figure omitted; refer to PDF] in such way that the ij th component of memory M is expressed as [figure omitted; refer to PDF] The Recalling Phase consists of presenting an input pattern xω to the memory, where ω∈{1,2,...,p} and doing operation [figure omitted; refer to PDF] The following form of expression allows us to investigate the conditions that must be met in order for the proposed recalling method to give perfect outputs as results: [figure omitted; refer to PDF] For the latter expression to give pattern yω as a result, it is necessary that two equalities hold:
(i) [(xω )t ·xω ]=1 ;
(ii) [(xμ )t ·xω ]=0 as long as μ≠ω .
This means that, in order to have perfect recall, vectors xμ must be orthonormal to each other. If that happens, then, for μ=1,2,...,p , we have [figure omitted; refer to PDF] Therefore, [figure omitted; refer to PDF] Taking advantage of the characteristic shown by the Linear Asssociator when the input patterns are orthonormal, and given that, by Definition 3.3, one-hot vectors vk with k=1,...,p are orthonormal, we can obviate the learning phase by avoiding the vectorial operations done by the Linear Associator , and simply put the vectors in order, to form the Linear Associator .
Stages 2 and 4 correspond to two modified Linear Associators , built with vectors y and x , respectively, of the fundamental set.
3.3.3. Algorithm
In this section we describe, step by step, the processes required by the Alpha-Beta BAM, in the Learning Phase as well as in the Recalling Phase (by convention only) in the direction x[arrow right]y , the algorithm for Stages 1 and 2.
The following algorithm describes the steps needed by the Alpha-Beta bidirectional associative memory for the learning and recalling phases to happen, in the direction x[arrow right]y .
Learning Phase
(1) For each index k∈{1,...,p} , do expansion: Xk =τe (xk ,hk ) .
(2) Create an Alpha-Beta autoassociative memory of type max V with the fundamental set [figure omitted; refer to PDF]
(3) For each index k∈{1,...,p} , do expansion: X¯k =τe (xk ,h¯k ) .
(4) Create an Alpha-Beta autoassociative memory of type min Λ with the fundamental set [figure omitted; refer to PDF]
(5) Create a matrix consisting of a modified Linear Associator with patterns yk
[figure omitted; refer to PDF]
Recalling Phase
(1) Present, as input to Stage 1, a vector of the fundamental set xμ ∈An for some index μ∈{1,...,p} .
(2) Build vector u∈Ap in the following manner: [figure omitted; refer to PDF]
(3) Do expansion: F=τe (xμ ,u)∈An+p .
(4) Operate the Alpha-Beta autoassociative memory max V with F , in order to obtain a vector R of dimension n+p [figure omitted; refer to PDF]
(5) Do contraction r=τc (R,n)∈Ap .
(6) If (∃k∈{1,...,p} such that hk =r ), it is assured that k=μ (based on Theorem 3.11), and the result is hμ . Thus, operation LAy · r is done, resulting in the corresponding yμ . STOP. Else {
(7) Build vector w∈Ap in such way that wi =ui -1 , for all i∈{1,...,p} .
(8) Do expansion: G=τe (xμ ,w)∈An+p .
(9) Operate the Alpha-Beta autoassociative memory min Λ with G , in order to obtain a vector S of dimension n+p [figure omitted; refer to PDF]
(10) Do contraction s=τc (Sμ ,n)∈Ap .
(11) If (∃k∈{1,...,p} such that h¯k =s ), it is assured that k=μ (based on Theorem 3.14), and the result is hμ . Thus, operation LAy·s... is done, resulting in the corresponding yμ . STOP. Else { .
Do operation t=r⋀s¯ , where Λ is the symbol of the logical AND. The result of this operation is hμ (based on Theorem 3.25). Operation LAy ·t is done, in order to obtain the corresponding yμ . STOP.}} .The process in the contrary direction, which is presenting pattern yk (k=1,...,p) as input to the Alpha-Beta BAM and obtaining its corresponding xk , is very similar to the one described above. The task of Stage 3 is to obtain a one-hot vector hk given a yk . Stage 4 is a modified Linear Associator built in similar fashion to the one in Stage 2.All this theoretical foundations assure every training pattern to be recalled without imposing any condition in the nature of patterns, such as linear dependency, Hamming distance, orthogonality, nor the number of patterns to be trained. The algorithm shows that the method is not iterative but rather a one-shot algorithm, which is an advantage because our model does not have stability problems.
4. Experiments and Results
We first use Lindig's algorithm [5] to generate a concept lattice from a set of objects and attributes. In the learning phase, each object or subset of objects is associated with their corresponding attribute or subset of attributes, that is, concepts are stored in a BAM. The bidirectionality of this associative model enables the system to retrieve a concept from objects or attributes information. We present an illustrative example to explain our proposal in a simple way.
Suppose the context of the planets showed in Table 3. From the table, it can be observed that there are 9 objects corresponding to the number of planets, and there are 7 attributes. Based on this table a concept lattice is derived from Lindig's algorithm, which is shown in Figure 4.
Table 3: Context of planets.
Planet | Size | Distance from Sun | Moon | ||||
S mall (ss ) | Medium (sm ) | Large (sl ) | Near (dn ) | Far (df ) | Yes (my ) | No (mn ) | |
| |||||||
Mercury (Me ) | -- | -- | -- | -- | -- | -- | -- |
Venus (V ) | -- | -- | -- | -- | -- | -- | -- |
Earth (E ) | -- | -- | -- | -- | -- | -- | -- |
Mars (Ma ) | -- | -- | -- | -- | -- | -- | -- |
Jupiter (J ) | -- | -- | -- | -- | -- | -- | -- |
Saturn (S ) | -- | -- | -- | -- | -- | -- | -- |
Uranus (U ) | -- | -- | -- | -- | -- | -- | -- |
Neptune (N ) | -- | -- | -- | -- | -- | -- | -- |
Pluto (P ) | -- | -- | -- | -- | -- | -- | -- |
Figure 4: Concept lattice for the context of the planets given in Table 3.
[figure omitted; refer to PDF]
In both forward and reverse directions, the number of objects becomes the number of elements of vectors x and the number of attributes is the number of elements of vectors y , as Figure 5 shows.
Figure 5: In the learning phase, concepts are stored as associations of objects and attributes.
[figure omitted; refer to PDF]
A software implementation of the Alpha-Beta BAM to store concept lattices derived from Lindig's algorithm was developed. The software was programmed with Visual C++6.0. A result related to the example showed in Figure 4 can be observed in Figure 6.
Figure 6: Example screen of software developed. Object information is provided and attributes are recalled.
[figure omitted; refer to PDF]
The first step is to generate the concept lattice. Information about objects and attributes is read from a txt file, then Lindig's algorithm is applied and the concept lattice is built. We have the option to choose objects or attributes; these are selected and the corresponding concept is showed.
We tested the system introducing each set of objects from each concept, and associated attributes were recalled. In the same way, sets of attributes from the concept lattice were presented to the Alpha-Beta BAM and associated objects were recalled. In this manner, we had perfect recall in the experiment.
In this case, the context has few elements. However, the context could have any number of objects and attributes and Alpha-Beta BAM will recall every association, that is, it will show perfect recall. This can be concluded because Alpha-Beta BAM has a mathematical foundation assuring perfect recall without imposing any condition.
5. Conclusions
Formal Concept Analysis is a tool to represent the way human beings conceptualize the real world by giving the bases to analyze contexts and to obtain formal concepts. Lindig's algorithm takes these formal concepts and builds a concept lattice to represent human thought. Therefore, this step provides a way to model mental level. On the other hand, Alpha-Beta Bidirectional Associative Memories are a great tool to store concept lattices because the model is a one-shot algorithm and all patterns are recalled perfectly in both directions. The process for storing formal concepts consists in associating every object with its corresponding attribute using Alpha-Beta operators during the learning phase. The recalling phase of Alpha-Beta BAM allows retrieving a formal concept by presenting an object or attribute. The main feature of Alpha-Beta BAM is that it exhibits perfect recall on all fundamental patterns without any condition in number of patterns or the nature of patterns. This makes our algorithm an adequate tool to store concepts. Besides, it provides a way to model brain level.
Our proposed model stores and retrieves concepts from a concept lattice in a suitable way. This model can be used to create knowledge databases, which is our next goal.
Acknowledgment
The authors would like to thank the Instituto Politécnico Nacional (COFAA and SIP) and SNI for their financial support to develop this work.
[1] C. Carpineto, G. Romano Concept Data Analysis: Theory and Applications , pp. xviii+201, John Wiley & Sons, Hoboken, NJ, USA, 2004.
[2] J.-P. Bordat, "Calcul pratique du treillis de Galois d'une correspondance," Mathématiques et Sciences Humaines , no. 96, pp. 31-47, 1986.
[3] M. I. Zabezhailo, V. G. Ivashko, S. O. Kuznetsov, M. A. Mikheenkova, K. P. Khazanovskii, O. M. Anshakov, "Algorithms and programs of the JSM-method of automatic hypothesis generation," Automatic Documentation and Mathematical Linguistics , vol. 21, no. 5, pp. 1-14, 1987.
[4] B. Ganter, "Two basic algorithms in concept analysis,", no. 831, Darmstadt University, Darmstadt, Germany, 1984.
[5] C. Lindig Algorithmen zur Begriffsanalyse und ihre Anwendung bei Softwarebibliotheken , Technische Universität Braunschweig, Braunschweig, Germany, 1999.
[6] M. Chein, "Algorithme de recherche des sou-matrices premières d'une matrice," Bulletin Mathématique de la Société des Sciences Mathématiques de Roumanie , vol. 13, no. 1, pp. 21-25, 1969.
[7] L. Nourine, O. Raynaud, "A fast algorithm for building lattices," Information Processing Letters , vol. 71, no. 5-6, pp. 199-204, 1999.
[8] M. E. Acevedo-Mosqueda, C. Yáñez-Márquez, I. López-Yáñez, "Alpha-beta bidirectional associative memories: theory and applications," Neural Processing Letters , vol. 26, no. 1, pp. 1-40, 2007., [email protected]; [email protected]; [email protected]
[9] Y.-J. Jeng, C.-C. Yeh, T. D. Chiueh, "Exponential bidirectional associative memories," Electronics Letters , vol. 26, no. 11, pp. 717-718, 1990.
[10] W.-J. Wang, D.-L. Lee, "Modified exponential bidirectional associative memories," Electronics Letters , vol. 28, no. 9, pp. 888-890, 1992.
[11] S. Chen, H. Gao, W. Yan, "Improved exponential bidirectional associative memory," Electronics Letters , vol. 33, no. 3, pp. 223-224, 1997., [email protected]
[12] Y.-F. Wang, J. B. Cruz Jr., J. H. Mulligan Jr., "Two coding strategies for bidirectional associative memory," IEEE Transactions on Neural Networks , vol. 1, no. 1, pp. 81-92, 1990.
[13] Y.-F. Wang, J. B. Cruz Jr., J. H. Mulligan Jr., "Guaranteed recall of all training pairs for bidirectional associative memory," IEEE Transactions on Neural Networks , vol. 2, no. 6, pp. 559-567, 1991.
[14] R. Perfetti, "Optimal gradient descent learning for bidirectional associative memories," Electronics Letters , vol. 29, no. 17, pp. 1556-1557, 1993.
[15] G. Zheng, S. N. Givigi, W. Zheng A New Strategy for Designing Bidirectional Associative Memories , vol. 3496, of Lecture Notes in Computer Science, Springer, Berlin, Germany, 2005.
[16] D. Shen, J. B. Cruz Jr., "Encoding strategy for maximum noise tolerance bidirectional associative memory," IEEE Transactions on Neural Networks , vol. 16, no. 2, pp. 293-300, 2005., [email protected]; [email protected]
[17] S. Arik, "Global asymptotic stability analysis of bidirectional associative memory neural networks with time delays," IEEE Transactions on Neural Networks , vol. 16, no. 3, pp. 580-586, 2005.
[18] G. X. Ritter, J.L. Diaz-de-Leon, P. Sussner, "Morphological bidirectional associative memories," Neural Networks , vol. 12, no. 6, pp. 851-867, 1999., [email protected]
[19] Y. Wu, D. A. Pados, "A feedforward bidirectional associative memory," IEEE Transactions on Neural Networks , vol. 11, no. 4, pp. 859-866, 2000., [email protected]
[20] B. Ganter, R. Wille Formal Concept Analysis: Mathematical Foundations , pp. x+284, Springer, Berlin, Germany, 1999.
[21] R. K. Rajapakse, M. Denham, "Information retrieval model using concepts lattices for content representation," in Proceedings of the FCA KDD Workshop of the 15th European Conference on Artificial Intelligence (ECAI '02), Lyon, France, July 2002.
[22] Kohonen, "Correlation matrix memories," IEEE Transactions on Computers , vol. 21, no. 4, pp. 353-359, 1972.
[23] G. X. Ritter, P. Sussner, J.L. Diaz-de-Leon, "Morphological associative memories," IEEE Transactions on Neural Networks , vol. 9, no. 2, pp. 281-293, 1998.
[24] C. Yáñez-Márquez, J. L. Díaz de León-Santiago, "Memorias asociativas basadas en relaciones de orden y operaciones binarias," Computación y Sistemas , vol. 6, no. 4, pp. 300-311, 2003.
[25] C. Yáñez-Márquez Associative Memories Based on Order Relations and Binary Operators (In Spanish) , Ph.D. thesis, Center for Computing Research, México, 2002.
[26] B. Kosko, "Bidirectional associative memories," IEEE Transactions on Systems, Man, and Cybernetics , vol. 18, no. 1, pp. 49-60, 1988.
[27] J. H. Park, "Robust stability of bidirectional associative memory neural networks with time delays," Physics Letters A , vol. 349, no. 6, pp. 494-499, 2006., [email protected]
[28] M. E. Acevedo Alpha-beta bidirectional associative memories (In Spanish) , Ph.D. thesis, Center for Computing Research, México, 2006.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer
Copyright © 2010 María Elena Acevedo et al. María Elena Acevedo et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
Alpha-beta bidirectional associative memories are implemented for storing concept lattices. We use Lindig's algorithm to construct a concept lattice of a particular context; this structure is stored into an associative memory just as a human being does, namely, associating patterns. Bidirectionality and perfect recall of Alpha-Beta associative model make it a great tool to store a concept lattice. In the learning phase, objects and attributes obtained from Lindig's algorithm are associated by Alpha-Beta bidirectional associative memory; in this phase the data is stored. In the recalling phase, the associative model allows to retrieve objects from attributes or vice versa. Our model assures the recalling of every learnt concept.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer