近接写像

$prox_{f} (v) = ar g min_{x} {f (x) + \frac{1}{2} ∥ x - v ∥_{2}^{2}}$ を最適性条件 $v - x \in \partial f (x)$ から求められる。ソフトしきい値 $prox_{λ ∣ \cdot ∣}$ や $prox_{λ ∥ \cdot ∥_{2}} (v) = (1 - \frac{λ}{∥ v ∥ _{2}})_{+} v$ を計算できる

前提

劣勾配と劣微分（大学院数学凸最適化・組合せ最適化）

この技能までの道筋（44 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
積と商の微分（数学III 微分法）
合成関数の微分（数学III 微分法）
偏微分と全微分（大学数学微分積分）
三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
1 次方程式の解き方（中学数学方程式）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
ベクトルの演算と成分（数学C ベクトル）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
最大公約数と最小公倍数（算数整数の性質）
比の性質と簡単な比（算数割合と比）
相似な三角形と長さの比（算数平面図形）
三角形の相似条件と対応する辺の長さ（中学数学相似と三平方の定理）
三角比の定義と値（数学I 図形と計量）
内積となす角（数学C ベクトル）
劣勾配と劣微分（大学院数学凸最適化・組合せ最適化）

説明

凸関数 $f$ に対して、点 $v$ を「 $f$ を小さくしつつ $v$ からあまり離れない点」に移す写像 $prox_{f} (v) = ar g min_{x} {f (x) + \frac{1}{2} ∥ x - v ∥_{2}^{2}}$ を、最適性条件 $v - x \in \partial f (x)$ から具体的に計算できるようになります。特に $λ ∣ \cdot ∣$ の近接写像（ソフトしきい値）と $λ ∥ \cdot ∥_{2}$ の近接写像を求められるようになります。近接写像は、微分できない項（ $ℓ_{1}$ 正則化など）を含む最適化問題を解く近接勾配法などの反復法で、各ステップの計算そのものとして使われます。

なぜそうしてよいのか

$f$ を凸関数（値 $+ \infty$ も許す）とし、 $ϕ (x) = f (x) + \frac{1}{2} ∥ x - v ∥_{2}^{2}$ とおきます。点 $x$ が $v - x \in \partial f (x)$ を満たすとします。劣勾配の定義から、すべての $y$ で $f (y) \geq f (x) + ⟨ v - x, y - x ⟩$ です。一方、展開すると $\frac{1}{2} ∥ y - v ∥_{2}^{2} = \frac{1}{2} ∥ x - v ∥_{2}^{2} + ⟨ x - v, y - x ⟩ + \frac{1}{2} ∥ y - x ∥_{2}^{2}$ が恒等的に成り立ちます。この 2 つを足すと内積の項が打ち消し合い、 $ϕ (y) \geq ϕ (x) + \frac{1}{2} ∥ y - x ∥_{2}^{2}$ が得られます。よって $x$ は $ϕ$ の最小点で、しかも $y \neq = x$ なら $ϕ (y) > ϕ (x)$ なので最小点はただ 1 つです。つまり「 $v - x \in \partial f (x)$ を満たす $x$ を見つければ、それが $prox_{f} (v)$ 」です。これは $0 \in \partial ϕ (x)$ という最適性条件を、 $\frac{1}{2} ∥ x - v ∥_{2}^{2}$ の勾配 $x - v$ を移項して書いたものと見ることもできます。

この条件を $f = λ ∣ \cdot ∣$ （ $λ > 0$ , 1 変数）に使います。 $\partial f (x) = {λ} (x > 0)$ , ${- λ} (x < 0)$ , $[- λ, λ] (x = 0)$ なので、 $x > 0$ なら $v - x = λ$ より $x = v - λ$ （これが正となるのは $v > λ$ のとき）、 $x < 0$ なら $x = v + λ$ （ $v < - λ$ のとき）、 $x = 0$ なら $v \in [- λ, λ]$ です。まとめると $prox_{λ ∣ \cdot ∣} (v) = ⎩ ⎨ ⎧ v - λ 0 v + λ (v > λ) (∣ v ∣ \leq λ) (v < - λ)$ で、これをソフトしきい値といいます（絶対値を $λ$ だけ $0$ に向かって縮め、行き過ぎるなら $0$ で止める）。 $∥ x ∥_{1} = \sum_{i} ∣ x_{i} ∣$ の場合は目的関数が成分ごとに分かれるので、各成分にソフトしきい値を施せばよいです。

$f = λ ∥ \cdot ∥_{2}$ では、 $\partial f (x) = {λ x /∥ x ∥_{2}} (x \neq = 0)$ , ${g ∣ ∥ g ∥_{2} \leq λ} (x = 0)$ です。 $x = 0$ が解になるのは $∥ v ∥_{2} \leq λ$ のとき。 $x \neq = 0$ なら $v = x (1 + λ /∥ x ∥_{2})$ なので $x$ は $v$ と同じ向きで $∥ v ∥_{2} = ∥ x ∥_{2} + λ$ 、すなわち $x = (1 - \frac{λ}{∥ v ∥ _{2}}) v$ （ $∥ v ∥_{2} > λ$ のとき）。 $t_{+} = max (t, 0)$ と書けば、どちらの場合も $prox_{λ ∥ \cdot ∥_{2}} (v) = (1 - \frac{λ}{∥ v ∥ _{2}})_{+} v$ （ $v = 0$ のときは $0$ ）とまとめられます。ベクトルの向きを保ったまま長さを $λ$ だけ縮める写像です。

手順

$f$ の劣微分 $\partial f (x)$ を、 $f$ が微分できる点とできない点に分けて書く。
最適性条件 $v - x \in \partial f (x)$ を立てる（ $f$ が $λ f_{0}$ の形なら $\partial f (x) = λ \partial f_{0} (x)$ を使う）。
$x$ がどの場合（例： $x > 0$ , $x < 0$ , $x = 0$ 、または $x \neq = 0$ , $x = 0$ ）にあるかで場合分けして、各場合の条件を解き、その場合と矛盾しない $v$ の範囲を求める。
与えられた $v$ が入る場合の $x$ を答える。条件を満たす $x$ はただ 1 つなので、それが $prox_{f} (v)$ である。
よく使う結果は公式として使ってよい： $prox_{λ ∣ \cdot ∣} (v) = sgn (v) max (∣ v ∣ - λ, 0)$ 、 $prox_{λ ∥ \cdot ∥_{2}} (v) = (1 - \frac{λ}{∥ v ∥ _{2}})_{+} v$ 。

例題

$λ = 2$ , $v = (3, 4) \in R^{2}$ とする。 $prox_{λ ∥ \cdot ∥_{2}} (v) = ar g min_{x \in R^{2}} {2∥ x ∥_{2} + \frac{1}{2} ∥ x - v ∥_{2}^{2}}$ を求めよ。

例題の解答

手順 1： $f (x) = 2∥ x ∥_{2}$ の劣微分は、 $x \neq = 0$ で $\partial f (x) = {2 x /∥ x ∥_{2}}$ 、 $x = 0$ で $\partial f (0) = {g ∣ ∥ g ∥_{2} \leq 2}$ 。

手順 2：最適性条件は $v - x \in \partial f (x)$ 。

手順 3： $x = 0$ の場合、条件は $∥ v ∥_{2} \leq 2$ だが、 $∥ v ∥_{2} = 3^{2} + 4^{2} = 5 > 2$ なのでこの場合は起こらない。 $x \neq = 0$ の場合、 $v - x = 2 x /∥ x ∥_{2}$ より $v = (1 + \frac{2}{∥ x ∥ _{2}}) x$ 。よって $x$ は $v$ と同じ向きで、長さを比べて $5 = ∥ x ∥_{2} + 2$ 、 $∥ x ∥_{2} = 3$ 。

手順 4： $x = \frac{3}{5} v = (1 - \frac{2}{5}) v = (\frac{9}{5}, \frac{12}{5})$ 。（公式 $(1 - \frac{λ}{∥ v ∥ _{2}})_{+} v$ でも同じ結果になる。）

確認： $v - x = (\frac{6}{5}, \frac{8}{5})$ 、 $2 x /∥ x ∥_{2} = \frac{2}{3} (\frac{9}{5}, \frac{12}{5}) = (\frac{6}{5}, \frac{8}{5})$ で一致する。

したがって $prox_{λ ∥ \cdot ∥_{2}} (v) = (\frac{9}{5}, \frac{12}{5})$ 。

答え: $(\frac{9}{5}, \frac{12}{5})$

よくある誤り

$λ ∥ \cdot ∥_{2}$ の近接写像を、成分ごとのソフトしきい値で計算してしまう誤り。 $v = (3, 4)$ , $λ = 2$ で $(3 - 2, 4 - 2) = (1, 2)$ とするのは $λ ∥ \cdot ∥_{1}$ の近接写像である。正しくは $(1 - \frac{2}{5}) (3, 4) = (\frac{9}{5}, \frac{12}{5})$ 。
正の部分 $(\cdot)_{+}$ を落としてしまう誤り。 $v = (1, 0)$ , $λ = 2$ で $(1 - \frac{2}{1}) v = (- 1, 0)$ とすると向きが反転してしまう。 $∥ v ∥_{2} = 1 \leq 2$ なので $x = 0$ の場合にあたり、正しくは $prox_{2∥ \cdot ∥_{2}} (v) = (0, 0)$ 。
ソフトしきい値で符号を落としてしまう誤り。 $λ = 1$ , $v = - 3$ で $max (∣ v ∣ - λ, 0) = 2$ と答えるのは誤り。正しくは $prox_{∣ \cdot ∣} (- 3) = sgn (- 3) \cdot 2 = - 2$ （ $x < 0$ の場合 $x = v + λ = - 2$ ）。
最適性条件の符号を逆にして $x - v \in \partial f (x)$ としてしまう誤り。正しくは $\frac{1}{2} ∥ x - v ∥_{2}^{2}$ の勾配 $x - v$ を移項して $v - x \in \partial f (x)$ 。例えば $f (x) = \frac{a}{2} x^{2} (a \geq 0)$ では $v - x = a x$ より $prox_{f} (v) = \frac{v}{1 + a}$ で、逆符号だと $\frac{v}{1 - a}$ という誤った値になる。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
$R^{3}$ に標準内積とユークリッドノルム $∥ \cdot ∥_{2}$ を入れる。凸関数 $f : R^{3} \to R$ を
$f (x) = 2 (∣ x_{1} ∣ + ∣ x_{2} ∣ + ∣ x_{3} ∣)$
で定め、その近接写像を
$prox_{f} (v) = ar g x \in R^{3} min {f (x) + \frac{1}{2} ∥ x - v ∥_{2}^{2}}$
とする。 $v = (5, - 1, - 3)$ のとき、 $prox_{f} (v) = (x_{1}, x_{2}, x_{3})$ を求め、組 $(x_{1}, x_{2}, x_{3})$ の形で答えよ。

この技能を使う問題

この技能の次に学べること

モローの分解と凸集合への射影（大学院数学凸最適化・組合せ最適化）