Recommended Readings in AI - a list by Russell and Norvig

Contributions to AI in the form of automated mathematicians is a descendant of Axiomated Set Theory and the desire to automate mathematics in the form of rigorous mechanical proofs. From Robin Milner we have the invention of ML whose actual purpose was as a scripting language to aid in the creation of Automated Proofs [1]! We also have contributions from AutoMath [2] which had a lot of modern cutting edge techniques such as dependent types in the late 1960s. All in all the original goal of automatic mathematics and reasoning proved impractical but the tools needed for their development have proven anything but.

Then there is Lisp. Lisp offered to both functional and object oriented techniques. Lisp was inspired by the lambda calculus which was also an offshoot of the whole mechanize maths movement. It was invented by John McCarthy - whose interest was in the old AI notion of symbolic computing - as a turing complete way of representing algorithms. A very old language its influence on all subsequent history is undeniable. From Lisp we see that: "Garbage collection was invented by John McCarthy around 1959 to solve problems in Lisp" [3]. We also notice that the AI researchers had concepts of object orientation in the early 60s [4] and that the later mixins and multiple inheritance had a root in Lisp. The development of multiple inheritance was also motivated by the needs of the old symbolic reasoning researchers.

As for Walmart? Walmart is a very big user of optimization theory and logistics. Walmart and its ilk also use Data Mining and Rule Learning stuff. And optimization is a lot more important than efficiently routing trucks: OR people are actually laying the foundation of AI and are seeing a lot of their work rediscovered. OR people also contributed dynamics programming for example. This is what I mention in another post about improving synergy between all these very related silos. These topics are essentially subsets of a more general theory that will be pivotal to AI.

I personally think optimization is a very important part of our universe. In a way the principle of Least Action is doing some kind of optimization. I feel that people working in machine learning, in particular the bayesian inference and graphical models part of AI are actually doing a subset of quantum mechanics. Vice versa these techniques will likely prove pivotal in programming quantum systems.

[1] http://en.wikipedia.org/wiki/Robin_Milner#Contributions

[2] http://en.wikipedia.org/wiki/Automath

[3] http://en.wikipedia.org/wiki/Garbage_collection_(computer_sc...

[4] http://en.wikipedia.org/wiki/Object-oriented_programming#His...

1. http://www-math.mit.edu/cse/

But Based on my readings genetic algorithms are more known to be susceptible to local minima, while simulated annealing in theory is a global method.

---

As for genetic algorithms - for optimization I prefer Differential Evolution. For Exploration maybe genetic algorithms are more fruitfull although I think Genetic programming and Learning Classifier Systems be slept on. Speaking of slept on - another under appreciated but much more used method is stochastic gradient descent. Global optimums might be overrated.

The terms "search" and "optimization" are often conflated, mostly because "search" was used by two different communities early on to mean two different things back in the 1970s. You still see echoes of it in the optimization community, particularly in single-solution techniques like stochastic hillclimbing, or old terms like "beam search".

So here's how I define them. I believe that "search" typically is applied to problems where you have something to search for. A state or point in space which meets a certain criterion. The most common examples of this are state-space search problems, where the path you took to get there matters, and constraint satisfaction search problems, where the path doesn't matter, only the result. It's also applied in simpler fashions: tree search, binary search, etc.

Optimization, on the other hand, applies to problems where you are trying to find a point which is optimal with regard to some criterion. Unlike search, where it's a find-it-or-not proposition, in optimization you do not necessarily expect to find the globally optimal criterion ever, and in fact you don't necessarily even know that one exists (it could just keep going up and up). You're just trying to find the best thing you can given the time and resources you have.

Optimization algorithms are usually more general, and weaker, than search algorithms. Thus you can typically cast a search problem into an optimization problem -- for example, use your heuristic as the optimization criterion -- but optimization algorithms were designed for a more general class of problems and thus are expected to be outperformed by a custom-designed search algorithm (this fact is a general rule of thumb for pretty much everything in optimization, particularly stochastic optimization -- it's a last-ditch approach). Similarly you can use an optimization algorithm to find a decision tree solution: but I'd get smacked around by colleagues in the machine learning community for calling PSO a machine learning algorithm.

So interesting question: is Alpha-Beta Pruning a search algorithm or an optimization algorithm?

At any rate -- Russell and Norvig are entirely muddled about this. They admit (p. 121) exactly what I state above, yet go on to lump the two together without any further explanation, and then make the strange case that local search is global if it is "complete" -- a very logician way of stating it, but not a term in the field so far as I know.

Also, Craft is organized a bit strangely -- IIRC, it was originally written as a response to a specific Prolog implementation's documentation.