In this paper, we show that formal concept analysis is a particular case of a more general problem that includes deriving rules for intelligent control, finding appropriate properties for deep learning algorithms, etc. Because of this, we believe that formal concept analysis techniques can be (and need to be) extended to these application areas as well. To show that such an extension is possible, we explain how these techniques can be applied to intelligent control.
This correlation enables us also to effectively interpolate and extrapolate, i.e., to adequately reconstruct missing information. For example, based on many readings of temperature, wind speed, and other meteorological characteristics ate several locations and heights, we can reasonable accurately reconstruct the values of these characteristics at other locations and heights.
Functions of one, two, etc. inputs. In many cases, we are interested in characteristics q that depend only on one (possible, multi-dimensional) input x: q = f (x). For example: – we may be interested in the temperature q(x) at different locations and different moments of time (i.e., at different points x in space-time), – we may be interested in the income q(x) of different people x at different moments of time, etc.
However, in many other cases, we are interested in characteristics q(x, y, . . .) that depend on two (or even more) different inputs x, y, . . . For example: – we may be interested in the degree q(x, y) to which a given person x would like or dislike a certain movie y (or a certain book, or a certain research paper if x is a researcher), – we may be interested in knowing the degree q(x, y) to which, in a given situation x, different controls y will lead to good results, etc.
In such situations, we need to compress, interpolate, and extrapolate the desired dependence q(x, y, . . .).
How can we compress, interpolate, and extrapolate multi-input dependencies: general description. For simplicity, let us consider the case when the desired quantity depends only on two inputs: q = q(x, y). In this case, in the beginning, – we have information about x and information about y, and – we need to perform some processing of this information.
A natural way to speed up data processing is to perform some operations in parallel – just like for us humans, a natural way for a person to perform a task faster is to have several helpers working at the same time on the same task. So, if there are some computational steps where we can process x separately and process y separately, these steps need to be performed in parallel before everything else. Thus, in general, processing such data consists of the following two major stages: – first, we perform an appropriate processing on x, resulting in some values a(x), and at the same time, we perform an appropriate processing on y, producing b(y); – after that, we perform some processing on the results a(x) and b(y) of the first stage, producing F (a(x), b(y)), where F denotes the algorithm performed at this second stage. At the end, we approximate the original dependence q(x, y) with the simpler-tostore and simpler-to-process dependence F (a(x), b(y)) ≈ q(x, y).
Let us describe possible situations, from the simplest to the most complicated. Linear case. The simplest case is when q(x, y) can be well approximated as a linear function of the values a(x) = (a1(x), . . . , ak(x)), i.e., when q(x, y) ≈ b0(y) + b1(y) · a1(x) + . . . + bk(y) · ak(y) for some coefficients bi(y) depending on y. By adding a0(x) = 1, we can make this formula more uniform
q(x, y) = b0(y) · a0(x) + b1(y) · a1(x) + . . . + bk(y) · ak(y).
In matrix notations qxy d=ef q(x, y), axi d=ef ai(x), and byi d=ef bi(y), this formula
takes the form
qxy =
k
X axi · byi.
i=0
(1)
This is a known idea of matrix decomposition, actively used in Principal
Component Analysis (see, e.g., [
A natural generalization of linear case, to operations generalizing addition and multiplication. In the above case (1): – we use multiplication to process individual components axi and bxi of the results a(x) and b(y) of processing x and y, and – we use addition to combine these results.
Instead of multiplication and addition, we can use more general combination functions.
For example, we can have expert control rules of the type “if x satisfies the
property ai (e.g., if x > 0.1), then the control y should satisfy the property bi
(e.g., y ∈ [
If we: – denote the truth value of the statement “x satisfies the property ai” by ai(x) and – denote the truth value of the statement “y satisfies the property bi” by bi(y), then the truth value q(x, y) of the statement “y is a reasonable control for x” takes the form
q(x, y) = (a1(x) & b1(y)) ∨ (a2(x) & b2(y)) ∨ . . .
This is the usual example of formal concept analysis; see, e.g., [
This example can be extended to the case when experts use imprecise
(“fuzzy”) words from natural language to describe their rules; see, e.g., see,
e.g., [
We can then ask the expert to estimate, on a scale from 0 to 1, the degrees ai(x) to which different values x satisfy the imprecise (“fuzzy”) property ai and the degrees bi(y) to which different values y satisfy the property bi.
Since it is usually not practically possible to ask the expert to provide estimates for the combined statement “x satisfies the property ai and y satisfies the property bi” for all the pairs (x, y) – there are just too many possible pairs – we have to estimate the degrees to which such statements are true based on whatever information is available – namely, the degrees ai(x) and bi(y). For this estimation, we can use a general algorithm f&(a, b) for estimating our degree of confidence in a composite statement A & B based on our degrees of confidence a and b in the statement A and B.
This algorithm has to satisfy certain properties: e.g., since A & B means the same as B & A, this operation must be commutative; since A & (B & C) is equivalent to (A & B) & C, this operation must be associative, etc. Such operations are known as “and”-operations, or, for historical reasons, t-norms.
Similarly, we can use a similarly motivated “or”-operation (also known as t-conorm) f∨(a, b) to estimate our degree of confidence in A ∨ B based on our degrees of confidence a and b in the statements A and B. In these terms, the desired degree of confidence q(x, y) can be described as follows: q(x, y) = f∨(f&(a1(x), b1(y)), f&(a2(x), b2(y)), . . .). (2) Case when some transformations are linear, while others are not. So far, we have considered the case when the functions F is linear – or similar to linear, with more general operations instead of addition and multiplication.
In some cases, a linear transformation is followed by a non-linear one. For
example, in a traditional 3-layer neural network (see, e.g., [
K q = X k=1
Wk · sk n X wki · xi − wki i=1 ! − W0, (3) for some non-linear functions sk(z). n In other words, we first compute linear combinations ak(x) = P wki·xi−wki, i=1 K and then perform a non-linear transformation q = P sk(ak) − W0. k=1 General case, when everything is possibly non-linear. In general, we may have non-linear transformations a(x) and b(y), followed by a nonlinear transformation F (a, b).
A typical example of such a representation is deep learning (see, e.g., [
What Is the Remaining Problem and How Formal Concept Analysis Techniques Can Help General problem. If we have rules, and these rules are perfect, there is no problem. However, this is rarely the case. In most practical situations, we have some information about q(x, y), and we need to come up with the appropriate decomposition into a(x), b(y), and F (a, b).
– In the linear case of matrix decomposition, we have examples of people’s attitude to different movies, and we need to come up with the most adequate values axi and byi. – In the case of formal concept analysis, we have a table (often only partially filled) of truth values q(x, y), and we need to find appropriate predicates ai(x) and bi(y). – In the case of intelligent control, we have degrees q(x, y), and we need to come up with appropriate rules – e.g., with the most appropriate functions ai(x) and bi(y). – In the case of deep learning, while there are spectacular successes – like beating a world champion in Go, there are also spectacular failures, when the system classifies a clearly cat picture as a dog and vice versa. This means that even in this case, the problem of finding the appropriate values ai(x) and bi(y) is far from being solved.
How can formal concept analysis technique help. Of course, most of
the above problems are NP-hard (see, e.g., [
Such an extension is clearly possible – e.g., the paper [
Conclusion. Our conclusion is simple and straightforward: let us thing big, let us extend what we have to other cases.
Acknowledgments The author is greatly thankful to Radim Belohlavek, Marketa Krmelova, and Martin Trnecka for their help and encouragement. A
How Formal Concept Analysis Can Help Extract Intelligent Control Rules We have a finite set of pairs (x, y) for which we know q(x, y). Let us denote this set by P . Based on this information, how can we find appropriate functions ai(x) and bi(y)?
In this appendix, we show that in this general intelligent control case, we can
use a greedy algorithm that was originally proposed in [
By definition of a greedy algorithm: – we start by finding the functions a1(x) and b1(y), – then we fix the selected functions a1(x) and b1(y) and find the functions a2(x) and b2(y), etc., and, – in general, we fix the already selected functions a1(x), b1(y), . . . , ak−1(x), bk−1(y), and select a pair of functions ak(x) and bk(x).
From the equation (2) and from the fact that p ≤ f∨(p, q) for all p and q, we can conclude that for each k, we should have f∨(f&(a1(x), b1(y)), . . . , f&(ak−1(x), bk−1(y)), f&(ak(x), bk(y))) ≤ q(x, y), qk−1(x, y) d=ef f∨(f&(a1(x), b1(y)), . . . , f&(ak−1(x), bk−1(y))) for k − 1 ≥ 1 and q0(x, y) d=ef 0.
A natural idea is to select the functions ak(x) and bk(y) that would cover as many pairs (x, y) as possible, i.e., for which the value
Nk(ak, bk) d=ef #{(x, y) ∈ P : f∨(qk−1(x, y), f&(ak(x), bk(y))) = q(x, y)} i.e., equivalently, that where we denoted f∨(qk−1(x, y), f&(ak(x), bk(y))) ≤ q(x, y), (4) is the largest possible, where #S denoted the number of elements in the set S.
From this viewpoint, once we selected bk(y), it is reasonable to select a function ak(x) which leads to the largest possible coverage, i.e., to select (bk)↓k (x) d=ef sup{a : ∀y ∈ Yx (f∨(qk−1(x, y), f&(a, bk(y))) ≤ q(x, y))}, where Yx d=ef {x : (x, y) ∈ P }. Similarly, if we have selected the function ak(x), then it is reasonable to select a function bk(y) which leads to the largest possible coverage, i.e., to select
(ak)↑k (y) d=ef sup{b : ∀x ∈ Xy (f∨(qk−1(x, y), f&(ak(x), b)) ≤ q(x, y))}, where Xy d=ef {y : (x, y) ∈ P }.
Comment. The notations similar to the usual notations from the formal concept analysis are motivated by the fact that in the usual 2-valued logic: – there are only two truth values 0 and 1; – when s0 ≤ s, then s0 ∨ t ≤ s if and only if t ≤ s; and – a & b ≤ s if and only if a ≤ (b → s).
By using these properties, one can check that in the 2-valued logic, the above formulas can be represented in the following simplified equivalent form (not depending on qk−1(x, y)): (ak)↑k (y) = inf (ak(x) → a(x, y));
x∈Xy (bk)↓k (x) = inf (bk(y) → S(x, y)),
y∈Yx which are exactly the usual notions (ak)↑ and (bk)↓ in formal concept analysis.
Let us now describe an iterative procedure for finding bk(y) and ak(x). In the beginning, the only information that we know about bk(y) and ak(x) is that bk(y) ≥ 0 and ak(x) ≥ 0. Thus, as the starting approximations to the desired functions bk(y) and ak(x), we take b(k0)(y) = 0 and a(k0)(x) = 0. For these functions, the quality Nk a(k0), b(k0) is simply equal to the previous value Nk−1.
Let us now start improving this selection step by step. In general, let us assume that we have already found approximations b(ki−1)(y) and a(ki−1)(x), for which the approximation quality is equal to Nk a(i−1), b(ki−1) . k
If some pairs (x, y) are still not covered by this selection, we should try to increase one of the functions b(ki−1)(y) and a(i−1)(x). Let us start with b(ki−1)(y). k The simplest idea is to increase the value b(ki−1)(y) for one of the value y0 to the largest possible value
by0 (y0) d=ef sup{b : ∀x ∈ Xy0 (f∨(qk−1(x, y0), f&(a(ki−1)(x), b) ≤ q(x, y0))}, while keeping all other values b(ki−1)(y) unchanged: by0 (y) = b(ki−1)(y) for all y 6= y0.
For each y0, we form the resulting function by0 (y), and take ak,y0 = (by0 )↓k and bk,y0 = (ak,y0 )↑k = (by0 )↓k↑k . For each y0, we find the value Nk(ak,y0 , bk,y0 ) of the objective function, and select ymax for which this value is the largest: Nk(ak,ymax , bk,ymax ) = max Nk(ak,y0 , bk,y0 ).
y0
The corresponding functions bk,ymax (y) and ak,ymax (x) are then taken as the next iteration b(ki)(y) and a(ki)(x): b(ki) = bk,ymax (y) and a(i) = ak,ymax (y). Iterak tions continue while the value Nk continues to grow, i.e., while
Nk a(ki), b(ki) > Nk a(i−1), b(ki−1) .
k Nk a(ki), b(ki) = Nk a(i−1), b(ki−1) , k the iterations stop, and the corresponding functions bk(y) d=ef b(ki)(y) and ak(x) d=ef a(ki)(x) are added to the list of pairs
(a1(x), b1(y)), . . . , (ak−1(x), bk−1(y)).
If after this addition, some pairs (x, y) ∈ P are still not covered, we similarly find and add the next pair of functions ak+1(x) and bk+1(y), etc., until all the pairs (x, y) ∈ P are covered.
Our preliminary experiments show that this algorithm leads to reasonable rules.
Comment. A similar greedy algorithm can be used when, instead of the abovedescribed methodology, we use a more logical way to convey the expert’s if-then rules, i.e., when we take
q(x, y) = f&(f→(a1(x), b1(y)), f→(a2(x), b2(y)), . . .), where f→(a, b) is an implication operation, i.e., an estimate for degree to which the statement A → B is true given the degrees of confidence a and b in the statements A and B.