This paper deals with the processing of TIL-Script constructions. TIL-Script constructions are a computational variant of the Transparent Intensional Logic (TIL) constructions. In this paper, two main directions are addressed. The first area is the use of TIL-Script in supervised machine learning with a symbolic representation of facts in a search for explications of atomic concepts. Subsequently, the paper discusses the modifications that were necessary for use in the spatial data processing. The paper describes the theory necessary to understand TIL theory, Supervised machine learning, formal conceptual analysis, and spatial data processing issues specified in the TIL-Script language.
This paper outlines the use of Transparent Intensional This section briefly introduces the Transparent IntenLogic (TIL) constructions with a focus on Formal Con- sional Logic system. ceptual Analysis (FCA) and supervised machine learning. The paper is divided into two parts. The first part contains the use of machine learning and FCA to find relevant textual sources of information. The second part contains the modification of supervised machine learning to process constructions that represent spatial data.
TIL is a partial, typed hyperintensional -calculus of partial functions with procedural semantics. Expressions of natural language encode algorithmically structured procedures as their meaning. These procedures produce extensional or intensional entities, or even lower-order procedures, as their products. In the early 1970s, Pavel The following section summarizes the current devel
Tichý defined six kinds of such procedures, which he opments in the use of TIL and, consequently, TIL-Script coined TIL constructions as the centerpiece of his system; in supervised machine learning.
see [
The paper is structured as follows. In the Chapter 2, The TIL distinguishes between two types of constructhe reader is introduced to the basics of TIL. This chapter tion: atomic and molecular constructions. These conis taken as a summary of the most important characteris- structions are Trivialization and Variables. The operatics and definitions that are relevant for understanding tional meaning of Trivialization is similar to the meaning the paper. However, since the language of TIL construc- of constants in formal languages or pointers in programtions is quite complex to process by a computer, in the ming language terminology. Trivialization supplies an Chapter 2.1, we introduce the TIL-Script language, which is a computational variant of TIL, and which is used in machine processing. In the Chapter 4, we will discuss the basics of formal conceptual analysis theory and the use object O without mediating any additional procedures.
We write the trivialization of an object O as ′ . The second atomic construction, Variable, produces objects depending on its evaluation. The variable v-constructs of this method to find relevant information sources. Suban object. sequently, the Chapter 5 discusses the issue of working The following constructions are molecular. Compowith spatial data. 1 …
] corresponds to an application in calculus. It is a procedure for applying a function to an ordered tuple (if any) produced by the 1 … procedure. The -composition constructs the value of the function on the arguments of 1 … if the function is defined on the arguments of 1 …
. However, if not defined, then
v-constructs nothing. This situation can also occur if Closure [ 1 … ] corresponds to a -abstraction in a native to TIL-Script (Indiv, World, Time). Each TIL con -calculus. It is a procedure that -constructs a function struction has an equivalent in TIL-Script, but with a difby abstraction over the values of the variables 1, … , . ferent syntax. For comparison, here are some examples: The closure is never -improper for any valuation, since it always -constructs a function.1 Now we define Double • Trivialization in TIL: 0 → Trivialization in TILexecution, Single execution is not relevant to us now. The Script: ’C Double Execution will execute the given construction • Composition in TIL: [ 1 … ] → Composition twice, thus reducing, for example, the mode of occurrence in TIL-Script: [ 1 … ] of the display construction to the mode of the execution • Closure in TIL: [ 1 … ] → Closure in TILconstruction. If -constructs a construction, and - Script: [\1 … [\ ] … ] constructs an entity , then -constructs . Otherwise, is -improper in that it does not produce anything. An example of a natural language sentence captured
The TIL ontology is organized into a branching hi- in TIL and TIL-Script: erarchy of types built on top of the base. It is a two- • Sentence: Charles counts 3 + 5. dimensional type hierarchy. The first ”horizontal” dimen- • TIL: [ ′ ′ℎ [ ′+ ′3 ′5]] sion increases the degree of molecularity, i.e. it starts • TIL-Script: at the level of atomic objects (base objects) and builds a [\ [\ [ ′ @ ′ℎ ′[′+ ′3 ′5]]]]. hierarchy of functions above them by folding functions into more and more complex functions. The second, ”ver- There is an EBNF grammar for TIL-Script. tical” dimension increases the order of construction. At its beginning are entities that are not constructions, followed by constructions that construct non-constructions, 3. Supervised machine learning etc. At the base level of type hierarchies, there are, from an algorithmic point of view, nonconstructive entities belonging to types of order 1. Given the base of atomic types ( -truth values, -individuals, -time instants/real numbers, -possible worlds), the induction rule for function creation is applied: where , 1, ..., are types of order 1, the set of partial mappings from 1 × ... × to , denoted by ( 1... ) is also an order 1 type. Constructions that construct entities of order 1 type are order 1 constructions. They belong to the order 2 type denoted by ∗1. This type, together with atomic types of order 1, serves as the basis for the induction rule: any set of partial mappings, type ( 1... ), involving ∗1 in their domain or range is a type of order 2. Constructions that construction entities of type order 1 or 2 are constructions of order 2. They belong to type of order 3 denoted by ∗2.
Any set of partial mappings involving ∗2 in their domain or range is a of type order 3 and so on ad infinitum.
In [
Here, we briefly summarize the basic characteristics of this approach.
Supervised machine learning is a subcategory of machine learning that uses training data partitioned into positive and negative examples of a concept to be learned.
These data are described by a set of input and output attributes. There is an unknown functional dependency f between the values of the input and output attributes.
The goal of learning is to approximate the unknown functional dependency f with the functional dependency h called hyphotesis. The hypothesis is obtained by observing the values of the input and output attributes of the training data. The correctness of the hypothesis is tested on test data for which only the input attribute values are known to the learner. The hypothesis is correct if it correctly predicts the values of the output attributes of the test data.
Supervised machine learning is most commonly used 2.1. TIL-Script to solve two types of problem: regression and classificaTIL is not suitable for computer processing due to its com- tion. Regression is a problem in which the values of the plex notation; therefore, we are using its computational output attributes are elements from a continuous range variant, TIL-Script [13]. TIL-Script ofers standardized of numbers. For example, when predicting the price of notation, base of types, and form notation using ASCII a diamond based on its properties. Examples of regrescharacters only (letters of the Greek alphabet, indices, etc. sion algorithms are linear regression, logistic regression, or cannot be written using ASCII characters). Compared polynomial regression. In classification , the output values to TIL, TIL-Script has a broader base of types, making are discrete, and the model matches the input examples construction more easily handled compared to TIL. Some with the output categories. The classification problem of the newly added types are well known for common is, for example, the recognition of trafic signs in the improgramming languages (Bool, Int, Real) and others are age data. Common classification algorithms are Support
each tuple 3.1. Winston Patrick Winston’s algorithm [14] presents learning using positive and negative near-miss examples. A near-miss example represents a negative example that difers from a positive example in one important diference. It is a supervised algorithm; therefore, each input example is labeled as positive or negative, and the model (hypothesis in the learning process) is modified based on observations of the values of the input and output attributes of these examples. The model is modified using induction heuristic functions. The heuristic functions are requirelink, forbid-link, climb-tree, enlarge-set, drop-link and close-interval. Winston represented the examples graphically by a semantic network in which the attribute values of objects are represented as nodes of the network, and the relations between them (edges of the network) are called links.2 The heuristics are described as follows. 1. Compare the hypothesis model and the positive
example to find the diference. 2. For each diference is verified: a) If the link in the model binds to a value diferent from the value in the example, then it is verified: i. If the attributes in which the model and the example difer have the most specific generic value, then climbtree is used. ii. If the attribute values are inconsis
tent, drop-link is used.
iii. Otherwise, enlarge-set is used. b) If there is a link in the model that is not in
the example, drop-link is used. c) If the model and the example difer in a numeric value or an interval of numeric values, close-interval is used. d) If none of the above can be applied, the example is ignored. • require-link: Used if the model contains link, which the near-miss example does not. The given link is marked in the model as MUST-BE (must be). • forbid-link: Used when there is a link in the near-miss example that is not in the model. The given link is inserted and marked as MUST-NOT
BE (must not be) in the model.
• climb-tree: Used when we want to generalize a
too specific model. Based on the positive example,
we generalize an attribute value that difers in the
model. The most common general value of the
attribute of the model and the example found in
the ontology provided by the teacher replace the
value in the model.
• enlarge-set: Used if the ontology is not provided
or the values in the example and model do not 3.2. Natural Language Processing
share a common most specific value in the
ontology. In this case, the values are concatenated into This work is based on the use of TIL in natural language
a set of values. processing, described in detail in [
Winston defines two main methods, Generalization and Specialization, in which heuristics are applied to the model. 2For example, if a cube is white in color, there would be two nodes in the graphical representation, one for the object cube and one for the attribute value white. These nodes would be connected by link has Specialization is triggered using near-miss examples.
1. Compare the hypothesis model and the near-miss
example to find a significant diference. 2. If a significant diference exists, then proceed: a) If the model has a link and the near-miss example does not, then require-link is used. b) If the near-miss example has a link and the
model does not, forbid-link is used.
c) Otherwise, the example is ignored.
Generalization is done with positive examples. 3A concept in TIL terminology is a closed construction. 4Carnapian explication, used in this paper, is the process of refining a vague or inaccurate expression into an adequately accurate one.
For simplicity, we refer to the refinement of a given expression as an explication. 3.2.1. Modified Winston’s algorithm In order to extract concept explications from text sources, Winston’s algorithm had to be adjusted. The input of the algorithm (examples) is formalized natural language sentences that mention the concept to be explicated. These sentences are formalized into TIL constructions. The result of the algorithm is a molecular TIL construction that describes a simple concept. In addition to the generalization and specialization methods, the algorithm also includes a refinement
method that inserts new constituents into the molecular construction.
Natural language sentences often contain only partial Using FCA, we search for a concept that is represented by a given set of properties or attribute values.
FCA [15] was introduced by Rudolf Wille in 1981. It is a popular technique used for data mining, software engineering, knowledge processing, machine learning, and many others. FCA studies the relationships between objects described by a set of attributes and their hierarchical grouping based on common attributes.
We now describe FCA and aspirant ordering using
formal definitions presented in [
Definition 1.
Let (, , ) be a formal context, then tion as constituents to the explication in a refinement protion. For this reason, a new heuristic method Concept- ⊆ × , introduction was proposed, which adds partial informa- , (, ) ∈ } information about a given simple concept. The exam- (, , ) = {(, )| ⊆ , ⊆ , ples used by Winston always contain complete informa- is a set of all formal concepts of context (, , ) ↓ = , ↑ = } where
Generalization contains heuristic functions General- formal concepts’ intents. cess. On the basis of the negative examples, the Negativeconcept method is triggered, which adds new constituents to the explication in a negated way. This method is used to distinguish explications of similar concepts. Generalization replaces the values of the constituents with more general values. concept, Disjunctive-concept and Close-interval. First two heuristic functions has similar functionality. They generalize values in constituents of the model. If the supervisor provides an ontology of values, and the positive example difer in value from the model,
the value in the model with the most specific general value of values in the model and example from ontology. If the ontology is not provided, Disjunctive-concept generalize the value in the model with an union of values in the model and example.
If the model and example difer in numerical value Close-interval generalize the model’s value with the numerical interval spanning both values.
The algorithm is described in detail in [
One of the main focuses of this work is the application of Formal conceptual analysis (FCA) to the explications obtained, aspirants ordering and the implementation of both methods.
In this section, we discuss a procedure for finding a
suitable atomic concept using explications of simple
concepts and FCA.5 This procedure has been published in
[
Definition 2. a in (, , )
Concept aspirants of the set of attributes is a set () =
⋃=1 , where is the extent of a concept (, ) ≠ (, ), ⊆ , ⊆ concept aspirants of the set of attributes a is a union of all formal concept extents where a is a subset of a particular . Namely, (, ), ⊆ , ( (|( () .
Definition 3.
Let () a set of attributes a, let () where ⊆ , i.e.: () = {( be a set of concept aspirants of be a set of concepts (, ) , ( )↑)|( , ( ↑ ) ) ≠ , ( ↑ ) ) ∈ (, , )} . Then x ⊑ y is in relation of aspirant ordering if (|( )↑|) ≤ )↑|), , , ∈ (), ( , ( )↑), ( , ( )↑) ∈ Definition 4. to the definition
Let ((), ⊑)
be an ordered set according
appropriate concepts.
FCA is used to obtain the set of all formal concepts and form a conceptual lattice over explications. The conceptual lattice captures the hierarchical ordering of the explications. On the basis of the set of all formal concepts, we find the so-called
Aspirants is the union set of all intents of formal concepts in which a set of selected attributes occurs. We order this set according to the definition of 3. If the set is in the relation Aspirant Ordering, then its maximal element is the most appropriate concept describing the search object. 4.1. Program implementation The entire algorithm for FCA and Aspirant Ordering is attribute values that occur in the explications obtained. implemented in Java without using third-party libraries 5For example, if we know some basic characteristics of an object for which we do not know the name. that address the issue. The formal context, which is the FCA input, is displayed in the code 1 and is obtained from the input CSV file. Each row of the formal context represents one object, and the values 1 or 0 in the columns indicate whether the object has the attribute. The next input argument is the attributes based on which the most appropriate concept will be searched.
First, we need to perform a complete FCA according to the definition of 1. We are looking for sets of objects that share sets of attributes. Each formal concept corresponds to a maximal submatrix whose elements all have the same attributes equal to 1. However, objects that form a formal concept do not need to have identical set of attributes, e.g., an object 2 and an object 7 can form a formal concept 1 = ({ 2, 7}, { 7}) even if 7 has attributes that 2 does not. The FCA algorithm is defined as follows: 1. For every possible set of objects: a) For each attribute: i. Check if each object of the currently examined set has the given attribute: A. If so, the attribute is added to
the set of common attributes.
B. If not, the attribute is ignored. b) Check if a formal concept with an identical set of common attributes already exists: i. If so, compare the number of objects of the formal concept and the currently examined set of objects: A. If the currently examined set has more objects than the existing formal concept, the existing formal concept is replaced by a new one including more objects.
B. If the existing formal concept has more objects, no change is made. ii. If not, a new formal concept is created with the currently examined set of objects and set of common attributes.
If we have a complete FCA, then the algorithm for Aspirant Ordering can start. In this particular example, the input will be 1 and 2, for which we want to find the most suitable concept that is described by the attributes given. We first look for formal concepts in which both input attributes occur at the same time; formal concepts are listed in code 3.
In the next step, we get the union of all extents from the previous step; as shown in code 4. We get all objects that have both attributes that we are looking for.
Next, for each of the retrieved objects, we search for its intent, as shown in code 5. This gives us a set of objects with all their attributes, where one of them is the most appropriate concept to be searched for. This set is called Concept Aspirants by the definition 2.
In the last step, we sort the set of concept aspirants according to the definition 3 and select the maximum element to obtain the most suitable concept described by the input attributes.
In this section of the paper, the issue of knowledge base representing space in multi-agent systems is discussed.
Using natural language processing, TIL, and previously
described machine learning methods, we create a
topological representation of a map that an agent can use to
navigate in space. The first outline of this approach is
proposed in [
The input for the construction of the topological map representation is a set of ordered sentences formalized using TIL-Script constructions describing the agent’s journey through the environment (in this particular case, a path through a city). Each sentence may contain information about who went where, how, from where, through what, etc., but some information may sometimes be missing or incomplete. We assume that the diferent parts of the journey are described sequentially, and hence some missing information can be obtained from the previous sentences. However, once a representation of one path is constructed, its form may not be final but may change if, for example, the same path is described in more detail by another agent; hence, we are concerned not only with the construction of the path representation but also with its modification. Part of this paper deals with the problem of knowledge base representing space in multi-agent systems.
The input to the algorithm is an ordered set of natural language sentences formalized into TIL-Script. These sentences describe the journey of some agent through the environment (in this particular case, a journey through a city). The sentences contain information about who, how, from where, to where, through what, etc. traveled. However, not all sentences contain complete information. The missing information is filled in from previous sentences in the preprocessing of the input, as it is a sequential description of the journey. The machine learning algorithm then creates a molecular construction that describes the agent’s journey from the preprocessed input. By combining the diferent paths of the agents with the same algorithm, we then obtain a topological representation of the space in which the agents traveled. In this paper, however, we focus only on the creation of a single agent path.
The heuristic methods and algorithm described in Section 3.2, but modified to handle path descriptions, are the basis for creating space representations. The fundamental diference from the application of the algorithm already mentioned is that we are now not specifying a simple concept, but building a molecular construction describing the agent’s path.
To handle path descriptions, we use the class of socalled motion verbs (which contains e.g. the verbs go, run, ride, cross, turn, etc.). Verbs in this class bind certain parts of sentences to each other by valency. The valency bindings for individual verbs are described us- 5.1. Path Preprocessing ing valency frames. The valency frame provides information on which complements are valence-bound to a particular motion verb [16]. For example, the verb go is valence-bound in sentences by complements written with a functor, such as ACT (who went), DIR1 (where he went), DIR2 (which way/what he went), DIR3 (where he went), MANN (how).
In [
school through the city center. • Direction - from where [DIR1] - Paul walked quickly home from school through the city centre. • Direction (direction) - which way [DIR2] - Paul walked quickly home from school through the city centre. • Direction (direction) - where [DIR3] - Paul walked quickly home from school through the city centre. • Manner (way) [MANN] - Paul walked fast home
from school through the city centre.
• Extent [EXT] - After 100m he turned right.
Using the valency structures of motion verbs, we get
a description of the journey. The path locations,
identiifed by directional functors (DIR1, DIR2 and DIR3), are
the basic information for the construction of the path
description. The path representation is defined in [
= {|( ′ 1 or ′ 3 ) and are constituents of B } and let = {| is a constituent of C } ⧵ then is a set of edges and is a set of nodes.
and let [ 1] be an edge. Then is a place, , are functors, and , , 1 are values.
2. Let , be connections, let be node then → → is a connection.
connection then → → be a path.
Definition 9 (same path). Let → → and → → be paths in model and positive example respectively, let = → ... → then if [ ′ 2 ] in (model) = [ ′ 2 ] in (positive example) then both paths represent the same path.
5.2. Heuristic application
scribed in the following sections are applied in diferent cases. Before deploying the heuristics, we need to check whether the model and the example capture same paths as defined by definition 9, and select the appropriate heuristic to apply based on the result. If they are Same Paths, the Path Update heuristic is applied. Otherwise, Path Introduction is applied. The description of the algorithm for checking Same Paths is as follows: 1. Check if DIR1 locations are the same in the model and example: a) If not, the algorithm terminates, and they are not same paths.
b) If so, the algorithm continues. 2. Check if the DIR3 locations in the model and example are the same: a) If not, the algorithm ends and they are not same paths.
b) If yes, the algorithm continues. 3. Check if all nodes in the model and example have the same DIR2 locations: a) If not, the algorithm ends and they are not same routes.
b) If yes, the algorithm continues.
4. All conditions are met and they are a same paths.
Subsequently, a specific heuristic is already applied. 5.3. Path Introduction After passing all sentences through Path Processing and checking whether they are same paths or not, we can start building the actual topological representation of the map from these sentences. First, we focus on the Path Introduction heuristic. This heuristic works with two constructions: the existing path model and an example representing a sub-path. Path Introduction adds a new path to the model. We will explain the whole process using an example.
The heuristic algorithm proceeds as follows: 5.4. Path Update The second heuristic for building the topological representation of the map is Path Update, which modifies the existing path in the model. The heuristic also works with a model and a positive example and is applied when both paths represent the same path. The positive example then describes the given path in more detail than is captured in the model, so we use the information from the positive example to refine the model.
Let us have the input data displayed in code 10. Both paths have the same origin and destination and also identical DIR2 locations, so Path Update can be deployed.
We refine the model by removing the entire DIR3 node explication, since here we have to link to the new location from the positive example. We then merge the model and positive example explications and insert the previously removed DIR3 node explication at the end. The resulting model is displayed in the code 11.
In this paper, we described the TIL-Script construction processing used for two purposes.
In the first part, we have described the method of ifnding an appropriate concept based on properties and attributes’ values known by the user. The method exploits Formal Conceptual Analysis applied on the explications of atomic concepts contained in textual sources. The method ofers appropriate concepts which fall under properties and attributes’ values provided by the user.
In the second part, we described heuristics that obtain descriptions of agent’s journeys from descriptions in natural language. Such a description can be used as a navigation tool in complex multi-agent systems environments.
Both methods in the first and second parts of this paper are based on the same supervised machine learning algorithm that processes TIL-Script constructions as examples. The algorithm is adjusted for its purpose. Acknowledgements This research has been supported by Grant of SGS No. SP2022/123, VŠB - Technical University of Ostrava, Czech Republic, “Application of Formal Methods in Knowledge Modelling and Software Engineering V” and by CZ.02.2.69/0.0/0.0/18_054/0014696 Development of R&D capacities of the Silesian University in Opava and also supported under the Student Funding Scheme, project SGS/8/2022.
Mass.: Addison-Wesley Pub. Co., 1992. ISBN 02-0153377-4. [15] Ganter, B., Wille, R.: ”Formal Concept Analysis: Mathematical Foundations”. 1st ed., Berlin: Springer, 1999, ISBN 978-3-540-62771-5. [16] Fischer, K., Ágel, V. Dependency grammar and valency theory. In: The Oxford handbook of linguistic analysis; 2010, p. 223-255.