[OT] Clustering models of similar agents

[jukofyork]

Please forgive the incorrect terminology (hopefully my explanation makes sense...), but this problem must come up in other domains and I just can't seem to find anything on it:

We have a population of agents who each take a feature vector as input and provide a single continuous variable as output. For each agent we have a (limited) set of cases in the form: [features]->output, and hence we can train a regression model for each agent (independently) to predict their behaviour.

We assume that many of the agents act in similar ways, so our goal is to group these similar agents into clusters (meta-agents) and train up meta-models using all of the data from all the agents in the corresponding cluster (which represents a model of the 'average agent' for all cluster members).

<u>Greedy algorithm (expensive/intractable):</u>

1. Create a regression model for each (meta-)agent using all of the cases for that (meta-)agent.
2. For every model vs every other model, find the correlation between outputs (using all cases for all agents as input) and create a matrix of R's.
3. Find the largest R in the matrix, and combine the two corresponding (meta-)agent's data thus creating a larger meta-agent with the combined data.
4. Repeat until we have a very disjoint set of (clustered) models remaining. When we have a small enough set of models, or largest R in matrix is below some arbitrary value, stop.

Any related papers anybody knows about? (+ whats this process/problem called?)

Any clever (fast) way to do the same thing? (like k-means, but for this task [using model correlation as distance metric]?)

Juk [img]/images/graemlins/smile.gif[/img]

EDIT: I'm not even sure if model correlation is quite the right metric to use either, but assume step (2.) above finds a decent normalized measure of model similarity so the highest value signifies the most similar models.

[tigerite]

It sounds like a self-organizing map problem to me. But I could be totally out. That's the only form of modelling like that I've really had any experience of.

[OrcaDK]

I'm not sure i understand the issue of the problem, but to me it sounds like the description of a genetic algorithm?

You let the agents run some input and produce data output for an arbitrary amount of time, you then find the most promising agents (based on whatever conditions the problem defines as promising), and then you combine/mate the best agents to create new genes which then repeat the process, untill you end up with a smaller amount of supergenes that correspond to the solution.

[jukofyork]

[ QUOTE ]
It sounds like a self-organizing map problem to me. But I could be totally out. That's the only form of modelling like that I've really had any experience of.

[/ QUOTE ]
Yep, a Kohonen SOM might work if I can see a way to transform it into a normal clustering problem, but atm I just cant seem to see a way to do this (yet).

[ QUOTE ]
I'm not sure i understand the issue of the problem, but to me it sounds like the description of a genetic algorithm?

[/ QUOTE ]
It might be possible to model the problem as some kind of optimization problem (where a GA would be useful in overcoming the high dimensionality my matrix idea had), but the fitness function would have to have some way to measure how well the models were clustered...


I originally thought it would be a pretty common problem is some other domain, but as of yet I can only seem to find any reference to the problem in papers about "Robotic Soccer" (eg: http://wwwbrauer.informatik.tu-muenc...olf-2003.pdf). Sadly, their methods are used to cluster models represented by Finite State Machines rather than regression based models. It seems that for other games (Poker included), and model types, there has been almost no work done on model clustering (ie: opponent classification), and it seems an open problem.

After alot more thought, I think I've found a fairly decent way to split models into clusters based on a top-down approach (which assumes model errors are distributed uniformly about a mean [which in practice they are not...]): Basically I generate a model of the "average agent", measure the error in model output for each agent, and split the agents into 2 groups based on if the sum of errors is +ve or -ve. I then keep doing this recursively on the new groups until I have a predefined number of model clusters.

I still can't see any easy way to cluster using a bottom up approach, but perhaps the group splitting will work well enough to not need this.

Juk [img]/images/graemlins/smile.gif[/img]

[Shroomy]

[ QUOTE ]
It seems that for other games (Poker included), and model types, there has been almost no work done on model clustering (ie: opponent classification), and it seems an open problem.


[/ QUOTE ]

oh there has been quite a bit done... just none of it has been very successfull [img]/images/graemlins/smile.gif[/img]

btw .. its funny juk, I read your website a long time before I was ever on 2p2. I never realized it was you untill recently. thanks btw, it was an informative site.

[jukofyork]

[ QUOTE ]
[ QUOTE ]
It seems that for other games (Poker included), and model types, there has been almost no work done on model clustering (ie: opponent classification), and it seems an open problem.


[/ QUOTE ]

oh there has been quite a bit done... just none of it has been very successfull [img]/images/graemlins/smile.gif[/img]

[/ QUOTE ]
If you know of any papers related to "opponent classification" then I'd be very interested - I'm not really interested in more papers on "opponent modeling" (of specific players), as the area I'm interested in atm is not specific models but rather creating/fitting players to general models (each with diversely different strategies - hence the need for model clustering).

[ QUOTE ]
btw .. its funny juk, I read your website a long time before I was ever on 2p2. I never realized it was you untill recently. thanks btw, it was an informative site.

[/ QUOTE ]
Glad it was of some help! Possibly one day it will get updated properly and I'll find the time to clean up some of my old code and post it their (alot of my old work is Linux based, so a bit of a pita to do though...). I've got interesting stuff related to chess, poker, sorting networks, reinforced learning, ... - all just need some tidying though...

Juk [img]/images/graemlins/smile.gif[/img]

[Shroomy]

I wish that I could help just to balance the scales a tiny bit, but the few projects I am aware of personally used EM or K means to cluster opponents based on their betting patterns, hole cards shown at SD, and a few other criteria.

They used K-means for opponents below a certain threshold of observed hands and expectation maximimization over the threshold.

I do know that the lead (aka friend of mine) was also in contact with others doing some similar projects and remember one of them was on the Carnegie Mellon CS staff, but I don't think anyone ever got to the point of writing up anything.

Unfortunately my interaction with any of them was peripheral and mainly involved exploring porting some of their stuff over to SQL 2005 using the business intelligence features newly added in SQL 2005, which worked surprisingly very well btw, and writing some UI’s.

I think the project that I mentioned initially died due to logistics (or maybe it was because of party being more active in prohibiting certain software.) He wanted to start another fee based opponent profile site and data mine the popular sites, but I’m almost certain that it never got off the ground.

I will try to find his email, unfortunately he moved to Barcelona over a year ago and we fell out of touch.

I wish I could provide more info, but while I have always been interested in neural nets, decision trees, markov, bayes etc.. I have had very few opportunities to put them to use, and I’m positive your knowledge far (add a few more far’s in there [img]/images/graemlins/smile.gif[/img] ) exceeds mine. I just don’t want to misrepresent that I really had any input or insight into the issue.

As for your site, [img]/images/graemlins/laugh.gif[/img] it would be nice to see updated stuff, but the main benifit that I got from it was seeing what approaches you were using to attack different problems, so code and myopic details are nice, but the overall approach is the true benifit IMHO, since as you have seen one project is never exactly like another [img]/images/graemlins/smile.gif[/img] and you always end up picking a piece here and a piece there.

enough rambling .. good luck

[jukofyork]

[ QUOTE ]
I wish that I could help just to balance the scales a tiny bit, but the few projects I am aware of personally used EM or K means to cluster opponents based on their betting patterns, hole cards shown at SD, and a few other criteria.

They used K-means for opponents below a certain threshold of observed hands and expectation maximimization over the threshold.

I do know that the lead (aka friend of mine) was also in contact with others doing some similar projects and remember one of them was on the Carnegie Mellon CS staff, but I don't think anyone ever got to the point of writing up anything.

Unfortunately my interaction with any of them was peripheral and mainly involved exploring porting some of their stuff over to SQL 2005 using the business intelligence features newly added in SQL 2005, which worked surprisingly very well btw, and writing some UI’s.

I think the project that I mentioned initially died due to logistics (or maybe it was because of party being more active in prohibiting certain software.) He wanted to start another fee based opponent profile site and data mine the popular sites, but I’m almost certain that it never got off the ground.

I will try to find his email, unfortunately he moved to Barcelona over a year ago and we fell out of touch.

I wish I could provide more info, but while I have always been interested in neural nets, decision trees, markov, bayes etc.. I have had very few opportunities to put them to use, and I’m positive your knowledge far (add a few more far’s in there [img]/images/graemlins/smile.gif[/img] ) exceeds mine. I just don’t want to misrepresent that I really had any input or insight into the issue.

As for your site, [img]/images/graemlins/laugh.gif[/img] it would be nice to see updated stuff, but the main benifit that I got from it was seeing what approaches you were using to attack different problems, so code and myopic details are nice, but the overall approach is the true benifit IMHO, since as you have seen one project is never exactly like another [img]/images/graemlins/smile.gif[/img] and you always end up picking a piece here and a piece there.

enough rambling .. good luck

[/ QUOTE ]
It's taken me a month or two, but I've finally found what I was looking for (and yes it appears that a lot of work has been done on this idea, but in a different domain!) [img]/images/graemlins/laugh.gif[/img]

If anybody here is taking an interest in the $1M NetFlix Prize, then the term Collaborative Filtering will mean something to you.

Basically using the NetFlix model as an example of a problem suitable for using Collaborative Filtering ideas:

If you think of the "movies" as the possible "states" in a poker game, and the movie "reviewers" as the "players" (regression models in my case) in a poker game, and the "review ratings" as the "action frequencies" and/or "hand distributions" (output from the regression models in my case), then the problems are equivalent (ie: Collaborative Filtering algorithms should also be applicable).

Not sure if this is of any interest to anybody here, but just thought I would post this in case anybody else has spent time thinking about the model clustering problem.

Juk [img]/images/graemlins/smile.gif[/img]

[Suerte]

Juk- I am sitting in my eco495 class right now, and have been thinking about the best way to run a regression anaylasis on my poker stats. We are learning how to use a stat program called STATA, and its pretty crazy what you can do to find correlatiions and what not. I did not read this post that closely, but I think this is what you did or are trying to do. Basically find what variables have the largest effect on the independednt variable which is "$Won". Right kind of thing?

[jukofyork]

[ QUOTE ]
Juk- I am sitting in my eco495 class right now, and have been thinking about the best way to run a regression anaylasis on my poker stats. We are learning how to use a stat program called STATA, and its pretty crazy what you can do to find correlatiions and what not. I did not read this post that closely, but I think this is what you did or are trying to do. Basically find what variables have the largest effect on the independednt variable which is "$Won". Right kind of thing?

[/ QUOTE ]
If you are interested in predicting BB/100 ($Won), then you might find this post of interest.

The problem I'm looking at is slightly different: Basically I want to use the combined data of many players with similar playing styles to create one big "meta-player" model.

Even with a huge amount of data on a single player, it is still not enough to make an accurate model. The hope is that if you can somehow cluster together many player's data (with similar playing styles), you can create a pretty good model for all of them.

Then after this model clustering process, you will have a set of models each which models a certain playing style. Then when you encounter a new unknown player, you can simply find which of the pre-existing model(s) fit closest to your observations so far and use that model (or a mixture of models) for the new player.

Juk [img]/images/graemlins/smile.gif[/img]