月報 2023/05 & 2023/06

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

• https://www.cs.bham.ac.uk/~jdk/parego/ParEGO-TR3.pdf

多目的最適化. 目的関数 \(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の推薦システムと多様性について

バンディットで多目的最適化. 報酬は実数一つじゃなくて, 複数の実数を一個のベクトルとしたもの. こっからやるアプローチは大きく２つ.

1. パレートセットを集める
2. 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

• Just a moment...
• 多目的ベイズ最適化のためのMOTPE入門 - Qiita

\(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\) の最適解が現実的に求まる.