A Rule-Based Approach to Specifying Preferences over Conflicting Facts and Querying Inconsistent Knowledge Bases

ملخص تقني: نهج قائم على القواعد لتحديد التفضيلات فوق الحقائق المتعارضة والاستعلام من قواعد المعرفة غير المتسقة

بيان المشكلة

تعد الدلالات المتحملة لعدم الاتساق، ولا سيما تلك القائمة على إصلاحات المجموعات الجزئية (subset repairs)، نهجاً قياسياً للاستعلام من قواعد المعالجة (KBs) التي تنتهك القيود. وبينما توجد أطر عمل لتحديد "الإصلاحات المثلى" باستخدام علاقة أولوية بين الحقائق المتعارضة (مثل إطار قواعد البيانات ذات الأولوية لـ Staworko وآخرون)، تظل هناك فجوة حرجة وهي: كيفية تحديد علاقة الأولوية نفسها بشكل مريح.

تفترض الأدبيات الحالية أن علاقة الأولوية معطاة مسبقاً، ولكن من غير الواقعي توقع أن يقوم المستخدمون بإدخال علاقة ثنائية يدوياً بين جميع الحقائق المتعارضة. علاوة على وجود قواعد يحاول المستخدمون من خلالها تحديد التفضيلات، قد تؤدي هذه القواعد إلى حدوث دورات (على سبيل المثال، الحقيقة A مفضلة على B، وB مفضلة على C، وC مفضلة على A)، مما يجعل العلاقة غير صالحة لأن علاقات الأولوية يجب أن تكون غير دورية. تعالج الورقة تحدي تحديد هذه التفضيلات بشكل تصريفي وحل الدورات الناتجة لتمكين الاستعلام العملي من قواعد المعرفة غير المتسقة.

المنهجية

1. تحديد التفضيلات القائم على القواعد

يقدم المؤلفون إطار عمل تصريفي حيث تُشتق علاقات الأولوية من قواعد تفضيل يتم تقييمها عبر مجموعة بيانات $D$ وقاعدة بيانات ميتا (meta-database) $M$.

• قاعدة بيانات الميتا: مجموعة بيانات $F$ تحتوي على بيانات وصفية (مثل التواريخ أو موثوقية المصدر) مرتبطة بالحقائق في $D$ عبر معرفات فريدة.
• قواعد التفضيل: قواعد من الشكل $Cond(x_1, x_2) \to pref(x_1, x_2)$، حيث يمكن لمتن الشرط $Cond$ أن يشير إلى:
  • وجود أو غياب حقائق في $D$.
  • بيانات الميتا في $F$ (مثل مقارنة التواريخ أو درجات الموثوقية).
  • بديهيات الأنطولوجيا (مثل علاقات الفئات الفرعية).
  • النفي واللامساواة.
• العلاقة المستحثة: تستحث القاعدة تفضيلاً $pref(id(\alpha), id(\beta))$ إذا تحقق الشرط. وتتشكل علاقة الأولوية الفعلية $\succ_{\Sigma, K, M}$ عن طريق تصفية هذه التفضيلات المستحثة لتشمل فقط الأزواج $(\alpha, \beta)$ التي تظهر معاً في تعارض.

2. التعامل مع الدورات

بما أن العلاقات المستحثة قد تحتوي على دورات، تقترح الورقة استراتيجيتين متكاملتين:

• التحقق الساكن من عدم وجود دورات (Static Acyclicity Checking): التحقق مما إذا كانت مجموعة من القواعد تضمن إنتاج علاقة غير دورية لأي مجموعة بيانات.
  • تثبت الورقة أن التحقق من عدم وجود دورات في لغة $PL_{DL}$ العامة هو أمر غير قابل للتقرير (undecidable).
  • ومع ذلك، بالنسبة للغة مقيدة $PL_{pos}$ (القواعد الإيجابية بدون عناصر أنطولوجيا أو نفي) وقيود الإنكار الثنائية، فإن المشكلة قابلة للتقرير في فئة coNP.
  • تم تقديم مفهوم عدم وجود الدورات القوي (strong acyclicity): مجموعة القواعد تكون قوية في عدم وجود الدورات إذا كانت العلاقة المستحثة غير دورية لأي قاعدة بيانات وميتا، بغض النظر عن التعارضات.
• حل الدورات العملي (Pragmatic Cycle Resolution): عندما لا تضمن القواعد عدم وجود دورات، يسمح النظام للمستخدمين بتقسيم القواعد إلى مستويات أولوية ($\Sigma_1, \dots, \Sigma_n$)، حيث تشير المؤشرات الأدنى إلى أولوية أعلى. تم تعريف أربع استراتيجيات لاستخراج علاقة فرعية غير دورية:
  1. الصعود للأعلى ($\succ_u$): إضافة المستويات بشكل تكراري بدءاً من أدنى مؤشر (الأولوية الأعلى، $\Sigma_1$)، والتوقف إذا كان إضافة المستوى التالي سيؤدي إلى دورة.
  2. النزول للأسفل ($\succ_d$): البدء باتحاد جميع المستويات وإزالة الأزواج تكرارياً من مستويات المؤشر الأعلى (الأولوية الأدنى) التي تشارك في دورات حتى يتم تحقيق عدم وجود الدورات.
  3. الصعود المحسن ($\succ_{ru}$): نسخة متغيرة تقوم بإزالة الدورات داخل المستوى الواحد قبل إضافة المستوى التالي.
  4. المستند إلى الأرضية ($\succ_g$): نهج نقطة ثابتة مستوحى من الامتدادات الأرضية في أطر الحجاج (argumentation frameworks).
  • توضح الورقة العلاقات النظرية بين هذه الاستراتيجيات (على سبيل المثال، $\succ_u \subseteq \succ_d \subseteq \succ_g$) وتربطها بمفاهيم معروفة مثل الإصلاحات الاحتمالية (possibilistic repairs) والإصلاحات غير المهزومة (non-defeated repairs).

3. التنفيذ

قام المؤلفون بتنفيذ نظام متكامل باستخدام البرمجة المنطقية لتعيين المجموعات (Answer Set Programming - ASP):

• ترميز المدخلات: تقوم البرامج المنطقية بترميز مجموعة البيانات، وقاعدة بيانات الميتا، والقيود، والاستعلامات، وقواعد التفضيل.
• حساب التعارض والسبب (Conflict & Cause Computation): يقوم النظام بحساب التعارضات والأسباب (المجموعات الفرعية غير المتسقة الدنيا) باستخدام ASP. ومن الجدير بالذكر أن هذا التنفيذ يتعامل مع التعارضات غير الثنائية (تعارضات ذات أحجام عشوائية)، بينما تقتصر العديد من الأدوات الحالية على التعارضات الثنائية.
• حساب الأولوية: يتم ترميز استراتيجيات حل الدورات كبرامج ASP لاشتقاق علاقة الأولوية النهائية.
• الإجابة على الاستعلامات: يقيم النظام الاستعلامات تحت دلالات مختلفة (Brave, AR, IAR) مدمجة مع أنواع الإصلاح (Subset, Pareto-optimal, Completion-optimal).

النتائج الرئيسية

المساهمات النظرية

• عدم قابلية التقرير (Undecidability): ثبت أن التحقق مما إذا كانت مجموعة عامة من قواعد التفضيل تنتج علاقة غير دورية هو أمر غير قابل للتقرير.
• قابلية التقرير (Decidability): ثبت أن التحقق من عدم وجود دورات للقواعد الإيجابية بدون عناصر أنطولوجيا ($PL_{pos}$) وقيود الإنكار الثنائية هو أمر قابل للتقرير في فئة coNP.
• تكافؤ الاستراتيجيات: أثبتت الورقة أن استراتيجيات حل الدورات المقترحة تتوافق مع مفاهيم الإصلاح المعروفة في الأدبيات (مثل Possibilistic, Non-defeated, Grounded) عند ربطها بهيكل محدد لقاعدة المعرفة.

التقييم التجريبي

تم تقييم النظام باستخدام معيار CQAPri (قواعد بيانات DL-Lite اصطناعية) بأحجام متغيرة (تصل إلى ~2 مليون حقيقة) وكثافات تعارض متفاوتة.

• أداء حل الدورات:
  • وُجد أن استراتيجية النزول للأسفل ($\succ_d$) أسرع بكثير في الحساب من $\succ_g$ و $\succ_u$ في معظم السيناريوهات، مع إنتاج نتائج متشابهة غالباً (تتطابق في كثير من الحالات).
  • تسببت استراتيجية الصعود المحسن ($\succ_{ru}$) في تجاوز سعة الذاكرة حتى في مجموعات البيانات الصغيرة بسبب تعقيد ترميز ASP.
  • نجح النظام في حساب علاقات الأولوية لمجموعات بيانات ذات نسب تعارض عالية (تصل إلى 46%) وأعداد كبيرة من حقائق التفضيل.
• أداء الإجابة على الاستعلامات:
  • كان النظام القائم على ASP أبطأ عموماً من أداة ORBITS القائمة على SAT (بأضعاف مضاعفة في مجموعات البيانات الكبيرة) لحساب الإجابات تحت دلالات الإصلاح الأمثل.
  • ومع ذلك، نجح نظام ASP في الإجابة على الاستعلامات تحت دلالات C-AR و C-brave في الحالات التي فشلت فيها ORATS (بسبب انتهاء الوقت أو تجاوز الذاكرة).
  • يعد هذا النظام الأول الذي ينفذ دلالات الإصلاح الأمثل للتعارضات غير الثنائية.

الأهمية والادعاءات

تدعي الورقة أنها تقدم أول إطار عمل تصريفي قائم على القواعد لتحديد علاقات الأولوية في قواعد المعرفة غير المتسقة، مما يعالج فجوة أعاقت الاعتماد العملي لآليات الإصلاح ذات الأولوية.

• المرونة: من خلال السماح للقواعد بالإشارة إلى بيانات الميتا وأنطولوجيا، يوفر الإطار طريقة مرنة لتحديد سياسات إدارة عدم الاتساق دون الحاجة لإدخال علاقة ثنائية يدوياً.
• إدارة الدورات: تقدم الورقة حلاً عملياً لمشكلة الدورات، حيث توفر استراتيجيات متعددة للحل وضمانات نظرية لفئات محددة من القواعد.
• التنفيذ: يوضح التنفيذ جدوى استخدام ASP لهذه المهمة، خاصة قدرته على التعامل مع التعارضات غير الثنائية، وهي ميزة تفتقر إليها الأدوات الحديثة مثل ORBITS.
• التواضع: يقر المؤلفون بأنه بينما يعتبر تنفيذ ASP الخاص بهم أقل كفاءة من النهج القائم على SAT للتعارضات الثنائية، إلا أنه يوفر قدرة تعبيرية أكبر (التعامل مع أحجام تعارض عشوائية) ووحدوية أكبر (سهولة التوسع في حسابات الإصلاح الأخرى). هم لا يدعون التفوق على SAT في السرعة الخام، بل يسلطون الضال الضوء على القدرات الفريدة لمنهجهم.

تختتم الورقة بتحديد الاتجاهات المستقبلية، بما في ذلك توسيع التحليل الساكن ليشمل فئات نظرية أوسع، والتحقيق في تفرد الإصلاحات المثلى، وبناء خط إنتاج مؤتمت بالكامل لتوليد البرامج المنطقية من تنسيقات البيانات القياسية.