Pratical machine learning: Scala implementation of Function Vectors

Sunday, February 26, 2017

Scala implementation of Function Vectors

Target audience: Intermediate

Estimated reading time: 15'

This post describes the definition and an implementation of the functions vector.

Overview

Space of functions are commonly used in machine learning (kernel functions) and differential geometry (tensors and manifolds).The most common technique to create a functions space is to define the space as a category and assign monadic operations to it.
This post discusses an alternative, less elaborate approach to define a functions space as a container. The key operator on function is the composition as defined in the Function1[-T, +R] class:

def andThen[A](g: (R) ⇒ A): (T) ⇒ A def compose[A](g: (A) ⇒ T): (A) ⇒ R
Let's use andThen as the basic block to build our functions space.

.. andThen

The andThen is a member method of some of the Scala standard library collections such as List and HashMap.

val xsInt = List[Int](4, 0, 9, 56, 11)
xsInt.andThen((n: Int) => n*n).mkString(",")
   // print 16,0,81,3136,121

As mentioned in the introduction, the Function1 implements andThen to compose two functions as this o otherFunction where the o composition operator is defined as

     f o g:  (t: T) => f(g(t))

The method is implemented using the andThen method

val fg = Math.sin andThen (x: Double) => x*x
Console.println(s"fg(5.0): ${fg(5.0)}")

Function vectors space

A function space is defined as a space of function vectors, similar to Euclidean space for which variables is defined as a vector or array of real values. A function vector is commonly used to convert a vector or tensor from one space to another non-euclidean space by transforming the original coordinates (x,y,z) to another coordinates in a different space (f(x,y,z), ..) using the function vector.

Let's implement the functions vector as the class FunctionVector (line 1) and its two most important method, composition (line 2) and the dot product (tensor product) (line 3).

class FunctionVector[T](fVec: List[T=>T]) {
  def andThen(op: T => T): T=>T
  def dot(opVec: List[T=>T])(implicit num: Numeric[T]): T => T
  def map(op: T => T): List[T=>T]
   ...
}

The dot product is defined as the product of two vectors functions. For example in a function vector spaces of dimension 3, v(f,g,h) and v'(f',g',h')
dot: (x,y,z) -> f o f'(x,y,z) + g o g'(x,y,z) + h o h'(x,y,z)
The method andThen composes this function vector with a function op and generates a 'cumulative' composed function as
f o g o h o op
The iteration along the function vector is implemented as a tail recursion. The method relies on the List[T=>T].andThen method (line 6).

def andThen(g: T => T): T => T = {

  @scala.annotation.tailrec
  def andThen(xsf: List[T=>T])(op: T => T): T => T =
   if(xsf.size == 0) op 
   else andThen(xsf.drop(1))(xsf.head andThen op)
   
  andThen(fVec.reverse)(op)
}

The 'dot' product takes another function vector of same size as argument. The two vectors are zipped to generate a Iterable[T=>T] vector of composed function elements using a map. Finally the resulting dot function is computed by generating a new function with summation of the elements of the composed functions vector. The summation requires the instance of Numeric to be declared as an implicit argument.

def dot(gVec: List[T=>T])(implicit num: Numeric[T]): T => T = { 
 
  val composed = fVec.zip(opVec).map(fg => fg._1.andThen(fg._2))
  (t: T) => composed.map( _(t)).sum
}

Contrary to the andThen method, the map convert a function vector to another function vector by applying a natural transformation.

  // return List[T => T]
def map(op: T => T) = fVec.map( _ andThen op)

Finally, the definition of the dot product can be extended to any aggregation method aggr

def dot(
  opVec: List[T=>T], 
  aggr: (T =>T, T=>T) =>  (T=>T)): T => T = {
  
  val composed = fVec.zip(opVec).map( 
    fg => fg._1 andThen fg._2
  )
  
  (t: T) => composed./:((t: T) => t)(
    (h,f) =>aggr(h,f)
  )(t)
}

The aggregation method passed as argument of the dot method (line 3) is a simplified version of the aggregation defined in the Scala standard library. It is used to implement the dot method on the composed functions vectors (line 10).
Let's apply our new found knowledge about FunctionVector:

val functionsList = List[Function1[Double,Double]](
   Math.sin, Math.sqrt
)
   
val vec = new FunctionVector[Double](functionsList)
val output1 = vec.andThen((x: Double) => x*x)
val opVec = List[Double=>Double](
 (x: Double)=> x+ 1.0, 
 (x: Double)=> Math.exp(-x)
)
val output2 = vec.dot(opVec)

For evaluating our Function vectors classes, we used a list of functions of type Double => Double (line 1): a sinusoidal and a square root functions (line 2).
Once the function vector is created (line 5), it is available to be composed with the existing list of functions of the class FunctionVector (lines 5 and 6).

References
Scala By Example - M. Odersky - June 2014