« December 2009 | Main | February 2010 »

2010.01.26

SODA2010 ALENEX2010@テキサス

先日までTexas Austinで開催されていたALENEX2010SODA2010に参加してきました。
一緒に行った吉田さんの感想もありますのでそれも参照してください

まず一応自分のALENEXでの発表資料は以下にありますので参照ください
"Conjunctive Filter: Conjunctive Filter: Breaking the Entropy Barrier"論文、発表スライド(pptx pdf)

他に聞いた中で印象的だったものを下に書いてみます。ただ、大部分の発表は私の基礎知識が足りなくてついていけませんでした。残念

昨年末の研究開発セミナーでも紹介しましたが、簡潔木とよばれる限界まで圧縮した上で(ノード数がnの時2n+o(n) bit)様々な木上での操作(親を辿る、子を辿る、共通祖先を探すなど)のあらゆる操作を統一された操作の組み合わせで実現するというものの理論的な話と、その実際の実装の話
実際に実装した人にいろいろ伺ってみましたが、実際に相当簡単だったらしい
ソースコードは手に入りますので(libcds)、実際にみてみるのが早いかもしれません。

ANALCOの招待講演はニュートン法の最新の話(slide pdf)
ニュートン法は最適化法で最初に出てくる方法ですが、その改善の話とかもろもろの話。衝撃的だったのが様々なCombinatorial Object(集合、文字列、二分木)を母関数を使って表し、この母関数を操作することで解析を行うというAnalytic Combinatoricsというすさまじい世界の紹介。Sedgewickが共著で800pの本がただで手に入るので興味のある方はぜひ読んでみると良いと思います。私モちょっと読んでみます

Partial SumsDynamic Membershipなどのクエリを情報理論的限界のスペースで実現するときの計算量の下限を示したり、あとは高次元でのなどを実現する論文などがありました。

Best Paperは非有効グラフの巡回セールスマン問題の多項式時間近似がO(log n)からO(log n / log log n)に改善されたというもので、それを実現するためには結構な大きさのステップを5つぐらい踏んで実現するというものでした。途中で最大エントロピーの話がでてきてこんなのも使うのかと思いました。

SODAの招待講演ではGoogle TV Adの中で行われているオークションのロジックの話。このGoogle TV Adとよばれるサービスでは100チャンネルぐらいのTVのCMの内容を毎日オークションで決めるというもので、何が配信されるかはそれぞれのCMの入札額などで決定されます(Google Adwordsと同じように)随分進んだ話しだなぁと。で他のところで全く同じのを話しているらしくその資料が手に入ります(pdf slide).話しがうまくオークションの専門でない私でも楽しめました。あまり不正確な話しでなんですが、オークションの仕組みは、「入札者が自分が実際に払いたいという価格を入札するのが入札者にとっても最適な戦略」となるようになるべきで、さらにどの価格もそれ以上動かしても誰も得しない状況(パレート最適)をどう実現するか(第二価格入札とかWalrasian均衡とか)という話でした。
実際の運用では様々な制約がさらに入るため、基本的には簡単なオークション決定アルゴリズムが使われているそうです。

次の招待講演は最近流行っているCompressed Sensingの話で、これまでと今の最新の話。未知の変数集合があって、それに関する線形方程式の数がそれよりはるかに少ない場合でも未知の変数の多くが0であるという事実がわかってさえすれば、L1ペナルティをかけて復元することができる。行列の要素が未知の場合でも同様で、この場合はTraceノルムを最小化するように最適化を行えば良いという話。

---
残りの時間は他の出席者とディスカッションして情報収集したり、自分の博士公聴会の準備したりとかでそこそこ忙しかった。観光は州議事堂ぐらいでした。テキサスバーガーはファーストフードで食べました。

また、ビジネスミーティングで、SODA2012の開催地として京都がきまったのですが、そのときの決戦投票(最後はバルセロナとの一騎打ち)が大接戦で盛り上がったのが印象的です。

| | Comments (5) | TrackBack (0)

« December 2009 | Main | February 2010 »