Imagine your have five different classes e.g. ['cat', 'dog', 'fish', 'bird', 'ant']. If you would use one-hot-encoding you would represent the presence of 'dog' in a five-dimensional binary vector like [0,1,0,0,0]. If you would use multi-hot-encoding you would first label-encode your classes, thus having only a single number which represents the presence of a class (e.g. 1 for 'dog') and then convert the numerical labels to binary vectors of size .

Examples:

'cat'  = [0,0,0]  
'dog'  = [0,0,1]  
'fish' = [0,1,0]  
'bird' = [0,1,1]  
'ant'  = [1,0,0]   

This representation is basically the middle way between label-encoding, where you introduce false class relationships (0 < 1 < 2 < ... < 4, thus 'cat' < 'dog' < ... < 'ant') but only need a single value to represent class presence and one-hot-encoding, where you need a vector of size (which can be huge!) to represent all classes but have no false relationships.

Note: multi-hot-encoding introduces false additive relationships, e.g. [0,0,1] + [0,1,0] = [0,1,1] that is 'dog' + 'fish' = 'bird'. That is the price you pay for the reduced representation.

Without using MultiLabelBinarizer

import numpy as np
classes=['comedy', 'xyz','thriller', 'sci-fi']
id_dict = {c:i for i,c in enumerate(classes)}
lists_of_movieIds = [{'sci-fi', 'thriller'}, {'comedy'}]
list_of_ratings = [[4,3],[5]]

data = np.zeros((len(lists_of_movieIds), len(classes)))
for i, (m_ids,rs) in enumerate(zip(lists_of_movieIds, list_of_ratings)):
  for m_id,r in zip(m_ids,rs):
    data[i, id_dict[m_id]] = r

print (data)

Output:

[[0. 0. 3. 4.]
 [5. 0. 0. 0.]]

You can think of binary encoding as a compromise between label encoding and one-hot encoding. For distinct categories, label encoding introduces a false linear order that brings a lot of noise into the model (category 1 < category 2 < category 3....) . Binary encoding introduces false additive relationships between the categories (e.g. category 4 + category 1 = category 5 or 100 + 001 = 101) but fewer of them.

Therefore, binary will usually work better than label encoding, however only one-hot encoding will usually preserve the full information in the data.

Unless your algorithm (or computing power) is limited in the number of categories it can handle, one-hot encoding will be preferred over other encoding schemes. If you are limited, mean encoding is a powerful alternative because it transform a categorical feature into a numeric one (giving you the minimal number of inputs) while preserving the most important information in the data.

[Mean encoding replaces every category with its target mean. The mean encodings need to be constructed carefully on a separate dataset to avoid data leakage. If you want to reduce your input dimensions as much as possible, this can be helpful. Mean encoding can also be helpful as an additional feature and is very popular on Kaggle to squeeze out some extra performance. This is also known as target encoding or likelihood encoding.]

TL;DR: you can use Numba to optimize np.dot to only operate only on binary values. More specifically, you can perform SIMD-like operations on 8 bytes at once using 64-bit views.

Converting lists to arrays

First of all, the lists can be efficiently converted to relatively-compact arrays using this approach:

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

This is faster than using the automatic Numpy conversion or np.array (there is less check to perform in the Numpy code internally and Numpy, Numpy know what type of array to build and the resulting one is smaller in memory and thus faster to fill). This step can be used to speed up your np.dot-based solution.

If the input are already a Numpy array, then check they are of type np.uint8 or np.int8. Otherwise, please cast them to such type using conflits = conflits.astype(np.uint8) for example.

First try

Then, one solution could be to use np.packbits to pack the input binary values much as possible in an array of bits in memory, and then perform logical ANDs. But it turns out that np.packbits is pretty slow. Thus, this solution is not a good idea in the end. In fact, any solution creating temporary arrays with a shape similar to conflicts will be slow since writing such an array in memory is generally slower than np.dot (which read conflicts from memory once).

Using Numba

Since np.dot is pretty well optimized, the only solution to defeat it is to use an optimized native code. Numba can be used to generate a native executable code at runtime from a Numpy-based Python code thanks to a just-in-time compiler. The idea is to perform a logical ANDs between vector and rows of conflicts per block. Conflict are check for each block so to stop the computation as early as possible. Blocks can be efficiently compared by groups of 8 octets by comparing the uint64 views of the two arrays (in a SIMD-friendly way).

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

Results

This is about 9 times faster than np.dot on my machine for a large conflicts array of shape (16, 65536) (without conflicts). The time to convert lists is not included in both cases. When there are conflicts, the provided solution is much faster since it can early stop the computation.

Theoretically, the computation should be even faster, but the Numba JIT do not succeed to vectorize the loop using SIMD instructions. That being said, it seems the same issue appears for np.dot. If the arrays are even bigger, you can parallelize the computation of the blocks (at the expense of a slower computation if the function return False).

Without having read the paper, from the name I would say a multi-hot encoding is a matrix $X \in \{0,1\}^{n \times m }$, with $\sum_{i = 1}^{n} X_{i,j} = 1, \forall j = 1,\ldots,m$.

You obtain the normal hot-encoding by setting $m=1$.