KR20230166853A - Algebraic word problem solving method and apparatus applying human strategy to artificial neural network - Google Patents

Abstract

Presents problem-solving devices and methods. The problem-solving device includes an input/output unit for receiving data and outputting results of calculating and processing the data, a storage unit for storing a program for performing a problem-solving method, and at least one process, and executing the program It includes a control unit that analyzes data received through an input/output unit, wherein the control unit receives a sentence-type math problem and generates an explanation text about the numbers and variables contained in the sentence-type math problem through an encoder-decoder-based explanation generation model. Generate and output, receive the sentence-type math problem, the generated explanation, or a combination thereof, and generate and output a mathematical equation through an encoder-decoder based mathematical equation generation model.

Description

Method and device for solving sentence-type algebra problems that apply human strategies to artificial neural networks {ALGEBRAIC WORD PROBLEM SOLVING METHOD AND APPARATUS APPLYING HUMAN STRATEGY TO ARTIFICIAL NEURAL NETWORK}

Embodiments disclosed in this specification relate to a method and device for solving sentence-type algebra problems. More specifically, a human strategy is applied to an artificial neural network model of an encoder-decoder structure to interpret a given mathematical problem and solve the problem based on this. It relates to a method and device for generating explanations of numbers and variables in natural language and automatically generating mathematical problems with correct mathematical expressions.

Human problem-solving strategies are largely divided into the steps of understanding the problem, writing mathematical equations, and calculating the answer. Contextual information, such as relationships between numbers, is used in the stages of understanding problems and writing mathematical equations.

At the stage of understanding a problem, humans extract information about numbers and variables by explaining the given problem. Humans write mathematical expressions by combining several templates that preserve information about the relationship between operators and operands.

Machine learning for sentence problem solving builds a model designed to encode a given sentence problem and decode it into a mathematical equation.

Previously, in order to solve sentence-type math problems, learning features defined by experts were built into the data set, and then a machine learning model learned the features to classify the problems into types and then provide solutions appropriate for those types. The method of applying was common, but this method has the problem of requiring expert work to build the model.

When using an artificial neural network, there is no need to use features defined in advance by experts, but there is a problem that it is difficult to interpret how the artificial neural network interprets the problem and through what process it infers the mathematical formula.

Therefore, there is a need for an automated model that makes inferences using artificial neural networks and a model that generates natural line-by-line descriptions of the main parts of the problem as evidence for interpreting artificial neural networks.

For reference, Patent Document 1 is an invention regarding an artificial intelligence-based mathematical problem-solving device, and Patent Document 2 is an invention regarding a method of providing a mathematical problem concept type prediction service using neural network-based machine translation and arithmetic. Patent Document 1 and Patent Document 2 only discloses general mathematical problem solving content and does not provide automated mathematical problem solving technology that can provide reliability regarding the explanation while explaining the problem understanding of artificial neural networks.

Korean Patent No. 10-2110784 (2020.05.08.) Korean Patent No. 10-1986721 (2019.05.31.)

Embodiments disclosed in this specification generate analysis results regarding numbers and variables in the problem in the form of natural language during the problem understanding process for sentence-type mathematical problems, and generate recombination problems that reconstruct the analysis results during the mathematical formula writing process. The purpose is to provide a problem-solving method and device for generating mathematical expressions using expressions, which are units that group operands associated with operators based on recombination problems and original problems.

Other objects and advantages of the present invention can be understood from the following description and will be more clearly understood through an example. In addition, it will be readily apparent that the objects and advantages of the present invention can be realized by means and combinations thereof as indicated in the claims.

As a technical means for achieving the above-described technical problem, a problem-solving device includes an input/output unit for receiving data and outputting the result of processing the data; a storage unit in which a program for performing a problem solving method is stored; and at least one process, including a control unit that analyzes data received through the input/output unit by executing the program, wherein the control unit receives a sentence-type math problem and runs it through an encoder-decoder based explanation generation model. Explanations about the numbers and variables contained in the sentence-type math problem are generated and output, and the sentence-type math problem, the generated explanation, or a combination thereof are input, and mathematics is performed through an encoder-decoder-based mathematical expression generation model. Create and output an expression.

According to another embodiment, in a problem solving method using a problem solving device, a sentence-type math problem is input and an explanation text regarding numbers and variables contained in the sentence-type math problem is generated through an encoder-decoder-based explanation text generation model. Step of outputting; and receiving the sentence-type math problem, the generated explanation, or a combination thereof, and generating and outputting a math equation through an encoder-decoder-based math equation generation model.

According to another embodiment, the recording medium is a computer-readable recording medium on which a program for performing a problem-solving method is recorded.

According to another embodiment, the computer program is a computer program that is executed by a problem-solving device and stored in a recording medium to perform a problem-solving method.

According to any one of the above-mentioned problem solving means, a problem-solving method and device can be proposed in which an explanatory text generation model interprets a sentence-type mathematical problem and based on this, generates an interpretation of the numbers and variables in the problem in the form of natural language.

In addition, according to any one of the above-mentioned problem solving means, a problem solving method and device for generating a mathematical expression by inputting the problem analysis together with the original problem into a mathematical expression generation model so that the model can compare and contrast itself to see if the problem analysis is accurate is provided. can be presented.

In addition, according to any one of the above-mentioned problem solving means, it is possible to present a problem solving method and device that preserves context information by using an expression in which a mathematical expression generation model is a unit of operands associated with an operator grouped together.

In addition, according to any one of the above-mentioned problem solving means, a problem solving method and device that improves the correct answer rate by improving the decoding and encoding process so that the artificial neural network model can preserve context information can be proposed.

The effects that can be obtained from the disclosed embodiments are not limited to the effects mentioned above, and other effects not mentioned are clear to those skilled in the art to which the disclosed embodiments belong from the description below. It will be understandable.

Hereinafter, the attached drawings illustrate preferred embodiments disclosed in the present specification, and serve to further understand the technical idea disclosed in the present specification along with specific details for carrying out the invention, and thus the drawings disclosed in the present specification The contents should not be construed as limited to the matters described in such drawings.
1 is a block diagram of a problem-solving device according to an embodiment.
Figure 2 is a diagram illustrating an artificial neural network model applied to a problem-solving device according to an embodiment.
Figures 3 and 4 are diagrams illustrating the operating principle of a mathematical equation generation model applicable to a problem-solving device according to an embodiment.
Figures 5 and 6 are diagrams illustrating ablation analysis of a mathematical equation generation model applicable to a problem-solving device according to an embodiment.
Figure 7 is a diagram illustrating the operating principle of an artificial neural network model applied to a problem-solving device according to an embodiment.
Figures 8 and 9 are diagrams illustrating ablation analysis of an artificial neural network model applied to a problem-solving device according to an embodiment.
10 and 11 are flowcharts of a problem solving method according to another embodiment.

Below, various embodiments will be described in detail with reference to the attached drawings. The embodiments described below may be modified and implemented in various different forms. In order to more clearly explain the characteristics of the embodiments, detailed descriptions of matters widely known to those skilled in the art to which the following embodiments belong have been omitted. In addition, in the drawings, parts that are not related to the description of the embodiments are omitted, and similar parts are given similar reference numerals throughout the specification.

Throughout the specification, when a configuration is said to be “connected” to another configuration, this includes not only cases where it is “directly connected,” but also cases where it is “connected with another configuration in between.” In addition, when a configuration “includes” a configuration, this means that other configurations may be further included rather than excluding other configurations, unless specifically stated to the contrary.

Hereinafter, embodiments will be described in detail with reference to the attached drawings.

Table 1 below provides examples of sentence-type math problems.

[Table 1]

In the problem in Table 1, a quarter is equal to $0.25 (25 cents) and a nickel is equal to $0.05 (5 cents). The artificial neural network model receives sentence-type math problems as input and infers appropriate mathematical formulas from the problems. Sentence-type math problems contain numbers but not variables, so the artificial neural network model must infer the appropriate variables. For example, set the number of quarters to the variable x, set the number of nickels to the variable y, and find the number of variables required for the solution corresponding to 2.

Artificial neural network models go through encoding and decoding processes when solving sentence-type math problems. During the encoding process, artificial neural network models correctly understand mathematical problems and convert them into numerical information that explains the role of numbers. For example, the artificial neural network model must understand that 12 means the total number of coins and 2.20 means the price of all coins. The artificial neural network model tracks the calculation structure and written parts of the mathematical expression during the decoding process and constructs the mathematical expression by combining small calculation units. For example, the artificial neural network model creates an x+y expression and reuses the generated expression for x+y=12.

Depending on how the artificial neural network model is designed, context information is lost during the encoding and decoding process. In order for the artificial neural network model to better preserve context information when solving sentence-type math problems, it is necessary to consider the relationships shown in Table 2 below.

[Table 2]

The problem-solving device according to this embodiment designs a mathematical expression generation model that uses an expression that groups operands related to operators to capture context information of the calculation structure of the mathematical expression during the decoding process of creating the mathematical expression. Because expressions represent relationships between operators and operands, the mathematical expression generation model can identify the context information of previously created expressions, and the mathematical expression generation model can easily identify the expressions it has created and the expressions to be additionally created. The mathematical expression generation model uses expressions to improve the correct answer rate.

The problem-solving device according to this embodiment designs an explanatory text generation model that explains numbers and variables in order to capture context information of elements such as numbers that make up the problem during the encoding process of understanding the problem. The explanation generation model can check the degree of understanding of the artificial neural network model by comparing the generated explanation with the original problem. By referring to the generated explanation, you can identify whether the artificial neural network model misunderstood the problem. The more the explanation generation model predicts the correct explanation, the more the artificial neural network model’s solving accuracy improves.

1 is a functional block diagram of a problem-solving device according to an embodiment.

Referring to FIG. 1, the problem-solving device 100 according to one embodiment includes an input/output unit 110, a storage unit 120, and a control unit 130.

The input/output unit 110 may include an input unit for receiving input from a user and an output unit for displaying information such as a task performance result or the status of the problem solving device 100 . In other words, the input/output unit 110 is configured to receive input data and output the results of processing the data. The problem-solving device 100 according to the embodiment may receive a sentence-type math problem, etc. through the input/output unit 110.

The storage unit 120 is a component in which files and programs can be stored, and can be configured using various types of memory. In particular, the storage unit 120 may store data and programs that enable the control unit 130, which will be described later, to perform calculations for solving problems according to the algorithm presented below.

The control unit 130 is a component that includes at least one processor such as CPU, GPU, Arduino, etc., and can control the overall operation of the problem solving device 100. That is, the control unit 130 can control other components included in the problem-solving device 100 to perform operations for solving the problem. The control unit 130 can perform calculations to solve the problem according to the algorithm presented below by executing the program stored in the storage unit 120.

The control unit 130 generates an explanation from a sentence-type math problem through an artificial neural network model. The control unit 130 receives a sentence-type math problem as input, generates and outputs an explanation about the numbers and variables contained in the sentence-type math problem through an encoder-decoder-based explanation generation model. The control unit 130 generates an explanation using context information related to the numbers in the problem, and uses the generated explanation to generate a mathematical equation. The generated explanation can serve as a standard for judging how correctly the artificial neural network model understands the problem.

The control unit 130 generates a mathematical equation from a problem that combines the problem of converting the explanation text through an artificial neural network model and the original sentence-type mathematical problem. The control unit 130 receives a sentence-type math problem, a generated explanation, or a combination thereof, generates a math equation through an encoder-decoder-based math equation generation model, and outputs it. If the problem with the converted explanation is entered together with the original sentence-type math problem, the problem with the converted explanation can complement the context information in the original sentence-type math problem and improve the performance of the artificial neural network model.

Figure 2 is a diagram illustrating an artificial neural network model applied to a problem-solving device according to an embodiment.

The artificial neural network model includes a description generation model (200) and a mathematical expression generation model (300). The description generation model 200 and the mathematical expression generation model 300 are designed with multiple layers of an encoder-decoder structure. The encoder performs embedding processing to convert high-dimensional information into low-dimensional information representing features. The decoder converts low-dimensional information into high-dimensional information and reconstructs the features.

The description generation model 200 includes an encoder 210, a decoder 220, a variable predictor 230, and a pointer generator 240.

The encoder 210 of the explanation generation model 200 receives a sentence-type math problem as input, segments it into tokens, and outputs a problem context vector representing context information of the sentence-type math problem for each token.

The decoder 220 of the explanation generation model 200 receives a problem context vector, a variable considering the number of variables, and a number of sentence-type math problems, and determines the hidden state of the decoder 220 based on the previously generated explanation token ( Calculate the hidden state.

The variable predictor 230 is connected between the encoder 210 and the decoder 220 of the description generation model 200. The variable predictor 230 receives the problem context vector and transforms the representative value to predict the number of variables needed to solve the sentence-type math problem.

The pointer generator 240 is connected to the decoder 220 of the explanation generation model 200, and the pointer generator 240 receives the hidden state of the decoder 220 and predicts the next explanation token.

The control unit 130 selects the context in which a number is located in a sentence-type math problem through the explanatory sentence generation model 200 and restructures the generated explanatory sentence about the number into a first sentence. The control unit 130 restructures the description of the variable created using the index of the variable through the description generation model 200 into a second sentence. The control unit 130 combines the restructured first and second sentences to create a recombination problem.

The mathematical expression generation model 300 includes an encoder 310 and a decoder 320.

The control unit 130 inputs the recombination problem and the sentence-type math problem to the encoder 310 of the mathematical expression generation model 300.

The encoder 310 of the mathematical expression generation model 300 receives the recombination problem and the original sentence-type math problem and outputs a recombination context vector.

The decoder 320 of the mathematical expression generation model 300 receives the recombined context vector and generates a mathematical expression using expression token units that group operators and necessary operands.

Figures 3 and 4 are diagrams illustrating the operating principle of a mathematical equation generation model applicable to a problem-solving device according to an embodiment.

The expression generation model (Expression Pointer Transformer, EPT), which can be applied to problem solving devices, uses expression tokens to solve the expression fragmentation problem and the operand-context information separation problem.

Referring to (a) of FIG. 3, the expression fragmentation problem is one in which an expression tree representing the calculation structure of a mathematical expression is split. As an example of an expression fragmentation problem, when applying an existing operator/operand token, it is decomposed into operator 'x', operands 'x ₁ ' and 'N ₂ '. The three decomposed tokens are meaningless and confuse the model until they are recombined into the single expression N ₂ xx ₁ .

The problem of operand-context information separation is the loss of connection between the operand and the numbers associated with the operand. As an example of the operand-context information separation problem, when applying existing operator/operand tokens, the number '8' is not used, but the abstract symbol 'N ₂ ', which does not appear in the problem, is used. It is not easy to find in the original problem which number corresponds to the abstract symbol 'N ₂ '.

In other words, the context information of the calculation structure is lost in the process of generating a mathematical expression due to the expression fragmentation problem and the operand-context information separation problem.

The mathematical expression generation model can preserve more context information of the calculation structure than traditional operator/operand tokens by applying expression token units that group operators and operands related to the operators. Since the grouped expression token unit maintains the tree structure and directly uses the context information of the operand, it can solve the expression fragmentation problem and the operand-context information separation problem.

As shown in Figure 3(b), applying expression tokens that group operators and related operands, each of the three tokens represents one of the subtrees of the expression tree. A mathematical expression generation model can explicitly consider context information about operators and related operands by using expression tokens that group operators and related operands.

When applying an expression token that groups an operator and its associated operands, rather than converting the numbers written in the problem into abstract symbols, a pointer is created to the location where the numbers occur. Each operand points directly to a written number or previous output. The mathematical expression generation model can directly access context information about the operand using the operand-context pointer.

Referring to FIG. 4, the encoder of the expression pointer transformer (EPT) applicable to the problem solving device reads the problem and outputs the encoder's hidden state vector for each token. The decoder then uses the hidden state vector as memory and generates the expression step by step.

The encoder reads the problem text and generates the encoder's hidden state vector and a numeric context vector.

The encoder tokenizes the input problem text into a series of subword tokens. We then convert each token into an embedding vector. The encoder uses the embedding vector to calculate the encoder's hidden state vector for each token.

The encoder obtains a context vector for each number written in the problem. Since the encoder performs tokenization of the given problem text into subword tokens, the written numbers have one or more hidden state vectors. Therefore, to obtain a single vector value, the encoder can take the average of these hidden state vectors.

For the initial weights of the encoder, you can refer to the ALBERT (A Lite BERT for Self-supervised Learning of Language Representations, Lan et al., 2019) model, which is a pre-trained language model. Since the ALBERT model is trained to predict words or sentences arranged in a large corpus, the ALBERT model can provide knowledge for solving word problems.

The decoder uses context vectors to solve the operand-context information separation problem. The decoder uses the encoder's hidden state vector as memory to generate expression tokens. The entire process of generating expression tokens proceeds recursively. The mathematical generation model predicts the ith token using the tokens before the ith step.

Table 3 below shows an example of a sequence of eight expression tokens that produces x ₀ -2x ₁ =8 and x ₀ +x ₁ =20.

[Table 3]

After inputting three tokens (BEGIN, VAR, and VAR), the decoder must predict operator × and operands 2 and R ₁ simultaneously. The decoder includes three special instructions in its list. 'BEGIN' is a command to start a sequence, 'VAR' is a command to create a new variable, and 'END' is a command to collect all mathematical expressions created so far.

The calculation structure of the decoder applicable to the mathematical expression generation model can refer to the calculation structure of the decoder of the Transformer (Attention Is All You Need, Vaswani et al., 2017) model.

Assuming the decoder predicts the ith expression token, the decoder receives the expression tokens generated so far and transforms them into an embedding vector v _j (j=0, ..., i-1). Based on the embedding vector vj and the encoder's hidden state vector e _t , the decoder constructs the decoder's hidden state vector d _i for the ith expression token. The decoder then predicts the next expression token with the hidden state vector di.

Unlike the decoder of the transformer model, the decoder applicable to the mathematical expression generation model receives expression tokens and modifies the input embedding part and the output prediction part to generate them.

Regarding the input embedding part, the input vector v _i of the ith expression token is obtained by combining the operator embedding f _i and the operand embedding a _ij as shown in Equation 1.

[Equation 1]

FF _* is a feed-forward linear layer, and Concat() means concatenate all vectors in parentheses. v _i , f _i , and a _ij have the same dimension D.

For the operator token f _i of the ith expression, the operator embedding vector f _i is calculated as in Equation 2.

[Equation 2]

E _* () represents a lookup table for the embedding vector, c _* represents a scalar parameter, LN _* () represents layer normalization, and PE() represents positional encoding.

The embedding vector a _ij representing the j-th operand of the i-th expression is calculated differently depending on the source of the operand a _ij . Three possible sources for reflecting the context information of the operands are issue-dependent numbers, issue-independent constants, and the result of the previous expression token.

Problem-dependent numbers are numbers provided in an algebraic problem. To calculate the number a _ij , the hidden state vector of the encoder corresponding to the number token is reused as shown in Equation 3.

[Equation 3]

u _* is a vector representing the source, is the context vector corresponding to the number a _ij .

Problem-independent constants are predefined numbers that are not specified in the problem. For example, 0.25 is used as a quarter amount. To calculate the constant a _ij , the lookup table E _c is used as shown in Equation 4.

[Equation 4]

The result of the previous expression token is the expression token generated before the current ith step. For example, referring to Table 3, R ₀ in the fourth step even though the hidden state vector of the decoder can be accessed before the ith step. The mathematical generation model uses positional encoding to maintain simultaneous decoding during the trading process.

[Equation 5]

k represents the index of the step in which the previous expression a _ij was created. LN _a and c _a are shared from different sources.

The input embedding part is suitable for handling expression fragmentation problems and operand-context information separation problems. To solve the expression fragmentation problem, the input of the decoder of the mathematical expression generation model maintains the structure of the expression. Therefore, operators and their associated operands are used to construct the input embedding of an expression. To solve the operand context separation problem, the decoder of the mathematical expression generation model utilizes the context information of the operand. In particular, the decoder directly uses the context vector of written numbers instead of abstract symbols.

Regarding the output prediction part, the decoder of the mathematical expression generation model simultaneously predicts the next operator f _{i +1} and the operand a _i+1,j when the ith expression token is provided. The next operator f _{i +1} is predicted as in Equation 6.

[Equation 6]

is the softmax function It is the probability of selecting item k from a distribution that follows the output of .

In order to utilize the context information of the operand when predicting the operand, the output layer applies an 'operand-context pointer' referring to Pointer Networks (Vinyals et al., 2015). In a pointer network, the output layer predicts the next token using attention to candidate vectors.

The mathematical expression generation model collects candidate vectors for the next (i+1)th expression in three different ways depending on the source of the operand. The source of the operand is for the kth number in the problem. , for the kth expression output , for constant x It is divided into

The mathematical expression generation model predicts the next jth operand a _i+1,j . Assuming A _ij is a matrix where the row vector is a candidate, the equation generation model calculates the attention of the query vector Q _ij in the key matrix K _ij and predicts a _i+1,j .

[Equation 7]

The output prediction part is suitable for handling expression fragmentation problems and operand-context information separation problems. To solve the problem of expression fragmentation, the decoder of a mathematical expression generative model predicts all components of the expression simultaneously. Operators and operands are generated from the hidden state vector d _i of the same decoder. To solve the operand-context information separation problem, the decoder of the mathematical expression generation model directly points to appropriate context information instead of generating abstract symbols. The encoder's hidden state vector and the decoder's hidden state vector can provide context information of the written number and the previous expression token, respectively.

The mathematical expression generation model is trained to minimize the sum of various loss functions (operator loss function and operand loss function). The loss function may be smoothed cross-entropy. The mathematical expression generation model can calculate the operand loss function separately for each operand position by considering noncommutative operators. For example, if the maximum arity of an operator used in a mathematical expression generation model is 2, three loss functions related to one operator loss function and two operand loss functions can be applied.

Figures 5 and 6 are diagrams illustrating ablation analysis of a mathematical equation generation model applicable to a problem-solving device according to an embodiment.

The model shown in Figure 4 is a model that applies both an expression token and an operand-context pointer, and the model shown in Figure 5 uses an operator/operand token (op token) instead of an expression token. It is a model in which an abstract symbol is applied instead of an operand-context pointer, and the model shown in Figure 6 is a model in which an expression token is applied and an abstract symbol is applied instead of an operand-context pointer.

Table 4 below shows the size and complexity of the three data sets applied to each model shown in Figures 4, 5, and 6.

[Table 4]

ALG514 and DRAW-1K are high-complexity data sets, and MAWPS is a low-complexity data set. The number of unknowns and tokens in ALG514 and DRAW-1K is almost twice that in MAWPS.

Table 5 below shows the correct answer accuracy of each model shown in Figures 4, 5, and 6.

[Table 5]

The accuracy of the model using expression tokens (Figure 6) was improved by approximately 15% in ALG514 and DRAW-1K, and by approximately 1% in MAWPS, compared to the transformer model (Figure 5). The model that applied operand-context pointers to the model that applied expression tokens (Figure 4) improved accuracy by about 30% in ALG514 and DRAW-1K and by about 3% in MAWPS.

In this way, higher performance improvements can be seen from two perspectives in the high-complexity data sets of ALG514 and DRAW-1K. First, as the number of unknowns and tokens increases in a high-complexity data set, the probability of encountering expression fragmentation problems for each token increases exponentially. Second, because number and expression tokens are candidates for selecting operands, the probability of operand-context information separation problems increases linearly as the number of numbers and expressions in an equation increases. Applying expression tokens and operand-context pointers to the mathematical expression generation model can solve the expression fragmentation problem and operand-context information separation problem for each token, thereby further improving accuracy in high-complexity data sets.

Even if the accuracy of the artificial neural network model that solves sentence-type math problems improves, it is necessary to verify whether the artificial neural network model correctly captures the numerical information of the problem.

Figure 7 is a diagram illustrating the operating principle of an artificial neural network model applied to a problem-solving device according to an embodiment.

The artificial neural network model (Expression Pointer Transformer with eXplanations, EPT-X) according to this embodiment must consider explanations that meet two criteria when solving a problem. First, the explanation must satisfy plausibility by thoroughly reflecting the given problem in the process of understanding the problem. In particular, because humans perceive each number and variable individually, the explanation must reveal what each number or variable represents in the context of the given problem. Second, in the process of writing mathematical equations, explanations must be used to satisfy faithfulness. If the description contains useful information for writing a mathematical expression, it should serve as a basis for selecting operators or operands.

In order to create a mathematical equation that is faithful to a valid explanation, the problem-solving device according to this embodiment modifies the mathematical expression generation model described in FIG. 4 and additionally designs an explanation generation model. The problem-solving device performs an explanation operation of numbers or variables based on an explanation generation model and a mathematical expression construction operation based on a mathematical expression generation model, respectively.

The explanation operation receives the original problem and passes it through the encoder 210, a prior learning language model, to obtain a problem context vector, which is a vector value representing the contextual meaning of the problem. As a pre-training language model, you can refer to the ELECTRA (Pre-training Text Encoders as Discriminators Rather Than Generators, Clark et al., 2020) model.

The explanation operation inputs the generated vector value into a variable predictor 230 to predict the number of variables needed to solve the problem.

The explanation operation inputs each number and predicted variable in the problem into the decoder 220 to obtain an explanation explaining each number and variable. The object for which an explanation is created is a part of the problem, such as a number/variable, not the entire problem.

The mathematical formula construction operation converts the generated description into a sentence and concatenates it to create a recombined problem in which the description is recombined. The generated recombination problem is the result of a paraphrase of the original problem, and the model can check if there is any information missed in the explanation operation by comparing it with the original problem.

The mathematical expression construction operation concatenates the original problem and the recombined problem, or receives only one side as input and passes through the encoder 310, a prior learning language model, to obtain a new vector value, a recombined context vector. You can refer to the ELECTRA model as a pre-learning language model. If necessary, the encoder 210 of the description generation model 200 and the encoder 310 of the mathematical expression generation model 300 may be shared.

The mathematical expression construction operation inputs a new vector value into the decoder 320 to predict a mathematical expression to solve a given problem.

The explanation operation is specifically divided into an operation to calculate the problem context vector, an operation to predict the number of variables, and an operation to generate an explanation sentence.

The operation of calculating the problem context vector is to segment the original problem into tokens when the original problem is input to the prior learning language model, and refer to the dictionary to convert each token into an index of the dictionary. The index list generated by segmentation and transformation is input to the pre-learning language model. A vector value is generated for each token according to the calculation process of the prior learning language model, and the problem context vector is obtained.

In the operation of calculating the problem context vector, the encoder 210 of the explanation text generation model 200 receives the natural language problem text as input and calculates the problem context vector. Given problem text, encoder 210 tokenizes the problem text into a series of sub-word tokens. Encoder 210 then converts each token into an embedding vector. Encoder 210 uses the embedding vector to calculate a problem context vector w _s for each token w _s of a given problem.

The weights of the encoder 210 can be initialized using the ELECTRA model, a pre-trained language model. Because the ELECTRA model is trained to predict alternative words in large corpora, the ELECTRA model can provide the knowledge needed to understand a given problem.

Since the given problem text hides the number of required variables, N, the number of variables, N, must be recovered using the problem context vector before generating the description.

The operation of predicting the number of variables selects a representative value that can express the problem among several vector values generated by the language model. There are several ways to select a representative value, for example, you can select the first value. The representative value is transformed by passing through several linear feed-forward layers and an activation function. Based on the transformed value, predict the probability that the number of variables will be from 1 to 9.

In the operation of predicting the number of variables, the variable predictor 230 of the explanation text generation model 200 selects the problem context vector w ₀ of the first token containing the entire meaning of the problem text among several methods of pooling the problem context vector. can be used. The probability distribution of the number of variables N is calculated as Equation 8.

[Equation 8]

FF() stands for feed forward layer. The maximum number of variables can be set to 9.

In the operation of generating a description, the decoder 220 completes the description by receiving the vector generated by the prior learning language model and the information of the number or variable to generate the description one by one. The decoder 220 of the description generation model 200 may refer to the transformer model. In the case of numbers, the context of the problem in which the number appears is selected, entered, and explained. In the case of variables, enter the index of the variable and explain it. When descriptions for all numbers and all variables are created, the operation to create descriptions ends.

In the operation of generating an explanation, the decoder 220 of the explanation generation model 200 uses the problem context vector as a memory to generate an explanation. The description generation model (200) is a decoder of the Transformer (Attention Is All You Need, Vaswani et al., 2017) model and a pointer-generator network (Get To The Point: Summarization with Pointer-Generator Networks, See et al., 2017). ) can be referred to.

Before predicting the next statement token x _t+1, the decoder 220 calculates the hidden state h _t based on the problem context vector ws and the previously generated statement tokens x ₁ , ..., x _t .

To utilize knowledge to generate explanations, BERTGeneration (Leveraging Pre-trained Checkpoints for Sequence Generation Tasks, Rothe et al., 2020) can be applied, and the ELECTRA (Clark et al., 2020) model can be used as initial weights. Depending on the operation of generating the description, the embedding of the decoder may be fixed after initialization.

Pointer generator 240 receives the calculated hidden state h _t and predicts the next token. If p _g , P _v , and P _c are the probability of using the generated word, the probability of generating a token in the vocabulary, and the probability of copying a token in the problem, respectively, then the next token x _t+1 is predicted as in Equation 9 do.

[Equation 9]

σ(), E(), and attn() represent sigmoid, embedding, and single head attention scoring function, respectively. represents the concatenation of vectors.

In the process of creating an explanation, a separate explanation is created for each number/variable to ensure the validity of the explanation. The description generation model 200 uses unique initial input values for all numbers and variables. Instead of ‘[CLS]’, which is the initial input value of the decoder of the transformer model, the explanation generation model 200 inputs “[CLS] explain: context [SEP]”. Here, the 'context' part depends on numbers or variables. For numbers, use the token window near the given number token. For example, if the window size is 3, the 3 tokens located before the specified token and the 3 tokens located after the specified token are used. In the case of variables, the variable index is used because the variable does not appear in the problem. For example, the initial input value of the nth variable becomes “[CLS] explain: variable n [SEP]”.

The mathematical formula construction operation is specifically divided into an operation to recombine descriptions, an operation to calculate a recombined context vector, and an operation to generate a mathematical expression.

The action of recombining a statement paraphrases the statement. In the case of explanatory sentences about numbers, they are restructured into general sentences such as “The explanation is a number,” and in the case of explanatory sentences about variables, they are restructured into question-type sentences such as “What is the explanation?” The recombination problem is obtained by concatenating the first sentence, which is a paraphrase of the explanation of numbers, and the second sentence, which is a paraphrase of the explanation of variables, in order. The form of the sentence being restructured was chosen for convenience, and it can be transformed into other types of sentences. To augment the data set, during the model's training process, one of the reference descriptions for each number/variable can be randomly selected before recombining.

The operation of recombining the description helps the function of the decoder 320 of the mathematical expression generation model 300 from two perspectives. First, the original problem is refined to exclude information that is irrelevant to solving the given problem. This is because the recombined problem text contains less irrelevant information than the original problem text. Second, the recombination problem supplements the contextual information needed to solve the problem. The original problem sometimes omits information about necessary variables, but the recombination problem explicitly specifies this information.

In the operation of calculating the recombined context vector, the encoder 310 of the mathematical expression generation model 300, which is a prior learning language model, acquires a new vector value, a recombined context vector. If both the original problem and the recombined problem are used, the original problem and the recombined problem are connected in order and used as input. If there is only one type of input problem, that problem is used as input.

The operation of calculating the recombined context vector is to segment the input problem into tokens when each problem or combined problem is input to the prior learning language model, and refer to the dictionary to convert each token into an index of the dictionary. The index list generated by segmentation and transformation is input to the pre-learning language model. A vector value is generated for each token according to the calculation process of the prior learning language model, and a recombined context vector is obtained.

After generating the recombined problem text, the original problem and the recombined problem are combined as “[CLS] original problem [SEP] recombined problem [SEP]” and provided as input to the encoder 310. Artificial neural network models can be designed to use both types of problems because using the original problem can prevent information loss. In the case of recombination problems, if the explanation is generated incorrectly, there may not be enough information to solve the problem. Even if the generated explanation is wrong, the original problem can help the artificial neural network model learn in the right direction.

In the operation of calculating the recombination context vector, the encoder 310 of the equation generation model 300 calculates the recombination context vector r _i for each input token r _i .

The artificial neural network model considers the similarity between the encoder 210 of the explanation generation model 200 and the encoder 310 of the mathematical expression generation model 300, and uses the encoder 210 of the explanation generation model 200 and the mathematical expression generation model ( The same encoder can be applied to the encoder 310 of 300).

The input text of the encoder 210 of the explanation generation model 200 is an original problem that is a sub-sequence input to the encoder 310 of the mathematical expression generation model 300, and the encoder 210 of the explanation generation model 200 and the mathematics The output of the encoder 310 of the expression generation model 300 has the same format. That is, the output of encoders 210 and 310 is a context vector that encapsulates the given input text. The training process can be stabilized by sharing training knowledge between the encoder 210 of the description generation model 200 and the encoder 310 of the mathematical expression generation model 300.

In the operation of generating a mathematical expression, the vector value of the generated prior learning language model is input and the decoder 320 of the mathematical expression generation model 300 generates the mathematical expression step by step.

The decoder 320 of the mathematical expression generation model 300 generates one operator at each step and copies the required operands from one or more of a recombination problem, a circle problem, a predefined constant value, or the result of a previous calculation step. . Finally, the generated mathematical expression is converted into an equation to solve the problem. If you calculate the converted equation, you can get the answer through the mathematical equation solving library.

The decoder 320 of the mathematical expression generation model 300 generates a mathematical expression using the recombined context vector as a memory. The mathematical expression generation model 300 utilizes the operating principle of the decoder described in FIG. 4 to generate a mathematical expression using an expression token unit, which is a group of operators and related operands.

The decoder 320 of the mathematical expression generation model 300 predicts the next jth token. First, the decoder 320 receives the expression tokens generated so far and converts them into an embedding vector v _k (k=0, ..., j-1). Then, using these embedding vectors v _k and the recombined context vector r _i , decoder 320 builds the mathematical context vector q _j for the next jth token. Finally, the decoder 320 uses the mathematical context vector q _j to predict the next operator and related operands.

In the operation of creating a mathematical equation, the explanation is used as an input data source to ensure the fidelity of the explanation. Change the input format of numbers and variables so that explanatory sentences can be used in the decoder of the mathematical expression generation model described in Figure 4. The decoder of the mathematical expression generation model described in Figure 4 inputs different types of vectors corresponding to the encoder's hidden state vector for each known number and the decoder's hidden state vector for each unknown variable.

The decoder 320 of the mathematical equation generation model 300 of the artificial neural network model according to this embodiment learns the model to generate a mathematical equation using information in the description. Since all numbers and variables appear in the recombination problem, the decoder 320 of the mathematical expression generation model 300 of the artificial neural network model according to this embodiment uses the recombination context vector r _i corresponding to each number/variable.

For learning and verification of the artificial neural network model according to this embodiment, PEN (Problem with Explanation for Numbers) is a sentential algebra problem data set containing problem text, mathematical equations, and explanations of numbers/variables for each problem. Design the data set.

Building a PEN data set goes through a data set selection stage, an error correction preparation stage, and an annotation stage to collect descriptions.

In the data set selection step, source data sets are collected. The data set should contain English word problems, most problems in the data set should use algebraic equations to solve the problem, and the data set should contain a gold standard equation for each problem.

In the error correction preparation stage, errors are corrected and data is organized. First, correct any typos, grammatical errors, or logical errors. Next, we extract the number type from the modified text. Sentence problems can contain numeric data that can be used to set up equations. Numeric data can be written in a variety of forms, such as Arabic numerals, fractions, ordinal numbers, or other representations of numbers (e.g., dozen). Finally, normalize the solution equation. Reconstruct the equation based on the predefined formula as shown in Table 6 below.

[Table 6]

In the annotation step to collect explanations, explanations for each number/variable in the problem are collected. Using a web-based system, you enter a natural language description for each number/variable and complete the sentence based on the given information. To ensure that the description matches the problem, we use two strategies: rules and validation, defined as shown in Table 7 below.

[Table 7]

Rule 1 requires you to write a description of the situation represented by the number/variable using words that appear in the text. Rule 2 is that each description is a simple noun phrase consisting of 3 to 25 words, so write it concisely. Rule 3 tells you to use at least one word that appears in the question text when writing your explanation. Rule 4 ensures that you do not use the same description for different entities. Rule 5 allows us to formulate an equation to solve the problem from the description alone. Rule 6 tells us to write the difference A-B as “the value of A minus the value of B.” Rule 7 requires that the ratio A/B be written as “the ratio of A to B.” Rule 8 states that the numerator [denominator] of A/B should be written as “the numerator [denominator] of the ratio A to B.”

The web-based system continuously checks whether the author complies with the rules, and if one of the first four rules is violated, the system warns the author to follow the violated rule before proceeding to the next issue. For the other four rules, the system displays hints so that the author can manually check the rules.

The size of the completed PEN data set is shown in Table 8 below.

[Table 8]

For the artificial neural network model (EPT-X) according to this embodiment, the PEN data set is used to measure the correct answer rate, which is the proportion of problems answered correctly. The order of variables in the generated equation is considered, and if the generated equation matches the optimal standard equation, it is considered correct.

The EPT in Figure 4 shows a correct answer rate of 74.52%, and the EPT-X in Figure 7 shows a correct answer rate of 69.59% even though it outputs an additional explanation.

Figures 8 and 9 are diagrams illustrating ablation analysis of an artificial neural network model applied to a problem-solving device according to an embodiment.

In order to check the balance between accuracy and fidelity, testing is performed after changing the input data and data path of the mathematical equation generation model of the artificial neural network model.

The model shown in Figure 8 is a model (EPTX+F) that inputs only explanatory text into the mathematical equation generation model. EPTX+F may be vulnerable to situations where an error occurs in the generated explanation because the decoder of the mathematical expression generation model depends only on the output of the decoder of the explanation generation model.

The model shown in Figure 9 is a model (EPTX+U) that inputs only the original problem into the equation generation model. EPTX+U does not utilize explanatory text, so fidelity cannot be secured.

Table 9 below shows the results of comparing EPT-X, EPTX+F, and EPTX+U.

[Table 9]

The validity of the explanation can be confirmed by measuring the similarity of the explanation. BLEU (a Method for Automatic Evaluation of Machine Translation, Papineni et al., 2002), ROUGE (A Package for Automatic Evaluation of Summaries, Lin, 2004), CIDEr (Consensus-based Image Description Evaluation, Vedantam et al., 2015) , and BLEURT (Learning Robust Metrics for Text Generation, Sellam et al., 2020) are methods for measuring the similarity of descriptions.

It can be seen that the correct answer rate is improved in the model (EPT-X) in which the original problem and the generated explanation are input together than in the model in which only the generated explanation is input (EPTX+F). This is because the explanatory text supplements the contextual information of the original problem. The correct answer rate may slightly improve in the model that inputs only the original problem (EPTX+U) compared to the model that inputs both the original problem and the generated explanation (EPT-X), but the model that inputs only the original problem (EPTX+U) has lower fidelity. There are limits that cannot be secured. The reason EPT-X, EPTX+F, and EPTX+U have a high percentage of correct answers is because they preserve context information by using expression token units that group operators and operands.

10 and 11 are flowcharts of a problem solving method according to another embodiment.

The problem-solving method according to the embodiment shown in FIGS. 10 and 11 includes steps processed in time series in the problem-solving device shown in FIG. 1. Therefore, even if the content is omitted below, the content described above regarding the problem solving device shown in FIG. 1 can also be applied to the problem solving method according to the embodiment shown in FIGS. 10 and 11.

Referring to FIG. 10, in step S1010, the problem solving device 100 receives a sentence-type math problem and generates and outputs an explanation about the numbers and variables contained in the sentence-type math problem through an encoder-decoder-based description generation model. do.

In the step of generating and outputting an explanation (S1010), the encoder of the explanation generation model receives the sentence-type math problem as input, segments it into tokens, and outputs a problem context vector representing the context information of the sentence-type math problem for each token.

In the step of generating and outputting an explanation (S1010), the variable predictor connected between the encoder and decoder of the explanation generation model receives the problem context vector and transforms the representative value to predict the number of variables needed to solve the sentence-type math problem.

In the step of generating and outputting an explanation (S1010), the decoder of the explanation generation model receives the problem context vector, variables considering the number of variables, and the number of sentence-type math problems, and hides the decoder based on the previously generated explanation token. Calculate the state.

In the step of generating and outputting a description (S1010), a pointer generator connected to the decoder of the description generation model receives the hidden state of the decoder and predicts the next description token.

In step S1020, the problem solving device 100 receives a sentence-type math problem, a generated explanation, or a combination thereof, generates a math equation through an encoder-decoder-based math equation generation model, and outputs it.

Referring to FIG. 11, the step of generating and outputting a mathematical equation (S1020) converts the generated description into a sentence and creates a recombination problem. The step of generating and outputting a mathematical formula (S1020) is a step of restructuring the explanatory statement about the number generated by selecting the context in which the number is located in the sentence-type math problem through the explanatory statement generation model into a first sentence (S1110), the explanatory statement A step of restructuring the description of the variable created using the index of the variable through the generative model into a second sentence (S1120), and combining the restructured first and second sentences to create a recombination problem ( S1130).

In the step of generating and outputting a mathematical equation (S1020), the recombination problem and the sentence-type mathematical problem are input to the encoder of the mathematical equation generation model.

In the step of generating and outputting a mathematical equation (S1020), the encoder of the mathematical equation generation model receives a recombination problem and a sentence-type math problem as input and outputs a recombination context vector.

In the step of generating and outputting a mathematical expression (S1020), the decoder of the mathematical expression generation model receives the recombined context vector and generates a mathematical expression using expression token units that group operators and necessary operands.

The generated mathematical expression can be answered through the mathematical equation solving library.

The term '~unit' used in the above embodiments refers to software or hardware components such as FPGA (field programmable gate array) or ASIC, and the '~unit' performs certain roles. However, '~part' is not limited to software or hardware. The '~ part' may be configured to reside in an addressable storage medium and may be configured to reproduce on one or more processors. Therefore, as an example, '~ part' refers to components such as software components, object-oriented software components, class components, and task components, processes, functions, properties, and procedures. , subroutines, segments of program code, drivers, firmware, microcode, circuits, data, databases, data structures, tables, arrays and variables.

The functions provided within the components and 'parts' may be combined into a smaller number of components and 'parts' or may be separated from additional components and 'parts'.

In addition, components and 'parts' may be implemented to reproduce one or more CPUs/GPUs within a device or a secure multimedia card.

Meanwhile, the problem-solving method according to an embodiment described through this specification may also be implemented in the form of a computer-readable medium that stores instructions and data executable by a computer. At this time, instructions and data can be stored in the form of program code, and when executed by a processor, they can generate a certain program module and perform a certain operation. Additionally, computer-readable media can be any available media that can be accessed by a computer and includes both volatile and non-volatile media, removable and non-removable media. Additionally, computer-readable media may be computer recording media, which are volatile and non-volatile implemented in any method or technology for storage of information such as computer-readable instructions, data structures, program modules, or other data. It can include both volatile, removable and non-removable media. For example, computer recording media may be magnetic storage media such as HDDs and SSDs, optical recording media such as CDs, DVDs, and Blu-ray discs, or memory included in servers accessible through a network.

Additionally, the problem-solving method according to an embodiment described through this specification may be implemented as a computer program (or computer program product) including instructions executable by a computer. A computer program includes programmable machine instructions processed by a processor and may be implemented in a high-level programming language, object-oriented programming language, assembly language, or machine language. . Additionally, the computer program may be recorded on a tangible computer-readable recording medium (eg, memory, hard disk, magnetic/optical medium, or solid-state drive (SSD)).

Accordingly, the problem-solving method according to an embodiment described throughout this specification can be implemented by executing the above-described computer program by a computing device. The computing device may include at least some of a processor, memory, a storage device, a high-speed interface connected to the memory and a high-speed expansion port, and a low-speed interface connected to a low-speed bus and a storage device. Each of these components is connected to one another using various buses and may be mounted on a common motherboard or in some other suitable manner.

Here, the processor can process instructions within the computing device, such as displaying graphical information to provide a graphic user interface (GUI) on an external input or output device, such as a display connected to a high-speed interface. These may include instructions stored in memory or a storage device. In other embodiments, multiple processors and/or multiple buses may be utilized along with multiple memories and memory types as appropriate. Additionally, the processor may be implemented as a chipset consisting of chips including multiple independent analog and/or digital processors.

Additionally, memory stores information within a computing device. In one example, memory may be comprised of volatile memory units or sets thereof. As another example, memory may consist of non-volatile memory units or sets thereof. The memory may also be another type of computer-readable medium, such as a magnetic or optical disk.

Additionally, the storage device can provide a large amount of storage space to the computing device. A storage device may be a computer-readable medium or a configuration that includes such media, and may include, for example, devices or other components within a storage area network (SAN), such as a floppy disk device, a hard disk device, an optical disk device, Or it may be a tape device, flash memory, or other similar semiconductor memory device or device array.

The above-described embodiments are for illustrative purposes, and those of ordinary skill in the technical field to which the above-described embodiments belong will recognize that they can be easily modified into other specific forms without changing the technical idea or essential features of the above-described embodiments. You will understand. Therefore, the embodiments described above should be understood in all respects as illustrative and not restrictive. For example, each component described as unitary may be implemented in a distributed manner, and similarly, components described as distributed may also be implemented in a combined form.

The scope sought to be protected through this specification is indicated by the patent claims described later rather than the detailed description above, and all changes or modified forms derived from the meaning and scope of the claims and their equivalent concepts are included in the scope of the present invention. It should be interpreted as being

100: Problem solving device
110: input/output unit
120: storage unit
130: control unit

Claims (10)

An input/output unit for receiving data and outputting the results of processing the data;
a storage unit in which a program for performing a problem solving method is stored; and
It includes at least one process, and includes a control unit that analyzes data received through the input/output unit by executing the program,
The control unit,
Receives a sentence-type math problem as input, generates and outputs an explanation about the numbers and variables contained in the sentence-type math problem through an encoder-decoder-based explanation generation model,
A problem-solving device that receives the sentence-type math problem, the generated explanation, or a combination thereof, and generates and outputs a math equation through an encoder-decoder-based math equation generation model. According to claim 1,
The encoder of the explanation generation model receives the sentence-type math problem as input, segments it into tokens, and outputs a problem context vector representing context information of the sentence-type math problem for each token,
The explanation generation model includes a variable predictor connected between the encoder and the decoder of the explanation generation model, and the variable predictor receives the problem context vector and transforms a representative value to determine the variable necessary to solve the sentence-type math problem. Predict the number of
The decoder of the explanation generation model receives the problem context vector, a variable considering the number of variables, and the number of sentence-type math problems, and calculates a hidden state of the decoder based on a previously generated explanation token,
The explanation generation model includes a pointer generator connected to the decoder, and the pointer generator receives the hidden state of the decoder and predicts the next explanation token. According to claim 1,
The control unit,
Restructuring the explanatory sentence about the number generated by selecting the context in which the number is located in the sentence-type math problem through the explanatory sentence generation model into a first sentence,
Restructuring the description of the variable generated using the index of the variable through the description generation model into a second sentence,
A problem-solving device that combines the restructured first sentence and the second sentence to create a recombination problem. According to claim 3,
The control unit,
Input the recombination problem and the sentence-type math problem into the encoder of the equation generation model,
The encoder of the mathematical expression generation model receives the recombination problem and the sentence-type math problem and outputs a recombination context vector,
The decoder of the mathematical expression generation model receives the recombined context vector and generates the mathematical expression using expression token units that group operators and necessary operands. In the problem solving method using a problem solving device,
A step of receiving a sentence-type math problem as an input and generating and outputting a description of numbers and variables contained in the sentence-type math problem through an encoder-decoder-based description generation model; and
A problem-solving method comprising receiving the sentence-type math problem, the generated explanation, or a combination thereof, and generating and outputting a math equation through an encoder-decoder-based math equation generation model. According to claim 5,
The encoder of the explanation generation model receives the sentence-type math problem as input, segments it into tokens, and outputs a problem context vector representing context information of the sentence-type math problem for each token,
The explanation generation model includes a variable predictor connected between the encoder and the decoder of the explanation generation model, and the variable predictor receives the problem context vector and transforms a representative value to determine the variable necessary to solve the sentence-type math problem. Predict the number of
The decoder of the explanation generation model receives the problem context vector, a variable considering the number of variables, and the number of sentence-type math problems, and calculates a hidden state of the decoder based on a previously generated explanation token,
The explanation generation model includes a pointer generator connected to the decoder, and the pointer generator receives the hidden state of the decoder and predicts the next explanation token. According to claim 5,
The step of generating and outputting the above equation is,
Restructuring the explanatory sentence about the number generated by selecting the context in which the number is located in the sentence-type math problem through the explanatory sentence generation model into a first sentence,
Restructuring the description of the variable generated using the index of the variable through the description generation model into a second sentence,
A problem-solving method that combines the restructured first sentence and the second sentence to create a recombination problem. According to claim 7,
The step of generating and outputting the above equation is,
Inputting the recombination problem and the sentence-type math problem into the encoder of the equation generation model,
The encoder of the mathematical expression generation model receives the recombination problem and the sentence-type math problem and outputs a recombination context vector,
The decoder of the mathematical expression generation model receives the recombined context vector and generates the mathematical expression using expression token units that group operators and necessary operands. A computer-readable recording medium on which a program for performing the method according to claim 5 is recorded. A computer program performed by a problem-solving device and stored in a recording medium to perform the method described in claim 5.