/ Programming II: Lecture
of Search II: Learning and `New AI'
- Those of
you who failed Programming I badly and have to rework the exam should
do it over break.
- Will help you do better in Programming II as well!
- Problems may not be just with programming, but also with exam
- Exam counts for more than all the courseworks combined.
I. AI at Bath
- Courses in Logic, Agents, Vision, HCI.
- Might be dedicated
courses in AI, machine learning and/or modelling by your final year (or
- Talk to your SSLC rep if you care.
- AI Seminar series (also HCI, Logic, general Department Seminars.)
- Look at Seminar link on dept. home page.
- Undergraduates can go to most of these, although we don't
organize your timetables around them.
- If you are keen, you can often work with a lecturer / help with
- Look at faculty web pages (here are the AI ones)
to find out
what people are interested in.
- 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
- Review on Hueristics and Search
- AI problems tend to be
- NP hard.
- Represented as a tree, where each node is an action, and its
children are the possible actions you could do next.
- Must use heuristics to prune
that tree and find a reasonable action.
- Design is search by the programmer!
- My PhD research area, see Designing
- Production Rule Systems (see ACT-R,
- Production: perceptual context / precondition connected to an action,
- Many productions in a system
- action selection:
- go through all productions,
- find one that's precondition matches the current context
- execute / `fire' its action
- Problem: many productions can be triggered (be able to fire / have
their preconditions match the context) at the same time.
- e.g. it's day, AND it's raining
- System for choosing which production to run.
- Many systems have rules like recency, efficacy (must learn
for both of these)
- Soar does a search if more than one rule files, then saves
the results of the search as another production.
- Supposed to be like the brain.
- Often learns too much!
- ACT-R has Bayesian statistics on efficacy as well as learning
- Both use "problem space" to narrow number of possible
Systems are production rule systems that encode knowledge
elicited from experts.
- The elicitation part is hard -- experts know things
- Perhaps should be called "novice systems"
- novices follow sets of rules
- experts recognize situations.
- Have got bad press (partly due to too large of sales pitch)
but still used in industry.
AI (that's my web page on the subject!)
- Designers replace evolution in providing the small search area
for what to do next.
- Will hopefully show
III. Searching in Advance II: Learning
- Important AI Concept: Anytime Algorithm.
- Have an algorithm that always gives you some solution.
- The longer you give the algorithm, the
better the solution gets.
- How chess programs work, some general
- Review on Parallel Search:
- One way to solve the problem of combinatorics is to have the
search run in parallel.
- Solutions people are currently working on:
- Quantum computing :
- Biological computing:
- Evolution / memetics:
- If a few members of a species or a culture find a good /
solution, the entire species or culture may eventually adopt that
- This works much faster in memetics (ideas) then genetics
(requires waiting for children to grow up and breed.)
- Evolution doesn't necessarily discover optimal solutions.
- Can think of it as an anytime algorithm.
- Can think of it as a search for heuristics.
- Sometimes heuristics work well in some environments and
- Other organisms or ideas are evolving too, will find hacks
around what used to be a good solution.
- E.g. giant birds as predators in SA, nailed when cats got
across from Asia.
- Evolution does come up with a bunch of `good tricks' (Dennett)
- This is true of cultural evolution as well.
- 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.
- Learning when you don't even know you've learned is called
- Adopting mannerisms of people you admire or just observe.
- Language -- you pick up new words and even dialects without
- May be most of what you learn.
- Several kinds of learning:
- Evolution: search done by species, we have a set of good
tricks to choose from.
- E.g. how we pick something up is limited / enabled by the
number of arms we have, which way the joints work.
- Reduces search space => affects expressed behaviour =>
part of intelligence!
- Storing results of previous search:
- Remember problem and solution, don't search again.
- update cost estimates (remember A*?) with real cost.
- These often are combined together
- Evolution essentially creates variables in animals which are
easily updated with the right kind of information.
- E.g imprinting.
- Short term memory, episodic memory, perceptual memory.
- Bottom line: learning is still search, it's just search in
advance, and search with a lot of biases / pruning already provided.
III. Learning in AI
- Many kinds of machine learning, again, could easily be a whole
- Don't neglect simple answers : giving variables and filling in
solutions when they become apparent.
- This approach can also be formalized: frames, case-based
- My work: Behaviour Oriented Design -- just use state in objects
- Neural Networks
- Perceptron Learning
- Applied Statistics (Chris Bishop
- Spiking models, compartment models. See Bath's group: Dan Richardson's page has
papers, he and all his students are a part of AmonI.
- Genetic Algorithms
- Evolution-like rules.
- Pick a representation of variables that affect the behavior
of an individual agent.
- Start with a population of possible values for those
- Run all the programs and evaluate how well they do.
- Select the ones that have done the job best,
- Create `children' by systematically permuting the variables
of the winners
- crossover : choose two (or more) parents, choose some of
the variable settings from each.
- mutation : just change a small number of variables randomly
- any other operator -- doesn't have to be naturally inspired.
- These children make a new population, now iterate! (go back
- Good for searching around likely solutions
- Need to have a good idea what the right representation / set
of variables is.
- Need to have a good idea of how to tell if the individuals
are doing well
- (tricky when starting from a solution too far from right --
- what solves the first steps well may not be able to solve
the last steps.)
- Many variations / applications:
- See Bath's learning
classifier systems group.
- See demo from Karl
Sims (you'll have to chase some links...)
- Just the tip of the iceberg.
- Learning is a form of search.
- But it's specialized so likely to succeed.
- Still any bias to search may mean that you miss a good solution.
- Intelligence is (NP) hard!
- Come to the seminars if you like.
page author: Joanna Bryson
16 March 2006