Chulalongkorn University Theses and Dissertations (Chula ETD)
การปรับปรุงและพัฒนาอัลกอริทึมการอนุมานไวยากรณ์ไม่พึ่งบริบท
Other Title (Parallel Title in Other Language of ETD)
Improving and developing context free grammar inference algorithm
Year (A.D.)
2006
Document Type
Thesis
First Advisor
อรรถสิทธิ์ สุรฤกษ์
Faculty/College
Faculty of Engineering (คณะวิศวกรรมศาสตร์)
Degree Name
วิทยาศาสตรมหาบัณฑิต
Degree Level
ปริญญาโท
Degree Discipline
วิทยาศาสตร์คอมพิวเตอร์
DOI
10.58837/CHULA.THE.2006.1285
Abstract
การอนุมานไวยากรณ์ไม่พึ่งบริบท เป็นส่วนสำคัญในการวิเคราะห์แก้ปัญหาการรู้จำ รูปแบบ และงานวิจัยต่างๆที่เกี่ยวกับการประมวลผลภาษาธรรมชาติได้เน้นไปที่วิธีการพัฒนาการอนุมาน ซึ่งปัญหาหลักของการอนุมานไวยากรณ์ไม่พึ่งบริบท คือ ใช้ค่าความซับซ้อนเชิงเวลาของการอนุมานไวยากรณ์ที่สูง ซึ่งมีผลงานวิจัยทางทฤษฏีระบุว่าไม่สามารถหาอัลกอริทึมอนุมานไวยากรณ์ไม่พึ่งบริบทที่ใช้ความซับซ้อนเชิงเวลาไม่เกินฟังก์ชั่นพหุนามได้ ดังนั้นงานวิจัยนี้ได้นำเสนออัลกอริทึมการอนุมานไวยากรณ์ไม่พึ่งบริบทสำหรับบางภาษาไม่พึ่งบริบทรวมทั้งภาษาสม่ำเสมอ ที่มีความซับซ้อนเชิงเวลาไม่เกินฟังก์ชั่นพหุนาม ซึ่งหลักการทำงานของอัลกอริทึมจะพิจารณาสร้างกฎวนซ้ำจากข้อมูลตัวอย่างที่อยู่ในภาษาเรียกว่า ข้อมูลตัวอย่างบวก และเพื่อไม่ให้ไวยากรณ์ไม่พึ่งบริบทมีความกว้างมากเกินไป งานวิจัยนี้ได้นำข้อมูลตัวอย่างที่ไม่อยู่ในภาษาเรียกว่าตัวอย่างลบมาร่วมพิจารณาด้วย
Other Abstract (Other language abstract of ETD)
Context-free grammar inference plays an important role in pattern recognition. Many researches in natural language processing are focused on how to improve an inference technique. In fact, the major problem is that it requires a high degree of computational complexity. Some theoretical results stated that the problem cannot be solved by any polynomial time algorithms. This research is aimed to introduce an inference algorithm for some context free languages including regular languages. The proposed algorithm needs a polynomial time complexity. Our concept is to create some recursive rules using positive samples. In order to avoid an overgeneralization problem, some negative samples are considered in the training process.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
สุนทรภัณฑ์, วุฒิ, "การปรับปรุงและพัฒนาอัลกอริทึมการอนุมานไวยากรณ์ไม่พึ่งบริบท" (2006). Chulalongkorn University Theses and Dissertations (Chula ETD). 66214.
https://digital.car.chula.ac.th/chulaetd/66214