Implementing Cognitive Semantics of Autoepistemic Membership Statements: The Case of Categories with Prototypes

This article presents models and methods for managing the process of generating autoepistemic statements about the belonging of observed objects to conceptual categories with a prototype. It continues, and at the same time, builds upon previous results from a broad research project aiming at a design of a set of technical implementations of cognitive semantics for a variety of classes of autoepistemic modal statements (see Section 2 below). The project assumes that in its final form an application of cognitive semantics is going to functionally enable software agents to meaningfully participate in semantic communication using natural or semi-natural language.

Research on cognitive semantics of language statements originates from a field of cognitive linguistics. A fundamental goal is to formulate a detailed description of a relationship between linguistic (external, realized using a graphic or verbal form) representations of internal states exhibited (experienced) by a language-processing entity (in this case, an artificial cognitive agent, referred to as the agent) and cognitive structures reflecting an internal non-linguistic representation of said states within the entity. A formulation of a model of such a relationship for a particular statement $\varphi$ (of natural or semi-natural language) is equivalent to a definition of cognitive semantics of this statement. A model of cognitive semantics of the statement needs to specify elements of the agent’s internal state which further serve as requirements for a generation of the statement in its linguistic (external) form. Cognitive semantics defined as such is understood as a description of the statement’s meaning which is intrinsic to the agent generating the statement.

An idea of cognitive semantics can be naturally understood using the semiotic triangle which is a theoretical tool originally derived from the field of semiotics [1,2]. It helps to distinguish cognitive semantics from other types of semantics (e.g., classic set theory-based semantics). The semiotic triangle (presented in Figure 1) reflects mutual relationships present in languages of semantic communication between the following:

Particular implementations of the semiotic triangle are always formed in relation to a particular cognitive agent and with respect to a particular language of semantic communication. In basic implementations of the semiotic triangle, referents are usually physical objects located in the real world and symbols, in a graphical or verbal form, are interpreted as tools used to point at particular aspects of these objects. Such implementations can be found in research on a controlled societal development of the language, in particular, the naming game (numerous works of Steels, Vogt, and others, e.g., [3,4,5,6]), with theoretical ideas dating back to 1950s and Wittgenstein’s works on language games.

Cognitive semantics within a semiotic triangle model binds a symbol with a corresponding reference and establishes an intrinsic (in this case, internally experienced) meaning of the symbol. It not only specifies elements of the subjective experience of the knowledge entity that corresponds to the external referent, but further describes a way in which the entity refers to parts of this experience during further processing.

For a particular sign, cognitive semantics describes a structure and contents of the internal reference related to the external sign. Signs with an assigned cognitive semantics become fully functional elements (statements) of a language of semantic communication and can be used by the agent to describe its convictions about perceived objects of the real world. In consequence, from the agent’s point of view, signs assigned with cognitive semantics become so-called symbols.

An idea of cognitive semantics outlined above aligns with a sense assigned within a broad and heterogeneous field of cognitive linguistics (compare [7]). Although originally cognitive semantics has been analyzed for natural languages, it is worth pointing out that over the years some elements of this approach to the modeling of meaning have been successfully applied in research on the semantics of communication between animals [8].

Real-life implementations of the semiotic triangle for a natural language in artificial cognitive agents try to mimic ways in which human minds store acquired empirical experience and ways in which they (often deliberately and creatively) refer to this experience in order to communicate parts of its contents to others. The reference, even for a case of the simplest natural language statements, becomes a very complex system consisting of multiple mental elements. In consequence, a design (modeling) of cognitive semantics for particular types of natural language statements is a task of substantial theoretical complexity as it involves references to multiple elements of an artificial mind.

The cognitive semantics proposed in this paper is designed and analyzed for so-called autoepistemic membership statements which have two fundamental pragmatic goals assigned in natural languages. Namely, the agent generating a particular autoepistemic membership statement fulfills a compound intention:

Obviously, such a statement must meet the grammar constraints of the semantic communication language used by both the sender and recipient, be composed of at least three dedicated syntactic elements indicating an object, a category, and an experienced confidence level. It is naturally implied that both the sender and a potential recipient are required to know the pragmatics, semantics, and syntax of the language.

Due to the specificity of the research results described in this article, some additional introductory comments are required on the following two issues: the nature of the considered conceptual categories and a permissible number of confidence levels mentally distinguishable by agents involved in acts of semantic communication.

In regard to the nature of the categories, the research reported in this article concerns the so-called categories with a prototype, which differentiates this research from our previous studies into cognitive semantics of autonomous membership statements covering the case of categories described by the so-called classical theory of categorization. The latter theory has been widely recognized for many centuries, based on the ideas developed by Aristotle, and often referred to as the necessary and sufficient condition model [9] or criterial-attribute model [10]. Its basic assumptions are [11] as follows:

Results from research conducted in the second half of the twentieth century, in virtually all cognitive science subdisciplines, showed that in many cases the above assumptions were too strict, and in consequence, were not met. For example, Geeraerts [12] pointed out that for a category bird, it is impossible to find necessary and sufficient conditions that are valid for all types of birds. Indeed, if we assume that a bird is an animal that is oviparous and has a beak, it turns out that there are species (e.g., a platypus) or even orders of animals (e.g., turtles) that posses these features but are not birds. On the other hand, the features that seem distinctive are missing from some members of the category: ostriches and penguins cannot fly, kiwis do not have wings, and penguins do not have the typical feathers.

Research conducted by Rosch [13,14] showed that in many cases people did not treat all elements of a particular category equally and some elements were considered more representative for the category than others. In particular, the systematic and extensive experiments conducted by Rosch proved that for different objects belonging to a category, the categorization time, the time after which the element is categorized in the learning process, and the prototypicality rating obtained from participants of the experiments could differ significantly. Rosch presented a proposal of systematic and integrated interpretation of the above effects, and summarized them as the so-called standard version of the prototype semantics.

Following [9], the basic assumptions related to categories with a prototype are usually summarized as follows:

In our research, we assume that the above assumptions on categories with prototypes must be adequately mapped into the originally formulated definition of cognitive semantics and effectively used in implemented software agents. It is worth pointing out that a process of category formation (learning) is interesting from a broader perspective as prototype-based approaches in general, and categories with prototypes in particular, are used in a plethora of knowledge processing tasks. Among others, Wang et al. [15] use a prototype-based approach for intent perception; Yongjie et al. [16] advocate a prototype-based approach to alleviate problems with outliers during unsupervised domain adaptation; Zhou et al. [17] introduce a class prototype discovery method and show further promising results in unsupervised domain adaptation.

In regard to confidence levels, it is assumed in this article (following previous research) that agents are capable of mentally distinguishing three levels of confidence about the compliance of the communicated belief (about the object’s membership to a category) with the real state of affairs. Namely, an agent can be in one of the following states:

These three states could be seen as certainty, strong belief, and weak belief. An introduction of three distinct levels of confidence is reflected in the pragmatics and semantics of multiple classes of natural languages. Among others, it is observable in English and Polish, both equipped with dedicated autoepistemic operators (or other means) for labeling rather three, and not more or less, levels of confidence.

Obviously, our final model of cognitive semantics, including a sub-model of reference (or thought) forming the semiotic triangle as part of it, will have to take into account the most important and necessary aspects of mental experience related to the processing of prototypical effects and to the capability of differentiating between assumed levels of autoepistemic confidence. It will also include a model of empirical knowledge base supporting the actual cognitive differentiation of levels of confidence in particular real situations.

Concluding the preliminary remarks on the considered case of autoepistemic membership statements, it can be said that in the subsequent parts of this article, the above-mentioned pragmatical, theoretical, and commonsense-related interpretations will be applied to statements for which the general structure can be summarized by the following symbol: and the correlated symbol: where $\Sigma ,x,c,\in ,\notin$ are assigned the following interpretation: $\Sigma$ is a label of an internally experienced level of confidence, x is a pointer to an internally located representation of object, c is a name of an internally represented category with prototype, ∈ and ∉ are labels denoting belonging and non-belonging of x to c. In such a perspective, $\Sigma ,x,c,\in$, and ∉ are to be understood as “physically” (e.g., graphically or verbally) realized pointers to particular elements (aspects) of an internally located complex and usually, as will be shown later, multidimensional reference.

This article introduces elements of technical implementations of the cognitive semantics and corresponding computational methods. From a broader perspective, it should be seen as an applied research work aiming at an application of models and methods of cognitive linguistics designed for modeling the meaning of symbols for semantic languages. These models are now being applied in a context of technical systems with linguistic capabilities, e.g., interactive AI systems.

In a more detailed and specific approach, the main research target of this article is to propose and at least partially verify an original version of a model of a software agent with a competence to process autoepistemic modal statements with the above-characterized cognitive semantics and pragmatics. This goal has led to the formulation of the following set of crucial functionalities required by the cognitive agent:

The organization of the rest of this article is as follows. The next section presents a brief review of related research works which influenced the final shape of the described research project. Due to the nature of the project, it includes chosen papers from the authors’ research group on other classes of autoepistemic modal statements, as well as papers setting a broader theoretical background for the original approach to modeling the meaning of the languages of semantic communication.

The third section is devoted to a more detailed discussion of the syntax of the considered class of modal statements and the commonsense (intuitive) meaning attributed to these statements. In other words, the section is devoted to an enumerative review of the basic syntactic elements that comprise the modal statements considered in this article, and to a discussion of the relationship of these elements with their equivalents in natural languages.

The fourth section contains a detailed discussion of the software agent model. The software agent ultimately acts as an entity that uses the original semantics of autoepistemic modal statements proposed in this article and manages the collection of categories with a prototype available to the agent. The agent model includes, in particular, the basic empirical database used in the process of acquiring and updating models of categories with a prototype.

The fifth section is devoted to a detailed presentation of an original strategy for learning categories with a prototype. This section considers a version of the strategy based on a universe of objects that is paired with a measure of distance as a tool for the technical realization of the agent’s mental ability to compare objects. An extended computational example using an assumed distance function is provided for convenience in this section.

The sixth and seventh sections are devoted to the presentation of original cognitive semantics and to the discussion of its properties. Suitable illustrative computational examples are included.

The last two sections contain the summary of this article and point at some of our further research goals.

R&D goals set in the introduction require a formulation of a dedicated internal architecture of an artificial agent allowing for an effective execution of key cognitive processes responsible for a formation (often through learning in a social setting) and management of categories with prototypes and for further usage of cognitive semantics based on these categories during communication acts. In order to realize these two main capabilities within an agent, its internal architecture needs to contain relevant internal structures. Figure 2 outlines such an architecture which contains, among others, the following set of interlinked components:

which are directly related to the investigated phenomena, that is, to a set of cognitive functions realized by:

Many of these processes must run concurrently in an agent. Therefore, the final implementation is bound to have to pay strong attention to the way in which they are dynamically interlinked within the agent’s artificial mind to ensure required dialogue capabilities [60].

From a cognitive perspective, the basic mental space is a key component of the architecture as it represents a fundamental cognitive competence of an agent of being able to distinguish objects of a particular universe. The elements of the basic mental space exhibit the nature of atomic (indivisible) entities, whose state, behavior, and relations with other elements can become an object of particular beliefs of an agent.

From this article’s goals’ standpoint, there are two crucial functionalities of the basic mental space. At first, elements of the basic mental space allow an agent to order (organize and conceptualize) an empirical material obtained through direct observation of the external environment. Contents of these observations is restricted to objects whose existence is entailed by the structure of the basic mental space. Elements not expressible in the basic mental space, provided they exist, are in this research treated, from the agent’s point of view, as cognitively ungraspable, and hence completely omitted.

At second, the basic mental space serves as a fundamental layer over which categories (in particular, investigated categories with a prototype) can be defined. But more importantly, we claim that each conceptual category has to be always defined in relation to a respective mental space. It entails that the basic mental space adopted in the presented architecture of an artificial agent, after equipping it with tools for a formal (numerical) expression of a degree of similarity (or distance) between any pair of objects from the mental space, corresponds directly to the aforementioned theory of the conceptual spaces [45,46,47].

We adopt the following definition of the basic mental space:

We assume that the domains $V_a$ of attributes $a\in A$ depend on the nature of objects considered by the agent and due to the range of practical applications we allow, they may contain values of the following type:

Obviously, despite being a phenomenological whole, from the agent’s point of view each element $o\in O$ is cognitively decomposable into specific values of attributes, which are still integral components of this object. It is worth noting that such a decomposition is integrally related to the process of generating statements about a specific feature of an object and, in a broader theoretical perspective, refers to one type of the so-called predication discussed in formal logic, cognitive science and, above all, in linguistics (e.g., [37,38]).

The way in which the basic mental space participates in building a mental representation of an agent’s observations of external worlds, as well as in obtaining and representing a model of a category with a prototype, is presented in the following parts of this article.

As can be seen in Figure 2, it is assumed that models of all categories known to the agent are stored in a dedicated repository. The repository is an important part of the internal representation of the so-called embodied ontology, representing how the agent perceives the conceptual order of the external world. Another basic element of such an ontology is the basic mental space introduced above.

Each category with a prototype is built in relation to the accessible mental basic space O. In our approach, we try to reflect as many structural and functional features as possible, which have been provided for categories in the so-called standard version of the prototype semantics [9]. In particular, each category is assigned a specialized object $o_c^{★}\in O$ distinguished from all other objects in this category, called a prototype of the category. It is perceived by the agent as being the most representative and in some sense "central" element of the category.

An agent’s attitude towards a membership of an object to a given category should be directly related to the degree of that object’s similarity (or distance) to the prototype. Such an approach translates to a requirement that the agent should be equipped with a cognitive ability allowing for comparison of any object $o\in O$ with a prototype $o_c^{★}$ of any category c. Additionally, this ability enables the agent to order objects according to their similarity (or distance) to the prototype. Naturally, the most similar (closest to the prototype) objects are considered as belonging to the category. On the other hand, the least similar (farthest from the prototype) objects are considered as not belonging to the category. This is going to be determined within the agent by a set of ranges assigned to the category by the agent itself during the process of category learning. Consistent with the assumption that the boundary of a category may be fuzzy, our model reflects it by using ranges in order to introduce an area of the mental basic space in which a membership of an object to a category is considered uncertain (understood here as partial rather than as probable) by the agent. These ideas lead to the formulation of category’s model consisting of the following:

Assuming the distance-based approach, perhaps in the simplest but still effective way the category can formally be defined as a triplet: where:

Figure 3 graphically presents a deliberately simplified model of a category with a prototype using a visual notion of the cognitive distance (reflected as graphical distance between points on the plane). The category is defined over the basic mental space $O=\{o_1,\dots ,o_8\}$. The object $o_7$ is indicated as the prototype of the category. Objects $o_1$ and $o_7$ are located in the core of the category and therefore are both perceived as belonging to the category c, although object $o_1$ is not assessed by the agent as fully conforming to the prototype $o_7$. Objects $o_2,o_5$ and $o_8$ are considered by the agent not only as different from the prototype of c, but also as objects with their membership to the category being uncertain. While objects $o_3,o_4,$ and $o_6$ are treated as not belonging to the category c.

This interpretation shows in what way the cognitive experience related to our model of the category with a prototype should be treated as naturally multidimensional, in particular, when it comes to the relationship of individual objects of the basic mental universe O with the category. Such a relation includes both the aspect related to objects’ location relative to the prototype, as well as the aspect of the degree of objects’ membership to the fuzzy boundary of the category. Both aspects need to be adequately addressed in any implementation of an agent to ensure its proper linguistic behavior.

Basic experience related to the agent’s knowledge about the external world is collected in an internal repository of the so-called episodes. The knowledge stored in the episodes relates to two dimensions of the agent’s cognition: direct perception of the state of objects of an external world in which the agent operates, and direct recognition of some semantic language messages produced by other agents (all together treated as a collective teacher) in relation to particular objects and representing statements about membership of these objects to some categories. It means that the basic experience stored in the episodes covers some aspects of physically and socially grounded experience. As a consequence, the functionality of the interface assumed in the proposed architecture (see Figure 2) is required to cover, among others, the following two groups of interrelated actions: at first, recognizing and internally representing actual states of external objects; at second, recognizing messages of a semantic language of communication and then building internal representations of their meaning.

The ability to cope with the social aspects of the external world is a prerequisite for an agent’s competence in any semantic communication, which must always be grounded in a fixed social context, as well as learned in such a context. In our model, we assume two kinds of messages incoming from externally located agents (as a group interpreted as a collective teacher) with each represented by an element from set L containing the following labels:

An important feature of the repository of episodes is that each episode is related to a particular time point, which means that in the model a specific competence of the agent in the processing of the temporal aspects of knowledge representation is assumed. Namely, each episode is treated as being related to a particular time point $t\in T=\{t_0,t_1,t_2,\dots \}$, where for each $i=1,2,\dots$, time point $t_i$ is interpreted as an immediate predecessor of $t_{i+1}$ in linear temporal order. For formal purposes, we will also use the following relation of temporal precedence: ${\le }^{TM}=\{(t_i,t_j):t_i,t_j\in T\wedge i\le j\}$.

Finally, the following definition of an episode is adopted:

From the formal point of view, the concept of an episode just introduced can be treated as an extension of the classic definition of a single-valued and complete information system [61,62]. The part of an episode which is equivalent to a complete information system is used by the agent to represent the result of a particular observation of a certain state of the external world. The extension is used as a collection of other agents’ beliefs about the membership of objects cognitively distinguished in the observed state of the external world to specific conceptual categories. Recognition of other agents’ beliefs is based on observed occurrences of the labels introduced above is-c or not-c.

It is important to note that individual episodes are constructed by the agent in working memory and then are used to update the main repository of episodes (see Figure 2). In order to distinguish individual states of the overall empirical knowledge base at particular time points (given by all collected episodes), the following symbol is additionally introduced:

The following example illustrates the way in which the above concepts are used to represent basic knowledge about the external world, stored internally in the agent. It is based on a deliberately simplified knowledge base, defined under the influence of the work [12] where the main considered objects were $birds$ described by a mutual set of attributes (including attributes: having beak or bill, having wings, dominant color, further in the example denoted by $a_1$, $a_2$ and $a_3$, respectively.

Potential functions of individual episodes within the proposed agent’s architecture can be diverse. The following two are particularly interesting in relation to the processing of autoepistemic membership statements:

The first of them is fundamental as a function that enables the agent to carry out an autonomous process of learning and updating socially valid models of categories with prototypes on the basis of examples of objects’ categorization obtained from individual acts of semantic communication with other agents (that are all treated in this work as a single collective teacher).

This fairly obvious possible relationship between the content of an individual episode and category learning is depicted in Figure 4 related to Example 1.

The main connection between the episode and the learning of categories are the elements of basic mental space O. Namely, in accordance with the assumption regarding the agent’s competence in mental conceptualization of objects in general, each element x in any set $X_t$ must and does have one and exactly one corresponding element $o\in O$. Such an element o plays the role of a conceptual pattern of x. In Example 1, this type of relationship was represented by pairs: $(x_{1,1},o_1)$, $(x_{1,2},o_2)$, $(x_{1,3},o_2)$, $(x_{2,1},o_1)$, and $(x_{2,2},o_8)$. On the other hand, each object $o\in O$ is an element of the universe O over which models of particular conceptual categories are defined, including categories bird and mammal, both stored in the example repository of categories. For this reason, gaining knowledge about relationships between models of external objects represented by elements in sets X and labels indicating specific conceptual categories, assigned by the collective teacher, allows for the agent to first establish, and then update, the internal model of the current social consensus regarding the meanings of the categories. In particular, such knowledge can and should influence the shape of the core, boundary, and outer components of relevant categories.

The second one of the above two distinguished functions, i.e., being a time point-related context for the production of autoepistemic membership statements, is strictly related to the range of semantic meanings of the statements chosen to be considered in this article. Namely, it was assumed in Definition 1 that each symbol $x\in X$, when it is used as a part of an individual autoepistemic membership statement, is an unambiguous pointer to a particular atomic object of the agent’s external world. It means that the assumed commonsense and pragmatic interpretation of $x_{i,j}\in X_t,{ }_{i,j\in \{1,2,\dots \}}$ refers unequivocally to Definition 5 where the result of each cognitive experience resulting in the mental distinction of a particular external object within an observation covering a particular state of the external world is represented by a dedicated pointer that corresponds to that object. Such a pointer is explicitly included in set $X_t$ which is a basic ontological component of the episode internally representing that state of the external world.

This remark explains why each episode, apart from its basic function of representing a certain state of the world, should also be treated as a complex cognitive structure mediating between any description of a state of the external world expressed by the agent in a chosen natural or semi-natural language, and the reality to which the description applies. Taking a slightly different perspective, it can also be said that episodes are elements of representation of the agent’s inherently subjective beliefs about external and observed individual states of the environment.

The following Example 2, again deliberately simplified, extends Example 1 and shows how the second function of episodes should be adopted within the agent’s architecture during natural language production.

In relation to Example 2, the following two supplementary notes are worth being made at this point in the presentation.

At first, it should now be announced that it is the cognitive semantics, reflecting the social consensus of meaning developed for the considered language K, that will determine which subset of the set $K_{/t_3}$ is ultimately used as an adequate linguistic representation of beliefs about the current state of affairs adopted by the agent. Figure 5 shows a possible example choice and some of the main cognitive components involved in making it. Firstly, the objects $x_{3,1}$ and $x_{3,2}$ are mapped onto the universe O in order to then be projected onto models of particular categories. Then, cognitive semantics, taking into account some additional numerical characteristics describing the latter mapping and specified explicitly in further definitions of cognitive semantics, determines the final range of statements representing the considered state of beliefs. As is assumed in Figure 5, such a possible set of relevant statements might be $\{Know(x_{3,1}\in bird),Pos(x_{3,2}\in bird),Know(x_{3,1}\notin mammal),Bel(x_{3,2}\in mammal)\}$, although the range of possible choices is not limited to the given case. The reason will be explained later in this article.

Secondly, in this article we consider a simplified version of the possible pragmatic context within which the considered cases of autoepistemic membership statements are generated. Namely, we establish that the agent’s "centered" attention covers the entire content of the episode representing the current state of the external world and the agent’s goal is to select a complete set of statements representing beliefs related to all cognitively available conceptual categories and to all objects distinguished in this and only this episode. However, a goal constructed in this way rarely occurs in practical situations. Indeed, typical uses of statements being under consideration are usually part of a dialogue involving more than one agent and in such a dialogue the production of a specific statement by a specific agent is usually a response to a query addressed to this agent. Possible examples of such questions are Does this object belong to category c?, What is $x_{3,1}$?, etc. The introduction of such or similar detailed and specific pragmatic contexts can and in fact leads to a significant expansion of the range of symbolic representations used. For example, in the case of the English language, it is enough to note that external (symbolic) references to the object $x_{3,1}$ appearing in $Episode\left(t_3\right)$, with the additional assumption of shared attention of agents participating in a specific dialogue, may take the form: this object, that object, it, etc., instead of object $x_{3,1}$ adopted in this article. Moreover, to be complete, such a list should also include extensive descriptive pointers to the object $x_{3,1}$, e.g., the object that is located here/there/next to, etc. The architecture we have considered has been deliberately simplified and does not include conceptual tools that, at the level of the agent’s internal knowledge bases, would allow for representing more detailed and specific contexts of the potential use of autoepistemic membership statements and, consequently, variant cognitive semantics related to beliefs about the belonging of currently observed objects to categories with prototypes. However, it is highly probable that changes to the proposed architecture that would enable the representation of more detailed and more specialized statement generation contexts would consist solely in extending the proposed architecture rather than eliminating or significantly changing the form of its already proposed elements.

Following a commonsense claim stated by Dennett [63] that “exposure to x—that is, sensory confrontation with x over a suitable period of time—is the normally sufficient condition for knowing (or having true beliefs) about x”, we have decided to perform a process of category learning based on a series of such exposures, namely the agent’s interactions with the external world, each represented by a particular episode and, among others, containing both positive (c confirmed—labeled as is-c) and negative (c denied—labeled as not-c) learning examples, as was introduced above. Therefore, in forthcoming parts of this article, the input collection of the learning examples to be used in acquiring a specific category c will be a multiset denoted by $Ex{p}_c$, defined over the universe $O\times \{is-c,not-c\}$, and represented as in the following formula: where:

A particular method by which the content of $Ex{p}_c$ can actually be extracted from an available collection of episodes depends always on practical context and rational choice criteria for learning data.

This section builds upon a strategy for learning categories with prototypes, which was in a brief manner presented in [64] to show how categories can be computationally and relatively consistently with intuition extracted from collected learning experience. The agent starts with the learning experience related to a particular category c aggregated into the above introduced multiset $Ex{p}_c$ (see Formula (9)). It intends to derive a model of a category with a prototype c, that is, the category’s prototype, core, and boundary. Following the model of category with prototype introduced in Section 4.3, the algorithm goals are, in particular, to find a prototype $o_c^{★}$ and to determine two related radii ${\tau }_c^{+}$ and ${\tau }_c^{-}$.

The basic ideas behind the algorithm are as follows: at first, to use an adopted basic mental space enriched with a specific distance or similarity function f (see Definition 4); at second, to determine candidates for prototype; at third, to analyze all the candidates according to some criteria; and at the end, to choose the prototype, if it exists. It is generally expected that the prototype should be surrounded by a core of the category with the currently largest possible radius, and contain a substantially large part of the supporting (positive) examples of the learning data. In a case where no candidates fulfill such requirements, the procedure should fail which means that the current experience does not support building a model of category c as a category with a prototype.

The algorithm iterates over objects $o\in O$ occurring (mentioned) in the learning experience. Therefore, to make further presentation more convenient, some additional notions (subsets) are derived from $Ex{p}_c$:

An idea behind the method for category formation [64] is to start with a set of suitable candidates for a prototype of a category for which the agent is trying to build an internal model. Omitting the whole philosophical discussion related to whether a prototype should be a reflection of a particular existing object the agent has ever observed in the past, or whether hypothetical objects from the whole mental space are also allowed, we skip to the conclusion by saying that the prototype should be, in a way, a central element of a multiset containing learning experience positively supporting a particular category, namely a multiset ${\widehat{E}}_c^{+}\left(Ex{p}_c\right)$.

An algorithm presented in the next section assumes a particular set of candidates for prototype as being extracted using a function $extractCandidates$. In a majority of practical contexts, candidates are chosen based on certain optimization criteria. When the basic mental space is equipped with a distance function f, usual cases of candidates $o_c$ for prototype $o_c^{★}$ are given as follows:

Obviously, if f is a similarity function, the Formulas (13) and (14) should be changed by replacing $argmin$ with $argmax$.

It is important to note that a frequent association of a particular language label to an object o is not enough to set it as a prototype of category c. It is, in particular, required that there is a region around a chosen o (in the sense of a similarity or distance function-based neighborhood) where an association with a particular concept is not ambiguous, that is, it has not been contested within the learning experience by labeling nearby objects by "not-c". Therefore, it is important to further verify the validity of extracted candidates. In consequence, all the candidates (usually there is just one but formally there might be more than one element $o\in O$ satisfying the above optimization criteria) are further passed to an algorithm (described in the upcoming section) in order to verify their feasibility and to either discard them or to choose one of them as the final prototype.

The category learning steps discussed above are integrated in the form of a strategy which is presented below as Algorithm 1. The input data is given as a learning set $Ex{p}_c\in \widehat{\Pi }\left(T^c\right)$ and the algorithm consists of the following:

An exhaustive list of potential adjustments and (both interpretation-related and computational) modifications to the strategy introduced above can be found in [64].

We can give the following extended example of how the strategy works:

An important question arises about the possible complexity of the actual implementation of the presented strategy. Theorem 1 formulated below concerns this issue:

The Theorem 1 shows that the computational complexity of the Algorithm 1 can be polynomial with respect to the number of objects observed by the agent in all episodes ${\displaystyle \sum _t\left|X_t\right|}$ and the number of attributes describing them $\left|A\right|$, provided that the following conditions are met:

If any of the above conditions is not met, then the complexity of the strategy becomes exponential and therefore might be relatively hard to be effectively applied in practice. The complexity of $extractCandidates$ seems to be the key parameter, in particular because, at the design level, in many implementations it may involve the need to solve the choice problem in a mathematical space. As has long been proven, the latter problem usually belongs to the class of tasks with exponential computational complexity, depending mainly on adopted choice criteria, but at a deeper level on the structure of objects and related metrics (distance/similarity function f). A sketch of a general theoretical structure from which detailed implementation models of $extractCandidates$ can be derived, and then within which the analysis of the complexity of a selected implementation model can be carried out, can be found, for example, in chapter 3 of [65]: Consensus as a Tool for Conflict Solving.