A cake for the new doctor... Raju Balakrishnan's Ph.D. Defense tomorrow (7/19; 10AM, BY528): Trust and Profit Sensitive Ranking for the Deep Web and On-line Advertisements

Dear all:

 Raju completed his defense successfully and is a newly minted "Dr". Please stop by the AI lab to celebrate with cake ;-)

Rao

---------- Forwarded message ----------
From: Subbarao Kambhampati <rao@asu.edu>
Date: Wed, Jul 18, 2012 at 5:36 PM
Subject: Raju Balakrishnan's Ph.D. Defense tomorrow (7/19; 10AM, BY528): Trust and Profit Sensitive Ranking for the Deep Web and On-line Advertisements
To: Rao Kambhampati <rao@asu.edu>

Dear all

 This is a reminder that  Raju Balakrishnan will be defending his PhD dissertation tomorrow (7/19 Thursday). Raju's work on deep web source selection and computational advertisements has garnered him a Yahoo! Key Scientific Challenges award (2009) as well as a WWW best poster award (2010), in addition to several archival publications and a lucrative job. 

You are all cordially invited to his defense.

Sincerely

Rao

Trust and Profit Sensitive Ranking for the Deep Web and On-line Advertisements

By

Raju Balakrishnan

Thursday, July 19, 2012

10:00 am

Brickyard 528

Subbarao Kambhampati, Chair

Yi Chen

AnHai Doan (U. Wisconsin, Madison)

Huan Liu

Abstract

Ranking is of definitive importance to both usability and profitability of web information systems. While ranking of

results is crucial for the accessibility of information to the user, the ranking of online ads increases the profitability

of the search provider. The scope of my thesis includes both search and ad ranking.

I consider the emerging problem of ranking the deep web data considering trustworthiness and relevance. I

address the end-to-end deep web ranking by focusing on: (i) ranking and selection of the deep web databases

(ii) topic sensitive ranking of the sources (iii) ranking the result tuples from the selected databases. Especially,

assessing the trustworthiness and relevances of results for ranking is hard since the currently used link analysis

is inapplicable (since deep web records do not have links). I formulated a method---namely SourceRank---to

assess the trustworthiness and relevance of the sources based on the inter-source agreement. Secondly, I extend

the SourceRank to consider the topic of the agreeing sources in multi-topic environments. Further, I formulate a

ranking sensitive to trustworthiness and relevance for the individual results returned by the selected sources.

For ad ranking, I formulate a generalized ranking function---namely Click Efficiency (CE)---based on a realistic

user click model of ads and documents. The CE ranking considers hitherto ignored parameters of perceived

relevance and user dissatisfaction. CE ranking guaranteeing optimal utilities for the click model. Interestingly, I

show that the existing ad and document ranking functions are reduced forms of the CE ranking under restrictive

assumptions. Subsequently, I extend the CE ranking to include a pricing mechanism, designing a complete

auction mechanism. My analysis proves several desirable properties including revenue dominance over popular

Vickery-Clarke-Groves (VCG) auctions for the same bid vector and existence of a Nash equilibrium in pure

strategies. The equilibrium is socially optimal, and revenue equivalent to the truthful VCG equilibrium. Further, I

relax the independence assumption in CE ranking and analyze the diversity ranking problem. I show that optimal

diversity ranking is NP-Hard in general, and that a constant time approximation algorithm is not likely.

Raju Balakrishnan's Ph.D. Defense tomorrow (7/19; 10AM, BY528): Trust and Profit Sensitive Ranking for the Deep Web and On-line Advertisements

Dear all

 This is a reminder that  Raju Balakrishnan will be defending his PhD dissertation tomorrow (7/19 Thursday). Raju's work on deep web source selection and computational advertisements has garnered him a Yahoo! Key Scientific Challenges award (2009) as well as a WWW best poster award (2010), in addition to several archival publications and a lucrative job. 

You are all cordially invited to his defense.

Sincerely

Rao

Trust and Profit Sensitive Ranking for the Deep Web and On-line Advertisements

By

Raju Balakrishnan

Thursday, July 19, 2012

10:00 am

Brickyard 528

Subbarao Kambhampati, Chair

Yi Chen

AnHai Doan (U. Wisconsin, Madison)

Huan Liu

Abstract

Ranking is of definitive importance to both usability and profitability of web information systems. While ranking of

results is crucial for the accessibility of information to the user, the ranking of online ads increases the profitability

of the search provider. The scope of my thesis includes both search and ad ranking.

I consider the emerging problem of ranking the deep web data considering trustworthiness and relevance. I

address the end-to-end deep web ranking by focusing on: (i) ranking and selection of the deep web databases

(ii) topic sensitive ranking of the sources (iii) ranking the result tuples from the selected databases. Especially,

assessing the trustworthiness and relevances of results for ranking is hard since the currently used link analysis

is inapplicable (since deep web records do not have links). I formulated a method---namely SourceRank---to

assess the trustworthiness and relevance of the sources based on the inter-source agreement. Secondly, I extend

the SourceRank to consider the topic of the agreeing sources in multi-topic environments. Further, I formulate a

ranking sensitive to trustworthiness and relevance for the individual results returned by the selected sources.

For ad ranking, I formulate a generalized ranking function---namely Click Efficiency (CE)---based on a realistic

user click model of ads and documents. The CE ranking considers hitherto ignored parameters of perceived

relevance and user dissatisfaction. CE ranking guaranteeing optimal utilities for the click model. Interestingly, I

show that the existing ad and document ranking functions are reduced forms of the CE ranking under restrictive

assumptions. Subsequently, I extend the CE ranking to include a pricing mechanism, designing a complete

auction mechanism. My analysis proves several desirable properties including revenue dominance over popular

Vickery-Clarke-Groves (VCG) auctions for the same bid vector and existence of a Nash equilibrium in pure

strategies. The equilibrium is socially optimal, and revenue equivalent to the truthful VCG equilibrium. Further, I

relax the independence assumption in CE ranking and analyze the diversity ranking problem. I show that optimal

diversity ranking is NP-Hard in general, and that a constant time approximation algorithm is not likely.

5x7 Folded Card

Dazzling Lime Print 5x7 folded card

Create cute birthday cards, valentines and more at Shutterfly.com.

View the entire collection of cards.

Thanks for all the ballot stuffing ;-)

To 

  The students who took classes with me in 2011-12:

Dear all:

 I have been told by the department that I was voted by the students as the best teacher in CSE for 2011-12 year. 

Assuming that my constituency would have been the students who took classes with me this year, which includes you, I would like to thank you for all the  energetic ballot stuffing ;-)

I am supposed to get the (no doubt very substantial cash)  award on Monday during the CIDSE awards shindig.

Cheers

Rao

 

Re: CSE 598 : IR -- Dating app based on Amazon, Netflix, Spotify, And Facebook Data

Thanks for letting me know!

 Since the lecture with that idea is recorded and is on youtube,

I wonder if I can get these Yokels to fork over some pre-IPO options for me.. 

Rao 

On Wed, Mar 28, 2012 at 7:06 PM, Abhishek Kumar <akumar66@asu.edu> wrote:

Dear Prof,

I took the IR course offered by you last semester.

In one of the lectures related to collaborative filtering, you were talking about an idea that

Amazon can use collaborative filtering to suggest soul mates.

There is a new app, Yoke, which is based on that idea.

http://techcrunch.com/2012/03/28/yoke/ 

Thanks
Abhishek Kumar
Graduate Student
Arizona State University
Mobile: 480-381-0004
 

Streaming videos of cse494 (albeit a bit late for you ..)

Thought this may be of interest to some of you. 

I was able to upload most of the cse494 videos to youtube. They are now linked to the class page http://rakaposhi.eas.asu.edu/cse494 and are streamable and random-accessible. 

Rao

teaching evaluations...

Dear all:

 Hope you had a good (if all too short) break; I certainly did roaming the backwaters of Kerala.

I just got your teaching evaluations for the course and it looks like the course was received  well. 

Thanks to the ~75% of you who took time to provide feedback and comments; 

I will try my best to take them into account (except perhaps for the "the course is hard" variety ;-). 

[And as for the other ~25%, they should be riddled with guilt for not taking part ;-)]

 It is my somewhat quixotic custom to make the complete evaluations--warts and all--available to 

the class students for a limited time.  So, here goes:

http://rakaposhi.eas.asu.edu/cse494/f11-598-evals.htm

http://rakaposhi.eas.asu.edu/cse494/f11-ug-evals.htm

If you have any further comments/questions you need to get off your chest, feel free to email me. Otherwise, this will likely be the last mail on this list.

Wishing you all a great new year..

Rao

The extra credit points

Here are the extra credit points 

For project extra credit, the points you got are normalized by the total for the regular project and multiplied by the weight

(so if you get 10 extra credit points on a project that is graded for 50 pts, and counts for 10% of your grade, then you get (10/50)*10 = 2 cumulative points)

The UGs got extra credit for doing the midterm at home (it was counted as 3.5 cumulative points)

The UGs also got extra credit if they did the last question on the final ( which counts for [x/100]*15  cumulative points)

The social networks extra credit homework counted for 3.5 cumulative points.

All said there were a maximum of  14 cumulative points that one could have amassed. 

This will likely be the last mail about the class cumulatives. You should be able to find your letter grades from the registrar as and when they get posted.

Wishing you all a wonderful (if all too brief) holiday season. 

Rao

(hopefully) final cumulatives

Folks

 Here are the final cumulatives for the class.  They contain your final exam marks; project 3 and demo marks and a participation grade. Let us know if you find any errors anywhere

[Note that the final was graded out of 115 for grads and 100 for UG--with the answers to the paper reviews kept as extra credit portion]

I computed the regular cumulative with 5% for participation, 25% for homeworks, 30% for exams and 40% for project. I will try some other weighted averages and take the maximum among those.

I have not computed the extra credit part---given that the grading is relative, adding extra credit to the total at the outset makes extra credit "mandatory". My idea is to set the thresholds first based on regular marks and

then consider bumping your grade based on your extra credit points. 

I normally ask the students at the top of the ladder in the 494 and 598 sections to suggest grade cutoffs for their respective sections. I offer the same chance to the current two top candidates. 

(of course, this is only advisory--but does give me useful input in that the students know the comparative level of difficulty of the class).

regards

Rao

Submitting the final

Folks

 You can submit the final in hard copy by just pushing it under my door (BY 560). If you come after 8AM, the department front desk should be open and you can also submit it there telling them that it is for me.

Please don't speed on the roads on my account; +/- a few minutes is fine. 

Rao

Clarification re: I.2

More than one person seems to have been confused by the word "learning"  in I.2 below. 

What I am asking is whether the information extracted by most IE (information extraction) methods are meant to be stored in RDF or OWL format.

 Semantic web has RDF and OWL standards for specifying structure. Information 

extraction aims to extract structure rather than wait for it being manually specified. Are 

current day IE approaches aimed at learning what is normally specified in RDF or in 

OWL? Why?

Re: Clarification on Qn VIII

yes both are per click.

Rao

On Sun, Dec 11, 2011 at 1:32 PM, Kalin Jonas <kjonas@asu.edu> wrote:

I notice you replaced A's pay rate with per-click, did you also mean to replace B's rate with per-click?

On Sat, Dec 10, 2011 at 10:21 PM, Subbarao Kambhampati <rao@asu.edu> wrote:

In the first part of the question VIII, please change "per impression" to "per click" (basically, the advertiser won't pay

unless the user actually goes to the advertiser's page by clicking on the ad)

VIII. [3+3] A search engine has bids on advertisements from two advertisers, A and B. 

Assume that A and B want their ads to be shown w.r.t the same query Q.  Suppose further 

that the search engine cannot show more than one advertisement. A is willing to pay 20c 

per XXimpressionXX click   . B is willing to pay 10c per impression.  How should the search engine 

decide as to whose ad it should show? Pay particular attention to whether the  search 

engine has all the information to make a decision, and if it needs more information, how 

it will get it.

Clarification on Qn VIII

In the first part of the question VIII, please change "per impression" to "per click" (basically, the advertiser won't pay

unless the user actually goes to the advertiser's page by clicking on the ad)

VIII. [3+3] A search engine has bids on advertisements from two advertisers, A and B. 

Assume that A and B want their ads to be shown w.r.t the same query Q.  Suppose further 

that the search engine cannot show more than one advertisement. A is willing to pay 20c 

per XXimpressionXX click   . B is willing to pay 10c per impression.  How should the search engine 

decide as to whose ad it should show? Pay particular attention to whether the  search 

engine has all the information to make a decision, and if it needs more information, how 

it will get it.

one of the search engine projects from the class

Hi all:

 Sushovan, the TA, came and asked me to check out the project by one of the students in the class. 

Here is the URL--  http://irproject.elasticbeanstalk.com/

The project is by Sathishkumar Poornachandran

The student seems to have done a pretty slick job--with online query completion thrown in. If only he had the page snippets too ;-)

Rao

 

Final released...

Folks

 The CSE494/598 Take home final is released. You can access it from the URL http://rakaposhi.eas.asu.edu/cse494/final-f11.html 

Please carefully read and follow the instructions about the honor-code that applies to this take home. You are essentially allowed only to 

use the class notes, lectures, and ask me for clarifications. NO discussions with other humans or web-trawling for answers is allowed.

Your signature on the first page serves as your oath that you followed these rules. 

Please also check back this URL for any errata/modifications to the final (I will also send emails if there are any errors found).

Rao

(Released 8:35AM on Thursday 12/8; Due back in hardcopy Monday 12/12 9AM)

Heads up on the last question of the exam..

I have the exam pretty much set--I will release it tomorrow morning.

For 598 students who are night owls, here is the last question on the exam (which is only required for 598 students; and is extra-credit for 494 ones).

You can get a head start if you want.

=======

 

 [IX] [15pt] [Required for 598 students. Optional-extra-credit for 494 ones]

For the purposes of this question, assume that you are planning to pick a topic for your next research paper (presumably because you want to make progress towards your dissertation/thesis). Here is the link to the proceedings of WWW 2011

http://www.www2011india.com/proceeding/forms/pcontents.htm

 

Suppose you are trying to work on extending one of these papers. Select a paper. Read at least the abstract and introduction. Now, use only the space given to answer:

 

·       In your words write down what the paper is trying to do and how it is related to what we discussed in the course. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

·      What follow-on work would you be interested in doing on the paper and why?

 

 

 

 

 

 

 

 

 

[Corrected] Re: Solutions for the social networks extra credit homework posted

There was an error in the solutions that were posted; please download the link again to get the correct version

rao

On Wed, Dec 7, 2011 at 11:57 AM, Subbarao Kambhampati <rao@asu.edu> wrote:

I didn't have the solution for the last question. basically, you should see a straight line (or close to one) if you plot

# citations w.r.t. rank. 

http://rakaposhi.eas.asu.edu/cse494/f11-socnet-hw-solns.pdf

The slope of that closest fit line is the r

Rao

final exam will be take home

Folks

 This is just to confirm that the final will be take-home. The exam itself will be almost in the in-class style, you will have to answer questions in the

space provided, and submit it.  You just get to do it at home. 

I am planning to release it by tomorrow (Thu), and it will be due Monday morning. 

Rao

fulton course evaluations

Folks

 I understand that today is the last day for the fulton course evaluations. You should have received mails on it.  I would encourage you all to take time to do them--as those are the most useful feedback I get about how the course went.

 (Just so you know, instructors will get those only sometime in January--*and* they will be anonymous--so you don't need to worry that it might affect your grade ;-)

cheers

Ra

Solutions for the social networks extra credit homework posted

I didn't have the solution for the last question. basically, you should see a straight line (or close to one) if you plot

# citations w.r.t. rank. 

http://rakaposhi.eas.asu.edu/cse494/f11-socnet-hw-solns.pdf

The slope of that closest fit line is the r

Rao