AlgoVision - A Framework for Differentiable Algorithms and Algorithmic Supervision

Overview

AlgoVision - A Framework for Differentiable Algorithms and Algorithmic Supervision

AlgoVision

This repository includes the official implementation of our NeurIPS 2021 Paper "Learning with Algorithmic Supervision via Continuous Relaxations" (Paper @ ArXiv, Video @ Youtube).

algovision is a Python 3.6+ and PyTorch 1.9.0+ based library for making algorithms differentiable. It can be installed via:

pip install algovision

Applications include smoothly integrating algorithms into neural networks for algorithmic supervision, problem-specific optimization within an algorithm, and whatever your imagination allows. As algovision relies on PyTorch it also supports CUDA, etc.

Check out the Documentation!

🌱 Intro

Deriving a loss from a smooth algorithm can be as easy as

from examples import get_bubble_sort
import torch

# Get an array (the first dimension is the batch dimension, which is always required)
array = torch.randn(1, 8, requires_grad=True)

bubble_sort = get_bubble_sort(beta=5)
result, loss = bubble_sort(array)

loss.backward()
print(array)
print(result)
print(array.grad)

Here, the loss is a sorting loss corresponding to the number of swaps in the bubble sort algorithm. But we can also define this algorithm from scratch:

from algovision import (
    Algorithm, Input, Output, Var, VarInt,                                          # core
    Let, LetInt, Print,                                                     # instructions
    Eq, NEq, LT, LEq, GT, GEq, CatProbEq, CosineSimilarity, IsTrue, IsFalse,  # conditions
    If, While, For,                                                   # control_structures
    Min, ArgMin, Max, ArgMax,                                                  # functions
)
import torch

bubble_sort = Algorithm(
    # Define the variables the input corresponds to
    Input('array'),
    # Declare and initialize all differentiable variables 
    Var('a',        torch.tensor(0.)),
    Var('b',        torch.tensor(0.)),
    Var('swapped',  torch.tensor(1.)),
    Var('loss',     torch.tensor(0.)),
    # Declare and initialize a hard integer variable (VarInt) for the control flow.
    # It can be defined in terms of a lambda expression. The required variables
    # are automatically inferred from the signature of the lambda expression.
    VarInt('n', lambda array: array.shape[1] - 1),
    # Start a relaxed While loop:
    While(IsTrue('swapped'),
        # Set `swapped` to 0 / False
        Let('swapped', 0),
        # Start an unrolled For loop. Corresponds to `for i in range(n):`
        For('i', 'n',
            # Set `a` to the `i`th element of `array`
            Let('a', 'array', ['i']),
            # Using an inplace lambda expression, we can include computations 
            # based on variables to obtain the element at position i+1. 
            Let('b', 'array', [lambda i: i+1]),
            # An If-Else statement with the condition a > b
            If(GT('a', 'b'),
               if_true=[
                   # Set the i+1 th element of array to a
                   Let('array', [lambda i: i + 1], 'a'),
                   # Set the i th element of array to b
                   Let('array', ['i'], 'b'),
                   # Set swapped to 1 / True
                   Let('swapped', 1.),
                   # Increment the loss by 1 using a lambda expression
                   Let('loss', lambda loss: loss + 1.),
               ]
           ),
        ),
        # Decrement the hard integer variable n by 1
        LetInt('n', lambda n: n-1),
    ),
    # Define what the algorithm should return
    Output('array'),
    Output('loss'),
    # Set the inverse temperature beta
    beta=5,
)

👾 Full Instruction Set

(click to expand)

The full set of modules is:

from algovision import (
    Algorithm, Input, Output, Var, VarInt,                                          # core
    Let, LetInt, Print,                                                     # instructions
    Eq, NEq, LT, LEq, GT, GEq, CatProbEq, CosineSimilarity, IsTrue, IsFalse,  # conditions
    If, While, For,                                                   # control_structures
    Min, ArgMin, Max, ArgMax,                                                  # functions
)

Algorithm is the main class, Input and Output define arguments and return values, Var defines differentiable variables and VarInt defines non-differentiable integer variables. Eq, LT, etc. are relaxed conditions for If and While, which are respective control structures. For bounded loops of fixed length that are unrolled. Let sets a differentiable variable, LetInt sets a hard integer variable. Note that hard integer variables should only be used if they are independent of the input values, but they may depend on the input shape (e.g., for reducing the number of iterations after each traversal of a For loop). Print prints for debug purposes. Min, ArgMin, Max, and ArgMax return the element-wise min/max/argmin/argmax of a list of tensors (of equal shape).

λ Lambda Expressions

Key to defining an algorithm are lambda expressions (see here for a reference). They allow defining anonymous functions and therefore allow expressing computations in-place. In most cases in algovision, it is possible to write a value in terms of a lambda expressions. The name of the used variable will be inferred from the signature of the expression. For example, lambda x: x**2 will take the variable named x and return the square of it at the location where the expression is written.

Let('z', lambda x, y: x**2 + y) corresponds to the regular line of code z = x**2 + y. This also allows inserting complex external functions including neural networks as part of the lambda expression. Assuming net is a neural networks, one can write Let('y', lambda x: net(x)) (corresponding to y = net(x)).

Let

Let is a very flexible instruction. The following table shows the use cases of it.

AlgoVision Python Description
Let('a', 'x') a = x Variable a is set to the value of variable x.
Let('a', lambda x: x**2) a = x**2 As soon as we compute anything on the right hand side of the equation, we need to write it as a lambda expression.
Let('a', 'array', ['i']) a = array[i] Indexing on the right hand requires an additional list parameter after the second argument.
Let('a', lambda array, i: array[:, i]) a = array[i] Equivalent to the row above: indexing can also be manually done inside of a lambda expression. Note that in this case, the batch dimension has to be written explicitly.
Let('a', 'array', ['i', lambda j: j+1]) a = array[i, j+1] Multiple indices and lambda expressions are also supported.
Let('a', 'array', [None, slice(0, None, 2)]) a = array[:, 0::2] None and slices are also supported.
Let('a', ['i'], 'x') a[i] = x Indexing can also be done on the left hand side of the equation.
Let('a', ['i'], 'x', ['j']) a[i] = x['j'] ...or on both sides.
Let(['a', 'b'], lamba x, y: (x+y, x-y)) a, b = x+y, x-y Multiple return values are supported.

In its most simple form Let obtains two arguments, a string naming the variable where the result is written, and the value that may be expressed via a lambda expression.

If the lambda expression returns multiple values, e.g., because a complex function is called and has two return values, the left argument can be a list of strings. That is, Let(['a', 'b'], lamba x, y: (x+y, x-y)) corresponds to a, b = x+y, x-y.

Let also supports indexing. This is denoted by an additional list argument after the left and/or the right argument. For example, Let('a', 'array', ['i']) corresponds to a = array[i], while Let('array', ['i'], 'b') corresponds to array[i] = b. Let('array', ['i'], 'array', ['j']) corresponding to array[i] = array[j] is also supported.

Note that indexing can also be expressed through lambda expressions. For example, Let('a', 'array', ['i']) is equivalent to Let('a', lambda array, i: array[:, i]). Note how in this case the batch dimension has to be explicitly taken into account ([:, ]). Relaxed indexing on the right-hand side is only supported through lambda expressions due to its complexity. Relaxed indexing on the left-hand side is supported if exactly one probability weight tensor is in the list (e.g., Let('array', [lambda x: get_weights(x)], 'a')).

LetInt only supports setting the variable to an integer (Python int) or list of integers (as well as the same type via lambda expressions). Note that hard integer variables should only be used if they are independent of the input values, but they may depend on the input shape.

If you need help implementing your differentiable algorithm, you may schedule an appointment. This will also help me improve the documentation and usability.

🧪 Experiments

The experiments can be found in the experiments folder. Additional experiments will be added soon.

🔬 Sorting Supervision

The sorting supervision experiment can be run with

python experiments/train_sort.py

or by checking out this Colab notebook.

📖 Citing

If you used our library, please cite it as

@inproceedings{petersen2021learning,
  title={{Learning with Algorithmic Supervision via Continuous Relaxations}},
  author={Petersen, Felix and Borgelt, Christian and Kuehne, Hilde and Deussen, Oliver},
  booktitle={Conference on Neural Information Processing Systems (NeurIPS)},
  year={2021}
}

📜 License

algovision is released under the MIT license. See LICENSE for additional details.

Owner
Felix Petersen
Researcher @ University of Konstanz
Felix Petersen
Learnable Motion Coherence for Correspondence Pruning

Learnable Motion Coherence for Correspondence Pruning Yuan Liu, Lingjie Liu, Cheng Lin, Zhen Dong, Wenping Wang Project Page Any questions or discussi

liuyuan 41 Nov 30, 2022
The official implementation of Autoregressive Image Generation using Residual Quantization (CVPR '22)

Autoregressive Image Generation using Residual Quantization (CVPR 2022) The official implementation of "Autoregressive Image Generation using Residual

Kakao Brain 529 Dec 30, 2022
PyTorch implementation of the paper Dynamic Token Normalization Improves Vision Transfromers.

Dynamic Token Normalization Improves Vision Transformers This is the PyTorch implementation of the paper Dynamic Token Normalization Improves Vision T

Wenqi Shao 20 Oct 09, 2022
Mae segmentation - Reproduction of semantic segmentation using masked autoencoder (mae)

ADE20k Semantic segmentation with MAE Getting started Install the mmsegmentation

97 Dec 17, 2022
SeMask: Semantically Masked Transformers for Semantic Segmentation.

SeMask: Semantically Masked Transformers Jitesh Jain, Anukriti Singh, Nikita Orlov, Zilong Huang, Jiachen Li, Steven Walton, Humphrey Shi This repo co

Picsart AI Research (PAIR) 186 Dec 30, 2022
For auto aligning, cropping, and scaling HR and LR images for training image based neural networks

ImgAlign For auto aligning, cropping, and scaling HR and LR images for training image based neural networks Usage Make sure OpenCV is installed, 'pip

15 Dec 04, 2022
Official Pytorch Implementation of 'Learning Action Completeness from Points for Weakly-supervised Temporal Action Localization' (ICCV-21 Oral)

Learning-Action-Completeness-from-Points Official Pytorch Implementation of 'Learning Action Completeness from Points for Weakly-supervised Temporal A

Pilhyeon Lee 67 Jan 03, 2023
Video Background Music Generation with Controllable Music Transformer (ACM MM 2021 Oral)

CMT Code for paper Video Background Music Generation with Controllable Music Transformer (ACM MM 2021 Best Paper Award) [Paper] [Site] Directory Struc

Zhaokai Wang 198 Dec 27, 2022
Pytorch tutorials for Neural Style transfert

PyTorch Tutorials This tutorial is no longer maintained. Please use the official version: https://pytorch.org/tutorials/advanced/neural_style_tutorial

Alexis David Jacq 135 Jun 26, 2022
Official repository for Natural Image Matting via Guided Contextual Attention

GCA-Matting: Natural Image Matting via Guided Contextual Attention The source codes and models of Natural Image Matting via Guided Contextual Attentio

Li Yaoyi 349 Dec 26, 2022
Ï€-GAN: Periodic Implicit Generative Adversarial Networks for 3D-Aware Image Synthesis

Ï€-GAN: Periodic Implicit Generative Adversarial Networks for 3D-Aware Image Synthesis Project Page | Paper | Data Eric Ryan Chan*, Marco Monteiro*, Pe

375 Dec 31, 2022
Paddle Graph Learning (PGL) is an efficient and flexible graph learning framework based on PaddlePaddle

DOC | Quick Start | 中文 Breaking News !! 🔥 🔥 🔥 OGB-LSC KDD CUP 2021 winners announced!! (2021.06.17) Super excited to announce our PGL team won TWO

1.5k Jan 06, 2023
PyTorch implementation of Weak-shot Fine-grained Classification via Similarity Transfer

SimTrans-Weak-Shot-Classification This repository contains the official PyTorch implementation of the following paper: Weak-shot Fine-grained Classifi

BCMI 60 Dec 02, 2022
This is the official implementation code repository of Underwater Light Field Retention : Neural Rendering for Underwater Imaging (Accepted by CVPR Workshop2022 NTIRE)

Underwater Light Field Retention : Neural Rendering for Underwater Imaging (UWNR) (Accepted by CVPR Workshop2022 NTIRE) Authors: Tian Ye†, Sixiang Che

jmucsx 17 Dec 14, 2022
FCA: Learning a 3D Full-coverage Vehicle Camouflage for Multi-view Physical Adversarial Attack

FCA: Learning a 3D Full-coverage Vehicle Camouflage for Multi-view Physical Adversarial Attack Case study of the FCA. The code can be find in FCA. Cas

IDRL 21 Dec 15, 2022
Spiking Neural Network for Computer Vision using SpikingJelly framework and Pytorch-Lightning

Spiking Neural Network for Computer Vision using SpikingJelly framework and Pytorch-Lightning

Sami BARCHID 2 Oct 20, 2022
GLANet - The code for Global and Local Alignment Networks for Unpaired Image-to-Image Translation arxiv

GLANet The code for Global and Local Alignment Networks for Unpaired Image-to-Image Translation arxiv Framework: visualization results: Getting Starte

stanley 29 Dec 14, 2022
Experiment about Deep Person Re-identification with EfficientNet-v2

We evaluated the baseline with Resnet50 and Efficienet-v2 without using pretrained models. Also Resnet50-IBN-A and Efficientnet-v2 using pretrained on ImageNet. We used two datasets: Market-1501 and

lan.nguyen2k 77 Jan 03, 2023
Supplementary code for the experiments described in the 2021 ISMIR submission: Leveraging Hierarchical Structures for Few Shot Musical Instrument Recognition.

Music Trees Supplementary code for the experiments described in the 2021 ISMIR submission: Leveraging Hierarchical Structures for Few Shot Musical Ins

Hugo Flores García 32 Nov 22, 2022
Accepted at ICCV-2021: Workshop on Computer Vision for Automated Medical Diagnosis (CVAMD)

Is it Time to Replace CNNs with Transformers for Medical Images? Accepted at ICCV-2021: Workshop on Computer Vision for Automated Medical Diagnosis (C

Christos Matsoukas 80 Dec 27, 2022