Rewrite ICP in ReverseDiff style #97

eeshan9815 · 2018-07-11T15:19:39Z

No description provided.

chriscoey · 2018-07-11T15:42:23Z

@jrevels what about cassette?

jrevels · 2018-07-11T16:36:39Z

@jrevels what about cassette?

Cassette would definitely be useful here if it was released/usable with a released version of Julia, but that's not currently the case.

Always down to help folks play around with a Cassette-based implementation if somebody wants to make the attempt, though.

dpsanders · 2018-07-11T18:03:14Z

I discussed using Cassette with @eeshan9815. We decided that this would be a good first step.

We are very interested in discussing that with you, though, @jrevels.

dpsanders · 2018-07-11T18:05:38Z

src/IntervalConstraintProgramming.jl

@@ -20,9 +20,12 @@ export
    SubPaving, Paving,
    pave, refine!,
    Vol,
-    show_code
+    show_code, icp!


You need to export icp too / instead.

Okay, I will add both versions.

dpsanders · 2018-07-11T18:06:06Z

src/icp.jl

+julia> constraint = -∞..1
+[-∞, 1]
+
+julia> icp(f, X, constraint)


Should this be icp!?

Oh yeah, sorry about the typo.

dpsanders · 2018-07-13T13:30:47Z

src/tape/tracked.jl

+const NULL_INDEX = typemin(Int)
+const NULL_TAPE = InstructionTape()
+
+ type TrackedReal{V<:Real,O} <: Real


immutable? And spacing problem.

The values in the TrackedReal are modified as the tape is traversed, so it can't be an immutable

dpsanders · 2018-07-13T13:30:55Z

src/tape/tracked.jl

+
+TrackedReal{V}(v::V, tp::InstructionTape = NULL_TAPE) = TrackedReal{V,Void}(v, tp)
+
+ immutable TrackedArray{V,N,VA} <: AbstractArray{TrackedReal{V,TrackedArray{V,N,VA}},N}


Extra space

dpsanders · 2018-07-14T15:02:36Z

type -> mutable struct

dpsanders · 2018-07-14T15:03:09Z

src/tape/tracked.jl

+const NULL_INDEX = typemin(Int)
+const NULL_TAPE = InstructionTape()
+
+type TrackedReal{V<:Real,O} <: Real


type -> mutable struct

dpsanders · 2018-07-14T15:04:49Z

src/tape/icp.jl

@@ -106,16 +106,47 @@ function reverse_pass!(tape::InstructionTape, input::AbstractArray)
        t = tape
        t[i].output.value = t[i].output.value ∩ t[i].cache
        op = IntervalContractors.reverse_operations[Symbol(t[i].func)]
+        if op == :mul_rev
+            if istracked(t[i].input[1]) && istracked(t[i].input[2])


This if seems to just be a combination of the two below, so can be eliminated (replacing the elseifs by ifs).

Won't that require four comparisions, instead of the current three?
The current flow of control is -

if a && b else if a #if a && !b else if b #if !a && b else #if !a && !b

As far as I can tell, there's just two things to check: a or !a, and separately b or !b

But isn't that four comparisions in the worst case, instead of 3 if elseif is used?

dpsanders · 2018-07-14T15:05:14Z

src/tape/icp.jl

+            elseif istracked(t[i].input[1])
+                rev_result = mul_rev_2(value(t[i].output), value.(t[i].input)...)
+                t[i].input[1].value = rev_result
+                if 0 < t[i].input[1].index <= n


What is this line for?

If the index of the variables is between 0 and n, that means that the variable is one of the input variables, for which, the changes need to be reflected in the input array as well.

dpsanders · 2018-07-14T15:07:39Z

src/tape/icp.jl

+
+"""
+
+function icp!(f::Function, input::AbstractArray, constraint::Interval)


The convention is that the first argument is modified, so I think we should reverse the order of the first two arguments.

Actually, if the mutating function accepts a function argument, then that usually comes first, e.g.

help?> map! search: map! asyncmap! map mapfoldr mapfoldl mapslices mapreduce mapreducedim asyncmap macroexpand @macroexpand map!(function, destination, collection...) Like map, but stores the result in destination rather than a new collection. destination must be at least as large as the first collection.

with the reason being that it allows use of the convenient do notation.

Ah, OK, thanks!

dpsanders · 2018-07-16T13:45:19Z

It's two comparisons: one for a and a separate one for b. Two separate ifs - they are independent. Or am I mistaken?

…

On Mon, 16 Jul 2018, 9:38 am Eeshan Gupta, ***@***.***> wrote: ***@***.**** commented on this pull request. ------------------------------ In src/tape/icp.jl <#97 (comment)> : > @@ -106,16 +106,47 @@ function reverse_pass!(tape::InstructionTape, input::AbstractArray) t = tape t[i].output.value = t[i].output.value ∩ t[i].cache op = IntervalContractors.reverse_operations[Symbol(t[i].func)] + if op == :mul_rev + if istracked(t[i].input[1]) && istracked(t[i].input[2]) But isn't that four comparisions in the worst case, instead of 3 if elseif is used? — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#97 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AALtTr400e48GlUjoJHCf4uRBnxxFXxuks5uHJdsgaJpZM4VLWJz> .

dpsanders · 2018-07-16T13:45:42Z

Since you seem to just be duplicating the code.

…

On Mon, 16 Jul 2018, 9:45 am David P. Sanders, ***@***.***> wrote: It's two comparisons: one for a and a separate one for b. Two separate ifs - they are independent. Or am I mistaken? On Mon, 16 Jul 2018, 9:38 am Eeshan Gupta, ***@***.***> wrote: > ***@***.**** commented on this pull request. > ------------------------------ > > In src/tape/icp.jl > <#97 (comment)> > : > > > @@ -106,16 +106,47 @@ function reverse_pass!(tape::InstructionTape, input::AbstractArray) > t = tape > t[i].output.value = t[i].output.value ∩ t[i].cache > op = IntervalContractors.reverse_operations[Symbol(t[i].func)] > + if op == :mul_rev > + if istracked(t[i].input[1]) && istracked(t[i].input[2]) > > But isn't that four comparisions in the worst case, instead of 3 if > elseif is used? > > — > You are receiving this because you commented. > Reply to this email directly, view it on GitHub > <#97 (comment)>, > or mute the thread > <https://github.com/notifications/unsubscribe-auth/AALtTr400e48GlUjoJHCf4uRBnxxFXxuks5uHJdsgaJpZM4VLWJz> > . >

eeshan9815 · 2018-07-16T13:57:18Z

Ohh, I just realized what you mean!
Yes you're right, I will update accordingly.

dpsanders · 2018-07-19T20:41:31Z

Please remove 0.5 from testing, and make nightly an allowed failure.

dpsanders · 2018-07-28T16:05:38Z

src/tape/icp.jl

+        t = tape
+        t[i].output.value = t[i].output.value ∩ t[i].cache #Propogation of constraints up
+        op = IntervalContractors.reverse_operations[Symbol(t[i].func)] #Looking up the reverse function in IntervalContractors
+        if op == :mul_rev #Special behavior to deal with constants


Isn't this generic for any binary operator?

dpsanders · 2019-05-11T23:47:08Z

I believe this is not up to date with Julia 1.0, so I am planning to close it. Feel free to re-open when possible.

dpsanders · 2024-03-19T16:02:37Z

No longer relevant.

Rewrite ICP in ReverseDiff style

b2ed42e

dpsanders reviewed Jul 11, 2018

View reviewed changes

eeshan9815 added 2 commits July 12, 2018 17:10

Add both icp and icp! and organize code in a subdirectory

5e53118

Add support for IntervalBox

12ce801

dpsanders reviewed Jul 13, 2018

View reviewed changes

Fix handling of constants in multiplication

a3ca319

eeshan9815 force-pushed the rewrite branch from a149016 to a3ca319 Compare July 14, 2018 12:09

dpsanders reviewed Jul 14, 2018

View reviewed changes

Add initial tests and documentation

962024e

eeshan9815 added 2 commits July 21, 2018 09:21

Add support for univariable constraints which make a 0-element tape

a7073fb

Remove 0.5 from testing and make nightly an allowed failure

493882b

dpsanders reviewed Jul 28, 2018

View reviewed changes

dpsanders mentioned this pull request Jan 31, 2019

Use MultivariatePolynomials to constraint #117

Closed

dpsanders closed this Mar 19, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Rewrite ICP in ReverseDiff style #97

Rewrite ICP in ReverseDiff style #97

eeshan9815 commented Jul 11, 2018

chriscoey commented Jul 11, 2018

jrevels commented Jul 11, 2018

dpsanders commented Jul 11, 2018

dpsanders Jul 11, 2018

eeshan9815 Jul 12, 2018

dpsanders Jul 11, 2018

eeshan9815 Jul 12, 2018

dpsanders Jul 13, 2018

eeshan9815 Jul 14, 2018

dpsanders Jul 13, 2018

dpsanders commented Jul 14, 2018

dpsanders Jul 14, 2018

dpsanders Jul 14, 2018

eeshan9815 Jul 16, 2018

dpsanders Jul 16, 2018

eeshan9815 Jul 16, 2018

dpsanders Jul 14, 2018

eeshan9815 Jul 16, 2018

dpsanders Jul 14, 2018

jrevels Jul 14, 2018

dpsanders Jul 14, 2018

dpsanders commented Jul 16, 2018 via email

dpsanders commented Jul 16, 2018 via email

eeshan9815 commented Jul 16, 2018

dpsanders commented Jul 19, 2018

dpsanders Jul 28, 2018

dpsanders commented May 11, 2019

dpsanders commented Mar 19, 2024


		TrackedReal{V}(v::V, tp::InstructionTape = NULL_TAPE) = TrackedReal{V,Void}(v, tp)

		immutable TrackedArray{V,N,VA} <: AbstractArray{TrackedReal{V,TrackedArray{V,N,VA}},N}


		"""

		function icp!(f::Function, input::AbstractArray, constraint::Interval)

Rewrite ICP in ReverseDiff style #97

Rewrite ICP in ReverseDiff style #97

Conversation

eeshan9815 commented Jul 11, 2018

chriscoey commented Jul 11, 2018

jrevels commented Jul 11, 2018

dpsanders commented Jul 11, 2018

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

dpsanders commented Jul 14, 2018

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

dpsanders commented Jul 16, 2018 via email

dpsanders commented Jul 16, 2018 via email

eeshan9815 commented Jul 16, 2018

dpsanders commented Jul 19, 2018

Choose a reason for hiding this comment

dpsanders commented May 11, 2019

dpsanders commented Mar 19, 2024