ぱらぱらめくる『Randomized Algorithmsの講義』 - ryamadaの遺伝学・遺伝統計学メモ

サイト
1 Introduction: Randomized algorithms とは乱数を使って何かの推定をする。その推定値に(証明された)確率的上限・下限をつける
2 確率変数の値がどれくらい狭い範囲にまとまっているか:まとまり具合 Concentration of random variablesを示す不等式
- Markovの不等式
- Chernoff bound→こちらにまとめました
  - 独立なランダム変数の和の分布に関する不等式
  - Randomized algorithmsの中心的存在(そのほかにはunion boundsがあるくらい)
  - Bound自体も有用だが、その証明の仕方も一般化することで有用である
  - Chernoff boundがわかりにくいのは、あちらこちらで見かけの違う式が現れて、いったい全体、どれが本物なのかわからないこと…→これをわかりやすく書いているのが、このシリーズのこの文書
3 Chernoff boundを活用する例(ボールを複数のBinに投げ入れ、グラフのMaxCut、負の二項分布)
4 5 負の二項分布を使ってさらに…,分散ネットワーク設計問題での利用
- 負の二項分布
  - k回の成功をおさめるまでに実施しないといけない試行回数の分布
  - とりうる値は0以上無限大なので、Chernoff boundのような閾値設定をして、おおよそこれこれ、というスタンスで扱わないと、扱いきれない分布であるので、Chernoff boundとそれを用いたRandomized algorithmとの対象として好適
  - ランダム・ネットワーク設計、分散型データ保管
6 次元縮減
- 高次元空間の点のノルムとペアワイズ距離とをほぼ維持したまま、低次元空間座標に対応付ける、という次元縮減をしようとする。それが、「ほぼ維持」の「ほぼ」に関してそこそこの「ずれ」程度に収めるようなランダマイズド・アルゴリズム(乱数を要素とする行列を使って高次元から低次元に変換してしまう、という単純なもの)があること、それが不等式で確率的に保証されていること
- Random Projection
7 Streaming, Nearest Neighbor
- Streaming: 次元縮約のランダマイズド・アルゴリズムで小さくした値セットをデータフローについて選び取って保管して、かいつまんで行く
- Nearest Neighbor: 最近接点を見つけるのがNN法だが、あるていどの不正確さを許して『最近接点とみなせる点』を選ぶ。その選び方がぐっと軽ければよい
圧縮センシング
- 減次元ベクトルから元の高次元ベクトルを再作成できるかどうかについての「圧縮センシング」自体についての資料はこちら
  - どうして、 $l_1$ ノルム(斜め線で囲まれた領域)が好都合かとか、それよりももっと軸方向に尖ったノルムが好都合化とかの話や、解の一意性はどうやって保証されているのか、その保証を考えるための零空間特性とか等長変換を少し緩めた制限等長性とかに関する議論から、最終的にRIP定数とかに行き着く文書
- 他方、Randomized algorithmsの適用例として圧縮センシングを扱っている、この記事の対象講義シリーズでは、上記の文書が各種証明で明らかにした事実を用いて、正規乱数行列が作るガウス行列アンサンブルを用いると不等式で範囲が限定された範囲にエラーが収まるように疎ベクトル変換するような行列が見つかる、という話をしている