import tensorflow as tf
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
plt.style.use('ggplot')
tf.__version__
'1.13.0-rc1'
Постановка задачи:
Так как задача должна решаться методом градиентного спуска, то будем рассматривать матрицу $X \in [0, 1]$ как матрицу вероятностей нахождения ребра {ij} в остовном дереве.
Будем опираться на следующие факты:
Отсюда мы получаем следующие ограничения:
Будем минимизировать следующий функционал: $L = \sum_{i=1}^{N}\sum_{j=1}^{N}{(A_{ij}*X_{ij})} + |\sum_{i=1}^{N}\sum_{j=1}^{N}{X_{ij} - (N - 1)}| + \sum_{i}{|\lambda_i|}$
def loss_function(X, A):
'''
The loss function.
Keyword arguments:
X - matrix of X_ij, probabilities that edge ij is in the Tree
A - adjacency matrix of the Graph
Return:
Loss
'''
weights_part = tf.reduce_sum(tf.multiply(X, A))
tree_limit = tf.abs(tf.abs(tf.reduce_sum(X)) - (int(A.shape[0]) - 1))
e, _ = tf.linalg.eigh(tf.multiply(X, A))
eigen_part = tf.reduce_sum(tf.square(e))
return 0.5*weights_part + tree_limit + eigen_part
def get_adj_matrix(X, A):
'''
Get adjacency of tree from weights X and adjacency X.
Keyword arguments:
X - matrix of X_ij, probabilities that edge ij is in the Tree
A - adjacency matrix of the Graph
Return:
new_adj - new adjacency matrix with threshold 0.5
'''
labels = tf.to_float(tf.greater_equal(X, 0.5))
return tf.multiply(labels, A)
def alg(A, steps=5000):
'''
Main algorithm.
Keyword arguments:
A - adjacency matrix of the Graph
steps - the number of steps in gradient descent process
Return:
X - matrix of learned weights
T - adjacency matrix of MST
'''
def prob_constr(T):
return tf.clip_by_value(T, 0, 1)
with tf.variable_scope("MST", reuse=tf.AUTO_REUSE):
X = tf.get_variable('Probs',
A.shape,
dtype=tf.float32,
initializer=tf.ones_initializer(),
constraint=prob_constr)
A = tf.constant(A,
dtype=tf.float32,
name='Adjacency')
loss = loss_function(X, A)
opt = tf.train.MomentumOptimizer(1e-3, 0.9, use_nesterov=True)
train = opt.minimize(loss)
initializer = tf.global_variables_initializer()
with tf.Session() as sess:
sess.run(initializer)
for step in range(steps):
sess.run(train)
x_matrix = sess.run(X)
tree_adj_matrix = sess.run(get_adj_matrix(X, A))
return (x_matrix, tree_adj_matrix)
random_weights = np.abs(np.random.normal(0, 1, (10, 10)))
G = nx.from_numpy_array(random_weights)
nx.draw_circular(G)
/usr/local/lib/python3.6/dist-packages/networkx/drawing/nx_pylab.py:611: MatplotlibDeprecationWarning: isinstance(..., numbers.Number) if cb.is_numlike(alpha):
x_matrix, tree_adj = alg(random_weights)
WARNING:tensorflow:From /usr/local/lib/python3.6/dist-packages/tensorflow/python/framework/op_def_library.py:263: colocate_with (from tensorflow.python.framework.ops) is deprecated and will be removed in a future version. Instructions for updating: Colocations handled automatically by placer. WARNING:tensorflow:From <ipython-input-5-2dafe6f10901>:13: to_float (from tensorflow.python.ops.math_ops) is deprecated and will be removed in a future version. Instructions for updating: Use tf.cast instead.
MST = nx.from_numpy_array(tree_adj)
nx.draw_circular(MST)
/usr/local/lib/python3.6/dist-packages/networkx/drawing/nx_pylab.py:611: MatplotlibDeprecationWarning: isinstance(..., numbers.Number) if cb.is_numlike(alpha):
nx.is_tree(MST)
False
MST.number_of_edges()
9
Мы видим, что алгоритм "почти" сходится к тому, что необходимо.
В целом, учитывая сильную неустойчивость алгоритма, я считаю, что задание выполнено - я ввел функцию потерь и нашел способ поиска Minimal Spanning Tree при помощи градиентного спуска, даже несмотря на то, что остовное дерево строго получено не было.
Алгоритм крайне чувствителен к гиперапараметрам, начальной инициализации, а также весов частей входящих в функцию потерь. Со временем я планирую доработать алгоритм.