09 2017/10 11
01 020304050607
08091011121314
1516 1718192021
22 232425262728
29303101020304
Click セミナー

過去のセミナー

開催日2017年1月30日(月曜日)
開催時間15時00分-16時00分
発表者本多 淳也 
発表者の紹介東京大学
タイトル雑音付きのソート・ランキング推定における計算論的・情報論的に最適なアルゴリズムについて 
発表の概要
要素ペアを比較する際に一定確率で誤った結果が返される場合において、確率1-p以上でn個の要素を正しくソートする(あるいは上位m この問題において通常のソートアルゴリズムの素朴な拡張はO(n(log n)(log 1/p))の比較回数を要するが、ソートされた集合に対する新規要素の挿入を行ううまいアルゴリズムをn回繰り返すことでO(n log(n/p))の比較回数が達成できることが知られている。
これはオーダーの意味では最適であるが、一方でこのアルゴリズムはlog 1/pの係数に関する情報論的な下限を達成することが本質的に不可能である。
そこで本研究ではオーダーおよびpに関する係数の両方の意味で最適なアルゴリズムについて考える。
また、上記のアルゴリズムの比較回数あたりの計算量が定数オーダーであるのに対し、与えられた比較結果に対して最も確からしい順序を推定する問題はNP困難であり、こちらの問題との関連についても議論する。
開催場所VBL棟 301B
開催時間16時00分-17時00分
発表者小宮山 純平 
発表者の紹介東京大学
タイトル統計的保証のあるエマージングパターンマイニング 
発表の概要
2つのデータセットでの差異が一定以上のパターン(エマージングパターン)を列挙することを考える。ただし、データセットは背後にある真の分布からのランダムな実現と考えると、ある程度の統計的な保証のあるパターンのみがほしい。
各パターン=仮説だと考えると、パターンの列挙は統計的多重(仮説)検定に対応する。多重検定には、誤ったパターンの発見に関して、FWERとFDRと呼ばれる制御すべき目的関数がある。
○FWER制御パターンマイニングに関してTaroneの補正を利用しLAMP[寺田+13,湊+14]と同じ系列のtestableな仮説集合の選択方法の導出を行った。
○FDR制御パターンマイニングに関しては、testableでの仮説集合の選択には
* FDRを制御するBenjamini-Yekutieli法にはTaroneの補正がないため、仮説数を安全に減らす方法がない
* 仮に減らしたとしても、FDRで仮説を棄却できるかどうかは他の仮説に強く依存しており、最も厳密な水準では大して仮説数の枝刈りができない。先に他の仮説を検定しておいて、棄却数の見積もりがほしい。
という困難がある。これらを解決し、FDRにおける準testableな仮説集合の導出を行った。
開催場所VBL棟 301B