第 14 回研究会
- 日時: 2021 年 1 月 8 日 (金) 13:30--18:00 (開場は 13:00 頃)
- 会場: ウェブ会議システム Zoom
- 講演 1
- 講演者: 藤井海斗氏 (国立情報学研究所 情報学プリンシプル研究系)
- 講演題目: 近似的劣モジュラ性を用いた局所探索法の近似保証
- 講演概要: 機械学習に現れるさまざまな問題に対して, 劣モジュラ最適化に基づいたアルゴリズムが設計されてきた.
しかしながら, 劣モジュラ最適化の枠組みには収まらないような問題も多数知られている.
近年, そのような問題に対して, 劣モジュラ性に近い性質 (近似的劣モジュラ性) を用いたアプローチが発展している.
本講演では, 機械学習において用いられるいくつかの近似的劣モジュラ性を紹介したあと, 局所化可能性 (localizability) という新しい近似的劣モジュラ性を提案する.
局所化可能性を用いて, 組合せ的な制約をもつ集合関数最大化に対する局所探索法に近似保証を与える.
また, 提案した枠組みをスパース最適化に応用し, 局所探索法を高速化する手法も提案する.
- 講演 2
- 講演者: 谷川眞一氏 (東京大学 大学院情報理工学系研究科 数理情報学専攻)
- 講演題目: グラフ上の極大マトロイドの構成
- 講演概要: グラフの辺集合上に定義される様々なマトロイドを導入し, それらのマトロイドを考察する工学的動機を紹介する.
さらに指定されたパターン (部分グラフ) をサーキットとするマトロイドで極大なものを構成するアルゴリズムを紹介し, 極大マトロイドの唯一性に関する Graver と Whiteley の予想を紹介する.
- 参加費用: 無料
- 参加資格: 自由 (会員/非会員不問)
- 事前申込: 要
- 参加者数 (事前申込者数): 49 名