|
Home
Biography
Books
Paintings & Links
Classes
Email
|
CS 156 Green Sheet, Spring 2002
Website: www.cs.sjsu.edu/faculty/rucker/cs156.htm
Prof. Rudy Rucker, MH 213, 924-5147, rucker@mathcs.sjsu.edu
Office Hours: 10:30 - 11:45, T and Th
Class meets 12:00 - 1:15 PM T and Th.
Midterm: Thursday, March 21.
Final Exam: Thursday, May 23, 9:45 - 12:00.
This course will study the history, theory, and the prospects of
artificial intelligence. We will cover a number of topics, including
search algorithms, alpha-beta pruning for game-playing, machine
learning, neural nets, genetic algorithms, machine vision, and robotics.
Most of the programming projects can be done in C++ (first choice)
or Java (second choice). Our neural nets assignment will require
use of C++, but not in any deep way. We are not going to use Scheme
or LISP. With respect to C and C++, the best bet is to use Microsoft
Visual Studio; you may rent the installation disks for $30.00 for
four days from the SJSU bookstore and legally install the software
on your machine. Information about Java programming environments
can be found off the home page for this course. If you have trouble
with C++, or are rusty with it, you can find a
quick review of C++ on this site.
The texts for the course are:
Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern
Approach, Prentice-Hall, 1995.
Hans Moravec, Robot¸ Oxford U. Press, 1999.
Russell and Norvig is too big a book to cover completely. We intend
to concentrate on four areas.
Basics, Searching, and Games: Chapters 1, 2, 3, 4, 5,
Logic and Knowledge Bases: Chapters 6, 7, 8, 9,
Machine Learning with Neural Nets and Genetic Algorithms: Chapters
18, 19 20, and 21
Vision and Robotics: Chapters 24, 24, 26 and Moravec's book..
Grades will be based on homework (~60 pts), on the midterm (50
pts), and on the final (75 pts). Homework later than 7 days will
not be accepted. WARNING: Skipping a homework assignment can lower
your final grade by as much as a full grade point.
Assignments are due at the START OF CLASS on the due dates. Assignments
will be graded down 20% for 1-7 days late. Assignments later than
7 days will not be accepted.
The prerequisite for this course is a C- grade or higher in CS
145A.
Cheating policy: Copying on an exam will result in a score of 0
on that exam for both parties.
|
|
Home page for Russell &
Norvig, Artificial Intelligence
|
|
We may write some programs in Java in this course. Information about Using Java.
But mostly we’ll use C++.
We may also simulate some intelligent creatures in a videogame
environment developed by Rucker. Videogame
Projects.
|
|
The Turing Test is the problem of writing a computer program (a
chatbot) that people will mistake for a live person when they “converse”
with it online. There is a standing prize of $100,000 for
the first one to succeed. Every year the Loebner Contest looks
for the best Turing Test program; the best among the entries gets
a prize. So far, though, nobody has won the big hundred K
prize for actually fooling something like ten judges for a half
hour’s worth of talk. Some Turing Test Links.
A Turing Test
Loebner Contest Home
Report
on the Loebner Contest (Turing Test) 2000
|
|
Here's an online Wumpus
game!
Russell and Norvig use Wumpus as an example where a logic agent
might be a useful kind of AI. Consider the Windows | Accessory |
Games | Minesweeper game as well.
|
Hmwk 1 Blind Search
Download and complete the two projects linked below and make three
executables:
queen8.exe, vacsearch.exe, vacsearchbreadth.exe.
Hand in a floppy with the three *.exe and your two altered *.cpp
files. Due Thursday, Feb 14. Also hand in a printed solution to
the Cannibal and Missionaries problem. You can either work the Cannibal
and Missionaries problem solution out by hand or by writing a program
to do it. Next to the written solution state the NUMBER OF STEPS
that it takes.
queen8hmwks02.zip
vacsearchhmwks02.zip
You should be able to unzip these using WinZip.
They will unzip into individual directories. You can open up the
projects by double clicking on the *.dsw files in Windows Explorer.
F7 should build the project, I've tested them and they do build
using my version of Visual C++ 6.0 which has service patches up
through patch 5.
If you have an older Visual C++ that doesn't have at least Service
Patch 2, you will get a compler error relating to the use of the
overloaded operator<<. In this case you should (a) get the
service patch from www.microsoft.com or (b) replace the code's use
of the << operator by, say, a member print(...) function that
you write.
Edit your homework by using File | Open dialog to open queen8.cpp
or vacsearch.cpp and editing it. Press F7 to build. The *.exe will
be in the Debug or the Release subdirectory depending on which kind
of build you are doing.
Run the programs from the command line interface by opening up
a DOS window. The *.cpp files explain the usage.
Your exe will run faster if you build the Release version, this
is selected by opeinng the Build | Set Active Configuration... and
choosing the Release version and then rebuilding.
If you close Visual Studio and click the clean.bat file in Windows
Explorer, it will remove the extra junk from the directory.
|
Hmwk 2 Search Projects. Due Thursday Feb 28.
You need to pick one of these projects and carry it out.
More details and specifications on the problems will be posted from
time to time, so check this page every now and then.
Do one of projects A, B, C, D. Most of you will do A, B,
or C.
My preferred programming language is C++, but if you prefer Java
that’s OK. I don’t want to deal with any projects
done in Lisp or Scheme, as I’m so rusty at those languages.
It will be a useful learning experience for you to THINK about
even those projects that you aren’t planning to do.
We’ll be discussing all of them.
Step one (in class on Feb 21): give me your first two choices of
problem . We’ll finalize problems in classs.
Step two: Give me a disk with a program and a page or two with
(a) a description of the design, (b) a guide to using the
program and (c) a report on what results you found.
(A) Hundred Queens Project.
We want to have some alternate search algorithms so we can handle
larger boards such as 100 queens. We should have command line
parameters to select the size of the problem and (possibly) the
search method used.
Treat the N-Queens problem with an IIA (Iterative Improvement Algorithm)
as described in section 4.4. As described in problem 4.12,
try the hill-climbing with random restart, and for max credit, an
annealing method. Make a little chart of comparing how well
these methods work (in terms of the number of candidate solutions
examined) for various sizes of N. Here's an interesting link on
annealing.
Note that you only have to fine ONE solution, not all of them (there
are too MANY to list anyway).
It woudl be nice if the output was (ASCII?) graphical so you could
see the symmetry of the solution...
(B) Eight Puzzle. Here we want a textmode graphic output
(picture of the problem using ASCII) and we want A* search.
Write a search algorithm to use A* search to solve the 8 puzzle.
Allow three kinds of input: (a) With no input the program starts
in a random configuration,
(b) with one integer input, the start state is scrambled n steps
from the answer.
(c) but you are also allowed to input a configuration in the a form
like a b c d e f g h i, where these are the values like this
a b c
d e f
g h i
We will use the number 0 to stand for the blank tile.
Unlike the book, let's say goal state is
0 1 2
3 4 5
6 7 8
Use the Manhattan heuristic.
For max credit do the 15 puzzle as well, with goal:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
(C) Big Vac Search. Write a bigvacsearch.exe takes as input two
kinds of input, with the third argument flaggin which kind.
Cols Rows 0 Dirt 1, Dirt2, dirt3, ....
same as before AND the format
Cols Rows 1 Percent_of_dirty_cells
So bigvacsearch 100 100 0.005 would be ten thousand cells with fifty
of them dirty.
To simplify, don't track vac direction, and let operator simply
be E, N, W, S, to move to one of the neighboring cells.
Use an A* search. Possible heuristics might be
h1(n) is the shortest Manhattan metric from n to a cell with an
uncollected piece of dirt or, if there's no dirt left the shortest
Manhattan metric to the home cell.
h2(n) is the sum of the Manhattan metrics to the cells that have
uncollected dirt. I think you would include the Manhattan metric
to the home cell in this sum as well.
(D) Polygon “Maze.” This one needs Windows graphics,
but uses a fairly simple search.
Solve problem 4.13 as a Windows program. Perhaps use the
Pop framework if you’ve had CS 160 with me, or maybe at least
use the cPolygon2 class and cVector2 classes from there. The
virtue of the Pop framework is that it lets you use floating point
values for the polygon vertices, which makes the algebra work better.
What I imagine here is a program that draws some standard polygons
like in the book illo or perhaps has an ability to create a random
scene with polygons. It might be espeically nice if the polygons
were long thin rectangles arranged to make a maze.
A start point S and an end point E are randomly selected (or optionally
by user mouse click). These points aren’t inside any
polygon. Your program does an A* search to find the shortest
path that runs from S to E. It is possible to prove that this
path must be a series of line segments that runs from S to a polygon
vertex (or to E, if possible) and then on to a succession of polygon
vertices and eventually to E. The one hard part of this (besides
drawing the scene) is to write a BOOL Polygon::Blocks(Point p1,
Point p2) that will return FALSE if and only if the line from p1
to p2 doesn’t cross any of the caller Polygon’s edges.
Program should probably allow user to randomize the polygon layout
rather than working for only one. But you can allow also to
read polygons in from a file.
|
|
Hmwk 3 Search Tree. Due Tuesday April 9.
Here are some links to commercial Decision Tree software products.
Look through the sites and see some of their example trees.
http://www.treeage.com/
http://www.salford-systems.com/products-cart.html
http://www.attar.com/
Take the Play Tennis cases I handed out in class and construct
the most efficient Search Tree, doing the entropy calculations we
describe in class, as in Section 18.4 or more informally as in Figure
18.6. Make a table or diagram showing your calculations, and draw
a picture of the tree. (10 Points)
|
|
Hmwk 4 Neural Nets for Face Recognition. Due
Thursday, April 28.
20 pts.
(Last updated Tue April 23, 2002, 12 noon ).
This example is taken from Tom
Mitchell, Machine Learning, McGraw-Hill 1997.
We have taken Mitchell's
Neural Networks for Face Recognition code, which is for a Unix
environment, and have ported it to a Windows environment using Visual
C++. The code itself was written for Mitchell by Jeff Shufelt of
Carnegie Mellon University in Fall 1994. Rucker ported it to the
Visual Studio/DOS envoronment, and then now-graduated SJSU student
Chris Nojima worked on it, and now Rucker is working on it again.
To get the ported code and examples for Windows, download Rucker's
facenetsupport5.zip file,
make a directory called facenet on your hard drive and uncompress
facenetsupport.zip into your facenet directory. Then get the code
files facenetcode9.zip, and decompress
into the facenet directory as well. The facenetsupport zip file
won't change very often, but the facenetcode zip file is still being
improved from time to time.
The Mitchell code trains a neural net to recognize features of
faces that are stored in a very portable byte per pixel *.PGM format.
So that you want to actually see what the faces look like, the SJSU
facenet?.zip package includes the executable of a program called
iview32.exe for viewing *.PGM files in Windows. This program is
by Irfan Skiljan
and is copyright to him. The complete Iview
package can be obtained online from Irfan's website at the Technical
University of Vienna. This is a very cool freeware program, and
it's worthwhile eventually getting the whole thing. But for now
you can get the viewer as part of the SJSU facenet?.zip download.
The first thing to do is for you to (a) get the facenetsupport
and facenetcode files and (b) figure out how to use the code to
build the default facetrain.exe Visual C++, by clicking on facenet.dsw
and (c) how to run facetrain.exe from the DOS command line. The
facetrain.exe application is currently set to try to learn to recognize
the face of a student named Glickman. I've provided some batch files
have examples of command lines which will work in our Windows environment.
Note that you have to be in the directory ABOVE the training and
faces directory, not down in the code directory. Also note that
the facenet.dsw project is set to place executables into the directory
above it where the batch files are.
When you run trainall.bat it creates an neural.net with binary
info about the weights for a net to distinguish things about the
faces. The default task is to recognize non-sunglasses. See below.
In order to make the neural nets do different things, you have
to edit some of the files and rebuild facetrain.exe. Search in the
code files for the phrase "CUSTOMIZE HERE" to find the
three places you may need to change, there are comments there explaining
what to do. Here is the most important spot, in imagenet.cpp
There is now a #define CHECKPOSE of some such in facetrain.h to
make the net try and recognize the pose.
// CUSTOMIZE HERE THE
TASK
if (!strcmp(eyes, "open")) //strcmp returns 0 if two strings
are equal.
net->setTargetUnit(0, TARGET_HIGH); //Want a high value to mean
TRUE
else
net->setTargetUnit(0, TARGET_LOW); //Want a low value to mean
FALSE
/* You change this test to tailor what your net learns. You can
keep
a simple condition on the output unit number 0 if you are just looking
for
a TRUE or FALSE answer.
Our default test looks for people not wearing sunglasses. If the
net
always answers TRUE or always answers FALSE, it will get about a
50% success rate, as half the pictures are with and half without
sunglasses.
Try trainng and testing on straight ahead poses with trainstraight.bat
and teststraight.bat, then try on all poses with trainall.bat and
testall.bat.
With our default 3 hidden units, for the sunglasses, you'll get
a test success of
about 97% on the straight face, and on the harder problem with varying
poses of all faces, you'll get about 75% success.
To train for other tasts, change the test. If you want to test to
recognize Glickman for instance, you could use this for your first
condition.
if (!strcmp(userid, "glickman"))
Careful, as a Glickman-seeking net can seem to do well if you look
at the
percentage of success, but this can be an illusion. A badly trained
net will
just say "NOT GLICKMAN" for every face, and it will USUALLY
be right, as most
faces aren't Glickman! You can see this is what's happening if when
the test
batch file lists all the incorrect answers and they are all pictures
of Glickman
that you said no on!
If you want to just decide if someone is looking up, you could change
the first line to this:
if (!strcmp(pose, "up"))
Again, be careful, as a badly trained net will in fact just say
"NO" for every face, and it'll look like you have 75%
success rate, and if you look at the mistaken
cases you'll in fact find they were all "UP" that you
said no on. Also make sure to train the looking up net on ALL faces,
not on just straight faces as none of those are looking up.
If you are doing a pick one of N answer, you will need to work with
the N output units here.
Make sure you keep in synch the changes at the three possible methods
that you may customize:
(a) the success condition in load_target in imagenet.cpp
(b) the args to new BackPropNN(...) in backprop_face in facetrain.cpp
(c) the evaluate_perormance function in facetrain.cpp
Change only (a) to simply change the type of TRUE/FALSE test you
consider,
but consider maybe using more hidden units, which means changing
(b).
Change (b) if you want to change the number of hidden or output
units.
Change (a), (b), and (c) if you want to change to a one-of-N decision.
Problem 1: Train a net to recognize sunglasses.(a) change the code
and make a new version of facetrain.exe suitable for this task and
name it shades.exe. Move the new exe into the right location, (b)
run our trainshades.bat file to make a shades.net for recognizing
shades, (c) test it with testshade.bat. Some students say the program
works better if you give it two output units instead of just one
and pick the higher valued one, so you may want to do that.
Problem 2: Make a yes/no pose recoginzer to recognize if the peson
is looking up.
Problem 3: Make a mood recognizer: normal, happy, sad, angry.
Problem 4:. Make a 1-of-20 face recognizer; i.e. implement a neural
net that accepts an image as input, and outputs the userid of the
person. (a) Change the code and make a new recognize.exe and move
it to the testing directory. You will need to implement a different
output encoding so as to distinguish among 20 people. (Hint: use
20 hidden units). (b) Run our trainrecognize.bat file to make a
recognize.net file. You can probably edit the bat file to train
for a longer number of iterations than the default. (c) Use our
testrecognize.bat file to test the net. One student said he got
65% accuracy after something like 1200 training steps. Consider
MItchless notion of preprocessign for pose.
Your homework will be to creat the shades.exe, shades.net and recognize.exe,
and recognize.net files, pose.net and pose.exe, mood.net and mood.exe
see if they work and hand them in on a disk. I will evaulate them
by using some bat files named grade*.bat files. Also hand in short
report (two pages at least) summarizing your conclusions or any
comments you have about additional tests you've done. Your grade
will be based on (a) if your nets work, and, more important, (b)
if your report is clear and (c) you tell me anything interesting.
For higher grade include some pictures and analysis of the weights,
using the two extra programs hidtopgm and outtopgm. To really do
a super report, select one of the addional problems Mitchell mentions
and do some work on it and tell me about it. Or make up one of your
own.
LAST FIX. In the file hidtopgm.cpp, Code VErsion 9 has
img->setPixel(i,j,pxl);
It should be
img->setPixel(j,i,pxl);
|
| |
|