Update for AD 4

[ericpashman]

@jfischoff, I've been trying to update your package to work with version 4.* of Numeric.AD, which introduced substantial changes to the underlying types. (In particular, reverse-mode AD now uses some Data.Reflection magic.) I've tried numerous different ways to reconstruct things, but I've ultimately been stymied by the type-checker every time.

On the ad4 branch of my fork, I have a stripped-down version of Numeric.AD.Lagrangian.Internal (ericpashman/lagrangian@8ee6ca01bd6158162ce9cf7ff946c788f18a9c2c) with a minimize function that "works", but only for a fixed objective function and set of constraints. Right now there's a max-entropy example in there that you can verify gives the right answer:

*Numeric.AD.Lagrangian.Internal> minimize (1e-10) 4
...    
Right (fromList [0.2500000000014204,0.2500000000014204,0.2500000000014204,0.2500000000014204],fromList [0.3862943611128916])

If you take a look, you'll see that my code is nearly unchanged from yours except for the types (and some imports). The problem is that I can't get the types right when I try to abstract minimize over toMin and constraints, and GHC is not being very helpful. I've gone through many permutations, with all sorts of fun existential newtypes and higher-rank signatures, but nothing doing. The types in there right now are the simplest (most general) that will work.

Will you give it a look if you have a chance? I imagine I'm missing something pretty basic, but if it's just as mysterious to you, maybe we can get @ekmett to give us a word of advice. ...

Thanks!

[ekmett]

Re: the changes with Reverse:

You can always use Kahn mode which is the old Reverse if you want to avoid the use of reflection to create a shared tape.

What happened was we did benchmarking and it turned out that the bottleneck of using a single "Wengert list" style tape for reverse mode was less than the overhead of doing the topological sort we were doing to push information through the reified expression graph.

[ericpashman]

Thanks for the tip, @ekmett. I want to get reverse mode working, but I'm planning to turn to one of the other, friendlier-looking modes this weekend.

One of the commoner dead-ends I hit was a "no instance for (Reifies s Tape)" type error. That's a sure sign of mess, isn't it? My understanding of Data.Reflection is poor, but I should never have to write an instance for Reifies, right?

[ekmett]

You need to use one of the combinators to generate a tape from whole cloth to use reverse mode. That is where the 'Reifies s Tape' noise is coming from. You're trying to go in and use the low level machinery without something fabricating a tape for you for the mode to use.

You may want to look at how some of the machinery in Numeric.AD.Newton works to get a sense for how to work with multiple modes on the same expression, and how to throw reverse mode into the mix. It is admittedly fairly complex. =)

-Edward

On Fri, Sep 12, 2014 at 10:52 PM, Eric Pashman notifications@github.com wrote:

Thanks for the tip, @ekmett https://github.com/ekmett. I want to get reverse mode working, but I'm planning to turn to one of the other, friendlier-looking modes this weekend.

One of the more common dead-ends I hit was a "no instance for (Reifies s Tape)" type error. That's a sure sign of mess, isn't it? My understanding of Data.Reflection is poor, but I should never have to write an instance for Reifies, right?

— Reply to this email directly or view it on GitHub https://github.com/jfischoff/lagrangian/issues/2#issuecomment-55479721.

[ericpashman]

Ah. I see. ... I wondered about that, but I thought surely I didn't need to get that deep into things when I could get something running with a fixed objective function.

I'll take a look at your implementation of Newton's method. I'm also fairly ignorant about how automatic differentiation really works, so wish me luck. :P

[ekmett]

If you want to avoid caring too much about the details I'd recommend sticking to forward mode and its variants until you have a solid understanding of what is going on.

[ericpashman]

I submitted a pull request that updates everything using reverse mode. I found more than one way to do this, so I wanted to discuss things a bit.

The last commit in my pull request changes the Constraint type, hiding all of the underlying numeric types behind an existential. This let me put very general rank-2 signatures on all of the functions in Lagrangian.Internal in order to pass around a universally quantified objective function (and transformed versions of it), inferring different specialized types as needed inside each function. The result is that everything is very simple, without any explicit type signatures indicating the AD mode. With this approach, I think it will also be easy to extend the library to use other AD modes if we want to.

But to use the library, you have to give an objective function to maximize, minimize, and (<=>) that is polymorphic in its underlying numeric type; that is, the objective function must have type Floating a => [a] -> a. This doesn't seem to me to be a problem, but I might be missing something.

I left in a messy penultimate commit because it shows a rather different way of doing things in Lagrangian.Internal. This way attaches signatures indicating the AD mode being used everywhere, much in the way I was trying to do initially, as discussed above. This works, and is broadly similar to the approach used in previous versions of the library, but I couldn't find a simple way to get the feasible function to work together with maximize and minimize: they require different mode types for the objective function, so the types on the helper functions (lagrangian and squaredGradient) have to be different. I couldn't find a nice way to get everything to unify, but it is possible to get feasible working—I have a version working in another module that re-implements the helper functions with alternative types. It's just a bit of a mess. It can be done, but if there's a good way to do it, it has eluded me.

TLDR: I like what's in the last commit, but am not sure whether requiring users to pass in objective functions polymorphic in their numeric type is problematic in ways I haven't foreseen. If that is a problem, there's another way to do things, but it's more complicated and I was making a mess of it.

[ericpashman]

Oh, I also made some somewhat opinionated, mostly unrelated changes that probably should have been done later, in separate commits. In particular, I changed the order of arguments to minimize and maximize to something that made more sense to me. Please feel free to nix these changes if you want to.

Also note that (in my preferred version) there's no longer any need to define or export any types other than Constraint. There's also no need to explicitly depend on Data.Reflection, so that should get removed from the updated Cabal file.

I'll shut up now!

[jfischoff]

Great!

I've been too busy to give any of my projects much love, so thanks. Merging.

On Thu, Sep 25, 2014 at 4:21 PM, Eric Pashman notifications@github.com wrote:

Oh, I also made some somewhat opinionated, mostly unrelated changes that probably should have been done later, in separate commits. In particular, I changed the order of arguments to minimize and maximize to something that made more sense to me. Please feel free to nix these changes if you want to.

Also note that (in my preferred version) there's no longer any need to define or export any types other than Constraint. There's also no need to explicitly depend on Data.Reflection, so that should get removed from the updated Cabal file.

I'll shut up now!

— Reply to this email directly or view it on GitHub https://github.com/jfischoff/lagrangian/issues/2#issuecomment-56899249.

[jfischoff]

@eric Also I don't know if you noticed but I added you as a collaborator. Feel free to merge what you see fit.

On Thu, Sep 25, 2014 at 5:55 PM, Eric Pashman notifications@github.com wrote:

Closed #2 https://github.com/jfischoff/lagrangian/issues/2 via d9810dc https://github.com/jfischoff/lagrangian/commit/d9810dc52bdc557af6282aa14fca83a079873a99 .

— Reply to this email directly or view it on GitHub https://github.com/jfischoff/lagrangian/issues/2#event-170496262.

[eric]

I think you picked the wrong eric.

[ericpashman]

@eric, there's enough automatically differentiated, Lagrange-multiplied, purely functional goodness here for more than one Eric. :P

Thanks, @jfischoff, I did see that you gave me push privileges. I'm planning to update your maxent library to incorporate these changes, too.