月報 2023/05, 2023/06, 2023/07
5月の月報書いてなかったし, 6月は多目的最適化についてしか考えてなかった.
Wed 31 May 2023
18:20:20
人生の幸福みたいなものにお金は関わってくるが, 例えば男都内一人暮らし（といった条件付きだが）では年収500万円くらいまでは確かにお金と幸福度は密接に比例関係にあるかもしれない. 条件を変えればこの額はもっと減るだろう. 逆説的に何が言いたいかというと, この額を超えてくるともはやお金は関係ない, ということだ. そしてこの臨界点は思ったほど大した額ではない. この臨界点を超えると, 本人の生活態度だったり交友関係の影響が支配的になってくる.
19:59:58
- 胸の grababble を false にする
- PhysBone/Advanced での制御を試す
-
amakazi のボーン修正?
- BM11 はうまく動くようになった
Wed 07 Jun 2023
19:19:13 多目的最適化
次を読んだ:
目的関数 \(f_i \colon X \to \mathbb R\) が複数 \(f_1, \ldots f_N\) あって, これらの最適化をしたい.
\[f \colon X \to \mathbb R^N\] \[f(x) = (f_1(x), \ldots, f_N(x))\] \[\min_x f(x)\]しょうがないので \(\mathbb R^N\) の上に半順序をつける.
\[x \preceq y \iff \forall x_i \leq y_i\]だと定義する. 例えば \((1,2) \preceq (2,3)\) であるが, \((1,2)\) と \((2,1)\) は比較できない. 比較できないとはつまり, \((1,2) \not\preceq (2,1)\) でもあるし \((1,2) \not\succeq (2,1)\) でもあるということ.
点集合 \(X\) に対してパレートセットとは, 値が極小であるものの集合のこと
\[X^\ast := \{ x \in X \mid \forall x', f(x) \not\prec f(x') \}\]パレートフロンティアとはこの集合が取る値のこと
\[F^\ast := \{ f(x) \mid \forall x \in X^\ast \}\]この集合に属する点及びその値が一種の最適解だと思う. そのような値は一般にはちょうど一つ存在するわけではないので集合として捉えている.
\(F^\ast\) と適当に決めた基準点 \(p\) で包まれる次のような図形を考える.
\[F^\ast_p := \{ q \in \mathbb R^N \mid p \preceq q \preceq f (\exists f \in F^\ast) \}\]その閉包を取って適切な測度で面積（体積）を測る. この値が大きいほど, 最適解（の候補）が多くあるということ.
最後の説明間違ってるかも. モチベーションは, 極小値を取る \(x\) をたくさん見つけることで, その評価として基準点と結んでその体積の大きさを比較するという話かも.
Thu 08 Jun 2023
14:10:40 多目的最適化:ParEGO, Expected Hypervolume Improvement
ParEGO
多目的最適化. 目的関数 \(f \colon X \to \mathbb R^L\) の最小化を考えてる. いくつかの点集合 \(x_1, \ldots, x_N\) についてその値が観測されてるのでブラックボックス最適化するというシチュエーション.
Tchebycheff 関数と称して次の関数を考える. おそらくはチェビシェフ距離の気持ちっぽい. ここで \(\rho\) はハイパーパラメータ. \(\theta\) はランダムにサンプリングされる(!).
\[f_\lambda(x) = \max_j ( \lambda_j f_j(x) ) + \rho \sum_j \lambda_j f_j(x)\]これは結局 \(L\) 次元の目的変数をチェビシェフ距離で一次元に潰したものを最適化しようとしてる.
ParEGO 自体はこれを使ってガウス最適化するアルゴリズム. 普通に進化最適化っぽくてそこは大した事なさそう. \(f\) を \(f_\lambda\) に潰すことと, 毎ステップでその \(\lambda\) をランダムに取り直すことがポイントっぽい.
Expected Hypervolume Improvement
パレート超体積の増加量の期待値を最大化する点を見つける.
Hypervolume indicator を定義する. いわゆるパレート超体積のこと.
有限の点集合 \(P \subset \mathbb R^m\) , 基準点 \(r\) , 適切なルベーグ測度 \(\mu\) . これらがあるときに, \(S = \{ p \in P \mid p \preceq r \} \subset P\) これと \(r\) を頂点にした図形のその測度（超体積）を言う.
Hypervolume Improvement とは, \(P\) には含まれてない点 \(p\) であって \(P\) を \(P \cup \{p\}\) に置き換えると超体積が増えるようなもののこと.
ガウス分布を仮定して, この Improvement の期待値を見積もってこれを最大化する.
18:07:06 多目的最適化の理論と手法
\(\mathbb R^p\) 空間に半順序をつける.
\[x \lt y \iff \forall i, x_i \lt y_i\] \[x \leq y \iff \forall i, x_i \leq y_i\] \[x = y \iff \forall i, x_i = y_i\]関数 \(f \colon X \to \mathbb R^p\) と点 \(x^\ast \in X\) について,
\[\not\exists x \in X, f(x) \lt f(x^\ast)\]なとき, \(x^\ast\) を 弱非劣解 という.
\[\not\exists x \in X, f(x) \leq f(x^\ast) \land f(x) \ne f(x^\ast)\]なとき, \(x^\ast\) を 非劣解 という.
Tue 20 Jun 2023
15:28:34 バンディットで多目的最適化
Spotifyの推薦システムと多様性について
報酬は実数一つじゃなくて, 複数の実数を一個のベクトルとしたもの. こっからやるアプローチは大きく２つ.
- パレートセットを集める
- Scalarisation: 一つのスカラー値に集約してこれを最適化
Spotify の "Bandit based Optimization of Multiple Objectives on a Music Streaming Platform" では後者を取ってる. うーん、つまらん.
最適化したい複数の指標を取り出す. それらの相関関係を見る. いくつかは正の相関があるので, どれかを最適化すればもう一方も勝手についてきそう.
文脈付きバンディット（線形バンディット）をする. 指標（報酬）が \(D\) 個あるとする. 報酬を以下でモデル化する.
\[x = J \theta + \zeta\]- \(x\) : \(D\) 次元報酬
- \(J\) : 文脈の特徴（なんでもいい）
- \(\theta\) : \(\mathbb R^D\) への線形変換
- \(\zeta\) : ノイズ
Generalised Gini Function (GGF)
報酬ベクトルをスカラー値に集約する.
\[G_w(x) = w^T x_\sigma\]-
\(w\) は適当な重みベクトル
- その要素は降順で正値, \(i \lt j \implies w_i \gt w_j \gt 0\)
- \(x_\sigma\) は \(x\) の要素を昇順ソートしたもの
この \(G_w\) を最大化する値はパレートフロンティアに乗る.
Thu 22 Jun 2023
13:39:56 MOTPE
\(X \to \mathbb Y\) ( \(Y=\mathbb R^p\) ) に関する多目的最適化をする. いくつかの観測集合 \(\Omega = \{ (x_i, y_i) \}\) の超体積を最大化するパレートフロンティアを探すことが目的.
ただし予め, \(Y\) 上に適切な基準点を大きい方と小さい方に一つずつ設けておくことで \(Y\) は有界な領域に制限しておく.
EHVI (Expected Hypervolume Improvement) を考える. つまり超体積の増加量を最大にするような点を探索する.
新しい点 \(x'\) を観測したとき \(y' \sim p(y|x)\) が得られると予め見積もられるとき, 超体積の増加量がこれによって期待値として得られる.
\[\mathrm{EHVI}(\Omega + x') = \int_y dy ~ I(\Omega + y) p(y|x') - I(\Omega).\]数式は雰囲気で書いてる. \(I\) は超体積で, それの \(y\) を追加した場合としてない場合との比較をしてる. 超体積 \(I\) は点集合が増えることで広義単調増加なので上の EHVI は必ずゼロ以上.
MOTPE は TPE という手法を他目的最適化 (MO) にアレンジしたもの.
最終的にやりたいことは上の \(p\) を推定すること. 結論としてはカーネル密度推定 (KDE) をやるんだけど, 空間を分割してそれぞれの密度を調べるだけで済ます.
観測集合 \(\Omega = \{(x_i,y_i)\}\) の内の最も良い（他に支配されてない）点の \(y\) だけを集めたものを \(Y^\ast\) とする. これを基準にして空間 \(Y\) を上位層と下位層に分割する.
-
下位層
- \(Y^\ast\) のいずれかの点によって支配される点
-
上位層
- 下位層以外すべて
予め \(Y\) は有界としておいたので下位層と上位層はそれぞれ面積を求める事ができる. その面積の比を用いることで,
\[\gamma = p(y \in Y \mid y が上位層に含まれる)\]という見積もりを行うことにする.
そして次に KDE で \(p(x \mid y)\) を見積もるのだが, \(y\) が上位層に含まれるか下位層に含まれるかどうかだけで見積もってしまうことにする.
-
\(p(x \mid y) =\)
- \(y\) が上位層なら \(\ell(x)\)
- \(y\) が下位層なら \(g(x)\)
これらを周辺化することによって \(p(x) = \gamma \ell(x) + (1-\gamma) g(x)\) を得る. またベイズの定理から \(p(y \mid x) = p(x \mid y) p(y) / p(x)\) 特に \(y\) が上位層にあると分かってるなら, \(p(y \mid x) = \frac{ \ell(x) p(y)}{ \gamma \ell(x) + (1-\gamma) g(x) }\) となる.
これを EHVI の式に代入すると,
\[\mathrm{EHVI}(\Omega + x) = \int_y dy ~ I(\Omega + y) \frac{ \ell(x) p(y)}{ \gamma \ell(x) + (1-\gamma) g(x) } - I(\Omega).\]\(y\) に関するところは定数なので \(C\) と置けば,
\[\mathrm{EHVI}(\Omega + x) = \frac{\ell(x)}{ \gamma \ell(x) + (1-\gamma) g(x) } C\]と置ける. これを最大化するには結局
\[\frac{\ell(x)}{\gamma(x)}\]を最大化すればいいとわかる. これが結論.
結論だけ見たら不自然じゃないし, まあ, はいという感じだが, これで EHVI 最大化になるなら便利.
Mon 26 Jun 2023
18:16:30
男女で遊ぶには付き合わなければいけない. 本当はクラスの人みんなと遊びたいだけなのに.
"Multi-objective Bandits: Optimizing the Generalized Gini Index" 多目的多腕バンディットをやる
問題を Generalized Gini Index (GGI) の最適化として定式化する. GGI は凸なので凸最適化が使える.
腕が \(K\) 本, コストと報酬が \(D\) 次元ベクトル. 腕 \(i\) に対応して確率変数 \(X_i \in [0,1]^D\) が割り当てられている. それぞれの期待値として \(\mu_i = E[X_i]\) っていうのもあるとする. 観測によって得られた平均を \(\hat{\mu_i}\) とする. これは実際の観測値（ベクトル）の平均を取ったもの.
パレート最適化の意味で \(\preceq\) を定める. 観測点の中で極小なものをパレートフロンティアと呼ぶ.
\(x \in \mathbb R^D\) に対して 重みベクトル \(w \in \mathbb R^D\) を決めておいて, GGI を次で定める.
\[G_w(x) = w^t x_\sigma\]ただしここで \(w\) は成分が降順になってること. \(x_\sigma\) は \(x\) の成分を昇順にソートしたもの.
これは \(D\) 次元置換群 \(\mathbb S\) で並び替えたときの最大値になってる.
\[G_w(x) = \max_{\pi \in \mathbb S} w^t x_{\pi}.\]そしてこの関数は区分線形凸関数になってる.
ちなみに \(w\) として適当な値を設定するとオリジナルの Gini Index が得られる. そういう意味で今回のこれはジニ指数の一般化だと言える.
Wed 28 Jun 2023
15:53:01
\(d\) 次元実数ベクトル \(x\) と \(w\) がある. \(x, w\) の成分を自由に並び替えて良い. 並び替えた後の2つのベクトルの内積を考える. 一般性を失わず \(w\) はすでに昇順（単調非減少）に並んでるとして \(x\) だけを並び替えることだけ考えれば良い. 並び替えを \(\pi\) とすると内積は
\[G_\pi(x,w) = \langle \pi(x) , w \rangle\]と書ける. これを最大化したい. \(x\) をやはり昇順（単調非減少）にソートする並び替えが最適解になる.
ところで一般にベクトル \(x=(x_1,x_2,\ldots,x_d)\) について成分の累積和を並べたものを \(L(x)\) と書くことにする. (これに Lonrenz vector という名前をつけてる論文を見つけたが, 全く他に使われてる文献を見ない.)
\[L(x) = (x_1, x_1+x_2, x_1+x_2+x_3, \ldots, x+1+x_2+ \cdots +x_d)\]逆も定義することが出来て,
\[L^{-1}(x) = (x_1, x_2-x_1, x_3-x_2, \ldots, x_d - x_{d-1})\]あと成分の順序を逆転させるもの (reverse) を関数 \(r\) として定める.
\[r(x) = (x_d, \ldots, x_2, x_1)\]次が成り立つ.
\[\langle x , w \rangle = \langle L(r(x)) , r(L^{-1}(w)) \rangle\]素直に式展開すると確かめられる.
\(r^{-1}=r\) なので \(L' = Lr\) とおけば
\[\langle x , w \rangle = \langle L'x , L'^{-1} w \rangle\]といえる.
GGI の多腕バンディット
腕 \(k\) に対して観測して得られた平均 \(\mu_k\) があって, 腕選択は \(G_w(\mu_k)\) を最小化する \(k\) を選択する.
Thu 29 Jun 2023
17:09:38
フレンドに、なんでお前たちはそんなにUnityを触ってる時間があるんだと問い詰められたが、 私は仕事をサボってるだけだし、そういうお前はVRCにログインしてる時間が長すぎるからだ.
18:44:31
"Multi-objective Bandits: Optimizing the Generalized Gini Index" の続き.
腕ごとに平均報酬ベクトルを持っておいて, それぞれの GGI が最小の腕を選択する. 観測値から腕 \(k\) の平均は \(\mu_k\) だとわかる. 基本的には各腕の GGI を最小化するものを選ぶ.
\[\mathop{\mathrm{argmin}}_k ~ G_w(\mu_k)\]ただそれをやると固定の腕を選ぶことになる. 混合戦略を使う.
\[A = \{ \alpha \in \mathbb{\Delta}^K \}\]で戦略を定義する. ただしここで \(\Delta\) は成分の和が \(1\) で非負値なベクトル. \(\alpha_k\) は腕 \(k\) を選択する確率を表す.
そして \(\alpha\) による期待値の GGI を最小化する.
\[\mathop{\mathrm{argmin}}_{\alpha} ~ G_w(\alpha \mu)\]んでもってこの最小化が凸最適化で, しかも線形計画問題になるので \(\alpha\) の最適解が現実的に求まる.
Mon 03 Jul 2023
15:49:20 新しい OLL を考える
次の形の OLL を考える. ここでトップ面を Y (黄色), それ以外の気にしない色を . としてある.
// U 面を上から見た図
// 側面まで描いている
Face {
Y.Y
. .Y. .
. YYY .
. YYY .
...
}
いつもこの形からの手順を覚えていたのだが, VHLS を使うと（少なくとも自分の手癖だと）この上下逆さまの形が出てくる. つまりこう
Face {
...
. YYY .
. YYY .
. .Y. .
Y.Y
}
もちろん \(U_2\) すれば同じなんだが, その手間も惜しみたい. cube で調べてみると, どちらの形からも OLL を完成させるのには 12 手だと出た (初めに \(U_2\) するようなこと無くである).
というわけで後者用の手順を覚えよう. 次の手順を見つけた. ここで \(-\) は自分の中で一息付くための区切りを表す (電話番号のハイフンのようなもの).
\[RU_2 R'U' - L'U_2 - RUR'U'_2 - L\]おなじみのセクシームーブ ( \(RUR'U'\) ) の少し変形が二度出現しているというのと, はじめの \(RU_2 R'U'\) をした直後にある \(ufl\) と \(uf\) の２つの動き方を見れば中盤の動かし方が覚えられる.
ところでこの手順, ぱっと見, 交換子の形式になってそうに見える. 見えない? まあ, なっていないわけだけど.
Mon 10 Jul 2023
12:58:06
勉強するもの
- two.js
- git worktree
23:50:58
ICFPC に出てた. Jockie Music という discord bot を入れて, みんなで同じ音楽を（半強制的に）聞くのが楽しかった. 山登り/焼きなましくらいは2日目か前半かのあいだまでに試しておくべきだった. 効果があるかどうかは分からなくても典型的でとりあえず出来ることは, やろう. 結局それは, 他のソルバーの出力をもらって 1% 程度改善するくらいの効果としてしか利用出来なかった.
Wed 12 Jul 2023
14:20:39
子供の頃から比較的本を読むのは好きだったし漫画はもちろん好きだったし, 中学の時はテレビ見て夜はラジオばっかり聞いてたし, 大人になったらずっとインターネットしてる.
先週から, 名取さなが毎週30分のラジオを持つようになったので, 本当に久しぶりにラジオを押し入れから引っ張り出してきた. Androidアプリのradikoでも聞いてみたが, 音がクリアすぎてなんか嫌だな, になった. 時々ノイズが入って, 手で本体を覆うと音がクリアになるこの感じが良い. カラスは黒いものだと学んで育ってきたので白色をしてたらなんか嫌なんだよね.
私が中学生のときに手に入れて今でもずっと持ってるラジオ. ICF-T45 っていうんだけど, もうソニーのページにも載って無くて,
ヨドバシにはページが見つかった. もちろん売られてないけどね.
後継機の ICF-T46 の情報はまだ比較的見つかる.
こちらは Amazon でなんと24,800円で売られている. そんなバカな.
もうこれもとっくに生産してないのでしょうがないんだけど.
この小ささと軽さででかいスピーカーが内蔵していて, アホほど電池持ちも良くて, なにより手に入れてからもうすぐ20年経つのに全く問題なく使えてる頑丈さがある. そういえばケースが付属してたような記憶もあるが, 中学生の私は, なんだか気に入らなくて捨てた.
余計な, 液晶ディスプレイやらボタンやらつけないで, これをそのままもう一回作ってくれれば, 防災グッズとしてもう一個買っていいかなと思ったんだけど.
今持ってる ICF-T4 を防災バッグに入れることにして, 普段家で使う用にはポケットサイズでなくていいので無難な機種を持つことにする.
Tue 25 Jul 2023
14:24:05
単３形乾電池を手で持つたびに、それを飲み込んだときの、喉を通る感覚を思い出す。 そんな思い出は無いのに。
Thu 27 Jul 2023
12:22:00
夢日記。少しえずいたら乾電池が口から出てきた。
Sat 29 Jul 2023
20:40:48
秋葉原のヨドバシカメラに行って, 実際に視聴したりモノを見て買うことを決心して, yodobashi.com を開いてたら店員が話しかけてきた. 店頭で買ったほうが嬉しいですか？ と聞くと, できればここで買ってほしいなあと言われた. まあそれはそうだと思うんで, 値段もどちらで買っても同じだし, 送料も無料だしで, 試しに店頭で買うことにした. すると何やらアンケートが始まって私がSIMを二枚持ってるからといって,
今この場でヨドバシポイントをいくらいくら手に入れて帰ることができるんですよ
といった本題になかなか入らない回りくどい言い方をするものだから笑ってしまった. SIM の話から入ったので乗り換えの話なのは丸見えだった. 2つともを Y!Mobile に乗り換えないか, という. わざわざ2つのSIMを持っていて, それも別々な回線にしてるような人間が, その両方を Y!Mobile にするだなんて, よくも考えたものだ.
- TODO 次からは素直に yodobashi.com で買うこと.
今日は朝からvketに行った. 10時からスタートなので9:30に家を出るぞと思ってたのに9:30に目がさめた. 10時過ぎに家を出て秋葉原行のバスに乗った. 1030くらいに到着, ちょうど開会式が始まったくらいだったのでちょうどよかった. 今日は予約に成功したトークイベントはないので, 企業の展示だけを一通り見た. SONY のブースは長蛇の列のくせにエンジニア一人が説明をしていて, そしてその人が, こちらがいくらでも質問したら何でもかんでも教えてくれるものだから, そりゃ長蛇の列になるわ. さすがにと思ってこちらから打ち切ったが, いくらでもまだ話せそうな人で良かった.
謎解きイベントは秋葉原の中を歩き回らされたが, 実は実際に歩かなくても十分推測すればほとんどすべて屋内で事足りた. それは解いた後だから言えることなんだけども.