Review List for CS410 Midterm

General advice

Part I: Background

1. have a good understanding of some of the very basic concepts in probability, statistics, and information theory. In particular, you should know the basic rules for conditional probabilities, especially the Bayes rule.
2. know the basic idea of maximum likelihood estimation and why it's problematic when the data sample is small.
3. know how to compute the maximum likelihood estimate of a multinomial distribution (i.e., relative frequency).
4. know how to compute entropy, cross entropy, mutual information, and KL-divergence, and know their relations. You need to remember the formulas of entropy, KL-divergence, and mutual information.

Important slides: slides 3-7, slides 11-12 in the prob & stat lecture; slides 5-6, 8-12 in the information theory lecture.

Part II: Understanding text -- Natural Language Processing

1. have a general picture of what we can do and what we can't do with today's NLP techniques.
2. know what is POS tagging, what is parsing, and what is syntactic/structural ambiguity.
3. know what is a statistical language model, what is a unigram/bigram language model
4. know Zipf's law.
5. know why smoothing is necessary when estimating a language model and know the formulas for Laplace smoothing, Dirichlet prior smoothing, and linear interpolation smoothing and their similarities and differences.

Important slides: Slides 4, 7, 10-12, 14, 18 in the Intro to NLP lecture; slides 2-3, 8-11, 13, 16-19 in the Statistical Language Models lecture.

Part III: Accessing Text -- Text Retrieval and Filtering

1. know how text retrieval is different from database retrieval
2. know the distinction of long term vs. short-term information need and how they can be satisfied in different ways (short-term = ad hoc retrieval; long-term= filtering).
3. know why ranking (without an explicit cutoff) is often preferred to selecting a subset of documents for the user.
4. know how to compute the basic retrieval evaluation measures (e.g., precision, recall, and mean average precision, NDCG, MRR, F1). know the relative advantages and disadvantages of these measures (e.g., why isn't precision@10documents as good as average precision for comparing different ranking results? what's the advantage of NDCG over Mean Average Precision?)
5. know what is stemming, what is a stop word.
6. know what is relevance feedback and what is pseudo feedback and how they are different.

7. know the basic idea of the vector space model.
8. know the major term weighting heuristics (i.e., TF, IDF, and document length normalization).
9. know the idea and formula for Rocchio feedback.

10. know what is an inverted index and how to build a large inverted index with only a limited amount of memory. know how to score documents quickly using an inverted index (i.e., how to use scoring accumulators for scoring).
11. know the basic compression methods for integers (i.e., unary, gamma, delta, and gap).

12. know the general retrieval formula of the query-likelihood retrieval method when the document language model is smoothed with a collection language model, and know why smoothing with a collection language model leads to a retrieval formula that is similar to a traditional TF-IDF retrieval formula with length normalization.
13. know why we need to do two-stage smoothing and the two different roles of smoothing

14. know the KL-divergence retrieval formula and why it covers the query likelihood method as a special case.
15. know how to use a simple two component mixture model for feedback.
16. know the general idea of EM and how to use EM to estimate the component model in the simple two-component mixture model for feedback.

17. know the basic idea of the axiomatic approach.
18. know how the common retrieval heuristics (TF-IDF weighting, document length normalizatio) can be formalized as constraints on retrieval functions.

19. know what is a Web crawler. know the names "Google File System", "Big Table", "MapReduce", and "Hadoop". know what is "anchor text" and why it is especially useful for web search.
20. know how PageRank works and why it is helpful for Web search. know the basic idea of HITS.
21. know the basic idea of learning a retrieval function involving combinations of multiple features (particularly logistic regression).

22. know the difference between content-based filtering (i.e., adaptive information filtering) and collaborative filtering. know how memory-based collaborative filtering approach works.

Part IV: Organizing and Mining Text Information : Categorization, Clustering, and Extraction

1. know how basic retrieval techniques can be used to perform text categorization (prototype-based classifier and k-nearest neighbor).
2. know how basic retrieval techniques can be used to perform clustering of documents/terms (single-link, complete-link, and average-link).
3. know how basic retrieval techniques can be used to summarize a document.

4. know how text mining differs from and supplements search.
5. know how probabilistic latent semantic analysis (PLSA) generalizes the two-component mixture model for feedback.
6. know how to write down the log-likelihood function of PLSA as specified on slide 13 of the lecture and know the meanings of all the parameters.
7. know how the E-step and M-step formulas computationally update parameters (i.e., in E-step, the old parameter values are used in a formula to predict the latent/hidden topic label for each word in each document based on Bayes rule, while in M-step, the predicted topic labels are used to split the word counts to re-estimate all the parameters). you don't need to remember the formulas for the EM algorithm, but if you are shown these formulas, you should know how to interpret them.
8. know how to obtain term clusters and document clusters from the estimated parameter values of PLSA.