MV-tropical polynomials and neural networks Stefano Aguzzolia , Antonio Di Nolab , Brunella Gerlac and Ciro Russod a DI - Università di Milano, Via Giovanni Celoria 18, 20133 Milano, Italy b Dipartimento di Matematica, Università di Salerno, Italy c DiSTA - Università dell’ Insubria, Via O. Rossi 9, 21100 Varese, Italy d Departamento de Matematica, Universidade Federal da Bahia, Salvador, Bahia, Brazil 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 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 flexible 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 coefficients, that can be considered as truth functions of formulas of the infinite- valued 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 inter- pretability, amalgamability and reuse of these objects. Many-valued logic has been proposed WILFVietri Wilf 2021:The 13th International Workshop on Fuzzy Logic and Applications, December 20-22, 2021, Vietri sul Mare, Italy ! aguzzoli@di.unimi.it (S. Aguzzoli); adinola@unisa.it (A. D. Nola); brunella.gerla@uninsubria.it (B. Gerla); ciro.russo@ufba.br (C. Russo) © 2020 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) ORCID: 0000-0002-7588-5048 (S. Aguzzoli), 0000-0003-3313-6724 (A. Di Nola), 0000-0002-9563-2136 (B. Gerla), 0000-0002-2513-270X (C. Russo) 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, definitions 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 define 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 definitions and properties of semirings and semimodules over them. Most of this material can be found in [15]. Definition 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 satisfies the equation x + x = x, • a semifield if hS \ {0}, ·, 1i is an Abelian group. Many relevant examples of semirings are known, among which we recall the (commu- tative) one of natural numbers hN, +, ·, 0, 1i. Further let R = R ∪ {−∞}. The structure hR, max, +, −∞, 0i is an idempotent semifield, sometimes called the tropical semiring. Definition 2.2. Let S be a semiring. A (left) S-semimodule is a commutative monoid hM, +, 0i with an external operation with coefficients 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 defined 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 hS X , +, 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 ∈ S X . Then we can define a scalar multiplication in S X as follows: · : (a, f ) ∈ S × S X 7−→ a · f ∈ S X , with the map a · f defined as (a · f )(x) = af (x) for all x ∈ X. It is clear that S X is a left S-semimodule. The semimodule S X can be defined also for X = ∅, in which case we obtain, up to an isomorphism, the one-element semimodule {0}. Remark 2.4. In all the definitions and results that can be stated both for left and right semi- modules, 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 infinite-valued propositional logic. In this section we recall the definition of MV-algebra and, briefly, some of the contents of the aforementioned papers; for a comprehensive study of MV-algebras we refer the reader to [8]. Definition 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 Definition 3.1 can be formulated in the language of Universal Algebra by means of equations, MV-algebras form a variety. Congruences and homomorphisms are defined 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 define 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 well- known 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 ∧ defined 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 satisfies 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 ∗ defined, 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 defined 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 defined 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 fixed positive element of G and [0, u] = {x ∈ G | 0 ≤ x ≤ u}. Now let us define, 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 MV- algebras 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 differently specified, we will refer only to A∨⊙ , all the results holding also for A∧⊕ up to the application of ∗ . We recall the following definition from [5]. Definition 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 iff b ≤ a∗ (where a ≤ b iff 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 define 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 coefficients in A, is an expression of the form a ⊙ X1j1 ⊙ . . . ⊙ Xnjn , with a ∈ A and j1 , . . . , jn nonnegative integers, with the assumption that Xi0 = 1. A (∨, ⊙)-MV-polynomial is a semilinear combination of monomials: 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 coefficients in A defines a function p̃ : n A −→ 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̃ verifies the following properties: P1 p̃ : [0, 1]n → [0, 1] is a continuous function P P2 p̃ is piecewise linear and each linear piece has locally the form a0 + ni=1 ai xi , where ai ∈ N for i > 0 and a0 ∈ R P3 p̃ is convex. 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} = xn = ((nx − (n − 1)) ∨ 0) ∧ 1 . | ⊙ ·{z x n times 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, W a ≥ 0 and b ∈ R if and only if it has a representation d as a (∨, ⊙)-MV-polynomial of the form i ci ⊙ X for ci ∈ [0, 1] and di ∈ N. i Proof. By a simpleW structural induction argument, we can prove that any function associated d with a polynomial i ci ⊙ X has the properties of the Proposition. i 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 = X a ⊙ (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 = X 0 . 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] (iff p̃ is the constant function 1), or Z(p) ⊆ {1}. In the latter case, Z(p) = ∅ iff p̃ is a constant function different 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). Definition 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 coefficients and real degree zero coefficient. Differently from McNaughton functions that take {0, 1} values on {0, 1}n , generalized Mc- Naugthon 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. Definition 4.5. An MV-tropical rational function is the difference of two MV-tropical polyno- mial 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 ) =   ! ! Xn(l) (l−1) nX X n ψ ωok ψ  ωkj ψ . . . ωli xi + bi . . .  , k=1 j=1 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 X Xn G(x1 , . . . , xn ) = αi ψ  wij xj + bi  , (1) 1=1 j=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 defined 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] defined as: n̄ X F (x) = αi ψ (wi x + bi ) 1=1 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̄ X f (x) = αi ψ (wi x + 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 benefit 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. 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 Mc- naughton Functions. J. Multiple Valued Log. Soft Comput. 11(1-2): 95-110 (2005) [5] Belluce L. P., Di Nola A., Commutative Rings whose Ideals form an MV-algebra, Mathe- matical 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, Idempo- tent 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. Communica- tions in Algebra 41:3 (2013), 1017–1048. [14] Di Nola, A., and Russo, C.; Corrigendum to “Semiring and semimodule issues in MV- algebras, 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 Learn- ing," in Proceedings of the IEEE, vol. 109, no. 5, pp. 728-755, May 2021. [18] McNaughton R., A theorem about infinite-valued sentential logic, Journal of Symbolic Logic, 16, 1–13, 1951. [19] Mundici D., Interpretation of AF C ∗ -algebras in Łukasiewicz sentential calculus, J. Func- tional Analysis, 65, 15–63, 1986. [20] Mundici D., A Constructive Proof of McNaughton’s Theorem in Infinite-Valued Logic, Journal of Symbolic Logic, 59, 596–602, 1994. [21] Russo C., A Unified 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 Artificial 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.