グラフ構造のダイナミクスを模倣する確率的形式グラフ体系の学習可能性の探究

点击翻译按钮获取中文摘要

本研究課題では、グラフ構造データの生成過程を形式化した体系として確率的形式グラフ体系の導入を行い、その学習理論を構築することを目標とする。2022年度は、2021年度に引き続き、形式グラフ体系の計算論的学習理論に基づく基礎的研究を行った。また、計算論的学習理論における学習モデルの精度評価を行うために、グラフ畳み込みネットワークと質問学習モデルの協調手法を提案し、その有効性を示した。具体的には次のとおりである。(1) 計算論的学習理論の観点から、次数に制限のあるパラメータ化された遺伝的形式グラフ体系(HFGS)によって定義されるHFGS言語のサブクラスの多項式時間PAC学習可能性を明らかにした。具体的には、HFGSのクラスを、(a)グラフ書き換え規則の数の上限と各種遺伝的性質、(b)HFGSグラフ言語の木幅と次数の上限、(c)グラフパターンの次数と超辺次元の上限、(d)グラフ書き換え規則の変数の個数、本体アトムの数、述語記号の引数の数の上限により階層付けして、グラフ言語の木幅以外のパラメータが定数ならば多項式時間PAC学習可能であることを証明した。(2) 質問学習モデルはAngluin(1988)により提案された計算論的学習理論における機械学習モデルの一つである。質問学習モデルは、常に正答を返すオラクルを仮定して機械学習における計算量などの解析を行うモデルである。一方、最近の小田ら(2022)の研究では、木構造データベースに対する二値分類問題を著しく高い精度で計算するグラフ畳み込みネットワーク(GCN)が報告されている。本研究課題では、超高精度GCNをオラクルとする無順序木パターンの質問学習モデルを提案した。そして、そのモデル上で二値分類問題、無矛盾性問題、可視化問題の3つの問題の精度を評価した。それにより、超高精度GCNをオラクルとする質問学習手法の有効性を示した。