3 ms·

Sutton cites people who were not convinced by the success of Deep Blue in chess: > They said that ``brute force" search may have won this time, but it was not

Sutton cites people who were not convinced by the success of Deep Blue in chess: > They said that ``brute force" search may have won this time, but it was not a general strategy, and anyway it was not how people played chess. But it is now clear that these people were completely right! The Deep Blue approach (apparently mostly brute force search) didn't scale. E.g. Go wasn't solved this way, and the AlphaGo approach (based on reinforcement learning) did in fact scale to a lot of other games with AlphaZero and MuZero. Sutton in fact says that both search and learning produce the big success in AI. But now, with the dominance of ML, it seems that mainly learning is responsible the big successes in AI, not search. Machine learning means that the AI models aren't written by hand, GOFAI style, like Deep Blue, but instead by a learning algorithm, which in turn is written by hand. That seems to be the breakthrough, not brute force search. (Do GPTs use "search" in any conventional way? I don't think so.)

cs702 3y ago
We train deep learning models with SGD, which is in fact a form of search -- in a high-dimensional parameter space. The purpose of SGD is to find parameter values that minimize a training loss.
- spmurrayzzz 3y ago
  I was thinking along similar lines, it does smell like search to me at its core. But do you think there is a meaningful differentiation for something more nuanced like AdamW? Does the latter fall into the "brute force search" category too though it tends to converge faster (and arguably more optimally than SGD per Jeremy Howard's observations)?
brresnic123 3y ago
SGD is a method of learning from examples (mapping X -> y). RL is a method of search (maximizing reward signal in a potentially open-ended environment, based on feedback on the actions that a model takes). Go was solved by combining learning and search (e.g. narrowing the search space with learned, educated guesses). Pretrained dense GPTs don't search in any conventional way. However, when these GPTs are fine-tuned using RL, an aspect of search is reintroduced. One the most interesting directions labs are pursuing to improve on today's best LLMs is to fine-tune them with search (RL) after a learning-based (next-token prediction) pre-training.
- cubefox 3y ago
  Yes, AlphaGo does use search, but classifying RL as search seems to be stretching the term.
TacticalCoder 3y ago
However the ultimate optimal game of chess is still not known/solved though (in the end it's either a win for white, for black or a draw) and brute-force is alive and well: every possible position with seven pieces on board has been solved by brute-force and the endgame is now only one lookup in a lookup table when there are only seven pieces left on board. I think they're currently solving it for eight pieces. So it's learning but then brute-force for the end game.
gradascent 3y ago
If I remember correctly, the algorithm in Alpha Go used a combination of reinforcement learning and searching the space of moves and possible outcomes to determine the next move. So it does indeed use both search and learning. Regardless, the author's point is that computation is a better way of finding and exploiting patterns/strategies than our own intuitions. The distinction between search and learning is not the important one here.
- cubefox 3y ago
  In hindsight computation wasn't the important thing though. A lot of things require a lot of computation that aren't intelligent or don't scale well, like Deep Blue. The important breakthrough in AI was learning ("machine learning").
  - laughingman2 3y ago
    Search/Reasoning/Inference time compute, however you phrase it is still essential. You need search to improve upon learning to work in novel situations.
    - cubefox 3y ago
      Humans do very little "search", as we can see in games like Go. Which suggests it isn't essential for AI either.
- milesvp 3y ago
  There was an important step prior to alpha go. At the time the combinatorics were in favor of Go. But someone had the bright idea to do a probabalistic search of the space. The key idea was to play a ton of random games and rate each position based what percentage that spot was included in winning games. This blew away all other go ai at the time. Sadly this was about the time I stopped having time to follow the space, so I’m not sure how this idea was further incorporated in Go AI. But it was truly a revolutionary idea at the time

cs702 3y ago

We train deep learning models with SGD, which is in fact a form of search -- in a high-dimensional parameter space. The purpose of SGD is to find parameter values that minimize a training loss.

spmurrayzzz 3y ago
I was thinking along similar lines, it does smell like search to me at its core. But do you think there is a meaningful differentiation for something more nuanced like AdamW? Does the latter fall into the "brute force search" category too though it tends to converge faster (and arguably more optimally than SGD per Jeremy Howard's observations)?

brresnic123 3y ago

SGD is a method of learning from examples (mapping X -> y). RL is a method of search (maximizing reward signal in a potentially open-ended environment, based on feedback on the actions that a model takes). Go was solved by combining learning and search (e.g. narrowing the search space with learned, educated guesses). Pretrained dense GPTs don't search in any conventional way. However, when these GPTs are fine-tuned using RL, an aspect of search is reintroduced. One the most interesting directions labs are pursuing to improve on today's best LLMs is to fine-tune them with search (RL) after a learning-based (next-token prediction) pre-training.

cubefox 3y ago
Yes, AlphaGo does use search, but classifying RL as search seems to be stretching the term.

TacticalCoder 3y ago

However the ultimate optimal game of chess is still not known/solved though (in the end it's either a win for white, for black or a draw) and brute-force is alive and well: every possible position with seven pieces on board has been solved by brute-force and the endgame is now only one lookup in a lookup table when there are only seven pieces left on board. I think they're currently solving it for eight pieces. So it's learning but then brute-force for the end game.

gradascent 3y ago

If I remember correctly, the algorithm in Alpha Go used a combination of reinforcement learning and searching the space of moves and possible outcomes to determine the next move. So it does indeed use both search and learning. Regardless, the author's point is that computation is a better way of finding and exploiting patterns/strategies than our own intuitions. The distinction between search and learning is not the important one here.

cubefox 3y ago
In hindsight computation wasn't the important thing though. A lot of things require a lot of computation that aren't intelligent or don't scale well, like Deep Blue. The important breakthrough in AI was learning ("machine learning").
- laughingman2 3y ago
  Search/Reasoning/Inference time compute, however you phrase it is still essential. You need search to improve upon learning to work in novel situations.
  - cubefox 3y ago
    Humans do very little "search", as we can see in games like Go. Which suggests it isn't essential for AI either.
milesvp 3y ago
There was an important step prior to alpha go. At the time the combinatorics were in favor of Go. But someone had the bright idea to do a probabalistic search of the space. The key idea was to play a ton of random games and rate each position based what percentage that spot was included in winning games. This blew away all other go ai at the time. Sadly this was about the time I stopped having time to follow the space, so I’m not sure how this idea was further incorporated in Go AI. But it was truly a revolutionary idea at the time