Error correction of semantic mathematical expressions based on bayesian algorithm

1.   Introduction

In the Information Era, the exchange and sharing of scientific information through electronic documents has been increasingly used, of which the Chinese scientific documents contain a large number of mathematical expressions. Therefore, it is of great significance to research the representation of mathematical expressions for the retrieval of scientific documents ^[1,2]. Meanwhile, semantic expressions with semantic information play a key role in related research ^[3,4,5].

Two kinds of markup to describe mathematical expressions are provided by MathML: presentation markup and content markup ^[6,7]. Mathematical expressions encoded with presentation markup are referred to as presentational expressions (presentation MathML) which focus on the layout of expressions and can preserve the prototypes of operators and operands, but do not contain semantic information. Mathematical expressions coded with content markup are referred to as semantic expressions (content MathML) which focus on the semantic information for calculation and processing, and contain the internal meaning of the expressions.

The experimental result of Michal et al. ^[8,9] showed that their search system performs best using content MathML queries. The explanation they given is that with content MathML there is smaller degree of ambiguity than with presentation MathML. These studies use English electronic scientific documents which are included in the NTCIR dataset ^[10] as datasets for experiments. The English scientific documents in the NTCIR dataset were sorted out by professionals. Each mathematical expression of these documents contains well-formed presentation MathML and content MathML.

However, some Chinese scientific documents contain only presentational expressions (presentation MathML). For example, the Chinese scientific documents collected by the laboratory from natural science journals on the CNKI (China National Knowledge Infrastructure) ^[11] website. Therefore, we are committed to automatically generate valid content MathML from presentation MathML in the CNKI dataset. The valid content MathML means that it has the correct indentation format and symbol order. In particular, the valid content MathML means that it can represent a complete mathematical expression and be displayed accurately on a webpage. In addition, the valid content MathML can facilitate in-depth research on expression similarity calculation and retrieval. Thus, it has become an urgent problem to obtain content MathML based on presentation MathML.

2.   Related works

The problem of format conversion of mathematical expressions has been studied for a long history.

Early on, Zhang et al. ^[12] used the principles of linked list and stacking and combined with the priority of operators to gradually replace the DOM tree nodes of semantic expressions, so that the interconversion between Content format and Infix format was realized. Hussain et al. ^[13] used abstract syntax tree to extract the structural information in LaTeX expressions, and generate XML structured mathematical expression. Zhu et al. ^[14] established a MathML to LaTeX conversion model by analyzing and studying the MathML structure and content information, and realized the conversion from MathML to LaTeX expressions. Su et al. ^[15] proposed a notation selection strategy to convert from Content MathML to Presentation MathML while using four conversion methods: element-to-element, element-to-text, attribute-to-attribute and structure-to-structure.

Schubotz et al. ^[16] presented a new approach that combines textual features with the converts to improve the outcome of mathematical format conversions and compared several LaTeX to MathML converters and they found that many converters simply do not support the conversion from presentation to Content format. Due to the particularity of the markups and internal structure in the expressions in the MathML format, as well as the lack of semantic information in presentational expressions, there is a little research on the conversion between the Presentation format and the Content format. Cai et al. ^[17] proposed a method for determining ambiguous content in expressions using type prediction. During the expressions conversion process, all symbols in the expression are first identified using a lexical analyzer, and then the type system converts the expression based on the obtained expression information. Doush et al. ^[18] used a kind of RDFa (Resource Description Framework in attributes) annotation to add the corresponding semantic information framework to expression conversion process. In this way, the expression is converted from presentation MathML to content MathML. Nghiem et al. ^[19] proposed a system that applied segmentation rules and translation rules to generate the corresponding content MathML tree from the given presentation MathML tree. Toloaca and Kohlhase ^[20] proposed the MathSemantifier system that converts a meaning tree to content MathML and displays the content MathML trees in the frontend. Using the system, they can convert presentation MathML to content MathML.

Presentational expressions have a strong two-dimensional structure, and pay more attention to the display of mathematical expressions. The complexity and ambiguity of operator notations in mathematical expressions, as Greiner-Petter et al. ^[21] pointed, have important affect for mathematical expressions format conversion. Grigore et al. ^[22] presented a preliminary study on disambiguation of symbolic expressions in mathematical documents. Their approach was based on the use of contextual information which is contained in the natural language surrounding the target mathematical expression. Then, disambiguation would be completed by computing a semantic similarity between the words from the lexical context of the given expression and a set of terms from term clusters based on OpenMath. Semantic expressions benefit from more markups advantages and pay more attention to the semantic information of mathematical expressions. For example, the order in which operators and operands of the semantic expression $(a + b)*(c + d)$ appears as $*, +, a, b, +, c, d$. With the rule mapping method, the two-dimensional structure of multiplication cannot be correctly processed, which gives a wrong expression. The order of operators and operands in the wrong expression is $+, a, b, *, +, c, d$, so the expression encoded in content MathML format cannot be displayed accurately on the web page. To obtain an accurate expression, it is necessary to perform error correction on the semantic expression.

Error correction techniques have been widely used in the fields of grammar correction in natural languages ^[23,24], spelling error correction ^[25], and text input and recognition ^[26]. Inspired by the error detection and correction model ^[27] for input text, this study uses a Bayesian algorithm ^[28] to correct errors in expressions, aided by edit distance algorithm ^[29,30], in the process of expression error correction by applying Bayesian error correction algorithm to error correct the wrong expressions.

Bayesian algorithm is a common probability model ^[31,32,33] which plays a significant role in the research and development of spam filtering, content recommendation, and spelling error detection, etc. ^{[34,35,36,37,38,39,40]}. It has the advantages of simple theory, clear algorithm logic, easy implementation, and fast training speed. The Bayesian algorithm is applied to the error correction of mathematical expressions, which solves the problem of low precision of expression format conversion and improves the accuracy of error correction.

The Bayesian algorithm is used in this study to correct errors in mathematical expressions obtained by the rule mapping method. The problem of incorrect display of converted expressions is solved, and expressions with semantic information are obtained. This study provides a benchmark for similarity calculation and expression retrieval system research, as well as ideas and references for the field of error detection and correction.

3.   Error correction of semantic mathematical expressions

The overall process of error correction of semantic mathematical expressions based on the Bayesian algorithm consists of two parts. The overall flow chart is shown in Figure 1.

Part one: Presentation MathML and content MathML are extracted from the documents in the training set. According to the content information and statistical results, mapping rules are constructed and a data dictionary is established.

Part two: The expressions in presentation MathML format in the test set are reformatted for correct indentation. The method of rule mapping converts presentational expressions in presentation MathML format into semantic expressions in content MathML format and then we correct those semantic expressions that cannot be presented correctly in web pages. In the error correction process, candidate sets are generated according to the data dictionary and the edit distance algorithm. The Bayesian probability of each expression in candidate sets is calculated after that. The expression with the highest probability is selected as the final result of the error correction expression.

3.1.   Mapping rules for expressions markups

Both presentational expressions and semantic expressions contain a large number of markups. Through a large amount of statistical information, it is known that a content markup may correspond several presentation markups. Therefore, creating a set of mapping rules for expressions markups is a key step to obtain semantic expressions and an important prerequisite for subsequent error correction of expressions.

The training set is used to build the mapping rules. In the data set of this study, there are three encoding formats for expressions in English electronic scientific documents: presentation MathML, content MathML and LaTeX expressions. First, the required presentation MathML expressions and content MathML expressions are extracted from the documents in the training set. Then mapping rules are constructed based on the contents of the expressions' markups and the tree encoding form, and are presented in terms of both content and structure. The specific algorithm is shown in Algorithm 1.

Content: Since both types of expressions have a large of markups, the exact correspondence of the markups is undoubtedly an important part of the process when converting from one type to the other when constructing mapping rules. Table 1 shows the example of expression $a + b$.

The start tag < math > and its corresponding end tag < /math > in the first and last lines indicate the expression is expressed in mathematical markup language (MathML). The < mrow > tag in the second line is used to group the subexpressions of an expression. An expression is usually composed of one or more subexpressions. The < apply > tag acts as an encapsulates in the expressions and is the most basic element in semantic markups. In general, the < mrow > tag corresponds to the < apply > tag. The < mi > tag in the fifth line displays the symbolic constants in the expression and corresponds to the < ci > tag in the semantic expression.

In addition, operators in presentation MathML expressions are usually contained by a pair of < mo > < /mo > . However, operators in content MathML expressions usually have their own specific tag representations. For example, the markups corresponding to $+$, $-$, $*$, and $\div$ are < plus/ > , < minus/ > , < times/ > , and < divide/ > , respectively.

Structure: Table 1 shows that the presentation MathML expressions are typeset in the order in which the operators and operands appear in the expression, while the content MathML expressions are different. The content MathML expressions obtained according to the content of presentation MathML expressions and combined with the mapping rules differ from the accurate content MathML expressions in part of the structure. Therefore, to address the impact of this problem in the experiment, this study constructs a data dictionary through statistics and data analysis and combines it with the Bayesian algorithm to correct wrong expressions and achieve expected results. Table 2 shows the correspondence between some commonly used symbols.

3.2.   Edit distance algorithm

In the course of the experiments, it was found that the reason why the content MathML expressions obtained after conversion could not be displayed properly in the web pages was that the positions between symbols and sub-formulas in the expressions crossed. In this study, inspired by the calculation of edit distance and graph edit distance ^[41,42], the edit distance algorithm is used to generate candidate sets. Edit distance is the minimum number of edit operations required for two sentences to become a unified form, and there are three types of edit operations: add, delete, and replace. For the convenience of calculation, when correcting symbol errors, the contents of the sub-formulae adjacent to the operator are ignored and only the start and end tags of the sub-formulae are retained, and each tag being recorded as a character. This study takes $x + y = z$ as an example to elaborate, as shown in Table 3.

In particular, the "wrong expression" in Table 3 refers to the expression that converted from presentation MathML to content MathML cannot be displayed accurately on the electronic scientific documents and webpage. Therefore, we consider that the content MathML cannot represent correct semantic information of the corresponding mathematical expression because of the wrong order of the nodes. Content MathML has a strict indentation. Content MathML requires not only that the parameter types of the operators and operands in mathematical expressions are accurate, but also that the order of nodes is correct. So, the wrong expression caused by the wrong order of the nodes requires error correction.

The first column in Table 3 is the presentation MathML that would be converted to content MathML. The second column is the content MathML obtained by using the rule mapping method to convert presentation MathML. But this content MathML cannot be displayed accurately on the electronic scientific documents and webpage because of the wrong order of the nodes. Because this content MathML cannot represent correct semantic information of the corresponding mathematical expression, it requires error correction. The third column is the wrong part of the content MathML that requires to be corrected. The fourth column is the candidate set generated by using the edit distance algorithm for the wrong part of the content MathML. The fifth column is the content MathML obtained by using the Bayesian algorithm error correction. This content MathML can be displayed accurately on the electronic scientific documents and webpage and represent correct semantic information of the corresponding mathematical expression.

3.3.   Bayesian algorithm

3.3.1.   The basic idea of Bayesian formula

The Bayesian error correction algorithm is based on the Bayesian formula. By observing the prior probability of the data and combining it with the conditional probability, the Bayesian formula is used to calculate the posterior probability and select the best data in the candidate set as its error correction object.

The Bayesian formula is defined as follows: This study assumes that in a randomized experiment $Q$, ${h_1}, {h_2}, \cdots, {h_n}$ are a division of the sample space $\Omega$, where $P\left({{h_i}} \right) > 0$ and $i = 1, 2 \cdots, n$. In addition, $D$ is the observation data in $Q$ and $P\left(D \right) > 0$. $D$ only has a corresponding relationship with certain data in the sample space. The Bayesian formula is

3.3.2.   Error correction algorithm

With the Bayesian algorithm in this study, we assume that $R = \left\{ {{R_1}, {R_2}, \cdots, \left. {{R_{\text{n}}}} \right\}} \right.$ is the set of candidate expressions, and $E = \left\{ {{E_1}, {E_2}, \cdots, {E_{\text{n}}}} \right\}$ is an incorrect expression with n sub-formulas. The task of the Bayesian error correction algorithm is to compute the most accurate error correction object ${R_i}$ based on the set of candidate expressions ${E_i}$ to be corrected. According to Eq (1), the Bayesian error correction algorithm is briefly described as: For any wrong expression $E$, combined with the Bayesian formula on the basis of prior probability, is calculated to obtain the only accurate expression ${R_i}$ with the maximum possible error expression $E$.

According to Eq (1), the Bayesian error correction algorithm is expressed as follows.

The necessary and sufficient conditions that the corrected object of expression $E$ to be corrected is the expression ${R_i}$ is

where $P\left({{R_i}|E} \right)$ denotes the probability that the expression ${R_i}$ is the expression $E$'s error correction target. The process of solving for the correct expression can be translated into solving for ${R_i}$ that maximizes the value of $P\left({{R_i}|E} \right)$. Since ${R_i} \in R$ and random $E$, the following equation is obtained:

where $\Sigma \left({{R_i}} \right)$ is the number of expressions ${R_i}$ in the data set. That is, no matter which $R$ is the optimal error correction target of $E$, $P\left(E \right)$ is the same value. So, the expression of the Bayesian error correction algorithm can be simplified as

where $P\left({{R_i}} \right)$ represents the prior probability as

where $\left| S \right|$ is the total number of samples of the expressions in the data set and $\left| {{S_{{R_i}}}} \right|$is the number of samples in the data set that contains ${R_i}$.

For the calculation of $P\left({E\left| {{R_i}} \right.} \right)$, if there are multiple parts of the expressions to be corrected that require error correction, in order to reduce the time and space complexity of the calculation process. In particular, assuming that the conditions are independent of each other, it can be described as shown in Eq (7).

The value of $P\left({{E_k}\left| {{R_i}} \right.} \right)$ can be derived by training the sample expressions in the data set, according to the statistics shown in Figure 2. This study assumes that the expressions are continuous attributes obeying Gaussian distribution, they can be described as shown in Eq (8). The $f\left({\chi; \mu, \sigma } \right)$ is the Gaussian density function, $\mu$ is the average value, and $\sigma$ is the standard deviation.

In summary, for the sample expression $E$ the value of $P\left({E\left| {{R_i}} \right.} \right)P\left({{R_i}} \right)$ is calculated and the expression with the highest probability is the corrected object of $E$. It can be described as shown in Eq (9). To reduce the calculation error, this study takes the logarithm for Eq (9), as shown in Eq (10).

An expression usually contains at least one mathematical symbol. Therefore, in the process of correcting mathematical expressions, it is necessary to check the symbols in the expressions one by one and then correct them. First, the expression is selected from the data set as the expression to be corrected. Then, the expression is traversed to locate the symbol tag and find the two sub-expressions adjacent to is so that it is a part to be corrected. Next, the candidate set is generated using the edit distance algorithm with the symbols to be corrected as the target and the expressions in the data set. Finally, the result is calculated and sorted according to the Bayesian formula and the best one is selected. These steps are repeated until all symbols in the error expression are corrected. The general process is shown in Algorithm 2.

4.   Experimental results and analysis

4.1.   Experimental data and environment

The experiment is implemented in the JDK (Java Development Kit) 1.8 environment. The Eclipse platform and the Java language are used to program the experiment. The experimental environment is shown in Table 4.

The public data set Ntcri-Mathir-Wikipedia-Corpus is used as the training set in this study. This data set contains 11,792 documents and 124,878 expressions have been extracted, which are used to establish mapping rules and build a data dictionary for the experiment. The test set used in the experiment is 78,348 expressions extracted from 10,372 Chinese documents collected by the laboratory from the CNKI website.

4.2.   Experiment result and data analysis

In order to verify the effectiveness of the algorithm in this paper quickly and efficiently, an unduplicated random sample of any 5000 mathematical expressions are selected and divided into 10 groups for the experiment. The experimental results are analyzed from three aspects: the conversion result of the rule mapping method, the performance of the Bayesian error correction algorithm, and the time efficiency of the algorithm.

4.2.1.   Evaluation metrics

In order to present the experimental results clearly, the comprehensive evaluation metrics F-Measure is used in this study to evaluate the experimental results. F-Measure is the weighted harmonic average of precision $P$ and recall $R$, as shown in Eq (11):

The most common ${F_1}$ with $\alpha = 1$ is adopted in this study, as shown in Eq (12). The higher the ${F_1}$, the better the performance. The precision $P$ and recall $R$ are calculated as shown in Eqs (13) and (14) respectively, where $N$ denotes the total number of expressions in the current sample group. $TN$ denotes the total number of expressions that can be accurately represented in the web page by the semantic expressions obtained by the rule mapping method, i.e., accurate expressions. $FN$ denotes the total number of expressions that are not accurately represented in the web page by the semantic expressions obtained by the rule mapping method, i.e., the expressions to be corrected. ${T_{FN}}$ denotes the total number of expressions that can be accurately represented in the web page after Bayesian error correction. The error correction rate is represented by $cr$. The specific equations are shown as follows.

4.2.2.   Conversion result and analysis of the rule mapping method

This study conducts experiments on 10 sets of sample expressions respectively. The rule mapping method is used to convert presentational expressions into semantic expressions and the number of expressions that can be converted is recorded. Semantic expressions are tested manually whether they can be presented as the corresponding mathematical expressions in the web page. If they can be presented as the corresponding mathematical expressions, they are accurate expressions. Otherwise, they are expressions that need to be corrected.

From Table 5, it can be seen that not all presentational expressions can be converted to semantic expressions using the rule mapping method. The reason is that in presentational expressions, irregular expressions can be represented as presentation MathML, such as poorly formatted expressions $xy +$, $x -$, and so on. However, these incomplete expressions cannot be encoded as content MathML in semantic expressions. Therefore, with the rule mapping method, they cannot be fully converted.

4.2.3.   Performance analysis of the Bayesian error correction algorithm

The comparison results of the number of accurate expressions and F-measures of the rule mapping method and the Bayesian algorithm are shown in Figure 3. The error correction rate of the Bayesian algorithm on 10 sets of experimental data is shown in Table 6.

It can be seen from Figure 3 that a certain number of accurate expressions can be directly obtained by the rule mapping method, because there are some simple expressions in the data set, such as $+$, $-$, $*$, and $\div$, from which the rule mapping method can directly get accurate expressions.

The experimental data of the first, fifth, sixth, and ninth groups show that the error correction rate is lower than the average, and the ${F_1}$ value after the Bayesian error correction algorithm is also lower than those of the other groups. The main reasons are as follows. First, the data set contains some expressions with special symbols, such as the $bra - ket$ symbolic. The symbol is denoted by $\left\langle {\phi } \mathrel{\left | {\vphantom {\phi \psi }} \right. } {\psi } \right\rangle$, consisting of a left part $\left\langle \phi \right|$ called the bra, and a right part $\left\langle \psi \right|$ called the ket. In the process of conversion and error correction, it is not possible to obtain the corresponding accurate semantic expressions based only on the content information in the presentational expressions. Second, a symbol can represent multiple meanings, such as $\left({} \right)$ which can represent an interval $\left({ - \pi, \pi } \right)$, a vector $\left({x, y} \right)$, a binomial$\left({\begin{array}{*{20}{c}} n \\ k \end{array}} \right)$, and so on. Their content markups are < interval > , < vector > , and < binomial > . Therefore, a certain error may occur during error correction, and the process of error correction may fail. Third, due to the insufficient number of expressions in the data set, the statistical results are biased and the final results are affected.

4.2.4.   Analysis of response time

In this study, the presentational expressions in Chinese electronic scientific documents are converted to semantic expressions with semantic information by using rule mapping method. However, using only the rule mapping method can cause problems such as incorrect structure of mathematical expressions. Therefore, the Bayesian error correction method is designed to correct the obtained wrong expressions. The response time of the two methods is shown in Figure 4. It can be seen from Figure 4 that the response time of the system increases as the number of expressions increases. Since the Bayesian error correction algorithm is a step after the rule mapping method, it causes an increase in response time. However, the increase in time complexity is not large and is still within an acceptable range. Therefore, this method is considered reasonable given the premise of improving the accuracy of the experimental results.

5.   Conclusions and future works

This study addresses the problem that the expressions with semantic information obtained by using only the rule mapping method are prone to errors, this study proposes a Bayesian algorithm to perform semantic errors correction on the converted expressions. In the semantic error correction process, the candidate sets are obtained by combining the edit distance algorithm. And then, the probability of each expression in the candidate set is calculated by Bayesian formula. Finally, these expressions are sorted to get the best result.

The presentational expressions and semantic expressions in the data set NTCIR are used as the training set in this study. Based on the markups and syntactic structure of the two formats, the mapping rules for the expression format conversion are formulated, and the parameters of the Bayesian error correction algorithm are statistically trained. The presentational expressions in the data set collected by the laboratory are used as the test set to test the performance of the algorithm. The experimental results prove that the average ${F_1}$ value of the method using only the rule mapping is 0.239, and the average ${F_1}$ value of the method using Bayesian error correction is 0.881, which is a significant improvement over the former. The average error correction rate $cr$ is 0.853, indicating that the Bayesian error correction algorithm can effectively correct the semantic of expressions. Since the Bayesian algorithm is performed on the basis of the rule mapping method, the response time increases. But the increase is within an acceptable range. Therefore, under the premise of improving the accuracy of the experimental results, this method is reasonable and the experiment has research significance.

Since presentational expressions focus more on the content in the expression and display only the symbols. Semantic expressions focus more on the inner meaning of the expression and need to display mathematical information. From the experimental, it is clear that the ambiguity of the symbols may have some influence on the results. For example, "e'' in expressions have different semantics in different situations. It can represent either a variable or a mathematical constant in an expression. To solve the problem of semantic ambiguity of mathematical expressions, in the next step of our study, on the one hand, we will try to disambiguate expressions by combining the relevant textual context of the mathematical expression; on the other hand, we will try to expand the content dictionaries to correctly define more complex functions. In addition, when the Bayesian formula is used for calculation, the statistical result of the expression content in the data set is required. Therefore, to make the experimental results more robust, the experimental data set needs to be enriched.

Acknowledgments

This work was supported by Science and Technology Project of Hebei Education Department (ZD2019131), the Natural Science Foundation of Hebei Province (F2019201451) and "One province, one university" fund of Hebei University (521000981155).

Conflict of interest

The authors declare no conflict of interest.