Edit on GitHub

InducingPoints

InducingPoints.jl aims at providing an easy way to select inducing points locations for Sparse Gaussian Processes both in an online and offline setting.

The point selection is splitted in the online and offline settings.

All methods inherit from AbstractInducingPoints which acts as a Vector of Vectors, making it especially compatible with KernelFunctions.jl

Offline Inducing Points Selection

Given a set of features X you can get a point selection by calling

    Z = KmeansIP(X, 10, obsdim=1)

The Offline options are:

  • KmeansIP : use the k-means algorithm to select centroids minimizing the square distance with the dataset. The seeding is done via k-means++. Note that the inducing points are not going to be a subset of the data
  • kDPP : sample from a k-Determinantal Point Process to select k points. Z will be a subset of X
  • StdDPP : sample from a standard Determinantal Point Process. The number of inducing points is not fixed here. Z will be a subset of X
  • RandomSubset : sample randomly k points from the data set uniformly.
  • GreedyIP : Will select a subset of X which maximizes the ELBO (in a stochastic way)

Online Inducing Points Selection

Online selection is a bit more involved.

Z = OIPS()
Z = init(x_1, args)
for x in eachbatch(X)
    update!(Z, x)
end

After the first instance is created init will return a new instance when seeing the first batch of data with the right parametrization. After one can simply call update! to update the vectors in place.

The Online options are:

  • OIPS : A method based on distance between inducing points and data
  • UniformGrid : A regularly-spaced grid whom edges are adapted given the data
  • SeqDPP : Sequential Determinantal Point Processes, subsets are regularly sampled from the new data batches conditionned on the existing inducing points.
  • StreamKmeans : An online version of k-means.
  • Webscale : Another online version of k-means

Index

API

InducingPoints.GreedyIP — Type
GreedyIP(X::AbstractVector, m::Int, y, s, kernel, σ²)
GreedyIP(X::AbstractMatrix, m::Int, y, s, kernel, σ²; obsdim = 1)
  • X is the input data
  • m is the desired number of inducing points
  • y is the output data
  • s is the minibatch size on which to select a new inducing point
  • σ² is the likelihood noise

Greedy approach first proposed by Titsias[1]. Algorithm loops over minibatches of data and select the best ELBO improvement.

[1] Titsias, M. Variational Learning of Inducing Variables in Sparse Gaussian Processes. Aistats 5, 567–574 (2009).

source
InducingPoints.KmeansIP — Type

KMeansIP(X::AbstractMatrix, m; obsdim = 1, nMarkov = 10, weights = nothing, tol = 1e-3)

k-Means [1] initialization on the data X taking m inducing points. The seeding is computed via [2], nMarkov gives the number of MCMC steps for the seeding. Additionally weights can be attributed to each data point

[1] Arthur, D. & Vassilvitskii, S. k-means++: The advantages of careful seeding. in Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms 1027–1035 (Society for Industrial and Applied Mathematics, 2007). [2] Bachem, O., Lucic, M., Hassani, S. H. & Krause, A. Fast and Provably Good Seedings for k-Means. Advances in Neural Information Processing Systems 29 55–63 (2016) doi:10.1109/tmtt.2005.863818.

source
InducingPoints.OIPS — Type
OIPS(ρ_accept=0.8, opt= ADAM(0.001); η = 0.95, kmax = Inf, kmin = 10, ρ_remove = Inf )
OIPS(kmax, η = 0.98, kmin = 10)

Online Inducing Points Selection. Method from the paper include reference here.

source
InducingPoints.StdDPP — Type
StdDPP(X::AbstractMatrix, kernel::Kernel; obsdim::Int = 1)
StdDPP(X::AbstractVector, kernel::Kernel)

Standard DPP (Determinantal Point Process) sampling given kernel. The size of the returned Z is variable

source
InducingPoints.StreamKmeans — Type
StreamKmeans(k_target::Int)

Online clustering algorithm [1] to select inducing points in a streaming setting. Reference : [1] Liberty, E., Sriharsha, R. & Sviridenko, M. An Algorithm for Online K-Means Clustering. arXiv:1412.5721 cs.

source
InducingPoints.UniGrid — Type
UniGrid(K::Int)

where K is the number of points on each dimension Adaptive uniform grid based on [1]

[1] Moreno-Muñoz, P., Artés-Rodríguez, A. & Álvarez, M. A. Continual Multi-task Gaussian Processes. (2019).

source
InducingPoints.UniformSampling — Type
UniformSampling(X::AbstractVector, m::Int; weights)
UniformSampling(X::AbstractMatrix, m::int; weights, obsdim = 1)

Uniform sampling of a subset of the data.

source
InducingPoints.Webscale — Type
Webscale(k::Int)

Online k-means algorithm based on [1].

[1] Sculley, D. Web-scale k-means clustering. in Proceedings of the 19th international conference on World wide web - WWW ’10 1177 (ACM Press, 2010). doi:10.1145/1772690.1772862.

source
InducingPoints.kDPP — Type
kDPP(X::AbstractVector, m::Int, kernel::Kernel)
kDPP(X::AbstractMatrix, m::Int, kernel::Kernel; obsdim::Int = 1)

k-DPP (Determinantal Point Process) will return a subset of X of size m, according to DPP probability

source