Statistics 4240 - Data Mining

Florence Nightingale article...


http://www.sciencenews.org/view/generic/id/38937/title/Math_Trek__Florence_Nightingale_The_passionate_statistician

A couple of interesting articles (from Jaclyn)

http://www.nytimes.com/2008/11/23/magazine/23Netflix-t.html?_r=1&ref=magazine
http://www.nytimes.com/2008/11/18/opinion/18salins.html?scp=1&sq=%22the%20test%20passes%20colleges%20fail%22&st=cse

Is it reasonable to evaluate the predictive performance of bagged regression trees using cross validation? For example, for each fold, you create B bootstrap samples from the training data (non hold out data), fit a regression tree to each one, then take the average of the B predictions on the hold-out data (call this the bagged predictions). Do this for each fold then take the average of the squared difference between bagged predictions for each fold and the actual values to come up with your estimate of predictive accuracy. Does anyone ever do this?

Yes, this is certainly something people do, although its obviously very expensive.

I think I noted an R function called "standardize" on a few people's homework assignments. I should have said the R function "scale." D.

Can you confirm that this is the schedule for the rest of the class?
Thurs 11/20 - regular class
Tues 11/25 - regular class
Thurs 11/27 - no class (Thanksgiving)
Tues 12/2 - class presentations
Thurs 12/4 - class presentations
Tues 12/16 final exam - the registrar's website says 7:10pm - 10:00pm

This is correct although I have not lined up
the presentations yet so will probably do a mix
of regular class and presentations at least on the
2nd. I'm actually out of town on Dec 4th and have
not yet decided what to do about class that night.



If we are turning in our projects on paper, is it okay to give them to you on 12/2?

Yes.


When will you let us know who is giving a presentation and on which day?

I'll work on this in the next few days.

Friday Nov 14th, 2008
11:00am - 12:00pm
Interschool Lab, 7th Floor Schapiro CEPSR

Dr. John Hershey
Speech and Language Algorithms department
IBM T. J. Watson research center
http://domino.research.ibm.com/comm/research_people.nsf/pages/hershey.index.html

"Factorial Hidden Markov Models, Super-Human Speech Separation, and
Word Confusability"

ABSTRACT
In modeling complex phenomena such as speech, it is natural to
consider interactions between different models. In this talk we
consider two different types of interaction that share a common
computational structure. One stems from the problem of single-channel
speech separation, in which two or more speech signals have to be
extracted and recognized from an acoustic mixture. Another arises in
the problem of estimating word confusability, the probability of
mistaking one spoken word for another. Both of these problems, it
turns out, can be reduced to inference in factorial hidden Markov
models.

In the word confusability problem, commonly used divergence measures
such as the Kullback-Liebler divergence and Bhattacharyya distance are
point of departure. Since these divergence measures are intractable
for hidden Markov models, we introduce variational bounds to reduce
the computation to closed-form divergences between components. In the
case of Bhattacharyya divergence the resulting approximation has the
same structure as a two-dimensional factorial HMM. We apply the
resulting forward algorithm to a simple word confusability task,
discuss other uses for HMM divergences and future directions for this
work.

In the speech separation problem, we have models of the grammar and
acoustics of different speakers, which are combined according to an
acoustic interaction model. Unfortunately, the time complexity of
exact inference in the resulting factorial hidden Markov model is
exponential in the size of the grammar and the number of sources. To
surmount this problem we propose a linear-time loopy belief
propagation algorithm. We show that it achieves super-human speech
separation in the PASCAL speech-separation challenge, in a fraction of
the time required for exact factorial HMM inference.

BIOGRAPHY
John Hershey received the BS degree (1992) in cognitive science from
the University of California, Los Angeles and the PhD degree (2004) in
cognitive science from the University of California, San Diego, where
he was a founding member of the Machine Perception Laboratory. His
doctoral thesis explored the use of generative graphical models for
speech enhancement, face tracking, and combinations of the two. During
his time at UCSD, he interned at Mitsubishi Electric Research Labs in
Cambridge, Massachusetts in 2001, and in the Machine Learning and
Applied Statistics Group at Microsoft Research in Seattle in 2003. In
2004, he spent a year as a visiting researcher in the Speech Group at
Microsoft Research. Since 2005, he has been at IBM T. J. Watson
Research Center in New York, where he is a research staff member in
the Speech Algorithms and Engines group.
_______________________________________________

What exactly are you looking for in terms of output for the homework?

Your code for part 1. For part 2, a description of what you found for
different values of k. For part 3, code and a description of whatever you
decided to try.

A few questions about the nstart argument for R's built-in kmeans function:
Am I correct that nstart is the number of times it randomly picks centers? So if you call kmeans with a k of 3, and an nstart value of 10, it will randomly generate 3 cluster center starting points, make cluster assignments, and then repeat that 9 more times?

Correct.

If so, how exactly does it choose which set of assignments to use? It just returns the solution that occurs most often? What if there was a tie in terms of the number of times each set of cluster assignments occurred?

It returns the solution with the smallest within-cluster MSE.

Also, should our kmeans algorithm include an nstart argument? Mine seems to be performing similarly to the one that's built in to R without one (meaning mine is only selecting random centers once).

Its a nice feature but not one that is required.

Is it okay to use R's kmeans function for part 2 of the homework?

I'd rather you didn't use it. The whole idea is to learn how
the algorithm really works.

For homework #3, should we standardize all variables before running k-means?

That's probably a good idea

What is the good size of data for class project?

That depends on the problem you are trying to solve. There isn't any particular minimum size.

In class, I recall you mentioned there were software implementations for ridge and lasso that are much faster than R.  You also mentioned that, when doing text categorization, the data structures are set up differently from the standard "spreadsheet view" to handle sparse data.  Could you post links on where we can find references or software for each of these topics?  Thanks,


For logistic regression, two reasonable options are:

http://www.bayesianregression.com
http://www.stanford.edu/~boyd/l1_logreg/

For regular regression..

http://www.stanford.edu/~boyd/l1_ls/ (matlab - doesn't scale so well)
http://www-stat.stanford.edu/~hastie/Papers/LARS/ (R - doesn't scale so well)

http://www.maths.uwa.edu.au/~berwin/software/lasso.html (I haven't
actually used this)


One sparse data format often used in sparse, high dimensional
applications is described at http://stat.rutgers.edu/~madigan/BBR.
In turn this is modeled on http://svmlight.joachims.org/

For homework #3, do you want us to explore different data frames? The bank data includes dummy variables. Can we use dummies in kmeans?

Different data frames? You mean different variables? That would be interesting but not required. You can code the dummy variables as 0-1 and include them. Or you can do something fancier with them if you wish.

I'm working on the K-means clustering algorithm and my implementation seems to be hitting local minima for the within cluster sum of squares. You mentioned in your slides a couple of ways of dealing with this, but didn't really go into any specific details. Do you have any links to good resources for deterministic annealing and/or genetic algorithms as they apply to this problem? There is no mention of them in the book, I've noticed. Also, in its discussion of the k-means algorithm, the book says that the Hartigan and Wong algorithm "ensures that there is no single switch of an observation from one group to another group that will decrease the objective." (p. 462) But they don't say how this is done. R's implementation clearly does this, but the source is difficult to get at (seems to be FORTRAN, too). Can you offer any suggestions?

The details of the Hartigan-Wong algorithm are here. I don't have much experience with fancier kmeans algorithms but if you search for "k means annealing" on google scholar you get tons of stuff. Running k-means from different starting points is usually a reasonable approach.