البحث عن برامج ديناميكية أكثر كفاءة

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

Computational models of human language often involve combinatorial problems. For instance, a probabilistic parser may marginalize over exponentially many trees to make predictions. Algorithms for such problems often employ dynamic programming and are not always unique. Finding one with optimal asymptotic runtime can be unintuitive, time-consuming, and error-prone. Our work aims to automate this laborious process. Given an initial correct declarative program, we search for a sequence of semantics-preserving transformations to improve its running time as much as possible. To this end, we describe a set of program transformations, a simple metric for assessing the efficiency of a transformed program, and a heuristic search procedure to improve this metric. We show that in practice, automated search---like the mental search performed by human programmers---can find substantial improvements to the initial program. Empirically, we show that many speed-ups described in the NLP literature could have been discovered automatically by our system.