tensorflow - 快速矩阵乘法和神经网络

Question

我使用过一点神经网络，但不多。因此，为了提高我的舒适度，我决定用它来解决我最喜欢的数学问题之一:快速矩阵乘法。 标准算法需要 O(n^3) 来乘以两个 nxn 矩阵。 Strassen 算法的时间复杂度为 O(n^2.8)。基于 Coppersmith 和 Winograd 工作的算法可以降低到 O(n^2.373)，但由于常数因子较大而不切实际。 后两者之间有很大的回旋余地。特别是，如果您可以使用 48 次或更少的乘法运算来将两个 4x4 矩阵相乘，那么您就比 Strassen 做得更好。

所以这是我的设置:我有两个(伪随机生成的)nxn 矩阵，A 和 B。一个神经网络采用 A 元素的 NMULT 线性组合和 B 的 NMULT 线性组合，将它们逐点相乘，然后取 n ^2 输出的线性组合，尝试重构乘积 AB。损失是条目的平方和误差。 对抗网络采用两个随机矩阵 A' 和 B'，并输出 softsign(A' + A_offset) 和 softsign(B' + B_offset)，损失函数 = -1 * 另一个网络的平方和误差。

我交替进行 3 个训练步骤:在随机输入矩阵 A 和 B 上训练快速矩阵乘法网络，在随机输入矩阵 A' 和 B' 上训练对抗网络，并在输出上训练 fmm 网络对抗网络。

这不起作用。我不仅不能比斯特拉森做得更好，我什至不能重现基本的矩阵乘法!也就是说，如果我取 n = 2 且 NMULT = 8，则错误不会降至 0。

我知道除了使用神经网络之外还有其他(可能更好)的方法来解决这个问题——我只是将其作为一种学习方法。谁能给我建议如何解决这个问题？

参见下面的代码:

import numpy as np
import tensorflow as tf

epochs=1000
tot_batch = 1000
learning_rate = 0.01

MATRIX_SIZE = 2
NMULTS = 8

nvals = MATRIX_SIZE * MATRIX_SIZE

# These are the inputs to the adversarial NN generating our input matrices A&B.
a_inputs = tf.placeholder(tf.float32, [None, nvals])
b_inputs = tf.placeholder(tf.float32, [None, nvals])

adv_a_icpt = tf.Variable(tf.random_normal([nvals]))
adv_b_icpt = tf.Variable(tf.random_normal([nvals]))

a_vector = tf.nn.softsign(a_inputs + adv_a_icpt)
b_vector = tf.nn.softsign(b_inputs + adv_b_icpt)

# These are the two adversarial matrices we are multiplying; all entries
# are in [-1, 1]. This makes normalizing the error easier.
a_matrix = tf.reshape(a_vector, [-1, MATRIX_SIZE, MATRIX_SIZE])
b_matrix = tf.reshape(b_vector, [-1, MATRIX_SIZE, MATRIX_SIZE])

# This is the product A * B.
m_matrix = tf.matmul(a_matrix, b_matrix)

# This is what the fast-matrix-multiply NN will be predicting.
m_vector = tf.reshape(m_matrix, [-1, nvals])

fmm_a_wts = tf.Variable(tf.random_normal([nvals, NMULTS]))
fmm_b_wts = tf.Variable(tf.random_normal([nvals, NMULTS]))
fmm_output_wts = tf.Variable(tf.random_normal([NMULTS, nvals]))

# This is the output of the fast-matrix-multiply NN.
def fmm_output(input_a_vec, input_b_vec):
  hidden_a_inputs = tf.matmul(input_a_vec, fmm_a_wts)
  hidden_b_inputs = tf.matmul(input_b_vec, fmm_b_wts)
  hidden_output = tf.multiply(hidden_a_inputs, hidden_b_inputs) 
  return tf.matmul(hidden_output, fmm_output_wts)

# Treat each element of the input arrays as having a variance of O(1). Then
# the output array elements have a variance of O(MATRIX_SIZE).
loss_adv = tf.divide(
    tf.losses.mean_squared_error(m_vector, fmm_output(a_vector, b_vector)),
    MATRIX_SIZE)
abs_err_vec_adv = tf.abs(tf.subtract(m_vector, fmm_output(a_vector, b_vector)))
mean_abs_err_adv = tf.reduce_mean(abs_err_vec_adv, reduction_indices=[1])

m_rand = tf.matmul(tf.reshape(a_inputs, [-1, MATRIX_SIZE, MATRIX_SIZE]),
                   tf.reshape(b_inputs, [-1, MATRIX_SIZE, MATRIX_SIZE]))
loss_rand = tf.divide(
    tf.losses.mean_squared_error(tf.reshape(m_rand, [-1, nvals]),
                                 fmm_output(a_inputs, b_inputs)),
    MATRIX_SIZE) 


optimizer = tf.train.AdamOptimizer(learning_rate=learning_rate)

train_ADV = optimizer.minimize(-loss_adv,
                               var_list=[adv_a_wts, adv_b_wts,
                                         adv_a_icpt, adv_b_icpt])

train_FMMA = optimizer.minimize(loss_adv,
                                var_list=[fmm_a_wts, fmm_b_wts,
                                          fmm_output_wts])

train_FMMR = optimizer.minimize(loss_rand,
                                var_list=[fmm_a_wts, fmm_b_wts,
                                          fmm_output_wts])


init = tf.global_variables_initializer()

with tf.Session() as sess:
  sess.run(init)

  adv_batch_size = 100
  fmm_batch_size = 100

  for epoch in range(epochs):
    adv_loss = 0.0
    rand_loss = 0.0
    for i in range(tot_batch):
      # Run the fast-matrix-multiply NN training against random inputs.
      batch_a_inputs = np.random.uniform(low=-1., size=[fmm_batch_size, nvals])
      batch_b_inputs = np.random.uniform(low=-1., size=[fmm_batch_size, nvals])
      _, rerr = sess.run([train_FMMR, loss_rand],
                         feed_dict={ a_inputs : batch_a_inputs,
                                     b_inputs : batch_b_inputs })

      # Run the adversarial NN training.
      batch_a_inputs = np.random.normal(size=[adv_batch_size, nvals])
      batch_b_inputs = np.random.normal(size=[adv_batch_size, nvals])
      sess.run(train_ADV, feed_dict={ a_inputs : batch_a_inputs,
                                      b_inputs : batch_b_inputs })

      # Run the fast-matrix-multiply NN training against adversarial inputs.
      batch_a_inputs = np.random.normal(size=[fmm_batch_size, nvals])
      batch_b_inputs = np.random.normal(size=[fmm_batch_size, nvals])
      _, aerr, mae = sess.run([train_FMMA, loss_adv, mean_abs_err_adv],
                         feed_dict={ a_inputs : batch_a_inputs,
                                     b_inputs : batch_b_inputs })

      adv_loss += aerr / tot_batch
      rand_loss += 3.0 * rerr / tot_batch
      if i % 200 == 0:
        print("Batch " + str(i) + ", mean abs error: " + str(mae[0:4]))
    print("Epoch: " + str(epoch) + ", rand loss = " + str(rand_loss) +
          ", adv loss = " + str(adv_loss))

Answer 1

找到(或重新发现)矩阵乘法算法相当于求解 Brent Equations 的系统.

对于具有 k 次初等乘法的 n*n 矩阵乘积，系统具有 n^6 个方程，总和为 k 三因子乘积。因此，系统是高度非线性的，并且具有 3k n^2 未知数。在 practice ，很难找到 2*2 情况之外的解决方案。对于 2*2，有 64 个方程，每个方程有 7 个乘积。对于 3*3，有 729 个方程，每个方程有 23 个乘积。

研究人员试图发现 decades. 小因子矩阵的矩阵乘法算法如果神经网络能够击败整个科学界，这是可能的，但确实令人惊讶。

尽管我心存疑虑，related research成功地利用神经网络重新发现了 2x2 和 3x3 的算法。