-
Welcome!
Welcome to Computer Science 308-644B: Pattern
Recognition. This course is an introduction to the fundamental
principles of pattern recognition systems with emphasis on an algorithmic
approach. Below is a description of the main ingredients involved in taking
this course with hints for passing, enjoying and making the best out of
it. Please study it carefully.
-
No Programming Assignments (but):
This course is NOT a programming
course and there will not be any programming homework assignments
in C or any other language. The course
is instead concerned with the principles behind the design of efficient
algorithms for solving a variety of different classes of problems that
arise in the design of pattern recognition systems. It is NOT
concerned with the details of implementing algorithms on real computers
with real programming languages. Instead we will use idealized computers
(mathematical models of computers if you like) such as the Real RAM
(Random Access Machine with real numbers as inputs) to measure the computational
complexities of our algorithms. We will also use idealized data structures
to study the algorithms and their storage requirements.
However, there is a web project requirement
which
requires knowledge of HTML and Java
for
the design of an applet. The emphasis here however is not on programming
but on designing and building a working system.
Hence finding free software on the web and putting it together are encouraged.
In fact it is suggested that no code be written if is is already available
somewhere. The idea is to do as little programming as possible!
-
Algorithms for Humans:
In this course we will be placing emphasis on the algorithms used for
measuring shape and for making decisions of class membership. Although
we are concerned with designing algorithms that are ultimately intended
for machines to process, we are NOT interested
in communicating with the machines but rather with each other. We are interested
in communicating with other humans about algorithms. Therefore we
will NOT use code in this course to
describe algorithms. Code was designed to be understood my machines not
humans. We will describe algorithms in a natural language such as English
and in the language of mathematics as has been done sucessfully and elegantly
for thousands of years. Furthermore mathematics should not be confused
with mathematical notation. The essence of mathematics lies in the precision
of concepts and not symbolic notation. Mathematical notation will be minimized.
Algorithms
described in code will get a mark of ZERO. Students using mathematical
notation gratuitously will be penalized. Mathematical notation should be
used only when absolutely necessary if it helps the reader. Remember that
storage space is no longer a problem and we need not save precious space
at the cost of making things difficult to read. In this course we will
practice how to use English (the international
scientific language) in a precise way.
-
Correctness of Algorithms:
One of the most important properties of an algorithm is its correctness.
In fact this is so important that many people refuse to call a procedure
an algorithm if it is not guaranteed to give the correct solution. Many
"algorithms" inhabiting the computers in society at large are incorrect.
This can cause great cost and tragic suffering. For example, patients have
been killed by overdoses of radiation because of incorrect algorithms.
The American astronauts aboard the space shuttle Challenger were killed
because of an incorrect geometric algorithm used in rebuilding the booster
rockets. In fact a nuclear world war could be caused by an incorrect algorithm.
Therefore it is very important to design correct algorithms. Students often
have trouble proving the correctness of algorithms. This
course will emphasize proving the correctness of algorithms.
-
Course Web Page:
Students should consult the course web page regularly. It can be found
at: http://www-cgrl.cs.mcgill.ca/~godfried/teaching.html.
This page contains several sections which we will now describe.
-
Course Logistics Information:
This page lists the times and location of the lectures, the method
of performance evaluation of the students, the coordinates of the lecturer
and teaching assistants, the text book and similar matters.
-
Calendar and Bulletin Board:
This page contains the calendar of events such as the in-class
exams, the dates the assignments are handed out, the due dates of the projects
and the dates of the student presentations. The bulletin
board at the beginning contains messages
from
me to you of important day to day changes of events, matters related to
the exams, etc and should be checked every week-day.
-
Lecture Descriptions, Homework and Play:
This web page contains a detailed list of topics covered in every lecture.
It contains the reading assignments made every week, the problem assignments
to practice for the tests, handouts and web reading material. It also contains
suggested applets to play with. Students are strongly encouraged to play
with the applets listed in this section. Those who do so will be at an
advantage since it greatly facilitates learning the course material.
-
WEB Course Contents:
This page contains most of the material that we will cover in the course.
Many of the reading assignments will concern pages in this section. This
web page also contains the applets for the suggested play section. Finally,
this web page serves as a reference library to satisfy your curiosity concerning
material directly relevant to the course. There is much more here than
we will cover in the course and I don't expect you to read it all. However,
I
do suggest you browse through all of it and read what you find most interesting.
-
Student Projects:
This page contains (by year) a list of student projects with links
to their web pages. Your project will be added to this list at the end
of the term. Please browse through the projects and play with the applets.
This will give you a good idea of what standards are expected of you for
your own project.
-
Class Talks:
This page contains the schedule of class talks.
-
Hints on How to Pass this Course Smiling:
This page contains the page you are now reading.
-
In-Class Tests:
There are two in-class tests during the course,
each counting 24%. They are closed
book. However, I am not interested in measuring your memory.
Computers are much better than we humans at that. The test will measure
your ability to think creatively. Students often ask: what material
will be covered in the test? My answer is always the same. I don't want
to insult your intelligence by asking you to regurgitate material we have
covered in class or that has been assigned reading. A machine can do that
much better than we can and I don't want to treat you like machines lest
I be labelled as machinist. I want to test you on what machines cannot
do (yet), and that is to generalize or apply your knowledge to solve new
problems in new contexts. Therefore the tests
will cover everything that we have NOT covered in the course.
The material I learned as a student in university, concerning radios, cathode
ray tubes, diodes, flip-flops and ultra-linear ramp generators that use
uni-junction transistors is all useless to me now. Many of the things I
teach today did not exist even ten years ago. However, the creative problem
solving techniques and critical thinking skills I learned as a student
can be applied to things other than transistors, such as the latest trends
in computational geometry. How can you do well on my tests? University
is (still, thank heaven) a place for discussing knowledge in a free and
open atmosphere and I encourage you to discuss all matters of the course
with your class mates. On the other hand the modern harsh reality dictates
that university is also a certification mechanism for certain skills -
hence the tests. The best way to study for the tests in this course is
to do the assignments and exercises on your own.
Only
personal discovery leads to true understanding. The book by Duda, Hart
and Stork (downloadable from the web) also contains many exercises at the
end of each chapter. Doing these exercises is an excellent way to learn
the material.
-
Web Project
There is a Web Project requirement counting
35%. Each student is required to do a
Web Project counting 35% of the total mark. The project is composed of
two parts: the HTML document counting 15%
and the JAVA applet counting 20%.
The goal of the project is to take a simple but elegant, important and
useful tool, concept or idea and design a web tutorial of it. The purpose
is not to do research on a topic but to write a tutorial exposition of
existing knowledge that will be accessible to a very wide audience. This
project will challenge the teacher in you. It will also challenge
the artistic designer in you since you are expected to exploit
the Web medium in all its potential. Ideally it should contribute something
that is not already on the Web. However, it can be on a topic that is already
on the web as long as it is much better than the existing
site.
The JAVA Applet:
The Java applet should be interactive and should NOT merely clarify
the HTML document. The applet should exploit its capabilities by contributing
significantly to the understanding of the topic in a way that the HTML
ocument cannot. Here again is a chance for you to demonstrate your creativity.
Surprise me!
Platform Compatibility: Your
project should work on as many platforms as possible but MUST work
well and fast on either Mozilla
or Firefox
in a UNIX
or LINUX
environment. The purpose of this requirement is to make you learn about
compatibility and to allow me to examine the project without having to
spend hours installing plug-ins and other such nonsense.
-
Oral Presentation
There is an Oral Presentation towards the
end of term counting 17%. Each student
is required to give a class oral presentation of a recently published paper
in an application of
pattern recognition. By an application it is meant a real problem of recognizing
some class of patterns. You can check the application
list for additional applications.
Chinese character recognition or heart disease diagnosis are applications.
A comparison of neural network classifiers for speech recognition is not
an
application; rather it is an empirical study of neural networks. In other
words the paper you select must be primarily trying to solve a recognition
problem and not investigate some tool for a recognition problem. In the
course I will cover pattern recognition techniques which are general and
thus application-independent. In contrast you will present the application
that most interests you. The talk will last between 15 and 25 minutes depending
on the size of the class. The goal is to make the class understand everything
you say while at the same time teaching them something interesting they
will remember.
Paper Selection: By
the middle of the term you should bring to me three papers published within
the previous year that you would like to present. I will also pass
out some papers which you may choose to present. I will select one of the
three for you. Once you have been assigned this paper, the application
area will be closed to other students (first come first served). This way
everyone will speak on a different application and the class will be exposed
to a wide range of applications.
Overhead Projector: Students
must
use an overhead projector and transparencies
(no more than 10). Use of color is encouraged.
Writing must be legible from the back of the class. Laptops
are not allowed.
Marking: Marking
will be done by the students in the class. Marks will take into account
both the (1) content and (2) the clarity of the visual and oral material.
-
Class Tests:
Please write the tests legibly. If
the TA cannot read your material you will get ZERO. Whenever
you are describing an algorithm you MUST always
include a proof of correctness. NEVER say that something is
obvious. Never use phrases such as "clearly....blah, blah, blah". Obviousness
is always the enemy of correctness and saying something is obvious sometimes
insults the reader as well. Always give clear simple short arguments.
Long convoluted sentences increase the probability that they are wrong.
Pretend you are explaining things to your ten-year old sibling. Don't guess.
If you are not sure of something say so. Clear thinking with a partial
answer will be rewarded. Cloudy thinking with a full answer will be penalized.
-
Teaching Assistants:
The TA is responsible for marking the tests, giving tutorials before
each class test and explaining course material to you during office hours.
If you have any questions about the course material or how you were marked
please go and see the TA.
-
Enjoy the Course!
If for some reason the TA cannot help you please come and see me. In
any case please come by sometime to say hello and tell me how you are doing
in the course. I expect to see you more frequently early in the term to
discuss your course project and its progress. My
door is always wide open during my office hours.
Godfried Toussaint