講演情報
[2Yin-A-21]無矛盾なサイズ限定ブール論理式の例からの厳密学習
〇川田 悠介1、有村 博紀1 (1. 北海道大学)
キーワード：
AI説明可能性、ブール関数の学習、離散最適化、列挙アルゴリズム、パラメータ化計算量
本研究はXAIの観点から、正負の例に矛盾せず、かつサイズt以下のブール論理式を同定する「無矛盾仮説発見問題」を扱う。これは計算学習理論における「実現可能設定」での「任意のデータ分布」からの「適切学習」に相当する。本問題の困難性を踏まえ、2つの厳密アルゴリズムを提案した。手法1は全候補の列挙に基づく。手法2は下界証明に用いられる「Razborovの論理式サイズゲーム」を応用し、動的計画法により式の存在を再帰的に検証する新しい手法である。理論的には，共に指数計算時間をもつが、前者はサイズtが、後者はデータ数mがパラメータのときの固定パラメータ計算量を詳細に調べた．最後に、ノイズを許容する不可知設定や不適切学習への拡張を議論する。