Life in logspace

The log lat­tice hints at the rea­son that en­g­ineers, sci­en­tists, and AI re­searchers find log­a­r­ithms so use­ful.

At this point, you may have a pretty good in­tu­ition for what log­a­r­ithms are do­ing, and you may be say­ing to yourself

Ok, I un­der­stand log­a­r­ithms, and I see how they could be a pretty use­ful con­cept some­times. Espe­cially if, like, some­one hap­pens to have an out-of-con­trol bac­te­ria colony ly­ing around. I can also see how they’re use­ful for mea­sur­ing rep­re­sen­ta­tions of things (like the length of a num­ber when you write it down, or the cost of com­mu­ni­cat­ing a mes­sage). If I squint, I can sort of see why it is that the brain en­codes many per­cepts log­a­r­ith­mi­cally (such that the tone that I per­ceive is the \(\log_2\) of the fre­quency of vibra­tion in the air), as it’s not too sur­pris­ing that evolu­tion oc­ca­sion­ally hit upon this nat­u­ral tool for rep­re­sent­ing things. I guess logs are pretty neat.

Then you start see­ing log­a­r­ithms in other strange places — say, you learn that AlphaGo pri­mar­ily ma­nipu­lated log­a­r­ithms of the prob­a­bil­ity that the hu­man would take a par­tic­u­lar ac­tion in­stead of ma­nipu­lat­ing the prob­a­bil­ities di­rectly. Then maybe you learn that sci­en­tists, en­g­ineers, and nav­i­ga­tors of yore used to pay large sums of money for gi­ant, pre-com­puted ta­bles of log­a­r­ithm out­puts.

At that point, you might say

Hey, wait, why do these logs keep show­ing up all over the place? Why are they that ubiquitous? What’s go­ing on here?

The rea­son here is that ad­di­tion is eas­ier than mul­ti­pli­ca­tion, and this is true both for nav­i­ga­tors of yore (who had to do lots of calcu­la­tions to keep their ships on course), and for mod­ern AI al­gorithms.

Let’s say you have a whole bunch of num­bers, and you know you’re go­ing to have to perform lots and lots of op­er­a­tions on them that in­volve tak­ing some num­bers you already have and mul­ti­ply­ing them to­gether. There are two ways you could do this: One is that you could bite the bul­let and mul­ti­ply them all, which gets pretty tire­some (if you’re do­ing it by hand) and/​or pretty ex­pen­sive (if you’re train­ing a gi­gan­tic neu­ral net­work on mil­lions of games of go). Alter­na­tively, you could put all your num­bers through a log func­tion (a one-time cost), and then perform all your op­er­a­tions us­ing ad­di­tion (much cheaper!), and then trans­form them back us­ing ex­po­nen­ti­a­tion when you’re done (an­other one-time cost).

Em­piri­cally, the sec­ond method tends to be faster, cheaper, and more con­ve­nient (at the cost of some pre­ci­sion, given that most log out­puts are tran­scen­den­tal).

This is the last in­sight about log­a­r­ithms con­tained in this tu­to­rial, and it is a piece of prac­ti­cal ad­vice: If you have to perform a large chain of mul­ti­pli­ca­tions, you can of­ten do it cheaper by first trans­form­ing your prob­lem into “log space”, where mul­ti­pli­ca­tion acts like ad­di­tion (and ex­po­nen­ti­a­tion acts like mul­ti­pli­ca­tion). Then you can perform a bunch of ad­di­tions in­stead, and trans­form the an­swer back into nor­mal space at the end.