feat: Hamming Distance Kernel

[patel-zeel]

Feature Request

Describe the Feature Request

In a regression problem where we have categorical inputs (for example, Patel et al.), euclidean distance does not make sense. People sometimes use one-hot-encoding which may not be space-efficient in cases where number of categories are very high. Thus, we can use a Hamming distance kernel for these features: $k\left(x, x^{\prime}\right)=\exp \left(-\frac{\mathbb{I}_{x \neq x^{\prime}}}{\ell}\right)$.

Describe Preferred Solution

• Implement the Hamming Distance Kernel in GPJAX.
• Add tests for it.
• Add a notebook demo for a toy dataset.

Describe Alternatives

• GPyTorch has a general version of this kernel called IndexKernel. If it is desired, we can implement IndexKernel over the Hamming distance kernel while retaining the ability to restrict the parameters to the Hamming distance kernel setting if needed.

Related Code

Additional Context

Papers where this kernel is discussed:

• Patel, Z. B., Purohit, P., Patel, H. M., Sahni, S., & Batra, N. (2022). Accurate and Scalable Gaussian Processes for Fine-Grained Air Quality Inference. Proceedings of the AAAI Conference on Artificial Intelligence, 36(11), 12080-12088. https://doi.org/10.1609/aaai.v36i11.21467
• Hutter, F.; Xu, L.; Hoos, H. H.; and Leyton-Brown, K. 2014. Algorithm runtime prediction: Methods & evaluation. Artifcial Intelligence, 206: 79–111.

If the feature request is approved, would you be willing to submit a PR?
Yes, unless someone else is eager enough to take this up before me :)

[thomaspinder]

Thanks @patel-zeel . I'd love to support a kernel such as this in JaxKern. Might I suggest holding off for a week or two on implementing this as we're currently refactoring the backend of JaxUtils which will mean all kernels need minor modifications.