Friday, December 2, 2011

DUE: 12/6: Mandatory Interactive Review Blog qn (You should post your answer as a comment to this thread )


"List five nontrivial ideas you came to appreciate during the course of this semester"
(You cannot list generic statements like "I thought pagerank was cool".  Any cross-topic connections
you saw are particularly welcome. )

Note that you must post your response as a comment to this particular message on the class blog. 
All comments must be done by the beginning of Tuesday's class (12/6). 

If you have forgotten what we have done, see the class home page for a description. 


Rao
---

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.))


  • To: cse471-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=
  • Sender: subbarao2z2@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