Polynomial Time Learnability of a Sub-class of Linear Languages

スポンサーリンク

概要

• 論文の詳細を見る

• We propose some PAC like settings for a learning problem of a sub-class of linear languages, and show its polynomial time learnability in each of our settings. Here, the sub-class of linear languages is newly defined, and it includes the class of regular languages and the class of even linear languages. We show a polynomial time learning algorithm in either of the following settings with a fixed but unknown probability distribution for examples. (1) The first case is when the learner can use randomly drawn examples, membership queries, and a set of representative samples. (2) The second case is when the learner can use randomly drawn examples, membership queries, and both of the size of a grammar which can generate the target language and d. Where d is the probability such that the rarest rule in the target grammar occurs in the derivation of a randomly drawn example. In each case, for the target language L_t, the hypothesis L_h satisfies that Pr[P(L_hΔL_t)≤ε]≥1-δ for the error parameter 0<ε≤1 and the confidential parameter 0<δ≤1.

• 一般社団法人情報処理学会の論文
• 2005-12-15

著者

• Tajima Yasuhiro

  Institute Of Symbiotic Science And Technology Tokyo University Of Agriculture And Technology

• KOTANI YOSHIYUKI

  Institute of Symbiotic Science and Technology, Tokyo University of Agriculture and Technology

• TERADA MATSUAKI

  Institute of Symbiotic Science and Technology, Tokyo University of Agriculture and Technology

• Terada Matsuaki

  Institute Of Symbiotic Science And Technology Tokyo University Of Agriculture And Technology

• Kotani Yoshiyuki

  Institute Of Symbiotic Science And Technology Tokyo University Of Agriculture And Technology

関連論文

• Polynomial Time Learnability of a Sub-class of Linear Languages
• Polynomial Time Learnability of a Sub-class of Linear Languages
• Polynomial Time Learnability of a Sub-class of Linear Languages

スポンサーリンク