To gain intuition for how p-locality functions, we will introduce another notion of locality, called Markov locality, which will use the language of Markov blankets. We will prove that under relatively relaxed conditions p-locality and Markov locality are equivalent. This will allow us to relate the notion of locality to various graph structures commonly used to represent probability distributions, and will be a key step in proving Properties 2.1 and 2.2. We start by defining the Markov boundary, M(X,S), of a random variable X contained in a set of random variables S, as a minimal set such that p(X|S) = p(X|M(X,S)). The Markov boundary defines a minimal set of variables such that, conditioned on these variables, conditioning on no additional random variables in S changes the probability of X [39]. Similarly, we define the Markov blanket, M(X,S) for X in S as any set of variables such that conditioning on M(X,S), makes X conditionally independent from all other variables [39]. In this way, the Markov boundary is a Markov blanket but not all blankets are boundaries. Markov locality: Given probability distribution p(Z) and function f: RNX+NΘ RNΘ, the update function f(Z) is Markov-local with respect to the distribution p over Z if and only if k: Z Ωs.t. AMarkov boundary can be thought of as the set of variables that'locally' communicate with the parameter Θk, thus providing a natural measure of locality. Importantly, for Markov-locality to be of use, we would like the Markov boundaries of random variables in the model of interest to be unique.

Out-of-distribution (OOD) detection and lossless compression constitute two problems that can be solved by the training of probabilistic models on a first dataset with subsequent likelihood evaluation on a second dataset, where data distributions differ. By defining the generalization of probabilistic models in terms of likelihood we show that, in the case of image models, the OOD generalization ability is dominated by local features.

A.1 Proof of Proposition 12 Proposition 1 The historical contrastive instance discrimination (HCID) can be modelled as a3 maximum likelihood problem optimized via Expectation Maximization.4 Maximum likelihood (ML) is a concept to describe the theoretic insights of clustering algorithms.6 PN n=1 Z(kn) = 1), and the last step of derivation13 employs Jensen's inequality [6, 7, 4]. Z(kn) log p(xq,kn; θE) (5) Expectation step focuses on estimating the posterior probability p(kn; xq,θE). We first gener-17 ate keys by a historical encoder: kt mn = Et m(xt), and xt Xtgt. Then, We calculate18 p(kn; xq,θE) = p(kt mn; xq,θE) = 1 (xq,kt mn), where 1 (xq,kt mn) = 1 if both belong to the19 positive pair; otherwise, 1 (xq,kt mn) = 0.20 Please note the notation "t m" shows that the k is encoded by a historical encoder.21