How Formal Concept Analysis Fits into the General Scheme of Being

General need for compression. The current world is filled with data. At any given moment of time, numerous sensors produce humongous amount of numerical measurement results, images, videos, etc. This data is usually useful -otherwise it would not have been produced, so it is desirable to store and process this information.

However, the problem is that our ability to produce information way exceeds our ability to store and process it. As a result, we cannot physically store every bit produced by the sensors, we need to compress this data.

Compression is closely related to interpolation and extrapolation. Of course, if all the bits were independent, if each was informative -containing information that cannot be extracted from other bits -there would be no way to drastically compress this information without losing a significant portion of it. And this would make producing this immediately deleted information useless.

Good news is that bits are not independent, there is usually a strong correlation between them, correlation that allows us to drastically decrease the number of stored bits without losing much information. For example, a photo can be easily compressed from several Megabytes to dozens of Kylobytes -several orders of magnitude -and we can still easily recognize all the features of a person on the webpage where this compressed photo is posted.

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) = (a 1 (x), . . . , a k (x)), i.e., when

q(x, y) ≈ b 0 (y) + b 1 (y) • a 1 (x) + . . . + b k (y) • a k (y)

for some coefficients b i (y) depending on y. By adding a 0 (x) = 1, we can make this formula more uniform

q(x, y) = b 0 (y) • a 0 (x) + b 1 (y) • a 1 (x) + . . . + b k (y) • a k (y).

In matrix notations q xy def = q(x, y), a xi def = a i (x), and b yi def = b i (y), this formula takes the form

q xy = k i=0 a xi • b yi .(1)

This is a known idea of matrix decomposition, actively used in Principal Component Analysis (see, e.g., [15]), in predicting people's reaction to movies, etc.

(see, e.g., [1,17]).

A natural generalization of linear case, to operations generalizing addition and multiplication. In the above case (1):

-we use multiplication to process individual components a xi and b xi 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 a i (e.g., if x > 0.1), then the control y should satisfy the property b i (e.g., y ∈ [0, 1])". We can then combine these rules into an equivalent formula, according to which y is a reasonable control for the situation x if:

-either the first rule is applicable, i.e., x satisfies the property a 1 and y satisfies the property b 1 , -or the second rule is applicable, i.e., x satisfies the property a 2 and y satisfies the property b 2 , etc.

If we:

-denote the truth value of the statement "x satisfies the property a i " by a i (x) and -denote the truth value of the statement "y satisfies the property b i " by b i (y),

Formal Concept Analysis Techniques Can Help in Intelligent Control, Deep

Learning, etc.

then the truth value q(x, y) of the statement "y is a reasonable control for x" takes the form

q(x, y) = (a 1 (x) & b 1 (y)) ∨ (a 2 (x) & b 2 (y)) ∨ .

. . This is the usual example of formal concept analysis; see, e.g., [3,6] 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., [2,8,10,13,14,16]. In this case, the expert's control rules have a similar form "if x is a i (e.g., small), then the control y should be b i (e.g., moderate)". We can similarly translate these rules into an equivalent formula, according to which y is a reasonable control for the situation x if:

-either the first rule is applicable, i.e., x satisfies the property a 1 and y satisfies the property b 1 , -or the second rule is applicable, i.e., x satisfies the property a 2 and y satisfies the property b 2 , etc.

We can then ask the expert to estimate, on a scale from 0 to 1, the degrees a i (x) to which different values x satisfy the imprecise ("fuzzy") property a i and the degrees b i (y) to which different values y satisfy the property b i . Since it is usually not practically possible to ask the expert to provide estimates for the combined statement "x satisfies the property a i and y satisfies the property b i " 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 a i (x) and b i (y). 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 & (a 1 (x), b 1 (y)), f & (a 2 (x), b 2 (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., [5]), the result q of processing the inputs x 1 , . . . , x n has the form

q = K k=1 W k • s k n i=1 w ki • x i − w ki − W 0 ,(3)

for some non-linear functions s k (z).

In other words, we first compute linear combinations

a k (x) = n i=1 w ki •x i −w ki ,

and then perform a non-linear transformation q

= K k=1 s k (a k ) − W 0 .

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., [7]), where the dimension of the signal decreases as we go from the multi-D input through processing layers, and thus, the original multi-dimensional signal is compressed -and, in general, compressed non-linearly. Interestingly, in many experiments, the intermediate results have intuitive meaning -so that the same intermediate values can be used for other problems y.

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 a xi and b yi . -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 a i (x) and b i (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 a i (x) and b i (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 a i (x) and b i (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., [11,12]), so we cannot expect to find a feasible algorithm that always finds a solution. However, many efficient techniques have been developed in formal concept analysis, and it is desirable to extend them to other cases as well. Such an extension is clearly possible -e.g., the paper [4] provided an efficient greedy algorithm for deriving fuzzy values when f & (a, b) = max(a + b − 1, 0) and f ∨ (a, b) = min(a + b, 1), and the paper [9] showed that the same algorithm can work for other "and"-and "or"-operations as well. The unpublished result from [9] is briefly described in the Appendix.

Conclusion.

Our conclusion is simple and straightforward: let us thing big, let us extend what we have to other cases.

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 a i (x) and b i (y)?

In this appendix, we show that in this general intelligent control case, we can use a greedy algorithm that was originally proposed in [4] for a specific case of "and"-and "or"-operations.

By definition of a greedy algorithm:

-we start by finding the functions a 1 (x) and b 1 (y), -then we fix the selected functions a 1 (x) and b 1 (y) and find the functions a 2 (x) and b 2 (y), etc., and, -in general, we fix the already selected functions a 1 (x), b 1 (y), . . . , a k−1 (x), b k−1 (y), and select a pair of functions a k (x) and b k (x).

How do we select these functions a k (x) and b k (y)? 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 & (a 1 (x), b 1 (y)), . . . , f & (a k−1 (x), b k−1 (y)), f & (a k (x), b k (y))) ≤ q(x, y), i.e., equivalently, that f ∨ (q k−1 (x, y), f & (a k (x), b k (y))) ≤ q(x, y),(4)

where we denoted

q k−1 (x, y) def = f ∨ (f & (a 1 (x), b 1 (y)), . . . , f & (a k−1 (x), b k−1 (y)))

for k − 1 ≥ 1 and q 0 (x, y) def = 0. A natural idea is to select the functions a k (x) and b k (y) that would cover as many pairs (x, y) as possible, i.e., for which the value

N k (a k , b k ) def = #{(x, y) ∈ P : f ∨ (q k−1 (x, y), f & (a k (x), b k (y))) = q(x, y)} Formal Concept Analysis Techniques Can Help in Intelligent Control, Deep

Learning, etc.

is the largest possible, where #S denoted the number of elements in the set S.

From this viewpoint, once we selected b k (y), it is reasonable to select a function a k (x) which leads to the largest possible coverage, i.e., to select

(b k ) ↓ k (x) def = sup{a : ∀y ∈ Y x (f ∨ (q k−1 (x, y), f & (a, b k (y))) ≤ q(x, y))},

where Y x def = {x : (x, y) ∈ P }. Similarly, if we have selected the function a k (x), then it is reasonable to select a function b k (y) which leads to the largest possible coverage, i.e., to select

(a k ) ↑ k (y) def = sup{b : ∀x ∈ X y (f ∨ (q k−1 (x, y), f & (a k (x), b)) ≤ q(x, y))},

where X y def = {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 s 0 ≤ s, then s 0 ∨ 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 q k−1 (x, y)): Let us now describe an iterative procedure for finding b k (y) and a k (x). In the beginning, the only information that we know about b k (y) and a k (x) is that b k (y) ≥ 0 and a k (x) ≥ 0. Thus, as the starting approximations to the desired functions b k (y) and a k (x), we take b If after this addition, some pairs (x, y) ∈ P are still not covered, we similarly find and add the next pair of functions a k+1 (x) and b k+1 (y), etc., until all the pairs (x, y) ∈ P are covered.

(a k ) ↑ k (y) = infy0 (y 0 ) def = sup{b : ∀x ∈ X y0 (f ∨ (q k−1 (x, y 0 ), f & (a (i−1) k (x), b) ≤ q(x, y 0 ))},

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 → (a 1 (x), b 1 (y)), f → (a 2 (x), b 2 (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.