The main result of the paper provides a lower bound on su cient number of randomly generated formal concepts to correctly predict all important positive test examples with given con dence level. The technique coincides with modern approach to the famous theorem of V.N. Vapnik and A.Ya. Chervonenkis. However the situation is dual to the classical one: in our case test examples correspond to xed subsets and probabilistically generated formal concepts must fall into selected areas of su cient large volume.
The key question of the approach is how to determine su cient number of hypotheses to predict target class with given level of con dence. The paper proposes an answer to this question.
Used technique mostly coincides with modern approach to the famous theorem of V.N. Vapnik and A.Ya. Chervonenkis. However the situation is dual to the classical one: in our case test examples correspond to xed subsets and probabilistically generated formal concepts must fall into selected areas of su cient large volume. The general approach of Vapnik-Chervonenkis uses the \Occam razor" principle where no assumption on selected hypothesis made except to its correctness on all training examples. Hence a hypothesis coincides with area of objects space. To reject a bad hypothesis is needed to randomly pick training objects from the corresponding subset. 2
2.1
Basic de nitions and facts of FCA Here we recall some basic de nitions and facts of Formal Concept Analysis (FCA) [1].
A ( nite) context is a triple (G; M; I) where G and M are nite sets and I G M . The elements of G and M are called objects and attributes, respectively. As usual, we write gIm instead of hg; mi 2 I to denote that object g has attribute m.
For A G and B M , de ne
A0 = fm 2 M j8g 2 A(gIm)g;
B0 = fg 2 Gj8m 2 B(gIm)g;
(
A concept of the context (G; M; I) is de ned to be a pair (A; B), where A G, B M , A0 = B, and B0 = A. The rst component A of the concept (A; B) is called the extent of the concept, and the second component B is called its intent. The set of all concepts of the context (G; M; I) is denoted by B(G; M; I).
Let (G; M; I) be a context. For concepts (A1; B1) and (A2; B2) in B(G; M; I) we write (A1; B1) (A2; B2), if A1 A2. The relation is a partial order on B(G; M; I).
A subset A G is the extent of some concept if and only if A00 = A in which case the unique concept of which A is the extent is (A; A0). Similarly, a subset B of M is the intent of some concept if and only if B00 = B and then the unique concept with intent B is (B0; B).
Proposition 1. [1] Let (G; M; I) be a context. Then (B(G; M; I); ) is a lattice with join and meet given by j2J j2J _ (Aj; Bj) = (( [ Aj)00; \ Bj); ^ (Aj; Bj) = ( \ Aj; ( [ Bj)00); j2J j2J
j2J j2J Lemma 2. Let (G; M; I) be a context, (A1; B1); (A2; B2) 2 B(G; M; I), g 2 G, and m 2 M . Then
(A1; B1) (A1; B1)
(A2; B2) ) CbO((A1; B1); g) (A2; B2) ) CbO((A1; B1); m)
CbO((A2; B2); g); CbO((A2; B2); m):
Now we represent the coupling Markov chain algorithm that is a core of probabilistic approach to machine learning based on FCA (VKF-method). Corollary 1. For context (G; M; I) the lattice (B(G; M; I); ) has (M 0; M ) as the bottom element and (G; G0) as the top element. In other words, for all (A; B) 2 B(G; M; I) the following inequalities hold: (M 0; M ) (A; B)
(G; G0): g 2 A ) CbO((A; B); g) = (A; B); m 2 B ) CbO((A; B); m) = (A; B);
g 2= A ) (A; B) < CbO((A; B); g); m 2= B ) CbO((A; B); m) < (A; B): De nition 1. For (A; B) 2 B(G; M; I), g 2 G, and m 2 M de ne CbO((A; B); g) = ((A [ fgg)00; B \ fgg0);
CbO((A; B); m) = (A \ fmg0; (B [ fmg)00): so CbO((A; B); g) is equal to (A; B) _ (fgg00; fgg0) and CbO((A; B); m) is equal to (A; B) ^ (fmg0; fmg00).
We call these operations CbO because the rst one is used in Close-by-One (CbO) Algorithm to generate all the elements of B(G; M; I), see [2] for details.
Useful properties of introduced operations are summarized in the following
Lemma 1. Let (G; M; I) be a context, (A; B) 2 B(G; M; I), g 2 G, and m 2 M .
Then
(
tu
(
tu
(
Result: random concept (A; B) 2 B(G; M; I) X := G t M ; (A; B) := (M 0; M ); (C; D) = (G; G0); while ((A 6= C) _ (B 6= D)) do select random element x 2 X; (A; B) := CbO((A; B); x); (C; D) := CbO((C; D); x); end
2.2
Probabilistic algorithms for FCA-based machine learning Now we represent the general scheme of machine learning based on FCA (VKFmethod). The reader can learn the classical deterministic FCA-based approach to machine learning from Kuznetsov [4]. Our technique uses probabilistic Algorithm 1 for computing a random subset of formal concepts.
As usual, there are two sets of objects called the training and test samples, respectively.
From positive examples of the training sample the program generates a formal context (G+; M; I). The negative examples form the set G of counter-examples (obstacles).
After that the program applies the coupling Markov chain algorithm 1 to generate a random formal concept (A; B) 2 B(G+; M; I). The program saves the concept (A; B), if there is no obstacle o 2 G such that B o0.
G+ := (+)-examples, M := attributes; I G+ M is a formal context for (+)-examples; G := (-)-examples; S := ;; i := 0; while (i < N ) do
Generate concept hA; Bi by Algorithm 1; hasObstacle := false; for (o 2 G ) do if (B o0) then
hasObstacle := true; end end if (hasObstacle = false) then
S := S [ fhA; Big; i := i + 1; end end
Condition (B o0) of Algorithm 2 means the inclusion of intent B of concept hA; Bi into the fragment (attributes subset) of counter-example o.
If a concept avoids all such obstacles it is added to the result set of all the concepts without obstacles.
We replace a time-consuming deterministic algorithm (for instance, "Closeby-One") for generation of all concepts by the probabilistic one to randomly generate the prescribed number of concepts.
The goal of Markov chain approach is to select a random sample of formal concepts without computation of the (possibly exponential size) set B(G; M; I) of all the concepts.
Finally, machine learning program predicts the target class of test examples and compares the results of prediction with the original target value.
for (o 2 X) do
P redictP ositively(o) := false; for (hA; Bi 2 S+) do if (B o0) then
P redictP ositively(o) := true; end end end
3
De nition 2. Object o with fragment (attributes subset) o0 predicted by concept hA; Bi if B o0.
M is positively
If there are n = jM j attributes then intent B of any concept hA; Bi is a point of n-hypercube f0; 1gn.
De nition 3. Lower half-space H#(o) corresponding to object o with fragment o0 M is de ned by linear inequality xj1 + : : : + xjk < 12 , where M n o0 = fmj1 ; : : : ; mjk g. The empty lower half-space 0 < 21 (equals to f0; 1gn) is allowed too and corresponds to o0 = M .
Lemma 3. Object o is positively predicted if and only if lower half-space H#(o) contains a fragment B of at least one concept hA; Bi.
De nition 4. Object o is called "-important if probability of occurrence of random concept hA; Bi with B 2 H#(o) is greater than ".
A family of concepts is called "-net if for each "-important object o there is at least one its member hA; Bi with B 2 H#(o).
Now we are interested only in 1-st type error probability (positive prediction fails): we need to determine a number N (depending on " and ) such that a random sample of cardinality N forms "-net with probability greater than 1 . Lemma 4. For all " with l > 2" and for any independent random samples S1 and S2 of concepts of cardinality l the following inequality holds: PlfS1 : 9H 2 (Sub #) [S1 \ H = ;; PH > "]g
2 P2lfS1S2 : 9H 2 (Sub #) [S1 \ H = ;; jS2 \ Hj > " l=2]g: Lemma 5. For all " and for any independent random samples S1 and S2 of concepts of cardinality l the following inequality holds:
P2lfS1S2 : 9H 2 (Sub #) [S1 \ H = ;; jS2 \ Hj > " l=2]g Theorem 1. For n = jM j and for any " > 0 and 1 > concepts of cardinality
N 2 (n + 1)
2 log2 "
mSub#(2l) 2 "l=2: > 0 random sample of 2 "N=2 with respect to N to obtain the forms "-net with probability > 1
.
estimate.
In this paper we provided a lower bound on su cient number of randomly generated formal concepts to correctly predict all important positive test examples with given con dence level. The technique mostly coincides with modern approach to the famous theorem of V.N. Vapnik and A.Ya. Chervonenkis, but the situation is dual to the classical one.
The author would like to thank Prof. Victor K. Finn and his colleagues at Federal Research Center for Computer Science and Control of Russian Academy of