On Concept Lattices as Information Channels

Abstract

This paper explores the idea that a concept lattice is an information channel between objects and attributes. For this purpose we study the behaviour of incidences in L-formal contexts where L is the range of an information-theoretic entropy function. Examples of such data abound in machine learning and data mining, e.g. confusion matrices of multi-class classi ers or document-term matrices. We use a wellmotivated information-theoretic heuristic, the maximization of mutual information, that in our conclusions provides a avour of feature selection providing and information-theory explanation of an established practice in Data Mining, Natural Language Processing and Information Retrieval applications, viz. stop-wording and frequency thresholding. We also introduce a post-clustering class identi cation in the presence of confusions and a avour of term selection for a multi-label document classi cation task.

-

Information Theory (IT) was born as a theory to improve the e ciency of (manmade) communication channels [ 1, 2 ], but it soon found wider application [ 3 ]. This paper is about using the model of a communication channel in IT to explore the formal contexts and concept lattices of Formal Concept Analysis as realisations of information channels between objects and attributes. Given the highly unspeci ed nature of both the latter abstractions such a model will bring new insights into a number of problems, but we are speci cally aiming at machine learning and data mining applications [ 4, 5 ].

The metaphor of a concept lattice as a communication channel between objects and attributes is already implicit in [ 6, 7 ]. In there, adjoint sublattices were already considered as subchannels in charge of transmitting individual acoustical features, and some e orts were done to model such features explicitly [ 7 ], ? FJVA and AP are supported by EU FP7 project LiMoSINe (contract 288024) for this work. CPM has been supported by the Spanish Government-Comision Interministerial de Ciencia y Tecnolog a project TEC2011-26807. but no conclusive results were achieved. The di culty rose from a thresholding parameter ' that controls the lattice-inducing technique and was originally xed by interactive exploration, a procedure hard to relate to the optimization of a utility or cost function, as required in modern machine learning.

In this paper we set this problem against the backdrop of direct mutual information maximization|using techniques and insights developed since [ 6, 7 ]|for matrices whose entries are frequency counts. These counts appear frequently in statistics, data mining and machine learning, for instance, in the form of document-term matrices in Information Retrieval [ 8 ], confusion matrices for classi ers in perceptual studies, data mining and machine learning [ 9 ], or simply two-mode contingency tables with count entries. Such matrices are called aggregable in [ 4 ], in the sense that any group of rows or columns can be aggregated together to form another matrix whose frequencies are obtained from the data of the elements in the groups. We will use this feature to easily build count and probability distributions whose mutual information can be maximized, following the heuristic motivated above, to improve classi cation tasks. Note that maximizing mutual information (over all possible joint distributions) is intimately related to the concept of channel capacity as de ned by Shannon [ 2 ].

For this purpose, in Sec. 2 we cast the problem of analysing the transfer of information through the two modes of contingency tables as that of analysing a particular type of formal context. First we present in Sec. 2.1 the model of the task to be solved, then we present aggregable data, as usually found in machine learning applications in Sec. 2.2, and then introduce the entropic encoding to make it amenable to FCA. As an application, in Sec. 3.1 we explore the particular problem of supervised clustering as that of transferring the labels from a set of input patterns to the labels of the output classes. Speci cally we address the problem of assigning labels to mixed clusters given the distribution of the input labels in them. We end with a discussion and a summary of contributions and conclusions. 2 2.1

Theory

Classi cation optimization by mutual information maximization

Consider the following, standard supervised classi cation setting: we have two domains X and Y , m instances of i.i.d. samples S = f(xi; yi)gim=1 X Y , and we want to learn a function h : X ! Y , the hypothesis, with certain \good" qualities, to estimate the class Y from X , the measurements of Y , or features.

A very productive model to solve this problem is to consider two probability spaces Y = hY; PY i and X = hX; PX i with Y PY and X PX , and suppose that there exists the product space hX Y; PXY i wherefrom the i.i.d. samples of S have been obtained. So our problem is solved by estimating the random variable Y^ = h(X), and a \good" estimation is that which obtains a low error probability on every possible pair P (Y^ 6= Y ) ! 0 .

Since working with probabilities might be di cult, we might prefer to use a (surrogate) loss function that quanti es the cost of this di erence L(y^ = h(x); y) and try to minimize the expectation of this loss, called the risk R(h) = E[L(h(x); y)] over a class of functions h 2 H, h = minh2H R(h) . Consequently, this process is called empirical risk minimization.

An alternate criterion is to maximize the mutual information between Y and Y^ [ 10 ]. This is clearly seen from Fano's inequality [ 11 ], serving as a lower bound, and the Hellman-Raviv upper bound [ 12 ],

HPY^

IPY Y^ HU ^

Y 1

P (Y^ 6= Y ) 1 2 HPY^ jY where UY^ is the uniform distribution on the support of Y^ , HPXX denotes the di erent entropies involved and IPY Y^ is the mutual information of the joint probability distribution. 2.2

Processing aggregable data

If the original rows and columns of contingency tables represent atomic events, their groupings represent complex events and this structure is compatible with the underlying sigma algebras that would transform the matrix into a joint distribution of probabilities, hence these data can be also interpreted as joint probabilities, when row- and column-normalized.

When insu cient data is available for counting, the estimation of empirical probabilities from this kind of data is problematic, and complex probability estimation schemes have to be used. Even if data galore were available, we still have to deal with the problem of rarely seen events and their di cult probability estimation. However, probabilities are, perhaps, the best data that we can plug onto data mining or machine learning techniques, be they for supervised or unsupervised tasks.

The weighted Pointwise Mutual Information. Recall the formula for

the mutual information between two random variables IPXY = EPXY [IXY (x; y)]

PXY (x;y) where IXY (x; y) = log PX (x) PY (y) is the pointwise mutual information, (PMI).

Remember that 1 IXY (x; y) < 1 with IXY (x; y) = 0 being the case where X and Y are independent. The negative values are caused by phenomena less represented in the joint data than in independent pairs as captured by the marginals. The extreme value IXY (x; y) = 1 is generated when the joint probability is negative even if the marginals are not. These are instances that capture \negative" association whence to maximize the expectation we might consider disposing of them.

On the other hand, on count data the PMI has an unexpected and unwanted e ect: it is very high for hapax legomena phenomena that are encountered only once in a tallying, and in general it has a high value for phenomena with low counts of whose statistical behaviour we are less certain.

However, we know that

IPXY =

X PXY (x; y) IXY (x; y) = x;y

X PXY (x; y) log x;y

PXY (x; y) PX (x) PY (y) and this is always a positive quantity, regardless of the individual values of IXY (x; y). This suggests calling weighted pointwise mutual information, (wPMI) the quantity wPMI(x; y) = PXY (x; y) log (1)

PXY (x; y) PX (x) PY (y) and using it as the subject of optimization or exploration to do so. Note that pairs of phenomena whose joint probability are close to independent, as judged by the pointwise information, will be given a very low value in the wP M I , and that the deleterious character of hapaxes on IPXY is lessened by the in uence of the joint probability. 2.3

Visualizing mutual information maximization

For a joint distribution PY Y^ (y; y^), [ 13 ] introduced a balance equation binding the mutual information between two variables IPY Y^ , the sum of their conditional entropies V IPY Y^ = HPY jY^ + HPY^ jY and the sum of their entropic distance between their distributions and uniformity

HPY Y^ = (HUY

HPY ) + (HUY^

HPY^ ), log(HUY ) + log(HUY^ ) =

HPY Y^ + 2 IPY Y^ + V IPY Y^ : By normalizing in the total entropy log(HUY ) + log(HUY^ ) we may obtain the equation of the 2-simplex that can be represented as a De Finetti diagram like that of Fig. 2.(a), as the point in the 2-simplex corresponding to coordinates

F (PY Y^ ) = [ HP0Y Y^ ; 2 IP0Y Y^ ; V IP0Y Y^ ] where the primes represent the normalization described above.

The axis of this representation were chosen so that the height of the 2simples|an equilateral triangle|is proportional to the mutual information between the variables so a maximization process is extremely easy to represent (as in Fig. 2): given a parameter ' whereby to maximize IPY Y^ (as a variable), draw the trace of the evaluation of the coordinates in the ET of the distributions that it generates, and choose the ' that produces the highest point in the triangle. This technique is used in Sec. 3.1, but other intuitions can be gained from this representation as described in [ 14 ]. 2.4

Exploring the space of joint distributions

Since the space of count distributions is so vast, we need a technique to explore it in a principled way. For that purpose we use K-Formal Concept Analysis (KFCA). This is a technique to explore L-valued contexts where L is a complete idempotent semi eld using a free parameter called the threshold of existence [ 15, 13 ].

We proceed in a similar manner to Fuzzy FCA: For L-context hY; Y^; Ri, con^ sider two spaces LY and LY , representing, respectively, L-valued sets of objects and attributes. Pairs of such sets of objects and attributes that ful l certain polars equation have been proven to de ne dually-ordered lattices of closed L-sets in the manner of FCA 3.

Since the actual lattices of object sets and attributes are so vast, KFCA uses a simpli ed representation for them: for the singleton sets in each of the spaces y, for y 2 Y and y^, for y^ 2 'Y^ , we use the L-polars to generate their object- Y' (y) and attribute-concept Y^ (y^), respectively, and obtain a structural '-context K' = hY; Y^; R'i, where yR'y^ () Y' (y) Y'^ (y^) 4.

In this particular case we consider the min-plus idempotent semi eld and the L-context hY; Y^; wP M Ii where wPMI is the weighted Pointwise Mutual Information relation between atomic events in the sigma lattices of Y and Y^ of Sec. 2.2, whence the degree or threshold of existence is a certain amount of entropy required for concepts to surpass for them to be considered.

The following step amounts to an entropy conformation of the joint distribution, that is, a redistribution of the probability masses in the joint distribution to obtain certain entropic properties. Speci cally, we use the (binary) '-formal context to lter out certain counts in the contingency table to obtain a conformal contingency table NY'Y^ (y; y^) = NY Y^ (y; y^) K', where represents here the Hadamard (pointwise) product. For each conformal NY'Y^ (y; y^) we will obtain a certain point F (') in the ET to be represented as described in Sec. 2.3. 3

Application

We next present two envisaged applications of the technique of MI Maximization. 3.1

Cluster identi cation

Confusion matrices are special contingency tables whose two modes refer to the same underlying set of labels[ 4 ]. We now put forward a procedure to maximize the information transmitted from a set of \ground truth" patterns acting as objects with respect to \perceived patterns" which act as attributes. As noted in the introduction, this is just one of the possible points of view about this problem.

Consider the following scenario, there is a clustering task for which extrinsic evaluation is possible, that is, there is a gold standard partitioning of the input data. One way to evaluate the clustering solution is to obtain a confusion 3 Refer to [ 13 ] for an in-depth discussion of the mathematics of idempotent semi elds and the di erent kinds of Galois connections that they generate. 4 And a structural '-lattice B'(K') as its concept lattice, but this is not important in the present application matrix out of this gold standard, in the following way: If the number of classes is known|a realistic assumption in the presence of a gold standard|then the MI optimization procedure can be used to obtain the assignments between the classes in the gold standard and the clusters of the procedure, resulting in cluster identi cation.

For the purpose of testing the procedure, we used the segmented numeral data from [ 16 ]. This is a task of human visual confusions between numbers as displayed by seven-segment LED displays, as shown in Fig. 1.(a). The entry in the count matrix NCK (c; k) = nck counts the number times that an instance of class c was confused with class k . Figure 1.(b) shows a heatmap presentation of the original confusion matrix and column-reshu ed variants. Note that the confusion matrix is diagonally-dominant, that is nii > Pj;j6=i nij and likewise for column i .

(a) (b)

To test the MI optimization procedure, we randomly permuted the confusion matrix columns: the objective was to recover the inverse of this random permutation from the MI optimization process so that the original order could be restored. This amounts to an assignment between classes and induced clusters, and we claim that it can be done by means of the mutual information maximization procedure sketched above.

For that purpose, we estimated PCK (c; k) using the empirical estimate P^CK (c; k)

NCK (c; k) n where n is the number of instances to be clustered n = Pck NCK (c; k) , and then we obtained its empirical PMI

I^CK (c; k) = log P^CK (c; k) and its weighted PMI

wP M ICK (c; k) = P^CK (c; k) I^CK (c; k) :

Next, we used the procedure of Sec. 2.4 to explore the empirical wPMI and select the threshold value which maximizes the MI. Figure 2.(a) shows the trajectory of the di erent conformed confusion matrices as ' ranges in [0; 1) on the ET: we clearly see how for this balanced task dataset the exploration results in a monotonous increase in MI in the thresholding range until a value that produces the maximum MI, at wP M I = 0:1366 . The discrete set of points stems from the limited range of counts in the data.

We chose this value as threshold and obtained the binary matrix which is the assignment from classes to clusters and vice-versa shown in Fig. 2.(b). Note that in this particular instance, the ' -concept lattice is just a diamond lattice re ecting the perfect identi cation of classes and clusters. In general, with contingency tables where modes have di erent cardinalities, this will not be the case. 3.2

Entropy conformation for count matrices

The case where the contingency matrix is squared and diagonally dominant, as in the previous example, is too speci c: we need to show that for a generic, rectangular count contingency matrix, entropy maximization is feasible and meaningful.

The rst investigation should be on how to carry the maximization process. For that purpose, we use a modi ed version of the Reuters-21578 5 that has already been stop-listed and stemmed. This is a multi-label classi cation dataset [ 17 ] describing each document as a bag-of-terms and some categorizations labels, the latter unused in our present discussion.

We considered the document-term matrix for training, a count distribution with D = 7 770 documents and T = 5 180, terms. Its non-conformed entropy coordinates are F (NDT ) = [0:1070; 0:3584; 0:5346] as shown in the deep blue circle to the left of Fig. 3. We carried out a joint-mutual information maximization process by exploring at the same time a max-plus threshold|the count has to be bigger thant the threshold to be considered|and a min-plus threshold|the count has to be less than the threshold. The rationale for this is a well-tested hypothesis in the bag-of-term model: very common terms (high frequency) do not select well for documents, while very scarce terms (low frequency) are too speci c and biased to denote the general \aboutness" of a document. Both should be ltered out of the document-term matrix. 5 http://www.daviddlewis.com/resources/testcollections/reuters21578/ readme.txt. Visited 24/06/2014. Fig. 2: Trajectory of the evolution of MI transmission for the segmented numeral data as the exploration threshold is raised in the wPMI matrix (a), and maximal MI cluster assignment matrix at wPMI = 1:366 bits (b) for column-shu ed Segmented Numerals. The resulting concept lattice is just a diamond lattice identifying classes and clusters and not shown.

Instead of count-based individual term ltering we carry a joint term-document pair selection process: for a document-matrix, we calculate its overall weighted PMI matrix, and only those pairs (d; t) whose wPMI lies in between a lower and an upper ' thresholds are considered important for later processing. For each such pairs, we created an indicator matrix I(d; t) that is 1 i wM I(d; t) ', and we used the Kronecker multiplication to lter out non-conforming pairs from the nal entropy calculation,

M^ IP0DT =

X wP M IDT (d; t) I(d; t) d;t

We can see how M^ IP0DT reaches a maximum over two values and then decreases again, going even below the original mutual information value. We read two di erent facts in this illustration: that the grid used is e ective in obtaining approximations to and ' for MI maximization, and that not every possible pair of values is a good solution for the process.

All in all, this procedure shows that MI maximization is feasible by tracking its in the ET. We do not present any results in this paper as to the e ectiveness of the process for further processing tasks, which should be evaluated on the extrinsic measures on the Reuters multi-labelling task. 4

Discussion

We now discuss the applications selected in a wider context. Although less pervasive than its unsupervised version, the basic task of supervised clustering has application, for instance, in tree-induction for supervised classi cation [ 5, 18 ] or unsupervised clustering evaluation using a gold-set [ 19 ]. Cluster identi cation in Sec. 3.1 is a sometimes-fussy sub-procedure in clustering which our proposal solves elegantly.

The feasibility study on mutual information conformation of Sec. 3.2 is a necessary step for further processing|binary or multi-labelling classi cation| but as of this paper unevaluated. Further work should concentrate on leveraging the boost in mutual information to lower the classi cation error, as suggested in the theoretical sections.

Besides, the use of two simultaneous, thresholds on di erent algebras makes it di cult to justify the procedure on FCA terms: this does not conform to the de nition of any lattice-inducing polars that we know of, so this feature should be looked into critically. Despite this fact, the procedure of conformation \makes sense", at least for this textual classi cation task.

Note that the concept of \information channel" that we have developed in this paper is not what Communication Theory usually considers. In there, \input symbols" enter the channel and come out as \output symbols", hence input has a sort of ontological primacy over output symbols in that the former cause the latter. If there is anything particular about FCA as an epistemological theory is that it does not prejudge the ontological primacy of objects over attributes or vice versa. Perhaps the better notion is that a formal concept is an information cochannel between objects and attributes, in the sense that the information \ ows" both from objects to attributes and vice versa, as per the true symmetric nature of mutual information: receiving information about one of the modes decreases the uncertainty of the other.

The previous paragraph notwithstanding, we will often nd ourselves in application scenarios in which one of the modes will be primary with respect to the other, in which case the analogies with communication models will be more evident. This is one of the cases that we explore in this paper, and that rst pointed at in [ 6, 7 ].

Contingency tables are an instance of aggregable data tables [4, x0.3.4]. It seems clear that not just counts, but any non-negative entry aggregable table can be treated with the tools here presented, e.g. concentrations of solutes. In that case, the neat interpretation related to MI maximization will not be available, but analogue ones can be found.

A tangential approach to the de nition of entropies in (non-Boolean) lattices has been taken by [ 20, 21, 22, 23, 24 ]. These works approach the de nition of measures, and in particular entropy measures, in general lattices instead of nite sigma algebras (that is, Boolean lattices). [ 22 ] and [ 24 ] speci cally address the issue of de ning them in concept lattices, but the rest provide other heuristic foundations for the de nition of such measures which surely must do without some of the more familiar properties of the Shannon (probability-based) entropy. 5

Conclusions and further work

We have presented an incipient model of L-formal contexts of aggregable data and their related concept lattices as information channels. Using KFCA as the exploration technique and the Entropy Triangle as the representation and visualization technique we can follow the maximization procedure on confusion matrices in general, and in confusion matrices for cluster identi cation in particular.

We present both the basic theory and two proof-of-concept applications in this respect: a rst one cluster identi cation, fully interpretable in the framework of concept lattices, and another, entropy conformation for rectangular matrices more di cultly embeddable in this framework.

Future applications will extend the analysis of count contingency tables, like document-term matrices, where our entropy-conformation can be likened to feature selection techniques.

Bibliography

References

[1] Shannon , C.E. : A mathematical theory of Communication . The Bell System Technical Journal XXVII ( 1948 ) 379 { 423

[2] Shannon , C. , Weaver , W.: A mathematical model of communication . The University of Illinois Press ( 1949 )

[3] Brillouin , L. : Science and Information Theory. Second Edition. Courier Dover Publications ( 1962 )

[4] Mirkin , B. : Mathematical Classi cation and Clustering . Volume 11 of Nonconvex Optimization and Its Applications . Kluwer Academic Publishers ( 1996 )

[5] Mirkin , B. : Core Concepts in Data Analysis: Summarization, Correlation and Visualization . Summarization, Correlation and Visualization. Springer, London ( 2011 )

[6] Pelaez-Moreno , C. , Garc a-Moral, A.I. , Valverde-Albacete , F.J.: Analyzing phonetic confusions using Formal Concept Analysis . Journal of the Acoustical Society of America 128 ( 2010 ) 1377 { 1390

[7] Pelaez-Moreno , C. , Valverde-Albacete , F.J.: Detecting features from confusion matrices using generalized formal concept analysis . In Corchado, E., Grana-Romay , M. , Savio , A.M., eds.: Hybrid Arti cial Intelligence Systems. 5th International Conference, HAIS 2010 , San Sebastian, Spain, June 23-25, 2010 . Proceedings, Part II . Volume 6077 of LNAI., Springer ( 2010 ) 375 { 382

[8] Manning , C.D. , Raghavan , P. , Schutze, H.: Introduction to Information Retrieval. Cambridge University Press ( 2008 )

[9] Japkowicz , N. , Shah , M. : Evaluating Learning Algorithms: A Classi cation Perspective . Cambridge University Press ( 2011 )

[10] Frenay , B. , Doquire , G. , Verleysen , M. : Theoretical and empirical study on the potential inadequacy of mutual information for feature selection in classi cation . NEUROCOMPUTING 112 ( 2013 ) 64 { 78

[11] M Fano , R. : Transmission of Information: A Statistical Theory of Communication . The MIT Press ( 1961 )

[12] Feder , M. , Merhav , N.: Relations between entropy and error probability . IEEE Transactions on Information Theory 40 ( 1994 ) 259 { 266

[13] Valverde-Albacete , F.J. , Pelaez-Moreno , C. : Two information-theoretic tools to assess the performance of multi-class classi ers . Pattern Recognition Letters 31 ( 2010 ) 1665 { 1671

[14] Valverde-Albacete , F.J. , Pelaez-Moreno , C. : 100 % classi cation accuracy considered harmful: the normalized information transfer factor explains the accuracy paradox . PLOS ONE ( 2014 )

[15] Valverde-Albacete , F.J. , Pelaez-Moreno , C. : Galois connections between semimodules and applications in data mining . In Kusnetzov, S., Schmidt , S., eds.: Formal Concept Analysis . Proceedings of the 5th International Conference on Formal Concept Analysis, ICFCA 2007 , Clermont-Ferrand, France . Volume 4390 of LNAI., Springer ( 2007 ) 181 { 196

[16] Keren , G. , Baggen , S. : Recognition models of alphanumeric characters . PERCEPT PSYCHOPHYS 29 ( 1981 ) 234 { 246

[17] Tsoumakas , G. , Katakis, I.: Multi-label classi cation: An overview . International Journal of Data Warehousing and . . . ( 2007 )

[18] Hall , M. , Frank , E. , Holmes , G. , Pfahringer , B. , Reutemann , P. , Witten , I.H. : The WEKA data mining software: An update . SIGKDD Explorations 11 ( 2009 )

[19] Meila , M. : Comparing clusterings|an information based distance . Journal of Multivariate Analysis 28 ( 2007 ) 875 { 893

[20] Knuth , K. : Valuations on Lattices and their Application to Information Theory . Fuzzy Systems , IEEE International Conference on ( 2006 ) 217 { 224

[21] Grabisch , M. : Belief functions on lattices . International Journal Of Intelligent Systems 24 ( 2009 ) 76 { 95

[22] Kwuida , L. , Schmidt , S.E. : Valuations and closure operators on nite lattices . Discrete Applied Mathematics 159 ( 2011 ) 990 { 1001

[23] Simovici , D. : Entropies on Bounded Lattices. Multiple-Valued Logic (ISMVL), 2011 41st IEEE International Symposium on ( 2011 ) 307 { 312

[24] Simovici , D.A. , Fomenky , P. , Kunz , W. : Polarities, axiallities and marketability of items . In: Proceedings of Data Warehousing and Knowledge Discovery - DaWaK . Volume 7448 of LNCS . Springer ( 2012 ) 243 { 252