Hihi.. I am currently looking at 20q.net to further understand the concept of classifier. What is the algorithm used in making this AI? i have been searching around but can't find a specific answer. Hope you can help. Thx=D

One thing I found interesting is this (from the FAQ at the page you linked to):

Quote: When you tell 20Q what your object is, the object and your game are placed in a queue of objects to be reviewed by a group of human moderators. A moderator will review the object you entered and either change your answer to something the game knows or add your object to the knowledgebase.

which is kind of funny, but understandable; there's no use learning from bad data (and otherwise someone could intentionally sabotage the thing by telling it falsehoods over and over).

Anyway, I don't claim to know how it works, but if someone were to ask me to design something similar I might try using a Bayesian network with some kind of structure learning (I'd have to learn about structure learning first though! :-)). Then the answer would be whichever noun maximized the posterior probability given the answers to the questions. I don't have personal experience with this though.

Interestingly, this is actually one time where a NN is appropriate to discuss around here. That is the ONE thing that NNs do well is classification. That's what they use in 20Q - both the toy and all the different web varieties.

http://en.wikipedia.org/wiki/20Q

I can tell you what my plan would be to implement a 20q program. I don't think I would use ANNs anywhere.

At every step you keep track of a vector that has one number (a probability) per object in the database. This represents your current knowledge of what the user is thinking. The entropy of this distribution is a measure of how clueless you are, so it would make sense to try to minimize it. Notice that the entropy is maximum when all the probabilities are equal and minimum (0) when a single object has probability 1.

This is the algorithm I would implement for picking questions, given a database of question-answer-object probabilities (what is the probability that the question "Is it soft?" will get an answer of "yes" if the object the user is thinking of is "wedding bouquet"?):

1) Start with a prior probability distribution for your entire collection of objects. Since you have a large history of people playing the game, you can use the frequency distribution from your history.

2) Find a question to ask (one that minimizes the expected entropy of the posterior probability distribution). If the probability distribution has one object with a probability close to 1 or if you have asked already 20 questions, try a guess instead (or you can simply think of this as just another valid question, whose associated probabilities of the user saying "yes" are 1 for that specific object and 0 for all the other objects).

3) From the answer, use Bayes's formula to update your probability distribution.

4) Goto 2.


Then there is the issue of how to update the database of question-answer-object probabilities. This is probably not too hard to do. I would start with something like this: Given a question-object pair, make the probability of each answer proportional to the sum of:
* The number of times we have actually seen that answer for that question-object pair.
* Some constant times the number of times we have seen that answer for that question, regardless of the object. Perhaps this term could be divided by the number of times we have seen the question asked; I would try it both ways.
* Some [much smaller] constant.

EDIT: Perhaps this is the part where an ANN could help? Give it several ingredients to come up with something proportional to a probability and let it learn the coefficients you need to mix them? It's a pretty minor role, and I would never use more than one neuron for it.

hmm. i am a little confuse over here. So from what i gather, it will be asking questions to eliminate solutions. Isn't this similar to that of decision tree? What is the difference in Neural Network?
Hope i am not getting the concepts mixed up=x

Quote: Original post by TeSsL
hmm. i am a little confuse over here. So from what i gather, it will be asking questions to eliminate solutions. Isn't this similar to that of decision tree? What is the difference in Neural Network?
Hope i am not getting the concepts mixed up=x

The problem is that some of the questions are not completely clear (as I said earlier, is a wedding bouquet soft?). So different people will give you different answers, and that's where probability plays a role.