The identification of the basic-level is performed in an already prepared hierarchy of clusters using basic-levelness measures. In the psycholinguistic literature, a few basic-levelness measures are found. In particular, the following basic-levelness measures can be utilized: (a) feature-possession (FP) proposed by Jones [
9], (b) category utility (CU) proposed by Corter and Gluck [
10], (c) category attentional slip (CAS) proposed by Gosselin and Schyns [
11], (d) category’s cue validity with global threshold (CCVGT) proposed by Katarzyniak et al. [
12], (e) category’s cue validity with feature-possession (CCVFP) proposed by Mulka and Lorkiewicz [
13]. The formal definitions of these measures are presented in [
13] and are included in this paper for completeness. It is worth noting that category’s cue validity [
1] is not considered, as it requires defining a feature-category relation (see Sect.
3.2).
3.1 Auxiliary Measures
There are five auxiliary measures utilized by at least one basic-levelness measure, namely: (a) probability of a feature, (b) probability of a cluster, (c) cue validity, (d) category validity, (e) collocation.
Probability of a feature The probability of a feature (denoted as
P(
f)) [
10] determines how it is probable that any object exhibits a feature
f. It is calculated as follows:
$$\begin{aligned} P(f) = \frac{\sum \nolimits _{o \in \mathcal {O}} \gamma _{o,f}}{\mid \mathcal {O}\mid }. \end{aligned}$$
(1)
The probability of a feature
P(
f) increases as the frequency increases with which a feature
f is common among objects. In general, the probability of a feature is equal to 0 when no objects exhibit a feature
f, and the value of 1 occurs when all objects exhibit a feature
f. However, in this paper, it is further assumed that each feature is exhibited by at least one object, hence
\(\forall _{f\in \mathcal {F}}\left[ P(f){>}0 \wedge P(f) \le 1\right] \).
This auxiliary measure is utilized only by one basic-levelness measure, namely CU.
Probability of a cluster The probability of a cluster (denoted as
\(P(\mathcal {X}_k^r)\)) [
10] determines how it is probable that an object belongs to a cluster
\(\mathcal {X}_k^r\). It is calculated as follows:
$$\begin{aligned} P(\mathcal {X}_k^r) = \frac{\mid \mathcal {X}_k^r\mid }{\mid \mathcal {O}\mid }. \end{aligned}$$
(2)
The probability of a cluster
\(P(\mathcal {X}_k^r)\) increases with the number of objects belonging to a cluster
\(\mathcal {X}_k^r\). In particular, the probability of a cluster cannot be equal to 0 since a cluster has to contain at least one object. While, the probability of a cluster is equal to 1 when all objects belong to this cluster. Due to the fact that each hierarchy level is a partition of the set
\(\mathcal {O}\), the sum of all probabilities of clusters from a specific hierarchy level is equal to 1.
This auxiliary measure is utilized only by one basic-levelness measure, namely, CU.
Cue validity Cue validity (denoted as
\(P(\mathcal {X}_k^r{\mid }f)\)) [
3] informs how a feature
f is a good predictor for determining a cluster
\(\mathcal {X}_k^r\), i.e., assuming that an object exhibit a feature
f, it informs how likely it is to say that an object belongs to a cluster. It is calculated as follows:
$$\begin{aligned} P(\mathcal {X}_k^r{\mid }f) = \frac{P(\mathcal {X}_k^r \cap f)}{P(f)} = \frac{\frac{\sum \nolimits _{o \in \mathcal {X}_k} \gamma _{o,f}}{\mid \mathcal {O}\mid }}{\frac{\sum \nolimits _{o \in \mathcal {O}} \gamma _{o,f}}{\mid \mathcal {O}\mid }} = \frac{\sum \nolimits _{o \in \mathcal {X}_k^r} \gamma _{o,f}}{\sum \nolimits _{o \in \mathcal {O}} \gamma _{o,f}}, \end{aligned}$$
(3)
where
\(\sum \nolimits _{o \in \mathcal {O}} \gamma _{o,f}\) denotes the sum of occurrences of a feature
f in objects
\(\mathcal {O}\), whilst
\(\sum \nolimits _{o \in \mathcal {X}_k^r} \gamma _{o,f}\) denotes the sum of occurrences of a feature
f in all objects from a cluster
\(\mathcal {X}_k^r\).
The value of cue validity \(P(\mathcal {X}_k^r{\mid }f)\) increases as the frequency increases with which a feature f is associated with a cluster \(\mathcal {X}_k\) and decreases as the frequency increases with which a feature f is related to other clusters than \(\mathcal {X}_k^r\). In particular, the cue validity’s value of 0 occurs when no objects from a cluster \(\mathcal {X}_k^r\) exhibit a feature f, and the value of 1 occurs when at least one object from a cluster \(\mathcal {X}_k^r\) exhibits a feature f and a feature f is not exhibited by any objects from all remaining clusters.
Four basic-levelness measures: FP, CU, CCVGT, CCVFP utilize this auxiliary measure.
Category validity Category validity (denoted as
\(P(f{\mid }\mathcal {X}_k^r)\)) [
10] is the probability that an object belonging to a cluster has a feature
f. It is calculated as follows:
$$\begin{aligned} P(f{\mid }\mathcal {X}_k^r) = \frac{P(\mathcal {X}_k^r \cap f)}{P(\mathcal {X}_k^r)} = \frac{\frac{\sum \nolimits _{o \in \mathcal {X}_k^r} \gamma _{o,f}}{\mid \mathcal {O}\mid }}{\frac{\mid \mathcal {X}_k^r\mid }{\mid \mathcal {O}\mid }} = \frac{\sum \nolimits _{o \in \mathcal {X}_k^r} \gamma _{o,f}}{\mid \mathcal {X}_k^r\mid }, \end{aligned}$$
(4)
where
\(\sum \nolimits _{o \in \mathcal {X}_k^r} \gamma _{o,f}\) denotes the sum of occurrences a feature
f in all objects from a cluster
\(\mathcal {X}_k^r\), whilst
\(\mid \mathcal {X}_k^r\mid \) denotes the total number of objects in a cluster
\(\mathcal {X}_k^r\).
The value of category validity \(P(f{\mid } \mathcal {X}_k^r)\) increases as the frequency of a feature f in a cluster \(\mathcal {X}_k^r\) increases. In particular, category validity is equal to 0 when no object from a cluster \(\mathcal {X}_k^r\) exhibits a feature f, while it is equal to 1 when all objects from a cluster \(\mathcal {X}_k^r\) exhibit a feature f.
This auxiliary measure is utilized by all considered basic-levelness measures.
Collocation Collocation (denoted as Col
\((\mathcal {X}_k^r,f)\)) [
9] is defined based on cue validity and category validity, and it represents a trade-off between a feature’s spread within a cluster and it’s ability to predict the cluster. It is calculated as follows
$$\begin{aligned} \mathrm{{Col}}(\mathcal {X}_k^r,f) = P(f{\mid }\mathcal {X}_k^r) P(\mathcal {X}_k^r {\mid }f), \end{aligned}$$
(5)
so collocation is a product of cue and category validities of a cluster
\(\mathcal {X}_k^r\) and a feature
f.
Collocation is equal to 0 when no objects from a cluster \(\mathcal {X}_k^r\) exhibit a feature f, and the value of 1 occurs when cue and category validities are equal to 1 for a specific feature and cluster.
Maximal collocations are denoted as
\(\mathrm{{Col}}_{\max }(f)\) and they are calculated as follows
$$\begin{aligned} \mathrm{{Col}}_{\max }(f) = {\max \limits _{\mathcal {X} \in \bigcup \limits _{\mathbb {X}_r \in \mathbb {X}}}{P(f{\mid }\mathcal {X}) P(\mathcal {X} {\mid }f)}}. \end{aligned}$$
(6)
Hence, maximal collocations are established for all features, using all clusters in a hierarchy of clusters.
This auxiliary measure is utilized only by two basic-levelness measures, namely, FP, CCVFP.
3.2 Basic-Levelness Measures
As aforementioned, there are five basic-levelness measures for which the time complexity of the identification of the basic-level is determined in this paper, namely (a) feature-possession, (b) category utility, (c) category attentional slip, (d) category’s cue validity with global threshold, (e) category’s cue validity with feature-possession.
Feature-possession Jones [
9] proposes a basic-levelness measure, which is called feature-possession. It captures a certain trade-off between cue validity and category validity on a category level. Furthermore, the author argues that the basic-level is a hierarchy level at which the average feature-possession is maximal. It reflects the basic-level property of assigning the largest number of features at the basic-level [
1].
Feature-possession for a hierarchy level
\(\mathbb {X}_r\) is defined based on collocation (see Definition
3).
The basic-level \(\mathbb {X}_b{\in }\mathbb {X}\) is a hierarchy level for which the value of feature-possession is maximized, namely \(\mathbb {X}_b = {\mathop {\text {arg max}}\nolimits _{\mathbb {X}_{r} \in \mathbb {X}}{FP(\mathbb {X}_r)}}\). It is not defined which hierarchy level should be identified as the basic-level if more than one hierarchy level maximizes such a basic-levelness measure.
Category utility Corter and Gluck [
10] propose a basic-levelness measure called category utility. A category is useful to the extent that it can be expected to improve people’s ability to: (a) accurately predict features of a member of such a category, (b) efficiently communicate information to others about features of members of such a category. They argue that a category which is optimal for one of these purposes also tends to be optimal for the other one. In particular, category utility captures the overall categories’ predictability and informativeness of features within a cluster (see Definition
4).
^{3}
The basic-level \(\mathbb {X}_b{\in }\mathbb {X}\) is the hierarchy level for which the value of category utility is maximized, namely \(\mathbb {X}_b = {\mathop {\text {arg max}}\nolimits _{\mathbb {X}_r \in \mathbb {X}}{CU(\mathbb {X}_r)}}\). It is not defined which hierarchy level should be identified as the basic-level if more than one hierarchy level maximizes such a basic-levelness measure.
Category attentional slip Gosselin and Schyns [
11] define a basic-levelness measure called category attentional slip. There are two fundamental determinants of basic-levelness, namely, the cardinality of redundant tests and the length of the optimal strategy needed to establish categories. The former is related to the distinctiveness of features among categories, i.e., how many different tests (understood as a verification whether an object exhibits a certain feature) can be performed to determine the placement of a new object in a hierarchical structure — it defines how features of a category characterize an object. The latter is related to the length of the optimal strategy to determine a category, i.e., how many decisions, starting from the root of a hierarchy, should be performed to establish a specific category.
Category attentional slip (see Definition
5) captures the aforementioned notions of cardinality and optimal strategy length. In particular, it is related to the number of tests required to determine the category by an ideal categorizer.
To calculate the probability of a relevant test \(q_k^r\) it is enough to focus on features that are common to all objects in a cluster, i.e., \(\frac{\sum \nolimits _{f \in \mathcal {F}}\theta (P(f,\mathcal {X}_k^r), 1)}{\mid \mathcal {F}\mid }\) and subtract all features that are common to any of its superclusters \(\sum \nolimits _{\mathcal {X}_j^r \in \Upsilon _k^r {\setminus } \mathcal {X}_k^r}{q_j^r}\).
Unlike other basic-levelness measures, the basic-level \(\mathbb {X}_b{\in }\mathbb {X}\) is the hierarchy level for which category attentional slip is minimized, namely \(\mathbb {X}_b ={\mathop {\text {arg min}}\nolimits _{\mathbb {X}_r \in \mathbb {X}}{CAS(\mathbb {X}_r)}}\). It is not specified which hierarchy level should be identified as the basic-level if more than one hierarchy level has a minimal value of such a basic-levelness measure.
Category’s cue validity Rosch et al. [
1] propose that it is possible to determine cue validity for an entire category. It is done by adding up cue validity of all features of a category, hence a category’s cue validity is no longer a probabilistic concept (so, its value may exceed 1). In addition, Rosch noticed that a category with a large value of category’s cue validity is by definition distinguishable from these with a low value for this parameter. Hence, the hierarchy level that maximizes the average category’s cue validity is the basic-level.
Murphy [
5] pointed out that such a definition of a category’s cue validity will always be maximal at the most general or inclusive hierarchy level (i.e., at the root). However, it should be noted that Murphy assumed that categories contain all features of all subordinate categories, whereas Rosch has a less restrictive understanding of feature-category relations, i.e., superordinate categories have fewer features as compared with the basic-level. To determine which features are shared by members of a category, two approaches are found in the literature: cue validity with a global threshold [
12], and category’s cue validity with feature-possession [
13].
Category’s cue validity with global threshold Katarzyniak et al. [
12] proposed category’s cue validity with global threshold (see Definition
6). Such a basic-levelness measure utilizes a global threshold (i.e., a borderline value) to determine which features fall into a cluster.
The basic-level \(\mathbb {X}_b{\in }\mathbb {X}\) is a hierarchy level for which category’s cue validity with global threshold is maximized, i.e., \(\mathbb {X}_b = {\mathop {\text {arg max}}\nolimits _{\mathbb {X}_r \in \mathbb {X}}{\mathrm{{CCVGT}}(\mathbb {X}_r)}}\). It is not specified which hierarchy level should be identified as the basic-level if more than one hierarchy level maximizes such a basic-levelness measure.
The introduced measure takes into account Rosch’s remarks, i.e., with a sufficiently large \(\delta \) value (e.g., at least greater than 0.5) at higher hierarchy levels some features are not taken into account since the value of \( P(f_i{\mid }\mathcal {X}_k^r) \) could be smaller than \(\delta \) (e.g., if more than 50% of objects do not exhibit a feature). It is worth noting that Murphy’s understanding of feature-category relations occurs when the global threshold is equal to 0.
A disadvantage of this basic-levelness measure is the need to determine the global threshold. Too low values of this threshold may result in maximizing cue validity at the root of a hierarchy of clusters (similarly as in Murphy’s comment [
5]), while too high values of the global threshold may cause that a hierarchy level that should be the basic-level is not correctly identified (since too many features could not be taken into account).
Category’s cue validity with feature-possession Mulka and Lorkiewicz [
13] proposed category’s cue validity with feature-possession. It assumes that a cluster exhibits a feature
f if and only if its or any of its superclusters’ collocation is equal to
\(\mathrm{{Col}}_{\max }(f)\) (see Definition
7).
The basic-level \(\mathbb {X}_b{\in }\mathbb {X}\) is a hierarchy level for which category’s cue validity with feature-possession is maximized, i.e., \(\mathbb {X}_b ={\mathop {\text {arg max}}\nolimits _{\mathbb {X}_r \in \mathbb {X}}{\mathrm{{CCVFP}}(\mathbb {X}_r)}}\). It is not specified which hierarchy level should be identified as the basic-level if more than one hierarchy level maximizes such a basic-levelness measure.