621. LLM 20 Questions | llm-20-questions
我参加这场竞赛正好大约三个月前，心中有一个特定的目标——赢得奖金。我承认，我得付账单。信不信由你，尽管拥有人工智能博士学位，我却几乎 3 年找不到工作。数百份申请被无数人力资源部门拒绝，没有任何反馈，或者最多经过简短的面试，而且，我没有任何天文数字般的期望。所以我不再找工作了。我对 Kaggle 很满意。是的，每次我获奖我都会讲这个故事，这将是我的复仇！xD
回到正题，关于字母二分法（alphabetical bisection）有很多争议。对于那些没有关注的人，让我 refer 到这篇帖子和评论，它提出了这种方法，最终主导了前 20 名。我知道很多人对此不高兴，因为它不符合竞赛的原始概念。好吧，这是一个现实检查。它就在那里，不难发现，等待着被使用，无论是公开地还是秘密勾结。所以我认为防止任何秘密勾结的最好方法是公开地提出它。 retrospectively，我不知道这种勾结是否真的能成功，但在当时看起来是一个真正的威胁。
所以不再多反思，让我描述一下解决方案，首先从我的两个智能体之间的区别开始——一个是主动的 Alpha，总是提供友好的握手，希望相互理解。第二个是害羞的 Omega，只接受握手但从不主动伸出。尽管起初落后并在坑里待了一段时间，但主动的 Alpha 一旦遇到其他 Alpha 和半 Alpha 后表现要好得多。但我的 Omega 也表现得相对不错，它在半 Alpha 和非 Alpha 智能体中得分最高，为 1081.7。紧随其后的是 YOLO @manh152924，得分为 1036.7——恭喜伙计！
比提问者/猜测者简单得多，它只有三个组件：
显然，正则表达式处理器可以处理所有常见的“首字母”、“结尾是”以及类似的问题。这只是做功课以确保尽可能与提问智能体合作的问题。有点奇怪的是，有些玩家会想出他们自己的“原创”问题，而那里已经有了更常见的语法。在我看来这是一个错误，当然我做功课主要是为了我的智能体的利益，而不是他们的，但毕竟这并不太重要。
Alpha 回答者也是基于正则表达式匹配，只是它是 Alpha 智能体类的一部分。
当问题没有被任何正则表达式匹配时，它被传递给 Llama 3， vanilla HuggingFace 8b-instruct。我也试过 Phi3 和 Gemma 2b 和 7b，但我发现 Llama 3 回答简单问题相当好，而且在其他子任务中也不错，所以我坚持用它。起初，我在过于花哨的答案和 incorrect format 上挣扎，但将 temperature 降到最低，并给它一个 6-shot 用户提示足以确保它坚持快速回答“是”或“否”，快速 timing 对于测试也很重要。
一个小技巧是根据问题是否涉及"keyword"或"it"使用略有不同的提示，例如"Is the keyword related to nature?"与"Is it related to nature?"。不过，我甚至没有尝试测量这是否对答案质量有任何影响。
无论如何，回答者部分只在与非 Alpha 智能体玩耍时很重要，因为对于 Alpha 搜索，回答者只是一个 trivial 的单行代码。
总的来说，我发现尝试任何 elaborate"prompt 系统"时与 LLM 一起工作有点繁琐。很难看到 prompt 的哪些部分会被 LLM“理解”，哪些只会混淆它们。也许方法论可以在未来改进，也许它会演变，但现在它基于试错且相当繁琐。
提问和猜测管道是 tied together 的，所以我将一起描述它们。它们由 3 个组件组成，优先级如下：
无论该顺序中的哪个智能体可以根据上下文响应适当的问题或猜测，都会发送响应。
当关键词已知且每个关键词在游戏期间成为秘密关键词的可能性相等时，它 simply optimal。当然有许多其他同样 optimal 的"vehicles"进行二分法，可以用正则表达式完成，或者询问秘密关键词是否“在这个非常长的关键词列表上”等。然而，我想不出比使用字母顺序二分法更简单清晰的方法了。
当可能的秘密关键词列表（即私有关键词）未知时，它变得更棘手。整体性能问题转移到我们词汇的质量上，即覆盖了多少私有关键词以及我们的词汇有多大。此外，有可能利用我们对语言的 knowledge 以及私有集应该与公共集"similar"的事实。
理论上，算法可以在 unlimited 关键词列表上工作，每个关键词被分配成为秘密关键词的可能性。如果我们继续根据可能性之和二分词汇（@cnumber 做到了！）并且只从所有剩余关键词中猜测最可能的关键词，那么性能仍然可以是 optimal——它将仅取决于我们可能性的质量，如果分配 perfect，整个解决方案将再次 unquestionably optimal。
我的 Alpha 中的词汇正好是 60,008 个关键词，其中包括公共关键词以防万一——事实证明一段时间内确实是这样。关键词是从几个来源收集的：
将它们编译成一个好列表有点 messy，主要是因为复数，但也因为一些关于 normalizations 的 dilemmas，例如字母大小写、标点符号、数字和破折号、联合与分开拼写等。好吧，我认为从词汇中删除复数/单数替代方案是非常 worthwhile 的（特别是对于 Omega 智能体），但这并不完全 straightforward。我没有找到任何 fully reliable 的方法来处理这么大的关键词字典，其中许多是 2 个单词甚至 3 个单词长。我发现最好的是 inflect 包。我也试过使用 Llama，但它在这个任务上一点也不好，而且很慢。直到后来，在评估期间我才想到，词汇中只有复数或单数形式实际上是一个错误！对于那些还没有考虑过的人——假设秘密关键词是"shoe"，但我们的词汇中没有单数形式，只有复数。在某个时刻 Alpha 可能会问，"Does the keyword precede 'shoes' in alphabetical order?"——答案是"yes"，我们刚刚排除了"shoes"，好像它与"shoe"完全是不同的东西。相比之下，下面描述的 Omega 智能体根本没有这个问题，清理词汇中的复数/单数替代方案实际上是 beneficial 的。同样的情况也适用于复合与分开拼写，例如"anthill"与"ant hill"。
无论如何，我最终得到了 60,008 个关键词，其中 1468 个结果是 exact hits。1798 个私有关键词中的 1468 个还不错，也许是因为私有关键词比我预期的要简单。
最终的关键词列表实际上具有 ranking 的形式，每个关键词根据其来源的"qualities"都有一个分数。来源的质量是根据其列表与公共关键词列表的相似程度计算的，如果关键词在多个来源中，其分数会累加。所以我有一个美丽的 ranking，然后……我忘了应用它来提高猜测准确性。这无疑是我解决方案的最大缺陷，我相信如果它到位会有很大不同。基本上，不是从词汇中弹出任何单词作为猜测，它应该是具有最高 rank 的关键词，即最常用和最简单的可用关键词。当我看到 Benjamin Kovacs 的智能体在开始时出乎意料地很好地猜测关键词时，我意识到我忘了完成这部分。只缺少 2 行简单的代码。@isakatsuyoshi 也有类似的想法，虽然有点 coarse——它涉及两个关键词子集，较容易的和较难的。幸运的是，没有多少其他 Alpha 应用了这个基本技巧，或者至少不那么明显。
为了估计猜测性能的差异，让我们只考虑秘密关键词在词汇中的那 1468 种情况。使用 uniform guessing，关键词预计在大约 1 + log2(30004) = 15.87 轮中找到。如果正确应用 ranking，秘密关键词在词汇中的平均索引或位置是 6123.2，且 1 + log2(6123.2) = 13.58。因此，在 1468/1798 -> 82% 的游戏中，秘密关键词平均会提前 2.3 轮找到。
你看，有些玩家看不起这样一个 CS 学生可以在课堂上实现的简单算法。然而为什么这么容易错过同样简单的改进并使其更好？也许是因为只有在看到之后才容易？当然另一个因素是 Alpha 预计在决赛中不会发挥如此大的作用，甚至我比其他部分更专注于解决方案的其他部分而不是字母搜索。
回到词汇，仍然有 330 个关键词缺失，这就是当游戏中词汇耗尽时字母搜索扩展介入的地方。搜索以 bounds 结束，例如"tow truck"和"towel"，我们要求 Llama 在 bounds 内生成更多候选者。复杂的是 LLM 不擅长字母和这样的 completions*。但可以帮助它们。迭代地：
通过这个过程，bounds 应该保持一致 narrowing down，除非当然 LLM 完全不知道如何为给定的下一个字母完成 prefix。这个过程有点 tricky 并且也 causing 一些 timeout 麻烦，但我最终设法将其限制在安全的时间限制内（也感谢 @matthewsfarmer 的建议），幸运的是它从未出错。我对它的有效性感到惊讶，我没有确切测量，但我粗略估计是，给定我的词汇和剩余的 3 次猜测，这个扩展大约 40% 的时间可以成功完成搜索。
*) 在他的解决方案中，@cnumber 提到了 specialized models，也许可以自己完成整个 trick。
我认为类似的想法已经在 Kha Vo 的 notebook 以及 majimekun 的解决方案中描述过，也许还有其他一些。它涉及一组固定的问题和一组带有 annotated"correct"答案的固定关键词——即我们在 knowledge base 中知道 A 是关键词 K 的问题 Q 的正确答案。注意 A 可以是二进制的"yes"或"no"，但更好的是它可以表示为 0.0 到 1.0 之间的 truth degree。
所以假设我们有这个 matrix，我们从 uniform distribution 的 prior probabilities 开始，表示每个关键词成为秘密关键词的概率。然后，问题的选择方式是为了最小化该概率分布上的 entropy。Miraculously 选择的第一个问题是那个会产生尽可能多的"bisection"的问题。概率分布的 entropy 相当 strange 且不易 visualize 或 conceptualize，所以它 work almost like magic。
一旦答案到达，我们可以相应地更新概率。在一个 prototype 中，我尝试使用一些 heuristics 更新，例如：增加答案匹配的关键词的概率，否则减少。它 work 了，但很快我发现只有一种 correct 的方式来做这件事——贝叶斯更新 (Bayesian Update)。
虽然 entropy minimization 负责选择可用的最佳问题，但 Bayesian update 以 best way possible 跟踪概率分布。所以基本上在每个问题和答案之后，我们根据以下内容更新整个概率分布 P(H|E)：
P(H),P(E) 和P(E|H)。P(H|E) = (QR * P(H) + (1 - QR) * (1 - P(H)) * P(E|H) / P(E)有点 surprising 的是"question reliability"，即 QR，毫无 trouble 地找到了它在 Bayes' theorem 中的位置。注意，它也可以称为"answer reliability"或只是"hearing the truth 的概率"。也许它在理论上没有 well-founded，或者甚至有什么 wrong，但它 work 了。
Interestingly，这种 extremely robust 的方法允许我们以任何顺序询问任何问题， without any particular semantic"narrowing down"。实际上这是 go this direction 的主要原因——拥有一组 easy 的 universal questions，而不是 sophisticated 和 labour-demanding 的 increasingly specific questions 树。理论上，我们可以询问 literally any nonsensical question 并且仍然获得 useful information，provided：
这个 engine 还有几种方式可以 further enhanced。
如前所述，knowledge base 中的答案是truth degree，即 contained some uncertainty，这 undoubtedly 使更新更 smooth。所以当从 Llama 3 收集答案时，prompt 允许 express some degree of confidence，因此答案可以 easily scaled 到 [0.0; 1.0] 范围。我选择 solely rely on Llama，然后使用 Llama 3.1 进行 verification，而不是像 ChatGPT 这样更 powerful 的 models， mainly because 我 figure 虽然 ChatGPT 可能 objectively more accurate，但 Llama 3 答案将有一些"compatibility"advantage，因为许多玩家显然使用 Llama 作为他们的 answerer。
我们可以 easily account for"answer reliability"或"question reliability"， whichever is available to us。在我的情况下，我从 Llama 3 收集了大约 95 个问题和 5294 个 top ranked 关键词的答案，其中 1039 个是 exact hits，如果包括复数/单数替代方案则有 1079 个 hits。与字母搜索不同，复数/单数形式在这里不是问题，并且最好只有一个形式。许多问题是 nested 或 conditional 的——如果"Is it edible?"的答案是"no"，就没有必要问"Is it sweet?"。但如前所述，我不想 go into it too much，只是一个 crude shallow tree，最多 1 级 nesting。
为了 estimate question reliability，我使用了 Llama 3.1 和 real answerer prompt，只给出"yes"或"no"，在 keywords 的 subsample 上以减少 effort。结果证明有些问题 highly reliable，高于 90%，而有些其他问题低于 80%。reliability simply inversely proportional 到 Llama 3 的 truth degree 和 Llama 3.1 的 plain answer 之间的 mean absolute error。这些信息用于 question selection 和 Bayesian update。所以 naturally 具有高 reliability 的问题被 preferred，因为它们能够更快地 bring down the entropy。
我也非常 liberally 地使用了问题"Does the keyword start with one of the letters 'A', 'B' or 'C'?"。实际上大约 15 个这样的问题为 random letters 在每一轮生成，我可以 simply leave it to the question selection by entropy minimization 来决定它们是否 good。也许我的智能体问的那些问题看起来有点 chaotic，但它在 control 之下。这些问题的 reliability 不容易 beforehand figure out，所以我 just assumed 它们在评估开始时 reliability 为 0.88，到结束时上升到 0.95。只是一个 crude assumption 但我认为比 assuming default 1.0 reliability rate 好。
Omega 提问者/猜测者在 self-play 中 work very well，当秘密关键词在其 knowledge base 中时，guess rate 约为 95%。但如果它 missing，那么它就根本无法猜测它。所以这里来了 rescue——Llama 3，它将 basically take all the knowledge gathered so far in a game，along with Omega 的"similar things"列表并 suggest a new guess。无论猜测如何，问题仍然可以由 Omega 询问。我也试过使用 Llama 询问问题，但 too often 它们是 erratic 的，此外，Omega 不能使用这些问题来更新概率并 suggest most likely similar things。我为 Omega 设置了 16 轮 limit，之后 Llama 获得剩余的 4 次 shots。这种方法 not very effective，though，roughly 只有 1/10 的游戏可以在 self-play 中由 Llama 成功完成 missing keywords。
这是一段漫长的 journey。终点线前的几个小时内 top spot 就在 reach 范围内，但我不 feel much regret 它 slipped out。我 anyway 有很多 luck，所以请让我 congratulate 赢家 @cnumber 和 runner-up @jademonk，以及 lucky guys 第 4 名 @jasperbutcher 和第 5 名 @yukkymaru。同时，我只能 sympathize 与那些 ended up within a single score outcome from the end zone 的其他玩家。我知道 agent alpha 在 final decider 中 played a role，但 surely everybody know 它 wasn't picking sides。Congrats 给所有 medalists，我 afraid I have to stop there，因为"finishers"已经 consumed enough GPU。
Many thanks 给 organizers 和 players 对于这个 season。Thank you, @bovard，for taking action when it was necessary and only when absolutely necessary。And special thanks 给 @cdeotte 和 @khahuras for being friendly and helpful to everybody all the way。See you in another challenge soon!