Generating gradients in the energy landscape using rectified linear type cost functions for efficiently solving 0/1 matrix factorization in Simulated Annealing

Makiko Konoshima, Hirotaka Tamura, Yoshiyuki Kabashima

Abstract

The 0/1 matrix factorization defines matrix products using logical AND and OR as product-sum operators, revealing the factors influencing various decision processes. Instances and their characteristics are arranged in rows and columns. Formulating matrix factorization as an energy minimization problem and exploring it with Simulated Annealing (SA) theoretically enables finding a minimum solution in sufficient time. However, searching for the optimal solution in practical time becomes problematic when the energy landscape has many plateaus with flat slopes. In this work, we propose a method to facilitate the solution process by applying a gradient to the energy landscape, using a rectified linear type cost function readily available in modern annealing machines. We also propose a method to quickly obtain a solution by updating the cost function's gradient during the search process. Numerical experiments were conducted, confirming the method's effectiveness with both noise-free artificial and real data.

Introduction

0/1 matrix factorization (0/1 MF) is a critical technique for decomposing binary matrices into latent factors, widely used in recommendation systems and collaborative filtering. By representing data through logical operations (AND/OR), it offers a computationally efficient way to reveal hidden structures compared to real-valued factorization.

However, solving 0/1 MF via Simulated Annealing (SA) faces a significant hurdle: the "flat plateau" problem. Because traditional 0/1 MF relies on discrete logical operations, the resulting energy landscape is often devoid of gradients. When an optimization algorithm encounters these flat regions, it lacks directional information to guide it toward the global minimum, leading to slow convergence and a tendency to get trapped in local minima.

Methods: Sculpting the Energy Landscape

To overcome the limitations of flat energy landscapes, this research introduces a shift from a standard Binary Cost (BC) function to a Rectified Linear (RL) type cost function.

The RL-type Cost Function

Inspired by the Rectified Linear Unit (ReLU) activation function in deep learning, the proposed RL-type cost function is defined as $max(0, a)$. While a binary cost only indicates whether a constraint is met (0 or 1), the RL function provides a linear gradient when a constraint is violated. This transforms flat plateaus into sloped hills, providing the "direction" necessary for efficient annealing.

The RL-type cost function $G_{ij}$ provides a linear gradient when constraints are not met, unlike the flat binary cost.

Comparison of Approaches

The study compares three distinct methods:

  1. Binary Cost (BC): The baseline approach using standard logical operations.
  2. RL-Fixed (RL-F): Employs the RL-type function with a constant weighting factor ($\lambda$).
  3. RL-Update (RL-U): A dynamic approach where the weight ($\lambda$) of unsatisfied constraints is increased during the search. This "raises the floor" under the algorithm, forcing it out of local minima and encouraging broader exploration of the landscape.

These methods were implemented on a Digital Annealer, hardware specialized for high-speed combinatorial optimization.

Experimental Evaluation

The effectiveness of the RL-type functions was tested using both artificial and real-world datasets.

Artificial Data

Experiments on randomly generated binary matrices (sizes up to $40 \times 40$) with varying sparsity ($\rho$) demonstrated the superiority of the RL-U method. In sparse scenarios ($\rho = 0.1$), RL-U reached the optimal solution up to 1,000 times faster than the traditional BC method.

Comparison of Monte Carlo steps to solution (MCS0) showing RL-U's significant efficiency gains over BC and RL-F for sparse data.

Real-World Application: MovieLens

Using a subset of the MovieLens 25M dataset ($74 \times 51$ user-movie matrix), the RL methods outperformed state-of-the-art techniques like Discretized Non-negative Matrix Factorization (DNMF). Notably, the RL-U method showed exceptional performance in missing value estimation, making it highly suitable for practical recommendation tasks.

Conclusion

By introducing arithmetic-style gradients into a logical optimization problem, the proposed RL-type cost functions significantly enhance the efficiency of 0/1 matrix factorization. The dynamic weighting in RL-U proves particularly effective at navigating complex energy landscapes. While current tests were limited to smaller matrices, the results suggest a powerful new direction for solving large-scale discrete optimization problems on modern annealing hardware. Future work will focus on scaling these methods and exploring alternative nonlinear activation functions to further refine the energy landscape.

Summary updated

Abstract

The 0/1 matrix factorization defines matrix products using logical AND and OR as product-sum operators, revealing the factors influencing various decision processes. Instances and their characteristics are arranged in rows and columns. Formulating matrix factorization as an energy minimization problem and exploring it with Simulated Annealing (SA) theoretically enables finding a minimum solution in sufficient time. However, searching for the optimal solution in practical time becomes problematic when the energy landscape has many plateaus with flat slopes. In this work, we propose a method to facilitate the solution process by applying a gradient to the energy landscape, using a rectified linear type cost function readily available in modern annealing machines. We also propose a method to quickly obtain a solution by updating the cost function's gradient during the search process. Numerical experiments were conducted, confirming the method's effectiveness with both noise-free artificial and real data.
BibTeX
@article{konoshima2024generating,
  author = {Makiko Konoshima and Hirotaka Tamura and Yoshiyuki Kabashima},
  title = {{Generating gradients in the energy landscape using rectified linear type cost functions for efficiently solving 0/1 matrix factorization in Simulated Annealing}},
  journal = {Journal of the Physical Society of Japan},
  year = {2024},
  doi = {10.7566/jpsj.93.044002},
}
Figure