Creating of concept lattices is unfortunately difficult timeconsuming process. Neural networks can solve this problem, because they are adaptive in nature, due to their use of a training phase for learning the relationships in the input data, and their generalization capabilities provide a means of coping with noisy or incomplete data. In this text there is presented one possible approach to creating conceptual lattices using multilayer perceptron. The applicability of this approach was experimentally tested as well as parameters it depends on. Hardware acceleration (of the computing) is also discussed.
Concept analysis has proven to be a valuable tool for gaining insight into complex data. In many applications of concept analysis experts learn from formal contexts by inspecting their carefully laid out concept lattices. Contexts in these applications tend to have a modest size.
The algorithmic complexity of concept analysis for these applications is consequently a minor concern. But concept analysis is used increasingly for applications like program analysis inside a compiler or is combined with statistical analysis where large contexts are constructed by a program. The resulting concept lattice is no longer inspected visually but is part of an application’s internal data structure. For these applications the algorithmic complexity of concept analysis does matter. This paper presents a solution for computing the concept lattice by neural network. The neural network will be implement using hardware accelerator. 2.1
FCA has been defined by R. Wille and it can be used for hierarchical order of objects based on object’s features. The basic terms are formal context and formal concept. In this section there are all important definitions the one needs to know to understand the problems. Definition: A formal context C = (G, M, I) consists of two sets G and M and a relation I between G and M . Elements of G are called objects and elements of M are called attributes of the context. In order to express that an object g is in a relation I with an attribute m, we write gIm and read it as ”the object g has the attribute m”. The relation I is also called the incidence relation of the context.
For a set A ⊂
A↑ = {m ∈ M | gIm f or all g ∈ A}, the set of attributes common to the objects in A. Correspondingly, for a set B ⊂ M of attributes we define
B↓ = {g ∈ G | gIm f or all m ∈ B},
1 f (ξ ) = 1 + e− λξ , where λ represents the slope of the sigmoid. the set of objects which have all attributes in B.
For more information about formal concept analysis see [5] 2.2
Multilayer perceptrons are the most used neural networks, because they are universal approximators.
General properties of artificial neural networks are: – Many simple neuron-like threshold switching units – Many weighted interconnections among units – Learning to associate inputs to output by adjusting the connection weights (adaptation phase) – Ability of generalization – Highly parallel, distributed processing – Fault tolerance
The function of formal neuron in the network can be described as follows: y = f (ξ ) = f
N ! X xiwi . i=0 where xi is the ith input, wi is a synaptic weight of the ith input, N is the number of inputs, and f is (usually nonlinear) transfer function.
As transfer function f was used sigmoidal (logistic) function because it is
widely used in the many applications:
(
For adaptation of M LP was used classical backpropagation algorithm (BP ) [7] [16]. The backpropagation algorithm is a gradient descent method which works in much the same way as the name suggests:
After propagating an input through the network, the partial error (
The reason why use neural network is obvious: fault tolerance, generalization, adaptability, etc. Fault tolerance is one of the key attributes of neural networks, and this accrues from the distributed representation nature of neural networks. Because the information is stored in a distributed way throughout the electronic (or other) implementation, even if a few percent of the internal devices fail, the impact on the overall operation can be negligible. In local representation devices, failure of internal components means total absence of the pieces of information that were stored in. Also, for the specific test here considered relative to the conceptual lattice, it appears, there will be signicfiant speed and memory size advantages on the side of neural networks vs. parallel hardware.
There is a number of works dealing with Neural network approaches to conceptual lattices, graphs etc. So far Self-organizing map or a type of recurrent neural network (like BAM and Hopefild) was used [10, 2, 9].
Application of neural networks to any problem context requires that the data associated with that problem be encoded (represented) in a manner meeting specific requirements imposed by the neural-network methodology. We used the (reduced) matrix representation of conceptual lattices. 3.1
(
So the M LP realizes a mapping (i.e. a function) τ :
τ : {A}m → {O}n,
(
M LP will learn selected patterns (composed of attributes together with the required response objects).
The purpose is let the M LP recognize hidden dependencies among attributes and objects during the adaptation phase. After learning can the M LP compute objects (de facto concepts) even for non-learned configuration of attributes.
M LP in active phase gives response in real-time.
For real applicability we need solve two non-trivial problems: 1. How to select representative training set. We need select the patterns which contains the important features of concepts. The quality of generalization of M LP is very sensitive to this selection. 2. The speed of adaptation. 3.2
The testing set contains all concepts which were making from generated collection of 99 documents. Sample of documents is below: document 20: Xbbbba Xbbbbb Xbbbbc Xbbbbd Xbbbbe Xbbbbf Xbbbbg bbbbh bbbbi bbbbj Xffa Xgggga Xggggb Xggggc Xhhhha Xhhhhb Xhhhhc Xhhhhd Xhhhhe document 21: Xbbbba Xbbbbb Xbbbbc Xbbbbd Xbbbbe Xbbbbf Xbbbbg Xbbbbh bbbbi bbbbj Xgggga Xhhhha Xhhhhb Xhhhhc Xiiiia Xiiiib Xiiiic Xiiiid Xiiiie document 22: Xbbbba Xbbbbb Xbbbbc Xbbbbd Xbbbbe Xbbbbf Xbbbbg Xbbbbh Xbbbbi bbbbj Xhhhha Xiiiia Xiiiib Xiiiic Xjjjja Xjjjjb Xjjjjc Xjjjjd Xjjjje
The testing set consists of 890 concepts in context with 150 attributes and 99 objects. The training set for neural network was composed by each ffith concept from context (178 inputs).
We performed a number of experiments on network and BP parameters like topology, learning rate, number of iterations and so on.
Initially it was designed the network topology 190 − 99 − 99 in order to reach good generalization results. The best results, (i.e. the minimum number of wrong identified concepts (objects) in the whole set of concepts) gave network with 190 − 150 − 99 topology in conjunction with small learning rate – 0.01, which needed over 2000 iterations (on an average). 4
Since it is possible to have for example matrix of type 300000× 300000 in the real world, and time of adaptation is increasing rapidly, the fast computing device is needed.
Three ways of efficient implementing of digital neural computing is described in this section. 4.1
A better way of handling large matrices is illustrated by the following small example [8]. Let us assume two 3 × 3 matrices to be multiplied, and a device with six inputs for different values. It is possible to reverse order of performing multiplication:
a13b31 a13b32 a13b33 + a23b31 a23b32 a23b33
a33b31 a33b32 a33b33
| M{z3 }
(
So M1 contains values from the first column of A and the first row from B, instead of the rfist row from A and rfist column from B. M2 is using the encond column and row from A and B, respectively, and M3 is using the third. Bz reading matrices A and B in this way the multiplication can be done in three stages instead of nine.
If the device has 2n inputs, the information received is enough for n2 arithmetic operations instead of only n operations. In other words the information processed grows by the square of the number of inputs instead of linearly, an data-oflw is reduced dramatically. 4.2
The interest in using integer weights stems from the fact that integer multipliers can be implemented more efficiency than floating-point ones. There are also special learning algorithm [11, 12] which use powers-of-two integers as weights. The advantage of powers-of-two integer weight learning algorithm is that the required multiplications in an neural network can be reduced to a series of shift operations. Since this learning algorithm uses the classical BP algorithm with real arithmetics (the rfist step of adaptation), it is not feasible in stand-alone device.
The fact that despite continuing advantages in digital technology (concrete FPGAs) is still impractical to implement neural networks on FPGAs with floatingpoint precision weights showed Nichols at al. in his work [15], where they implemented on-line adaptation on the chip (direct implementation of BP ). 4.3
The solution described by Skrbek in [17] is based on linearly approximated functions in combination with the shift operation. It is based on simple functions 2x, log2 x and sigmoidal function.
Simple functions The linearly approximated 2x function can be defined by the expression
EXP2(x) = 2int(x)(1 + frac(x)),
(
The linearly approximated log2 x function can be expressed by
(
For easy implementation, the equation is valid for x ∈ h1, ∞) and for x ∈ h0, 1) is generated zero.
The sigmoid or tanh functions are often used an transfer function of a neuron. Both functions are based on ex which is very complex to calculate. Instead, we use the new function [17] based on the power of two: s(x) = sgn(x) 1 − 1 2|x| . its linearly approximated version is:
S(x) = sgn(x)
1
2int(|x|)
frac(| x |)
2
− 1
+ 1 ,
and range of this function is (
The small error caused by linear approximation is obvious (see figure 4.3).
Complex function Complex function are a composition of simple functions. Some complex functions require addtitional add operation to accomplish them. From the set of complex function we describe the most important one: multiplication. Multiplication is defined by x ∗ y = sgn(x)sgn(y)
EXP2(LOG2(2n | x |) + LOG2(2n | y |) ,
22n
(
About problems mentioned at the end of section 3: We selected each fifth pattern. This approach revealed itself successful and better than manual pattern selection. The strategies of pattern selection will be expanded in our further work.
The convergention speed during the adaptation phase can be accelerated by other suitable selection strategy (see above) and by hardware implementation. Efficient hardware implementation of neural networks is subject of research at VSB-Technical University of Ostrava.