Please use this identifier to cite or link to this item:
https://cuir.car.chula.ac.th/handle/123456789/13663
| Title: | การสร้างไวยากรณ์ไม่พึ่งบริบทแบบเชื่อมตรงโดยใช้ลำดับของกฎแฝง |
| Other Titles: | An on-line context-free grammars construction using sequences of hidden productions |
| Authors: | สุรพงษ์ ผลประกอบศิลป์ |
| Advisors: | อรรถสิทธิ์ สุรฤกษ์ |
| Other author: | จุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์ |
| Advisor's Email: | athasit@cp.eng.chula.ac.th |
| Subjects: | ภาษารูปนัย อัลกอริทึม การประมวลผลภาษาธรรมชาติ (คอมพิวเตอร์) |
| Issue Date: | 2550 |
| Publisher: | จุฬาลงกรณ์มหาวิทยาลัย |
| Abstract: | ในการวิเคราะห์และแก้ปัญหาด้านการอนุมานภาษาด้วยไวยากรณ์ไม่พึ่งบริบท งานวิจัยส่วนใหญ่จะมุ่งเน้นหาอัลกอริทึมเพื่อเรียนรู้และพัฒนาภาษาไวยากรณ์ไม่พึ่งบริบท จากการพิจารณาโครงสร้างของข้อมูลตัวอย่าง ซึ่งปัญหาที่พบคือ อัลกอริทึมส่วนใหญ่มีความซับซ้อนเชิงเชิงเวลาระดับเลขชี้กำลัง มีงานวิจัยของ วุฒิ สุนทรภัณฑ์ ที่สามารถอนุมานภาษาโดยใช้ความซับซ้อนเชิงเวลาระดับพหุนาม ซึ่งต้องอาศัยตัวอย่างลบในการลดทอนความกว้างของภาษาขณะเรียนรู้ ดังนั้นงานวิจัยนี้จึงเสนออัลกอริทึมสร้างไวยากรณ์ไม่พึ่งบริบทแบบใหม่ สำหรับบางภาษาไม่พึ่งบริบทรวมทั้งทุกภาษาสม่ำเสมอ ที่ใช้ความซับซ้อนเชิงเวลาระดับพหุนาม สามารถเรียนรู้ภาษาได้ด้วยจากตัวอย่างบวก ไม่จำเป็นต้องใช้ตัวอย่างลบ หลักการทำงานของอัลกอริทึม จะเริ่มสร้างไวยากรณ์ไม่พึ่งบริบทที่กว้างครอบคลุมทุกตัวอย่าง แล้วเรียนรู้รูปแบบลำดับของกฎแฝงให้อยู่ในรูปภาษาสม่ำเสมอ จะเห็นว่าลดความซับซ้อนเชิงเวลาน้อยกว่าเมื่อเทียบกับงานวิจัยอื่น และงานวิจัยของ วุฒิ สุนทรภัณฑ์ นอกจากนี้การทำงานของอัลกอริทึมเป็นแบบเชื่อมตรง คือสามารถเรียนรู้รูปแบบลำดับของกฎแฝงไปเรื่อยๆ เมื่อมีตัวอย่างใหม่เข้ามา |
| Other Abstract: | In an analysis and solving of grammar induction with context-free grammar, many researches focused on the algorithms that learned from considering the structure of data. The problem is that most algorithms have exponential time complexity. Wutthi Soonthonpant’s research can inference languages in polynomial time complexity, but needs negative examples to reduce the redundant of language during the learning process.Thus, this proposed research introduces a new construction algorithm for some context-free languages including all regular languages that has polynomial time complexity. This algorithm can be learned from only positive examples, with no need for negative examples. The concept of the algorithm is to initialize a general context-free grammar that covers all data, and learns sequences of hidden productions used in regular language. The time complexity of this algorithm is less than the other researches and Wutthi Soonthonpant’s research. In addition, The proposed algorithm also uses an on-line algorithm that can learn pattern of hidden productions in real-time, when receiving new input data. |
| Description: | วิทยานิพนธ์ (วท.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2550 |
| Degree Name: | วิทยาศาสตรมหาบัณฑิต |
| Degree Level: | ปริญญาโท |
| Degree Discipline: | วิทยาศาสตร์คอมพิวเตอร์ |
| URI: | http://cuir.car.chula.ac.th/handle/123456789/13663 |
| URI: | http://doi.org/10.14457/CU.the.2007.1740 |
| metadata.dc.identifier.DOI: | 10.14457/CU.the.2007.1740 |
| Type: | Thesis |
| Appears in Collections: | Eng - Theses |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Surapong_Ph.pdf | 764.45 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.