5
$\begingroup$

I've been toying with this idea for a while. I think there is probably some method in the text mining literature, but I haven't come across anything just right...

What is/are some methods for tackling a problem where the number of variables it its self a variable. This is not a missing data problem, but one where the nature of the problem fundamentally changes. Consider the following example:

Suppose I want to predict who will win a race, a simple multinomial classification problem. I have lots of past data on races, plenty to train on. Lets further suppose I have observed each contestant run multiple races. The problem however is that the number or racers is variable. Sometimes there are only 2 racers, sometimes there are as many as 100 racers.

One solution might be to train a separate model for each number or racers, resulting in 99 models in this case, using any method I choose. E.g. I could have 100 random forests.

Another solution might be to include an additional variable called 'number_of_contestants' and have input field for 100 racers and simply leave them blank when no racer is present. Intuitively, it seems that this method would have difficulties predicting the outcome of a 100 contestant race if the number of racers follows a Poisson distribution (which I didn't originally specify in the problem, but I am saying it here).

Thoughts?

$\endgroup$
2
$\begingroup$

I don't see the problem. All you need is a learner to map a bit string as long as the total number of contestants, representing the subset who are taking part, to another bit string (with only one bit set) representing the winner, or a ranked list, if you want them all (assuming you have the whole list in your training data). In the latter case you would have a learning-to-rank problem.

If the contestant landscape can change it would help to find a vector space embedding for them so you can use the previous embeddings as an initial guess and rank anyone, even hypothetical, given their vector representation. As the number of users increases the embedding should stabilize and retraining should become less costly. The question is how to find the embedding, of course. If you have a lot of training data, you could probably find a randomized one along with the ranking function. If you don't, you would have to generate the embedding by some algorithm and estimate only the ranking function. I have not faced your problem before so I can't direct you to a particular paper, but the recent NLP literature should give you some inspiration, e.g. this. I still think it is feasible.

$\endgroup$
  • $\begingroup$ This presupposes you know the total number of contestants and that number isn't infinite? And so when a new guy shows up to the race track you have to re-train the entire model? $\endgroup$ – rawkintrevo Dec 4 '14 at 14:53
  • 1
    $\begingroup$ I updated my answer. $\endgroup$ – Emre Dec 4 '14 at 19:53
1
$\begingroup$

Would it be possible to use Approximate Bayesian computation (ABC)? If you assume a distribution for the number of competitors (e.g. Poisson), select a subset of competitors each iteration and simulate your data using multinomial distributions with probabilities based on competitors' features, after discarding parameters that don't match your training data, you should be able to obtain parameters for each competitor (that is, posterior distributions) and generate more races.

This might not work if the number of competitors is so important that it affects the coefficients of features for each competitor.

$\endgroup$
  • $\begingroup$ I was thinking more along the lines of Bayesian nonparametric ranking. $\endgroup$ – Emre Dec 4 '14 at 23:59
  • $\begingroup$ Sure. That is definitely a good fit. It could be a bit difficult to implement, though. $\endgroup$ – Robert Smith Dec 5 '14 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.