Tuesday, November 29, 2011

masochist special: cse471 seats for grad students...

Sorry for spamming the whole class, but a couple of students asked for overrides to get into the 598 section of cse471.

I told them to send me their name and student id, and I will let them know if more seats become available (a few might be
by the time the class starts). 

This is just to let others who may be interested but didn't think there is any use in asking, to know about this possibility.

I am always willing to try to make exception for masochists who want to suffer through multiple courses from me. 

cheers
Rao

Tuesday, November 15, 2011

On the question of whether relational schemas can capture books with multiple authors

In the class, I said that XMLschema allows us to easily capture books with multiple authors in contrast to RDBMS. 

Two of you pointed out that RDBMS can handle multiple authors by storing authors in a table along  with book IDs (say isbn numbers)

<isbn1, author11>
<isbn1, author12>
<isbn2,author21> 

etc, with the isbn number working as a foreign key into table.

While this way of doing it allows books with arbitrary number of authors,  it does not allow us to constrain the number of authors (say to be always
between 1 and 3). 

To do that, you will have to either use extra-RBDMS ideas such as triggers, or put upto three columns in the book table, resigned to the fact that the when there are
no second or third authors there will be null values in the column.  This is the price we pay for writing a single table for data that essentially is a union of three schemas--books with 
one author, books with two authors and books with three authors. It is here that XMLSchema differs by allowing specification of disjunctive schemas.

Rao




Colorless green ideas and universal grammar

Here is a mail I had sent once to my AI class (http://rakaposhi.eas.asu.edu/cse471
about the Colorless green ideas example. FYI.

Rao

=============

Colorless green ideas sleeping furiously (Chomsky, Universal Grammars etc. (Long.))


  • Tocse471-f06@parichaalak.eas.asu.edu
  • Subject: Colorless green ideas sleeping furiously (Chomsky, Universal Grammars etc. (Long.))
  • From: "Subbarao Kambhampati" <rao@asu.edu>
  • Date: Thu, 16 Nov 2006 23:14:06 -0700
  • Domainkey-signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:sender:to:subject:mime-version:content-type:x-google-sender-auth; b=DZcxkBhR/QwDSmP8JAKwyKQUzBNXY6RB/pBRq0QUXJY70J25FuBrGZDA6BivzEXgEGFmrFZb7nst+Q6ZMt0eyon7XcKSTFHAcSpPU9R9+pcKBWremnY+gW4IwIS5wrH74a3msuNVztExR4UMPpcogLfAd+iocBrXJ5hsEu7ZE6s=
  • Sendersubbarao2z2@gmail.com


As I mentioned in the class today, for the longest time, and by that I
mean, until well into late 50's, the conventional scientific wisdom
was that infants come into this world with a "Tabula Rasa" (blank slate) mind, and pick up everything by learning (supervised or
reinforced) and observation. The reigning doctrine was
"behaviorism"--you can condition/reinforce any behavior into any
organism. To behaviorists, children were but cuter (pavlovian) rats, and language acquisition was no different than a acquisition of maze
following skills. B.F. Skinner was the leading exponent of behaviorism
and was, in early fifties, writing book after book expounding on how
behaviorism can explain all sorts of human behavior.
[Skinner was such an ardent behaviorist that there was even an
apocryphal urban legend that said he raised his own daughter in a
"skinner box" to test his behaviorism hypotheses--see
http://www.snopes.com/science/skinner.htm ]

When Skinner came around to applying behaviorism explanations to
language acquisition and wrote the book on "Verbal Behavior", it was expected to further shore up the behaviorism doctrine, and become a
classic. What became a classic instead is a critical scholarly 1959
"review" of the book by a then little-known linguist named Noam
Chomsky (
http://cogprints.ecs.soton.ac.uk/archive/00001148/00/chomsky.htm ).

Chomsky essentially killed the book as well as much of the euphoria of behaviorism by an arugment that has since then come to be known as
the "poverty of stimulus" argument. He said that behaviorism and
stimulus/response reinforcement does not quite explain how it is that children seem to be able to generate sentences that they have never
heard of. In other words, there are not enough examples (hence a
poverty of "stimuli") for the children to learn entire
language--grammar and sentences together (even for children--such as mine--with overly talkative parents ;-) [You note that the argument
that something cannot be learned is being done in terms of the
the inordinate number of examples needed to learn it. As we saw in
the class, difficulty of learning tasks is measured in terms of "sample complexity".]

As an alternative explanation, Chomsky cited his own work on
"generative grammars"--a set of grammar rules that can generate
"grammatically correct" sentences from a language. He said that it must be the case that children come into the world with grammar rules
already in their head. Since the grammars of different world languages
are different, he posited that the children come into this world with
a "universal" grammar. Using the language being spoken around them,
they then set the "parameters" (or knobs, if you will) on their
universal grammar such that it becomes customized to the specific language environment they are in. Once they have the customized
grammar, they then are in the business of learning word sense (or
semantics). "Colorless green ideas sleep furiously" is one of
Chomsky's famous examples, which he uses to show that even small kids
with limited vocabularies can tell automatically whether a sentence is
grammatically correct. [Even here, in learning semantics, children
come into the world with pretty strong biases--including the so-called
"whole object hypothesis". If I point towards a big moving bus and say
"Bus", the kid hypothesizes that the whole big thing is called
bus--not just the wheels, or the hubcaps, or some subset of the
parts. Pretty strong bias, come to think of it--what if I said
"Driver" pointing towards the driver side of the bus?]

Chomsky of course went on to become the demi-god of cognitive science
in general, and mathematical linguistics in particular (and you obviously heard of him in your CSE 355, when you probably learned
about the Chomskian hierarchy of languages--which is in terms of their
grammar complexity). A lot of research has been done since Chomsky's
original work, to shore up the support for the universal grammar
hypothesis. It is so much of an accepted fact (dogma) now that it
(universal grammar) in turn is seen as yet another evidence that all
humans evolved from a common set of ancestors--as against evolving
separately and independently (the "Lucy" theory,
http://www.pbs.org/wgbh/evolution/library/07/1/l_071_01.html ; by the
way Don Johanson, who found Lucy skeleton in Ethiopia, is right here
at ASU--check out http://www.asu.edu/clas/iho/dcj.html ). The basic
argument is that the rank similarity of the human languages cannot be
explained without it. (Of course, there are much stronger arguments for the common ancestor theory--including the fact that we are all
same species--any man from anywhere in the world can mate with any
woman from anywhere in the world and produce healthy offspring).

So that is some of the background on the universal grammar. By the way, note that none of the above says that conditioning will not be
effective in changing ones behavior--you probably saw the recent press
accounts of the infamous Wendell Johnson orphan stuttering experiments
(http://www.jsonline.com/news/nat/jun01/stutter11061001.asp). All
Chomsky's argument says is that conditioning and reinforcement are
only part of the story and cannot alone explain language acquisition; evolution did a whole other part too.

Now for a couple of references. Probably the best-written lay-person
book on human language acquisition is Steven Pinker's "Language
Instinct"( http://www.amazon.com/exec/obidos/tg/detail/-/0060976519/104-1220170-3641559).
A very nice and eminently watchable 3-part PBS series on language
acquisition is "Human Language"
( http://equinoxfilms.home.mindspring.com/HLseries.html).

That is all for now. Now for more important things like Seinfeld rerun
already in progress.

Rao

Epilogue/Postscript: These days of course, a search on Chomsky on the
web is more likely to turn up references to his political views than
his linguistic ones. He is sort of a one-man vocal and loyal
opposition for many of the US government policies. For example, he
wrote one of the first dissenting "non-party line" opinions of the 9/11. Whether I agree with him or not, I am grateful that there is
someone unafraid of speaking his mind--especially in these days of
hyper-patriotism, where FBI thinks it normal to monitor you because
you are against war, and your freedoms are being re-defined as the ones Ashcroft hasn't yet gotten around to excising into the "Patriot
Act".

----------------
"I simply want to tell you that there are some men in this world who
were born to do our unpleasant jobs for us. Your father's one of
them."
[..] "I always thought Maycomb folks were the best folks in the world,
least that's what they seemed like."
"We're the safest folks in the world" said Miss Maudie. "We're so
rarely called on to be Christians, but when we are, we've got men like
Atticus to go for us."

--Miss Maudie and Jem talking about Atticus Finch, as
Scout and Dill look on..


============

Wednesday, November 9, 2011

[CSE 494] Regarding Extra Credit in Project Phase 3

I would like to clarify how the points will be awarded for extra credit in Phase 3. You can pick up a maximum of 10 points as extra credit, and it will be graded on a curve. You may attempt any number of extra credit problems from the problem statement, but please remember that points are awarded for a thorough analysis. Doing a little bit of three different extra credit questions will gain you fewer points than doing one problem thoroughly.

 

Thanks and Regards,

Sushovan De

 

Re: questions about today's class

This is a good question.

This is the difference between probability (which assumes that the model parameters are known, and infers/computes the probability of an event) and statistics (which first learns the parameters first).

In your example below, if you assume that the model parameters are given (e.g. saying that the coin is a fair one),  you can say that the next toss is going to come heads with half probability. If however you cannot assume the model--i.e., you have to learn/update it first, then 
the "likelihood" that the 2million heads out of 3million tosses is caused by a biased coin is much higher than that it is caused by a fair coin. So, you learn/estimate the biased probabilities first (the model parameters), and subsequently infer, using the new model, that the next toss will come heads with higher probability. 

Rao


On Wed, Nov 9, 2011 at 12:59 AM, Shaunak Shah <skshah7@asu.edu> wrote:
Hello Dr. Rao,

I have a question not from today's class but on the topic "need for smoothing" in classification. 
Why do we consider that if a coin comes up as Heads for 2 million times out of the 3 million tosses, then it should be a biased coin ?
Should we not think otherwise that the coin is not actually biased and is just having a bad day because we know for sure that the probability of Heads/Tails if 0.5.

--
Shaunak Shah


On Tue, Nov 8, 2011 at 7:10 PM, Subbarao Kambhampati <rao@asu.edu> wrote:
folks

 I couldn't call on several raised hands today. If you remember your questions, feel free to ask me by email and
I will respond. 
(and if I think the question is of general interest I will post my answer to the blog too)

rao



Tuesday, November 8, 2011

Complications and the Brazil reference..

In case you wondered about the Brazil reference..

rao

Re: questions about today's class


True value of the item for whom? Reserve price is the minimum price at which the seller is willing to part with the item. 

The whole point of selling is  that the item being sold is hopefully valued higher by the buyer than by the seller.

The tender-based auction you describe below is a first price auction. For first price auction, bidding by true values (i.e., submitting a tender that truly reflect what the max price you are willing to pay for it) is not a dominant strategy and is thus not encouraged. [If you have trouble coming to terms with it, remember that   doing the bidding in an ascending or descending price open auction gives the fairest price to the item in the long run. Second price auction emulates it using sealed bids]

Rao

ps: You have to first realize that there is no such thing as "true value" of an item independent of the buyers. The value of an item depends what what buyers are willing to pay for it (in other words, the worth of an item is what the market bears for it). an appraised value is basically only an approximation with some assumptions about buyer population. 

On Tue, Nov 8, 2011 at 7:46 PM, shubhendra singh <Shubhendra.Singh@asu.edu> wrote:
If there is a reserve price, isnt it indicating a true value of item? Like in India the tenders are filled in same way (closed sealed, ignoring corruption for a while). The governments sets the reserve price, people bid and the one who is willing to pay highest price is given the project, with the quotation price he gave. 
 
Shubhendra Singh


From: Subbarao Kambhampati <rao@asu.edu>
To: shubhendra singh <Shubhendra.Singh@asu.edu>
Sent: Tuesday, 8 November 2011 7:28 PM
Subject: Re: questions about today's class

I assume you are talking about "reserve price"--i.e., a price below which the you don't want to sell the item.

The way to handle reserve prices is to assume that the seller (in the case of search ads, the search enginer). is also bidding--with the minimum (reserve) prices. 

If the seller wins, then basically that means there are no bids from others that the seller is willing to take (and so basically the item is not sold).

Rao


On Tue, Nov 8, 2011 at 7:23 PM, shubhendra singh <Shubhendra.Singh@asu.edu> wrote:
In vickrey second auction, is minimum pricing of an item done? I mean for lets say query/keywords, we know the number of hits, we (thinking of we as search engine), we already know how important this query is, Do we decide the minimum quotation for it? 
 
Shubhendra Singh


From: Subbarao Kambhampati <rao@asu.edu>
To: Rao Kambhampati <rao@asu.edu>
Sent: Tuesday, 8 November 2011 7:10 PM
Subject: questions about today's class

folks

 I couldn't call on several raised hands today. If you remember your questions, feel free to ask me by email and
I will respond. 
(and if I think the question is of general interest I will post my answer to the blog too)

rao







Re: questions about today's class

I assume you are talking about "reserve price"--i.e., a price below which the you don't want to sell the item.

The way to handle reserve prices is to assume that the seller (in the case of search ads, the search enginer). is also bidding--with the minimum (reserve) prices. 

If the seller wins, then basically that means there are no bids from others that the seller is willing to take (and so basically the item is not sold).

Rao


On Tue, Nov 8, 2011 at 7:23 PM, shubhendra singh <Shubhendra.Singh@asu.edu> wrote:
In vickrey second auction, is minimum pricing of an item done? I mean for lets say query/keywords, we know the number of hits, we (thinking of we as search engine), we already know how important this query is, Do we decide the minimum quotation for it? 
 
Shubhendra Singh


From: Subbarao Kambhampati <rao@asu.edu>
To: Rao Kambhampati <rao@asu.edu>
Sent: Tuesday, 8 November 2011 7:10 PM
Subject: questions about today's class

folks

 I couldn't call on several raised hands today. If you remember your questions, feel free to ask me by email and
I will respond. 
(and if I think the question is of general interest I will post my answer to the blog too)

rao




questions about today's class

folks

 I couldn't call on several raised hands today. If you remember your questions, feel free to ask me by email and
I will respond. 
(and if I think the question is of general interest I will post my answer to the blog too)

rao

[CSE 494] Homework 4, question 1 typo

HW4 question 1 says:

Show the cluster dissimilarity measure (which is defined as the sum of the similarities of docs from their respective cluster centers).

It should read “the sum of the dissimilarities.

 

Thanks to the two of you who pointed this out.

 

Thanks and Regards,

Sushovan De

 

Monday, November 7, 2011

Added an *optional* homework on social networks as promised

It is in the homeworks list--note that this is *OPTIONAL* and will be counted as extra credit if you choose to do it (you will have to view the lectures I had sent earlier to 
make sense of the questions).

The homework will be due by the last day of the class. 

Rao

ps: Note that there will be a *required* homework that is also going to be due on that day. So if you want to do this one, it would be wiser to allocate time early on.


Midterm solutions...

Sorry for the delay in getting these to you.. I gave the undergraduates a chance to do the midterm again at home (as an extra homework) and I was waiting for them to 
be done before sending these.

Rao

Sunday, November 6, 2011

Current cumulatives

Folks:

 I am attaching the current cumulatives. I scaled the homework1 to 5points homework 2 to 6pt each, the google paper to 2pt--so a total of 11pt, the midterm to 20pt, the pop quiz to 2pt,
the projects to 10pt--thus a total of 44pt. 

The extra credit points are kept separate from the main cumulative.

If you see any entry errors, please let us know.

Rao

Friday, November 4, 2011

Google's Timelier Search Results

Google has tweaked its search algorithm to present results which are as recent as possible for a particular query. You can read more about this here http://www.informationweek.com/news/development/web/231902412

Preethi

Social networks lectures..

Folks:

 Because I decided to add lecture topics on Map-reduce and search advertising, I will have to skip one of the topics I normally cover. I reluctantly decided that it would be "Social Networks"--mostly because it is a self-contained 2-class topic for which video lectures from a previous offering are available (see below).

In addition to being quite engaging, this topic also comes bundled with a discussion on power laws and their importance. 

I would encourage you to watch the video lectures. I will also give optional homework questions on the topic. If you choose to do them, you can get extra credit.

Rao





===========
Social networks and their applications on the Web
  • 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. 
    [starts at 25min] 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).

Tuesday, November 1, 2011

Bi-annual Grade Anxiety Amelioration Program

Folks

 I have been meaning to send this mail earlier than the course withdrawal deadline, but got side-tracked into various deadlines. Better late than never.. 

I wanted to reiterate something I had said at the beginning of the semester about letter grades in this course. 

As I said, I don't go with 95-->A+; 90-->A  sort of scale. So, you shouldn't worry too much based just on your
cumulatives. 

I also recognize that people who can't keep up with the demands of the course leave early on (or don't register to begin with--thanks to the miracle of internet-word-of-mouth)--thus I normally don't have the
same kind of bottom distribution as might be present in other classes. 

My general advice to anyone who has come up to this point in the course and has done all assignments, and is enjoying the 
course, is to de-stress (note the "de" not "di") and continue (unless you need absolute guarantee of an A+). Your personal mileage of course may vary.

Rao


ps: If it helps, here are the final cumulatives and the actual reported grades for a previous offering of this course. The first 
three are 471 and the rest are 598. This is for illustrative purposes.
 There are *no* implicit guarantees that if you get those points, you will get those grades. If you have other questions, feel free to 
send me email.





 
88.40A+
79.57A
62.83B

 
91.97A+
90.61A+
87.55A+
85.76A
85.11A
84.34A
84.00A
83.88A
83.85A
81.27A-
79.92B+
78.76B+
78.63B+
74.76B
69.64B
69.35B

You might want to read this easy to read paper on Netflix prize before next class...

http://rakaposhi.eas.asu.edu/cse494/lsi-for-collab-filtering.pdf

it is in the readings and tells you how collaborative filtering and LSI style techniques are combined. We will talk only briefly about it next class

rao

office hours cancelled (again!)

Folks

 Due to a conflict I can't hold office hours today. If you were planning to meet with me, you can talk to me anytime tomorrow morning.

sorry
rao