AI算法有20个问题如何工作？

20个问题的简单在线游戏,由精确的AI精确驱动.

他们怎么猜得那么好？

1> Yogi..：

---

您可以将其视为二进制搜索算法.在每次迭代中,我们提出一个问题,该问题应该消除大约一半可能的单词选择.如果总共有N个单词,那么我们可以期望在log2(N)个问题之后得到答案.

有了20个问题,我们应该能够在2 ^ 20 = 100万个单词中找到一个单词.

消除异常值(错误答案)的一种简单方法是使用像RANSAC这样的东西.这意味着,您不必考虑所有已回答的问题,而是随机选择一个较小的子集,这足以给您一个答案.现在你用不同的随机问题子集重复几次,直到你看到大部分时间,你得到相同的结果.然后你知道你有正确的答案.

当然,这只是解决这个问题的多种方法之一.

---

这个简单的程序很好地展示了你所谈论的内容.到达那里后,您可以点击"code"链接查看:http://openbookproject.net/py4fun/animal/animal.html

2> Nathan Shive..：

---

决策树直接支持这种应用程序.决策树通常用于人工智能.

决策树是二叉树,它在每个分支处询问"最佳"问题,以区分由其左右子代表的集合.最好的问题是由20个问题应用程序的创建者用来构建树的一些学习算法确定的.然后,正如其他海报所指出的那样,20层深的树给你一百万件事.

在每个点定义"最佳"问题的一种简单方法是查找最均匀地将集合划分为一半的属性.这样当你得到该问题的是/否答案时,你就会在每一步中摆脱大约一半的收集.这样您就可以进行二进制搜索.

维基百科提供了一个更完整的例子:

http://en.wikipedia.org/wiki/Decision_tree_learning

还有一些一般背景:

http://en.wikipedia.org/wiki/Decision_tree

---

+1，我会注意到这是Atwood文章中的评论之一。

3> cgp..：

---

我建议在这里阅读有关游戏的内容:http://en.wikipedia.org/wiki/Twenty_Questions

特别是计算机部分:

该游戏表明识别任意对象所需的信息(由Shannon的熵统计量测量)约为20位.在向人们讲述信息理论时,游戏通常被用作一个例子.在数学上,如果每个问题的结构都是为了消除一半的对象,那么20个问题将允许提问者区分2 ²⁰或1,048,576个主题.因此,二十个问题最有效的策略是提出一些问题,这些问题将每次剩余可能性的范围大致分成两半.该过程类似于计算机科学中的二进制搜索算法.

---

这解释了一些.但是当你考虑不正确的答案和一般模糊性时,它似乎仍然不是那么简单.

4> Cerin..：

---

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 2005 patent filing.

5> 小智..：

---

它使用的是学习算法.

k-NN就是其中之一的一个很好的例子.

维基百科:k-最近邻算法

---

在这种情况下,最近邻算法是一个不错的选择吗？似乎对错误的答案过于宽容,并且最终可能会有大量的维度,其中许多都没有数据.(我假设使用汉明距离,每个问题一维.)决策树看起来更自然.