高速行列乗算とニューラルネットワーク

Question

私はニューラルネットワークを多少使用しましたが、それほど多かったわけではありません。だから私のレベルの快適性を高める試みとして、私は好きな数学の問題の1つ、すなわち高速行列の乗算を使って遊んでみることにしました。 標準アルゴリズムでは、2つのnxn行列を掛けるためにO（n^3）が必要です。 StrassenアルゴリズムはO（n^2.8）でそれを行います。 CoppersmithとWinogradによる作業に基づくアルゴリズムは、O（n^2.373）まで下がるが、大きな一定係数のために実用的ではない。 後者の2つの間には、多くのウィグルルームがあります。特に、2倍の4x4行列を48乗算以下で掛けることができれば、Strassenよりも優れています。

これは私の設定です：私は2つの（疑似ランダムに生成された）nxn行列AとBを持っています。一つのニューラルネットワークは、AとNMULTの線形結合の要素のNMULT線形結合をとり、出力のn^2線形結合、積ABを再構築しようとする。損失は​​、エントリに対する二乗和の誤差です。 敵対ネットワークは、2つのランダム行列A 'とB'をとり、他のネットワークの損失関数= -1 *二乗和の誤差を伴うソフトサイン（A '+ A_offset）とソフトサイン（B' + B_offset）を出力します。

ランダム入力マトリックスAとBで高速マトリックス乗算ネットワークを訓練し、ランダム入力マトリックスA 'とB'で敵対ネットワークを訓練し、出力上でfmmネットワークを訓練する敵対的ネットワークの

動作しません。 Strassenより良くできないだけでなく、基本的な行列乗算も再現できません。つまり、n = 2、NMULT = 8の場合、0エラーにはなりません。

私は神経ネットワークを使用するよりも、この問題を解決する他の（潜在的により良い）方法があることを知っています。私はこれを学習方法としてのみ行っています。誰も私にこの問題を解決する方法を教えてもらえますか？行列乗算アルゴリズムはBrent Equationsのシステムを解くことと等価である見つける（または再検出）する

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

：

は、以下のコードを参照してください。 k基本乗算とn*nマトリックス製品の

、システムは、k 3因子の積の和とn^6式を有します。したがって、システムは高度に非線形であり、3k n^2未知数を有する。 practiceでは、2*2のケースを超える解決策を見つけることは非常に困難です。 2*2については、それぞれ7つの製品を含む64の式があります。 3*3については、それぞれ729の式があり、それぞれ23の製品があります。

研究者は、小因子マトリクスの行列乗法アルゴリズムを発見しようとしましたdecades.ニューラルネットワークが科学コミュニティ全体を打ち負かす可能性はありますが、本当に驚異的です。

疑問にもかかわらず、related researchは、ニューラルネットワークを使用して2x2と3x3のアルゴリズムを再発見することに成功しました。