AIMA Python Algorithms

Posted on | In ,

AIMA is short for the book “Artificial Intelligence: A Modern Approach” which is written by Stuart Russell and Peter Norvig. Currently they are working on the 4th edition which will be published soon. In the new edition, there are many major changes to the book structure and machine learning algorithms. I worked in the open-source organization AIMA to implement the new and modified algorithms in Python. The algorithms in the book can fall into two categories: classic machine learning algorithms and deep learning algorithms.The initial proposal listed the plan of implementation of main algorithms in detail.

Proposal of AIMA Python project

Abstract

Currently AIMA is transferring from the 3rd to the 4th edition, thus some algorithms are removed, updated or added. To support the release of newest edition of AIMA, some of the original Python instances need to be altered to fit the changes in book. Currently the repo aima-Python records all the algorithms in the 3rd edition but not updated for the 4th yet. What needs to be done is to check differences between the third edition and fourth edition pseudocode, provide python examples, test cases, demos and documents for the altered parts. If possible, some visualization methods such as animation will make the algorithms clearer.

Deliverables

Below I tried to structure the potential contributions to AIMA project following the steps in timeline:

  • Document the differences of algorithms in 3rd and 4th edition in README.md under repo aima-pesudocode.

  • Update Python algorithms and data structures of 3rd version following chapter sequence: agent.py, search.py, games.py, csp.py, logic.py, planning.py, probability.py, mdp.py, learning.py ,knowledge.py , rl.py and nlp.py.

  • Create test cases for updated algorithms under folder tests.

  • Create documentations for each algorithm. Create demo cases under gui.

I tried to list above items in a logical, chronological order, but this is not always true about the test phase, as test cases need to be added incrementally through the whole development phase of CSoC project.

Timeline

During the implementation period, I plan to spend around 40 hours per week on the project. Besides the community bounding activities, during which I will get familiar with the community itself as well as the work flow and development tools, I will also be studying the previous code and algorithms, and explore better ways for algorithm visualization.

Below is the proposed schedule based on my percepted workload over each section:

  • Week1:
    • Record the differences of algorithms and data structures in the 3rd and 4th edition AIMA.
    • Explore the 3rd version source code of algorithms, tests and demos. Get aware of their structures, references and realations.
  • Week2:
    • Update agent algorithms and data structures in AIMA’s chapter 2: investigate the differences in agent descriptions in books, change the corresponding part about agent and environment in agent.py.
    • Update tests of agent.py under tests.
  • Week3:
    • Update search algorithms in AIMA’s chapter 3, including MODEL-BASED-REFLEX_AGENT, BEST-FIRST-SEARCh, BREADTH-FIRST-SEARCH, DEPTH-LIMITED-SEARCH, BIDIRECTIONAL-SEARCH, RECURSIVE-BEST-FIRST-SEARCH and etc. Update the search algorithms in search.py.
    • Update test cases of search.py in tests.
  • Week4:
    • Update advanced search algorithms in chapter 4 : GENETIC-ALGORITHM in search.py. Update game search algorithms in chapter 5 : MONTE-CARLO-TREE-SEARCH in game.py.
    • Update test case of search.py and game.py.
  • Week5:
    • Update csp problem algorithms in chapter 6, local agent algorithms in chapter 7 and inference algorithms in first order logic in chapter 9.
    • Update test cases for above algorithms.
  • Week6:
    • Update planning algorithms in chapter 9, 10 & 11.
    • Update test cases for these algorithms.
  • Week7:
    • Update probabilities algorithms in chapter 13, 14, 15 and 16. Big changes are about GIBBS-ASK.
    • Update test cases for altered algorithms.
  • Week8:
  • Week9:
    • Update advanced learning algorithms in the following part of the book. Update test cases.
    • Recheck all scheduled algorithm changes are implemented. Record the missed algorithm changes, and schedule for them.
  • Week10&11:
    • Test on all GUI demo cases. Make sure all GUI’s functionalities are normal.
    • Run previous tests on all unchanged algorithms, make sure all scripts’ functions are normal.

Implementation

During the development phase, all code will be implemented with Python. Certain tests and demos will also be developed with jupyter notebook in order to show results step by step. All generated code and test will be applying the same naming convention as in 3rd edition. In our development of 4th edition algorithms, we will try to migrate the 3rd edition’s class hierarchy because the main structure of this course is not changed. Then we will alter the changed parts and fit our new algorithms in.

For each single algorithm, there are several phases to implement: 1. Convert pesudocode to python code. Guarantee its performace is the same as demonstrated in the book. 2. Implement thorough test cases for each newly developed algorithm, make sure the test cases are reasonable and complete. 3. Debug to make sure each algorithm can pass its tests with acceptable performance. 4. Decide the visualization method for each algorithm: jupyter notebook, GUI or no need for visualization.

Real Implementation

In the real implementation phase, most of the time the work sticks to the original plan. Besides the algorithms, I also changed some of the util functions with applying numpy to make the code simpler. I also included a module of R-CNN in order to create a simple demonstration of R-CNN. Besides the algorithms, I also provided demostration cases for each of the algorithm.