Typicality in conceptual structures within the framework of formal concept analysis

Abstract

We continue our exploration of phenomena studied in the psychology of concepts. In particular, we examine typicality within the framework of formal concept analysis. We first briefly review some of the psychological theories of typicality and discuss various issues related to the goal of providing an operational account of typicality. We then propose a formalization of the notion of typicality, provide its experimental evaluation, and discuss ramifications of our findings and topics for future research.

Keywords

• typicality
• concepts
• formal concept analysis
• psychology of concepts

Motivation and our aims

Exploration of concepts and conceptual structures subsumes a number of diverse approaches. Among them, studies conducted in the psychology of concepts have a significant place due to the centrality of concepts in human cognition. The psychology of concepts provides a number of interesting views and theories on how human mind acquires and utilizes concepts and conceptual structures.

In pursuing their broad goals, psychologists identified and examined several interesting phenomena. These are of interest not only for the domain of psychology itself but, naturally, also for other theories concerned with concepts, in particular for various formal approaches to reasoning and information processing using concepts. Important among these phenomena is typicality: A sparrow is a typical bird, an ostrich is not; a trout is a typical fish, an eel or a flounder is not.

Our aim in this paper is to examine typicality within the framework of formal concept analysis (FCA). Doing so, we continue our previous effort to examine the basic level of concepts [ 2,3 ] using FCA. In particular, our goals are the following. We provide a formalization of a fundamental psychological account of typicality within FCA. For one, the formalization allows us to approach and examine typicality in more precise terms amenable to formal analysis. This is important particularly in view of the fact that in the psychology of concepts, theories of typicality are described rather informally. In addition, making a definition of typicality operational via formalization lets one see various subtleties and possible shortcomings of an informal, verbally described definition, as well as see possible relationships to alternative definitions and related notions.1 On the other hand, we believe that a proper extension of FCA and other information processing methods by notions coming from the psychology of concepts may enhance the potential of these methods. In particular, we demonstrate that typicality may improve our understanding of the internal structure of formal concepts.

Our paper is organized as follows. In section 2, we provide an account of typicality from the viewpoint of the psychology of concepts. Section 3 presents our formalization of typicality within FCA. In section 4, we provide examples and experiments involving the notion of typicality. Overall, our paper is meant to make first steps in studying typicality in the framework of FCA. Correspondingly, a prospect of future research is outlined in section 5. 2 2.1

Typicality in the psychology of concepts

Graded structure of concepts

Typicality emerged as a significant phenomenon in the psychology of concepts in the mid 1970s in connection with explorations of the internal structure of concepts (or categories, a term commonly used in that area). These studies, most importantly by Eleanor Rosch [ 12,13,14 ], revealed fundamental limitations of the so-called classical view of concepts. A detailed exposition of developments in the psychological theories of concepts is provided in [ 11 ]; see also [ 9 ].

According to the classical view, a concept is determined by a set of yes/no conditions (i.e. attributes) which are necessary and jointly sufficient, i.e. definitory: An object is covered by the concept (is a member of the category, in terms of the psychology of concepts) iff the object satisfies each of these conditions.2 The classical view does not account, at least not directly, for various phenomena related to what is referred to as a graded structure of concepts. Namely, according to this view, all members of a category have an equal status w.r.t. the category. On the other hand, people naturally regard some members of a category more typical than others. As research has shown, people are capable of assigning to objects their degrees of typicality for a given category in a consistent manner.

Another phenomenon, which had been examined in the early 1970s, that involves degrees and is not addressed by the classical view is membership in category itself. That is, an object may not just be a member or a non-member of a given category, but rather a member to a certain degree in the sense of fuzzy sets.3

Note in this connection that the literature on the psychology of concepts does not make it very clear to which of the following two possible views a particular 1 This aspect was a significant part of our work on basic level in [ 2,3 ]. 2 This view has a long tradition in philosophy and logic and also underlies the notion of a concept in formal concept analysis. 3 Note that Rosch’s studies of graded nature of categories were conducted independently and and in about the same time as Zadeh’s studies of fuzzy sets [ 16 ]. study of typicality subscribes; see. e.g. [ 11 ]. In the first view, membership in a category is bivalent (i.e. classical, yes/no) and typicality represents and additional structure of a category. In the second view, membership is graded and possibly even equivalent (or otherwise strongly correlated) to typicality. In our formalization below we assume the former view, i.e. that categories (concepts) are classical and that typicality represents an additional structure. Such view is adopted, e.g., in the design of experiments in the seminal paper [ 13 ].

Note also that typicality is regarded as highly significant from a cognitive point of view; see e.g. [ 1,11,13 ]. For one, people tend to agree on typicality ratings. Moreover, typicality is reported to predict performance in a variety of cognitive tasks including learning of a category, speed of deciding membership in categories, and production of category exemplars. Typical items are also useful in making inferences about categories and serve as so-called cognitive reference points. 2.2

Explanations of typicality

In their seminal paper [ 13 ], Rosch and Mervis put forward a hypothesis of what makes an object a typical in a category. This hypothesis was confirmed by a carefully designed experiments in [ 13 ], had later been examined by numerous other studies [ 11 ], and nowadays represents the main theoretical explanation of typicality. This explanation forms the basis of our approach to typicality within the framework of FCA. Rosch and Mervis [13, p. 575] describe their hypothesis as follows: . . . members of a category come to be viewed as prototypical of the category as a whole in proportion to the extent to which they bear a family resemblance to (have attributes that overlap those of) other members of the category. Conversely, items viewed as most prototypical of one category will be those with least family resemblance to or membership in other categories.

The first part referring to resemblance (similarity) to objects of the given concept (category) is intuitively compelling and relatively straightforward to formalize; it is this part that we use in our approach. The second part referring to resemblance to objects in other concepts is not so straightforward and brings some non-trivial problems, which are also reflected in the experiments in [ 13 ], and we hence do not consider it in what follows.4

In addition, several other possible explanations of typicality of an item have been suggested and tested in later studies, including similarity to central tendency (central tendency being e.g. the average of a numerical characteristic of an 4 The problem is with the meaning of “other categories”. We shall expand on the second part in the extended version of this paper. Note, however, that the properties mentioned in the first part (i.e. similarity to objects of the given category, which we use) and the second part were tested separately in [ 13 ] and that each was found significantly correlated with typicality ratings. item), closeness to ideals in goal-oriented categories (ideals represent characteristics that items should possess if they are to serve a goal associated to a category), frequency of instantiation (i.e. frequency of encounter with the item as a member of a given category), and familiarity (i.e. frequency of encounter across all contexts); see e.g. [ 1,10,11 ] and also [ 7 ]. The explanation of [ 13 ] mentioned in the preceding paragraph, nevertheless, appears to be the most commonly accepted. 3 3.1

Formalization of typicality within FCA framework

Preliminaries from formal concept analysis

We assume familiarity with basic notions of formal concept analysis [ 4,8 ]. In particular, a formal context is denoted by hX, Y, Ii, i.e. X and Y are non-empty sets of objects and attributes, respectively, and I ⊆ X × Y is the incidence relation. A pair hA, Bi consisting of A ⊆ X and B ⊆ Y is called a formal concept in hX, Y, Ii if and only if A↑ = B and B↓ = A where

A↑ = {y ∈ Y | for each x ∈ X : hx, yi ∈ I},

B↓ = {x ∈ X | for each y ∈ Y : hx, yi ∈ I} are the set of all attributes common to all objects in A and the set of all objects having all the attributes in B, respectively. The set of all formal concepts of hX, Y, Ii is denoted by B(X, Y, I). B(X, Y, I) equipped with a subconceptsuperconcept partial order ≤ is the concept lattice of hX, Y, Ii. Here, hA, Bi ≤ hC, Di if and only if A ⊆ C (if and only if B ⊇ D). 3.2

Our approach to typicality

As noted above, psychological explorations of typicality and other facets of the graded structure of concepts are considered a strong argument against the abovementioned classical view of concepts. Since FCA may be regarded as representing the classical view, one might argue that using FCA is not appropriate for our purpose. In our view, this is not the case. We contend that typicality naturally occurs even if the objects are described solely by yes/no attributes as in the basic setting of FCA. Moreover, the seminal psychological experiments on typicality mentioned above are based on objects described by yes/no attributes.

Let hA, Bi ∈ B(X, Y, I) be a formal concept in a given formal context hX, Y, Ii. In accordance with section 2.2, we intend to regard an object x typical for the given concept hA, Bi to the extent to which it is similar to the objects of the concept. A straightforward way is to assume a function sim : X × X → [ 0, 1 ] (1) assigning to every two objects x1, x2 ∈ X a number sim(x1, x2) ∈ [ 0, 1 ] that may be interpreted as a degree to which x1 and x2 are similar (we come back to such functions below). Similarity of x to the objects x1 ∈ A may naturally be interpreted as the average similarity.5 Definition 1. Given a similarity (1), a degree of typicality of object x ∈ A in a formal concept hA, Bi ∈ B(X, Y, I) with A 6= ∅ is defined by typ(x, hA, Bi) =

Px1∈A sim(x, x1)

A | | .

Remark 1. (a) Admittedly, our approach is restrictive. One might, for instance, consider formula (2) for x not necessarily in A, or consider the notion of typicality of a subconcept, rather than an object, in a given concept. We proceed with our definition for simplicity.

(b) Typicality degrees provide additional information about a concept hA, Bi. Namely, they reveal a certain graded structure of the concept hA, Bi. Such a structure has a cognitive significance and may be further utilized. Notice that since typ(x, hA, Bi) ∈ [ 0, 1 ] due to sim(X, X) ⊆ [ 0, 1 ], the mapping t : A → [ 0, 1 ] defined by t(x) = typ(x, hA, Bi) may be regarded as a fuzzy set [ 16 ] of objects typical of hA, Bi.

(c) We add subscripts, e.g. typsim , to make apparent the connection of the typicality and similarity in question.

As regards the choice of the similarity function (1), it seems natural to derive sim(x1, x2) from the sets {x1}↑ and {x2}↑ (note that {x}↑ is the set of attributes possessed by x). Hence we assume

sim(x1, x2) = simY ({x1}↑, {x2}↑), where simY , which we also denote just by sim, is a function assigning to any subsets B1 and B2 of Y a degree simY (B1, B2) ∈ [ 0, 1 ] interpreted as similarity of B1 and B2. Two particular functions serving this purpose, which we use in our experiments, are the well-known Jaccard index, simJ, and the simple matching coefficient, simSMC, defined by (2) (3) (4) (5) simJ(B1, B2) = |B1 ∩ B2| and

|B1 ∪ B2| simSMC(B1, B2) = |B1 ∩ B2| + |Y − (B1 ∪ B2)| , |Y | respectively; see e.g.[ 6 ]. Note that simJ is the number of attributes that belong to both B1 and B2 divided by the number of all attributes that belong to B1 or B2; simSMC is the number of attributes on which B1 and B2 agree (either y ∈ B1 and 5 Average similarity is mentioned in some psychological studies; see e.g. [1, p. 630].

Note that we also tried minimum instead of average, as it represents the best lower similarity-threshold. Average, nevertheless, yielded more intuitive results. We use [ 0, 1 ] for the range (i.e. similarity is scaled), but R+ is also a natural option (nonscaled). y ∈ B2, or y 6∈ B1 and y 6∈ B2) divided by the number of all attributes. That is, while simSMC treats both presence and non-presence of attributes symmetrically, simJ disregards non-presence. This is the main conceptual difference between simJ and simSMC.

The choice of the similarity simY is in a sense crucial and, obviously, several other options different from simJ and simSMC are possible. In the rest of this section, we naturally come to a third similarity, which we consider in this paper.

Formula (2) for typicality derives in a straightforward (and we contend that the most direct) way from the verbal description of Rosch and Mervis’s hypothesis quoted in section 2.2. Interestingly, in their experiments to test the hypothesis, Rosch and Mervis [ 13 ] use a different formula for typicality of an object. Strangely, this formula does not bear a direct connection to similarity of objects, which is crucial in the hypothesis. The formula is described in [ 13 ] as follows. Given a concept, one assigns to every attribute its weight, namely the number of all objects of the concept that possess the attribute. A typicality of a given object in the concept is then the sum of the weights of all the attributes possessed by the object.

This definition translates to the FCA framework as follows. For a given hA, Bi ∈ B(X, Y, I) and y ∈ Y , put w(y, hA, Bi) = |{x ∈ A | x ∈ {y}↓}| (weight) and let for x ∈ A,

typRM(x, hA, Bi) = Py∈{x}↑ w(y, hA, Bi).

The following theorem shows that in fact, Rosch and Mervis’s formula for typicality may be regarded as resulting from a particular case of our scheme (2) by a simple scaling; the proof is done by a direct verification given the definitions of typRM and typrm.

Theorem 1. For the function simrm(x1, x2) = |{x1}↑∩{x2}↑| we have |Y | typRM(x, hA, Bi) = |A| · |Y | · typrm(x, hA, Bi) where typrm(x, hA, Bi) is determined by simrm according to (2). 4

Experiments

We performed experiments with several data and present our results for the ZOO dataset [ 5 ] because its objects are commonly known and its concepts are, by and large, well interpretable. ZOO describes 101 animals (objects; we kept all, including the somewhat disputable “girl”; we renamed the one of the two objects denoted “frog” to “frog venomous”) by their 17 attributes. All of the attributes are yes/no attributes except for the attribute describing the number of legs, which we nominally scaled, and an attribute determining the type of animal, which we removed. The resulting formal context is presented in Appendix (to save space, objects with the same attributes are put on the same row).

Our main purpose was to assess whether the typicalities computed by our formulas described above are intuitively sound, i.e. whether the objects with high typicality values for the examined concepts are those we ourselves would intuitively consider typical.6

We first selected a collection of concepts on which we examined typicality. We made a selection from formal concepts with high basic level indices [ 3 ] because these tend to be easily understood by humans. In what follows, we present three such concepts, which may verbally be described as “bird,” “fish,” and “mammal.”

Table 1 presents the concept “bird” (rows represent all the objects in the extent; columns include all the attributes possessed by at least one object in the extent) along with the typicality ratings by the three functions typJ, typSMC, and typRM. irreobn itcaqu trreaod ceaokbn trseeah il itsce ize 2 a a p b b ta odm tsca lseg 6 Note in this connection that, as in our previous studies involving basic level [ 2,3 ], we observed that in order to obtain intuitively plausible results, the data needs to be of reasonable quality. Most importantly, it needs to contain attributes people naturally regard when determining typicality.

The table is ordered by the values of typJ in a descending order (and alphabetically where ties occur). Therefore, typJ tells us that lark is one of the five most typical birds while penguin is the least typical. In our culture, one would probably move pheasant and flamingo to lower ranks. However, from the viewpoint of the attributes present in the dataset, pheasant is indistinguishable from lark and flamingo is very similar to lark.7 Taking this into account we regard the values of typJ intuitively plausible.

Similar conclusions may be drawn for “fish” (table 2) and “mammal” (table 3). Strictly speaking, the concept in table 2, which defined by attributes “aquatic” and “legs 0,” does not correspond to fish according to the present biological standards, since it contains sea snake (snake), seal (mammal), and sea wasp (jellyfish). We use “fish” for simplicity.8 ilk itcau treaod teohd ceokbn tseeah soonum snfi lita itsceodm itsczea lseg0 m aq rp to ab rb ev 7 A way to resolve this situation and to obtain more appropriate values of typicality is to add further, distinctive attributes, which we did; details shall be reported in an extended version of this paper. 8 Interestingly, this would be correct according to a 16th century classification; see C. P. Hickman, Jr., L. S. Roberts, A. L. Larson, Integrated Principles of Zoology. McGraw-Hill, 2001. irah segg likm irreoabn itcaaqu trreaodp tteoohd ceoakbnb trseeahb sfin lita itsceodm itszcea lse0g lse2g lse4g

As regards the other typicality functions, typSMC and typRM, a natural general question arises: To what extent do two possible typicality functions determine similar ordering by typicality. To explore this topic in a greater detail, we computed the well-known Kendall tau rank correlation coefficients.9 The correlation between typJ and typSMC for the three concepts is 0.95 (“birds”), 0.97 (“fish”), and 0.90 (“mammal”); between typJ and typRM is 0.06 (“birds”), 0.44 (“fish”), and 0.70 (“mammal”); and between typSMC and typRM is 0.01 (“birds”), 0.41 (“fish”), and 0.60 (“mammal”). We also computed the average of Kendall tau coefficients over all the concepts in the ZOO dataset with at least two objects, and obtained 0.89 for typJ and typSMC, 0.38 for typJ and typRM, and 0.28 for typSMC and typRM. These relationships shall be examined further. In particular, typJ—which in our view yields most plausible rankings—seems to be not very strongly correlated with Rosch and Mervis’s typRM.

We also examined typicality in some upper and lower neighbors of the three basic level concepts, because these play a significant role in the psychological experiments regarding typicality (so-called superordinate and subordinate categories). The results are in accordance with psychological findings in that the average typicalities for superordinate categories are smaller while those for subordinate categories are higher. For instance, while the average value of typJ is 0.79 for “birds,” the average for the lower neighbor of “birds” determined by the additional attribute “airborne” is 0.84, and the average for the upper neighbor determined by the attributes “eggs,” “backbone,” “breathes,” and “tail” is 0.65.

Let us also note that our experiments resulted a number of observations relevant not only to typicality, but also to the phenomena of basic level and cohesion, and shall be reported in future. 5

Further topics

Our main aim in this paper is to open examination of typicality within the context of formal concept analysis. Due to limited scope, we restricted to introducing the problem, our approach, and basic findings including experimental demonstration. Major topics to be explored further are the following: – Datasets. As mentioned above, experimental evaluation regarding psychological phenomena such as typicality and basic level requires quality datasets that make it sensible to compare to what extent results of formal methods (e.g. methods computing typicality) agree with results obtained by humans (e.g. typicality ratings). We intend to prepare a collection of suitable datasets, which shall include both data taken from public repositories as well as data obtained from humans by means of methods inspired by experiments in the psychology of concepts. 9 These measure ordinal association between two quantities, i.e. between two typicalities in our case. The coefficient ranges from 1 (same ranking) to −1 (opposite ranking). We used tau-b to account for ties in typicality values and used the Python library [ 15 ]. – Experiments involving human judgment. So far, we have assessed our methods of computing typicality by our own intuition. We plan to move from the question “Do the typicality ratings provided by the explored formal methods seem reasonable to us?” to “Do the ratings provided by formal methods correspond to how humans perceive typicality ?” To do so, we plan to design proper experiments, again inspired by procedures used in the psychology of concepts. – Since the similarity function sim plays a crucial role in our approach, further explorations, both theoretical and experimental, regarding the properties and effect of various similarity functions are of utmost importance. Interestingly, all the three similarity functions considered above may be shown to be three particular cases of a parameterizable family of similarity functions which we started to explore. The question of which similarity is the best one is not likely to be resolved; nevertheless, questions of this sort need to be asked. – As shown above, the original Rosch and Mervis’s formula for typicality may be regarded as resulting from a particular case of our scheme (2) by a simple scaling. We obtained preliminary results regarding the converse question of whether our typicality formulas may be derived from a particular case of the general scheme behind Rosch and Mervis’s formula. – Typicality of attributes seems just a dual case of typicality of objects. From a psychological point of view, however, typicality of attributes has a rather different role; see e.g. [ 11 ]. Methods to determine typicality of attributes shall thus be explored. – In a sense, we considered typicality of objects per se. Connections both to the psychology of concepts (e.g. examination of psychological facets of the above-mentioned role of similarity functions) and data science (e.g. possible utilization of typicality in various data analytic and machine learning tasks) should be explored. – Formalization of further psychological explanations of typicality, some of which are mentioned in section 2.2. – Relationship other psychological phenomena. It comes as no surprise that typicality may be used to define related phenomena, such as the basic level of concepts and concept cohesion. Such relationships shall be analyzed. – Explorations of typicality in a broader context of clustering of binary (i.e. yes/no) and more general data. This is significant from a data analytic viewpoint, but also from a psychological viewpoint. Namely, it is repeatedly argued in various of the above-mentioned studies that the concepts on which typicality has been explored do not have a set of definitory attributes, as assumed by the classical view. More often than not, those concepts are rather assumed to be “held together” by family resemblance.

Acknowledgment Supported by the projects IGA 2019, reg. no. IGA PrF 2019 034, and IGA 2020, reg. no. IGA PrF 2020 019, of Palacky University Olomouc Appendix

References

1. Barsalou , L. W. : Ideals, central tendency, and frequency of instantiation as determinants of graded structure in categories . J. Experimental Psychology: Learning, Memory, and Cognition 11 , 4 , 629 - 654 ( 1985 ). https://doi.org/10.1037/ 0278 - 7393 . 11 .1- 4 . 629 .

2. Belohlavek , R. , Trnecka , M. : Basic Level of Concepts in Formal Concept Analysis . Domenach , F. et al. (eds.) Formal Concept Analysis . pp. 28 - 44 . Springer, Berlin/Heidelberg, Heidelberg ( 2012 ). https://doi.org/10.1007/ 978-3- 642 -29892- 9 _ 9 .

3. Belohlavek , R. , Trnecka , M. : Basic level in formal concept analysis: Interesting concepts and psychological ramifications . Twenty-Third International Joint Conference on Artificial Intelligence . pp. 1233 - 1239 ( 2013 ).

4. Carpineto , C. , Romano , G.: Concept Data Analysis: Theory and Applications . Wiley, Chichester, England, Hoboken, NJ ( 2004 ).

5. Dua , D. , Graff , C.: UCI Machine Learning Repository . University of California, Irvine, School of Information and Computer Sciences ( 2019 ). [http://archive. ics.uci.edu/ml]

6. Everitt , B. S. , Landau , S. , Leese , M. : Cluster Analysis . Wiley, Chichester, West Sussex, UK ( 2011 ).

7. Fisher , D.H.: A computational account of basic level and typicality effects . Proc. AAAI-88 . pp. 233 - 238 ( 1988 ).

8. Ganter , B. , Wille , R.: Formal Concept Analysis: Mathematical Foundations . Springer, Berlin ( 1999 ).

9. Machery , E.: 100 years of psychology of concepts: the theoretical notion of concept and its operationalization . Studies in History and Philosophy of Biological and Biomedical Sciences 38 , 1 , 63 - 84 ( 2007 ). https://doi.org/10.1016/j.shpsc. 2006 . 12 .005.

10. Mervis , C. B. , Catlin , J. , Rosch , E.: Relationships among goodness-of-example, category norms, and word frequency . Bull. Psychon. Soc. 7 , 3 , 283 - 284 ( 1976 ). https://doi.org/10.3758/BF03337190.

11. Murphy , G. L. : The Big Book of Concepts . MIT Press, Cambridge, Mass ( 2002 ).

12. Rosch , E.: Principles of categorization . Rosch, E. , Lloyd , B.B. (Eds.): Cognition and Categorization, Erlbaum, Hillsdale, NJ, pp. 27 - 48 ( 1978 ).

13. Rosch , E. , Mervis , C. B. : Family resemblances: Studies in the internal structure of categories . Cognitive Psychology 7 , 4 , 573 - 605 ( 1975 ). https://doi.org/10. 1016/ 0010 - 0285 ( 75 ) 90024 - 9 .

14. Rosch , E. et al.: Basic objects in natural categories . Cognitive Psychology 8 , 3 , 382 - 439 ( 1976 ). https://doi.org/10.1016/ 0010 - 0285 ( 76 ) 90013 - X .

15. SciPy 1.0 Contributors et al.: SciPy 1.0: fundamental algorithms for scientific computing in Python . Nature Methods ( 2020 ). https://doi.org/10.1038/ s41592-019-0686-2.

16. Zadeh , L. A. : Fuzzy sets . Information and Control 8 , 3 , 338 - 353 ( 1965 ). https: //doi.org/10.1016/S0019- 9958 ( 65 ) 90241 - X .