Gradient-Free Textual Inversionについて

# はじめに
**Gradient-Free Textual Inversion**は名の通り勾配(Gradient)を用いずにTextual Inversion重みを探索する手法である。
しかしながら実装コードに目を通してもどうやっているのか、なかなか理解が進まなかった。
CMA-ES(共分散行列適応進化戦略)に関するページを検索してようやくどういうことかが分かったので自分の理解を記す。

https://github.com/feizc/Gradient-Free-Textual-Inversion

https://arxiv.org/pdf/2304.05818v1.pdf

# 論文の図
Evolution Strategy(ES、適応進化戦略)を理解せずにこの図を眺めてもおそらく何も理解できないし、Textual Inversion重みをどうやって学習するのかも分からない。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/07cd5238-8a38-b9d0-9d86-5fc024ee604c.png)

# CMA-ES(共分散行列適応進化戦略)
共分散行列適応進化戦略とは適当に平均と偏差と共分散行列$(m,\sigma, C)$から各サンプルを生成し、その各サンプルを任意関数に通してlossを求める。その各サンプルの値とlossの大きさ順の情報だけを使ってサンプリングの平均と偏差、共分散行列$(m,\sigma, C)$を更新するという手順である。

次に**共分散行列**とはある変数組のデータの相関を示す行列である。
平均$0$、標準偏差$1$の正規分布が$N(0,I)$
平均$m$、標準偏差$\sigma$、共分散行列が単位行列$I$ の正規分布が$N(m,\sigma^2 I)$
平均$m$、標準偏差$\sigma$、共分散行列が$C$ の正規分布が$N(m,\sigma^2 C)$

共分散行列は一般には以下の様に書かれます。
$\sigma_x^2,\sigma_y^2$がデータ$x,y$の分散、
$Cov(x,y)$がデータ$x,y$の共分散である。
```math
C=\begin{pmatrix}
\sigma_x^2 & Cov(x,y) \\
Cov(y,x)  & \sigma_y^2
\end{pmatrix}
```
例えば下記のような二次元の適当な**共分散行列**$C$を与えると各分布は二変数間で以下の相関を持つのが見える。

```python
import numpy as np
import matplotlib.pyplot as plt

mean = np.array([1.2, -0.5])
sigma = np.array([2, 0.3])
t = np.deg2rad(30)
C = np.array([[np.cos(t), -np.sin(t)],
              [np.sin(t),  np.cos(t)]])

data = np.random.multivariate_normal(mean, np.diag(sigma)@C, size=200) 

plt.scatter(data[:,0], data[:,1])
plt.show()
```
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/dc097c32-d823-3e99-ba80-40461bbe6c81.png)

# 推定概略図
通常のTextual Inversionはlossの勾配を使ってadd_tokensで追加されたTextEncoderのtoken_embeddingテーブルの重みを学習する。このtoken_embeddingテーブルは1token追加なら$(49408+1,768)$である。ここでlossから誤差逆伝播法を使ってtoken_embeddingテーブル内の追加tokenのTI重みを更新する。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/3c437c14-d214-5293-af15-8fb0ef532c9f.png)
一方のGradient-Free Textual InversionではCMA-ES(共分散行列適応進化戦略)を使ってサンプリング$Q$(次元は256)を与える$(m,\sigma, C)$を最適化する手法である。
一点引っかかる点は$Q$を768次元に変換する$W$は適当に初期化されていて、特に最適化されることはない。
$W$の値が何であれ$Q$を作る$(m,\sigma, C)$を最適化さえすれば$e=e_0+WQ$となる値で$e$が最適化されるという事だが本当にそうなのかはよく分からない。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/88a49972-56b9-5870-74f9-23305860046c.png)

しかし、Gradient-Free Textual Inversionの論文中には下記の数式が示されるくらいで$(m,\sigma, C)$をCMA-ES(共分散行列適応進化戦略)によってどうやって更新していくかに関しては詳細はほとんど書かれていない。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/74e0d415-91d6-8185-17ec-075f5bdc769c.png)

CMA-ES(共分散行列適応進化戦略)について調べれば例えば以下の様な式も見つかる。
ここで$w_i$はlossを昇順に並べた時、総和が1で、lossが小さい順であるほど大きく、ある程度$\lambda$以上大きい順だと0になる重みである。例えば$w_i=\frac{log\frac{\lambda}{2}-\log i}{\Sigma w_i} $
**lossの値自体を全く使わず(lossの大きさ順は使う)に$(m,\sigma, C)$の値を更新する。**
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/a8ec5bdc-b338-9d87-bee1-2bce015dedf2.png)

[ソースコード](https://github.com/feizc/Gradient-Free-Textual-Inversion)についてもcma/evolution_strategy.pyのコードが4861行に対してtrain_inversion.pyのコードが308行であるので、CMA-ESの実装内容が非常に長く、その中身の把握は困難である。


# 参考実装検証
CMA-ESの[参考コード](https://horomary.hatenablog.com/entry/2021/01/23/013508)を元にBeale関数$(1.5-x+xy)^2+(2.25-x+xy^2)^2+(2.65-x+xy^3)^2$の最適化の動作を見た。(参考コード元ではlevi関数の最適化をやっている)
```python
def beale_func(x1, x2):
    return (1.5 - x1 + x1 * x2)**2 + (2.25 - x1 + x1 * x2**2)**2 + (2.65 - x1 + x1 * x2**3)**2

def contor_plot():
    xlist = np.linspace(-40.0, 40.0, 100)
    ylist = np.linspace(-40.0, 40.0, 100)
    X, Y = np.meshgrid(xlist, ylist)
    Z = beale_func(X, Y)
    fig,ax=plt.subplots(1,1)
    cp = ax.contourf(X, Y, Z, levels=[0, 0.1, 0.2, 0.8, 2.0, 4.0, 8.0, 16.0, 32.0, 64.0, 128.0])
    return fig, ax
```

$(m,\sigma, C)$を更新してBeale関数の最小値、x1=3.0, x2=0.5に収束してるっぽい。
![image.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/fc0eae35-c866-2565-72ad-6c7d1b59d2c1.gif)
また開始位置を変えても収束に問題はない。
![image2.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/73cb7375-853c-f015-4a71-ee911dcfdb8d.gif)


# 部分空間次元(subspace dimensionality)
実装コードではGradient-Free Textual Inversionの部分空間次元は256次元である。
これを64次元にすると画像の再現度が落ちるし、512次元や2-wordや3-wordにするとテキストの再現度が落ちる（過学習気味になる？）。また初期化をしておかないと精度が落ちる。
Gradient-Free Textual Inversionの実装(PCAとPrior Norm)は標準のTextual Inversionよりも良い事が示されている。勾配を使わない方が局所最適解に陥りにくいのだろうか？
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/900040e1-6d4e-aafb-a277-b26c7f14b8d8.png)

# まとめ
Gradient-Free Textual Inversionを理解するためには前提としてCMA-ES(共分散行列適応進化戦略)の知識がいる。これは正規分布のサンプリングパラメータをlossの大きさ順から最適化する手法である。これさえ分かっていればCMA-ESで任意関数のlossが最小となる分布$Q$を探すだけなのでそれほど難しくはない。

# 参考:
https://horomary.hatenablog.com/entry/2021/01/23/013508
https://www.jstage.jst.go.jp/article/isciesci/60/7/60_292/_pdf/-char/en