Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

nature.com

Post reply on HN
Print view View original

321–328 of 328 posts

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#321

Post by thraidh »

thraidh wrote: post #320

Can someone explain why the sort3 function produced by Alphadev is correct? The instruction that was removed was: `P=min(A,C)`, which means that `P=A` at that point. The next instructions: cmp S Q cmovg Q P with `S=min(A,C)` and `Q=B` can be translated into if S>Q: P=Q or if min(A,C)>B: P=B which means: if B is the smallest, then `P=B`. Otherwise P stays as before, meaning `P=A` for Alphadev and `P=min(A,C)` for the…

Found my mistake. I wrongly assumed the algorithms shown in the paper were the original sorting algorithm and the one improved by Alphadev.

Apparently it just shows some algorithm that was modified and resulted in a different one, neither being a sorting algorithm, but the original still being better.

The text praises Alphadev by saying it makes "moves" that look like a mistake, but are actually brilliant. After that passage the code is shown that does not corroborate that statement, and just illustrates that Alphadev can make changes to code.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#322

Post by elcomet »

wsdookadr wrote: post #317
elcomet wrote: post #312

Earlier quoted context omitted.

It cannot explain because (1) it is not necessary to become good and (2) it wasn't explicitly trained to explain. But it's reasonable to imagine a later model trained to explain things. The issue is that some positions might not be explainable, as they require branching too much and a lot of edge cases, so the explanation is not understandable by the human.

It's unreasonable to give up on explanations and deem something "not understandable" when we've been doing this thing for 3000+ years called mathematics, where it's exactly explainability that we seek and the removal of doubt. The only other entities that we know of who can't communicate or explain what they're doing are animals.

Can you explain your tastes? Why you prefer an apple to an orange for instance? Not really.

Can you explain how you had the intuition for a certain idea ? No you can explain why it works but not how the intuition came.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#323

Post by wsdookadr »

elcomet wrote: post #322
wsdookadr wrote: post #317

Earlier quoted context omitted.

It's unreasonable to give up on explanations and deem something "not understandable" when we've been doing this thing for 3000+ years called mathematics, where it's exactly explainability that we seek and the removal of doubt. The only other entities that we know of who can't communicate or explain what they're doing are animals.

Can you explain your tastes? Why you prefer an apple to an orange for instance? Not really. Can you explain how you had the intuition for a certain idea ? No you can explain why it works but not how the intuition came.

This isn't a question of taste. The topic can't be trivialized to a choice between apples and oranges. I actually reject your entire last message.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#324

Post by elcomet »

wsdookadr wrote: post #323
elcomet wrote: post #322

Earlier quoted context omitted.

Can you explain your tastes? Why you prefer an apple to an orange for instance? Not really. Can you explain how you had the intuition for a certain idea ? No you can explain why it works but not how the intuition came.

This isn't a question of taste. The topic can't be trivialized to a choice between apples and oranges. I actually reject your entire last message.

My point is that most of our actions are intuitive and cannot be explained. maybe this is similar to system 1 vs system 2.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#325

Post by wsdookadr »

elcomet wrote: post #324
wsdookadr wrote: post #323

Earlier quoted context omitted.

This isn't a question of taste. The topic can't be trivialized to a choice between apples and oranges. I actually reject your entire last message.

My point is that most of our actions are intuitive and cannot be explained. maybe this is similar to system 1 vs system 2.

It's fine if you want to refer to Kahneman's classification [1] of instinctual and thorough thinking. Explainability is a separate topic. Also when the amount of energy and compute used are as high as they are.. the results, the return on investment really isn't that high. Hopefully there are better days ahead.

[1] https://en.wikipedia.org/wiki/Thinking,_Fast_and_Slow

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#326

Post by ralfn »

yunohn wrote: post #82
ralfn wrote: post #43

Earlier quoted context omitted.

If the thing you have to sort is within a known domain you can definitely beat o(n log(n)). Just expect crazy memory usage. And that's only not the case in theory. But nobody owns a real Turing machine with infinite tape and truly infinite numbers. It doesn't exist in reality. You can always divide time by multiplying space with the same factor.

Parent said: > not going to find a general sorting algorithm You said: > you have to sort is within a known domain you can definitely beat Not sure why you framed your response this way?

Sorry I didn't phrase my point well enough.

Every sorting on a computer existing in reality is within a limited domain.

The general sorting problem is an artificial problem for theoretical computers with infinite memory.

It's a philosophical problem not an engineer one

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#327

Post by manwe150 »

moonchild wrote: post #310
manwe150 wrote: post #308

Earlier quoted context omitted.

Does that end up moving high bits into the low bits? That could possibly be very helpful for all sets of strings, since the equality test will start with the first byte, so it could better to have the rotr on the hash so that the hash is less affected by the first byte (and more affected by later bytes). Just hypothetically speaking that is where the implication could break down, since it doesn’t consider the non-uni…

> the equality test will start with the first byte I would expect the equality test to compare at least a full word at a time, just as the hash hashes at least a full word at a time.

I didn’t look at their implementation, but in general, strings don’t have to be aligned so you can only peek one byte at a time looking for the end, besides not wanting to annoy valgrind and other similar UB detection tools by reading past the end of the string.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#328

Post by moonchild »

manwe150 wrote: post #327
moonchild wrote: post #310

Earlier quoted context omitted.

> the equality test will start with the first byte I would expect the equality test to compare at least a full word at a time, just as the hash hashes at least a full word at a time.

I didn’t look at their implementation, but in general, strings don’t have to be aligned so you can only peek one byte at a time looking for the end, besides not wanting to annoy valgrind and other similar UB detection tools by reading past the end of the string.

Strawman; nul-terminated strings are horribly slow for nearly every application. Hence I assume (especially given that they are using c++) that they are using length-accompanied strings rather than nul-terminated ones.
Post reply on HN