algorithm - 确定乘积和多项式中最佳权重的快速算法？

Question

我正在寻找一种比蛮力更快的算法来找到像这样的问题中的最佳系数(也称为权重):

将样本定义为一系列N 数字。在这种情况下，假设 N=10。样本数 M 非常大，比如 M=1000000。这本质上是一个 M 行 X N 列的矩阵。所以这些样本的集合看起来像这样:

S_0_0  S_0_1 S_0_2 ... S_0_N
S_1_0  S_1_1 S_1_2 ... S_1_N
...
S_M_0  S_M_1 S_M_2 ... S_M_N

此外，还有一个对应的N个权重系列。权重系列的数量 P 也很大，比如 P=2000000。这是另一个 P 行 X N 列的矩阵。它看起来类似于样本集:

W_0_0  W_0_1 S_0_2 ... W_0_N
W_1_0  W_1_1 S_1_2 ... W_1_N
...
W_P_0  W_P_1 S_P_2 ... W_P_N

我正在尝试找到使以下总和(即第 x 行)最大化的一系列权重(即权重集中的右行):

W_x_0 * S_0_0  +  W_x_1 * S_0_1  + ... +  W_x_N * S_0_N +
W_x_0 * S_1_0  +  W_x_1 * S_1_1  + ... +  W_x_N * S_1_N +
...
W_x_0 * S_M_0  +  W_x_1 * S_M_1  + ... +  W_x_N * S_M_N

两组数据(W 和 S)都是从文件中加载的。 S 是 x86 CPU 支持的整个范围内的 double float (从负到正)。我们可以假设的 W 是整数。

这样做的蛮力方法非常简单:对于每个权重行，将其乘以样本集中的每个样本行，同时保持运行总和。跟踪每个权重行的总和，并在最后选择最好的。

现在，我认为在权重集的组成方面存在更智能/更快算法的空间。我们可以假设每行权重集中只有一个数字发生变化。因此权重集可能如下所示(为简洁起见，此处 N=5):

1 1 1 1 1
1 1 1 1 2
1 1 1 2 2
1 1 2 2 2
1 2 2 2 2
2 2 2 2 2
2 2 2 2 1
2 2 2 1 1
2 2 1 1 1

等等。

换句话说，在蛮力方法中，显然会有很多冗余计算。如果数据集不是那么大，一个想法是创建每个样本权重产品的映射/缓存，并在计算之前检查它。但是考虑到数据集的大小，我认为内存使用率会太高；我的直觉也表明映射/缓存查找可能比执行简单的乘法要慢。

有人知道适合这里的算法或库吗？

编辑 1: 我在原帖中有一个拼写错误:权重设置错误地显示了从一行到下一行的两个变化。事实上，每一行应该只有一个变化。此外，不要过多解读变化的“模式”:主要思想是每行只有一个变化，但可以修改这些变化实际出现的方式以适应特定算法。

编辑 2:我认为示例权重集现在确实每行只显示一个变化。

Answer 1

至少，观察一下

W_x_0 * S_0_0  +  W_x_1 * S_0_1  + ... +  W_x_N * S_0_N +
W_x_0 * S_1_0  +  W_x_1 * S_1_1  + ... +  W_x_N * S_1_N +
...
W_x_0 * S_M_0  +  W_x_1 * S_M_1  + ... +  W_x_N * S_M_N

等于

W_x_0 * (S_0_0 + S_1_0 +...S_M_0) +
W_x_1 * (S_0_1 + S_1_1 +...S_M_1) +
...
W_x_N * (S_0_N + S_1_N +...S_M_N)

这意味着我们可以对 S 求和，然后对列表中的每个权重向量运行运算。

可能存在基于“最远点查询”(多维)的优化，我对此了解不多，但会尝试调查。