In this paper we present an approach for estimating the error rate of bitset representation of object descriptions in FCA-based knowledge discovery. Errors of this kind lead to overfitting phenomenon. The key technique used in our approach is based on the Mo¨bius function on finite partial ordered sets, which was introduced by G.-C. Rota.
‘JSM-method of automatic hypotheses generation’ is an approach to Knowledge
Discovery that was proposed by V.K. Finn (see, [
Later JSM-method has been extended to arbitrary (lower semi-)lattices of
object descrptions, where similarity operation on object descriptions (wedge
operation) satisfies usual idempotent, commutative and associative laws. In [
The author [
The analysis of such situations reveals that FCET can reject some phantom hypotheses if the data contains errors in values of some attributes. This paper considers a possibility to estimate error rates in attribute values taking into account the lattice structures on them. Without loss of generality, we restrict ourselves to the case of single target attribute. The general case is reduced to this one by assuming the independence of errors rates of values of different attributes. 1 1.1
A (finite) context is a triple (G, M, I) where G and M are finite 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 ∈ I to denote that object g has attribute m.
For A ⊆ G and B ⊆ M , define
A0 = {m ∈ M |∀g ∈ A(gIm)}, B0 = {g ∈ G|∀m ∈ B(gIm)}; (1) (2) so A0 is the set of attributes common to all the objects in A and B0 is the set of objects possesing all the attributes in B. The maps (·)0 : A 7→ A0 and (·)0 : B 7→ B0 are called derivation operators (polars) of the context (G, M, I).
A concept of the context (G, M, I) is defined to be a pair (A, B), where A ⊆ G, B ⊆ M , A0 = B, and B0 = A. The first 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 L(G, M, I).
Let (G, M, I) be a context. For concepts (A1, B1) and (A2, B2) in L(G, M, I) we write (A1, B1) ≤ (A2, B2), if B1 ⊆ B2. The relation ≤ is a partial order on L(G, M, I).
Element x ∈ L of finite lattice hL, ∧, ∨i is called ∨-irreducible, if x 6= ∅ and for all y, z ∈ L y < x and z < x imply y ∨ z < x. Element x ∈ L of finite lattice hL, ∧, ∨i is called ∧-irreducible, if x 6= ∅ and for all y, z ∈ L x < y and x < z imply x < y ∧ z.
If subsets of attributes {gi}0 ⊂ M and {gj }0 ⊂ M are intents of objects gi ∈ G and gj ∈ G, respectively, with corresponding bitsets, then the derivation operator on a pair of objects corresponds to bit-wise multiplication, since {gi, gj }0 = {gi}0 ∩ {gj }0. Moreover, polars correspond to iteration of bit-wise multiplication (in arbitrary order) of corresponding bitset-represented objects and attributes, respectively. The last remark is important, since bit-wise multiplication is a basic operation of modern CPU and GPGPU. In terms of JSM-method the binary operation ∩ : 2M × 2M → 2M is called ‘similarity operation’. This operation defines a low-semilattice on subsets of attributes.
Descriptions of objects can combine discrete and continuous attrtibutes. Here
we restrict ourselves to discrete case only, and we will consider the continuous
case in another paper. The set of objects’ descriptions must be a part of extended
set F of ‘fragments’ supplied with binary ‘similarity’ operation ∧ : F × F → F ,
which is idempotent x ∧ x = x, commutative x ∧ y = y ∧ x, and associative
x ∧ (y ∧ z) = (x ∧ y) ∧ z. Moreover, there is the minimal element ∅ satisfying
x ∧ ∅ = ∅ (so-called ‘trivial fragment’). In FCA this construction is realized by
means of pattern structures [
Theorem 1. [
In [
Data: set V of values of current attribute Result: matrix B with rows as bitset codes of values V := topological sort(V ); // topological sorting T := order matrix; // transitive closure of cover relation ∀i[Del[i] = f alse]; // deleted columns for (index = 2; index < n; + + index) do for (indx = 1; indx < index; + + indx) do for (ndx = 0; ndx < indx; + + ndx) do if (T [ ][V [index]] == T [ ][V [indx]]&T [ ][V [ndx]]) then
Del[V [index]] := true; end end end
end end end end for (index = 2; index < n; + + index) do for (indx = 1; indx < index; + + indx) do if ¬Del[indx] then ⇒ B[indx][index] := T [index][indx];
Algorithm 1: Encoder Algorithm
For instance, when we consider famous Mushroom Data Set [
c k 1. Topological sorting of elements of the semilattice. 2. In the context of order ≥ look for columns that coincide with bit-wise multiplication of previous ones (every such column corresponds to ∨-reducible element). 3. All found (∨-reducible) columns are removed. 4. Rows of reduced context form bitset representations of the corresponding values.
We sort the values as k < n < c < y < b in correspondence with the partial order on them. Then Theorem 1 gives a big context corresponding to ≥.
The column ‘c’ is equal to the product of columns ‘k’ and ‘n’ since c = k ∨ n. Hence it is reducible. The other ∨-reducible element of the lattice is ‘b’ (again column ‘b’ is a product of columns ‘n’ and ‘y’).
The rows of reduced context are the bitset representations of the corresponding colors of spore print.
The encoding of the whole description is a concatenation of bit-set presentation of values of its features in some fixed order. Since the bitset representations of different values of same feature have same length, the bit-wise multiplication of the whole representations reduces to the bit-wise multiplications of the corresponding parts, and the similarity between objects is given by the componentwise similarity of their intents. We begin with a demonstration of the phenomenon by JSM-method’s application to a school problem in geometry. The task is to learn sufficient conditions on a convex polygon to be circled and to predict this property for test examples. Hence there are two target classes: the positive one (with a possible circle around the figure) and the negative one.
The training sample contains regular triangle, rectangular triangle, square, isosceles trapezoid, and diamond (the last figure is negative, the rest contains positive training examples). The test sample contains isosceles triangle, rectangle, and deltoid. We consider the most general case of the corresponding polygon. Hence, for instance, isosceles trapezoid has bases of different sizes and differs from rectangle.
We represent each polygon by a subset of attributes from the following list: (a) the figure is a triangle; (b) the figure is a quadrangle; (c) the figure has a right angle; (d) the figure has a pair of equal length sides; (e) all sides of the figure have same length; (f) the figure has a pair of parallel sides; (g) the figure has a pair of equal angles; (h) all angles of the figure are equal. (i) the sum of the opposite angles of the quadrangle is equal to π.
Hence, the training context (G+, M = {a, b, c, d, e, f, g, h, i}, I) is training objects a b c d e f g h i regular triangle 1 0 0 1 1 0 1 1 0 rectangular triangle 1 0 1 0 0 0 0 0 0
square 0 1 1 1 1 1 1 1 1 isosceles trapezoid 0 1 0 1 0 1 1 0 1 This context generates the following concepts with extents of cardinality > 1 h{regular triangle, rectangular triangle}, {a}i,
h{regular triangle, square}, {d, e, g, h}i, h{regular triangle, square, isosceles trapezoid}, {d, g}i,
h{square, isosceles trapezoid}, {b, d, f, g, i}i.
The first concept h{a}0, {a}i corresponds to the well-known geometric theorem “Each triangle can be circumscribed by a circle”. The second one expresses the famous fact about regular polygons “Vertices of regular polygon lie on a circle”. This concept has the form h{e, h}0, {e, h}00i. The fourth concept represented as h{i}0, {i}00i corresponds to the well-known geometric theorem “Every quadrangle with the sum of opposite angles equal to π can be circumscribed by a circle”. The third concept is a ‘phantom’ because its extent contains two types of objects: a regular triangle with the first ‘real’ cause, and quadrangles with the sum of opposite angles equal to π (square and isosceles trapezoid). Its intent consists of ‘accidental common’ attributes. Luckily, the forbidden counter-example test (FCET) procedure rejects this concept because of the counter-example counter − example a b c d e f g h i
diamond 0 1 0 1 1 1 1 0 0
However, the situation is very subtle, since the 4th concept has two types of objects in its extent. However, it corresponds to the true geometric fact! We think that this concept is a ‘real cause’ as opposed to ‘phantom concept’ 3.
Test sample Gτ contains
test objects a b c d e f g h i isosceles triangle 1 0 0 1 0 0 1 0 0 rectangle 0 1 1 1 0 1 1 1 1
deltoid 0 1 0 1 0 0 1 0 0
JSM-method predicts the first test (isosceles triangle) positively through the 1st concept. The second test object (rectangle) is classified positively by applying the 4th concept. JSM-method might incorrectly predict the target property of the last test case if the 3rd hypothesis is not rejected. This is exactly the phenomenon of overfitting: the hypothesis is consistent with the training sample, but it leads to the incorrect classification of test examples.
A similar situation occurs in real data experiments with the use of
JSMmethod. For example, consdier an application of JSM-method to the study of
toxicity of substituted nitrobenzenes [
Concept (hypothetical cause of toxicity) 28 with extent consisting 2 elements (training examples 37 and 39) has the form shown in figure 2.
However, example 37 and other 6 training examples generate alternative hypothesis 3. Similarly, example 39 contains alternative concept 41 with 16 elements extent. There is a plausible assertion that hypothesis 28 is a ‘phantom’ because of an accidental coincidence fragment between two training examples each of which contains some different ‘real cause’ (example 37 has ’real cause’ 3, and example 39 contains ‘real cause’ 41).
This case was not unique. More than 10 percent of concepts without
counterexamples exhibit the same behavior. The aim of her study was to study
empirically the overfitting phenomenon, which was previously investigated theoretically
by the author in [
An attribute is called essential, if it appears in some ‘real cause’. Here ‘cause’ is a set of attributes. Assume for the sake of simplicity that two ‘real causes’ have no common attributes. Other attributes are called accompanying. Hence we partition set M of all attributes into three subsets: the first ‘real cause’, the second one, and accompanying attributes.
Term ‘real cause’ corresponds to a generator of intent {a} of 1st concept and {i} of 4th concept in our initial illustrative example. However in mathematical study below it means just a special subset of attributes other than the accompanying ones. Last attributes form building blocks for ‘phantom’ concepts. So ‘real’ in ‘real causes’ means nothing! It’s simply initially introduced term to distinct the group of essential attributes from accompanying ones.
Assume for the sake of simplicity that counter-examples do not contain any essential attribute. Now we introduce probabilistic model to simultaneously generate accompanying attributes for a pair of training examples and m counterexamples.
Denote the number of counter-examples by m, and the number of accompanying attributes by n. It is clear that the accompanying attributes of training objects and counterexamples form a (2 + m) × n binary matrix. It contains N = (2 + m) · n bits. Accompanying attributes are generated by Bernoulli series of N tests.
Bernoulli series of N tests is the probability distribution on {0, 1}N with P(x1 = δ1, . . . , xN = δN ) =
N Y pδj · (1 − p)1−δj , j=1 where 0 < p < 1. The number p > 0 is called success probability xj = 1 in test j.
Then we set all the attributes of first “real” cause to 1s, all attributes of the second “real” cause to 0s, and add accompanying attributes of first training example to obtain first training example itself. We generate the second training example by setting attributes of the first “real” causes to 0, and of the second one to 1. All counter-examples have 0 in positions corresponding to both “real” causes.
As result we obtain context 2 × |M | and list of m counter-examples. What is the probability to generate concept with 2 element extent without any counterexample from the list? Theorem 2. If number n of random attributes tends to infinity, the probability of success equals to p na , and there are m = b · √n counterexamples, then the probability of an accidental formal concept with 2 elements extent and without any counterexample is 1 − e−a − a · e−a · [1 − e−b·√a] at limit.
Note, that even smaller number 1 − e−a − a · e−a is positive, since it coincides with the probability that the Poisson variable Ya with mean a has value Ya > 1.
Recently Lyudmila A. Yakimova, a former master student of the Russian
State University for Humanities made experimental studies [
Another result of Yakimova’s study is a higher rate of ‘phantom’ concepts
than its estimate by the theorem. The reason is in the difference of frequency
of appearance of different attributes. Moreover, Yakimova’s experiments do not
detect overfitting phenomenon for VKF method of Machine Learning based on
FCA [
While checking the condition of forbidding counter-examples, the similarity of some training examples can be contained in description of a counter-example. JSM-method rejects such similarities, however some suspicious hypotheses may be missed if some values of attributes were entered erroneously. Can we estimate the rate of such errors?
Consider again Figure 1. Assume that an expert mistakenly replaces buff spore print color (b) by yellow one (y) for some counter-example. Then the similarity with a mushroom with chocolate spore print has common brown color (n) and can not be included into counter-example, so the procedure saves the hypothesis. If such similarity is phantom it leads to overfitting.
It is clear that value w ∈ V frequently replaces value v ∈ V when w ≤ v. The case of totally fatal mistake is ignored in this study. Denote the rate of such errors r(v|w). The problem is that there does not exist a way to discover v, we see only w as a value entered by an expert. To resolve this difficulty the M¨obius function from the incidence algebra is used. 2.2
In fundamental work [
Consider the set of real-valued functions of two variables on V with the property f (x, y) = 0, if x 6≤ y. It has the structure of an associative algebra over the real field if we define the product of such functions h = f · g as h(x, y) =
X z:x≤z≤y f (x, z) · g(z, y).
Then g(x) = X f (y).
y:x≤y f (u) = X μ(u, z)g(z). Addition and multiplication by constants are defined in a natural way. This structure is called incidence algebra of the given poset. This algebra has the identity element δ(x, y) = 1 if x = y and δ(x, y) = 0 otherwise, the Kronecker delta.
The zeta function ζ(x, y) is an element of incidence algebra such that ζ(x, y) = 1 if x ≤ y and ζ(x, y) = 0 otherwise. It has the inverse element μ(x, y), M¨obius function. The proof of the next statement is trivial check.
Proposition 1. Function defined by induction as μ(x, x) = 1 and μ(x, y) = −
X z:x≤z<y μ(x, z) is the inverse element to zeta function.
Proposition 2. Let f (x) be a real-valued function, defined on (locally) finite p.o.set V . Let an element v ∈ V exists with property that f (x) = 0 unless x ≤ v. Suppose that (3) (4) (5) (6) Proof. The function g(x) is well-defined since it equals to f (y), which is finite for a locally finite poset.
Substituting the right side of 5 into the right side of 6 and simplifying, we P y:x≤y≤v get
X μ(u, z)g(z) = X
X μ(u, z)f (y) = X
X μ(u, z)ζ(z, y)f (y). z:u≤z z:u≤z y:z≤y z:u≤z y Interchanging the order of summation, this becomes
X f (y) X μ(u, z)ζ(z, y) = y z:u≤z
X f (y)δ(u, y) = f (u).
y 2.3
We can collect statistics for mistakenly missed phantom hypotheses h (with help of negative examples from tests sample). Let hypothesis h be included into some negative example o (either from the training or test sample) when we omit the values of the attribute under study. Such inclusions are called pruned.
Let us fix value x of the attribute under study. We compute the fraction qw(x) of pruned inclusions of hypotheses with value x into counter-examples with value w with respect to total of all pruned inclusions of hypotheses with value x into negative examples (either from training or tests samples).
Then we have gw(x) =
X (ζ(w, v) − δ(w, v))r(v | w).
v:x≤v Here ζ(w, v)−δ(w, v) determines the condition w < v since there exists erroneous replacement invisible v by observable w < v. Summation holds because rates of different replaces are additive.
At first, we use Proposition 1 to compute M¨obius functions for every attribute values lattice.
Then we compute statistics gw(x) by application of pruning inclusions. Finally, we apply Proposition 2 to estimate errors rates as r(v|w) = X μ(v, z)qw(z).
z:v≤z (7) (8) The omitted factor ζ(w, v) − δ(w, v) means w < v.
We applied M¨obius functions on finite posets to estimate rates of mistakenly
replaces of attribute value by a smaller one that leads to overfitting in
JSMmethod. Experiments with Mushroom Dataset [
Author would like to thank his colleagues from Dorodnicyn Computing Center of Federal Research Center ”Computer Science and Control” of Russian Academy of Science and Russian State University for Humanities for long-term support and useful discussions. Author is grateful to anonymous reviewers, whose comments helped significantly improve the presentation.