Causality and a Cost Semantics for Neural Networks

post by scottviteri · 2023-08-21T21:02:00.542Z · LW · GW · 1 comments

Contents

  Introduction
    How I Would Like People to Engage with this Work
  Cost Semantics
    Definition
    Basic Operations and Warm-Up
  Building Out the Tech Tree
    We Want If Statements
    Division
    If Statements Finally, Logic, and Causality Calculations
    Causality Calculations on Booleans
    Derivative Estimation
  Causality via an Approximation
    Power Series versus Piece-wise Linear and an Aside on Recursion
None
1 comment

$\text{Epistemic status:}$ I time-boxed this idea to three days of effort. So any calculations are pretty sloppy, and I haven't looked into any related works. I probably could have done much better if I knew anything about circuit complexity. There are some TODOs and an unfinished last section -- if you are interested in this content and want to pick up where I have left off I'll gladly add you as a collaborator to this post.

Here is a "tech tree" for neural networks. I conjecture (based on admittedly few experiments) that the simplest implementation of any node in this tree includes an implementation of its parents, given that we are writing programs starting from the primitives +, *, and relu. An especially surprising relationship (to me) is that "if statements" are best implemented downstream of division. 

Introduction

While discussing with my friend Anthony Corso, an intriguing idea arose. Maybe we can define whether program $p_1$ "causes" $p_2$ in the following way: Given a neural network that mimics $p_1$, how easy is it to learn a neural network which mimics the behavior of $p_2$? This proposition is intriguing because it frames causality as a question about two arbitrary programs, and reduces it to a problem of program complexity.

Suppose that $p_1$ and $p_2$ are written in a programming language P, and let P(ops) represent P extended with ops as primitive operations. We define a complexity function $C:P\left(ops\right)\to R$, which takes a program in the extended language and returns a real number representative of the program's complexity for some fixed notion of complexity. Let's define the degree to which $p_1$ "causes" $p_2$ as the minimum complexity achievable by a program p from $P\left(p_1\right)$ such that p is extensionally equal (equal for all inputs) to $p_2$. If $P_2$ is the set of all p in $P(obs+p1)$ that are extensionally equal to $p_2$, then $causes(p_1,p_2)={min}_{p\in P_2}C\left(p\right)$. We can also use this definition in the approximate case, considering the minimum complexity achievable by programs p such that $E\left(p\right(x)-p_2(x){)}^2<\epsilon$ with respect to some $L_1-integrable$ probability measure.

We can define a particular complexity function $C$ that represents the cost of executing a program. We can estimate this quantity by looking at the program's Abstract Syntax Tree (AST) in relation to some cost model of the primitive operations in the language. For this exploration, we have chosen the lambda calculus as the language. Lambda calculus is a minimalist Lisp-like language with just a single type, which in our case we will think of as floating point numbers. The notation is simple: lambda abstraction is represented as $\lambda$ x. x, and function application as (f g), which is not the same as f(g) in most other languages.

How I Would Like People to Engage with this Work

• By writing Ops in your favorite programming language
• By circumventing my proposed tech tree, by reaching a child without reaching a parent and using fewer (or equal) number of operations
• By training some neural networks between these programs, and seeing how difficult it is to learn one program after pre-training on another

Cost Semantics

Definition

We define the cost of operations and expressions in the following manner:

$\begin{array}{ccc}\text{Ops op}& =1,& \text{for any operation op in ops}\\ \text{Ops c}& =0,& \text{for any floating-point constant c}\\ \text{Ops x}& =0,& \text{for any variable x}\\ \text{Ops}(\lambda x.e)& =\text{Ops e}& \\ \text{Ops}\left(fg\right)& =\text{Ops f}+\text{Ops g}& \end{array}$

For operations of higher arity, we have

(Ops (op $x_1$ $\dots$ $x_n$)) =  (Ops op) + ${\sum }_i$ (Ops $x_i$)

The selected operations for a neural network are ops = {+, *, relu}.

Basic Operations and Warm-Up

Let's take a few examples to demonstrate this cost calculus:

• To derive subtraction, we first create negation $neg$.

(Ops neg) = (Ops ($\lambda$ x. (* -1 x))) = (Ops (* -1 x))
= (Ops *) + (Ops -1) + (Ops x) = 1 + 0 + 0 = 1

• The cost of subtraction ($-$) is then:

(Ops -) = (Ops ($\lambda$ x y. (+ x (neg y)))) = (Ops +) + (Ops (neg y)) = 1 + 1 = 2

• The cost of the $square$ operation is:

(Ops square) = (Ops ($\lambda$ x. (* x x))) = (Ops (* x x)) = (Ops *) = 1

With this, we have a framework for extending the $Ops$ function to more complex operations, providing a robust way to estimate the cost of various neural network operations. As we proceed, we will apply this framework to understand the complexity and causality in a neural network.

One crucial note in these calculations is that each time we find an equivalent program using the primitives, we can extend the domain of the $Ops$ function to include it. For instance, after calculating $neg$, it now acts as a base case. In this sense, $Ops$ is intended to be an upper bound - if we come up with another representation of an operation later that is less expensive, we can replace it as a base case in $Ops$. It might be necessary to propagate such changes downstream in $Ops$ for consistency.

As we proceed, let's explore the cost of a few more operations:

• The cost of a cube operation can be calculated as follows:

(Ops (cube x)) = (Ops (* (* x x) x)) = (Ops *) + (Ops (* x x)) + (Ops x) = 1 + 1 + 0 = 2

Interestingly, this case highlights why we are using a fixed arity for each operation. If we allowed $\ast$ to be nary, then we could say (Ops (cube x)) = (Ops (* x x x)) = 1 and the same would apply to higher n. This seems similar to unbounded fan-in circuits, so maybe it leads to a reasonably consistent but relatively un-physical system.

Since float is our only datatype, we will use the sign of $p$ to represent whether it is "true".

• For the absolute function $abs$, we calculate the cost as:

abs = $\lambda$ x. (+ (relu x) (relu (neg x)))
(Ops abs) = (Ops ($\lambda$ x. (+ (relu x) (relu (neg x)))) = (Ops +) + (Ops relu) + (Ops relu) + (Ops neg) = 1 + 1 + 1 + 1 = 4

In this $Ops$ calculation, I have started using n-ary $+$ as a transformation of the syntax. While it maintains many properties, it doesn't preserve $Ops$ itself. Hence, if we were to run $Ops$ on $Ops$, we would not use this notational convenience.

• ($>$ = $\lambda$ x y.(- x y)) and ($<$ = $\lambda$ x y. (- y x) 
  (Ops $>$) = (Ops $<$) = 1 
• ${\approx }_{ϵ}$ = $\lambda$ x y $ϵ$. ($<$ (abs (- x y)) $ϵ$) 
  (Ops ${\approx }_{ϵ}$) = (+ (Ops $<$) (Ops abs) (Ops -)) = (+ 1 5 7) = 13
• And composition: 
  $\circ$ = $\lambda$ f g x. (f (g x)) 
  (Ops $\circ$) = (Ops (f (g x))) = (Ops f) + (Ops g) = 0 + 0 = 0

Building Out the Tech Tree

We Want If Statements

Adding case statements into our programming language allows for greater expressiveness. A simple instance of this would be the "if" operation: (if p x y).

If we had a step function (0 if $x<0$ else 1), we could write "if" as a convex combination of cases x and y. Namely, (if p x y) = (let ((b (step p))) (+ (* b x) (* (-1 b) y))), where (Ops (let ((x e1)) e)) = (+ (Ops e1) (Ops e)). Then (Ops if) = (+ (Ops step) 3). However, a step function is discontinuous, and we only have continuous primitives.

So we multiply relu by a large constant and add it to a shifted negated version of itself, and it looks like an approximate version of a step function. I am calling it rightstep because the positive slope section occurs to the right of zero.

• shift = ($\circ$ f ($\lambda$ x. (- x c))) 
  (Ops shift) = (Ops -) = 2
• rightstep = ($\lambda$ m x. let ((mr (* m (relu x)))) (+ mr (shift (neg mr) (inv m)))) 
  (Ops rightstep) = (Ops (list * relu + shift neg inv)) = (Ops inv) + 6

For convenience, I am writing (Ops ops) for a list of ops so I can just sum them.

Remember that negative numbers represent falsity and positive numbers represent truth, so I would like 0 to represent a perfect balance between the two. Though it is not strictly necessary to do so, I will write step which shifts rightstep to be centered around zero:
 

• step = ($\lambda$ m x. shift (rightstep m x) (* -0.5 m)) 
  (Ops step) = (Ops (list shift rightstep *)) = (+ 9 (Ops inv))

Division

Given that division can be expressed as multiplication with the inverse, div = ($\lambda$ x y. * x (inv y)), with (Ops div) = (+ 1 (Ops inv)), we can focus on inv.

At this point, things start to get interesting. How can you use multiplication, addition, and relu to get division?

One might consider using a geometric series since $g\left(x\right)=(1-x{)}^{-1}=1+x+x^2+x^3+...$, so $g(1-x)=\frac{1}{x}$. However, this approach only converges for $-1<x<1$. And even if we could do this, sometimes it converges slowly, since $g(x,n)={\sum }_i^n=\frac{x^{n+1}-1}{x-1}$, so $error(x,n)=\frac{x^{n+1}}{x-1}$. If $x=\frac{1}{2}$, then convergence to float 32 precision will take 32 steps. In general, we are solving $2^{-32}=x^n⟹n=\frac{-32\ast log2}{\log x}$, which for $x=\frac{3}{4}⟹n\approx 77$.

A search on the internet for how to compute inverses and division gives Newton's method, which finds a zero of a differentiable function $f$ by using an initial guess $x_n$,  and picks an $x_{n+1}$ such that a line with slope $f^{\prime }\left(x_n\right)$ and value $f\left(x_n\right)$ would intercept the x-axis at $x_{n+1}$.

The nice thing about inverses in the context of Newton's method is that they cancel out under the division. Let $f\left(x\right)=x^{-1}-a$. Then $x_{n+1}=x_n-\frac{x_n^{-1}-a}{-x_n^{-2}}=x_n-(-x_n+a\ast x_n^2)=x_n(2-a{x}_n)$.

Each iteration of Newton's method only uses subtraction and multiplication. With Newton's method, the number of correct digits squares each time. Hence, we have (Ops inv) = (* 5 4) = 20.

If Statements Finally, Logic, and Causality Calculations

So, after our previous analysis, we find that (Ops div) = 21 and (Ops step) = (+ 9 (Ops inv)) = 29. Therefore, we have (Ops if) = (+ (Ops step) 3) = 32.

Now we can use "if" to generate logical connectives (expect $\neg$ which is the same as neg with 1 operation). 

Causality Calculations on Booleans

TODO: Then do causality calculations for nor-or, if-and

Derivative Estimation

The addition of division into our arsenal of operations also opens the door to employing Newton's method when we have access to the derivative, allowing us to find zeros of differentiable functions, such as polynomials.

Moreover, division gives us the ability to estimate gradients even when we don't have a closed form. For some small fixed $h$, we can define gradient estimation grad = $\lambda$ f x. (div (- (f (+ x h)) (f x)) h). The operation cost for this gradient estimation is (Ops grad) = (Ops (list div - +)) = (+ 21 2 1) = 24.

Armed with this gradient estimation, we can simulate a gradient descent step using descend = $\lambda$ x $\mu$. (- x ($\ast$ $\mu$ (grad f x)))
The operation cost for the gradient descent step is (Ops descend) = (Ops (list - * grad)) = (+ 2 1 24) = 27. Given the cost of these operations, the decision to minimize some functions using n steps of descent with (* 27 n) operations depends on the cost of your alternatives.

Returning to the central topic of causality, within the context of the programming language lambda calculus + {+, *, relu}, we can finally state that ($\lambda$ x. x) causes ($\lambda$ x. (* 2 x)) more than ($\lambda$ x. (* 2 x)) causes ($\lambda$ x. x) because Ops ($\lambda$ x. (* 2 x)) = 1 and Ops ($\lambda$ x. (div x 2)) = 21.

Note that we did not explicitly utilize $p_1$ as a primitive when determining the complexity of $p_2$, since Ops $p_1$ = Ops $p_2$ = 1. Thus, adding $p_1$ as a cost 1 base case to Ops would have been superfluous. But hopefully the algorithm is clear.

Causality via an Approximation

Power Series versus Piece-wise Linear and an Aside on Recursion

Maybe at this point you are thinking that many of these representations of functions are silly: a neural network will just end up fitting everything in a piece-wise linear fashion. And I think that may be true, especially for basic examples and small networks. But I could imagine that a larger neural network will end up learning efficient datastructures for common operations, and maybe we can predict when which datastructures will arise based on their relative numbers of operations.

Let's think about $e^x$ specifically.

Now, I would like to discuss the case where we are not considering equality, but rather the fidelity of the approximation to $p_2$. We can then compare the expected error of a piece-wise linear fit (TODO)

Consider this problem: I can envision using several different representations of a function inside a neural network. Take $e^x$ as an example, which can be expressed as $e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots ={\Sigma }_i\frac{x^i}{i!}$. We can approximate it as follows:

$dec=\lambda x.(-x1)=\lambda x.(+x-1)$, hence $Opsdec=1$

$Ops\left(fact0\right)=0$

$Ops\left(facti\right)=Ops(\lambda x.(\ast xi\left)\right)+Ops\left(fact\right(deci\left)\right)=1+Ops\left(fact\right(deci\left)\right)=2$

So, $Ops\left(facti\right)=2\times i$ because $Ops$ sums with recursive calls. However, this calculation seems to violate our language's current assumptions for two reasons: recursion and pattern matching.

We just used recursion, though we never defined recursion in your programming language. However, it's not a problem in principle because you can use $Y=(\lambda f.(\lambda x.\left(f\right(xx\left)\right)\left)\right(\lambda x.\left(f\right(xx\left)\right)\left)\right)$, which allows you to find a fixed point $\left(Yfn\right)=\left(f\right(Yf\left)n\right)$. However, this approach explodes with normal order evaluation, leading us to question what exactly we are attempting to accomplish. Are we aiming to create more of a static analysis function $Ops$ that runs on your program $p$ before running $p$, or are we crafting a dynamic $Ops$ that expands/runs as much of $p$ as necessary to compute $Ops$ of a recursive function? If the latter, why not just see how long $p$ takes to run? Notably, $Ops$ can use symbolic rewriting with respect to previously calculated programs to short-circuit the $Ops$ computation, which might be quite helpful. It would be nice if $Ops$ could be differentiable, since it's built out of case statements and recursion (which are, in themselves, case statements), and we just demonstrated how to make case statements differentiable by representing them in this language. Then we could use gradients to search for a minimum-length program equivalent to a baseline program.

The Y combinator could assist us in calculating $Ops$ symbolically. Let's express the factorial in the Y-combinator style, where it takes its own recursive call as a parameter $f$:

$Factfp=\left(if\right(iszerop\left)1\right(\ast n\left(f\right(decn\left)\right)\left)\right)$

and $fact=YFact$, such that $Fact$ continues to be applied until it reaches the termination condition.

Expressed this way, without syntactic sugar, it's evident that we neglected to count the cost of the termination condition check $iszero$, which was being covered by pattern matching. This observation brings us back to the significance of being precise when defining $Ops$ over our programs, to ensure that we are adhering to the specific program language primitive "ops" in $P\left(ops\right)$.

I made another mistake when I wrote $Ops\left(factn\right)=Ops\left({\Pi }_{i=0}^{n}i\right)={\Sigma }_{i=0}^n(1+Opsi)=n+1$.

The issue is that ${\Pi }_{i=0}^{n}i$ is not yet in our programming language, so it's not precise enough with respect to our primitive operations. For example, does it mean to iterate linearly through the sequence, or does it mean to multiply disjoint pairs recursively in a balanced merge tree? These interpretations would yield different $Ops$ values, and $Ops$ should be deterministic given a specific AST and a particular set of estimates for the costs of other operations.
 

1 comments

Comments sorted by top scores.