Nyström Kernel
This kernel allows to approximate explicit feature maps for kernels whose explicit representation lives in an infinite-dimensional Hilbert space. Through eigendecomposition, we are able to find a base in the RKHS spanned by the provided sample. By looking at the RKHS coefficients for each datapoint, we are able to recover an approximate explicit feature map.
- class kerch.kernel.Nystrom(*args, **kwargs)[source]
Bases:
ExplicitNyström kernel. Constructs an explicit feature map based on the eigendecomposition of any kernel matrix based on some sample.
- Parameters:
dim (int, optional) – Dimension of the explicit feature map to be constructed. This value cannot exceed the number of sample points. During eigendecomposition, very small eigenvalues are also going to be pruned to avoid numerical instability. If None, the value will be assigned to num_sample., defaults to None
base_kernel_type – The name of kernel on which the explicit feature map is going to be constructed. Default to kerch.DEFAULT_KERNEL_TYPE
base_kernel_transform – Same as kernel_transform but for the base kernel, when using the factory through base_type. Defaults to [].
**kwargs (dict, optional) – Other arguments for the _Projected kernel (e.g. the bandwidth for an RBF kernel, the degree for a polynomial kernel etc.). For the default values, please refer to the requested class in question.
base_kernel (kerch.kernel.*, optional) – Instead of creating a new kernel on which to use the Nyström method, one can also perform it on an existing kernel. In that case, the other _Projected arguments are bypassed., defaults to None
kernel_transform (List[str]) – A list composed of the elements ‘normalize’ or ‘center’. For example a centered cosine kernel which is centered and normalized in order to get a covariance matrix for example can be obtained by invoking a linear kernel with default_transform = [‘normalize’, ‘center’, ‘normalize’] or just a cosine kernel with default_transform = [‘center’, ‘normalize’]. Redundancy is automatically handled., defaults to [].
sample (Tensor(num_sample, dim_input), optional) – Sample points used to compute the kernel matrix. When an out-of-sample computation is asked, it will be given relative to these samples., defaults to None
sample_trainable (bool, optional) – True if the gradients of the sample points are to be computed. If so, a graph is computed and the sample can be updated. False just leads to a static computation., defaults to False
num_sample (int, optional) – Number of sample points. This parameter is neglected if sample is not None and overwritten by the number of points contained in sample., defaults to 1
dim_input (int, optional) – Dimension of each sample point. This parameter is neglected if sample is not None and overwritten by the dimension of the sample points., defaults to 1
idx_sample (float, optional) – Initializes the indices of the samples to be updated. All indices are considered if both idx_stochastic and prop_stochastic are None., defaults to None
prop_sample – Instead of giving indices, specifying a proportion of the original sample set is also possible. The indices will be uniformly randomly chosen without replacement. The value must be chosen such that \(0 <\) prop_stochastic \(\leq 1\). All indices are considered if both idx_stochastic and prop_stochastic are None., defaults to None.
sample_transform (List[str]) – TODO
cache_level (str, optional) – Cache level for saving temporary execution results during the execution. The higher the cache, the more is saved. Defaults to
'normal'. We refer to the Cache Management documentation for further information.logging_level (int, optional) – Logging level for this specific instance. If the value is
None, the current default kerch global log level will be used. Defaults toNone(default kerch logging level). We refer to the Logging in Kerch documentation for further information.
- property C: Tensor
Returns the explicit matrix on the sample datapoints.
\[C = \frac{1}{\texttt{num_idx}}\sum_i^\texttt{num_idx} \phi(x_i)\phi(x_i)^\top.\]
- property K: Tensor
Returns the kernel matrix on the sample data. Same result as calling
k(), but faster. It is loaded from memory if already computed and unchanged since then, to avoid re-computation when recurrently called.\[K_{ij} = k(x_i,x_j).\]
- property Phi: Tensor
Returns the explicit feature map \(\phi(\cdot)\) of the sample datapoints. Same as calling
phi(), but slightly faster. It is loaded from memory if already computed and unchanged since then, to avoid re-computation when recurrently called.
- property base_kernel
Kernel on which Nystrom performs the decomposition.
- c(x=None, transform=None) Tensor
Out-of-sample explicit matrix.
\[C = \frac{1}{\texttt{num_x}}\sum_{i}^{\texttt{num_x}} \phi(x_i)\phi(x_i)^\top.\]- Parameters:
x (Tensor(num_x,dim_input), optional) – Out-of-sample points (first dimension). If None, the default sample will be used., defaults to None
- Returns:
Explicit matrix
- Return type:
Tensor[dim_feature, dim_feature]
- cache_keys(private: bool = False) Iterable[str]
Returns an iterable containing the different cache keys. We refer to the Cache Management documentation for more information.
- Parameters:
private (bool, optional) – Some cache elements are private and are not returned unless set to
True. Defaults toFalse.
- property cache_level: str
Cache level for saving temporary execution results during the execution. The higher the cache, the more is saved. Defaults to
'normal'unless set otherwise during instantiation. The different possible values are:"none": the cache is non-existent and everything is computed on the go."light": the cache is very light. For example, only the kernel matrix and statistics of the sample points are saved."normal": same as light, but the statistics of the out-of-sample points are also saved."heavy": in addition to the statistics, the final kernel matrices of the out-of-sample points are saved."total": every step of any computation is saved.
We refer to the Cache Management documentation for further information.
- property centered: bool
Indicates whether the feature map is centered relative to its sample or equivalently is the kernel in centered in its RKHS space, spanned by the sample.
- corr(x=None) Tensor
Returns the correlation matrix fo the provided input.
- Parameters:
x (Tensor[N, dim_input], optional) – Out-of-sample points (first dimension). If None, the default sample will be used., defaults to None
- Returns:
Correlation matrix
- Return type:
Tensor[dim_feature, dim_feature]
- cov(x=None) Tensor
Returns the covariance matrix fo the provided input.
- Parameters:
x (Tensor[N, dim_input], optional) – Out-of-sample points (first dimension). If None, the default sample will be used. Defaults to None.
- Returns:
Covariance matrix
- Return type:
Tensor[dim_feature, dim_feature]
- property current_sample_projected: Tensor
Returns the sample that is currently used in the computations and for the normalizing and centering statistics if relevant.
- property dim
Dimension of the explicit feature map.
- explicit_preimage(phi_image: Tensor | None = None, method: str = 'explicit', **kwargs) Tensor
Computes a pre-image of an explicit feature map of the kernel, given by
phi_image. Different methods are available:'explicit': Uses an explicit implementation specific to the kernel (if available). This is always preferable if available.'knn': Nearest neighbors. We refer tokerch.method.knn()for more details.'smoother': Kernel smoothing. We refer tokerch.method.smoother()for more details'iterative': Iterative optimization. We refer tokerch.method.iterative_preimage_phi()for more details
- Parameters:
phi_image (torch.Tensor [num_points, dim_feature], optional) – Explicit feature map image to be inverted. If not specified (
None), the explicit feature map on the sample is used.method (str, optional) – Pre-image method to be used. Defaults to
'explicit'.**kwargs (dict, optional) – Additional parameters of the pre-image method used. Please refer to its documentation for further details.
- Returns:
Pre-image
- Return type:
torch.Tensor [num_points, dim_input]
- forward(x, representation='dual') Tensor
Passes datapoints through the kernel.
- Parameters:
x (Tensor(,dim_input)) – Datapoints to be passed through the kernel.
representation (str, optional) – Chosen representation. If dual, an out-of-sample kernel matrix is returned. If primal is specified, it returns the explicit feature map., defaults to dual
- Returns:
Out-of-sample kernel matrix or explicit feature map depending on representation.
- Raises:
RepresentationError
- hparams_fixed()[source]
Dictionnary containing the hyper-parameters and their values. This can be relevant for monitoring.
- property hparams_variable: dict
Dictionnary containing the parameters and their values. This can be relevant for monitoring.
- property idx: Tensor
Indices used when performing various operations. This is only relevant in the case of stochastic training.
- implicit_preimage(k_image: Tensor | None = None, method: str = 'knn', **kwargs)
Computes a pre-image of coefficients in the RKHS of the kernel, given by
k_image. Different methods are available:'knn': Nearest neighbors. We refer tokerch.method.knn()for more details.'smoother': Kernel smoothing. We refer tokerch.method.smoother()for more details'iterative': Iterative optimization. We refer tokerch.method.iterative_preimage_k()for more details
- Parameters:
k_image (torch.Tensor [num_points, num_idx], optional) – RKHS coefficients to be inverted. If not specified (
None), the kernel matrix on the sample is used.method (str, optional) – Pre-image method to be used. Defaults to
'knn'.**kwargs (dict, optional) – Additional parameters of the pre-image method used. Please refer to its documentation for further details.
- Returns:
Pre-image
- Return type:
torch.Tensor [num_points, dim_input]
- init_sample(sample=None, idx_sample=None, prop_sample=None)[source]
Initializes the sample set (and the stochastic indices).
- Parameters:
sample (Tensor, optional) – Sample points used for the various computations. When an out-of-sample computation is asked, it will be given relative to these samples. In case of overwriting a current sample, num_sample and dim_input are also overwritten. If None is specified, the sample data will be initialized according to num_sample and dim_input specified during the construction. If a previous sample set has been used, it will keep the same dimension by consequence. A last case occurs when sample is of the class torch.nn.Parameter: the sample will then use those values, and they can thus be shared with the level calling this method., defaults to None
idx_sample (int[], optional) – Initializes the indices of the samples to be updated. All indices are considered if both idx_sample and prop_sample are None., defaults to None
prop_sample – Instead of giving indices, specifying a proportion of the original sample set is also possible. The indices will be uniformly randomly chosen without replacement. The value must be chosen such that \(0 <\) prop_sample \(\leq 1\). All indices are considered if both idx_sample and prop_sample are None., defaults to None.
- k(x=None, y=None, explicit=None, transform=None) Tensor
Returns a kernel matrix, either of the sample, either out-of-sample, either fully out-of-sample.
\[K = [k(x_i,y_j)]_{i,j=1}^{\texttt{num_x}, \texttt{num_y}},\]with \(\{x_i\}_{i=1}^\texttt{num_x}\) the out-of-sample points (x) and \(\{y_i\}_{j=1}^\texttt{num_y}\) the sample points (y).
Note
In the case of centered kernels on an out-of-sample, this computation is more expensive as it requires to center according to the sample data, which implies computing a statistic on the out-of-sample kernel matrix and thus also computing it.
- Parameters:
x (Tensor[num_x, dim_input], optional) – Out-of-sample points (first dimension). If None, the default sample will be used. Defaults to
Noney (Tensor[num_y, dim_input], optional) – Out-of-sample points (second dimension). If None, the default sample will be used. Defaults to
None
- Returns:
Kernel matrix
- Return type:
Tensor[num_x, num_y]
- Raises:
ExplicitError
- property kernel_transform: TransformTree
Default transform performed on the kernel
- property normalized: bool
Indicates whether the feature map is centered relative to its sample or equivalently is the kernel in centered in its RKHS space, spanned by the sample.
- property num_idx: int
Number of selected indices when performing various operations. This is only relevant in the case of stochastic training.
- phi(x=None, transform=None) Tensor
Returns the explicit feature map \(\phi(x)\) of the specified points.
- Parameters:
x (Tensor[num_x, dim_input], optional) – The datapoints serving as input of the explicit feature map. If None, the sample will be used. Defaults to
None.- Returns:
Explicit feature map \(\phi(x)\) of the specified points.
- Return type:
Tensor[num_x, dim_feature]
- Raises:
ExplicitError
- print_cache(private: bool = False) None
Prints the cache content. We refer to the Cache Management documentation for further information.
- Parameters:
private (bool, optional) – Some cache elements are private and are not returned unless set to
True. Defaults toFalse.
- reset(recurse=False, reset_persisting=True) None
Resets the cache to be empty. We refer to the Cache Management documentation for more information.
- Parameters:
recurse (bool, optional) – If
True, resets the cache of this module and also of its potential children. otherwise, it only resets the cache for this module. Defaults toTrue.reset_persisting (bool, optional) – Persisting elements are meant to resist to a cache reset (see
_save()). The option allows to also reset them ifTrue. Defaults toTrue.
- property sample: Parameter
Full original raw sample without any transform or potential stochastic selection.
- property sample_transform: TransformTree
Default transform used by the sample.
- stochastic(idx=None, prop=None)
Resets which subset of the samples are to be used until the next call of this function. This is relevant in the case of stochastic training.
- Parameters:
idx (int[], optional) – Indices of the sample subset relative to the original sample set., defaults to None
prop (double, optional) – Instead of giving indices, passing a proportion of the original sample set is also possible. The indices will be uniformly randomly chosen without replacement. The value must be chosen such that \(0 <\) prop_stochastic \(\leq 1\)., defaults to None.
If None is specified for both idx_stochastic and prop_stochastic, all samples are used and the subset equals the original sample set. This is also the default behavior if this function is never called, nor the parameters specified during initialization.
Note
Both idx_stochastic and prop_stochastic cannot be filled together as conflict would arise.
- train(mode=True)
Activates the training mode, which disables the gradients computation and disables stochasticity. For the gradients and other things, we refer to the torch.nn.Module documentation. For the stochastic part, when put in evaluation mode (False), all the sample points are used for the computations, regardless of the previously specified indices.
- transform_sample_revert(data) Tensor
Get back the original value from a projected value, by using the same transform as the sample, but in reverse. This is not always feasible, depending on the transform used (normalizations are typically not invertible as they are transform which are not bijective).
- update_sample(sample_values, idx_sample=None)[source]
Updates the sample set. In contradiction to init_samples, this only updates the values of the sample and sets the gradients of the updated values to zero if relevant.
- Parameters:
sample_values (Tensor) – Values given to the updated samples.
idx_sample (int[], optional) – Indices of the samples to be updated. All indices are considered if None., defaults to None
Example
Explicit RBF
We first consider an RBF kernel and will approximate its explicit feature map both for the sample input and an out-of-sample input.
import kerch
import numpy as np
from matplotlib import pyplot as plt
sample = np.sin(np.arange(0,15) / np.pi) + .1
oos = np.sin(np.arange(15,30) / np.pi) + .1
k_base = kerch.kernel.RBF(sample=sample)
k = kerch.kernel.Nystrom(base_kernel=k_base)
# kernel matrix
fig1, axs1 = plt.subplots(2,2)
fig1.suptitle('Kernel Matrices of the Base Kernel (RBF)')
axs1[0,0].imshow(k_base.K, vmin=0, vmax=1)
axs1[0,0].set_title("Sample - Sample")
axs1[0,1].imshow(k_base.k(y=oos), vmin=0, vmax=1)
axs1[0,1].set_title("Sample - OOS")
axs1[1,0].imshow(k_base.k(x=oos), vmin=0, vmax=1)
axs1[1,0].set_title("OOS - Sample")
im1 = axs1[1,1].imshow(k_base.k(x=oos, y=oos), vmin=0, vmax=1)
axs1[1,1].set_title("OOS - OOS")
for ax in axs1.flat:
ax.set_xticks([])
ax.set_yticks([])
fig1.colorbar(im1, ax=axs1.ravel().tolist())
# explicit feature map
fig2, axs2 = plt.subplots(1,2)
fig2.suptitle('Explicit Feature Maps (Nystrom)')
axs2[0].imshow(k.Phi)
axs2[0].set_title("Sample")
im2 = axs2[1].imshow(k.phi(x=oos))
axs2[1].set_title("OOS")
for ax in axs2.flat:
ax.set_xticks([])
ax.set_yticks([])
fig2.colorbar(im2, ax=axs2.ravel().tolist())
# kernel matrix from the explicit feature map
fig3, axs3 = plt.subplots(2,2)
fig3.suptitle('Kernel Matrices from the Explicit Feature Map (Nystrom)')
axs3[0,0].imshow(k.K, vmin=0, vmax=1)
axs3[0,0].set_title("Sample - Sample")
axs3[0,1].imshow(k.k(y=oos), vmin=0, vmax=1)
axs3[0,1].set_title("Sample - OOS")
axs3[1,0].imshow(k.k(x=oos), vmin=0, vmax=1)
axs3[1,0].set_title("OOS - Sample")
im3 = axs3[1,1].imshow(k.k(x=oos, y=oos), vmin=0, vmax=1)
axs3[1,1].set_title("OOS - OOS")
for ax in axs3.flat:
ax.set_xticks([])
ax.set_yticks([])
fig3.colorbar(im3, ax=axs3.ravel().tolist())
Effect of the dimension
On the example hereabove, al lot of features seem to contain few information. One may decide that keeping all the bases of the RKHS is unnecessary, and only keeping the ones corresponding to the most variance on the sample dataset. In the following example, only 6 dimensions are kept (few to accentuate the effect for demonstration purposes). This of course reduces the quality of the approximation.
import kerch
import numpy as np
from matplotlib import pyplot as plt
sample = np.sin(np.arange(0,15) / np.pi) + .1
oos = np.sin(np.arange(15,30) / np.pi) + .1
k_base = kerch.kernel.RBF(sample=sample)
k = kerch.kernel.Nystrom(base_kernel=k_base, dim=6)
# kernel matrix
fig1, axs1 = plt.subplots(2,2)
fig1.suptitle('Kernel Matrices of the Base Kernel (RBF)')
axs1[0,0].imshow(k_base.K, vmin=0, vmax=1)
axs1[0,0].set_title("Sample - Sample")
axs1[0,1].imshow(k_base.k(y=oos), vmin=0, vmax=1)
axs1[0,1].set_title("Sample - OOS")
axs1[1,0].imshow(k_base.k(x=oos), vmin=0, vmax=1)
axs1[1,0].set_title("OOS - Sample")
im1 = axs1[1,1].imshow(k_base.k(x=oos, y=oos), vmin=0, vmax=1)
axs1[1,1].set_title("OOS - OOS")
for ax in axs1.flat:
ax.set_xticks([])
ax.set_yticks([])
fig1.colorbar(im1, ax=axs1.ravel().tolist())
# explicit feature map
fig2, axs2 = plt.subplots(1,2)
fig2.suptitle('Explicit Feature Maps (Nystrom)')
axs2[0].imshow(k.Phi)
axs2[0].set_title("Sample")
im2 = axs2[1].imshow(k.phi(x=oos))
axs2[1].set_title("OOS")
for ax in axs2.flat:
ax.set_xticks([])
ax.set_yticks([])
fig2.colorbar(im2, ax=axs2.ravel().tolist())
# kernel matrix from the explicit feature map
fig3, axs3 = plt.subplots(2,2)
fig3.suptitle('Kernel Matrices from the Explicit Feature Map (Nystrom)')
axs3[0,0].imshow(k.K, vmin=0, vmax=1)
axs3[0,0].set_title("Sample - Sample")
axs3[0,1].imshow(k.k(y=oos), vmin=0, vmax=1)
axs3[0,1].set_title("Sample - OOS")
axs3[1,0].imshow(k.k(x=oos), vmin=0, vmax=1)
axs3[1,0].set_title("OOS - Sample")
im3 = axs3[1,1].imshow(k.k(x=oos, y=oos), vmin=0, vmax=1)
axs3[1,1].set_title("OOS - OOS")
for ax in axs3.flat:
ax.set_xticks([])
ax.set_yticks([])
fig3.colorbar(im3, ax=axs3.ravel().tolist())
Factory
The following lines are equivalent. First, an example with the default arguments:
k_base = kerch.kernel.RBF(sample=sample)
k = kerch.kernel.Nystrom(base_kernel=k_base)
k_base = kerch.kernel.RBF(sample=sample)
k = kerch.kernel.factory(kernel_type='nystrom', base_kernel=k_base)
k_base = kerch.kernel.factory(kernel_type='rbf')
k = kerch.kernel.Nystrom(base_kernel=k_base)
k = kerch.kernel.factory(kernel_type='nystrom', base_type='rbf', sample=sample)
And now with some arguments:
k_base = kerch.kernel.RBF(sample=sample, sigma=2)
k = kerch.kernel.Nystrom(base_kernel=k_base, dim=3)
k_base = kerch.kernel.RBF(sample=sample, sigma=2)
k = kerch.kernel.factory(kernel_type='nystrom', base_kernel=k_base, dim=3)
k_base = kerch.kernel.factory(kernel_type='rbf', sample=sample, sigma=2)
k = kerch.kernel.Nystrom(base_kernel=k_base, dim=3)
k = kerch.kernel.factory(kernel_type='nystrom', base_type='rbf', sample=sample, sigma=2, dim=3)