tag:blogger.com,1999:blog-11295132.post609656141647906897..comments2014-04-16T10:57:46.206-07:00Comments on A Neighborhood of Infinity: Two Papers and a PresentationDan Piponihttps://plus.google.com/107913314994758123748noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-11295132.post-38374337820333681542008-11-14T17:09:00.000-08:002008-11-14T17:09:00.000-08:00barak,I've decided I like your point of view after...barak,<BR/><BR/>I've decided I like your point of view after all and I think I'll mention it if (1) my paper is accepted and (2) I get a chance to revise it. If this happens, I'd like to acknowledge you. What name should I use. (I think I know your full name but I could be wrong.)sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-4076902253411348362008-11-14T13:56:00.000-08:002008-11-14T13:56:00.000-08:00barak,But this is what I mean by trivial:(linear f...barak,<BR/><BR/>But this is what I mean by trivial:<BR/><BR/>(linear f) => Jf f x = f<BR/><BR/>Anyway, I think we understand each other, we're just using different names. Everything in my paper could be carried out by passing linear filters into a reverse mode automatic differentiator. (So on one level, of course it is differentiation.) But I see myself as extracting out the parts of the algorithm that aren't about explicitly derivatives because in the case that your function is linear you don't need to think about calculus, just multiplying matrices.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-74857762550506671562008-11-14T11:24:00.000-08:002008-11-14T11:24:00.000-08:00> You're only computing derivatives in> ...> You're only computing derivatives in<BR/>> the sense that any linear map is the<BR/>> derivative of some function.<BR/><BR/>No, that's really not what I'm doing.<BR/><BR/>AD, at least in the form appropriate for consideration here, does not compute the derivative as a number. Rather it computes a linear function, namely a product with the Jacobian, that product being (J f x)*v for forward AD, and (J f x)^T*v for reverse AD, where J f x is the Jacobian matrix of f at x.<BR/><BR/>Here is another way to look at it. The Jacobian J f x is a matrix of numbers. But we can abstract away the representation of this matrix, instead considering it merely as a linear map. (In differential geometry this is called the push-forward.) That is what is done in AD. If we denote the forward-mode AD transform operator as Jf, then we have a numerical equality, Jf f x v = (J f x)*v, but calculated efficiently. And with Jr being the reverse mode operator, we have a numerical equality Jr f x v = (J f x)^T*v, but calculated efficiently.<BR/><BR/>When f is linear, Jf f x v = (J f x)*v = f v for any vectors x:R^n and v:R^n. These have the same extension, so we can say (linear f) => Jf f x = f. Similarly, (linear f) => Jr f x = f^*, where f^* is the adjoint of f.<BR/><BR/>Note that I'm not constructing any quadratic functions, or any other function whose derivative is f, or anything like that.<BR/><BR/>> ... representing linear functions<BR/>> as quadratic ...<BR/><BR/>From the linear function f:R^n -> R^m we can construct a bilinear form g x y = y^T (f x). Appropriate cascaded application of AD operators to g can yield f or f^*. This is made cleaner if we note that, in f x, the vector x is living in the input space of f; but in g x y, it is more natural to consider x to be living instead in the tangent space of some point in the input space of f; and to consider y to be living not in the output space of f, or even the tangent space of some point in the output space of f, but rather in the co-tangent space of some point in the output space of f. This renders the dot product in the definition of g meaningful.barakhttp://barak.a.pearlmutter.myopenid.com/noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-50139438197745956492008-11-13T09:34:00.000-08:002008-11-13T09:34:00.000-08:00barak,You're only computing derivatives in the sen...barak,<BR/><BR/>You're only computing derivatives in the sense that any linear map is the derivative of some function. But actually, I have considered this. At one point I toyed with the idea of representing linear functions as quadratic functions in this way: you get a single representation (as sparse as your implementation of the quadratic) from which I think a compiler can extract both the linear function and its adjoint. I think that's right.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-10744251879558354892008-11-13T08:30:00.000-08:002008-11-13T08:30:00.000-08:00Thanks for a wonderful blog. Most of your posts ar...Thanks for a wonderful blog. Most of your posts are great fun, but there is a technical connection here I feel obliged to point out.<BR/><BR/>The manuscript <A HREF="http://www.sigfpe.com/adjoint.pdf" REL="nofollow">Two Tricks for the Price of One: Linear Filters and their Adjoints</A> says:<BR/><BR/><I>It is closely related to adjoint mode automatic differentiation [5] although the principle under discussion here is more general as we are not in fact computing derivatives.</I><BR/><BR/>This isn't quite accurate. If we let<BR/> <BR/> y = f x<BR/><BR/>where f : R^n -> R^m then we can define the Jacobian matrix operator J by<BR/><BR/> (J f x)_ij = (d/dx_j) (f_i x)<BR/><BR/>meaning that the (i,j)-th element of J f x is the derivative of the i-th component of f x with respect to the j-th component of x, evaluated at the given x.<BR/><BR/>Forward accumulation mode automatic differentiation efficiently calculates this matrix-vector product:<BR/><BR/> (J f x) v<BR/><BR/>for any vector v:R^n, and reverse accumulation mode automatic differentiation efficiently calculates this matrix-vector product:<BR/><BR/> (J f x)^T v<BR/><BR/>for any vector v:R^m.<BR/><BR/>In the case treated in the above manuscript f is linear, so we could write<BR/><BR/> f x = F x<BR/><BR/>where F is some matrix, so<BR/><BR/> J f x = F<BR/><BR/> (J f x)^T = F^T<BR/><BR/> (J f x)^T v = F^T v = f^* v<BR/><BR/>where f^* is the adjoint of f.<BR/><BR/>In fact the transformation described in the above manuscript is <I>precisely</I> reverse-mode AD, in this case. (Note that J f x is constant in x, so some simplifications occur. These are precisely the optimizations a good compiler would make in eliminating dead code or in simplifying a+0*b to a.)barakhttp://barak.a.pearlmutter.myopenid.com/noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-72806568749063167732008-09-18T11:20:00.000-07:002008-09-18T11:20:00.000-07:00bob c,Steganographic quines? Hmmm...there might be...bob c,<BR/><BR/>Steganographic quines? Hmmm...there might be some interesting ideas to play with there.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-6382303884054941072008-09-17T14:45:00.000-07:002008-09-17T14:45:00.000-07:00Wow, the quine is very cool. I once did one that ...Wow, the quine is very cool. I once did one that did the cheating approach of sticking the source in an image (http://bobcopeland.com/tile.html) but that was in perl where quines are really easy to write. Table of all the ascii values is a nice approach.Bob Chttp://www.blogger.com/profile/03259347506426060152noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-75545880278399771052008-09-16T15:22:00.000-07:002008-09-16T15:22:00.000-07:00Twan,I actually wrote that paper a few years ago, ...Twan,<BR/><BR/>I actually wrote that paper a few years ago, before I'd started playing with languages with immutable values (like Haskell), so it reflects my C++ background. My procedural programming colleagues didn't blink at it because it corresponds to the notation in almost all of the languages they use (from Matlab and Mathematica to Fortran and C++). I suspect the reviewers won't blink at it either.<BR/><BR/>But fundamentally, I do agree with your criticism and if I get a chance I may change my notation.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-86867164860943313912008-09-16T15:14:00.000-07:002008-09-16T15:14:00.000-07:00In the adjoint paper, why do you write (a,b) = <...In the adjoint paper, why do you write (a,b) = <matrix>(a,b) when you mean an <I>update</I>? To me this is very confusing, using (a',b') = <matrix>(a,b) would have been clearer.Twan van Laarhovenhttp://www.blogger.com/profile/18138442561179666544noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-5416330673417238992008-09-16T12:58:00.000-07:002008-09-16T12:58:00.000-07:00Fixed now.Fixed now.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-2876297066647501002008-09-16T12:03:00.000-07:002008-09-16T12:03:00.000-07:00Hey, the links to your papers don't seem to be wor...Hey, the links to your papers don't seem to be working.Keeganhttp://www.blogger.com/profile/09118581957266220491noreply@blogger.com