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

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

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