情報処理学会 第79回全国大会講演要旨

形式言語における学習理論の研究では，語句の分布情報を利用する分布学習が大きな成果を挙げている．特に，ClarkとYoshinaka(2014)は，分布学習が文脈自由言語を超える複雑な文法形式にも拡張できることを示した．本発表では，分布学習が形式グラフ体系と呼ばれる形式体系によるグラフ言語の学習にも適用できることを示す．形式グラフ体系は，Uchidaら(1995)によって導入されたグラフを項とする論理プログラムの一種で，文脈自由グラフ文法と等価な部分クラスを持つ．本発表では，文脈自由な形式グラフ体系は，それが有限な文脈で表現可能で，有界な次数と木幅のグラフ言語を生成するとき，所属性質問を用いて多項式更新時間で正例から帰納推論可能であることを示す．