Classifiers that guess an author's native language from their English essays work very well when they are tested on essays like those they were trained on. They fail badly on essays from a different collection, because they learn the topics and place names of the training essays rather than how the writers build sentences. One way to remove topic is to replace every word with its grammatical category, its part of speech (POS), so that "the old man left" becomes DET ADJ NOUN VERB. Existing systems then count short exact runs of these tags. Exact counting is brittle: one inserted adverb turns a familiar sentence shape into features the model has never seen. We propose to describe each document by how closely its sentences, written as tag strings, resemble a few hundred "prototype" sentence shapes. Closeness is measured with length-normalized edit distance, the number of insertions, deletions, substitutions and swaps needed to turn one tag string into another, divided by length. These similarities are fed to an ordinary linear support vector machine (SVM), a classifier that finds the widest-margin separating hyperplane.
The intended result is a classifier that keeps the speed and convexity of linear SVMs and is blind to vocabulary by construction. It should also tolerate small structural variations and upstream tagging errors that exact POS n-gram features cannot. The test bed is cross-corpus native language identification, where the gap is largest and best documented. A model trained on EFCamDat and evaluated on TOEFL11 falls from 64.95% to 33.45% accuracy (Large-Scale Native Language Identification with Cross-Corpus Evaluation).
Core Claim
Whole-sentence syntactic shape, compared elastically and normalized for length, carries native-language signal that survives a change of corpus. That signal is not captured by exact POS n-grams. It is not captured by POS n-grams with gaps either, and it is not captured by character n-grams. Turning this comparison into explicit prototype-similarity features keeps the classifier linear. It also avoids the quadratic document-pair kernel matrix and sidesteps the fact that normalized edit distances do not always form a valid kernel.
Concretely, let $s$ be a sentence's tag string and $p_k$ the $k$-th prototype tag string. Let $\mathrm{DL}$ be Damerau-Levenshtein distance, which is edit distance with adjacent swaps allowed. Let $|\cdot|$ be string length. Let $\lambda$ be a small length floor that prevents very short sentences from looking identical to everything. The normalized distance is
$$d(s,p_k)=\frac{\mathrm{DL}(s,p_k)}{\max(|s|,|p_k|,\lambda)}.$$
A document $D$, with $|D|$ sentences, is described by the average soft similarity of its sentences to each prototype, with $\tau$ a temperature:
$$\phi_k(D)=\frac{1}{|D|}\sum_{s\in D}\exp\!\left(-d(s,p_k)/\tau\right).$$
Relation to Prior Work
The pieces exist in separate places, and the file shows no work that combines them.
The closest work for the distance itself is Improving English-Russian sentence alignment through POS tagging and Damerau-Levenshtein distance. It computes Damerau-Levenshtein distance between POS "watermarks" built from four content tags. It divides by target length and passes the single resulting number to logistic regression to flag misaligned sentence pairs. That paper motivates our work, because it shows tag-string edit distance carries structural signal. We differ in three ways. We use the full tagset including function-word tags. We use a symmetric normalization. We classify documents with a high-dimensional feature vector, not sentence pairs with one number.
The symmetric max-length normalization comes from Detecting English-French Cognates Using Orthographic Edit Distance. That paper found max-length and geometric-mean normalization more stable than asymmetric normalization for word-pair similarity. We reuse its normalization and test it against target-length and raw variants. Separately, The Influence of Minimum Edit Distance on Reference Resolution showed that normalized edit distance recovers matches that exact matching misses. Adding it raised definite-noun-phrase F-measure from 15.84% to 33.94% in coreference resolution. This supports elastic matching, but in a lexical rather than syntactic setting.
On the classification side, three papers run linear SVMs over exact-count POS n-grams for native language identification. Finnish Native Language Identification reports 55.2% for POS bigrams and 69.5% combined. Large-Scale Native Language Identification with Cross-Corpus Evaluation found POS trigrams among the few features that transfer across corpora. The Power of Character N-grams in Native Language Identification found that POS tags added nothing on top of character 1–9-grams in a within-corpus test. All three count exact matches. Our proposal keeps their classifier and changes only the representation. The third paper constrains us: we must show value cross-corpus, and we should not expect gains within a corpus.
For sequence kernels, Dynamic Time-Alignment Kernel in Support Vector Machine builds alignment directly into an SVM kernel for variable-length speech. It normalizes by alignment path length, which costs $O(l^2)$ per pair and requires the full pairwise matrix. We avoid both costs by comparing sentences only to a fixed set of prototypes. This is an explicit "empirical kernel map" in which every feature is a real number, so validity of the kernel is not required. Convolutional Embedding for Edit Distance learns 128-dimensional embeddings that approximate edit distance on character strings. We use it only as an optional speed-up for large corpora such as EFCamDat, never as the core method. The neural alternative is PMAES: Prompt-mapping Contrastive Learning for Cross-prompt Automated Essay Scoring. It feeds POS sequences to a contrastively trained CNN-LSTM to get topic-invariant essay representations. It shares our goal of using tags to remove topic, but it gives up the convex, small-data behaviour that our setting relies on.
Research Program
We will tag every sentence with a universal tagset and a finer tagset that includes punctuation and function-word classes. Prototypes come only from the source corpus. We draw them in two ways. The first is k-medoids clustering of sentence tag strings under $d$. The second is class-balanced medoids, drawn per native language, so that rare-language shapes are represented. The prototype count $K$ ranges from 100 to 2000.
Cost is sentences × $K$ × roughly $20^2$ dynamic-programming cells. This is linear in corpus size and easily parallel. For EFCamDat, with more than 550,000 texts, we will also train the convolutional edit embedding on tag strings and compare its features with exact distances.
The resulting feature vector goes to a linear SVM alone, and also concatenated with standard feature blocks. We will analyse which prototypes receive large SVM weights for each native language. This checks whether the model is picking up plausible transfer patterns, such as article omission or word-order shapes, rather than artefacts. We will also measure robustness to tagger error by randomly corrupting a controlled fraction of tags. The motivation is that tagger accuracy near 85% is realistic on non-standard text (Low Saxon dialect distances at the orthographic and syntactic level).
Baselines
The naive reference points are the majority class and chance. The file reports 11.11% random accuracy for the EFCamDat-to-TOEFL11 transfer and 19.6% majority accuracy on the Finnish corpus.
The first strong competitor is a linear SVM on character 1–9-grams, reimplemented after The Power of Character N-grams in Native Language Identification. It reached a test F1 of 0.8756 on the 2017 shared task, first place. It is the strongest known within-corpus system and the system most likely to absorb any syntactic signal through function words. On within-corpus data it is the reference to match. On cross-corpus data it is expected to lose, and we will measure how much.
The strongest existing cross-corpus result in the file is the ensemble of Large-Scale Native Language Identification with Cross-Corpus Evaluation. It reports 33.45% accuracy trained on EFCamDat and tested on TOEFL11, against 64.95% within EFCamDat. We will rebuild its POS-trigram, function-word and grammar-rule SVM on the same nine-language overlap and the same splits. Our reimplemented number, not only the published one, will be the comparison point.
The most important baseline is a linear SVM on exact POS 1–3-gram TF-IDF features over the same tagset. It isolates whether elastic matching adds anything beyond vocabulary removal. Beating it, and the gapped POS n-gram ablation below, is the central result.
For distributional embeddings, the file reports only relative macro-F1 gains of 4.39% to 19.27% over n-gram baselines (Cross-corpus Native Language Identification via Statistical Embedding). It gives no absolute number on our pairs, so we will run that method ourselves.
The ablations each isolate one ingredient. Prototype features with raw unnormalized distance test length normalization. A four-tag Kutuzov-style watermark tests whether function-word tags matter. Exact-match prototypes, where similarity is 1 only when distance is 0, test elasticity. Randomly sampled prototypes against medoids test prototype selection.
All systems get the same tagger, the same training documents, and the same budget of 50 hyperparameter configurations. Tuning is done on a held-out slice of the source corpus only, never on the target corpus.
We will count the proposal as successful if two things hold. First, prototype features alone, or concatenated with POS n-grams, beat the exact POS n-gram SVM on cross-corpus macro-F1, with paired bootstrap confidence intervals excluding zero, on at least two of the three corpus pairs. Second, adding them to character n-grams improves cross-corpus accuracy while costing no more than one point within corpus.
Why not just…?
Why not just use character n-grams in a linear SVM? They are the within-corpus winner (The Power of Character N-grams in Native Language Identification), and we do not expect to beat them there. But character features carry the topic and place-name information that Large-Scale Native Language Identification with Cross-Corpus Evaluation blames for the collapse to 33.45%. Our cross-corpus experiments and the topic-leakage test below measure this directly rather than assuming it.
Why not just use POS n-grams, perhaps with gaps? This is the real threat. POS trigrams already transfer well, and gapped n-grams would tolerate a single inserted adverb at linear cost. We take it seriously by including gapped POS 2–4-grams as a matched baseline. Our claim is that sentence-level shape, compared with length normalization, adds information beyond local windows, gapped or not. If gapped n-grams match our cross-corpus scores, the honest conclusion is that local elasticity is enough. The proposal would then reduce to a negative result about whole-sentence alignment, which we would report.
Why not just use distributional statistical embeddings? The method of Cross-corpus Native Language Identification via Statistical Embedding improves cross-corpus macro-F1 without a tagger. It is built from lexical term-weight statistics, however, and ignores word order entirely. We will run it on our splits and also concatenate it with prototype features. If the two are complementary, the concatenation should beat either alone.
Why not just train a neural encoder on POS sequences? PMAES: Prompt-mapping Contrastive Learning for Cross-prompt Automated Essay Scoring shows that this can work for essay scoring. Neural models lost to linear SVMs on native language identification (The Power of Character N-grams in Native Language Identification), and the 204-document Finnish corpus is far too small for one. We will include a POS-input CNN-LSTM under the same tuning budget as a reference. The small-data comparison is where we expect the clearest difference.
Proposed Experiments
The main experiment trains on one corpus and tests on another. The pairs are EFCamDat to TOEFL11, TOEFL11 to EFCamDat, and Lang-8 to ICLE and FCE, following Robust, Lexicalized Native Language Identification. The file reports no Lang-8-to-ICLE number, so all numbers on that pair will be our own reimplementations. We restrict each pair to the native languages it shares and report accuracy and macro-F1. Within-corpus control results come from the 2017 shared-task split, reference F1 0.8756, and from the Finnish learner corpus, reference 69.5% combined accuracy. The Finnish corpus tests whether the method helps when data are scarce and morphology is rich.
Two decisive checks go beyond accuracy. The first measures topic leakage. We train a probe to predict essay prompt from each feature block. Prompt predictability from our features should sit near the level achieved by exact POS n-grams and far below character n-grams; if it does not, the vocabulary-blindness argument fails. The second is the tag-corruption curve. As random tag errors rise from 0% to 20%, prototype features should lose accuracy more slowly than exact POS n-grams. This prediction follows from the fact that one wrong tag changes up to $n$ exact n-grams but shifts a normalized edit distance by at most $1/|s|$.
Finally, a sweep over normalization, comparing raw, target-length, maximum-length and geometric-mean divisors, and over the length floor $\lambda$, will show whether the short-sentence problem noted by Kutuzov actually affects document-level classification.
References
- Large-Scale Native Language Identification with Cross-Corpus Evaluation
- Improving English-Russian sentence alignment through POS tagging and Damerau-Levenshtein distance
- Detecting English-French Cognates Using Orthographic Edit Distance
- The Influence of Minimum Edit Distance on Reference Resolution
- Finnish Native Language Identification
- The Power of Character N-grams in Native Language Identification
- Dynamic Time-Alignment Kernel in Support Vector Machine
- Convolutional Embedding for Edit Distance
- PMAES: Prompt-mapping Contrastive Learning for Cross-prompt Automated Essay Scoring
- Low Saxon dialect distances at the orthographic and syntactic level
- Cross-corpus Native Language Identification via Statistical Embedding
- Robust, Lexicalized Native Language Identification