Aussie AI

Max-Plus and Tropical Algebra

  • Book Excerpt from "Generative AI in C++"
  • by David Spuler, Ph.D.

Max-Plus and Tropical Algebra

The “max-plus” or “min-max-plus” networks use maximum or minimum operations, combined with addition, rather than multiplication. The theoretical basis of this idea is called “tropical algebra” which is a specialized mathematics consisting of min/max and addition to define a pseudo-multiplication operation.

Some other areas of theory are related to this area. Addition in the logarithmic number system can be approximated with maximum and addition (like “max-plus”). The tropical algebra is also relevant for “log-sum-exp networks” which calculate the logarithm of the sum of exponentials, which is similar to LNS addition, and can possibly be approximated similarly. Also, the calculation of the Softmax function has a denominator that is the sum-of-exponentials, so Softmax approximation is similar to LNS addition, and could involve theory from max-plus networks and tropical algebra.

Research papers on max-plus networks and tropical algebra:

  1. Yunxiang Zhang, Samy Blusseau, Santiago Velasco-Forero, Isabelle Bloch, Jesus Angulo, 2019, Max-plus Operators Applied to Filter Selection and Model Pruning in Neural Networks, https://arxiv.org/abs/1903.08072, Code: https://github.com/yunxiangzhang (Analysis of the “max-plus” operation, based on maximum and addition, such as the maximum of the pairwise sum of an internal computation plus a weight, rather than the sum of multiplied pairs.)
  2. Ye Luo, Shiqing Fan, 2021, Min-Max-Plus Neural Networks, Feb 2021, https://arxiv.org/abs/2102.06358 (Theory of max-plus networks, including “tropical math”, also with minimum.)
  3. Philippe Bich; Luciano Prono; Mauro Mangia; Fabio Pareschi; Riccardo Rovatti; Gianluca Setti 2022, Aggressively prunable MAM²-based Deep Neural Oracle for ECG acquisition by Compressed Sensing, 2022 IEEE Biomedical Circuits and Systems Conference (BioCAS) 13-15 October 2022 DOI: 10.1109/BioCAS54905.2022.9948676, https://doi.org/10.1109/BioCAS54905.2022.9948676, https://ieeexplore.ieee.org/abstract/document/9948676, https://faculty.kaust.edu.sa/en/publications/aggressively-prunable-mam-based-deep-neural-oracle-for-ecg-acquis, (Not traditional max-plus; uses max-and-min with multiplication.)
  4. Luciano Prono; Mauro Mangia; Fabio Pareschizy; Riccardo Rovatti; Gianluca Settizy, 2022, A Non-conventional Sum-and-Max based Neural Network layer for Low Power Classification, IEEE International Symposium on Circuits and Systems (ISCAS), June 2022, DOI: 10.1109/ISCAS48785.2022.9937576, https://ieeexplore.ieee.org/document/9937576
  5. Luciano Prono, Philippe Bich, Mauro Mangia, Fabio Pareschi, 2023, A Multiply-And-Max/min Neuron Paradigm for Aggressively Prunable Deep Neural Networks, https://www.techrxiv.org/articles/preprint/A_Multiply-And-Max_min_Neuron_Paradigm_for_Aggressively_Prunable_Deep_Neural_Networks/22561567, PDF: https://www.techrxiv.org/articles/preprint/A_Multiply-And-Max_min_Neuron_Paradigm_for_Aggressively_Prunable_Deep_Neural_Networks/22561567/1/files/40119760.pdf
  6. Yunsheng Li, Yinpeng Chen, Xiyang Dai, Dongdong Chen, Mengchen Liu, Lu Yuan, Zicheng Liu, Lei Zhang, Nuno Vasconcelos, 2021, MicroNet: Improving Image Recognition with Extremely Low FLOPs, https://ieeexplore.ieee.org/abstract/document/9857393 PDF: https://openaccess.thecvf.com/content/ICCV2021/papers/Li_MicroNet_Improving_Image_Recognition_With_Extremely_Low_FLOPs_ICCV_2021_paper.pdf (Uses shift-max algorithm.)
  7. Goodfellow, I. J., Warde-Farley, D., Mirza, M., Courville, A., and Bengio, Y., 2013, Maxout networks, In Proceedings of the International Conference on Machine Learning (ICML), 2013, https://arxiv.org/abs/1302.4389 (Uses maximum operator arithmetic.)
  8. S. Fan, L. Liu, and Y. Luo. 2021, An alternative practice of tropical convolution to traditional convolutional neural networks, In 2021 The 5th International Conference on Compute and Data Analysis, pages 162–168, 2021, https://arxiv.org/abs/2103.02096 (Tropical arithmetic)

For more research papers on max-plus neural networks and tropical algebra, see https://www.aussieai.com/research/zero-multiplication#maxplus.

 

• Next:

• Up: Table of Contents

• Buy: Generative AI in C++: Coding Transformers and LLMs

Generative AI in C++ The new AI programming book by Aussie AI co-founders:
  • AI coding in C++
  • Transformer engine speedups
  • LLM models
  • Phone and desktop AI
  • Code examples
  • Research citations

Get your copy from Amazon: Generative AI in C++