Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Log semiring
open-in-new
<h2 id="definition">Definition</h2> <p>The operations on the log semiring can be defined extrinsically by mapping them to the non-negative real numbers, doing the operations there, and mapping them back. The non-negative real numbers with the usual operations of addition and multiplication form a <a href="/facts/Semiring/7cSvWXVQ">semiring</a> (there are no negatives), known as the <a href="/facts/Probability_semiring/7cSvWXVQ">probability semiring</a>, so the log semiring operations can be viewed as <a href="/facts/Pullback/AcMfwboF">pullbacks</a> of the operations on the probability semiring, and these are <a href="/facts/Isomorphic/pj8KgkxU">isomorphic</a> as rings. </p><p>Formally, given the extended real numbers R ∪ {–∞, +∞}<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> and a base <i>b</i> ≠ 1, one defines: </p> x ⊕ b y = log b ( b x + b y ) x ⊗ b y = log b ( b x × b y ) = log b ( b x + y ) = x + y . {\displaystyle {\begin{aligned}x\oplus _{b}y&=\log _{b}\left(b^{x}+b^{y}\right)\\x\otimes _{b}y&=\log _{b}\left(b^{x}\times b^{y}\right)=\log _{b}\left(b^{x+y}\right)=x+y.\end{aligned}}} <p>Regardless of base, log multiplication is the same as usual addition, x ⊗ b y = x + y {\displaystyle x\otimes _{b}y=x+y} , since logarithms take multiplication to addition; however, log addition depends on base. The units for usual addition and multiplication are 0 and 1; accordingly, the unit for log addition is log b 0 = − ∞ {\displaystyle \log _{b}0=-\infty } for b > 1 {\displaystyle b>1} and log b 0 = − log 1 / b 0 = + ∞ {\displaystyle \log _{b}0=-\log _{1/b}0=+\infty } for b < 1 {\displaystyle b<1} , and the unit for log multiplication is log 1 = 0 {\displaystyle \log 1=0} , regardless of base. </p><p>More concisely, the unit log semiring can be defined for base <i>e</i> as: </p> x ⊕ y = log ( e x + e y ) x ⊗ y = x + y . {\displaystyle {\begin{aligned}x\oplus y&=\log \left(e^{x}+e^{y}\right)\\x\otimes y&=x+y.\end{aligned}}} <p>with additive unit −∞ and multiplicative unit 0; this corresponds to the max convention. </p><p>The opposite convention is also common, and corresponds to the base 1/<i>e</i>, the minimum convention:<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p> x ⊕ y = − log ( e − x + e − y ) x ⊗ b y = x + y . {\displaystyle {\begin{aligned}x\oplus y&=-\log \left(e^{-x}+e^{-y}\right)\\x\otimes _{b}y&=x+y.\end{aligned}}} <p>with additive unit +∞ and multiplicative unit 0. </p> <h2 id="properties">Properties</h2> <p>A log semiring is in fact a <a href="/facts/Semifield/4UsQTJMm">semifield</a>, since all numbers other than the additive unit −∞ (or +∞) has a multiplicative inverse, given by − x , {\displaystyle -x,} since x ⊗ − x = log b ( b x ⋅ b − x ) = log b ( 1 ) = 0. {\displaystyle x\otimes -x=\log _{b}(b^{x}\cdot b^{-x})=\log _{b}(1)=0.} Thus log division ⊘ is well-defined, though log subtraction ⊖ is not always defined. </p><p>A mean can be defined by log addition and log division (as the <a href="/facts/Quasi-arithmetic_mean/LeU10jRp">quasi-arithmetic mean</a> corresponding to the exponent), as </p> M l m ( x , y ) := ( x ⊕ y ) ⊘ 2 = log b ( ( b x + b y ) / 2 ) = log b ( b x + b y ) − log b 2 = ( x ⊕ y ) − log b 2. {\displaystyle M_{\mathrm {lm} }(x,y):=(x\oplus y)\oslash 2=\log _{b}{\bigl (}(b^{x}+b^{y})/2{\bigr )}=\log _{b}(b^{x}+b^{y})-\log _{b}2=(x\oplus y)-\log _{b}2.} <p>This is just addition shifted by − log b 2 , {\displaystyle -\log _{b}2,} since logarithmic division corresponds to linear subtraction. </p><p>A log semiring has the usual Euclidean metric, which corresponds to the <a href="/facts/Logarithmic_scale/CvIGK5TQ">logarithmic scale</a> on the <a href="/facts/Positive_real_numbers/VFXU56H9">positive real numbers</a>. </p><p>Similarly, a log semiring has the usual <a href="/facts/Lebesgue_measure/8us9cGoW">Lebesgue measure</a>, which is an <a href="/facts/Invariant_measure/X75B3PcM">invariant measure</a> with respect to log multiplication (usual addition, geometrically translation) with corresponds to the <a href="/facts/Logarithmic_measure/VFXU56H9">logarithmic measure</a> on the <a href="/facts/Probability_semiring/7cSvWXVQ">probability semiring</a>. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Logarithmic_mean/j386VtQb">Logarithmic mean</a></li> <li><a href="/facts/LogSumExp/m6jQDk1a">LogSumExp</a></li> <li><a href="/facts/Softmax_function/pvxeWV6L">Softmax</a></li></ul> <h2 id="notes">Notes</h2> <ul><li><a href="/facts/M._Lothaire/pC43ftpJ">Lothaire, M.</a> (2005). <a href="https://archive.org/details/appliedcombinato0000loth"><i>Applied combinatorics on words</i></a>. Encyclopedia of Mathematics and Its Applications. Vol. 105. A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, <a href="/facts/Gesine_Reinert/YfQIfkcL">Gesine Reinert</a>, <a href="/facts/Sophie_Schbath/57VMYyCB">Sophie Schbath</a>, Michael Waterman, Philippe Jacquet, <a href="/facts/Wojciech_Szpankowski/hfopodEp">Wojciech Szpankowski</a>, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and <a href="/facts/Val%C3%A9rie_Berth%C3%A9/0puS3RSe">Valérie Berthé</a>. Cambridge: <a href="/facts/Cambridge_University_Press/fgEBSSRq">Cambridge University Press</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-521-84802-4. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:1133.68067">1133.68067</a>.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Since b − x = ( b − 1 ) x = ( 1 / b ) x {\displaystyle b^{-x}=\left(b^{-1}\right)^{x}=(1/b)^{x}} <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Usually only one infinity is included, not both, since ∞ ⊗ − ∞ = ∞ + ( − ∞ ) {\displaystyle \infty \otimes -\infty =\infty +(-\infty )} is ambiguous, and is best left undefined, as is 0/0 in real numbers. <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Lothaire 2005, p. 211. - Lothaire, M. (2005). Applied combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 105. A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé. Cambridge: Cambridge University Press. ISBN 0-521-84802-4. Zbl 1133.68067. <a href="https://archive.org/details/appliedcombinato0000loth" target="_blank">https://archive.org/details/appliedcombinato0000loth</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> </ol>