betaFeedback

WorksComputer Science

A polynomial-size logical twin for neural networks

Abstract

A logical twin of a neural network is a logical representation that mimics the computation of the network through logical formulas. We revisit two earlier proposals for constructing logical twins of feedforward neural networks in Łukasiewicz logic, both of which are susceptible to exponential blow-up in running time and representation size. Building on ideas from both approaches, we present a new construction that directly yields logical twins in Łukasiewicz logic. We show that this construction can be computed in polynomial time and produces polynomial-size logical twins. Finally, we report an empirical evaluation of the three methods, showing that the new proposal substantially outperforms the other two.

Introduction

A logical twin of a neural network, as we propose to use this term, is a representation of such a network in the formal language of a logical framework. Just as formulas of classical logic represent Boolean functions and formulas of Łukasiewicz logic represent McNaughton functions, formulas of a logical system may represent the functions computed by a neural network. In this way, the computation performed by a neural network, usually represented by a graph circuit together with its associated weights and biases, may be carried out through evaluations of logical formulas comprised in its logical twin.

Neural networks are traditionally associated with the blackbox problem, which may be understood as the difficulty of justifying their learned weights and biases and of explaining their decisions, classifications, and the way they perform tasks [4, 6]. By contrast, logic and symbolic frameworks are usually regarded as being grounded in established laws of reasoning and as having a neatly defined semantics. In this sense, a logical twin may offer a new perspective on the blackbox problem by presenting its neural network twin in a symbolic framework that is often more interpretable, even though we acknowledge that logical formulas are not necessarily amenable to human interpretation, especially when they are large. A more immediate possibility, however, lies in the use of such logical twins for formal verification, which has already proved feasible for some neural networks and some of their properties—namely, reachability and robustness [17, 18].

The architecture of feedforward neural networks with the ReLU activation function is widely used in practice. If such an architecture is considered with input values in the unit interval [0,1][0,1] and with the truncated identity max⁡(0,min⁡(1,x))\max(0,\min(1,x)) as the activation function in the output layer, then each output value of the network, as a function of its nn input values, determines a rational McNaughton function f:[0,1]n→[0,1]f : [0,1]^n \to[0,1] [17]. Such functions are continuous piecewise linear, and their linear pieces have rational coefficients. In this work, we refer to neural networks of this kind as ReLU–TId neural networks.

Formulas of Łukasiewicz logic represent McNaughton functions, which are the particular case of rational McNaughton functions whose linear pieces are constrained to have integer coefficients. Thus, direct representations by Łukasiewicz formulas are restricted to McNaughton functions. One approach to circumvent this restriction is representation modulo satisfiability in Łukasiewicz logic, formalized in the system L-MODSAT, a technique for implicitly representing functions by logical formulas proposed by Preto and Finger [15, 16].

In this setting, a function is represented not by a single formula, but by a pair ⟨φ,Φ⟩\langle\varphi, \Phi\rangle, where φ\varphi is a formula and Φ\Phi is a set of formulas. Then, once designated propositional variables are evaluated by a valuation vv according to the arguments of the function, its value is given by v(φ)v(\varphi), provided that vv satisfies the set Φ\Phi. Rational McNaughton functions were shown to be representable in L-MODSAT. Moreover, these representations can be constructed in polynomial time when the functions are given in the so-called closed regional format.

A regional format is a natural representation of piecewise linear functions in which the domain is partitioned into regions so that each linear piece coincides with the function over an associated region. Thus, an encoding of a function in regional format consists of pairs ⟨p,Ω⟩\langle p, \Omega\rangle, where pp is a linear piece and Ω\Omega is a region. When the regions Ω\Omega are polyhedra given by linear inequalities and these pairs satisfy a special property called lattice property, the encoding is said to be in closed regional format. In this case, a lattice representation can be built from it. The construction of representations in L-MODSAT is based on this lattice representation; see Section 3.1.

In order to build a logical twin for a ReLU–TId neural network, one must still extract a regional representation from its graph circuit as an intermediate step. This was the starting point of our earlier workshop paper Regional, Lattice and Logical Representations of Neural Networks, published in the proceedings of the 19th International Workshop on Logical and Semantic Frameworks, with Applications (LSFA 2024) [19], where an algorithm was provided for carrying out this translation. Although the translation produced by that algorithm is not guaranteed to satisfy the lattice property, our experiments indicated that such failures are rare in practice. The present work continues that line of research. However, rather than simply extending the workshop version, this article reframes the problem around a new algorithmic approach that substantially outperforms the previous method.

Beyond the problem that the lattice property is not guaranteed, and therefore that correctness or exactness of the resulting representation is not guaranteed either, that algorithm is exponential in the number of neurons of the ReLU–TId neural network. For this reason, in the present work we propose a new algorithm that abandons the intermediate step of constructing a regional format representation and, inspired by the work of [21], constructs a representation directly by following the architecture of the network.

The algorithm by Zhang and Bö lcskei [21] represents each neuron of a neural network separately by logical formulas and then mimics the compositional, circuit-structured nature of the network through substitutions in logical formulas. It uses both Łukasiewicz logic and rational Łukasiewicz logic, an extension of the former, to represent the neurons individually. However, this technique cannot be applied directly to ReLU–TId neural networks, but only to equivalent neural networks that must first be computed. Unfortunately, these equivalent neural networks generally have more neurons than the original ones, which may cause an exponential blow-up in this intermediate representation.

In this work, we present a polynomial-time algorithm for directly representing a ReLU–TId neural network in the system L-MODSAT, thereby yielding a polynomial-size logical twin. The neural network is first transformed into an equivalent one by operations that we call output and input normalizations. However, this equivalent network has the same number of neurons as the original one. Then, the function computed by each neuron, which is a truncated linear function, is represented in L-MODSAT. These functions are particular cases of rational McNaughton functions whose representations in L-MODSAT are even less complex. Finally, we leverage the representational framework of L-MODSAT to represent the circuit-based compositions by means of interface propositional variables and linking formulas, producing the logical twin.

We also show that the approach of Zhang and Bö lcskei [21] can be adapted so as to use neuron representations in L-MODSAT together with interface propositional variables and linking formulas. Thus, the paper brings together three methods for constructing logical twins of ReLU–TId neural networks in the L-MODSAT setting: a lattice-based method built on regional representations, an architecture-based compositional method, and our new polynomial-time proposal yielding polynomial-size logical twins. Finally, we present an empirical evaluation based on implementations of all three methods on randomly generated ReLU–TId neural networks, showing that the new proposal performs substantially better than the other two.

The rest of this work is organized as follows. Section 2 presents the necessary preliminaries on feedforward neural networks, Łukasiewicz logic, and semantics modulo satisfiability. Section 3 revisits two approaches to the construction of logical twins with exponential blow-up, namely the lattice-based method and the architecture-based compositional method. Section 4 introduces our new polynomial-size logical twin construction. Section 5 describes the implementations of the proposed methods and reports the experimental evaluation. Finally, Section 6 concludes the paper.

Preliminaries

Feedforward neural networks

A feedforward neural network NN may be given (and represented) by a graph whose nodes are partitioned into an ordered family of ordered sets LN={L0,…,Lλ}\mathcal{L}_N = \{L_0,\ldots,L_\lambda\}, where a node is called a neuron and each LiL_i is a layer. All neurons in layer LiL_i, for i∈{0,…,λ−1}i \in\{0,\ldots,\lambda-1\}, are linked by an edge to all neurons in layer Li+1L_{i+1} establishing a computational circuit such that all output values of neurons in LiL_i are input values to each neuron in Li+1L_{i+1}. There is a linear function fji:R∣Li−1∣→Rf_j^i:\mathbb{R}^{|L_{i-1}|}\to\mathbb{R} associated to each neuron njin_j^i in layer LiL_i, for j∈{1,…,∣Li∣}j\in\{1,\ldots,|L_i|\} and i∈{1,…,Λ}i\in\{1,\ldots,\Lambda\}. In the context of neural networks, the coefficients of fjif_j^i are called weights, and the constant term is called the bias. For a tuple of input values x=⟨x1,…,x∣Li−1∣⟩∈R∣Li−1∣\mathbf{x}=\langle x_1,\ldots,x_{|L_{i-1}|}\rangle\in\mathbb{R}^{|L_{i-1}|} to neuron njin_j^i, it has as output the value nji(x)=ρi∘fji(x)n_j^i(\mathbf{x})=\rho_i\circ f_j^i(\mathbf{x}), where ρi:R→R\rho_i:\mathbb{R}\to\mathbb{R} is an activation function. Thus, for x=⟨x1,…,x∣Li−1∣⟩\mathbf{x}=\langle x_1,\ldots,x_{|L_{i-1}|}\rangle as input to layer LiL_i, it has as outputs the values in the tuple

Li(x)=⟨ρi∘f1i(x),…,ρi∘f∣Li∣i(x)⟩.L_i(\mathbf{x})=\langle\rho_i\circ f_1^i(\mathbf{x}),\ldots,\rho_i\circ f_{|L_i|}^i(\mathbf{x})\rangle.

Input values to NN in a tuple x=⟨x1,…,x∣L0∣⟩∈R∣L0∣\mathbf{x}=\langle x_1,\ldots,x_{|L_0|}\rangle\in\mathbb{R}^{|L_0|} are neatly associated to the neurons n10,…,n∣L0∣0∈L0n_1^0,\ldots,n_{|L_0|}^0\in L_0, called input neurons. For uniformity with the the remaining layers, each input neuron nj0n_j^0 may be regarded as receiving the whole input tuple x\mathbf{x} and computing ρ0∘fj0\rho_0\circ f_j^0, where ρ0\rho_0 is the identity function and fj0:R∣L0∣→Rf_j^0:\mathbb{R}^{|L_0|}\to\mathbb{R} is the coordinate projection given by fj0(x)=xjf_j^0(\mathbf{x})=x_j, for j∈{1,…,∣L0∣}j\in\{1,\ldots,|L_0|\}. Thus, although its formal input is the whole tuple, nj0n_j^0 effectively depends only on the jj-th input value.

In this way, from an input tuple x∈R∣L0∣\mathbf{x}\in\mathbb{R}^{|L_0|}, NN produces the output values in the ∣LΛ∣|L_\Lambda|-tuple

N(x)=⟨N(x)1,…,N(x)∣LΛ∣⟩=(LΛ∘⋯∘L0)(x).N(\mathbf{x})=\langle N(\mathbf{x})_1,\ldots,N(\mathbf{x})_{|L_\Lambda|}\rangle=(L_\Lambda\circ\cdots\circ L_0)(\mathbf{x}).

Neurons in LΛL_\Lambda are called output neurons. We say that each output neuron njΛn_j^\Lambda in a neural network NN computes a function for which the value N(x)jN(\mathbf{x})_j is given in function of the input tuple x∈R∣L0∣\mathbf{x}\in\mathbb{R}^{|L_0|}. Let us denote by NN=⋃LN∖L0\mathcal{N}_N=\bigcup\mathcal{L}_N\setminus L_0 the set of all neurons in the neural network NN, except the ones in the input layer.

The input values of a neural network may be restricted to a subset of R\mathbb{R}. In this work, we focus on ReLU–TId neural networks: they accept input values from [0,1][0,1] and have as activation functions the rectified linear unit ρi=ReLU⁡:R→R\rho_i=\operatorname{ReLU}:\mathbb{R}\to\mathbb{R}, given by ReLU⁡(x)=max⁡(0,x)\operatorname{ReLU}(x)=\max(0,x), for i∈{1,…,Λ−1}i\in\{1,\ldots,\Lambda-1\}, and the truncated identity function ρΛ=TId⁡:R→R\rho_\Lambda=\operatorname{TId}:\mathbb{R}\to\mathbb{R}, given by TId⁡(x)=max⁡(0,min⁡(1,x))\operatorname{TId}(x)=\max(0,\min(1,x)). Such activation functions are given by piecewise linear definitions as follows.

ReLU⁡(x)={0,x<0x,x≥0TId⁡(x)={0,x<0x,0≤x≤11,x>1(1)\begin{aligned} \operatorname{ReLU}(x)&=\begin{cases}0,&x<0\\x,&x\ge0\end{cases} & \operatorname{TId}(x)&=\begin{cases}0,&x<0\\x,&0\le x\le1\\1,&x>1\end{cases} \tag*{(1)} \end{aligned}

Example 2.1. Let EE be a ReLU–TId neural network with LE={L0,L1,L2}\mathcal{L}_E=\{L_0,L_1,L_2\}, where L0={n10,n20}L_0=\{n_1^0,n_2^0\}, L1={n11,n21}L_1=\{n_1^1,n_2^1\} and L2={n12}L_2=\{n_1^2\}. The graph of EE depicted in Figure 1 highlights the input values x1x_1 and x2x_2 in layer L0L_0 and the functions f11,f21,f12:R2→Rf_1^1,f_2^1,f_1^2:\mathbb{R}^2\to\mathbb{R} in layers L1L_1 and L2L_2, which are given by:

  • f11(x1,x2)=43x1−x2f_1^1(x_1,x_2)=\frac{4}{3}x_1-x_2;

  • f21(x1,x2)=x1−x2+12f_2^1(x_1,x_2)=x_1-x_2+\frac{1}{2};

  • f12(x1,x2)=x1+x2+12f_1^2(x_1,x_2)=x_1+x_2+\frac{1}{2}.

Figure 1. Graph of the ReLU–TId neural network EE

For a tuple of inputs e=⟨1/8,1/2⟩\mathbf{e} = \langle1/8,1/2\rangle to EE, we have L1(e)=⟨ReLU⁡(−1/3),ReLU⁡(1/8)⟩=⟨0,1/8⟩L_1(\mathbf{e}) = \langle\operatorname{ReLU}(-1/3),\operatorname{ReLU}(1/8)\rangle= \langle0,1/8\rangle and, thus, E(e)=L2(L1(e))=TId⁡(5/8)=5/8E(\mathbf{e}) = L_2(L_1(\mathbf{e})) = \operatorname{TId}(5/8) = 5/8.

A rational McNaughton function f:[0,1]n→[0,1]f : [0,1]^n \to[0,1] is a function that satisfies the following:

  • ff is continuous with respect to the usual topology of [0,1][0,1] as an interval of the real number line;

  • There are linear polynomials p1,…,pmp_1,\ldots,p_m over [0,1]n[0,1]^n with rational coefficients such that, for each point x∈[0,1]n\mathbf{x} \in[0,1]^n, there is an index i∈{1,…,m}i \in\{1,\ldots,m\} with f(x)=pi(x)f(\mathbf{x}) = p_i(\mathbf{x}). Polynomials p1,…,pmp_1,\ldots,p_m are the linear pieces of ff.

A neural network whose ν=∣LΛ∣\nu= |L_\Lambda| output neurons exactly compute rational McNaughton functions in function of its input neurons is called a ν\nu-rational McNaughton neural network (ν\nu-RMcN3^3); a 1-RMcN3^3 is also called rational McNaughton neural network (RMcN3^3).

A useful observation is that ReLU–TId neural networks are ν\nu-rational McNaughton neural networks [17]. Thus, once logical representations of rational McNaughton functions have been established, they naturally yield logical representations of such neural networks.

Łukasiewicz logic

To obtain logical representations of neural networks, we introduce Łukasiewicz logic (Ł\mathsf{Ł}) [5]. The basic language LŁ\mathcal{L}_{\mathsf{Ł}} of Ł\mathsf{Ł} comprehends formulas freely generated from a countable set of propositional variables P\mathsf{P}, a binary disjunction operator ⊕\oplus and a unary negation operator ¬\neg. For the semantics of Ł\mathsf{Ł}, a valuation is a function v:LŁ→[0,1]v : \mathcal{L}_{\mathsf{Ł}} \to[0,1] that obeys, for φ,ψ∈LŁ\varphi,\psi\in\mathcal{L}_{\mathsf{Ł}}:

v(¬φ)=1−v(φ); and(2)v(\neg\varphi) = 1-v(\varphi); \text{ and} \tag*{(2)}
v(φ⊕ψ)=min⁡(1,v(φ)+v(ψ)).(3)v(\varphi\oplus\psi) = \min(1,v(\varphi)+v(\psi)). \tag*{(3)}

From disjunction and negation one may derive the following operators.

Conjunction:φ⊙ψ≔¬(¬φ⊕¬ψ)v(φ⊙ψ)=max⁡(0,v(φ)+v(ψ)−1)Implication:φ→ψ≔¬φ⊕ψv(φ→ψ)=min⁡(1,1−v(φ)+v(ψ))Maximum:φ∨ψ≔¬(¬φ⊕ψ)⊕ψv(φ∨ψ)=max⁡(v(φ),v(ψ))Minimum:φ∧ψ≔¬(¬φ∨¬ψ)v(φ∧ψ)=min⁡(v(φ),v(ψ))Bi-implication:φ↔ψ≔(φ→ψ)∧(ψ→φ)v(φ↔ψ)=1−∣v(φ)−v(ψ)∣\begin{aligned} \text{Conjunction:}\quad&\varphi\odot\psi\coloneqq\neg(\neg\varphi\oplus\neg\psi) && v(\varphi\odot\psi)=\max(0,v(\varphi)+v(\psi)-1) \\ \text{Implication:}\quad&\varphi\to\psi\coloneqq\neg\varphi\oplus\psi&& v(\varphi\to\psi)=\min(1,1-v(\varphi)+v(\psi)) \\ \text{Maximum:}\quad&\varphi\lor\psi\coloneqq\neg(\neg\varphi\oplus\psi)\oplus\psi&& v(\varphi\lor\psi)=\max(v(\varphi),v(\psi)) \\ \text{Minimum:}\quad&\varphi\land\psi\coloneqq\neg(\neg\varphi\lor\neg\psi) && v(\varphi\land\psi)=\min(v(\varphi),v(\psi)) \\ \text{Bi-implication:}\quad&\varphi\leftrightarrow\psi\coloneqq(\varphi\to\psi)\land(\psi\to\varphi) && v(\varphi\leftrightarrow\psi)=1-|v(\varphi)-v(\psi)| \end{aligned}

A formula φ\varphi is satisfiable if there exists a valuation vv such that v(φ)=1v(\varphi)=1; otherwise it is unsatisfiable. A set of formulas Φ\Phi is satisfiable if there exists a valuation vv such that v(φ)=1v(\varphi)=1, for all φ∈Φ\varphi\in\Phi. Note that v(φ→ψ)=1v(\varphi\to\psi)=1 iff v(φ)≤v(ψ)v(\varphi) \le v(\psi); similarly, v(φ↔ψ)=1v(\varphi\leftrightarrow\psi)=1 iff v(φ)=v(ψ)v(\varphi)=v(\psi). Let XX be a propositional variable, then v(X⊙¬X)=0v(X \mathbin{\odot} \neg X)=0, for any v∈Valv \in\mathrm{Val}; we define the constant 00 by X⊙¬XX \mathbin{\odot} \neg X. We also define 0φ≔00\varphi\coloneqq0, 1φ≔φ1\varphi\coloneqq\varphi and nφ≔φ⊕⋯⊕φn\varphi\coloneqq\varphi\oplus\cdots\oplus\varphi, nn times, for n∈N∖{0,1}n \in\mathbb{N} \setminus\{0,1\}; and ⨁i∈∅φi≔0\bigoplus_{i\in\varnothing}\varphi_i \coloneqq0.

A well-known result due to McNaughton states that L\mathrm{L}-formulas represent McNaughton functions, which are rational McNaughton functions constrained to allow only integer coefficients in their linear pieces. This means that, given a McNaughton function f:[0,1]n→[0,1]f:[0,1]^n \to[0,1], there is a formula φf\varphi_f whose propositional variables are X1,…,Xn∈PX_1,\ldots,X_n \in\mathbb{P} such that

f(x1,…,xn)=v(φf),(4)f(x_1,\ldots,x_n)=v(\varphi_f), \tag*{(4)}

whenever vv is a valuation for which v(X1)=x1,…,v(Xn)=xnv(X_1)=x_1,\ldots,v(X_n)=x_n. Conversely, every McNaughton function is represented by some L\mathrm{L}-formula in this setting [12, 14].

Therefore, McNaughton’s Theorem guarantees that a particular class of ν\nu-rational McNaughton neural networks—namely, those computing (integer) McNaughton functions—admits logical representations within the framework of Łukasiewicz logic.

Semantics modulo satisfiability

Although L\mathrm{L}-formulas do not represent rational McNaughton functions in general, this issue may be circumvented by adopting different approaches. One possibility is to extend the language of L\mathrm{L}, yielding the rational Łukasiewicz logic, as done by Gerla [10]. The language LL\mathcal{L}_{\mathrm{L}} is extended with unary division operators δn\delta_n, for n∈N∗n \in\mathbb{N}^*, in such a way that the semantics entails v(δnφ)=v(φ)/nv(\delta_n\varphi)=v(\varphi)/n. The analogous of McNaughton’s Theorem for rational Łukasiewicz logic ensures that its formulas represent all rational McNaughton functions and, conversely, any such function may be represented by some formula in this system [12, 14].

Another approach, which we follow in this work, is to represent such functions implicitly in plain L\mathrm{L} using the technique of representation modulo satisfiability [8, 15, 16]. We introduce the latter approach below by means of some particular cases; in Section 3.1 we discuss the general case.

Let Val\mathrm{Val} denote the L\mathrm{L}-semantics, that is the set of all valuations. Also, let ValΦ\mathrm{Val}_{\Phi} denote the set of valuations v∈Valv \in\mathrm{Val} that satisfy a set of formulas Φ\Phi; we call such a restricted set of valuations a semantics modulo satisfiability. Given a rational McNaughton function f:[0,1]n→[0,1]f:[0,1]^n \to[0,1], a formula φf\varphi_f and a set of formulas Φf\Phi_f, we say that φf\varphi_f represents ff modulo Φf\Phi_f-satisfiable or that the pair ⟨φf,Φf⟩\langle\varphi_f,\Phi_f\rangle represents ff (in the system L-MODSAT) if, for distinguished propositional variables X1,…,Xn∈PX_1,\ldots,X_n \in\mathbb{P}:

  • For all ⟨x1,…,xn⟩∈[0,1]n\langle x_1,\ldots,x_n\rangle\in[0,1]^n, there exists some valuation v∈ValΦfv \in\mathrm{Val}_{\Phi_f}, such that v(Xi)=xiv(X_i)=x_i, for i=1,…,ni=1,\ldots,n;

  • For all valuations v,v′∈ValΦfv,v' \in\mathrm{Val}_{\Phi_f}, such that v(Xi)=v′(Xi)v(X_i)=v'(X_i), for i=1,…,ni=1,\ldots,n, we have v(φf)=v′(φf)v(\varphi_f)=v'(\varphi_f); and

  • f(v(X1),…,v(Xn))=v(φf)f(v(X_1),\ldots,v(X_n))=v(\varphi_f), for all v∈ValΦfv \in\mathrm{Val}_{\Phi_f}.

Example 2.2. Constant functions with value 1/b1/b, where b∈N∗b \in\mathbb{N}^{*}, may be represented by

⟨φ,Φ⟩=⟨Z1/b,{Z1/b↔¬(b−1)Z1/b}⟩(5)\langle\varphi, \Phi\rangle= \left\langle Z_{1/b}, \left\{Z_{1/b} \leftrightarrow\neg(b-1)Z_{1/b}\right\}\right\rangle \tag*{(5)}

where formula φ\varphi is only the propositional variable Z1/bZ_{1/b} and set Φ\Phi is a singleton comprehending formula Z1/b↔¬(b−1)Z1/bZ_{1/b} \leftrightarrow\neg(b-1)Z_{1/b}, which we denote by φ1/b\varphi_{1/b}. In fact, for any valuation v∈Valφ1/b≠∅v \in\mathbf{Val}_{\varphi_{1/b}} \ne\varnothing, we have that v(Z1/b)=1/bv(Z_{1/b}) = 1/b. Also, functions that take constant value a/ba/b, with a∈Na \in\mathbb{N} and a≤ba \le b, may be represented by the pair ⟨aφ,Φ⟩\langle a\varphi, \Phi\rangle.

Example 2.3. Let f:[0,1]→[0,1]f : [0,1] \to[0,1] be the function given by f(x)=x/3f(x) = x/3. It may be represented by

⟨φ,Φ⟩=⟨Z,{φ1/3,Z⊕Z⊕Z↔X,Z→Z1/3}⟩.\langle\varphi, \Phi\rangle= \left\langle Z, \left\{\varphi_{1/3}, Z \oplus Z \oplus Z \leftrightarrow X, Z \to Z_{1/3}\right\}\right\rangle.

For any valuation v∈ValΦv \in\mathbf{Val}_{\Phi}, the propositional variable ZZ is assigned one third of the value assigned to the propositional variable XX.

Note that the expressions as nψn\psi, with n∈N∖{0,1}n \in\mathbb{N} \setminus\{0,1\}, have exponential length on the binary representation of nn. By means of a semantics modulo satisfiability, such an unwanted issue is avoidable: using ⌊log⁡n⌋+1\lfloor\log n \rfloor+ 1 new propositional variables ξψ0,ξψ1,…,ξψ⌊log⁡n⌋\xi_{\psi}^{0}, \xi_{\psi}^{1}, \ldots, \xi_{\psi}^{\lfloor\log n \rfloor}, replace formula nψn\psi with

ξnψ=⨁k=0⌊log⁡n⌋ξψk.\xi_{n\psi} = \bigoplus_{k=0}^{\lfloor\log n \rfloor} \xi_{\psi}^{k}.

where nk∈{0,1}n_k \in\{0,1\} comes from the binary representation ∑k=0⌊log⁡n⌋2knk\sum_{k=0}^{\lfloor\log n \rfloor} 2^k n_k of nn, and let Ξnψ\Xi_{n\psi} be the set that comprehends the following formulas:

ξψ0↔ψ;\xi_{\psi}^{0} \leftrightarrow\psi;
ξψk↔ξψk−1⊕ξψk−1,for k=1,…,⌊log⁡n⌋.\xi_{\psi}^{k} \leftrightarrow\xi_{\psi}^{k-1} \oplus\xi_{\psi}^{k-1}, \quad\text{for } k=1,\ldots,\lfloor\log n \rfloor.

The formulas above define the propositional variables ξψk\xi_{\psi}^{k} and we have that v(nψ)=v(ξnψ)v(n\psi) = v(\xi_{n\psi}), for any valuation v∈Ξnψv \in\Xi_{n\psi}.

Any rational McNaughton function admits a representation in Ł-MODSAT [15, 16]. In particular, any truncated linear function f#:[0,1]n→[0,1]f^{\#} : [0,1]^n \to[0,1]—that is, a rational McNaughton function of the form f#(x)=defTId⁡(f(x))f^{\#}(\mathbf{x}) =_{\mathrm{def}} \operatorname{TId}(f(\mathbf{x})), where ff is a linear function—admits a polynomial representation in Ł-MODSAT. The examples given in this section are truncated linear functions for which f#=ff^{\#} = f. For details on this construction and algorithm, see [16 Section 5.2].

A note on time complexity. In order to better interpret the experimental results in § 5, let us briefly refine the running-time analysis for computing Ł-MODSAT representations of truncated linear functions. A closer inspection of [15, Algorithms 1, 2, and 3; proof of Theorem 5.6] leads us to a more explicit bound for the construction of a representation of f#f^{\#}, where

f(x1,…,xn)=γ0+γ1x1+⋯+γnxn,f(x_1,\ldots,x_n) = \gamma_0 + \gamma_1 x_1 + \cdots+ \gamma_n x_n,

and each coefficient γj\gamma_j is given as a fraction γj=aj/bj\gamma_j = a_j/b_j. Let L=∑j=0n(∥aj∥+∥bj∥)L = \sum_{j=0}^{n}(\lVert a_j\rVert+ \lVert b_j\rVert) be the length of the binary encoding of the coefficients, where ∥m∥\lVert m\rVert denotes the binary length of an integer mm. The running time of the construction may be decomposed into the time needed to compute:

  • The sets of indices P={j∈{0,…,n}:γj>0}P = \{j \in\{0,\ldots,n\} : \gamma_j > 0\} and N={j∈{0,…,n}:γj<0}N = \{j \in\{0,\ldots,n\} : \gamma_j < 0\};

  • The values αj=∣aj∣\alpha_j = \lvert a_j\rvert;

  • The factor β=⌈max⁡{∑j∈Pγj,∑j∈N∣γj∣}⌉\beta= \lceil\max\{\sum_{j\in P}\gamma_j,\sum_{j\in N}\lvert\gamma_j\rvert\}\rceil; and

  • The values βj=βbj\beta_j = \beta b_j.

Once these values have been computed, the remaining formula-construction phase takes

O((L+nlog⁡β)π)O((L+n\log\beta)\pi)

time, where π\pi is an upper bound on the length of a propositional variable identifier.

In the exact version of the algorithm, computing β\beta requires rational arithmetic, while computing the products βj\beta_j may involve arbitrary-precision integer multiplication. In practical implementations, however, the sums defining β\beta might be evaluated using fixed-precision floating-point arithmetic, while β\beta and the products βj\beta_j may be represented using fixed-width machine integers. Moreover, propositional variables might be represented by fixed-size identifiers. Under these assumptions, and provided that formulas are constructed incrementally, the construction procedure runs in time linear in LL within the computational regime supported by the implementation.

Logical twins with exponential blow-up

Lattice-based logical representations. A possibility to represent rational McNaughton functions (consequently, ν\nu-rational McNaughton neural networks) is through the regional formats. Let Ω∘\Omega^\circ denote the topological interior of Ω⊆[0,1]n\Omega\subseteq[0,1]^n and say that, given functions f,g:[0,1]n→Rf,g : [0,1]^n \to\mathbb{R}, ff is above gg over the set Ω\Omega if f(x)≥g(x)f(\mathbf{x}) \geq g(\mathbf{x}), for all x∈Ω\mathbf{x} \in\Omega. A given rational McNaughton function f:[0,1]n→[0,1]f : [0,1]^n \to[0,1] is said to be encoded in the closed regional format if it is given by mm (not necessarily distinct) linear pieces

pi(x)=γi0+γi1x1+⋯+γinxn,(6)p_i(\mathbf{x}) = \gamma_{i0}+\gamma_{i1}x_1+\cdots+\gamma_{in}x_n, \tag*{(6)}

where x=⟨x1,…,xn⟩∈[0,1]n\mathbf{x}=\langle x_1,\ldots,x_n\rangle\in[0,1]^n, γij∈Q\gamma_{ij}\in\mathbb{Q} and i∈{1,…,m}i\in\{1,\ldots,m\}, such that each pip_i is identical to ff over a polyhedron Ωi⊆[0,1]n\Omega_i\subseteq[0,1]^n, called region. These regions are determined by the finite intersection of half-spaces given by linear inequalities as

\Omega_i = \left\{\mathbf{x}\in[0,1]^n \mathrel{\left|} \omega_{j0}+\omega_{j1}x_1+\cdots+\omega_{jn}x_n\geq0,\ j\in\{1,\ldots,\lambda_{\Omega_i}\}\right.\right\} \tag*{(7)}

and such setting of linear pieces and regions satisfy the following properties:

  • ⋃i=1mΩi=[0,1]n\bigcup_{i=1}^{m}\Omega_i=[0,1]^n;

  • Ωi′∩Ωi′′=∅\Omega_{i'}\cap\Omega_{i''}=\varnothing, for i′≠i′′i'\ne i''; and

  • The lattice property: for i≠ji\ne j, there is kk such that linear piece pip_i is above linear piece pkp_k over region Ωi\Omega_i and linear piece pkp_k is above linear piece pjp_j over region Ωj\Omega_j.

The lattice property yields the possibility to represent rational McNaughton functions and ν\nu-RMcNs3^{3}_{s} by lattice representations—i.e., based on operations of maximum and minimum over functions—as follows. First, let fΩj:[0,1]n→Rf_{\Omega_j}:[0,1]^n\to\mathbb{R} be the function given by

fΩj(x)=min⁡{pk(x)∣pk is above pj over Ωj}.(8)f_{\Omega_j}(x)=\min\left\{p_k(x)\mid p_k\text{ is above }p_j\text{ over }\Omega_j\right\}. \tag*{(8)}

Note that fΩj(x)≤f(x)f_{\Omega_j}(x)\leq f(x), for all x∈[0,1]nx\in[0,1]^n, which is obvious for x∈Ωjx\in\Omega_j and follows from the lattice property for x∈Ωix\in\Omega_i where i≠ji\ne j. In this way, we have that

f(x)=max⁡{fΩj(x)∣j∈{1,…,m}}.f(x)=\max\left\{f_{\Omega_j}(x)\mid j\in\{1,\ldots,m\}\right\}.

When a rational McNaughton function is given in an encoding that nearly matches the closed regional format, except that satisfaction of the lattice property is not guaranteed, we say that it is in pre-closed regional format. In this case, however, the above construction is not guaranteed to yield a representation; for a counterexample, see [16 Example 5].

Since lattice operations are expressed in L through the minimum and maximum operators, piecewise linear functions may admit lattice representations in L whenever their linear pieces are representable in this system. The same applies when their truncated linear pieces are representable in L, as one may replace (8) by

fΩj(x)=min⁡{pk#(x)∣pk is above pj over Ωj}.(9)f_{\Omega_j}(x)=\min\left\{p_k^{\#}(x)\mid p_k\text{ is above }p_j\text{ over }\Omega_j\right\}. \tag*{(9)}

This construction yields McNaughton’s Theorem, according to which McNaughton functions are represented, in the sense of (4), by formulas of L. Another consequence is that rational McNaughton functions may be represented in the L-MODSAT system. Together with the representation of truncated linear functions (§ 2.3), the lattice representation yields a polynomial-time algorithm for such constructions from closed regional format inputs; for details, see [16 Section 5.3].

To determine whether a linear piece pp lies above qq over a region Ω\Omega, one can compute the minimum value mm of p−qp-q over Ω\Omega: if m≥0m\geq0, then pp is above qq over Ω\Omega; otherwise, it is not. Since regions are given by polyhedra as in (7), this decision problem can be solved by linear programming, which is known to be solvable in polynomial time [2]. Therefore, to construct lattice representations, m2m^2 linear programs must be solved in order to establish expressions (8) or (9).

In view of the above, establishing lattice-based logical representations in L for ReLU–TId neural networks first requires representing them in the regional formats. In the following, we sketch an algorithm for constructing such representations in pre-closed regional format.

Given a ReLU–TId neural network NN for which LN={L0,…,LΛ}\mathcal{L}_N=\{L_0,\ldots,L_{\Lambda}\}, our aim is to translate it into a tuple ΞN=⟨Ξ1,…,ΞLΛ⟩\Xi_N=\langle\Xi_1,\ldots,\Xi_{L_\Lambda}\rangle, where each Ξk\Xi_k, k∈{1,…,LΛ}k\in\{1,\ldots,L_\Lambda\}, is the codification for a rational McNaughton function in pre-closed regional format, which is the function computed by NN through the path to its kk-th output neuron. Each Ξk\Xi_k is a set of pairs ⟨p,Ω⟩\langle p,\Omega\rangle, where pp is a linear piece and Ω\Omega is its associated region.

Let us begin by analyzing the computation that takes place in each neuron of NN. Given a tuple of input values v∈R∣Li−1∣\mathbf{v} \in\mathbb{R}^{|L_{i-1}|} to neuron njin_j^i of NN, where i∈{1,…,Λ−1}i \in\{1,\ldots,\Lambda-1\} and so ρi=ReLU⁡\rho_i = \operatorname{ReLU}, the computation proceeds in two steps: first, the linear function fji(x)f_j^i(\mathbf{x}) is evaluated for x=v\mathbf{x} = \mathbf{v}; second, the activation function ReLU⁡(x)\operatorname{ReLU}(x) is evaluated for x=fji(v)x = f_j^i(\mathbf{v}). In the second step, one from the two possible values highlighted in the piecewise definition of ReLU in (1) is chosen as the output of njin_j^i. Such choice depends on the position of point v∈R∣Li−1∣\mathbf{v} \in\mathbb{R}^{|L_{i-1}|} in relation to the hyperplane given by equation fji(x)=0f_j^i(\mathbf{x}) = 0, since it may be a point lying either in the half-space given by fji(x)≤0f_j^i(\mathbf{x}) \le0 or in the half-space given by fji(x)≥0f_j^i(\mathbf{x}) \ge0. For instance, for e=⟨1/8,1/2⟩\mathbf{e} = \langle1/8,1/2\rangle as input to the neuron n11n_1^1 of EE in Example 2.1, the fact that f11(e)≤0f_1^1(\mathbf{e}) \le0 indicates that e\mathbf{e} lies in one of the half-spaces determined by f11(x)=0f_1^1(\mathbf{x}) = 0 where, according to ρ1=ReLU⁡\rho_1 = \operatorname{ReLU}, n11n_1^1 outputs 0. On the other hand, if e\mathbf{e} is given as input to the neuron n21n_2^1, as f21(e)≥0f_2^1(\mathbf{e}) \ge0, e\mathbf{e} lies in the half-space determined by f21(x)=0f_2^1(\mathbf{x}) = 0 where, according to ρ1=ReLU⁡\rho_1 = \operatorname{ReLU}, n21n_2^1 outputs f21(e)=1/8f_2^1(\mathbf{e}) = 1/8. Figure 2a depicts the position of e\mathbf{e} in relation to these hyperplanes.

Similarly, in case i=Λi = \Lambda, we have that ρi=TId⁡\rho_i = \operatorname{TId} and, then, one from three possible values is chosen for TId⁡(fjΛ(v))\operatorname{TId}(f_j^\Lambda(\mathbf{v})) depending on the position of v∈R∣LΛ−1∣\mathbf{v} \in\mathbb{R}^{|L_{\Lambda-1}|} in relation to the hyperplanes fjΛ(x)=0f_j^\Lambda(\mathbf{x}) = 0 and fjΛ(x)=1f_j^\Lambda(\mathbf{x}) = 1. It may be a point lying either in the half-space given by fjΛ(x)≤0f_j^\Lambda(\mathbf{x}) \le0, or in the half-space given by fjΛ(x)≥1f_j^\Lambda(\mathbf{x}) \ge1 or in the intersection of half-spaces fjΛ(x)≥0f_j^\Lambda(\mathbf{x}) \ge0 and fjΛ(x)≤1f_j^\Lambda(\mathbf{x}) \le1. Again, for e=⟨1/8,1/2⟩\mathbf{e} = \langle1/8,1/2\rangle as input to the neural network EE in Example 2.1, we have e1=L1(e)=⟨0,1/8⟩\mathbf{e}_1 = L_1(\mathbf{e}) = \langle0,1/8\rangle. Since f12(e1)≥0f_1^2(\mathbf{e}_1) \ge0 and f12(e1)≤1f_1^2(\mathbf{e}_1) \le1, e1\mathbf{e}_1 lies in a position relative to f12(x)=0f_1^2(\mathbf{x}) = 0 and f12(x)=1f_1^2(\mathbf{x}) = 1 where, according to ρ2=TId⁡\rho_2 = \operatorname{TId}, n12n_1^2 outputs f12(e1)=5/8f_1^2(\mathbf{e}_1) = 5/8.

Now, still considering Example 2.1, let x∈[0,1]∣L0∣\mathbf{x} \in[0,1]^{|L_0|} be any point that, as e=⟨1/8,1/2⟩\mathbf{e} = \langle1/8,1/2\rangle, satisfies both inequalities

f11(x)≤0andf21(x)≥0.(10)f_1^1(\mathbf{x}) \le0 \quad\text{and} \quad f_2^1(\mathbf{x}) \ge0. \tag*{(10)}

Then, to x1=L1(x)\mathbf{x}_1 = L_1(\mathbf{x}) satisfy inequalities f12(x1)≥0f_1^2(\mathbf{x}_1) \ge0 and f12(x1)≤1f_1^2(\mathbf{x}_1) \le1 is equivalent to x\mathbf{x} satisfy inequalities

f12(0,f12(x))≥0andf12(0,f12(x))≤1.(11)f_1^2(0,f_1^2(\mathbf{x})) \ge0 \quad\text{and} \quad f_1^2(0,f_1^2(\mathbf{x})) \le1. \tag*{(11)}

As the former inequalities (10), the latter inequalities (11) are also linear over tuples from [0,1]∣L0∣[0,1]^{|L_0|} of input values to the neural network EE. Moreover, for x∈[0,1]∣L0∣x \in[0,1]^{|L_0|} satisfying inequalities (10) and (11), we have that E(x)=f12(f21(x))E(x)=f_1^2(f_2^1(x)). In this way, we have just devised a region and its associated linear piece for the rational McNaughton function computed by neural network EE.

Generalizing the observations above, the idea behind the base algorithm for building Ξk\Xi_k, for k∈{1,…,∣LΛ∣}k \in\{1,\ldots,|L_\Lambda|\}, is to compute each pair ⟨p,Ω⟩∈Ξk\langle p,\Omega\rangle\in\Xi_k beginning by: associating a symbol between ≤\leq and ≥\geq to each neuron njin_j^i, for i<Λi<\Lambda, alluding to one of the two possible positions of an input to njin_j^i in relation to the hyperplane fji(x)=0f_j^i(x)=0—i.e., lying in the half-space fji(x)≤0f_j^i(x)\leq0 or in the half-space fji(x)≥0f_j^i(x)\geq0—; and associating a symbol among ≤\leq, ≥\geq and ⋚\lesseqgtr to the neuron nkΛn_k^\Lambda alluding to one of the three possible positions of an input to nkΛn_k^\Lambda in relation to the hyperplanes fkΛ(x)=0f_k^\Lambda(x)=0 and fkΛ(x)=1f_k^\Lambda(x)=1—i.e., lying in the half-space fkΛ(x)≤0f_k^\Lambda(x)\leq0, or in the half-space fkΛ(x)≥1f_k^\Lambda(x)\geq1 or in the intersection of the half-spaces fkΛ(x)≥0f_k^\Lambda(x)\geq0 and fkΛ(x)≤1f_k^\Lambda(x)\leq1. These associations of symbols to all the neurons in layers L1,…,LΛL_1,\ldots,L_\Lambda determine a configuration of symbols. Then, the algorithm proceeds by defining Ω⊆[0,1]∣L0∣\Omega\subseteq[0,1]^{|L_0|} as an intersection of half-spaces based on such configuration of symbols and establishing a linear expression for pp such that N(x)k=p(x)N(x)_k=p(x), for x∈Ωx\in\Omega.

Example 3.1. For the neural network EE in Example 2.1, in a configuration of symbols where we associate ≤\leq to n11n_1^1 and ≥\geq to n21n_2^1, the consequent region Ω\Omega should comprehend the inequalities 43x1−x2≤0\frac{4}{3}x_1-x_2\leq0 and x1−x2+12≥0x_1-x_2+\frac{1}{2}\geq0 (shaded area in Figure 2a). For an input x∈[0,1]2x\in[0,1]^2 that satisfies these inequalities, we have the outputs n11(x)=0n_1^1(x)=0 and n21(x)=f21(x)n_2^1(x)=f_2^1(x) which, composed with f12f_1^2, gives us the expression x1−x2+1x_1-x_2+1. In this way, in case we complete the configuration of symbols by associating ≤\leq to n1Λn_1^\Lambda, Ω\Omega should comprehend the inequality x1−x2+1≤0x_1-x_2+1\leq0 and pp should be given by p(x1,x2)=0p(x_1,x_2)=0. In case we associate ≥\geq to n1Λn_1^\Lambda, Ω\Omega should comprehend the inequality x1−x2+1≥1x_1-x_2+1\geq1 and pp should be given by p(x1,x2)=1p(x_1,x_2)=1. In the last case, if we associate ⋚\lesseqgtr to n1Λn_1^\Lambda, Ω\Omega should comprehend both inequalities x1−x2+1≤1x_1-x_2+1\leq1 and x1−x2+1≥0x_1-x_2+1\geq0 (shaded area in Figure 2b) and pp should be given by p(x1,x2)=x1−x2+1p(x_1,x_2)=x_1-x_2+1. Note that the last case is the only one where region Ω\Omega would be non-empty.

Determining a region for neural network $E$

Figure 2. Determining a region for neural network EE

In order to build the entire representative tuple ΞN=⟨Ξ1,…,Ξ∣LΛ∣⟩\Xi_N=\langle\Xi_1,\ldots,\Xi_{|L_\Lambda|}\rangle, the algorithm needs to compute all the pairs ⟨p,Ω⟩\langle p,\Omega\rangle, each one associated to a different configuration of symbols, for all possible configurations of symbols. Thus, the entire computation of ΞN\Xi_N ends up with

2∣L1∣×⋯×2∣LΛ−1∣×3∣LΛ∣2^{|L_1|}\times\cdots\times2^{|L_{\Lambda-1}|}\times3^{|L_\Lambda|}

pairs ⟨p,Ω⟩\langle p,\Omega\rangle.

For a comprehensive presentation of the base algorithm, together with auxiliary methods proposed to mitigate its high complexity, we refer the reader to our earlier LSFA 2024 paper [19]. That paper also reports empirical results showing that exponential blow-up remains unavoidable, even when such auxiliary methods are combined with the base algorithm. Interestingly, among the 1,100 randomly generated ReLU-Tld neural networks considered in those experiments, only one produced a regional representation that failed to satisfy the lattice property and therefore did not yield a representation in the closed regional format.

Architecture-based compositional logical representations.

Another approach to the logical representation of ReLU–TId neural networks, where their compositional structure is exploited, is due to Zhang and Bölcskei [21]. Following the architecture of a neural network, the logical representations of its individual neurons are composed so as to obtain a representation of the entire network. In this way, the logical representation is proportional to the graph representation, thereby avoiding the exponential blow-up associated with regional representations.

However, a generic neuron in a ReLU–TId neural network does not necessarily compute a rational McNaughton function, since hidden-layer neurons do not necessarily have both inputs and output in the unit interval [0,1][0,1]. Therefore, the network is first transformed into an equivalent one whose neurons are suitable for representation in Łukasiewicz logic. Each hidden-layer neuron, which computes a linear function composed with a ReLU activation function, is then replaced by a sequence of neurons computing linear functions composed with TId activation functions.

Such a neuron nn in the hidden layer LiL_i computes a function n:R∣Li−1∣→Rn:\mathbb{R}^{|L_{i-1}|}\to\mathbb{R}, which is given by

n(x)=ReLU⁡∘f(x),n(\mathbf{x})=\operatorname{ReLU}\circ f(\mathbf{x}),

where f:R∣Li−1∣→Rf:\mathbb{R}^{|L_{i-1}|}\to\mathbb{R} is a linear function with rational coefficients. The output of nn lies in the nonnegative real half-line [0,+∞)[0,+\infty).

As the inputs of a ReLU–TId neural network are constrained to [0,1][0,1], it follows that the input and output of every neuron in the network, each of which computes a continuous function, are constrained to a closed interval. Let MM be the maximum output value attained by neuron nn. Then the computation of nn may be replaced by the sum of the outputs of ⌊M⌋+1\lfloor M\rfloor+1 neurons

t0,t1,…,t⌊M⌋:R∣Li−1∣→R,t_0,t_1,\ldots,t_{\lfloor M\rfloor}:\mathbb{R}^{|L_{i-1}|}\to\mathbb{R},

given by

tι(x)=TId⁡∘(f(x)−ι),t_{\iota}(\mathbf{x})=\operatorname{TId}\circ\left(f(\mathbf{x})-\iota\right),

for ι=0,…,⌊M⌋\iota=0,\ldots,\lfloor M\rfloor, where each f(x)−ιf(\mathbf{x})-\iota is still a linear function with rational coefficients. In fact, assuming x∈[0,1]∣Li−1∣\mathbf{x}\in[0,1]^{|L_{i-1}|}, we have

n(x)=t0(x)+⋯+t⌊M⌋(x).n(\mathbf{x})=t_0(\mathbf{x})+\cdots+t_{\lfloor M\rfloor}(\mathbf{x}).

Note that, since the output of each tιt_{\iota} is constrained to the unit interval [0,1][0,1], these neurons compute rational McNaughton functions provided that their inputs are also constrained to [0,1][0,1]. Particularly, with such a constraint, a neuron tιt_{\iota} computes a truncated linear function.

Once each neuron njn_j, for j∈{1,…,∣Li∣}j\in\{1,\ldots,|L_i|\}, has been replaced in a hidden layer LiL_i by a sequence of neurons t(j,0),…,t(j,Mj)t_{(j,0)},\ldots,t_{(j,M_j)}, each neuron mm in layer Li+1L_{i+1} must be adapted to this new input configuration. Let MjM_j be the maximum output value attained by the original neuron njn_j, and let

M=⌊M1⌋+⋯+⌊M∣Li∣⌋+∣Li∣.\mathcal{M}=\lfloor M_1\rfloor+\cdots+\lfloor M_{|L_i|}\rfloor+|L_i|.

Suppose that mm computes the function

m(x)=ρ∘g(x),m(\mathbf{x})=\rho\circ g(\mathbf{x}),

where ρ∈{TId,ReLU}\rho\in\{\mathrm{TId},\mathrm{ReLU}\} and g:R∣Li∣→Rg:\mathbb{R}^{|L_i|}\to\mathbb{R} is given by

g(x)=γ0+γ1x1+⋯+γ∣Li∣x∣Li∣,g(\mathbf{x})=\gamma_0+\gamma_1x_1+\cdots+\gamma_{|L_i|}x_{|L_i|},

for x∈R∣Li∣\mathbf{x}\in\mathbb{R}^{|L_i|}. Then mm is replaced by a neuron mˉ\bar{m}, which receives M\mathcal{M} inputs and computes the function

mˉ(xˉ)=ρ∘gˉ(xˉ),\bar{m}(\bar{\mathbf{x}})=\rho\circ\bar{g}(\bar{\mathbf{x}}),

where gˉ:RM→R\bar{g}:\mathbb{R}^{\mathcal{M}}\to\mathbb{R} is given by

gˉ(xˉ)=γ0+(γ1x(1,0)+⋯+γ1x(1,⌊M1⌋))+⋯+(γ∣Li∣x(∣Li∣,0)+⋯+γ∣Li∣x(∣Li∣,M∣Li∣)),\bar{g}(\bar{\mathbf{x}})=\gamma_0+\left(\gamma_1x_{(1,0)}+\cdots+\gamma_1x_{(1,\lfloor\mathcal{M}_1\rfloor)}\right) +\cdots+\left(\gamma_{|L_i|}x_{(|L_i|,0)}+\cdots+\gamma_{|L_i|}x_{(|L_i|,\mathcal{M}_{|L_i|})}\right),

for xˉ∈RM\bar{\mathbf{x}}\in\mathbb{R}^{\mathcal{M}}. Originally, the variable xjx_j in gg was intended to receive the output of neuron njn_j; now, the variable x(j,ι)x_{(j,\iota)} in gˉ\bar{g} is intended to receive the output of neuron t(j,ι)t_{(j,\iota)}. Note that gˉ\bar{g} is still a linear function with rational coefficients.

Example 3.2. For the neural network EE in Example 2.1, the maximum value computed by function f21f^1_2 is M2=1.5M_2=1.5. Therefore, neuron n21n^1_2 should be replaced by two neurons t(2,0)1t^1_{(2,0)} and t(2,1)1t^1_{(2,1)}, whose associated linear functions are, respectively, given by:

  • f(2,0)1(x1,x2)=f21(x1,x2)−0=x1−x2+1/2f^1_{(2,0)}(x_1,x_2)=f^1_2(x_1,x_2)-0=x_1-x_2+1/2; and

  • f(2,1)1(x1,x2)=f21(x1,x2)−1=x1−x2−1/2f^1_{(2,1)}(x_1,x_2)=f^1_2(x_1,x_2)-1=x_1-x_2-1/2.

Neuron n11n^1_1 should also be replaced by two neurons—namely, t(1,0)1t^1_{(1,0)} and t(1,1)1t^1_{(1,1)}. Then, neuron n12n^2_1 should be replaced by a neuron nˉ12\bar{n}^2_1 associated to linear function fˉ12:R4→R\bar{f}^2_1:\mathbb{R}^4\to\mathbb{R}, given by

fˉ12(x(1,0),x(1,1),x(2,0),x(2,1))=x(1,0)+x(1,1)+x(2,0)+x(2,1)+1/2.\bar{f}^2_1\left(x_{(1,0)},x_{(1,1)},x_{(2,0)},x_{(2,1)}\right)=x_{(1,0)}+x_{(1,1)}+x_{(2,0)}+x_{(2,1)}+1/2.

Therefore, the transformation of a neural network proceeds one layer at a time, starting from layer L1L_1: each neuron nn in layer LiL_i, whose input values lie in [0,1][0,1], is replaced by a sequence of ⌊M⌋+1\lfloor M\rfloor+1 neurons tιt_\iota, whose output values also lie in [0,1][0,1]. Then, before the same procedure is applied to the neurons in layer Li+1L_{i+1}, they must first be adapted to receive M\mathcal{M} inputs, whereas originally they received only ∣Li∣≤M|L_i|\leq\mathcal{M}. Note that the neurons in layer L1L_1 do not require any adaptation of their input values, since the inputs to a ReLU–TId neural network already lie in [0,1][0,1]. Likewise, the neurons in the output layer LΛL_\Lambda do not need to be replaced by a sequence of neurons tιt_\iota, since they already compute the TId activation function.

Let N′N' be the neural network obtained from a ReLU–TId neural network NN by the transformation discussed above. In [21], the function computed by each neuron nn in NN′N_{N'}, which is a rational McNaughton function, is first represented, in the traditional sense, by a formula φn\varphi_n of Łukasiewicz logic or rational Łukasiewicz logic, depending on whether the weights are integers or rational numbers. Let φn1,…,φn∣Li∣\varphi_{n_1},\ldots,\varphi_{n_{|L_i|}} be the representations of the functions computed by the neurons n1,…,n∣Li∣n_1,\ldots,n_{|L_i|} in layer LiL_i. Also, let X1,…,X∣Li∣X_1,\ldots,X_{|L_i|} be the propositional variables corresponding to the variables x1,…,x∣Li∣x_1,\ldots,x_{|L_i|} in the function computed by a neuron mm in layer Li+1L_{i+1}. Then the composition of neurons yields a representation by replacing each XjX_j in φm\varphi_m with φnj\varphi_{n_j}. Performing these substitutions throughout the compositions in N′N' yields a formula φN\varphi_N that is a logical twin of N′N', and hence of NN.

Going beyond [21], we now show how to adapt these representations to the L-MODSAT setting. Let ⟨φn,Φn⟩\langle\varphi_n,\Phi_n\rangle be a representation in the L-MODSAT system of the function computed by each neuron n∈NN′n \in\mathcal{N}_{N'}. In this setting, the propositional variables XjX_j corresponding to the function variables xjx_j must be distinct across neurons in different layers. Thus, we write such variables as the interface propositional variables XjiX_j^i, to indicate their association with Layer LiL_i. Moreover, let us agree that such propositional variables XjiX_j^i are the only ones shared among representations ⟨φn,Φ⟩\langle\varphi_n,\Phi\rangle. Let nn be a neuron in layer LiL_i whose output feeds the function variable xjx_j of a neuron mm in layer Li+1L_{i+1}. Then, instead of composing formulas directly, we may simulate this composition by asserting the linking formulas φn↔Hn\varphi_n \leftrightarrow H_n and Hn↔Xji+1H_n \leftrightarrow X_j^{i+1}, where HnH_n is a fresh propositional variable associated with neuron nn. This technique avoids repeating the whole formula φn\varphi_n, which encodes an input to all neurons in layer Li+1L_{i+1}, reducing the representation complexity.

Let us write XjX_j for the propositional variables intended to be evaluated with the inputs to the network; these are evaluated according to the input tuple x=⟨x1,…,x∣L0∣⟩\boldsymbol{x}=\langle x_1,\ldots,x_{|L_0|}\rangle, whose components correspond to the input neurons in layer L0L_0. Also, let nkΛn_k^\Lambda be an output neuron of N′N'. Then, the function computed by N′N' with output at nkΛn_k^\Lambda is represented in L-MODSAT by the pair ⟨φNk,ΦN⟩\langle\varphi_N^k,\Phi_N\rangle, where

φNk≔HnkΛ,\varphi_N^k \coloneqq H_{n_k^\Lambda},
ΦN≔⋃n∈NN′Φn∪⋃n∈NN′{φn↔Hn}∪⋃j=1∣L0∣{Xj↔Xj1}∪{Hnji↔Xji+1:nji∈Li, i∈{1,…,Λ−1}}.\Phi_N \coloneqq\bigcup_{n\in\mathcal{N}_{N'}}\Phi_n \cup\bigcup_{n\in\mathcal{N}_{N'}}\{\varphi_n\leftrightarrow H_n\} \cup\bigcup_{j=1}^{|L_0|}\{X_j\leftrightarrow X_j^1\} \cup\{H_{n_j^i}\leftrightarrow X_j^{i+1}:n_j^i\in L_i,\ i\in\{1,\ldots,\Lambda-1\}\}.

In this way, for every L-valuation vv satisfying ΦN\Phi_N and such that v(X1)=x1,…,v(X∣L0∣)=x∣L0∣v(X_1)=x_1,\ldots,v(X_{|L_0|})=x_{|L_0|}, we have

v(φNk)=Nk′(x1,…,x∣L0∣)=Nk(x1,…,x∣L0∣).v(\varphi_N^k)=N_k'(x_1,\ldots,x_{|L_0|})=N_k(x_1,\ldots,x_{|L_0|}).

Therefore, the pairs ⟨φN1,ΦN⟩,…,⟨φN∣LΛ∣,ΦN⟩\langle\varphi_N^1,\Phi_N\rangle,\ldots,\langle\varphi_N^{|L_\Lambda|},\Phi_N\rangle constitute a logical twin of N′N', and hence of NN. In the next section, we revisit in greater detail the representations given by the pairs ⟨φNk,ΦN⟩\langle\varphi_N^k,\Phi_N\rangle.

To conclude this exposition, we note that, while following the architecture of the neural network avoids the exponential blow-up associated with regional representations, there is still no guarantee that replacing each neuron nn by ⌊M⌋+1\lfloor M\rfloor+1 neurons tℓt_\ell will not itself result in such a blow-up. Note that, if ⌊M⌋\lfloor M\rfloor is encoded in binary, then a quantity proportional to ⌊M⌋\lfloor M\rfloor is only pseudo-polynomial: it is polynomial in the numerical value of ⌊M⌋\lfloor M\rfloor, but exponential in the length of its binary representation.

A polynomial-size logical twin

Inspired by the logical twins introduced in the previous section, we now present a new architecture-based compositional representation founded on the L-MODSAT framework. As in the previous construction, following the network architecture avoids the exponential blow-up associated with regional formats. The crucial difference, however, is that the present proposal starts from a ReLU–TId neural network NN and yields an equivalent neural network N′N' with the same number of neurons, thus avoiding the possible exponential blow-up arising from the use of a much larger equivalent network.

When establishing an equivalent network in this approach, each neuron may undergo two normalizing transformations: input normalization and output normalization. Recall that, since the inputs to a ReLU–TId neural network lie in [0,1][0,1] and each neuron computes a continuous function, the output of every neuron is constrained to a closed interval.

The output normalization consists in replacing a neuron nn with a neuron tt whose output lies in the unit interval [0,1][0,1]. Let nn be a neuron in a hidden layer LiL_i computing a function n:R∣Li−1∣→Rn:\mathbb{R}^{|L_{i-1}|}\to\mathbb{R}, given by

n(x)=ReLU⁡∘f(x),(12)n(\mathbf{x})=\operatorname{ReLU}\circ f(\mathbf{x}), \tag*{(12)}

where f:R∣Li−1∣→Rf:\mathbb{R}^{|L_{i-1}|}\to\mathbb{R} is a linear function with rational coefficients. Let MM be the maximum value attained by nn, assuming that its inputs are constrained to [0,1][0,1]; so we have M∈QM\in\mathbb{Q}. Then, we define neuron t:R∣Li−1∣→Rt:\mathbb{R}^{|L_{i-1}|}\to\mathbb{R}, given by

t(x)={TId⁡∘(f(x)M),if M≠0,TId⁡∘f(x),if M=0.(13)t(\mathbf{x})= \begin{cases} \operatorname{TId}\circ\left(\dfrac{f(\mathbf{x})}{M}\right), & \text{if } M\ne0,\\ \operatorname{TId}\circ f(\mathbf{x}), & \text{if } M=0. \end{cases} \tag*{(13)}

Neuron tt computes a rational McNaughton function, particularly a truncated linear function, provided that its inputs are constrained to [0,1][0,1]. Moreover, the outputs of the original neuron nn can be easily recovered, as stated in the following result.

Lemma 4.1. Let n:R∣Li−1∣→Rn:\mathbb{R}^{|L_{i-1}|}\to\mathbb{R} be a neuron in the hidden layer LiL_i given by (12), and let MM be the maximum value attained by nn, assuming that its inputs are constrained to the unit interval [0,1][0,1]. Also, let t:R∣Li−1∣→Rt:\mathbb{R}^{|L_{i-1}|}\to\mathbb{R} be the neuron obtained from nn by output normalization as in (13). Then the output of tt is guaranteed to lie in [0,1][0,1], and

n(x)=M⋅t(x),n(\mathbf{x})=M\cdot t(\mathbf{x}),

for every x∈[0,1]∣Li−1∣\mathbf{x}\in[0,1]^{|L_{i-1}|}.

Proof. The output of tt is in [0,1][0,1] due TId being its activation function. Let x∈[0,1]∣Li−1∣\mathbf{x}\in[0,1]^{|L_{i-1}|}. First, let M>0M>0. If f(x)≤0f(\mathbf{x})\le0, then n(x)=t(x)=0n(\mathbf{x})=t(\mathbf{x})=0, since nn and tt activation functions are ReLU and TId, respectively. If f(x)>0f(\mathbf{x})>0, then noting that 0≤f(x)/M≤10\le f(\mathbf{x})/M\le1, we have that

M⋅t(x)=M⋅TId⁡(f(x)M)=M⋅f(x)M=f(x)=ReLU⁡(f(x))=n(x).M\cdot t(\mathbf{x})=M\cdot\operatorname{TId}\left(\frac{f(\mathbf{x})}{M}\right)=M\cdot\frac{f(\mathbf{x})}{M}=f(\mathbf{x})=\operatorname{ReLU}(f(\mathbf{x}))=n(\mathbf{x}).

The case M=0M=0 is obvious.

Note that output normalization is not necessary if M<1M < 1. In this case, we already have that n(x)=ReLU⁡(f(x))=TId⁡(f(x))∈[0,1]n(\mathbf{x}) = \operatorname{ReLU}(f(\mathbf{x})) = \operatorname{TId}(f(\mathbf{x})) \in[0,1], for x∈[0,1]∣L0∣\mathbf{x} \in[0,1]^{|L_0|}.

Now, once each neuron njn_j, j∈{1,…,∣Li∣}j \in\{1,\ldots,|L_i|\}, has been replaced in a hidden layer LiL_i by its output-normalized version, each neuron mm in layer Li+1L_{i+1} must be adapted in order to preserve the coherence of the network. To this end, each neuron mm is replaced by a neuron m‾\overline{m} through a procedure called input normalization. Let MjM_j be the maximum output value attained by the original neuron njn_j, and suppose that mm computes the function

m(x)=ρ∘g(x),(14)m(\mathbf{x}) = \rho\circ g(\mathbf{x}), \tag*{(14)}

where ρ∈{ReLU⁡,TId⁡}\rho\in\{\operatorname{ReLU},\operatorname{TId}\} and g:R∣Li∣→Rg : \mathbb{R}^{|L_i|} \to\mathbb{R} is given by

g(x)=γ0+γ1x1+⋯+γ∣Li∣x∣Li∣,g(\mathbf{x}) = \gamma_0 + \gamma_1 x_1 + \cdots+ \gamma_{|L_i|}x_{|L_i|},

for x∈R∣Li∣\mathbf{x} \in\mathbb{R}^{|L_i|}. Then mm is replaced by a neuron m‾\overline{m} that computes the function

m‾(x)=ρ∘g‾(x),(15)\overline{m}(\mathbf{x}) = \rho\circ\overline{g}(\mathbf{x}), \tag*{(15)}

where g‾:R∣Li∣→R\overline{g} : \mathbb{R}^{|L_i|} \to\mathbb{R} is given by

g‾(x)=γ0+(γ1⋅M1)x1+⋯+(γ∣Li∣⋅M∣Li∣)x∣Li∣,\overline{g}(\mathbf{x}) = \gamma_0 + (\gamma_1 \cdot M_1)x_1 + \cdots+ (\gamma_{|L_i|} \cdot M_{|L_i|})x_{|L_i|},

for x∈R∣Li∣\mathbf{x} \in\mathbb{R}^{|L_i|}. Again, g‾\overline{g} is a linear function with rational coefficients. Moreover, input normalization ensures that the output normalization performed in layer LiL_i leaves the outputs of m‾\overline{m} unchanged, as established by the following result.

Lemma 4.2. Let nj:R∣Li−1∣→Rn_j : \mathbb{R}^{|L_{i-1}|} \to\mathbb{R} be a neuron in layer LiL_i with maximum output value MjM_j on [0,1]∣Li−1∣[0,1]^{|L_{i-1}|}, and let tj:R∣Li−1∣→Rt_j : \mathbb{R}^{|L_{i-1}|} \to\mathbb{R} be its output-normalized version, for each j∈{1,…,∣Li∣}j \in\{1,\ldots,|L_i|\}. Also, let m‾:R∣Li∣→R\overline{m} : \mathbb{R}^{|L_i|} \to\mathbb{R} be the neuron obtained from a neuron m:R∣Li∣→Rm : \mathbb{R}^{|L_i|} \to\mathbb{R} in layer Li+1L_{i+1}, given by (14), through input normalization regarding neurons tjt_j, as in (15). Then,

m‾(t1(x),…,t∣Li∣(x))=m(n1(x),…,n∣Li∣(x)),\overline{m}(t_1(\mathbf{x}),\ldots,t_{|L_i|}(\mathbf{x})) = m(n_1(\mathbf{x}),\ldots,n_{|L_i|}(\mathbf{x})),

for every x∈[0,1]∣Li−1∣\mathbf{x} \in[0,1]^{|L_{i-1}|}.

Proof. For each j∈{1,…,∣Li∣}j \in\{1,\ldots,|L_i|\} and every x∈[0,1]∣Li−1∣\mathbf{x} \in[0,1]^{|L_{i-1}|}, Lemma 4.1 guarantees that

nj(x)=Mj⋅tj(x).n_j(\mathbf{x}) = M_j \cdot t_j(\mathbf{x}).

Hence, by the definitions of mm and m‾\overline{m} in (14) and (15), respectively,

g‾(t1(x),…,t∣Li∣(x))=γ0+(γ1M1)t1(x)+⋯+(γ∣Li∣M∣Li∣)t∣Li∣(x)=γ0+γ1n1(x)+⋯+γ∣Li∣n∣Li∣(x)=g(n1(x),…,n∣Li∣(x)).\begin{aligned} \overline{g}(t_1(\mathbf{x}),\ldots,t_{|L_i|}(\mathbf{x})) &= \gamma_0 + (\gamma_1M_1)t_1(\mathbf{x}) + \cdots+ (\gamma_{|L_i|}M_{|L_i|})t_{|L_i|}(\mathbf{x}) \\ &= \gamma_0 + \gamma_1n_1(\mathbf{x}) + \cdots+ \gamma_{|L_i|}n_{|L_i|}(\mathbf{x}) \\ &= g(n_1(\mathbf{x}),\ldots,n_{|L_i|}(\mathbf{x})). \end{aligned}

Therefore,

m‾(t1(x),…,t∣Li∣(x))=ρ(g‾(t1(x),…,t∣Li∣(x)))=ρ(g(n1(x),…,n∣Li∣(x)))=m(n1(x),…,n∣Li∣(x)).\begin{aligned} \overline{m}(t_1(\mathbf{x}),\ldots,t_{|L_i|}(\mathbf{x})) &= \rho(\overline{g}(t_1(\mathbf{x}),\ldots,t_{|L_i|}(\mathbf{x}))) \\ &= \rho(g(n_1(\mathbf{x}),\ldots,n_{|L_i|}(\mathbf{x}))) \\ &= m(n_1(\mathbf{x}),\ldots,n_{|L_i|}(\mathbf{x})). \end{aligned}

Example 4.3. For the neural network EE in Example 2.1, the maximum values computed by functions f11f_1^1 and f21f_2^1 are M1=4/3M_1=4/3 and M2=3/2M_2=3/2. Therefore, neurons n11n_1^1 and n21n_2^1 should be replaced by two neurons t1t_1 and t2t_2, respectively, whose associated linear functions are, respectively, given by:

  • f11(x1,x2)/M1=x1−3/4x2f_1^1(x_1,x_2)/M_1=x_1-3/4x_2; and

  • f21(x1,x2)/M2=2/3x1−2/3x2+1/3f_2^1(x_1,x_2)/M_2=2/3x_1-2/3x_2+1/3.

Then, neuron n21n_2^1 should be replaced by a neuron nˉ21\bar{n}_2^1 associated to linear function fˉ12:R4→R\bar{f}_1^2:\mathbb{R}^4\to\mathbb{R}, given by

fˉ12(x1,x2)=4/3x1+3/2x2+1/2.\bar{f}_1^2(x_1,x_2)=4/3x_1+3/2x_2+1/2.

Again in this proposal, the transformation of a neural network proceeds one layer at a time, starting from layer L1L_1: each neuron nn in layer LiL_i, whose input values lie in [0,1][0,1], is replaced by its output-normalized version tt, whose output value also lie in [0,1][0,1]. Then, before the same procedure is applied to the neurons in layer Li+1L_{i+1}, those neurons are first replaced by their input-normalized versions. The neurons in layer L1L_1 do not require input normalization, since the inputs to a ReLU–TId neural network already lie in [0,1][0,1]; equivalently, they may be normalized using Mj=1M_j=1, for j∈{1,…,∣L0∣}j\in\{1,\ldots,|L_0|\}. Likewise, the neurons in the output layer LΛL_\Lambda do not require output normalization, since they already compute the TId activation function.

Theorem 4.4. Let NN be a ReLU–TId neural network with LN={L0,…,LΛ}\mathcal{L}_N=\{L_0,\ldots,L_\Lambda\}, where Λ>1\Lambda>1, and let N′N' be a neural network obtained from NN, one layer at a time starting from layer L1L_1, in such a way that:

  • Layer L1L_1 of N′N' is obtained from layer L1L_1 of NN by output normalization of its neurons;

  • For each i∈{2,…,Λ−1}i\in\{2,\ldots,\Lambda-1\}, layer LiL_i of N′N' is obtained from layer LiL_i of NN by first applying input normalization to its neurons, according to the MjM_j-values arising from the output normalization of layer Li−1L_{i-1}, and then applying output normalization to its neurons;

  • Layer LΛL_\Lambda of N′N' is obtained from layer LΛL_\Lambda of NN by input normalization of its neurons.

Then NN and N′N' are equivalent, in the sense that N(x)=N′(x)N(x)=N'(x), for every x∈[0,1]∣L0∣x\in[0,1]^{|L_0|}.

Proof. Let x∈[0,1]∣L0∣x\in[0,1]^{|L_0|} be an input tuple. For each i∈{0,…,Λ}i\in\{0,\ldots,\Lambda\}, let

yi(x)≔(Li∘⋯∘L0)(x)andzi(x)≔(Li′∘⋯∘L0′)(x),\mathbf{y}^i(\mathbf{x})\coloneqq(L_i\circ\cdots\circ L_0)(\mathbf{x})\qquad\text{and}\qquad\mathbf{z}^i(\mathbf{x})\coloneqq(L'_i\circ\cdots\circ L'_0)(\mathbf{x}),

where Li′L'_i is the ii-th layer of N′N'; note that L0′=L0L'_0=L_0. Thus, yi(x)\mathbf{y}^i(\mathbf{x}) and zi(x)\mathbf{z}^i(\mathbf{x}) are the output tuples of the ii-th layers of NN and N′N', respectively. Also, let n~ji\tilde{n}_j^i stand for the neuron obtained from nji∈NNn_j^i\in\mathcal{N}_N after input normalization, and let nˉji∈NN′\bar{n}_j^i\in\mathcal{N}_{N'} stand for the neuron obtained from n~ji\tilde{n}_j^i after output normalization. If i=1i=1, let n~j1=nj1\tilde{n}_j^1=n_j^1, and if i=Λi=\Lambda, let nˉjΛ=n~jΛ\bar{n}_j^\Lambda=\tilde{n}_j^\Lambda.

For each hidden layer LiL_i, with i∈{1,…,Λ−1}i\in\{1,\ldots,\Lambda-1\}, write

yi(x)=⟨y1i(x),…,y∣Li∣i(x)⟩andzi(x)=⟨z1i(x),…,z∣Li∣i(x)⟩.\mathbf{y}^i(\mathbf{x})=\langle y_1^i(\mathbf{x}),\ldots,y_{|L_i|}^i(\mathbf{x})\rangle\qquad\text{and}\qquad\mathbf{z}^i(\mathbf{x})=\langle z_1^i(\mathbf{x}),\ldots,z_{|L_i|}^i(\mathbf{x})\rangle.

We claim that, for every i∈{1,…,Λ−1}i\in\{1,\ldots,\Lambda-1\} and every j∈{1,…,∣Li∣}j\in\{1,\ldots,|L_i|\}, there exists a value MjiM_j^i, namely the maximum value attained by the neuron n~ji\tilde{n}_j^i on [0,1]∣Li−1∣[0,1]^{|L_{i-1}|}, such that

yji(x)=Mjizji(x).(16)y_j^i(\mathbf{x}) = M_j^i z_j^i(\mathbf{x}). \tag*{(16)}

For i=1i=1, the layer L1′L'_1 is obtained from L1L_1 only by output normalization. Hence, by Lemma 4.1,

yj1(x)=Mj1zj1(x),y_j^1(\mathbf{x}) = M_j^1 z_j^1(\mathbf{x}),

for every j∈{1,…,∣L1∣}j \in\{1,\ldots,|L_1|\}.

Now assume that (16) holds for some i∈{1,…,Λ−2}i \in\{1,\ldots,\Lambda-2\}. Fix j∈{1,…,∣Li+1∣}j \in\{1,\ldots,|L_{i+1}|\}. Since zi−1(x)∈[0,1]∣Li−1∣\mathbf{z}^{i-1}(\mathbf{x}) \in[0,1]^{|L_{i-1}|}, Lemma 4.2 yields

n~ji+1(zi(x))=n~ji+1(n~1i(zi−1(x)),…,n~∣Li∣i(zi−1(x)))=nji+1(n~1i(zi−1(x)),…,n~∣Li∣i(zi−1(x))).\begin{aligned} \widetilde{n}_j^{i+1}\left(\mathbf{z}^i(\mathbf{x})\right) = \widetilde{n}_j^{i+1}\left(\widetilde{n}_1^i\left(\mathbf{z}^{i-1}(\mathbf{x})\right),\ldots,\widetilde{n}_{|L_i|}^i\left(\mathbf{z}^{i-1}(\mathbf{x})\right)\right) \\ &= n_j^{i+1}\left(\widetilde{n}_1^i\left(\mathbf{z}^{i-1}(\mathbf{x})\right),\ldots,\widetilde{n}_{|L_i|}^i\left(\mathbf{z}^{i-1}(\mathbf{x})\right)\right). \end{aligned}

On the other hand, for each ℓ∈{1,…,∣Li∣}\ell\in\{1,\ldots,|L_i|\}, by Lemma 4.1 and the induction hypothesis,

n~ℓi(zi−1(x))=Mℓi⋅n~ℓi(zi−1(x))=Mℓi⋅zℓi(x)=yℓi(x).\widetilde{n}_\ell^i\left(\mathbf{z}^{i-1}(\mathbf{x})\right) = M_\ell^i \cdot\widetilde{n}_\ell^i\left(\mathbf{z}^{i-1}(\mathbf{x})\right) = M_\ell^i \cdot z_\ell^i(\mathbf{x}) = y_\ell^i(\mathbf{x}).

Therefore,

n~ji+1(zi(x))=nji+1(yi(x)).\widetilde{n}_j^{i+1}\left(\mathbf{z}^i(\mathbf{x})\right) = n_j^{i+1}\left(\mathbf{y}^i(\mathbf{x})\right).

Since n~ji+1\widetilde{n}_j^{i+1} is the output-normalized version of n~ji+1\widetilde{n}_j^{i+1}, Lemma 4.1 yields

n~ji+1(zi(x))=Mji+1n~ji+1(zi(x)).\widetilde{n}_j^{i+1}\left(\mathbf{z}^i(\mathbf{x})\right) = M_j^{i+1}\widetilde{n}_j^{i+1}\left(\mathbf{z}^i(\mathbf{x})\right).

Hence,

nji+1(yi(x))=Mji+1n~ji+1(zi(x)),n_j^{i+1}\left(\mathbf{y}^i(\mathbf{x})\right) = M_j^{i+1}\widetilde{n}_j^{i+1}\left(\mathbf{z}^i(\mathbf{x})\right),

that is,

yji+1(x)=Mji+1zji+1(x).y_j^{i+1}(\mathbf{x}) = M_j^{i+1}z_j^{i+1}(\mathbf{x}).

This proves (16) for all i∈{1,…,Λ−1}i \in\{1,\ldots,\Lambda-1\}.

Finally, consider the output layer LΛL_\Lambda. By construction, LΛ′L'_\Lambda is obtained from LΛL_\Lambda only by input normalization. Fix j∈{1,…,∣LΛ∣}j \in\{1,\ldots,|L_\Lambda|\}. Since zΛ−2(x)∈[0,1]∣LΛ−2∣\mathbf{z}^{\Lambda-2}(\mathbf{x}) \in[0,1]^{|L_{\Lambda-2}|}, Lemma 4.2 yields

n~jΛ(zΛ−1(x))=njΛ(n~1Λ−1(zΛ−2(x)),…,n~∣LΛ−1∣Λ−1(zΛ−2(x))).\widetilde{n}_j^\Lambda\left(\mathbf{z}^{\Lambda-1}(\mathbf{x})\right) = n_j^\Lambda\left(\widetilde{n}_1^{\Lambda-1}\left(\mathbf{z}^{\Lambda-2}(\mathbf{x})\right),\ldots,\widetilde{n}_{|L_{\Lambda-1}|}^{\Lambda-1}\left(\mathbf{z}^{\Lambda-2}(\mathbf{x})\right)\right).

By Lemma 4.1 and (16) for i=Λ−1i=\Lambda-1, for every ℓ∈{1,…,∣LΛ−1∣}\ell\in\{1,\ldots,|L_{\Lambda-1}|\} we have

n~ℓΛ−1(zΛ−2(x))=MℓΛ−1n~ℓΛ−1(zΛ−2(x))=MℓΛ−1zℓΛ−1(x)=yℓΛ−1(x).\widetilde{n}_\ell^{\Lambda-1}\left(\mathbf{z}^{\Lambda-2}(\mathbf{x})\right) = M_\ell^{\Lambda-1}\widetilde{n}_\ell^{\Lambda-1}\left(\mathbf{z}^{\Lambda-2}(\mathbf{x})\right) = M_\ell^{\Lambda-1}z_\ell^{\Lambda-1}(\mathbf{x}) = y_\ell^{\Lambda-1}(\mathbf{x}).

Therefore,

zjΛ(x)=n~jΛ(zΛ−1(x))=njΛ(yΛ−1(x))=yjΛ(x).z_j^\Lambda(\mathbf{x}) = \widetilde{n}_j^\Lambda\left(\mathbf{z}^{\Lambda-1}(\mathbf{x})\right) = n_j^\Lambda\left(\mathbf{y}^{\Lambda-1}(\mathbf{x})\right) = y_j^\Lambda(\mathbf{x}).

Hence,

N′(x)=zΛ(x)=yΛ(x)=N(x),N'(\mathbf{x}) = \mathbf{z}^\Lambda(\mathbf{x}) = \mathbf{y}^\Lambda(\mathbf{x}) = N(\mathbf{x}),

for every x∈[0,1]∣L0∣\mathbf{x} \in[0,1]^{|L_0|}.

Let us now proceed to the representation in L-MODSAT of a ReLU–TId neural network NN by means of its equivalent network N′N', as established by the theorem above, following the same path sketched in Section 3.2. Since each neuron n∈NN′n \in\mathcal{N}_{N'} computes a truncated linear function, let ⟨φn,Φn⟩\langle\varphi_n,\Phi_n\rangle be its representation in the L-MODSAT system. Let XjiX_j^i denote the propositional variable in pairs ⟨φn,Φn⟩\langle\varphi_n,\Phi_n\rangle corresponding to the function variable xjx_j of the functions computed by the neurons n∈Lin \in L_i. The propositional variables X1,…,X∣L0∣X_1,\ldots,X_{\lvert L_0\rvert} are intended to be evaluated with the inputs to the network N′N'. Also, for each neuron nn, let HnH_n be a fresh propositional variable. Then, the function computed by N′N' with output at neuron nkΛn_k^\Lambda is represented in L-MODSAT by the pair ⟨φNk,ΦN⟩\langle\varphi_N^k,\Phi_N\rangle, where

φNk=HnkΛ,\varphi_N^k=H_{n_k^\Lambda},
ΦN=⋃n∈NN′Φn∪⋃n∈NN′{φn↔Hn}∪⋃j=1∣L0∣{Xj↔Xj1}∪{Hnji↔Xji+1:nji∈Li, i∈{1,…,Λ−1}}.(17)\Phi_N=\bigcup_{n\in\mathcal{N}_{N'}}\Phi_n\cup\bigcup_{n\in\mathcal{N}_{N'}}\{\varphi_n\leftrightarrow H_n\}\cup\bigcup_{j=1}^{\lvert L_0\rvert}\{X_j\leftrightarrow X_j^1\}\cup\{H_{n_j^i}\leftrightarrow X_j^{i+1}:n_j^i\in L_i,\ i\in\{1,\ldots,\Lambda-1\}\}. \tag*{(17)}

Theorem 4.5. Let NN be a ReLU–TId neural network with LN={L0,…,LΛ}\mathcal{L}_N=\{L_0,\ldots,L_\Lambda\}, and let N′N' be its equivalent neural network obtained by the output–input normalization procedure discussed in this section. Also, let ⟨φn,Φn⟩\langle\varphi_n,\Phi_n\rangle be the L-MODSAT representations of the neurons n∈NN′n\in\mathcal{N}_{N'}, and let ⟨φNk,ΦN⟩\langle\varphi_N^k,\Phi_N\rangle, for k∈{1,…,∣LΛ∣}k\in\{1,\ldots,\lvert L_\Lambda\rvert\}, be the pairs given by (17). Then, for any L\mathcal{L}-valuation vv satisfying ΦN\Phi_N and such that v(X1)=x1,…,v(X∣L0∣)=x∣L0∣v(X_1)=x_1,\ldots,v(X_{\lvert L_0\rvert})=x_{\lvert L_0\rvert}, we have

v(φNk)=Nk′(x1,…,x∣L0∣)=Nk(x1,…,x∣L0∣),v(\varphi_N^k)=N'_k(x_1,\ldots,x_{\lvert L_0\rvert})=N_k(x_1,\ldots,x_{\lvert L_0\rvert}),

for every k∈{1,…,∣LΛ∣}k\in\{1,\ldots,\lvert L_\Lambda\rvert\}. Moreover, for every ⟨x1,…,x∣L0∣⟩∈[0,1]∣L0∣\langle x_1,\ldots,x_{\lvert L_0\rvert}\rangle\in[0,1]^{\lvert L_0\rvert}, there exists at least one L\mathcal{L}-valuation satisfying ΦN\Phi_N such that v(X1)=x1,…,v(X∣L0∣)=x∣L0∣v(X_1)=x_1,\ldots,v(X_{\lvert L_0\rvert})=x_{\lvert L_0\rvert}.

Proof. Let vv be a L\mathcal{L}-valuation satisfying ΦN\Phi_N such that v(X1)=x1,…,v(X∣L0∣)=x∣L0∣v(X_1)=x_1,\ldots,v(X_{\lvert L_0\rvert})=x_{\lvert L_0\rvert}, and let x=⟨x1,…,x∣L0∣⟩\mathbf{x}=\langle x_1,\ldots,x_{\lvert L_0\rvert}\rangle. For each i∈{0,…,Λ}i\in\{0,\ldots,\Lambda\}, let

zi(x)=(Li′∘⋯∘L0′)(x),\mathbf{z}^i(\mathbf{x})=(L'_i\circ\cdots\circ L'_0)(\mathbf{x}),

where Li′L'_i is the ii-th layer of N′N'. Also, write

zi(x)=⟨z1i(x),…,z∣Li∣i(x)⟩.\mathbf{z}^i(\mathbf{x})=\langle z_1^i(\mathbf{x}),\ldots,z_{\lvert L_i\rvert}^i(\mathbf{x})\rangle.

We show by induction on the layers of N′N' that, for every neuron n∈Li′n\in L'_i, for i∈{1,…,Λ}i\in\{1,\ldots,\Lambda\}, one has

v(φn)=n(zi−1(x))andv(Hn)=n(zi−1(x)).v(\varphi_n)=n(\mathbf{z}^{i-1}(\mathbf{x}))\qquad\text{and}\qquad v(H_n)=n(\mathbf{z}^{i-1}(\mathbf{x})).

For i=1i=1, we have that z0(x)=x\mathbf{z}^0(\mathbf{x})=\mathbf{x}, and the formulas Xj↔Xj1X_j\leftrightarrow X_j^1 in (17) ensure that the propositional variables Xj1X_j^1 are evaluated by the corresponding inputs xjx_j. Since vv satisfies Φn\Phi_n, it follows from the definition of representation modulo satisfiability that

v(φn)=n(x)v(\varphi_n)=n(\mathbf{x})

for every neuron n∈L1′n\in L'_1. Then, by the linking formulas φn↔Hn\varphi_n\leftrightarrow H_n in ΦN\Phi_N, we also have

v(Hn)=n(x),v(H_n)=n(\mathbf{x}),

for every neuron n∈L1′n\in L'_1.

Assume now that the claim holds for every neuron in layer Li′L'_i, where i∈{1,…,Λ−1}i\in\{1,\ldots,\Lambda-1\}. By the linking formulas

Hnji↔Xji+1H_{n_j^i}\leftrightarrow X_j^{i+1}

in ΦN\Phi_N, the interface propositional variables Xji+1X_j^{i+1} are evaluated by the outputs of the neurons njin_j^i, that is, by zji(x)z_j^i(\mathbf{x}). Since vv satisfies Φn\Phi_n for every neuron n∈Li+1′n \in L'_{i+1}, the definition of representation modulo satisfiability yields

v(φn)=n(z1i(x),…,z∣Li∣i(x))=n(zi(x)),v(\varphi_n)=n(z_1^i(\mathbf{x}),\ldots,z_{|L_i|}^i(\mathbf{x}))=n(\mathbf{z}^i(\mathbf{x})),

for every neuron n∈Li+1′n \in L'_{i+1}. Again, using the linking formulas φn↔Hn\varphi_n \leftrightarrow H_n, we conclude that

v(Hn)=n(zi(x)),v(H_n)=n(\mathbf{z}^i(\mathbf{x})),

for every neuron n∈Li+1′n \in L'_{i+1}. This completes the induction.

In particular, for every k∈{1,…,∣LΛ∣}k \in\{1,\ldots,|L_\Lambda|\},

v(φNk)=v(HnkΛ)=Nk′(x1,…,x∣L0∣).v(\varphi_N^k)=v(H_{n_k^\Lambda})=N'_k(x_1,\ldots,x_{|L_0|}).

By Theorem 4.4, we also have

Nk′(x1,…,x∣L0∣)=Nk(x1,…,x∣L0∣),N'_k(x_1,\ldots,x_{|L_0|})=N_k(x_1,\ldots,x_{|L_0|}),

and hence the first claim follows.

For the second claim, let x=⟨x1,…,x∣L0∣⟩∈[0,1]∣L0∣\mathbf{x}=\langle x_1,\ldots,x_{|L_0|}\rangle\in[0,1]^{|L_0|}. Define a partial L\mathcal{L}-assignment by setting

v(Xj)=v(Xj1)=xj,v(X_j)=v(X_j^1)=x_j,

for j∈{1,…,∣L0∣}j \in\{1,\ldots,|L_0|\}, and

v(Hnji)=v(Xji+1)=zji(x),v(H_{n_j^i})=v(X_j^{i+1})=z_j^i(\mathbf{x}),

for every i∈{1,…,Λ−1}i \in\{1,\ldots,\Lambda-1\} and every j∈{1,…,∣Li∣}j \in\{1,\ldots,|L_i|\}, together with

v(HnkΛ)=zkΛ(x),v(H_{n_k^\Lambda})=z_k^\Lambda(\mathbf{x}),

for every k∈{1,…,∣LΛ∣}k \in\{1,\ldots,|L_\Lambda|\}. By the definition of representation modulo satisfiability, for each neuron n∈NN′n \in\mathcal{N}_{N'} this partial assignment extends to a L\mathcal{L}-valuation satisfying Φn\Phi_n. Since different neuron representations share only the interface propositional variables XjiX_j^i, and these have been assigned consistently, these local extensions can be combined into a global L\mathcal{L}-valuation satisfying ΦN\Phi_N. This proves the existence claim. □

We have just established that the sequence of pairs

PN=⟨⟨φN1,ΦN⟩,…,⟨φN∣LΛ∣,ΦN⟩⟩P_N=\left\langle\langle\varphi_N^1,\Phi_N\rangle,\ldots,\langle\varphi_N^{|L_\Lambda|},\Phi_N\rangle\right\rangle

constitute a logical twin of N′N', and hence of NN. We now turn to the algorithmic aspects of this construction.

For complexity purposes, we measure the size of a ReLU–TId neural network NN by the length of its graph encoding, namely, the total length of the binary representations of its weights and biases—that is, the coefficients of the linear functions computed by its neurons—, together with the information needed to encode the connectivity of the network. Let ∥N∥\lVert N\rVert denote the length of the graph encoding of NN.

A possible algorithm for building the representation PNP_N traverses all neurons n∈NNn \in\mathcal{N}_N of the ReLU–TId neural network NN in order to construct an equivalent neural network N′N', whose neurons are obtained by output–input normalization whenever necessary. These normalization procedures involve only elementary operations on rational numbers, together with the computation of the maximum value attained by a neuron given by (12). More precisely, if

n(x)=ReLU⁡(γ0+γ1x1+⋯+γ∣Li−1∣x∣Li−1∣),n(\mathbf{x}) = \operatorname{ReLU}(\gamma_0 + \gamma_1 x_1 + \cdots+ \gamma_{\lvert L_{i-1}\rvert}x_{\lvert L_{i-1}\rvert}),

then its maximum value on [0,1]∣Li−1∣[0,1]^{\lvert L_{i-1}\rvert} is

M=max⁡x∈[0,1]∣Li−1∣n(x)=max⁡{0,γ0+∑{γj:γj>0, j∈{1,…,∣Li−1∣}}}.M = \max_{\mathbf{x}\in[0,1]^{\lvert L_{i-1}\rvert}} n(\mathbf{x}) = \max\left\{0,\gamma_0 + \sum\{\gamma_j : \gamma_j > 0,\, j \in\{1,\ldots,\lvert L_{i-1}\rvert\}\}\right\}.

For each neuron, only a bounded number of such elementary operations is performed. Hence, the transformation from NN to N′N' runs in polynomial time in the size of the graph encoding of NN.

Then, the algorithm proceeds by traversing all neurons n∈NN′n \in\mathcal{N}_{N'} and, for each such neuron, computing:

  • The L-MODSAT representation ⟨φn,Φn⟩\langle\varphi_n,\Phi_n\rangle of the function computed by nn;

  • The linking formula φn↔Hn\varphi_n \leftrightarrow H_n, where HnH_n is a fresh propositional variable;

  • The linking formulas connecting HnH_n to the propositional variables corresponding to the inputs of the neurons in the next layer.

Accordingly, the set ΦN\Phi_N comprises all such formulas for all n∈NN′n \in\mathcal{N}_{N'}, together with the formulas Xj↔Xj1X_j \leftrightarrow X^1_j, for j∈{1,…,∣L0∣}j \in\{1,\ldots,\lvert L_0\rvert\}. In addition, the representation PNP_N includes the formulas φNk=HnkΛ\varphi^k_N = H^\Lambda_{n_k}, for k∈{1,…,∣LΛ∣}k \in\{1,\ldots,\lvert L_\Lambda\rvert\}.

By [16 Theorem 11], the cost of computing a representation ⟨φn,Φn⟩\langle\varphi_n,\Phi_n\rangle for a truncated linear function is polynomial in the total length of the binary representations of its coefficients, written as fractions; we revisit and refine this result in Section 2. Since the coefficients of the neurons of N′N' are obtained from those of NN by polynomial-time normalization procedures, the encoding length of each such truncated linear function is polynomial in ∥N∥\lVert N\rVert. Hence, each local representation ⟨φn,Φn⟩\langle\varphi_n,\Phi_n\rangle has polynomial size in ∥N∥\lVert N\rVert.

Moreover, N′N' has the same number of neurons as NN, and this number is bounded by the length of the graph encoding of NN. Therefore, the total size of all local representations ⟨φn,Φn⟩\langle\varphi_n,\Phi_n\rangle, for n∈NN′n \in\mathcal{N}_{N'}, is polynomial in ∥N∥\lVert N\rVert.

When assembling the global representation PNP_N, these local representations must be renamed apart at the level of their auxiliary propositional variables, except for the designated interface variables XjiX^i_j, which are intended to be shared. This can be done by systematically renaming the auxiliary variables in each ⟨φn,Φn⟩\langle\varphi_n,\Phi_n\rangle. Since the total number of propositional variables occurring in all local representations is polynomial in ∥N∥\lVert N\rVert, and since the global construction adds only polynomially many further propositional variables—namely, XjX_j, for j∈{1,…,∣L0∣}j \in\{1,\ldots,\lvert L_0\rvert\}, and HnH_n, for n∈NN′n \in\mathcal{N}_{N'}—the total number of propositional variables occurring in PNP_N is polynomial in ∥N∥\lVert N\rVert.

Let us agree that propositional variables in P\mathbb{P} are encoded by the concatenation of the symbol X with the binary representation of a natural number, for instance X0, X1, X1010, X1100100, and so on. Under this encoding, the length of the representation of each propositional variable is logarithmic in the total number of propositional variables, and hence polynomial in ∥N∥\lVert N\rVert. It follows that the cost of computing all local representations ⟨φn,Φn⟩\langle\varphi_n, \Phi_n\rangle so that only the designated interface variables are shared is polynomial in ∥N∥\lVert N\rVert.

Moreover, apart from the computation of the local L-MODSAT representations themselves, only a bounded number of formulas containing a constant number of symbols is introduced for each neuron. It follows that the overall construction runs in polynomial time in ∥N∥\lVert N\rVert. We may therefore state the following result.

Theorem 4.6. The construction above yields a layer-by-layer, neuron-by-neuron algorithm for computing a logical twin of a ReLU–TId neural network NN in the L-MODSAT system. Moreover, this algorithm terminates in polynomial time in the length of the graph encoding of NN. Hence, the resulting logical twin has polynomial size in the length of the graph encoding of NN.

Implementation and experimental evaluation

We developed C++ implementations of the three methods described in this work in order to evaluate their performance on randomly generated neural networks. We refer to these methods as Regional–Lattice (Section 3.1), Compositional (§ 3.1), and PolyTwin (§ 4), in the order in which they were presented above. The source code of our implementations, together with a script for the experiments, is publicly available.1

The Regional–Lattice method consists of two steps: first, nn2pwl, which translates a ReLU–TId neural network into the pre-closed regional format; and second, a routine that constructs a lattice representation in L-MODSAT. A routine for constructing L-MODSAT representations of truncated linear functions is also used in Compositional and PolyTwin. For the routines used to construct L-MODSAT representations, we relied on a publicly available C++ implementation.2

Weights and biases of a neural network are represented by fixed-width machine types; so output–input normalizations in PolyTwin are performed via floating-point operations. When such values are required as fractions for truncated linear function representations in L-MODSAT, we approximate them by fractions whose numerators and denominators are bounded by an implementation-defined limit, and then reduce them to lowest terms.

For each randomly generated ReLU–TId neural network NN, at least one of the three methods constructs a pair ⟨φN,ΦN⟩\langle\varphi_N, \Phi_N\rangle. For each such pair, we measure the user CPU running time required by the method used to complete the construction, as well as the total complexity of the formulas in {φN}∪ΦN\{\varphi_N\}\cup\Phi_N. The complexity of a formula φ\varphi, as usual, is defined inductively by: #(φ)=1\#(\varphi)=1, if φ\varphi is a propositional variable; #(¬φ)=1+#(φ)\#(\lnot\varphi)=1+\#(\varphi); and #(φ□ψ)=2+#(φ)+#(ψ)\#(\varphi\mathbin{\Box}\psi)=2+\#(\varphi)+\#(\psi), if □\Box is a binary operator. The total complexity of a set of formulas is the summation of these formulas individual complexities.

The experiments reported in our earlier LSFA 2024 paper showed that the complexity of the regional representation of ReLU–TId neural networks grows more sharply when the number of neurons per layer is varied while the number of layers is kept fixed than when the number of layers is varied while the number of neurons per layer is kept fixed [19].

For that reason, in the first batch of experiments reported here, we generate ReLU–TId neural networks with 5 hidden layers and a single neuron in the output layer. The numbers of neurons in the input layer and in each hidden layer vary from 1 to 7. For each configuration, 100 ReLU–TId neural networks are generated. The weights and biases of these networks have the form i+di+d, where ii and dd are generated uniformly from {−1,0,1}\{-1,0,1\} and [0,1)[0,1), respectively.

The three considered methods are applied to the neural networks generated in this first batch of experiments. However, it must be noted that, while the pairs ⟨φN,ΦN⟩\langle\varphi_N,\Phi_N\rangle constructed by Compositional and PolyTwin are logical twins of NN, the same is not guaranteed for the pairs constructed by Regional–Lattice. This holds only when the regional format output by NN2PWL satisfies the lattice property.

Therefore, we rerun an enhanced version of the Regional–Lattice method on the instances generated in the first batch. This new version includes a routine that counts the number of ordered pairs of regions ⟨Ωi,Ωj⟩\langle\Omega_i,\Omega_j\rangle generated by NN2PWL that fail to satisfy the lattice property. If this count is 0, then the output of NN2PWL is indeed in closed regional format, and the constructed pair ⟨φN,ΦN⟩\langle\varphi_N,\Phi_N\rangle is a logical twin of NN. For performing such counting, if the regional format has mm regions, at most 2m32m^3 linear programs need to be solved.

The results regarding the lattice property in the first batch of experiments reproduce the phenomenon already observed in our earlier LSFA 2024 paper. Among the 700 instances, only three representations in regional format computed by NN2PWL failed to satisfy the lattice property, all of them from instances with 7 neurons per input/hidden layer: in one case, 126 pairs of regions among 6382638^2 failed to do so, in another, 387 pairs among 1562156^2, and in the last one, 14 among 50250^2.

Using the first batch, we compare all three methods with respect to their average running times, shown in Figure 3, and the average complexities of their outputs, shown in Figure 4, for increasing numbers of neurons per layer. It becomes clear that, in terms of running time, Compositional represents a major advance over Regional–Lattice, although the latter performs better in terms of representation complexity. In turn, PolyTwin outperforms Compositional in both respects. Figure 3 also includes the running times of the enhanced Regional–Lattice method. Although counting failures of the lattice property adds only a polynomial overhead, this additional cost may still be significant for larger instances.

Average running time in the first batch of experiments

Figure 3. Average running time in the first batch of experiments

Average representation complexity in the first batch of experiments

Figure 4. Average representation complexity in the first batch of experiments

Both Regional–Lattice and Compositional perform a preprocessing step before constructing a representation in L-MODSAT, namely the construction of an intermediate representation: in the former case, a regional format Ξ\Xi, and in the latter, a neural network N′N' equivalent to NN. From these intermediate representations, the final pair ⟨φN,ΦN⟩\langle\varphi_N, \Phi_N \rangle can then be computed in polynomial time. However, an exponential blow-up may already occur at the level of these intermediate constructions. For this reason, for the Regional–Lattice outputs we count the number of regions generated by nn2pwl, while for the Compositional outputs we count the number of neurons in the equivalent neural network N′N'. We take these quantities as complexity measures for the corresponding intermediate representations.

Figure 5 shows, for increasing numbers of neurons per layer, the average numbers of regions and neurons in the intermediate representations produced by Regional–Lattice and Compositional, respectively, in the first batch. We observe that the equivalent networks N′N' tend to be considerably more complex than the regional formats Ξ\Xi, which explains why Regional–Lattice outperforms Compositional in terms of representation complexity.

Bar chart showing average intermediate representation complexity for neurons per layer

Figure 5. Average complexity of intermediate representations in the first batch of experiments

A possible explanation for the running-time advantage of Compositional over Regional–Lattice is that, although more representations of truncated linear functions must be constructed, these can be produced in linear time at the implementation level, as discussed in § 2.3. By contrast, what appears to dominate the running time of Regional–Lattice is the need to solve m2m^2 linear programs, where mm is the number of regions, in order to establish expressions such as (9) in the lattice representation. Although linear programming is solvable in polynomial time, it is not a linear-time task, and these routines dominate the cost of constructing the individual truncated linear functions.

In order to compare Compositional and PolyTwin more closely, in the second batch of experiments we generate ReLU–TId neural networks with 5 hidden layers and a single neuron in the output layer. The numbers of neurons in the input layer and in each hidden layer vary from 1 to 20. For each configuration, 100 ReLU–TId neural networks are generated. The weights and biases of these networks have the form i+di+d, where ii and dd are generated uniformly from {−1,0,1}\{-1,0,1\} and [0,1)[0,1), respectively.

In the second batch, the advantage of PolyTwin over Compositional becomes clear. Figure 6 shows the average running time of the two methods on instances with increasing numbers of neurons per layer. Figure 7 shows the average complexities of the logical twins they generate. Moreover, Figure 8 shows a sharp growth in the number of neurons of the equivalent networks N′N' constructed from NN as the intermediate representations computed by Compositional.

Line chart showing average running time for neurons per layer

Figure 6. Average running time in the second batch of experiments

Average representation complexity in the second batch of experiments

Figure 7. Average representation complexity in the second batch of experiments

Average complexity of intermediate representations in the second batch of experiments

Figure 8. Average complexity of intermediate representations in the second batch of experiments

Finally, to test the scalability of PolyTwin, we consider only this method in the third and fourth batches of experiments. In both batches, the randomly generated ReLU–TId neural networks have 10 hidden layers and a single output neuron. The numbers of neurons in the input and hidden layers vary from 1 to 50. For each configuration, 100 ReLU–TId neural networks are generated. The weights and biases of these networks have the form i+di+d, where dd is generated uniformly from [0,1)[0,1). In the third batch, ii is generated uniformly from {−1,0,1}\{-1,0,1\}; in the fourth batch, it is generated uniformly from {−10,…,0,…,10}\{-10,\ldots,0,\ldots,10\}.

Figure 9 shows that the integer part ii of the weights and biases does not influence either the running time or the representation complexity of the PolyTwin method. More importantly, the third and fourth batches of experiments make it clear that PolyTwin is highly scalable: even for the largest instances in these batches, in which the ReLU–TId neural networks have 500 neurons, the average running time of the method does not exceed 5 seconds.

Running time and representation complexity in the third and fourth batches

Figure 9. Running time and representation complexity in the third and fourth batches

Final remarks and conclusions

In this work, we proposed a new algorithm for constructing logical twins for ReLU–TId neural networks through formulas of Łukasiewicz logic, namely as representations in the system Ł-MODSAT of the functions computed by these networks.

To this end, we first revisited two earlier approaches. The first is based on lattice representations of rational McNaughton functions built from encodings in regional format, and ultimately yields representations in Ł-MODSAT [15, 16, 19]. The second is an architecture-based compositional approach introduced by Zhang and Bölcskei [21] that constructs logical twins by formulas of Łukasiewicz logic or rational Łukasiewicz logic. We also showed how to adapt this second approach so as to construct logical twins in the system Ł-MODSAT. The main drawback of both approaches is that they are susceptible to exponential blow-up in running time and/or representation size.

Inspired by both of them, we then proposed a new polynomial-time, architecture-based compositional algorithm that constructs logical twins for ReLU–TId neural networks in the system Ł-MODSAT. More precisely, the new construction yields polynomial-size logical twins. In addition to establishing these complexity bounds, we submitted all three approaches to empirical evaluation on randomly generated ReLU–TId neural networks, showing a clear superiority of the new algorithm.

A feature of representations in Ł-MODSAT is that they avoid restricting the class of ReLU–TId neural networks that can be represented, since they allow plain Łukasiewicz logic to represent rational McNaughton functions, whose linear pieces have rational coefficients. Importantly, Łukasiewicz logic provides a well-studied logical setting whose main computational problems have reasonable complexity: satisfiability is NP-complete and validity is coNP-complete [13]. Moreover, there is extensive literature on algorithms for solving these problems, including implementations in which the phase-transition phenomenon has been detected [1, 3, 7].

An important application of such logical twins in Łukasiewicz logic lies in the formal verification of neural-network properties. Properties such as reachability and robustness for ReLU–TId neural networks have already been encoded in the language of Łukasiewicz logic by means of logical twins in L-MODSAT [17, 18]. However, the practical scalability of these verification techniques for large networks still depended on more compact logical twins. In this sense, the contribution of the present work is a significant step forward for the use of such verification methods in practice.

As directions for future work, one may consider neural networks with architectures other than ReLU–TId neural networks. Networks computing non-piecewise linear functions might be addressed by approximate logical twins in L-MODSAT; an initial study on approximate representations was carried out by Lobo et al. [11].

In this context, the computational problems of Łukasiewicz logic themselves, such as satisfiability and validity, may also be revisited. Although there is already substantial literature on these problems and on algorithms for solving them, such methods may now be further tested and improved on instances arising from neural network properties encoded through the polynomial-size logical twins introduced in this work. Some work in this direction has already been done by testing existing algorithms and tools on instances using lattice-based twins in L-MODSAT [20]. One may also investigate how polynomial approximations to reasoning in Łukasiewicz logic, such as the one proposed by Finger and Preto [9], could be used for incomplete or approximate formal verification methods.

On another front, one may also investigate more deeply the regional and lattice representations of ReLU–TId neural networks. Although such representations are computationally harder to construct and are not necessarily compact, precisely because they provide representations that differ from the original network architecture, they may support alternative forms of interpretation based on their regional or lattice structure. In particular, for regional representations, one may pursue a better understanding of the rare cases in which the lattice property fails, a correction procedure for such cases, or even the extent to which these representations may still approximate the original network despite lacking the lattice property.

To conclude, this work strengthens the connection between neural networks and symbolic methods in many-valued logic, and opens new perspectives for their formal analysis and verification.

Acknowledgements

This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001. This study was financed by the São Paulo Research Foundation (FAPESP), Brasil, process #2024/19144-7 (SPRINT). Preto was financed by the São Paulo Research Foundation (FAPESP), Brasil, process #2025/15917-4 (Learning to Prove). Finger was partly supported by CNPq grant PQ 302963/2022-7 and by the São Paulo Research Foundation (FAPESP), Brasil, process #2023/00488-5 (SPIRA).

Center for Mathematics, Computing and Cognition, Federal University of ABC, Santo André, Brazil

Email address: [email protected]

Institute of Mathematics, Statistics and Computer Science, University of São Paulo, São Paulo, Brazil

Email address: [email protected]

References

  1. [1]C. Ansótegui, M. Bofill, F. Manyà, and M. Villaret, Building automated theorem provers for infinitely-valued logics with satisfiability modulo theory solvers, 2012 IEEE 42nd International Symposium on Multiple-Valued Logic, 2012, pp. 25–30.DOI
  2. [2]Dimitris Bertsimas and John N. Tsitsiklis, Introduction to linear optimization, Athena scientific series in optimization and neural computation, Athena Scientific, 1997.
  3. [3]Miquel Bofill, Felip Manyà, Amanda Vidal, and Mateu Villaret, Finding hard instances of satisfiability in Łukasiewicz logics, Multiple-Valued Logic (ISMVL), 2015 IEEE International Symposium on, IEEE, 2015, pp. 30–35.
  4. [4]Davide Castelvecchi, Can we open the black box of AI?, Nature 538 (2016), no. 7623, 20–23.DOI
  5. [5]Roberto L.O. Cignoli, Itala M.L. D’Ottaviano, and Daniele Mundici, Algebraic foundations of many-valued reasoning, Trends in Logic, Springer Netherlands, 2000.DOI
  6. [6]Marcelo Finger, Logic in times of big data, A True Polymath: A Tribute to Francisco Antonio Doria (J. Acacio de Barros and Décio Krause, eds.), College Publications, 2020, pp. 184–198.
  7. [7]Marcelo Finger and Sandro Preto, Probably half true: Probabilistic satisfiability over Łukasiewicz infinitely-valued logic, Automated Reasoning (Cham) (Didier Galmiche, Stephan Schulz, and Roberto Sebastiani, eds.), Springer International Publishing, 2018, pp. 194–210.DOI
  8. [8]———, Probably partially true: Satisfiability for Łukasiewicz infinitely-valued probabilistic logic and related topics, Journal of Automated Reasoning 64 (2020), no. 7, 1269–1286.DOI
  9. [9]———, Polyhedral semantics and the tractable approximation of Łukasiewicz infinitely-valued logic, Journal of Logic and Computation 35 (2025), no. 5, exad059.
  10. [10]Brunella Gerla, Rational Łukasiewicz logic and DMV-algebras, Neural Network World 11 (2001), no. 6, 579–594.
  11. [11]João Lobo, Marcelo Finger, and Sandro Preto, Logical approximation and formal verification of neural networks, Anais do V Workshop Brasileiro de Lógica (Porto Alegre, RS, Brasil), SBC, 2024, pp. 1–8.
  12. [12]R. McNaughton, A theorem about infinite-valued sentential logic, Journal of Symbolic Logic 16 (1951), 1–13.DOI
  13. [13]Daniele Mundici, Satisfiability in many-valued sentential logic is NP-complete, Theoretical Computer Science 52 (1987), no. 1-2, 145–153.DOI
  14. [14]———, A constructive proof of McNaughton’s theorem in infinite-valued logic, The Journal of Symbolic Logic 59 (1994), no. 2, 596–602.DOI
  15. [15]Sandro Preto and Marcelo Finger, An efficient algorithm for representing piecewise linear functions into logic, Electronic Notes in Theoretical Computer Science 351 (2020), 167–186, Proceedings of LSFA 2020, the 15th International Workshop on Logical and Semantic Frameworks, with Applications (LSFA 2020).
  16. [16]———, Efficient representation of piecewise linear functions into Łukasiewicz logic modulo satisfiability, Mathematical Structures in Computer Science 32 (2022), no. 9, 1119–1144.
  17. [17]———, Effective reasoning over neural networks using Łukasiewicz logic, Compendium of Neurosymbolic Artificial Intelligence (Pascal Hitzler, Md Kamruzzaman Sarker, and Aaron Eberhart, eds.), Frontiers in Artificial Intelligence and Applications, vol. 369, IOS Press, 2023, pp. 609–630.
  18. [18]———, Proving properties of binary classification neural networks via Łukasiewicz logic, Logic Journal of the IGPL 31 (2023), no. 5, 805–821.DOI
  19. [19]______, Regional, lattice and logical representations of neural networks, Proceedings of the 19th International Workshop on Logical and Semantic Frameworks, with Applications, Goiânia, Brazil, 18th-20th September 2024 (Cynthia Kop and Helida Salles Santos, eds.), Electronic Proceedings in Theoretical Computer Science, vol. 421, Open Publishing Association, 2025, pp. 64–79.DOI
  20. [20]Sandro Preto, Felip Manyà, and Marcelo Finger, Benchmarking Łukasiewicz logic solvers with properties of neural networks, 2023 IEEE 53rd International Symposium on Multiple-Valued Logic (ISMVL), 2023, pp. 158–163.
  21. [21]Yani Zhang and Helmut Bölcskei, Extracting formulae in many-valued logic from deep neural networks, IEEE Transactions on Signal Processing 74 (2026), 1–12.

Paper details

vlnc:W_qftxvbya
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents