The article demonstrates computational eficiency of the probabilistic approach to knowledge extraction using the FCA. In addition to the result previously proved by the author on suficiency of a polynomial number of hypotheses (concepts) about the causes of the target property under study, this paper will give a polynomial upper bound on the average running time of the algorithm for generating one concept. The proven result concerns a family of algorithms based on coupling Markov chains for arbitrary formal contexts formed from the positive part of training sets. To get a good estimate for the length of trajectory (before entering to some ergodic state) of such a chain, we had to enrich the representation of the training sample by adding negation for every original binary attribute.
small training context generates exponentially large number of concepts [7]. Another one is the appearance of so-called ’phantom’ concepts as accidental similarities between small number of training objects each of which belongs to a diferent concept with larger extent [ 8]. It can be argued that the appearance of such hypotheses corresponds to the over-fitting phenomenon. This statement was experimentally confirmed in the master thesis of L.A. Yakimova [9].
To overcome these limitations, the author [10] proposed to use a probabilistic approach. The idea is to generate a random sample of concepts by trajectories of Markov chain making random walks through the concept lattice. We named our approach the VKF method in honor of V.K. Finn and because of the abbreviation of the Russian term "Probabilistic Combinatorial Formal method" to indicate efective processing using probabilistic algorithms and FCA of various combinations of training objects for generating concepts.
Such algorithms are based on the "Close-by-One" operations , for which the part with respect to objects was proposed earlier by S.O. Kuznetsov [11] in the eponymous algorithm for exhaustive generation of all candidates for hypotheses, the number of which in some cases may be exponentially large. Using these operations, the author proposed to generate a polynomial-size random subset of concepts, each element of which corresponds to one trajectory of random walk across the corresponding lattice.
The author [12] has proved that it is suficient to generate · ln 2− ln random concepts in order to correctly predict all the -important test objects with the reliability of 1 − .
Therefore, the single obstacle for polynomial complexity of full scheme of the VKF-method is the absence of polynomial upper bound on the length of trajectories of Markov chain. The main result of this paper is polynomial upper bound on the average length of trajectories of the coupling Markov chain when the training context is dichotomized, i.e., expanded by additional binary attributes that correspond to negations of all original attributes. Such expansion is useful if the absence of an original attribute is allowed to be a part of cause for the target attribute. Previously, only special cases of formal contexts (for instance, Boolean algebra and linear order) were investigated. The new result concerns the general case of arbitrary lattice.
2.1. Basic definitions and facts of FCA Here we recall some basic definitions and facts from Formal Concept Analysis (FCA) [5].
A (formal) context is a triple (, , ) where and are finite sets and ⊆ × . The elements of and are called objects and attributes, respectively. As usual, we write instead of ⟨, ⟩ ∈ to denote that object has attribute .
For ⊆ and ⊆ , define
′ =
′ =
{ ∈ : ∀ ∈ ()},
{ ∈ : ∀ ∈ ()};
(
A concept of the context (, , ) is defined to be a pair (, ), where ⊆ , ⊆ , ′ = , and ′ = . The first component of the concept (, ) is called the extent of the concept, and the second component is called its intent. The set of all concepts of the context (, , ) is denoted by B(, , ).
Let (, , ) be a context. For concepts (, ) and (, ) in B(, , ) we write (, ) ≤ (, ), if ⊆ . The relation ≤ is a partial order on B(, , ).
A subset ⊆ is the extent of some concept if and only if ′′ = in which case the unique concept of which is the extent is (, ′). Similarly, a subset of is the intent of some concept if and only if ′′ = and then the unique concept with intent is (′, ). Proposition 1. Let (, , ) be a context. Then (B(, , ), ≤ ) is a lattice with join and meet given by ⋁︁ ( , ) ∈ ⋀︁ ( , ) ∈ = = (( ⋃︁ )′′, ⋂︁ ), ∈
∈ ( ⋂︁ , ( ⋃︁ )′′); ∈ ∈ Corollary 1. For context (, , ) the lattice (B(, , ), ≤ ) has ( ′, ) as the bottom element and (, ′) as the top element. In other words, for all (, ) ∈ B(, , ) the following inequalities hold:
( ′, ) ≤ (, ) ≤ (, ′).
For (, ) ∈ B(, , ), ∈ , and ∈ define
((, ), )
((, ), )
=
=
(, ) ∨ ({}′′, {}′),
(, ) ∧ ({}′, {}′′),
so according to (
The useful properties of introduced operations are summarized in the following Lemmas.
Lemma 1. Let (, , ) be a context, (, ) ∈ B(, , ), ∈ , and ∈ . Then
(
Data: context (, , ), external function ( , ) Result: random concept (, ) ∈ B(, , ) := ⊔ ; (, ) := ( ′, ); (, ) = (, ′); while (( ̸= ) ∨ ( ̸= )) do select random element ∈ ; (, ) := ((, ), ); (, ) := ((, ), ); end
The algorithm terminates when the upper and lower concepts coincide. The condition on remaining of ordering between two concepts (, ) ≤ (, ) at any intermediate step of the while loop of Algorithm 1 follows from Lemma 2.
The classical theorem of Markov chain Theory about transient (non-ergodic) states [13] implies almost surely termination of algorithms 1, i.e. finiteness of a trajectory until it enters to some ergodic state with probability 1.
Consider the moment () = min{ : ∈ , 0 = } of the first entering to , starting with an arbitrary transient state = (⟨, ⟩ < ⟨, ⟩) ∈/ .
Theorem 1. The moment () is Markov one for every transient state .
Proof. We need to prove P [() < ∞ | 0 = ] = 1.
Use decomposition { ∈ , 0 = } = ⋃︀≤ (), where
() = { ∈ , − 1 ∈/ , . . . , 1 ∈/ , 0 = }.
lim P [ ∈/ | 0 = ] → 0. →∞ (14)
P{ ∈ | 0 = } = ∑︁ P [() | 0 = ] → 1,
≤ if → ∞.
Since () = {() = } the -additivity leads to needed conclusion.
As direct corollary of the theorem 1 we conclude that the termination of algorithm 1 takes place almost surely (i.e. with probability 1).
The goal of current research is to obtain a polynomial upper bound on the average length of trajectories of the coupling Markov chain. In general, it is an open problem. In sequel, we’ll provide such bound, when the training context is expanded by additional binary attributes that correspond to negations of all existing attributes (dichotomic expansion).
Example 1. Dichotomic expansion of the left context is the right one.
× 1 2 3 4 where ⊤ = ⟨∅, {1, ¬1, 2, ¬2, }⟩, = ⟨{ }, { }′⟩, = ⟨{ }′, { }⟩, ¬ = ⟨{¬ }′, {¬ }⟩, and ⊥ = ⟨{1, 2, 3, 4}, ∅⟩.
The coupled Markov chain starts with state (⊥ ≤ ⊤ ). A trajectory of the random walk depends on random choices from ⊔ +.
Consider an example of such trajectory. Assume that 1 is selected at the 1st step, then the chain goes to state (⊥ ≤ 1). The choice of 2 at the 2nd step leads to (⊥ ≤ 1). If the chain selects ¬1 at the 3rd step, then the state becomes (¬1 ≤ ⊤ ). The choice of 4 at the 4th step leads to (¬1 ≤ 4). After selection of 3 at the 5th step the trajectory goes to ergodic state (¬1 ≤ ¬ 1), and algorithm 1 stops.
In [14] the author developed a useful tool to estimate the average length of trajectories of coupling Markov chain through recurrence relations.
for every ∈/ .
E [()] = 1 + ∑︁ E [ ()] · P [1 = |0 = ] = 1 + ∑︁ E [ ()] · P [1 = |0 = ] .
Here we sequentially use identity (15), the Markov property for moment () (theorem 1) and the Law of Total Probability.
This easily results in an upper bound of the order ( · ln ) on the average length of trajectories of algorithm 1 for -dimensional Boolean algebra case.
A more striking result from [14] concerns the average trajectory length of the algorithm 1 for linear orders. Here the upper bound of 4 on the average length does not depend on the number of elements of the linear order.
Example 2. Apply lemma 3 to the lattice from example 1.
This lattice allows us to define a distance between ordered candidates (i.e. components of a state). State 0 = (⊥ ≤ ⊤ ) has distance 3. States 1 = (⊥ ≤ 1), . . . , 4 = (⊥ ≤ 4), 5 = (1 ≤ ⊤ ), 6 = (2 ≤ ⊤ ), 7 = (¬2 ≤ ⊤ ), 8 = (¬1 ≤ ⊤ ) have distance 2. States with distance 1 are divided into 2 groups (external and internal ones). External states are 9 = (⊥ ≤ 1), 10 = (⊥ ≤ 2), 11 = (⊥ ≤ ¬ 2), 12 = (⊥ ≤ ¬ 1), and 13 = (1 ≤ ⊤ ), . . . , 16 = (4 ≤ ⊤ ). Internal states correspond to edges 17 = (1 ≤ 1), . . . , 24 = (¬1 ≤ 4). The rest states are ergodic ones (with distance 0).
Denote the length of trajectory starting from state 0 by 3. The states with distance 2 determine a random walk of length 2. External states initiate trajectories of length 1 , and internal ones start trajectories of length 1 .
Lemma 3 leads to E3 = 1 + E2 and system of equations ⎧E2 = 1 + 38 E2 + 82 E1 + 28 E1 ⎪ ⎨
E1 = 1 + 18 E2 + 82 E1 + 28 E1 ⎪⎩E1 = 1 + 28 E1 + 82 E1 (16)
The solution E2 = 27828 = 4 of the system (16) leads to the value E3 = 1 + 4 = 5 of the average length of trajectory of algorithm 1 for the context considered in example 1.
Now we extend component-wise the operations to states of coupling Markov chain ((⟨, ⟩ ≤ ⟨ , ⟩) , ) = ((⟨, ⟩, ) ≤ (⟨, ⟩, )) and
((⟨, ⟩ ≤ ⟨ , ⟩) , ) = ((⟨, ⟩, ) ≤ (⟨, ⟩, )) .
Then we define a (partial) order between states = (⟨, ⟩ ≤ ⟨ , ⟩) and = (⟨ , ⟩ ≤ ⟨ , ⟩) of coupling Markov chain as following ⩽ ⇔ ⟨, ⟩ ≤ ⟨ , ⟩ ≤ ⟨ , ⟩ ≤ ⟨ , ⟩. (17)
Lemma 4. For any ordered pair of states ⩽ , any ∈ , and any ∈ ( , ) ⩽ (, ) and ( , ) ⩽ (, ) hold.
We denote the number of training objects by = || and the number of attributes by = | |.
Lemma 5. E () ≤ E() for any ordered pair of transient states ⩽ of coupling Markov chain.
P ︀[ 1 = ′ , 1 = ′ | 0 = , 0 = ]︀ = ⎪0, ⎪ ⎪ ⎪ ⎪ ⎩ ⎪⎪⎧ + , = |{ ∈ : ′ = ( , ), ′ = (, )}|+ ⎪ ⎪ ⎪ = ⎨ +|{ ∈ : ′ = ( , ), ′ = (, )}| ¬∃ ∈ [︁′ = ( , ), ′ = (, )]︁ & .
&¬∃ ∈ [︁′ = ( , ), ′ = (, )]︁ Lemma 4 implies P [1 ⩽ 1 | 0 ⩽ 0] = 1.
Since ⟨, ⟩ = ⟨, ⟩ for ⟨, ⟩ ≤ ⟨ , ⟩ ≤ ⟨ , ⟩ ≤ ⟨ , ⟩ implies ⟨, ⟩ = ⟨ , ⟩ = ⟨ , ⟩ = ⟨, ⟩, then by definitions it follows that P [ = ∈ | 0 = ⩽ 0 = ] ≥ P [ ∈ | 0 = ⩽ 0 = ] . (18)
Recall that for an integer-valued random variable , the equality E = ∑︀∞=0 P [ > ] is fulfilled. Now ∈/ ⇔ () > and ∈/ ⇔ () > .
P [ () > | 0 = , 0 = ] ≤ P [() > | 0 = , 0 = ] , and the summation over leads to the required result.
Usually 2 ≪ ⊆ × + by the rule: common to all training objects.
In the following we’ll assume ′ = ∅. This is easily achieved by eliminating all the attributes
Let’s dichotomize the context, i.e., enrich the set of attributes by introducing an attribute for the negation ¬ of every binary attributes ∈ . This construction often has a useful meaning: we want the absence of a attribute to be a new attribute, i.e., we propose dichotomic scaling of the context (according to [5]).
The enriched set of attributes will be denoted by +, and we denote its power by 2 = | +|. = ||, which we will assume in the future. Enrich the training context to ¬ ⇔ ¬( ).
For = { = (⟨, ⟩ < ⟨, ⟩) : ∃ ∈ + [ ∈ ]} = { = (⟨, ⟩ < ⟨, ⟩) : ∀ ∈ + [ ∈/ ]}. (19) (20) It is clear that the state 0 = (⊥ < ⊤) ∈ . By lemma 5 for any ∈ , E () ≤ By the definition of the set and the lemma 5 for any ∈ we have E () ≤ E(), where = (⟨{}′, {}′′⟩ < ⊤) ∈ for any ∈ with = ⟨, ⟩.
Let’s introduce an integer-valued random variable taking the value on the event of steps of the algorithm 1 by states from ∈ until we get = (⊥ = ⊥). { = (⊥ = ⊥), − 1 ∈/ , . . . , 1 ∈/ , 0 = 0}, which determines the minimum number ∞ =1 E = ∑︁ P [ ≥ ] ≤ ( + 2) · ︂( ln(2) +
1 1 for context ⊆ × + with 2 = | +| ≤ = ||. {1 ≤ < ( + 2) · ln(2)} and Proof. We divide the summands into disjoint subsets of 0 ⊔ ⨆︀∞ =1 , where 0 = = {( + 2) · (ln(2) + − 1) ≤ < ( + 2) · (ln(2) + )}.
It is clear that ∑︀(+2)· ln(2)− 1 =1
P [ ≥ ] ≤ ( + 2) · ln(2).
In order for the event ≥ to occur, it is necessary that at least one attribute (out of 2) is selected, so that no example in the series of length is selected in which this attribute is not present. Therefore, by Boole’s inequality
P [ > ] ≤ 2 · ︂( 1
1 ︂) . (+2)· (ln(2)+)− 1
∑︁ =(+2)· (ln()+− 1) 1
P [ ≥ ] ≤ ( + 2) · ∑︁ − +1 = ∞ =1 ≤ ( + 2) · ln 2 · − (ln(2)+− 1) = ( + 2) · − +1.
≤ ≤
( ) = { = ∈ , − 1 ∈/ , . . . , 1 ∈/ , 0 = 0}. (21) union ⨆︀
∈ ,( ) by ,.
We denote event {+ ∈ , +− 1 ∈/ , . . . , +1 ∈/ } ∩ ( ) by ,( ), and the
{+ ∈ , +− 1 ∈/ , . . . , 0 = 0} = = ⨆︁ ({+ ∈ , +− 1 ∈/ , . . . , +1 ∈/ } ∩ ( )) ⊔
⊔ {+ = (⊥ = ⊥), +− 1 ∈/ , . . . , 1 ∈/ , 0 = 0}.
E0() = ∑︁ · P [ ∈ , − 1 ∈/ , . . . , 1 ∈/ | 0 = 0] . (22) It is clear that E0() =
E0′() + E, where 0′() is restriction of 0() on = || the upper bound on the average length of trajectories of algorithm 1 is Theorem 2. For the dichotomized (enriched) training context ⊆ × + with 2 = | +| ≤ E0 ≤ ( + 2)(2 + (2 + 1) + 42 + 2) 2(2 + + 2) +
Then Markov property implies (⟨{}′, {}′′⟩ < ⊤), and similarly for ¬ .
∑︀
1 =1 +2 ( + ¬ ), where = () for = E0′() = ∑︁ ∑︁( + ) · P, =
∞ = ∑︁ =1 ∞ + ∑︁ =1 · · ∞
∞ ∑︁ P [ ∈ , − 1 ∈/ , . . . , 1 ∈/ | 0 = ] · ∑︁ P [( )] + ∑︁ P [( )] · ∑︁ P [ ∈ , − 1 ∈/ , . . . , 1 ∈/ | 0 = ] ≤ ∞ =1 ≤ ∑︁ E () · P [1 = | 0 = 0] + ∑︁ ∑︁ · P [( )] ≤
∞ ∈ =1 ≤ E + where the last term is the average of geometrically distributed random variable of the time before first selection of some attribute.
E ≤ 1 + ∑︁ =1
1
E ≤ + 2 which leads to the required result.
E0() ≤ E +
+ , VKF method about finding a polynomial upper bound on the average length of trajectories of a coupling Markov chain - the average time of computation by the probabilistic algorithm 1, which generates concepts of the training context for knowledge extraction. Only special cases, such as Boolean algebra and linear order, were investigated earlier. The important step is based on the dichotomic scaling of a training context.
Combining the new result with the previously obtained polynomial lower bound on the suficient number of concepts, we obtain a fully polynomial scheme for extracting knowledge using a binary similarity operation implemented in the VKF-method.
Experimental studies of author’s PhD student L.A. Yakimova demonstrate that probabilistic approach to FCA-based knowledge extraction (in combination with "Counterexample Forbidding Condition") is practically not subject to the phenomenon of over-fitting (through generation of ’phantom’ candidates), unlike the classical JSM-method.
The author thanks his colleagues from Dorodnicyn Computing Center of Federal Research Center "Computer Science and Control" of Russian Academy of Sciences for support and useful discussions. The author is grateful to his PhD student Lyudmila A. Yakimova for long-term cooperation that stimulated the described research. [10] D. V. Vinogradov, VKF-method of hypotheses generation, in: Proceedings of the 3rd International Conference on Analysis of Images, Social Networks and Texts (AIST’2014), volume 436 of Communications in Computer and Information Science, 2014, pp. 237–248. doi:10.1007/978-3-319-12580-0_25. [11] S. O. Kuznetsov, A fast algorithm for computing all intersections of objects from an arbitrary semilattice, Nauch.-Tekh. Inf. Ser.2 27 (1993) 17–20. [12] D. V. Vinogradov, Algebraic machine learning: Emphasis on eficiency, Automation and
Remote Control 83 (2022) 831–846. doi:10.1134/S0005117922060029. [13] J. G. Kemeny, J. L. Snell, Finite Markov Chains, Undergraduate Texts in Mathematics, 1 ed., Springer, New York, 1976. Originally published by Van Nostrand Publishing Company, 1960. [14] D. V. Vinogradov, Markov chains, law of total probability, and recurrence relations, Autom.
Doc. Math. Linguist. 57 (2023) 68–72. doi:10.3103/S0005105523010090.