CM10135 / Programming II:   Lecture 18


Applications of Search II: Learning and `New AI'


-I. Housekeeping

  1. Those of you who failed Programming I badly and have to rework the exam should do it over break.
    1. Will help you do better in Programming II as well!
    2. Problems may not be just with programming, but also with exam taking.
    3. Exam counts for more than all the courseworks combined.
  2. Coursework Marking:
    1. I'm glad many students have gotten programs working for the first time here.
      1. Unfortunately, we can't give you extra marks for that, this is programming II.
    2. Last year many students also first understood programming second term.f
      1. Their marks got better & better across the three courseworks.
      2. This is partly why CW1 is only worth 10 points instead of 13.333333...
    3. Appeal procedure on marking:
      1. Go to the TAs.
      2. If it can't be resolved, sign up for my office hours using this link (only accessable from campus.)
      3. I still won't set a new mark without checking again with the TAs so that everything is fair.

I.  AI at Bath

  1. Courses in Logic, Agents, Vision, HCI.
    1. Might be dedicated courses in AI, machine learning and/or modelling by your final year (or for MEng.)
    2. Talk to your SSLC rep if you care.
  2. AI Seminar series (also HCI, Logic, general Department Seminars.)
    1. Look at Seminar link on dept. home page.
    2. Undergraduates can go to most of these, although we don't organize your timetables around them.
  3. If you are keen, you can often work with a lecturer / help with research.
    1. Look at faculty web pages (here are the AI ones) to find out what people are interested in.
    2. Only do this if you have time after your coursework -- if you tend to finish things both well and early.

II.  Searching in Advance I: Heuristic-Based AI

  1. Review on Hueristics and Search
    1. AI problems tend to be
      1.  NP hard.
      2. Represented as a tree, where each node is an action, and its children are the possible actions you could do next.
    2. Must use heuristics to prune that tree and find a reasonable action.
  2. Design is search by the programmer!
    1. My PhD research area, see Designing Intelligent Systems
    2. Trying to come up with good design rules is like evolution.
    3. This is why sometimes programmers can chance on the right answer to a question even sooner than they can understand how to solve the question.
    4. Languages like java are designed to give you a heavily pruned search space.
    5. Using good technique makes it likely you will find good answers!
  3. Using very limited search of known good strategies is the key to several other kinds of AI...
    1. Production Rule Systems (see ACT-R, Soar)
      1. Production: perceptual context / precondition connected to an action,
        1. Many productions in a system
        2. action selection:
          1. go through all productions,
          2. find one that's precondition matches the current context
          3. execute / `fire' its action
      2. Problem: many productions can be triggered (be able to fire / have their preconditions match the context) at the same time.
        1. e.g. it's day, AND it's raining
      3. System for choosing which production to run.
        1. Many systems have rules like recency, efficacy (must learn for both of these)
        2. Soar does a search if more than one rule files, then saves the results of the search as another production.
          1. Supposed to be like the brain.
          2. Often learns too much!
        3. ACT-R has Bayesian statistics on efficacy as well as learning new productions.
        4. Both use "problem space" to narrow number of possible productions tested.
      4. Expert Systems are production rule systems that encode knowledge elicited from experts.
        1. The elicitation part is hard -- experts know things implicitly.
        2. Perhaps should be called "novice systems"
          1. novices follow sets of rules
          2. experts recognize situations.
        3. Have got bad press (partly due to too large of sales pitch) but still used in industry.
    2. Reactive AI (that's my web page on the subject!)
      1. Designers replace evolution in providing the small search area for what to do next.
      2. Will hopefully show some movies.
      3. Excellent slides about this approach.

III.  Searching in Advance II:  Learning

  1. Important AI Concept:  Anytime Algorithm.
    1. Have an algorithm that always gives you some solution.
    2. The longer you give the algorithm, the better the solution gets.
    3. How chess programs work, some general planning systems.
  2. Review on Parallel Search:
    1. One way to solve the problem of combinatorics is to have the search run in parallel.
    2. Solutions people are currently working on:
      1. Quantum computing :
      2. Biological computing:
      3. Evolution / memetics:
        1. If a few members of a species or a culture find a good / winning solution, the entire species or culture may eventually adopt that solution.
        2. This works much faster in memetics (ideas) then genetics (requires waiting for children to grow up and breed.)
  3. Evolution doesn't necessarily discover optimal solutions.
    1. Can think of it as an anytime algorithm.
    2. Can think of it as a search for heuristics.
    3. Sometimes  heuristics work well in some environments and not others.
      1. Other organisms or ideas are evolving too, will find hacks around what used to be a good solution.
      2. E.g. giant birds as predators in SA, nailed when cats got across from Asia.
  4. Evolution does come up with a bunch of `good tricks' (Dennett)
    1. This is true of cultural evolution as well.
    2. Although we think we are rational agents who do things that provably make sense, in fact much of what we do and know we get by imitation of authority.
    3. Learning when you don't even know you've learned is called Implicit Learning.
      1. Adopting mannerisms of people you admire or just observe.
      2. Language -- you pick up new words and even dialects without noticing.
      3. May be most of what you learn.
  5. Several kinds of learning:
    1. Evolution:  search done by species, we have a set of good tricks to choose from.
      1. E.g. how we pick something up is limited / enabled by the number of arms we have, which way the joints work.
      2. Reduces search space => affects expressed behaviour => part of intelligence!
      3. Examples with legs.
    2. Storing results of previous search:
      1. Remember problem and solution, don't search again.
      2. update cost estimates (remember A*?) with real cost.
    3. These often are combined together
      1. Evolution essentially creates variables in animals which are easily updated with the right kind of information.
      2. E.g imprinting.
      3. Language?
      4. Short term memory, episodic memory, perceptual memory.
  6. Bottom line: learning is still search, it's just search in advance, and search with a lot of biases / pruning already provided.

IV.  Learning in AI

  1. Many kinds of machine learning, again, could easily be a whole course.
    1. Tom Mitchell Book
    2. New Chris Bishop Book
  2. Don't neglect simple answers : giving variables and filling in solutions when they become apparent.
    1. This approach can also be formalized: frames, case-based reasoning.
    2. My work: Behaviour Oriented Design -- just use state in objects for learning.
  3. Neural Networks
    1. Perceptron Learning
    2. Backpropogation
    3. Applied Statistics (Chris Bishop Book NN Book)
    4. Spiking models, compartment models.  See Bath's group: Dan Richardson's page has papers, he and all his students are a part of AmonI.
  4. Genetic Algorithms
    1. Evolution-like rules.
      1. Pick a representation of variables that affect the behavior of an individual agent.
      2. Start with a population of possible values for those variables.
      3. Run all the programs and evaluate how well they do.
      4. Select the ones that have done the job best,
      5. Create `children' by systematically permuting the variables of the winners
        1. crossover : choose two (or more) parents, choose some of the variable settings from each.
        2. mutation : just change a small number of variables randomly
        3. any other operator -- doesn't have to be naturally inspired.
      6. These children make a new population, now iterate! (go back to 2)
    1. Good for searching around likely solutions
      1. Need to have a good idea what the right representation / set of variables is.
      2. Need to have a good idea of how to tell if the individuals are doing well
        1. (tricky when starting from a solution too far from right --
        2. what solves the first steps well may not be able to solve the last steps.)
    2. Many variations / applications: 
      1. See Bath's learning classifier systems group.
      2. See demo from Karl Sims (you'll have to chase some links...)
    3. Just the tip of the iceberg.

V.  Summary

  1. Learning is a form of search.
  2. But it's specialized so likely to succeed.
  3. Still any bias to search may mean that you miss a good solution.
  4. Intelligence is (NP) hard!
  5. Come to the seminars if you like.

page author: Joanna Bryson
6 March 2007