启发式选择使点积最大化的五列数组
Heuristic to choose five column arrays that maximise the dot product
我有一个稀疏的 60000x10000 矩阵 M，其中每个元素是 1 或 0。矩阵中的每一列都是不同的信号组合（即 1 和 0）。我想从 M 中选择五个列向量并取它们的 Hadamard（即元素方式）乘积；我将生成的向量称为策略向量。在这一步之后，我计算了这个策略向量与目标向量（不变）的点积。目标向量用 1 和 -1 填充，因此在策略向量的特定行中有 1 会受到奖励或惩罚。
是否有一些启发式或线性代数方法可以帮助我从矩阵 M 中选择五个向量，从而产生高点积？我没有对 Google 的 OR 工具和 Scipy 的优化方法有任何经验，所以我不太确定它们是否可以应用于我的问题。对此的建议将不胜感激！ :)
注意：作为解给出的五个列向量不一定是最优的；我宁愿有一些东西不需要 months/years 到 运行。
也许太天真了，但我首先想到的是选择距离目标最短的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
"""
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
让我印象深刻的是，您可以添加另一个步骤，从 M–target 距离中提取前百分之几并检查它们的相互距离 — 但这可能非常昂贵。
我没有检查这与详尽搜索相比如何。
首先感谢提问。我不会经常练习 numpy。另外，我在 SE 上发帖经验不多，所以欢迎任何反馈、代码批评和与答案相关的意见。
一开始我是想找到一个最优解，但我没能处理好复杂性。但是，该算法应该为您提供一个可能被证明是足够的贪婪解决方案。
Colab Notebook (Python code + Octave validation)
核心理念
Note: During runtime, I've transposed the matrix. So, the column vectors in the question correspond to row vectors in the algorithm.
请注意，您可以一次将目标与一个向量相乘，从而有效地获得一个新目标，但其中包含一些 0s。这些永远不会改变，因此您可以通过在进一步的计算中完全删除这些行（算法中的列）来过滤掉一些计算 - 无论是从目标还是矩阵。 - 然后你又得到了一个有效的目标（其中只有 1s 和 -1）。
这就是算法的基本思想。鉴于：
n: 需要选取的向量数量b：要检查的最佳向量数m: 检查一个向量的矩阵运算的复杂度
进行指数级复杂的 O((n*m)^b) 深度优先搜索，但通过减小 target/matrix 大小来降低更深层计算的复杂性，同时使用一些启发式方法减少一些搜索路径。
使用启发法
到目前为止取得的最好成绩在每个递归步骤中都是已知的。计算一个乐观向量（将 -1 变为 0）并检查仍然可以达到哪些分数。不要在分数不能超过的关卡中搜索
如果矩阵中的最佳向量 1s 和 0s 均匀分布，则此方法无用。乐观的分数太高了。但是，越稀疏越好。
忽略重复项。基本上，不要检查同一层中的重复向量。因为我们减小了矩阵大小，所以在更深的递归级别中以重复结束的机会增加了。
关于启发式的进一步思考
最有价值的是那些在一开始就消除了矢量选择的。就它们对目标的影响而言，可能有一种方法可以找到比其他向量更差或相等的向量。假设，如果 v1 与 v2 仅相差一个额外的 1，并且目标在该行中有一个 -1，那么 v1 是差或等于比 v2.
问题是我们需要找到超过 1 个向量，并且不能轻易丢弃其余向量。如果我们有 10 个向量，每个都比前一个差或等于，我们仍然必须在开始时保留 5 个（以防它们仍然是最佳选择），然后在下一个递归级别保留 4 个，在接下来的递归级别保留 3 个等
也许可以生成一棵树并将其传递给递归？不过，这对 trim 一开始的搜索 space 没有帮助……也许只考虑更差或相等链中的 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
我有一个稀疏的 60000x10000 矩阵 M，其中每个元素是 1 或 0。矩阵中的每一列都是不同的信号组合（即 1 和 0）。我想从 M 中选择五个列向量并取它们的 Hadamard（即元素方式）乘积；我将生成的向量称为策略向量。在这一步之后，我计算了这个策略向量与目标向量（不变）的点积。目标向量用 1 和 -1 填充，因此在策略向量的特定行中有 1 会受到奖励或惩罚。
是否有一些启发式或线性代数方法可以帮助我从矩阵 M 中选择五个向量，从而产生高点积？我没有对 Google 的 OR 工具和 Scipy 的优化方法有任何经验，所以我不太确定它们是否可以应用于我的问题。对此的建议将不胜感激！ :)
注意：作为解给出的五个列向量不一定是最优的；我宁愿有一些东西不需要 months/years 到 运行。
也许太天真了，但我首先想到的是选择距离目标最短的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
"""
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
让我印象深刻的是，您可以添加另一个步骤，从 M–target 距离中提取前百分之几并检查它们的相互距离 — 但这可能非常昂贵。
我没有检查这与详尽搜索相比如何。
首先感谢提问。我不会经常练习 numpy。另外，我在 SE 上发帖经验不多，所以欢迎任何反馈、代码批评和与答案相关的意见。
一开始我是想找到一个最优解，但我没能处理好复杂性。但是，该算法应该为您提供一个可能被证明是足够的贪婪解决方案。
Colab Notebook (Python code + Octave validation)
核心理念
Note: During runtime, I've transposed the matrix. So, the column vectors in the question correspond to row vectors in the algorithm.
请注意，您可以一次将目标与一个向量相乘，从而有效地获得一个新目标，但其中包含一些 0s。这些永远不会改变，因此您可以通过在进一步的计算中完全删除这些行（算法中的列）来过滤掉一些计算 - 无论是从目标还是矩阵。 - 然后你又得到了一个有效的目标（其中只有 1s 和 -1）。
这就是算法的基本思想。鉴于：
n: 需要选取的向量数量b：要检查的最佳向量数m: 检查一个向量的矩阵运算的复杂度
进行指数级复杂的 O((n*m)^b) 深度优先搜索，但通过减小 target/matrix 大小来降低更深层计算的复杂性，同时使用一些启发式方法减少一些搜索路径。
使用启发法
到目前为止取得的最好成绩在每个递归步骤中都是已知的。计算一个乐观向量（将
-1变为0）并检查仍然可以达到哪些分数。不要在分数不能超过的关卡中搜索如果矩阵中的最佳向量
1s和0s均匀分布，则此方法无用。乐观的分数太高了。但是，越稀疏越好。忽略重复项。基本上，不要检查同一层中的重复向量。因为我们减小了矩阵大小，所以在更深的递归级别中以重复结束的机会增加了。
关于启发式的进一步思考
最有价值的是那些在一开始就消除了矢量选择的。就它们对目标的影响而言，可能有一种方法可以找到比其他向量更差或相等的向量。假设，如果 v1 与 v2 仅相差一个额外的 1，并且目标在该行中有一个 -1，那么 v1 是差或等于比 v2.
问题是我们需要找到超过 1 个向量，并且不能轻易丢弃其余向量。如果我们有 10 个向量，每个都比前一个差或等于，我们仍然必须在开始时保留 5 个（以防它们仍然是最佳选择），然后在下一个递归级别保留 4 个，在接下来的递归级别保留 3 个等
也许可以生成一棵树并将其传递给递归？不过，这对 trim 一开始的搜索 space 没有帮助……也许只考虑更差或相等链中的 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