Is SBPH itself a complete classifier?

No; generated features still need learned statistics, a scoring rule and a decision procedure.

Does sparse mean few training documents?

No; here it refers to omitted positions in the pattern construction.

Are all CRM114 classifiers based on exactly the same features and weights?

No; the research and implementation describe multiple variants.

AI Glossary / Statistics and probability / Advanced

Sparse binary polynomial hashing

Definition

Sparse binary polynomial hashing, or SBPH, is a text-feature generation technique associated with the CRM114 classifier. It represents combinations of words within a sliding window, including patterns that skip selected positions, and converts those patterns into hash values. These features can feed a statistical classifier such as a spam filter. In this context, sparse describes omitted word positions, binary describes inclusion choices, and polynomial hashing combines token hashes. It is not a general synonym for neural text embeddings or semantic similarity search.

What it means

A single-word representation can miss useful phrase structure. An exact phrase representation can be too brittle when one word changes. SBPH creates several overlapping patterns from a short passage, preserving order and gaps while omitting selected words. Some features can therefore survive a local wording change. The resulting representation captures limited textual structure without requiring a full linguistic analysis. It does not understand the meaning of a message, and similar meanings expressed with very different wording may share few useful features.

How it works

Tokenize the text according to a specified rule and move a fixed-width window through the token sequence. In the historical five-word construction, retain the first word and consider all inclusion choices for the remaining four positions, producing sixteen patterns for a full window. Compute hashes that reflect the selected words and their positions, then update or consult learned class statistics. The downstream scoring rule matters: CRM114 variants used different weighting schemes. Feature generation, classification and decision thresholds are separate components that should be documented together.

Three practical examples

Example 1: A historical spam filter uses both complete short phrases and patterns that tolerate an intervening word change. Example 2: A text-classification experiment compares SBPH features with single-word features on a labeled collection. Example 3: A researcher examines whether preserving gaps helps distinguish recurring message templates. These are examples of feature engineering rather than guarantees of accuracy. Evaluation must include realistic new messages and the costs of false positives, especially when legitimate messages resemble unwanted ones.

Think of it this way

Think of viewing a short phrase through several stencils. Some reveal every word; others cover one or more positions while leaving the remaining words in their original places. Two phrases can match through a stencil even when a covered word differs. Hashing gives each revealed pattern a compact identifier, but identifiers can collide and the stencil never supplies a full understanding of the sentence.

Worked example

Use a simplified four-token window, shorter than the historical five-token example, containing claim, your, reward, now. Always include claim and independently include or omit each of the other three positions. There are 2 cubed = eight positional patterns: one with only the anchor, three with two words, three with three words, and one containing all four. Compare a second window containing claim, the, reward, now. Before hashing, exactly four patterns are shared: those omitting the changed second position while choosing freely whether to include reward and now. The full four-word pattern is not shared. This count illustrates partial matching, not a predicted class or an accuracy rate. With a full five-token window and the first token fixed, the same counting rule gives 2 to the fourth power = sixteen patterns. Actual hashes, boundaries and scoring depend on the implementation.

Illustrative case study

In this fictional case study, Beacon Mail evaluates an archived CRM114-based approach as a transparent historical baseline. Engineers inspect how short message templates produce overlapping features and test false-positive rates on legitimate correspondence. They keep tokenization fixed, separate training from evaluation and review messages whose class scores are close. The team does not adopt an old accuracy claim as a current service guarantee. Its report distinguishes the representation's ability to preserve some local patterns from the classifier's measured performance on the present dataset.

Common misconceptions and mistakes

Common mistakes include calling SBPH a cryptographic protection method, assuming hashes are collision-free, and treating all generated features as independent evidence. Features from the same window overlap strongly, so a probability-like score may need calibration before being interpreted literally. Another mistake is confusing the historical sequence-and-spacing-sensitive construction with a bag of words or with every possible subsequence of an entire document. The window width limits the local context, and tokenization changes which features are produced.

Business use

Businesses can learn from SBPH when comparing lightweight text representations or maintaining older classification systems. A practical assessment should measure missed unwanted messages, incorrectly blocked legitimate messages, memory use and processing cost under the chosen configuration. Increasing window width increases the number of inclusion patterns exponentially, so representational richness has a cost. Language changes and adversarial wording can affect performance. Any operational use needs a monitored feedback process and a way to review consequential mistakes, rather than reliance on the feature generator alone.

Check your understanding

How many anchored patterns arise from four positions?

Answer: Eight.

Why are four patterns shared after the second token changes in the example?

Answer: They omit that position and independently select the last two.

Do sixteen generated patterns imply sixteen independent observations?

Answer: No; their contents overlap.

What is still needed to assign a message category?

Answer: A trained scoring and decision process.

Related terms

Tokenization
Skip-gram
Bag of words
Related terms include feature hashing
Bayesian text classification
hash collision and CRM114

Learn next

Learn next how tokenization, window boundaries and hash collisions affect text representations. Compare independent-word models with overlapping phrase features, and inspect calibration separately from classification accuracy. For historical implementations, read the exact classifier documentation before assuming that a newer variant uses the same feature weighting or evaluation rule.

Tokenization

Sources

Sources: Yerazunis, MERL research report TR2004-091, https://www.merl.com/publications/docs/TR2004-091.pdf; CRM114 implementation notes, https://sources.debian.org/src/crm114/20100106-9/CLASSIFY_DETAILS.txt; CRM114 TREC report, https://www.mi.fu-berlin.de/en/inf/groups/ag-db/media/publications/2005/siefkes-NIST_TREC_2005_paper.pdf. These primary sources describe the historical construction and classifier variants. The four-token count is original and independently enumerated; the case is fictional.

Previous: Sparse Auto Encoder Next: Sparse feature