Chulalongkorn University Theses and Dissertations (Chula ETD)

ระดับของภาษายอมรับได้-เค และความสามารถในการเรียนรู้

Other Title (Parallel Title in Other Language of ETD)

A class of k-acceptable and its learnability

Year (A.D.)

2010

Document Type

Thesis

First Advisor

อรรถสิทธิ์ สุรฤกษ์

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

วิศวกรรมศาสตรดุษฎีบัณฑิต

Degree Level

ปริญญาเอก

Degree Discipline

วิศวกรรมคอมพิวเตอร์

DOI

10.58837/CHULA.THE.2010.1430

Abstract

วิทยานิพนธ์ฉบับนี้ได้ศึกษาระดับของภาษารูปนัยที่เรียกว่าภาษายอมรับได้-เค และ ความสามารถในการเรียนรู้ของระดับของภาษานี้ บนแบบจำลองการเรียนรู้เชิงตัวอย่างที่เรียกว่าการระบุภาษาได้ในขอบเขตจำกัด วิทยานิพนธ์นี้ได้ทำการศึกษาความสามารถในการเรียนรู้ในรูปแบบการนำเสนอตัวอย่างที่แตกต่างกัน 2 รูปแบบ คือ การนำเสนอด้วยตัวอย่างบวกเพียงอย่างเดียว และการนำเสนอด้วยตัวอย่างบวกและตัวอย่างลบ ผลจากการศึกษาเชิงทฤษฎีแสดงให้เห็นว่าระดับภาษายอมรับได้-เคไม่สามารถเรียนรู้ได้ในขอบเขตจำกัดในกรณีที่นำเสนอด้วยตัวอย่างบวกเพียงอย่างเดียวแต่สำหรับในกรณีที่การนำเสนอมีทั้งตัวอย่างบวกและตัวอย่างลบระดับภาษายอมรับได้-เคสามารถเรียนรู้ได้ในขอบเขตจำกัด นอกจากนี้งานวิจัยนี้ยังได้ศึกษาถึงประสิทธิภาพของการเรียนรู้อีกด้วย ผลการวิจัยพบว่าระดับของภาษายอมรับได้-เคสามารถเรียนรู้ได้อย่างมีประสิทธิภาพจากเวลาและจำนวนตัวอย่างเชิงพหุนามในกรณีที่การนำเสนอมีทั้งตัวอย่างบวกและตัวอย่างลบ

Other Abstract (Other language abstract of ETD)

This thesis studies a class of formal languages called k-acceptable languages and its learnability on an explanatory learning model. This model is well known identification in the limit. Two different types of presentation of language information have been investigated to the learnability of this class of languages. First type is presentation with only positive examples. Second type is presentation with both positive and negative examples. The result theoretically shows that the class of k-acceptable languages is not learnable in the limit from only positive examples. Conversely, the class of k-acceptable languages is learnable in the limit from both positive and negative examples. In addition, the issue of efficiency of learning has been considered in term of learning time and characteristic examples used in the process of learning. Our result shows that the class of k-acceptable languages is learnable from polynomial time and data by using both positive and negative examples.

Link to Full Text

Share

COinS