Automatic Differentiation in Machine Learning: A Survey [pdf]

Re:Automatic Differentiation in Machine Learning: A Survey [... by edflsafoiewq on Monday November 19, 2018 @10:40PM (#18491663)

AD reminds me of another idea: in cryptography, you can determine eg. how bit dependencies propagate through a state vector by running the regular code for your compression function or whatever, but on "numbers" that actually track the dependencies of bits. Details vary, but a simple idea is to use as a "number" a vector of symbolic equations for each bit in the number in terms of symbolic variables for input bits to the function. You can then easily calculate items of interest eg. at this many rounds, has every input bits affected every output bit?

So, jets instead of numbers for differentiation, systems of boolean equations instead of numbers for answering some crypto questions... anyone know of other tricks in this vein?

[ Parent | on HN ]

Re:Automatic Differentiation in Machine Learning: A Survey [... by aaaaaaaaaab on Tuesday November 20, 2018 @03:56AM (#18492626)

Taint checking: https://en.m.wikipedia.org/wiki/Taint_checking

Every external input to a program is assumed “tainted”. There are certain operations that make them “safe” (e.g. escaping a string makes it safe against SQL injection, etc.).

You simply attach this “tainted/safe” bit of information to each piece of data and flow it through your program. There is a simple calculus for combining these tainted/safe values, i.e. appending a tainted string to a safe string produces a tainted string, etc.

The goal is to prove that tainted values can’t make it to the business logic, so that your program is safe against certain kinds of malicious input.

[ Parent | on HN ]

Re:Automatic Differentiation in Machine Learning: A Survey [... by profquail on Tuesday November 20, 2018 @06:56AM (#18493182)

What you’re describing sounds like Abstract Interpretation[1], a technique used in static analyzers and compilers (e.g. for bounds-check elimination). You can pick any abstract domain you want, but the more complex the domain — i.e., the more complex/precise your tracking of the possible values associated with each variable — the longer it takes for the analysis to run.

[1]: https://en.m.wikipedia.org/wiki/Abstract_interpretation

[ Parent | on HN ]

Re:Automatic Differentiation in Machine Learning: A Survey [... by edflsafoiewq on Tuesday November 20, 2018 @12:55PM (#18495882)

Abstract interpretation would be the equivalent of symbolic differentiation in this analogy.

[ Parent | on HN ]

Re:Automatic Differentiation in Machine Learning: A Survey [... by xKingfisher on Tuesday November 20, 2018 @01:05AM (#18492085)

The KLEE project[1] does something similar for general code, with symbolic variables.

[1] http://klee.github.io

[ Parent | on HN ]

Re:Automatic Differentiation in Machine Learning: A Survey [... by YorkshireSeason on Tuesday November 20, 2018 @05:42AM (#18492935)

I would be surprised if there was any crypto where not any output bit depended on any input bit (of course it depends on what precisely one means by "depends upon"). Otherwise, couldn't the search-space be partitioned? See also: Shannon's confusion and diffusion principle [1], as well as the avalanche effect [2].

[1] https://en.wikipedia.org/wiki/Confusion_and_diffusion

[2] https://en.wikipedia.org/wiki/Avalanche_effect

[ Parent | on HN ]

Re:Automatic Differentiation in Machine Learning: A Survey [... by antidesitter on Tuesday November 20, 2018 @10:25AM (#18494431)

Sounds like higher-order differential cryptanalysis:

https://en.wikipedia.org/wiki/Higher-order_differential_cryp...

[ Parent | on HN ]

Re:Automatic Differentiation in Machine Learning: A Survey [... by CardenB on Monday November 19, 2018 @10:53PM (#18491703)

There’s definitely some work of tracking activations in a network for a given set of inputs. It’s a good black-box way to prune your network for lighter weight models.

[ Parent | on HN ]

Re:Automatic Differentiation in Machine Learning: A Survey [... by tnecniv on Tuesday November 20, 2018 @01:09AM (#18492098)

Do you have a reference for the crypto trick you described?

[ Parent | on HN ]

Re:Automatic Differentiation in Machine Learning: A Survey [... by goldenkey on Tuesday November 20, 2018 @05:29AM (#18492896)

Would you mind providing a reference to this technique? I recently got into theoretical cryptography and am quite interested in any analytical tools.

[ Parent | on HN ]