Define isequal and == more widely between Kernels

[mjp98]

It would be nice to define isequal and/or == as widely as possible between Kernels and Transforms. At the moment some basic cases seem to be missing, such as

julia> using KernelFunctions

julia> a = 2*WhiteKernel()
White Kernel
        - σ² = 2

julia> b = 2*WhiteKernel()
White Kernel
        - σ² = 2

julia> a == b
false

julia> isequal(a, b)
false

I'm not clear exactly when isequal/== both should be extended (and if hash is also needed), but would be happy to work on an PR that starts to improve this if there's a clear way forward.

[willtebbutt]

I think it's fair to say that we've avoided taking this implementation task seriously until now because we've not had a complelling use-case -- about the most that we've been able to say is that it is a nice-to-have, rather than a necessity. Do you have a particular use-case in mind?

[mjp98]

The use case that brought me here was to pass an interface test that would like two fitted objects to be equal when one is updated with unchanged parameters. I was hoping to store the posterior in a fitted object to save recomputing it which I think would require PosteriorGPs to be equal, and this seemed to be one of the points that needed to be addressed.

Maybe there's a better way?

[willtebbutt]

Ahh I see. This definitely does indeed sound like an interesting use-case.

Probably the best way forward is to first consider how equality tests would be included in our standard collection of interface tests.

Clearly k==k (or isequal(k, k) -- I'm also not sure what the right function to implement is) is a necessary condition. I'm not sure how we would check that the converse (that things aren't equal when they ought not to be) could be checked using our current testing infrastructure though. I would be keen to know if you have thoughts on how we might tackle that side of things.

edit: updated phrasing

[devmotion]

Relevant parts of the docstrings:

help?> isequal
search: isequal issetequal

  isequal(x, y)

  Similar to ==, except for the treatment of floating point numbers and of missing values.
  [...]

  Implementation
  ≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡

  The default implementation of isequal calls ==, so a type that does not involve
  floating-point values generally only needs to define ==.

  isequal is the comparison function used by hash tables (Dict). isequal(x,y) must imply
  that hash(x) == hash(y).

  This typically means that types for which a custom == or isequal method exists must
  implement a corresponding hash method (and vice versa). Collections typically implement
  isequal by calling isequal recursively on all contents.

  Furthermore, isequal is linked with isless, and they work together to define a fixed
  total ordering, where exactly one of isequal(x, y), isless(x, y), or isless(y, x) must be
  true (and the other two false).

  Scalar types generally do not need to implement isequal separate from ==, unless they
  represent floating-point numbers amenable to a more efficient implementation than that
  provided as a generic fallback (based on isnan, signbit, and ==).
  [...]

help?> ==
search: == === !==

  ==(x, y)

  [...]

  Implementation
  ≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡

  New numeric types should implement this function for two arguments of the new type, and
  handle comparison to other types via promotion rules where possible.

  isequal falls back to ==, so new methods of == will be used by the Dict type to compare
  keys. If your type will be used as a dictionary key, it should therefore also implement
  hash.

  If some type defines ==, isequal, and isless then it should also implement < to ensure
  consistency of comparisons.

That is, according to my understanding one should implement == and hash but not isequal.

[mjp98]

Thanks for the reference!

@willtebbutt It's not clear to me that testing inequality at the interface level well is feasible. This must be a standard issue, perhaps typically dealt with by unit tests all the way down?

To me a natural, compare something similar, but different test for composite types would require a similar_but_unequal constructor for all types, perhaps defined recursively, and some strategy specification for how the difference should be introduced. This seems out of scope, but maybe something like this exists?

At the interface level, I'd lean towards having a k==k test, and k !== transform(k), which would just provide a sanity check that the kernel wasn't spuriously equal to all other kernels. It could be documented that subtle inequality checks should be added kernel by kernel, although it's a bit unsatisfactory.

It could also be suggested that equality is implemented for all types in an automated manner - how would you feel about using AutoHashEquals.jl on all structs? Since types in the AbstractGP world are almost always immutable, I think this approach makes sense?

AutoHashEquals.jl seems to define == using isequal for subcomparisons.

[willtebbutt]

Thanks for looking at that @devmotion . I agree with your assessment of what should be implemented.

At the interface level, I'd lean towards having a k==k test, and k !== transform(k), which would just provide a sanity check that the kernel wasn't spuriously equal to all other kernels. It could be documented that subtle inequality checks should be added kernel by kernel, although it's a bit unsatisfactory.

I think this makes a lot of sense. Checking the precise definition of equality is inherently kernel-specific so I don't think we can do much better than your proposal in general. Checking that k==k and k !== transform(k) for some standard transform (perhaps just k + 0.1?) is clearly always doable, and we know the answer in both cases. I like this.

To me a natural, compare something similar, but different test for composite types would require a similar_but_unequal constructor for all types, perhaps defined recursively, and some strategy specification for how the difference should be introduced. This seems out of scope, but maybe something like this exists?

I agree that this feels out-of-scope, and I don't think I'd be keen to add it at this point.

It could also be suggested that equality is implemented for all types in an automated manner - how would you feel about using AutoHashEquals.jl on all structs? Since types in the AbstractGP world are almost always immutable, I think this approach makes sense?

I'm less keen on this, but mainly because I don't like the idea of having to write @auto_hash_equals in front of many of our structs. Maybe it's fine though?

Okay. I'm happy that we can do a decent job of testing. The question is then what to do about implementation.
I can think of a few different cases:

1. no method needed. e.g. SEKernel() == SEKernel() holds out-of-the-box (somehow)
2. method needed e.g. 5 * SEKernel() == 5 * SEKernel() isn't currently correct
3. method between types needed. e.g. Matern12Kernel() == MaternKernel(nu=0.5)` should probably hold

I'm really hoping that there aren't too many things in category three. Do you think this model of the cases is accurate @mjp98 , or are there some cases that I've missed?

[theogf]

Regarding the second point, would making some of those transformed kernels (like the scaled one) completely immutable solve the solution?

[willtebbutt]

Possibly -- I still don't fully understand why they're not already equal to be honest. I also don't really understand why SEKernel() == SEKernel() holds, because our SEKernels contain a metric.

[mjp98]

I'm hesitant about Matern12Kernel() == MaternKernel(nu=0.5), since this would introduce cases where K1 == K2 but K1(x,y) !== K2(x,y) due to numerical error, e.g.

julia> K1 = KernelFunctions.Matern12Kernel()
Exponential Kernel (metric = Distances.Euclidean(0.0))

julia> K2 = KernelFunctions.MaternKernel(ν=0.5)
Matern Kernel (ν = 0.5, metric = Distances.Euclidean(0.0))

julia> x = 1e-6; y = -x;

julia> K1(x,y) == K2(x,y)
false

Maybe a specialised kind of equality could be implemented for category 3 later, if needed, and stick to cases 1 and 2 for now?

[willtebbutt]

Maybe a specialised kind of equality could be implemented for category 3 later, if needed, and stick to cases 1 and 2 for now?

I would be happy to leave it for now to be honest. It would be good to try and write down a succinct definition of what it mean for two kernels to be equal under this system. It clearly has something to do with

1. them being the same struct (as opposed to type -- I'm assuming 5 * SEKernel() == 5.0 * SEKernel() would be the same)
2. each of their fields being equal

but I'm not sure whether this is exactly it, or if I've missed something.

I just want it to be crystal clear what definition we're picking, and whether any two kernels are equal under it.

[mjp98]

A clear definition is definitely sensible to avoid ending up in a hole.

There do seem to be various edge cases, as I don't think points 1. and 2. above would catch a case where a Kernel stores certain information only in a type parameter, and not a property, along the lines of

struct MyKernel{T} end;
function (K::MyKernel{T})(x,y) where T
    return T
end

[willtebbutt]

Good catch.

Maybe point 1 is better phrased as a necessary condition: k1 and k2 are necessarily unequal if they are instances of different (mutable) structs.

If k1 and k2 have the same struct, they may be equal. It will be kernel-specific whether or not they are equal.

I think the above excludes the annoying case 3, but leaves it open to the kernel-implementer to decide what it means for two instances of their kernel to be equal.

[mjp98]

Okay, so we could have:

k1 and k2 are necessarily unequal if they are instances of different (mutable) structs.
If k1 and k2 have the same struct, they may be equal. It will be kernel-specific whether or not they are equal.

and maybe document some general expectations (the first may be too optimistic if methods dispatch on numeric type)

1. if k1==k2 then isequal(k1(x,y), k2(x,y)) (and similarly for kernelmatrix, etc.)
2. all corresponding parameters are isequal

but otherwise

leave it open to the kernel-implementer to decide what it means for two instances of their kernel to be equal.

I think this would be sorted by adding the following methods where needed:

# For something like
struct SomeKernel{T} 
    param::T
end
# Define
Base.hash(a::SomeKernel, h::UInt) = hash(a.param, hash(nameof(typeof(a)), h))
Base.(:(==))(a::SomeKernel, b:SomeKernel) = isequal(a.param, b.param)

If this seems sensible I'll start working on a PR?

[willtebbutt]

if k1==k2 then isequal(k1(x,y), k2(x,y)) (and similarly for kernelmatrix, etc.)

This seems like an excellent definition. This will clearly only hold approximately for things like 5.0 * SEKernel() vs 5f0 * SEKernel() or whatever, but I agree that it seems like a good defintion. Maybe we just replace the second bit with "isapprox for some precision-appropriate tolerance" or something?

Otherwise, I think we're good to go. Looking forward to the PR.

[mjp98]

I have almost got tests passing locally on the addition to test_interface of

    # Check that two instances of the same kernel are equal
    @test k == deepcopy(k)
    @test k !== 2 * k
    @test hash(k) == hash(deepcopy(k))

The outstanding failures are due to issues with equality between metrics, e.g.

Rational Quadratic Kernel (α = 0.36842547149772464, metric = WeightedEuclidean{Vector{Float64}}([1.0, 2.0])) == 
Rational Quadratic Kernel (α = 0.36842547149772464, metric = WeightedEuclidean{Vector{Float64}}([1.0, 2.0]))

WeightedEuclidean appears to be the only case hit. Fixing this requires JuliaStats/Distances.jl#247

[willtebbutt]

Fantastic. How urgent is this for you? We can implement this in this package now and recurse into Distances when the issue is fixed if you need this soon.