がべーじこれくしょん

技術系とかいろいろ

7/21日報

今日も暑かったです。ますますコーラが美味しい季節になってきました。

AOJ-ICPC

  • Hanafuda Shuffle 100 → 解き切りませんでした…

なぜかWAで詰んでます。100なのにまずいです。人権をかけて明日あたりにでも再挑戦します。

読んだ本

最近、友人に薦められて「白と黒のとびら」という本を読み始めました。

この本のあらすじは、ざっと以下のような感じです。

偉大なる魔法使いとその弟子が、次々と出会う奇妙な「遺跡」や奇妙な「言葉」を通して、その秘密に迫っていく。

友人曰く、「気づいたら形式言語理論の基礎が身についていた」とのことです。

私の学科では、形式言語理論を学ぶ「情報数学」という講義があるのですが、できればその講義が始まる前に出会いたかったです。来年の再履修のときに活かしたいと思います(白目)

読み終わって気が向いたら要約を書こうと思います(ここだとネタバレになっちゃうので)

読んだ論文

Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design N.Srinivas et al.

ハイパーパラメータのベイズ最適化について調べていたときに発掘したものなのですが、読み切るには前提知識があまりにも足らなすぎました。

Many applications require optimizing an un- known, noisy function that is expensive to evaluate. We formalize this task as a multiarmed bandit problem, where the payoff function is either sampled from a Gaussian process (GP) or has low RKHS norm. We resolve the important open problem of deriving regret bounds for this setting, which imply novel convergence rates for GP optimization. We analyze GP-UCB, an intuitive upper-confidence based algorithm, and bound its cumulative regret in terms of maximal information gain, establishing a novel connection between GP optimization and experimental design. Moreover, by bounding the latter in terms of operator spectra, we obtain explicit sublinear regret bounds for many commonly used covariance functions. In some important cases, our bounds have surprisingly weak dependence on the dimensionality. In our experiments on real sensor data, GP-UCB compares favorably with other heuristical GP optimization approaches.

雰囲気↓

なんだかよくわからないノイズだらけの関数は評価コストが高すぎるので最適化したい。このタスクを"多腕バンディット問題(multiarmed bandid problem)“とし、ここでは報酬関数をガウス的手法を用いてサンプルし、再生核ヒルベルト空間(Reproducing Kernel Hilbert Space; RKHS)の低ノルム(?)としたときに、なんかいい感じにガウス最適化を用いていい感じになるような手法を紹介しちゃうよ〜

>>>(1ミリも理解できていない)<<<

RKHSについては以下のブログが詳しかったです。

mathetake.hatenablog.com

Lpノルムに関しては↓

http://www-adsys.sys.i.kyoto-u.ac.jp/mohzeki/Presentation/lectureslide20150902-3.pdf

regret boundsのregretの意味を理解するのにすごく時間がかかりました。これは、決定理論における"損失"という意味らしいです。ほう…

決定理論 - Wikipedia

多腕バンディット問題については以下のスライドが超わかりやすかったです。

http://www.it.k.u-tokyo.ac.jp/~honda/FIT_bandit.pdf

いずれにせよちゃんと統計やらないとわからないですね。反省してます。