Homework 2--three questions added. Due Thursday in class

Folks:
  I added three questions to the homework--one on social networks, one on string distances and one on inverted indexes. These questions are not exactly very hard but are put there to make you look at the notes.

the homework as a whole is due on Thursday 10/9 in class

Rao

Where the Web is Going: Web 2.0, 3.0 and Beyond

Interesting round table style panel on Web 3.0 and beyond...

http://link.brightcove.com/services/link/bcpid980795693/bctid1790936412

(If you watch far enough through, you'll notice Peter Norvig happens to mention his spelling corrector that was shown in the "Indexing and Tolerant Dictionaries" lecture)

Beyond Text Ranking

I am personally more interested in applying ranking and retrieval techniques developed in IR for image ranking. In particular, I am working on a project which, given a query biological image, the task is to find similar images in the database. You can find more information about this project at: http://www.flyexpress.net/

Recently, it seems that people is beginning to apply text retrieval techniques to image ranking and I noticed two papers which I found interesting and want to share with you.

@article{ 10.1109/TPAMI.2008.121,
author = {Yushi Jing and Shumeet Baluja},
title = {VisualRank: Applying PageRank to Large-Scale Image Search},
journal ={IEEE Transactions on Pattern Analysis and Machine Intelligence},
volume = {30},
number = {11},
year = {2008},
pages = {1877-1890},
}

@ARTICLE{Sivic:PAMI08,
AUTHOR = {J. Sivic and A. Zisserman},
TITLE = {Efficient Visual Search of Videos Cast as Text Retrieval},
JOURNAL = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
VOLUME = {},
NUMBER = {},
PAGES = {},
YEAR = {2008},
NOTE = {In press},
}

Shuiwang

added new slides at the beginning of page-importance measures lecture

Folks:

 I revised the first slide and added a new second slide in the  page-importance measures. I encouarge you to look at them.

rao

Regarding Page Importance

Sir,

When you were discussing about page importance you mentioned about the amount of access a page gets as one of the criteria for evaluating importance. I have 2 questions on that.

1. There are lots of websites which display the number of visitors for that page. How do they compute that?
2. Is there any relevance to that for computing the page rank for that page? If yes can this make the website owners to increase the page rank of their website by logging in again and again themselves and make it to the top of the rank?

On the question of when eigen values are guaranteed to be positive (and the property of positive definiteness)

There was a question in the class (by Dmitry I think) as to when can we be sure that  eigen values of a matrix are all positive.

Here is the answer

 All symmetric matrices are guaranteed to have real valued eignen values, but are not all guaranteed to have positive eigen values.

Having positive eigen values turns out to be closely related to a *very* important property of matrices called "positive definiteness"

However, if the symmetric matrix M under consideration can be written as B*B'  where B is a non-singular matrix (i.e., has non-zero determinant),
then it is guaranteed to have +ve eigen values. (Notice that the matrices we power-iterated on in A/H computation are of this form).

-------------

While we are at it, we should note that the property of having positive eigen values is intimately linked to another very deep and useful property called
"positive definiteness"

A matrix M is called positive definite, if for *any* vector u,

 u * M * u' > 0  (it is called positive semi-definite if  "greater than" is replaced by "greater than or equal to")

It turns out that M is +ve definite if and only if it has all positive eigen values (you can sort of  see the "if" case in terms of viewing vector/matrix multiplication in terms of
stretching vector's projections in the eigen vector directions by the amount equal to eigen values).


cheers
Rao

Search on google's 2001 index

hi all

If you all dont know yet..google has put up its 2001 index for searching as a means to celebrate its 10th birthday..for searching back in time.. you can visit 

http://www.google.com/search2001.html 

and for more on their 10th birthday, visit 

http://www.google.com/tenthbirthday/

I searched for apple ipod and got 36 documents as results with none of them pointing to apple.com