CSE 494/598 Information Retrieval, Mining and Integration on the Internet

Instructor: Subbarao Kambhampati

Next offering: Spring 2010 (T/Th 10:30--11:45AM; BYAC 150)

Note for Undergrads:I am particularly interested in seeing more undergraduate students register for this course.

1. How do search engines work? Why are some pp better than others?
2. Can we think of the web as a big database/knoweldge base and support efficient database style query processing?
3. Can we find useful pearls and patterns in the mass of accessible data on the Internet?

This course will be breadth-oriented introduction to the issues involved in answering these questions.

Prerequisites: CSE 310 required. Other courses that will help include CSE 471 (AI) CSE 412 (Databases) and CSE 450 (Algorithms). I am hoping that students have had at least one of these 4-level courses already, but won't insist on them. Students planning to register for this course are encouraged to talk to the instructor (via email at rao wholivesat asu dot edu).

Grading: The grading will be based on class participation, exams and projects.

Textbooks: There is no prescribed textbook. We will read papers (see the reading list.)

Overview: The best overview is the list of topics and lecture notes from the previous offering (shown below).

Additional pointers:

• Check out what students say about the last offering of this course in CEAS student evaluations.
• Check out what students "learned" from the last offering of this course (in their own words).
• Check out what earlier students did in the last offering of the course
• Check out what some of the earlier students are doing now.

Lecture Notes & Audio from Fall 2008

Notes from Fall 2008; T/Th 1:30--2:45pm, BY 270

Instructor: Subbarao Kambhampati (Office Hours: T/Th 2:45--3:45PM BY 560)

(TA: Garrett Wolf. Office Hours: Wed: 3:30--4:30pm BY557AD)

1. Introduction [Aug 26, 2008]
   • Audio of the lecture 1

2. Information Retrieval start [Aug 28, 2008]
   • Audio of the lecture 2

   • Audio of the lecture 3 (Precision/recall; TREC; IR models; Text-ops; Brief review of inverted index; Boolean model; start of vector model

   • Audio of the lecture 4 [Sep 4, 2008] (types of web-search queries; bag of words model and distance metrics for it; vector similarity; tf/idf weighting; relevance feedback)

3. Correlation Analysis, dimensionality reduction and latent semantic indexing
   • Audio of the lecture on [Sep 9, 2008]. Correlation analysis--on document corpus (and query logs); Need for dimensionality reduction and LSI as a linear dimensionality reduction technique. LSI as a special case of LDA.

   • Audio of the lecture on [Sep 11, 2008]. Latent semantic indexing: The whole deal.

4. Indexing and Tolerant Dictionaries
   • Audio of the lecture on [Sep 10, 2008;makes up for the class of 16th]. Ranking documents with inverted indices; approximate ranking; tolerant retrieval and spelling correction; k-gram distance and edit distance. A little on the issues of distributed indexing

5. Doing IR on Web
   • Audio of the lecture on [Sep 23, 2008] Issues of adapting traditional IR to Web search. Crawler design. Web scale index constructin. Distributing index construction and the map-reduce parallelism in cluster computing

6. Social Networks
   • Audio of the lecture on [Sep 25, 2008]Using tags and anchor text to improve similarity computation on web pages. Need for page importance measures. (BIG) digression into traditional Social Networks. Applications of social networks (general and web-related). Measures of centrality and importance in social networks. Small world phenomena--Kevin Bacon game, Erdos number, Milgram experiment. Theoretical analysis of small world phenomena (uniform) random graphs

   • Audio of the lecture on [Sep 30, 2008]Small world phenomena in (uniform) random networks; comparing uniform random to real-world networks and seeing that the degree distribution of the former is Poisson while the latter is power-law. Characterization of Scale-free networks (as the networks whose degree distribution is powerlaw). generative models for scale-free distribution. Disruptions and attacks on scale-free vs. uniform-random networks. Efficient navigation in small-world networks.

7. Link Analysis to Predict Web-page Importance
   • Audio of the lecture on [October 2nd, 2008]Zipfian distribution of words; and its implication on lexicon growth (and Heap's law); a bit on Benford's law.

     Start of discussion on page-importance measures; desiderata for importance measures (and understanding why certain measures are redundant given other measures); importance of stability of importance. Discussion of Authroities/Hubs measure of importance; computing A/H values using power iteration; understanding why this computation in independent of the initialization values. A/H computation as a query-dependent importance measure.

   • Audio of the lecture on [October 7th, 2008] Continuation of the discussion of A/H. Making the adjacency matrix edge weights query sensitive. The issue of stability of A/H. Tyranny of Majority and the Bridge effect. Discussion that A/H can be done at query time or for the web-graph (although the original idea was mooted for query time). Start of page rank discussion. Connection between Markov Chains and page-rank computation. Pointing out that markov chains have unique stationary distribution only when there are no nodes or clusters without outgoing links (sink-nodes or sink clusters). Making the web matrix not have this.

   • Audio of the lecture on [October 9th, 2008] Page rank--reset distribution, and its possibly many uses; how pagerank is combined with similarity; robustness of link-importance measures w.r.t. adversarial collusion; pagerank variants--topic specific page rank, trust rank, recency rank--and how all of them play around with the reset distribution. Discussion of topic specific page rank. Start of discussion of trust rank--and propagation of trust in social networks,

   • Audio of the lecture on [October 14th, 2008]Trust propagation in social networks; discussion of Trust-Rank; Efficient computation of page rank. Removal of dangling nodes (but recomputing their page-rank later); Block-based methods for efficient computation; asynchronous iteration (i.e., using the page-rank values from different iterations together in updating the

8. Clustering (of search results)
   • Audio of the lecture on [Oct 23, 2008] Clustering and its applications in information retrieval. Exampls of search engines doing clustering (Clusty etc).
   • Audio of the lecture on [Oct 28, 2008] Clustering II--limitations and variations of K-means; Hierarchical clustering methods.

9. Text Classification
   • Audio of the lecture on [Oct 30, 2008] Fast paced introduction to classification learning with emphasis on text classification. k-NN, Rocchio and Naive Bayes learning techniques (NBC started)
   • Audio of the lecture on [Nov 4th, 2008] Naive Bayes continued; Laplacian Smoothing; Unigram model for Naive Bayes classifn of text docs; Feature selection using mutual information content. Feature selection vs. dimensionality reduction in unsupervised vs. classification scenarios. Start of Recommendation systems. Content-based vs. Collaborative Filtering systems. Viewing collaborative filtering in terms of users as vectors in item space, and person correlation coeff as the distance between users, and k-NN as the way to do recommendation.

10. Recommendation Systems
    • Audio of the lecture on [Nov 6th, 2008] Recommender systems; eliciting ratings; justifying recommendations; bag-of-bags NBC model for content-based filtering; Collaborative filtering ideas; Combining content-based and Collaborative Filtering; Seague into "semi-supervised learning"--and how to use unlabelled examples to improve learning accuracy (through EM-style improvement of the classifier)

11. Structure on the web
    • Audio of the lecture on [Nov 13, 2008]Challenges of acquiring, representing and using the structure on the web. Review of databases as an example of a traditional discipline that aims at managing data with full structure. Start of XML.
    • Audio of the lecture on [Nov 18, 2008]. XML standard, syntax of XML, DOM tree and XML data model; meaning in XML, Using XML structure in IR, XML as a data standard; how RDBMS can use an XML/XQUERY front-end; DTD and XSchema models; Overview of Xquery and how it differs from SQL.
    • Audio of the lecture on [Nov 20, 2008]. XQuery--use cases (XMP;SEQ;R;STRING etc.); IR-style querying on XML--indexing using Lexical trees; structured keyword querying etc; Semnatic Web Standards: RDF and RDF-Schema. Who annotates semantic web?

12. Information Extraction
    • Audio of the lecture on [Nov 25, 2008] Discussion on database-style vs. semantic-web style inferencing. Three approaches for reaching the semantic web dream; Discussion on folksonomies and collaborative curation; Information extraction as NLP-lite; Templated information extraction as undoing XML-->HTML conversion and wrapper generation. Discussion of semi-automated generation of wrappers; using inductive learning techniques (and pointing out that learning here is mostly with +ve examples; pointing that grammar induction is also like that; digression to how children learn)
    • Video of the make-up lecture on [Nov 26, 2008] Information extraction from unstructured text. First narrow-scope extraction--where we know what relations we are trying to extract. A tutorial discussion of the problems and approaches. Discussion of sliding-window and boundary-based extraction methods. Explanation of why joint extraction is the current direction. Discussion of open information extraction where the extraction system determines what facts it extracts (and extracts them). How the web can be used to assess the accuracy of the extracted patterns.

13. Information Integration

    End

    • Audio of the lecture on [Dec 2, 2008] Information Integration. Alteranative views of II. Three architectures for II--surfacing, mediator and warehousing. Dimensions affecting II architectures including source autonomy, horizontal vs. vertical integration, level of up-front effort etc., main phases of mediator architectures--source selection, source data access (wrappers), source/data alignment (schema mapping), query processing.
    • Audio of the lecture on [Dec 4, 2008] Query procesing in Information Integration. GAV/LAV models for connecting mediator and source schemas (and their relative tradeoffs). Query optimization issues in information integration (data aggregation). Computing and using source statistics. Use of source coverage and overlap statistics in source selection.
    • Audio of the lecture on [Dec 9, 2008] Query procesing in Information Integration continued. More on coverage/overlap statistics; discussion on local closed world assumptions as a qualitative analog of coverage statistics; latency statistics with respect to binding patterns; trust ranking of sources. Handling imprecision/incompleteness in databases. Bridging the DB/IR divide. Computing value similarities with super-tuples. Review of Structure on the Web. Review of the sememster and Sayanora with a corny ending.

14. Interactive review (or what students seem to remember from the course)

classes coming up

• 12/9: Final class

• 12/16: Final exam (12:10--2:00pm)

Todo

• Search contextualization..
• Measures for comparing ranked lists..