Chow–Liu tree
امکانات کے نظریہ اور اعداد و شمار میں چو-لیو ٹری مشترکہ امکانات کی تقسیم کے دوسرے درجے کے پروڈکٹ کے تخمینے کی تعمیر کے لیے ایک موثر طریقہ ہے، جسے سب سے پہلے ایک کاغذ میں بیان کیا گیا ہے۔ اس طرح کے سڑنے کے اہداف، جیسا کہ عام طور پر اس طرح کے بایسیئن نیٹ ورکس کے ساتھ، ڈیٹا کمپریشن یا تخمینہ ہو سکتے ہیں۔ چو-لیو کی نمائندگی چو-لیو طریقہ مشترکہ امکان کی تقسیم کو دوسرے درجے کی مشروط اور معمولی تقسیم کی پیداوار کے طور پر بیان کرتا ہے۔ مثال کے طور پر، چھ جہتی تقسیم کا تخمینہ لگایا جا سکتا ہے جہاں پروڈکٹ میں ہر نئی اصطلاح صرف ایک نیا متغیر متعارف کراتی ہے، اور پروڈکٹ کو پہلے درجے کے انحصار کے درخت کے طور پر پیش کیا جا سکتا ہے، جیسا کہ شکل میں دکھایا گیا ہے۔ چو-لیو الگورتھم (نیچے) اس بات کا تعین کرتا ہے کہ پروڈکٹ کے تخمینے میں کون سے مشروط امکانات استعمال کیے جائیں گے۔ عام طور پر، جب تک کہ کوئی تیسرا آرڈر یا اعلی آرڈر تعاملات نہ ہوں، چو-لیو کا تخمینہ درحقیقت ایک تخمینہ ہے، اور اصل تقسیم کے مکمل ڈھانچے پر قبضہ نہیں کر سکتا۔ بیسیئن نیٹ ورک کے طور پر چو-لیو درخت کا جدید تجزیہ فراہم کرتا ہے۔ چو-لیو الگورتھم چو اور لیو دکھاتے ہیں کہ پروڈکٹ کے تخمینے کے لیے دوسرے درجے کی اصطلاحات کا انتخاب کیسے کیا جائے تاکہ، اس طرح کے تمام دوسرے درجے کے تخمینوں (پہلے درجے کے انحصار کے درختوں) میں، تعمیر شدہ تخمینے میں اصل تقسیم کے لیے کم از کم کل بیک-لیبلر انحراف ہو، اور اس طرح کلاسیکی معلومات-نظریاتی معنوں میں یہ قریب ترین تخمینہ ہے۔ دوسرے درجے کے پروڈکٹ کے تخمینے اور اصل تقسیم کے درمیان کل بیک-لیبلر انحراف یہ دکھایا گیا ہے کہ متغیر اور اس کے والدین کے درمیان باہمی معلومات کہاں ہے اور متغیر سیٹ کی مشترکہ اینٹروپی ہے۔ چونکہ شرائط اور ٹری میں انحصار کی ترتیب سے آزاد ہیں، صرف جوڑی کے لحاظ سے باہمی معلومات کا مجموعہ، تخمینہ کے معیار کا تعین کرتا ہے۔ اس طرح، اگر درخت کی ہر شاخ (کنارے) کو اس کے چوٹیوں پر متغیرات کے درمیان باہمی معلومات کے مطابق وزن دیا جاتا ہے، تو وہ درخت جو ہدف کی تقسیم کو زیادہ سے زیادہ دوسرے درجے کا تخمینہ فراہم کرتا ہے وہ صرف زیادہ سے زیادہ وزن والا درخت ہے۔ مندرجہ بالا مساوات تخمینہ میں انحصار کے کردار کو بھی اجاگر کرتی ہے: جب کوئی انحصار موجود نہیں ہوتا ہے، اور مساوات میں پہلی اصطلاح موجود نہیں ہوتی ہے، تو ہمارے پاس صرف فرسٹ آرڈر مارجنلز کی بنیاد پر ایک تخمینہ ہوتا ہے، اور تخمینہ اور حقیقی تقسیم کے درمیان کا فاصلہ ان بے کاریوں کی وجہ سے ہوتا ہے جن کا حساب اس وقت نہیں لیا جاتا جب متغیرات کو آزاد سمجھا جاتا ہے۔ جیسا کہ ہم دوسرے درجے کے انحصار کی وضاحت کرتے ہیں، ہم اس ڈھانچے میں سے کچھ پر قبضہ کرنا شروع کرتے ہیں اور دونوں تقسیم کے درمیان فاصلے کو کم کرتے ہیں۔ چو اور لیو بہترین درخت کی تعمیر کے لیے ایک آسان الگورتھم فراہم کرتے ہیں۔ طریقہ کار کے ہر مرحلے پر الگورتھم صرف درخت میں زیادہ سے زیادہ باہمی معلومات کا جوڑا شامل کرتا ہے۔ مکمل تفصیلات کے لیے اصل کاغذ دیکھیں۔ شاذ و نادر ڈیٹا کے عام معاملے کے لیے ایک زیادہ موثر ٹری کنسٹرکشن الگورتھم کا خاکہ پیش کیا گیا تھا۔ چو اور ویگنر نے بعد کے ایک مقالے میں ثابت کیا کہ چاؤ-لیو درخت کا سیکھنا مستقل ہے جو نمونے (یا مشاہدات) دیے گئے ہیں یعنی ڈی۔ درخت کی ساخت کی تقسیم سے۔ دوسرے لفظوں میں، کسی غلط درخت کو سیکھنے کا امکان صفر ہو جاتا ہے کیونکہ نمونوں کی تعداد لامحدود ہو جاتی ہے۔ ثبوت میں بنیادی خیال جوڑی کے لحاظ سے حاشیہ تقسیم میں باہمی معلومات کا تسلسل ہے۔ حال ہی میں، غلطی کے امکان کے ارتکاز کی تیز رفتار شرح فراہم کی گئی تھی۔ چو-لیو درختوں پر تغیرات واضح مسئلہ جو اس وقت پیدا ہوتا ہے جب اصل تقسیم حقیقت میں دوسرے درجے کا انحصار درخت نہیں ہوتا ہے پھر بھی کچھ معاملات میں "بڑے نوڈ" چو-لیو درخت حاصل کرنے کے لیے متغیرات کے گھنے جڑے ہوئے ذیلی سیٹوں کو ملا کر یا جمع کر کے، یا لالچی زیادہ سے زیادہ شاخ کے وزن کے انتخاب کے خیال کو غیر درخت (متعدد والدین) ڈھانچوں تک بڑھا کر حل کیا جا سکتا ہے۔ (متغیر متبادل اور تعمیر کی اسی طرح کی تکنیکیں بیس نیٹ ورک لٹریچر میں عام ہیں، مثال کے طور پر، لوپس سے نمٹنے کے لیے۔ دیکھیں۔) چو-لیو درخت کی عمومی شکلیں نام نہاد ٹی-چیری جنکشن درخت ہیں۔ یہ ثابت ہوتا ہے کہ ٹی-چیری جنکشن کے درخت ایک مجرد کثیر الجہتی امکانات کی تقسیم کے لیے بہتر یا کم از کم اتنا ہی اچھا تخمینہ فراہم کرتے ہیں جیسا کہ چو-لیو درخت دیتا ہے۔ تھرڈ آرڈر ٹی-چیری جنکشن ٹری کے لیے دیکھیں، kth-آرڈر ٹی-چیری جنکشن ٹری کے لیے دیکھیں۔ سیکنڈ آرڈر ٹی-چیری جنکشن ٹری درحقیقت چو-لیو ٹری ہے۔ بایسیئن نیٹ ورک نالج ریپریزنٹیشن نوٹس حوالہ جات بھی دیکھیں۔ ۔ ۔ ۔ ۔ ۔ ۔ علم کی نمائندگی