One AI Algorithm

All Programmers Should Know

https://OneAIAlgorithm-confoo.azurewebsites.net/

Barry S. Stahl - @bsstahl - http://www.CognitiveInheritance.com

About Me

I think it is noteworthy that I am the type of person who has both favorite physicists and favorite mathematicians - @bsstahl 16 Apr 2017

Other notables: Niels Bohr, Galileo Galilei, Michael Faraday, Blaise Pascal, Johann Gauss, Grace Hopper, Stephen Hawking, Marvin Minsky, Daphne Koller, Benoit Mandelbrot

Some OSS Projects I Run

GiveCamp

International Headquarters: http://givecamp.org

A weekend event where software creators come together to create great software for some amazing local charities

Artificial Intelligence

A Computational System that Behaves Rationally

Rationality

A system is rational if it attempts to make the best possible decision​ based on the best available understanding of the problem (model)​ and of the state of the domain (data)​.

Intelligent Agents

Knapsack Problems

Memoization

Memoization

Memoization

Memoization

Memoization

Memoization

Memoization

Memoization

Memoization

Memoization

Memoization

Memoization

Memoization

Memoization

Memoization

Memoization

Memoization

Memoization

Memoization

Memoization

Memoization

Memoization

Memoization

Dynamic Programming

A mathematical optimization technique

• Best for solving problems that can be described recursively.​
• Breaks the problem into smaller sub-problems​
• Solves each small problem only once​
• Guarantees an optimal solution​

Optimization Problems

• Find the best values for a set of decision variables that​
  • Satisfies all constraints
  • Maximizes the features we want​
  • Minimizes the features we don’t want

Simple Example - Chutes and Ladders

Chutes and Ladders - Greedy Algorithm

Start at the 1st space on the board​ While we haven't reached the last space​ Add the space to the current path​ If the current space has a ladder​ Add the end of the ladder to the path​ Make that space the current space​ Move to the next space on the board​ Return the completed path through the board

Dynamic Programming - Step 1

DetermineDistance(s,d) Call DetermineDistance(space[0], 0) If shorter​ than previously found Set DistanceFromStart property If this space starts a chute or ladder​ DetermineDistance(endOfNavigation, distanceFromStart+1​) If not at the end of board​ DetermineDistance(nextSpace, distanceFromStart+1) Return all spaces with their DistanceFromStart property populated

Dynamic Programming - Step 2

Start at the last space on the board​ While we are still on the board​ Add the current space to the path​ Set the current space to a space that is a neighbor of the current space and whose DistanceFromStart is space.DistanceFromStart-1​ Reverse the direction of the path​

Memoization

Shortest Path

Shortest Path

Shortest Path

Shortest Path

Shortest Path

Shortest Path

Shortest Path

Shortest Path

Shortest Path

Shortest Path

Shortest Path

Shortest Path

Summary - Dynamic Programming

• Populate the cache​
  • Simple calculations​
  • Build from the ground-up​
• Use the cached data to determine the answer(s)​
  • Work backwards through the cache​
• Guaranteed Optimality​
  • A fully populated cache means all options are explored​
  • Works in any number of dimensions​
• Works with any graph (nodes & edges)​
  • Works best when​
    • Problems can be described recursively​
    • 1 or more axis are limited in scope

Resources

• This Slide Deck
  • https://OneAIAlgorithm-ConFoo.azurewebsites.net/
• More Information​
  • Dynamic Programming on Wikipedia
  • Optimization - Coursera Course
• Practice Examples​
  • Clemson University
• My Blog​
  • Cognitive Inheritance
• Complete Code Sample​
  • DPDemo on GitHub