CS/EE 555/655: Analyzing Sequences

Synopsis

Many types of data occur sequentially. A conversation between two people can be thought of as a sequence of speech turns; a written sentence can be thought of as a sequence of words and punctuation symbols, while a spoken sentence can be thought of as a sequence of phonemes. Time-series data (weather observations, stock tickers, etc.) is inherently sequential, and, of course, molecular biology is replete with examples of sequential data (sequences of nucleotide bases in DNA and RNA, amino acids in protein strands, etc.).

This course will concern itself with methods for analyzing these kinds of data, with a particular emphasis on sequences derived from linguistic data. Topics will include:

Applications of finite state automata, in particular with regards to language modeling;
Discrete and continuous Hidden Markov Models, in the context of tagging;
Gaussian Mixture Models & the Expectation-Maxmization algorithm;
Suffix Arrays & Trees/Tries;
Sequence alignment & matching.

While we will be primarily focused on written language, we may dip our toes into speech here and there.

Fig. 1: xkcd #851, "Na", by Randall Munroe. An example of an FSA describing the surprisingly regular language of several notable songs.

Prerequisites

The course will include several hands-on assignments in which students will implement various algorithms and run them on real-world data. As such, students must be very comfortable with basic programming (in the language of their choice). What does this mean? It means that any graduate student in Computer Science or Electrical Engineering should have the appropriate background for this course. For students from other backgrounds, consider the following description of a hypothetical programming assignment:

"Write a program to traverse a directory hierarchy containing the various plays of Shakespeare, and generate a report that lists which words are most over-represented in the tragedies as compared to the comedies."

Can you do this? If so, that means that you know about file I/O and some basic data structures (lists, dictionaries/hashes, etc.). You are probably good to go for the course, as far as the programming piece is concerned.

Another important pre-requisite is the ability to work comfortably with a UNIX-style command line. You don't need to know about every command ever written, but you should be at least a little bit familiar with how to navigate a directory hierarchy, create, copy, and move files, run programs, and pipe IO from one program to another.

In addition to being comfortable with this the above, students should also be comfortable working with probabilities, statistics, and algebra. Specific concepts to know about include: joint and conditional probabilities, Bayes' Theorem, random variables drawn from specific probability distributions (e.g. the Gaussian distribution), logarithms and log-probabilities, etc. Some past exposure to linear algebra will also be extremely useful for certain parts of the course.

Instructor

Fig. 2: The instructor, next to a large sculpture of the majestic Crotaphytus bicintores.

CS/EE 5/655 is being taught by Steven Bedrick. He can usually be found in his natural habitat, Gaines Hall room 19. While he has no set office hours, GH is far enough off the beaten path that you should probably schedule something with him before making the schlep.

We strongly encourage you to consult the Student Health Center for guidance about any pre-travel immunizations that may be required before visiting Gaines Hall.

Textbook

We will be using Jurafsky & Martin's "Speech and Language Processing", 2^nd edition as our primary text in this course, but we will also probably use readings from other sources as well. New copies of J&M are absurdly expensive, but well worth the investment, as you will find this book necessary and useful for future CSLU classes. You may be able to find used copies online at a significant discount.

Note that many of the electronic copies of J&M floating around the Internet, besides being of questionable provenance, are of the first edition— which contains numerous errata and less material than does the second edition.

Schedule

Date	Topic	Reading	HW Assigned
Sep 29 (M)	Introduction
Oct 1 (W)	Regular Expressions	J&M Chap. 2	HW1 - Regexes
Oct 6 (M)	FSTs, part 1
Oct 8 (W)	FSTs, part 2 [in-class FST examples]	Sproat & Roark Chapter 1.	HW2 - Number Name generation, ROT-13, & T9
Oct 13 (M)	LMs
Oct 15 (W)	LMs & Smoothing
Oct 20 (M)	String Similarity
	Edit distance - Levenshtein - Jaccard - Jaro-Winkler - Wagner-Fischer Algorithm - Back-door way to introduce Dynamic Programming;
Oct 22 (W)	Discrete HMM
Oct 27 (M)	Viterbi & Baum-Welch	J&M 5.5, 6.1-6.4	HW3 - Implement simple Viterbi tagger
Oct 29 (W)	VQ & GMMs
Nov 3 (M)	EM algorithm
Nov 5 (W)	GMM HMMs
Nov 10 (M)	Speaker Diarization Case Study		HW4 - Diarization
Nov 12 (W)	String Matching - Literal (1) [supplementary slides: Naïve algorithm, Improved naïve algorith, Linear-time "Z" algorithm]	Gusfield Chapter1, Add'l Resources
Nov 17 (M)	String Matching - Literal (2)	Gusfield 1 & 2
	[supplementary slides: `roark_kmp.pdf` `roark_boyer_moore.pdf`]
Nov 19 (W)	String Matching - Approximate [Aho-Corasick, Baeza-Yates & Perleberg]	Gusfield Chapters 3.4.. & 12
Nov 24 (M)	String Alignment
Nov 26 (W)	Suffix Trees & Arrays
Dec 1 (M)	More Fun and games with suffix trees		HW5 - Boyer-Moore (& KMP)
Dec 3 (W)	Tries and Levenshtein Automata	Add'l Reading
Dec 8 (M)	Joel: Information Theory & Cross-entropy; Shiran: Coding & Compression
Dec 10 (W)	HW5 presentations!		HW6 - Tries & Levenshtein Automata

Logistics

CS655 will be held Mondays and Wednesdays, from 4:00 to 5:30 PM, in GH5.

Homework

We will have homework, (basically) all of which will involve programming. The point of the homework is to give you "hands on" experience with the algorithms we'll be covering, not to learn how to write production-ready code. For some of the assignments, I will provide "scaffolding" code that may save you significant time; mostly, this code will be written in Python. If you want to use something else to do the assignment, you are of course free to do so.

Some assignments will, however, make use of Python libraries to do some of the heavy lifting. When this is the case, the assignment description will include notes on which libraries are needed and how to install them. Please make your life easier by installing those libraries at the very earliest opportunity, since some of them are known to be a bit finicky to get running.

The homework assignments will all come with a "due date." Assignments will be due at 11:59 pm (Portland time) on their due date. If you think you will need additional time to complete an assignment, let me know as soon as possible. If something serious and unexpected comes up at the last minute (illness, family emergency, etc.), we'll work something out.

Grading

There will be no final project, nor will there be a final exam. This means that most of your grade (70%) in the course will be from the homework assignments. The remaining 30% will be based on class participation. What does this mean? It means attending class, asking questions during lectures, coming to talk to me about homework assignments, and so on.

Resources

Useful books

Jurafsky & Martin, Speech and Language Processing, 2^nd edition.
Crochemore, Hancart, & Lecroq, Algorithms on Strings
Gusfield, Algorithms on Strings, Trees, and Sequences
Sproat & Roark, Computational Approaches to Morphology and Sytnax

Websites of note

Regular Expression Tools
Homebrew - Useful package manager for Mac OS X
- Main homepage
- homebrew/science repository of scientific software
FST Stuff:
- Mohri M, Pereira F, Riley M. Weighted finite-state transducers in speech recognition. Computer Speech & Language. 2002;16:69–88.
- OpenFST:
  - OpenFST
  - Useful Tutorial
- pyfst - Simplified Python interface to OpenFST
- Useful FST Tools:
  - ascii.syms.txt - An ASCII OpenFST symbol table
  - fstcompilestring.sh - A shell script for compiling FSTs from strings. Note that you will almost certainly have to futz around with the first part of the script (where it specifies which symbol table to use) a little bit. Please see the comments in this file about its origins.
  - fstprintstrings - A C++ program that will print the strings generated by certain acyclic FSTs.
  - wordlist.fst - An FST representing /usr/share/dict/words
- Files from the in-class FST examples
Jason Eisner's HMM / Baum-Welch Demo:
- Spreadsheet
- Description, supplementary material, etc.
GMM & EM resources (used by Meysam in constructing his lectures):
EM & Coin Flipping
- Do CB, Batzoglou S. What is the expectation maximization algorithm? Nat Biotechnol. 2008 Aug;26(8):897–9.
- StackOverflow conversations discussing the article:
  1. "Numerical example to understand Expectation-Maximization"
  2. Follow-up to #1: how does expectation maximization work?
  3. Follow-up to #2: how does expectation maximization work in coin flipping problem
- Meysam's code
String Matching
- Ivan Yurchenko's lovely tutorial on the Z-algorithm, as described in Gusfield.
- Carl Kingsford's slides on the Z-algorithm
- Tries & Levenshtein Automata
  - Navarro G. A guided tour to approximate string matching. ACM Computing Surveys. 2001 Mar;33(1).
  - Schulz KU, Mihov S. Fast string correction with Levenshtein automata. International Journal on Document Analysis and Recognition. 2002 Nov 1;5(1):67–85.
  - Mihov S, Schulz KU. Fast Approximate Search in Large Dictionaries. Computational Linguistics. 2004 Dec;30(4).
  - Ji S, Li G, Li C, Feng J. Efficient interactive fuzzy keyword search. Proc. WWW '09.
  - Feng J, Wang J, Li G. Trie-join: a trie-based method for efficient string similarity joins. The VLDB Journal. 2012 Aug;21(4).
Homebrew (for installing stuff on OSX)
Additional Readings:

Student Access Statement

Our program is committed to all students achieving their potential. If you have a disability or think you may have a disability (physical, learning, hearing, vision, psychological) which may need a reasonable accommodation please contact Student Access at (503) 494-0082 or e-mail studentaccess@ohsu.edu to discuss your needs. You can also find more information at www.ohsu.edu/student-access. Because accommodations can take time to implement, it is important to have this discussion as soon as possible. All information regarding a student’s disability is kept in accordance with relevant state and federal laws.