شجرة تشاو ليو

في نظرية الاحتمالات والإحصاء، تُعد شجرة تشاو-ليو طريقة فعّالة لبناء تقريب حاصل من الدرجة الثانية لتوزيع احتمالي مشترك ، وقد تم وصفها لأول مرة في ورقة بحثية كتبها تشاو وليو (1968). قد تكون أهداف مثل هذا التحليل، كما هو الحال مع مثل هذه الشبكات البايزية بشكل عام، إما ضغط البيانات أو الاستدلال .

تصف طريقة تشاو ليو توزيع الاحتمالات المشترك على أنه حاصل ضرب التوزيعات الشرطية والهامشية من الدرجة الثانية. على سبيل المثال، يمكن تقريب التوزيع ذي الأبعاد الستة على النحو التالي: ${\displaystyle P(X_{1},X_{2},\ldots ,X_{n})}$${\displaystyle P(X_{1},X_{2},X_{3},X_{4},X_{5},X_{6})}$

${\displaystyle P^{\prime }(X_{1},X_{2},X_{3},X_{4},X_{5},X_{6})=P(X_{6}|X_{5})P(X_{5}|X_{2})P(X_{4}|X_{2})P(X_{3}|X_{2})P(X_{2}|X_{1})P(X_{1})}$

حيث يقدم كل مصطلح جديد في المنتج متغيرًا جديدًا واحدًا فقط، ويمكن تمثيل المنتج كشجرة تبعية من الدرجة الأولى، كما هو موضح في الشكل. تحدد خوارزمية تشاو ليو (أدناه) الاحتمالات الشرطية التي يجب استخدامها في تقريب المنتج. ^[1] بشكل عام، ما لم تكن هناك تفاعلات من الدرجة الثالثة أو من الدرجة الأعلى، فإن تقريب تشاو ليو هو في الواقع تقريب ، ولا يمكنه التقاط البنية الكاملة للتوزيع الأصلي. يقدم بيرل (1988) تحليلًا حديثًا لشجرة تشاو ليو كشبكة بايزية .

يوضح تشاو وليو كيفية اختيار مصطلحات من الدرجة الثانية لتقريب المنتج بحيث يكون التقريب المبني، من بين كل هذه التقريبات من الدرجة الثانية (أشجار التبعية من الدرجة الأولى)، له الحد الأدنى من تباعد كولباك-ليبلر للتوزيع الفعلي ، وبالتالي فهو أقرب تقريب بالمعنى الكلاسيكي لنظرية المعلومات . يُظهِر تباعد كولباك-ليبلر بين تقريب منتج من الدرجة الثانية والتوزيع الفعلي أنه ${\displaystyle P^{\prime }}$${\displaystyle P}$

${\displaystyle D(P\parallel P^{\prime })=-\مجموع I(X_{i};X_{j(i)})+\مجموع H(X_{i})-H(X_{1},X_{2},\ldots ,X_{n})}$

حيث هي المعلومات المتبادلة بين المتغير ووالده و هي الإنتروبيا المشتركة لمجموعة المتغيرات . ونظرًا لأن المصطلحين و مستقلان عن ترتيب التبعية في الشجرة، فإن مجموع المعلومات المتبادلة الزوجية فقط ، ، يحدد جودة التقريب. وبالتالي، إذا تم إعطاء كل فرع (حافة) في الشجرة وزنًا يتوافق مع المعلومات المتبادلة بين المتغيرات عند رؤوسها، فإن الشجرة التي توفر التقريب الأمثل من الدرجة الثانية للتوزيع المستهدف هي مجرد شجرة ذات أقصى وزن . تسلط المعادلة أعلاه الضوء أيضًا على دور التبعيات في التقريب: عندما لا توجد تبعيات، ويكون المصطلح الأول في المعادلة غائبًا، يكون لدينا تقريب يعتمد فقط على الهوامش من الدرجة الأولى، والمسافة بين التقريب والتوزيع الحقيقي ترجع إلى التكرارات التي لا يتم أخذها في الاعتبار عند التعامل مع المتغيرات على أنها مستقلة. عندما نحدد التبعيات من الدرجة الثانية، نبدأ في التقاط بعض هذا الهيكل وتقليل المسافة بين التوزيعين. ${\displaystyle I(X_{i};X_{j(i)})}$${\displaystyle X_{i}}$${\displaystyle X_{j(i)}}$${\displaystyle H(X_{1},X_{2},\ldots ,X_{n})}$${\displaystyle \{X_{1},X_{2},\ldots ,X_{n}\}}$${\displaystyle \sum H(X_{i})}$${\displaystyle H(X_{1},X_{2},\ldots ,X_{n})}$${\displaystyle \مجموع I(X_{i};X_{j(i)})}$

يقدم تشاو وليو خوارزمية بسيطة لبناء الشجرة المثلى؛ في كل مرحلة من مراحل الإجراء، تضيف الخوارزمية ببساطة زوج المعلومات المتبادلة الأقصى إلى الشجرة. راجع الورقة الأصلية، تشاو وليو (1968)، للحصول على التفاصيل الكاملة. تم توضيح خوارزمية بناء شجرة أكثر كفاءة للحالة الشائعة للبيانات المتفرقة في ميلا (1999).

أثبت تشاو وفاجنر في ورقة بحثية لاحقة بعنوان تشاو وفاجنر (1973) أن تعلم شجرة تشاو-ليو متسق مع العينات (أو الملاحظات) المرسومة بشكل مستقل من توزيع مبني على شجرة. بعبارة أخرى، يتناقص احتمال تعلم شجرة غير صحيحة إلى الصفر مع ميل عدد العينات إلى اللانهاية. الفكرة الرئيسية في الإثبات هي استمرارية المعلومات المتبادلة في التوزيع الهامشي الثنائي. وفي الآونة الأخيرة، تم تقديم معدل التقارب الأسي لاحتمال الخطأ. ^[2]

إن المشكلة الواضحة التي تحدث عندما لا يكون التوزيع الفعلي في الواقع شجرة تبعية من الدرجة الثانية يمكن معالجتها في بعض الحالات عن طريق دمج أو تجميع مجموعات فرعية من المتغيرات المتصلة بكثافة للحصول على شجرة "عقدة كبيرة" من نوع Chow–Liu (هوانج، كينج وليو 2002)، أو عن طريق توسيع فكرة اختيار أقصى وزن فرع جشع إلى هياكل غير شجرة (متعددة الوالدين) (ويليامسون 2000). (تعتبر التقنيات المماثلة لاستبدال المتغيرات وإنشائها شائعة في أدبيات شبكة بايز ، على سبيل المثال، للتعامل مع الحلقات. انظر بيرل (1988).)

التعميمات لشجرة تشاو-ليو هي ما يسمى بأشجار تقاطع الكرز-t. وقد ثبت أن أشجار تقاطع الكرز-t توفر تقريبًا أفضل أو على الأقل جيدًا لتوزيع الاحتمالات المتعدد المتغيرات المنفصل مثل ما توفره شجرة تشاو-ليو. بالنسبة لشجرة تقاطع الكرز-t من الدرجة الثالثة، انظر (Kovács & Szántai 2010)، وبالنسبة لشجرة تقاطع الكرز-t من الدرجة k ، انظر (Szántai & Kovács 2010). شجرة تقاطع الكرز-t من الدرجة الثانية هي في الواقع شجرة تشاو-ليو.

• الشبكة البايزية
• تمثيل المعرفة