The max-plus algebra R∪{−∞} is defined in terms of a combination of the following two operations: addition a⊕b:=max(a,b) and multiplication a⊗b:=a+b. In this study, we propose a new method to ...characterize the set of all solutions of a max-plus two-sided linear system A⊗x=B⊗x. We demonstrate that the minimum “min-plus” linear subspace containing the “max-plus” solution space can be computed by applying the alternating method, which is a well-known algorithm to compute single solutions of two-sided systems. Further, we derive a sufficient condition for the “min-plus” and “max-plus” subspaces to be identical. The computational complexity of the algorithm presented in this study is pseudo-polynomial.
Switching linear systems over the max-plus algebra can be used to model production plants where different choices in resource allocation are possible. In such case, internal and external variables ...represent the time instants at which internal or external events occur. In particular, output variables represent the time instants at which lots of manufactured goods are released to the market. Here, we consider the problems of system synchronization and sub-synchronization, which consist in forcing the output of a system to equal or to anticipate the output of a given model. Their solution in the max-plus framework provides a viable strategy to control a given production plant in such a way to comply with a desired production time schedule. Using structural methods and introducing novel structural notions, necessary and sufficient solvability conditions are given. Practical methods to construct solutions are illustrated and discussed.
We present necessary and sufficient criteria for a max-algebraic supereigenvector, i.e., a solution of the system A⊗x≥x with A∈R‾n×n in max-plus algebra, to be an extremal. We also show that the ...suggested extremality criteria can be verified in O(n2) time for any given solution x.
Max-Plus Algebra has been applied in several contexts, especially in the control of discrete events systems. In this article, we discuss another application closely related to control: the use of ...Max-Plus algebra concepts in the context of reinforcement learning. Max-Plus Algebra and reinforcement learning are strongly linked due to the latter’s dependence on the Bellman Equation which, in some cases, is a linear Max-Plus equation. This fact motivates the application of Max-Plus algebra to approximate the value function, central to the Bellman Equation and thus also to reinforcement learning. This article proposes conditions so that this approach can be done in a simple way and following the philosophy of reinforcement learning: explore the environment, receive the rewards and use this information to improve the knowledge of the value function. The proposed conditions are related to two matrices and impose on them a relationship that is analogous to the concept of weak inverses in traditional algebra.
Tropical Geometry and Machine Learning Maragos, Petros; Charisopoulos, Vasileios; Theodosis, Emmanouil
Proceedings of the IEEE,
05/2021, Letnik:
109, Številka:
5
Journal Article
Recenzirano
Odprti dostop
Tropical geometry is a relatively recent field in mathematics and computer science, combining elements of algebraic geometry and polyhedral geometry. The scalar arithmetic of its analytic part ...preexisted in the form of max-plus and min-plus semiring arithmetic used in finite automata, nonlinear image processing, convex analysis, nonlinear control, optimization, and idempotent mathematics. Tropical geometry recently emerged in the analysis and extension of several classes of problems and systems in both classical machine learning and deep learning. Three such areas include: 1) deep neural networks with piecewise linear (PWL) activation functions; 2) probabilistic graphical models; and 3) nonlinear regression with PWL functions. In this article, we first summarize introductory ideas and objects of tropical geometry, providing a theoretical framework for both the max-plus algebra that underlies tropical geometry and its extensions to general max algebras. This unifies scalar and vector/signal operations over a class of nonlinear spaces, called weighted lattices, and allows us to provide optimal solutions for algebraic equations used in tropical geometry and generalize tropical geometric objects. Then, we survey the state of the art and recent progress in the aforementioned areas. First, we illustrate a purely geometric approach for studying the representation power of neural networks with PWL activations. Then, we review the tropical geometric analysis of parametric statistical models, such as HMMs; later, we focus on the Viterbi algorithm and related methods for weighted finite-state transducers and provide compact and elegant representations via their formal tropical modeling. Finally, we provide optimal solutions and an efficient algorithm for the convex regression problem, using concepts and tools from tropical geometry and max-plus algebra. Throughout this article, we also outline problems and future directions in machine learning that can benefit from the tropical-geometric point of view.
This paper is a survey of the history of max-plus algebra and its role in the field of discrete event systems during the last three decades. It is based on the perspective of the authors but it ...covers a large variety of topics, where max-plus algebra plays a key role.
This work investigates the computation of finite abstractions of Stochastic Max-Plus-Linear (SMPL) systems and their formal verification against general bounded-time linear temporal specifications. ...SMPL systems are probabilistic extensions of discrete-event MPL systems, which are widely employed for modeling engineering systems dealing with practical timing and synchronization issues. Departing from the standard existing approaches for the analysis of SMPL systems, we newly propose to construct formal, finite abstractions of a given SMPL system: the SMPL system is first re-formulated as a discrete-time Markov process, then abstracted as a finite-state Markov Chain (MC). The derivation of precise guarantees on the level of the introduced formal approximation allows us to probabilistically model check the obtained MC against bounded-time linear temporal specifications (which are of rather general applicability), and to reliably export the obtained results over the original SMPL system. The approach is practically implemented on a dedicated software and is elucidated and run over numerical examples.
We study how geometric properties of tropical convex sets and polytopes, which are of interest in many application areas, manifest themselves in their algebraic structure as modules over the tropical ...semiring. Our main results establish a close connection between pure dimension of tropical convex sets, and projectivity (in the sense of ring theory). These results lead to a geometric understanding of idempotency for tropical matrices. As well as their direct interest, our results suggest that there is substantial scope to apply ideas and techniques from abstract algebra (in particular, ring theory) in tropical geometry.
PDF
