{
  "id": "enwiki-001349582208",
  "slug": "random-feature",
  "title": "Random feature",
  "qid": "",
  "lead": "Random features (RF) are a technique used in machine learning to approximate kernel methods, introduced by Ali Rahimi and Ben Recht in their 2007 paper \"Random Features for Large-Scale Kernel Machines\", and extended by. RF uses a Monte Carlo approximation to kernel functions by randomly sampled feature maps. It is used for datasets that are too large for traditional kernel methods like support vector machine, kernel ridge regression, and gaussian process.",
  "body": "Random features (RF) are a technique used in machine learning to approximate kernel methods, introduced by Ali Rahimi and Ben Recht in their 2007 paper \"Random Features for Large-Scale Kernel Machines\", and extended by. RF uses a Monte Carlo approximation to kernel functions by randomly sampled feature maps. It is used for datasets that are too large for traditional kernel methods like support vector machine, kernel ridge regression, and gaussian process. Given a feature map \\phi: \\R^d \\to V , where V is a Hilbert space (more specifically, a reproducing kernel Hilbert space), the kernel trick replaces inner products in feature space \\langle \\phi(x_i), \\phi(x_j)\\rangle_V by a kernel function k(x_i, x_j): \\R^d \\times \\R^d \\to \\R Kernel methods replaces linear operations in high-dimensional space by operations on the kernel matrix: K_X := [k(x_i, x_j)]_{i, j \\in 1:N} where N is the number of data points. The problem with kernel methods is that the kernel matrix K_X has size N \\times N . This becomes computationally infeasible when N reaches the order of a million. The random kernel method replaces the kernel function k by an inner product in low-dimensional feature space \\R^D : k(x,y) \\approx \\langle z(x), z(y)\\rangle where z is a randomly sampled feature map z : \\R^d \\to \\R^D . This converts kernel linear regression into linear regression in feature space, kernel SVM into SVM in feature space, etc. Since we have K_X \\approx Z_X^T Z_X where Z_X = [z(x_1), \\dots, z(x_N)] , these methods no longer involve matrices of size O(N^2) , but only random feature matrices of size O(DN) . k(x_i, x_j) = \\exp\\left(-\\frac{\\|x_i - x_j \\|^2}{2\\sigma^2}\\right) where \\|x_i - x_j \\|^2 is the squared Euclidean distance and \\sigma is a free parameter defining the shape of the kernel. It can be approximated by a random Fourier feature map z: \\R^d \\to \\R^{2D} : z(x) := \\frac{1}{\\sqrt D}[\\cos\\langle \\omega_1, x\\rangle, \\sin\\langle \\omega_1, x\\rangle, \\ldots, \\cos\\langle \\omega_D, x\\rangle, \\sin\\langle \\omega_D, x\\rangle]^T where \\omega_1, ..., \\omega_D are IID samples from the multidimensional normal distribution N(0, \\sigma^{-2} I) . {{Math proof |proof= (Unbiased estimation) By independence of \\omega_1, ..., \\omega_D , it suffices to prove the case of D=1 . By the trigonometric identity \\cos(a-b) = \\cos(a)\\cos(b) + \\sin(a)\\sin(b) , \\langle z(x), z(y)\\rangle = \\frac 1D \\sum_{i=1}^D \\cos \\langle \\omega_i, x-y\\rangle Apply the spherical symmetry of normal distribution, then evaluate the integral: \\int_{-\\infty}^\\infty \\frac{\\cos (k x) e^{-x^2 / 2}}{\\sqrt{2 \\pi}} d x=e^{-k^2 / 2}. (Variance bound) Since \\omega_1, ..., \\omega_D are IID, it suffices to prove that the variance of \\cos \\langle \\omega_1, x-y\\rangle is finite, which is true since it is bounded within [-1, +1] . (Convergence) By Chebyshev's inequality. }}Since \\cos, \\sin are bounded, there is a stronger convergence guarantee by Hoeffding's inequality. By Bochner's theorem, the above construction can be generalized to arbitrary positive definite shift-invariant kernel k(x, y) = k(x-y) . Define its Fourier transform p(\\omega)=\\frac{1}{2 \\pi} \\int_{\\R^d} e^{-j \\langle\\omega, \\Delta \\rangle} k(\\Delta) d \\Delta then \\omega_1, ..., \\omega_D are sampled IID from the probability distribution with probability density p . This applies for other kernels like the Laplace kernel and the Cauchy kernel. Given a random Fourier feature map z , training the feature on a dataset by featurized linear regression is equivalent to fitting complex parameters \\theta_1, \\dots, \\theta_D \\in \\C such that f_\\theta(x) = \\mathrm{Re}\\left( \\sum_k \\theta_k e^{i \\langle \\omega_k , x \\rangle} \\right) which is a neural network with a single hidden layer, with activation function t \\mapsto e^{it} , zero bias, and the parameters in the first layer frozen. In the overparameterized case, when 2D \\geq N , the network linearly interpolates the dataset \\{(x_i, y_i)\\}_{i \\in 1:N} , and the network parameters is the least-norm solution: \\hat \\theta = \\arg\\min_{\\theta \\in \\C^D, f_\\theta(x_k) = y_k \\forall k\\in 1:N} \\|\\theta\\| At the limit of D \\to \\infty , the L2 norm \\|\\hat\\theta\\| \\to \\|f_{K}\\|_H where f_K is the interpolating function obtained by the kernel regression with the original kernel, and \\|\\cdot\\|_H is the norm in the reproducing kernel Hilbert space for the kernel.",
  "categories": [
    "20314193",
    "22921972",
    "23603337",
    "26220375",
    "41698445",
    "72655480"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1349582208",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1776464510.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001349582208",
    "type": "webpage",
    "title": "Random feature",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/random-feature",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001349582208",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1349582208",
    "note": "Immutable snapshot enwiki-001349582208"
  }
}