MV-tropical polynomials and neural networks

Abstract

We introduce the notion of MV-tropical polynomial starting from the language of semiring reducts of an MV-algebra. We show, in the one-variate case, how MV-tropical polynomial functions can be used to describe some classes of neural networks.

Keywords

• eol>Semirings
• Many-valued logic
• MV-algebras
• Feedforward neural networks

1. Introduction

Propositional many-valued logics have been proposed in the last decades as a mathematical tool to formalize fuzzy logic. In particular, among all the possible many-valued logics, the so called Łukasiewicz logic is of special interest both for its !exible semantics and for the rich mathematical structure associated with it, namely MV-algebras. Indeed, a prototypical example of MV-algebra is given by the set of functions in [ 0, 1 ] that are continuous and piecewise linear with integer coe"cients, that can be considered as truth functions of formulas of the in#nitevalued logics of Łukasiewicz. Starting from [9] (see also [10]), MV-algebras have been compared with semirings and in particular with tropical geometry: this line of research is still in its early steps but it is very promising, since it would permit a logical approach to a new kind of algebraic geometry based on linear pieces, putting together the many results obtained for MV-algebras with the ones of tropical geometry.

In this paper we focus in particular on the connection between tropical geometry and neural networks, as in [22]. As also shown in [16], there is a strict connection between convex geometry (hence in particular tropical geometry) and Optimal Transport theory that in turns is related with machine learning and deep neural networks. In this paper we consider the case of multilayer perceptrons with a linear activation function, but independently from the type of networks that we consider, our aim is to show how to use MV-semirings to give a formal and logical interpretation of networks. See also [17].

We suggest indeed a logical representation of neural networks that could widen the interpretability, amalgamability and reuse of these objects. Many-valued logic has been proposed in [7] to model neural networks: it is shown there that, by taking as activation function ψ the identity truncated to zero and one (i.e., ψ(x) = (1 ∧ (x ∨ 0))), it is possible to represent the corresponding neural network as a combination of propositions of Łukasiewicz calculus (and vice versa). Further, in [ 4 ] it is shown that neural networks whose activation function is the identity truncated to zero and one, can be fully interpreted as logical objects, since they are equivalent to (equivalence classes of) formulas of Rational Łukasiewicz logic.

Other mathematical structures have been proposed to model neural network, as for example the tropical semiring that is a structure on the real numbers that mimics the usual ring operations of sum and multiplication, by replacing them with supremum and sum, respectively. Starting from such a structure, de#nitions of polynomials can be given that corresponds to piecewise linear functions. In [22] the authors establish connections between feedforward neural networks with real valued, linear activation functions, and tropical geometry and they show that the family of such neural networks is equivalent to the family of tropical rational maps.

In this paper we deal with polynomials written in the language of the semiring reducts of the MV-algebra [ 0, 1 ]. We characterize the associated formulas in the one variable case, and we state some results about their geometry. Further, following [22], we de#ne rational functions for MV-semirings and compare them with the whole class of generalised McNaughton functions corresponding to MV-polynomials (see [6]). We then show how MV-polynomials can be used to describe functions associated with a special class of neural networks.

2. Semirings and Semimodules

In this section we recall some basic de#nitions and properties of semirings and semimodules over them. Most of this material can be found in [15].

De!nition 2.1. A semiring is an algebraic structure hS, +, ·, 0, 1i such that (S1) hS, +, 0i is a commutative monoid; (S2) hS, ·, 1i is a monoid; (S3) · distributes over + from either side; (S4) 0 · a = 0 = a · 0 for all a ∈ S.

A semiring S is called

• commutative if so is the multiplication, • idempotent if so is the sum, i. e. if it satis#es the equation x + x = x, • a semi"eld if hS \ {0}, ·, 1i is an Abelian group.

Many relevant examples of semirings are known, among which we recall the (commutative) one of natural numbers hN, +, ·, 0, 1i. Further let R = R ∪ {−∞}. The structure hR, max, +, −∞, 0i is an idempotent semi#eld, sometimes called the tropical semiring. De!nition 2.2. Let S be a semiring. A (left) S-semimodule is a commutative monoid hM, +, 0i with an external operation with coe"cients in S, called scalar multiplication, · : (a, x) ∈ S × M 7−→ a · x ∈ M , such that the following conditions hold for all a, b ∈ S and x, y ∈ M : (SM1) (ab) · x = a · (b · x), (SM2) a · (x + y) = (a · x) + (a · y), (SM3) (a + b) · x = (a · x) + (b · x), (SM4) 0S · x = 0M = a · 0M , (SM5) 1 · x = x.

Right S-semimodule are de#ned in an analogus way.

Example 2.3. Let S be a semiring and X be an arbitrary non-empty set. We can consider the monoid hSX , +, 0i of all functions from X to S, where 0 is the 0S-constant function from X to S and (f + g)(x) = f (x) + g(x) for all x ∈ X and f, g ∈ SX .

Then we can de"ne a scalar multiplication in SX as follows:

· : (a, f ) ∈ S × SX 7−→ a · f ∈ SX , with the map a · f de"ned as (a · f )(x) = af (x) for all x ∈ X.

It is clear that SX is a left S-semimodule. The semimodule SX can be de"ned also for X = ∅, in which case we obtain, up to an isomorphism, the one-element semimodule {0}. Remark 2.4. In all the de#nitions and results that can be stated both for left and right semimodules, we will refer generically to “semimodules” — without specifying left or right — and we will use the notations of left semimodules.

3. MV-semirings and MV-semimodules

In [5] and [9] semirings were studied in connection with MV-algebras — the algebraic semantics of Łukasiewicz in#nite-valued propositional logic. In this section we recall the de#nition of MV-algebra and, brie!y, some of the contents of the aforementioned papers; for a comprehensive study of MV-algebras we refer the reader to [8].

De!nition 3.1. An MV-algebra is an algebra hA, ⊕,∗ , 0i of type (2, 1, 0) such that hA, ⊕, 0i is a commutative monoid, and, for all x, y ∈ A, (MV1) (x∗)∗ = x; (MV2) x ⊕ 0∗ = 0∗; (MV3) (x∗ ⊕ y)∗ ⊕ y = (y∗ ⊕ x)∗ ⊕ x.

Since De#nition 3.1 can be formulated in the language of Universal Algebra by means of equations, MV-algebras form a variety. Congruences and homomorphisms are de#ned in an obvious way, namely, as equivalence relations that are compatible with ⊕ and ∗ and functions that preserve the operations and the constant 0 respectively.

On every MV-algebra A it is possible to de#ne another constant 1 = 0∗ and the operation ⊙ by x ⊙ y = (x∗ ⊕ y∗)∗; moreover, for all x, y ∈ A, the following well-known properties hold: - hA, ⊙,∗ , 1i is an MV-algebra; - ∗ is an isomorphism between hA, ⊙,∗ , 1i and hA, ⊕,∗ , 0i; - 1∗ = 0; - x ⊕ y = (x∗ ⊙ y∗)∗; - x ⊕ 1 = 1 (reformulation of (MV2)); - x ⊕ x∗ = 1.

For any MV-algebra A and x, y ∈ A, we write x ≤ y if and only if x∗ ⊕ y = 1. It is wellknown that ≤ is a partial order on A, called the natural order of A. Moreover, the natural order determines a structure of bounded distributive lattice on A [8, Propositions 1.1.5 and 1.5.1], with 0 and 1 respectively bottom and top element, and ∨ and ∧ de#ned by x ∨ y = (x ⊙ y∗) ⊕ y, x ∧ y = (x∗ ∨ y∗)∗ = x ⊙ (x∗ ⊕ y).

A subset I of an MV-algebra A is called an ideal if it is a downward closed submonoid of hA, ⊕, 0i, i. e. if it satis#es the following properties: • 0 ∈ I; • I is downward closed, that is, b ≤ a implies b ∈ I for all a ∈ I and b ∈ A; • a ⊕ b ∈ I for all a, b ∈ I.

Example 3.2. Consider the interval [ 0, 1 ] of R with the operations ⊕ and ∗ de"ned, respectively, by x ⊕ y := min{x + y, 1} and x∗ := 1 − x. Then structure h[ 0, 1 ], ⊕,∗ , 0i is an MV-algebra, often called the standard MV-algebra. The reason for such a name is the fact (which is perfectly equivalent to Theorem 3.3 below) that the algebra [ 0, 1 ] generates the whole variety of MV-algebras, namely, every MV-algebra can be obtained as a quotient of a subalgebra of a Cartesian power [ 0, 1 ]κ (with pointwise de"ned operations) for some cardinal κ.

In the standard MV-algebra the order relation (and therefore the lattice structure) is the usual one of real numbers; the product ⊙ is de"ned by x ⊙ y := max{0, x + y − 1}.

Theorem 3.3. An equation holds in [ 0, 1 ] if and only if it holds in every MV-algebra. Example 3.4. Let hG, +, −, 0, ∨, ∧i be a lattice-ordered Abelian group, let u be a "xed positive element of G and [0, u] = {x ∈ G | 0 ≤ x ≤ u}. Now let us de"ne, for all x, y ∈ [0, u], x ⊕ y := (x + y) ∧ u and x∗ := u − x. Then it is easy to check that the structure h[0, u], ⊕,∗ , 0i is an MV-algebra.

Example 3.5. For any Boolean algebra hB, ∨, ∧,′ , 0, 1i, the structure hB, ∨,′ , 0i is an MV-algebra. Boolean algebras form a subvariety of the variety of MV-algebras. They are precisely the MValgebras satisfying the additional equation x ⊕ x = x.

For the proof of the following result we refer the reader to [9, Proposition 3.6]. Proposition 3.6. Let A be an MV-algebra. Then A∨⊙ = hA, ∨, ⊙, 0, 1i and A∧⊕ = hA, ∧, ⊕, 1, 0i are semirings. Moreover, the involution ∗ : A −→ A is an isomorphism between them. Remark 3.7. Thanks to Proposition 3.6, we can limit our attention to one of the two semiring reducts of A; therefore, whenever not di$erently speci#ed, we will refer only to A∨⊙, all the results holding also for A∧⊕ up to the application of ∗.

We recall the following de#nition from [5].

De!nition 3.8. An MV-semiring is a commutative, additively idempotent semiring hA, ∨, ·, 0, 1i for which there exists a map ∗ : A −→ A — called the negation — satisfying, for all a, b ∈ A, the following conditions: (i) a · b = 0 i$ b ≤ a∗ (where a ≤ b i$ a ∨ b = b); (ii) a ∨ b = (a∗ · (a∗ · b)∗)∗.

Proposition 3.9. For any MV-algebra hA, ⊕, 0i, both the semiring reducts A∨⊙ and A∧⊕ are MV-semirings. Conversely, if hA, ∨, ·, 0, 1i is an MV-semiring with negation ∗, the structure hA, ⊕,∗ , 0i, with a ⊕ b = (a∗ · b∗)∗ for all a, b ∈ S, is an MV-algebra.

When A = [ 0, 1 ] we speak of MV-tropical semiring.

4. MV-tropical polynomials and McNaughton functions

We shall now de#ne tropical polynomials on MV-semirings and see their connection with McNaughton functions and — therefore — with free MV-algebras.

Given an MV-semiring hA, ∨, ⊙, 0, 1i, a (∨, ⊙)-MV-monomial in n variables X1, . . . , Xn and with coe"cients in A, is an expression of the form with a ∈ A and j1, . . . , jn nonnegative integers, with the assumption that Xi0 = 1.

A (∨, ⊙)-MV-polynomial is a semilinear combination of monomials:

a ⊙ X1j1 ⊙ . . . ⊙ Xnjn , m _ ai ⊙ X1j1i ⊙ · · · ⊙ Xnjni .

i=0

The set A[X1, . . . , Xn] of (∨, ⊙)-MV-polynomials is an A-semimodule in an obvious way, due to the distributivity of ∨ and ⊙.

Every (∨, ⊙)-MV-polynomial p in n variables with coe"cients in A de#nes a function p˜ : An −→ A by setting X˜ i as the i−th projection and then proceeding by structural induction. In particular, if A = [ 0, 1 ] is the standard MV-semiring then MV-polynomials are called MV-tropical polynomials and it is immediate to verify that p˜ veri#es the following properties: P1 p˜ : [ 0, 1 ]n → [ 0, 1 ] is a continuous function P2 p˜ is piecewise linear and each linear piece has locally the form a0 + Pin=1 aixi, where ai ∈ N for i > 0 and a0 ∈ R

We focus now on the case of one-variable MV-tropical polynomials. Recall that, for every x ∈ [ 0, 1 ] and n ∈ N, we have x ⊙ · · · ⊙ x = xn = ((nx − (n − 1)) ∨ 0) ∧ 1 .

| n t{imzes } Proposition 4.1. A function [ 0, 1 ] −→ [ 0, 1 ] is continuous, convex and piecewise linear in which each piece has the form ax + b with a ∈ Z, a ≥ 0 and b ∈ R if and only if it has a representation as a (∨, ⊙)-MV-polynomial of the form Wi ci ⊙ Xdi for ci ∈ [ 0, 1 ] and di ∈ N.

Proof. By a simple structural induction argument, we can prove that any function associated with a polynomial Wi ci ⊙ Xdi has the properties of the Proposition.

Reciprocally, suppose f : [ 0, 1 ] −→ [ 0, 1 ] is continuous, convex and piecewise linear in which each piece has the form ax + b with a ∈ Z, a ≥ 0 and b ∈ R. Since f is convex and piecewise linear, then it can be written as the supremum of linear pieces of the form ax + b with a ∈ Z, a ≥ 0 and b ∈ R. We are going to write monomials associated to each truncated function 1 ∧ (0 ∨ (ax + b)) in order to prove the claim. Indeed, consider the following cases: • if a + b ∈ [ 0, 1 ] then by a direct calculation one can show that letting p = Xa ⊙ (a + b) we have p˜ : x ∈ [ 0, 1 ] → 1 ∧ (0 ∨ (ax + b)) and p is an MV-tropical polynomial. • if a + b < 0 then for every x ∈ [ 0, 1 ], ax + b < a + b < 0, hence we can consider the polynomial p = X ⊙ 0. • if a + b > 1 then a > 1 − b hence (1 − b)/a < 1 and the function 1 ∧ (0 ∨ (ax + b)) is equal to 1 for some c < 1. Then two cases are possible: either (1 − b)/a ≤ 0 and the function 1 ∧ (0 ∨ (ax + b)) is constantly equal to 1 in [ 0, 1 ], hence we can consider the polynomial p = X0. Or 0 < (1 − b)/a < 1, hence the function is not constant and it is truncated at 1, but this is against the hypothesis of convexity.

As a consequence of properties in Proposition 4.1 we have:

Proposition 4.2. If p is an MV-polynomial with one variable, then the function p˜ is such that: • p˜(1) = a < 1 if and only if p˜ is constantly equal to a.

• p˜(x) = 1 for some x < 1 if and only if p˜ is the constant function 1.

Corollary 4.3. Let p be an MV-tropical polynomial with one variable and let Z(p) = {x ∈ [ 0, 1 ] | p˜ = 1}. Then either Z(p) = [ 0, 1 ] (i# p˜ is the constant function 1), or Z(p) ⊆ {1}. In the latter case, Z(p) = ∅ i# p˜ is a constant function di#erent from 1.

Due to the distributivity of ⊙ over ∨, the set of MV-tropical polynomial functions coincides with the set of functions associated to any term written in the language of semirings. On the other hand, the same does not hold for general terms of MV-algebras (when also the negation is involved), even when we consider in the language a constant symbol for every element in [ 0, 1 ], as we explain in the following lines (we refer to [ 18, 20, 3 ] for details on MNaughton functions and in particular [ 2 ] for the one variable case).

De!nition 4.4. A function f from [ 0, 1 ]n to [ 0, 1 ] is called a generalized McNaughton function if it is continuous, piecewise linear and each piece has integer degree one coe"cients and real degree zero coe"cient.

Di$erently from McNaughton functions that take {0, 1} values on {0, 1}n, generalized McNaugthon functions can attain any real value in [ 0, 1 ] when restricted to {0, 1}n. The set GMn of generalized McNaughton functions from [ 0, 1 ]n to [ 0, 1 ], equipped with pointwise operations, forms an MV-algebra. We can hence consider the semiring reduct of the MV-algebra GMn and it is of course an MV-semiring.

According to Proposition 4.1, convex generalized McNaughton functions in GM1 are precisely the MV-tropical polynomial functions with one variable.

De!nition 4.5. An MV-tropical rational function is the di$erence of two MV-tropical polynomial functions f and g and can be described in the language of MV as

f ⊖ g = f ⊙ g∗

5. Neural Networks

Among the many possible neural networks typologies and structures, we focus our attention on multilayer perceptrons. These are feedforward neural networks with one or more hidden layers. A multilayer perceptron with l hidden layers, n inputs and one output can be represented as a function F : [ 0, 1 ]n → [ 0, 1 ] such that F (x1, . . . , xn) =

 n(l) n(l−1) ψ X ωokψ  X ωkj ψ . . .

k=1 j=1

n ! X ωlixi + bi . . . i=1 !  , where ψ : R → [ 0, 1 ] is a monotone-nondecreasing continuous function (referred to as activation function), ωok is the synaptic weight from neuron k in the l-th hidden layer to the single output neuron o, ωkj is the synaptic weight from neuron j in the (l − 1)-th hidden layer to neuron k in the l-th hidden layer, and so on for the other synaptic weights.

In the simplest case, a multilayer perceptron has exactly one hidden layer. This network can be represented as a function G : [ 0, 1 ]n → [ 0, 1 ]:

n  n  G(x1, . . . , xn) = X αiψ X wij xj + bi , 1=1 j=1 (1) where n¯ is the number of neurons in the hidden layer.

In the following we shall consider multilayer perceptrons where the activation function is piecewise linear function ψ(x) = max(min(1, x), 0), and the synaptic weights are integer values and we focus on the one-variable case.

Theorem 5.1. Let ψ : R 7−→ [ 0, 1 ] be de"ned as ψ(x) = (1 ∧ x) ∨ 0. Then: (i) For all n¯ ∈ N, αi, wij ∈ Z, bi ∈ R, where i = 1, . . . , n¯, the function F : [ 0, 1 ] 7−→ [ 0, 1 ] de"ned as: is an MV-tropical rational function (ii) For any MV-tropical rational function f , there exist n¯ ∈ N and αi, wi ∈ Z, bi ∈ R, where i = 1, . . . , n¯ and j = 1, . . . , n, such that ¯ n F (x) = X αiψ (wix + bi) 1=1 ¯ n f (x) = X αiψ (wix + bi)

1=1

6. Conclusions

In this paper, putting together the approaches in [ 4 ] and [22], we suggest a description of functions calculated by a class of neural networks by means of functions corresponding to formulas written in the language of MV-tropical semirings. The bene#t of such approach is to have a logical representation of a neural network, in which the parameters of the network are easily recognizable. Further, polynomials also provide a sort of normal forms for expressions in a given language.

Already many results have been obtained in the context of tropical geometry from one side and of Łukasiewicz logic and MV-algebras from another side. This paper is a further step in the direction of showing that both tropical geometry and MV-algebras are an interesting tool for the developing of the logic of algebraic geometry.

Acknowledgments

Ciro Russo was supported by the individual travel grant Professor Visitante no Exterior Sênior - Grant No. 88887.477515/2020-00, awarded by the Coordenadoria de Aperfeiçoamento de Pessoal de Nível Superior and the Universidade Federal da Bahia through the CAPES-PrInt UFBA. [5] Belluce L. P., Di Nola A., Commutative Rings whose Ideals form an MV-algebra, Mathematical Logic Quarterly, 55 (5), 468–486, 2009. [6] Belluce, L., Di Nola, A., and Lenzi, G. (2014). Algebraic Geometry for MV-algebras. The

Journal of Symbolic Logic, 79(4), 1061-1091. [7] J.L. Castro and E. Trillas. (1998). The logic of neural networks. Mathware and Soft

Computing, 5:23–27. [8] Cignoli R.L.O., D’Ottaviano I.M.L., Mundici D., Algebraic Foundations of Many-valued

Reasoning, Trends in Logic, 7, Kluwer Academic Publishers, Dordrecht, 2000 [9] Di Nola A., Gerla B., Algebras of Łukasiewicz’s Logic and their Semiring Reducts, Idempotent Mathematics and Mathematical Physics, 131–144, Contemp. Math., 377, Amer. Math.

Soc., 2005. [10] Antonio Di Nola, Ciro Russo: The semiring-theoretic approach to MV-algebras: A survey.

Fuzzy Sets Syst. 281: 134-154 (2015) [11] Di Nola A., Russo C., Łukasiewicz Transform and its application to compression and reconstruction of digital images, Informat. Sci., 177 (6), 1481–1498, 2007. [12] Di Nola A., Russo C., Łukasiewicz Transform Based Algorithm for Image Processing, Proc. of the 2006 IEEE Intl. Conf. on Fuzzy Systems, pp. 1996–2003, Vancouver, BC, Canada, July 16–21, 2006. [13] Di Nola, A., and Russo, C.; Semiring and semimodule issues in MV-algebras. Communications in Algebra 41:3 (2013), 1017–1048. [14] Di Nola, A., and Russo, C.; Corrigendum to “Semiring and semimodule issues in MValgebras, Communications in Algebra 41:3 (2013), 1017–1048”. Communications in Algebra 46:5 (2018), 2227–2231. [15] Golan J. S., Semirings and their Applications, Kluwer Academic Publishers, Dordrecht, 1999. [16] Na Lei, Kehua Su, Li Cui, Shing-Tung Yau, Xianfeng David Gu; A Geometric View of Optimal Transportation and Generative Model, Computer Aided Geometric Design, Volume 68, Pages 1-21, 2019. [17] P. Maragos, V. Charisopoulos and E. Theodosis, "Tropical Geometry and Machine Learning," in Proceedings of the IEEE, vol. 109, no. 5, pp. 728-755, May 2021. [18] McNaughton R., A theorem about in#nite-valued sentential logic, Journal of Symbolic

Logic, 16, 1–13, 1951. [19] Mundici D., Interpretation of AF C∗-algebras in Łukasiewicz sentential calculus, J. Functional Analysis, 65, 15–63, 1986. [20] Mundici D., A Constructive Proof of McNaughton’s Theorem in In#nite-Valued Logic,

Journal of Symbolic Logic, 59, 596–602, 1994. [21] Russo C., A Uni#ed Algebraic Framework for Fuzzy Image Compression and Mathematical Morphology, In: V. Di Gesù, S.K. Pal, and A. Petrosino (eds.), Proc. of WILF 2009, Lecture Notes in Arti"cial Intelligence, 5571, 205-212, Springer-Verlag, 2009.

arXiv:1002.0982v1 [cs.IT] [22] L. Zhang, G. Naitzat, and L.-H. Lim, Tropical geometry of deep neural networks, in International Conference on Machine Learning, ICML 2018, 2018.

References

[1] Stefano Aguzzoli : A note on the representation of McNaughton lines by basic literals . Soft Comput . 2 ( 3 ): 111 - 115 ( 1998 )

[2] Aguzzoli , S. The Complexity of McNaughton Functions of One Variable . Advances in applied mathematics. 21.1 ( 1998 ): 58 - 77 . Web.

[3] S. Aguzzoli , S. Bova , B. Gerla , Chapter IX : Free algebras and functional representation for fuzzy logics , in: Handbook of Mathematical Fuzzy Logic, Studies in Logics, College Publications, 2011 .

[4] Paolo Amato , Antonio Di Nola, Brunella Gerla: Neural Networks And Rational Mcnaughton Functions. J. Multiple Valued Log. Soft Comput . 11 ( 1-2 ): 95 - 110 ( 2005 )