Reading Notes for Week 10

19.Web search basics

The essential feature that led to the explosive growth of the web – decentralized content publishing with essentially no central control of authorship – turned out to be the biggest challenge for web search engines in their quest to index and retrieve this content.  And the search engine developed because of the spam detection in the early time.

Advertising as the economic model 

CPC model:clicking on the adver- tisement leads the user to a web page set up by the advertiser, where the user is induced to make a purchase.

Goto:for every query term q it ac- cepted bids from companies who wanted their web page shown on the query q. In response to the query q, Goto would return the pages of all advertisers who bid for q, ordered by their bids. Furthermore, when the user clicked on one of the returned results, the corresponding advertiser would make a payment to Goto

The search user experience

It is crucial that we understand the users of web search as well,and the more user traffic a web search engine can attract, the more revenue it stands to earn from sponsored search.
There are three web search queries:(1) informational    (2) navigational   (3) transactional.

Index size and estimation
It is  difficult to reason about the fraction of the Web indexed by a search engine, because there is an infinite number of dynamic web pages and the number of the web page is very large.

The relative sizes of the indexes is imprecise:
1).In response to queries a search engine can return web pages whose con- tents it has not (fully or even partially) indexed.

2).Search engines generally organize their indexes in various tiers and parti- tions, not all of which are examined on every search.

So that there is no single measure of index size. 

Construct the random page samples:

1. Random searches
2. Random IP addresses 

3. Random walks 

4.random queries

Near-duplicates and shingling
The Web contains multiple copies of the same content. By some estimates, as many as 40% of the pages on the Web are duplicates of other pages. 

The simplest approach to detecting duplicates is to compute, for each web page, a fingerprint that is a succinct (say 64-bit) digest of the characters on that page. Then, whenever the fingerprints of two web pages are equal, we test whether the pages themselves are equal and if so declare one of them to be a duplicate copy of the other.  

shingling 

Illustration of shingle sketches. We see two documents going through four stages of shingle sketch computation. In the first step (top row), we apply a 64-bit hash to each shingle from each document to obtain H(d1) and H(d2) (circles). Next, we apply a random permutation Π to permute H(d1) and H(d2), obtaining Π(d1) and Π(d2) (squares).  

21.Link analysis 

In this chapter author focus on the use of hyperlinks for ranking web search results. Such link analysis is one of many factors considered by web search engines in computing a compos- ite score for a web page on any given query.  

PageRank
Definition: first technique for link analysis assigns to every node in the web graph a numerical score between 0 and 1

In assigning a PageRank score to each node of the web graph, we use the teleport operation in two ways: 
(1) When at a node with no out-links, the surfer invokes the teleport operation. 
(2) At any node that has outgoing links, the surfer invokes the teleport operation with probability 0 < α < 1 and the standard random walk.

 Markov chains

 A Markov chain is characterized by an N × N transition probability matrix P each of whose entries is in the interval [0, 1]; the entries in each row of P add up to 1.

The PageRank computation:
⃗π P = λ ⃗π .
The N entries in the principal eigenvector π⃗ are the steady-state proba- bilities of the random walk with teleporting, and thus the PageRank values for the corresponding web pages.

Topic-specific PageRank.  

In this example we consider a user whose interests are 60% sports and 40% politics. If the teleportation probability is 10%, this user is modeled as teleporting 6% to sports pages and 4% to politics pages. 

Muddiest point for week 7

I don't have any muddiest points for this week.

Week 9 reading notes

Chapter 10 for MIR,

In this chapter, author introduced the user interface which  should help users to express their information needs and formulate queries. This chapter talks about recent development in this area.
There are three design rules for users:

1. Offer informative feedback
2. Reduce working memory load
3. Provide alternative interfaces for novice and expert users
4. Information access interfaces must contend with specialkinds of simplicity/power trade

How to judge a interactive system

An important aspect of human-computer interaction is the methodology for evaluation of user interface techniques. Precision and recall measures have been widely used for comparing the ranking results of non-interactive systems, but are less appropriate for assessing interactive systems. The standard evaluations emphasize high recall levels; in the TREC tasks systems are compared to see how well they return the top 1000 documents.

The procedure to process interaction system:

1. Start with an information need
2. Select a system and a collection to search on
3. Formulate a query
4. Send the query to the system
5. Receive the results in the form of information items
6. Scan, evaluate, and interpret the results
7. Either stop, or,
8. Reformulate the query and go to step 4

About the starting points:
    
One study found that for non-expert users the results of clustering were difficult to use, and that graphical depictions (for example, representing clusters with circles and lines connecting documents) were much harder to use than textual representations (for example, showing titles and topical words, as in Scatter/Gather), because documents' contents are difficult to discern without actually reading some text .

About the query specification:
Boolean queries are problematic because the basic syntax is counter-intuitive. 
Solutions to solve this problem are :1. allow users to choose from a selection of common simple ways of combining query terms 2. provide a simpler or more intuitive syntax.

Visualization For Text Mining:

One of the most common strategies used in text mining is to identify important entities within the text and attempt to show connections among those entities. 

Visualizing Document Concordances And Word Frequencies

In the field of literature analysis it is commonplace to analyze a text or a collection of texts by extracting a concordance : an alphabetical index of all the words in a text, showing those words in the contexts in which they appear. The standard way to view the concordance is to place the word of interest in the center of the view with “gutters” on either side, and then sort the surrounding text in some way.

Visualizing Literature And Citation Relationships

This information is used to assess the importance of the authors, the papers, and the topics in the field, and how these measures change over time. 

Some more recent approaches have moved away from nodes-and-links in order to break the interesting relationships into pieces and show their connections via brushing-and-linking interactions.

Reading notes for week6

I realize that I missed some reading notes of the paper required for the last weeks and I've read the chapter 9 in the last week, so I decided to bring some notes for the previous papers.

Cumulated Gain-Based Evaluation of IR Techniques

In this paper, the author presented us something about the measurements of the novel, which compute the cumulative gain the user obtains and examine the retrieval result up to a given ranked position.

And large amount of the output has been confused by the users for a long time when using the IR system.

There are three new evaluation measures. The firs one accumulates the relevance scores of retrieved documents along the ranked result list. The second one is similar but applies a discount factor on the relevance scores in order to devaluate late-retrieved documents. The third one computes the relative-to-the-ideal performance of IR techniques. An essential feature of the proposed measures is the weighting of documents at different levels of relevance. 

For example. the discounted cumulated gain:A discounting function is needed that progressively reduces the document score as its rank increases but not too steeply to allow for user persistence in examining further documents. A simple way of discounting with this requirement is to divide the document score by the log of its rank.

Relevance Judgments:Possible differences between IR techniques in retrieving highly relevant documents might be evened up by their possible indifference in retrieving marginal documents. The net differences might seem practically marginal and statistically insignificant.

Moiddest Point for week 6

In pooling method we talked in the Monday, you mentioned use top n documents form each search result to build a pool for judgment, what I wanna ask is that how do you define the number n is the most proper.

• 
  

Week 5 Reading Notes

Chapter 10 & Chapter 11

Most of the time the Chapter 10 id talking about the XML and its use in the encoding the document and the text. An XML document is an ordered, labeled tree, each node of the tree is an XML element and is writteen with an opening and closing tag. XPath is a standard for enumerating path in an XML document collection.
Then the author mentioned some challenges that make structured retrieval(the collection consists of structured documents and queries are either structured).The first challenge in structured retrieval is that users want us to return parts of documents (i.e., XML elements), not entire documents as IR systems. So,it will use one of the useful principle:Structured document retrieval principle. When I read through the paper, I were impressed by one method , it is we can use one of the largest elements as the indexing unit.

The Picture is a example of speration of a Xml document using the vector space model. We can interpret all queries as extended queries – that is, there can be an arbitrary number of intervening nodes in the document for any parent- child node pair in the query.

We ensure that retrieval results respect this preference by computing a weight for each match. A simple measure of the similarity of a path cq in a query and a path cd in a document is the following context resemblance function CR

In the Chapter12, the author introduces more systematically introduce this probabilistic approach to IR, which provides a different formal basis for a retrieval model and results in different techniques for setting term weights.we can straightforwardly start to estimate the probability of a term t appearing in a relevant document P(t|R = 1), and that this could be the basis of a classifier that decides whether documents are relevant or not.  

Binary Inde- pendence Model: is exactly the same as the multivariate Bernoulli Naive Bayes model.

Under the BIM, we model the probability P(R|d, q) that a document is relevant via the probability in terms of term incidence vectors P(R|⃗x,⃗q). Then, using Bayes rule as described above.
In probability estimates in practice,it is plausible to approximate statistics for nonrelevant documents by statistics from the whole collection.

Okapi BM25: a non-binary model:The BM25 weighting scheme, often called Okapi weighting, after the system in which it was first implemented, was developed as a way of building a probabilistic model sensitive to these quantities while not introducing too many additional pa- rameters into the model

muddiest point for week 5

I am quite confused about the language model. Is it based on the vector space model. If we have the same document and can we construct different language model?