Main result of the paper provides a small upper bound on a probability of overfitting in FCA-based Machine Learning in the simplest case of Boolean algebra without counter-examples. This Machine Learning approach uses a set of randomly generated formal concepts to predict test examples. The well-known Vapnik-Chervonenkis' technique of empirical risk minimization determines a number of generated concepts. Estimations of Mixture and Stopping times of several probabilistic algorithms based on Markov chains leads to a plausible assumption on the uniform independent distribution of elements of Boolean algebra. In this case the main theorem proves that the probability of overfitting in fixed fraction of test examples tends to zero faster than exponent when the number of attributes goes to infinity.
applies the coupling Markov chain to generate a random sample of concepts. Each run of this chain terminates with probability 1. Early the system uses a monotonic Markov chain that corresponds to the famous Lazy Random Walk in the case of Boolean algebra. The paper [10] discuses Induction procedure for generalization of training examples into hypotheses about causes of the property under research with counter-examples forbidding. Finally the system predicts a target class of each test example by Analogy reasoning.
The main result of paper [10] gives a suficient number of hypotheses to predict a target class with given level of confidence. The framework is dual to the famous one of V.N. Vapnik and
However V.N. Vapnik and A.Ya. Chervonenkis also developed another approach to choose a good hypothesis. Best one must minimize an empirical risk (a fraction of wrongly predicted training examples). The main problem in this approach is to estimate a fraction of test examples with prediction error. We provide a partial answer on this task in the simplest case of Boolean algebra without counter-examples.
Here we recall some basic definitions and facts of Machine Learning based on Formal Concept
Analysis (FCAML) in the particular case of Boolean algebra. Most general situation is considered
in [10]. Book [
The smallest (formal) context for -dimensional Boolean algebra is a triple (, , ̸=), where = {1, . . . , } is a set of coatoms (objects), = {1, . . . , } is a set of binary attributes, and ̸=⊆ × is relation defined as ̸= ⇔ ̸= .
A concept of the Boolean algebra context (, , ̸=) is defined to be a pair (, ), where ⊆ , ⊆ , = { ∈ : ∀ ∈ [ ̸= ]}. The first component of the concept (, ) is called the extent of the concept, and the second component is called its intent. It clear that the lattice of concepts coincides with Boolean algebra of all the subsets ⊆ . We consider the partial order on it dual to set inclusions.
This observation proves truth of the first obstacle of applicability of FCA to Big Data from Introduction. When formal context occupies 2 bites only, the full description of -dimensional Boolean algebra requires · 2 bites of memory.
Proposition 1. For context (, , ̸=) corresponding Boolean algebra of concepts has (∅, ) as the bottom element and (, ∅) as the top element. In other words, for every the concept (, ) the following inequalities hold:
(∅, ) ≤ (, ) ≤ (, ∅).
Definition 1. For a concept (, ), ∈ , and ∈ define
((, ), ) = ((, ), ) = {︃(, ) {︃(, ) ( ∪ {}, ∖ {}) ∈/ ( ∖ { }, ∪ { }) ∈/ ∈ .
(1) (2) (3)
We call these operations CbO because the first one is used in Close-by-One (CbO) Algorithm
to generate all the formal concepts of an arbitrary context, see [
Monotonicity property of introduced operations are summarized in the following Lemma. Lemma 1. Let (, , ̸=) be a context, (, ) and (, ) be concepts for it, ∈ , and ∈ . Then
(, ) ≤ (, ) ⇒ ((, ), ) ≤ ((, ), ), (, ) ≤ (, ) ⇒ ((, ), ) ≤ ((, ), ). (4) (5)
Initially the system used the monotonic Markov chain algorithm as a core of probabilistic approach to Machine Learning based on FCA.
Data: context (, , ̸=)
:= ⊔ ; (, ) := (∅, ); for ( := 0; < ; + +) do select random element ∈ ; (, ) := ((, ), ); end
The main dificulty with the monotonic Markov chain in general case is an absence of a good estimation on length of its trajectory to achieve approximately stationary distribution. However the case of Boolean algebra was investigated successfully by the author. Next subsection contains the key results about it.
Then the coupling Markov chain algorithm described below appears, where there exists the natural stopping moment. Now it is a working horse for our approach.
Data: context (, , ̸=) Result: random concept (, ) := ⊔ ; (, ) := (∅, ); (, ) = (, ∅); while ( ̸= ) do select random element ∈ ; (, ) := ((, ), ); (, ) := ((, ), ); end
The algorithm terminates when upper and lower concepts coincide. Condition on remaining of ordering between two concepts (, ) ≤ (, ) at any intermediate step of the while loop of Algorithm 2 follows from Lemma 1.
Now we represent Machine Learning based on FCA (FCAML-method) for our setting (Boolean algebra without counter-examples). See seminal paper[10] for description of the general scheme of FCAML-method.
The reader can learn the classical deterministic FCA-based approach to Machine Learning from Kuznetsov [5]. Our technique uses probabilistic Algorithm 2 for computing a random subset of concepts.
As usual, there are two sets of objects called the training = {1, . . . , } and test = {1, . . . , } samples, respectively. Set contains examples to predict the target class (so-called test objects).
From the training samples the program generates a formal context (, , ̸=), where = {1, . . . , }. After that the program applies the coupling Markov chain Algorithm 2 to generate a given number of random concepts (, ).
while ( < ) do
Generate concept (, ) by Algorithm 2; := ∪ {(, )}; := + 1; end end break; end end
FCAML-method replaces a time-consuming deterministic algorithm (for instance, "Close-byOne") 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 of all the concepts.
How to select number of concepts for the coupling Markov chain? There are 2 diferent approaches, both based on ideas of V.N. Vapnik and A.Ya. Chervonenkis. The approach promoted by K.V. Vorontsov is the empirical risk minimization.
:=training examples; := 0; for ( ∈ ) do for (⟨, ⟩ ∈ ) do if ( ⊆ { }′) then := + 1 ;
In the Boolean algebra case it is possible select suficiently large to make the empirical rick equals to 0.
With permutation, we can assume without reducing generality that the first objects were included in the training sample, and the last objects form the test sample.
Let of FCA Machine Learning hypotheses be generated using a coupling Markov chain from a training sample for Boolean algebra, where chosen suficiently large to obtain = 0.
Stationary distribution uniformity on hypotheses allows to construct hypothesis ℎ = ( , ) (where 1 ≤ ≤ ) from independent Bernoulli sequence = ( ,1, . . . , ,) as = { : , = 0} and = { : , = 1}.
Finally, the FCAML program predicts the target class of test examples and computes tests example + with the intent {+}′ = { ∈ : ̸= }.
Consider set of binary features = {1, . . . , }. For each 1 ≤ ≤ introduce test Independent Bernoulli sequence = ( ,1, . . . , ,) determines the corresponding hypothesis ℎ = ( , ), where = { : , = 0} and = { : , = 1}.
Data: random sample = {(1, 1), . . . , ( , )} of concepts :=test examples; = 0; for ( ∈ ) do for ( := 0; < ; + +) do if ( ⊆ { }′) then
:= + 1; end break; end end hypercube.
Algorithm 1 in the case of Boolean algebra coincides with famous Lazy Random Walk on Boolean Lemma 2. Stationary distribution of Lazy Random Walk is uniform.
The simplest proof of Lemma 2 uses reversibility of the corresponding Markov chain with
∈ ⟩ on finite space is defined as the half of 1-metric, i.e. ‖ − ‖ = 21 · ∑︀ Definition 2.
Total variation distance between distributions = ⟨ : ∈ ⟩ and = ⟨ : ∈ | − |.
Lemma 3. ‖ − ‖ = max⊆ | () − ()|.
Proposition 2. For Lazy Random Walk let and = 0 otherwise, and let be the uniform distribution. Then (0) =
P [+1 = | = ] = , ( ) =
P [+1 = ( ⊕ ) | = ] = 1 2 1 2 − 1 . holds for ≥ 21 · · (log + ).
This proposition is analogue of result of Diakonis [
Comparison of Algorithms 1 and 2 gives assertion that the lower component of the coupling
The next two propositions estimate mean length E of trajectory of coupling Markov chain (Algorithm 2) and proves the strong concentration of trajectory length around the mean E . The author proved them during research on coupling Markov chain (Algorithm 2). Proposition 3. For -dimensional Boolean algebra Proposition 4. For -dimensional Boolean algebra
=1 when → ∞ for any > 0.
Statements of Propositions 2 and 3 and Lemma 4 imply the assertion that outputs of Algorithm
Since each trajectory depends only on (pseudo-)random number generator, these outputs are independent.
But random subsets of binary attributes can be generated by Bernoulli sequences. It provides possibility of direct probabilistic computations. In the next section these considerations lead to main result of the paper.
Any set of hypotheses about causes of the target property can be considered as a classifier: if a test example includes at least one hypothesis, then the classifier will predict the target class positively; if none of the hypothetical reasons is embedded in a test example, then this example is classified negatively.
The method of minimizing empirical risk proposed by V.N. Vapnik and A.Ya. Chervonenkis [7] consists in choosing algorithms for which the classification of training examples contains the minimum number of errors (empirical, or observed, risk). In our case, there will always be classifiers (sets of hypotheses) whose empirical risk is zero. We restrict ourselves to these situations only. On the other hand, a risk of making a mistake in predicting test examples remains.
Following K.V. Vorontsov[11], we will randomly divide objects into two groups: training and test examples. For simplicity, let’s assume that the number of objects is even, and the splitting is done in half. This assumption does not reduce generality, since the mean binomial coeficient is the largest one.
Let’s denote the empirical risk by and introduce the prediction risk as a fraction of = / incorrectly predicted test examples. We are interested in the probability of P [ = 0, = ] when objects are evenly divided into training and test samples in half.
Since the probabilities are equal for each partition, we can assume without reducing generality that the first objects were included in the training sample, and the last objects form the test sample.
Let of FCAML hypotheses be generated using a coupling Markov chain from a training sample for Boolean algebra. If the trajectories are chosen long enough, then the distribution of hypotheses will be (almost) uniform and independent. Uniformity follows from the property of fast mixing to a uniform stationary distribution, and independence follows from the independence of the Markov chain trajectories generating the FCAML hypotheses.
Denote generated hypotheses as = {ℎ1, ℎ2, . . . , ℎ } and form a table like | 1 +1 . . . . . . . . . (1+ ) (1+ )+1 2 ℎ1
ℎ2 0 . . . 0 0 . . . 0 1 . . . 0 1 . . . 0 0 . . . 0 0 . . . 1 . . . . . . . .
. . . . . . . 0 . . . . . . . .
. . . .
ℎ 0 . . . 1 0 . . . 0 0 . . . 1
Here 1 corresponds to inclusion of given hypothesis into a given example, i.e. the hypothesis predicts the example correctly (positively).
To reach the empirical risk = 0 each of the first rows must contain at least one 1.
Due to the uniform distribution and independence of hypotheses, the corresponding cells form an independent Bernoulli series with a probability of success 12 .
Lemma 4. If hypotheses number ≥ (1+ ) log2 for some > 0 then lim→∞ P [ = 0] = 1. Proof.
1 ≥ →∞ lim (︀ 1 − 2− )︀ = lim →∞ ︂[ ︀( 1 − 2− )︀ 2 ]︂ · 2−
= →∞ = lim [︀ − 1]︀ · 2− ≥ →∞ lim − 1/ = 1.
To achieve = fraction of erroneous predictions of test examples it needs to select · rows of the lower half (there are (︀ ·)︀ ways to do this) containing zeroes only, the rest rows can contains ones somewhere. Table above corresponds to the situation with choice of rows +1, . . . , (1+ )· .
The task is to estimate P = (︀ ·)︀ · ︀( 1
− 2− )︀ (2− ) · (︀ 2− )︀ · when → ∞.
Lemma 5 (Stirling’s formula). ! ≈
√2 for → ∞.
Lemma 6 (Entropy inequality). − · ln − (1 − ) · ln(1 − ) ≤ ln 2.
Theorem 1. lim→∞ P ≤ ∞ and ≥ (1 + ) log2 . exp {︀ − (1 + ) · · · ln + ln 2 · − Proof. The second factor of P = (︀ ·)︀ · ︀( 1 − 2− )︀ (2− ) · (︀ 2− )︀ · does not exceed 1. Stirling’s formula and Entropy inequality imply
P ≤
√2 · · · · (1− )· · · · (1− )· · (︀ 2− )︀ · · √2 · · √︀2 (1 − ) · · · · · · (1 − )(1− )· · (1− )· ≤
2− · · (1+ )· log2 = ≤ √︀2 (1 − ) · · · · ln · (1− )· · ln(1− ) − · (1+ )· · ln · · (− · ln − (1− )· ln(1− )) √︀2 (1 − ) · √
= ≤ − · (1+ )· · ln · ln 2· √︀2 (1 − ) · √
Main theorem of the paper provides a small upper bound on a probability of overfitting in FCA-based Machine Learning in the simplest case of Boolean algebra without counter-examples. It states that the probability of overfitting in fixed fraction of test examples tends to zero faster than exponent when the number of attributes goes to infinity. Interesting alternative for our research is the work of T.P. Makhalova and S.O. Kuznetsov [6], where classifiers form a lattice.
The author would like to thank his colleagues at Dorodnicyn Computing Center of Russian Academy of Science and especially his PhD student L.A. Yakimova for collaboration and helpful discussions.
The author is grateful to anonymous reviewers for improving the style of presentation. [4] Kuznetsov S.O. Complexity of Learning in Concept Lattices from Positive and Negative
Conference on Formal Concept Analysis: Springer LNAI, Vol. 2961. – 2004. – pp. 287–312 [6] Makhalova T.P. and Kuznetsov S.O. On Overfitting of Classifiers Making a Lattice. Proc. 14th International Conference on Formal Concept Analysis: Springer LNAI, Vol. 10308. – 2017. – pp. 184–197 [7] Vapnik V.N. Statistical Learning Theory, Wiley-Interscience, 1998 [8] Vinogradov D.V. A Markov Chain Approach to Random Generation of Formal Concepts.
Proc. of Workshop Formal Concept Analysis Meets Information Retrieval (FCAIR 2013): CEUR Workshop Proceedings, Vol. 977. – 2013. – p. 127–133 [9] Vinogradov D.V. Accidental Formal Concepts in the Presence of Counterexamples. Proc. of Workshop on Formal Concept Analysis for Knowledge Discovery (FCA4KD 2017): CEUR Workshop Proceedings, Vol. 1921. – 2017. – p. 104–112 [10] Vinogradov D.V. FCA-based Approach to Machine Learning. Proc. of Workshop on Formal Concept Analysis for Artificial Intelligence (FCA4AI 2019): CEUR Workshop Proceedings , Vol. 2529. – 2019. – p. 57–64 [11] Vorontsov K.V. and Ivahnenko A. Tight Combinatorial Generalization Bounds for Threshold Conjunction Rules. Proc. of 4th International Conference on Pattern Recognition and Machine Intelligence. – 2011. – p. 66–73