|
|
 |
|
Supervisions (DRAFT arrangements for 2004)
Dates:
Week 3 29 Jan
Week 4 5 Feb
Week 5 12 Feb **
Week 7 26 Feb
Week 8 4 Mar
Week 9 11 Mar
** Note the exclusion of
Week 6 19 Feb
which is intended to reduce your and my 6th week blues.
One of the main assignments for this course is to write
compression and uncompression algorithms
to compress
a sparse file containing N=10000 bits of which roughly 0.01 are 1s;
your algorithm should work well on all such files.
Please email to djcm1 the compressed size that your algorithm achieves,
and maybe write a brief webpage summarising your method.
If you'd like to use the Huffman algorithm in constructing your
solution, here's one in perl.
[Worked solutions: C programs for compression]
Another of the three main assignments is this:
-
implement or describe a method to distinguish, based on
string of successive characters in a document,
- whether the document is an English-language document or
a totally-random document.
-
OR - whether the document is an English-language document or German
-
OR - whether the document is an English-language document or backwards-English (siht ekil)
-
estimate how many successive characters your method needs in order
to work well.
-
English and German letter frequencies are provided, in
case you find them useful.
An outline of the main topics to be covered in each of the
six supervisions is as follows:
- Design your own code; typicality; Gibbs's inequality
- Symbol codes, Arithmetic codes
[Worked solutions: C programs for compression]
- Capacity of channel; noisy channel coding theorem
- Bayesian inference
- Monte Carlo methods, variational methods
- Single neuron, Hopfield network
First supervision
Some topics for discussion:
1.9 [p14] make your own code
2.28 [p38] efficient computation of entropy
2.36 [p39] Bayes's theorem
A list of all the recommended exercises
for the course is being refined below.
Before each supervision, please hand in a sheet of paper, with a summary of your REACTIONS to
the chapters of the book. Please write one paragraph on each chapter, giving the
parts that were
difficult to follow, the examples that were helpful, the examples that were not included that should
have been, anything that's still unclear or confusing.
These reactions will help guide the supervision onto worthwhile topics of discussion.
Reactions may be sent by email.
Particularly recommended exercises for 2004 are as follows (with bold highlighting
exercises to be discussed in supervisions):
| Exercise | Purpose |
| 1.3 (p.7) | familiarity with repetition code, and approximation |
| 1.5, 1.6, 1.7 (p.13) | familiarity with Hamming code |
| 1.9 | make your own code
- very likely to be an exam question |
| 2.4, 2.5 (p.27) | familiarity with binomial distribution, how to compute variances |
| 2.21-2.26 (p.37) | working with probabilities, proving inequalities |
| 2.28 | efficient computation of entropy |
| 2.16 (p36) | law of large numbers |
| 2.37 | Bayes's theorem |
| 2.17 | manipulating probabilities |
| 2.20 | life in high dimensions |
| 3.3 (p47) | Bayes's theorem |
| no specific exercise
| Typicality
|
| 5.21, 5.22 (p.102) | Make optimal symbol code |
| 5.29 | Creative use of Huffman algorithm
- likely to be part of an exam question |
| 6.2, 6.3, 6.9 | Arithmetic coding
- likely to be part an exam question
|
[From here onwards are the old ex's for 2003; watch this space for updates to 2004.]
|
| 8.3 (p.157), 8.4, 8.6, 8.7, 8.10 (159) | Two-variable entropy expressions |
| 9.17 (175), 10.12 (196), 15.10, 15.11 (262), 15.13
| Computing Capacity of channel |
| 9.20 (176) | "Birthday problem" - collisions between random strings |
| 9.19 | Modelling real information sources and channels |
| 15.3 (260) | |
| 15.4, 15.5 | Counting arguments, computing mutual information |
| 24.4, 24.5 (332), 24.8 (337). (Cut from list: 24.12)
| Finding Maximum Likelihood parameters |
| 24.14 | life in high dimensions; atypicality of the most probable state |
| 24.15 | occasional silliness of Maximum Likelihood answers |
| 29.1 (377) | Laplace approximation |
| 31.13, 31.14 (415) | Metropolis method |
| 31.4 (404), 31.5 | Gibbs sampling |
| 33.3 (447) | Think creatively about making a content-addressable memory
|
| 35.5, 35.6, 35.7 | Variational methods |
| 37.5 (484) | Inference problems |
| 42.1 (510) | Perceiving connections between topics |
| 42.2 (513) | Deriving simple learning algorithms |
| 42.5 (519) | Inferences as "neurons" |
| [43.1 (529) (This topic is probably not examinable)] | Counting |
| 43.3 | Information in the real world |
| 45.3, 45.4 (551), 45.9 (560) | Hopfield net |
| | |
| | |
For further suggested reading and examples before the supervision,
see the course summary page.
|
Site last modified Thu Sep 30 20:34:34 BST 2004
|
|
