- L3 Audio
of [Jan 26, 2010]. IR--traditional model. Relevance
function and how to compute it. How it is
approximated. Evaluating IR systems using
precision/recall. Precision/recall curves, F-measure.
- L4 Audio
of [Jan 28, 2010]. Categories of queries submitted to
search engines... and how not all of them conform to the
query model in IR. TREC competitions; Ways of representing
documents/queries/users in relevance computation; default
keyword representations used in IR, and how they lead to
relevance as "similarity". Keyword
generation in traditional IR. Boolean ranking model, its
uses and its disadvantages. Desiderata for
ranking. Imminent start of bag of words/vector similarity.
- L5 Audio of [Feb 2, 2010] Bag and Vector models of documents. Bag similarity by generalizaign Jaccard Similarity. Vector similarity in terms of eucledian distance. Term weighting and its connection to feature selection.
- L6 Audio of [Feb 4, 2010] Review/sanity check on similarity metrics. Efficient indexing and retrieval. The idea of inverted index (and the use of positional information in the index). Approximate ranking (or realizing that no one really cares even if you get the ranking between 10000th and 10005th entry wrong). Distributing the main index when it is too large to fit on a single m/c
- L7 Audio
of [Feb 9, 2010] Tolerant dictionaries and how
mis-spelled/mis-typed words can be corrected on the
fly. k-gram distance model; edit-distance model;
bayesian perspective (and the "fallacy of prior"). Start
of improvements to vector space similarity.
- L8 Audio of [Feb 11, 2010] (*Audio cut off about 2/3rd way as the battery died :-( Correlation analysis; making our intuitions about independence and correlation clear. Association and Scalar clusters. Three ways of doing keyword clusters: on the full corpus; on just the top-k documents for the query; and on the query logs. Motivating dimensionality reduction in terms of a malicious oracle adding "fake" keywords that are (linearly) dependent on the existing ones. The fishies example.
- L9 Audio
of [Feb 16, 2010] (***THE LSI LECTURE***) Review of the
fish example; connecting it to feature selection and
showing dimensionality reduction is a *general* version
of feature selection (since we first refine the
coordinate axes and then select the
features). Considering "linear tranformation" of axes
(i.e., translation and rotation) in the fish
case. Noticing that the new axes are the *less correlated*
to each other than the original axes (and recalling that
the "correlation" can be measure in terms of how narrow
the ellipsoid enclosing the data is..). Realizing that
these uncorrelated axes can be sorted in the order of
the amount of variance of the data they capture.
Going from fish to documents. First noticing the unintuitiveness of high-dimensinoal spaces (high-D apples are all peel and no core!). Next noticing that the fish analysis can be done with Singular Value Decomposition. Understanding that SVD is a general method to find *low-rank* approximations to data. The mechanics of SVD, and LSI for the rest of the class (culminating in a "hands-on" matlab example). - L10 Audio of [Feb 18, 2010] (***THE ADVANCED LSI LECTURE***) Lengthy recap of LSI analysis; discussion of class blog questions; discussion of relation between LSI and feature selection (feature selection looks for just subspaces of existing space); LSI and LDA (LDA takes the "class" information into account LSI doesn't know what classification you might be attempting); LSI and nonlinear dimensionality reduction (one idea is to first blow up the dimensionality and then find a lower-dimensional hyperplane in this blown up space. So, you might go from 20-D to 300-D and come down to 4-D).
- L11 Audio of [Feb 23, 2010] IR for Web pages. Discussion of how web pages are different from traditional IR corpora. Discussion of how to exploit tag information, and anchor text. Connection to "google bombs". Need for page importance measures (over and above page similarity ones). Desiderata for defining page importance measures. Measures based on link analysis. Overview of HITS (A/H) and Pagerank computation. (A digression on the importance of publishing ;-). Discussion of A/H algorithm--and its relation to primary eigen vectors of the correlation matrices AA' and A'A derived from the adjacency matric A).
- L12 Audio of [Feb 25, 2010] Example of A/H computation; discussion of power iteration and relating its convergence rate to eigen gap. Viewing link matrix as a transition matrix and giving it markov chain semantics. Understanding the conditions under which markov chains have unique stationary probabilities. Realizing that sink nodes and disconnected components lead degenerate markov chains (whose steady state probabilities do not converge to a unique vector). [Viewing disconnected components as sort of like a "super sink node"].[Digression: showing the effect of components on A/H computation; the tyranny of majority]. Avoiding the problem through weak links from every node to every node (and arguing that it corresponds to an impatient surfer who sometimes want to re-set to a random page not linked from the current page). The many different ways of setting up the reset matrix. Page rank computation example. Comparing page rank and A/H on the same examples.
- L13 Audio of [March 2, 2010] One more worked-out example of A/H and Pagerank computation (on the same graph). Approaches for combining importance and similarity (and the impact of global vs. local/query-specific analysis). Topic-specific page-rank as a middle-ground between fully global vs. fully query-specific importance computation. Analysis of stability of page rank and A/H computation. Understanding the importance of eigen gap in deciding the stability to random perturbation. Analysis of robustness to adversarial attacks.
- L14 Audio
of [March 5, 2010] (
Video of the lecture video part 1 (the first 1hr 5min 4gb) and video part 2 (the remaining 10+ min)
Efficient computation of pagerank (and how it is important to not
represent the M* matrix explicitly given that it is not
sparse); doing block-based pagerank iteration to avoid
thrashing, the use of asynchronous pagerank iteration to
improve convergence.
Social networks start. Connections between link-analysis and the general field of social network analysis. Some iconic examples of social network analysis (Typhoid Mary, Patient Zero, Web graph (and its small-world nature), Offcial florida ballot viral spread, Saddam capture, Aardvark acquisition). Applications of social networks. Graph-based representation and analysis of social entworks. Measures of influence and centrality. Smallworld phenomena--and their examples in kevin bacon game and erdos number. - L15 Audio
of [March 9, 2010] (Video of the lecture video part 1 (the first 1hr 5min 4gb) and video part 2 (the remaining 10+ min)
Milgram experiment; six-degrees of separation; (uniform) random
networks and their properties; realizing that the small world
probability increases sharply to 1 right near k=1; where k is the
average (expected) degree of the random network. If human networks are
(uniform) random, then they will have small-world phenomena (since k,
i.e., average number of friends per person, is almost always greater
than 1). Trying to confirm whether large-scale social networks are in
fact uniform random by comparing their degree distribution to the
Poisson degree distribution expected for random networks. Realizing
that most real world network degree distributions instead correspond
to negative sloping straightlines in log-log space (which means they
are of the form P=1/k^r, which is called powerlaws. Discussion of the
properties of power-law disributions (which have long tails that fall
off only polynomially rather than exponentially). Implications of long
tails on everything from probability of existence of such
highly-linked sites as google to the ability of making money selling
west wing DVDs and iranian classical music CDs on the web. Discussion
of generative
models which can result in power law distributions over network
degrees.
- L16 Audio
of [March 11, 2010] (Video of the lecture video part 1 (the first 1hr; battery died after that :( )
Attacks vs. disruptions on powerlaw vs. exponential networks;
navigation on social networks; applications of social networks;
discussion of trust and reputation; trust rank (a page-rank variant);
discussion of social search (and aardvark); discussion of othe
powerlaws in cse494--zipf's law; heap's law (and even benford's law).
Topics below this line are not included for Midterm
- L17 [March 23, 2010](Audio missing)Video of the lecture video part 1 (the first 1hr 5min 4gb) and video part 2 (the remaining 10+ min) Issues in designing a crawler; tradeoff between page importance and page change rate in deciding crawling priority; how Mercator supports politeness and priority; Connectivity server and its connection to inverted indices; start of hardware issues and the role for coarse-grained parallelism in search engines.
- L18 [March 25, 2010]Audio; Video of the lecture video part 1 (the first 1hr 5min 4gb) and video part 2 (the remaining 10+ min) Map-reduce parallelism, and how indexing can be done in map-reduce format. Clustering start. Examples of search results clustering. Computing cluster descriptions using tf/icf measures. Impact of "feature representation", "distance measures", cluster tightness and inter-cluster distance on clustering. Internal vs. external measures of quality for clustering.
- L19 [Mar 30, 2010]Audio; Video of the lecture video part 1 (the first 1hr 5min 4gb) and video part 2 (the remaining 10+ min) Internal and external measures of evaluting clustering; on the number of different k clusterings over n data points (and the realization that the full optimization can be computationally hard); distance measures for text clustering, and the useful properties of dot product distance metrics (such as cosine metric); local-search algorithms for clustering; k-means clustering--example, the tradeoffs in synchronous (centroid computed only once per iteration) and asynchronous (centroid re-computed everytime a change of membership occurs); explaining that given K, we only need to focus on intra-cluster tightness; G-measure which is the sum of squared distances of each point from the centroid of the cluster it belongs to; noticing that k-means comes to a minimum on G measure--but it can be local minimum; the discussion that one way to make k-means globablly optimal would be to allow simultaneous switch of sets of points together; alternative idea of considering multiple initial centroids and seeing which gives a better G measure. Problems with K-means--deciding on K using the knee points in the plot of G vs. k.
- L20 [Apr 6, 2010]Audio; Video of the lecture video part 1 (the first 1hr 5min 4gb) and video part 2 (the remaining 10+ min) More discussion on K-means and its limitations; "semi-supervised" clustering--where you are given "must-link" and "must-not-link" information. Hierarchical clustering methods--HAC and Bisecting K-means; discussion of how the inter-cluster distance definition changes the way HAC produces clusters. Buckshot and bisecting K-means as hybrid methods. Start of classification--and discussion of Rocchio Relevance Feedback as a classification technique.
- L21 [Apr 8, 2010]Audio; Video of the lecture video part 1 (the first 1hr 5min 4gb) and video part 2 (the remaining 10+ min)More on Rocchio Relevance feedback; long discussion on why rocchio and k-NN ideas are not good enough for classification (and how classification requires clusters to respect the labels--which may make the clusters not have sufficient internal quality); general classification methods, and why Naive Bayes is a good approach for text classification; discussion of Navie bayes and how it gets by with fewer learned parameters by making strong independence assumptions (and how those are also the same independence assumptions made by the vector similarity model)
- L22 [Apr 13, 2010]Audio; Video of the lecture video part 1(only first 30 min recorded due to battery failure). Naive bayes discussion continued; need for laplacian smoothing; unigram model of text; feature selection using mutual information; example of using mutual information to rank features; realization that MI-based approaches tend to focus on individual features; connection to dimensionality reduction which finds linear (or non-linear) combination of features that are most relevant. Start of recommendation systems.
- L23 [Apr 15, 2010]Audio; Video of the lecture video part 1 (the first 1hr 5min 4gb) and video part 2 (the remaining 10+ min)Recommendation systems. Content vs. Collaborative. Discussion of the collaborative filtering algorithm. Relative advantages of content vs. collaborative filtering approaches; a way to combine them by using content-based filtering to handle the sparse ratings problem. Adapting that idea to content-based filtering itself and using unlabeled examples to improve the performance of a classifier.
- L24 [Apr 20, 2010]Audio;
Video of the lecture video part 1 (the first 1hr 5min 4gb) and video part 2 (the remaining 10+ min)Discussion of item-centered approaches for collaborative filtering (and the connections to association and scalar clustering); discussion of LSI-style approaches to collaborative filtering, and their connection to the NETFLIX prize winner; the technical challenge of doing LSI in the presence of null values (unrated items)--two methods--imputation and going with a dot product on just on the co-rated items; the issue of over-fitting associated with the latter idea, and handling the overfitting through regularization term as part of low-rank approximation.
Overview of the part 3 of the course which is about specifying and exploiting structure--and how XML and Information Extraction fit in the "specifying/extracting structure", how Xquery and structure-exploiting query processing fit into "exploiting structure" and how the semantic web fits into "integrating structured sources". (Important: make sure you get this discussion as it lays out the overview of the rest of the semester)
- L25 [Apr 22, 2010]Audio;
Video of the lecture video part 1 (the first 1hr 5min 4gb) and video part 2 (the remaining 10+ min)XML--motivations for the standard, a little on the syntax, view of XML from IR and DB, path-querying of XML from IR side; XML as a data model and as an "exchange language" for data.
- L26 [Apr 27, 2010]Audio; Video of the lecture video part 1 (the first 1hr 5min 4gb) and video part 2 (the remaining 10+ min)XML from Database side--XML DTD, XML Schema, Xquery and its use cases; comparing XQuery and SQL; challenges in putting an XML front-end to relational databases--tagging and converting Xquery to SQL. XML and meaning--"Schema-abiding XML as grammatically correct text, which needs semantic (meaning) constraints". Mapping tags and the semantic web dream.
- L27 [Apr 29, 2010]Audio;
Video of the lecture video part 1 (the first 44min; the rest didn't get recorded :-( ) Starting Semantic web--and motivation through Ramayana; Motivating RDF and OWL standards by viewing RDF as providing the "base facts" in the text, and "OWL/RDF-SChema" as providing the background knowledge. Examples of RDF and OWL standards; critical discussion of expressiveness tradeoffs made by RDF and OWL. Use cases if semantic web standards.
Information extraction as a way of converting text into RDF-triples stage (which is also equivalent to populating a database given some text). Why it is different from full-blown NLP (if IR is a poorman's NLP, IE is a middle-class mans NLP..), why we think it is possible (especially the unwrapping issue).
- L28 [Apr 30, 2010]Audio; Video of the lecture video part 1 (the first 1hr 5min 4gb) and video part 2 (the remaining 10+ min)Information extraction; its history; how it differs from NLP, the spectrum of approaches for information extraction and how the scope of the tasks (e.g pattern scope, unary vs. n-ary relation extraction etc) make the task harder; three specific techniques--wrappers/unwrappers that use path expressions on the dom tree to extract information from highly templated text; extractors that use hyponymy patterns on parts-of-speech parse trees to extract general facts; and semtag/seeker which proposes a tag beureau.
- L29 [May 4, 2010]Audio;
Video of the lecture video part 1 (the first 1hr 5min 4gb) and video part 2 (the remaining 10+ min)Information Integration: A brief introduction of the
spectrum of approaches and methods; a short discussion of the
sourcerank work; Ending.
- Additional information on information integration can be found here: Information Integration on the Web (AAAI 2007 Tutorial with Craig Knoblock)