人工知能学会 第113回人工知能基本問題研究会(SIG-FPAI)

開催情報

開催日

2020年9月29日(火), 30日(水)

会場

オンライン開催(具体的な参加方法は参加申込者に追って連絡いたします。)

参加申込

以下のページより申込ください。 https://www.ai-gakkai.or.jp/sig-system/sigusers/add/fpai/113

参加費

当研究会の聴講は無料です.

発表資料

電子版(一般 1,500円,学生無料)【通販サイト:https://jsaioffice.stores.jp/】
紙冊子(2,000円)【申込先:https://forms.gle/Nu9k9FvhisRK1qYQA 】
※ 電子版は 9月20日より販売開始です.
※ 紙冊子は 9月22日(火)までにご購入、並びにお申し込みください.
※ 学生は紙冊子の申込みフォームから無料で電子版を受け取れます.
※ ⼈⼯知能学会員の⽅は研究会登録により年間購読割引があります.
https://www.ai-gakkai.or.jp/sig/announce/sig-registeration/

テーマ:特集「離散構造処理の最新動向」および一般

開催趣旨

離散構造とは論理, 集合, グラフなどの記号的に表現される対象である. 離散構造は扱う対象, モデル, データ表現など, 様々な形で現れる. 何らかの意味でよい離散構造を考えるとき, 一般的のその候補の数は組合せ爆発的に増加する. そのため, それらの候補を愚直に列挙してしまうと, 途方もない処理時間が必要となり, 現実的には扱うことが不可能となる.
今回の研究会では, 離散構造処理に代表される離散構造を効率的に扱うための枠組みや, 離散構造を対象とした研究, 離散構造で表現されるモデルなど, 離散構造に関連した研究などを幅広く募集する.
もちろん, これらに限らず, 人工知能の基本問題に関する理論・技術の研究発表も歓迎します.

招待講演

招待講演1

畑埜 晃平 (九州大学)

講演タイトル

データの簡潔表現に基づく最適化

講演概要

本発表では,大規模な決定空間/データ上の最適化問題を,それらの簡潔表現上の最適化問題に帰着する方法を紹介する.具体例として,順序制約付きジョブスケジューリング問題の厳密解法や,圧縮データ上のSVMやブースティングの事例を示す.これらの事例ではZDD等の決定ダイアグラムが簡潔表現として用いられる.また,帰着後の問題のサイズは簡潔表現のサイズのみに依存し,元の決定空間やデータのサイズには依存しない.

招待講演2

木村 慧 (埼玉大学)

講演タイトル

制約充足問題に対する充足可能性保存割当ての解析

講演概要

本講演では,制約充足問題に対する充足可能性割当ての解析とそのアルゴリズム設計への応用について述べる.制約充足問題とは,与えられた制約を満たすような変数への値の割当てが存在するか否かを判定する問題であり,SAT問題の拡張とみることができる.充足可能性保存割当てとは,充足可能性を保つような一部の変数への値の割当て(部分割当て)のことであり,その割当てにより,解くべき問題のサイズを小さくすることができる.例えば,SATにおける単位伝播は充足可能性保存割当ての一例であり,多くのSATソルバーに用いられている.本講演ではまず,制約充足問題において考えられていた様々な充足可能性保存割当ての間の関係を整理する.次に,充足可能性保存割当てを求める計算複雑性について議論する.空でない充足可能性保存割当てを求めることは一般にはNP困難である.そこで,効率的に求めることができる特殊な充足可能性保存割当てを考える.SAT問題に対してはKullmannにより,線形計画問題を解くことにより効率的に求めることができる「線形オーターク割当て」が提案されている.本講演では,線形オーターク割当てを,部分割当ての凸近似とみなし,「線形充足可能性保存割当て」として制約充足問題へ拡張するとともに,凸近似としての極大性を示す.最後に,線形充足可能性保存割当てを求める効率的なアルゴリズムを設計し,整数計画問題の実行可能判定に対する既存研究の結果が統一できることを示す.特に,これまで擬多項式時間で解けることが知られている(それぞれホーンSATおよび2SATの拡張である)ホーン整数計画問題および二次整数計画問題を包含するクラスで,実行可能性判定が擬多項式時間可解であることを示す.

プログラム

発表は1件あたり25分(発表20分、質疑5分)です。
★ マークの発表は新型コロナウイルス感染症を考慮し開催中止となった FPAI112 で発表予定であった発表です。

2020/09/29(火)

招待講演1(15:00 - 16:00)

セッション1(16:15 - 17:30)

2020/09/30(水)

セッション2(10:00 - 11:15)

招待講演2(13:00 - 14:00)

セッション3(14:15 - 15:30)

セッション4(15:45 - 17:10)

運営情報

運営メンバー

主査: 大久保 好章
幹事: 石畠 正和, 大滝 啓介, 後藤 啓介, 小林 靖明, 蓑田 玲緒奈
担当幹事: 石畠 正和

人工知能学会の研究会資料(第一種)の扱いについて(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)の付与ルールを下記のように統一しました.

資料ID: [研究会名略称]-[巻(3桁)]-[号(2桁)] 例:SIG-SWO-021-03
巻: 研究会の通算の開催回数 例:21
号: 特定の回での論文の発表順 例:3
頁: 研究会毎に以下の何れかのポリシーで付与する.
A)各回でページナンバリングしている場合は,そのページ情報を使用
B)そうでない場合には,発表毎に「pp. 1-論文のページ分量」
(※2) 紙媒体の奥付に記載された発行日