2
$\begingroup$

I have a matrix that should be a permutation matrix. I want a function that should return zero loss for all valid permutation matrices and a non-zero number otherwise.

e.g.

loss([
[1, 0, 0],
[0, 1, 0],
[0, 0, 1],
]) = 0

loss([
[0, 1, 0],
[1, 0, 0],
[0, 0, 1],
]) = 0

# Negative numbers and numbers greater than 1 are bad
loss([
[-1, 0, 0],
[0, 2, 0],
[0, 0, 1],
]) > 0

# Fractions are bad
loss([
[0.1, 0, 0],
[0, 0.1, 0],
[0, 0, 0.1],
]) > 0

etc.

This is my current implementation in tensorflow

@tf.function
def bistable_loss(x):
    a = (x ** 2)
    b = (x - 1) ** 2
    
    return a * b

@tf.function
def permute_matrix_loss(P):
    loss = 0
    
    P_square = tf.math.square(P)
    axis_1_sum = tf.reduce_sum(P_square, axis=1)
    axis_0_sum = tf.reduce_sum(P_square, axis=0)
    
    # Penalize axes not adding up to one
    loss += tf.nn.l2_loss(axis_1_sum - 1)
    loss += tf.nn.l2_loss(axis_0_sum - 1)
    
    # Penalize numbers outside [0, 1]
    loss += tf.math.reduce_sum(bistable_loss(P))
    
    return loss

Is there any existing literature on this subject which has a more elegant/robust solution for this?

$\endgroup$
2
  • $\begingroup$ since you want to learn permutation matrices, why not to use some sort of soft-max arrangement to force each entry to be positive and each column (or row) to sum up to 1? $\endgroup$
    – carlo
    Commented Jul 18, 2020 at 14:12
  • $\begingroup$ this way I guess you could use a cross-entropy loss. it depends on what is your problem exactly $\endgroup$
    – carlo
    Commented Jul 18, 2020 at 14:14

1 Answer 1

3
$\begingroup$

This paper might help: http://arxiv.org/abs/1901.08624. From the abstract:

[...] In this paper, we propose to automate channel shuffling by learning permutation matrices in network training. We introduce an exact Lipschitz continuous non-convex penalty so that it can be incorporated in the stochastic gradient descent to approximate permutation at high precision. Exact permutations are obtained by simple rounding at the end of training and are used in inference. [...]

$\endgroup$
1
  • $\begingroup$ I dont remember why I asked this question 7 months ago but thanks. This might help someone else in the future. $\endgroup$ Commented Mar 14, 2021 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.