DOI: https://doi.org/10.1613/jair.1.21105
تاريخ النشر: 2026-01-27
المؤلف: Marianne Defresne وآخرون
الموضوع الرئيسي: تحقيق القيود والتهيئة
نظرة عامة
في هذا البحث، يقدم المؤلفون بنية عصبية رمزية قابلة للاشتقاق مصممة لمعالجة مشاكل الاستدلال والتفكير المنفصل الصعبة من نوع NP. تتضمن البنية دالة خسارة احتمالية متخصصة، تُسمى E-PLL، والتي تمكّن من التعلم المتزامن لكل من القيود والأهداف ضمن المشاكل التوافقية. يسمح هذا النهج بتدريب قابل للتوسع من خلال إزالة الحلول التوافقية من حلقة التدريب، مع تحقيق دقة عالية من خلال الاستدلال الدقيق. تظهر النتائج التجريبية كفاءة البنية في تعلم حل أنواع مختلفة من سودوكو ومهام تحسين مثل مشكلة القطع المرئي Min-Cut/Max-Cut، بالإضافة إلى معالجة تحديات العالم الحقيقي المعقدة مثل تصميم البروتينات.
يؤكد المؤلفون على قدرة البنية على دمج المدخلات الطبيعية في صياغة مشاكل الاستدلال المنفصل، مما يعزز كفاءة البيانات ويمكّن من دمج التحيزات الاستقرائية. بينما يُطلب أن تكون الطبقة العصبية الرمزية هي الطبقة النهائية في الشبكة، فإن هذا الخيار التصميمي عملي للعديد من التطبيقات حيث تمثل القرارات المنفصلة الناتج النهائي. يُقترح أن يتم استكشاف قدرة البنية على تحديد الخصائص العالمية والتفاعلات المعقدة في الأعمال المستقبلية، بالإضافة إلى توسيع خسارة E-PLL لاستيعاب مجموعة أوسع من المشاكل NP-complete من خلال لغات نمذجة محسّنة. بشكل عام، يساهم هذا البحث بشكل كبير في مجال الأنظمة الهجينة العصبية الرمزية، مع آثار على تطبيقات مختلفة في التحسين والاستدلال.
مقدمة
تناقش مقدمة الورقة ظهور الهياكل العصبية الهجينة التي تدمج الاستدلال المنفصل والتحسين ضمن الشبكات العصبية، مدفوعة بالحاجة إلى معالجة عدم اليقين في اتخاذ القرار. وقد أدى ذلك إلى تطوير التعلم الموجه نحو القرار (DFL)، الذي يهدف إلى الاستفادة من البيانات المتاحة لإنتاج حلول عالية الجودة للأشياء المعقدة ذات الهيكل المنفصل، مثل التسلسلات والأشجار والرسوم البيانية. يبرز المؤلفون قيود نماذج اللغة الكبيرة في الاستدلال المنطقي، مما يضع الأنظمة العصبية الرمزية كبديل واعد في السعي نحو الذكاء الاصطناعي العام (AGI).
تركز الورقة بشكل خاص على توقع المخرجات الهيكلية (SOP)، حيث الهدف هو توقع الحلول المثلى لمشاكل التحسين التوافقي (CO) مع وظائف وأهداف غير معروفة. يحدد المؤلفون التحديات التي تطرحها الطبيعة المنفصلة للمتغيرات، مما يعقد التعلم القائم على التدرجات ويزيد من المتطلبات الحاسوبية أثناء التدريب. لمعالجة هذه التحديات، يقترحون بنية عصبية رمزية تجمع بين طبقات التعلم العميق وطبقة استدلال نموذج رسومي صعب من نوع NP، مقدمة دالة خسارة جديدة، وهي Emmental Pseudo-LogLikelihood (E-PLL)، التي تتعلم بفعالية القيود من المدخلات الطبيعية. تظهر البنية دقة عالية في حل المشاكل المعقدة، مثل سودوكو المرئي وحالات تصميم البروتين، مما يبرز قابليتها للتوسع وتطبيقها في سياقات مختلفة.
طرق
في هذا القسم، يحدد المؤلفون منهجيتهم التجريبية لتدريب النماذج لحل ألغاز سودوكو، مع التركيز على مستويات مختلفة من صعوبة الشبكة. يستخدمون مجموعة بيانات RRN، التي تتكون من شبكات سودوكو ذات الحل الواحد مع 17 إلى 34 تلميحًا، لتأسيس خط أساس للتدريب والتحقق. على وجه التحديد، يقومون بالتدريب على 100 شبكة والتحقق على 32 شبكة، بينما يتم الاختبار على مجموعة من 1,000 حالة صعبة تحتوي على 17 تلميحًا. بالإضافة إلى ذلك، يدمجون مجموعة بيانات سودوكو-إكستريم الجديدة، التي تصنف الشبكات بناءً على عدد التراجعات المطلوبة من قبل الحل، مما يزيد مجموعة تدريبهم إلى 1,000 شبكة من خلال إجراء تعزيز محدد.
علاوة على ذلك، يستكشف المؤلفون معيارًا من Nandwani وآخرون (2021) يتضمن شبكات ذات حلول متعددة. في هذا السيناريو، يكون فقط مجموعة فرعية من الحلول (حتى 5) متاحة أثناء التدريب، مع الهدف من توقع أي حل ممكن. تتكون مجموعات التدريب والتحقق والاختبار من 100 و32 و256 شبكة، على التوالي، مع اختيار أحد الحلول المتاحة بشكل عشوائي أثناء التدريب. يهدف هذا النهج إلى تعزيز قدرة النموذج على التعميم عبر تكوينات سودوكو المختلفة ومجموعات الحلول.
نتائج
في قسم النتائج، يقيم المؤلفون أداء دالة خسارة E-PLL المقترحة في حل ألغاز سودوكو مقارنة بدالة خسارة NPLL التقليدية. أدى التدريب الأولي باستخدام NPLL إلى تعلم الشبكة فقط مجموعة محدودة من القواعد، مما أدى إلى استدلال غير فعال على مجموعة الاختبار. بالمقابل، باستخدام E-PLL مع معلمة فرعية $k=10$—التي تتجاهل الرسائل من $k$ متغيرات مختارة عشوائيًا—تحققت دقة 100% على الشبكات الصعبة للاختبار، مما يظهر تحسينات كبيرة في كل من كفاءة التدريب (تستغرق فقط دقيقتين على وحدة معالجة مركزية واحدة) وموثوقية الحل.
يقدم المؤلفون أيضًا تحليلًا مقارنًا لطريقتهم مقابل مجموعة متنوعة من الأساليب الموجودة، بما في ذلك نماذج التعلم العميق النقية والأساليب الهجينة. بينما تتطلب نماذج أخرى، مثل الشبكات العلائقية المتكررة ونماذج الانتشار الضوضائي الاحتمالية، بيانات واسعة وتكافح مع الألغاز الأكثر صعوبة، تتفوق طريقة E-PLL في كفاءة البيانات والدقة، محققة موثوقية مثالية مع الحد الأدنى من وقت التدريب. تسلط النتائج الضوء على مزايا نهج E-PLL، خاصة في قدرته على حل ألغاز سودوكو بفعالية مع الحفاظ على متطلبات حسابية منخفضة مقارنة بالأساليب الأخرى.
نقاش
في هذا القسم، يناقش المؤلفون العلاقة بين عملهم والأساليب الموجودة في التحسين العكسي، واكتساب القيود، والتعلم الموجه نحو القرار (DFL). يبرزون أن الأساليب التقليدية للتحسين العكسي تعتمد على الحلول الدقيقة لتحديد المعلمات غير المعروفة، بينما يستفيد نهجهم من الميزات القابلة للملاحظة، مثل صور سودوكو، لتعلم القيود والأهداف. يميزون طريقتهم عن التقنيات الموجودة التي تركز على مشاكل التحسين المستمر، مؤكدين قدرتهم على التعامل مع قيود المجال المحدود الزوجية العشوائية، على عكس الأعمال السابقة التي تقتصر على أشكال محددة من قيود الكاردينالية.
يقدم المؤلفون Emmental Pseudo-Log-Likelihood (E-PLL) كدالة خسارة جديدة مصممة لمعالجة قيود دالة الخسارة التقليدية Negative Pseudo-Log-Likelihood (NPLL) في تعلم القيود من البيانات الملاحظة. تتضمن E-PLL استراتيجية قناع عشوائي للتخفيف من تأثير القيود الزائدة على تحديثات التدرج، مما يعزز عملية التعلم. كما يناقشون التحديات التي تطرحها المتغيرات غير الملاحظة في نموذجهم، خاصة في سياق سودوكو المرئي، ويقترحون إجراء تعويض لتحسين الوظيفة المشتركة المحددة بواسطة نموذجهم الرسومي. يختتم القسم بتسليط الضوء على تعددية بنيتهم، التي تم اختبارها في مهام تعلم متنوعة، بما في ذلك الألغاز الرمزية والمرئية، مما يوضح فعاليتها في تعلم القيود والأهداف في مشاكل NP-hard.
DOI: https://doi.org/10.1613/jair.1.21105
Publication Date: 2026-01-27
Author(s): Marianne Defresne et al.
Primary Topic: Constraint Satisfaction and Optimization
Overview
In this research, the authors present a novel differentiable neuro-symbolic architecture designed to tackle NP-hard discrete reasoning and optimization problems. The architecture incorporates a specialized probabilistic loss function, termed E-PLL, which enables the simultaneous learning of both constraints and objectives within combinatorial problems. This approach allows for scalable training by removing the combinatorial solver from the training loop, while still achieving high accuracy through exact inference. Empirical results demonstrate the architecture’s efficiency in learning to solve various Sudoku variants and optimizing tasks such as the visual Min-Cut/Max-Cut problem, as well as addressing complex real-world challenges like protein design.
The authors emphasize the architecture’s ability to integrate natural inputs into the formulation of discrete reasoning problems, enhancing data efficiency and enabling the incorporation of inductive biases. While the neuro-symbolic layer is required to be the final layer of the network, this design choice is practical for many applications where discrete decisions represent the final output. Future work is suggested to explore the architecture’s capacity for identifying global properties and complex interactions, as well as extending the E-PLL loss to accommodate a broader range of NP-complete problems through enhanced modeling languages. Overall, this research contributes significantly to the field of hybrid neural-symbolic systems, with implications for various applications in optimization and reasoning.
Introduction
The introduction of the paper discusses the emergence of hybrid neural architectures that integrate discrete reasoning and optimization within neural networks, driven by the need to address uncertainty in decision-making. This has led to the development of Decision-Focused Learning (DFL), which aims to leverage available data to produce high-quality solutions for complex discrete structured objects, such as sequences, trees, and graphs. The authors highlight the limitations of large language models in logical reasoning, positioning neurosymbolic systems as a promising alternative in the pursuit of artificial general intelligence (AGI).
The paper specifically focuses on structured output prediction (SOP), where the goal is to predict optimal solutions for combinatorial optimization (CO) problems with unknown objective functions and constraints. The authors outline the challenges posed by the discrete nature of variables, which complicates gradient-based learning and increases computational demands during training. To address these challenges, they propose a neurosymbolic architecture that combines deep learning layers with a discrete NP-hard Graphical Model (GM) reasoning layer, introducing a new loss function, the Emmental Pseudo-LogLikelihood (E-PLL), which effectively learns constraints from natural inputs. The architecture demonstrates high accuracy in solving complex problems, such as Visual Sudoku and protein design instances, showcasing its scalability and applicability in various contexts.
Methods
In this section, the authors outline their experimental methodology for training models to solve Sudoku puzzles, focusing on varying levels of grid difficulty. They utilize the RRN dataset, which comprises single-solution Sudoku grids with 17 to 34 hints, to establish a baseline for training and validation. Specifically, they train on 100 grids and validate on 32 grids, while testing on a set of 1,000 challenging 17-hint instances. Additionally, they incorporate the newly developed Sudoku-Extreme dataset, which categorizes grids based on the number of backtracks required by a solver, augmenting their training set to 1,000 grids through a specific augmentation procedure.
Furthermore, the authors explore a benchmark from Nandwani et al. (2021) that includes grids with multiple solutions. In this scenario, only a subset of solutions (up to 5) is accessible during training, with the goal of predicting any feasible solution. The training, validation, and testing sets consist of 100, 32, and 256 grids, respectively, with one of the available solutions randomly selected during training. This approach aims to enhance the model’s ability to generalize across different Sudoku configurations and solution sets.
Results
In the results section, the authors evaluate the performance of their proposed E-PLL loss function in solving Sudoku puzzles compared to traditional NPLL loss. The initial training with NPLL resulted in the network learning only a limited subset of rules, leading to ineffective inference on the test set. In contrast, using E-PLL with a hyperparameter $k=10$—which disregards messages from $k$ randomly chosen variables—achieved 100% accuracy on hard test grids, demonstrating significant improvements in both training efficiency (taking only 2 minutes on a single CPU) and solution reliability.
The authors also present a comparative analysis of their method against various existing approaches, including pure deep learning models and hybrid methods. While other models, such as Recurrent Relational Networks and Denoising Diffusion Probabilistic Models, require extensive data and struggle with harder puzzles, the E-PLL method excels in data efficiency and accuracy, achieving perfect reliability with minimal training time. The findings highlight the advantages of the E-PLL approach, particularly in its ability to solve Sudoku puzzles effectively while maintaining low computational demands compared to other methodologies.
Discussion
In this section, the authors discuss the relationship between their work and existing approaches in inverse optimization, constraint acquisition, and decision-focused learning (DFL). They highlight that classical inverse optimization methods rely on exact solutions to identify unknown parameters, while their approach leverages observable features, such as Sudoku images, to learn constraints and objectives. They differentiate their method from existing techniques that focus on continuous optimization problems, emphasizing their ability to handle arbitrary pairwise finite domain constraints, unlike previous works that are limited to specific forms of cardinality constraints.
The authors introduce the Emmental Pseudo-Log-Likelihood (E-PLL) as a novel loss function designed to address the limitations of the traditional Negative Pseudo-Log-Likelihood (NPLL) in learning constraints from observed data. The E-PLL incorporates a random masking strategy to mitigate the impact of redundant constraints on gradient updates, thereby enhancing the learning process. They also discuss the challenges posed by unobserved variables in their model, particularly in the context of visual Sudoku, and propose an imputation procedure to optimize the joint function defined by their graphical model. The section concludes by outlining the versatility of their architecture, which has been tested on various learning tasks, including symbolic and visual puzzles, demonstrating its effectiveness in learning constraints and objectives in NP-hard problems.