Infinitely-differentiable C++; conditionals, loops, recursion and all things C++
###Abstract We provide an illustrative implementation of an analytic, infinitely-differentiable machine, implementing infinitely-differentiable programming spaces and operators acting upon them, as constructed in the paper Operational calculus on programming spaces and generalized tensor networks. Implementation closely follows theorems and derivations of the paper, intended as an educational guide.
This is the openSource version.
###Theory
From abstract of the paper Operational calculus on programming spaces and generalized tensor networks in which the theory is derived by Žiga Sajovic and Martin Vuk:
In this paper, we develop the theory of analytic virtual machines, that implement analytic programming spaces and operators acting upon them. Such a machine fully integrates control structures, reataining the expressive freedom of algorithmic control flow.
#Operational calculus on programming spaces and generalized tensor networks
###Abstract
In this paper, we develop the theory of analytic virtual machines, that implement analytic programming spaces and operators acting upon them.
A paper explaining implementation of this theory is avaliable /paper/dCpp.pdf.
The paper Operational calculus on programming spaces and generalized tensor networks , containing construction of the theory will soon be available on arXiv.
###Usage By employing analytic virtual machines, we can construct analytic procedures, viewing algorithms in a new light. One can start incorporating variable parameters into algorithm design, revealing the true nature of hyper-parameters often used in practice.
###Tutorial As most programmers face the need of differentiability through machine learning, we use the concept a Recurrent neural network employing logistic regression with softmax normalization as a vessel for this tutorial. We demostrate, how it is simply constructed using algorithmic control flow and reccursion, by employing dCpp.
First we include the necessities
#include <iostream>
#include <dCpp.h>
#include <vector>
We initialize a n-differentiable programming space (order is arbitrary here)
using namespace dCpp;
int n_differentiable=2;
initSpace(n_differentiable);
We will need the folowing functions
####Maps contained in the function algebra over var
By coding sigmoid(x), we will learn about creating differentiable maps, constructable using the differentiable programming space dCpp and the algebra of the virtual memory var.
var sigmoidMap(const var&v){return 1/(1+exp(-1*v));};
We test it out and and compute it on a simple example.
// set inputs
double x=4;
double y=2;
// set weights
var w_1(0.4);
var w_2(0.6);
// initialize weights as twice differentiable variables
dCpp::init(w_1);
dCpp::init(w_2);
// now we use sigmoid map as a differentiable map
var f=sigmoidMap(w_1*x+w_2*y);
Accessing the derivatives is done by calling d(var* w) function of the class var. It returns the derivative with respect to the variable w, as a var variable.
// df/dw_1
std::cout<<"df/dw_1 = "<<f.d(&w_1).id<<std::endl;
// df/dw_2
std::cout<<"df/dw_2 = "<<f.d(&w_2).id<<std::endl;
// df/dw_1dw_1
std::cout<<"df/dw_1dw_1 = "<<f.d(&w_1).d(&w_1).id<<std::endl;
// df/dw_1dw_2
std::cout<<"df/dw_1dw_2 = "<<f.d(&w_1).d(&w_2).id<<std::endl;
// df/dw_2dw_1
std::cout<<"df/dw_2dw_1 = "<<f.d(&w_2).d(&w_1).id<<std::endl;
// df/dw_2dw_2
std::cout<<"df/dw_2dw_2 = "<<f.d(&w_2).d(&w_2).id<<std::endl;
####Operator dTau
Similarly, we could have used the operator tau by coding , which allows one to create it's own elements of the differentiable programming space dCpp, returning a differentiable variable var. The operator tau is initialized by a double-->double map representing the desired function, and a var-->var map representing its derivative. Lets take a closer look, by creating a differentiable map log:var-->var.
//coding the derivative
var log_primitive(const var&v){return 1/v;};
The map is created by providing the operator with the two maps
//operator returning a differentiable map
tau log(std::log,log_primitive);
The map is now ready to use
// set variables
var x(10);
var y(20);
// initialize x and y as a differentiable variables
dCpp::init(x);
dCpp::init(y);
// now we use log as a differentiable map
var f=log(((x^2)-(y^0.23))^2.1);
Again, we display all first and second derivatives
// df/dx
std::cout<<"df/dx = "<<f.d(&x).id<<std::endl;
// df/dy
std::cout<<"df/dy = "<<f.d(&y).id<<std::endl;
// df/dxdx
std::cout<<"df/dxdx = "<<f.d(&x).d(&x).id<<std::endl;
// df/dxdy
std::cout<<"df/dxdy = "<<f.d(&x).d(&y).id<<std::endl;
// df/dydx
std::cout<<"df/dydx = "<<f.d(&y).d(&x).id<<std::endl;
// df/dydy
std::cout<<"df/dydy = "<<f.d(&y).d(&y).id<<std::endl;
####Integrating control structures
With dTau explained, we turn to coding the softmax normalization, we reveal how analytic virtual machines fully integrate control structures.
//simply code the map existing in the programming space dCpp
//and the belonging algebra
std::vector<var> softmax(const std::vector<var>& V){
std::vector<var> out;
var sum(0);
init(sum);
for(var v:V){
sum=sum+exp(v);
}
for(var v:V){
out.push_back(exp(v)/sum);
}
return out;
}
We test it, by inititalizing a four-differentiable programming space and displaying all derivatives.
// initiaize Virtual memory of fourth order
initSpace(4);
//get a vector of variables
int size=2;
std::vector<var> vars;
for(int i=1;i<=size;i++){
var tmp=var(i);
init(tmp);
vars.push_back(tmp);
}
// use the softmax function
std::vector<var> f=softmax(vars);
// display derivatives of all four orders
// of one of the components
f[1].print();
####Recurrent neural network
Assume existence of functions vecSum, matVecProd, genRandVec and forAll written in a similar fashion. Thus, we have all the tools needed to build a recursive layer. It will consist of two layers, mapping a 2-vector to a 2-vector. Output of the second layer will be recursively connected to the input of the next recursive layer.
For brevity, we denote std::vector<std::vector > by mat and std::vector by vec.
vec recursionNet(vec input, mat weights[2],vec bias[], int depth){
if(depth==0){
return softmax(input);
}
else{
vec firstOut;
//matrix vector multiplication
firstOut=matVecProd(weights[0],input);
firstOut=vecSum(firstOut,bias[0]);
forAll(firstOut,sigmoid);
vec secondOut;
secondOut=matVecProd(weights[1],firstOut);
secondOut=vecSum(secondOut,bias[1]);
forAll(secondOut,sigmoid);
return recursionNet(secondOut,weights, bias,depth-1);
}
}
Now only some initialization of weights is needed and the network can be used, exactly like any other function would, with the exception, that this function is n-differentiable.
vec output = recursionNet(input,weights[],bias[], depth);
for(var v:output)v.print();
to display derivatives of all orders, up to n by which the space has been initialized.
###External libraries
Usage with external libraries written in generic paradigm is demonstrated on the example of Eigen. We will code a perceptron with sigmoid activations, followed by softmax normalization. We will use dCpp provided mappings in the dEigen header.
#include <iostream>
#include <dCpp.h>
#include <dEigen.h>
using namespace std;
using namespace dCpp;
//create a softmax function
template <typename Derived>
void softmax(Eigen::MatrixBase<Derived>& matrix){
//maps each element of the matrix by y=e^x;
dCpp::map_by_element(matrix,&dCpp::exp);
//sums the elements of the matrix using Eigens function
var tmp=matrix.sum();
//divides each element by the sum
for (size_t i=0, nRows=matrix.rows(), nCols=matrix.cols(); i<nCols; ++i)
for (size_t j=0; j<nRows; ++j)matrix(j,i)=matrix(j,i)/tmp;
}
void dEigenExample(){
// space is n-times differentiable
int n=2;
// initialize the space
dCpp::initSpace(n);
// Matrix holding the inputs (imgSizeX1 vector)
const int inputSize=28;
Eigen::Matrix<var,1,inputSize>input=Eigen::Matrix<var,1,inputSize>::Random(1,inputSize);
dCpp::init(input);
// number of outputs of the layer
const int outputSize=1;
// matrix of weights on the first level (imgSizeXnumOfOutOnFirstLevel)
Eigen::Matrix<var,inputSize,outputSize>firstLayerVars=Eigen::Matrix<var,inputSize,outputSize>::Random(inputSize,outputSize);
// initializing weights
dCpp::init(firstLayerVars);
// mapping of the first layer
Eigen::Matrix<var,outputSize,1>firstLayerOutput=input*firstLayerVars;
// add bias
Eigen::Matrix<var,outputSize,1>bias=Eigen::Matrix<var,outputSize,1>::Random(outputSize,1);
// initialize bias
dCpp::init(bias);
firstLayerOutput=bias+firstLayerOutput;
// apply sigmoid we coded earlier
dCpp::map_by_element(firstLayerOutput,sigmoid);
// apply sofmax layer
softmax(firstLayerOutput);
// display the first output layer and its (1-n)-th derivatives
for (size_t i=0, nRows=firstLayerOutput.rows(), nCols=firstLayerOutput.cols(); i<nCols; ++i){
for (size_t j=0; j<nRows; ++j) firstLayerOutput(j,i).print();
cout<<endl;
}
}
dC++ by Žiga Sajovic is licensed under a Creative Commons Attribution 4.0 International License.