GitHub

DataDrivenSparse

DataDrivenSparse provides a universal framework to infer system of equations using sparse regression. Assume the system:

\[y_{i} = f(x_{i}, p, t_i, u_{i})\]

Then might be able to express the unknown function $f$ as a linear combination of basis elements $\varphi_i : \mathbb R^{n_x} \times \mathbb R^{n_p} \times \mathbb R \times \mathbb R^{n_u} \mapsto \mathbb R$ .

\[y_i = \sum_{j=1}^k \xi_k ~ \varphi_k\left(x_i, p, t_i, u_i \right)\]

And simply solve the least squares problem

\[\Xi' = \min_{\Xi} \lVert Y - \Xi \varPhi \rVert_2^2\]

In the simplest case, we could use a Taylor expansion. However, if we want interpretable results, we need a key ingredient: sparsity! So, instead we aim to solve the problem

\[\Xi' = \min_{\Xi} \lVert\Xi \rVert_0 \\ \text{s.t.} \qquad \Xi \varPhi = Y\]

In its original version or via sufficient relaxation of the $L_0$ norm.

Similarly, implicit problems of the form

\[f(y_i, x_i, p, t_i, u_i) = 0\]

can be solved using an ImplicitOptimizer. Similar to the formulation above, we try to solve the corresponding optimization problem

\[\Xi' = \min_{\Xi} \lVert\Xi \rVert_0 \\ \text{s.t.} \qquad \Xi \varPhi_y = 0\]

Where the matrix of evaluated basis elements $\varPhi_y \in \mathbb R^{\lvert \varphi \rvert} \times \mathbb R^{m}$ now may also contain basis functions which are dependent on the target variables $y \in \mathbb R^{n_y}$.

Tuning parameters for sparse regression

The algorithms used by DataDrivenSparse are sensible to the tuning of the hyperparameters! These are problem and coefficient specific, e.g. depend on the data and the unknown equations. While the examples used here are designed to work well, the used settings are not guaranteed to lead to success on other problems. User who want to explore the space of possible hyperparameters further might be interested in using Hyperopt.jl.

Algorithms

DataDrivenSparse.STLSQ — Type
struct STLSQ{T<:Union{Number, AbstractVector}, R<:Number} <: DataDrivenSparse.AbstractSparseRegressionAlgorithm

STLSQ is taken from the original paper on SINDY and implements a sequentially thresholded least squares iteration. λ is the threshold of the iteration. It is based upon this Matlab implementation. It solves the following problem

\[\argmin_{x} \frac{1}{2} \| Ax-b\|_2 + \rho \|x\|_2\]

with the additional constraint

\[\lvert x_i \rvert > \lambda\]

If the parameter ρ > 0, ridge regression will be performed using the normal equations of the corresponding regression problem.

Fields

  • thresholds: Sparsity threshold

  • rho: Ridge regression parameter

Example

opt = STLSQ()
opt = STLSQ(1e-1)
opt = STLSQ(1e-1, 1.0) # Set rho to 1.0
opt = STLSQ(Float32[1e-2; 1e-1])

Note

This was formally STRRidge and has been renamed.

source
DataDrivenSparse.ADMM — Type
mutable struct ADMM{T, R<:Number} <: DataDrivenSparse.AbstractSparseRegressionAlgorithm

ADMM is an implementation of Lasso using the alternating direction methods of multipliers, and loosely based on this implementation. It solves the following problem

\[\argmin_{x} \frac{1}{2} \| Ax-b\|_2 + \lambda \|x\|_1\]

Fields

  • thresholds: Sparsity threshold parameter

  • rho: Augmented Lagrangian parameter

Example

opt = ADMM()
opt = ADMM(1e-1, 2.0)
source
DataDrivenSparse.SR3 — Type
mutable struct SR3{T, V, P<:DataDrivenSparse.AbstractProximalOperator} <: DataDrivenSparse.AbstractSparseRegressionAlgorithm

SR3 is an optimizer framework introduced by Zheng et al., 2018 and used within Champion et al., 2019. SR3 contains a sparsification parameter λ, a relaxation ν. It solves the following problem

\[\argmin_{x, w} \frac{1}{2} \| Ax-b\|_2 + \lambda R(w) + \frac{\nu}{2}\|x-w\|_2\]

Where R is a proximal operator, and the result is given by w.

Fields

  • thresholds: Sparsity threshold

  • nu: Relaxation parameter

  • proximal: Proximal operator

Example

opt = SR3()
opt = SR3(1e-2)
opt = SR3(1e-3, 1.0)
opt = SR3(1e-3, 1.0, SoftThreshold())

Note

Opposed to the original formulation, we use nu as a relaxation parameter, as given in Champion et al., 2019. In the standard case of hard thresholding the sparsity is interpreted as λ = threshold^2 / 2, otherwise λ = threshold.

source
DataDrivenSparse.ImplicitOptimizer — Type
mutable struct ImplicitOptimizer{T<:DataDrivenSparse.AbstractSparseRegressionAlgorithm} <: DataDrivenSparse.AbstractSparseRegressionAlgorithm

Optimizer for finding a sparse implicit relationship via alternating the left-hand side of the problem and solving the explicit problem, as introduced here.

\[\argmin_{x} \|x\|_0 ~s.t.~Ax= 0\]

Fields

  • optimizer: Explicit Optimizer

Example

ImplicitOptimizer(STLSQ())
ImplicitOptimizer(0.1f0, ADMM)
source

Proximal Operators

DataDrivenSparse.ClippedAbsoluteDeviation — Type
struct ClippedAbsoluteDeviation{T} <: DataDrivenSparse.AbstractProximalOperator

Proximal operator, which implements the (smoothly) clipped absolute deviation operator.

abs(x) > ρ ? x : sign(x) * max(abs(x) - λ, 0)

Where ρ = 5λ per default.

#Fields

  • ρ: Upper threshold

Example

opt = ClippedAbsoluteDeviation()
opt = ClippedAbsoluteDeviation(1e-1)

See by Zheng et al., 2018.

source