Which classifier should I use for sparse boolean features? I have training data that is classified into 2 categories: X and Not X

Each piece of training or experimental data has a variable number of boolean features. Each piece of data may have ~100 features, but the total number of possible boolean features may be in the tens or hundreds of thousands. 

I want to train a classifier so that given an observation (which has a set of boolean features), it will output the probability that it is X. 

Could you recommend which ML algorithms could be used for a large number of sparse boolean features?

Follow-up question:

I also have a large amount of training data that would be best described as Maybe X (I haven't verified is X, but there's a good chance it is X). I could further segment those Maybe X's into Likely X, Maybe X, Probably Not X. Is there a way I can train with Maybe X or it's subclassifications? In the end, what I still only care for is the probability that an observation is X.
Mapping your inputs into a sparse matrix and using logistic regression with an $\ell_1$ penalty should work well. In R this is very straight forward with the glmnet and matrix libraries. 

Additionally, if you have boolean features with a low frequency, you can filter some of them by taking a subset with at least some number of observations.

Here's a quick simulation in R of a lasso logistic regression with sparse features. 

library(glmnet)
library(Matrix)

n &lt;- 1e5
set.seed(420)

# These are all converted to boolean variables since they're arbitrary categories
ls &lt;- data.frame(cat1=sample(letters, n, replace=TRUE), 
                 cat2=sample(letters, n, replace=TRUE), 
                 cat3=sample(letters, n, replace=TRUE))
ls$cat1cat2 &lt;- factor(paste(ls$cat1, ls$cat2, sep="-"))
xs &lt;- sparse.model.matrix(~.-1,data=ls)
betas&lt;- rnorm(dim(xs)[2])
error &lt;- runif(n)

ytrue &lt;- xs %*%betas
ylogit &lt;- 1/(1 + exp(- (ytrue + error))
ylabel &lt;- ifelse(ylogit&gt;0.5,1,0)

trainfilter &lt;- runif(n)&lt;=0.3
sparsemodel &lt;- cv.glmnet(x=xs[trainfilter,],
                         y=ylabel[trainfilter],
                         alpha=1,
                         nfolds=3,
                         family='binomial')

preds &lt;- predict(sparsemodel, xs, s='lambda.min', type='class')
print(table(ylabel, preds))


The classifier doesn't matter as much in this case as the underlying algorithm's ability to handle sparse matrices. 

It's also worth noting that you can handle sparse boolean features by mapping them to arbitrary numeric indices and running them through a tree based algorithm (e.g., Random Forest or Gradient Boosting). In practice, this seems to work well.