Teaching a Bayesian spam filter to play chess (2005) | Hacker News Reader

Teaching a Bayesian spam filter to play chess (2005)

dbacl.sourceforge.net

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.

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 fast and scalable GPU implementations of GAs? (I'm not trying to trick you, genuinely curious).

I think one problem, making GAs fitness functions. If the ambient fitness function has a lot of data-dependent branching, SIMD will be slow. Moreover GAs have two phases: measuring fitness and mutation/crossing over to produce the next generation. Is the mutation/crossover phase SIMD friendly? Typically, it involves randomness ...

In contrast, neural net training Multiply) which is an incredibly predictable workload -- almost no data dependent branching. So none of the things that make processors slow and complicated (caches, prefetching, branch prediction, reservation station, scheduler ...) is needed: instead you can just stream the data from main memory directly into the matrix multiplier (tensor core). This means you can use the available transistors (and energy) much more efficiently.

As far as I am aware, GAs uniform and predictable a workload as GeMM, which I believe is why GAs don't usually get run on a GPU (not to mention more specialised hardware like TPUs).

   run each machine almost entirely independently.

I am not sure how this works with mutation/crossover. faster and more efficient. Why?

Regarding neuro-evolution and hyperparameter, here 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

This is the canonical article about the heart of the problem that I re-share periodically:

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

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.

> 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.

> 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”.

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

[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.

I fear this is just a debate over semantics, which is always an unhappy debate. In my opinion “finding the square root” isn’t a “problem”, perhaps precisely because it doesn’t involve search. Something like “how can I determine the side length of this square I needed 67 sq feet of tile to cover” is a problem: I could use your algorithm on paper, I could guess based on prior experience, I could measure, I could estimate, I could use a calculator, etc. Which of those I pick is a search based on the constraints at hand (how much time do I have, what resources do I have, how precise an answer do I need, etc), and the act of considering many approaches to the problem and proceeding with some based on the constraints at hand is evolution.

Again, this is all semantics imo, so not really a debate so much as sharing world views. Which perhaps is what debate is. Hm.

Oh man, reading what you wrote out, it just occurred to me that learning is actually caching.

We already have a multitude of machines that can solve any problem: the global economy, corporations, capitalism (Darwinian evolution casted as an economic model), organizations, our brains, etc.

So take an existing model that works, convert it to code made up of the business logic and tests that we write every day, and start replacing the manual portions with algorithms (automate them). The "work" of learning to solve a problem is the inverse of the solution being taught. But once you know the solution, cache it and use it.

I'm curious what the smallest fully automated model would look like. We can imagine a corporation where everyone has been replaced by a virtual agent running in code. Or a car where the driver is replaced by chips or (gasp) the cloud.

But how about a program running on a source code repo that can incorporate new code as long as all of its current unit tests pass. At first, people around the world would write the code. But eventually, more and more of the subrepos would be cached copies of other working solutions. Basically just keep doing that until it passes the Turing test (which I realize is just passé by today's standards, look at online political debate with troll bots). We know that the compressed solution should be smaller than the 6 billion base pairs of DNA. It just doesn't seem like that hard of a problem. Except I guess it is:

https://github.com/opencog/opencog

> “finding the square root” isn’t a “problem”, perhaps precisely because it doesn’t involve search

Well, it can be solved by search (as I've defined it). It just happens that it doesn't have to be.

In my own life, I've come to view the search for meaning as the fundamental goal of consciousness. My good friend calls this the "reconnection" and I've often wondered if connectedness could be used as the primary incentive for a general machine learning algorithm.

You can look at a genetic algorithm as a neighbourhood search, where the neighbourhood is defined by whatever you can reach via 1 mutation. crossover can be seen as a way to avoid being stuck near a local optimum.

That's not quite fair to evolution: crossover is vastly more important to real world evolution than mutation (even as mutation is critical to create the raw material that's crossed).

I don't think I ever have seen a GA application that made prior use of crossover, because most use genotype->phenotype codings that can't even in theory make it useful. That's where anyone young starting on this road should start.

viruses disagree about crossover.

Ya I was just thinking that the simplest learning algorithm would actually be something simpler like "solving systems of equations as a matrix" (I'm feeling lucky Google result):

https://www.mathsisfun.com/algebra/systems-linear-equations-...

So you enter your inputs and outputs in a big table and solve by brute force to get an algorithm. It might not be an interesting one, or one useful beyond that one problem, but it's something.

There are also some graphical techniques for truth tables (boolean-value matrices):

https://www.allaboutcircuits.com/textbook/digital/chpt-8/log...

And this is kinda sorta loosely related to classification algorithms like k-means clustering, at least that's how my brain associates them:

https://en.wikipedia.org/wiki/K-means_clustering

Anyway, I view neural networks as a way of solving a huge matrix with gradient descent (hill climbing) as the optimization technique. It fundamentally will always struggle with the local minimum (maximum) problem just like in calculus.

Whereas genetic algorithms bust out of that mental trap via random sampling. I'm sure there's a proof out there somewhere that says they can solve any problem, given enough time, which is why I view them as the basis of learning. As I write this with my neural net hmmm..

To me, the only way forward is at the meta level, quantum computing or similar (as you very astutely pointed out).

An analogy for this might be that the vast majority of us do our daily work on the imperative side of programming (Turing machines) without realizing that they can be made equivalent to the vastly simpler functional side of programming (Lambda calculus) that solved most of the problems we face today 50+ years ago.

The state of the art when I first starting following this in the late 90s was optimizing neural nets evolved via genetic algorithms. I never heard anything else about it, but keep in mind that shortly after that, HP bought Compaq, private industry research spending cratered, native mobile app programming buried the innovation of declarative and data-driven programming that the web popularized, single page apps made web development untenable, video cards ended CPU innovation, and wealth inequality directed us all into nursing CRUD apps back from the brink of death instead of making contributions to open source projects that could fundamentally advance the human condition.

The problems are so widespread and entrenched now that if we can even break past a few of them, then I see rapid and transformative change potentially happening very quickly. It's like how the forces that be work to make sure that nobody gets UBI, because we can't have the plebeians enjoying the same return on investment that the wealthy take for granted. No, everyone must be kept poor and struggling or else they might just find the time to automate themselves out of a job.

Edit: sorry I just realized that I contradicted you on search. I was trying to make the point that if you could fit the whole search space into a matrix, then we could just solve it. Since that's not possible for most real-world problems, then yes I agree with you that search is actually the fundamental problem-solving algorithm.

As a GPU programmer and someone who’s experimented with genetic algorithms, I believe you are misunderstanding the concepts involved.

Genetic algorithms are in fact much better suited to SIMD than MISD, as you want to run the same evaluation on a population of individuals with different attributes, and they scale perfectly well with current hardware.

Take a toy example, you could fit a small neural network in a single kernel, and there you would obviously run the same inference algorithm with each neural network having different weights and biases.

That won’t work for large networks, but in general there you’d want to scale by using multiple GPUs, and there genetic algorithms scale even better as you can run each machine almost entirely independently.

An interesting question is: why are we not seeing as they are understood today (maybe there is a better way), is the freewheeling, unconstrained nature of GA is essentially GeMM (General Matrix have not, so far, been reduced to as simple Learning happens by 'throwing away' unpromising search avenues (genes). So if different machines do not synchronise their populations, they don't learn from each other. Synchronisation OTOH is very slow.

Evolution strategies (essentially the same as genetic algorithms) have been successfully applied to GPU-training of neural networks and parallelise very well. Look at various papers on neuro-evolution (e.g. the ones from the now defunct Uber AI Labs).

A simple, very inefficient implementation would be: do inference on n randomly initialised neural networks, calculate loss, select the m best performing and copy them to fill all n spots, add gaussian noise to each weight and bias of every individual, repeat. More efficient mutation and selection strategies exist, but the principle is similar and parallelisation on GPUs is trivial and actually easier than current approaches (atomic operations e.g. compare-and-swap can be used to avoid going back to the CPU for selection).

I believe the real reason for neuro-evolution's unpopularity is that for most problems, gradient descent is just faster and more efficient.

What would be interesting might be to combine both approaches, using evolution strategies on hyperparameter search, although I haven't read the literature on that front.

   gradient descent is the question becomes why would the stochastic nature of GAs (and ESs) be particularly better than e.g. brute force search?

In their basic form, genetic algorithms essentially approximate gradient descent by randomly sampling the search space to find the direction of steepest descent (similar to a finite differences method). If the loss function is differentiable, you are essentially wasting computing resources on calculating paths that are known not to be optimal, hence, why not apply gradient descent directly instead of a slower approximation?Brute force search would be even more inefficient, genetic algorithms at least throw away unpromising directions.

Oh hmm, I've always approached it from the other direction, imagining a population of creatures with different genes interacting with the same environment. Like 10,000 very different shader programs (mutations of each other) running simultaneously, but sharing the same texture/environment/data. Analogous to each creature being its own process on its own CPU, ideally.But I never saw how such a setup could be run on a video card. Admittedly, I got really disheartened about this stuff a decade ago when OpenCL and CUDA came out and seemed to be made for running one program on a bunch of different data. And complicated. Do you or does anyone know if things have changed?
The closest I've come to this lately is Unity shaders, but I vaguely remember there is a way to run Julia on GPU? Like if each different shader program is run as a layer in a rendering pass. Except rather than 8 or 16 layers, can modern GPUs run more on the order of 100+ layers? What's the limit?

Stumbled onto a few crash course items that helped get me a bit up to speed on this:https://www.cl.cam.ac.uk/teaching/1819/AdvGraphIP/03_OpenCL....
https://stackoverflow.com/a/27250785/539149
https://community.amd.com/t5/opencl/parallel-execution-of-ke...
https://www.intel.com/content/www/us/en/programmable/documen...
It's kind of looking like it's not really feasible to run more than a handful of OpenCL kernels simultaneously, certainly not 10,000. Maybe I'm looking at it the wrong way?
Conceptually, I want to run a C-style "Hello, World" program with a hundred random instructions after it, hardcoded into 10,000 variations. Then compile and run them simultaneously, passing them all the same data. I mean even being able to do this with 16 different kernels to start with would be awesome!

Ah, I think you’re talking about applying genetic algorithms to self modifying code.In that case you’d want to run the self-modifying code in a VM; if you’re just putting random instructions after another, you’ll most likely just have segfaults, invalid memory addressing, and worse.  With a simple VM, you could fit it in a GPU kernel (keep in mind the language limitations) and then you’ll have no issues launching your huge batch in parallel.
I don’t know if genetic program generation has any useful applications however. Personally I am more interested in applying genetic algorithms to machine learning, i.e. neuroevolution. A few examples include NEAT and Uber’s reinforcement learning research.

Ya the method I want to try is transpiling Lisp to C and then running that on GPU (so no segfaults). As far as I can tell, the problem is that I can only run 10,000 copies of the same shader, not 10,000 different shaders at once on the same data.This is the closest I can come to a "proof" that today's hardware is on the wrong branch of the search space of possible hardwares.
I'm hoping to be proven wrong though, and that someone knows a way to run say 16 or more different shaders simultaneously on a GPU. Maybe there is a way to encode the variations in sub-shaders and run those at the same time or something?
Edit: a few more links about running concurrent GPU kernels:
https://stackoverflow.com/a/53341888/539149
https://stackoverflow.com/a/52978372/539149
https://community.amd.com/t5/opencl/opencl-concurrent-kernel...
https://community.khronos.org/t/concurrents-kernels-in-openc...
http://ecosimulation.com/chrisgregg/Publications/Fine-Graine...
http://docs.potionmagic.eu/per.pdf
Unfortunately, concurrent kernels execution is only possible with CUDA on NVIDIA graphics cards. For other cards, OpenCL does not offer this functionality.
Looks like it may only be possible on NVIDIA, according to the last link. Since this was the first thing I wanted to do with OpenCL, it doesn't bode well for the standard or AMD. As a software developer, I see this issue a lot. What happened is, their public interface is too thick so doesn't reflect the actual capabilities of the hardware. I hit this with OpenGL too way back before ES2 and shaders were mainstream. I just wanted direct access to some of the matrix hardware math but couldn't get to it.
I'd vote to scrap current GPU implementations and move to a pure 2D or 3D grid of compute units (a bit like AWS EC2) running something like Docker. Then write OpenGL, OpenCL, Vulkan, Metal and the rest as niche libraries implementing use cases above the runtime. That would give us bare metal access to get real work done with languages like C, Rust, MATLAB, Julia, Erlang, Go, etc and finally drop the distinction between CPU and GPU.

Yea, Julia compiles natively to GPUs. See here: https://juliagpu.org/

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

Ahead of its time.

Title needs an edit.

To wit, "to filter" -> "filter to".

Yeah, sorry, I can't edit it.

Fixed. Thanks!

Reply on news.ycombinator.com