一意標準形文法をもつ文脈自由言語族およびその学習に関する研究

本研究課題は，近年の文脈自由言語に対する分布学習アプローチを発展させ，分布学習可能で一意標準形を持つ文脈自由言語族を探究することを目的としている．2022年度の成果の第一は，無限アルファベット上の文脈自由言語の学習に関するものである．古典的な有限アルファベット上の正則言語の学習手法を，シンボリックオートマトンと呼ばれる言語受理機械を用いて無限アルファベット上の正則言語の学習へと拡張した先行研究を参考にしつつ，正例から極限同定可能であることが知られていた可代入文脈自由言語を無限アルファベット上のそれへと拡張した際の学習可能性について考察した．その結果，文脈自由文法中の規則に現れる無限アルファベット上の概念クラスが学習可能であるだけでは不十分であるという否定的な結果を得る一方で，効率的な学習可能性を損なわない条件を発見し，正例から極限同定可能な無限アルファベット上の文脈自由言語族を見出す，世界初の結果となった．第二の成果は，分布学習アプローチ自体の一般化についてである．従来の文脈自由言語の分布学習では，いかなる文字列と文脈の結合が学習対象の言語に属する文字列を形成するか，という文字列と文脈の関係に焦点を当て，有限個の文脈が受理するような文字列で特徴づけ可能な非終端記号を学習するアプローチをとっていた．本研究ではこれを一般化し，文脈の受理する文字列集合に対するブール演算やスター演算を許した場合に，従来のアプローチでは学習できなかった多様な文脈自由言語が，所属性質問と正例から極限同定可能になることを示した．これらの成果は現在国際会議に投稿中で，査読を待っている状況である．

本研究課題は，近年の文脈自由言語に対する分布学習アプローチを発展させ，分布学習可能で一意標準形を持つ文脈自由言語族を探究することを目的としている．2022年度の成果の第一は，無限アルファベット上の文脈自由言語の学習に関するものである．古典的な有限アルファベット上の正則言語の学習手法を，シンボリックオートマトンと呼ばれる言語受理機械を用いて無限アルファベット上の正則言語の学習へと拡張した先行研究を参考にしつつ，正例から極限同定可能であることが知られていた可代入文脈自由言語を無限アルファベット上のそれへと拡張した際の学習可能性について考察した．その結果，文脈自由文法中の規則に現れる無限アルファベット上の概念クラスが学習可能であるだけでは不十分であるという否定的な結果を得る一方で，効率的な学習可能性を損なわない条件を発見し，正例から極限同定可能な無限アルファベット上の文脈自由言語族を見出す，世界初の結果となった．第二の成果は，分布学習アプローチ自体の一般化についてである．従来の文脈自由言語の分布学習では，いかなる文字列と文脈の結合が学習対象の言語に属する文字列を形成するか，という文字列と文脈の関係に焦点を当て，有限個の文脈が受理するような文字列で特徴づけ可能な非終端記号を学習するアプローチをとっていた．本研究ではこれを一般化し，文脈の受理する文字列集合に対するブール演算やスター演算を許した場合に，従来のアプローチでは学習できなかった多様な文脈自由言語が，所属性質問と正例から極限同定可能になることを示した．これらの成果は現在国際会議に投稿中で，査読を待っている状況である．