Pick forward or reverse MaxMatch with a unigram language model

Context

Hashtags glue words together, so #alliswell has to be split before it is useful as a feature. Question 2 asked for MaxMatch over NLTK's word list, Question 3 for the same algorithm run from the right-hand end, and Question 4 for a language model trained on the Brown corpus to choose between the two outputs. My MaxMatch also accepts a fragment when its WordNet lemma is in the word list, so inflected forms such as "images" match.

The dataset has 425 distinct hashtags. The two directions disagree on 124 of them. There is no gold segmentation in the dataset, so neither direction has a measured accuracy.

Decision

I score both candidate splits with a unigram model over the lowercased Brown corpus and keep the one with the less negative score. Each token contributes log((count + 1) / (N + V)), with N = 1,161,192 tokens and V = 49,815 word types. Add-one smoothing gives tokens Brown has never seen a small probability instead of zero, so every candidate gets a finite score.

Options considered

1. Always forward MaxMatch. Simple, but greedy matching from the left breaks words such as "october" in #1stsundayofoctober into "ofo · c · tobe · r".
2. Always reverse MaxMatch. It handles that case but fails in the other direction, for example #alliswell becomes "al · li · swell".
3. Score both with a unigram model (chosen). This is what the question asked for. It needs only word counts and is easy to explain.
4. A bigram model or a Viterbi segmenter over every possible split. Stronger in principle, but outside the question, which asked me to compare the two MaxMatch outputs.

Why

The unigram model was the simplest model that could rank two candidate splits, and its scores are easy to inspect by hand. The question set the scope, and the comparison only had to be between the two greedy outputs.

What happened

• Of the 124 hashtags where the directions disagree, one is an exact tie. Of the other 123, the reverse split wins 67 times (54.5%, Wilson 95% CI 45.7% to 63.0%) and the forward split wins 56 times. The interval includes 50%, so this sample gives no evidence that either direction is better in general.
• In 59 disagreements the two splits have a different number of tokens. The model chose the split with fewer tokens in 58 of them (98.3%, Wilson 95% CI 91.0% to 99.7%). Every token adds a negative term to the score. The most common Brown word, "the", costs about −2.85 and a token Brown has never seen costs about −14.0. In practice the model works mostly as a penalty on the number of tokens.
• When both directions are wrong, the model can only pick the less bad error. #vegan becomes "vega · n" forward and "v · e · gan" reversed, and the model keeps "vega · n".
• The TypeScript port reproduces all 425 forward and reverse segmentations and matches the notebook's log-probabilities to 9 decimal places.

What I'd change

• Hand-label a random sample of about 100 hashtags with gold splits, so each method gets an accuracy with a Wilson interval instead of a win count.
• Compare against a Viterbi segmenter over all splits, with a per-token penalty tuned on held-out hashtags, and against a bigram model.
• Count words from social-media text. Brown is 1961 American English and has never seen "vsco" or "kpop".