Is the final model random every time it answers?

Usually no. A fixed sampled map and fitted predictor give repeatable outputs for the same input.

Are the output coefficients learned?

Yes, commonly a linear model learns how to use the fixed random representation.

Do random Fourier features approximate every possible kernel?

No. Their standard construction applies to suitable shift-invariant kernels under the relevant assumptions.

AI Glossary / AI and machine learning / Advanced

Random feature

Definition

A random feature is a component of a representation constructed using sampled parameters rather than learning every transformation parameter from the training labels. In kernel approximation, random features provide an explicit map whose inner products approximate a chosen kernel, allowing a linear learning algorithm to model nonlinear relationships in the original inputs.

What it means

Random does not mean irrelevant or unstructured. The sampling distribution is chosen to produce useful mathematical properties. Once sampled, the same transformation must be applied consistently to training and future inputs. The output model can then learn how to combine the transformed features. A common example is random Fourier features for suitable shift-invariant kernels. The approach trades an exact or more expensive representation for a finite approximation, so the number of features becomes a practical choice affecting computation and accuracy.

How it works

Choose a target kernel and a compatible randomized feature construction. Sample the transformation parameters, map each input into the resulting feature vector, and train a linear predictor on those vectors. Rahimi and Recht describe random Fourier and random binning constructions for kernel approximation. For Fourier features, sampled frequencies and sinusoidal functions create an explicit representation. The central relationship is that a dot product between mapped inputs approximates their kernel similarity. Preserve the sampled parameters for serving and evaluate the approximation and prediction quality under the intended data distribution.

Three practical examples

A hypothetical forecasting team tests random features when a full kernel-based model becomes too expensive on its growing training set.
A classification experiment compares different feature-map sizes, measuring whether the extra computation produces meaningful gains on held-out examples.
A deployment engineer stores the sampled transformation alongside the fitted predictor so the same raw input receives the same representation after the model is moved to another environment.

Think of it this way

Think of constructing many predetermined measuring lenses, then learning which combination of their readings helps predict an outcome. Random sampling chooses the lenses according to a useful design, rather than guessing a new answer each time. The analogy has limits: the actual approximation depends on the construction and its mathematical assumptions, not on randomness alone.

Worked example

Suppose a learning problem has 20,000 training examples. A fully stored pairwise kernel matrix would contain 20,000² = 400 million entries. An explicit random-feature matrix with 500 columns would contain 20,000 × 500 = 10 million entries. At eight bytes per stored value, these raw arrays occupy approximately 3.2 billion and 80 million bytes respectively, before other storage. This comparison illustrates why a feature approximation may be attractive. It does not include mapping costs, solver workspaces or alternatives that avoid storing the full kernel matrix. It also does not show that 500 features provide sufficient accuracy for the problem.

Illustrative case study

A fictional service-demand team explores nonlinear prediction as its historical dataset grows. It compares a simple linear baseline, a kernel model on a manageable reference sample and several random-feature models. The team repeats the randomized construction with different seeds to see whether results are stable. It selects a configuration using validation data, then evaluates it on a later period without retuning. The chosen artifact includes preprocessing, sampled mapping parameters and fitted coefficients. The project judges success by useful predictions and practical operating cost, rather than interpreting a smaller matrix as proof of a better business model.

Common misconceptions and mistakes

Random features are not the same as selecting a random subset of existing columns. They are also not simply arbitrary noise appended to data. The generated representation may have more dimensions than the original input while still approximating a much larger or implicit kernel space. More features usually increase cost and do not guarantee better held-out predictions. Redrawing the map at prediction time breaks the relationship with learned coefficients. A small approximation error for a kernel does not remove errors caused by unsuitable inputs, targets or model assumptions.

Business use

The method can help teams explore kernel-like nonlinear models under memory and computation limits. Ask which kernel is being approximated and whether that similarity assumption suits the task. Compare complete training and serving costs, not just matrix dimensions. Preserve reproducibility through saved parameters, and measure variation across seeds during development. Treat feature count, kernel settings and regularization as model choices requiring validation. For a production decision, weigh any accuracy gain against latency, maintenance and the availability of simpler approaches that meet the same need.

Check your understanding

Why must the feature map travel with the fitted model?

Answer: The coefficients refer to those particular transformed coordinates.

In the storage example, what crucial question remains unanswered?

Answer: Whether the approximation meets the task's predictive requirements.

Why compare several seeds during development?

Answer: A single sampled map can give an unrepresentative result. Explain why “linear in transformed features” can still mean nonlinear behavior in the original inputs.

Related terms

Kernel method
Feature map
Linear model
Random projection
random Fourier features
kernel approximation

Learn next

Study the kernel trick and why pairwise similarities can become expensive. Then compare random-feature and Nyström approximations. Explore feature-map size, kernel scale and regularization together, keeping the final test set separate from those choices.

Sources

Ali Rahimi and Benjamin Recht, Random Features for Large-Scale Kernel Machines: https://papers.nips.cc/paper/3182-random-features-for-large-scale-kernel-machines.pdf Conference record: https://papers.nips.cc/paper/2007/hash/013a006f03dbc5392effeb8f18fda755-Abstract.html The storage calculation and service-demand scenario are original illustrations, not measured benchmark results. Independent review consulted Rahimi and Recht's explicit feature-map formulation and Fourier/binning constructions, including the shift-invariant-kernel assumptions. The storage comparison was independently checked and explicitly excludes solver overhead and any accuracy guarantee.

Previous: Random experiment Next: Random forest