Syntactic parsing (computational linguistics)
نحو تجزیہ قدرتی زبان کی نحو ساخت کا خودکار تجزیہ ہے، خاص طور پر نحو تعلقات (انحصار گرائمر میں) اور اجزاء کے لیبلنگ اسپینس (انتخابی حلقے کے گرائمر میں)۔ یہ قدرتی زبان میں ساختی ابہام کے مسئلے سے متاثر ہوتا ہے: ایک جملے کو متعدد گراماتی تجزیہ تفویض کیے جا سکتے ہیں، لہذا کمپیوٹیشنل گرامر کے اصولوں سے بالاتر کسی قسم کے علم کو یہ بتانے کی ضرورت ہے کہ کس تجزیہ کا ارادہ ہے۔ نحو تجزیہ کمپیوٹیشنل لسانیات اور قدرتی زبان کی پروسیسنگ میں اہم کاموں میں سے ایک ہے، اور کمپیوٹر کی آمد کے ساتھ 20 ویں صدی کے وسط سے تحقیق کا موضوع رہا ہے۔ گرائمر کے مختلف نظریات جملوں کی نحو ساخت کو بیان کرنے کے لیے مختلف رسم و رواج پیش کرتے ہیں۔ کمپیوٹیشنل مقاصد کے لیے، ان رسمی طریقوں کو انتخابی حلقے کے گرامر اور انحصار کے گرامر کے تحت گروپ کیا جا سکتا ہے۔ کسی بھی کلاس کے لیے پارسرز مختلف قسم کے الگورتھم کا مطالبہ کرتے ہیں، اور دونوں مسائل کے نقطہ نظر نے مختلف شکلیں اختیار کی ہیں۔ مختلف رسمی طریقوں کا استعمال کرتے ہوئے انسانی اشارہ شدہ درختوں کے کناروں کی تخلیق (جیسے۔ یونیورسل ڈیپینڈینسیاں) تجزیہ کے لیے نئے الگورتھم اور طریقوں کی ترقی کے ساتھ ساتھ آگے بڑھی ہیں۔ پارٹ آف اسپیچ ٹیگنگ (جو کچھ بامعنی ابہام کو حل کرتی ہے) ایک متعلقہ مسئلہ ہے، اور اکثر نحو تجزیہ کے لیے ایک شرط یا ذیلی مسئلہ ہے۔ نحو تجزیہ کو معلومات نکالنے کے لیے استعمال کیا جا سکتا ہے (مثال کے طور پر۔ ایونٹ پارسنگ، سیمنٹک رول لیبلنگ، اینٹیٹی لیبلنگ) اور رسمی سیمنٹک نمائشیں نکالنے کے لیے مزید استعمال کیا جا سکتا ہے۔ انتخابی حلقے کی تجزیہ تجزیہ میں انتخابی حلقے کے گرائمر کی رسمی کارروائیوں کے مطابق تجزیہ کرنا شامل ہے، جیسے کہ کم از کم یا پین ٹری بینک کی رسمی حیثیت۔ اس کا، کم از کم، مطلب یہ بتانا ہے کہ کون سے اسپانس اجزاء ہیں (جیسے۔ [آدمی] یہاں ہے۔] اور یہ کس قسم کا جزو ہے (جیسے۔ [آدمی] ایک اسم فقرہ ہے) جو سیاق و سباق سے پاک گرائمر (سی ایف جی) کی بنیاد پر ہے جو اجزاء کی تشکیل اور انضمام کے اصولوں کو انکوڈ کرتا ہے۔ الگورتھم کے لیے عام طور پر سی ایف جی کو چومسکی نارمل فارم (فی جزو دو بچوں کے ساتھ) میں تبدیل کرنے کی ضرورت ہوتی ہے، جو کہ 1979 میں ہاپکرافٹ اور المین کے ذریعے بیان کردہ الگورتھم کا استعمال کرتے ہوئے درخت کے بارے میں کوئی معلومات کھونے یا اظہار کو کم کیے بغیر کیا جا سکتا ہے۔ انتخابی حلقے کی تجزیہ کے لیے سب سے مشہور الگورتھم کاک-کسامی-ینگ الگورتھم (سی کے وائی) ہے، جو ایک متحرک پروگرامنگ الگورتھم ہے جو الفاظ کے جملے پر بدترین صورت میں تجزیہ بناتا ہے اور چومسکی نارمل فارم میں دیئے گئے سی ایف جی کے سائز کا ہوتا ہے۔ ابہام کے مسئلے کو دیکھتے ہوئے (مثال کے طور پر۔ انگریزی میں پریپوزیشن-اٹیچمنٹ ابہام) جس کی وجہ سے متعدد قابل قبول تجزیہ ہوتے ہیں، یہ ضروری ہے کہ تجزیہ کے امکانات کو اسکور کرنے کے قابل ہو تاکہ سب سے زیادہ ممکنہ تجزیہ کو منتخب کیا جا سکے۔ ایسا کرنے کا ایک طریقہ ممکنہ سیاق و سباق سے پاک گرائمر (پی سی ایف جی) کا استعمال کرنا ہے جس میں ہر حلقے کے اصول کا امکان ہوتا ہے، اور نیچے سے تجزیہ کرتے وقت امکانات کو زیادہ سے زیادہ کرنے کے لیے سی کے وائی میں ترمیم کرنا ہے۔ ایک اور ترمیم لیکسیکلائزڈ پی سی ایف جی ہے، جو ہر جزو کو ایک سر تفویض کرتا ہے اور اس ہیڈ سلاٹ میں ہر لیکسیم کے لیے اصول کو انکوڈ کرتا ہے۔ اس طرح، جہاں پی سی ایف جی میں ایک قاعدہ "این پی → ڈی ٹی این این" ہو سکتا ہے (ایک اسم فقرہ ایک تعین کنندہ اور اسم ہے) جبکہ لیکسیکلائزڈ پی سی ایف جی میں خاص طور پر "این پی (کتا) → ڈی ٹی این این (کتا)" یا "این پی (شخص)" وغیرہ جیسے اصول ہوں گے۔ عملی طور پر اس سے کارکردگی میں کچھ بہتری آتی ہے۔ مزید حالیہ کام سی کے وائی کو فیڈ کرنے کے لیے اسپان امکانات (جو (پی) سی ایف جی کے برعکس سیاق و سباق کو مدنظر رکھ سکتا ہے) کی نیورل اسکورنگ کرتا ہے، جیسے کہ ورڈ ایمبیڈنگ کے اوپر بار بار نیورل نیٹ ورک یا ٹرانسفارمر کا استعمال کرنا۔ 2022 میں، نکیتا کتایف اور دیگر۔ ایک انکریمنٹل پارسر متعارف کرایا گیا جو پہلے ہر ان پٹ ٹوکن کے لیے مجرد لیبل (ایک مقررہ الفاظ سے باہر) سیکھتا ہے جسے صرف بائیں ہاتھ کا سیاق و سباق دیا جاتا ہے، جو اس کے بعد سی کے وائی چارٹ پارسر کے لیے واحد ان پٹ ہوتے ہیں جن کا حساب سیکھے ہوئے نیورل اسپین اسکورر کا استعمال کرتے ہوئے کیا جاتا ہے۔ یہ نقطہ نظر نہ صرف لسانی طور پر حوصلہ افزائی کرتا ہے، بلکہ انتخابی حلقے کی تجزیہ کے پچھلے طریقوں کے ساتھ بھی مسابقتی ہے۔ ان کے کام نے اے سی ایل 2022 میں بہترین پیپر کا ایوارڈ جیتا۔ منتقلی پر مبنی انحصار کے گرائمرز کے لیے منتقلی پر مبنی تجزیہ کی کامیابی کے بعد، انتخابی حلقے کے تجزیہ کے نقطہ نظر کو اپنانے پر کام شروع ہوا۔ اس طرح کا پہلا کام 2005 میں کینجی ساگے اور ایلون لاوی کا تھا، جس نے لالچ سے منتقلی کے فیصلے کرنے کے لیے خصوصیت پر مبنی درجہ بندی پر انحصار کیا۔ اس کے بعد 2009 میں یو ژانگ اور اسٹیفن کلارک کا کام ہوا، جس نے عالمی سطح پر زیادہ سے زیادہ تجزیہ کرنے کے لیے ڈیکوڈر میں بیم سرچ کا اضافہ کیا۔ چارٹ پر مبنی تجزیہ کار کو پیچھے چھوڑنے والا اس خاندان کا پہلا تجزیہ کار موہوا زو اور دیگر کا تھا۔ 2013 میں، جس نے پیڈنگ آپریشن کو شامل کرکے یونیری انتخابی حلقے کے قوانین (انحصار تجزیہ کے لیے ایک غیر موجود مسئلہ) کی وجہ سے مختلف منتقلی کے سلسلے کی لمبائی کے فرق کے مسئلے کو اٹھایا۔ نوٹ کریں کہ منتقلی پر مبنی تجزیہ خالصتا لالچی ہو سکتا ہے (یعنی۔ درخت کی تعمیر کے ہر وقت کے مرحلے پر بہترین آپشن کا انتخاب کرنا، جو ممکنہ طور پر غیر بہترین یا غیر تشکیل شدہ درختوں کی طرف لے جاتا ہے) یا کارکردگی کو بڑھانے کے لیے بیم سرچ کا استعمال کریں جبکہ کارکردگی کی قربانی نہ دیں۔ سیکوینس ٹو سیکوینس حلقے کے تجزیہ کے لیے ایک مختلف نقطہ نظر جو عصبی ترتیب کے ماڈلز کا فائدہ اٹھاتا ہے، اوریول وینیلس اور دیگر نے تیار کیا تھا۔ 2015 میں۔ اس نقطہ نظر میں، جزو تجزیہ کو مشین ترجمہ کی طرح ماڈل کیا جاتا ہے: اصل کاغذ میں توجہ کے طریقہ کار کے ساتھ گہرے ایل ایس ٹی ایم کا استعمال کرتے ہوئے، کام جملے سے انتخابی حلقے کے تجزیہ میں ترتیب سے ترتیب میں تبدیلی ہے۔ گولڈ ٹریننگ ٹری کو اس قسم کے ماڈل کے لیے لکیریائز کرنا پڑتا ہے، لیکن تبدیلی سے کوئی معلومات ضائع نہیں ہوتی ہے۔ یہ 10 چوڑائی کے بیم سرچ ڈیکوڈر کے ساتھ چلتا ہے (لیکن انہیں زیادہ بیم سائز سے بہت کم فائدہ ہوا اور یہاں تک کہ اسے لالچی ڈیکوڈنگ تک محدود رکھنا بھی اچھی کارکردگی کا مظاہرہ کرتا ہے)، اور سی کے وائی جیسے سیاق و سباق سے پاک تجزیہ کے لیے روایتی الگورتھم کے ساتھ مسابقتی کارکردگی حاصل کرتا ہے۔ انحصار تجزیہ انحصار گرائمر فارملزم کے مطابق تجزیہ کیا جاتا ہے، جیسے کہ یونیورسل ڈیپینڈینسیاں (جو کہ ایک ایسا پروجیکٹ بھی ہے جو کثیر لسانی انحصار ٹری بینک تیار کرتا ہے)۔ اس کا مطلب ہے ایک سربراہ (یا کچھ رسمی طریقوں میں متعدد سربراہان تفویض کرنا جیسے بہتر انحصار، جیسے۔ ہم آہنگی کی صورت میں) ہر ٹوکن اور ہر کنارے کے لیے متعلقہ انحصار کا تعلق، بالآخر پورے جملے پر ایک درخت یا گراف بناتے ہیں۔ انحصار تجزیہ کی ماڈلنگ کے لیے وسیع پیمانے پر تین جدید مثالیں ہیں: منتقلی پر مبنی، گرائمر پر مبنی، اور گراف پر مبنی۔ ٹرانزیشن پر مبنی انحصار ٹری پارسنگ کے بہت سے جدید نقطہ نظر ٹرانزیشن پر مبنی پارسنگ کا استعمال کرتے ہیں (اس کی بنیادی شکل کو بعض اوقات آرک اسٹینڈرڈ کہا جاتا ہے) جیسا کہ 2003 میں جوکیم نیوری نے وضع کیا تھا، جو ٹوکن کے رننگ اسٹیک کو رکھ کر شفٹ کم پارسنگ پر پھیلا ہوا ہے، اور اگلے ٹوکن کے لیے تین کارروائیوں میں سے فیصلہ کرتا ہے: (موجودہ ٹوکن اسٹیک کے اوپری حصے کا بچہ ہے، اسٹیک میں شامل نہیں کیا گیا ہے) (موجودہ ٹوکن اسٹیک کے اوپری حصے کا والدین ہے، اوپر کی جگہ لے لیتا ہے) (اسٹیک میں موجودہ ٹوکن شامل کریں) الگورتھم کو اسٹیک کے اوپری دو ٹوکن (اسٹیک میں اگلا ٹوکن شامل کرنے کے بعد) کا موازنہ کرنے کے طور پر وضع کیا جا سکتا ہے۔ اس طرح کے الگورتھم کے لیے تربیتی ڈیٹا ایک اوریکل کا استعمال کرتے ہوئے بنایا جاتا ہے، جو سونے کے درختوں سے منتقلی کا ایک سلسلہ بناتا ہے جسے پھر درجہ بندی کرنے والے کو کھلایا جاتا ہے۔ درجہ بندی کرنے والا سیکھتا ہے کہ اسٹیک، بفر، اور موجودہ ٹوکن کی موجودہ حالت کو دیکھتے ہوئے تینوں میں سے کون سا آپریشن بہترین ہے۔ جدید طریقے ایک عصبی درجہ بندی کا استعمال کرتے ہیں جسے لفظ کے سرایت پر تربیت دی جاتی ہے، جس کا آغاز 2014 میں ڈینکی چن اور کرسٹوفر میننگ کے کام سے ہوتا ہے۔ ماضی میں، فیچر پر مبنی درجہ بندی بھی عام تھی، جس میں پارٹ آف اسپیچ ٹیگز، جملے کی پوزیشن، مورفولوجیکل معلومات وغیرہ سے منتخب کردہ خصوصیات تھیں۔ یہ ایک لالچی الگورتھم ہے، لہذا یہ بہترین ممکنہ تجزیہ یا یہاں تک کہ لازمی طور پر درست تجزیہ کی ضمانت نہیں دیتا ہے، لیکن یہ موثر ہے۔ یہ بھی ضروری نہیں ہے کہ کسی خاص درخت میں درست منتقلی کا صرف ایک سلسلہ ہو جو اس تک پہنچ سکے، لہذا ایک متحرک اوریکل (جو کارروائیوں کے متعدد انتخاب کی اجازت دے سکتا ہے) کارکردگی میں اضافہ کرے گا۔ اس میں ایک ترمیم آرک-ایجر پارسنگ ہے، جو ایک اور آپریشن کا اضافہ کرتی ہے: (اسٹیک پر موجود ٹاپ ٹوکن کو ہٹا دیں)۔ عملی طور پر، اس کے نتیجے میں پہلے آرک کی تشکیل ہوتی ہے۔ یہ سب اب تک صرف پروجیکٹو درختوں کی حمایت کرتے ہیں، جن کے کنارے جملے سے ٹوکن آرڈر کو دیکھتے ہوئے پار نہیں ہوتے ہیں۔ غیر پروجیکٹو درختوں کے لیے، 2009 میں نیور نے آپریشن کو شامل کرنے کے لیے آرک اسٹینڈرڈ ٹرانزیشن پر مبنی تجزیہ میں ترمیم کی (اسٹیک پر سب سے اوپر دو ٹوکن کو تبدیل کریں، یہ فرض کرتے ہوئے کہ فارمولیشن جہاں اگلا ٹوکن ہمیشہ پہلے اسٹیک میں شامل کیا جاتا ہے)۔ اس سے رن ٹائم بڑھ کر بدترین صورت میں لیکن عملی طور پر اب بھی قریب لکیری ہو جاتا ہے۔ گرامر پر مبنی پروجیکٹو انحصار تجزیہ کے لیے ایک چارٹ پر مبنی متحرک پروگرامنگ نقطہ نظر مائیکل کولنز نے 1996 میں تجویز کیا تھا اور اسی سال جیسن ایزنر نے اسے مزید بہتر بنایا۔ یہ سی کے وائی (پہلے انتخابی حلقے کی تجزیہ کے لیے مذکور) کی قیادت والے انحصار کے لیے موافقت ہے، ایک فائدہ یہ ہے کہ انتخابی حلقے کی تجزیہ سے واحد تبدیلی یہ ہے کہ ہر جزو کی سربراہی اس کے نسل نوڈس میں سے ایک کرتا ہے۔ اس طرح، کوئی بھی صرف اس بات کی وضاحت کر سکتا ہے کہ کون سا بچہ گرائمر میں ہر حلقے کے اصول کے لیے سربراہ فراہم کرتا ہے (مثال کے طور پر۔ حلقہ سی کے وائی تجزیہ سے انحصار سی کے وائی تجزیہ تک جانے کے لیے این پی کی سربراہی اس کا بچہ این کرتا ہے۔ میکڈونلڈ کی اصل موافقت کا رن ٹائم تھا، اور آئزنر کی متحرک پروگرامنگ کی اصلاح نے رن ٹائم کو کم کر دیا۔ آئزنر نے اپنے مقالے میں مدت کے امکانات کا حساب لگانے کے لیے تین مختلف اسکورنگ کے طریقے تجویز کیے۔ انحصار کے درخت میں ممکنہ کناروں کی گراف پر مبنی مکمل تلاش، غیر تشکیل شدہ درخت بننے کی صورت میں بیک ٹریکنگ کے ساتھ، گراف پر مبنی انحصار تجزیہ کے لیے بیس لائن رن ٹائم فراہم کرتی ہے۔ اس نقطہ نظر کو سب سے پہلے 2001 میں مائیکل اے کوونٹن نے باضابطہ طور پر بیان کیا تھا، لیکن انہوں نے دعوی کیا کہ یہ "ایک الگورتھم ہے جو 1960 کی دہائی سے کسی نہ کسی شکل میں جانا جاتا ہے"۔ تجزیہ کرنے کے مسئلے کو انحصار کے تمام ممکنہ کناروں کے گراف پر زیادہ سے زیادہ امکان کے پھیلاؤ کو تلاش کرنے اور پھر درخت کے کناروں کے لیے انحصار کے لیبل کو چننے کے طور پر بھی ماڈل کیا جا سکتا ہے۔ اس کے پیش نظر، ہم چو-لیو/ایڈمنڈز الگورتھم کی توسیع کو ایج اسکورر اور لیبل اسکورر کے ساتھ استعمال کر سکتے ہیں۔ اس الگورتھم کو سب سے پہلے 2005 میں ریان میکڈونلڈ، فرنینڈو پیریرا، کیرل رباروف اور جان حاجیچ نے بیان کیا تھا۔ یہ آرک اسٹینڈرڈ ٹرانزیشن بیسڈ پارسر اور سی کے وائی کے برعکس غیر پروجیکٹو درختوں کو سنبھال سکتا ہے۔ پہلے کی طرح، اسکور کرنے والے اعصابی (لفظ کے سرایت پر تربیت یافتہ) یا خصوصیت پر مبنی ہو سکتے ہیں۔ یہ ٹارجن کے الگورتھم کی توسیع کے ساتھ چلتا ہے۔ تشخیص نحو تجزیہ کاروں کی کارکردگی کو معیاری تشخیصی میٹرکس کا استعمال کرتے ہوئے ماپا جاتا ہے۔ انتخابی حلقے اور انحصار تجزیہ کے طریقوں دونوں کا اندازہ عین مطابق مماثلتوں کے تناسب (ان جملوں کا فیصد جو بالکل تجزیہ کیے گئے تھے)، اور درستگی، یاد، اور F1 اسکور کے حساب سے کیا جا سکتا ہے جو حوالہ اور/یا مفروضے کے تجزیہ میں اس تعداد کے مقابلے میں تجزیہ میں صحیح انتخابی حلقے یا انحصار تفویض کی بنیاد پر کیا جاتا ہے۔ مؤخر الذکر کو پارسل میٹرکس کے نام سے بھی جانا جاتا ہے۔ انحصار تجزیہ کا اندازہ منسلک اسکور کا استعمال کرتے ہوئے بھی کیا جا سکتا ہے۔ غیر لیبل شدہ منسلک اسکور (یو اے ایس) صحیح طور پر تفویض کردہ سروں والے ٹوکن کا فیصد ہے، جبکہ لیبل شدہ منسلک اسکور (ایل اے ایس) صحیح طور پر تفویض کردہ سروں اور انحصار سے متعلق لیبل والے ٹوکن کا فیصد ہے۔ یہ دیکھتے ہوئے کہ انگریزی نحو تجزیہ پر اتنا کام پین ٹری بینک پر منحصر تھا، جس نے انتخابی حلقے کی رسم الخط کا استعمال کیا، انحصار تجزیہ پر بہت سے کاموں نے پین رسم الخط کو تعیناتی طور پر انحصار نحو میں تبدیل کرنے کے طریقے تیار کیے، تاکہ اسے تربیتی ڈیٹا کے طور پر استعمال کیا جا سکے۔ تبادلوں کے بڑے الگورتھم میں سے ایک Penn2Malt تھا، جس نے اس مسئلے پر پچھلے کام کو دوبارہ نافذ کیا۔ انحصار سے تشکیل میں تبدیلی کی سمت میں کام کرنا انحصار تجزیہ الگورتھم کے تیز رن ٹائم سے فائدہ اٹھاتا ہے۔ ایک نقطہ نظر یہ ہے کہ محدود سی کے وائی تجزیہ کا استعمال کیا جاتا ہے، ان اسپان کو نظر انداز کیا جاتا ہے جو واضح طور پر انحصار تجزیہ کے ڈھانچے کی خلاف ورزی کرتے ہیں اور اس طرح رن ٹائم کو کم کر دیتے ہیں۔ ایک اور طریقہ یہ ہے کہ درجہ بندی کرنے والے کو تربیت دی جائے کہ وہ ہر ٹوکن کے تمام انحصار کرنے والوں کے لیے ایک ترتیب تلاش کرے، جس کے نتیجے میں انتخابی حلقے کے پارس کے لیے ایک ڈھانچہ آئسومورفک ہوتا ہے۔ مزید پڑھنے کے حوالے انحصار تجزیہ قدرتی زبان تجزیہ قدرتی زبان پروسیسنگ