Uncovering Meanings of Embeddings via Partial Orthogonality
Authors: Yibo Jiang
Bryon Aragam
Victor Veitch
Venue: NeurIPS 2023 poster (2023)
Keywords: embedding
representation
graphical models
partial orthogonality
Markov boundary
TL;DR: We generalize the notion of Markov boundary to embedding space using partial orthogonality to uncover semantic meanings

Abstract: Machine learning tools often rely on embedding text as vectors of real numbers.
In this paper, we study how the semantic structure of language is encoded in the algebraic structure of such embeddings.
Specifically, we look at a notion of  "semantic independence" capturing the idea that, e.g., "eggplant" and "tomato" are independent given "vegetable". 
Although such examples are intuitive, it is difficult to formalize such a notion of semantic independence. The key observation here is that any sensible formalization should obey a set of so-called independence axioms, and thus any algebraic encoding of this structure should also obey these axioms. This leads us naturally to use partial orthogonality as the relevant algebraic structure. We develop theory and methods that allow us to demonstrate that partial orthogonality does indeed capture semantic independence.
Complementary to this, we also introduce the concept of independence preserving embeddings where embeddings preserve the conditional independence structures of a distribution, and we prove the existence of such embeddings and approximations to them.

Uncovering Meanings of Embeddings via Partial Orthogonality
Yibo Jiang', Bryon Aragam², and Victor Veitch
Department of Computer Science, University of Chicago Booth School of Business, University of Chicago
Department of Statistics, University of Chicago Data Science Institute, University of Chicago
Abstract
Machine learning tools often rely embedding text vectors of real numbers. In this paper, we study how the semantic structure of language is encoded the algebraic structure of such embeddings. Specifically, we look notion of "semantic independence" capturing the idea that, e.g., "eggplant" and "tomato" are independent given "vegetable". Although such examples intuitive, it is difficult to formalize such a notion of semantic independence. The key observation here is that any sensible formalization should obey set of so-called independence axioms, and thus any algebraic encoding of this structure should also obey these axioms. This leads naturally to use partial orthogonality as the relevant algebraic structure. We develop theory and methods that allow us to demonstrate that partial orthogonality does indeed capture semantic independence. Complementary to this, we also introduce the concept of independence preserving embeddings where embeddings preserve the conditional independence structures of distribution, and we prove the existence of such embeddings and approximations to them.
Introduction
This paper concerns the question of how semantic meaning is encoded in neural embeddings, such as those produced by [Rad+21]. There is strong empirical evidence that these embeddings- of real numbers-coe capture the semantic meaning of the underlying text. For example, classical results show that word embeddings can be used for analogical reasoning [c.g.. Mik+13; PSM14], and such embeddings are the backbone of modern generative AI systems [e.g.. Ram+22; Bub+23; Sah+22; Dev+18]. The high-level question we'r 're interested is: How is the semantic structure text encoded in the algebraic structure of embeddings? In this paper, we provide evidence that the concept of partial orthogonality plays a key role.
The first step is to identify the semantic structure of interest. Intuitively, words or phrases possess a notion of semantic independence, which does not have to be statistical in nature. For example, the word "eggplant" seems more similar to "tomato" than to "ennui". Yet, if we were to "condition" on the common property of "vegetable", then "eggplant" and "tomato" should be "independent" And, if we condition on both "vegetable" and "purple", then "eggplant" may be "independent" of all other words. However, is difficult to formalize what meant by "independent" and "condition on" in these informal statements. Accordingly, it is hard to establish formal definition of semantic independence, and thus is challenging to explore how this structure might be encoded algebraically!
The key observation in this paper is to recall that most reasonable concepts of "independence" adhere common of axioms similar those defining probabilistic conditional independence. Formally, this abstract idea is captured by the axioms of the so-called independence models [Lau96]. Thus,
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

0.30
Npct aer. P
0.31
Span Warden Drvioce
0.2
Saunce Pordaa
023
2:2
0.0
0.9
0:3
Narbir of humssar Namt
Rammtto TLanssen Phantio
(2) 'oggplant"
'zebra'
Figure 1: For target embedding of "eggplant", the set of embeddings that include "purple" and "vegetable" forms the subspace such that after projection, the residual of "eggplant" has the lowest cosine similarity with residuals of other test embeddings. This matches our intuition for the meaning "eggplant". Similarly, for target embedding of "zebra", the set of embeddings that include "striped" and "animal" forms the most suitable subspace.
semantic independence is encoded algebraically, it should be encoded as an algebraic structure that respects these axioms. In this paper, we use natural candidate independence model in vector spaces known as partial orthogonality [Lau96; AAZ22]. Here, for two vectors Va and iú and a conditioning set of vectors UC, partial orthogonality takes va independent 4b given ve if the residuals of Ua and db. are orthogonal after projecting onto the span of uc. We discover that this particular tool is indeed valuable for understanding CLIP embeddings. For instance, Figure shows that after projecting onto the linear subspace spanned by CLIP embeddings of "purple" and "vegetable" the residual of embedding "eggplant" has on average low cosine similarity with the residuals of random test embeddings, which also matches our intuitive understanding of the word.
Since partial orthogonality is an independence model, we can go one step further to define Markov boundaries for embeddings as well. Drawing inspiration from graphical models, is reasonable to expect that the Markov boundary of any target embedding should constitute a minimal collection of embeddings that encompasses valuable information regarding the target. Unlike classical applications of partial orthogonality in regression and Gaussian models, however, the geometry of embeddings presents several subtle technical challenges to directly adopting the usual notion of Markov boundary. First, the intersection axiom never holds for practical embeddings, which makes the standard Markov boundary non-unique. More importantly, practical embeddings could potentially incorporate distor- tion, noise and undergo phenomena resembling superposition [Elh+22]. Therefore, in this paper, introduce generalized Markov boundaries for studying the structure of text embeddings.
Contributions Specifically, we make the following contributions:
We adapt ideas from graphical independence models to specify the structure that should be satisfied by semantic independence. We discover that partial orthogonality in the embedding space offers a natural way of encoding semantic independence structure (Section 2).
2. We study the semantic structure of partial orthogonality via Markov boundaries. Due the unique characteristics of embeddings and noise in learning, exact orthogonality is unlikely hold. So, we give a distributional relaxation of the Markov boundary and use this to provide a practical algorithm for finding generalized Markov boundaries and measuring the semantic independence induced by generalized Markov boundaries (Section 3.2).
3. We introduce the concept of independence preserving embeddings, which studies how embeddings can be used to maintain the independence structure of distributions. This holds its intrigue for further research (Section 4).
4. Finally, we design and conduct experimental evaluations on CLIP text embeddings, finding that the partial orthogonality structure and generalized Markov boundary encode semantic structure (Section 5).
Throughout, we use CLIP text embeddings as a running example, though the method and theory presented can be applicd more broadly.
2

---

Related work There are many papers [e.g,, Aro+16; GAM17; AH19; EDH19; Tra+23; Per+23; Lee+23; MEP23; Wan+23] connecting semantic meanings and algebraic structures of popular embeddings like CLIP [Rad+21]. Glove [PSM14] and word2vec [Mik+13]. Simple arithmetic on these embeddings reveals that they carry semantic meanings. The most popular arithmetic operation is called linear analogy [. There are several papers trying to understand the reasoning behind this phenomenon. Arora et al. [Aro+16]] explains this by proposing the latent variable model but requires the word vectors to be uniformly distributed in the embedding space which generally is not true practice [MT17]. Alternatively, [GAM17; AH19] adopts the paraphrase model that also does not fit practice. [HDH19], on the other hand, studies the geometry of embeddings that decomposes the shifted pointwise mutual information (PMI) matrix. Trager et al. [Tra+23] and Perera et al. [Per+23] decomposes embeddings into combinations of smaller set of vectors that more interpretable. On the other hand, similar to using vector orthogonality to represent (conditional) independence, kernel mean embeddings [Mua+17] Hilbert space embeddings of distributions that can also be used to represent conditional independences [Son+09; SFG13J. is a popular method for machine learning, and causal inference [Gre+05; Moo+09; GS20J. But unlike independence preserving embeddings, kernel mean embeddings use the kernel and do not explicitly construct finite-dimensional vector representations.
2 Independence Model and Markov Boundary
Let E' be a finite set of embeddings with E n and each embedding is of size d. Every embedding vector representation of a word. other words, there exists a function f that maps words vectors in R. As explained above, we might expect embeddings to encode "independence structures" between words. These independence structures are difficult define formally, though the structure is similar to that of probabilistic conditional independence. We will use independence models as an abstract formalization of this structure.
2.1 Independence Model
Throughout this paper, we use many standard definitions and facts about graphical models and more generally, abstract independence models. A detailed overview of this material can be found, for instance, in [Lau96; StuO5].
Suppose V is finite set. In the of embeddings, V would be set of vectors. An independence model L, is a ternary relation on V. Let A, B, C, D be disjoint subsets of V. Then a semi aemi-graphoid an independence model that satisfies the following axioms:
(A1) (Symmetry)
II BJC, then B 1 A/C:
(A2) (Decomposition) If ( U D)JC, then A 1 B and I DIC: (A3) (Weak Union) If A L D) then A l. B|U D):
(A4) (Contraction) If A IL, BJC and A L. DI(B U C), then A I. (B D)JCC.
The independence model a graphoid it also satisfies
(A5) (Intersection) If A JL, BI(CUD D) and A L. C D), then A ALL
And, the graphoid called compositional graphoid if also satisfiss
(A6) (Composition) If A I, B|C and A 1,, DIC, then A L.
We also use IVVV) be the set of conditional independent tuples under the independence model 1 1.. In other words, if (A, B, C* (V), then A 1,, BJC where A, B, C are disjoint subsets of V.
Probabilistic Conditional Independence (Lp) Given finite set of random variables V. prob- abilistic conditional independence over V defines an independence model that satisfies (A1)-(A4) which means that probabilistic independence models are semi-graphoids. are not compositional graphoids. If the distribution has strictly positive density w.r.t. product mea- sure, then the intersection axiom is true. this case, probabilistic independence models are graphoids. Still, in general, the composition axiom is not satisfied because pairwise independence does not imply
general, however, they
3

---

joint independence. One notable exception is when the distribution is regular multivariate Gaussian; then the probabilistic independence model is compositional graphoid.
Undirected Graph Separations (Lc)) For finite undirected graph G = (V, E). One can easily show that ordinary graph separation undirected graphs compositional graphoid. The rela- tions between probabilistic conditional independences and graph separations are well-studied in the graphical modeling literature [KP09; Lau96]. We recall a few important definitions here for completeness. Consider a natural bijection between graphical nodes and random variables. Then if (V) S [V))), we say the distribution P over V satisfies the Markov property with respect to and 9 is called an I-map of P. An I-map G for P is minimal if no subgraph of G is also an I-map of P. It not difficult to show that there exists a minimal I-map for any distribution
Remark Not every compositional graphoid can be represented by an undirected graph. Sadeghi [Sad17] provides sufficient and necessary conditions for this.
Partial Orthogonality (Lo) Let V be finite collection of vectors in Rd. If e V,b e and C' S V, then we say that a and b are partially orthogonal given C' if
Lo blC + (projčla), proj [b]> = =0,
where projela] a proje(a] is the residual of after projection onto the span of C. It is not hard to verify that oo is semi-graphoid that also satisfies the composition axiom (A6). When V is set of linearly independent vectors, then o satisfies (A5) and thus is a compositional graphoid. Partial orthogonality has been studied under different names in the statistics literature for many decades. For example, if we replace Euclidean space with the T,2 space of random variables, partial orthogonality is equivalent to the well-known concept of partial correlation or second-order independence (Example 2.26 in [Lau20]). The concept of geometric orthogonality (Example 2.27 in [Lau20]) is closely related but does not always satisfy the intersection axiom. More recently, the concept of partial orthogonality
abstract Hilbert spaces was defined and studied extensively in [AAZ22]. Finally, when V is linearly independent collection of vectors, partial orthogonality yields a stronger independence model known as a Gaussoid, which is well-studied [e.g. LM07; BK19, and the references therein]. It is worth emphasizing that in the present setting of text embedding, typically have d < n, and hence V cannot be linearly independent.
2.2 Markoy boundaries
Suppose L,, is an independence model over finite set V. Let be element in V. then the Markov blanket M of U; is any subset of V \ {ee such that
1 Lo V MM
Markov boundary a minimal Markov blanket.
A Markov boundary, by definition, always exists and can be an empty set. However, it might not be unique. It is well-known that the intersection property is sufficient condition to guarantee Markov boundaries are unique. Thus, the Markov boundary is unique in any graphoid. The proof is presented here for completeness.
Theorem 2. If La is graphoid over V, then the Markov boundary is unique for any element in V.
Proof. Let ii V. Suppose v has two distinct Markov boundaries Mj, M2. Then they must be non-empty and o; LoMMM M1. L. M2, v; Lo M2 Mi, &; Mi [Mg. By the intersection axiom, U; N. Mi UM1 Then by the decomposition axiom, 0; L. Mi and 0; Lo M2 which is a contradiction.
Remark 3.
For any semi-graphoid, the intersection property is not necessary condition for the uniqueness of Markov boundaries. See Remark I in [WW20].
The connection between orthogonal projection and graphoid axioms is well-known [Lau96; Daw01; Whi09]. But graphoid axioms find their primary applications in graphical models [Lau96]. In particular, there are many existing papers on Markov boundary discovery for graphical models [Tsa+03; Ali+ 10; SV16; GA21; TAS03; Pen+07]. They typically assume faithfulness or the

---

distributions are strictly positive, which are sufficient conditions for the intersection property and thus ensure unique Markoy boundaries. As an important axiom for graphoids. the intersection property has also been thoroughly investigated [SMMRO5; Pet15; Finl But the intersection property rarely holds for embeddings (See Section 3), which means there could be multiple Markov boundaries. (SLA13; WW20] study this case for graphical models and causal inference.
3 Markov Boundary of Embeddings
As indicated in Section 2, partial orthogonality (1o) can be used as an independence model over can use partial orthogo-
vectors in Euclidean space and is compositional semi-graphoid. Thus, nality to study embeddings, which are real vectors. When n Σ d and the vectors in E are linearly independent, every vector in E has unique Markov boundary by Theorem 2.
Unfortunately, when d < n, which happens in practice with embeddings as there are usually more objects to embed than the embedding dimension, there is a possibility of having multiple Markov boundaries. In fact, the main challenge with Markov boundary discovery for embeddings is that the intersection property generally does not hold, as opposed to graphical models where this property is commonly assumed [Tsa++3;; Ali+ 10; SV16).
While the Markov boundary might not be unique, the following theorem says that all Markoy boundaries of the target vector capture the same "information" about that vector.
Theorem 4. Let partial orthogonality to be the independence model over a finite set of embedding vectors E. Suppose MI, M2 are two distinct Markov boundaries of 0h E E, then,
proj [0a] = proj
When d & n, then it is likely that the target embedding ia lies in the linear span of other embeddings (i.e, vi E span(E {e;))), Corollary 5 below shows that, in this case, the span of any Markov boundary is precisely the subspace that contains ey:
Corollary 5. Lel parital orthogonality Lo be the independence model over a finite set of embedding vectors E. Suppose Mi E is a Markov boundary of 0g E E and tq E span(E (v;)). then,
proj [us] =. Us.
In other words, to find a Markov boundary of Us we need find some vectors such that their linear combination is exactly U. This seems very strict but is necessary because the formal definition of the Markov boundary requires residual orthogonalities between v; and every other vector. In the sequel, we show how to relax the definition of the Markov boundary.
3.1 From Elementwise Orthogonality to Distributional Orthogonality
Corollary 5 suggests that the span of the Markov boundary for any target vector should contain that target vector. This is a consequence of the elementwise orthogonality constraint because the definition of the Markov boundary requires the residual of target vector be orthogonal to the residual of any test vector. The implicit assumption here that embeddings are distortion-fie free and every non-zero correlation is meaningful. However, due to the inherent limitation of the embedding dimension-which often restricts the available space for storing all the orthogonal vectors-ann and noises introduced from training, embeddings relatively small Fuclidean space. In fact, we empirically show in Section 5.2 that inner products in embedding space do not necessarily respect semantic meanings faithfully. Therefore, the notion of elementwise orthogonality loses practical significance.
likely prone to distortion when compressed into
Instead of enforcing elementwise orthogonality, we relax the definition of the Markov boundary of embeddings such that intuitively, after projection, the residual of the target vector and the residuals of test vectors should be orthogonal in distributional sense where the distribution is the empirical distribution over test vectors. To capture distributional orthogonalities, this paper focuses on the average of cosine similarities.
In particular, we have the following definition of generalized Markov boundary for partial orthogo-
nality.
5

---

Algorithm 1: Approximate Algorithm to Find Generalized Markov Boundary
Input: E.
** is the set of all embeddings and v E E is the target embedding Input: Byy, d,, K
*/
/* Ry is the number of sampled random subspaces, d, is the number of sampled vectors for each random subspace and K is the number candidate vectors to construct generalized Markov boundary Output: M E
/* M is the estimated generalized Markov boundary for
for i + 1 to n, do
randomly sample set of d, vectors M, = (o/) S (E caculate S M. (U, u) for all a E (E)(
end
Find the top K vectors {u, with the highest (U, Find the subset M of {u, that has the lowest E),
Result: M
Definition 6 (Generalized Markov Boundary for Partial Orthogonality). Given a finite set E of embedding vectors. Let e be an element in E, then a generalized Markov boundary M of v is minimal subset of E (v) such that
S)
Σ MEF
S (), =0
E
where S MMM u) is the cosine similarity of and v after projection and E = (X((v) M.)
Specifically, S MM, u) = Dirro Ielll (pre) [+]ll
(proj [v) proj wo [u])
Intuitively, this suggests that, on average. there is no particular direction of residuals that have nontrivial correlations with the residual of the target embedding.
Remark 7. It is evident that the conventional definition of Markov boundary implies Definition 6 (Lemma 15 in Appendix A).
3.2 Finding Generalized Markov Boundary
With formal definition of the generalized Markov boundary established, our objective is now to identify this boundary. One can always use brute force by enumerating all possible subsets E, but the algorithm would be infeasible when E is large.
Suppose E. is target vector and M is its generalized Markov boundary, then [ Intuitively, Definition 6 suggests that
write
tu dn where ti pr [u] and ln the residual of test vectors can appear in any direction relative to ti Therefore, if one samples random test vectors {u,). ). their span is likely to be close V In other words, the residual of e after projection onto span( {w should contain more information about the generalized Markov boundary direction U/|-
This motivates the approximate method Algorithm 1. For any target embedding v. one first sample subspaces spanned by randomly selected embeddings. Embeddings that, average have high cosine similarities with the target embedding after projecting onto orthogonal complements of previously sampled random subspaces, are considered to be candidates for the generalized Markov boundary. The final selection of generalized Markov boundary searches over these top K candidates.
Empirically, for text embedding models like CLIP, random projections prove to be advantageous in revealing semantically related concepts. Section 5.2, we provide several examples where, for given target embedding, the embeddings that exhibit high correlation after random projections are more semantically meaningful compared to embeddings with merely high cosine similarity with the target embedding before projections.

---

Independence Preserving Embeddings (IPE)
In the previous sections, discussed the Markov boundary of embeddings under the partial orthog- onality independence model. In Section 5, we will test its effectiveness at capturing the "semantic independence structure" through experiments conducted CLIP text embeddings. The belief is that the linear algebraic structure possesses the capacity to uphold the independence structure of semantic meanings.
natural question to ask is: Is it always possible to use vector space embeddings to preserve independence structures of interest? In this section, we study the case for random variables. Consider an embedding function f that maps a random variable X to f(X) E R Ideally, it is desirable for mirror the conditional independences present in the
the partial orthogonalities of embeddings joint distribution of X. We call such representations independence preserving embeddings (IPE) (Definition 8). In this section, delve into the theoretical feasibility of these embeddings by initially demonstrating the construction IPE and then showing how one can use random projection to reduce the dimension of IPE. We believe that studying IPE lays the theoretical foundation to understand embedding models in general.
Definition 8 (Independence Preserving Embedding Map). Let V be finite set of random variables with distribution P. A function f V Rd is called an independence preserving embedding map (IPE map) if
Io(J(V)) Iv(V).
An IPE map is called a faithful IPE map if
Io(((V)
4.1 Existence and Universality of IPE Maps
We first show that for any distribution P over random variables V, we can construct an IPE map.
For any distribution P over V. there exists minimal I-map G = (V, E) such that [V((V S Ip(V) (See Section 2). We will use Gp to be minimal I-map of P and adj(Gp) to be the adjacency matrix of Gp. We further define adj. (G)) to be an adjusted adjacency matrix with E IR where
adj_(Pp) = + pd)((p)
and 1l is the identity matrix.
Ideally, this matrix is invertible, however, it turns that not every E produces an invertible (9)). We therefore define the following perfect perturbation factor. For any matrix A E R=*= define Ar.J be the submatrix of A with row and column indices from I and J. respectively. If J. the submatrix is called a principal submatrix and we denote it simply as Az.
(V, where [V] i called perfect perturbation factor if (1) adj (G p) is invertible and (2) for any I S [m], (adj, (GP)z), 0 if and only if vz, 1G vz Ko k & I} where I2 is the ith element of I.
Definition 9 (Perfect Perturbation Factor). For given graph
Theorem 10. Let V be a finite set of random variables with distribution P. 9p is minimal T-map of P. Let A be equal to adj.(G)) (g with eigen decomposition = UEUT. If & is a perfect perturbation factor, then the function f with
f(v.) = U,E1/2
is an IPE map of P where vn is a random variable in V and U4 is the i-th row U.. U. Furthermore, if P is faithful to Gp, then f is a faithfil IPE map for P.
Remark 11. One can always normalize these embeddings to have unit norms without changing the
partial orthogonality structures.
Finding a perfect perturbation factor might seem daunting, but the following lemma, which is a direct consequence Theorem I in Lněnička and Matúš [LM07], shows that almost every is perfect perturbation factor.
Lemma 12. For any simple graph G, is perfect for all but finitely many R.
7

---

4.2 Dimension Reduction of IPE
Theorem 10 shows how to learn a perfect IPE but it requires the dimension of embeddings to be the same as the number of variables in V. In the worst case, this inevitable for faithful IPE map: If the random variables in V are mutually independent, then we need at least [V] dimensions in the embedding space to contain V orthogonal vectors.
But this not practical. Suppose we want to embed millions of random variables (e.g. tokens) in a vector space, having the dimension of each embedding be in the magnitude of millions is less than ideal. Therefore, one needs to do dimension reduction.
In this section, we show that by using random projection, the partial orthogonalities induced by Markov boundaries are preserved approximately. Intuitively, this is guaranteed by the Johnson- Lindenstrauss lemma [Vem05].
Theorem 13. Let U be of vectors in TR where U| and every vector is unit vector Let E be a matrix in RRxx where Eij = (Uz Uz). Assume A1 = Amin (X) > O. Then there exists a mapping 9. RR" + R where & = (o0g(2))((E))) with e' m E/ X1 /2/2r2]
and E E (0. 1) such that for any us U with its unique Markov boundary M; U and any uj E U \ ({u) U M.), have
proig(m,)lou (ro proig( SE
where r, [M]. max; M.] and C (r- + () 2Amas (E) (2)+2(++1)))
Awin
Theorem 13 shows that as long as the partial orthogonality structure of embeddings is sparse in the sense that the size of the Markov boundary for each embedding small. Then one can reduce the dimension of the embedding and the residuals of target and test vectors after projection onto the Markov boundary are almost orthogonal.
Remark 14. The assumption in Theorem 13 is satisfied by the construction of IPE in Section 4.1.
Experiments
One of the central hypotheses of the paper is that the partial orthogonality of embeddings, and its byproduct generalized Markov boundary, carry semantic information. To verify this claim, we provide both quantitative and qualitative experiments. Throughout this section, consider the set of normalized embeddings E that represent the 49815 words in the Brown corpus [FK79]. For each target embedding of word, under any experiment setting, embeddings have 0.9 or above cosine similarities with the target embedding, or words, whose Wu- Palmer similarity measure with the target word is almost 1, The purpose of this filtering step is to prevent the inclusion of synonyms.
automatically filter words, whose
5.1 Semantic Structure of Partial Orthogonality
To examine the rule of partial orthogonality, nine categories are chosen, each with 10 words in (See Table 3 in Appendix B). Specifically, each word within given category is hyponym for that category in WordNet [Mi195]. We assess how much, on average, the cosine similarities between words within each category decrease when conditioned on these different nine categories. By conditioning. we use the clip embedding of the category word of interest and project out the subspace of that clip embedding. The results are shown in Figure We normalize reduction values by sampling 10,000 embeddings and calculating the mean and standard deviation of cosine reductions between these embeddings. is apparent that on average, cosine similarities of cara-category words decrease more than inter-category words. One interesting finding is that when conditioned on the category word "food", the average similarities between word pairs in "beverage" also drop considerably. We suspect this is because one synset of "food" is also hypernom of "beverage". Although words in the "food" category are chosen to mean solid food, could also mean nutrient which also encompasses the meaning of "beverage".

---

Hatter open donbnbbedrgg
Namber Fandor Parts
Figure 2: Experiments show conditioning the category word, cosine similarities ctta-cat words decrease more than inter-category words. Each row shows the (normalized) average cosine similarities reduction between words within each category when conditioned the category word of that row.
Figure 3: Experiments show that learned general- ized Markov boundaries have on average smaller principal angles with the description embedding compared subspaces spanned by randomly se- lected embeddings. The standard errors are over 50 examples.
5.2 Sampling Random Subspaces
The first step of Algorithm embeddings even after projecting onto orthogonal complements of subspaces spanned by randomly selected embeddings. It turns out that this step can reveal semantic meanings. In this section, we design experiments to show both quantitatively and qualitatively that embeddings of words that remain highly correlated with the target embedding after projection are semantically closer to the target word. In various experimental configurations, we employ 10 sets of 50 randomly chosen embeddings to form random projection subspaces for each target embedding. Qualitatively, Table in Appendix B gives few examples showing that the words that average remain highly correlated with the target word tend to possess greater semantic significance. Quantitatively, we calculate the average Wu-Palmer similarities between target words and the top 10 correlated words before and after random projections. We conduct experiments on 1000 random words as well as 300 common nouns provided by ChatGPT. The results are shown in Table 4 verify claims. This set of experiments also indirectly shows that the embeddings are noisy and that generalized Markov boundaries are indeed needed.
to find embeddings that have high similarities with the target
Table 1: Experiments show that the top 10 words that have, on average, high correlations with target words after projecting onto the orthogonal complements of randomly selected lincar subspaces have higher Wu- Palmer similarities with the target words than the top 10 highly correlated words without projections. This table contains average Wu-Palmes similarities with standard errors.
Target
Before Projection
After Projection
Random Words
0.223 0.006
0.245 + 0.007
Common Nouns
0.343 + 0.008
0.422 + 0.008
5.3 Generalized Markov Boundaries
We first demonstrate that Algorithm can find generalized Markov boundaries. The experiments are run over 1000 randomly selected words. In particular, Table 2 shows that with a relatively small candidate set, the algorithm can already approximate generalized Markov boundaries well, suggesting that the size of generalized Markov boundaríes for CLIP text embeddings should be small.
Semantic Meanings of Markov Boundaries
The estimated generalized Markov boundaries re- turned by Algorithm a set of embeddings. is reasonable to anticipate that the linear spans of these embeddings hold semantic meanings. To evaluate this hypothesis, we propose to calculate the smallest principal angles [KA02] between the span of generalized Markoy boundaries and the span of selected embeddings that are meaningful to the target word.

---

We again conducted both quantitative and qualitative experiments. Qualitatively, Figure in Ap- pendix B give few examples comparing target words' generalized Markov boundaries with the span of selected embeddings. For instance, the generalized Markov boundary of "car' is more aligned with the subspace spanned by embeddings of 'road' and "vehicle" than the span of "sea" and 'boat' and randomly selected subspaces. This suggests that the estimated generalized Markov boundaries hold semantic significance. To verify this quantitatively, we ask ChatGPT to provide a list of common nouns with short descriptions (selected examples are provided in Table 5). We then use CLIP text em- bedding to convert the description sentence into one vector and compare the smallest angle between the description vector with generalized Markov boundaries and random linear spans. Figure 3 shows that the generalized Markov boundaries are more semantically meaningful than random subspaces.
Table 2: With relatively small number of K, the average SM (v, E) is small. The standard errors are over 1000 experiments.
K
8
10
AVERAGE (M(
0.34510.03
0. 0.00030.03
0.05411.002
0.015
0.008.10.001
6
Conclusion
This paper studies the role of partial orthogonality in analyzing embeddings. Specifically, we extend the idea of Markov boundaries to embedding space. Unlike Markov boundaries in graphical models, the boundaries for embeddings are not guaranteed to be unique. We propose alternative relaxed definitions of Markov boundaries for practical use. Empirically, these tools prove to useful in finding the semantic meanings of embeddings. We also introduce the concept of independence preserving embeddings where embeddings use partial orthogonalities to preserve the conditional independence structures of random variables. This opens the door for substantial future work. In particular, one promising theoretical direction is to study if CLIP text embeddings preserve the structures in the training distributions.
7 Acknowledgments
This work is supported by ONR grant N00014-23-1-2591, Open Philanthropy, NSF IIS-1956330 NIH R01GM14046) and the Robert H. Topel Faculty Research Fund at the University of Chicago Booth School of Business.
References
[Ali+10]
C. F. Aliferis, A. Statnikov, I. Tsamardinos, S. Mani, and X. D. Koutsoukos. "Local causal and markov blanket induction for causal discovery and feature selection for classification part i: algorithms and empirical evaluation." In: Journal of Machine Learning Research (2010).
[AH19]
C. Allen and T. Hospedales. "Analogies explained: towards understanding word em- beddings". In: International Conference on Machine Learning. PMLR. 2019.
[AAZ22]
A. A. Amini, B. Aragam, and Q. Zhou. "A non non-graphical representation of conditional independence via the neighbourhood lattice". In: arXiv preprint arXiv:2206.05822 (2022).
[Aro+16]
Arora, Y. Li, Y. Liang, Ma, and A. Risteski. "A latent variable model approach to pmi-based word embeddings". In: Transactions of the Association for Computational Linguistics (2016).
[BK19]
T. Boege and T. Kahle, "Construction methods for gaussoids". In: arXiv preprint arXiv: 1902. 1260 (2019).
[Bub+23]
S. Bubeck, V. Chandrasekaran, R. Eldan, J. Gehrke, E. Horvitz, E. Kamar, P. Lee, Y. T. Lee, Y. Li, S. Lundberg, et al. "Sparks of artificial general intelligence: early experiments with gpt-4". In: arXiv preprint arXiv:2303.122 12712 (2023).
10

---

[Daw01]
A. P. Dawid. "Separoids: a mathematical framework for conditional independence and irrelevance". In: Annals of Mathematics and Artificial Intelligence (2001).
[Dev+18]
Devlin, M.-W. Chang, K. Lee, and Toutanova. "Bert: pre-training of deep bidirec- tional transformers for language understanding". In: arXiv preprint arXiv:1810.00m 04805 (2018).
[Elh+22]
N. Elhage, T. Hume, C. Olsson, N. Schiefer, T. Henighan, S. Kravec, Z. Hatfield-Dodds, R. Lasenby, D. Drain, C. Chen, Grosse, S. McCandlish, J. Kaplan, D. Amodei, M. Wattenberg, and C. Olah. "Toy models of superposition". In: Transformer Circuits Thread (2022).
[EDH19]
K. Ethayarajh, D. Duvenaud, and G. Hirst. Towards Understanding Linear Word Analogies. 2019.
[Fin11]
A. Fink. "The binomial ideal of the intersection axiom for conditional probabilities".
In: Journal of Algebruic Combinatorics (2011). 1).
[FK79]
W. N. Francis and H. Kucera. "Brown corpus manual". In: Letters to the Editor 2 (1979).
[GA21]
M. Gao and B. Aragam. "Efficient bayesian network structure learning via local markov boundary search". In: Advances in Neural Information Processing Systems (2021). A. Gittens, D. Achlioptas, and M. W. Mahoney. "Skip-gram: zipf+ uniform= vec- tor additivity". In: Proceedings of the 55th Anmual Meeting of the Association for Computational Linguistics (Volume Long Papers). 2017.
[GAM17]
[GS20]
D. Greenfeld and U. Shalit, "Robust learning with the hilbert-schmidt independence criterion". In: International Conference on Machine Learning. PMLR. 2020.
[Gre+05]
A. Gretton, O. Bousquet, A. Smola, and B. Schölkopf. "Measuring statistical depen- dence with hilbert-schmidt norms". In: Algorithmic Learning Theory: 16th Interna- tional Conference, ALT 2005, Singapore, October 8- 2005. Proceedings 16. Springer. 2005.
[HJ12]
R. A. Hor and C. R. Johnson. Matrix analysis. 2012.
[IR08]
C. Ipsen and R. Rehman. "Perturbation bounds for determinants and characteristic polynomials". In: SIAM Journal on Matrix Analysis and Applications 2 (2008).
[KA02]
A. V. Knyazev and M. E. Argentati. "Principal angles between subspaces in an a-based
scalar product: algorithms and perturbation estimates". In: SIAM Journal on Scientific Computing 6 (2002).
[KF09]
D. Koller and N. Friedman. Probabilistic graphical models: principles and techniques. 2009.
[Lau96]
S. L. Lauritzen. Graphical models. 1996.
[Lau20]
S. L. Lauritzen. Lectures on graphical models. 2020.
[Lec+23]
T. Leemann, M. Kirchhof, Y. Rong, E. Kasneci, and G. Kasneci. "When post-hoc conceptual explanations identifiable?" In: Uncertainty in Artificial Intelligence. PMLR. 2023.
[LM07]
R. Lněnička and F. Matúš. "On gaussian conditional independence structures". In: Kybernetika 3 (2007).
[MEP23]
J. Merullo, C. Fickhoff, and F. Pavlick. "Language models implement simple word2vec- style vector arithmetic". In: arXiv preprint arXiv:2305. 16130 (2023).
[Mik+13]
T. Mikolov, K. Chen, G. Corrado, and J. Dean. "Efficient estimation of word represen- tations in vector space", In: arXiv preprint arXiv: /301.378/7 (2013).
[Mi195]
G. A. Miller. "Wordnet: a lexical database for english". In: Commun. ACM 11 (1995).
[MT17]
D. Mimno and L. Thompson. "The strange geometry skip-gram with negative sampling". In: Empirical Methods in Natural Language Processing. 2017.
[Moo+09]
J. Mooij, D. Janzing, J. Peters, and B. Schölkopf. "Regression by dependence minimiza- tion and its application to causal inference in additive noise models". In: Proceedings of the 26th annual international conference on machine learning. 2009.
[Mua+17]
K. Muandet, K. Fukumizu, B. Sriperumbudur, B. Schölkopf, et al. "Kernel mean embedding of distributions: review and beyond". In: Foundations and Trends@ in Machine Learning 1-2 (2017).

---

[Pen+07]
J. M. Pena, R. Nilsson, J. Björkegren, and J. Tegnér. "Towards scalable and data efficient learning of markov boundaries". In: International Journal of Approximate Reasoning 2 (2007).
[PSM14]
J. Pennington, R. Socher, and C. D. Manning. "Glove: global vectors for word repre- sentation". In: Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). 2014.
[Per+23]
P. Perera, M. Trager, L. Zancato, A. Achille, and S. Soatto. "Prompt algebra for task composition". In: arXiv preprint arXiv:2306. 00310 (2023).
[Pet15]
J. Peters. "On the intersection property of conditional independence and its application to causal discovery". In: Journal of Causal Inference (2015).
[Rad+21]
A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry. A. Askell, P. Mishkin, J. Clark, G. Krueger, and I. Sutskever. Learning Transferable Visual Models From Natural Language Supervision. 2021.
[Ram+22]
A. Ramesh, P. Dhariwal, A. Nichol, C. Chu, and M. Chen. "Hierarchical text- conditional image generation with clip latents". In: arXiv preprint wxxiv2204.06122 (2022).
[Sad17]
K. Sadeghi. "Faithfulness of probability distributions and graphs". In: Journal of Machine Learning Research 148 (2017).
[Sah+22]
C. Saharia, W. Chan, S. Saxena, L. Li, J. Whang, E. L. Denton, K. Ghasemipour, R. Gontijo Lopes, B. Karagol Ayan, T. Salimans, et al. "Photorealistic text-to-image diffu- sion models with deep language understanding". In: Advances in Neural Information Processing Systems (2022).
[SMMR05]
E. San Martin, M. Mouchart, and J.-M. Rolin. "Ignorable common information, null sets and basu's s first theorem". In: Sankhyā: The Indian Journal of Statistics (2005). L. Song, K. Fukumizu, and A. Gretton. "Kernel embeddings of conditional distributions: unified kernel framework for nonparametric inference in graphical models". In: IEEE Signal Processing Magazine 4 (2013).
[SFG13]
[Son+09]
L. Song, Huang, A. Smola, and K. Fukumizu. "Hilbert space embeddings condi- tional distributions with applications to dynamical systems". In: Proceedings of the 26th Annual International Conference on Machine Learning. 2009.
[SLA13]
A. Statnikov, J. Lemeir, and C. F. Aliferis. "Algorithms for discovery of multiple markov boundaries". In: The Journal of Machine Learning Research (2013).
[SV16]
E. Strobl and S. Visweswaran. "Markov boundary discovery with ridge regularized linear models". In: Journal of Causal inference 1 (2016).
[Stu05]
M. Studený. Probabilistic conditional independence structures. 2005.
[Tra+23]
M. Trager, P. Perera, I.. Zancato, A. Achille, P. Bhatia, and S. Soatto. "Linear spaces of meanings: compositional structures in lision-anguage models". In: Proceedings of the IEEE/CVF International Conference on Computer Vision. 2023.
[TAS03]
Tsamardinos, C. F. Aliferis, and A. Statnikov. "Time and sample efficient discovery of markov blankets and direct causal relations". In: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. 2003. Tsamardinos, C. F. Aliferis, A. R. Statnikov, and E. Statnikov. "Algorithms for large scale markov blanket discovery." " In: FLAIRS conference. St. Augustine, FL. 2003.
[Tsa+03]
[Vem05]
S. S. Vempala. "The random projection method". In: DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 2005.
[WW20]
Y. Wang and L. Wang. "Causal inference in degenerate systems: impossibility result". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2020.
[Wan+23]
Z. Wang, L. Gui, J. Negrea, and Veitch. Concept Algebra for -oore-Based Condi- tional Models. 2023.
[Whi09]
J. Whittaker. Graphical models in applied multivariate statistics. 2009.
12

---

A
Additional Proofs
Lemma 15. Let be an element in E, and M a Markov boundary u, then M also a generalized Markov boundary.
Proof. By definition, for any E (N M(C, = 0. Therefore, M is also generalized Markov boundary.
Theorem 4.
Let partial orthogonality Lo be the independence model over a finite set of embedding vectors E. Suppose M2 C. are two distinct Markov boundaries of 04 E E, then,
proj [us] = =proj [
Proof. To slightly abuse notation, we also use Mi to be matrix where each column is element in Mi. We define M2 similarly.
Because M1 and M2 are two distinct Markov boundaries, they must not be empty. Therefore, vs Lo M₁ and v; oo M2. By the definition of Markov boundary, we also have or Lo M1 MM and e; Lo M2 M1. Note that M2 and M₁ must have full rank, otherwise, they are not minimal.
Thus,
(projtu, [rz], projte, [1y]) = 0, Vuz E M2
= (projtn, [ov]: Uÿ) 0, Voy E M2
= of Mi(M} [n)-MM Uj = = U3 Vo, E MM2
= of MI(M} M1) MI M2 = = M2
With (compact) singular value decomposition, we have Mi = UVE, and Mr = U2E2V Then,
of Mi MI) M M₂ u/ UP M₂ of M₂
uن U,U U2
Similarly,
of UU = Un
Therefore,
.TU;UTUVU o U2U
In other words,
proj (proj [v:]] = proj [us]
On the other hand, v Lo Mi.
proj (ad) U.UF 0/ #0
Similarly,
proj [ia] = U2U22 0u #0
Therefore, we must have,
proj [ui] span(MM2)
which means,
proj Sproj M, [bv]] = proj [vi] proj [v:]]
Corollary Let parital orthogonalliy Lo be the independence model over a finite set of embedding vectors E. Suppose Mi S E is Markov boundary of E E. and E span(E)) M(;))) then,
proj [u:] U..
13

---

Proof. Because V; E span(E E (u;)), then = k== Ogti with E' = {ui...., um S E.
Since Mi Markov boundary of U;.
of Mi(M M1) Mf 2k of up Vey E E'
of Mi(M M1) M Σ
Uk = 2.
1=1
k=
(proj M. [0s]. vs) = =(us: v2)
Thus, proj [0:] U4.
A.1
Construction of IPE Map
Theorem 10. Let V be a finite set of random variables with distribution P. 9p is minimal I-map of P. Let A be equal adj, (dj with eigen decomposition UEUT. If is a perfect perturbation factor, then the function f with
f(v:) = U2
is an IPE map of P where v4 is random variable in V and Up is the i-th row of U. Furthermore, if P is faithful to p, then f is a faithful IPE map for P.
Proof. Let [V = n and, to slightly abuse notation, we use index E [n]] to mean the vertex e and the i-th embedding. And
Av,.y, where V,, V22 V to mean the submatrix of A ((
Because Gp is miminal /-map of P, we have Ia(V) C IV(V).
We just need to show Ic(V) Io()(V)) And if P is faithful to Gy. then Io(s(V)) = IV()) Ip(V).
If oz La V where V C V. let = V V' then
Ave Ave.v Avi,ve,Ay
=
On the other hand, if f(:) Lo [v;)))((V)) then f(w)) f(w,) f(v.)" (VWVT//VVVV(VV f(y)) =0
(A.1)
Note that by our construction, (((V)) Av invertible. We can write (A.I) follows:
f(x)) (
Ais Avt
By Schur's complement, we have that
(Gr)v=)-- (A- =
Av Ap
Becasue is a perfect perturbation factor, by definition, f(v.) Lo f(v)))((V)) if and only .G Uy VV. By the compositional property, we have that Io(V) = Io(((V)).
Lemma 12. For any simple graph G, is perfect all but finitely many E R.
Proof. This is direct consequence of Theorem 1 in [LM07].
14

---

A.2 Dimension Reduction of IPE
Theorem 13. Let U be a set of vectors in I where U and every vector is unit vector. Let Σ be matrix in RRxx where Enj (ug uz). Assume X = Amin (2) >> O. Then there exists mapping g IR" + Rh where k- = [20 log(2n)) that for any us U with its unique Markov boundary M₁ S U and any us E (fu,) 3 U M,), we have
with e' = min //2, e/,, X1 /222) and & E (0, 1) such
(proig proig(M))l((u))) (rotil).pooigamalle proigha,)( SE
where Ti = MMab r max; Mi] and C = + 1) 2Amor (m (3)+ 2(m+1))))))
Amin
Proof. Let g be linear map of Lemma 16 with error parameter e' E (0, 4). For convenience, let i = gu.), ii = ((u)) and M, = (M). Let r; = [M,] To slightly abuse notation, we use M, and M, to also mean matrices where each column is an element in the set. Furthermore, we also define Σ to be Σng (ü,, ūz). We use ΣA,B where A, B _ U to be submatrix where the row indices from A and the column indices are from B, and when A = B, we just use ΣĄ for simplicity. In Ei.j (M.ih EM.
Σg,M,
particular, let M..M).G.M.)
And we can define a similar thing for Σ.
We first want to find e' such that ÊM, is non-singular for all i [U]. Note that for any u, U, we know that by Weyl's inequality for eigenvalues [HJ12),
Amin (EM.) Amin Amin( (EM,)l S 1|EM. Em.ll S 1|EM. EM,lIF S 126
Thus,
Amin (EM.) 2 Amin (Ens,) - -28 2 Amin (E) r2e d1 - -26
Therefore, if we want Amin (MM,) >
d1 2 we need s' < 2,
On the other hand, because M, is Markov boundary for Ui, we have
u uf (M M.) M =
(A.2)
Note that M, must be full rank. Otherwise, we can find a subset of M; to be the Markov boundary. And there is a different way to write this. Remember that ((I.M)).(..M. Schur's complement, we have that
Eiji EMarr
Ei
Using
EM,
det (E) det(EM, ddetEE,,))ee....... - (fMM) ( uz))
ddet(2'm)) uy uf M,MM,
We want to estimate the following:
(oro)t(xs,l((ss))) (o(;))) 1 ú. - of M.M M.) MM
det (..(S(..M..G.M)))
(A.3)
det (et(
We already know that det((S..)) > (2 yr, On the other hand, by Theorem 2.12 [TR08], we have that
| |dct [det(E((M))G..m)) = dot (E..)...M))))).M) - doc(E(..o.G.MM)))
(n + 1) E(I.M).0MM)) max{ ( (.E.
By Weyl's inequality for singular values, we have that
(...M))..MMIl Tmax (E(.MM)...M..) S Tmax (2...M)...M.)) + (r: + 1)3e' < Amax (2) + (ri + 1)26' < Amax (2) + (ri 112
15

---

Thus,
|det( S (os + 1)(r; 1)2 (Amam (E) + (rs + 1)
And,
del(S (ri (A (I) + (rr 1)2gr. (et
Let C = (r + 1)3( 2Amax +2)++)+)))
yr Then,
Aman (2)
det (
S ECC
det (et(EMM))
Let = m &. 2xb } and lo (2r) we have that
(e')²
(proiy(M)) (pproi(s))l((u))) [g(u:)], proigea,)lo e
Lemma 16. Let (0, 4) Let V S 1a be set of n points and k. 20 20 2m)
there exists
linear mapping g Rd + R* such that for all u, v E V:
Kg(u), g(v)) - (u, o) S
Proof. The proof an easy extension of the JL lemma [Vem05] by adding all the -v for all i E V into the set V.
16

---

B Additional Experiments, Figures and Tables
Table categories of words used test the semantic meaning of partial orthogonality
Category
Words in Category
'vehicle"
'aar', 'hicycle', 'skatchoard", 'motoreycle', 'helicopter', 'truck', 'boat', 'airplane", 'submarine" 'scooter'
'animal'
'lion', "dolphin', "cagle', ; 'dog'. 'elephant', 'cat', 'rat', 'giraffe', 'bird', "tiger'
'tool'
'hammer', 'screwdriver', 'wrench', 'pliers', 'hacksaw', 'dilll,, 'chisel', 'plunger', 'trowel', 'cutter'
'clothing'
'shirt', 'pants', 'dress', 'sweater', 'jacket', 'hat', "socks', 'gloves', 'scarf", 'vest"
'beverage"
'coffee', 'tea', 'soda', 'lemonade', 'milk', 'wine", 'beer', 'sake", 'smoothie", 'nectar'
'science'
'biology', 'ecology'. 'geneties', 'chemistry', 'physics', 'geology', 'mathematie'', 'linguistics', 'psychology', 'cryptography'
'furniture"
'couch', 'bed', 'cabinet', 'dresser', 'hallstand', 'lamp'. 'bench', 'chair', 'table', "closet"
'plant"
'daisy,, 'pine', 'iris', 'lily', 'oak", 'tulip', 'fem', "ros",, 'hamboo', "cactus'
'oodd"
'chocolate', 'meat', 'steak', 'pasta', 'fish', 'brisket', 'sausage", 'loaf", 'roe", 'lobster"
Table 4: Experiments show that top correlated words with target words after projecting onto the orthogonal complements randomly selected linear subspaces are more semantically meaningful
Target
Top Correlated Words Before Projection
Top Correlated Words After Projection
'eggplant'
'potato', 'banana', 'grape', 'vegetable" "bananas', 'tomato', 'espagnol" 'eternal', 'potatoes", 'e.g.'
'grape', 'purple-black, 'purple', 'turnips' 'plum', 'lilac', 'vegetable" 'vegetables' 'banana', 'ultra-violet'
'king'
'mister", 'bossman', 'thet', 'thatt" 'beast', 'killed', 'yesiree' 'bossed', 'outdo', 'queen's'
'royalty', 'sport-king' 'bossman', 'kingan' 'mister', 'prince's', 'princess' 'princes' 'handsomest', 'ruling'
'advise"
'spoken', 'askin', 'concur', 'applies' 'said', 'according', , 'astute' 'pertinent', 'evident', 'preached"
'guidelines', 'guidance', 'tips', 'motto" 'motivating'. 'encourages', 'advising' 'advisory" 'self-help', 'reminder"
'work-out'
"healthy', 'weights', 'worked', 'time-on-the-job" 'on-the-job', "work-successs: 'busy-work' "out'n", 'healthiest', 'hardworking"
'gym', 'weights', "footing'. 'running' 'jogs'. 'dumbbells', 'conditioning" 'body-building" 'runing", 'pumped-up'
'poem'
',, 'ya', 'ch', "yes', "y' 'mem', 'oh", "), "poignant", 'hee'
'poems', 'poctizing', 'poetry's', 'rhyming' 'sonnet', 'lyries', 'recited' 'poctically" 'sonnets', 'rhyme'
17

---

Table 5: Selected examples provided by ChatGPT when asked "give me a list of 50 common nouns, each with short description, and the first one is eggplant"
Target Word
Description Sentence
"eggplant"
'A purple or dark-colored vegetable with smooth skin, often used in cooking and known for its mild flavor.'
"dog"
'A domesticated mammal often kept as a pet or used for various purposes.'
'book'
'A physical digital publication containing written or printed content.'
"car'
'A motorized vehiele used for transportation roads.'
"tree'
'A woody perennial plant with a main trunk and branches, usually producing leaves.'
'house"
'A building where people live, providing shelter and accommodation."
'computer'
'An electronic device used for processing and storing data, and performing various tasks.'
'cat'
'A small domesticated carnivorous mammal commonly kept as pet.'
'chair'
'A piece of furniture designed for sitting on, often with a backrest and four legs.'
'phone"
'A communication device that allows voice calls and text messaging."
22.5
Spor yy ve f
faxd tool pous" "woel lap splr) compurer Srannar
apan turr
Spertye (ssnd)))
Sparia Purcer Endectopp
33.6
12.5
Number POWNS
Nimber Rasnsom Paines
(a) 'lemon'
(b) 'book'
king
Spur yoor Seiskkg
Spard brpplly Touch
Ster "plawdf
Spar Rankerr bronkrngs
Spar Mumdeer bronkegg
22
16
Numtier Randoo RoanTs
Nttvberr Famdom Roans
(c) 'car'
(d) 'king'
Figure 4: Linear subspaces spanned by estimated generalized Markov boundaries have smallest subspace angles with lincar subspaces spanned by embeddings that best match semantic meanings
18


Reviews:
[{"review_id": "R1hUQiwcAC", "reviewer": "Reviewer_1qJm", "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.\n\nAs 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.\n\nFinding 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.\n\nSeparately, 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.\n\nExperiments 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.", "questions": "1. Primarily, I would like to see experiments verifying Theorem 13 on dimensionality reduction in independence preserving embeddings.\n1. Is the only difference between kernel mean embeddings and independence preserving embeddings the choice of a kernel with finite dimensional feature map?\n1. What is the relationship to work on information theory with kernel methods [2]?\n1. 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.\n\n[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.\n[2] Francis Bach. Information Theory with Kernel Methods. 2022. ⟨hal-03577992v2⟩", "limitations": "I did not find a discussion of limitations.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "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.\n2. The proposed definition of generalized Markov boundary and method for finding boundaries are reasonable.\n3. 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.\n1. 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.\n1. No experiments are performed for independence preserving embeddings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**“The method and experiments for the generalized Markov boundary only involve a single target embedding.”**\n\nThe goal of this paper is to find good descriptions/explanations of given embeddings with other embedding vectors. We feel like it does not make too much sense to try to describe/explain multiple word embeddings at the same time. However, one could consider embeddings of phrases and sentences. \n\n**“The experimental evaluation only evaluates token embeddings, whereas the text encoder in CLIP can encode sequences.”**\n\nThanks for the suggestion! Because our objective is to uncover the semantic meanings of words, finding the semantic meanings of sentences is a much harder task and very difficult to define, although one could use contextualized embeddings to deal with polysemantic words. In this paper, to avoid ambiguity, we choose to study nouns whose meanings are less ambiguous like “eggplant” and “zebra”.\n\n**“No experiments are performed for independence preserving embeddings.”**\n\nThe study of IPE is mainly used to answer the theoretical question of whether such embeddings are possible. Its practical application is an interesting future research direction. Nevertheless, we include some additional experiments on IPE. Please see the top review for more details. \n\n\n**“Relation with kernel mean embedding and information theory with kernel method”**\n\nThat’s a good question! We will try to explain this better in the updated version. In general, kernel embeddings are infinite dimensional embeddings that are more concerned with the moments of distributions they are trying to embed. For kernel mean embedding, it’s the first moment, and for information theory with kernel method, it’s the second moment. On the contrary, our independence-preserving embedding is a finite-dimensional embedding. Such finite dimension embedding can be directly used in practice. The reason we can produce finite dimension embedding is that we are only focused on the _structure_ of distributions, i.e., conditional independence statements, and not other statistical properties of the distributions. \n\n**“A more realistic application that utilizes the method developed in the paper would greatly strengthen the paper.”**\n\nThanks for the suggestion! Finding an interesting application for our results is definitely an interesting next direction. \n"}, {"review_id": "C0QDh4E3oL", "reviewer": "Reviewer_3K9o", "summary": "The central question (quoting the paper) is \"How to make sense of an embedding vector in relation to other embedding vectors?\"  For that\npurpose, the authors propose to generalize the idea of the Markov boundary to embeddings, with a relaxed adaptation of this notion to\ncope with word embeddings peculiarity. The paper then introduces an algorithm to find (approximately) what is called the generalized Markov boundary for a given embedding. Empirical evaluations are carried out on CLIP.", "questions": "I have no question. \n", "limitations": "No", "rating": 2, "confidence": 4, "soundness": 1, "presentation": 1, "contribution": 2, "strengths": "The real scientific goal should be first clarified before one can assess the strength of this proposition.\n", "weaknesses": "Maybe I completely misunderstand this paper, but I cannot tell what is its scientific goal. For me everything is confused in the paper: the notion of markov boundary for vectors in the context of contextualized embeddings (like CLIP), why so much formal definitions for at the end a rough relaxation.\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review!\n\n**“The scientific goal”**\n\nWe apologize for the confusion. In this paper, we hypothesize that semantic meanings have an independence structure. We use the abstract “independence model” to formalize this idea. On the other hand, embeddings, which are vector representations of words, should also have a similar independence structure. A natural candidate “independence model” for vector space is partial orthogonalities. \n\n_Therefore, the main conjecture of this paper is that partial orthogonalities of embedding spaces encode semantic meanings._ To test this theory, we first study the theoretical aspect of the problem. In particular, we generalize the notion of the Markov boundary to embeddings. The relaxation is necessary because the intersection property of “partial orthogonality” rarely holds for embeddings. And then we verify the theory empirically in our experiment section. Specifically, we examine whether the Markov boundary effectively conveys \"semantic meanings.\"\n"}, {"review_id": "K5bNZQKahK", "reviewer": "Reviewer_DCJZ", "summary": "This paper investigates the relationship between the semantics and linear algebraic structure of token embeddings. It proposes utilizing partial orthogonality to define the \"Markov boundary\" of token embeddings. Given that token embeddings have limited dimensions and the Markov boundary can consist of numerous embeddings, the authors suggest relaxing the definition of partial orthogonality. They subsequently introduce an approximate algorithm to identify this boundary, which iteratively locates embeddings with high cosine similarity to the target vector after projecting onto orthogonal complement subspaces. To justify the effectiveness of vector space, the authors present the concept of independence preserving embeddings, which serves as the foundation for studying linear algebraic independence in embedding vectors.", "questions": "1. The embeddings studied in this paper is static embedding. I wonder what if the embeddings are contextualized? For example, what would happen if the embeddings are processed by Transformers?\n\n2. Throughout the section 3, the definitions of d and n are confusing. It says if d is smaller or equal to n, vectors are linearly independent. Should it be the opposite? And the same things happens to line 132.\n\n3. Typo: In line 96, period should be replaced by comma.", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper formally discussed the relationship between meanings of tokens and their algebraic independence.  It generalizes the idea of Markov boundary and relaxes its definition so it can be practically applied to word embeddings.\n\n2. To validate the use of linear algebraic independence relationships between embeddings for studying their semantics, the author introduces the concept of independence preserving embedding. This concept demonstrates that embeddings maintain the independence structure of distribution, making the paper comprehensive and self-contained.\n\n3. The authors conduct experiments using CLIP embeddings and demonstrate that their algorithm effectively identifies intriguing patterns between word embeddings, indicating that these embeddings possess semantic meanings.\n", "weaknesses": "1. Although the authors aim to study the independence relationship between word embeddings, they do not provide an evaluation metric to substantiate the effectiveness of the proposed method. The experimental results are presented as case studies with a limited number of words as examples, which may not be compelling for readers. A more robust experimental section would be beneficial.\n\n2. The experiments conducted in the paper focus solely on the CLIP embedding model. While it is understandable that CLIP, being trained with visual information, may encode semantics that are more meaningful to humans, it would be interesting to explore whether the proposed method can be applied to other models that rely exclusively on text-based training.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review and suggestions!\n\n**“Although the authors aim to study the independence relationship between word embeddings, they do not provide an evaluation metric to substantiate the effectiveness of the proposed method.”**\nThe experiment section is divided into two parts. The first part tests the effectiveness of the proposed method in finding subspaces that can reduce residual correlations. The second part is the qualitative study, which evaluates whether the Markov boundary is semantically meaningful. In the paper, we measure semantic meaningfulness via human intuition. How to quantify this measure is an open question and we feel like deserves its own paper. Nevertheless, we include some additional experiments that have numerical evaluations of our method. Please see the top review for more details. \n\n**“The experiments conducted in the paper focus solely on the CLIP embedding model”**\nThanks for the suggestion! And you’re right. We found that CLIP text embedding tends to encode more interpretable semantics meanings. For instance, for the word “eggplant”, the word “purple” appears more meaningful in CLIP embedding than other text-based only embeddings. \n\n\n**“The embeddings studied in this paper are static embedding. I wonder what if the embeddings are contextualized? For example, what would happen if the embeddings are processed by Transformers?”**\n\nThanks for the suggestion! It would be an exciting future direction to extend this work to contextualized embeddings. On the other hand, in this paper, our experiments are done on nouns whose meanings are less ambiguous like “eggplant” and “zebra” to demonstrate the effectiveness of Markov boundaries. \n\n**“The definitions of d and n are confusing.”**\n\nThanks for your careful attention and sorry for the confusion. It is a typo. We’ll correct it in the updated version.\n"}, {"review_id": "lNWOHBT7D2", "reviewer": "Reviewer_zRa2", "summary": "This paper aims to uncover the semantic meaning of embedding vectors\nwithin a given space. The basic idea is to determine\na generalized Markov boundary by computing the cosine similarity of the\northogonality projected vectors within a subspace. The top K\ncandidates are then selected. Furthermore, the authors provide a theoretical\nanalysis of the concept of Independence preserving embedding in section\nfive.", "questions": "- What is the critical motivation for using Image-language pre-train model\nCLIP as embedding? It would be better to compare it with other embedding techniques such as GloVe, word2vec, and BERT. And How does the\ndimensionality of the embedding vectors decide the performance of the\nproposed algorithm?\n- This paper only provides five examples in Table 2 regarding meaningful\nsemantic evaluation. Would it be possible to compute the precise numer-\nical results using semantic evaluation metrics to show the advantage after\northogonality projection?\n- In section five, the author introduces the concept of IPE, which might\nbe more straightforward to understand through toy examples or visual\nfigures", "limitations": "No", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- the connection between graphical model theory and explanation of embeddings seems novel (although similar ideas are present in other fields, such as the study of knowledge graph embeddings)\n- conceptually, everything is well defined and formally presented\n- The research question is clear and meaningful.\n- The structure of this paper is well-organized. In particular, in section\ntwo, the authors explain the necessary background information clearly", "weaknesses": "- experiments and results analysis is rather sparse, the paper has more focus on the theory and definitions\n- experimental setup can be criticized (see comments below)\n- related work with respect to knowledge graph embeddings could be more thorough. Several studies have focused on using projection or rotation techniques for KG embedding to predict the missing relationship between two entities [THW, SLH, SW]. Can these KG meth-\nods be adapted to uncover meaningful word embeddings?\n\n[THW] Yun Tang, Jing Huang, Guangtao Wang, Xiaodong He, and Bowen Zhou. Orthogonal\nrelation transforms with graph context modeling for knowledge graph embedding. arXiv\npreprint arXiv:1911.04910, 2019.\n[SLH] Tengwei Song, Jie Luo, and Lei Huang. Rot-pro: Modeling transitivity by projection\nin knowledge graph embedding. Advances in Neural Information Processing Systems,\n34:24695–24706, 2021.\n[SW] Baoxu Shi and Tim Weninger. Proje: Embedding projection for knowledge graph comple-\ntion. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your questions! We're glad you found the ideas novel and the paper well written.\n\n**Experiments**\nWe completely agree with the reviewer that the paper is more focused on theory and definitions. The reason we consider pre-trained image-language model CLIP is that we found it tends to encode more interpretable semantic meanings. For example, for the target word “eggplant”, the word “purple” appears more meaningful in CLIP embedding than other text-based only embeddings. \n\n\n**Connection to knowledge graph**\nThanks for suggesting these related works. We’ll include them in the updated version. On the other hand, although the “independence model” is a concept closely related to the graphical model, its abstract notion has applicability beyond graphs. In fact, many independence models cannot be embedded in graphs. \n\n**“This paper only provides five examples in Table 2 regarding meaningful semantic evaluation. Would it be possible to compute the precise numerical results using semantic evaluation metrics to show the advantage after orthogonality projection?”**\nThanks for the suggestion! We have run additional experiments by using Wu-Palmer similarities as the numerical estimates. Please see the global review for more details. \n"}]

Author rebuttal:
We thank the reviewers for their thoughtful reviews and for recognizing the ideas presented in the paper as novel and appealing. In addition, we ran some quick experiments to additionally verify the effectiveness of our method and theory as suggested by reviewers. Tables and figures are included in the pdf file. 

**Random projections**
In the paper, we show that top correlated words after random projections are more semantically meaningful by presenting some examples. To provide a numerical estimate as suggested by Reviewer zRa2, we adopt the Wu-Palmer similarity metric. We run the experiments in two settings. In the first setting, 1000 target words are randomly selected from the Brown corpus. As those words might contain rare and obscure ones, we run experiments in the second setting with 300 common nouns as target words. These words are selected by ChatGPT. Table 1 shows that the average WP similarities of top correlated words with target words are higher after random projections. 

**Markov boundary**
In the paper, we demonstrate the effectiveness of our Markov boundary learning algorithm by measuring the smallest principal angle between Markov boundaries and random subspaces as well as some subspaces spanned by relevant words to target words. We present some selected examples in the paper. The additional experiments here provide numerical estimates. We first ask ChatGPT to give us a list of 50 common nouns each with a short description. Next, we convert the short descriptions into embeddings using CLIP text encoder. Finally, we compare the principal angle between description embeddings and subspaces spanned by Markov boundaries as well as randomly selected words. Figure 1 shows the learned Markvo boundaries consistently have smaller angles with description embeddings.

**IPE**
In the paper, we show the theories of independence-preserving embeddings. Here, we present additional empirical evidence of the theories. We randomly generate graphs using Erdős–Rényi model with p = 0.01 and the number of nodes to be 1000. We first apply the IPE construction method to get the embeddings and then apply random projections. Figure 2 shows that without projection (dimsion=1000), the average absolute cosine similarities of residuals after projecting onto respective Markov boundaries are nearly zero. As the random projection dimension increases, the average absolute cosine similarities increase slowly. 


Meta-review: This paper builds upon a vector space model of independence in order to propose a way of capturing the "meaning" of an embedding via a Markov boundary consisting of other embeddings.

The reviews mostly find the work interesting, but hard to evaluate; the authors have proposed some additional results that help. I agree that the mathematical model is interesting here and believe that this paper deserves some attention, and thus recommend acceptance. I stress however that the paper is rather weakly anchored in linguistic or lexicographic theory, approaching concepts such as "meaning" in a fairly rough way, somewhat conflated with similarity. I would also strongly recommend updating the additional experiments (submitted at rebuttal time) to use more reproducible sources for word definitions and word frequency such as dictionaries rather than ChatGPT.
Decision: Accept (poster)