1 Introduction
1.1 Motivation
Writing, which is an important indicator for assessing a test taker’s language skill, is an essential part of language tests. In Chinese language tests, test takers are usually required to write an essay according to a given topic, and then human raters will score these essays on the basis of some given educational benchmarks. It often happens that the scores of an identical essay scored by different human raters vary considerably because scoring by human raters is subjective (Peng Reference Peng2005; Li et al. Reference Li, Peng and Zhao2011; Peng et al. Reference Peng, Ke and Xu2012; Peng and Yu Reference Peng and Yu2013). In addition, as the number of the MHK test takers increases rapidly year by year, it becomes a huge and expensive task for the organizers to score the essays. Therefore, an accurate automated simplified Chinese essay scoring system reducing both costs and evaluation time is urgently needed.
1.2 Research background
Many automated English essay scoring systems have been developed over the past several decades. Project Essay Grader (PEG) is the earliest automated English scoring system developed by Ellis Batten Page in the 1960s. Page updated PEG and ran some successful trials in the early 1990s (Page Reference Page1994; Shermis and Burstein Reference Shermis and Burstein2003). PEG grades essays predominantly on the basis of writing quality. An educational company called Measurement Incorporated acquired the rights to PEG in 2002 and has continued to develop it. Thomas Landauer has developed a system based on LSA using a scoring engine called Intelligent Essay Assessor (IEA). IEA is an implementation of the Knowledge Analysis Technologies (KAT) engine from Pearson Educational Technologies, which was first used to score essays in 1997 (Landauer et al. Reference Landauer, Foltz and Laham1998; Foltz et al. Reference Foltz, Laham and Landauer1999). IntelliMetric is Vantage Learning’s product and was first used commercially to score essays in 1998 (Elliot Reference Elliot, Shermis and Burstein2003). Educational Testing Service offers e-rater, an automated essay scoring program which was first used commercially in 1999 and now is used to score the Test of English as a Foreign Language (TOEFL) and Graduate Record Examination (GRE) (Burstein Reference Burstein, Shermis and Burstein2003). E-rater is a sophisticated hybrid feature technology that uses syntactic variety, discourse structure (like PEG) and content analysis (like LSA) (Attali and Burstein Reference Attali and Burstein2006; Burstein and Chodorow Reference Burstein, Chodorow and Kaplan2010; Ramineni et al. Reference Ramineni, Trapani, Williamson, Davey and Bridgeman2012). Bayesian Essay Test Scoring sYstem (BETSY) is based on Bayes’ theorem and developed by Lawrence Rudner (Rudner and Liang Reference Rudner and Liang2002). Pacific Metrics offers a constructed response automated scoring engine, called CRASE. Currently utilized by several state departments of education and in a U.S. Department of Education-funded Enhanced Assessment Grant, CRASE has been used in large-scale formative and summative assessment since 2007. Numerous researchers have reported that their automated essay scoring systems can, in fact, do better than a human rater. Page made this claim for PEG in 1994 (Page Reference Page1994) and Scott Elliot said in 2003 that IntelliMetric typically outperformed human scorers in speed and consistency (Elliot Reference Elliot, Shermis and Burstein2003).
1.3 Related work
Although many researchers have attached importance to automated English essay scoring and some systems have been applied widely, there has been relatively little research on automated Chinese essay scoring.
For Chinese text processing, segmentation (Teahan et al. Reference Teahan, Wen, McNab and Witten2000; Wang and Liu Reference Wang and Liu2011) is an important first step. Unlike English and other western languages, Chinese does not provide inter-word delimiters, so a sentence may have different meanings with different segmentations. Such an example is shown in Figure 1. Therefore, segmenting reasonably is challenging in automated Chinese essay scoring. In many fields such as search engines and detection and correction for erroneous characters in Chinese texts, several algorithms have been introduced (Pan and Yan Reference Pan and Yan2009; Chang et al. Reference Chang, Chen, Tseng and Zheng2013). For example, Yan Wu uses regulation-based and count-based methods (Wu et al. Reference Wu, Li, Liu and Wang2001); Jinshan Ma has proposed a method based on tri-gram and dependency parsing (Ma et al. Reference Ma, Zhang, Liu and Li2004); Zhipeng Chen uses an n-gram model to correct Chinese spelling in search engines (Chen et al. Reference Chen, Lv, Liu and Tu2009). These methods are viable to some extent, but they are not very effective when considering all the possible segmentations. This problem becomes more obvious when faced with large-scale tests, such as the MHK test.
Different meanings caused by different segmentations.
As for automated Chinese essay scoring, inspired by the studies of English essay scoring, research work has been done for several years (Li Reference Li2006; Chang et al. Reference Chang, Lee and Tam2007, Reference Chang, Lee, Tsai and Tam2009). These methods give automated scores from various perspectives. For instance, Latent Semantic Analysis (LSA) focuses on word usage and the content it reflects (Cao and Chen Reference Cao and Chen2007; Zhao Reference Zhao2011). The word level method concentrates on word usage purely, based on a word list trained by human-scored essays (Ke et al. Reference Ke, Peng, Zhao, Chen and Wang2011). Regularized Latent Semantic Indexing (RLSI) from the field of topic modeling focuses on topic(s) in a dataset (Wang et al. Reference Wang, Xu, Li and Craswell2013; Hao et al. Reference Hao, Xu, Peng, Su and Ke2014). Among them, LSA, designed for indexing documents for information retrieval, is the most common technique that has been successfully applied to a wide range of fields (Wang and Yu Reference Wang and Yu2009; Tonta and Darvish Reference Tonta and Darvish2010; Jin et al. Reference Jin, Gao, Shi, Shang, Wang, Yang, Fyfe, Tino, Charles, Garca-Osorio and Yin2011; McInerney et al. Reference McInerney, Rogers and Jennings2011), such as bioinformatics (Ismail et al. Reference Ismail, Othman and Kasim2011), language processing (Yeh et al. Reference Yeh, Ke, Yang, Lim, Foo, Khoo, Chen, Fox, Urs and Thanos2002; Gorrell Reference Gorrell2006; Liu et al. Reference Liu, Wang and Liu2007; Wang and Wan Reference Wang and Wan2011; Chang et al. Reference Chang, Sung and Lee2013) and signal processing (Mesaros et al. Reference Mesaros, Heittola and Klapuri2011). The underlying idea is to identify which one of several calibration documents is most similar to the new document based on the most specific (i.e., least frequent) index terms. For essays, the average grade on the most similar calibration documents is assigned as the computer generated score (Landauer et al. Reference Landauer, Foltz and Laham1998). LSA reduces the interference of variety and complex characteristics of natural languages (i.e., ambiguities and synonyms), and represents the relations between terms and documents in a lower-dimension and noise-reduced space. Singular Value Decomposition (SVD) is the fundamental mathematical technique of LSA. By this decomposition, terms from the original matrix can be used to construct an approximate matrix or space under which any document can be represented.
When using LSA to perform essay scoring, SVD requires the entire dataset of essays being loaded into memory for computation, which is impossible if the matrix is huge, not to mention the temporarily stored data during the computation. As more and more people take the MHK test year by year, the number of the essays increases rapidly, so time and memory consumption becomes a big problem. Therefore, an automated simplified Chinese essay scoring system dealing with big datasets is highly desirable.
1.4 Main contributions
MHK, known as the Chinese proficiency test for minorities, is the most popular test of simplified Chinese as a foreign language. We construct SCESS, a WFSA-based automated simplified Chinese essay scoring system with Incremental Latent Semantic Analysis (ILSA), to score MHK test essays. In general, an automated essay scoring system for MHK tests follows two steps, as shown in Figure 2. The exception diagnosis includes plagiarism detection, empty essay detection and so forth. Those with such problems are identified as abnormal essays and scored by human raters. The remaining essays are normal, and will be sent to SCESS.
A complete procedure of automated essay scoring.
When scoring normal essays, the flowchart of SCESS is shown in Figure 3. Text pre-processing is the first step, but current Chinese text processing techniques are not suitable for MHK tests as stated above. In order to provide a more effective method that can be used in this step and a more accurate result for subsequent steps, we propose a WFSA-based algorithm to perform dynamic segmenting, detection and correction for erroneous Chinese characters simultaneously by using beam search (Steinbiss et al. Reference Steinbiss, Tran and Ney1994) and heuristic search (Xu et al. Reference Xu, Yue, Su, Deng, Hopcroft and Xue2009). In this algorithm, we use an n-gram language model to construct a WFSA. By replacing possible erroneous characters with the help of a Confusing-Character Table and a Part-Of-Speech Table, we can find the best path which represents the most reasonable segmentation and a correct sentence. When applied in SCESS, WFSA can also be used to obtain an initial assessment from the surface information like character and word usage. In this paper, the performance of error detection and correction is demonstrated, but WFSA is only used to segment sentences for the current version of SCESS.
The flowchart of SCESS.
The second step is to analyse essays using LSA. As to the deficiencies of LSA discussed above, in this paper, we use ILSA in SCESS to solve the problem caused by big datasets. ILSA is introduced by Mattthew Brand (Brand Reference Brand, Heyden, Sparr, Nielsen and Johansen2002) and has been implemented to the fields of image processing (Chin et al. Reference Chin, Schindler and Suter2006) and information retrieval such as recommender systems (Sarwar et al. Reference Sarwar, Karypis, Konstan and Riedl2002; Brand Reference Brand, Barbar and Kamath2003) and natural language processing (Gorrell Reference Gorrell2006). However, there is no related work using ILSA and Incremental Singular Values Decomposition (ISVD) in automated essay scoring. In this paper, we use ISVD as a part of ILSA, to process huge datasets of test essays. Experimental results show that ILSA is very effective. It not only reduces time and memory consumption, but also has a good scoring performance of 89.50%.
The final step is to use several machine learning or pattern recognition strategies to complete automated scoring and a Support Vector Machine (SVM) is used to assist this processing.
1.5 Structure of the paper
The remainder of this paper is organized as follows. We introduce the automated word segmentation and correction based on WFSA as part of text pre-processing of SCESS in the next section. In Section 3, we present the term-document matrix, weighting, ILSA and scoring performance measurement used in SCESS. Section 4 reports the experimental results and gives discussion about detection and correction for erroneous characters and automated essay scoring using ILSA. Finally, in Section 5, we conclude the paper by summarizing our work and giving some remarks on future directions.
2 Automated word segmentation and correction based on WFSA
The first step of automated essay scoring is text pre-processing, including word segmentation. WFSA is a powerful tool to detect and correct erroneous Chinese characters, and segment Chinese sentences into words. The flowchart of word segmentation and correction based on WFSA is shown in Figure 4.
The flowchart of word segmentation and correction.
2.1 N-gram language model
An n-gram language model is an n-tuple of words appearing in a corpus with a conditional probability of the last word, given the previous n-1 words (Rosenfeld Reference Rosenfeld1994). For convenience, in this paper, an n-gram language model is called an n-gram model. In order to achieve a good balance between practical performance and computational complexity, we choose the tri-gram language model, including uni-grams, bi-grams and tri-grams. This model is constructed from a list including 47, 450 words, which turn out to be the uni-gram terms. Then we construct bi-grams and tri-grams and calculate their probabilities from the corpus, trained by SRILM toolkitFootnote 1 (Stolcke Reference Stolcke2002). Because of the different levels of trimming, the number of uni-grams may be slightly different according to different corpora.
Figure 5 shows some examples of n-grams. For every term, the first value is log (P) where P is the probability of a word, and the last value is the backoff coefficient (calculated by modified KN-discount; 0 as default). The middle characters are words (terms). 〈s〉 and 〈/s〉 stand for the start and the end of a sentence respectively, which are added to the sentence before decoding.
Examples of n-grams (The sentence in Chinese in this figure means ‘Hello.’). Note that the term 〈s〉 stands for the start of a sentence. Because it is impossible to start a sentence before 〈s〉, its probability is set to − 99.
2.2 Converting N-gram model to WFSA
A WFSA can be regarded as a directed graph G = (S, Aforward, Abackoff), where S, Aforward and Abackoff denote States, Forward Arcs and Backoff Arcs respectively.
States: We use ε (the epsilon state) as the very start of the proposed WFSA. Each state Si is defined as follows:
where these arcs are out-edges of Si (except arc 0). In practice, because every state represents an n-gram with its lower order (n-1)-gram, we use arc 0 as the backoff arc whose probability is the backoff coefficient from the high order n-gram to its lower order (uni-gram to ε). Additionally, each state can be regarded as a breakpoint for a segmentation and a start point for the remaining segmentation when decoding in a WFSA.
\begin{equation*}
S_{i}=\lbrace arc_{0},arc_{1},arc_{2}\ldots arc_{n}\rbrace
\end{equation*}
Forward Arcs: Each forward arc Ai represents a word connecting two n-grams with a conditional probability of the word. That is:
where Sin records the previous state and Sout indicates the next state. The word corresponds to the word of a term in an n-gram model and the probability is the probability from the n-gram model.
\begin{equation*}
A_{i}=\lbrace S_{in}, S_{out}, word, probability\rbrace
\end{equation*}
Backoff Arcs: Each state has one backoff arc, namely arc 0. By passing through this arc, the system moves from a higher order n-gram state to a lower order (n-1)-gram state. The structure of the backoff arc is similar to the forward arc, except that the word is empty and the probability is the backoff coefficient.
Figure 6 illustrates the WFSA converted from Figure 5. The solid lines are forward arcs and the dashed ones are backoff arcs. The characters on the arcs are words and the probabilities are not shown for the sake of clarity.
The WFSA converted from Figure 5.
2.3 Confusing-character table and Part-Of-Speech table
2.3.1 The confusing-character table
It is well-known that Chinese characters are ideographic, so there are two kinds of mistakes caused by confusing characters. The first one stems from the confusion of characters with similar or same pronunciation, and the second one is caused by similar appearance.
Our method is to construct a Confusing-Character Table, linking the most often confused characters together. Figure 7 shows a fragment of this table. It is hard to translate these Chinese characters in Figure 7 to English. All we need to know is that characters in each line look alike or have similar pronunciations, and are considered as equally likely to be confused with one another. Looking up this table and replacing corresponding confusing characters will complete the automated correction.
A fragment of the confusing-character Table.
We manually did the statistics and constructed the Confusing-Character Table based on Modern Chinese Dictionary and previous MHK test essays, which covers 6, 674 confusing characters.
2.3.2 The Part-Of-Speech table
Many words have different representations caused by different parts of speech. We construct a Part-Of-Speech (POS) Table to deal with these words. During decoding, we check the POS Table as well. If the first several characters have different representations caused by different parts of speech, the arcs whose words are these representations are also passable. Figure 8 illustrates a fragment of the POS Table. The first column shows the words and the second column describes their parts of speech. The materials we used in the POS Table are from Eight Hundred Words in Modern Chinese (Lv Reference Lv1999).
A fragment of the Part-Of-Speech Table.
2.4 Decoding using beam search and heuristic search
Decoding using a WFSA is performed simultaneously with computing of a sentence’s probability, dynamic word segmenting and correction. Passing through different arcs will result in different forms of segmentation and different probabilities of a sentence. The higher the probability is, the more possible it is a correct sentence, and this is the principle for word segmentation and correction.
The word segmentation and correction algorithm.
2.4.1 The word segmentation and correction algorithm
When decoding a sentence, we need to record the current state, the arc just passed, the scored-string, the unscored-string and the probability of the scored-string. Note that the term probability refers to the log probability (the sum of the log probabilities of the arcs). Thus, we associate each sentence with a member denoted as:
\begin{equation*}
member=\lbrace state, arc, \emph {scored-string}, \emph {unscored-string}, probability\rbrace .
\end{equation*}
Moreover, two sets are used during the decoding: the pre-candidate set and the candidate set. The pre-candidate set is a list preserving members that need to be examined in each step, whereas the candidate set preserves the segmentation results. A Beam Container is used to perform beam search, selecting the best n members to add to the pre-candidate set. Therefore, the pre-candidate set is a list that preserves the most promising n members for the next step instead of preserving all the new members to avoid producing numerous useless branches (or members).
The word segmentation and correction algorithm is shown in Algorithm 1. At the beginning of the decoding, we initialize two members M1 and M2 and add them to the candidate set (lines 1–9). If there is an arc starting from the state of the current member (line 15), a new path with a new member will be generated (lines 16–20). The arc and the state of this new member record the arc just passed and the state arrived at respectively, in preparation for subsequent expansions (lines 16–17). The probability on the arc is added to the probability of the member which records the sum of the probabilities of all its past arcs (line 18). Along with scoring, the word in the unscored-string corresponding to the word on the arc will be moved to the scored-string (line 19), and the remaining unscored-string is prepared for subsequent segmenting (line 20). The empty unscored-string means the end of the decoding (line 10), and the probability of a member is that of the whole sentence under the corresponding segmenting.
We adopt the following three conditions to judge whether an arc is passable (line 15):
(1) The backoff arc;
(2) The unscored-string starts exactly with the word on the arc;
(3) After replacing several characters according to the Confusing-Character Table or after checking the POS Table, the second condition is satisfied.
The third condition provides automated correction. Moreover, we subtract a proper value (called the punishment value) per modified character from the score to avoid that a correct character is mistakenly modified to a wrong one. Figures 9 and 10 show examples of these techniques.
An example showing three conditions.
An example showing how to check the POS Table.
In Figure 9, from the current state Sc, arc 0, arc 1, arc 2 and arc 3 are passable, corresponding to condition 1 (arc 0), condition 2 (arc 1, arc 2) and condition 3 (arc 3) respectively. Note that when passing through the backoff arc, the backoff coefficient is added to the probability of the member, though no segmenting happens. Because all the four arcs are passable, four new members will be generated.
In Figure 10, we show how the POS Table works. First, we check the first several characters of the unscored-string (underlined characters in the figure) in the table. Since it has two parts of speech, the sentence can pass both arc 1 and arc 2 whose words match two different representations of the unscored-string. Without the POS Table, only arc 1 is passable.
Whenever a new member is generated, it will be sent to the Beam Container (lines 21, 26). The Beam Container decides which one in the pre-candidate set will be preserved or removed immediately to avoid huge expansion of states. The principles for pruning branches are the probability and the heuristic value of the unscored-string. If the pre-candidate set is larger than the beam width after adding the new member, the one whose sum of the probability and the heuristic value is minimum will be removed. After all the members in the candidate set are examined, a new pre-candidate set is generated and this new set will be the candidate set for the next step (line 29). At the end of the decoding, we will get n paths (according to the beam width), and the path with the highest probability is the best one.
2.4.2 Heuristic search
Heuristic search, which can find applicable paths from a given initial node to a goal node, is widely used in planning and replanning (Yue et al. Reference Yue, Xu, Su, Sattar and Kang2006; Xu and Yue Reference Xu and Yue2009). In the Beam Container, the pre-candidate set is pruned in order to avoid useless expansion. The criterion is to use the members’ probabilities of their scored-strings. To improve the efficiency, we use a heuristic function at the same time. Briefly, a heuristic function is to predict the possible number of erroneous characters in the remaining unsegmented sentence (unscored-string), based on the currently segmented and corrected sentence (scored-string). Therefore, the Beam Container will consider the probability of the scored-string and the heuristic value of the unscored-string of every member, to estimate the probability of the whole sentence and preserve the most promising members for the subsequent expansion.
We propose three heuristic functions for our algorithm. In these functions, the number of the characters in the scored-string is denoted as Nr, and that in the unscored-string is denoted as Nu.
(1) Predict by scored characters and backoff paths: H 1 =
$\frac{probability}{N_r}$ × Nu, where probability means the scored-string’s probability.(2) Predict only by scored-string: H 2 =
$\frac{probability^{\prime}}{N_r}$ × Nu, where probability′ is the sum of probabilities without backoff coefficients.(3) Predict by word segmentation: H 3 =
$\frac{N_u}{T_r}$ × Sa, where Tr is the average number of characters in a word segmentation and Sa is the average probability of a segmentation according to the scored-string and its probability.
We have conducted an experimental study of these three functions and found that H 1 is the best one for SCESS.
2.4.3 WFSA-based segmentation in SCESS
In Algorithm 1, we notice that if condition 3 is removed, WFSA can be used as an algorithm for word segmentation. In SCESS, we use WFSA to segment the essays into words without correction. It is inappropriate to use detection and correction in LSA and ILSA, because there exists the risk that it will erroneously correct essays and thus deviate from the original contents. However, since the detection and correction of errors by WFSA has been proved effective, in the near future, we will combine this function with other perspectives, like the word level method (Ke et al. Reference Ke, Peng, Zhao, Chen and Wang2011), to give a more comprehensive scoring system.
3 Automated essay scoring using incremental latent semantic analysis
Traditionally, LSA can be performed through four sub-steps, which are matrix construction, weighting, calculating SVD and re-projection (Wild et al. Reference Wild, Stahl, Stermsek, Neumann and Penya2005). Calculating SVD, however, becomes a hard or even impossible task when faced with a huge dataset. Therefore, we use ILSA to resolve this problem efficiently. At first, all essays are segmented into words using the method described in Section 2, and then constructed into essay vectors which form the original dataset matrix. Next, a frequency weighting function is used to calculate the dataset matrix. Finally, applying the incremental algorithm on that matrix will establish a semantic space where all essay vectors can be re-projected.
3.1 Producing the t-d matrix
After segmentation, SCESS will produce a t-d (term-document) matrix based on the number of words (terms) appearing in the essays (documents). Typically, SCESS needs a training set and a testing set, and the t-d matrix of the former is denoted as D and that of the latter as Q. In these matrices, each column is an essay vector di or qi.
At first, according to the segmentation results, we generate the matrix 
$\mathbf {D} = [\mathbf {d}_1,\mathbf {d}_2,\ldots, \mathbf {d}_n]\in \mathbb {R}^{m\times n}$ where m is the number of distinct words appearing in the training set, and n is the size of the training set. For each essay vector 
$\mathbf {d}_i=[d_1,d_2,\ldots, d_m]^\top \in \mathbb {R}^m$ (i = 0, 1, . . ., n), if the j-th word (j = 0, 1, . . ., m) appears in other essays but not in this essay, its weight will be 0. Next, we eliminate stop words, such as prepositions and verbal auxiliaries, because they do not have real meanings but appear with high frequencies, and get a set of words 
$\mathcal {V}$.
Then, we use $\mathcal {V}$ and the segmentation results to generate the matrix Q. For the words appearing in an essay from the testing set, if they are included in $\mathcal {V}$, their weights in essay vectors are their numbers of occurrences. For those out of $\mathcal {V}$, we do not add these words into $\mathcal {V}$ and just eliminate them.
Finally we will get two t-d matrices D and Q, sharing the same set of words $\mathcal {V}$.
3.2 Calculating the TF-IDF matrix
The TF-IDF matrix, where TF stands for the term frequency and IDF for the inverse document frequency, is a common method for weighting (Nakov et al. Reference Nakov, Popova and Mateev2001). Every element in the t-d matrix can be weighted as
\begin{equation}
d_{i,j}=TF_{i,j}\times IDF_{i,j}
\end{equation}
The term frequency, TF i, j is defined as
\begin{equation}
TF_{i,j}=\frac{num_{i,j}}{\sum ^{m}_{k=1}num_{k,j}}
\end{equation}
where num i, j is the number of the occurrences of the i-th word in the j-th essay, and m is the number of the words in the training set. As for IDF, it can be calculated as
\begin{equation}
IDF_{i,j}=log\frac{n}{1+DF_{i}}
\end{equation}
where n is the size of the training set (or the number of essay vectors), and DFi is the number of essays which contain the i-th word.
3.3 Incremental latent semantic analysis
ILSA is composed of two parts: incremental decomposition of a dictionary-based space and re-projection of any essay vector under the reconstructed semantic space. The first part can be accomplished by ISVD, avoiding the synonyms and ambiguities of words and enabling essay vectors to be projected onto a low-dimension semantic space. The second part is re-projection, in which any dictionary-based essay vector can be re-projected to the semantic space.
3.3.1 Conventional SVD
SVD is the underlying algorithm of LSA, which constructs a semantic space of a given dataset. Given the r-rank matrix 
$\mathbf {D}\in \mathbb {R}^{m\times n}$ where m is the size of the set of words $\mathcal {V}$ and n is the size of the training set, we apply SVD as follows:
\begin{equation}
\mathbf {D}_{m\times n}=\mathbf {U}_{m\times m}\mathbf {\Sigma}_{m\times n} \mathbf {V}^{\top}_{n\times n}
\end{equation}
where U and V are orthogonal matrices, and Σ is a r-rank diagonal matrix where the elements are in descending order. In general, Σ is not a square matrix (m ≠ n), so it contains extra columns or rows filled with zeros for matrix multiplication.
Specifically, in natural language processing, maintaining only k ≪ r will produce a lower dimensionality and better approximation to the original matrix D. By removing (r - k) columns in U, (r - k) rows in V and (r - k) elements in Σ that are small enough to be considered as trivial, we can multiply the matrices and get an approximation to the original matrix D′m × n:
\begin{equation}
\mathbf {D}_{m\times n}\approx \mathbf {D}^{^{\prime}}_{m\times n}=\mathbf {U}_{m\times k}\mathbf {\Sigma}_{k\times k}\mathbf {V}^{\top}_{k\times n}.
\end{equation}
3.3.2 Incremental SVD
As the dataset grows larger, conventional SVD becomes impractical due to huge memory usage and intolerably long running time. Hence, in SCESS, we use ISVD instead of conventional SVD. ISVD performs as follows. First, given the matrix 
$\mathbf {D}\in \mathbb {R}^{m\times n}$, we partition it into a small matrix 
$\mathbf {M}\in \mathbb {R}^{m\times n^{\prime}}$ and matrices 
$\mathbf {C}_i \in \mathbb {R}^{m\times q}$ (i = 1, 2, . . ., p):
\begin{equation}
\mathbf {D}= {\left[\begin{array}{*10c}\quad \mathbf {M} &\quad \mathbf {C}_1 &\quad \mathbf {C}_2 &\quad \dots &\quad \mathbf {C}_p \end{array}\right]}
\end{equation}
where 
$p=\lceil \frac{n-n^{\prime}}{q}\rceil$ and n′ is called the initial value and q is called the batch size.
Next, conventional SVD is used on M. Because M is small, the computation is fast. Then we update the decomposition result by using M and Ci:
\begin{equation}
[\mathbf{M} \ \mathbf{C}_i]=[\mathbf{U} \ \mathbf{J}]
\begin{bmatrix}
\quad \mathbf{\Sigma} &\quad \mathbf{L} \\
\quad \mathbf{0} &\quad \mathbf{K} \\
\end{bmatrix}
\begin{bmatrix}
\quad \mathbf{V}^{\top} &\quad \mathbf{0} \\
\quad \mathbf{0} &\quad \mathbf{I} \\
\end{bmatrix}^{\top} \\
= \mathbf{tU} \cdot \mathbf{t\Sigma} \cdot \mathbf{tV}
\end{equation}
where L = U⊤Ci and I is an identity matrix. Define H = Ci − UL. Applying QR decomposition to H, we get 
${\bf H}\xrightarrow {\texttt {QR}} {\bf JK}$. Then we decompose tΣ in Equation (7) and it is fast as well:
\begin{equation}
[\mathbf {M} \ \mathbf {C}_i]=[\mathbf {U} \ \mathbf {J}]\mathbf {U}^{\prime}\cdot \mathbf {\Sigma}^{\prime}\cdot {\left[\begin{array}{*10c}\quad \mathbf {V}^{\top} &\quad \mathbf {0} \\
\quad \mathbf {0} &\quad {\bf I} \\
\end{array}\right]}^{\top}\mathbf {V}^{\prime \top}=\mathbf {U}^{\prime \prime}\cdot \mathbf {\Sigma}^{\prime}\cdot \mathbf {V}^{\prime \prime \top}.
\end{equation}
During the process, an important issue is to maintain necessary semantics (dimensions) to construct the semantic space. Producing too much noise will not only lower the precision of the semantic space, but also has an impact on the computational performance, i.e., larger memory usage and longer computational time. Therefore, we maintain k dimensions, called the threshold value, to guarantee the effectiveness of the updating procedure and remove the extra dimensions immediately.
Incremental Singular Value Decomposition.
The algorithm of ISVD is presented in Algorithm 2. In this algorithm, the function 
$\texttt {svds(}\mathbf {M},k\texttt {)}$ is used as conventional SVD where M is the matrix to be decomposed and k is the threshold value. First, it constructs the matrix M by the first n′ essay vectors according to the initial value, to apply conventional SVD. Then, an intermediate result of decomposition (line 6) is produced.
The next step is to update the intermediate result by adding matrices Ci from the rest of D. According to the mathematical derivation we introduced previously, it is easier and faster to update the intermediate result, and this updating result has been proved to be approximate to conventional SVD (Brand Reference Brand, Heyden, Sparr, Nielsen and Johansen2002). This process repeats until all the partitions Ci in the TF-IDF matrix have been updated to the intermediate result (lines 7–11). Finally, we get the final result of ISVD (lines 12–14).
3.3.3 Re-projection
By applying (5), where k is the threshold value for the dimension retained, we construct a semantic space of the dataset. Any term-based essay vector, dj, can be re-projected to the space to obtain a uniform and semantic-based representation.
Suppose that U · Σ · V⊤ is the final result of ISVD performed on the TF-IDF matrix of the training set, and dj is an essay vector based on the same set of words $\mathcal {V}$. Then, we will re-project dj to the semantic space as:
\begin{equation}
\widehat{\mathbf {d}_{j}}=\mathbf {\Sigma}^{-1}\cdot \mathbf {U}^{\top}\cdot \mathbf {d}_{j}
\end{equation}
3.4 Scoring performance measurement
In this final part, we use a Support Vector Machine to automatically score essays (Peng and Wang Reference Peng and Wang2009; Yannakoudakis et al. Reference Yannakoudakis, Briscoe and Medlock2011). Usually, SVM can be described as an optimization problem:
\begin{equation}
$\hspace{1.7cm}\displaystyle\min_{\textbf{w},b,\xi}$ & $\frac{1}{2}\textbf{w}^{\top}\textbf{w}+C\sum^{l}_{i=1}\xi_{i}$ & \vspace{1mm}\\
$\mbox{subject to}$ & $y_{i}(\mathbf{w}^{\top}\phi(\textbf{x}_{i})+b)\geq1-\xi_{i},$ \vspace{1mm}\\
&$\xi_{i}\geq0,i=1,\ldots,l,$\vspace{1mm} \\
\end{equation}
where C is a positive regularization parameter. The input data are pairs of (xi,yi), where xi is the feature vector, and yi is the classification label. In SCESS, xi and yi can be regarded as a re-projected essay vector and the human score of this essay respectively. The kernel function ϕ(xi) maps the input data xi to a higher-dimension space where xi (i = 1, . . ., l) are separable according to yi, so that when new data arrive, they can be classified correctly.
The choice of the kernel function is a nontrivial part of SVM, and it is also an open problem to design an appropriate kernel. In SCESS, the Radial Basis Function (RBF) is used for the kernel, for it allows non-linear relations between the features and the labels:
\begin{equation}
K({\bf x}_{i},{\bf x}_{j})=\phi ({\bf x}_{i})^{\top}\phi ({\bf x}_{j})=\exp \left(-\gamma ||{\bf x}_{i}-{\bf x}_{j}||^{2}\right),\gamma >0.
\end{equation}
Essay vectors from the training set and human scores are used to generate support vectors and establish decision planes. Based on these planes, the essay vectors from the testing set are classified according to support vectors. By this kind of classification, their class labels of essay vectors from the testing set are the automated scores predicted by SVM. Comparing the predicted scores with human scores, we can estimate the performance of automated essay scoring with ILSA.
4 Experimental results and discussion
In this section, we show experimental results of detection and correction for erroneous characters, and the experiments on automated essay scoring using ILSA. SCESS is implemented in C++ and all experiments were run on a machine with a 2 GHz CPU and 96 GB RAM under Linux.
4.1 Introduction to MHK
In MHK tests, test takers are required to write an essay of no more than 350 words based on a given topic, and these essays are restricted to a genre rather than free texts.
According to the scoring criteria of MHK tests, there are four levels for human raters to evaluate an essay (Peng and Wang Reference Peng and Wang2009): Character, Word, Sentence and Paragraph. Character and Word are basic requirements including using correct characters, spelling and meaningful words in simplified Chinese; Sentence is a higher requirement and test takers should use correct grammar in a sentence and think about the relations between the topic and sentences; Paragraph is a consideration about the logical relations among paragraphs and even the whole passage.
A complete system scores essays from those four perspectives, and allocates different weights to them to get comprehensive assessments as overall scores. In consideration of expression and reading comprehension, Character and Word are basic criteria to assess an essay. Moreover, they are relatively easier to be studied compared with Sentence and Paragraph. Therefore, in this paper, we implement SCESS based on Character and Word levels, and we will develop SCESS further by combining all perspectives.
The procedure of human scoring is as follows. First, two human raters give each essay an initial score respectively, from point 1 to point 6 at intervals of 1. If the discrepancy between two scores for a certain essay surpasses 2 points, this essay will be rated by a senior researcher, and the final score will be the average of these three scores; otherwise, the final score will be the average of those two scores. The final score of the essay in MHK tests, ranging from 1 to 6 at intervals of 0.5, will be sent back to the test taker. In our experiments, we use the final score as the annotated score of each essay.
In order to give a first impression about the dataset we use, we give an assignment in the MHK test. All the essays in our dataset are written under the requirement shown in Figure 11. We randomly show two essays in Figure 12, whose scores are 5 and 1 respectively.
The assignment of the essays in our dataset. In this assignment, test takers are required to read a fable talking about the perfect leaf three monks are searching for, and write an essay, rephrasing this fable and expressing their thoughts according to their experiences. An effective response must contain a minimum of 350 words.
Two representative essays of the MHK test (without translation).
The given assignment varies from year to year, leading to the changes of contents of the essays, and thus, the changes of the set of words $\mathcal {V}$. Because LSA and ILSA are both content-oriented methods, for each MHK test, we need to train a different model. In 2009, 190, 000 students in Xinjiang Province in China took the test, and this number has been continuously increasing. Large scale model training requires a system like SCESS which can process big datasets.
4.2 Experiments on detection and correction for erroneous characters
4.2.1 Introduction to datasets
We use two datasets in this part. The first one is a large corpus for training the n-gram model, whereas the second one is to test the word segmentation and correction algorithm based on WFSA.
The selection of the corpus of the training set is important to experimental results because it influences the probability of every term in the N-gram model. We have tested three kinds of corpora: The People’s Daily, diverse sources (Hodgepodge) and the Literature Corpus in Chinese.
The People’s Daily is the most formal and influential newspaper in China, reporting official news and national affairs. By training on this corpus, we get an n-gram model, consisting of 47, 493 uni-grams, 3, 716, 267 bi-grams and 954, 446 tri-grams in total.
The diverse source is a hodgepodge, containing various writings such as micro-blog posts, blog posts, publications, news articles, lyrics, subtitles and so forth. This corpus produces 47, 494 uni-grams, 3, 246, 941 bi-grams and 908, 188 tri-grams.
The Literature Corpus includes writings in Chinese literature, such as the Mao Dun Literature Awards, which is the highest award for Chinese writers. By training on this corpus, we get 47, 489 uni-grams, 6, 557, 265 bi-grams and 7, 173, 881 tri-grams.
The testing set used for WFSA comes from the MHK test. We manually collected sentences from 200 test essays, and counted four kinds of character-wise writing errors. They are substitution, deletion, insertion and transposition errors and their proportions are shown in Table 1. From Table 1, we see that the substitution error is the most common and serious one. Therefore, in SCESS, we focus on detection and correction of substitution.
The proportions of four kinds of errors. We have selected 411 sentences from 200 essays. There are 607 character-wise errors in total. These errors are easy for native speakers to correct, so we manually annotated the erroneous characters and corrected them.
4.2.2 Performance criteria
There are three performance criteria for estimating the results of detection and correction for erroneous characters, which are Recall Rate, Detection Precision and Correction Precision (Leacock et al. Reference Leacock, Chodorow, Gamon and Tetreault2010):
\begin{equation}
Recall\ Rate=\dfrac{N(W\rightarrow R)+N(W\rightarrow S)}{N(W)}
\end{equation}
\begin{equation}
Detection\ Precision=\dfrac{N(W\rightarrow R)+N(W\rightarrow S)}{N(W\rightarrow R)+N(W\rightarrow S)+N(R\rightarrow W)}
\end{equation}
\begin{equation}
Correction\ Precision=\dfrac{N(W\rightarrow R)}{N(W\rightarrow R)+N(W\rightarrow S)+N(R\rightarrow W)}
\end{equation}
Additionally, we introduce F − measure as an indicator, which is a common index in natural language processing. Adapted to WFSA, we get the equation:
\begin{equation}
F-measure=\dfrac{2\cdot Detection\ Precision \cdot Recall\ Rate}{Detection\ Precision + Recall\ Rate}.
\end{equation}
Equation (14) is used to compare WFSA with other methods.
4.2.3 Experimental settings
The first step is to choose an appropriate corpus. Table 2 shows the comparison of three kinds of corpora, namely, People’s Daily, Hodgepodge and Literature. People’s Daily does not perform well, because its official form of usage is distant from daily use and test essays. Hodgepodge uses informal Chinese, so it is not satisfactory, either. Literature is proved to be the best one because it uses not only standard but also daily Chinese which is closest to the style of test essays, so we choose it for subsequent experiments.
Comparison of three corpora. The testing set comes from the MHK test (200 essays). We set all the parameters empirically (the beam width = 10, the punishment value = 0.5, the heuristic function = H1).
After the corpus has been determined, we need to tune the key parameters to achieve best results. There are three parameters in our approach: the heuristic value, the punishment value and the beam width. As described in Section 2.4.2 (Heuristic Search), we have tested three heuristic functions and found H 1 (= 
$\frac{probability}{N_r}$ × Nu) is the best one. We have also set different punishment values from 0.1 to 3.5 per modified character at intervals of 0.1 and found that 1.3 is the best choice. The beam width is used to limit the size of the pre-candidate set in the Beam Container. We have tested different beam widths from 5 to 30 at intervals of 5 and decided to choose 25 to balance the performance and the efficiency.
4.2.4 Experimental results and analysis
Our experimental results are shown in Table 3. The Recall Rate of 88.50%, the Detection Precision of 92.31% and the Correction Precision of 88.46% indicate that our method is quite effective.
Comparisons of WFSA, Google and Baidu. The testing set comes from the MHK test (200 essays).
In order to further demonstrate that WFSA is effective in detecting and correcting erroneous characters, we compare WFSA with current Chinese text correction systems. They are used by www.google.com and www.baidu.com, both of which are popular search engines in China and provide detection and correction prompts for erroneous characters.
From Table 3, we see that the Recall Rate of WFSA performs much better than Google and Baidu, though the Detection Precision and the Correction Precision are slightly lower. F-measure demonstrates that WFSA is much more effective.
4.3 Experiments on ILSA
In the experiments on automated essay scoring using ILSA, MATLAB is used to multiply matrices and do re-projection. For the training set, their corresponding human scores (from 0 to 6 at intervals of 0.5) will be paired with the essay vectors in order to train the scoring model based on SVM. LIBSVMFootnote 2 (Chang and Lin Reference Chang and Lin2011) is used to help to complete the training and scoring.
4.3.1 Introduction to datasets
In order to test ILSA, we use 157, 760 essays and 1, 000 essays with the same assignment from the MHK test as the training set and the testing set respectively. The human scoring distribution is shown in Figure 13.
Human scoring distribution of the training set (left) and the testing set (right).
4.3.2 Optimal batch size
The batch size of essays is very important to ILSA, so we have conducted a series of experiments to find the optimal batch size. The results of ILSA as the batch size increases are shown in Table 4. In these experiments, we set both the threshold value and the initial value to 100. Then we set the batch size from 10 to 1,000, at intervals of 10 and 100. When the batch size is 0, there is no difference between conventional LSA and ILSA, because it means that we decompose the matrix in only one iteration procedure. That is to say, if batch size is 0, when we are performing conventional SVD on the initial matrix M in line 6 in Algorithm 2, we are in fact decomposing the original matrix D, and the Algorithm 2 finishes here. Apparently, in this case, no incremental decomposition happens. As the batch size increases, from Table 4, we can see that the time of ILSA decreases sharply at first, and continues increasing gradually.
Results of ILSA with different batch sizes. In order to smooth out biases that may occur in the processing, we run these experiments 10 times on the same dataset and compute average values.
When we concentrate on the results from 260 to 400 as shown in Table 5, we can see the optimal batch size is 320. Therefore, in the subsequent experiments, the batch size is set to 320.
Optimal batch size.
4.3.3 Relative update time
The relative update time is used to observe the performance of ILSA based on the size of the dataset and the optimal batch size:
\begin{equation}
\mbox{ \emph {relative update time}} = \frac{(n-n^{\prime})}{optimal\ batch\ zize}\times \frac{base}{n}
\end{equation}
where n is the number of essay vectors (the size of the original dataset matrix), and n′ is the initial value. Base means the size of the dataset as a unit. For example, in our experiment, base is 100, 000 because the size of the training set is 157, 760. Thus, the relative update time reflects the ability of ILSA when faced with different sizes of datasets.
To make it clear, we have conducted a series of experiments. In these experiments, we increase n from 10, 000 to 80, 000 at intervals of 10, 000 with n′ = 100. Fixing n and n′, by using various batch sizes on the decomposition and observing the running time, we choose optimal batch sizes for different sizes of datasets in Table 6. From Table 6, we can see that as the size of the dataset grows, the optimal batch size grows as well.
Optimal batch sizes for different sizes of datasets. In order to smooth out biases that may occur in the processing, we run these experiments 10 times on the same dataset and compute average values.
For showing that the performance of ILSA does not become worse, we compute the relative update time and plot it in Figure 14. From Figure 14, we can see that as n grows, the relative update time decrease, meaning that ILSA performs more efficiently as the dataset grows larger. For instance, when n = 20, 000, ILSA updates decomposition in 32 iteration procedures; when n = 80, 000, ILSA finishes updating in only about 20 iteration procedures.
Relative update time.
4.3.4 Comparison of ILSA and conventional LSA
The comparison of ILSA and conventional LSA for running time is illustrated in Figure 15. In the experiments, we increase the size of the training set from 31, 552 to 157, 760. Figure 15 shows that when the size grows larger, ILSA performs far more efficiently than conventional LSA. Specifically, when the size grows to 110, 432, the time of conventional LSA is more than two hours (7, 200s), as is shown in Figure 15, so it is obvious that ILSA is much better.
Comparison of ILSA and conventional LSA for running time.
In addition to running time, memory usage is another huge advantage of ILSA. Figure 16 shows the comparison of ILSA and conventional LSA for memory usage as the size of the training set grows. From Figure 16, we can see that the maximum memory usage of ILSA is only 492 MB, and moreover, it performs relatively stably. In sharp contrast, conventional LSA uses much more memory and increases distinctly. In practical application, language tests usually produce a big dataset, so, even given huge memory, it is impossible for conventional LSA to finish the decomposition task, but it is viable for ILSA to perform it.
Comparison of ILSA and conventional LSA for memory usage.
4.3.5 Scoring performance
From the experimental results, we see that ILSA has great advantages both in time and memory usage. More encouragingly, ILSA does not weaken the scoring performance, compared with conventional LSA. To evaluate ILSA, we use several criteria: Scoring Accuracy, Quadratic Weighted Kappa and Spearman’s Coefficient.
Scoring Accuracy: The Scoring Accuracy is calculated as follows:
(16)where n is the size of the testing set, and hsi and psi are the human score and predicted score of the i-th essay respectively. The function t(hsi, psi) is binary, defined as:
\begin{equation}
\mbox{\emph {Scoring Accuracy}} = \frac{\sum ^{n}_{i=1}t(hs_{i}, ps_{i})}{n}
\end{equation}
(17)If the difference between a human score and a predicted score is no more than 1 point, it is acceptable.
\begin{equation}
t(hs_i,ps_i) = \left\lbrace \begin{array}{@{}l@{\quad}l@{}}1& |hs_i-ps_i| \le 1 \\
0&\text{otherwise} \end{array}\right.
\end{equation}
Quadratic Weighted Kappa: For Quadratic Weighted Kappa, we construct two confusion matrices. The first one shows the human scores and the predicted scores given by conventional LSA, and the second one shows the human scores and the predicted scores given by ILSA. Quadratic Weighted Kappa takes chance agreement into account.
Spearman’s Correlation: We calculate the Spearman’s Correlation ρ:
(18)where X and Y stand for the ranks of human scores and the predicted scores respectively, and
\begin{equation}
\rho _{X,Y}=\frac{\sum _{i=1}^n(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum _{i=1}^n(x_i-\bar{x})^2(y_i-\bar{y})^2}}
\end{equation}
$\bar{x}$ and $\bar{y}$ for their average values respectively, and n is the size of the dataset.
In order to give an overall impression of SCESS, we show the results in Table 7. In this table, not only are the performances of LSA and ILSA compared, a further comparison of a baseline classifier (Baseline) and two human raters’ performance (Human) is also shown.
Scoring performance of ILSA, conventional LSA, Baseline and Human. The size of the testing set is 1, 000.
The baseline classifier counts the most frequent score in the training set, and thus, gives the predicted scores of the essays in the testing set. In our training set, since the most frequent score is 4, this baseline classifier will give point 4 to all the essays in the testing set. The extreme low values of the Quadratic Weighted Kappa and Spearman’s Correlation verify this unreasonable method.
From Table 7, we see that ILSA has the best Scoring Accuracy. The Spearman’s Correlations of ILSA and LSA are the same and it is better than that of Human. Although the Quadratic Weighted Kappa of ILSA is slightly lower than LSA, ILSA is still effective, because the difference is very small.
Focusing on ILSA and LSA, we use Table 8 to show the scoring deviations. Each cell is the number of the unacceptable scores whose differences with human scores lie in the corresponding deviation interval.
Scoring deviations of ILSA and conventional LSA.
5 Conclusions and future work
In this paper, we describe the development of an automated simplified Chinese essay scoring system based on WFSA and ILSA, called SCESS. Combined with the Confusing-Character Table, the Part-Of-Speech Table, beam search and heuristic search, WFSA can effectively segment Chinese sentences into words. In addition, it can detect and correct erroneous simplified Chinese characters. A Recall Rate of 88.50%, a Detection Precision of 92.31% and a Correction Precision of 88.46% show that WFSA is very effective. After segmentation, SCESS uses ILSA to process segmented essays and extract semantic features. Finally, we use SVM to score essays automatically. From the experimental results, we see that ILSA is quite efficient, because it significantly reduces both running time and memory usage. Additionally, it can successfully score essays with the Scoring Accuracy of 89.50%. Overall, SCESS proves to be promising.
In the future, we will test SCESS on more assignments so that the generalizability can be verified. For further improvement of SCESS, we will continue to develop it on Character and Word levels. For example, we will consider essay contexts to identify the gender of a person and utilize names of entities. For a complete and mature SCESS, WFSA-based detection and correction for erroneous characters will be integrated. Moreover, we will study more methods to assess essays automatically on Sentence and Paragraph levels. Many novel methods will be tested, including Contextualized Latent Semantic Indexing (CLSI), probabilistic LSA (pLSA), Latent Dirichlet Allocation (LDA), hierarchical LDA (hLDA) and so forth.
Acknowledgements
We would like to thank the anonymous referees for their helpful comments and suggestions on the earlier versions of this paper and Bin Huang, Mingqing Zhang and Zongtian Gao for their help in the experiments. This work is supported by the Beijing Higher Education Young Elite Teacher Project (YETP0768), the Fundamental Research Funds for the Central Universities (YX2014-18) and the National Natural Science Foundation of China (61103152 and 61472369).
