Saturday, October 27, 2012

Feature selection and linear modeling

...being a test of the Knitr document generation tool for R.

library(glmnet)

Let's give the glmnet package a little workout. We'll generate data for a bunch of features, some of which yield a response. Many of the features are unrelated to the response. Of course, we'll inject some noise into the data, too.

generate.data <- function(n=1000, m=5,
      sig.features=1:5, noise.level=0.10) {

  # create bogus feature matrix
  features <- matrix(runif(n*m), nrow=n, ncol=m)
  rownames(features) <- sprintf("ex%04d",seq(n))
  colnames(features) <- sprintf("feat%04d",seq(m))

  # generate random model parameters
  intercept <- rnorm(1)
  coefs <- rnorm(length(sig.features))
  names(coefs) <- colnames(features)[sig.features]

  # create response data
  response <- features[,sig.features] %*% coefs
              + intercept 
              + rnorm(n, sd=noise.level)

  # return generated data
  list(n=n, m=m,
       sig.features=sig.features,
       noise.level=noise.level,
       features=features,
       params=list(intercept=intercept, coefs=coefs),
       response=response)
}

A function to check correspondence between true coefficients and fit cofficients:

## return a data.frame containing all non-zero fit
## coefficients along with the true values
compare.coefs <- function(data, fit) {
  coefs <- data$params$coefs
  intercept <- data$params$intercept
  merge(
    data.frame(
      feature.name=c('(Intercept)', names(coefs)),
      param=c(`(Intercept)`=intercept, coefs)),
    subset(
      data.frame(
        feature.name=rownames(coef(fit)),
        coef=coef(fit)[,1]),
      coef!=0),
    all=TRUE)
}

Make predicted vs actual plots

plot.predicted.vs.actual <-
  function(data, predicted, 
      actual, noise.level, label=NULL) {

  corr <- cor(predicted, actual)
  order.by.predicted <- order(predicted)

  ##  create a plot of predicted vs actual
  plot(actual[order.by.predicted],
       pch=21, col="#aaaaaaaa", bg="#cc000030",
       ylab="response", xlab="sample")

  title(main="predicted vs. actual",
        col.main="#666666")

  lines(predicted[order.by.predicted],
        col='blue', lwd=2)

  legend("topleft", pch=c(NA, 21), lwd=c(2,NA), 
         col=c("blue", "#aaaaaa"),
         pt.bg=c(NA,"#cc000030"),
         legend=c('predicted','actual'))

  if (!is.null(label)) mtext(label, padj=-0.5)

  legend("bottomright",
    legend=c(
      sprintf('corr=%0.3f', corr),
      if (abs(noise.level) >= 2.0)
        sprintf('noise=%0.1fx', noise.level)
      else
        sprintf('noise=%0.0f%%', noise.level*100)))
}

Generate data

n <- 1000
noise.level <- 0.50
data <- generate.data(n, m=20,
                     sig.features=1:5, noise.level)

Select training and testing sets

train <- sample.int(n, n*0.85)
test <- setdiff(seq(n), train)

Fit model using elastic net.

fit <- cv.glmnet(data$features[train,], 
                 data$response[train, drop=FALSE],
                 alpha=0.7)
compare.coefs(data, fit)
  feature.name   param     coef
1  (Intercept) -2.2119 -2.32176
2     feat0001 -1.4536 -1.23601
3     feat0002  1.2987  1.12962
4     feat0003 -0.6622 -0.56728
5     feat0004  0.8445  0.70143
6     feat0005 -2.4279 -2.25502
7     feat0013      NA -0.04111

Elastic net estimates the true parameters pretty well. It also gives a small weight to a spurious predictor. With 1000 features to choose from, it's not unlikely that one will look like a predictor by chance.

For some reason, cv.glmnet will cross validate over a range of lambda values, but doesn't do the same for alpha. Tweaking alpha might be help eliminate that extra coefficient.

Check our ability to model training data

p <- predict(fit, data$features[train,])
plot.predicted.vs.actual(
  data$features[train,], p,
  data$response[train,],
  noise.level, "training")

plot of chunk plot1

Correlation with training data

cor(p, data$response[train,])
    [,1]
1 0.8831

Check our ability to predict test data

p <- predict(fit, data$features[test,])
plot.predicted.vs.actual(
  data$features[test,], p,
  data$response[test,],
  noise.level, "testing")

plot of chunk plot2

Correlation with testing data

cor(p, data$response[test,])
    [,1]
1 0.8799

Created with the help of the excellent package Knitr. This document is also published at http://rpubs.com/cbare/2341.

Monday, October 22, 2012

Complex systems

One hundred years from now, the role of science and technology will be about becoming part of nature rather than trying to control it. - Joichi Ito, MIT Media Lab director

In complex systems, trade-offs are everywhere. Engineers designing technological artifacts carefully balance competing objectives. An economy allocates resources like land, labor and capital to one use or another. Even evolution faces trade-offs.

Optimal bundles for three different incomes--2 normal goods. Price Theory, David D. Friedman

Optimal bundles for three different incomes--2 normal goods.
Price Theory, David D. Friedman

Economists study trade-offs using tools like utility and indifference curves. The figure shows the optimal bundle consisting of two goods (apples and oranges, of course) for three different income levels. The curves represent trade-offs of equal utility; red lines represent income. They intersect at the points X, Y and Z, the points of highest utility achievable at each level of income.

Pareto optimality

At a macro level, millions of competing buyers and sellers make thousands of such trade-offs daily. Such multiobjective optimization problems often shake out in a way described by Pareto optimality. If an allocation of resources in an economy is such that no-one could be made better off without making someone else worse off, that allocation is said to be Pareto optimal. Competitive markets can be shown to deliver a Pareto optimal allocation of resources. Rather than a single optimal point, the Pareto optimal frontier defines a surface in high-dimensional space of best possible trade-offs. The notion of Pareto optimality turns out to be portable to other fields of study.

Evolutionary Trade-Offs, Pareto Optimality, and the Geometry of Phenotype Space (Shoval et al., Science 2012), a short-but-awesome paper from Uri Alon's lab, applies the concept of Pareto optimality to evolutionary biology. The morphology of finch beaks, ant heads, and bat wings are all re-examined in the light of Pareto optimality. The idea applies at the molecular level as well. Microbial gene expression moves along an axis between competing priorities of growth and stress response.

In each case, there is a trade-off among competing objectives - performance at various specialized tasks. One of the simplifying ideas in the paper is to work in terms of measurable task performance rather than the resulting contribution to fitness. Fitness, like the economic concept of utility, is hard to quantify and maybe not precisely knowable.

For example, a beak might be optimized for a particular diet: cracking hard seeds, chewing soft seeds or plucking insects from their hiding places in the bark of a tree. The Pareto frontier defines solutions in which it is not possible to improve performance of one task without sacrificing performance of another. Selection favors phenotypes near the Pareto front. Local environment dictates the distribution of species and individuals along the front.

Complex adaptive systems

Biology, economics and, to some extent, engineering are all turning into the study of complex adaptive systems. Economics is the ecology of money. Biology is just the economics of the jungle. Here are a few big ideas and questions that generalize across disciples.

  • Biology - adaptability
    Living systems are adaptive. They deal with extremes of environment, degrading gracefully with damage and keep on functioning in situations that stop mechanical systems dead. Economic systems, too, are adaptable. New information is constantly being factored into prices carrying signals that balance the needs of consumers with productive capacity. So far, engineered systems fall short in terms of adaptability.
  • Engineering - modularity A hallmark of engineered systems is modularity. In software, we struggle against the entropy of spaghetti-code. But, somehow modularity emerges spontaneously in living systems, their processes algorithmic in nature. Evolved systems are clearly different from engineered systems and are clearly far from fully modular, but, to a surprising degree, modularity is found in biology. What forces cause modularity to arise and what are the opposing forces?
  • Economics - distributed information Information flows through complex systems. Price is an emergent property integrate over millions of individuals each making hundreds of economic decisions daily. Living things, too, aggregate information in order to compute how best to allocate their budget of energy and scarce nutrients to achieve competing objectives. How do complex systems achieve balance, find and maintain stable states (homeostasis) and tend towards optimality? How do feedback mechanisms promote or disrupt stability?

These some of the fundamental features of complex systems: adaptivity, information flow and modularity. (I'm calling the book “Darwin, Hayek, Knuth”. Nice, huh?) Adaptability and robustness emerge from information flowing across interconnected networks often hierarchical in structure.

After bouts of physics envy, biology and economics have arrived at roughly the same place. The toolkits used to study both are converging on the same set of statistical techniques and machine learning algorithms for computationally deriving models from big data.

Both fields are wrestling with the same problems: complexity and uncertainty. With an emerging understanding of the properties of complex systems, we might see more robust engineered systems and the ability to re-engineer systems like economies and metabolisms or ecosystems or at least know the limits to which these systems can be engineered. Learning to engineer complex systems is the frontier of the 21st century.

More

Sunday, October 07, 2012

Hacking education

On-line education is blossoming in a virtuous cycle of innovation, threatening disruption to expensive traditional universities and opening access to higher learning for anyone with an internet connection and a curious mind.

For developers, the on-line education boom means rich opportunities to learn, to create learning environments, and to analyze the data collected in the process of running massive open online courses - hacking education itself.

Coursera, an early leader, signed up 17 more universities on top of the 12 that joined in July and are now offering 198 classes from 33 schools.

Founders Daphne Koller & Andrew Ng published an article in Forbes, Log On and Learn: The Promise of Access in Online Education. Koller, whose "Probabilistic Graphical Models" strained my few remaining brain cells, spoke at TED on What we’re learning from online education

A Seattle Times piece on the recent wave of educational startups featured enthusiastic comments from Ed Lazowska at UW and Vitalina Komashko at Sage Bionetworks.

Why some of the best universities are giving away their courses Each has answers. But basically it comes down to these: To serve the greater good. To win a public-relations race. And, most especially, to enhance reputations.

On-line education is a perfect complement for hotness that is data science. Not only is it a means for transferring trendy skills, but the data collected in the process should have amazing things to teach us about learning.

Not all the action is in cyber-space, either. If you have a hungry mind that needs feeding, you can:

The only limit is your own bandwidth. That, and the tolerance of your spouse.

The flashy technology is new but, the ideal of open access to knowledge has been around for a long time. The Seattle Times quotes Dave Cillay, executive director of WSU Online, "We've had MOOCs and open learning resources for centuries. They're called libraries."

Echoing Carnegie and his libraries, the Gates Foundation announced in June $9 million in grants for on-line secondary education, including a million to the MIT/Harvard venture edX.

I remember poking my head into a cinder-block schoolhouse in a tiny village in Laos, back in my traveling days. There were 2 books; a book that appeared to be equal parts farming manual and government propaganda and another of Buddhist scripture. The potential to mitigate that kind of information-poverty in the remote corners of the world is one of the most exciting aspects of on-line education.

Building on previous innovation is key to progress, especially in science and technology. Hacking education will help information flow faster, getting people to the frontier where they can start pushing the envelope and maybe make the world a slightly better place. That's why these are exciting times for those that love learning.

More

Still don't believe me that there's a lot going on? Here's more Ed-tech news:

Monday, October 01, 2012

The future of dev tools

Classic developer tools have a timeless quality to them. Greybeards and college kids alike happily hack away in Emacs, vi, Bash and a host of other tools older than many of their users. It's surprisingly hard to improve upon these old tools.

But, interest in designing new developer tools seems finally to be emerging. Rather than replacing powerful and expressive textual interfaces with pretty but limiting graphical interfaces, these new tools augment the command-line experience with immediate visual feedback.

Light Table

Chris Granger's re-imagining of the IDE, Light Table, seeks to enhance the developer's "ability to traverse abstraction". Slick demo videos here and here show Light Table's good looks, but also its presentation of functions as the primary unit of abstraction, the ability to show values propagating through code and its handy access to documentation.

During Granger's talk at StrangeLoop, one questioner raised the issue of whether dynamic languages lead to a different style of interaction between tool and developer. Static languages lend themselves to autocompletion and refactoring tools as in Eclipse, whereas dynamic languages emphasize the REPL and perhaps metaprogramming and DSLs.

Though originally funded through KickStarter project, Light Table is closed-source, at least for now. It's scheduled for release next May with support for Clojure, Javascript, and Python.

Neo4j

Modern browsers provide capabilities like accelerated graphics, advanced page layout and process isolation, enabling environments like Neo4j's console demo that combine command shells with interactive graphics.

As far as I can tell, that's just a demo. The real admin console for Neo4j doesn't suck either, but requires tabbing between command shell and graph visualization.

Dev tools in browsers

Browsers keep getting better. In-browser REPLs exists for numerous languages: clojure, haskell, javascript and others. These are typically targeted at language learners, as is Chas Emerick's Clojure Atlas, a visual and conceptual interface for navigating Clojure's documentation. But, I expect more advanced tools will find their way into the browser over time. Fogus's Himera project shows one way forward, delegating some of the heavy lifting to the server.

Amazingly, R Studio Server puts full IDE into the browser, with the help of QTWebkit, GWT and some grand-master level wizardry. With Knitr integration, R Studio approaches live document capabilities.

Sublime Text

On the desktop, the Sublime Text editor picks up where TextMate left off. Sublime can use syntax files from TextMate, which means it already supports your favorite language, plus it's programmable in Python.

Xiki

I heard about Xiki (for executable wiki) from Tom Henderson, who owes me a book, by the way. An impressive demo video shows off Xiki's merger of advanced UI and command shell.

Xiki integration with Sublime is progressing.

Design principles for programming tools

Bret Victor, known for his design work at Apple and lots of other cool things, has thought deeply about using technology to help people “learn, understand and create”. Victor followed up the inspiring talk Inventing on principle his presentation at StrangeLoop on design principles for programming tools, captured in the essay Learnable Programming.

Tools should enable the programmer to:

  • Read the vocabulary
  • Follow the flow
  • See the state
  • Create by reacting
  • Create by abstracting

What this means is roughly this: Quick access to docs, often triggered by mouse-over, simplifies reading. Visibility into flow and state increases comprehension. “Dumping the parts bucket onto the floor&rduo; encourages mixing and matching and provides visual prompting emphasizing recognition over recall. Abstractions are created by starting concrete and generalizing.

Code is written for a dual audience: machine and human reader, requiring a difficult combination of precision and clarity. As the tools get smarter, the conversation between machine and programmer will get richer. The common thread here is supporting the programmer without imposing limitations, providing an experience more like a blank page and a box of sharp pencils than a menu of canned options, helping to create what Bret Victor calls, “environments that function as an external imagination”.

Monday, September 24, 2012

Computing kook density in R

Do you ever see strange lights in the sky? Do you wonder what really goes on in Area 51? Would you like to use your R hacking skills to get to the bottom of the whole UFO conspiracy? Of course, you would!

UFO data from infochimps is the focus of a data munging exercise in Chapter 1 of Machine Learning for Hackers by Drew Conway and John Myles White, two social scientists with a penchant for statistical computing.

The exercise starts with slightly messy data, proceeds through cleaning up some dates. I think I slightly improved on the code given in the book. Have a look (gist:3775873) and see if you agree.

Dividing the data up by state (for sightings in the US), I noticed something funny. My home state of Washington has a lot of UFO sightings. Normalizing by population, this becomes even more pronounced.

I learned a neat trick from the chapter. The transform function helps to compute derived fields in a data.frame. I use transform to compute UFO sightings per capita, after merging in population data by state from the 2000 census.

sightings.by.state <- transform(
 sightings.by.state,
 state=state, state.name=name,
 sightings=sightings,
 sightings.per.cap=sightings/pop)

Creating the plot above, with a pile of ggplot code, we see that Washington state really is off the deep end when it comes to UFO sightings. Our northwest neighbors in Oregon come in second. I asked a couple fellow Washington residents what they thought. The first reasonably conjectured a relationship to the number of air bases. The second Washingtonian gave the explanation I favor: "High kook density".

If you'd like to the data, it's from Chapter 1 of Machine Learning for Hackers. Data and code can be found in John Myles White's github repo.

Thursday, September 13, 2012

OO in R

The R Project

"Is there a package for obfuscating code in #rstats?", someone asked. "The S4 object system?!" came the snarky reply. If you're smiling right now, you know that it wouldn't be funny if it weren't at least a little bit true.

Options: S3, S4 or R5?

There can be little doubt that object oriented programming in R is the cause of some confusion. We'll look at S4 classes more closely in a minute, but be warned that S4 classes are just one of at least three object systems available to the R programmer:

  • S3: simple and lightweight
  • S4: formal classes implemented by the methods package
  • R5: Reference classes

It's not super clear when to use which, at least not to me. It seems to depend strongly on style and personal preference. The Bioconductor folks, for example, make heavy use of S4 classes. Google, on the other hand, advises to "avoid S4 objects and methods when possible".

Here's the way it looks to me. S3 classes feel a bit like Javascript classes - easy, loose and informal. S4 classes are rigid, verbose and harder to understand. But, they offer a better separation between interface and implementation, along with some advanced features like multiple dispatch, validation and type coercion. Reference classes (aka R5) encapsulate mutable state and look more like familiar Java-style classes. They're new and pass-by-reference can violate expectations of R users.

An S4 class example

Now, let's return to S4 classes with a simple example. First, we define a class to represent people.

# define an S4 class for people
setClass(
  "Person",
  representation(name="character", age="numeric"),
  prototype(name=NA_character_, age=NA_real_)
)

A person has a name and an age, which default to NAs of their respective types - character string and numeric. For the sake of demonstrating polymorphism, let's define a couple subclasses.

# define subclasses for different types of people
setClass("Musician",
  representation(instrument="character"),
  contains="Person")

setClass("Programmer",
  representation(language="character"),
  contains="Person")

There's no reason not to write normal R functions that take S4 classes as arguments. Polymorphism is called for when a method has different implementations for different classes. In that case, we declare a generic method.

# create a generic method called 'talent' that
# dispatches on the type of object it's applied to
setGeneric(
  "talent",
  function(object) {
    standardGeneric("talent")
  }
)

The following code implements two subtypes of person, each with a talent for something.

setMethod(
  "talent",
  signature("Programmer"),
  function(object) {
    paste("Codes in", 
      paste(object@language, collapse=", "))
  }
)

setMethod(
  "talent",
  signature("Musician"),
  function(object) {
    paste("Plays the",
      paste(object@instrument, collapse=", "))
  }
)

Now, let's make some talented people.

# create some talented people
donald <- new("Programmer",
  name="Donald Knuth",
  age=74,
  language=c("MMIX"))

coltrane <- new("Musician",
  name="John Coltrane",
  age=40,
  instrument=c("Tenor Sax", "Alto Sax"))

miles <- new("Musician",
  name="Miles Dewey Davis",
  instrument=c("Trumpet"))

monk <- new("Musician",
  name="Theloneous Sphere Monk",
  instrument=c("Piano"))

talent(miles)
[1] "Plays the Trumpet"

talent(donald)
[1] "Codes in MMIX"

talent(coltrane)
[1] "Plays the Tenor Sax, Alto Sax"

Mutability

One common stumbling block with S4 classes concerns changes in state. For instance, we might want to give our hard-working employees a raise.

setClass("Employee",
  representation(boss="Person", salary="numeric"),
  contains = "Person"
)

setGeneric(
  "raise",
  function(object, percent=0) {
    standardGeneric("raise")
  }
)

setMethod(
  "raise",
  signature("Employee"),
  function(object, percent=0) {
    object@salary <- object@salary * (1+percent)
    object
  }
)

True to it's functional heritage, R deals with immutable values. Changes in state happen by making new objects. The trick is to return the new object from the mutator methods and capture it on the way out.

smithers <- new("Employee",
  name="Waylon Smithers",
  boss=new("Person",name="Mr. Burns"),
  salary=100000)

# doesn't work?!?!
raise(smithers, percent=15)
smithers@salary
[1] 100000

Setting a new salary creates a new value. Notice that we return the modified object from the raise function. Don't forget to catch it.


# remember to reassign smithers to the new value
smithers <- raise(smithers, percent=15)
smithers@salary
[1] 115000

Multiple Inheritance

Through the magic of multiple inheritance, the lowly Code Monkey is both a programmer and an employee. Just set the contains value to indicate its two parent classes.


setClass("Code Monkey",
  contains=c("Programmer","Employee"))

setMethod(
  "talent",
  signature("Code Monkey"),
  function(object) {
    paste("Codes in",
      paste(object@language, collapse=", "),
        "for", object@boss@name)
  }
)

chris <- new("Code Monkey",
  name="Chris",
  age=29,
  boss=new("Person", name="The Man"),
  salary=2L,
  language=c("Java", "R", "Python", "Clojure"))

talent(chris)
[1] "Codes in Java, R, Python, Clojure for The Man"

So, there you have it - encapsulation, polymorphism and inheritance in S4 classes. Complete code for this example is in gist:3670578.

OO in R resources

It's lucky that there are loads of places to go to learn about S4 classes.