知识工作者问答论坛中的最优调度

# 知识工作者问答论坛中的最优调度
来源：https://arxiv.org/html/2606.19759
###### 摘要

随着个人转向互联网寻找问题的答案，多种问答论坛应运而生。在这些论坛中，精通特定话题的用户可以贡献他们的专业知识来回答信息请求。虽然目前这些论坛依赖于志愿者，但我们设想未来版本将雇佣知识工作者，他们是特定话题的专家。在这样的系统中，构成排队系统的请求-回答过程可能利用调度器，将不同话题的请求分配给论坛中的专家，这些专家可以根据他们在不同话题的专业水平来回答。基于此模型，我们计算了系统在保持稳定的前提下处理请求的能力，并设计了能够实现该能力的调度器。我们还研究了专家之间协作回答请求如何可能提高系统容量。

关键词：问答，社交网络，调度。

## 1 引言

问答论坛[1 (https://arxiv.org/html/2606.19759#bib.bib1)]如Quora和StackExchange[2 (https://arxiv.org/html/2606.19759#bib.bib2)]允许个人提出问题，以便论坛中精通该话题的用户根据自己的知识，或许还能通过信息源搜索相关信息来回答。发布的提问可能包含关键词（标签），也可能发布在问答系统内的特定狭窄论坛中，以便问题的主题对可能回答者（即精通该话题的用户）是清晰的。问答论坛引发了多种研究，例如基于文本信息的主题自动识别[3 (https://arxiv.org/html/2606.19759#bib.bib3)]、在线社交网络中的信息扩散[4 (https://arxiv.org/html/2606.19759#bib.bib4)]，以及理解这种扩散对人类行为影响的模型[5 (https://arxiv.org/html/2606.19759#bib.bib5)]。

虽然目前由志愿者驱动的问答论坛确实很成功，但其中一定比例的问题仍未得到回答，原因是缺乏志愿者的兴趣或专业知识。例如，对检索到的档案数据[6 (https://arxiv.org/html/2606.19759#bib.bib6)]分析显示，在37个最受欢迎的StackExchange技术网站上的180万个问题中，16%的问题未得到回答，54%的问题没有标记为“已采纳”的答案。同样，某些问题会得到志愿者的积极关注，有几十个答案，而其他问题则因缺乏志愿者兴趣而无人问津。与此同时，大型语言模型的兴起，例如问答论坛Quora正在测试的ChatGPT机器人，可能会对专门的人类专家提出更高要求，因为他们能够回答机器人无法轻易回答的复杂问题。因此，尽管研究人员正在研究众包应用中志愿者的激励措施以完成任务（如问答）[8 (https://arxiv.org/html/2606.19759#bib.bib8)]，但想象这些问答论坛的未来版本（或现有论坛中的高级层级）也许是值得的。该版本通过货币化论坛，能够雇佣专门的知识工作者（我们称之为**专家**），以保证在复杂问题成功回答方面达到可接受的性能水平。通过要求这些知识工作者按合同提供可用性，并利用调度器动态地将特定问题分配给这些工作者，旨在提高系统总容量，可以获得这样的保证。即使这样一个基于知识工作者的论坛（或高级层级）未能实现，对所提议系统的理论分析也将为志愿者驱动型问答论坛的容量提供一个上界，因为志愿者的动机不一定是为了最大化系统容量。

本文研究为所提议的基于知识工作者的系统设计这种调度器的问题，以在不使专家过载的情况下最大化请求回答容量。我们提出一个系统模型，其中不同话题的信息请求到达并被放入主题队列。在先前基于此模型的研究[9 (https://arxiv.org/html/2606.19759#bib.bib9)]中，我们提出了一种固定调度器，将来自主题队列的不同比例的请求分配给不同的专家。然而，该调度器需要**离线计算**分配的比率，基于对请求到达过程统计信息的完全了解，以及所有专家的能力。在本文中，我们提出一种**在线调度器**，根据专家在不同话题的专业水平和系统当前状态，动态地将每个请求从队列分配给专家，以便一个问题由一位或多位专家研究直至回答。此外，我们研究了一种**协调**操作模式，其中不同专家处理不同请求，以及一种**协作**模式，其中多位专家通过汇集他们的专业知识共同处理一个请求。利用排队论分析调度器来计算问答系统的容量。获得了对容量的深入理解，并探索了专家间协作相对于单纯协调的益处。虽然已有大量关于调度分析[10 (https://arxiv.org/html/2606.19759#bib.bib10)]在各种应用中的先前工作可供我们分析参考，但本文对问答论坛的关注揭示了诸如这些论坛的知识处理系统容量的有趣见解。

## 2 模型

我们假设个人可以在问答论坛中提出**问题**，也称为**信息请求**。每个问题属于一个话题 \(x \in \mathcal{X}\)，其中 \(\mathcal{X}\) 是一个**有限的**可能话题集合，问题的主题通过问题中标记的关键词、基于问题文本的自动分类器识别，或直接发布到专门针对该主题的狭窄子论坛中。我们假设时间被划分为时隙 \(t=1,2,\ldots\)，在时隙 \(t\) 结束时，随机数量的关于话题 \(x\) 的问题 \(a_x(t)\) 到达，其中 \(a_x(t)\) 在时间上是独立同分布的，并且在不同 \(x\) 之间独立。我们假设 \(\mathbb{E}[a_x(t)] = \lambda p(x)\)，其中概率质量函数 \(p(x) > 0, \forall x\) 表示不同主题的相对频率，请求负载 \(\lambda\) 是每个时隙的平均问题数。我们假设 \(a_x(t)\) 的方差以 \(c_a \lambda^2\) 为界，其中 \(c_a\) 是某个常数。为未回答的问题维护主题队列，每个主题一个，\(Q_x(t)\) 表示在时间 \(t\) 开始时主题 \(x\) 的队列长度。

有 \(n\) 个可用的专门专家，记为 \(i=1,2,\ldots,n\)，他们可以监控问答论坛。我们假设专家同意使用调度器将问题分配给他们，这样这些专家彼此**协调**。（因此，该模型明确地**不**考虑基于志愿者的论坛，在那种论坛中志愿者的动机可能与任何系统容量的概念不一致。）令 \(\sigma_{x,i}(t)=1,0\) 分别表示专家 \(i\) 在时间 \(t\) 是否被分配来自主题 \(x\) 的请求。我们假设专家 \(i\) 在每个 \(t\) 可以处理（或**研究**）不超过 \(n_i\) 个请求，其中能够投入更多时间的专家可以选择更高的 \(n_i\) 值，类似于拼车行业中司机的工作方式。专家 \(i\) 在给定时隙中成功回答一个问题的概率为 \(q_i(x)\)（可能为零），我们称之为**回答率**，并取决于主题 \(x\)。记 \(d_{x,i}(t)\) 为专家 \(i\) 在时间 \(t\) 在主题 \(x\) 上提供的成功回答数量。如果专家未成功，请求将返回到其主题队列，并可能在后续时隙中分配给另一位（或同一位）专家。（我们通过实验表明，该假设对结果似乎并不非常关键——见第5节 (https://arxiv.org/html/2606.19759#S5)。我们还设计了另一个调度器，明确允许工作者一直处理请求直至完成。）

我们假设成功回答该请求的概率与其过去历史无关，因此专家 \(i\) 回答该请求所需的（可能不连续的）时隙数 \(T\) 是一个几何随机变量，其取值为 \(1,2,\ldots\)，均值 \(T_i(x) = \frac{1}{q_i(x)} \geq 1\)。（虽然这是一个出于技术原因的有用假设，但我们在第5节 (https://arxiv.org/html/2606.19759#S5) 中通过实验表明，只要对 \(T\) 设置一个上界，该假设从实践角度来看似乎是足够的。）随机变量 \(T\) 对于调度器是事先未知的，尽管我们假设其均值（即平均研究时间 \(T_i(x)\)）对于所有 \(i, x\) 是已知的。因此，就调度而言，专家 \(i\) 简单地是一个函数 \(T_i: \mathcal{X} \rightarrow [1, \infty]\)。随机回答时间考虑了不同问题（即使是同一主题下）在搜索信息或处理信息方面不同的难度。它也考虑了问答论坛中基于部分答案进行问题来回细化的过程。\(T_i(\cdot)\) 函数通常因不同专家的特定专业知识而不同。估计 \(T_i(x)\) 的最简单方法是使用专家在不同主题上的回答历史。也可以使用更复杂的方法，例如文献[11 (https://arxiv.org/html/2606.19759#bib.bib11)]中的方法。我们假设调度器可以使用过去和当前的历史，包括队列长度 \(Q_x(t)\)，来决定 \(\sigma_{x,i}(t), \forall x,i\)。由于我们假设到达发生在时隙结束时，队列长度更新为：

\[
Q_x(t+1) = Q_x(t) + a_x(t) - \sum_{i=1}^n d_{x,i}(t), \quad \forall x \tag{1}
\]

如果对于任何使用过去和当前历史的调度器，队列长度可能发散，即

\[
P\left( \lim_{t \to \infty} \sum_{x \in \mathcal{X}} Q_x(t) = \infty \right) > 0 \tag{2}
\]

则我们称该问答系统是**不稳定的**。为了证明稳定性，我们只考虑在时间 \(t\) 使用当前队列长度 \(Q_x(t)\) 的调度器。对于这样的调度器，由于独立同分布的到达和几何分布的回答时间，问答系统是一个马尔可夫链，状态为时间 \(t\) 时的 \(Q_x(t), \forall x\)。如果该马尔可夫链是正递归的[12 (https://arxiv.org/html/2606.19759#bib.bib12)]，我们就说系统是稳定的。特别地，这也意味着系统在 (2) 的意义上不是不稳定的。如果某个调度器能够保持系统稳定，我们就说 \(\lambda\) 是**可实现的**。所有这样的 \(\lambda\) 的上确界是系统的**容量**。

为简洁起见，我们通常省略索引的集合，当该集合显而易见时，例如写 \(\sum_x\) 代替 \(\sum_{x \in \mathcal{X}}\)。类似地，我们写 \(\max_{\alpha_i}\) 代替 \(\max_{\alpha_i, i=1,2,\ldots,n}\)。由于篇幅限制，我们将证明留待后续完整论文，但要指出这些证明依赖于李雅普诺夫分析，但针对的是此公式中遇到的特定图论问题。虽然我们获得的容量概念上可用于设计或演化问答论坛（例如通过雇佣能够提高计算容量的专家），我们也提供了对容量表达式的直观理解。

## 3 协调容量

假设 \(n\) 位专家决定按照第2节 (https://arxiv.org/html/2606.19759#S2) 的描述进行**协调**，通过使用一个调度器在每个时隙 \(t\) 决定未回答问题的分配对象，以期最大化可实现的请求负载 \(\lambda\)。令 \(M_i \doteq \{x: q_i(x) > 0\}\) 为专家 \(i\) 有能力回答的主题集合。我们假设 \(M_i \neq \emptyset, \forall i\)，因为不能回答任何话题的专家不需要考虑调度。在这种情况下，我们有以下结果。

###### 引理 1

如果存在一个主题 \(x\) 使得 \(\max_i q_i(x) = 0\)，则具有协调专家的容量为 \(\lambda^* = 0\)；否则容量严格为正，并给出为：

\[
\lambda^* = \left( \max_{\alpha_i} \sum_{x \in \mathcal{X}} \min_{i: q_i(x) > 0} \left( \alpha_i \frac{p(x)}{q_i(x)} \right) \right)^{-1} \tag{4}
\]

其中

\[
\sum_{i=1}^n \alpha_i n_i = 1, \quad \alpha_i \geq 0, \quad \forall i=1,\ldots,n.
\]

此外，任何 \(\lambda < \lambda^*\) 都可以通过基于队列长度的调度器实现，例如下面描述的**贪心在线协调调度器**。

**贪心在线协调调度器**：在每个时隙 \(t\)，对于每个专家 \(i\) 分别地，调度器首先按奖励 \(r_i(x) = Q_x(t) q_i(x)\) 的降序对主题队列中的请求进行排序。然后，它将 \(n_i\) 个最大奖励的请求暂分配给专家 \(i\)。在第二阶段，它通过任意删除每个主题 \(x\) 中超过该主题队列等待数量 \(Q_x(t)\) 的暂定超额请求，最终确定请求，并将它们呈现给专家。

注意，这是一个在线算法，因为这里的调度器不需要预先计算分配给不同专家的请求的固定比例，这与文献[9 (https://arxiv.org/html/2606.19759#bib.bib9)]中的情况不同，后者需要知道到达的 \(p(x)\)，并且当此概率质量函数缓慢变化时，该算法也能潜在适应。调度器可以以**联邦**方式实现，如下所示。每个专家可以独立计算其自身的奖励 \(r_i(x)\)，并选择最大的 \(n_i\) 个，向调度器宣布其暂定调度。调度器在收集所有这些暂定调度后，可以运行贪心分配的第二阶段。因此，\(q_i(x)\) 的值仅需被相应的专家 \(i\) 知道。

引理 1 的证明：协调是协作的一个特例，如第4节 (https://arxiv.org/html/2606.19759#S4) 所述，因此本定理是定理1 (https://arxiv.org/html/2606.19759#Thmtheorem1) 的一个特例，通过设置 \(\mathcal{S} = \{\{i\}, i=1,2,\ldots,n\}\)，即所有单点集的集合得到。此外，上述提出的贪心调度器是算法1 (https://arxiv.org/html/2606.19759#alg1) 中为协作情况描述的两阶段贪心调度器的一个特例。尽管在协作情况下，两阶段贪心算法只能保证相对于容量的近似比为 \(\gamma \doteq (\max_{S \in \mathcal{S}} |S|)^{-1}\)（引理6 (https://arxiv.org/html/2606.19759#Thmlemma6)），但在协调情况下，\(\gamma = 1\)。