Shark machine learning library
Installation
Tutorials
Benchmarks
Documentation
Quick references
Class list
Global functions
include
shark
Algorithms
ApproximateKernelExpansion.h
Go to the documentation of this file.
1
//===========================================================================
2
/*!
3
*
4
*
5
* \brief The k-means clustering algorithm.
6
*
7
*
8
*
9
* \author T. Glasmachers
10
* \date 2011
11
*
12
*
13
* \par Copyright 1995-2017 Shark Development Team
14
*
15
* <BR><HR>
16
* This file is part of Shark.
17
* <https://shark-ml.github.io/Shark/>
18
*
19
* Shark is free software: you can redistribute it and/or modify
20
* it under the terms of the GNU Lesser General Public License as published
21
* by the Free Software Foundation, either version 3 of the License, or
22
* (at your option) any later version.
23
*
24
* Shark is distributed in the hope that it will be useful,
25
* but WITHOUT ANY WARRANTY; without even the implied warranty of
26
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
27
* GNU Lesser General Public License for more details.
28
*
29
* You should have received a copy of the GNU Lesser General Public License
30
* along with Shark. If not, see <http://www.gnu.org/licenses/>.
31
*
32
*/
33
//===========================================================================
34
35
36
#ifndef SHARK_ALGORITHMS_APPROXIMATE_KERNEL_EXPANSION_H
37
#define SHARK_ALGORITHMS_APPROXIMATE_KERNEL_EXPANSION_H
38
39
#include <
shark/Core/DLLSupport.h
>
40
#include <
shark/Core/Random.h
>
41
#include <
shark/Models/Kernels/KernelExpansion.h
>
42
namespace
shark
{
43
/// \brief Approximates a kernel expansion by a smaller one using an optimized basis.
44
///
45
/// often, a kernel expansion can be represented much more compactly when the points defining the basis of the kernel
46
/// expansion are not fixed. The resulting kernel expansion can be evaluated much quicker than the original
47
/// when k is small compared to the number of the nonzero elements in the weight vector of the supplied kernel expansion.
48
///
49
/// Given a kernel expansion with weight matrix alpha and Basis B of size m, finds a new weight matrix beta and Basis Z with k vectors
50
/// so that the difference of the resulting decision vectors is small in the RKHS defined by the supplied kernel.
51
///
52
/// The algorithm proceeds by first performing a kMeans clustering as a good initialization. This initial guess is then optimized
53
/// by finding the closest weight vector to the original vector representable by the basis. Using this estimate, the basis
54
/// can then be optimized.
55
///
56
/// The supplied kernel must be dereferentiable wrt its input parameters which excludes all kernels not defined on RealVector
57
///
58
/// The algorithms is O(k^3 + k m) in each iteration.
59
///
60
/// \param rng the Rng used for the kMeans clustering
61
/// \param model the kernel expansion to approximate
62
/// \param k the number of basis vectors to be used by the approximation
63
/// \param precision target precision of the gradient to be reached during optimization
64
SHARK_EXPORT_SYMBOL
KernelExpansion<RealVector>
approximateKernelExpansion
(
65
random::rng_type& rng,
66
KernelExpansion<RealVector>
const
& model,
67
std::size_t k,
68
double
precision = 1.e-8
69
);
70
71
}
// namespace shark
72
#endif