F-034
系列二分決定図の質問学習

◎渡部航也・ディプタラマ ヘンリアン・吉仲　亮・篠原　歩（東北大）

質問学習とは，学習者が教師に対して何かしらの質問を能動的に行いながら，教師が持つ概念を同定しようとする学習の枠組みである．正規言語を表現するDFAが多項式回数の質問によって学習可能なことがAngluinによって初めて示された．以降質問回数の削減や，NFAやBDD，ZDDといった様々なデータ構造の為の質問学習アルゴリズムの研究がなされている．本研究では系列二分決定図（SeqBDD）の多項式質問回数学習アルゴリズムを提案する．SeqBDDはLoekitoらによって提案された，有限の系列データをコンパクトに保存するデータ構造であり，BDD，ZDDの構造を受けついだデータ構造である．