def parity_problem(x_0):
    '''
    k : the length of the circular Chain
    x_0 : Boolean input
    xs : parameters array, Boolean, size k-1
    ys : array, Boolean, size
    '''
    xs = [x_0] concanate with xs
    ys = [ XOR(xs[i], xs[i+1 % k]) for i in range(k) ]
    return ys

Rethinking about alternative methods.

The main reason for advocating such differentiable programming languages is that, the differentiability allows for gradient-based parameter learning. And the result of the parity chain problem should be somewhat pessimistic to see. From my point of view, we can expect gradient-based learning to be slower since it requires iteractive mini-batchs, but it cannot be the case that it fails to learn in very simple problems.

As in the parity chain problem, it fails because some parameters happen to be 50% for zero and 50% for one, and being 50% makes it receive no more gradient as the computed gradient becomes zero. So a natural solution is, let us avoid the case of being 50%: each boolean variable must have an asymmetric distribution for being zero and one; if the 50% situation is avoided, then we get rid of the zero-gradient situation, and then we perhaps can learn successfully!

I tried with several alternative methods and I append a short description of experimental observation for each.

• Gumbel-softmax trick: does not work.
• Straight-through Estimator (STE): work, but a little bit unstable.
• Binary Optimizer (Bop) : works and very stable, even works for \(k=1024\) ⊕For Bop, I did not test with larger \(k\) but I think for larger \(k\), Bop will work as expected, just costing more epoch.

Alternative Methods.

Gumbel-softmax trick

The Gumbel-softmax trick or known as the concrete distribution is proposed independently by Jang, Gu, and Poole (⊕2016Jang, Eric, Shixiang Gu, and Ben Poole. 2016. “Categorical Reparameterization with Gumbel-Softmax.” arXiv Preprint arXiv:1611.01144.), Maddison, Mnih, and Teh (⊕2016Maddison, Chris J, Andriy Mnih, and Yee Whye Teh. 2016. “The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables.” arXiv Preprint arXiv:1611.00712.). Basically it uses an extra temperature parameter that is manually decreased per epoch. When the temperature is small, the distribution will be close to very clean and sharp discrete value; but when the temperature is high, the distribution might be more ambiguous, like 50%/50%.

Gumbel-softmax is widely applied in a lot of applications, but unfortunately in the parity chain problem, it also fails to work. It seems that the temperature is not really helpling and the same 50%/50% is obtained in the end.

Because of the failure of Gumbel-softmax, I start to think a more aggressive perspective, like in binary neural networks where the weight only have two discrete values, can we also say that we let the Boolean variables have either a value of 1 or 0? instead using the previous “soft” solution.

Straight-through Estimator (STE) Straight-through Estimator (STE) is now the dominant technique for binary neural networks. Straight-through estimator (STE) is first proposed in Hinton’s course lecture, and later more formally analyzed and evaluated by Bengio, Léonard, and Courville (⊕2013Bengio, Yoshua, Nicholas Léonard, and Aaron Courville. 2013. “Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation.” arXiv Preprint arXiv:1308.3432.). It was designed for parameters of value \(\{-1,1\}\), but now we wil consider the case of \(\{0,1\}\). STE maintains a continuous parameter, but only threshold into binary values in the forward computation. Note that a thresholded parameter \(\hat{w}\) is used for computing the objective function in the forward pass, but in the backward pass, the gradient is updated to \(w\). Since what is actually being optimized is still a continuous one, usual continuous optimization methods like SGD/Adam still apply.

In the forward pass, we binarize \(w\) into \[ \hat{w} = \begin{cases} 1, & \text{if } w > 0.5 \\ 0, & \text{otherwise}. \end{cases} \] and in the backward pass, the gradient is upated to the continuous parameterer \(w\).

In practice, we test STE and find that it can learn the parity problem successfully. Use the github reposity and run “python run.py –type=2 –k=128 –v=128”, you can see the STE converges to the right solution in about 2000 epochs. This is the screenshot taken by runing this command in terminal. Each line represent the states of the parameres, while a full block represents 100% being zero, and a empty block represents 0% being zero. For \(k=128\), STE converges in about 2000 epochs but you can see in the above figure that for epochs before the convergence, some of the parameters seems to accasionally flip its value of zero and one. This is just the way STE is. It does not have a mechanism like Bop which will be introduced below, to prevent the nosiy flips of zero-one values, so it might be a little bit not so stable compared to Bop.

Binary Optimizer (Bop) The Binary Optimizer (Bop) by Helwegen et al. (⊕2019Helwegen, Koen, James Widdicombe, Lukas Geiger, Zechun Liu, Kwang-Ting Cheng, and Roeland Nusselder. 2019. “Latent Weights Do Not Exist: Rethinking Binarized Neural Network Optimization.” In Advances in Neural Information Processing Systems, 7531–42.) provides a new perspective on learning binary parameters. So far, all the methods we introduced maintains a latent continuous parameter and thus optimization is straight forward. Standard optimization methods like SGD or Adam can be employed with no difficulty. One might ask, can we start making a new optimizer that directly optimize discrete valued parameters? The answer is yes and that is Binary Optimizer (Bop).

⊕The Bop is originally developed for binary neural network with parameter value in \(\{-1,1\}\). We will suit into the case of \(\{0,1\}\) Bop uses gradient as the learning signal and flips the value of \(w \in \{0,1\}\) only if the gradient signal \(m\) exceeds a predefined accepting threshold \(\tau\): \[ w = \begin{cases} 1-w , & \text{if } |m| > \tau \text{ and } ( w=1 \text{ and } m>0 \text{ or } w= 0 \text{ and } m<0 ) \\ w, & \text{otherwise}. \end{cases} \] where \(m\) is the gradient-based learning signal computed in the backward pass.

A non-zero \(\tau\) is introduced to avoid rapid back-and-forth flips of the binary parameter and we find it helpful to stabilize the learning because \(m\) is of high variance. To obtain consistent learning signals, instead of using vanilla gradient \(\nabla\) as \(m\), the exponential moving average of gradients is used \[ m = \gamma m + (1-\gamma) \nabla \] where \(\gamma\) is the exponential decay rate and \(\nabla\) is the gradient computed for a mini-batch.

In the parity problem, we set \(\gamma=1-10^{-5}\) and \(\tau=10^{-1}\). A smaller \(\tau\) will takes longer to converge to the right solution. It should also be mentioned that the accepting threshold \(\tau\) is the main advantage of Bop over STE, because a non-zero \(\tau\) helps avoid rapid back-and-forth update by noisy gradient, and is thus more stable than STE.

Use the refered github reposity and run “python run.py –type=3 –k=128 –v=128”, you can see the Bop converges to the right solution in about 100 epochs. For \(k=1024\), Bop converge to the right solution in about 900 epoch.

For \(k=128\), Bop can recover the solution in about 100 epoch. This is the screenshot taken by runing this command in terminal. Each line represent the states of the parameres, while a full block represents 100% being zero, and a empty block represents 0% being zero.

One thing to mention, with a smaller accepting threshold, Bop can takes longer to converge; as in the extreme case, if we set the accepting threshold to zero, then Bop will be somewhat very like STE. But of course, when introduce a new hyperparameter (the accepting threshold), we will need to spend extra efforts to tune it.