The Additive Summary Equation

post by johnswentworth · 2021-07-13T18:23:06.016Z · LW · GW · 3 comments

Contents

  The Summary Equation
  The Additive Summary Equation
    Main Theorem
    Main Trick of the Proof
    Rest of the Proof
  Loose Threads
  Some Special Cases
    Structure
    Symmetry
None
3 comments

This post contains some theorems and proofs needed for a hopefully-upcoming post on some powerful generalizations of the Koopman-Pitman-Darmois (KPD) Theorem. Unless you find functional equations interesting in their own right, and want to read some pretty dense math, you should probably skip this post. The theorems are pretty self-contained, and will be summarized in any future posts which need them.

The Summary Equation

We can represent the idea of a $D$-dimensional “summary” of $x$ for a function $f$ via a functional equation:

$F\left(G\right(x\left)\right)=f\left(x\right)$

Given the function $f$, we try to find some $D$-dimensional “summary” $G\left(x\right)$ such that $f$ can be computed from $G$ - i.e. we want some $F,G$ such that $F\left(G\right(x\left)\right)=f\left(x\right)$ for all $x$.

In order for this to be meaningful, we need some mild assumptions on $f$, $F$, and $G$; at the very least, we certainly need to exclude space-filling curves, which would defeat the point of a “$D$-dimensional summary”. Throughout this post, we’ll assume differentiability, although this should be easy to relax somewhat by taking limits of differentiable functions.

Easy theorem: The $D$-dimensional summary equation for $f$ is solvable only if the rank of the matrix $\frac{\partial f}{\partial x}$ is at most $D$ for all values of $x$. I’ll call this the “Summarizability Theorem”. (If you want a more official-sounding name, it’s the global converse of the constant-rank theorem.)

Proof: differentiate both sides of the equation to get $\frac{\partial F}{\partial G}\frac{\partial G}{\partial x}=\frac{\partial f}{\partial x}$. Since $G$ is $D$-dimensional, this is itself a rank-at-most-$D$ decomposition of $\frac{\partial f}{\partial x}$.

In practice, the converse will also usually hold: if the rank of $\frac{\partial f}{\partial x}$ is at most $D$ for all values of $x$, then we can usually find a $D$-dimensional summary $G\left(x\right)$. Indeed, if the rank is constant near some point $x^0$, then we can always find a local $D$-dimensional summary near $x^0$; that’s what the constant rank theorem says. However, Weird Stuff can sometimes prevent stitching these local summaries together into a global summary. (Thank you to Vanessa [LW · GW] for pointing me to an example of such “Weird Stuff”, as well as the name of the constant rank theorem.)

Minor notation point: each variable $x_j$ corresponds to a column of $\frac{\partial f}{\partial x}$. This convention will be used throughout the post. We will also assume that each $x_j$ is one-dimensional; higher-dimensional variables are represented by their components.

The Additive Summary Equation

The heart of the generalized KPD theorems is a family of special cases of the Summary Equation in which $f\left(x\right)$ is a sum of terms, each of which depend on only a few variables. I’ll call this the Additive Summary Equation. The most general version looks like this:

$F\left(G\right(x\left)\right)=f\left(x\right)={\sum }_i{f}_i\left(x_{N_f\left(i\right)}\right)$

… where $f_i$ are (known) smooth functions of output dimension $m>D$, and $N_f\left(i\right)$ specify (known) indices of $x$. Notation example: if we have a term $f_2(x_5,x_7)$, then $N_f\left(2\right)=\{5,7\}$ and $x_{N_f\left(2\right)}=(x_5,x_7)$.

The notation $N_f\left(i\right)$ here stands for a “neighborhood” induced by $f_i$, specifying the indices of $x$-variables on which $f_i$ depends. In the following sections, we’ll talk about the neighborhood of a variable $x_j$, denoted $N\left(j\right)$. This consists of all the variables which are neighbors of $x_j$ in any of the $f$-induced neighborhoods, i.e. $N\left(j\right)={\cup }_{i:j\in N_f\left(i\right)}{N}_f\left(i\right)$. In other words, $N\left(j\right)$ contains the indices of variables $x_{j^{\prime }}$ for which some $f_i$ depends on both $x_j$ and $x_{j^{\prime }}$.

In the generalized KPD theorems, the neighborhoods $N_f\left(i\right)$ reflect the graphical structure of the distribution. If $P\left[X|\Theta \right]$ factors according to a DAG [LW · GW]:

$P\left[X|\Theta \right]={\prod }_{i}P[X_i|X_{pa\left(x_i\right)},\Theta ]$

… then the corresponding functional equation looks like

$F\left(G\right(x\left)\right)={\sum }_i{f}_i(X_i,X_{pa\left(i\right)})$

… i.e. $N_f\left(i\right)=pa\left(i\right)\cup \left\{i\right\}$, with $f_i$ derived from $P[X_i|X_{pa\left(x_i\right)},\Theta ]$. (Here the “parents” $pa\left(i\right)$ are nodes with arrows into node $i$ in the DAG.) For instance, if the $X_i$ are all conditionally independent (as in the original KPD), then the equation is simply

$F\left(G\right(x\left)\right)={\sum }_i{f}_i\left(X_i\right)$

… i.e. $N_f\left(i\right)=\left\{i\right\}$. Another example: if the variables form a Markov Chain with $P\left[X|\Theta \right]={\prod }_{i}P[X_i|X_{i-1},\Theta ]$, then the corresponding equation is

$F\left(G\right(x\left)\right)={\sum }_i{f}_i(X_i,X_{i-1})$

… i.e. $N_f\left(i\right)=\{i,i-1\}$.

Main Theorem

Let $f\left(x\right):={\sum }_i{f}_i\left(x\right)$. Then the additive summary equation $F\left(G\right(x\left)\right)=f\left(x\right)$ is solvable for $F$ and $D$-dimensional $G$ only if $f$ can be expressed as

$f\left(x\right)={\sum }_{i:\frac{\partial f_i}{\partial x_{N\left(B\right)}}\equiv ̸0}{f}_i\left(x\right)+U{\sum }_{i^{\prime }}{g}_{i^{\prime }}\left(x\right)+C$

… for some at-most $D$-dimensional functions $\left\{g_{i^{\prime }}\right\}$, constant matrix $U$ of column-dimensional at-most $D$, constant vector $C$, and a set of at-most $D$ $x$-indices $B$. The notation $N\left(B\right)$ denotes “neighbors” of $B$, meaning $x$-indices $j$ for which some $f_i$ depends on both $x_j$ and a variable in $x_B$. (In particular, this means that all $f_i$ which depend on $x_B$ are constant when $x_{N\left(B\right)}$ is held constant.) Furthermore, the sparsity structure of each $g_{i^{\prime }}$ (i.e. the set of variables $\left\{x_j\right\}$ on which $g_{i^{\prime }}$ depends) matches one of the $f_i$. (See the end of the “Rest of the Proof” section for the exact correspondence.)

The theorem is interesting mainly when:

• The number of variables $n$ is much larger than the summary dimension $D$, i.e. $n>>D$, and...
• The number of variables $x_j$ on which each $f_i$ depends is small, so each $x_j$ has few neighbors $N\left(j\right)$

When these conditions hold, $\frac{\partial f_i}{\partial x_{N\left(B\right)}}$ will be nonzero only for a very small fraction of terms, so the impact of the vast majority of terms/variables on $f\left(x\right)$ is mediated by the at-most $D$-dimensional ${\sum }_{i^{\prime }}{g}_{i^{\prime }}\left(x\right)$; this sum serves as a summary for the $x_{\overline{N}\left(B\right)}$ (i.e. the variables which are not neighbors of the $D$ variables in $x_B$).

Intuitively, the simple result we’d “really like” is $f\left(x\right)=U{\sum }_{i^{\prime }}{g}_{i^{\prime }}\left(x\right)+C$, with ${\sum }_{i^{\prime }}{g}_{i^{\prime }}\left(x\right)$ at-most $D$-dimensional. This is not true in general for functions $f$ with $D$ dimensional summaries, but it is “almost true”: it holds for all but a few “exceptions”, i.e. a few extra terms/variables which can influence $f$ in more general ways. The number of exceptional variables is $|N\left(B\right)|$ - i.e. the $D$ variables $x_B$ plus their neighbors.

Note that the theorem claims “only if”, but not “if”. In the other direction, we can make a slightly weaker statement: any $f$ satisfying the above form has a summary-function $G\left(x\right)=(x_{N\left(B\right)},{\sum }_{i^{\prime }}{g}_{i^{\prime }}(x\left)\right)$, with dimension at-most $D+|N\left(B\right)|$. The summary is just the at-most D-dimensional summary of $x_{\overline{N}\left(B\right)}$, i.e. ${\sum }_{i^{\prime }}{g}_{i^{\prime }}\left(x\right)$, plus the "exception" variables.

Main Trick of the Proof

Pick some point $x^0$ at which the rank of $\frac{\partial f}{\partial x}$ takes its maximum value (which is at most $D$ by the Summarizability Theorem). Then we can pick a set $B$ of $x$-indices, of size at most $D$ (i.e. $|B|\le D$), such that $\frac{\partial f}{\partial x_B}{|}_{x^0}$ is a basis for the (at-most $D$-dimensional) column span of $\frac{\partial f}{\partial x}{|}_{x^0}$. If the system is very sparse, then $\frac{\partial f}{\partial x_B}$ will only depend on a few of the $x$-variables, namely $x_{N\left(B\right)}$.

Since $\frac{\partial f}{\partial x_B}{|}_{x^0}$ spans the maximum number of dimensions, all columns of $\frac{\partial f}{\partial x}{|}_{x^0}$ must fall within that span - otherwise the rank of $\frac{\partial f}{\partial x}$ would be greater. And since $\frac{\partial f}{\partial x_B}$ depends only on $x_{N\left(B\right)}$, this must hold for any values of the other variables $x_{\overline{N}\left(B\right)}$. So, we can change the other variables any way we please, holding $x_{N\left(B\right)}$ constant, and $\frac{\partial f}{\partial x}$ will remain in the span of $\frac{\partial f}{\partial x_B}{|}_{x^0}$.

Let $U$ be any basis for the span of $\frac{\partial f}{\partial x_B}{|}_{x^0}$. (Of course we could choose $U=\frac{\partial f}{\partial x_B}{|}_{x^0}$ itself, but often there’s some cleaner basis, depending on the application.) Then $U{U}^{†}$ is a projection matrix, projecting into the span. For any $x$ with $x_{N\left(B\right)}=x_{N\left(B\right)}^0$,  $\frac{\partial f}{\partial x}$ must fall within the span, which is equivalent to

$\frac{\partial f}{\partial x}=U{U}^{†}\frac{\partial f}{\partial x}$ (for $x_{N\left(B\right)}=x_{N\left(B\right)}^0$)

Rest of the Proof

Next, we integrate. We’ll start at $x^0$, then take any path from $x_{\overline{N}\left(B\right)}^0$ to $x_{\overline{N}\left(B\right)}$ holding $x_{N\left(B\right)}$ constant. Then, we’ll go from $x_{N\left(B\right)}^0$ to $x_{N\left(B\right)}$ holding $x_{\overline{N}\left(B\right)}$ constant. So:

$f\left(x\right)=f\left(x^0\right)+\int \frac{\partial f}{\partial x_{\overline{N}\left(B\right)}}{|}_{x_{N\left(B\right)}^0}d{x}_{\overline{N}\left(B\right)}+\int \frac{\partial f}{\partial x_{N\left(B\right)}}{|}_{x_{\overline{N}\left(B\right)}}d{x}_{N\left(B\right)}$

For the first integral, $x_{N\left(B\right)}$ is held constant at $x_{N\left(B\right)}^0$, so by the previous section $\frac{\partial f}{\partial x}=U{U}^{†}\frac{\partial f}{\partial x}$:

$=f\left(x^0\right)+U\int U^{†}\frac{\partial f}{\partial x_{\overline{N}\left(B\right)}}{|}_{x_{N\left(B\right)}^0}d{x}_{\overline{N}\left(B\right)}+\int \frac{\partial f}{\partial x_{N\left(B\right)}}{|}_{x_{\overline{N}\left(B\right)}}d{x}_{N\left(B\right)}$

… and we’ll expand $f={\sum }_i{f}_i$:

$={\sum }_i{f}_i\left(x^0\right)+U{\sum }_i\int U^{†}\frac{\partial f_i}{\partial x_{\overline{N}\left(B\right)}}{|}_{x_{N\left(B\right)}^0}d{x}_{\overline{N}\left(B\right)}+{\sum }_i\int \frac{\partial f}{\partial x_{N\left(B\right)}}{|}_{x_{\overline{N}\left(B\right)}}d{x}_{N\left(B\right)}$

Now, we break the sum up into terms which do not depend on $x_{N\left(B\right)}$, i.e. $f_i$ for which $\frac{\partial f_i}{\partial x_{N\left(B\right)}}\equiv 0$ (for which the second integral contributes zero), and terms which do depend on $x_{N\left(B\right)}$, i.e. $f_i$ for which $\frac{\partial f_i}{\partial x_{N\left(B\right)}}\equiv ̸0$ (for which we can’t say anything nontrivial):

$={\sum }_i{f}_i\left(x^0\right)+U{\sum }_{i:\frac{\partial f_i}{\partial x_{N\left(B\right)}}\equiv 0}\int U^{†}\frac{\partial f_i}{\partial x_{\overline{N}\left(B\right)}}{|}_{x_{N\left(B\right)}^0}d{x}_{\overline{N}\left(B\right)}+{\sum }_{i:\frac{\partial f_i}{\partial x_{N\left(B\right)}}\equiv ̸0}\left(f_i\right(x)-f_i(x^0\left)\right)$

… and simplify a bit:

$={\sum }_{i:\frac{\partial f_i}{\partial x_{N\left(B\right)}}\equiv ̸0}{f}_i\left(x\right)+{\sum }_{i:\frac{\partial f_i}{\partial x_{N\left(B\right)}}\equiv 0}{f}_i\left(x^0\right)+U{\sum }_{i:\frac{\partial f_i}{\partial x_{N\left(B\right)}}\equiv 0}{U}^{†}\left(f_i\right(x)-f_i(x^0\left)\right)$

Since $U$ is $D$-dimensional (on the right), that proves the theorem; we can choose $g_{i^{\prime }}\left(x\right)=U^{†}\left(f_{i^{\prime }}\right(x)-f_{i^{\prime }}(x^0\left)\right)$ with $i^{\prime }$ ranging over $\{i:\frac{\partial f_i}{\partial x_{N\left(B\right)}}\equiv 0\}$, and $C={\sum }_{i:\frac{\partial f_i}{\partial x_{N\left(B\right)}}\equiv 0}{f}_i\left(x^0\right)$.

Loose Threads

This theorem is strong enough for my immediate needs, but still a little weaker than I’d ideally like.

First, there’s the converse of the Summarizability Theorem. In practice, when $\frac{\partial f}{\partial x}$ is rank at-most $D$ everywhere, I generally expect there to be a $D$-dimensional summary. But there are exceptions, and I haven’t found a simple, convenient condition which is sufficient to ensure the existence of the summary and easily applies to most of our day-to-day functions. On the other hand, I haven’t spent that much effort looking for such a condition, so maybe someone can point me to it. It’s definitely the sort of thing I’d expect somebody else to have already solved to death.

Second, there’s probably room to reduce the freedom available to $B$ and the $x_{N\left(B\right)}$-dependent terms. In particular, I believe we can impose $|B|+dim\left(U\right)\le D$, rather than just $|B|\le D$ and $dim\left(U\right)\le D$ separately. This requires first reducing $U$, so that it only spans the dimensions actually needed to summarize $x_{\overline{N}\left(B\right)}$, rather than all the dimensions spanned by $\frac{\partial f}{\partial x_B}{|}_{x^0}$. Given that reduction of $U$, the basic trick is to first go through the process from the above proof, but after that choose a new basis $B^{\prime }$ which includes $dim\left(U\right)$ variables from $x_{\overline{N}\left(B\right)}$, and go through the whole construction again with $B^{\prime }$ to get a new $U^{\prime }$. Terms dependent only on  $x_{\overline{N}\left(B\right)}$ or only on $x_{\overline{N}\left(B^{\prime }\right)}$ can be summarized via ${U^{\prime }}^{†}\left(f_i\right(x)-f_i(x^0\left)\right)$, so the only variables which can’t be summarized this way are those dependent on variables in both $x_{N\left(B\right)}$ and $x_{N\left(B^{\prime }\right)}$. We should be able to iterate this process until no further reduction of the “exception” terms occurs, which should happen when $|B|+dim\left(U\right)$ is equal to the maximum rank of $\frac{\partial f}{\partial x}$.

In the special case where $f_i$ depends only on $x_i$, this process of iteratively reducing the number of exception terms is relatively sraightforward, and we can indeed impose $|B|+dim\left(U\right)\le D$. (I'm not going to go through the proof here; consider it an exercise for the reader.) (In case anyone isn't familiar with what "exercise for the reader" means in math: don't actually do that exercise, it's a pain in the ass.)

Some Special Cases

There are two main classes of special cases: special “neighborhood” structure, and symmetry.

Structure

The simplest example of special neighborhood structure is when $f_i$ depends only on $x_i$ (corresponding to conditionally independent variables in the generalized KPD theorem). As alluded to above, we can then strengthen the theorem so that $|B|+dim\left(U\right)\le D$. Furthermore, “neighbors” are trivial: $N\left(B\right)=B$, so $|N\left(B\right)|+dim\left(U\right)\le D$. That means the summary $G\left(x\right)=(x_{N\left(B\right)},{\sum }_{i^{\prime }}{g}_{i^{\prime }}(x\left)\right)=(x_B,{\sum }_{i^{\prime }}{g}_{i^{\prime }}(x\left)\right)$ is at-most D-dimensional. Thus we have the converse of the theorem; it becomes an if-and-only-if.

Another useful structural constraint is when each $x_j$ has at most $k$ neighbors (including itself), i.e. $N\left(j\right)\le k$ for all $j$. In that case, $|N\left(B\right)|\le k|B|\le kD$. If the number of variables is much larger than $kD$, i.e. $n>>kD$, then this guarantees that the large majority of variables influence $f$ only via the at-most $D$-dimensional summary ${\sum }_{i^{\prime }}{g}_{i^{\prime }}\left(x\right)$.

Symmetry

By “symmetry”, I mean that $f$ is invariant under swapping some variables, e.g. swapping $x_1$ with $x_2$. This is interesting mainly when we can swap a variable in $x_{N\left(B\right)}$ with a variable not in $x_{N\left(B\right)}$. When that happens, both variables must be summarizable by ${\sum }_{i^{\prime }}{g}_{i^{\prime }}\left(x\right)$. In particular, if every variable potentially in $x_{N\left(B\right)}$ can always be swapped with a variable not in $x_{N\left(B\right)}$, then we can eliminate the exception terms altogether.

For instance, the original KPD assumed conditionally IID variables, corresponding to a summary equation with $f\left(x\right)={\sum }_i{f}^{\prime }\left(x_i\right)$ - i.e. each term is the same function $f^{\prime }$ acting on a different variable. In this case, any variable can be swapped with any other, so we can eliminate the exception terms; we must have $f\left(x\right)=U{\sum }_i{g}_i\left(x_i\right)+C$ for at-most D-dimensional ${\sum }_i{g}_i\left(x_i\right)$. In fact, this is somewhat stronger than the corresponding result in the original KPD: it applies even when the number of variables is finite, whereas the original KPD only requires that the summary have a finite dimension as the number of variables increases to infinity.

3 comments

Comments sorted by top scores.