主査: 瀧川 一学
幹事: 井 智弘,大久保 好章,杉山 麿人,戸田 貴久,西野 正彬
担当幹事: 井 智弘,戸田 貴久
2020.2.28. 政府方針の発表と状況の悪化を受け、協議の結果、感染拡大防止の観点から現地開催を中止とさせていただきます。
2020.2.21. プログラム通り開催の予定ですが、今後の情勢により学会または会場から中止要請があれば中止させていただくことがあります。また参加される皆様には各自の感染予防対策や発熱などの症状がある場合の参加自粛のご協力をどうぞよろしくお願いいたします。
2020年3月8日(日), 9日(月)
〒832-0826 福岡県柳川市三橋町高畑256 柳川市藤吉コミュニティセンター
https://www.city.yanagawa.fukuoka.jp/kyoiku/shogaigakushu/shisetsu/20160506.html
命題論理式の充足可能性判定(SAT)問題は,約半世紀に渡って膨大な量の研究が蓄積されてきました.特に近年SAT問題を解くプログラムであるSATソルバーの性能が飛躍的に向上し,様々な応用領域における推論の基盤技術としてSAT技術は注目を集めています.
今回の研究会で扱う話題の例としては,SATソルバー,SAT符号化,SAT型システムなどはもとより,SMT,ASP,CSP,QBF,MaxSAT,擬似ブール制約などSAT技術に関連する話題や,プランニング,モデル検査,ソフトウェア検証など各種の応用や事例研究,あるいは,SATの複雑さに関する基礎理論などが挙げられます.さらには,より広い視点から BDD/ZDD などのような実用的なアルゴリズムやデータ構造 なども含まれます.このように多面的な観点から,SATを取り巻く近年の動向を学ぶ機会として,幅広く研究発表を募集します.
もちろん,これらに限らず,人工知能の基本問題に関する理論・技術の研究発表も歓迎します.
制約充足問題に対する充足可能性保存割当ての解析
本講演では,制約充足問題に対する充足可能性割当ての解析とそのアルゴリズム設計への応用について述べる.制約充足問題とは,与えられた制約を満たすような変数への値の割当てが存在するか否かを判定する問題であり,SAT問題の拡張とみることができる.充足可能性保存割当てとは,充足可能性を保つような一部の変数への値の割当て(部分割当て)のことであり,その割当てにより,解くべき問題のサイズを小さくすることができる.例えば,SATにおける単位伝播は充足可能性保存割当ての一例であり,多くのSATソルバーに用いられている.本講演ではまず,制約充足問題において考えられていた様々な充足可能性保存割当ての間の関係を整理する.次に,充足可能性保存割当てを求める計算複雑性について議論する.空でない充足可能性保存割当てを求めることは一般にはNP困難である.そこで,効率的に求めることができる特殊な充足可能性保存割当てを考える.SAT問題に対してはKullmannにより,線形計画問題を解くことにより効率的に求めることができる「線形オーターク割当て」が提案されている.本講演では,線形オーターク割当てを,部分割当ての凸近似とみなし,「線形充足可能性保存割当て」として制約充足問題へ拡張するとともに,凸近似としての極大性を示す.最後に,線形充足可能性保存割当てを求める効率的なアルゴリズムを設計し,整数計画問題の実行可能判定に対する既存研究の結果が統一できることを示す.特に,これまで擬多項式時間で解けることが知られている(それぞれホーンSATおよび2SATの拡張である)ホーン整数計画問題および二次整数計画問題を包含するクラスで,実行可能性判定が擬多項式時間可解であることを示す.
データの簡潔表現に基づく最適化
本発表では,大規模な決定空間/データ上の最適化問題を,それらの簡潔表現上の最適化問題に帰着する方法を紹介する.具体例として,順序制約付きジョブスケジューリング問題の厳密解法や,圧縮データ上のSVMやブースティングの事例を示す.これらの事例ではZDD等の決定ダイアグラムが簡潔表現として用いられる.また,帰着後の問題のサイズは簡潔表現のサイズのみに依存し,元の決定空間やデータのサイズには依存しない.
当研究会の聴講は無料です.
研究会資料は発表の有無に関わらず1500円(学生会員無料)です.
研究会は資料の売上で運営しているため,可能な限り,1グループ
1冊程度で良いので研究会資料を購⼊頂けるとありがたいです.
※ ⼈⼯知能学会員の⽅は研究会登録により年間購読割引があります.
https://www.ai-gakkai.or.jp/sig/announce/sig-registeration/
ご参加いただける方はこちらからお申し込みください.
日時: 3月8日(日) 研究会終了後 - 会場: 福泉操 https://fukusensou.com/ 会費: 5000円程度
詳細な開始時間および会費については後ほど決定しだい掲載します.
井 智弘 (九州工業大学) , 戸田 貴久 (電気通信大学)
E-mail: fpai_kanji@sig-fpai.org
1人当たりの発表時間は質疑を含めて25分.発表者には○印.
SMTソルバーを用いた制約階層解消法
○ 細部 博史(法政大学)
CEGARと反例の共有を用いたSAT型CSPソルバーの並列化方法の考察
○ 宋 剛秀(神戸大学),鍋島 英知(山梨大学),番原 睦則(名古屋大学),田村 直之(神戸大学),井上 克巳(国立情報学研究所)
Transformation of SQL-based combinatorial optimization problems into Constraint problems
Genki Sakanashi(Nagoya University),○ Masahiko Sakai(Nagoya University)
解釈遷移からの学習を用いた遺伝子制御ネットワーク推論手法の開発
○ 池田 光(東京工業大学),井上 克巳(国立情報学研究所)
Inducing belief revision operator from examples.
○ 戸塚 悠太郎(東京工業大学),井上 克巳(国立情報学研究所)
解の多様性を考慮したビームサーチと局所探索法によるフロンティア法を高速化するための変数順序付け
○ 長谷 洋斗(奈良先端科学技術大学院大学),川原 純(京都大学),笠原 正治(奈良先端科学技術大学院大学)
閉包計算に基づく一般化飽和集合の高速な列挙法:相関ルールの一般化を目指して
○ 安藤 祐太(山梨大学),岩沼 宏冶(山梨大学)
ZDDを用いた集合分割の列挙索引化手法の提案と実験的評価
○ 高橋 翔哉(北海道大学),吉岡 真治(北海道大学)
アピアランスを用いたクラスタリングにおける確信度の評価手法と実データによる検証
岩﨑 幸子(国立情報学研究所),○ 宇野 毅明(国立情報学研究所)
クラスタリング安定化手法を用いた芯クラスタの抽出と実データによる質の評価
岩﨑 幸子(国立情報学研究所),○ 宇野 毅明(国立情報学研究所)
可換マッチング問題の固定パラメーター容易性に関する研究
○ 久保田 稜(京都大学),小島 健介(京都大学),小林 靖明(京都大学),山本 章博(京都大学)
ユーザの納得感を考慮した線形モデルの重み付き Lasso による定式化と一解法
○ 鈴木 浩史(富士通研究所),後藤 啓介(富士通研究所),岩下 洋哲(富士通研究所),高木 拓也(富士通研),大堀 耕太郎(富士通研),原 聡(大阪大学)
非循環な双極議論フレームワークの段階的作成手法
○ 川崎 樹(関西学院大学),高橋 和子(関西学院大学)
人工知能学会の研究会資料(第一種)の扱いについて(2015年度より)
2015年4月以降に人工知能学会第一種研究会に投稿された研究会資料は,
紙冊子に掲載されると同時に,学会事務局で資料ID(※1)を付与した上で
学会文献提供サイト「AI書庫」(https://jsai.ixsq.nii.ac.jp/ej/)上のPDF
ファイルとして閲覧可能となります.
発行日(※2)から一年間は,一本あたり(非会員 600円+消費税,学会員 300
円+消費税,登録会員 0円)にて販売します.一年間の保留期間(エンバーゴ)
後は無料購読できるようになりオンライン公開されます.
なおAI書庫上のデータには,標準的な識別子(番号)は付与されませんが,
一般的な検索エンジンや国立情報学研究所が提供するCiNiiなどから容易に
検索できるようになります.
(※1) 研究会資料ID付与規則の変更(2015年度より)
研究会資料ID(論文ID)の付与ルールを下記のように統一しました.
(※2) 紙媒体の奥付に記載された発行日