07 2019/08 09
28293031010203
04050607080910
11121314151617
18192021222324
252627 28 293031
Click セミナー

今後のセミナー

開催日2019年8月28日(水曜日)
発表者山口 勇太郎
タイトル無制約XOS関数最大化に対する最適近似アルゴリズム
発表者佐々木 勇和
タイトル Structural Indexing for Conjunctive Path Queries
開催日2019年8月29日(木曜日)
発表者平原 秀一
タイトルNP内での非ブラックボックス最悪時・平均時帰着
発表者伊藤 伸志
タイトル組合せ制約付きオンラインポートフォリオ最適化
発表者大城 泰平
タイトル重みつき行列木定理
発表者黒木 菜保子
タイトルフラグメント化の手法に基づく物理化学シミュレーションと機械学習による混合液体の物性予測
    

詳細

閉じる
開催日2019年8月28日(水曜日)
開催場所VBL301B
開催時間15時30分-16時30分 
発表者山口 勇太郎  
発表者の紹介大阪大学
タイトル無制約XOS関数最大化に対する最適近似アルゴリズム 
発表の概要いくつかの加法的な集合関数の最大値を取る形で表現できる集合関数は,XOS関数と呼ばれ,劣モジュラ関数などを含むことが知られている.本講演では,関数値オラクルで与えられたXOS関数を最大化する問題を考え,最適な近似比を達成する多項式時間アルゴリズムを提案する.本研究は,河瀬 康志氏,小林 佑輔氏との共同研究に基づき,これは昨年度の SSSW2018.09B において開始されたものである.
接続サイト神田ラボ,京大ラボ
開催時間16時30分-17時30分 
発表者佐々木 勇和  
発表者の紹介大阪大学
タイトル Structural Indexing for Conjunctive Path Queries 
発表の概要Structural indexing is a powerful approach to accelerating query
evaluation, whereby data objects are partitioned reflecting the
expressive power of a given
query language. Each partition block of the index holds exactly those
objects that are indistinguishable with respect to queries expressible
in the language.
Structural indexes have proven successful for XML, RDF, and relational
data management. In this paper we study structural indexing for
conjunctive path
queries. Conjunctive path queries form the core of contemporary graph
query languages such as SPARQL, Cypher, PGQL, and G-CORE. The
conjunctive path queries play the same fundamental role that the
conjunctive queries do for SQL. We develop the first
practical structural indexes for this important query language. In
particular, we propose a structural index based on
k-path-bisimulation, tightly
coupled to the expressive power of the conjunctive path queries, and
develop algorithms for efficient query processing with our index.
Furthermore, we
study workload-aware structural indexes to reduce both the
construction and space costs according to a given workload. We
demonstrate through
extensive experiments using real and synthetic graphs that our methods
accelerate query processing by up to four orders of magnitude over the
state-of-the-art methods, without increasing index size.
接続サイト神田ラボ,京大ラボ
    
閉じる

詳細

閉じる
開催日2019年8月29日(木曜日)
開催場所VBL301B
開催時間10時30分-11時30分 
発表者平原 秀一  
発表者の紹介国立情報学研究所
タイトルNP内での非ブラックボックス最悪時・平均時帰着 
発表の概要公開鍵暗号方式は我々の情報通信の秘密を守る基盤技術であるが、その安全性は複
数の計算量理論の予想に基づいている。例えばP!=NP予想や、NPに対する最悪時・平
均時計算量の同値性を示す必要がある。残念ながら既存の証明手法には限界があり、
それらの未解決問題を解決することができないことが知られている。特に、ブラック
ボックス帰着と呼ばれる証明手法ではNP完全問題について最悪時・平均時計算量の同
値性を示すことができない。
 本講演では、その限界を初めて突破した非ブラックボックス帰着について解説する
とともに、計算量理論を概説する。本講演はFOCS’18の論文に基づく。(https://eccc.weizmann.ac.il/report/2018/138/)
接続サイト神田ラボ,京大ラボ
開催時間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.
接続サイト神田ラボ,京大ラボ
開催時間15時30分-16時30分 
発表者大城 泰平  
発表者の紹介東京大学
タイトル重みつき行列木定理 
発表の概要行列木定理はグラフの全域木の数に関する定理であるが,本質的には
正則マトロイドの基の数について述べる定理である.本定理は数学的に
美しいのみならず,数え上げ問題の効率的な解法を与える.
本発表では,正則マトロイドの最小重み基の数についての「重みつき
行列木定理」を立式し,その数え上げを行う効率的アルゴリズムを与える.
さらに,2 つの正則マトロイドの組がある性質を満たす場合について,
最小重み共通基の数についての定理および効率的な数え上げアルゴリズムを与える.
これらの結果は最大重み有向全域木の数え上げや,ある種の二部グラフの
最大重み完全マッチングの数え上げを特殊ケースとして含む.
接続サイト神田ラボ,京大ラボ
開催時間16時30分-17時30分 
発表者黒木 菜保子  
発表者の紹介中央大学
タイトルフラグメント化の手法に基づく物理化学シミュレーションと機械学習による混合液体の物性予測 
発表の概要機能性液体の物性に関する詳細な知見は、工学的・物理化学的観点から重要である。液体物性は、その液体を構成する分子の間に働く相互作用により決まる。だが、分子間相互作用は分子構造に対して非線形に変化するため、狙った機能をもつ液体を自在にデザインすることは困難であった。本研究の目的は、量子化学計算・分子動力学計算および機械学習の手法を組み合わせることで、実験に先立ち液体物性を高速予測することである。当日は、イオン液体のCO2吸収性を含め、混合液体の物性予測結果を報告する。
接続サイト神田ラボ,京大ラボ
    
閉じる