Hashing, sketching and very wide data
A training collection can become difficult to handle because its representation is wide. An observation may use only a few features drawn from a very large vocabulary, leaving most entries empty. The important resource question is then how to represent the active information without maintaining an unnecessarily large structure.
Hashing and sketching address related parts of this problem. Feature hashing maps feature identities into a fixed space; a sketch keeps a compact summary for particular queries. Both introduce collisions or approximation that must be understood alongside their memory use. Compactness is useful only when the information retained serves the learning task.
Width and sparsity are different properties
Width describes how many feature positions a representation allows. Sparsity describes how few of those positions are active for an observation. A sparse vector can be extremely wide while storing only its nonzero entries. Processing such data efficiently requires attention to both properties: a method may avoid storing empty entries yet still need a large dictionary connecting feature identities to positions.
Text data provide a common setting for this distinction. A vocabulary defines possible features, while an individual document contains only a portion of them. New observations can also introduce previously unseen features. A representation that depends on a complete dictionary has to manage this growth. Online learning makes that requirement visible because data may arrive before the eventual vocabulary is known.
Feature hashing replaces a lookup with a rule
Feature hashing applies a hash function to a feature’s identity and uses the result to select a position in a vector. The mapping can be applied whenever the feature appears, without looking up an entry in a separately maintained dictionary. A fixed representation can therefore accept features from a larger identity space, although distinct features can map to the same position.
The research paper Feature Hashing for Large Scale Multitask Learning analysed feature hashing and reported experiments in multitask learning. Its description included probability bounds and the interaction between random subspaces. This treated hashing as a statistical representation whose behaviour needed analysis, rather than merely a convenient way to shorten feature identifiers.
A collision shares a position between features that otherwise have different identities. The available representation size affects how much information is combined in this way. A hashing scheme also has to use the same mapping during training and later prediction. Changes in the mapping would change what the model’s parameter positions mean, even if the incoming observations remained the same.
A count–min sketch answers frequency queries
Wikipedia’s count–min-sketch article describes a probabilistic frequency table for events in a stream. It uses hash functions and a compact table instead of keeping a separate exact count for every possible event. An arriving event updates selected positions, and a query combines information from the positions associated with that event.
In the basic count–min setting, collisions can make an event’s frequency appear larger than its true count. The approximation has a direction as well as a magnitude. That matters when a later operation interprets a frequency estimate. The table’s dimensions and hashing assumptions are therefore part of its meaning, rather than an incidental implementation choice.
A sketch is designed around the queries it supports. A frequency summary does not retain every property of the underlying observations and cannot automatically replace the full training collection. The appropriate question is which later calculation needs the summary. A compact structure is valuable when its defined approximation fits that calculation’s tolerance for error.
Vowpal Wabbit and online representations
Vowpal Wabbit’s project description presents online and active learning among its capabilities. Its feature representation also uses the hashing trick to convert feature identities into weight indices. This connects an incremental learning process to a representation that can handle features as observations are processed.
The representation and the update algorithm solve different parts of the task. Hashing determines which parameter positions correspond to incoming features; the learning method determines how those parameters change. The optimisation topic explains the cost and variability of such updates. Combining these ideas requires checking their interaction rather than assuming that a compact vector establishes the quality of the fitted model.
PCA and clustering ask different questions
Wikipedia’s principal-component-analysis article describes PCA as a linear dimensionality-reduction technique. PCA uses patterns of variation in the data to define a new coordinate system. Feature hashing instead uses a rule based on feature identity. These are distinct ways to change a representation, with different information requirements and different reasons for retaining some structure over others.
K-means groups observations around representative centres by assigning each observation to its nearest centre. Its task is clustering rather than feature indexing or frequency estimation. At scale, repeated assignment and centre-update steps require data access and aggregation. Dataflow systems gives a framework for reasoning about those repeated operations and the movement of intermediate results.
Assessment follows the information retained
A compact representation should be evaluated through the downstream task and the approximation it introduces. Memory consumption, processing work and predictive behaviour describe different outcomes. A smaller structure can change several of them at once. The overview of big learning places this choice within the wider question of useful statistical progress under a computing budget.