python - 启发式选择最大化点积的五个列数组

Question

我有一个稀疏的 60000x10000 矩阵 M，其中每个元素都是 1 或 0。矩阵中的每一列都是不同的信号组合(即 1 和 0)。我想从 M 中选择五个列向量并取它们的 Hadamard(即元素方式)乘积；我将结果向量称为策略向量。在这一步之后，我计算这个策略向量与目标向量(不会改变)的点积。目标向量用 1 和 -1 填充，这样策略向量的特定行中的 1 要么得到奖励，要么受到惩罚。
是否有一些启发式或线性代数方法可以帮助我从矩阵 M 中选择导致高点积的五个向量？ 我对 Google 的 OR 工具和 Scipy 的优化方法没有任何经验，所以我不太确定它们是否可以应用于我的问题。对此的建议将不胜感激! :)
注意:作为解给出的五个列向量不需要是最优的；我宁愿拥有不需要数月/数年才能运行的东西。

Answer 1

首先，谢谢你的好问题。我不能经常练习 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)深度优先搜索，但通过减少目标/矩阵大小来降低更深层计算的复杂性，同时通过一些启发式方法减少一些搜索路径。
使用的启发式方法

迄今为止，在每个递归步骤中获得的最佳分数都是已知的。计算一个乐观向量(将 -1 转为 0 )并检查仍然可以达到哪些分数。不要在无法超过分数的级别中搜索。
如果矩阵中的最佳向量具有 1s，则这是无用的。和 0s平均分配。乐观的分数太高了。但是，随着稀疏性的增加，它会变得更好。

忽略重复项。基本上，不要检查同一层中的重复向量。因为我们减小了矩阵大小，所以在更深的递归级别中出现重复的机会增加。

关于启发式的进一步思考
最有值(value)的是那些在一开始就消除向量选择的那些。可能有一种方法可以找到比其他向量更差或相等的向量，就其对目标的影响而言。说，如果 v1仅与 v2 不同通过额外 1 ，并且目标有一个 -1在该行，然后 v1差于或等于 v2 .
问题是我们需要找到 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