Gradient Ascent

Labels / Tags

  • Preprocessing
  • AnyType
  • NumericalVector
  • BinaryVector
  • MixedVector
  • Monovariate temporal series
  • Multivariate temporal series

Principle

Gradient ascent consists in shifting elements toward local modes from another dataset. By mode we mean here the densest space point, i.e the finite area within there exists the highest number of elements.

Let input be the input collection of values and ref be the referential dataset toward which input’s elements will converge toward its modes. It is good to understand that the ref data will remains the same during the whole process. Often ref dataset is input itself, our current implementation follows this logic.

It is an iterative algorithm where at each step each input value is shifted to an updated state by applying a kernel on it. The kernel inputs are the value to be shifted itself and the ref, from then it will computes and returns the updated value. Once it is done for every input values, the whole data have been shifted, it will then be used for the next iteration, instead of input, along ref. The process stops when values shift is under a threshold $\epsilon$.

An critical part of this algorithm is the used kernel which apply the values shift, many exist and implemented ones are describe in Paramters section.

but current implementation use de $K$NN kernel. It consist to apply the $K$NN for the query on ref dataset, then an aggration of found $K$NN is apply to returns the updated value.

Scalability

Computationa complexity is in $O(n^2)$.

Input

A collection of Any data type who has an associated distance metrics.

Parameters

1 : kernel, defines how values are shifted.

$K$NN kernel

It consist to apply the $K$NN for the query on ref dataset, then an aggration of found $K$NN is apply to returns the updated value.

Gausian kernl

Flat kernel

Sigmoid kernel

Ouput

The GradientAscentModel is the collection of shifted input’s values, for each observation the sum of every shift made during algorithm running is also stored.

Associated visualization

  • 2/3D numerical datasets

Practical strategies

Gradiend ascent can be used to improve clustering algorithms. It can be combined with density based algorithm because after the input dataset has converged, its observations will be much more closer than their local modes making easier the clustering step. The application with the $K$Means can also gives good results.

It also shifts points outside clusters toward them.

Business case

Usage

Initiate K-Means like.