6 ms·

Teaching a Bayesian spam filter to play chess (2005)

uniformlyrandom 6y ago
That was fun to read, thank you. There are obvious limitation to the approach, as stated by the author, but it was an interesting experiment.
djmips 6y ago
Title needs an edit.
- mgsouth 6y ago
  To wit, "to filter" -> "filter to".
- ignoranceprior 6y ago
  Yeah, sorry, I can't edit it.
- dang 6y ago
  Fixed. Thanks!
zackmorris 6y ago
I realized 20 years ago after learning about genetic algorithms (GAs) that all AI and machine learning approaches can be used interchangeably to solve any problem, and that the fundamental approach to problem-solving is evolution itself. The differences only arise when we examine various models from a compute-bound perspective because we ruled out the O(n^2+) embarrassingly simple/parallel algorithms that actually work. Unfortunately genetic algorithms can't run on video cards efficiently (because shaders are SIMD instead of MIMD), so IMHO most of the "progress" in computing power the last 20 years, even all the way up to stuff as advanced as TensorFlow on GPUs, has mostly been hand waving. The problem is that shaders run the same code with different data (that's the SIMD part), but GAs run different code on each CPU/thread/actor instance (which is MIMD or even MISD). But, maybe there are ways. This looks promising: https://people.scs.carleton.ca/~dmckenne/5704/Papers/14.pdf https://people.scs.carleton.ca/~dmckenne/5704/Papers/14.pdf This is the canonical article about the heart of the problem that I re-share periodically: http://aggregate.org/MOG/ http://aggregate.org/MOG/ And unbelievably, it never occurred to me why MISD is so important and overlooked, but this is about the closest thing to a eureka moment that I've had in a long time: https://en.wikipedia.org/wiki/MISD https://en.wikipedia.org/wiki/MISD A "theory" about why progress in AI is so sluggish is that we can't scale Docker containers to 1000+ on our own computers with video cards. Until we can do that, progress is effectively at a standstill. And that visceral reaction of "oh that's a terrible idea for XYZ reason" represents the real work that needs to be done to advance computing power. It also captures the sense of why computers today feel like they are running many thousands of times slower than they should be for the number of transistors they have. TL;DR: I'm saying that with this computer, you could write a short shell script that uses a Bayesian spam filter (or anything else) and it would compete with the best algorithms we have by sheer brute force. But more importantly, we could iterate on our solutions faster (because they're so much simpler than neural nets so more people could be involved) and quickly discover emergent behavior that guides us towards a formula for artificial general intelligence (AGI). There's no mystery here, to me, it's just plug and chug and thinking about the heart of the problem from a different perspective.
- lisper 6y ago
  > the fundamental approach to problem-solving is evolution itself Not quite. The fundamental approach to problem solving is search, and evolution is a kind of search. It's not a particularly efficient search algorithm, but it has the interesting property that it is able to invent new search algorithms that are more efficient than it is. We have a pretty good handle on search. What we do not yet have is the foggiest clue about this sort of "meta-search", the search for new kinds of searching mechanisms. We've invented/discovered one: the Turing machine, and everything we've done since then has been a riff off that one idea. Even so called "neural networks" are really just a fairly uninteresting algorithm that happens to bear a superficial resemblance to our brains and happens to produce some interesting results. But, as you very correctly observe, they are nowhere near the Right Answer. UPDATE: OK, quantum computers probably count as a mechanism distinct from TMs. But I'll give long odds against QC turning out to be the key to understanding how our brains work, Roger Penrose notwithstanding.
  - jakear 6y ago
    > The fundamental approach to problem solving is search, and evolution is a kind of search Ehh, problem-solving is search (searching for an answer), so it this statement doesn’t really make sense except as a tautology. I agree that evolution is a core means by which problems are solved, and perhaps the core means. Humans are incredibly good searchers because of the evolution we’ve undergone, to the extent we’ve started evolving our own searchers to enhance our problem solving ability. I’m not sure if we can reasonably say that those searchers have started to evolve their own searchers, but it’s safe to say it will happen soon. The big question to me is what beings evolved us (the universe/whatever the embedding we call reality really is), and what problem were we meant to solve? This is basically unknowable as far as I can tell, and the foundation of all “religion”.
    - deleted 6y ago
      [deleted]
    - lisper 6y ago
      Not all problem solving is search and not all search is problem solving. Some problems can be solved algorithmically with no search (e.g. computing a square root) and search can obviously be done in service of something other than problem-solving (unless you take the meaning of "problem" to be so broad as to apply to just about any activity). I also intended the word "search" to be understood in a narrow technical sense: https://en.wikipedia.org/wiki/Search_algorithm https://en.wikipedia.org/wiki/Search_algorithm [EDIT] Just to clarify, because I just realized that these two statements might seem contradictory: "The fundamental approach to problem solving is search" "Not all problem solving is search" All problem solving can be cast as search, but some problems have heuristics that allow the correct branch of the search space to be chosen the first at every decision point with no backtracking required. The "search" becomes degenerate because no backtracking is ever required. The word "search" is generally reserved to apply only to algorithms that don't have such strong heuristics and do require backtracking.
KingOfCoders 6y ago
Ahead of its time.
dang 6y ago
A thread from 2007: https://news.ycombinator.com/item?id=75422 https://news.ycombinator.com/item?id=75422

That was fun to read, thank you. There are obvious limitation to the approach, as stated by the author, but it was an interesting experiment.

djmips 6y ago

Title needs an edit.

mgsouth 6y ago
To wit, "to filter" -> "filter to".
ignoranceprior 6y ago
Yeah, sorry, I can't edit it.
dang 6y ago
Fixed. Thanks!

zackmorris 6y ago

I realized 20 years ago after learning about genetic algorithms (GAs) that all AI and machine learning approaches can be used interchangeably to solve any problem, and that the fundamental approach to problem-solving is evolution itself. The differences only arise when we examine various models from a compute-bound perspective because we ruled out the O(n^2+) embarrassingly simple/parallel algorithms that actually work. Unfortunately genetic algorithms can't run on video cards efficiently (because shaders are SIMD instead of MIMD), so IMHO most of the "progress" in computing power the last 20 years, even all the way up to stuff as advanced as TensorFlow on GPUs, has mostly been hand waving. The problem is that shaders run the same code with different data (that's the SIMD part), but GAs run different code on each CPU/thread/actor instance (which is MIMD or even MISD). But, maybe there are ways. This looks promising: https://people.scs.carleton.ca/~dmckenne/5704/Papers/14.pdf https://people.scs.carleton.ca/~dmckenne/5704/Papers/14.pdf This is the canonical article about the heart of the problem that I re-share periodically: http://aggregate.org/MOG/ http://aggregate.org/MOG/ And unbelievably, it never occurred to me why MISD is so important and overlooked, but this is about the closest thing to a eureka moment that I've had in a long time: https://en.wikipedia.org/wiki/MISD https://en.wikipedia.org/wiki/MISD A "theory" about why progress in AI is so sluggish is that we can't scale Docker containers to 1000+ on our own computers with video cards. Until we can do that, progress is effectively at a standstill. And that visceral reaction of "oh that's a terrible idea for XYZ reason" represents the real work that needs to be done to advance computing power. It also captures the sense of why computers today feel like they are running many thousands of times slower than they should be for the number of transistors they have. TL;DR: I'm saying that with this computer, you could write a short shell script that uses a Bayesian spam filter (or anything else) and it would compete with the best algorithms we have by sheer brute force. But more importantly, we could iterate on our solutions faster (because they're so much simpler than neural nets so more people could be involved) and quickly discover emergent behavior that guides us towards a formula for artificial general intelligence (AGI). There's no mystery here, to me, it's just plug and chug and thinking about the heart of the problem from a different perspective.

lisper 6y ago
> the fundamental approach to problem-solving is evolution itself Not quite. The fundamental approach to problem solving is search, and evolution is a kind of search. It's not a particularly efficient search algorithm, but it has the interesting property that it is able to invent new search algorithms that are more efficient than it is. We have a pretty good handle on search. What we do not yet have is the foggiest clue about this sort of "meta-search", the search for new kinds of searching mechanisms. We've invented/discovered one: the Turing machine, and everything we've done since then has been a riff off that one idea. Even so called "neural networks" are really just a fairly uninteresting algorithm that happens to bear a superficial resemblance to our brains and happens to produce some interesting results. But, as you very correctly observe, they are nowhere near the Right Answer. UPDATE: OK, quantum computers probably count as a mechanism distinct from TMs. But I'll give long odds against QC turning out to be the key to understanding how our brains work, Roger Penrose notwithstanding.
- jakear 6y ago
  > The fundamental approach to problem solving is search, and evolution is a kind of search Ehh, problem-solving is search (searching for an answer), so it this statement doesn’t really make sense except as a tautology. I agree that evolution is a core means by which problems are solved, and perhaps the core means. Humans are incredibly good searchers because of the evolution we’ve undergone, to the extent we’ve started evolving our own searchers to enhance our problem solving ability. I’m not sure if we can reasonably say that those searchers have started to evolve their own searchers, but it’s safe to say it will happen soon. The big question to me is what beings evolved us (the universe/whatever the embedding we call reality really is), and what problem were we meant to solve? This is basically unknowable as far as I can tell, and the foundation of all “religion”.
  - deleted 6y ago
    [deleted]
  - lisper 6y ago
    Not all problem solving is search and not all search is problem solving. Some problems can be solved algorithmically with no search (e.g. computing a square root) and search can obviously be done in service of something other than problem-solving (unless you take the meaning of "problem" to be so broad as to apply to just about any activity). I also intended the word "search" to be understood in a narrow technical sense: https://en.wikipedia.org/wiki/Search_algorithm https://en.wikipedia.org/wiki/Search_algorithm [EDIT] Just to clarify, because I just realized that these two statements might seem contradictory: "The fundamental approach to problem solving is search" "Not all problem solving is search" All problem solving can be cast as search, but some problems have heuristics that allow the correct branch of the search space to be chosen the first at every decision point with no backtracking required. The "search" becomes degenerate because no backtracking is ever required. The word "search" is generally reserved to apply only to algorithms that don't have such strong heuristics and do require backtracking.

KingOfCoders 6y ago

Ahead of its time.

dang 6y ago

A thread from 2007: https://news.ycombinator.com/item?id=75422 https://news.ycombinator.com/item?id=75422