确定多热编码的有效性

Question

假设我有 N 个项目和一个多热向量值 {0, 1}，表示结果中包含这些项目：

N = 4

# items 1 and 3 will be included in the result
vector = [0, 1, 0, 1]

# item 2 will be included in the result
vector = [0, 0, 1, 0]

我还提供了一个冲突矩阵，指示哪些项目不能同时包含在结果中：

conflicts = [
  [0, 1, 1, 0], # any result that contains items 1 AND 2 is invalid
  [0, 1, 1, 1], # any result that contains AT LEAST 2 items from {1, 2, 3} is invalid
]

鉴于此冲突矩阵，我们可以确定早期 vectors 的有效性：

# invalid as it triggers conflict 1: [0, 1, 1, 1]
vector = [0, 1, 0, 1]

# valid as it triggers no conflicts
vector = [0, 0, 1, 0]

检测给定 vector 是否“有效”（即不触发任何冲突）的简单解决方案可以通过 numpy 中的点积和求和运算来完成：

violation = np.dot(conflicts, vector)
is_valid = np.max(violation) <= 1

是否有更有效的方法来执行此操作，也许是通过 np.einsum 或完全绕过 numpy 数组以支持位操作？

我们假设被检查的向量数量可能非常大（例如，如果我们评估所有可能性，最多 2^N）但一次可能只检查一个向量（以避免生成形状矩阵高达 (2^N, N) 作为输入）。

Answer 1

TL;DR: 你可以使用 Numba 来优化 np.dot 以仅在 上运行二进制值。更具体地说，您可以使用 64 位视图.

一次对 8 个字节执行 SIMD-like 操作

将列表转换为数组

首先，使用这种方法可以将列表有效地转换为 relatively-compact 数组：

vector = np.fromiter(vector, np.uint8)
conflicts = np.array([np.fromiter(conflicts[i], np.uint8) for i in range(len(conflicts))])

这比使用自动 Numpy 转换或 np.array 更快（在 Numpy 代码内部和 Numpy 中执行的检查更少，Numpy 知道要构建什么类型的数组，并且生成的数组更小内存，因此填充速度更快）。此步骤可用于加快基于 np.dot 的解决方案。

如果输入已经是 Numpy 数组，则检查它们是 np.uint8 或 np.int8 类型。否则，请使用 conflits = conflits.astype(np.uint8) 将它们转换为此类类型。

第一次尝试

然后，一种解决方案可能是使用np.packbits将输入的二进制值尽可能多地打包在内存中的位数组中，然后执行逻辑与运算。但事实证明 np.packbits 非常慢。因此，这个解决方案最终不是一个好主意。事实上，任何创建形状类似于 conflicts 的临时数组的解决方案都会很慢，因为在内存中写入这样的数组通常比 np.dot（从内存中读取 conflicts 一次）慢。

使用 Numba

由于 np.dot 优化得很好，唯一的解决办法就是使用优化的本机代码。得益于 just-in-time 编译器，Numba 可用于在运行时从 Numpy-based Python 代码生成本机可执行代码。这个想法是在每个块的 vector 和 conflicts 行之间执行逻辑与。对每个块进行冲突检查，以便尽早停止计算。通过比较两个数组的 uint64 视图（以 SIMD-friendly 方式），可以按 8 个八位字节为一组有效地比较块。

import numba as nb

@nb.njit('bool_(uint8[::1], uint8[:,::1])')
def check_valid(vector, conflicts):
    n, m = conflicts.shape
    assert vector.size == m

    for i in range(n):
        block_size = 128 # In the range: 8,16,...,248
        conflicts_row = conflicts[i,:]
        gsum = 0 # Global sum of conflicts
        m_limit = m // block_size * block_size

        for j in range(0, m_limit, block_size):
            vector_block = vector[j:j+block_size].view(np.uint64)
            conflicts_block = conflicts_row[j:j+block_size].view(np.uint64)

            # Matching
            lsum = np.uint64(0) # 8 local sums of conflicts
            for k in range(block_size//8):
                lsum += vector_block[k] & conflicts_block[k]

            # Trick to perform the reduction of all the bytes in lsum
            lsum += lsum >> 32
            lsum += lsum >> 16
            lsum += lsum >> 8
            gsum += lsum & 0xFF

            # Check if there is a conflict
            if gsum >= 2:
                return False

        # Remaining part
        for j in range(m_limit, m):
            gsum += vector[j] & conflicts_row[j]

        if gsum >= 2:
            return False

    return True

结果

对于形状为 (16, 65536) 的大型 conflicts 数组（无冲突），这比我机器上的 np.dot 快 9 倍 .两种情况都不包括转换列表的时间。当存在冲突时，提供的解决方案更快，因为它可以提前停止计算。

理论上，计算应该更快，但 Numba JIT 不能成功地使用 SIMD 指令对循环进行矢量化。话虽如此，np.dot 似乎也出现了同样的问题。如果数组更大，您可以并行计算块（如果函数 return False，则计算速度较慢）。

确定多热编码的有效性

Determining the validity of a multi-hot encoding

python

bit-manipulation

numpy

numpy-einsum

将列表转换为数组

第一次尝试

使用 Numba

结果