跨多个维度的 Top-k 评分

Question

例如在机器学习中的自然语言处理中，束搜索通常用于预测下一个要添加到序列中的对象并对它们进行排序。 beam-search 的一个关键部分是 top-k 分数度量，它实际上是：给定长度为 N 的概率分数的选择列表, return k 个得分最高的项目N。这就像对列表进行排序然后取最高值一样简单。
参考一个可视化的例子https://www.researchgate.net/figure/A-partially-completed-beam-search-procedure-with-a-beam-width-of-5-for-an-example-input_fig2_317377611 in a beam-search (in the above case, k=5, and a ‘top’ score is a minimal value), at each iteration, each node selects the top k items from the list of choices N, resulting in k² total potential paths. From these paths, the top k overall are filtered, which form the nodes for the next iteration. In the previous example, you can see only the filtered nodes at each time-step. https://d2l.ai/_images/beam-search.svg全面展开了k=2,N=5的情况

想象一下，您不必为每个 branch/node 优化 N 中的一个选择，而是必须选择多个值：从节点探索时，您有一组选择维度 (N, q)，您希望从中获得 select q 值, 每列 q 一个。然后，要找到得分最高的选项集，您需要考虑这些列中值的组合。例如：对于选择矩阵 N=5, q=4:

+---+--------+--------+--------+--------+
| N |   q0   |   q1   |   q2   |   q3   |
+---+--------+--------+--------+--------+
| 0 | 0.9763 | 0.0791 | 0.1530 | 0.5565 |
| 1 | 0.1560 | 0.1014 | 0.6932 | 0.7551 |
| 2 | 0.8142 | 0.9494 | 0.4582 | 0.4411 |
| 3 | 0.3807 | 0.2403 | 0.6897 | 0.7356 |
| 4 | 0.0156 | 0.9419 | 0.9568 | 0.2266 |
+---+--------+--------+--------+--------+

如果k=5，这个top-k函数应该return如下：

3.6376 = q₀[0] + q₁[2] + q₂[4] + q₃[1]
3.6301 = q₀[0] + q₁[4] + q₂[4] + q₃[1]
3.6181 = q₀[0] + q₁[2] + q₂[4] + q₃[3]
3.6106 = q₀[0] + q₁[4] + q₂[4] + q₃[3]
3.4755 = q₀[2] + q₁[2] + q₂[4] + q₃[1]

这是最大可能的总和，使用每一列中的一个值。

解决任意 N 和 q，天真的方法是计算所有 N^q 求和，对它们进行排序，然后取前 k 个结果。优化的第一步是对每一列进行排序，然后只计算每一列中顶部 k 值的总和组合，将复杂度降低到 k^q.

但是，考虑到这个查找最高分的函数必须在 beam-search 的每个时间步调用 k 次，如果希望扩展到高 k 或高 q。我提出的最佳解决方案（浓缩为最小示例，假设 matrix 是一个形状为 (N, q), 取q为4):

import numpy as np
from itertools import combinations


class Beamsearch():
    def __init__(self, klen, q=4):
        self.klen = klen
        self.combis = []
        for lens in range(klen):
            self.combis.extend(list(self.partition(lens, q)))
        self.width = q
        self.wdth = list(range(q))

    def partition(self, N, size):
        n = N + size - 1
        for splits in combinations(range(n), size - 1):
            yield [s1 - s0 - 1 for s0, s1 in zip((-1,) + splits, splits + (n,))]

    def getkmaxscores(self, matrix):
        matrix_argsort = np.argsort(-matrix, axis=0)
        sums = []
        for comb in self.combis:
            midxs = matrix_argsort[comb, self.wdth]
            midxslist = midxs.tolist()
            msum = (sum(matrix[midxs, self.wdth]),
                    midxslist)
            sums.append(msum)
        sums.sort(reverse=True)
        return sums[:self.klen]

此方法将整数 p 划分为给定宽度 q 的整数 0 ≤ p ≤ k，例如q=4:

p0: [0, 0, 0, 0]
p1: [0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0]
p2: [0, 0, 0, 2], [0, 0, 1, 1], [0, 0, 2, 0], [0, 1, 0, 1], [0, 1, 1, 0], [0, 2, 0, 0], [1, 0, 0, 1], [1, 0, 1, 0], [1, 1, 0, 0], [2, 0, 0, 0]

等等

然后将这些用于对 argsorted 输入矩阵进行索引，以 select 每个组合进行求和。在q=4的情况下p_i的长度遵循三角锥序列（https://oeis.org/A000292): This reduces the search space to the sum of all p_0...k which is the Binomial coefficient (k,4) = k(k-1)(k-2)(k-3)/24 (https://oeis.org/A000332).这是对小型 kk⁴ 解决方案的巨大改进（对于 k < 30，这个小于k³)，但仍然增长在k的数量级⁴。是否存在复杂度 k^q) 的任意情况的解决方案？

Answer 1

这个问题在文献中被称为 selecting from X + Y。规范参考是 Frederickson and Johnson，他在对 X 和 Y 进行排序时给出了最优的 O(k) 时间算法.你的列没有排序，而且 F&J 的算法很复杂，所以让我画出更简单的 O(k log k) 算法。

首先对于 X 和 Y，select 前 k 个元素并对它们进行排序。初始化最大堆，其中元素 (i, j) 的优先级为 X[i] + Y[j]。插入 (0, 0)。重复以下 k 次：弹出最大元素 (i, j) 并记录其优先级。插入 (i, j+1)。如果 j = 0，也插入 (i+1, 0)。这一切都需要时间 O(n + k log k) ，其中 n 是列中元素的数量。

最后，让我们将问题减少到两列。如果有两个以上，例如 X、Y、Z，那么我们可以 select 来自 X + Y 的前 k 个元素，然后 select 来自 (X + Y) + Z 的前 k 个元素。

跨多个维度的 Top-k 评分

Top-k scoring across multiple dimensions

python

algorithm

optimization

machine-learning

time-complexity