Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The authors propose KITT, a novel method exploiting a transformer-based architecture to generate kernel recommendations. KITT has two main features: (1) agnostic to the length and dimensionality of the data; (2) it offers double permutation invariance. They demonstrate the effect of KITT on synthetic data compared with other baselines.
main_review: Originality: The kernel search problem is new for transformer-based architecture but it's not novel for kernel design. The authors just provide some prior kernel selections and select the result from them. I think one interesting part is Proposition 1 & 2. However, the main result is based on Zaheer et al. [33] and their Proposition can be seen as a direct extension.

Quality: I think the claim is intuitive and heuristic. For example, after defining a set of prior kernels, the authors apply addition and multiplication operations to generate more kernel candidates. The advantage is that the double permutation invariance is supported by their proof.

Clarity: In my view, the paper is not well organized and difficult to follow. For example, the contribution part in lines 36-47 is too scattered. Also, I think Section 3 is disordered: they use bold titles for each unparallel part. For instance, Encoder and Decoder should be the sub-part of Model Architecture.

Significance: The authors verify their KITT synthetic data and show its improvement compared with baselines. I am not sure about the improvement on the real-world data (like NLP dataset). 
limitations_and_societal_impact: The authors don't provide limitations of their work in the paper.

I mainly have the following concerns about the paper.
1. In my view, KITT apply an ensemble of tricks or technique together. Thus, an ablation study is important to illustrate the effect of different parts. For example, authors use a lot of places to describe heteroscedastic noise. I wonder what if we remove the noise and keep other parts the same.

2. As said in the Main Review part, all experiments are done on synthetic data, which is a simpler case in reality. Since Transformer is popular for NLP and CV tasks, can the authors show KITT on some small real-world data?
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a transformer-based neural network that can recommend appropriate kernels for Gaussian process regression. In the first step, the encoder uses a permutation-invariant version of multi-head self-attention to generate a representation of an entire dataset. This is further used by the decoder to recursively select a sequence of primitive kernels, which are then additively combined. The entire model is trained on a synthetic dataset consisting of samples drawn from GP priors with different kernels. Finally, the method is evaluated on a selection of regression datasets from the UCI repository in terms of prediction fit and runtime.
main_review: The paper provides valuable and---to the best of my knowledge---novel contributions to the field of Gaussian process kernel selection. Compared to the closely related work by Liu et al., KITT can also recommend non-stationary kernels. Compared to search-based methods, the computational overhead during test time is significantly reduced. The paper is generally well-written and easy to understand; however, the structure of the presentation can be improved. Please see the detailed comments below.
 
The key strength of the paper is that the model is trained entirely on synthetic data while still being able to select good kernels for previously unseen, real-world datasets. In my opinion, the authors should emphasize this fact much more, as it is never really mentioned explicitly in the paper.
 
Its main weakness is that the description of the method lacks vital details (for example, about the data generation process) or spreads them across several sections, making it hard to understand the procedure. Furthermore, the evaluation seems slightly unfinished and relatively weak compared to the literature. Please see the comments below for more details.
 
Overall, I do not see any significant issues with the paper, and I deem that the idea is interesting and useful. For now, I would still rate it slightly below the acceptance threshold due to the issues mentioned in the comments. However, I am confident that the authors can address my comments/questions during the discussion phase, and I would be happy to raise my score if that is the case.


# Questions/Detailed Comments 
* What training data was used for training the KITT network? That information is fragmented into several sections of the paper, the supplementary material and I even had to take a look at the code and related work (Liu et al.) to be completely sure. For example, the data generation process is only mentioned briefly in the paragraph about GP hyperparameter priors, the “training” paragraph states the dimensionality of the data, and the supplementary material contains the information that 200,000 samples are used in total. Why not compile this in a single paragraph about the training procedure? That would make the paper much easier to read and understand.
* It seems a bit odd to me that the AHGP model performs consistently worse than the simple RBF-ARD baseline, because, as you mentioned, the RBF kernel should be included in their formulation of the spectral mixture kernel. Were you able to reproduce results from the AHGP paper?
* How exactly does the “encoder-only” model mentioned in Fig. 4 work? I did not find this information anywhere in the paper. Is it perhaps the classification model from the ground truth recovery experiment and does it simply select a single primitive kernel expression from the vocabulary or a combination of the top-3 based on softmax values?
* Based on the experimental results, it seems that the encoder-only model’s performance is on par with the full model including the decoder. Is there any specific reason why you would ever want to use the decoder if the encoder-only model works just as well?
* The “Scalability” section (l. 232 ff.) feels a bit out of place. Its claims would need to be justified or you should at least provide references. In my opinion, the entire KITT pipeline also includes an $O(N^3)$ term as you optimize hyperparameters after the transformer suggests a suitable kernel, using the marginal likelihood gradient. I would suggest scrapping this section entirely and focusing on a more detailed empirical comparison of wall clock runtime instead, which is probably more relevant than asymptotic complexity for people who want to use your method anyway.
* Evaluation in the AHGP paper includes experiments in the domain of Bayesian optimization and Bayesian quadrature as well. It would be interesting to see how your methods performs for those tasks, but it is not strictly necessary in my opinion. However, your main selling point over the search-based methods is computational efficiency, so you should certainly include runtime comparisons for the UCI experiments or at least summarize the results and refer to the supplementary material. To make the comparison fair, I think that the KITT’s runtime should also include the optimization of hyperparameters.
* What is the effect of increasing/decreasing the maximal sequence length that the encoder is allowed to output? What happens if you allow products of more than two kernels. I only found the sentence “We use products of two primitive kernels as part of the base vocabulary and found that incorporating higher order products do not significantly change performance.” (l. 130 f.), but the supplementary material does not contain experimental results that support this statement.

## Minor:
* l. 57: “This quantity is available in closed-form for data modelled by Gaussian likelihoods.” You my want to explicitly state that “this” refers to the log marginal likelihood and not its global maximum to avoid confusion.
* Please cite published conference/journal papers instead of the arxiv version. E.g., Vaswani et. al was accepted at NIPS’17

## Typos:
* l. 122: “multiplying noise kernel” -> “multiplying a noise kernel”
* p. 5, fig. 2 caption: “heterescedastic” -> “heteroscedastic”
* l. 191: There is a footnote mark for the Set Attention Block, but the actual footnote does not seem to exist.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper presents a new approach to select kernel functions via transformers. The proposed approach mimics image captioning tasks where the model takes the pair of data covariates and targets as image inputs,and then produces kernel grammars as captions. The paper designs a transformer architecture in the way that it is invariant to permutations across input indices and input dimensions. 
main_review: Kernel selection is one of the important problems in learning Gaussian processes. And using the representation power of transformers is a very interesting idea. The method allows to train a transformer once and reuse many times to predict kernel structures  and therefore avoids exhausted search procedures like in the automatic statistician.

However, the technical contribution of this paper is limited. The double permutation invariance is obtained via a function composition of deep sets. Although experiments show promising results, the paper may need more ablation study to demonstrate the efficacy of the proposed method (please see below).

limitations_and_societal_impact: While experiments show promising results in medium-dimensional datasets, the paper may need to verify that the method should work for 1D datasets. Because it is easier to justify the quality of found kernels from plotting and visualization. A plot of kernel structure found by KITT for Mauna or airline passengers might be sufficient. One suggestion here is that the paper may follow the setup of the signal-to-noise experiment in [Duvenaud et al. 2013] to check if the method is sensitive to noise. 

Minors:
- The explanation of why AHGP performs worse than RBF is not clear. If RBF is the subset of Spectral Mixture (SM), SM is at least as good as RBF. And if AHGP really learned the lengthscale of the primary component, the paper should provide a way to demonstrate it.

- Missing related work on stochastic grammar using probabilistic programming. For example, https://arxiv.org/pdf/1611.07051.pdf 

Questions:

- The output of KITT is a sum of product kernels in which components are also commutative and order does not matter. Transformers for natural language generates sentences where the order or words within a sentence matters. Does it cause any difficulty to identify the kernel in KITT?

- What potential challenges may arise if data and kernel grammar includes change-point and change-window? 

- In Figure 3 (first), why does the increase in the number of test points result in better classification accuracy although the model trained on 64 points?

- Is automatic relevant determination (ARD) considered during sampling from priors? Is there a way to extend this work where kernel structures vary across input dimensions?

---- After rebuttal ----
Overall, the proposed approach for GP kernel selection is interesting. So I raised the score to 6. However, the paper representation can be improved. I hope the authors could add the discussion of 1-dimensional case to the paper as in the rebuttal.
review_title: null

Meta-review: The paper presents a new approach to select kernel functions via transformers. The proposed idea is interesting, and is a novel contribution to the field of Gaussian process and kernel selection with significantly reduced computational overhead during test time. Experimental results can be further strengthened by adding in more ablation studies. Moreover, organization and presentation can be improved.
Decision: Accept (Poster)