抄録
F-034
系列二分決定図の質問学習
◎渡部航也・ディプタラマ ヘンリアン・吉仲 亮・篠原 歩(東北大)
質問学習とは,学習者が教師に対して何かしらの質問を能動的に行いながら,教師が持つ概念を同定しようとする学習の枠組みである.正規言語を表現するDFAが多項式回数の質問によって学習可能なことがAngluinによって初めて示された.以降質問回数の削減や,NFAやBDD,ZDDといった様々なデータ構造の為の質問学習アルゴリズムの研究がなされている.本研究では系列二分決定図(SeqBDD)の多項式質問回数学習アルゴリズムを提案する.SeqBDDはLoekitoらによって提案された,有限の系列データをコンパクトに保存するデータ構造であり,BDD,ZDDの構造を受けついだデータ構造である.