我有一个稀疏的 60000x10000 矩阵 M，其中每个元素都是 1 或 0。矩阵中的每一列都是不同的信号组合（即 1 和 0）。我想从 M 中选择五个列向量并取它们的 Hadamard（即逐元素）乘积；我将得到的向量称为策略向量。在此步骤之后，我计算该策略向量与目标向量（不会改变）的点积。目标向量填充有 1 和 -1，这样策略向量的特定行中有 1 就会受到奖励或惩罚。
是否有一些启发式或线性代数方法可以帮助我从矩阵 M 中选择五个向量，从而产生高点积？我没有任何使用 Google 的 OR 工具或 Scipy 的优化方法的经验，所以我不太确定它们是否可以应用于我的问题。对此的建议将不胜感激！ :)
注意：作为解给出的五个列向量不一定是最优的；我宁愿拥有不需要数月/数年才能运行的东西。
首先，感谢您提出一个好问题。我不经常练习 numpy。另外，我在向 SE 发帖方面没有太多经验，因此欢迎任何反馈、代码评论和与答案相关的意见。
一开始我试图寻找最佳解决方案，但我没能处理好复杂性。然而，该算法应该为您提供一个可能被证明是足够的贪婪解决方案。
Colab Notebook（Python代码+Octave验证）
核心理念
注意：在运行时，我已经转置了矩阵。因此，问题中的列向量对应于算法中的行向量。
请注意，您可以一次将目标与一个向量相乘，从而有效地获得一个新目标，但其中包含一些
0s1s-1这就是算法的基本思想。给定：
nbm进行指数复杂度
O((n*m)^b)使用启发法
在每个递归步骤中，迄今为止取得的最佳成绩都是已知的。计算一个乐观向量（将
-10如果矩阵中的最佳向量具有
1s0s忽略重复项。基本上，不要检查同一层中的重复向量。因为我们减小了矩阵大小，所以在更深的递归级别中最终出现重复的机会会增加。
关于启发式的进一步思考 最有价值的是那些从一开始就消除载体选择的方法。可能有一种方法可以找到比其他向量更差或等于对目标的影响的向量。比如说，如果
v1v21-1v1v2问题是我们需要找到超过 1 个向量，并且不能轻易丢弃其余向量。如果我们有 10 个向量，每个向量都比之前的向量更差或等于，我们仍然必须在开始时保留 5 个向量（以防它们仍然是最佳选择），然后在下一个递归级别中保留 4 个向量，在接下来的递归级别中保留 3 个向量等等
也许可以生成一棵树并将其传递给递归？尽管如此，这并不能帮助在开始时缩减搜索空间……也许只考虑更差或相等链中的 1 个或 2 个向量会有所帮助？这将探索更多样化的解决方案，但并不能保证它是更优化的。
警告： 请注意，示例中的 MATRIX 和 TARGET 位于
int8代码
# Given:
TARGET = np.random.choice([1, -1], size=60000).astype(np.int8)
MATRIX = np.random.randint(0, 2, size=(10000,60000), dtype=np.int8)
# Tunable - increase to search more vectors, at the cost of time.
# Performs better if the best vectors in the matrix are sparse
MAX_BRANCHES = 3 # can give more for sparser matrices
# Usage
score, picked_vectors_idx = pick_vectors(TARGET, MATRIX, 5)
# Function
def pick_vectors(init_target, init_matrix, vectors_left_to_pick: int, best_prev_result=float("-inf")):
assert vectors_left_to_pick >= 1
if init_target.shape == (0, ) or len(init_matrix.shape) <= 1 or init_matrix.shape[0] == 0 or init_matrix.shape[1] == 0:
return float("inf"), None
target = init_target.copy()
matrix = init_matrix.copy()
neg_matrix = np.multiply(target, matrix)
neg_matrix_sum = neg_matrix.sum(axis=1)
if vectors_left_to_pick == 1:
picked_id = np.argmax(neg_matrix_sum)
score = neg_matrix[picked_id].sum()
return score, [picked_id]
else:
sort_order = np.argsort(neg_matrix_sum)[::-1]
sorted_sums = neg_matrix_sum[sort_order]
sorted_neg_matrix = neg_matrix[sort_order]
sorted_matrix = matrix[sort_order]
best_score = best_prev_result
best_picked_vector_idx = None
# Heuristic 1 (H1) - optimistic target.
# Set a maximum score that can still be achieved
optimistic_target = target.copy()
optimistic_target[target == -1] = 0
if optimistic_target.sum() <= best_score:
# This check can be removed - the scores are too high at this point
return float("-inf"), None
# Heuristic 2 (H2) - ignore duplicates
vecs_tried = set()
# MAIN GOAL: for picked_id, picked_vector in enumerate(sorted_matrix):
for picked_id, picked_vector in enumerate(sorted_matrix[:MAX_BRANCHES]):
# H2
picked_tuple = tuple(picked_vector)
if picked_tuple in vecs_tried:
continue
else:
vecs_tried.add(picked_tuple)
# Discard picked vector
new_matrix = np.delete(sorted_matrix, picked_id, axis=0)
# Discard matrix and target rows where vector is 0
ones = np.argwhere(picked_vector == 1).squeeze()
new_matrix = new_matrix[:, ones]
new_target = target[ones]
if len(new_matrix.shape) <= 1 or new_matrix.shape[0] == 0:
return float("-inf"), None
# H1: Do not compute if best score cannot be improved
new_optimistic_target = optimistic_target[ones]
optimistic_matrix = np.multiply(new_matrix, new_optimistic_target)
optimistic_sums = optimistic_matrix.sum(axis=1)
optimistic_viable_vector_idx = optimistic_sums > best_score
if optimistic_sums.max() <= best_score:
continue
new_matrix = new_matrix[optimistic_viable_vector_idx]
score, next_picked_vector_idx = pick_vectors(new_target, new_matrix, vectors_left_to_pick - 1, best_prev_result=best_score)
if score <= best_score:
continue
# Convert idx of trimmed-down matrix into sorted matrix IDs
for i, returned_id in enumerate(next_picked_vector_idx):
# H1: Loop until you hit the required number of 'True'
values_passed = 0
j = 0
while True:
value_picked: bool = optimistic_viable_vector_idx[j]
if value_picked:
values_passed += 1
if values_passed-1 == returned_id:
next_picked_vector_idx[i] = j
break
j += 1
# picked_vector index
if returned_id >= picked_id:
next_picked_vector_idx[i] += 1
best_score = score
# Convert from sorted matrix to input matrix IDs before returning
matrix_id = sort_order[picked_id]
next_picked_vector_idx = [sort_order[x] for x in next_picked_vector_idx]
best_picked_vector_idx = [matrix_id] + next_picked_vector_idx
return best_score, best_picked_vector_idx
也许这太天真了，但我首先想到的是选择与目标距离最短的 5 列：
import scipy
import numpy as np
from sklearn.metrics.pairwise import pairwise_distances
def sparse_prod_axis0(A):
"""Sparse equivalent of np.prod(arr, axis=0)
From https://stackoverflow.com/a/44321026/3381305
"""
valid_mask = A.getnnz(axis=0) == A.shape[0]
out = np.zeros(A.shape[1], dtype=A.dtype)
out[valid_mask] = np.prod(A[:, valid_mask].A, axis=0)
return np.matrix(out)
def get_strategy(M, target, n=5):
"""Guess n best vectors.
"""
dists = np.squeeze(pairwise_distances(X=M, Y=target))
idx = np.argsort(dists)[:n]
return sparse_prod_axis0(M[idx])
# Example data.
M = scipy.sparse.rand(m=6000, n=1000, density=0.5, format='csr').astype('bool')
target = np.atleast_2d(np.random.choice([-1, 1], size=1000))
# Try it.
strategy = get_strategy(M, target, n=5)
result = strategy @ target.T
令我惊讶的是，您可以添加另一个步骤，从
Mtarget我还没有检查这与详尽的搜索相比如何。