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.
Comparison of Approaches
The study compares three distinct methods:
- Binary Cost (BC): The baseline approach using standard logical operations.
- RL-Fixed (RL-F): Employs the RL-type function with a constant weighting factor ($\lambda$).
- 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.
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