5 ms·
From the programming language point of view, what's interesting to me is that this means, I think, that there is a differentiation monad. This arises because mo
by noelwelsh 7y ago
From the programming language point of view, what's interesting to me is that this means, I think, that there is a differentiation monad. This arises because monads are equivalent to continuations and hence anything you can express with continuations can also be expressed as a monad.
I haven't seen this discussed before, except in the context of category theory (https://ncatlab.org/nlab/show/differentiation https://ncatlab.org/nlab/show/differentiation) I'm not sure how this ties into the programming language point of view.
- edflsafoiewq 7y agoCan you unpack this a little? What exactly is the monad?
- noelwelsh 7y agoIf you speak Scala, here's code for reverse mode differentiation as a monad. The flatMap / bind operation becomes the the chain rule. If this "explanation" (scare quotes because it's not really an explanation, just a code dump) doesn't work for you let me know and I can try a different approach. final case class AD[A](v: A, k: Double => Double) { // Chain rule def flatMap[B](f: A => AD[B]): AD[B] = { val self = this val next = f(v) AD(next.v, (d: Double) => next.k(d) * self.k(d)) } def +(that: AD[Double])(implicit ev: A =:= Double): AD[Double] = AD(this.v + that.v, (d: Double) => this.k(d) + that.k(d)) def *(that: AD[Double])(implicit ev: A =:= Double): AD[Double] = AD(this.v * that.v, (d: Double) => (this.k(d) * that.v) + (that.k(d) * this.v)) def sin(implicit ev: A =:= Double): AD[Double] = this.flatMap(x => AD(Math.sin(x), (d) => Math.cos(x) * d)) def gradient: Double = this.k(1.0) } object AD { def pure(x: Double): AD[Double] = AD(x, d => 1.0) }
- edflsafoiewq 7y agoOh, that's the monad — × M where M is a monoid right? M being, in this case, the monoid of functions R -> R under point-wise multiplication. Shouldn't M actually be a monoid under composition? ie. you should compose like next.k(self.k(d)), not multiply.
- noelwelsh 7y agoSorry, I don't understand your notation. To me a monad is defined by two functions, pure and bind (aka flatMap). I don't understand how — × M corresponds to this.
- tome 7y ago— × M is the functor. In Haskell it would generally be used as "Writer M", but (M,) can also be used.
- noelwelsh 7y agoSorry, that doesn't help. I literally do not understand the notation. I do not know what — means in this context, I don't understand what role × plays here, etc.
- tome 7y ago"—" means "the parameter of the type constructor goes here". I believe in Scala you use underscore for this, at the value level at least. "×" is what mathematicians call the type constructor for the usual product type. In Haskell this is called (,). I don't know what it's called in Scala. So, — × M means something like "type T a = T a M", in Haskell notation.
- edflsafoiewq 7y agoIn your notation it would be something like final case class Mon[A](v: A, m: M) { def flatMap[B](f: A => Mon[B]): Mon[B] = Mon(f(this.v).v, f(this.v).m * this.m) // * is M's binary operation } object Mon { def pure(v: A): Mon[A] = Mon(v, M.unit) // M.unit is M's identity element }
- tiarkrompf 7y agoHi Noel, can you clarify how this corresponds to reverse mode AD? To me it seems more like a delayed or on-demand version of forward AD.