INFO 295: Mathematical Methods for Information Science

Tue/Thu 2:55-4:10 PM
4 credits, S/U Optional
Co-requisite: Math 231 or equivalent

This course teaches basic mathematical concepts in information modeling. Topics to be covered include graph theory, discrete probability, finite automata, Markov models and hidden Markov models. We will be guided by examples and applications from various areas of information science such as: the structure of the Web, genome sequences, natural languages, and signal processing.

Professor: Paul Ginsparg (301 College Ave, 5-7371, ginsparg@cs.cornell.edu)
Office hours: Wednesdays 2-3 PM (or by appointment)
Course website: http://courses.cit.cornell.edu/cis295_2005fa/ (this page)

Note: This is the course site for Fall 2005
The course site for Fall 2007 is here

Lecture 1 (Thu 25 Aug 05)

Intro, overview of topics to be discussed. Background discussion of Set Theory.
(See also CIS 295 Fall 2004)

Lecture 2 (Tue 30 Aug 05)

Probability and Counting 1 (Probability space, events, binomial coefficients, conditional probability).
See also counting examples.

Lecture 3 (Thu 1 Sep 05)

More on conditional probability: Bayes' Law and examples. (see also Bayesian inference)

Lecture 4 (Tue 6 Sep 05)

more on independent events, binomial distributions, random variables, expectation and variance (Probability and Counting 2 and newer notes)

Problem Set 1

Lecture 5 (Thu 8 Sep 05)

Continued notes on expectation and variance of Bernoulli distributions (also some comments on normal distributions and the central limit theorem, see also), and started review of exponentials and logarithms.

Lecture 6 (Tue 13 Sep 05)

finished discussion of exponentials and logarithms. Discussed counting equal heads/tails coin flips using Stirling's formula, and the voter problem.

Lecture 7 (Thu 15 Sep 05)

discuss www-admin spam, introduce A plan for spam (Graham, 2002). (See also "naive Bayes" document classification and Bayesian filtering.)

Lecture 8 (Tue 20 Sep 05)

continue A plan for spam (specifically "naive Bayes" and combining probabilities), plus more details on "naive Bayes".

Problem Set 2

Lecture 9 (Thu 22 Sep 05)

Some final comments on combining probabilities ( p(L or R | O) vs p(O | L and R) ).
Start Graph Theory 1 (Basic definitions, isomorphisms, paths)

Lecture 10 (Tue 27 Sep 05)

Graph Theory 2 (Eulerian and Hamiltonian circuits)
(See also Hamiltonian circuit)
Graph Theory 3 (Trees, planarity, colorings)

Lecture 11 (Thu 29 Sep 05)

finish Graph Theory 3 (Euler's formula), 6 color theorem (and 5 color theorem), start Graph Theory 4 (Graph algorithms)

Lecture 12 (Tue 4 Oct 05)

Some comments on Erdös-Renyi random graphs and Milgram's "small world" experiment.
Finished Graph Theory 4 (Graph algorithms)

Problem Set 3

Lecture 13 (Thu 6 Oct 05)

More comments on small world networks: Collective dynamics of 'small-world' networks (Watts/Strogatz, 1998)
and brief discussion of quantitative methods applied to social networks, node and link centrality (browse sections 1.1, 1.2, 1.3.6, and 1.4 [pp 1-3, 14-25] of Who is the best connected Scientist? (Newman, 2003))

Lecture 14 (Thu 13 Oct 05)

No class due to a conflict.
Instead read historical background material in
1) Vannevar Bush, As We May Think, Atlantic Monthly, July 1945
2) The World Wide Web: A very short personal history, Tim Berners-Lee
3) The Anatomy of a Large-Scale Hypertextual Web Search Engine (Brin/Page, 1998), equivalent html (read sections 1-3, pp 1-6)

Lecture 15 (Tue 18 Oct 05)

Recapped brief history of the web, discussed Page rank algorithm and Perron-Frobenius theorem.

Lecture 16 (Thu 20 Oct 05)

Completed discussion of Page rank algorithm and discussed other features used in ordering heuristics, mentioned "Google bombing" (NYTimes, 22 Jan 04) and Authoritative sources in a hyperlinked environment (Kleinberg, 1998).

Lecture 17 (Tue 25 Oct 05)

Finite State Automata 1 (alphabet, DFA, regular sets)

Midterm

Lecture 18 (Thu 27 Oct 05)

Finite State Automata 2 (NFA, subset construction)

Lecture 19 (Tue 1 Nov 05)

example of subset construction, Finite State Automata 3 (Regular expressions)

Problem Set 4

Lecture 20 (Thu 3 Nov 05)

Comments on random graphs and Poisson distributions (problem 4 of midterm).
connection between NFA's and regular expressions (examples). construction of automaton for A* from automaton for language A.

Lecture 21 (Tue 8 Nov 05)

more examples of the regexp/NFA connection, ultimately periodiocity and constraints on lengths of elements of regular sets. NFA's for vending machines, language parsing, and for gapped sequence alignment. Colorless green ideas sleep furiously and Chomsky transformational grammars.

Lecture 22 (Thu 10 Nov 05)

Examples of regular grammars, example of context-free grammar (SCIgen - An Automatic CS Paper Generator).
Started discussion of Markov Chains 1 (Basic definitions, transition matrix). "Mark V Shaney", and other examples generated from trigram probability distributions.

Problem Set 5

Lecture 23 (Tue 15 Nov 05)

Markov Chains 2 (Ergodic chains, stationary distributions)
(more on PageRank as a Markov process, How to make the top ten: Approximating PageRank from in-degree)

Lecture 24 (Thu 17 Nov 05)

Introductory parts on Hidden Markov Models from A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Rabiner, 1989), 257-261
Set up example of Viterbi by hand.

Lecture 25 (Tue 22 Nov 05)

Examples of Markov chains to determine the expected number of coin flips to reach a given number of heads in a row.
Finished example of Viterbi by hand.
Some HMM examples from "Biological Sequence Analysis", by Durbin, Eddy, Krogh, Mitchison (ISBN: 0521629713) pp 46-57 (Class handout)

Problem Set 6

Lecture 26 (Tue 29 Nov 05)

Completed Examples of Markov chains to determine the expected number of coin flips.
Example of max probability state not on maximum probability path.
Example of CpG islands from Durbin et al pp 46-57 (handout).
Started example from Bursty and Hierarchical Structure in Streams.

Lecture 27 (Thu 1 Dec 05)

More comments on Poisson distributions.
Mentioned recent HMM speech recognition application: An elitist approach for extracting automatically well-realized speech (Maj et al., 2005)
Finished HMM example from Bursty and Hierarchical Structure in Streams.
Derivation of (Shannon) information uncertainty, I = -Σ_i p_i log₂ p_i, and lightning review of applications (compression, ...).

Final Exam

Take Home: available 2p.m. Tues 6 Dec, due 2 p.m. Fri 9 Dec (should take no more than a few hours...)

Background text for Lecture 2: Chpt 4 of Rosen, Discrete Mathematics and its Applications (on reserve at engineering library, also used by cs 280)

Background text for Lectures 17-20: D. Kozen, Automata and Computability, pp 1-54.

Background text for Lectures 22-25 Sheldon Ross, Stochastic Processes

Advising Notes

This course is a required course for the new Information Science (IS) major in the College of Arts and Sciences and the College of Agriculture and Life Sciences. It can also be used to satisfy the math/stats course requirement for the Information Science minor/concentration.
INFO295 and CS280 may not both be taken for credit towards the IS major.