随机厨房水槽算法工作原理是什么？如何近似高斯过程与支持向量机？

Awesome question—let’s unpack this clearly, starting with the basics.

First, let's set the context: traditional kernel methods (like kernel SVMs or Gaussian Processes) work great for capturing nonlinear patterns, but they hit a wall with large datasets. The problem is the O(n²) complexity of computing and storing the kernel matrix—for millions of samples, this becomes computationally impossible (think a matrix with 1e12 elements).

Random Kitchen Sinks solves this by using randomly generated linear projections to approximate kernel functions, turning a nonlinear kernel problem into a linear one. Here's the step-by-step breakdown:

1. Generate random feature mappings: For a target kernel (most commonly the Gaussian RBF kernel), we randomly sample parameters like weight vectors w and biases b. For RBF kernels, the mapping looks like:
   z(x) = (1/√d) * cos(w·x + b)
   Here, d is the number of random features, w is sampled from a distribution matching the kernel's properties (Gaussian for RBF), and b is uniformly sampled from [0, 2π).
2. Train a linear model: In this new random feature space, we train a simple linear model (like linear SVM or linear regression). The key trick is that the dot product of two random features z(x)·z(y) closely approximates the original kernel function k(x,y). This means the linear model’s performance matches the kernel method’s, but with a much lower O(n*d) complexity—critical for large datasets.

The "kitchen sink" name comes from the no-fuss approach: we throw a bunch of random features into the mix (like tossing stuff into a kitchen sink) and rely on sheer quantity to approximate the kernel’s effect, no fancy feature engineering required.

Approximating Gaussian Processes (GPs) #

Gaussian Processes depend on an n×n covariance matrix K (computed via the kernel function) to model sample relationships. For large n, inverting or decomposing K is O(n³)—completely infeasible.

RKS approximates k(x,y) ≈ z(x)·z(y), so the covariance matrix K can be replaced with Z^T Z (where Z is the matrix of random features for all samples). This lets us convert GP predictions into linear model predictions: we train a linear regression model on Z, and the results closely match a full GP—with complexity reduced to O(n*d + d³), which is manageable when d is much smaller than n.

Approximating Support Vector Machines (SVMs) #

Traditional kernel SVMs require solving a quadratic programming problem with O(n²) to O(n³) complexity—way too slow for large datasets.

With RKS, we map the original data to the random feature space, then train a linear SVM instead. Since the random feature dot product approximates the kernel, the linear SVM’s decision boundary in this space is nearly identical to the kernel SVM’s nonlinear boundary in the original space. Linear SVMs can be trained efficiently with methods like Stochastic Gradient Descent (SGD), bringing complexity down to O(n*d) and making large-scale training feasible.

Rahimi and Recht showed just how simple RKS can be with this concise snippet (core logic preserved):

% x = input data (d_input dimensions), y = labels
d = 1000; % Number of random features
w = randn(d, size(x,1)); b = rand(d,1)*2*pi; % Sample random params
z = cos(w*x + b)/sqrt(d); % Generate random features
model = fitlinear(z, y); % Train linear model
y_pred = model.predict(cos(w*x_test + b)/sqrt(d)); % Make predictions

内容的提问来源于stack exchange，提问作者MachineEpsilon