寻找最大化正确多数决策的预测子集

Question

假设我有一个多类序列预测问题，正确答案是：

gold = [1,2,1,0,2,2]

有N个模型给出了不同的预测：

pred1 = [1,2,2,0,2,2]
pred2 = [2,2,1,1,1,1]
pred3 = [1,2,1,0,2,1]
pred4 = [1,1,0,2,1,2]
pred5 = [2,2,1,0,1,2]

我想找到预测的一个子集（例如[pred1，pred3，pred5]），这样，如果我在每个位置取最常见的项目，正确投票结果的数量就会最大化。你知道吗

在实际问题中，序列长度大于10000，N大于100，有没有有效的方法来寻找子集？你知道吗

目前我只是随机抽样的子集，因为我找不到一个确切的搜索算法（我也不知道它是否存在）。一些启发式算法可以帮助减少计算量，例如删除一致的预测，但不包括复杂性。你知道吗

如果没有一个有效的答案，我也希望有一个轻松问题的解决方案：即二进制而不是多类预测，这样最常见的预测是大多数（>；50%）预测。你知道吗

（欢迎使用Python/Numpy本机函数的解决方案）

Answer 1

这个问题似乎类似于"set cover problem"，它是NP完全的。这意味着你不会找到一个完美的，快速的解决方案。你知道吗

第一步可以是根据与目标的距离对列表进行排序：

gold = [1,2,1,0,2,2]

preds = [
    [1,2,2,0,2,2],
    [2,2,1,1,1,1],
    [1,2,1,0,2,1],
    [1,1,0,2,1,2],
    [2,2,1,0,1,2]
]

def count_correct(pred, goal=gold):
    return sum(1 for a,b in zip(pred, goal) if a==b)

print(sorted(preds, key=count_correct, reverse=True))
# [[1, 2, 2, 0, 2, 2], [1, 2, 1, 0, 2, 1], [2, 2, 1, 0, 1, 2], [2, 2, 1, 1, 1, 1], [1, 1, 0, 2, 1, 2]]

您还可以计算预测正确的指数，并尝试寻找一套封面：

def correct_ids(pred, goal=gold):
    return [i for i,(a,b) in enumerate(zip(pred,goal)) if a==b]
print([correct_ids(pred) for pred in preds])
# [[0, 1, 3, 4, 5], [1, 2], [0, 1, 2, 3, 4], [0, 5], [1, 2, 3, 5]]

但是请注意，您的问题略有不同，因为不正确的元素在投票过程中起作用。你知道吗

祝你好运！你知道吗