Joseph Van Name comments on Joseph Van Name’s Shortform

Joseph Van Name 14 May 2025 5:42 UTC
1 point
0
In this post, we shall describe 3 related fitness functions with discrete domains where the process of maximizing these functions is pseudodeterministic in the sense that if we locally maximize the fitness function multiple times, then we typically attain the same local maximum; this appears to be an important aspect of AI safety. These fitness functions are my own. While these functions are far from deep neural networks, I think they are still related to AI safety since they are closely related to other fitness functions that are locally maximized pseudodeterministically that more closely resemble deep neural networks.
Let $K$ denote a finite dimensional algebra over the field of real numbers together with an adjoint operation $*$ (the operation $*$ is a linear involution with $(x y)^{*} = y^{*} x^{*}$ ). For example, $K$ could be the field of real numbers, complex numbers, quaternions, or a matrix ring over the reals, complex, or quaternions. We can extend the adjoint $*$ to the matrix ring $M_{r} (K)$ by setting $(x_{i, j})_{i, j}^{*} = (x_{j, i}^{*})_{i, j}$ .
Let $n$ be a natural number. If $A_{1}, \dots, A_{r} \in M_{n} (K), X_{1}, \dots, X_{r} \in M_{d} (K)$ , then define
$Γ (A_{1}, \dots, A_{r}; X_{1}, \dots, X_{r}) : M_{n, d} (K) \to M_{n, d} (K)$ by setting $Γ (A_{1}, \dots, A_{r}; X_{1}, \dots, X_{r}) (X) = A_{1} X X_{1}^{*} + \dots + A_{r} X X_{r}^{*}$ .
Suppose now that $1 \leq d < n$ . Then let $S_{d} \subseteq M_{n, n} (K)$ be the set of all $0, 1$ -diagonal matrices with $d$ many $1$ ’s on the diagonal. We observe that each element in $S_{d}$ is an orthogonal projection. Define fitness functions $F_{d}, G_{d}, H_{d} : S_{d} \to R$ by setting
$F_{d} (P) = ρ (Γ (A_{1}, \dots, A_{r}; P A_{1} P, \dots, P A_{r} P))$ ,
$G_{d} (P) = ρ (Γ (P A_{1} P, \dots, P A_{r} P; P A_{1} P, \dots, P A_{r} P))$ , and
$H_{d} (P) = \frac{F_{d} (P)^{2}}{G_{d} (P)}$ . Here, $ρ$ denotes the spectral radius.
$F_{d} (P)$ is typically slightly larger than $G_{d} (P)$ , so these three fitness functions are closely related.
If $P, Q \in S_{d}$ , then we say that $Q$ is in the neighborhood of $P$ if $Q$ differs from $P$ by at most 2 entries. If $F$ is a fitness function with domain $S_{d}$ , then we say that $(P, F (P))$ is a local maximum of the function $F$ if $F (P) \geq F (Q)$ whenever $Q$ is in the neighborhood of $P$ .
The path from initialization to a local maximum $(P_{s}, F (P_{s}))$ for will be a sequence $(P_{0}, \dots, P_{s})$ where $P_{j}$ is always in the neighborhood of $P_{j - 1}$ and where $F (P_{j}) \geq F (P_{j - 1})$ for all $j$ and the length of the path will be $s$ and where $P_{0}$ is generated uniformly randomly.
Empirical observation: Suppose that $F \in {F_{d}, G_{d}, H_{d}}$ . If we compute a path from initialization to local maximum for $F$ , then such a path will typically have length less than $n$ . Furthermore, if we locally maximize $F$ multiple times, we will typically obtain the same local maximum each time. Moreover, if $P_{F}, P_{G}, P_{H}$ are the computed local maxima of $F_{d}, G_{d}, H_{d}$ respectively, then $P_{F}, P_{G}, P_{H}$ will either be identical or differ by relatively few diagonal entries.
I have not done the experiments yet, but one should be able to generalize the above empirical observation to matroids. Suppose that $M$ is a basis matroid with underlying set ${1, \dots, n}$ and where $| A | = d$ for each $A \in M$ . Then one should be able to make the same observation about the fitness functions $F_{d} |_{M}, G_{d} |_{M}, H_{d} |_{M}$ as well.
We observe that the problems of maximizing $F_{d}, G_{d}, H_{d}$ are all NP-complete problems since the clique problems can be reduced to special cases of maximizing $F_{d}, G_{d}, H_{d}$ . This means that the problems of maximizing $F_{d}, G_{d}, H_{d}$ can be sophisticated problems, but this also means that we should not expect it to be easy to find the global maxima for $F_{d}, G_{d}, H_{d}$ in some cases.