Chinese and Japanese are written without spaces, so a program must decide where words begin and end. Often the answer depends on characters well before or after the ambiguous spot. Classical models that track that context explicitly, such as Markov models conditioned on the previous $m$ characters, need tables that grow exponentially with $m$. This is the "state space explosion." Neural segmenters avoid the tables by compressing history into a learned vector, but they need days of gradient training and plenty of labeled data. This note asks whether a third option works: a large recurrent network with random, never-trained weights, called a reservoir. Only a linear readout on top of it is fitted, and it is fitted in closed form by ridge regression.
The concrete proposal has three parts. Characters drive a bidirectional reservoir. Closed-form readouts score both character boundaries and whole candidate words from the reservoir states. An exact variable-length decoder then picks the best segmentation. Its cost is linear in sentence length and maximum word length, and it does not depend on how far back the context reaches. The scientific question is sharper than "does it work." We want to know whether fixed random dynamics carry boundary information that the same readout cannot get from an equally large bag of explicit character n-gram features. If they do not, the reservoir is just an expensive hash, and the experiments are designed to reveal that.
Core Claim
Our claim is that a reservoir can stand in for an unbounded-order Markov history in segmentation. Its state is a fixed-size summary of all past characters that fades with distance. A linear function of that summary can then play the role that a $|S|^{m+1}$ transition table plays in a high-order model, without ever building the table. Because the readout is linear and the dynamics are fixed, three things follow. Training reduces to one regularized least-squares solve. Word-level span scores can be computed from state differences in constant time per span. Exact decoding over variable-length words stays at first-order cost.
We expect the advantage over trained networks to appear mainly when labeled data is scarce. We expect the advantage over explicit n-gram features to appear mainly on overlapping ambiguities whose resolving context lies beyond a short window. We do not expect to match fully trained segmenters at full data, and the proposal is not premised on doing so.
Where This Sits
Three strands of prior work set up the gap.
The first strand treats high-order context in segmentation as a combinatorial problem to be tamed. The Power of Amnesia prunes a potential 30th-order character model on English down to fewer than 3,000 suffix-tree states. Practical Very Large Scale CRFs uses L1 penalties to zero out all but 0.02% of 250 million candidate features. Efficient Staggered Decoding for Sequence Labeling collapses inactive labels into bounding nodes and gets a 270x exact speedup, but its authors confine it to first-order chains and leave semi-Markov models open. Online Markov Decoding proves that exact online decoding still costs exponentially in the Markov order. These papers motivate the proposal: they show that explicit history is expensive. They also constrain it. The suffix-tree result shows that discrete pruning is a strong, cheap competitor that we must beat, not dismiss.
The second strand solves segmentation with trained dense history. Neural Word Segmentation Learning for Chinese scores whole candidate words with a gated character composer and an LSTM over the word history, and it takes 2 to 4 days to train. Fast and Accurate Neural Word Segmentation for Chinese makes this greedy and cuts training to 3 to 6 hours. Applying Conditional Random Fields to Japanese Morphological Analysis and ZEN depend on external lexicons. Interpreting Word-Level Hidden State Behaviour of Character-Level LSTM Language Models shows that trained character LSTMs concentrate word information at boundaries. That leaves open whether training is what puts it there. We borrow our method from this strand: we reuse word-level span scoring from Cai and Zhao, but replace the trained LSTM with fixed dynamics.
The third strand supplies the reservoir machinery. Echo state networks keep a fading memory by holding the recurrent spectral radius below one (Gallicchio et al.). Readouts are fitted in closed form (Jaeger), and cached states make hyperparameter search cheap (Lukosevicius et al.). Bidirectional deep echo state networks run fixed reservoirs forward and backward to repair short memory, and they train up to 70x faster than a gated recurrent network. Robot Language Acquisition Modelling via Cross-Situational Learning with Little Data finds that an echo state network stays below about 10% error with 1,000 examples where small LSTMs fail. That task used pre-segmented words mapped to scenes, so it motivates our low-data hypothesis without testing it. Learning Beyond Experience shows that reservoirs generalize to unseen regions of continuous state spaces, but it never touches discrete symbol streams.
No paper in the file combines these ingredients. What is new is the combination: fixed reservoir states as span features, closed-form word scoring, and exact semi-Markov decoding. The same applies to the controlled test of whether recurrence beats explicit n-grams at equal feature budget.
Research Program
Each character $c_t$ is mapped to an input vector $e(c_t)$. In the main setting this is a fixed random vector per character, so that nothing is learned upstream. A secondary setting uses frozen pretrained character embeddings and reports the gain separately. A forward reservoir and a backward reservoir are each updated with a leaky rule:
$$x_t = (1-\alpha)\,x_{t-1} + \alpha \tanh\!\big(W x_{t-1} + U e(c_t)\big).$$
Here $x_t \in \mathbb{R}^D$ is the state, $W$ is a sparse random matrix rescaled to spectral radius $\rho < 1$, $U$ is a random input matrix, and $\alpha$ is the leak rate that sets the memory timescale. We will also stack two layers, following the deep reservoir design of Micheli et al., so that different layers hold different timescales.
We fit two readouts by ridge regression, both in one pass over the training data. The boundary readout predicts whether a word ends after position $t$ from the concatenated forward state at $t$ and backward state at $t+1$.
The span readout scores a candidate word covering positions $i$ through $j$, with $j - i < K$. Its input is a feature vector $\phi(i,j)$ built from the forward states at the span edges, their difference, the backward states at the span edges, and a one-hot length code. It is trained to output 1 for gold words and 0 for sampled non-word spans.
A sentence segmentation $y$ is scored as
$$S(y) = \sum_{(i,j)\in y} \Big[\, w^\top \phi(i,j) + \lambda \log p_{\text{len}}(j-i+1) \,\Big].$$
In this sum, $w$ is the span readout, $p_{\text{len}}$ is the word-length distribution counted from training data, and $\lambda$ is one weight tuned on development data.
A semi-Markov Viterbi pass finds the exact maximum of $S(y)$ in $O(TK)$ span evaluations for a sentence of $T$ characters. This is the point of contact with state-space explosion. All long-range context is absorbed into the states, so the decoder never enumerates character histories, and its cost does not depend on any Markov order.
Training cost is one accumulation of a $D \times D$ Gram matrix followed by one solve. For $D$ in the low thousands this takes minutes on a CPU. Because states are cached, sweeping $\rho$, $\alpha$ and the ridge penalty only re-solves the readout.
The analysis half of the program asks where boundary information lives. We will fit linear probes for boundary identity on reservoir states at each spectral radius. We will then relate probe accuracy to the linear memory capacity of the reservoir, meaning how many steps back a linear readout can reconstruct past inputs. The prediction is that errors on an ambiguity concentrate where the resolving character lies beyond that capacity. If that prediction holds, the fading-memory limitation named in the reservoir literature becomes a measurable property of segmentation errors.
Baselines
The naive reference point is forward maximum matching against the training-set word list. It is standard, parameter-free, and shows how much of each benchmark is solved by lexicon lookup alone. We will run it on identical splits.
The strongest existing methods are the trained neural segmenters. Fast and Accurate Neural Word Segmentation for Chinese reports F1 of 95.8% on PKU and 97.1% on MSR. Neural Word Segmentation Learning for Chinese reports 95.2% and 96.4% without handcrafted features. Transfer Deep Learning for Low-Resource Chinese Word Segmentation reports 96.1% on PKU and 96.2% on CTB. For out-of-vocabulary recall, Synthetic Word Parsing Improves Chinese Word Segmentation reports 0.822 on PKU and 0.717 on MSR.
At full data we quote these numbers rather than re-run them. We will also re-train a character BiLSTM tagger of our own on each data fraction, with the same random-free input embeddings and a tuning budget of equal wall-clock hours on one GPU. This is the fair low-data comparison, because none of the cited papers reports results on subsampled training sets. There is no reported result found on Lacuna for PKU or MSR segmentation at 1% to 10% of the training data.
Beating the trained baseline means higher F1 than our re-trained BiLSTM at the 1% and 5% fractions. At full data, the claim is only that we come within a stated gap of the quoted numbers at a small fraction of training time. We will report that gap honestly whatever it turns out to be.
The ablation that isolates the key ingredient is the equal-budget n-gram readout. Every character n-gram of order 1 to 5 inside a window around the span edges is hashed into the same $D$ dimensions. The same ridge readouts and the same semi-Markov decoder are applied on top. This baseline removes recurrence while keeping everything else fixed.
We add two further ablations. The first is a nonlinear random projection of the window n-gram features with no recurrence, in the style of closed-form random-feature models (Miche). The second is a unidirectional reservoir. Beating the n-gram readout means a significant F1 gain on the overlapping-ambiguity subset defined below, measured by paired bootstrap over sentences. A gain on overall F1 alone would not suffice.
Why not just…?
Why not just train a character BiLSTM or fine-tune a pretrained encoder like ZEN? At full data this will almost certainly win. The reported 95.8% and 97.1% from Cai et al. set a bar we do not claim to clear. The proposal's claims are therefore restricted to two regimes. One is data scarcity, where the only evidence the file offers is Hinaut's non-segmentation task. The other is training cost, where a closed-form solve competes with hours of training. Our re-trained BiLSTM curves over data fractions settle this. If the BiLSTM matches the reservoir at 1% of the data, the low-data claim is dead.
Why not just put hashed character n-grams into a linear model or L1-regularized CRF? This is the real threat. A reservoir might be nothing more than a lossy random encoding of recent n-grams, and Practical Very Large Scale CRFs shows that sparse explicit features scale well. That is why the equal-budget n-gram readout is the central ablation and why success is judged on long-context ambiguities. If the n-gram readout ties everywhere, we will report that fixed recurrence adds nothing for segmentation, which is itself a useful negative result.
Why not just use a variable-length Markov model? The Power of Amnesia compresses deep history cheaply. Its authors note, however, that prediction suffix trees ignore segment length. They also cannot share statistics across unseen character combinations, which matters for out-of-vocabulary words. We will train a suffix-tree boundary model with the same length prior and decoder. Out-of-vocabulary recall is the metric where we expect it to fall behind. If it does not, reservoir dynamics offer no generalization over discrete history pruning.
Why not just use fixed random features over a window, with no recurrence? If this matches the reservoir, the benefit comes from random nonlinear expansion rather than from dynamics. The feedforward random-projection ablation tests exactly this.
Proposed Experiments
The benchmarks are SIGHAN Bakeoff-2005 PKU and MSR, Chinese TreeBank 8.0, and the Kyoto University Corpus. On Kyoto, the CRF of Kudo et al. reports 98.96% segmentation F-score using a dictionary lattice; our system uses no dictionary. Metrics are word F1, out-of-vocabulary recall, training wall-clock time, and decoding throughput. Each setting uses five reservoir seeds, and we report the variance across seeds. Training fractions are 1%, 5%, 25% and 100%.
We construct an overlapping-ambiguity test subset automatically. It contains every gold test position where two different training-lexicon words overlap. Each case is tagged with the distance to the nearest character whose removal flips the reference segmenter's decision.
Three decisive checks follow.
First, on the ambiguity subset, reservoir F1 should exceed the equal-budget n-gram readout, and the gap should widen with resolving distance. If the gap is flat or reversed, the core claim fails.
Second, sweeping spectral radius and leak rate should move reservoir memory capacity. Ambiguity error at each distance should track that capacity. This links the fading-memory property to specific segmentation errors.
Third, at the 1% and 5% fractions, the reservoir should beat the re-trained BiLSTM on F1 and on out-of-vocabulary recall. If it does not, the low-data motivation drawn from Hinaut does not transfer to boundary discovery.
A secondary check measures decoding cost as the maximum word length $K$ grows. It compares our first-order semi-Markov pass with an explicit order-$m$ character Markov tagger. The aim is to confirm that accuracy gains from longer context come without the exponential table growth.
References
- The Power of Amnesia
- Practical Very Large Scale CRFs
- Efficient Staggered Decoding for Sequence Labeling
- Online Markov Decoding: Lower Bounds and Near-Optimal Approximation Algorithms
- Neural Word Segmentation Learning for Chinese
- Fast and Accurate Neural Word Segmentation for Chinese
- Applying Conditional Random Fields to Japanese Morphological Analysis
- ZEN: Pre-training Chinese Text Encoder Enhanced by N-gram Representations
- Interpreting Word-Level Hidden State Behaviour of Character-Level LSTM Language Models
- Randomized Machine Learning Approaches: Recent Developments and Challenges
- Adaptive Nonlinear System Identification with Echo State Networks
- Efficient Implementations of Echo State Network Cross-Validation
- Bidirectional deep echo state networks.
- Robot Language Acquisition Modelling via Cross-Situational Learning with Little Data
- Learning Beyond Experience: Generalizing to Unseen State Space with Reservoir Computing
- Comparison between DeepESNs and gated RNNs on multivariate time-series prediction
- Transfer Deep Learning for Low-Resource Chinese Word Segmentation with a Novel Neural Network
- Synthetic Word Parsing Improves Chinese Word Segmentation
- Spiking networks for improved cognitive abilities of edge computing devices