Many discussions of missing data in supervised (and unsupervised) learning deal with various methods of imputation, like mean values or EM. But in some cases the data will be missing as a necessary consequence of the data generation process.
For instance, let's say I'm trying to predict students' grades, and one of the inputs I want to analyze is the average grades of the student's siblings. If a particular student is an only child, then that value will be missing, not because we failed to collect the data, but because logically there is no data to collect. This is distinct from cases where the student has siblings, but we can't find their grades.
Other examples abound: say we're in college admissions and we want to include students' AP exam results, but not all students took AP exams. Or we're looking at social network data, but not all subjects have facebook and/or twitter accounts.
These data are missing, but they're certainly not missing at random. And many algorithms, such as all supervised learning packages in scikit-learn, simply demand that there be no missing values at all in the data set.
How have people dealt with this in the past, and what off-the-shelf solutions are there? For instance, I believe the gradient boosting algorithm in R uses trees with three possible branches: left, right, and missing. Any other alternatives out there?