确定乘积和多项式中最佳权重的快速算法？
Fast algorithm to determine best weights in a product-sum polynomial?
我正在寻找一种比蛮力更快的算法来找到像这样的问题中的最佳系数（也称为权重）：
将 样本 定义为一系列 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
两组数据（Ws 和Ss）都是从文件中加载的。 S是x86 CPU支持的整个范围内的双精度浮点数（负到正）。我们可以假设的 Ws 是整数。
这样做的蛮力方法非常简单：对于每个权重行，将其乘以样本集中的每个样本行，同时保持 运行 总和。跟踪每个重量行的总和，并在最后选择最好的。
现在，我认为 smarter/faster 算法的空间在于权重集的构成。我们可以假设每行权重集中只有一个数字发生变化。所以权重集可能看起来像这样（这里 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
以此类推
换句话说，在蛮力的方法中，显然会有很多冗余的计算。如果数据集不是那么大，一个想法是为每个样本权重产品创建一个 map/cache，并在计算之前检查它。但是考虑到数据集的大小，我认为内存使用率会太高；我的直觉也说 map/cache 查找可能比做简单的乘法慢。
有人知道适合这里的算法或库吗？
编辑 1: 我在原文中有一个错字 post：重量设置错误地显示了从一行到下一行的两次变化。事实上，每一行应该只有一个变化。此外，不要过多解读 "pattern" 的变化：主要思想是每行只有一个变化，但是可以修改这些变化实际出现的方式以适应特定算法。
编辑 2： 我 认为 示例权重集现在确实每行只显示一个变化。
至少要注意
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 求和，然后 运行 对列表中的每个权重向量进行运算。
可能有基于 "farthest point query" 的优化（在多个维度上），我对此了解不多，但会尝试进行调查。
我正在寻找一种比蛮力更快的算法来找到像这样的问题中的最佳系数（也称为权重）：
将 样本 定义为一系列 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
两组数据（Ws 和Ss）都是从文件中加载的。 S是x86 CPU支持的整个范围内的双精度浮点数（负到正）。我们可以假设的 Ws 是整数。
这样做的蛮力方法非常简单：对于每个权重行，将其乘以样本集中的每个样本行，同时保持 运行 总和。跟踪每个重量行的总和，并在最后选择最好的。
现在，我认为 smarter/faster 算法的空间在于权重集的构成。我们可以假设每行权重集中只有一个数字发生变化。所以权重集可能看起来像这样（这里 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
以此类推
换句话说，在蛮力的方法中，显然会有很多冗余的计算。如果数据集不是那么大，一个想法是为每个样本权重产品创建一个 map/cache，并在计算之前检查它。但是考虑到数据集的大小，我认为内存使用率会太高；我的直觉也说 map/cache 查找可能比做简单的乘法慢。
有人知道适合这里的算法或库吗？
编辑 1: 我在原文中有一个错字 post：重量设置错误地显示了从一行到下一行的两次变化。事实上，每一行应该只有一个变化。此外，不要过多解读 "pattern" 的变化：主要思想是每行只有一个变化，但是可以修改这些变化实际出现的方式以适应特定算法。
编辑 2： 我 认为 示例权重集现在确实每行只显示一个变化。
至少要注意
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 求和，然后 运行 对列表中的每个权重向量进行运算。
可能有基于 "farthest point query" 的优化（在多个维度上），我对此了解不多，但会尝试进行调查。