blocks|key|1553162|text|它正在使用一种学习算法。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1553163|k-NN就是其中一个很好的例子。|1553164|Wikipedia:+k-Nearest+Neighbor+Algorithm|offset|length|1553165|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm^0|0|0|0|13|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@$F|S|G|T|1|U]]|A|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]]]

It is using a learning algorithm.

k-NN is a good example of one of these.

<a href="http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm" rel="noreferrer">Wikipedia: k-Nearest Neighbor Algorithm</a>

blocks|key|1553425|text|您可以将其视为二进制搜索算法。在每次迭代中，我们都会问一个问题，这应该会消除大约一半的可能单词选择。如果总共有N个单词，那么我们可以期望在log2(N)个问题之后得到答案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1553426|有了20个问题，我们应该能够在2%5E20+=100万个单词中找到一个单词。|1553427|消除异常值(错误答案)的一种简单方法可能是使用RANSAC之类的东西。这意味着，不是考虑所有已经回答的问题，而是随机选择一个较小的子集，这足以给出一个单一的答案。现在，你用不同的随机问题子集重复几次，直到你看到大部分时间，你都得到了相同的结果。然后你就知道你得到了正确的答案。|offset|length|1553428|当然，这只是解决这个问题的许多方法中的一种。|1553429|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/RANSAC^0|0|0|N|6|0|0|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|S|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|T|8|@]|9|@$F|U|G|V|1|W]]|A|$]]|$1|H|3|I|5|6|7|X|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Y|8|@]|9|@]|A|$]]]|K|$L|$5|M|N|O|A|$P|Q]]]]

You can think of it as the Binary Search Algorithm.
In each iteration, we ask a question, which should eliminate roughly half of the possible word choices. If there are total of N words, then we can expect to get an answer after log2(N) questions.

With 20 question, we should optimally be able to find a word among 2^20 = 1 million words.

One easy way to eliminate outliers (wrong answers) would be to probably use something like <a href="http://en.wikipedia.org/wiki/RANSAC" rel="noreferrer">RANSAC</a>. This would mean, instead of taking into account all questions which have been answered, you randomly pick a smaller subset, which is enough to give you a single answer. Now you repeat that a few times with different random subset of questions, till you see that most of the time, you are getting the same result. you then know you have the right answer.

Of course this is just one way of many ways of solving this problem.

blocks|key|1337911|text|决策树直接支持这种应用程序。决策树通常在人工智能中使用。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1337912|决策树是一种二叉树，它在每个分支上询问“最好的”问题，以区分由其左子节点和右子节点表示的集合。最好的问题由20个问题应用程序的创建者用来构建树的一些学习算法确定。然后，正如其他海报所指出的那样，一棵20层深的树会给你带来一百万样东西。|1337913|在每个点上定义“最佳”问题的一种简单方法是寻找一个最均匀地将集合一分为二的属性。这样，当你得到这个问题的是/否答案时，你在每一步都会删除大约一半的集合。这样你就可以近似二进制搜索了。|1337914|维基百科给出了一个更完整的例子：|1337915|http://en.wikipedia.org/wiki/Decision_tree_learning|offset|length|1337916|以及一些一般背景：|1337917|http://en.wikipedia.org/wiki/Decision_tree|1337918|entityMap|0|LINK|mutability|MUTABLE|url|1^0|0|0|0|0|0|1F|0|0|0|0|16|1|0^^$0|@$1|2|3|4|5|6|7|X|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Y|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|Z|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|10|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|11|8|@]|9|@$J|12|K|13|1|14]]|A|$]]|$1|L|3|M|5|6|7|15|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|16|8|@]|9|@$J|17|K|18|1|19]]|A|$]]|$1|P|3|-4|5|6|7|1A|8|@]|9|@]|A|$]]]|Q|$R|$5|S|T|U|A|$V|I]]|W|$5|S|T|U|A|$V|O]]]]

A decision tree supports this kind of application directly. Decision trees are commonly used in artificial intelligence.

A decision tree is a binary tree that asks "the best" question at each branch to distinguish between the collections represented by its left and right children. The best question is determined by some learning algorithm that the creators of the 20 questions application use to build the tree. Then, as other posters point out, a tree 20 levels deep gives you a million things. 

A simple way to define "the best" question at each point is to look for a property that most evenly divides the collection into half. That way when you get a yes/no answer to that question, you get rid of about half of the collection at each step. This way you can approximate binary search.

Wikipedia gives a more complete example:

<a href="http://en.wikipedia.org/wiki/Decision_tree_learning" rel="noreferrer">http://en.wikipedia.org/wiki/Decision_tree_learning</a>

And some general background:

<a href="http://en.wikipedia.org/wiki/Decision_tree" rel="noreferrer">http://en.wikipedia.org/wiki/Decision_tree</a>

blocks|key|1553686|text|它标榜自己是“互联网上的神经网络”，关键就在这里。它可能将问题/答案概率存储在备用矩阵中。使用这些概率，它能够使用决策树算法来推断出哪个问题最适合缩小下一个问题的范围。一旦它将可能答案的数量缩小到几十个，或者如果它已经达到20个问题，那么它就开始阅读最有可能的答案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1553687|20q.net真正耐人寻味的方面是，与我所知的大多数决策树和神经网络算法不同，20q支持稀疏矩阵和增量更新。|1553688|编辑:答案一直都在网上。发明者Robin+Burgener在他的2005+patent+filing中详细描述了他的算法。|offset|length|1553689|entityMap|0|LINK|mutability|MUTABLE|url|http://www.google.com/patents/US20060230008?dq=Artificial%2520neural%2520network%2520guessing%2520method%2520and%2520game^0|0|0|W|I|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@$F|S|G|T|1|U]]|A|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]]]

It bills itself as "the neural net on the internet", and therein lies the key. It likely stores the question/answer probabilities in a spare matrix. Using those probabilities, it's able to use a decision tree algorithm to deduce which question to ask that would best narrow down the next question. Once it narrows the number of possible answers to a few dozen, or if it's reached 20 questions already, then it starts reading off the most likely.

The really intriguing aspect of 20q.net is that unlike most decision tree and neural network algorithms I'm aware of, 20q supports a sparse matrix and incremental updates.

Edit: Turns out the answer's been on the net this whole time. Robin Burgener, the inventor, described his algorithm in detail in his <a href="http://www.google.com/patents/US20060230008?dq=Artificial%20neural%20network%20guessing%20method%20and%20game" rel="noreferrer">2005 patent filing</a>.

Simple online games of 20 questions powered by an eerily accurate AI.

How do they guess so well?

How do 20 questions AI algorithms work?

20个问题的简单在线游戏由一个精准得离奇的人工智能提供支持。他们怎么能猜得这么准呢？

问20个问题AI算法是如何工作的？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问20个问题AI算法是如何工作的？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问20个问题AI算法是如何工作的？
EN