最適化を考察する
Reflecting to optimise (magnusross.github.io)
要約
この記事では、筆者が最適化に関する知識の不足を認めつつ、タンパク質バインダー設計に関連する興味深い問題を例に挙げ、最適化手法について考察しています。特に、制約付き最適化問題に対する再パラメータ化アプローチと、より概念的にシンプルな射影勾配降下法(PGD)という2つの異なるアプローチを比較し、それぞれの利点と課題について議論しています。最終的には、PGDが計算コストの面で有利である可能性を示唆しています。
全文翻訳
最適化のためのリフレクション
これは誇れることではありませんが、私は最適化を深く学んだことがありません。もちろん、AdamとAdaGradの違いは知っていますし、一度だけL-BFGSを使ったこともあります。しかし、人々がL∞連続関数の双対空間や収束について話し始めると、私は少し上の空になってしまいます。なぜか、私の頭の中では、それらの多くが少し時代遅れのように思えたのです。それが何を意味するのかは分かりませんが。あらゆるものに勾配降下法を使い、あるいは実際には事前学習済みモデルを使う時代に、なぜ制約付き凸関数の最適化について学ぶ必要があるのでしょうか?それは、例えば、できるだけ安いダイエット食品を作るために使われていたようなものではないでしょうか?退屈です!
さて、今日のブログでは、タンパク質バインダー設計に関連する興味深い問題の文脈で、私の最適化における盲点について少しお話ししたいと思います。物事を行う最初の方法は、決して最善ではありません。ここでは、その具体的な例を議論します。もしあなたが私と同じように最適化の専門家でないなら、この投稿から何か役立つことを学んでいただければ幸いです。もし専門家であれば、私の無知を笑っていただいても構いません!
セットアップ
さて、セットアップはどうなっているのでしょうか?k個のカテゴリを持つ離散確率分布があり、各カテゴリの確率はベクトル x∈Rk で与えられるとしましょう。x が有効であるためには、いくつかの制約があります。
- 確率は正規化されている必要があります: ∑i=1kxi=1
- 確率は0より大きくなければなりません: xi≥0 ∀i∈{1,⋯,k}
私たちは、確率ベクトルを入力として受け取り、実数を出力する非凸関数 f を持っています。私たちは、この関数を最小化する x∗ を見つけたいのです: x∗=argminx∈Δf(x)。私たちのセットアップでは、勾配 ∇xf が計算できると仮定しますが、勾配の評価、そして関数自体の評価は計算コストが高いです。
タンパク質関連の余談
これは、de novo バインダー設計における「ハルシネーション」問題の単純化されたバージョンです。ここで x は k=20 個のアミノ酸の分布を表し、f は Alphafold のような折り畳みモデルで、位置特異的スコアリング行列(PSSM)と呼ばれる、これらのアミノ酸分布の L 個のシーケンスを入力として受け取ります。私たちは、最高の折り畳み(ipSAE のようなメトリックによる)を与えるシーケンスを見つけたいのです。この場合、f の入力は行列 X∈Rk×L となり、各列は確率ベクトルです。
最初のアプローチ
制約付きで何かを最適化する必要があるこのような問題を見たとき、私の最初の直感は、制約を気にする必要がないように問題を再パラメータ化し、「通常の」メソッドをすべて使用できるようにすることです。基本的に、制約のない他のパラメータの関数として x を書き直したいのです。この場合、次のように書くことができます。
xi=softmax(ℓ)i=eℓi∑j=1keℓj
ここで ℓ∈Rk をロジットと呼びます。任意の ℓ に対して、出力 x は常に有効な確率ベクトルであることが保証され、先に設定した制約を満たします。完璧です!問題解決です!これで、ℓ の勾配を取り、何らかの勾配降下法を実行して ℓ∗=argminℓ∈Rkf(softmax(ℓ)) を見つけ、x∗=softmax(ℓ∗) を得ることができます。これはすべて理にかなっており、過去の私ならこれで一件落着でしたが、他の方法もあり、それらは興味深いのです!
シンプレックス
一歩立ち止まって、この問題の構造についてもう少し考えてみましょう。最初に設定した制約を満たす x の空間には、確率シンプレックス Δk−1 という特別な名前があることが分かりました。そのため、x∈Δk−1 と書くことができます。確率シンプレックスは、非負性と正規化の両方が満たされる空間の k−1 次元の領域です。カテゴリ A, B, C の k=3 の具体的な例を考えてみましょう。2-シンプレックスは、(1,1,1) 方向に垂直な三角形の領域であり、次のような見た目になります。
[画像: 2-シンプレックスの 3D および 2D 表示。]
2-シンプレックスの 3D および 2D 表示。
左側には k=3 次元の完全な領域を示し、右側には 2D の「真上から見た」ビューを示します。シンプレックスの頂点は、1つのカテゴリが確実である点です。面では、カテゴリの1つが寄与しません(例: A/C 面では、B は寄与しません)。私たちの最適化問題は、このシンプレックス上にある f の最小値を見つけることに帰着します。
プロジェクションしている
私たちが考えられる最も単純なことを試した場合に何が起こるかを考えてみましょう。シンプレックス上の点 xt から開始し、勾配 ∇xf(xt) を取り、勾配降下法の一歩を実行しようとします: xt+1=xt−η∇xf(xt)。約4つのことが起こり得ます。
- シンプレックス領域の「上」または「下」にステップしてしまう。これは、勾配が 1=(1,1,1) に垂直でない場合に起こります。この場合、すべての確率を同時に加算することになり、正規化が破れるため許可されません。
- 勾配は 1 に垂直だが、三角形の領域の「外側」にステップしてしまう。これは、座標の1つが負になることを意味します。
- ひどい間違いを犯し、1 と 2 の両方を行う。
- 1 も 2 も行わず、シンプレックス上に留まる 🥳
したがって、一般的にはシンプレックスから外れて無効な領域に到達してしまいます。勾配の 1 に垂直な成分を計算し、その方向にステップするだけで、ケース 1 を pretty easily 回避できることが分かりました。これは、勾配成分の平均を引くことで行えます。[1] これ以降、勾配が中心化されていると常に仮定します。これにより、生の確率に勾配降下法を適用する際の唯一の問題は、ケース 2、つまり有効な領域の外側にステップしてしまうことになります。それがどのように見えるかの例を以下に示します。
[画像: 2-シンプレックス上での PGD の1ステップ。]
2-シンプレックス上での PGD の1ステップ。
黒い矢印は生の勾配降下ステップを表しています。次のステップを実行するためには、有効な点を見つける必要があります。これを行うために、ステップをシンプレックスに射影します。つまり、目的の生の勾配ステップに最も近いシンプレックス上の点を見つけます。この射影操作は赤い破線矢印で表され、最終的なステップは黒い破線矢印で与えられます。このプロセスは、最初の再パラメータ化ソリューションよりも概念的に簡単な意味で、「射影勾配降下法」(PGD)と呼ばれます。xx を最適化したい場合は、GD を実行し、間違った場合はいつでも修正します。PGD の1ステップは次のように書くことができます。
xt+1=ΠΔk−1[xt−η∇xf(xt)]
ここで ΠΔk−1 は k−1 シンプレックスへの射影演算子です。射影の計算は実際には簡単ではなく、ここでは詳細には触れませんが、いくつかのクールなトリックを使用することで O(k) 時間で実行する方法があります。これは、この 2008 年のクラス ICML の論文で読むことができます。基本的に、勾配の計算コストと比較して非常に高速です。
上記の単純な 2D ケースから高次元にスケールアップした際に、直感的でないかもしれないことがいくつかあります。まず、シンプレックスの次元が増加するにつれて、勾配ステップでシンプレックスから外れる確率はますます大きくなります。シンプレックス内のより多くの点が辺の近くにあります。シンプレックスから外れるたびに、少なくとも1つの座標がゼロに設定される面に射影されます。高次元では、ますます低い次元の面に射影される可能性が高くなり、結果としてスパースなステップになります。簡単なシミュレーションを実行し、頂点の1つからランダムな方向のステップを取ると、2D ではシンプレックス内に戻る確率は 0.17 です。k=9 では約 10⁻⁷、k=20 では実質的に 0 です。基本的に、高次元での PGD はスパースな解を生成する傾向があり、最適化が進むにつれてよりスパースになります。これは覚えておくべき興味深く有用なことです。
ミラーを見る
制約のない実数から確率を得るためにソフトマックス関数を適用することは、機械学習において非常に一般的な操作です。そのため、最初のセクションの再パラメータ化は自然に感じられますが、一歩立ち止まってその正当性を考える価値があります。非負性/正規化を維持する別の関数を使用しないのはなぜでしょうか?ここではさまざまな楽しいことを行うことができます。f が非凸であることを覚えておく必要があります。異なる変換を使用すると、最適解を見つけられない可能性が高いため、最適解が完全に異なる結果になる可能性があります。そのため、変換の選択は実際には非常に重要です。この選択に数学的な肉付けをするには、追加の仕組みが必要になります。この場合、それは興味深いことに「ミラー降下法」と呼ばれるものです。数学が得意な方は、これらの講義ノート(第17章)を読むことができます。非常に明確です。私は要点を伝えようとします。
標準的な勾配降下法で実際に行われていることは何でしょうか?勾配ステップを取るとき、現在のイテラート xt の局所的な近傍が線形関数(一次テイラー近似)でよく近似できると仮定しています。ステップを取るときは、この近似を最小化したいのです。しかし、それをただ行うと無限に到達してしまいます。なぜなら、線形関数には最小値がないからです。そのため、近傍にとどまるように追加のペナルティを導入する必要があります。各ステップで、次のことを最小化したいのです。
argminx∈Rk[f(xt)+η⟨∇f(xt),x⟩+12∣∣x−xt∣∣2]
これを x について微分してゼロに設定して最小値を見つけると、次のようになります。
η⋅∇f(xt)+(x−xt)=0 ⟹ xt+1=xt−η⋅∇f(xt)
したがって、各ステップの最適解は標準的な勾配降下法になります。賢い方は、「待てよ?なぜ L2 ノルムなんだ?その正当性は?」と思うかもしれません。さて、読者諸君、それはもっともな質問です。そして実際、美しいのは、(いくつかのルールに従えば)ここで異なるペナルティを選択し、異なるアルゴリズムを生成できることです。ここで選択できるペナルティのクラスは「ブレグマンダイバージェンス」と呼ばれます。厳密に凸な関数 h に対して、点 y と x の間のブレグマンダイバージェンスは、点 y における h の値と、点 x で取られた h の線形近似との差を測定します。
Dh(y∣∣x)=h(y)−h(x)−⟨∇h(x),y−x⟩
これは、この便利な可視化(講義ノートから私が再描画したもの)を見ると、おそらくより明確になるでしょう。
[画像: 1次元関数に対するブレグマンダイバージェンスの可視化。]
1次元関数に対するブレグマンダイバージェンスの可視化。
ここでブレグマンダイバージェンスは青色です。h(x)=12∥x∥² を使用すると、二乗 L2 距離 12∥x−xt∥² が戻ってきます。一般の場合、各ステップで次のことを解決しようとしています(定数項を省略)。
xt+1=argminx∈Δk−1[η⋅⟨∇f(xt),x⟩+Dh(x∣∣xt)]
同様に微分してゼロに設定すると、(少しいじると)次のようになります。
xt+1=(∇h)⁻¹(∇h(xt)−η∇f(xt))
おそらく、このすべては何のためにあるのか、そしてなぜミラーがセクションタイトルにあるのか(後で説明します)疑問に思っているでしょう。そこで、少し動機付けとなる例を見てみましょう。もし、私に付き合ってくれるなら、正規化されていない負のエントロピー関数 h(x)=∑ixilogxi−xi をブレグマンダイバージェンスで使用したらどうなるでしょうか?すると、次のようになります。
Dh(y∣∣x)=∑iyilog(yixi)=DKL(y∣∣x)
ここで、勾配の線形性と確率ベクトルの正規化を適用しました。ブレグマンダイバージェンスは、この場合 KLダイバージェンスに等しくなります!この勾配更新は、f の線形近似を最小化し、同時に更新が KL 項で近くなるようにすることを意味すると解釈できます。これは興味深いことです。なぜなら、確率に負のエントリが含まれないようにできるからです(それらは無限の KL を持つでしょう)。そのため、シンプレックスの制約の1つが自動的に満たされます。残念ながら、このステップは自動的に正規化されません。正規化を確実にするために、シンプレックスに射影します。これは、正規化されていないベクトルに最も近い点を KL ダイバージェンスの点で探すことになります。これは、ベクトルの合計で割る、つまり正規化することと同等であることが判明しました。
∇h(x)=[logx1,⋯,logxk] であることに注意してください。したがって、更新方程式は、「確率空間」からロジットへの勾配更新を適用し、次に ∇h⁻¹ で確率空間にマッピングし直すものとして解釈できます。この更新が、元のソフトマックス再パラメータ化(追加の正規化項 ∇h⁻¹ はまさにソフトマックスです)と非常に似た更新を与えることがわかります。しかし、1つの重要な違いがあります。ロジット空間の勾配ではなく、確率空間の勾配を使用しているのです。これは、更新がソフトマックスのヤコビアンの係数で異なることを意味します。
∇ℓf=(diag(x)−xx⊤)∇xf
頂点付近のケース、例えば x=[1−(k−1)ϵ,ϵ,⋯,ϵ] で小さな ϵ の場合を考えると、各エントリが O(ϵ) となるヤコビアンが得られるため、これが問題となる理由がわかります。これは勾配が消滅することを意味し、最適化の軌跡が頂点付近で「スタック」する可能性があります。悪いことです!
さて、ソフトマックス再パラメータ化に関連する、より理論的に根拠のある更新ルールを確立しましたが、使用する特定の勾配に重要な違いがあります。実際、理論はさらに深くなります。ここではあまり詳細には触れません。それは、学部時代の物理学の講義で場の理論を理解できなかったという不快なフラッシュバックを与えるからです。しかし、ポイントは、よく考えると、勾配ベクトルをパラメータベクトルに加算するのはかなり奇妙だということです。次元解析を少し適用すると、x の単位は [x] であり、∇f の単位は [f]/[x] なので、2 つは η が秘密裏に単位 [x]²/ [f] を運んでそれらを変換しない限り加算できません。実際には無次元であるべきです。これは、勾配が実際にはベクトルではなく、「余ベクトル」[2] であり、パラメータが存在する「原始空間」とは異なる「双対空間」に住んでいるためです。基本的に、勾配を線形関数と見なすことができ、ベクトル(内積付き)に適用するとその方向の変化率が得られるという考え方です。そのようなすべての線形関数が双対空間を構成します。
この難解な理論が、上記の更新方程式を理解するのに役立つことがわかります。h をミラーマップと呼ぶと、∇h は私たちを双対空間にマッピングし、そこで勾配更新を適用し、次に (∇h)⁻¹ は更新を原始空間にマッピングし直します。逆マッピングは制約領域の外に出る可能性があるため、最終的な射影を適用して更新を取得します。私の素敵な図から、なぜミラー降下法と呼ばれるのかがわかります。双対空間で降下しており、それは実空間を「ミラーリング」しています。
[画像: ミラー降下法の1ステップ。]
ミラー降下法の1ステップ。
h が厳密に凸であるということは、勾配とその逆の両方が全単射であることを意味します。そのため、原始空間での「前方」は常に双対空間での「前方」に対応します。h が凸であると定義するとき、それはあるノルムに対してです[3]。このノルムが空間の幾何学的構造を決定します。負のエントロピーミラーマップは L1 ノルムに関して凸であり、これにより原始空間の幾何学的構造が定義されます。すると、双対空間は L∞ ノルムを持つことがわかります。
ここでさらに混乱する部分ですが、双対空間の形式はベクトル空間のノルムに依存します。L2 ノルムを持つユークリッド空間は実際には自己双対であることがわかっています。そのため、双対空間と原始空間は同一です。したがって、標準的な勾配降下法の場合、勾配をパラメータベクトルに加算しても問題ありませんが、これは L2 ノルムの自己双対プロパティのためだけです。前のセクションで議論した PGD メソッドは、実際にはミラー降下法の一種ですが、ミラーの部分は実際には何もしていません。すべての重い作業は、シンプレックスへの最終的な射影によって行われます。負のエントロピーミラーマップの場合、射影は(単なる正規化)はるかに簡単です。なぜなら、KL ダイバージェンスは確率を尊重するからです。
まとめ
シンプレックス上の最適化問題に対する3つの異なるアプローチについて議論しました。ソフトマックスロジットでの勾配降下法、確率での射影勾配降下法、そして負のエントロピーミラーマップを使用したミラー降下法です。言うまでもなく、他にも多くの方法があります。タンパク質分野で Bindcraft(ハルシネーションのためのフレームワーク)に詳しい方がいれば、彼らが採用しているアプローチはさらに異なります。多くの構造予測モデルは、実際にはシンプレックスの制約に違反する入力を受け入れることができます。そのため、Bindcraft では制約のない変数から開始し、最適化の過程でそれらをゆっくりとシンプレックスに押し込みます。これは最適化問題の緩和と見なすことができます。
これらの手法のどれが特定の Роblem に最適かは多くの要因に依存するため、1つの「最良」の方法があると言うのは簡単ではありません。単純なソフトマックス再パラメータ化手法の勾配は、頂点付近でいくつかの病的な振る舞いをすることが知られているため、おそらく避けるべきです。実際、最近実行しているいくつかの実験では、これはミラー降下法よりも常にパフォーマンスが悪いです。前述したように、PGD は多くの座標が正確にゼロになるスパースな解につながります。ミラー降下法の場合、正確にゼロの座標を得ることは不可能です。
ここで議論できることは他にもたくさんあります。他のミラーマップはどうでしょうか?他の問題に対してミラー降下法はどのように機能するのでしょうか?最適化の幾何学的構造はどうなっているのでしょうか?残念ながら、この投稿は一般の読者には少し長くなりすぎたように思われるので、ここで終わりにします。これらの問題のいずれかに興味がある場合は、遠慮なく私に連絡してください!議論するのは大好きです!
- これを見るには、ベクトル g の 1=(1,⋯,1) に垂直な部分空間への射影は g−⟨g,1⟩∥1∥²1=g−gˉ 1 であり、ここで gˉ=1k∑igi は単に成分の平均であることを思い出してください。結果の成分は合計がゼロになるため、1 に垂直であり、それに沿ってステップすると ∑ixi が不変に保たれます。つまり、正規化が維持されます。[↩︎]
- 余ベクトルは、物理学では通常「1-形式」と呼ばれます。[↩︎]
- 関数 h が、すべての x,y に対して h(y)≥h(x)+⟨∇h(x),y−x⟩+μ2∥y−x∥² である場合、ノルム ∥⋅∥ に関して μ 強凸であると言います。重要な点は、この下限のノルムが L2 ノルムである必要はないということです。異なる選択肢は「距離」を異なる方法で測定するため、空間に異なる幾何学的構造を付与します。[↩︎]