08 2019/09 10
01020304050607
08091011121314
1516 17 18 192021
22232425262728
29300102030405
Click セミナー

過去のセミナー

開催日2019年8月29日(木曜日)
開催時間10時30分-11時30分
発表者平原 秀一 
発表者の紹介国立情報学研究所
タイトルNP内での非ブラックボックス最悪時・平均時帰着 
発表の概要
公開鍵暗号方式は我々の情報通信の秘密を守る基盤技術であるが、その安全性は複
数の計算量理論の予想に基づいている。例えばP!=NP予想や、NPに対する最悪時・平
均時計算量の同値性を示す必要がある。残念ながら既存の証明手法には限界があり、
それらの未解決問題を解決することができないことが知られている。特に、ブラック
ボックス帰着と呼ばれる証明手法ではNP完全問題について最悪時・平均時計算量の同
値性を示すことができない。
 本講演では、その限界を初めて突破した非ブラックボックス帰着について解説する
とともに、計算量理論を概説する。本講演はFOCS’18の論文に基づく。(https://eccc.weizmann.ac.il/report/2018/138/)
開催場所VBL301B
接続サイト神田ラボ,京大ラボ
開催時間14時30分-15時30分
発表者伊藤 伸志 
発表者の紹介NEC/東京大学
タイトル組合せ制約付きオンラインポートフォリオ最適化 
発表の概要
オンラインポートフォリオ選択 [1] は,逐次的な意思決定問題の一種であり,価値が変化する資産の
配分・投資比率を繰り返し調整して長期的な利益の最大化を目指す問題である.
この問題に対しては,ある意味で最適な意思決定を実現する多項式時間アルゴリズムが知られている[2,3].
一方で,現実の応用例においては,投資可能な資産の種類数に制約がある状況が考えられるが
そのような制約付きの問題に直接適用できる方法は知られていなかった.

そこで本研究では,投資可能な資産数が高々k個に制限されたオンラインポートフォリオ問題を扱い,
次の2つの設定を考察する:
(i) full-feedback設定では,すべての資産の投資効果(利益とコストの比率)が観測できる.
(ii)bandit-feedback設定では,投資した資産の投資効果のみが観測できる.
これらの問題設定において,劣線形リグレットを達成する,つまり最善の固定戦略のパフォーマンス
に漸近することが保証されたアルゴリズムを提案する.加えて,最悪ケースにおける損失の下界を
評価することで,提案アルゴリズムのある種の最適性を示す.
参考文献:
[1] T. M. Cover. Universal portfolios. Mathematical Finance, 1(1):1–29, 1991.
[2] E. Ordentlich and T. M. Cover. The cost of achieving the best portfolio in hindsight.
Mathematics of Operations Research, 23(4):960–982, 1998.
[3] E. Hazan, A. Agarwal, and S. Kale. Logarithmic regret algorithms for online convex optimization.
Machine Learning, 69(2-3):169–192, 2007.
開催場所VBL301B
接続サイト神田ラボ,京大ラボ
開催時間15時30分-16時30分
発表者大城 泰平 
発表者の紹介東京大学
タイトル重みつき行列木定理 
発表の概要
行列木定理はグラフの全域木の数に関する定理であるが,本質的には
正則マトロイドの基の数について述べる定理である.本定理は数学的に
美しいのみならず,数え上げ問題の効率的な解法を与える.
本発表では,正則マトロイドの最小重み基の数についての「重みつき
行列木定理」を立式し,その数え上げを行う効率的アルゴリズムを与える.
さらに,2 つの正則マトロイドの組がある性質を満たす場合について,
最小重み共通基の数についての定理および効率的な数え上げアルゴリズムを与える.
これらの結果は最大重み有向全域木の数え上げや,ある種の二部グラフの
最大重み完全マッチングの数え上げを特殊ケースとして含む.
開催場所VBL301B
接続サイト神田ラボ,京大ラボ
開催時間16時30分-17時30分
発表者黒木 菜保子 
発表者の紹介中央大学
タイトルフラグメント化の手法に基づく物理化学シミュレーションと機械学習による混合液体の物性予測 
発表の概要
機能性液体の物性に関する詳細な知見は、工学的・物理化学的観点から重要である。液体物性は、その液体を構成する分子の間に働く相互作用により決まる。だが、分子間相互作用は分子構造に対して非線形に変化するため、狙った機能をもつ液体を自在にデザインすることは困難であった。本研究の目的は、量子化学計算・分子動力学計算および機械学習の手法を組み合わせることで、実験に先立ち液体物性を高速予測することである。当日は、イオン液体のCO2吸収性を含め、混合液体の物性予測結果を報告する。
開催場所VBL301B
接続サイト神田ラボ,京大ラボ