Abstract
Natural Ontologies are presented in this work as a useful tool to model the way in which concepts are organized inside the human mind. In order to be compared, ontologies are represented as matrices and an elastic matching technique is used. For this purpose, a distance measure called Modern Fréchet is proposed, which is an approximation to the NP-Complete problem of elastic matching between matrices. An applied case of study is presented in which human knowledge is compared among different groups of people in the Computer Science domain.
Introduction
Comparison is a very relevant phase during ontology processing, as several crucial decisions are made based on some type of comparison. When the human mind performs comparison, the first thing it does is to identify the attributes or descriptive features of the objects involved in the comparison, in order to observe the similarities and differences between them. This strategy is carried out naturally in human beings; however, for a computer this is not a simple task—computers need a mathematical tool for performing quantitative measurement which enables them to actually make a comparison. Therefore, it is a common practice to represent ontologies in an attribute-value description language as patterns and then, following a pattern recognition approach, propose a similarity function.
Following this structural and feature-based approach, several works have been proposed. [1] proposes clustering synsets and then measure the synonymical similarity of concepts; [2] utilizes structural information of ontologies to determine their corresponding entities; [3] presents a graph-derivation-representation-based approach for semantic measurement, which captures structural semantics of ontologies.
An alternative, presented in this paper, is to perform a comparison, not by considering only particular features, but taking into account all available data, i.e., a global comparison. In order to obtain ontologies suited for such comparison, the Natural Semantic Networks technique is proposed. This techinque, originally proposed by [4], has been widely used with favorable results in several studies within different knowledge domains [5–8]. The output resulting from this technique is a Natural Ontology represented as a matrix. Although much work has been done for the extraction and storage of ontologies of human knowledge [9], there are no other proposed methods to quantitatively compare Natural Ontologies considering all information globally.
In this paper we present an approximation to the open problem of elastic alignment of matrices. This problem directly compares the information of numerical matrices and seeks to quantify the effort to find the minimum distance between them. The elastic alignment itself is an NP-Complete problem. In this proposal, the goal is to quantify the effort of aligning the matrices, as opposed to identifying a fine graded concept alignment.
With this work the aim is to contribute with: (1) a method for canonical comparison of ontologies, that is, the comparison with different parameters of an ontology against a group of ontologies; (2) the comparison of human knowledge obtained using Natural Ontologies; and finally, the proposal of a new technique to perform the direct comparison between pairs of matrices using a distance technique called Modern Fréchet.
For that purpose, the following steps are followed:
Finally, in Section 6 conclusions are drawn.
Ontology elicitation
Ontology elicitation refers to the process of creating ontologies by applying individual questionnaires to selected people asking them to define concepts of a certain domain. The result of this process is the creation of a Natural Ontology.
The process consists of six steps that can be observed globally in Fig. 1. A relevant feature of this process is that it can be applied within any knowledge domain to obtain natural ontologies. Particularly, in this work it will be used to obtain ontologies in the Computer Science domain.
The construction process of Natural Ontologies.
Here the method to obtain natural ontologies within a certain knowledge domain, from instruments answered by test subjects is described. This methodology was originally proposed by [4].
Steps 1 and 2 - Define the Test Group and apply the instrument
The instrument refers to a survey questionnaire, which must be answered by a group of 30 or more test subjects. These subjects should belong to the same knowledge domain (biology, medicine, computing, etc.). According to [10], 30 test subjects to capture the knowledge of a group.
The content of the protocol is divided into two activities:
In this way, for each domain group that is required, 30 instruments will be answered. Concept-stimuli must be carefully selected: they should not be composed of isolated words only, but of words that could be given as defining concepts, aiming to create a network [10]. Each concept has room for 15 definers but the subject is allowed to give between 10 and 15 defining words per concept. In this work, the designed instrument has been desgined to have 18 concept-stimuli in the Computing domain for the concepts listed in Table 1. Each of these concepts must be defined by the subjects using 10 to 15 defining words.
Concepts used for the computer knowledge domain protocol
Concepts used for the computer knowledge domain protocol
Once the instruments are answered, four main measures are computed as a help for the analysis of natural semantic networks. These measures will be used throughout the following sections.
Semantic weights for the number of definers obtained
The
The
Knowledge elicitation using natural semantic networks originally used |SAM|=15 to limit the number of definers that are taken into account. Unlike the original work of [12], this work considers the use of more definers due to two important reasons: (1) computing power is not a limitation as it was in its time when the work of Natural Semantic Networks was first published, and (2) because the semantic network is enriched by using more defining concepts, as all relations that can be formed between all definers are analyzed [10].
Once the instruments have been answered, they must be transcribed to a computer. During this process of transcription some errors of spelling and semantics are manually corrected.
From each concept-stimulus a list of defining concepts with their corresponding rankings is obtained.
All the defining-concepts that every test subject provided to the first concept-stimulus is listed, then the same is done for the second concept-stimulus and so on, until completing all the concept-stimuli. This list of defining concepts for each concept-stimulus is variable and usually consists of 100 ∼ 200 defining-concepts.
Step 4 - Counting of defining-concepts
The complete list of defining-concepts of a single concept-stimulus is taken and a table is made. This new table has the following format: the list of defining concepts that all subjects provided on the same concept-stimulus can be found in the first column, as shown in Table 3. In the last column of this table the TMV of each defining concept is listed.
Table for registering answers from the instruments.
Table for registering answers from the instruments.
The first row of the table contains a number from 1 to 10, indicating the possible rankings that test subjects can assign to a particular defining concept—assuming a value of J = 10. A value of one is added in the column corresponding to the ranking assigned to a defining concept.
Let us elaborate this with a small example. Table 4 shows an extract of the instruments for the concept "structure" that we will use to illustrate this process. For the first defining concept “data”, subject 1 assigned a ranking of 1, while subject 2 assigned a ranking of 2 and subject 3 a ranking of 2. For subjects 2 and 3, the granted ranking was the same, so that it will be counted with a frequency of occurrence of 2.
Defining concepts by three subjects for the concept "structure"
It is probable that there are unique defining concepts that are used by a single subject (i.e., not repeated between subjects); in that case, a frequency of occurrence of 1 indicates that the definer was chosen by only one subject. These definers also form part of the semantic information and are added in the TMV.
Then, this information is registered as shown in Table 5.
Registry of definer’s occurrences for "structure".
Once this procedure is performed, the M-value of each defining concept is obtained and the TMV is calculated for each row by adding up these M-values. See Table 6.
Definers’ frequency of occurrence with semantic values
Definers’ frequency of occurrence with semantic values
It should be noted that for this example, ranking values range from 1 to 10, however, this range may vary depending on the subjects. If a single subject wrote 15 defining concepts for at least one concept-stimulus, the ranking range should have values from 1 to 15, and thus the table should show rankings from 1 to 15.
With the previous procedure semantic weights are computed for the defining concepts for each concept-stimulus. This process is repeated for all the concept-stimuli presented in the instrument, creating a table like Table 6 for each of them.
The next step is to obtain a global matrix for the whole group, that is, the defining concepts of all concept-stimuli are joined in a single table. An example is shown in Table 7.
Global table of semantic values for concept-stimuli
Global table of semantic values for concept-stimuli
The resulting matrix can be visualized as a graph where the horizontal axis represents the concept-stimuli (defined concepts) and the vertical axis represents the defining concepts, see Fig. 2. Semantic weights are represented in different colors, using red for the highest, and blue for the lowest.
Matrix representation of an ontology.
Once that knowledge of a group of subjects has been elicited, and it is represented as a matrix, a comparison mechanism is needed. The conventional analysis for the measurement of similarity is through the selection of those attributes (properties) that are considered important or relevant. However, making an appropriate selection is a very difficult task, in addition to this, there is always loss of information in the original data by virtue of a discarding process [13]. The research challenge is to develop procedures without making such selection, but to use techniques that allow all available information to be used on the entities involved, in this case they are numeric data matrices.
There are many ways for comparing two matrices. The simplest techniques are based on distance measures in I R2 (See Section 3.1); more complex techniques are those based on measuring image similarity indices (see Section 3.2). Finally, we focus on techniques that perform elastic comparison in I R2, called 2DW (Section 3.3).
I R2 measures
For comparing two matrices, let A and B be numerical data matrices, then d a distance function such that d (A, B) = k, where k belongs to I R.
Other measures are Manhattan Distance, which performs fewer operations; Supreme Norm; the Chord Distance between two vectors x and y, that is the distance measure between the projected vectors of x and y to a unitary sphere; and Spearman rank coefficient.
Several indices have been used to measure image similarity [15]. Their original purpose was the evaluation of the quality in the spectral fidelity in images. However, they can be used for comparing matrices of completely different origin. Proposed indices are bias, correlation coefficient, difference in variance, ERGAS (Erreur Relative Globale Adimensionnelle de Synthèse—dimensionless global relative error of synthesis), image entropy, universal image quality index, RASE (Relative Average Spectral Error), and RMSE (Root Mean Squared Error), one of the most popular. See [15] for a definition on these indices.
Elastic matching
Elastic Matching (EM) has been used in various problems, such as face recognition, fingerprint recognition, medical image analysis, computer vision, among others. It is a technique that has generally given good results. Formally speaking, EM is defined as an optimization problem with respect to an element-element mapping, linear or non-linear [16]. In other words, EM measures the effort needed to adjust A on B, where A and B are two matrices. EM optimizes the alignment problem in several dimensions, 1D, 2D, 3D, etc., for this work an alignment is done in two dimensions, also called 2-Dimensional Warping (2DW).
Most of the elastic comparison techniques can be found within the framework of solving the task of handwritten characters recognition [17]; although mainly the efforts to solve this task are limited to obtain predefined characteristics of the images of characters, albeit they do not make a global comparison.
Techniques that perform a 2D elastic comparison for the task of recognizing handwritten characters can be divided in parametric and non-parametric. For the sake of convenience, the classification of 2D elastic alignment techniques proposed by [17] is reproduced in Fig. 3. The interest of this research is to focus on the non-parametric, discrete and constrained techniques. That kind of functions can be optimized using the Dynamic Programming technique.
Classification of 2D elastic alignment techniques for recognition of handwritten characters (Reproduced from [17]).
A commonly and widely accepted technique is the monotonic and continuous 2DW function proposed by [18]. Unfortunately, the optimization of this function is an NP-hard problem [19]. Even if matrices are small (20x20), it is impossible to obtain a globally optimum value for 2DW [17].
Modern Fréchet (MF) is the name of the matrix comparison technique that has been developed in this work. It is based on Dynamic Programming, where a global optimal solution is provided. MF is an elastic measure between data matrices that was named after Fréchet’s distance. The distance computed using this approach is invariant to deformations and arises due to the lack of techniques that allow direct and global comparison of matrices such as those provided by natural ontologies. Modern Fréchet is explained in detail in the following section.
Modern Fréchet (MF) turns out to be a very useful technique when global comparison of data is required, that is, when all the data must be considered, and not only characteristic data. This technique can also be applied to any kind of data that can be represented as a matrix. Modern Fréchet is based on two key concepts: the original Fréchet distance and Dynamic Time Warping.
Foundations
Maurice Fréchet was a French mathematician with several relevant works on topology [20]. In his doctoral thesis [21], he presented a general procedure to measure the similarity between two curves where the order of the points along the two curves or sequences is considered. Informally, Fréchet presented this as an analogy, in which distance between two curves is calculated at each point as the minimum length of the belt necessary to connect a dog along a trajectory with its owner, or someone who is walking on another path, while moving forward without going back to along their respective trajectories from one initial point to another [22].
Matrix of minimum distances with a drawn path. Starts at position (1, 1) and ends at position (p, q).
Modern Fréchet is an optimization to the problem of elastic alignment in two dimensions (2DW). The comparison of matrices is made by obtaining the minimum distance the data of the matrices. For this, Dynamic Time Warping (DTW) is used, which in turn uses Euclidean Distance as the base distance. Modern Fréchet extends the base DTW method to two dimensions, i.e. data are not sequences, but two-dimensional matrices.
Suppose a metric space M (D, MFD) defined for an object domain D and a distance function MFD:D × D ↦ I R. Let A, B ∈ D two matrices of size (P, Q) and (R, S) respectively, let p, q be indices to access the elements of the matrix A and let r, s be the respective ones for the matrix B. The distance function MFD Is defined by the recursive function:
To compute the MFD (p, q, r, s), a 4-sized array of indices (P, Q, R, S) is constructed. A path is followed where for each element of matrix A the operations on matrix B are performed. These operations are defined in the cost function.
The cost function is defined by the computation of DTW using sequences R1 and R2, which are those corresponding to the input indices p, r of d, C1 and C2 use the corresponding indices q, s. This is explained in detail below.
The cost function is defined as the elastic alignment between two sequences or arrangements. This alignment is sought using the DTW technique, as mentioned in Section 4.1.
Let R1 and C1 be two subsequences of the matrix A, corresponding to the input indices (p, q). R1 are the values corresponding to the row p from the interval [1, q]. C1 are the values corresponding to the column q from the interval [1, p]. Similarly, R2 and C2 correspond to the indices (r, s). These sequences are shown in the diagram of Fig. 5.
R1 is the subsequence in row p bounded on the interval (1, q), C1 the column q bounded on the interval (1, p) for matrix A. Similarly, R2 is the row r bounded on the interval (1, s) and C2 the column s bounded on the interval (1, r) for matrix B.
To compute the cost function for the next input d (3, 4, 2, 3), we obtain the subsequences R1 and C1 from indices (3, 4). The same is done for the indices (2, 3) to obtain R2, C2. The cost function is DTW (R1, R2) + DTW (C1, C2). As input indices increase, all positions in the input matrices are compared through subsequences and their elastic matching. Figure 6 illustrates this idea.
MF is an elastic comparison method that compares the distortion found in rows and columns of an element of matrix A over all elements of matrix B, so that a complete path is made in the two input matrices.
To compute the value of each coordinate of d (p, q, r, s) their previous stages must be computed. For a position of the matrix A given by the indices (p, q) there are three possible previous stages that are subject to boundary limitations: (p - 1, q - 1) (p, q - 1) (p - 1, q)
Previous positions of d (p, q, r, s) are all the possible combinations of the previous stages of each matrix. The possible combinations of these are 15, and are listed in Table 8.
Total previous positions with the calculation of the cost function corresponding to each stage
Total previous positions with the calculation of the cost function corresponding to each stage
In order to reduce the computational complexity Dynamic Programming is used to iteratively compute previous stages with their respective cost. An array structure of four indices d (p, q, r, s) is used to register the minimum costs accumulated during the iterations. The final result will be the last position of this structure. This is detailed in Algorithm 1. A complex path in I R2 must be followed. In this algorithm the previous 15 positions are shown, along with their corresponding cost function for each stage.
1: P← Rows of A
2: Q← Columns of A
3: R← Rows of B
4: S← Columns of B
5: d (P, Q, R, S) Array of 4 indexes, initialized in ∞
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
Results obtained by applying the proposed method on different applications are presented in this section.
Comparison of natural ontologies is accomplished by using the Modern Fréchet distance described in Section 4. This method takes two matrices of numerical data as input. These matrices are in turn obtained from the process of elicitation of natural ontologies (Section 2).
The elicitation of knowledge through the use of the natural ontology technique was applied to three groups of people in the computer science domain. Each group consisted of 20 individuals to which the questionnaire in Spanish was applied and from it, three different natural ontologies were applied.
The groups were: Postgraduate students of the Computer Research Center (Centro de Investigación en Computación, Students of the 8th semester of Computer Systems Engineering from the Higher School of Computing (Escuela Superior de Cómputo, Students of 8th semester of Computer Science of the Technological Institute of Iztapalapa, Mexico (
Three natural ontologies have been obtained, one for each group. The goal was to compare them by using the Modern Fréchet technique. Our hypothesis is that the first two groups should be more similar, since both of them belong to the same institute, while the third one comes from a different university. Additionally, we expect the first group to present more precise definitions, as it is conformed by postgraduate students.
The vocabulary of defining-concepts of each group is different, so that the following cases may occur: Definitors are in a group but are not in the other two groups. Definitors are in two groups but not in one. Definitors are common for all three groups.
The union process consists in merging all the defining-concepts of all groups into a global matrix; semantic weights of groups are maintained separately. Therefore, this global matrix unifies the position of the defining-concepts, but maintains the semantic weights of each group. In this way we have three matrices with all defining concepts in the same position but what changes in each matrix are the semantic weights, as shown in Fig. 7.
Union of defining-concepts (full vocabulary). The x axis corresponds to the concept-stimuli, the y axis corresponds to the defining concepts of the 3 groups, the z axis represents the semantic weights.
Having the matrices unified after the union process, it is possible to compare them since now each one has the same position of its defining concepts and its concept-stimuli. The distance between them can be computed using Modern Fréchet; however, these matrices are too large for the distance technique, due to the complex path it develops. For this reason the SAM set for each matrix is obtained using the semantic value of the SAM set (the top n defining concepts with highest TMV, see Section 2.1.1) for computing ontology similarity. We have chosen n to be equal to 20.
Once the SAM matrices of each group have been obtained, the same binding process is performed for the new matrices, so that they are aligned. Now, there are smaller matrices that correspond to the most frequent vocabulary of each group (34 words in total). Once the matrices of the 3 SAM groups are obtained, they are compared using the Fréchet Modern distance. Table 9 shows the resulting matrix of distances between groups. It can be observed that distance of knowledge of the CIC group versus the ESCOM group is smaller than the distance between CIC and IZTA. This is as expected, because the first two are two faculties of the same institute, and the third one belongs to a different system. Additionally, the hypothesis that stated that concepts should be more precisely defined by the CIC group can be corroborated in Fig. 7 by considering the amount and distribution of the defining vocabulary.
Distances between groups
For this experiment we assumed that postgraduate students have more accurate knowledge on computer science concepts.
Knowledge of a group of people can be stored as a bi-dimensional Natural Ontology, where nodes represent concepts defined in turn by other defining concepts. Natural Ontologies serve to directly represent a source of knowledge in a domain, and several operations can be performed on the network. The natural semantic networks technique is a powerful tool to explore how meanings are intermingled in a particular domain. This technique was proposed based on human cognition theory, and this is why using it to extract natural ontologies is feasible and constitutes a well-founded method.
The methodology of elicitation presented in this work is a way to obtain human knowledge in a particular domain. This methodology in conjunction with the proposed Modern Fréchet distance provides a way to quantitatively compare human knowledge. Modern Fréchet is an elastic distance. In this work, this technique was applied to compare elements from different domains: ontologies, images and artificial data to validate its properties. For the ontologies domain, this technique allowed us to quantitatively compare the knowledge of three different groups of students.
The presented technique is not based on feature analysis as other techniques; instead it makes a global comparison with all data represented as the matrices, effectively providing a method to compare Natural Ontologies by considering all information globally.
This technique allows the study of different real groups within a particular domain. It allows to analyze what are the most prevalent defining concepts for a group of people, and this in turn allows to identify what are the differences with other groups.
As future work, research presented here can be extended in several ways. First, it is possible to explore other contexts where the presented distance technique can be used (images, text, documents, matrix entities, etc). Second, to extend the application of this method to larger matrices, it is necessary to optimize the algorithm, particularly the part of dynamic programming; this kind of problems is well suited for optimization using parallel programming.
From the perspective of the knowledge model, it is possible to identify specific conceptual deficiencies in groups. These deficiencies might be related to the defining concepts that an expert group has, compared with those missing in the non-expert groups. Once these deficiencies have been identified, it is possible to propose an adjustment in the knowledge network of the groups, in order to be more like the expert group. This allows to implement automatic tutor systems that can evaluate the progress of groups of people given the reference to a control group, leading to a better learning of a particular domain by groups of individuals.
Footnotes
Acknowledgments
We thank the support of the Mexican Government and Instituto Politécnico Nacional (IPN): COFAA-SIBE, EDI, Projects SIP 20195886, SIP 20200811; and Consejo Nacional de Ciencia y Tecnología – CONACyT (SNI, RedTTL).