[4Yin-A] ポスター6

[4Yin-A-KA02] 研究会優秀賞：「グラフアテンションに基づく微分可能なMaxSAT解法」人工知能基本問題研究会（SIGｰFPAI）

〇森山  総太 ^1,2、井上  克巳² (1. 総合研究大学院大学、2. 国立情報学研究所)

深層学習を用いて充足可能性判定問題（SAT）などの推論問題を解く試みは、頑健でスケーラブルなAIシステムを開発するために近年注目されている。本研究は、重み付き充足最大化問題（Weighted MaxSAT）を微分可能な形で解く新たなグラフニューラルネットワーク（GNN）を開発することで、このようなニューラル推論技法を発展させることを目指す。具体的には、t-ノルムに基づいたアテンション機構とメッセージパッシング機構を用いて、貪欲的に分散局所探索を行うように設計されたGNNであるSAT-based Graph Attention Network (SGAT)を提案する。本モデルの有効性を示すため、MaxSAT問題を連続空間で解くことができる新たな局所探索ソルバーをSGATに基づいて開発した。（重み付き）MaxSATのベンチマーク問題を対象とした実験では、提案手法が既存のニューラルネットワークを用いたアーキテクチャを大幅に上回る性能を発揮し、連続的手法の中では最も良い性能を発揮することが示された。