Mark Humphrys - Teaching - CA318

Advanced Algorithms and AI Search

---

Course Descriptor

• CA318 - Advanced Algorithms and AI Search (and here)

• This module is 75 exam, 25 project.

• Past exam papers
  • It was a new module in 2012.
  • Exam paper 2012
  • Repeat paper 2012
  • Somewhat relevant: Past papers from CA300 and CA622.

• This year:
  Answer all 10 multiple-choice questions. (3 marks each.) Total 30 marks.
  Answer 2 long questions out of 3. (30 marks each.) Total 60 marks.
  Answer the bonus question. (10 marks.)

• email lists
  • CA318 email list

---

How to contact me

See How to contact me.

---

Notes

My notes contain many hyperlinks to background material. Some students get confused about what is the core course. The core course is anything that is linked to directly on this front page. All other links are just background material.

1. Introduction to AI
   1. Introduction to AI
   2. Survey of AI

   3. Continuum of Autonomy
   4. History of AI
      • Reading

   
   

2. Reference
   1. AI Links
      • AI and games
   2. Robotics Links

   3. Computational Evolution - Reference
   4. Machine Learning - Reference

   
   

3. Search and Learning
   1. Search
      • Local and Global Optima

   2. Maximising a function
   3. Chaotic functions
   4. Chaos Theory demo

   5. Machine Learning
      • Representing a function
      • Sample applications of Neural Networks
      • Distance in n-dimensions
      • The Neural Network data structure

   
   

4. State space Search
   1. State space Search
   2. Heuristic Search
   3. More Heuristic Search
   4. Adversarial Search

   
   

5. Machine Evolution
   1. Computational Evolution
      • Introduction to Evolution
      • Definitions
   2. The Genetic Algorithm [HEURISTIC]
      • Encoding the Genotype
      • Fitness - Who reproduces?
   3. Reproduction
      • 2 copies of instructions - Nature's elegant algorithm
      • 50-50 ratio - Further elegance in nature
   4. Boltzmann "soft max" distribution
   5. GAs - Discussion
      • Sample applications of Genetic Algorithms

   6. Advanced Topics in Machine Evolution
      • Speciation (Local mating)

   7. What is Life?
   8. Sample code for Genetic Algorithms
   9. How to make a decision probabilistically
   10. GA Exercise - Adaptive Landscape

   
   

6. Machine Learning - NOT ON COURSE THIS YEAR

   Single-layer Neural Networks Perceptron Learning Rule [SINGLE-LAYER LEARNING RULE] Convergence Proof [EXISTS] Multi-layer Neural Networks Timeline Continuous Output - The sigmoid function Notation [REFERENCE] Back-propagation [MULTI-LAYER LEARNING RULE] No method of finite sampling can guarantee to find the global minimum Convergence Proof [DOES NOT EXIST, HEURISTIC] Designing the Network Designing the Inputs The Back-propagation algorithm [REFERENCE] Infinite weights/thresholds are bad Specialisation Need random, diverse initial w's How does specialisation happen? Sample code for Neural Networks Neural Net Exercise - Binary Encoder Network Neural Net Exercise - X and O recogniser

   
   

   1. Alternatives to Supervised Learning

   
   

7. General AI
   1. Comparison of Neural Net and GA
   2. Continuum of Autonomy
   3. Architectures of Autonomous Agents
      • Reading
   4. Open Issues in AI

   
   

8. Philosophy of AI - NOT ON COURSE THIS YEAR

   Philosophy of AI Reading Philosophy and Future of AI What is Intelligence? What is Consciousness? What is Life?

   
   

9. String searching - NOT ON COURSE THIS YEAR

   String searching Knuth–Morris–Pratt string search algorithm Boyer-Moore string search algorithm

---

Notes on Assignment Notation

I often use   :=   for assignment to distinguish from   =   for equality.

• Assignment
  • Notation
  • Assignment versus Equality
• Equality
  • Usage in mathematics and programming

---

Labs

I will hold one or two hands-on labs for the practical. Dates will be announced.

---

Practical

Practical.
Java.
Do in your own time.

Deadline Wed 12 Dec 2012.

---

Reading

1. Coverage of both the symbolic and the biological approaches to AI in one book:
   • Artificial Intelligence, George F. Luger - Library 006.3.LUG, and Bookshop.
     • 6th edn is good, but my refs are to 5th edn, 2005.
     • Student resources
     • Lecturer resources

2. Neural Networks:
   • Neural Networks - A Systematic Introduction (and here) by Raúl Rojas

   • Neural Computing, Philip D. Wasserman, 1989. - Library 006.3.WAS.
   • Neural Network Architectures: An Introduction, Judith Dayhoff, 1990. - Library 006.3.DAY.
   • An Introduction to Neural Computing, Igor Aleksander and Helen Morton, 2nd edn, 1995. - Library 006.3.ALE.

   • "Learning Internal Representations by Error Propagation", Rumelhart et al, Chapter 8 in Parallel Distributed Processing, Rumelhart and McClelland, 1986. - Library 153.RUM.

3. Genetic Algorithms:
   • Genetic Algorithms in Search, Optimization and Machine Learning, David Goldberg, 1989. - Library 006.31.GOL.

---

Library categories

• 006 - Special computer methods
  • 006.3 - Artificial Intelligence

• 629 - Other branches of engineering
  • 629.8 - Automatic control engineering (robotics)

• 100 - Philosophy and psychology
  • 120 - Epistemology, causation, humankind
    • 128 - Humankind
  • 150 - Psychology
    • 153 - Mental processes and intelligence

---

Morelli course on State space Search

This may help clarify some of the concepts.

• Ralph Morelli
  • State space Search course using Luger's book.
    • Symbolic AI
    • State Space Search
    • Heuristic Search
    • A* Algorithm
    • Minimax and Alpha Beta Pruning

---

Copyright of Luger and Morelli images

1. I use some images from Luger's book in this course.
   These images will be protected by a password I will give out in class.
   Images can be used for class access but not public access on the Web.
   Copyright notice:

   This work is protected by regional copyright laws and is provided solely for the use of instructors in teaching their courses and assessing student learning. Dissemination or sale of any part of this work (including on the Internet) will destroy the integrity of the work and is not permitted. The copyright holder grants permission to instructors who have adopted the textbook accompanying this work to post this material online only if the use of the website is restricted by access codes to students in the instructor's class that is using the textbook and provided the reproduced material bears this copyright notice.

2. I also use some images from Morelli's course in this course. These images are used with the kind permission of Ralph Morelli.

---

This course is hard!

The 2013 exam results show that this course is hard! The practical work in 2013 was great, but the exam was not. I was not happy.

Conclusion: Treat this course as hard. The notes are online, but you need to go to every lecture. You will not understand this course from the notes alone.

2013 exam results summary:

• 0 to 10 percent: 0
• 10 to 20 percent: 2
• 20 to 30 percent: 9
• 30 to 40 percent: 10
• 40 to 50 percent: 17
• 50 to 60 percent: 23
• 60 to 70 percent: 3
• 70 to 80 percent: 0
• 80 to 90 percent: 0
• 90 to 100 percent: 0