Summary
This paper presents some theory and a method for reasoning about information gain in embedding space via a relaxation of conditional independence, as well as some theory on independence preserving embeddings.
As information gain is inherently linked to independence, the paper focuses on defining a generalization of the Markov boundary that is meaningful in embedding space. The Markov boundary is a set of embeddings that "separate" the target embedding from all other test embeddings not in the boundary. Concretely, this means the cosine similarity between the projection of the target and test embeddings onto the orthogonal complement of the generalized Markov boundary should be 0. The proposed generalization relaxes elementwise orthogonality to distributional orthogonality, where the cosine similarities between the projections are allowed to cancel out, rather than all be 0. This criterion is motivated by practical concerns, where embeddings are low-dimensional representations where orthogonal residuals are rare.
Finding a generalized Markov boundary for a single target embedding is then accomplished by sampling a number of random sets of embeddings, finding the top $K$ embeddings that contain information about the target given the random embedding sets, then constructing the boundary from within those top $K$ embeddings.
Separately, the paper addresses another question of how to embed a set of independence assumptions in a lower dimensional space. A theorem is presented that shows that one can preserve independence assumptions as residual orthogonality to some degree, depending on the dimension.
Experiments are presented, using CLIP embeddings, that show that generalized Markov boundaries can indeed be found, that projecting onto the orthogonal complement of the span random embeddings is meaningful, and that the discovered generalized Markov boundaries are more aligned with the span of embeddings of related words than unrelated.
Strengths
1. The first research question of reasoning about conditional independence and information gain in embedding space is appealing. Recent works in resolving ambiguity through dialogue, such as for image retrieval through 20 questions, reason over the space of individual images. However, if there are many images, this is not scalable. Intuitively, many of those images are likely to be very similar, motivating reasoning in the much lower dimensional CLIP embedding space.
2. The proposed definition of generalized Markov boundary and method for finding boundaries are reasonable.
3. The second research question about independence preserving embeddings is also worth studying for the same reason as above: potential applications would be very interesting.
Weaknesses
1. The method and experiments for the generalized Markov boundary only involve a single target embedding.
1. The experimental evaluation only evaluates token embeddings, whereas the text encoder in CLIP can encode sequences. An experiment involving reasoning over sequence embeddings would make the paper much stronger, especially if the experiment involved a realistic task.
1. No experiments are performed for independence preserving embeddings.
Questions
1. Primarily, I would like to see experiments verifying Theorem 13 on dimensionality reduction in independence preserving embeddings.
1. Is the only difference between kernel mean embeddings and independence preserving embeddings the choice of a kernel with finite dimensional feature map?
1. What is the relationship to work on information theory with kernel methods [2]?
1. A more realistic application that utilizes the method developed in the paper would greatly strengthen the paper. One possible application is an image retrieval game such as 20 questions [1], where the goal is to retrieve the correct image out of a set by asking questions.
[1] White, Julia, et al. "Open-domain clarification question generation without question examples." Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing. 2021.
[2] Francis Bach. Information Theory with Kernel Methods. 2022. ⟨hal-03577992v2⟩
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
I did not find a discussion of limitations.