最適化を考察する

これは誇れることではありませんが、私は最適化を深く学んだことがありません。もちろん、AdamとAdaGradの違いは知っていますし、L-BFGSを一度使ったこともありますが、L∞L^\inftyL∞連続関数の双対空間や収束について話し始めると、少しぼんやりしてしまいます。どういうわけか、私の頭の中ではその多くが少し時代遅れに思えていました。勾配降下法がすべてであり、実際には事前学習済みモデルを使う時代に、制約付き凸関数の最適化について学ぶ必要があるのでしょうか？それは、最も安価なダイエットを作るために使われていたものではなかったでしょうか？退屈です！さて、今日のブログでは、タンパク質バインダー設計に関連する私が取り組んでいる興味深い問題の文脈で、私の最適化の盲点について少しお話ししたいと思います。何かを行うための最初の方法は、めったに最善ではありません。ここでは、その具体的な例について議論します。もしあなたが私と同じように最適化の専門家でないなら、この投稿から何か役立つことを学んでいただけると幸いです。もしあなたが専門家なら、私の無知を大いに笑ってください！ セットアップ では、どのようなセットアップでしょうか？kカテゴリーを持つカテゴリカル確率分布があり、各カテゴリーの確率はベクトルx∈Rk\mathbf{x}\in\mathbb{R}^kx∈Rkで与えられるとします。x\mathbf{x}xが有効であるためにはいくつかの制約があります。確率は正規化されている必要があります。∑i=1kxi=1\sum^{k}_{i=1} x_i = 1∑i=1k​xi​=1。そして、確率は0以上である必要があります。xi≥0 ∀i∈{1,⋯ ,k}x_i \geq 0 \ \ \forall i \in \{1, \cdots, k\}xi​≥0 ∀i∈{1,⋯,k}。我々には、確率ベクトルを入力として実数を出力する非凸関数fffがあります。この関数を最小化するx\mathbf{x}xを見つけたいのです。x∗=argminx∈Δf(x)\mathbf{x}^{*} = \text{argmin}_{\mathbf{x}\in\Delta}f(\mathbf{x})x∗=argminx∈Δ​f(x)。我々のセットアップでは、勾配∇xf\nabla_\mathbf{x} f∇x​fを計算できると仮定しますが、勾配の評価、そして関数自体の評価は計算コストが高いです。 タンパク質関連の余談 これは、de-novoバインダー設計における「幻覚」の問題の簡略版です。ここでx\mathbf{x}xはk=20k=20k=20個のアミノ酸の分布を表し、fffはAlphafoldのようなフォールディングモデルで、L個のアミノ酸分布のシーケンス（位置特異的スコアリング行列（PSSM）と呼ばれる）を入力として受け取ります。我々は、最高のフォールド（ipSAEのような何らかの指標に従って）を与えるシーケンスを見つけたいのです。この場合、fffへの入力は、各列が確率ベクトルである行列X∈Rk×L\mathbf{X} \in \mathbb{R}^{k \times L}X∈Rk×Lになります。 最初の試み このような問題、つまり制約付きで何かを最適化する必要がある問題を見たとき、私の最初の本能は、制約について心配する必要がないように問題を再パラメータ化し、「通常の」メソッドをすべて使用しようとすることです。基本的に、x\mathbf{x}xを制約のない他のいくつかのパラメータの関数として書き換えたいのです。そうすれば、それらを最適化できます。この場合、xi=softmax(ℓ)i=eℓi∑j=1keℓj \mathbf{x}_i = \text{softmax}(\mathbf{\ell})_i = \frac{e^{\ell_i}}{\sum^{k}_{j=1} e^{\ell_j}} xi​=softmax(ℓ)i​=∑j=1k​eℓj​eℓi​​と書けます。ここで、ℓ∈Rk\ell\in \mathbb{R}^{k}ℓ∈Rkをロジットと呼びます。任意のℓ\mathbf{\ell}ℓに対して、出力x\mathbf{x}xは、前に設定した制約を満たす有効な確率ベクトルであることが保証されていることに注意してください。完璧です！問題解決です！これで、ℓに関する勾配をとり、何らかの勾配降下法を実行することで、ℓ∗=argminℓ∈Rkf(softmax(ℓ))\mathbf{\ell}^{*} = \text{argmin}_{\mathbf{\ell}\in \mathbb{R}^{k}}f(\text{softmax}(\ell))ℓ∗=argminℓ∈Rk​f(softmax(ℓ))を見つけ、x∗=softmax(ℓ∗)\mathbf{x}^* = \text{softmax}(\ell^*)x∗=softmax(ℓ∗)を得ることができます。これはすべて理にかなっており、以前なら私にとって一件落着だったでしょうが、他にも方法があり、それらの方法は興味深いことが判明しました！ シンプレックス 少し立ち止まって、この問題の構造についてもう少し考えてみましょう。最初に設定した制約を満たすx\mathbf{x}xの空間には、特殊な名前があることがわかります。それは確率シンプレックスΔk−1\Delta^{k-1}Δk−1であり、x∈Δk−1\mathbf{x} \in \Delta^{k-1}x∈Δk−1と書くことができます。確率シンプレックスは、非負性と正規化の両方が満たされるk−1k-1k−1次元の空間領域です。k=3k=3k=3でカテゴリーA、B、Cという具体的な例を考えてみましょう。2-シンプレックスは、(1,1,1)(1, 1, 1)(1,1,1)方向に対して垂直に配向した三角形の領域で、このような形をしています。 3Dおよび2Dの2-シンプレックス。左側はk=3k=3k=3の全次元における領域を示し、右側は2Dの「上から見た」図を示しています。シンプレックスの頂点は、1つのカテゴリーが確実である点です。面の上では、カテゴリーの1つは寄与しません（例えば、A/C面ではBは寄与しません）。私たちの最適化問題は、このシンプレックス上に存在するfffの最小値を見つけることに帰着します。 あなたは射影しています 考えられる最も単純なことを試したらどうなるか考えてみましょう。シンプレックス上の点xt\mathbf{x}_txt​から始め、勾配∇xf(xt)\nabla_\mathbf{x} f(\mathbf{x}_t)∇x​f(xt​)を計算し、勾配降下法の一歩を実行しようとします。xt+1=xt−η∇xf(xt)\mathbf{x}_{t+1} = \mathbf{x}_t - \eta\nabla_\mathbf{x} f(\mathbf{x}_{t})xt+1​=xt​−η∇x​f(xt​)。おおよそ4つのことが起こりえます。 1. 勾配が1=(1,1,1)\mathbf{1}=(1, 1, 1)1=(1,1,1)に垂直でない場合、シンプレックス領域の「上」または「下」にステップしてしまいます。この場合、すべての確率に一度に加算することになり、正規化を破るため許されません。 2. 勾配は1\mathbf{1}1に垂直ですが、三角形の領域の「外側」にステップしてしまい、いずれかの座標が負になります。 3. 1.と2.の両方をひどく間違ってしまいます。 4. 1.も2.も起こらず、シンプレックス上に留まります🥳 したがって、一般的には、シンプレックスから外れて、無効な領域に到達することになります。実際、勾配の1\mathbf{1}1に垂直な成分のみを計算し、その方向にステップするだけで、ケース1.をかなり簡単に回避できます。これは、勾配成分の平均を引くことで行うことができます。1これ以降、勾配は常に中心化されていると仮定します。これにより、生確率に勾配降下法を適用する唯一の問題はケース2.、つまり有効な領域の外側にステップしてしまうことになります。これがどのように見えるかを示します。 2-シンプレックス上のPGDの1ステップ。黒い矢印は生の勾配降下ステップを表します。次のステップに進むためには、有効な点を見つける必要があります。これを行うには、ステップのシンプレックスへの射影を計算します。つまり、目的の生の勾配ステップに最も近いシンプレックス上の点を見つけます。この射影操作は赤い点線の矢印で表され、最終的なステップは黒い点線の矢印で与えられます。このプロセスは射影勾配降下法（PGD）と呼ばれ、ある意味では、最初の再パラメータ化ソリューションよりも概念的にシンプルです。xxxを最適化したい場合、GDを実行し、間違った場合はいつでも修正します。PGDの1ステップは次のように書くことができます。xt+1=ΠΔk−1[xt−η∇xf(xt)] \mathbf{x}_{t+1} = \Pi_{\Delta^{k-1}}[\mathbf{x}_t - \eta\nabla_\mathbf{x} f(\mathbf{x}_{t})] xt+1​=ΠΔk−1​[xt​−η∇x​f(xt​)]。ここで、ΠΔk−1\Pi_{\Delta^{k-1}}ΠΔk−1​はk−1k-1k−1シンプレックスへの射影演算子です。射影の計算は実際には自明ではありませんし、ここでは詳細には触れませんが、いくつかのクールなトリックを使ってO(k)\mathcal{O}(k)O(k)時間で行う方法があります。これについては、'08年のこの洗練されたICML論文で読むことができます。基本的には、勾配の計算コストと比較して非常に高速です。上記の単純な2Dケースから高次元にスケールアップすると、必ずしも直感的ではないいくつかの点に注意する価値があります。第一に、シンプレックスの次元が増加するにつれて、勾配ステップでシンプレックスから外れる確率はどんどん大きくなります。シンプレックス内のより多くの点がエッジに近くなります。いつでも