Differentiable implementation of common computer science algorithms.
Trying out the Tensorflow 2.0 Gradient tape during the pandemic
These algorithms can be thought as overengineered loss functions. They are meant to be used in conjuction with deep learning networks. However, unlike loss function, they dont need to be attached to the end of the network. As demonstrated in the Bubble Sort example, it can also be interleaved with the graph of the network.
All algorithms in this repository follow these rules
- It must be deterministic in forward pass - Although, these are intended to be used in conjunction with deep neural networks, there must be a very clear boundary of separation of code with learnable parameters and code without learnable parameters. Therefore no stochasticity is allowed, either during run time or during the generation of code which will be executed at runtime.
- It must be lossless in forward pass - The algorithms must behave identically to classical algorithms when the inputs are discrete. When non-discrete data points are passed, it should produce well behaved, interpretable and continious output.
- It must have well definied gradients in backward pass - The algorithms should have well defined gradients with at least one of its inputs.
- Bubble Sort - Differentiable implementation of bubble sort with configurable (learnable) comparator function
- Boolean Satisfiability - Solving CNF boolean SAT with gradient descent
- Subset Sum - Solving Subset Sum with gradient descent
- Higher Order Functions - Demonstrating gradient descent through higher order functions
- Differentiable indexed arrays - Listing strategies to implement array indexing with gradients defined for both input and index.
- Stacks - A basic implementation of differentiable stacks
- Differentiable Indirection - Implementation of circular linked lists with differentiable indexing
- Custom gradient - Demonstration of tensorflow custom gradients