---
abstract: 'In this work an iterative algorithm based on unsupervised learning is presented, specifically on a Restricted Boltzmann Machine (RBM) to solve a perfect matching problem on a bipartite weighted graph. Iteratively is calculated the weights $ w_{ij} $ and the bias parameters $\theta = ( a_i, b_j) $ that maximize the energy function and assignment element $i$ to element $j$. An application of real problem is presented to show the potentiality of this algorithm.'
author:
- |
    Francesco Curia\
    Department of Statistical Science\
    Sapienza, University of Rome\
    Rome, 00185 Italy\
    `francesco.curia@uniroma1.it`\
title: |
    Restricted Boltzmann Machine Assignment Algorithm:\
    Application to solve many-to-one matching problems on weighted bipartite graph
---

Introduction {#intro}
============

The assignment problems fall within the combinatorial optimization problems, the problem of matching on a bipartite weighted graph is one of the major problems faced in this compound. Numerous resolution methods and algorithms have been proposed in recent times and many have provided important results, among them for example we find: Constructive heuristics, Meta-heuristics, Approximation algorithms, Iper-heuristics, and other methods. Combinatorial optimization deals with finding the optimal solution between the collection of finite possibilities. The finished set of possible solutions. The heart of the problem of finding solutions in combinatorial optimization is based on the efficient algorithms that present with a polynomial computation time in the input dimension. Therefore, when dealing with certain combinatorial optimization problems one must ask with what speed it is possible to find the solutions or the optimal problem solution and if it is not possible to find a resolution method of this type, which approximate methods can be used in polynomial computational times that lead to stable explanations. Solve this kind of problem in polynomial time $o(n)$ has long been the focus of research in this area until Edmonds \[1\] developed one of the most efficient methods. Over time other algorithms have been developed, for example the fastest of them is the Micali e Vazirani algorithm \[2\], Blum \[3\] and Gabow and Tarjan \[4\]. The first of these methods is an improvement on that of Edmonds, the other algorithms use different logics, but all of them with computational time equal to $o(m \sqrt n)$. The problem is fundamentally the following: we imagine a situation in which respect for the characteristics detected on a given phenomenon is to be assigned between elements of two sets, as for example in one of the most known problems such as the tasks and the workers to be assigned to them. A classical maximum cardinality matching algorithm to take the maximum weight range and assign it, in a decision support system, through the domain expert this could also be acceptable, but in a totally automatic system like a system could be of artificial intelligence that puts together pairs of elements on the basis of some characteristics, this way would not be very reliable, totally removing the user’s control. Another problem related to this kind of situation is that of features. Let’s take as an example a classic problem of flight-gate assignment in an airport, on the basis of the history we could have information about the flight, the gates and the time, the flight number and maybe the airline. Little information that even through the best of feature enginering would lead to a model of machine learning, specifically of classification, very poor in information. Treating the same problem with classical optimization, as done so far, would lead to solving it with a perfect matching of maximum weight, and we would return to the beginning.

Matching problems {#sec:1}
=================

Matching problems are among the fundamental problems in combinatorial optimization. In this set of notes, we focus on the case when the underlying graph is bipartite. We start by introducing some basic graph terminology. A graph $G = (V, E)$ consists of a set $V = A \cup B$ of vertices and a set $E$ of pairs of vertices called edges. For an edge $e = (u, v)$, we say that the endpoints of e are $u$ and $v$; we also say that $e$ is incident to $u$ and $v$. A graph $G = (V, E)$ is bipartite if the vertex set $V$ can be partitioned into two sets $A$ and $B$ (the bipartition) such that no edge in $E$ has both endpoints in the same set of the bipartition. A matching M is a collection of edges such that every vertex of $V$ is incident to at most one edge of $M$. If a vertex $v$ has no edge of $M$ incident to it then $v$ is said to be exposed (or unmatched). A matching is perfect if no vertex is exposed; in other words, a matching is perfect if its cardinality is equal to $|A| = |B|$. In the literature several examples of the real world have been treated such as the assignment of children to certain schools \[5\], or as donors and patients \[6\] and workers at companies \[7\]. The problem of the weighted bipartite matching finds the feasible match with the maximum available weight. This problem was developed in several areas, such as in the work of \[8\] about protein and structure alignment, or within the computer vision as documented in the work of \[9\] or as in the paper by \[10\] in which the similarity of the texts is estimated. Other jobs have faced this problem in the classification \[11\],\[12\] e \[13\], but not for many to one correspondence. The mathematical formulation can be solved by presenting it as a linear program. Each edge $(i,j)$, where $i$ is in $A$ and $j$ is in $B$, has a weight $w_{ij}$. For each edge $(i,j)$ we have a decision variable

$$x_{ij} =\begin{cases} 1 & \mbox{if the edge is contained in the matching} \\ 0 & \mbox{otherwise}
\end{cases}$$

and $x_{ij}\in \mathbb {Z} {\text{ for }}i,j \in A,B$, and we have the following LP:

$$\begin{aligned}
& \underset{x_{ij}}{\text{max}} \sum _{(i,j)\in A\times B}w_{ij}x_{ij}
\end{aligned}$$

$$\begin{aligned}
\sum _{j\in B}x_{ij}=1{\text{ for }}i\in A
\end{aligned}$$

$$\begin{aligned}
\sum _{i\in A}x_{ij}=1{\text{ for }}j\in B
\end{aligned}$$

$$\begin{aligned}
0 \leq x_{ij} \leq 1{\text{ for }}i,j \in A,B
\end{aligned}$$

$$\begin{aligned}
x_{ij}\in \mathbb {Z} {\text{ for }}i,j\in A,B
\end{aligned}$$

![Bipartite Weighted Matching[]{data-label="fig:1"}](matching.PNG){width="55.00000%"}

Motivation {#sec:2}
==========

The problem in a weighted bipartite graph $G = (V = A \cup B, W)$, is when we have different weights (historical data) $W = \left(w_{11}, w_{12} ..., w_{ij} \right)$ for the set of nodes to which corresponds the same set of nodes $B$. One of most popular solution is Hungarian algorithm \[16\] . The assignment rule therefore in many real cases could be misleading and limiting as well as it could be unrealistic as a solution. Machine learning (ML) algorithms are increasingly gaining ground in applied sciences such as engineering, biology, medicine, etc. both supervised and unsupervised learning models. The matching problem in this case can be seen as a set of inputs $ x_1, ..., x_k$ (in our case the nodes of the set A) and a set of ouput $y_1, ..., y_k$ (the respective nodes of the set $B$), weighed by a series of weights $w_{11}, ... w_{ij}$, which inevitably recall the structure of a classic neural network. The problem is that in this case there would be a number of classes (in the case of assignment) equal to the number of inputs. Considering it as a classic machine learning problem, the difficulty would lie in the features and their engineering, on the one hand, while on the other the number of classes to predict (assign) would be very large. For example, if we think about matching applicants and jobs, if we only had the name of a candidate for the job, we would have very little info to build a robust machine learning model, and even a good features engineering would not lead to much, but having available other information on the candidate they could be extracted it is used case never as “weight” to build a neural network, but even in this case the constraint of a classic optimization model solved with ML techniques would not be maintained, let’s say we would “force” a little hand. While what we want to present in this work is the resolution of a classical problem of matching (assignment) through the application of a ML model, in this case of a neural network, which as already said maintains the mathematical structure of a node (input) and arc (weight) but instead of considering the output of arrival (the set $B$) as classification label (assignment) in this case we consider an unsupervised neural network, specifically an Restricted Boltzmann Machine.

Contributions {#sec:3}
=============

The contributions of this work are mainly of two types: the first is related to the ability to use an unsupervised machine learning model to solve a classical optimization problem which in turn has the mathematical structure of a neural network based on two layers, in our case of RBM a visible and a hidden one. In this case the nodes of the set $ B $ become the variables of the model and the number of times that the node $i$ has been assigned to the node $j$ (for example in problems that concerns historical data analysis), becomes the weight $ w_ {ij} $ which at its turn becomes the value of the variable $i$-th in the RBM model. The second is the ability to solve real problems, as we will see later in the article, in which it is necessary to carry out a matching between elements of two sets and the maximum weight span is not said to be the best assignment, especially in the case where the problem is many-to-one, like many real problems.

Restricted Boltzmann Machine {#sec:3}
============================

Restricted Boltzmann Machine is an unsupervised method neural networks based \[14\]; the algorithm learns one layer of hidden features. When the number of hidden units is smaller than that of visual units, the hidden layer can deal with nonlinear complex dependency and structure of data, capture deep relationship from input data , and represent the input data more compactly. Assuming there are $c$ visible units and $m$ hidden units in an Restricted Boltzmann Machine. So $v_i$ for $i = 1,...,c$ indicates the state of the $i-$th visible unit, where

$$v_i =\begin{cases} 1 & \mbox{if the i-th term is annotated to the element } \\ 0 & \mbox{otherwise}
\end{cases}$$

for $i=1,...,c$ and furthemore we have

$$h_j =\begin{cases} 1 & \mbox{the state of hidden unit is active} \\ 0 & \mbox{otherwise}
\end{cases}$$

for $j=1,...,m$ and $w_{ij}$ is the weight associated with the connection between $v_i$ and $h_j$ and define also the joint configuration $(v,h)$.

The energy function that capturing the interaction patterns between visible layer and hidden layer is define as follow: $$E(v,h| \theta ) = - \sum_{i = 1}^{c} a_i v_i - \sum_{j = 1}^{m} b_j h _j - \sum_{i = 1}^{c}  \sum_{j = 1}^{m} v_i h_j w_{ij}$$

where $\theta = \left( w_{ij}, a_i, b_j\right)$ are parameters of the model: $a_i$ and $b_j$ are biases for the visible and hidden variables, respectively. The parameters $w_{ij}$ is the weights of connection between visible variables and hidden variables. The joint probability is represented by the follow quantity: $$p(v,h) = \frac{e^-E(v,h)}{Z}$$

where

$$Z = \sum_{v,h} e^{-E(v,h)}$$

is a normalization constant and the conditional distributions over the visible and hidden units are given by sigmoid functions as follows:

$$p(v_i = 1 | h) = \sigma \left( \sum_{j = 1}^{m} w_{ij} h_j + a_i \right)$$

$$p(h_j = 1 | v) = \sigma \left( \sum_{i = 1}^{c} w_{ij} v_i + b_j  \right)$$

where $\sigma = \frac{1}{1 + e^{-x}}$

$\\$ RBM are trained to optimizie the product of probabilities assigned to some training set $V$ (a matrix, each row of which is treated as a visible vector v)

$$\begin{aligned}
& \underset{w_{ij}}{\text{arg} \ \text{max}} \prod_{i=1}^c p(v_i)
\end{aligned}$$

The RBM training takes place through the Contrastive Divergence Algorithm (see Hinton 2002 \[15\]). For the (4) and (7) we can pass to log-likelihood formulation

$$L_v = log \sum_{h} e^{-E(v,h)} - log \sum_ {v,h} e^{-E(v,h)}$$

and derivate the quantity

$$\frac{\partial L_v}{\partial w_{ij}} = \sum_{h} p(h|v) \cdot v_i h_j - \sum_{v,h} p(v,h) \cdot v_i h_j$$

$$\frac{\partial L_v}{\partial w_{ij}} = \mathbb{E} [p(h|v)]  - \mathbb{E}[p(v,h)]$$

In the above expression, the first quantity represents the expectation of $v_i \cdot h_j$ to the conditional probability of the hidden states given the visible states and the second term represents the expectation of $v_i \cdot h_j$ to the joint probability of the visible and hidden states. In order to maximize the (7), which involves log of summation, there is no analytical solution and will use the stochastic gradient ascent technique. In order to compute the unknown values of the weights $w_{ij}$ such that they maximize the above likelihood, we compute using gradient ascent : $$w_{ij}^{k+1}  = w_{ij}^{k} + \alpha \cdot \frac{\partial L_v}{\partial w_{ij}} %- \beta \cdot w_{ij}^{k} + \lambda \cdot  \left(w_{ij}^{k}  - w_{ij}^{k-1}\right)$$ where $\alpha \in (0,1) $ is the learning rate. At this formulation we can add an term of penality and obtain the follow $$w_{ij}^{k+1}  = w_{ij}^{k} + \alpha \cdot \frac{\partial L_v}{\partial w_{ij}} + \eta \cdot \frac{w_{ij}^{k-1}}{w_{ij}^k}$$ where $\eta > 0$ is penalty parameters and $ \eta \cdot \frac{w_{ij}^{k-1}}{w_{ij}^k}$ measure the contribute of weights variation in the $k$-th step of update.

Restricted Boltzmann Machine Assignment Algorithm (RBMAA) {#sec:4}
=========================================================

In this section is presented the algorithm RBM based and is explaneid the single steps.

1.  In this step the algorithm takes as input the matrix $W$ relative to the weights of the assignments, either the weight $ w_ {ij} $ represents the number of times that the element $ i $ has been assigned to the element $ j $

2.  The matrix $W$ is binarized. For each element $ w_ {ij} > $ 0 take 1 or 0 and an a matrix $\tilde W$ is created with elements 0-1.

3.  In this step the RBM is applied taking as input the binary matrix $\tilde W $. The probability product related to the visible units of the RBM is maximized (13). The weights $ w_ {ij} $ are updated according to (17) and the biases according to the RBM training rule. Once these updated values are obtained, the optimized value $ \hat p (v_i) $ if this is greater than $\epsilon >$ 0 assigns 1 otherwise 0 and the iteration of the RBM is restarted until for each row of the matrix there is not a single value 1 which is the same as assignment. The quantile of level $ \alpha = $ 0.99 was used to determine the threshold $\epsilon$.

4.  The output of the algorithm is a matrix with values 0-1 and on each line we obtain a single value equal to 1 which is equivalent to the assignment of the element $ i $ to the element $ j $.

The pseudocode is presented in the next section.

**Input**:\
$\epsilon$, threshold value\
$b_j$, hidden units bias value\
$a_i$, visible units bias value\
$\alpha$, learning rate for visible bias updating\
$\beta$, learning rate for hidden bias updating\
Matrix $n  \times m$, $W = \{ w_{ij} \}$ number of times which $i$ has been assigned to $j$ \

Application of the RBMAA to a real problem {#sec:5}
==========================================

Now we proceed to provide the results of the application of the algorithm (see Appendix). The problem instance is 351 elements for the set $ A $ and 35 for the set $ B $; the goal is to assign for each element of $ A $, one and only one element of $ B $, so as to have the sum for row equal to 1 as in (3) and in step 4 of the algorithm. The weights $ w_ {ij} $ are represented by the number of times the element $ a_i \in A $ has been assigned to the element $ b_j \in B $, based on a set of historical data that we have relative to flight-gate assignments of a well-known international airport. The difficulty is the one discussed in the first part of the work, in which we want to obtain a robust machine learning algorithm that classifies and assigns the respective gate for each flight. Starting from the available features, the algorithm presented in the work was implemented. The computational results are very interesting in terms of calculation speed and assignment.

Conclusions and discussion {#sec:6}
==========================

This can be the starting point for more precise, fast and sophisticated algorithms, which combine the combinatorial optimization with machine learning but on the basis of unsupervised learning and not only on the optimization of cost functions.

J. Edmonds. “Paths, trees and flowers”. Canadian Journal of Mathematics, 17: 449-467, 1965 S. Micali and V. V. Vazirani. “An $O(\sqrt{|V|} \cdot |E|)$ algorithm for finding maximum matching in general graphs”. In Proceedings of the twenty First annual IEEE Symposium on Foundations of Computer Science,1980. N. Blum. “A new approach to maximum matching in general graphs”. In Proc. 17th ICALP, volume 443 of Lecture Notes in Computer Science, pages 586 - 597. Springer-Verlag, 1990. H. N. Gabow and R. E. Tarjan. “Faster scaling algorithms for general graph matching problems”. J. ACM, 38(4):815 - 853, 1991. Ryoji Kurata, Masahiro Goto, Atsushi Iwasaki, and Makoto Yokoo. “Controlled school choice with soft bounds and overlapping types”. In AAAI Conference on Artificial Intelligence (AAAI), 2015. Dimitris Bertsimas, Vivek F Farias, and Nikolaos Trichakis. “Fairness, efficiency, and flexibility in organ allocation for kidney transplantation”. Operations Research, 61(1):73–87, 2013. John Joseph Horton. “The effects of algorithmic labor market recommendations: evidence from a field experiment”,To appear, Journal of Labor Economics, 2017. E Krissinel and K Henrick. “Secondary-structure matching (ssm), a new tool for fast protein structure alignment in three dimensions”. Acta Crystallographica Section D: Biological Crystallography, 60(12):2256–2268, 2004. Serge Belongie, Jitendra Malik, and Jan Puzicha. “Shape matching and object recognition using shape contexts”. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(4):509–522, 2002. Liang Pang, Yanyan Lan, Jiafeng Guo, Jun Xu, Shengxian Wan, and Xueqi Cheng. “Text matching as image recognition”. In AAAI Conference on Artificial Intelligence (AAAI), 2016. Gediminas Adomavicius and YoungOk Kwon.“ Improving aggregate recommendation diversity using ranking-based techniques”. IEEE Transactions on Knowledge and Data Engineering (TKDE), 24(5):896–911, 2012. Chaofeng Sha, Xiaowei Wu, and Junyu Niu. “A framework for recommending relevant and diverse items”. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2016. Azin Ashkan, Branislav Kveton, Shlomo Berkovsky, and Zheng Wen. “Optimal greedy diversity for recommendation”. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pages 1742–1748, 2015. A. Fischer and C. Igel, “An Introduction to Restricted Boltzmann Machines, in Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications”, vol. 7441 of Lecture Notes in Computer Science, pp. 14–36, Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. Hinton, G. E. “A Practical Guide to Training Restricted Boltzmann Machines”. Technical Report, Department of Computer Science, University of Toronto, 2010. H.W. Kuhn, “On the origin of the Hungarian method for the assignment problem, in J.K. Lenstra, A.H.G. Rinnooy Kan, A. Schrijver”, History of Mathematical Programming, Amsterdam, North-Holland, 1991, pp. 77-81

$\\$ $\\$ $\\$ $\\$

$\\$ $\\$ $\\$ $\\$ $\\$ $\\$ $\\$ $\\$ $\\$ $\\$ $\\$ $\\$

Appendix
========
