Question-answer (QA) systems are systems that can take questions and respond to them in a natural language. In most cases, the principles of building question-answer systems are used in the development of decision support systems. The mechanism of syntagmatic patterns is used when processing open-ended questions and when extracting answers to it from semi-structured resources. This article describes the application of the mechanisms of syntagmatic patterns in the construction of various types of QA-systems and expert systems.
The knowledge base (KB) of our question-answer system has a tree-like structure. Semantic networks
are currently actively used in the construction of a KB [
KB SP, TD, R , where SP SP1, SP2 , , SPn is a set of syntagmatic patterns;
RTD R1TD , R2TD , , RnTD – is a set of relations between the internal and terminal nodes of the KB tree.
The internal nodes of the KB tree contain a syntagmatic pattern as a label. Terminal nodes contain text information. The answer to the question will be extracted from this textual information. An example of the KB structure of our question-answer system is shown in Figure 1.
More general syntagmatic patterns are located closer to the root element of the tree. More precise syntagmatic patterns are located closer to the terminal nodes of the tree. Thus, this knowledge base structure of our question-answer system allows us to find the necessary terminal nodes on the user's question (if the answer to this question is in the knowledge base).
The modified fuzzy C-Means (FCM) fuzzy clustering algorithm is used for learning (building a tree) the KB of our QA system. It is necessary to present each document as an index for the FCM algorithm. Indexing documents consists of the following steps: 1. Download the document. 2. Removing stop words (words that do not have semantic value: prepositions, particles, etc.). 3. Stemming using the Porter algorithm (highlighting the basis of the word). 4. Calculation the frequency of occurrence of words in the document. 5. The index of the document can be represented as an expression: where wid – i -th word of the document d ; fid – is the frequency of occurrence of i -th word in the document d ; n – is the number of words in the document d .
The modified FCM clustering algorithm is based on minimizing the function:
D C 2 F FCM uimj I i I cj ,1 m ,
i1 j1 where D – is the number of document indexes for clustering;
C – is a number of clusters; m – is any real number greater than 1; uij – is the degree to which the document index belongs Ii to the cluster j ; Ii – i -th document index; I cj – is a center of j -th cluster;
I i I cj – the normalized distance between the index of the document and the center of the cluster.
The FCM algorithm consists of the following steps: 1. Initialization of the matrix of indexes belonging to documents to clusters:
U uij . 2. Calculation of cluster centers: 3. Formation of a new membership matrix:
I cj uij iD1uimj I i iD1uimj
. 1 k1 I i I kc 4. The value of the objective function is calculated. The obtained value is compared with the value at the previous iteration. Clustering is complete if the difference does not exceed the threshold value. Otherwise, go to the second step of the algorithm.
The knowledge base is learned in the process of hierarchical clustering. First, the entire set of document indexes I 0 is clustered. Clusters are formed after the algorithm is executed. Each cluster obtained contains a subset of the documents of the original set: I 1 I 2 I n I 0 . A new partition is performed for each cluster received. The split continues as long as the value or equal to 2.
Thus, a tree is constructed whose internal nodes contain indexes of cluster centers, and terminal nodes contain text data. It is necessary to form internal node labels in the form of syntagmatic patterns based on the contents of internal nodes.
4. An algorithm for constructing syntagmatic patterns
There are currently many approaches to the analysis of texts in natural language [
It is sufficient to use the first two steps of the process of text analysis in natural language to form syntagmatic patterns: graphematic and morphological analysis.
The algorithm for syntagmatic patterns can be written as follows in pseudocode:
For each terminal node of the knowledge base.
For each document from the current terminal node.
Split the text of the document into sentences.
For each proposal of the document.
Split the sentence into words.
For each word of the sentence.
Get morphological signs.
For each untreated internal node, except for the root node.
Until the root node is reached or the parent of the current node is not the root node.
For each word of the index of the parent ejected node.
Find all the documents in which the word appears.
For each document.
Select syntagmatic units.
Delete the same syntagmatic units.
For each selected syntagmatic unit.
Find similar syntagmatic units.
Form candidates in syntagmatic patterns.
Solve the problem of optimal coverage.
Write the result in the node label.
Mark the node as processed.
Go to the parent node.
Thus, internal nodes of the knowledge base tree are marked with syntagmatic patterns as a result of this algorithm. 5. The search for the answer to the question in the KB The learned KB of our QA system allows us to find answers to the user's requests. First you need to find the required terminal node of the knowledge base. The internal node labels are used to find the most relevant terminal node. Each internal node of the knowledge base is marked with a syntagmatic pattern.
In pseudocode, the search algorithm for the most relevant terminal node of the knowledge base tree can be written as follows:
Syntagmatic units are allocated from the question that has entered the system entrance. Set the position on the root node of the knowledge base tree.
For each child node of the knowledge base.
Find the number of syntagmatic patterns of the current child node
corresponding to the syntagmatic units of the question.
Set the position to the child node with the highest match.
Continue if the selected child node is not terminal, otherwise, return the terminal node.
It is necessary to find in the text documents the most relevant sentence after finding the terminal node. The answer to the question is the most relevant sentence.
In pseudocode, the search algorithm for the most relevant sentence from the text documents of the terminal node found can be written as follows:
For each terminal node document.
For each sentence of the current document. Find the number of syntagmatic patterns of the current sentence corresponding to the syntagmatic units of the question.
Choose the best match.
Select the document with the highest match.
Thus the two algorithms presented above make it possible to organize the search for the most relevant answer to an incoming question.
The materials of the Sberbank Data Science Contest [
Two question-answer systems were used to conduct the experiment. Their knowledge base was learned using a modified FCM algorithm. The first knowledge base contained many pairs of "termfrequency" as labels of internal nodes. The second knowledge base contained syntagmatic patterns as labels of internal nodes.
A proximity measure was used to find the most relevant document and / or sentence in the first knowledge base. The proximity measure is obtained using the square of the Euclidean distance: W 2 Dist(I ic , I q ) f wc - f wq , w1 where I ic – is the index of the i -th terminal node document c ;
I q – is the index of the received question;
f wc , f wq – is the frequency of occurrence of the word w in the indexes I ic and I q .
The most relevant document and / or sentence is a document and / or sentence with a minimum proximity measure.
During the experiment 50,365 questions were submitted to both question-answer systems. The sentence from the paragraph was given as an answer to the question. The result was considered successful if the reference answer was a substring of the found sentence. The results of the experiments are presented in Table 1.
Thus, the developed syntagmatic approach to the development of question-answer systems is effective. This approach can be used to develop the following types of software systems: the system for automating the process of interaction with customers based on the analysis of the knowledge base and corporate correspondence; decision support system based on the analysis of the knowledge base and use cases; the system of verification of information flows of the enterprise to ensure information security; the system for automating the work of the technical support service based on the analysis of the knowledge base and use cases.
In the future, we plan to modify the developed approach by finding answers to questions in an implicit form.