权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

形式言語を特徴づけるサンプル集合と効率的な学習可能性に関する研究

研究表征形式语言和高效学习可能性的样本集

基本信息

批准号：
16700007
负责人：
但馬康宏
金额：
$ 1.47万
依托单位：
Tokyo University of Agriculture and Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2005
项目状态：
已结题

项目摘要

形式言語の質問による学習について,以下の結果を得た.1.代表部分集合をランダムサンプルから効率的に構成する方法昨年までの研究において,単純決定性言語などの文脈自由言語の部分言語族が,所属性質問と代表部分集合と呼ばれる特徴的な記号列集合から効率的に学習可能であることを示した.このとき,代表部分集合をランダムサンプルから効率的に構成できれば,形式言語の学習可能性において新たな展開となる.本研究では,そのような構成が可能となる条件を考察し,以下の定理を得た.定理:学習対象を表すことのできる文法の生成規則の出現確率について,その最小値が既知ならば,単純決定性言語は,所属性質問とランダムサンプルから効率的に学習可能である.また,上記定理における出現確率の最小値を何らかの形で学習者が得ることができれば,より理想的な結果を得られる.そこで,ある特別なサンプル分布の元では,学習者が上記の最小値を予測可能であることを示し,以下の定理を得た.定理:サンプル分布が"規則が連続出現する分布"であるとき,単純決定性言語は,所属性質問とランダムサンプルから効率的に学習可能である.2."やさしい教師"と効率的な学習所属性質問と反例による学習において,反例を正の(もしくは,負の)反例から優先的に与える教師を"やさしい教師"と呼ぶ.このとき以下の定理を得た.定理:単純決定性言語は,所属性質問とやさしい教師から多項式時間厳密学習可能である.以上の各定理および昨年までの研究により,形式言語の学習において,それを特徴づけるサンプル集合と効率的な学習について大きな進歩を得ることができた.

The following results are obtained from the study of questioning formal speech. 1. Methods for the composition of the effectiveness of representing partial sets of speech. In a research conducted last year, it was shown that some speech families of purely decisive speech and contextually free speech belong to different speech families, and the nature of the problem and the effectiveness of learning from the set of tokens representing the characteristics of partial sets and calls are possible. This is a representation of a partial set of speech learning possibilities. In this study, the following theorems are obtained by examining the conditions under which the composition of the system is possible. Theorem: The learning object is expressed in terms of the probability of occurrence of grammar rules, the minimum value of which is known, the pure decisive speech, the property of which is the probability of learning. The minimum value of the occurrence rate of the theorem mentioned above is what the learner gets, and the ideal result is what the learner gets. The following theorem is obtained by calculating the minimum predicted probability of the learner. Theorems: Distribution of rules and continuous occurrence of distribution of pure decisive speech, belonging to the nature of the question and the probability of learning. 2. "Teacher" and "teacher" in the rate of learning belong to the nature of the question and counterexample "learning in the middle, counterexample" positive and negative "counterexample" priority "and" teacher "and" teacher "call. The following theorem is obtained. Theorem: Pure deterministic speech is the property of the teacher. The above theorems were studied in the past year, and the learning of formal speech was studied in the past year.

项目成果

期刊论文数量（11）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Polynomial time learning of simple deterministic languages via queries and a representative sample

通过查询和代表性样本对简单确定性语言进行多项式时间学习

DOI：
发表时间：
2004
期刊：
Theoretical Computer Science vol.329
影响因子：
0
作者：
Y.Tajima;E.Tomita;M.Wakatsuki;M.Terada
通讯作者：
M.Terada

Polynomial time learnability of a sub-class of linear languages

线性语言子类的多项式时间可学习性

DOI：
发表时间：
2005
期刊：
IPSJ Transactions on Mathematical Modeling and its Applications vol.46, no.SIG17
影响因子：
0
作者：
Yasuhiro TAJIMA;Yoshiyuki KOTANI et al.
通讯作者：
Yoshiyuki KOTANI et al.

A restricted sample distribution of simple deterministic languages and its learnability

简单确定性语言的受限样本分布及其可学习性

DOI：
发表时间：
2005
期刊：
Proceedings of the 2005 Inter.Conf.on Parall.Distr.Proc.Tech.and Appl. vol.II
影响因子：
0
作者：
Yasuhiro TAJIMA;Yoshiyuki KOTANI
通讯作者：
Yoshiyuki KOTANI

単純決定性言語の学習におけるサンプル分布のある制限と学習可能性

学习简单确定性语言时样本分布的某些局限性和可学习性