Skip to main content

26.09.2023 | Original Paper

Representing piecewise linear functions by functions with small arity

verfasst von: Christoph Koutschan, Bernhard Moser, Anton Ponomarchuk, Josef Schicho

Erschienen in: Applicable Algebra in Engineering, Communication and Computing

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

A piecewise linear function can be described in different forms: as a nested expression of \(\min\)- and \(\max\)-functions, as a difference of two convex piecewise linear functions, or as a linear combination of maxima of affine-linear functions. In this paper, we provide two main results: first, we show that for every piecewise linear function \(f:{\mathbb{R}}^{n} \rightarrow {\mathbb{R}}\), there exists a linear combination of \(\max\)-functions with at most \(n+1\) arguments, and give an algorithm for its computation. Moreover, these arguments are contained in the finite set of affine-linear functions that coincide with the given function in some open set. Second, we prove that the piecewise linear function \(\max (0, x_{1}, \ldots , x_{n})\) cannot be represented as a linear combination of maxima of less than \(n+1\) affine-linear arguments. This was conjectured by Wang and Sun (IEEE Trans Inf Theory 51:4425–4431, 2005) in a paper on representations of piecewise linear functions as linear combination of maxima.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Arora, R., Basu, A., Mianjy, P., Mukherjee, A.: Understanding deep neural networks with rectified linear units. In: ICLR (2018) Arora, R., Basu, A., Mianjy, P., Mukherjee, A.: Understanding deep neural networks with rectified linear units. In: ICLR (2018)
3.
Zurück zum Zitat Goodfellow, I., Bengio, Y., Courville, A.: Deep Learning, pp. 164–172. MIT Press (2016)MATH Goodfellow, I., Bengio, Y., Courville, A.: Deep Learning, pp. 164–172. MIT Press (2016)MATH
4.
Zurück zum Zitat Gritzmann, P., Sturmfels, B.: Minkowski addition of polytopes: computational complexity and applications to Gröbner bases. SIAM J. Discrete Math. 6(2), 246–269 (1993)MathSciNetCrossRefMATH Gritzmann, P., Sturmfels, B.: Minkowski addition of polytopes: computational complexity and applications to Gröbner bases. SIAM J. Discrete Math. 6(2), 246–269 (1993)MathSciNetCrossRefMATH
5.
Zurück zum Zitat Hertrich, C., Basu, A., Di Summa, M., Skutella, M.: Towards lower bounds on the depth of ReLu neural networks. NeurIPS 34, 3336–3348 (2021)MATH Hertrich, C., Basu, A., Di Summa, M., Skutella, M.: Towards lower bounds on the depth of ReLu neural networks. NeurIPS 34, 3336–3348 (2021)MATH
6.
Zurück zum Zitat Kripfganz, A., Schulze, R.: Piecewise affine functions as a difference of two convex functions. Optimization 18(1), 23–29 (1987)MathSciNetCrossRefMATH Kripfganz, A., Schulze, R.: Piecewise affine functions as a difference of two convex functions. Optimization 18(1), 23–29 (1987)MathSciNetCrossRefMATH
7.
Zurück zum Zitat Montúfar, G., Ren, Y., Zhang, L.: Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums. SIAM J. Appl. Algebra Geom. 6(4), 618–649 (2022)MathSciNetCrossRefMATH Montúfar, G., Ren, Y., Zhang, L.: Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums. SIAM J. Appl. Algebra Geom. 6(4), 618–649 (2022)MathSciNetCrossRefMATH
8.
Zurück zum Zitat Nair, V., Hinton, G.E.: Rectified linear units improve restricted Boltzmann machines. In: ICML, pp. 807–814. Omnipress (2010) Nair, V., Hinton, G.E.: Rectified linear units improve restricted Boltzmann machines. In: ICML, pp. 807–814. Omnipress (2010)
9.
Zurück zum Zitat Ovchinnikov, S.: Max-min representation of piecewise linear functions. Beitr. Algebra Geom. 43(1), 297–302 (2002)MathSciNetMATH Ovchinnikov, S.: Max-min representation of piecewise linear functions. Beitr. Algebra Geom. 43(1), 297–302 (2002)MathSciNetMATH
10.
Zurück zum Zitat Schlüter, N., Darup, M.S.: Novel convex decomposition of piecewise affine functions. In: Proceedings of the 21th IFAC World Congress. Elsevier (2020) Schlüter, N., Darup, M.S.: Novel convex decomposition of piecewise affine functions. In: Proceedings of the 21th IFAC World Congress. Elsevier (2020)
11.
Zurück zum Zitat Tarela, J., Martinez, M.: Region configurations for realizability of lattice piecewise-linear models. Math. Comput. Model. 30(11), 17–27 (1999)MathSciNetCrossRefMATH Tarela, J., Martinez, M.: Region configurations for realizability of lattice piecewise-linear models. Math. Comput. Model. 30(11), 17–27 (1999)MathSciNetCrossRefMATH
Metadaten
Titel
Representing piecewise linear functions by functions with small arity
verfasst von
Christoph Koutschan
Bernhard Moser
Anton Ponomarchuk
Josef Schicho
Publikationsdatum
26.09.2023
Verlag
Springer Berlin Heidelberg
Erschienen in
Applicable Algebra in Engineering, Communication and Computing
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-023-00627-1