Implications

This blog is a continuation of the FCA blog. I actually mused over this in Summer 2004, but wanted to recap for myself and share some source code.

The article I read back then was Endliche Hüllensysteme und ihre Implikationenbasen (Finite hull systems and their implications). I summarize this article here, since I didn't find an english version online.

In short, a context is constructed, where rows are subsets of attributes ''A'', i.e. elements of the power set, and columns are implications between subsets and the incidence is given by respects (⊢ ), H = {2^A, 2^A × 2^A, ⊢} . This context is simplified, by applying the Armstrong rules, to form a non-redundant, complete, reduced context, named B . Then an algorithm is presented, which takes the intents of some context and recursively constructs the respected implications using B and afterwards uses the 3rd Armstrong rule to find an easy set of implications, i.e. not necessarily minimal, but easier than the Duquenne-Guiges-Basis.

Definitions

• U → V : an implication is a pair (U, V) , U ⊆ M and V ⊆ M U is premiss and V conclusion.
• W⊢U → V : A set W respects (U, V) , if U⊈W or V ⊆ W . One also says: (U, V) holds for W .
• If V ⊆ U the implication is called trivial.

An intelligent system repeatedly gets sets of elements (attributes) as input (objects) and associates these elements. Implications are the result of many such sets.

• A concept lattice C respects (U, V) , iff U’ ⊆ V’ .
• (U, V) holds in C , iff V ⊆ U’’

Implications can be composed to give new implications. The minimal set of implications that produce all other implications is called an implication basis.

A minimal implication basis is given by the Duquenne-Guiges-Basis (stem basis), which consists of all pseudo-contents:

Let X ↦ X’’ be a closure operation, then P is pseudo-closed if

• P  ≠  P’’
• Q ⊂ P  ⇒  Q’’ ⊆ P

There cannot be a implication basis with less implications, than the Duquenne-Guiges-Basis, but one can choose implications that are easier (with low ∑|U||V| , U → V with V ≠ ∅ and U∩V = ∅ ).

Construction of H

H = {2^A, 2^A × 2^A, ⊢} is a context and the according concepts C(H) = {(O, A)} are subsets (= objects of H ) that respect a set of implications (= attributes H ).

The basic implications ( ⇒  ) respected by this context C (⊨ ) are given by the Armstrong Axioms:

∅  ⇒ {U → U}  (A1)       {U → V}  ⇒ {UW → U}  (A2)       {U → V, VW → Z}  ⇒ {UW → Z}  (A3)      

Some derived ones are ( ≡  is  ⇒  in both directions):

{U → V}  ≡ {U → UV}  (A4)       {U → V, U → W}  ≡ {U → VW}  (A5)       {U → V}  ≡ {W → V|U ⊆ W}  (A6)       {U → V, UVW → Z}  ≡ {U → V, UW → Z}  (A7)      

Note

Notation: UV means U∪V and Ui means U∪{i}

H can be constructed inductively. The sequence of the attributes is of no importance when constructing the power set.

Note

In [1] {⋆} named the new attribute in the step n and {⋆⋆} in the step n + 1 . Here I name them i and j and ⋆ becomes a wild card meaning whatever element in a previous step.

In the following i means a new attribute. Because of A4:{X → Y}  ≡ {X → XY} only implications with sets U ⊆ V are included, therefore Ui → V is not there.

• H_o = 1 , because ∅⊢∅ → ∅ .
• L_o = 0 , because ∅⊬∅ → {i} .

H_n + 1 =  ⊢   U → V   U → Vi   Ui → Vi         X H_n L_n 1         Xi H_n H_n H_n        

• (2, ⋆) implications hold with Xi = X∪{i} , because X respects U → V at location (1, 1) .
• The L in (1, 2) is discussed below
• The 1 in (1, 3) is because Ui⊈X makes the implication hold.

L_n + 1 is part of H_n + 2 , which adds another element j .

L_n + 1 =  ⊢   U → Vy   U → Vij   Ui → Vij         X L_n L_n 1         Xi L_n L_n L_n        

• The columns of L_n + 1 are those of H_n + 1 augmented by j at the conlusion side.
• The rows are the same as in H_n + 1 .
• As i , so is j not in X and we can distribute L to all but (1, 3) , where Ui⊈X makes it hold.

Construction of B

Because of A5 ({U → V, U → W}  ≡ {U → VW} ) we can reduce H to implications of the shape U → U∪{i} , abbreviated U → i (thus Ui → j means U∪{i} → U∪{i, j} .

In the following ⋆ names the extra element on the right of a previous recursion step, whichever that was.

B is in analogy to H horizontally subdivided by three event:

• no new element i , ie some other ⋆ of a previous step is on the right.
• with i on right side
• with i on both sides: the extra element on the right is any ⋆ of a previous step.

B₁ =  0   1         A₁ =  0 1     0 0    

B_n + 1 =  ⊢   U → ⋆   U → i   Ui → ⋆         X B_n A_n 1         Xi B_n 1 B_n        

• (1, 3) : Ui⊈X , so it holds.
• (2, 2) : Xi⊢U → i . If U⊈X , so is Ui⊈Xi , ie it holds; same for  ⊆  .
• (1, 1) ⇒ (2, 1), (2, 3) : X⊢U → ⋆ ≡ Xi⊢U → ⋆ ≡ Xi⊢Ui → ⋆
• (1, 2) : see below

A_n + 1 is part of B_n + 2 , which adds another element j on the right side. The new element of step n (i ) can be on the left side or not, hence the horizontal partitioning.

A_n + 1 =  ⊢   U → j   Ui → j       X A_n 1       Xi A_n A_n      

The implications (columns) in B are reduced. The rows are reduced apart from the last line, which is always full.

Application to Find Implications for a Context

H , L , B , A ( = X ) are used to find the implication basis and the intents.

We recursively construct the composed context K○X defined by X(K(g)) , g is object of K .

Every attribute of K(g) = g’ gets a position. This position says whether the attribute is there or not there - column after the if in the following formulas. So every g’ is coded by a binary number. This is λ:2^M↦{0, 1}ⁿ in [1].

The first two lines for (g_[n])^H_n show the according implication coding. This is κ:(U↦V)↦{0, 1, 2}ⁿ with 2 = i ∈ U , 1 = i ∈ V and U∩V = ∅ in [1]. So every binary attribute coding becomes a ternary implication coding.

For n = 1

(g_[1])^H₁ =  1, 0, 1   1, 1, 1    (g_[1])^L₁ =  0, 0, 1  if g₁ = 0     0, 0, 0  if g₁ = 1

For n > 1

(g_[n])^H_n =  0   1   2       U → V   U → Vi   Ui → Vi       (g_{[n − 1]})^{H_n − 1}   (g_{[n − 1]})^{L_n − 1}   1^3n − 1  if g_n = 0         (g_{[n − 1]})^{H_n − 1}   (g_{[n − 1]})^{H_n − 1}   (g_{[n − 1]})^{H_n − 1}  if g_n = 1

(g_[n])^L_n =  (g_{[n − 1]})^{L_n − 1}   (g_{[n − 1]})^{L_n − 1}   1^3n − 1  if g_n = 0         (g_{[n − 1]})^{L_n − 1}   (g_{[n − 1]})^{L_n − 1}   (g_{[n − 1]})^{L_n − 1}  if g_n = 1

The recursive construct with coding 1 = x ∈ V < 2 = x ∈ U shows that the column position, interpreted as ternary number, codes the implication. If the incidence at the column position is 1, then g’ respects this implication: {g’}^H_n is indicator function for the respected implications.

The coding will also place a larger V before a smaller one when going from right to left. This way one can filter out implications with already encountered same left side.

The U∪V will be closed. If there is no implication for a left side, this is a closed intent, too.

Note

Python Implementation

Python's arbitrary precission integers is used for coding. An attribute's position is the bit position of the integer. Every object is thus an integer. A context is a list of integers.

In here higher bits are more left; in the [1] they are more right; the horizontal order is inverted.

def UV_H(Hg,gw):
    """
    Return implications UV respecting g.
    gw = g width
    Hg = H(g), g is the binary coding of the attribute set
    UV = all non-trivial (!V⊂U) implications U->V with UuV closed; in ternary coding (1=V,2=U)
    K = all closed sets
    """
    lefts = set()
    K = set()
    UV = set()
    p = Hwidth(gw)
    pp = 2**p
    while p:
        pp = pp>>1
        p = p-1
        if Hg&pp:
            y = istr(p,3,gw)
            yy = y.replace('1','0')
            is02 = y.find('1') == -1 #y∈{0,2}^n
            if is02:
                K.add(y)
            elif yy not in lefts:
                lefts.add(yy)
                UV.add(y)
    return (UV,K)

Now we do the analogue procedure with the B context. In B the implications are of the shape U → U∪{x} , so we need to specify U and the one binary position of x. This implication coding can be derived from the column position recursively (see below).

For n = 1 :

(g_[1])^B₁ =  0   1    (g_[1])^A₁ =  0 1  if g₁ = 0       0 0  if g₁ = 1

For n > 1 :

(g_[n])^B_n =  U → ⋆   U → i   Ui → ⋆       (g_{[n − 1]})^{B_n − 1}   (g_{[n − 1]})^{A_n − 1}   1^{(n − 1)2n − 2}    if g_n = 0         (g_{[n − 1]})^{B_n − 1}   1^2n − 1   (g_{[n − 1]})^{B_n − 1}    if g_n = 1

(g_[n])^A_n =  U → j   Ui → j     (g_{[n − 1]})^{A_n − 1}   1^2n − 1    if g_n = 0       (g_{[n − 1]})^{A_n − 1}   (g_{[n − 1]})^{A_n − 1}    if g_n = 1

The following Python returns the implication coding for a column t .

Awidth = lambda n: 2**n
Bwidth = lambda n:n*2**(n-1)
def A012(t,i):
    if i<0:
        return ""
    nA = Awidth(i)
    if t < nA:
        return "0"+A012(t,i-1)
    else:
        return "2"+A012(t-nA,i-1)
def B012(t,i):
    """
    Constructs ternary implication coding (0=not there, 2=U, 1=V)
    t is B column position
    i = |M|-1 to 0
    """
    if not i:
        return "1"
    nA = Awidth(i)
    nB = Bwidth(i)
    nBB = nB + nA
    if t < nB:
        return "0"+B012(t,i-1)
    elif t < nBB:
        return "1"+A012(t-nB,i-1)
    else:
        return "2"+B012(t-nBB,i-1)

The positions of the 1's in the B row for a given g yield the implications. Here the python source code:

def UV_B(Bg,gw):
    """
    returns the implications UV based on B
    Bg = B(g), g∈2^M
    gw = |M|, M is the set of all attributes
    """
    UV = []
    p = Bwidth(gw)
    pp = 2**p
    while p:
        pp = pp>>1
        p = p-1
        if Bg&pp:
            uv = B012(p,gw-1)
            UV.append(uv)
    return UV

To get the implications that hold in a context K , i.e. for intent 1 and intent 2 and ..., we &-combine (multiply) the B rows for intent 1 and intent 2 and ...

Note

See pyfca for the full and possibly updated source code.

Constructing a Basis

The implications that result via B can be pruned by

• first finding the minimal antichain
• then applying the 3rd Armstrong

The minimal Antichain

The 1-position (j) in the ternary coding is called significant component. L_j are all implications with the same significant component.

The implications U → j constructed in this way via K○B are ordered lexicographically based on 0 ≤ 1 ≤ 2 .

They are also ordered with the product order, which is a partial order, and it depicts the containment hierarchy of the U side. We want to find the smallest U of every chain in L_j . This minL_j is an antichain and so is L = ∪minL_j .

The UV_B above changed to return this minimal antichain:

def v_Us_B(Bg,gw):
    """
    returns the implications {v:Us} based on B
    v is the significant component
    Bg = B(g), g∈2^M
    gw = |M|, M is the set of all attributes
    """
    v_Us = defaultdict(list)
    p = Bwidth(gw)
    pp = 2**p
    while p:
        pp = pp>>1
        p = p-1
        if Bg&pp:
            uv = B012(p,gw-1)
            #lets find minima regarding product order
            #{v:[Umin1,Umin2,...]}
            v = uv.find('1')#v=significant
            u = uv[:v]+'0'+uv[v+1:]
            u = int(u.replace('2','1'),2)
            Umin_s = self[gw-v-1]#bit position from right
            it = [i for i,U in enumerate(Umin_s) if U&u==u]
            for i in reversed(it):
                del Umin_s[i]
            else:
                Umin_s.append(u)
    return v_Us

The Basis

In the construction of the minimal antichain the 2nd Armstrong rule has been used, but there is still redundancy due to the 3rd Armstrong rule {U → V, VW → Z}  ⇒ {UW → Z} .

A component-wise operation is created to represent the 3rd Armstrong rule for the 0,1,2-coding

• U○VW ⇒ UW : 0○0 = 0 and 2○0 = 0○2 = 2○2 = 2 This is a binary or operation.
• V○VW ⇒ UW , no V in UW : 1○2 = 2○1 = 0 .
• Z ⇒ Z , V∩Z = ∅ : 1○0 = 0○1 = 1
• L_i○L_j = {x○y|x ∈ L_i, y ∈ L_j, i ≠ j}

Note that it is required that, with X → x and Y → y , x ∈ Y xor y ∈ X to make this the 3rd Armstrong rule.

This is implemented in python as

#u1,u2 code the attribute sets via the bits of an integer
#v1,v2 are bit indices
#u1->v1, vv1 = 2**v1
#u2->v2, vv2 = 2**v2
if vv2&u1 and not vv1&u2:
    return (v1,[(u1|u2)&~vv2])
elif vv1&u2 and not vv2&u1:
    return (v2,[(u1|u2)&~vv1])

The properties of ○ are:

• x○y = y○x
• x ≠ x○y ≠ y
• If x ≤ _ny , then x○y ≤ _ny ,  ≤ _n is the product order
• If x○y ∈ L_i , then x ∈ L_i or y ∈ L_i (note: L_i not minL_i )
• If there exits x○y = z ∈ L , then there exist x̃, ỹ ∈ L with x̃○ỹ = z

The objective is to find Y ⊆ L , of which the repeated application of ○ produces L : Y = L .

Y is defined as

• Y² = Y○Y
• Y^n + 1 = Yⁿ∪{z ∈ L|z = x○y, x ∈ Yⁿ, y ∈ Y∪Yⁿ} This means that of Yⁿ○(Yⁿ∪Y) only elements in L are added at each step. But the algorithm below can cope with Yⁿ getting bigger than L.
• ○Y = ∪_n ≥ 2Yⁿ
• Y = Y∪○Y

One starts with Y₀ = L (L○L) , i.e. all those elements of L that are not results of an application of the 3rd Armstrong rule. As long as Y_n ≠ L , we add z ∈ L Y_n to Y_n . Y_n∪{z} cannot generate elements of Y₀ , but it can generate elements of Z_n = Y_n Y₀ . Therefore we do Y_n + 1 = Y₀∪(Z_n (○(Y_n∪z)))∪z , i.e. we also remove elements, but only those that can be generated together with z , hence Y_n ⊂ Y_n + 1 .

Note

The formula Y_n + 1 = Y₀∪(Z_n (○(Y_n∪z)))∪{z} in [1] lets you think, that only the current z can generate itself. But actually other z ∈ Z_n could generate themselves. Z_n (○(Y_n∪z)) could remove elements other than z that are needed for the generation of elements in Y_n , thus making Y_n¬ ⊂ Y_n + 1 . Still the latter is postulated in [1]. There is a comment, though, that states, one should use disjunct union. This is interpreted as: don't remove elements of Z_n , where the current z is not involved in the generation.

Here ist the python code for that:

def basis_minomega(self):
    L = self
    Y = L - (L*L)
    while True:
        Ybar = Y + ~Y
        take = L - Ybar
        if not len(take):
            return Y
        else:
            z = next(take.flatten())
            Yzgen = Y**z #generate with z involved
            Y = (Y - Yzgen) + z

Note

This algorithm can generate a basis that is smaller regarding ω(UV) = ∑|U||V| , but not necessarily in count compared to the Duquenne-Guiges-Basis.

[1]	(1, 2, 3, 4, 5, 6) Endliche Hüllensysteme und ihre Implikationenbasen by Roman König.