Dear game developers and game-AI experts, I'm finishing the development of a C++ library that implements algorithms which are considered, by the international machine-learning community, among the the most powerful known. The library can perform on-line learning and prediction of a time-series from uni- or multi-variate input data, and it is suitable for real-time applications. I developed the lib for applications other than videogames, but I could adapt it fairly easily. It works better than neural networks without having problems with local minima, so the training algorithm always converges to an optimal solution in a reasonable time. Is anybody interested? Does anybody have a good business case that would justify the investment necessary to adapt the libs to gaming application? Thank you! Kind regards, 42

Questions:

1 - You imply that the algorithms you implement are well known in the machine learning literature. Which algorithms are they?

2 - In what context have you developed these algorithms, and what makes the current interfaces inappropriate as they are for games?

3 - What are you trying ultimately to achieve? An open source library, which you will freely distribute under the GPL? Or are you hoping to keep the source closed, and find "buyers" here? (The latter is... unlikely.)


Also, you should know that there are some "no free lunch" theorems that prove that no machine learning algorithm can be better at all tasks than another. So you should be careful to avoid claims, without qualifiers, about the "goodness" of a particular machine learning algorithm, as they're almost certainly not literally correct.


Cheers.

I cannot disclose the kind of algorithms, nor their original application, which is anyway not relevant. Also, I do not want to enter a discussion about which algorithm is better for which application. My libs are tuned for time series. I'm not looking for a peer-review, but for somebody who would like to give it a try and possibly collaborate with the development of a commercial product.

Cheers

oooohhhhh I'm so thrilled with the opportunity to learn about these
techniques that are so powerful and secret you can't even mention their
names.

Seriously, If you want serious consideration, publish a synopsis
of what you're offering and where you think they might be applicable.

If you're thrilled by machine-learning algorithms, you probably have downloaded the most recent, freely-available, scientific papers and gone through them, so, why do you ask? There's no secret, it's all freely available, but I'm not going to explain the details of the implementation and fine tuning, sorry.

I can offer access to time-series-predicting algorithms via remote method invocation, with a couple of functions of the kind train(x_0, x_1, ..., x_n) and predict(x_1, ..., x_n), where x_0 is the prediction target and x_i, i=1...n the features. I assume that x_0=x_0(x_1(t-m), ..., x_1(t), ..., x_n(t-m), ..., x_n(t)), with t is the (discretized) time.

Quote: Original post by forty-two
I'm finishing the development of a C++ library that implements algorithms which are considered, by the international machine-learning community, among the the most powerful known.

If they are respected, surely there are papers on them by you? If they are secret, how have they been peer-reviewed? I thought academics were not normally keen to hide their work, but to share it.

The best thing might be to present a demo... even if your library isn't optimised for games, can it be twisted into it for the purposes of showing the potential?

So, what are the time complexities of these algorithms? Well, I guess this may not be as big a consideration since you are talking about series prediction.

What are some of the required space complexities? What is the memory foot print as the problem scales?

How much training is required for it to converge? How much data is needed for an accurate prediction? And how would this data be fed in? One at a time? All at once? Can the training be suspended and restarted at anytime? So, if the system shuts down, can we pick up where we left off, and how would we save off where we left off?

When given the same set of training data, is the end result deterministic? If we need to debug it, can we just feed in the same training set to reproduce a bug?

Can the actual prediction step be broken up into smaller states, so making it sort of stop and go as needed? Also, is it thread-safe?

Off the top of my head, these are some of the questions I would ask when evaluating a package like this for use in a game. Based on the answers, the way the package can be used in a game would vary greatly.

I'll first reply to d000hg's remarks:

I wrote papers about neural networks, several years ago, when I was a computational-neuroscience PhD student, but they're relevant only for neuroscience applications, as the algorithms are not fast or optimized in any way.

I'd love to have a demo: that's why I'm asking for help here.

Now for WeirdoFu:

The complexity of the algorithm is O(N3), but it's probably only an upper bound, the actual value being dependent of the data. I can imagine cases in which the algorithm could converge very quickly.

The memory footprint is linked to speed: to give an idea, with a 100Mb footprint, learning to classify 3000 vectors in R^300 takes something in the order of a few tens of seconds on a 3.0GHz intel processor. Please note that the model, which is generated by the learning and is used to compute the prdictions, can be used while a new one is being generated on a possibly partially new data set. By incrementally removing older data and performing the training on a partially new data set, it's possible to "emulate" the palinsest property observed in neural (but also neuronal) networks.

The amount of data needed depends much on the feature space dimensionality and characteristics of the dynamic system that generates the time series. Learning chaotic time series can be quite hard, although they're deterministic. I think (and hope) that predicting, for example, the behavior of a human player in a game, given the limited number of degrees of freedom, might require a relatively small dataset, but I'm just guessing... that's why I'd like to interact with experts... I have no experience in this field.

>And how would this data be fed in?

By a function call, or by sending a signal (eg, boost/QT signals). The algorithm responds to a new data point by computing a prediction and starting a new training session (unless one is already running) on two threads.

>One at a time? All at once?

Both modalities are working, the former is normally used during normal functioning (ie, at regime), the latter to "bootstrap" the algorithm by providing older data at startup.

>Can the training be suspended and restarted at anytime?

Yes, it can.

>So, if the system shuts down, can we pick up where we left >off, and how would we save off where we left off?

Yes. At startup it's possible to provide to the algorithm an old dataset (that's what I do now) or de-serialize the most recent model that was serialized to disk before shutdown. I do not see any problem in using other approaches to persistency.

>When given the same set of training data, is the end >result deterministic?

Yes, it is. It's not a genetic algorithm or simulated annealing... no random numbers involved.

>If we need to debug it, can we just feed in the same >training set to reproduce a bug?

Yes, that's what I do.

>Can the actual prediction step be broken up into smaller >states, so making it sort of stop and go as needed?

It's possible to start and stop the data feed. The algorithm will generate a model on the newest dataset and wait for new data. In the meantime, it will still provide predictions by using the most recent model, whose quality might obviously deteriorate with time, as the training dataset becomes less and less representative of the actual state of the system.

>Also, is it thread-safe?

Yes, I painfully made it thread-safe.

Thank you for your questions, I hope to have given you a satisfactory answer.

Quote: Original post by forty-two
I cannot disclose the kind of algorithms, nor their original application

I find this highly peculiar. I'm an academic. I've never had an issue with telling someone the name of an algorithm I've implemented, even if it's one I've created and not yet published. Revealing the name does nothing to devalue the implementation, nor does it tell people how the algorithm works, unless they go and look it up (which implies that the knowledge is freely available and there is no basis for obfuscating it).

That you refuse to identify which algorithms you have implemented leads me to question your claims that these are "among the most powerful known". This could easily be a claim intended to hide the fact that you've implemented your own algorithms and wish to establish a claim of their value by getting someone else to find problems on which they work, rather than actually evaluate their usefulness over a class of problems.

If your looking to evaluate your implementation of these algorithms on a game scenario, then you'll need to be able to learn functions u(t) for arbitrary problems of the form

r = arg max[p(f(u(t)))]

where f() is an unknown (typically nonlinear) stochastic function, u(t) is an input (control) function (typically in discrete time and finite space) and p() is a chosen performance metric.

If you solve this problem with an existing algorithm, or make a significant contribution to it with a new algorithm and you don't rely on pseudo-random search procedures, please let me know (a link to a published paper with experimental results and no algorithmic details would be sufficient).

Regards,

Timkin

Dear Timkin,

you're right and I agree... revealing the name does nothing to devalue the implementation, nor does it tell people how the algorithm works. But the description of the algorithm is available in the scientific literature (I'm not the author): The field I'm applying it to is very competitive and I don't want to give anybody a head start by giving suggestions about methodologies. I'm a bit paranoid, of course.

Unfortunately, I haven't contributed that much to the advancement of machine-learning... I didn't implemented my own algorithms, I've just coded the infrastructure to use them in real-time and done some tuning in this respect.

The problem you write about (r = arg max[p(f(u(t)))]) seems to me more an optimization problem than a machine-learning one. Of course, if you know u(t) for a given f(), it might be possible to learn it, that is to predict u(t+1) | u(t). For example, it might be possible to predict the movements of human player in a possibly changing landscape. Of course, there is no maximisation of p() in that: it's a plain learn-by-example brute-force approach. The problem you suggest is actually much more complex than what I had in mind...

Regards
42