Neat things do come of it though. Code Search, for example, ended up as an technical explanation [1], which I found fascinating, and example implementation [2], which I found useful.
That's my point though: just because a retired product is heavily tied to Google's infrastructure doesn't mean that they couldn't release something useful out of it.
Be careful: "x / 16" won't get converted to "x >> 4" by the compiler if x is a signed int. I lost an argument about this in a code review once. Look at the disassembly for the case that x is and is not signed if you don't believe me.
int main(int argc,char *argv[])
{
int x = strtol(argv[1],NULL,10);
printf("result is %d\n",x/16);
return 0;
}
The resulting assembly contained no division instructions, nor a call to a divide routine, but there is one instruction that does an arithmetic right shift by 4. Changing x to unsigned changed the instruction to a logical right shift by 4.
Strangely, I can't reproduce the effect with a divide by 16. With GCC 4.5.2 -O2, I see a "shrl $4, %eax" for unsigned, and "sarl $4, %eax" for signed. However, if I divide by 2, the results are different; the function:
unsigned int div_by_2(unsigned int x) {return x/2;}
compiles to:
div_by_2:
movl %edi, %eax
shrl %eax
ret
My conclusion remains that for hot loops, you should check the compilers assembly to make sure the compiler is applying the strength reduction you expect.
It first generates an offset value in ESI: 15 if the value to divide was negative, or 0 if it was positive.
Then it adds this to the original value. This is the cunning part - well I think so anyway. It ensures that for the values where x>>4 would give the wrong value (i.e., -15<=x<0), x is made positive and smaller than 16, so that x>>4 gives the correct value of zero. For all other values, the bottom 4 bits don't affect the result of the division, so it's fine to offset them as well.
(Don't think I've ever seen VC++ generate anything like this, but I'd pretty much always have an explicit shift rather than a divide by 16 so maybe it does and I'd just never noticed. The choice of 16 usually comes from having some 4-bit field somewhere, and when dealing with bitfields you're best off using bitwise instructions.)
It's really a wonderful thing. I haven't yet figured out the specific magic combination of things that will guarantee it popping up on the phone though - sometimes it does, sometimes it doesn't. I really love Now but it needs to be omnipresent.
San Francisco, CA and Cambridge, MA - Locu is hiring Frontend
Engineers, Backend Engineers and Visual Designers -
Full-time; H-1B OK
Locu is developing technologies to change local search ($35bn
advertising market by 2014) through a number of initiatives
that help local businesses better connect with their consumers.
As part of this vision, we created one of the world's largest
semantically-annotated repositories of real-time small-business
data, which is now distributed and viewable on sites like
OpenTable, Citysearch and TripAdvisor (and more). We recently
launched Locu.com, our local business facing product, that
combines great tech and beautiful design to help local
businesses better manage their online presence.
Our beautiful offices are in downtown San Francisco, CA (Union
Square) and Cambridge, MA (Kendall Square). Check out photos
and learn more about our other perks: http://locu.com/about/jobs/
Frontend Engineering
If you are passionate about building products that will touch
millions of merchants and hundreds of millions of consumers
through the applications powered by our local data APIs, Locu
is the right place for you. [JQuery, Less, Django, etc.]
Backend engineering
We started Locu out of MIT to solve real-world problems by
leveraging the latest research in computer science. If you
are looking to solve some of the most challenging problems in
machine learning, NLP and human computation, you'll feel
right at home. [Python, Django, Node.js, Postgres, Redis,
AWS, etc.]
Design
We're looking for visual designers who are excited to
redefine what the future of local business data looks like
across web and print, and to create tools that put modern web
technology in the hands of merchants.
Interested? Drop us a line at jobs@locu.com. Please include
"[HN]" in the subject of your letter. Learn more about us at
http://locu.com/about/jobs/.
San Francisco, CA and Cambridge, MA - Locu is hiring Frontend
Engineers, Backend Engineers and Visual Designers -
Full-time; H-1B OK
Locu is developing technologies to change local search ($35bn
advertising market by 2014) through a number of initiatives
that help local businesses better connect with their consumers.
As part of this vision, we created one of the world's largest
semantically-annotated repositories of real-time small-business
data, which is now distributed and viewable on sites like
OpenTable, Citysearch and TripAdvisor (and more). We recently
launched Locu.com, our local business facing product, that
combines great tech and beautiful design to help local
businesses better manage their online presence.
Our beautiful offices are in downtown San Francisco, CA (Union
Square) and Cambridge, MA (Kendall Square). Check out photos
and learn more about our other perks: http://locu.com/about/jobs/
Frontend Engineering
If you are passionate about building products that will touch
millions of merchants and hundreds of millions of consumers
through the applications powered by our local data APIs, Locu
is the right place for you. [JQuery, Less, Django, etc.]
Backend engineering
We started Locu out of MIT to solve real-world problems by
leveraging the latest research in computer science. If you
are looking to solve some of the most challenging problems in
machine learning, NLP and human computation, you'll feel
right at home. [Python, Django, Node.js, Postgres, Redis,
AWS, etc.]
Design
We're looking for visual designers who are excited to
redefine what the future of local business data looks like
across web and print, and to create tools that put modern web
technology in the hands of merchants.
Interested? Drop us a line at jobs@locu.com. Please include
"[HN]" in the subject of your letter. Learn more about us at
http://locu.com/about/jobs/.
Hey everyone, I'm a fullstack engineer here. It's a fantastic place to work, we're doing really exciting things in a bunch of different areas. Please drop me a line (peter@locu.com) if you have any questions or just want to chat.
Both RProp and Conjugate Gradient are descent methods-- they find a path to a local minima from the starting configuration. They do not help with finding the global minimum.
Using simulated annealing to guide random initializations can help find a better minima, but to get the global minima with simulated annealing takes an inordinate amount of time.
(Poor) local minima can be sometimes reached in back propagation due to a bad setting of the learning rate and RProp does help with that. You can also repeat the learning process using one of those algorithms many times with different initial random weights and use the results of the best attempt. I think this most often suffices in practical applications of NN for getting decent results, you are right I got some of this wrong, I basically wanted to say that backprop is no longer state of the art in training and that optimization is the relatively easy part of learning.
Wow. Released, then community-sourced patches offered and integrated, all in ten hours. Sometimes open source makes me feel all warm & fuzzy inside. :)
While we do support numeric differentiation, we don't suggest you use it. What we have is automatic differentiation, which is a technique to take exact derivatives without resorting to symbolic differentation.
Check out he jet.h file which is the core implementation of this:
The technique is clever: they add an finite difference along the imaginary axis, and this turns out to give a more accurate derivative than normal forward differences.
We don't support this in Ceres and suggest autodiff instead.
I apologize for replying without actually looking at your posted code first.
What I meant to say was, "If it's all in one C++ project, it's not symbolic differentiation" and I took the liberty of changing "not symbolic" to "numeric."
Having now read your posted code, I kind of feel like a 17th century naturalist trying to classify a platypus. Clearly this technique is not symbolic differentiation, since it can only produce numerical and not symbolic results (although I suppose the Jet template could handle an "expression" type as its first argument - have you actually tried this?), and it's not really numerical in the normal sense because there's no h parameter that changes the accuracy as it varies.
As an aside, "autodmatic ifferentiation" is a terrible name, in the sense that it doesn't convey any real information about the technique, except maybe that it's being done by a computer and I knew that already. It might still be a good marketing term (like how Richard Bellman named his technique "Dynamic Programming" because it's impossible to call something "dynamic" in a perjorative sense, although there really isn't anything intrinsically dynamic, and in fact you commonly end up solving "static dynamic programming" problems).
Automatic differentation is "symbolic" in the sense that the resulting derivatives are exact, in the same way that you get exact derivatives if you differentiate by hand and implement the resulting expression. There is no approximation.
Numeric differentiation has a specific meaning - which is computing derivatives via finite differencing.
There's three ways to compute derivatives; for whatever reason most people only know about symbolic (take the derivative by hand, implement it in C++) and numeric (implement your cost function, do finite differences on each parameter to determine the gradient) differentiation. Automatic differentiation is a totally different way to take derivatives. The Wikipedia article about it is fairly good.
Interesting; this is the first I've heard of automatic differentiation and it's quite elegant and exact. Do you know why it's not covered more in academia?
I've wondered the same myself. It's rather popular in industry. I hadn't head of it until coming to Google. Fun fact: backpropagation for neural networks, which is really just a fancy word for computing the derivatives of the cost, is equivalent to reverse mode autodiff.
For the people wondering what autodiff is, I found the following article a real eye-opener when I came across it (mainly, his paper he links is very accessible: http://homepage.mac.com/sigfpe/paper.pdf).
