In this paper we present a new technique for the analysis of data tables by means of Formal Independence Analysis (FIA). This is an analogue of Formal Concept Analysis for the study of independence relations in data, instead of hierarchical relations. A FIA of a context produces, when possible, its block diagonalization by detecting pairs of sets of objects and attributes that are not mutually incident, or tomoi, that partition the context. In this paper we combine this technique with the exploration of contexts with entries in a semifield to find independent sets in contingency matrices. Specifically, we apply it to a number of confusion matrices issued from cognitive experiments to find evidences for the hypothesis of perceptual channels.
In this paper we derive a technique for data analysis from the recently introduced
Formal Independence Analysis, (FIA) [
Independent Perceptual Channels. Miller and Nicely [
Paper published in Dmitry I. Ignatov, Lhouari Nourine (Eds.): CLA 2018, pp. 117{128, Department of Computer Science, Palacky University Olomouc, 2018. Copying permitted only for private and academic purposes.
Specifically, consider the confusion matrix Cij describing the results of an iterated classification experiment “when presented with stimulus i, and the (human) classifier answered response j.” If the hypothesis of independent channels were true, we would expect this confusion matrix to be reordered by specific permutations of its rows and columns into a block diagonal form, more specifically, a squared block diagonal form. In this block-diagonal form, each block would describe the confusions within a perceptual channel, while confusions outside the channel would not be observed.
Reading Guide. In this paper we will use the recently developed FIA
(Section 2.1) to obtain a block-diagonal form for confusion matrices, that leads to the
independent virtual channel hypothesis of Miller and Nicely. This result actually
stems from the consideration of a disjoint union of subcontexts decomposition
technique already available from [
FIA was defined to complement the analysis of the information in formal contexts
carried out by FCA, originally in terms of the hierarchical relation of formal
concepts in terms of the inclusion between extents and intents. Instead, FIA
targets the relation of independence between sets of objects and attributes [
Theorem 1 (Basic theorem of formal independence analysis). 1. The context analysis phase: Given a formal context (G, M, I), (a) The operators ·∼ : 2G → 2M and ·∼ : 2M → 2G α∼ = M r β∼ = G r [ I(g, ·) = {m ∈ M | g I\ m for all g ∈ α} g∈α [ I(·, m) = {g ∈ G | g I\ m for all m ∈ β} m∈β (1) (2) form a right-Galois connection (·∼, ·∼) : (2G, ⊆) (*(2M , ⊆) whose formal tomoi are the pairs (α, β) such that α∼ = β and α = β∼. 3 From the Greek “tomos-tomoi”, division. (b) The set of formal tomoi A(G, M, I) with the relation
(α1, β1) ≤ (α2, β2) iff α1 ⊇ α2 iff β1 ⊆ β2 is a complete lattice, which is called the tomoi lattice of (G, M, I) and denoted A(G, M, I), where infima and suprema are given by: ∼
∼! ^ (αt, βt) = t∈T [ αt, t∈T \ βt t∈T _ (αt, βt) = t∈T \ αt ∼ , [ βt t∈T ∼ t∈T ! (c) The mappings γ : G → A(G, M, I) and μ : M → A(G, M, I) g 7→ γ(g) = ({g}∼∼, {g}∼)
m 7→ μ(m) = ({m}∼, {m}∼∼) are such that γ(G) is infimum-dense in A(G, M, I) , μ(M ) is supremumdense in A(G, M, I). 2. The context synthesis phase: Given a complete lattice L = hL, ≤i (a) L is isomorphic to4 A(G, M, I) if and only if there are mappings γ : G → L and μ : M → L such that – γ(G) is infimum-dense in L , μ(M ) is supremum-dense in L, and – g I m is equivalent to γ(g) 6≥ μ(m) for all g ∈ G and all m ∈ M . (b) In particular, L =∼ A(L, L, 6≥) and, if L is finite, L =∼ A(M (L), J (L), 6≥) where M (L) and J (L) are the sets of meet- and join-irreducibles, respectively, of L.
It is already known that the lattices of formal tomoi and concepts are deeply
related [
A(G, M, I) ∼= B(M, G, Icd) 2.2
To set this scenario in a Formal Concept Analysis setting, recall from [2, Definition 30] that the disjoint sum of two contexts K1 = (G1, M1, I1) and K2 = (G2, M2, I2), with disjoint object and attribute sets is the context K1 ∪ K2 = (G1 ∪ G2, M1 ∪ M2, I1 ∪ I2), and that the concept lattice of the total context is the horizontal sum of the two concept lattices, that is, a union of the two lattices which only overlap in the top and bottom elements
K = K1 ∪ K2 ⇐⇒
B(K1 ∪ K2) = B(K1) ∪ B(K2). 4 Read can be built as.
This can be straightforwardly generalized to a finite number n of lattices, n n n K = [i=1 Ki ⇐⇒
B [ i=1 Ki = [ i=1
B(Ki). ! (3) This is what we call in this paper an (explicit) block diagonal form for the context, which results in a concept lattice of adjoined sublattices.
For this latter generalization, notice that each extent of K, except for the extent G = ∪iGi, is entirely contained in one of the sets Gi, and concept-lattice dually for intents. So it makes sense to say that two non-extreme concepts are orthogonal is they belong to different adjoined sublattices 5.
The relationship between tomoi lattices and block decompositions is provided by the following proposition.
Proposition 2. If A(G, M, I) ∼= 2n then the context (G, M, I) has an explicit block diagonal form.
Proof (Sketch). By Theorem 1 (item 2.b) the context (G, M, I) can be transformed into another one whose object-concepts are the meet-irreducible elements and whose attribute-concepts are the join-irreducible elements and, hence, because of the isomorphism with 2n, they are the co-atoms and the atoms, respectively. Moreover, they are complementary pairs of one object-tomos and one attribute-tomos.
As consequence, it is possible to reorganize the tabular expression of (G, M, I) in such a way that we obtain a block diagonal form. tu 3 3.1
The purpose of proving the existence of independent channels for different percepts can be achieved by reducing a confusion matrix to a block diagonal form. But, confusion matrices are not binary incidences and may not be subject to a simple process of block diagonalization. Instead, we may look for an approximate block-diagonal block, that retains the main structure of the confusions.
We can motivate this approximation in the following way:
– A perfect classifier would obtain a diagonal matrix of counts. This has been
proven in terms of information-theoretic arguments in [
– Using structural analysis from an adequately transformed matrix M = f (CA)
we could use the paradigm of Landscapes-of-Knowledge (LoK) [
In the following section, we check the feasibility of this scheme on the Miller and Nicely data. 3.2
Data Description. In this paper we will use the data from the Miller and Nicely study to show examples of phenomena and test the proposed data analysis procedures. These are the confusion data of a consonant perception task, and we will refer to it as the M&N data. Specifically they are six different confusion matrices of 16 entries for different Signal-to-Noise Ratios (SNR) in dB of {−18, −12, −6, 0, 6, 12} obtained in a (human) speech recognition task for the consonants listed in Table 1. The stimuli where balanced, but the responses may be unbalanced due to non-symmetrical confusion effects.
Data Preprocessing. Due to the symmetry inherent in the confusion task, since the category of the responses was the same as that of the stimuli, we extracted the symmetric component of each confusion matrix. This was done by obtaining from each matrix C its symmetric component CS = (C + Ct)/2. The antisymmetric component CA = (C − Ct)/2 can then be interpreted as a residue. For the M&N confusion matrix at −6dB these two components can be seen in Fig. 1.
The data were preprocessed to obtain both the Pointwise Mutual Information (MI) and the Weighted Pointwise Mutual information (WPMI) as shown in Fig. 2. Although prior work suggested that WPMI lends itself to more clear analyses, for the purpose of finding independent blocks in the matrix, we found— on using both types of data preprocessing—MI to retain more details about confusions that define the blocks, e.g. between elements that share (unknown) features motivating the confusion, for instance the voiceless fricatives /s/ vs. /R /.
Data Analysis. We carried out min-plus exploratory analysis in the MItransformed confusion matrix above by thresholding for each ϕ in increasing order and generated a sequence of K = 105 (binary) formal contexts K(ϕk) = (G, M, I(ϕk)), k ∈ [1, . . . K].
For each of these contexts, we calculated the number of formal tomoi for each thresholded I(ϕ) by actually working out the formal concepts of the contrary context K(ϕ)cd = (M, G, I\t). We do not explore at ϕ = −∞ which entails a trivial full-incidence and a count of one tomoi.
The graph of these counts in base-2 logarithm, shown in Fig. 3.a, allows us to define three regions:
(a) Tomoi count of I(ϕ) vs. ϕ(dB) (b) I(ϕ) at ϕ = −1.299010 (c) I(ϕ) at ϕ = 1.539160 – An initial segment where the threshold is too lax and we see essentially few blocks and a number of “noise” tomoi, where our assumption, viz. that there are virtual channels, does not hold.
In the example being analyzed, this is the range (−5.2, 1.53), to the left of the leftmost vertical line in Fig. 3.a . To ascertain the shapes of the thresholded we present an instance for where ϕ ≈ −1.23 and |K(ϕ)| = 30 focused on by the leftmost circle. In the heatmap of Fig. 3.b we can see and inkling of three different blocks, but since they are not complete, a number of “noisy” tomoi appear, making the tomoi lattice drift away from 23. Figure 4.a shows this non-boolean tomoi lattice whose incidence is that of Fig. 3.b – A middle segment where we start seeing many blocks, and consequently the number of tomoi |A(G, M, I(ϕ))| falls exactly into one of the powers of 2, where our assumption holds.
In the example, this is ϕ ∈ [1.53, 2.07] between the vertical lines in Fig. 3.a comprising the ramp where the cardinalities range from 29 to 214 tomoi. This is the case, for instance, of ϕ ≈ −1.53, |K(ϕ)| = 29, signaled as the rightmost red circle. We can see the 9-block incidence in Fig. 3.c, while Fig. 4.b shows the boolean lattice K(ϕ) ∼= 29. For reference, the (average) mutual information for this matrix, M I−6dB = 1.80 falls within this range, and would generate the tomoi lattice isomorphic to 210. – A final segment where the threshold is too stringent and we no longer see a block diagonal form.
This is the least interesting zone for us. In the example it appears as a descending slope in the range ϕ ∈ (2.07, 3.61) of Fig. 3.a.
We checked whether this behavior was analogous for all confusion matrices by analyzing the rest of the matrices at different SNR. The following are the main trends of analysis: – We could only obtain boolean tomoi lattices considering all stimuli for those confusion matrices with SNR of {18, 12, 6, 0, −6}. The matrices at SNR ∈ {−12, −18} were too noisy and some elements in the diagonal were less stable than elements off the diagonal, hence they disappeared on early exploration. – In all of the instances where in some range of MI values the exploration procedure obtained boolean tomoi lattices, the average MI for the whole matrix, that is in the standard definition of mutual information, actually belonged in the range where the hypothesis held. Most of the times, this MI was close to the value for values of ϕ that obtained the boolean tomoi lattice of highest cardinality. – The highest SNR in the confusion matrix being analyzed, the higher number of blocks in I(ϕ). This is congruent with the supposition that high SNR situations allow us to distinguish individual phones better and it is therefore more difficult to obtain evidence of the perceptual channels through confusions.
Extracting Perceptual Channels. The tomoi provide the basis for obtaining the perceptual channels on top of boolean tomoi lattices, since for every objecttomoi, a meet-irreducible, its complement is an attribute tomoi, hence a joinirreducible. By the properties of complementary tomoi, the crossed extents and intents, define the blocks in the block diagonalization.
To see this, consider Table 2 of object-tomoi extents and their complementary
tomoi intents—the attribute tomoi—to be used to build the block-diagonal form
of (3). We see how, modulo a permutation, they constitute a refinement of the
perceptual channels that Miller and Nicely proposed [
In fact, FIA seems to detect much finer perceptual channels than the original paper suggests, perhaps because of the granularity of the perceptual features used there (see below). In order to obtain a rougher partition of phones to support Miller and Nicely’s hypothesis, we have tried to analyze a balanced mixture of all the confusion matrices. But FIA has proven too strong for this unrealistic type of noise: the absence of confusions at 12dB dominates the behavior of the mixture, and the confusions from those behaviors at −18dB and −12dB are lost. Recall that it is precisely from the confusions where we obtain the evidence for the perceptual channels, so clearly a more nuanced approach to such mixture would be needed.
Although we have provided a data-induced procedure to obtain perceptual
channels from confusion matrices, this is only a first step in actually obtaining the
experimental channels. In particular, we have not investigated justifying those
channels in terms of perceptual characteristics. While Miller and Nicely
proposed an encoding of phones based on traditional categorical phonetic features,
modern studies favor the consideration of numeric features. In our opinion this
necessarily entails considering idempotent semimodule models of such spaces [
By no means is ours the only attempt at block-diagonalizing matrices over
idempotent semifields. In fact, such process is important for the calculation of the
Moore-Penrose inverse of a matrix over an idempotent semifield [
Yet a more general version of the problem is that of Cell Formation (CF)
in Group Technology, in the field of Manufacturing [
Finally, further work is necessary to ascertain the relationship of lattices of
formal tomoi to lattices of formal concepts, as well as to find out whether these
are the only information lenses available for formal contexts, or how to measure
the “quality” of the tomoi, in an effort similar to that shown for triadic analysis
and triclustering in [
We have introduced a new technique to analyze data tables based on the newly proposed Formal Independence Analysis. The purpose of the technique is to obtain tomoi,—pairs of sets of objects and attributes unrelated through an incident relation— and their complements in the lattice of tomoi, which define as many partitions of the sets of objects and attributes. These tomoi will then be used to define a block-diagonal form for the incidence.
We apply the technique to the diagonally-dominant incidences of confusion matrices. By a process of exploration we select special thresholds that obtain boolean tomoi lattices. In these lattices we obtain the meet-irreducible objecttomoi and their complements, the join-irreducible attribute-tomoi, that define diagonal blocks on the looked-for incidence.
These diagonal blocks can be interpreted as virtual channels that transmit different types of information in the spirit of some classical perceptual experiments, e.g. Miller and Nicely’s.
(a) Tomoi lattice for ϕ = −1.299010