Office of Academic Resources
Chulalongkorn University
Chulalongkorn University

Home / Help

Titleการสร้างไวยากรณ์ไม่พึ่งบริบทแบบเชื่อมตรงโดยใช้ลำดับของกฎแฝง / สุรพงษ์ ผลประกอบศิลป์ = An on-line context-free grammars construction using sequences of hidden productions
Author Surapong Phonprakobsin
Imprint 2550
Connect tohttp://cuir.car.chula.ac.th/handle/123456789/13663
Descript ง-ญ, 38 แผ่น : ภาพประกอบ

SUMMARY

ในการวิเคราะห์และแก้ปัญหาด้านการอนุมานภาษาด้วยไวยากรณ์ไม่พึ่งบริบท งานวิจัยส่วนใหญ่จะมุ่งเน้นหาอัลกอริทึมเพื่อเรียนรู้และพัฒนาภาษาไวยากรณ์ไม่พึ่งบริบท จากการพิจารณาโครงสร้างของข้อมูลตัวอย่าง ซึ่งปัญหาที่พบคือ อัลกอริทึมส่วนใหญ่มีความซับซ้อนเชิงเชิงเวลาระดับเลขชี้กำลัง มีงานวิจัยของ วุฒิ สุนทรภัณฑ์ ที่สามารถอนุมานภาษาโดยใช้ความซับซ้อนเชิงเวลาระดับพหุนาม ซึ่งต้องอาศัยตัวอย่างลบในการลดทอนความกว้างของภาษาขณะเรียนรู้ ดังนั้นงานวิจัยนี้จึงเสนออัลกอริทึมสร้างไวยากรณ์ไม่พึ่งบริบทแบบใหม่ สำหรับบางภาษาไม่พึ่งบริบทรวมทั้งทุกภาษาสม่ำเสมอ ที่ใช้ความซับซ้อนเชิงเวลาระดับพหุนาม สามารถเรียนรู้ภาษาได้ด้วยจากตัวอย่างบวก ไม่จำเป็นต้องใช้ตัวอย่างลบ หลักการทำงานของอัลกอริทึม จะเริ่มสร้างไวยากรณ์ไม่พึ่งบริบทที่กว้างครอบคลุมทุกตัวอย่าง แล้วเรียนรู้รูปแบบลำดับของกฎแฝงให้อยู่ในรูปภาษาสม่ำเสมอ จะเห็นว่าลดความซับซ้อนเชิงเวลาน้อยกว่าเมื่อเทียบกับงานวิจัยอื่น และงานวิจัยของ วุฒิ สุนทรภัณฑ์ นอกจากนี้การทำงานของอัลกอริทึมเป็นแบบเชื่อมตรง คือสามารถเรียนรู้รูปแบบลำดับของกฎแฝงไปเรื่อยๆ เมื่อมีตัวอย่างใหม่เข้ามา
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.


ภาษารูปนัย อัลกอริทึม การประมวลผลภาษาธรรมชาติ (วิทยาการคอมพิวเตอร์) Formal languages Algorithms Natural language processing ‪(Computer science)‬

LOCATIONCALL#STATUS
Central Library @ Chamchuri 10 : Thesis501092LIB USE ONLY



Location



Office of Academic Resources, Chulalongkorn University, Phayathai Rd. Pathumwan Bangkok 10330 Thailand

Contact Us

Tel. 0-2218-2929,
0-2218-2927 (Library Service)
0-2218-2903 (Administrative Division)
Fax. 0-2215-3617, 0-2218-2907

Social Network

  line

facebook   instragram