Умножение секционированной матрицы в тензорном потоке или питоре

Question

Предположим, у меня есть матрицы P размером [4, 4], которые разделены (блок) на 4 меньшие матрицы [2,2].Как я могу эффективно умножить эту блочную матрицу в другую матрицу (не разделенную матрицу, а меньшую)?

Давайте предположим, что наша исходная матрица:

P = [ 1 1 2 2
      1 1 2 2
      3 3 4 4
      3 3 4 4]

Какой разделитьв подматрицы:

P_1 = [1 1    , P_2 = [2 2  , P_3 = [3 3   P_4 = [4 4
       1 1]            2 2]          3 3]         4 4]

Теперь наш P:

P = [P_1 P_2
     P_3 p_4]

На следующем шаге я хочу сделать поэлементное умножение между P и меньшими матрицами, размер которых равенколичество подматриц:

P * [ 1 0   =   [P_1  0  = [1 1 0 0 
      0 0 ]      0    0]    1 1 0 0
                            0 0 0 0
                            0 0 0 0]    

Answer 1

Вы можете подумать о представлении своей большой блочной матрицы более эффективным способом.

Например, блочная матрица

P = [ 1 1 2 2
      1 1 2 2
      3 3 4 4
      3 3 4 4]

Может быть представлена ​​с помощью

a = [ 1 0    b = [ 1 1 0 0    p = [ 1 2
      1 0          0 0 1 1 ]        3 4 ]
      0 1
      0 1 ]

Как

P = a @ p @ b

С (@ представляет матричное умножение).Матрицы a и b представляют / кодируют блочную структуру P, а маленькие p представляют значения каждого блока.

Теперь, если вы хотите умножить (поэлементно) p с маленькой (2x2) матрицей q вы просто

a @ (p * q) @ b

Простой пример с пирохом

In [1]: a = torch.tensor([[1., 0], [1., 0], [0., 1], [0, 1]])
In [2]: b = torch.tensor([[1., 1., 0, 0], [0, 0, 1., 1]]) 
In [3]: p=torch.tensor([[1., 2.], [3., 4.]])
In [4]: q = torch.tensor([[1., 0], [0., 0]])

In [5]: a @ p @ b

Out[5]:
tensor([[1., 1., 2., 2.],
        [1., 1., 2., 2.],
        [3., 3., 4., 4.],
        [3., 3., 4., 4.]])

In [6]: a @ (p*q) @ b

Out[6]:
tensor([[1., 1., 0., 0.],
        [1., 1., 0., 0.],
        [0., 0., 0., 0.],
        [0., 0., 0., 0.]])

Я оставляю это вам в качестве упражнения, как эффективно создавать "структурные" матрицы a и b с учетом размеров блоков.

Answer 2

Если матрицы маленькие, вы, вероятно, в порядке с cat или pad.Решение с факторизацией очень изящно, как и решение с реализацией block_mul.

Другое решение заключается в превращении 2D-блочной матрицы в 3D-объем, где каждый 2D-срез является блоком (P_1, P_2, P_3, P_4).Затем используйте мощность вещания, чтобы умножить каждый 2D-фрагмент на скаляр.Наконец измените вывод.Изменение формы не является немедленным, но это выполнимо, порт от numy к pytorch https://stackoverflow.com/a/16873755/4892874

В Pytorch:

import torch

h = w = 4
x = torch.ones(h, w)
x[:2, 2:] = 2
x[2:, :2] = 3
x[2:, 2:] = 4

# number of blocks along x and y
nrows=2
ncols=2

vol3d = x.reshape(h//nrows, nrows, -1, ncols)
vol3d = vol3d.permute(0, 2, 1, 3).reshape(-1, nrows, ncols)

out = vol3d * torch.Tensor([1, 0, 0, 0])[:, None, None].float()

# reshape to original
n, nrows, ncols = out.shape
out = out.reshape(h//nrows, -1, nrows, ncols)
out = out.permute(0, 2, 1, 3)
out = out.reshape(h, w)

print(out)

tensor([[1., 1., 0., 0.],
        [1., 1., 0., 0.],
        [0., 0., 0., 0.],
        [0., 0., 0., 0.]])

Я не сравнивал это с остальными, но это не такпотреблять дополнительную память, как это делает заполнение, и оно не выполняет медленных операций, таких как конкатенация.Он также обладает тем преимуществом, что его легко понять и визуализировать.

Вы можете обобщить его в любой ситуации, играя с h, w, nrows, ncols.

Answer 3

Не знаю об эффективном методе, но вы можете попробовать это:

Метод 1:

Использование torch.cat()

import torch

def multiply(a, b):
    x1 = a[0:2, 0:2]*b[0,0]
    x2 = a[0:2, 2:]*b[0,1]
    x3 = a[2:, 0:2]*b[1,0]
    x4 = a[2:, 2:]*b[1,1]
    return torch.cat((torch.cat((x1, x2), 1), torch.cat((x3, x4), 1)), 0)

a = torch.tensor([[1, 1, 2, 2],[1, 1, 2, 2],[3, 3, 4, 4,],[3, 3, 4, 4]])
b = torch.tensor([[1, 0],[0, 0]])
print(multiply(a, b))

вывод:

tensor([[1, 1, 0, 0],
        [1, 1, 0, 0],
        [0, 0, 0, 0],
        [0, 0, 0, 0]])

Способ 2:

Использование torch.nn.functional.pad()

import torch.nn.functional as F
import torch

def multiply(a, b):
    b = F.pad(input=b, pad=(1, 1, 1, 1), mode='constant', value=0)
    b[0,0] = 1
    b[0,1] = 1
    b[1,0] = 1
    return a*b

a = torch.tensor([[1, 1, 2, 2],[1, 1, 2, 2],[3, 3, 4, 4,],[3, 3, 4, 4]])
b = torch.tensor([[1, 0],[0, 0]])
print(multiply(a, b))

вывод:

tensor([[1, 1, 0, 0],
        [1, 1, 0, 0],
        [0, 0, 0, 0],
        [0, 0, 0, 0]])

Answer 4

Ниже приведено общее решение на основе Tensorflow, которое работает для входных матриц p (большой) и m (маленький) произвольной формы, если размеры p делятся на размеры mпо обеим осям.

def block_mul(p, m):
   p_x, p_y = p.shape
   m_x, m_y = m.shape
   m_4d = tf.reshape(m, (m_x, 1, m_y, 1))
   m_broadcasted = tf.broadcast_to(m_4d, (m_x, p_x // m_x, m_y, p_y // m_y))
   mp = tf.reshape(m_broadcasted, (p_x, p_y))
   return p * mp

Тест:

import tensorflow as tf

tf.enable_eager_execution()

p = tf.reshape(tf.constant(range(36)), (6, 6))
m = tf.reshape(tf.constant(range(9)), (3, 3))
print(f"p:\n{p}\n")
print(f"m:\n{m}\n")
print(f"block_mul(p, m):\n{block_mul(p, m)}")

Выход (Python 3.7.3, Tensorflow 1.13.1):

p:
[[ 0  1  2  3  4  5]
 [ 6  7  8  9 10 11]
 [12 13 14 15 16 17]
 [18 19 20 21 22 23]
 [24 25 26 27 28 29]
 [30 31 32 33 34 35]]

m:
[[0 1 2]
 [3 4 5]
 [6 7 8]]

block_mul(p, m):
[[  0   0   2   3   8  10]
 [  0   0   8   9  20  22]
 [ 36  39  56  60  80  85]
 [ 54  57  80  84 110 115]
 [144 150 182 189 224 232]
 [180 186 224 231 272 280]]

Другое решение, которое используетнеявное вещание выглядит следующим образом:

def block_mul2(p, m):
   p_x, p_y = p.shape
   m_x, m_y = m.shape
   p_4d = tf.reshape(p, (m_x, p_x // m_x, m_y, p_y // m_y))
   m_4d = tf.reshape(m, (m_x, 1, m_y, 1))
   return tf.reshape(p_4d * m_4d, (p_x, p_y))

Answer 5

Хотя другой ответ может быть решением, это не эффективный способ.Я придумаю еще одну для решения проблемы (, но все еще не идеально ).Следующая реализация требует слишком много памяти, когда наши входы имеют 3 или 4 измерения.Например, для входного размера 20 * 75 *1024* 1024, следующий расчет требует около 12 ГБ оперативной памяти.

Вот моя реализация:

import tensorflow as tf

tf.enable_eager_execution()


inps = tf.constant([
    [1, 1, 1, 1, 2, 2, 2, 2],
    [1, 1, 1, 1, 2, 2, 2, 2],
    [1, 1, 1, 1, 2, 2, 2, 2],
    [1, 1, 1, 1, 2, 2, 2, 2],
    [3, 3, 3, 3, 4, 4, 4, 4],
    [3, 3, 3, 3, 4, 4, 4, 4],
    [3, 3, 3, 3, 4, 4, 4, 4],
    [3, 3, 3, 3, 4, 4, 4, 4]])

on_cells = tf.constant([[1, 0, 0, 1]])

on_cells = tf.expand_dims(on_cells, axis=-1)

# replicate the value to block-size (4*4)
on_cells = tf.tile(on_cells, [1, 1, 4 * 4])

# reshape to a format for permutation
on_cells = tf.reshape(on_cells, (1, 2, 2, 4, 4))

# permutation
on_cells = tf.transpose(on_cells, [0, 1, 3, 2, 4])

# reshape
on_cells = tf.reshape(on_cells, [1, 8, 8])

# element-wise operation
print(inps * on_cells)

Вывод:

tf.Tensor(
[[[1 1 1 1 0 0 0 0]
  [1 1 1 1 0 0 0 0]
  [1 1 1 1 0 0 0 0]
  [1 1 1 1 0 0 0 0]
  [0 0 0 0 4 4 4 4]
  [0 0 0 0 4 4 4 4]
  [0 0 0 0 4 4 4 4]
  [0 0 0 0 4 4 4 4]]], shape=(1, 8, 8), dtype=int32)