A novel theoretical background of fuzzy associative memories (FAM) is proposed. A framework of formal concept analysis is used for a new working theory of FAM. Two principal activities of FAM are formalized : data retrieval and noise reduction. It is shown that the problem of data retrieval is connected with solvability and eigen sets of a certain system of fuzzy relation equations. The differentiation of FAM models according to their ability to reduce noise is defined. It is shown how the choice of formal context determines a type of noise that can be reduced by the corresponding retrieval mechanism. Finally, we propose a fast algorithm of data retrieval.
One of the first publications devoted to fuzzy associative memories (FAM) has been made by Kosko - [6]. The FAM has been characterized as a single-layer feedforward neural net performing a nonlinear matrix-vector multiplication. This approach was later extended with the purpose to increase the storage capacity (e.g. [4]). Significant progress was achieved by introduction of learning implication rules [3, 5], that afterwards led to implicative fuzzy associative memory (IFAM) with implicative fuzzy learning. A justification of validity of a certain
[17] and propose a working theory of FAM. Let us remark that the language and technique of formal concept analysis is used in other theories, e.g., fuzzy property-oriented concept lattices, as well as in applications such as modeling and processing of incomplete knowledge in information systems [1, 2].
duction. We use the proposed formalism and show that the problem of data retrieval is connected with solvability and eigen sets of a certain system of fuzzy relation equations. We differentiate FAM models according to their ability to reduce noise and show how the choice of formal context determines a type of noise that can be reduced by the corresponding retrieval mechanism.
From the technical point of view, we extend the theory of FAM by using a general algebraic structure instead of a specific one (Lukasiewicz algebra in [14]) and by enlarging the set of autoregressive fuzzy associative memory models (AFAM). We propose a formal characterization of AFAM models and show the way of various modifications. We analyze the retrieval mechanism of AFAM and its ability to remove noise. We show that the larger is the amount of noise, the greater should be the fuzzy relation that models retrieval with noise reduction.
2 2.1
D = {x1, . . . , xp}, of objects (images, patterns, signals, texts, etc.) is represented by normal fuzzy sets such that every xk, k = 1, . . . , p, is a map xk : X → [0, 1], where X = {u1, . . . , un} is a universe. The problem is to find a model of D together with a retrieval mechanism such that every element xk ∈ D can be successfully retrieved even from its noisy version.
According to [14], a model of AFAM for database D can be identified with the 3-tuple (W, θ, ), consisting of a fuzzy relation W : X × X → [0, 1], a bias vector θ ∈ [0, 1]n, and a set-relation composition : [0, 1]n×n ×[0, 1]n ×[0, 1]n → [0, 1]n, such that for all xk ∈ D,
xk ∨ θ, k = 1, . . . , p.
We say that (
than some database element, say xk, then the retrieved output is close to xk as well.
introduce the algebraic background of what will be proposed as a new model of
Let L = hL, ∨, ∧, ∗, →, 0, 1i be a fixed, complete, integral, residuated, commutative l-monoid (a complete residuated lattice). We remind the main characteristics of this structure: hL, ∨, ∧, 0, 1i is a complete bounded lattice, hL, ∗, →, 1i is a residuated, commutative monoid.
Let X be a non-empty set, LX a class of (L-valued) fuzzy sets on X and LX×X a class of (L-valued) fuzzy relations on X. Fuzzy sets and fuzzy relations are identified with their membership functions, i.e. elements from LX and LX×X , respectively. A fuzzy set A is normal if there exists xA ∈ X such that A(xA) = 1. The (ordinary) set Core(A) = {x ∈ X | A(x) = 1} is the core of the normal fuzzy set A. Fuzzy sets A ∈ LX and B ∈ LX are equal (A = B), if for all x ∈ X, A(x) = B(x). A fuzzy set A ∈ LX is less than or equal to a fuzzy set B ∈ LX (A ≤ B), if for all x ∈ X, A(x) ≤ B(x).
The lattice operations ∨ and ∧ induce the union and intersection of fuzzy sets, respectively. The binary operations ∗ and → of L are used for set-relation compositions of the types sup −∗ or inf − → that are usually denoted by ◦ and . where (R ◦ A)(y) =
_ (R(x, y) ∗ A(x)), and (R . A )(y) =
^ (R(x, y) → A(x)).
We say that compositions ◦ and . are skew adjoint, which means that for every A, B ∈ LX , R ∈ LX×X , the following holds:
R ◦ A ≤ B ↔ A ≤ Rop . B, x∈X x∈X where Rop(x, y) = R(y, x).
Let us remind that the ◦ composition was introduced by L. Zadeh [18] in the form max − min. 3
3.1
A binary fuzzy relation on X is a ∗-fuzzy preorder of X, if it is reflexive and ∗-transitive. The fuzzy preorder Q∗ ∈ LX×X , where
Q∗(x, y) = ^(Ai(x) → Ai(y)),
i∈I
(
In this Section, we show that fuzzy preorder Q∗ (given by (
W ◦ Ai = Ai, i ∈ I,
W . A i = Ai, i ∈ I. is generated by an arbitrary family of fuzzy sets (Ai)i∈I of X.
Remark 1. The fuzzy preorder Q∗ is often called Valverde order determined by the family of fuzzy sets (Ai)i∈I of X (see [16] for details).
If Q is a fuzzy preorder on X, then Qop is a fuzzy preorder on X as well.
Proposition 1. Let (Ai)i∈I ⊆ LX , be a family of fuzzy sets of X and a fuzzy
preorder Q∗ be generated by this family in the sense of (
(fuzzy) relation is a solution to (
The following chain of equivalences can be easily obtained from the first claim: (∀y) _ (Q∗(x, y) ∗ Ai(x)) ≤ Ai(y)
⇔ (∀y)(∀x)(Q∗(x, y)∗Ai(x) ≤ Ai(y)) ⇔ !
^ (Q∗(x, y) → Ai(y)) . y∈X x∈X By reflexivity of Q∗,
(∀x)(∀y)(Ai(x) ≤ Q∗(x, y) → Ai(y)) ⇔ (∀x) Ai(x) ≤ ^ (Q∗(x, y) → Ai(y)) ≤ Ai(x). y∈X
(Q∗)op . A i = Ai.
Corollary 1. Let the assumptions of Proposition 1 be fulfilled. Then fuzzy sets Ai, i ∈ I, are eigen fuzzy sets of the relation Q∗ ((Q∗)op) with respect to composition ◦ (. ).
By Proposition 1, fuzzy relation Q∗ ((Q∗)op) is the greatest solution of the
system (
Proposition 2. Let (Ai)i∈I ⊆ LX be a family of fuzzy sets of X and fuzzy
preorder Q∗ be generated by this family in the sense of (
Then Δ(Q∗) is a solution to the system (
The first inequality is due to Δ(Q∗) ≤ Q∗. The second inequality follows from reflexivity of Δ(Q∗).
At second, we show that Δ(Q∗) is a preorder relation on X. The property of reflexivity is inherited from Q∗.To prove transitivity we choose t, u, v ∈ X and consider the case Δ(Q∗)(t, u) = 1 and Δ(Q∗)(u, v) = 1. It is easy to see that Δ(Q∗)(t, u) ∗ Δ(Q∗)(u, v) = Q∗(t, u) ∗ Q∗(u, v) ≤ Q∗(t, v).
We refer to Δ(Q∗) as to a binary “skeleton” of Q∗. 4
and the theory of autoregressive fuzzy associative memories (AFAM), presented in Section 2. We propose a new concept of adjoint AFAM models that share a common fuzzy preorder relation. We characterize types of noise that can be reduced by retrieval in corresponding AFAM models. 4.1
Let us choose and fix complete residuated lattice with the support L = [0, 1] and database D = {x1, . . . , xp} of 2D [0, 1]-valued (gray scaled) images. We assume that the images in D are represented by n-dimensional vectors, so that each vector is a sequence of image rows. We identify every image with a fuzzy set on n¯ = {1, 2, . . . , n}, so that xk ∈ [0, 1]n, k = 1, . . . , p. We additionally assume that all fuzzy sets in D are normal.
Definition 1. We say that a pair (W, ), where W ∈ [0, 1]n×n is a fuzzy relation and : [0, 1]n×n × [0, 1]n → [0, 1]n is a set-relation composition, is an AFAM model of database D, if for all xk ∈ D,
We say that two AFAM models (W, ) and (W, e ) of D are adjoint, if there exists a complete residuated lattice L such that is of the sup −∗ type, e is of the inf − → type and and e are skew-adjoint.
By (
Example 1. Let us choose a complete residuated lattice L on [0, 1] and give
two examples of adjoint AFAM models. Following (
Q∗(i, j) =
p
^ (xk(i) → xk(j)),
(
Definition 2. Let (W, ) be a model of AFAM with respect to database D, x˜ ∈ [0, 1]n, and x˜ 6∈ D. We say that x˜ is a noisy version of some element x ∈ D, that can be removed by the retrieval in (W, ), if x = W x˜.
(
Proof. We give the proof of the case (i). Assume that x = (x1, . . . xn), x˜ = (x˜1, . . . x˜n) and W ◦ x˜ = x. Then for any j = 1, . . . , n,
n xj = _ (W (i, j) ∗ x˜i) ≥ W (j, j) ∗ x˜j ) = x˜j .
i=1 Therefore, x˜ ≤ x. 5
We choose and fix a finite set X and a complete residuated lattice L. The following formal context K = (A, R, I ) where A ⊆ LX is a set of objects, R ⊆ LX×X is a set of attributes, and I is an incidence relation on A × R, is proposed. We say that an object (dataset) A possesses an attribute R, if the latter is an AFAM model of A via the composition . Equivalently and in accordance with Definition 1, I (A, R) = 1 if and only if A ∈ A is an eigen fuzzy set of R ∈ R with respect to the composition .
Let us choose and fix a formal context K with the given above specification. A couple (A, W) is a formal concept of K, if A ⊆ A is a dataset, W ⊆ R is a set of fuzzy relations such that A ∈ A if and only if A is an eigen fuzzy set of any W ∈ W with respect to the composition , and vise versa, W ∈ W if and only if (W, ) is an AFAM model of A.
attribute in W, i.e. can be successfully retrieved from its sample using any AFAM model (W, ) where W ∈ W and composition is clear from the context K.
can be formalized in terms of context analysis. We formulate two assertions and characterize formal concepts where datasets as formal concept objects are connected with retrieval models as formal concept attributes. The proofs of both below given statements can be obtained from Propositions 1,2.
Proposition 4. Let X be a set, L a complete residuated lattice, K = (LX , LX×X , I◦) a formal context and A ⊆ LX a dataset of objects. Then the smallest concept with objects from A includes as attributes all fuzzy relations R ∈ LX×X such that Δ(Q∗) ≤ R ≤ Q∗ where Q∗ and Δ(Q∗) are specified in Propositions 1,2. Proposition 5. Let X be a set, L a complete residuated lattice, K = (LX , LX×X , I. ) be a formal context and A ⊆ LX a dataset of elements. Then the smallest concept with elements from A includes as attributes all fuzzy relations R ∈ LX×X such that Δ(Q∗)op ≤ R ≤ (Q∗)op where (Q∗)op and Δ(Q∗)op are specified in Propositions 1,2.
dataset with the corresponding model.
By Definition 2, a noisy and ideal elements from A are connected by equation
(
Let us construct a formal concept of K, suitable for characterization of an
latter will be defined as δ(W ) =
W (x, y),
X
x,y∈X
where W ∈ LX×X . It is easy to see that for two fuzzy relations Q∗ (given by (
The aim of this Section is to give illustrations to the theoretical results of this
paper. We use gray scaled images with the range [0, 1], where 0 (
We tested the two AFAM models (Q∗, ◦) and (Δ(Q∗), ◦), given in Example 1. The first experiment is to verify data retrieval. Both models successfully passed the verification. For the model that is based on the relation Δ(Q∗), we elaborated a fast algorithm of data retrieval that uses the fact that Δ(Q∗) is actually a binary relation.
conclude that the algorithm based on Δ(Q∗) is up to thirty time faster than that based on Q∗, see Table 1.
Image size 40 x 30 120 x 90
Run-time 1 Run-time 2 5.40 0.195 435.80 13.79
models (Q∗, ◦) and (Δ(Q∗), ◦) on eroded noise. For this purpose, we added 70% pepper noise to the original image in Fig. 1. The algorithm of data retrieval, based on the model (Q∗, ◦), was more efficient than that, based on the model (Δ(Q∗), ◦), see Fig. 2. 7
proposed. It extends [14] by using general algebraic structures and new types of autoregressive fuzzy associative memory models. We showed how the proposed theory is connected with systems of fuzzy relation equations and eigen sets of their solutions. We proposed a new concept of adjoint AFAM models that share
Fig. 1. Original image without noise (left) and with 70 % pepper noise (right). a common fuzzy preorder relation. We characterized two types of noise that can be reduced by retrieval in corresponding AFAM models. Two problems have been discussed: data retrieval and noise reduction.
analysis has been analyzed. We proposed a new working theory of FAM and formalized it in the language of formal concept analysis. We characterized two principal activities of FAM: data retrieval and noise reduction. We used the proposed formalism and showed that the problem of data retrieval is connected with solvability and eigen sets of a certain system of fuzzy relation equations.
13. Steinbuch, K.: Die lernmatrix. Kybernetik 1, 36-45 (1961) 14. Sussner, P. , Valle, M.-E.: Implicative Fuzzy Associative Memories. IEEE Trans.
Fuzzy Systems 14, 793–807 (2006) 15. Taylor, W.: Eletrical simulation on some nervous system functional activities. Inf.
Theory 15, 166-177 (2004) 16. Valverde, L.: On the structure of F-indistinguishability operators. Fuzzy Sets and
Syst. 17, 313-328 (1985) 17. Wille, R.: Formal Concept Analysis as Mathematical Theory of Concepts and Concept Hierarchies. In: B. Ganter et al. Formal Concept Analysis. Foundations and Applications, Springer (2005) 18. Zadeh, L. A.: The concept of a linguistic variable and its application to approximate reasoning I, II, III. Inf. Sci. 8-9, 199–257, 301–357, 43–80 (1975)