# regression algorithms which work with sparse categorical predictors

I am working with a very sparse problem with a large number of categories per feature and I am currently looking for existing machine learning regression algorithm implementations which can either take a large number of categories per feature as input (say 10^4 categories), or can operate on sparse input design matrices (with categories unrolled into columns using binary dummy variables). The algorithm also has to take a vector of observation weights for each row of the design matrix.

More formally, suppose that there are k features F_1, F_2, ... F_k. Each feature contains unordered categorical data, e.g. F_1 is color: red, blue, green. Features can be placed into the categorical m by k design matrix X. Each i-th row of the design matrix is associated with observing s_i successes and f_i failures, so the probability of success can be expressed as p_i = s_i / (s_i + f_i), where the total number of observations per row is s_i + f_i.

For example, in R, the call to the stats::glm routine which fits this data can be executed using the following code, where I placed all variables inside the "input" dataframe and dropped subscripts to denote m-dimensional vectors:

model <- input$p ~ input$F.1 + input$F.2 + ... + input$F.k
fit <- stats::glm(model, weights = input$s +input$f, family = binomial, data = input)
predict(fit, type = "response")


Now the problem is that when for feature j the number of categories N_j grows large, stats::glm will run out of memory (and so will party::ctree, partykit::ctree, rpart::rpart, etc); tree::tree routine only has a maximum of 32 categories per feature. The solution is to then unroll the columns of X into binary dummy variables, stored in the sparse matrix x. Using the color example, where the first element denotes the intercept, the unrolled sparse matrix x would have rows “red” = [1, 0, 0], “green” = [1 1 0] and “blue” = [1 0 1]:

alpha <- 0
lambda.grid <- 10^seq(4, -12, length = 100)
x <- Matrix::sparse.model.matrix(model, input)[,-1]
fit <- glmnet::glmnet(x, input$p, weights = input$s + input\$f, thresh = 1e-12, alpha = alpha, lambda = lambda.grid)


Elastic net in glmnet package works for my application. I am looking for other algorithms which work with this problem. e1071 SVM package in R (libSVM) doesn’t take weights (one can perform weighted regression using SVMs by weighting the slack variables in primal form). Are there other implementations which can work on “model” or “x” directly? The algorithm can be in any language/package.

• I am a big fan of the Lasso in the BigData R package. – honeyoak Jun 5 '14 at 15:05