现在我们来考虑一个很典型的基本问题，即给定数据集 $\left\{ (\mathbf{x}{n},y{n}) \right\}{n=1}^{N}$ ，其中 $\mathbf{x}{n}\in\mathcal{X}$ 为数据， $y_{n}\in\mathcal{Y}$ 为对应数据的标签（在分类问题中）。这里，我们先忽略偏置项，假设一个线性模型可以找到一个超平面 $\boldsymbol{\alpha}^{\top} = \left[ \alpha_{1}, \alpha_{2}, \dots, \alpha_{N}\right]$ 满足以下等式（或决策函数）
$$ f^{\ast}(\mathbf{x}) = \boldsymbol{\alpha}^{T} \mathbf{x} \tag{1} $$
以至于对某一特定目标函数是最优的。例如，在逻辑回归问题里面，我们可以计算逻辑函数 $f(\mathbf{x})$ ，然后对计算的输出值设定一个固定的阈值，就可以得到一个二分类的问题，使得 $\mathcal{Y} = \left\{ 0,1 \right\}$ 。很明显，当我们数据不是线性可分的时候，或者当数据和标签之间的关系不是线性关系的时候，直接简单线性回归的公式（1）就不行了。
为了处理该类问题，在核方法（kernel method）中，经常会将输入域 $\mathcal{X}$ 映射到另外一个空间 $\mathcal{V}$ ，并且在该空间内，标签可以被看作为数据点的线性表示。这里需要指出的是：空间 $\mathcal{V}$ 的维度有可能是高维的，也可以是无限维的。巧妙的是，使用核技巧可以避免在该高维空间中进行显式操作，即：如果核 $k: \mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$ 是一个正定核，那么根据理论，存在一个基函数或特征映射 $\varphi:\mathcal{X}\rightarrow\mathcal{V}$ ，使得以下成立：
$$ k(\mathbf{x},\mathbf{y})=⟨φ(\mathbf{x}),φ(\mathbf{y})⟩_{\mathcal{V}} \tag{2} $$
其中， $⟨\cdot,\cdot⟩_{\mathcal{V}}$ 是在空间 $\mathcal{V}$ 下的内积。利用这个核技巧及表征理论，核方法能够使得我们构建一个关于 $\mathcal{X}$ 的非线性模型，但是该模型却是核 ，$k(\cdot，\cdot)$ 的线性函数，即
$$ f^{\ast}(\mathbf{x})= \sum_{n=1}^{N} \alpha_n k(\mathbf{x},\mathbf{x}n)=⟨\boldsymbol{\alpha},φ(\mathbf{x})⟩{\mathcal{V}} \tag{2} $$
在公式（3）中， $f^{\ast}$ 表示最优的 $f$ 。这里我们注意到，将公式（2）和公式（3）结合起来，表明我们得到了一个正定的核函数 ，$k(\cdot，\cdot)$ ，我们可以避免在可能无限维空间 $\mathcal{V}$ 内进行操作计算，并且只计算 $N$ 个数据点就足够了。理论上而言，最佳决策规则可以表示为关于训练样本的某种扩展或延伸，所以这种操作变换是可行并且合理的。
核函数的应用在机器学习中经常用到，比如我们常用到的非线性支持向量机（Support Vector Machine）就会常用到核技巧。然而，任何可以表示为样本对之间的点积的算法都可以使用公式（2）转换为核方法， 其他可以视为核方法的方法有高斯过程（Gaussian Process，GP）、核主成分分析（ Kernel PCA） 和核回归（Kernel regression）。
尽管核技巧是一个非常好的想法，也是各种核方法的核心思想，但是针对于数据量大的情况下（即 $N$ 较大），需要计算由多个核函数组成的协方差矩阵 $\mathbf{K}_{X}$
$$ \mathbf{K}{X} = \begin{bmatrix} k(\mathbf{x}{1}, \mathbf{x}{1}) & k(\mathbf{x}{1}, \mathbf{x}{2}) & \dots & k(\mathbf{x}{1}, \mathbf{x}{N}) \\ k(\mathbf{x}{2}, \mathbf{x}{1}) & k(\mathbf{x}{2}, \mathbf{x}{2}) & \dots & k(\mathbf{x}{2}, \mathbf{x}{N}) \\ \vdots & \vdots & \ddots & \vdots \\ k(\mathbf{x}{N}, \mathbf{x}{1}) & k(\mathbf{x}{N}, \mathbf{x}{2}) & \dots & k(\mathbf{x}{N}, \mathbf{x}{N}) \\ \end{bmatrix}{N\times N} \tag{4} $$
当数据较多时，尽管核技巧可以避免在高维空间 $\mathcal{V}$ 内进行操作计算，但是还是无法避免大量的运算量，即 $\mathbb{R}^{N}$ 。
这里我们来考虑一个新问题，我们**是不是可以通过一种新的方式来近似公式（2）呢？**答案是可以的，具体如下：
首先，根据 Ali 和 Ben 的论文结论可知，我们可以找到一个随机映射 $\mathbf{z}:\mathbb{R}^{N}\rightarrow\mathbb{R}^{R}$ 近似公式（2），其中有维度 $R$ 远小于 $D$ （即 $R\ll N$ ），
$$ k(\mathbf{x},\mathbf{y}) = ⟨\varphi(\mathbf{x}), \varphi(\mathbf{y})⟩_{\mathcal{V}} \approx \mathbf{z}^{\top}(\mathbf{x})\mathbf{z}(\mathbf{y}) \tag{5} $$
如果我们能够比较好的近似 $\varphi(\cdot)$ ，那么我们可以得到
$$ \begin{equation} \begin{split} f^{\ast}(\mathbf{x}) & = \sum_{n=1}^{N} \alpha_{n} k(\mathbf{x}{n},\mathbf{x}) \\ & = \sum{n=1}^{N} \alpha_{n} ⟨\varphi(\mathbf{x}{n}), \varphi(\mathbf{x})⟩{\mathcal{V}} \\ & \approx \sum_{n=1}^{N} \alpha_{n}\mathbf{z}^{\top}(\mathbf{x}_{n})\mathbf{z}(\mathbf{x}) \\ & = \boldsymbol{\beta}^{\top} \mathbf{z}(\mathbf{x}) \end{split} \end{equation} \tag{6} $$
公式（6）表明，如果我们可以通过近似 $\varphi(\cdot)$ 为 $\mathbf{z}(\cdot)$ ，那么就可以简单的将我们的数据利用函数 $\mathbf{z}(\cdot)$ 映射到另一个空间 $\mathbb{R}^{R}$ ，且在该空间 $\mathbb{R}^{R}$ 内，由于 $\boldsymbol{\beta}$ 和 $\mathbf{z}(\cdot)$ 均是 $R$ 维的向量，我们可以利用快速高效的线性模型实现。因此，上述核近似的问题变成了找到一个随机映射 $\mathbf{z}(\cdot)$ 使得能够较好的近似非线性核。