[GSoC] Automatic Differentiation in the Faust Compiler

[hatchjaw]

Google Summer of Code: Automatic Differentiation in the Faust Compiler

The goal of this project was to add automatic differentiation functionality to the Faust compiler as a signal stage transformation, and create a Faust architecture file for carrying out gradient descent based on automatically differentiated Faust DSP instances.

Support for differentiable Faust algorithms would facilitate gradient computation, suitable for application in machine learning problems, for all available Faust backends.

Deliverables

The following headline contributions have been made:

• Derivative implementations for the majority of Faust's primitive operators, in the SignalAutoDifferentiate class and, for math.h-equivalent primitives, descendents of the xtended class.
• An architecture file, autodiff.cpp, compilable to an executable for computing gradient descent.
  • A selection of example differentiable and ground-truth Faust .dsp files for exploring and testing autodiff functionality and gradient descent.
  • A python script for plotting the evolution of loss and parameter values during the gradient descent process.
  • A shell script, autodiff.sh for streamlining the process of building the gradient descent application, executing it with suitable example files, and plotting the results.
• Another architecture file, autodiffVerifier.cpp, compilable to an executable for assessing the validity of automatically differentiated Faust programs via comparison with differentiation by finite differences.

Usage

The autodiff architecture file uses libfaust to compile DSP algorithms dynamically at runtime, so Faust must be compiled and installed with the LLVM backend:

cd build
make BACKENDS=all.cmake TARGETS=all.cmake  
sudo make install

Building and running an autodiff example

Rather than using the Faust compiler with the -a flag, the autodiff architecture file should be compiled directly, and llvm-config used to generate the appropriate compiler flags:

cd architecture/autodiff
c++ -std=c++14 autodiff.cpp $(faust -libdir)/libfaust.a \  
  $(llvm-config --ldflags --libs all --system-libs) \ 
  -o ~/tmp/faust-autodiff/autodiff_example

The compiled executable can then be run, with input (--input), ground truth (--gt) and differentiable (--diff) DSP files specified, plus optional loss function (-lf) and learning rate (-lr):

cd ~/tmp/faust-autodiff
examplesdir=$(faust --archdir)/examples/autodiff  
./autodiff_example --input $examplesdir/noise.dsp \ 
  --gt $examplesdir/gain/gt.dsp \ 
  --diff $examplesdir/gain/diff.dsp \ 
  -lf l2 \ 
  -lr 0.1

Output is a tabular representation of per-iteration loss and parameter values. For instance, for the one_zero filter example, with a single learnable parameter b1:

Learning rate: 0.1  
Sensitivity: 1e-07  
...  
Learnable parameter: b1, value: 0.5  

-----------------------------------------------------------------  
 Iter   Ground truth      Learnable           Loss             b1
-----------------------------------------------------------------  
    1  -0.9990000129  -0.9990000129      0.000e+00              - 
    2  -1.9870100021  -1.4975000620   0.2396199852   0.5978040695 
    3  -1.9850200415  -1.5936084986   0.1532029957   0.6759297848 
    4  -1.9830299616  -1.6699019670   0.0980491415   0.7383674979 
    5  -1.9810400009  -1.7304140329   0.0628133789   0.7882921696 
 ...

The executable also generates a csv file containing this data; the data can be plotted with the script plot.py.

The above commands are encapsulated in the shell script autodiff.sh.

Verification via finite differences

Compile autodiffVerifier.cpp to produce an executable for comparing the output of an autodiffed algorithm with that of the same algorithm differentiated by way of finite differences:

c++ -std=c++14 autodiffVerifier.cpp $(faust -libdir)/libfaust.a \  
  $(llvm-config --ldflags --libs all --system-libs) \ 
  -o ~/tmp/faust-autodiff/autodiff_verify

Run the executable, specifying input and differentiable .dsp files, and the finite difference --epsilon:

cd ~/tmp/faust-autodiff  
examplesdir=$(faust --archdir)/examples/autodiff  
./autodiff_verify --input $examplesdir/noise.dsp \  
  --diff $examplesdir/gain_dc/diff.dsp \ 
  --epsilon 1e-3

Output is the per-iteration delta between autodiffed and finite difference output:

--------------------------------------------------------------------------------  
 Iter          Param       Autodiff    Finite diff        |delta|     Rel. error
--------------------------------------------------------------------------------  
    1             dc   1.0000000000   0.9999870658      1.293e-05        0.001 % 
                gain   0.0000057486   0.0000298023      2.405e-05      418.428 % 
    2             dc   1.0000000000   0.9999870658      1.293e-05        0.001 % 
                gain  -0.3448459506  -0.3448426425      3.308e-06        0.001 %
    3             dc   1.0000000000   0.9999870658      1.293e-05        0.001 %  
                gain  -0.6951856613  -0.6951763630      9.298e-06        0.001 %
...

See architecture/autodiff/README.md for more detail on background, usage, and mathematical underpinnings.

Outstanding/Future work

The following tasks and aims remain for future work:

• Derivative implementations for the following primitives and expressions have not been implemented:
  • The recursive compostition operator ~;
  • rdtable and rwtable primitives;
  • soundfile and waveform primitives;
  • select2 and select3 primitives;
  • The atan2 math.h-equivalent primitive;
  • Foreign expressions.
• Implementation of reverse mode autodiff.
• Implementation of loss functions in addition to L1-norm and L2-norm.
• Calculation of loss over multiple samples — per-audio-buffer loss calculation; spectral loss calculation.
• Nomenclature could be improved; the architecture file uses autodiff functionality, but its purpose is to compute gradient descent, which the filename doesn't indicate.

The lack of a derivative expression for recursive expressions is a significant drawback, given the ubiquity of recursion in signal processing and audio synthesis algorithms. A mathematical expression for the derivative of a general-case recursive algorithm was devised, but implementing it at the signal stage proved to be beyond the reach of this body of work, and may not, in fact, be possible at the signal stage. Future work should focus on investigating whether realising autodiff as a box stage transformation instead will yield more favourable results. (Again, consult architecture/autodiff/README.md for more information.)

Given the absence of a derivative implementation for recursion, and much scope for improvement on what has been developed to date (in terms of loss calculation, etc.), this pull request is targeting the auto-differentiate branch rather than master-dev. It is hoped that, with more work, autodiff and gradient descent may become core language features, and that the work represented by this pull request can be refined into something worthy of being merged into Faust's main development branch.

Challenges, Reflections

In addition to the problem of recursion, which consumed at least a couple of weeks of doomed experimentation, I encountered a number of challenges along the way:

• (Re)acquainting myself with calculus, and thinking about differentiation in a far more general, abstract way than I ever have before was a significant challenge. I enjoyed putting pen to paper and deriving expressions, but at times I felt out of my depth.
• Similar sentiments apply to the topic of machine learning, which I now feel I understand a lot better than I did three months ago; what we've achieved here in terms of machine learning is, however, just the hint of a scratch on the surface of that topic.
• I've learnt a lot about how Faust works, I gave considerable attention to the syntax section of the not-so-quick Faust Quick Reference, and it has been a really interesting challenge to try to understand some of the more arcane corners of the compiler.
• Many thanks to Agathe, David, and Stéphane for their support and (more importantly) patience during the coding period.

[sletz]

Thanks for the PR. I had a small conflict but it should be OK. Testing a bit before merge.

[hatchjaw]

Thanks for the PR. I had a small conflict but it should be OK. Testing a bit before merge.

Thanks Stéphane. Yeah, I tried to resolve some conflicts via the interface here, but I must've overlooked something.

[hatchjaw]

SignalAutoDifferentiate was duplicated in sigPromotion.hh. Just pushed a fix.

[sletz]

Got:

/autodiff.sh  gain
/usr/local/share/faust/autodiff/autodiff.cpp:221:28: error: use of undeclared identifier 'iszero'
                gradient = iszero(delta) ?
                           ^
1 error generated.
./autodiff.sh: line 62: ./my_autodiff: No such file or directory

[hatchjaw]

Oh, is iszero architecture/platform-specific?

[sletz]

Where is iszero supposed to be defined ?

[hatchjaw]

On the (linux) machine I'm working on it lives in math.h, line 1129.

[sletz]

Seems not standard, then better provide a custom defined version.

[sletz]

Thanks.

[sletz]

Finally rebased in master-dev branch and merged in https://github.com/grame-cncm/faust/commit/681a303b8ddc9ef2e67c2cc5d5df83f27323b865, thanks!

[Pujakumari1202]

Hi there I am Puja Kumari currently planning to contribute to open source through GSOC and I found the GRAME community quite intresting because primarily focusing on projects related to audio programming and digital signal processing. It would be really great if the community members would help me to know regarding how should I get started.

[hatchjaw]

Hi @Pujakumari1202, take a look at the Faust Ideas repository; read the links in the readme there, and consider joining the Discord server (https://discord.gg/RzuFg6B8zA).

[Pujakumari1202]

I have joined Discord, but this is my first time, and i have no idea what to do next or how to proceed, but we really want to do this.