Eliciting Thinking Hierarchy without a Prior

Abstract

针对无法验证答案的众包任务，传统思路：选择大多数人支持的答案

存在问题：大多数人犯系统性错误，会导致最终结果出错

本文希望：在没有任何先验的情况下，在所有答案中建立一个等级制度，使得根据该制度得到的排名较高的答案（可能不被大多数人支持）来自更可靠的人

本文提出：

1. 一个新的模型来描述人们的思维层次

2. 两种算法来学习没有任何先验的思维层次

3. 一种基于上述理论框架的新的公开回答的众包方法

本文实验：

1. 本文方法所学习到的排名靠前的答案的准确度远远高于全体投票（在一个问题中，全体投票的答案得到了74名受访者的支持，但正确答案只得到了3名受访者的支持。我们的方法在没有任何先验的情况下将正确答案排在最高位置）

2. 本文模型有很高的拟合度，特别是对于我们排名第一的答案是正确的问题

Introduction

群体智慧在面对系统性错误的时候往往会得出错误结果

一个例子：圆A的半径是圆B半径的1/3，圆A绕着圆B转了一圈后回到起点。圆A总共会旋转多少次？

根据实验，有11个人认为是1次，8个人选2次，134个人选3次，16个人选4次，27个人选6次，21个人选9次。显然在多数一致的众包任务中，这个题的答案会被认为是3次，但其实正确答案是4次，只有16个人选。

如果事先了解所有受访者的先验水平，我们也许能根据大家的专业水平来确定正确答案，但是在大多数众包场景中，往往没这样的先验知识。

为了解决上述问题，Prelc等人[15]提出了一种创新的方法，他们准备了多个选择，要求受访者挑选一个选项，并预测其他人的选择分布。他们使用预测结果来构建一个关于选择的先验分布，然后选择比先验分布更受欢迎的选择，这样就纠正了偏见（是2017年的nature）。许多其他工作[10, 5, 16]发展了使用先验或预测来纠正偏差的想法。

然而，首先，将以前的方法应用于运行中的例子，即圆圈问题，是不适用的，因为它们需要先验知识来设计选择。让受访者报告所有选择的整体分布也很费力。第二，以前的工作主要是利用预测来纠正偏见，而利用他们的预测来建立一个思维层次是内在的问题。这也导致了答案之间的层次性。著名的认知分层理论（CHT）[21, 22, 3]在人们玩游戏的场景中建立了一个思维理论，这样我们就可以学习不同复杂程度的玩家的行动。然而，CHT只是为游戏理论环境设计的。我们对在一般的问题解决场景中建立一个思维理论感到好奇。该问题的关键在于，水平较高的人知道水平较低的人的想法，但反之则不然[3, 9]。我们想应用这个见解来学习不同复杂程度的人的答案，称为思维层次，而不需要任何先验。

关键问题：我们的目标是建立一个实用的方法，在没有任何先验的情况下学习思维层次。基于思维层次，我们可以对答案进行排序，这样，排名较高的答案，可能不被大多数人支持，但是来自更可靠的人。

层次性思维方式的优势除了在于选出正确答案以外，还有以下几点：

1. 一些主观性问题可能有多个高质量答案，完整的层次结构能提供更丰富的结果。

2. 答案的层次性有助于更好地理解人们的思维方式，尤其当我们试图征求人们对某项政策的意见时这一点更重要。

本文方法：和以往研究一样，让受访者同时写出自己的回答和对其他人答案的预测，并将其扩展到一个更实用的基于开放回答的范式。该范式提出了一个单一的开放回答问题，并要求每个回答者的答案和对其他人的答案的预测。例如，在圆圈问题中，一个回答者可以提供：答案。”4”，预测。”3”。然后我们构建一个答案-预测矩阵A，记录报告特定答案-预测对的人数。（例如，图2（a）显示有28人回答 “3”，预测其他人回答 “6”）。

为了学习思维层次，本文提出了一个新颖的模型，它描述了不同复杂程度的人如何回答问题，和预测其他人的答案。回答者的答案和预测的联合分布取决于描述人们思维层次的潜在参数。本文表明，鉴于回答者的答案和预测的联合分布，可以通过解决非负矩阵分解问题的一个新变体来推断潜在的思维层次，该问题被称为非负全等三角化（NCT）。基于对NCT的分析，本文提供了两个简单的答案排序算法，并表明在适当的假设下，给定应答者的答案和预测的联合分布，这些算法将学习潜在的思维层次。

直接一些来说，就是专业人士不仅能答对，还能知道业余者会犯什么错。

最后，本文将答案和预测的联合分布表示为答案-预测矩阵，并在该矩阵上实现了基于NCT的答案排序算法。默认的排序算法是使矩阵上三角区域内的元素的平方和最大化，在变体的排序算法中，为了让不同的答案具有相同的复杂程度，答案被分割以压缩矩阵，该算法使压缩后的矩阵的上三角区域的平方和最大化。

在实验方面，进行了包括数学、围棋、常识和字符发音的实证研究。

需要说明的是：在前面那个矩阵图中，因为默认算法不需要用对角线的元素，所以这里对角线上的元素不再是答案-预测的人数，而是选择了这个答案的人数，这样方便和普通的多数一致众包方法做对比，例如那个矩阵里(3,3)对应的134表示有134个人回答了3，而不是说这么多人自己回答3也预测别人回答3。

Related Work

先略，以下是从他们公众号的介绍里复制来的内容：

正如前文所言，在没有先验的情况下，很难对这些答案采取支持度以外的排序方式。Prelec [1], Prelec et al. [2] 通过在单选题中额外询问回答者对各个选项分布的预测，进而构造先验信息，并汇总答案为支持度“令人意外地高”的选项，并实验证明该方法比多数决有效。Rothschild and Wolfers [3] 在民调时除了询问“你会选谁”，还额外询问选民“你觉得谁会得到更多的支持”，并实验证明额外信息具有更高的信息量。

类似地，我们采用了一套基于填空题的问卷调查方式：

“你的答案是？”

“你觉得别人会答什么？”

与之前工作不同，在以上框架下，询问者无需任何先验设计选项，回答者无需提供分布信息。针对答案的汇总，Kong and Schoenebeck [4] 提出一个猜想：“专业度高的人可以预测专业度低的答案，反之不然。”

这个猜想和行为经济学有限理性理论中的等级 k（Level-k）[5] 以及认知等级（Cognitive Hierarchy）[6] 理论相似，都认为人在逻辑思考推理中存在不同的等级。等级 k 和认知等级理论认为高等级知道低等级的存在并采取针对低等级的最优策略。

Learning Thinking Hierarchy

Thinking hierarchy

给定一个问题q（例如圆圈问题），T表示思维类型的集合，A表示可能出现的回答的集合，这两个都是有限集，$\Delta_A$表示A的所有可能分布。

Generating answers：说明不同思维类型的人是如何得出答案的。

定义2.1：思维类型的预言机W：一个生成答案的预言机（an anwser generating oracle，不太理解这是指生成预言机的答案还是指生成答案的预言机，感觉是后者）将问题映射到集合A中的（随机）答案。每一个类型t都对应了一个预言机$O_t$，$O_t(q)$的输出是一个随机变量，其分布是$w_t\in \Delta_A$。$W$是一个$|T|\times|A|$矩阵，其中每一行是$w_t$。

每一个受访者都有概率$p_t$是类型$t$，且$\sum_t p_t=1$，类型t的受访者通过运行预言机$O_t$得到自己的答案。对于所有$a\in A$，一个受访者回答$a$的概率是$\sum_t p_tw_t(a)$，假设对于所有$a\in A$，概率都是正的。

例2.2（运行示例）：有两种思维类型$T=\{0,1\}$，回答空间是$A=\{3,4,6\}$，预言机$O_0$有0.8的概率输出3，0.2的概率输出6；$O_1$会直接输出4。在这个例子中，$W=[\begin{matrix}0.8&0&0.2\\0&1&0 \end{matrix}]$，其中第一行是$O_0$的输出，第二行是$O_1$的输出。

Generating predictions：说明不同思维类型的人会如何预测其他人的回答。这里的预测不是一个分布，而是一个其他人可能会报告的答案。当类型t的受访者预测时，她会运行一个预言机来得到预测结果$g\in A$，该预言机有概率$p_{t\rightarrow t’}$等于$O_{t’}$，其中$\sum_{t’}p_{t\rightarrow t’}=1$。

Combination: answer-prediction joint distribution M：M表示一个$|A|\times |A|$的矩阵，其中$M_{a,g}$是受访者回答a且预测他人回答g的概率，$\Lambda$表示一个$|T|\times |T|$的矩阵，其中$\Lambda_{t,t’}$是受访者为类型t且预测他人类型t'的概率。

例2.3：在本例中，当类型0的受访者进行预测时，她会以概率1再次运行预言机$O_0$。当类型1的受访者进行预测时，她会以0.5的概率运行预言机$O_0$，0.5的概率运行预言机$O_1$。且受访者有0.7的概率是类型0，0.3的概率是类型1。则$\Lambda=[\begin{matrix}p_0p_{0\rightarrow 0}&p_0p_{0\rightarrow 1}\\p_1p_{1\rightarrow 0}&p_1p_{1\rightarrow 1}\end{matrix}]=[\begin{matrix}0.7&0\\0.15&0.15\end{matrix}]$

观点2.4：基于以上生成过程，$M=W^{\top}\Lambda W$。
证明：对于每一个受访者，她回答a且预测g的概率为

$$M_{a, g}=\sum_t p_t \mathbf{w}_t(a) \sum_{t^{\prime}} p_{t \rightarrow t^{\prime}} \mathbf{w}_{t^{\prime}}(g)=\sum_{t, t^{\prime}} \mathbf{w}_t(a) p_t p_{t \rightarrow t^{\prime}} \mathbf{w}_{t^{\prime}}(g)$$

我们对所有受访者可能的类型进行求和，假定她的类型为t，则她会运行预言机$O_t$来得到答案，且有概率$w_t(a)$得到答案a。我们对她所有可能为了预测而运行的预言机进行求和，假定她运行$O_{t’}$，则预测为g的概率是$w_{t’}(g)$。

一些补充说明：这里从证明到2.4的过程我其实没完全搞明白，姑且写一下理解：

首先$w_t(a)$就是矩阵W的第t行第a列的元素，中间的$p_tp_{t\rightarrow t’}$是矩阵$\Lambda$的第t行第t'列的元素，最后的$w_{t’}(g)$是第t'行第g列的元素。

接下来回顾一下矩阵相乘的公式：
矩阵A和矩阵B相乘得到矩阵C，其计算方法是：

$$C_{i,j} = \sum_{k=0}A_{i,k}B_{k,j}$$

由此可以推导出，三个矩阵连乘法的计算方式：

$$D_{i,m}=\sum_{j=0}(\sum_{k=0}A_{i,k}B_{k,j})C_{j,m}=\sum_{j=0,k=0}A_{i,k}B_{k,j}C_{j,m}$$

回到前面2.4的公式来看，

$$M_{a, g}=\sum_{t, t^{\prime}} \mathbf{w}_t(a) p_t p_{t \rightarrow t^{\prime}} \mathbf{w}_{t^{\prime}}(g)=\sum_{t, t^{\prime}}W_{t,a}\Lambda_{t,t'}W_{t',g}$$

显然，如果能把第一个$W_{t,a}$的行列交换一下，这个公式就可以改写为三个矩阵连乘了，而这恰好就是矩阵转置，即$W_{t,a}=W_{a,t}^\top$。由此，就可以得出$M=W^{\top}\Lambda W$。

关键假设：上三角(upper-triangular)$\Lambda$. 我们假设，水平较低的人永远无法运行水平较高的预言机。类型$\pi:\lbrace 1,2,3,…,|T| \rbrace \mapsto T$的线性排序将排名位置映射到类型。例如，$\pi(1)\in T$是排序最高的类型。

假设2.5：我们假设，在类型的适当排序$\pi$下，$\Lambda$是一个上三角矩阵。形式上而言，存在$\pi$使得$\forall i > j, \Lambda_{\pi(i),\pi(j)}=0$。任意能使$\Lambda$为上三角形式的$\pi$都是这些类型的一种有效的思维层次。

在运行示例（例2.2）中，有效的思维层次是$\pi(1)$为类型1，$\pi(2)$为类型0。需要注意的是，在上面的假设中，并不要求$\forall i \leq j, \Lambda_{\pi(i),\pi(j)}>0$，当$\Lambda$为对角矩阵时，类型之间不能相互预测，而且同样复杂，因此任何排序都是有效的思维层次。

给定由未知的w和$\Lambda$生成的M，算法可以寻找其思维层次，并输出矩阵$W^\ast$，它等价于行顺序是有效思维层次的行置换后的W。形式上而言，存在一种有效的思维层次$\pi$使得$W^\ast$的第i行是$W$的第$\pi(i)$行，即$w_i^\ast=w_{\pi(i)}$。

Non-negative Congruence Triangularization (NCT)

在上述模型中，推断思维层次引出了一个新的矩阵分解问题，这个问题类似于对称非负矩阵分解问题(NMF)。

定义2.6：非负同余三角化(NCT)。给定非负矩阵M，NCT旨在寻找非负矩阵W（是不止一个非负矩阵）和非负上三角矩阵$\Lambda$，使得$M=W^\top\Lambda W$。在一个基于 Frobenius 范数的近似版本中，给定矩阵W的集合，NCT旨在寻找非负矩阵W（是不止一个非负矩阵）和非负上三角矩阵$\Lambda$，从而最小化：

$$\min _{\mathbf{W} \in \mathcal{W}, \boldsymbol{\Lambda}}||\mathbf{M}-\mathbf{W}^{\top} \boldsymbol{\Lambda} \mathbf{W}||_F^2$$

得到的最小值被定义为：M关于$\mathcal{W}$的不适度(lack-of-fit)。

类似NMF，要求结果的严格唯一性是不可能的。令$P_{\Lambda}$表示能使得$\Pi^\top\Lambda\Pi$仍然是上三角的置换矩阵的集合。如果$(W,\Lambda)$是一个解，则当D是所有元素为正数的对角矩阵且$\Pi\in P_\Lambda$时，$(\Pi^{-1}DW, \Pi^\top D^{-1}\Lambda D^{-1}\Pi)$也是一个解。我们将唯一性结果陈述如下，并在附录C中证明。

定理2.7：唯一性。如果$|T|\leq |A|$，且W的T列包含一个置换正对角矩阵，则$M=W^\top\Lambda W$的NCT是唯一的，因为对于所有的$W’^\top\Lambda’ W’=W^\top\Lambda W$，都存在一个正对角矩阵D和一个$|T|\times |T|$置换矩阵$\Pi\in P_\Lambda$，使得$W’=\Pi^{-1}DW$。

当我们将W限制为半正交时，就可以在不需要寻找最优$\Lambda$的情况下得到NCT的简洁格式。$\mathcal{I}$是所有半正交矩阵W的集合，其中W的每一列有且仅有一个非零元素，且$WW^\top=I$。例如，例2.2中的矩阵W可以被标准化为半正交矩阵，下面的引理来自于 Frobenius 范数的扩展，我们在附录C中进行证明。

引理2.8：半正交：最小F范数=最大化平方的上三角和。对于所有矩阵$\mathcal{W}\subset \mathcal{I}$的集合，$\min _{\mathbf{W} \in \mathcal{W}, \boldsymbol{\Lambda}}||\mathbf{M}-\mathbf{W}^{\top} \boldsymbol{\Lambda} \mathbf{W}||_F^2$等价于求解$max_{\mathbf{W} \in \mathcal{W}}\sum_{i\leq j}(\mathbf{W}\mathbf{M}\mathbf{W}^{\top})^2_{i,j}$，且设置$\Lambda$为$Up(\mathbf{W}\mathbf{M}\mathbf{W}^{\top})$，即$\mathbf{W}\mathbf{M}\mathbf{W}^{\top}$的上三角区域。

这里总的来说就是：让回答排名靠前且预测排名靠后的受访者尽量多

Inferring the thinking hierarchy with answer-prediction joint distribution M

给定M，推断其思维层次，等价于求解NCT问题。虽然我们并没有M，但我们可以获取其代理。为了简化实际应用，我们基于引理2.8引入了两个简单的排序算法。排序算法以M为输入，输出所有回答的线性排序结果$\pi:\lbrace 1,2,…,|A| \rbrace \mapsto A$，它表示了排序位置到回答的映射。

回答排序算法（默认）：记作AR(M)，该算法计算

$$\boldsymbol{\Pi}^* \leftarrow \arg \max _{\Pi \in \mathcal{P}} \sum_{i \leq j}\left(\boldsymbol{\Pi} \mathbf{M} \boldsymbol{\Pi}^{\top}\right)_{i, j}^2$$

其中，$\mathcal{P}$是所有$|A|\times |A|$的置换矩阵的集合。对于所有i，在每一个置换矩阵$\Pi$和一个线性顺序$\pi:\Pi_{i,\pi(i)}=1$ 之间都存在一个一对一的映射。因此，最优$\Pi^\ast$会引出所有回答的最优排序，而默认算法也可以表示为：

$$\pi^* \leftarrow \arg \max _\pi \sum_{i \leq j} M_{\pi(i), \pi(j)}^2$$

默认算法隐含假设$|T|=|A|$，且所有预言机都是确定的。为了允许$|T|\leq|A|$和不确定的预言机，我们引入了一个变体，将$\mathcal{P}$推广到半正交矩阵$\mathcal{I}$的一个子集。每一个$|T|\times |A|$的半正交矩阵W表示一个硬聚类，每一类$t\in T$包含了所有使得$W_{t,a}>0$成立的回答。例如，例2.2中的矩阵W可以被标准化为半正交矩阵，并表示一个硬聚类{4},{6,3}。因此，变体算法将把回答划分为多个聚类，并为之分配一个层次结构。

回答排序算法（变体）：记作$AR^{+}(M,\mathcal{W})$，该算法计算

$$\mathbf{W}^{*} \leftarrow \arg \max _{\mathbf{W} \in \mathcal{I}} \sum_{i \leq j}\left(\mathbf{W M W}^{\top}\right)_{i, j}^{2}$$

其中，$\mathcal{W}\subset \mathcal{I}$。$\mathbf{W}^{\ast}$被标准化为每行之和是1。

$\mathbf{W}^{\ast} \Rightarrow$ Answer rank 输出$\mathbf{W}^{\ast}$表示了所有回答的硬聚类。我们按照如下方式对所有回答进行排序：对于任意$i<j$，聚类i中的回答比聚类j中的回答有着更高的排序。对于所有i，任意两个聚类i中的回答a和a'，如果$W_{i,a}^\ast >W_{i,a’}^\ast$，则a排序高于a'。

理论论证：当M完全符合模型约束条件，即隐含的W为置换矩阵或硬聚类时，我们的算法就找到了思维层次。否则，我们的算法会找到由 Frobenius 范数度量的“最接近”的解。

定理2.9：当存在$\Pi_0 \in \mathcal{P}$和非负上三角矩阵$\Lambda_0$使得$\mathbf{M}=\boldsymbol{\Pi}_{0}^{\top} \boldsymbol{\Lambda}_{0} \boldsymbol{\Pi}_{0}$，算法AR(M)可以找到思维层次。一般来说，AR(M)会输出$\boldsymbol{\Pi}^\ast$，其中$\boldsymbol{\Pi}^\ast,\Lambda^\ast = Up(\boldsymbol{\Pi}^\ast M {\boldsymbol{\Pi}^\ast}^\top)$是$\arg \min _{\Pi \in \mathcal{P}, \Lambda}\left|\mathbf{M}-\boldsymbol{\Pi}^{\top} \Lambda \Pi\right|_{F}^{2}$的一个解。把$\mathcal{P}$换成$\mathcal{W}\subset \mathcal{I}$，把AR(M)换成$AR^{+}(M,\mathcal{W})$，上述语句仍然成立。

证明仍然在附录C。

A proxy for answer-prediction joint distribution M

在实践中，我们没有完美的M。我们使用下面的开放式反应范式来获得M的代理。

回答-预测范式：受访者会被问两个问题：

1. 你的回答是什么？
2. 你认为其他人会回答什么？

在圆圈问题中，可能的反馈是：“回答4，预测3”、“回答3，预测6，9，1”等。我们用A表示所有回答的集合。在圆圈问题的例子中，$A=\lbrace 1,2,3,4,6,9 \rbrace$。我们同样允许受访者不进行预测或者预测多个值。

回答-预测矩阵：我们聚合反馈并通过回答-预测矩阵将其可视化。回答-预测矩阵A是一个$|A|\times |A|$的方阵，其中$|A|$是受访者提供的不同答案的数量。每一项$A_{a,g}, a,g\in A$是回答a且预测g的受访者的数量。

我们将证明，在适当的假设下，回答-预测矩阵A的期望与M成正比。首先，为了便于分析，我们假设每个受访者的预测都是独立样本。其次，由于我们允许人们有选择地提供预测，因此我们还需要假设每个受访者愿意提供的预测数量与她的类型和答案无关。我们将形式化的结果陈述如下，并在附录 C中进行证明。

定理2.10：当每一个受访者的预测都是独立样本，并且她给出的预测数量与她的类型和答案无关时，回答-预测矩阵A 的期望与M成正比。

Studies

我们进行了四组研究，分别是：研究1(35道数学题) ，研究2(30道围棋题) ，研究3(44道常识题)和研究4(43道汉字发音题)。

数据收集：通过在线众包平台发送调查问卷来收集数据，所有受访者被要求不能上网搜索或者与其他人交流，受访者可以填写“我不知道”这样的答案。除围棋问题以外，所有问卷采用定额支付的方式，具体过程在附录A。允许受访者参加多个研究，因为算法分别独立计算每一个问题。

数据处理：合并等价的答案，例如0.5和50%。忽略那些选择人数小于等于3%或者只有一个人选择的答案。剩下的答案包括“我不知道”共同组成了大小为$|A|$的回答集合。接下来构建回答-预测矩阵并执行算法，伪代码在附录B。本文算法不要求任何先验知识或受访者的专业水平。

Results

基线算法：投票，即多数一致方案

对比结果：本文的两种算法都比基线算法好

152个问题中，有138个问题变体算法和默认算法得出了相同的思维层次。其他问题中，变体算法得到的排名靠前的答案可能有不止一个。有一个问题，变体算法得到的答案是错的，而默认算法得到的是正确的。

我们同样计算了算法的不适度指标，发现那些算法能输出正确答案的问题都有着低不适度，进而更符合思维层次模型。因此我们可以用不适度作为算法可靠性的指标。

我们还从每个研究中都选取了几个代表性的例子，其矩阵采用默认算法进行排列，对角线区域修改为例1.1所示。所有例子中，多数一致方案得到的答案是错的，而本文算法得到的答案是对的。其他问题的答案在这个网站上有展示。

选出来的题和对应的矩阵如下：

1. Monty Hall 问题（三门问题）：在三个关闭的门中任选一个打开，三个中有一个门后面是车，两个门后面是山羊。当你选好一个以后，Monty Hall会把剩下两个门中的一个打开，并展示说明这个门后面是山羊，然后问你是否要改选另一个门。那么如果你改选了，则你得到车的概率是多少？
   
2. 出租车问题：这个城市85% 的出租车是绿色的，其他的都是蓝色的。一个目击者看到一辆蓝色的出租车。她通常正确的概率是80% 。目击者看到的出租车确实是蓝色的概率是多少？
   
   说明：这里论文插入的矩阵可能有错，我在数据网站上找到了它的正确矩阵，如下图：
   
3. 为黑棋选择一步能使其活下来的走法
   
4. 为黑棋选择一步能使其活下来的走法（原文最后的ko不清楚是指活下来并取胜，还是打错了）
   
5. 边界问题：中国和朝鲜交界处的河流是什么？
   
6. 中世纪新年问题：中世纪时期新年是哪天？
   
7. “睢”这个字的读音是什么？
   
8. “滂”这个字的读音是什么？
   

根据这些实验，有以下发现：

1. 本文方法能够得到丰富的思维层次，例如在出租车问题中，过往研究认为人们通常会忽略基本比例而报告 “80%”，设想中的层次可以是41%, 80%，而本文则发现了更丰富的思维层次：41%, 50%, 80%, 12%, 15%, 20%。（这里都是按思维水平从专业到普通再到离谱排序的）
2. 最专业的思维水平可能没法预测最离谱的思维水平。例如在出租车问题中，回答了41%的专业人士能预测到常见的错误回答80%，却没法预测到12%, 15%这样比较离谱的回答。反之，回答了80%的普通人却预测到了这种离谱答案。
3. 对于没有明显错误的问题（例如围棋），本文方法仍然有效。
4. 在边界问题中，只有3个人回答了正确答案，但我们的算法仍然在没有任何先验的情况下选出了这个正确答案。

上述例子是多数一致方案出错的。在一些多数一致方案正确的问题中，本文算法也能得出更丰富的思维层次。例如，一个题目问：唐太宗李世民什么时候登基？出于启发效应，还补充了一句是大于50岁还是小于50岁？这个题目要求回答年龄，多数一致方案和本文算法都能得出正确答案（28岁）。本文算法得出的思维层次是28,27,30,35,40,50，可以看出来，使用了锚定与调整性法则的回答被本文算法排到了后面，因为其思维层次较简单。

在我们的研究中，人们犯了一些系统性的错误，比如做了一个错误的统计假设(三门问题的“1/2”) ，忽略了基准率(出租车的“80%”) ，使用了可得性启发法，即依赖于易于搜索的记忆(“鸭绿江”，“ Songhua River”，“ju1”，“12月25日，1月1日”) ，回答了一个更容易的替代问题(使用贪婪的动作或看起来优雅的动作，发音成分) ，以及使用锚定与调整性法则(“40,50”李世民问题)[24]。重要的是，我们的实验结果表明，在没有任何先验的情况下，我们的算法将这些错误标记为不那么复杂的思维类型。

Discussion

本文算法什么情况下出错：

1. 一些复杂问题，我们没法从任何人那里得到正确答案。
2. 一些回答空间很少的问题，例如只能回答yes或no，每个人都不需要专业知识就能很容易猜到其他人的回答。
3. 不适用于人们同意不同意的情况，因为人们能预测出其他人的回答，但仍然坚持己见。例如在问题“中国古代从哪个朝代开始把最高统治者称为王？”这个问题得出的矩阵如下：
   
   正确答案是商，但本文算法排序把周放到了第一位，这可能是因为我们平常总把“夏商周”放到一起提，所以每个人都能猜出来别人的回答，而无需专业知识。如前文所说，可以用不适度来衡量算法是否能找出正确答案。

部分顺序与DAG：我们观察到，在我们的研究中，最专业的人可能不知道最离谱的人的思想。一个潜在的原因是，最专业的人数量很少。另一个潜在的原因是人们有认知限制，他们可能需要大量的努力来推理那些专业程度与他们相去甚远的人。未来的发展方向是通过多种实验来探究其原因。

激励与对手：本文没考虑激励和奖励设计。同时如果模型中存在对手，对手能比多数一致方案更容易地操控本文的算法。因此未来研究方向一方面是引入激励，另一方面是考虑对手的存在，增加模型稳定性。

开放性问题：前文所述实验都是已经有确切答案的问题，或虽然是开放性问题，但答案空间由潜在的文字片段或数字组成，我们进一步针对没有确切答案的开放性问题进行了实验，将本文方法扩展到从人群中获取主观意见的场景，例如“为什么酒吧的椅子很高”。这里的关键挑战是自动对人们的意见进行分类，一个可能的方向是与学习算法相结合，另一个挑战是验证得出的层次结构。我们在北大的一个班级里问了酒吧椅子这个问题，并手动统计。回答人数最多的是“因为酒吧柜台很高”，而本文算法排名第一的是“与站着的人有更好的目光接触”。看起来，后者会导致前者进而导致提问中的“椅子很高”，所以本文算法能得到一个更为根本性的回答。

总结：

1. 本文提出了思维层次模型和无先验情况下寻找思维层次的方法
2. 实验说明本文方法的优越性
3. 方法可用于众包的语音识别，图像描述，植物物种识别等

附录

算法流程

默认算法

1. 总体思路是挨个看哪种顺序得到的上三角平方和最大
2. 利用了动态规划的思想，先把矩阵拆成2维的，看2维情况下怎么排列最合适，然后在每一个2维的左上增加三维，看3维怎么排列最合适。

这个过程如下图所示：

变体算法

证明

引理2.8的证明

引理2.8：半正交：最小F范数=最大化平方的上三角和。对于所有矩阵$\mathcal{W}\subset \mathcal{I}$的集合，$\min _{\mathbf{W} \in \mathcal{W}, \boldsymbol{\Lambda}}||\mathbf{M}-\mathbf{W}^{\top} \boldsymbol{\Lambda} \mathbf{W}||_F^2$等价于求解$max_{\mathbf{W} \in \mathcal{W}}\sum_{i\leq j}(\mathbf{W}\mathbf{M}\mathbf{W}^{\top})^2_{i,j}$，且设置$\Lambda$为$Up(\mathbf{W}\mathbf{M}\mathbf{W}^{\top})$，即$\mathbf{W}\mathbf{M}\mathbf{W}^{\top}$的上三角区域。

$$\begin{array}{l} ||\mathbf{M}-\mathbf{W}^{\top} \boldsymbol{\Lambda} \mathbf{W}||_F^2 &= Tr((\mathbf{M}-\mathbf{W}^{\top} \boldsymbol{\Lambda} \mathbf{W})(\mathbf{M}^\top-\mathbf{W}^{\top} \boldsymbol{\Lambda}^\top \mathbf{W}))\\ & = ||\mathbf{M}||_F^2-Tr(\mathbf{W}^{\top} \boldsymbol{\Lambda} \mathbf{W}\mathbf{M})-Tr(\mathbf{M}\mathbf{W}^{\top} \boldsymbol{\Lambda}^\top \mathbf{W})+Tr(\mathbf{W}^{\top} \boldsymbol{\Lambda} \mathbf{W} \mathbf{W}^{\top} \boldsymbol{\Lambda}^\top \mathbf{W})\\ & = ||\mathbf{M}||_F^2-2Tr(\mathbf{W}^{\top} \boldsymbol{\Lambda} \mathbf{W}\mathbf{M})+Tr(\mathbf{W}^{\top} \boldsymbol{\Lambda}\boldsymbol{\Lambda}^\top \mathbf{W})\\ & = ||\mathbf{M}||_F^2-2Tr(\mathbf{W}^{\top} \boldsymbol{\Lambda} \mathbf{W}\mathbf{M})+||\boldsymbol{\Lambda}||_F^2 \end{array}$$

接下来，

$$\begin{array}{l} ||\boldsymbol{\Lambda}-\mathbf{WMW^\top}||_F^2 &=Tr((\boldsymbol{\Lambda}-\mathbf{WMW^\top})(\boldsymbol{\Lambda}^\top-\mathbf{WM^\top W^\top}))\\ &= ||\boldsymbol{\Lambda}||_F^2-2Tr(\mathbf{\Lambda WM^\top W^\top})+||\mathbf{WMW^\top}||_F^2 \end{array}$$

需要注意的是：$Tr(\mathbf{\Lambda WM^\top W^\top})=Tr(\mathbf{W^\top \Lambda WM^\top })$，由此可得：

$$||\mathbf{M}-\mathbf{W}^{\top} \boldsymbol{\Lambda} \mathbf{W}||_F^2 = ||\boldsymbol{\Lambda}-\mathbf{WMW^\top}||_F^2 -||\mathbf{WMW^\top}||_F^2+||\mathbf{M}||_F^2$$

因此，

$$\underset{\mathbf{W}, \boldsymbol{\Lambda}}{\arg \min }\left\|\mathbf{M}-\mathbf{W}^{\top} \boldsymbol{\Lambda} \mathbf{W}\right\|_{F}^{2}=\underset{\mathbf{W}, \boldsymbol{\Lambda}}{\arg \min }\left\|\boldsymbol{\Lambda}-\mathbf{W} \mathbf{M} \mathbf{W}^{\top}\right\|_{F}^{2}-\left\|\mathbf{W} \mathbf{M} \mathbf{W}^{\top}\right\|_{F}^{2}$$

最优上三角矩阵$\boldsymbol\Lambda^\ast$ 应该是$\mathbf{W} \mathbf{M} \mathbf{W}^{\top}$的上三角部分，即，对于所有$i\leq j$，$\Lambda_{i,j}^\ast=\mathbf{W} \mathbf{M} \mathbf{W}^{\top}_{i,j}$。当$\Lambda$取最优时，$||\boldsymbol{\Lambda}^{*}-\mathbf{W M W}^{\top}||_{F}^{2}-||\mathbf{W M W}^{\top}||_{F}^{2}$就等于$-\sum_{i\leq j}(\mathbf{W M W}^{\top})_{i,j}^2$。因此，$\min _{\mathbf{W} \in \mathcal{W}, \boldsymbol{\Lambda}}||\mathbf{M}-\mathbf{W}^{\top} \boldsymbol{\Lambda} \mathbf{W}||_F^2$等价于求解$max_{\mathbf{W} \in \mathcal{W}}\sum_{i\leq j}(\mathbf{W}\mathbf{M}\mathbf{W}^{\top})^2_{i,j}$。