差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン 前のリビジョン 次のリビジョン | 前のリビジョン 次のリビジョン両方とも次のリビジョン | ||
intro:researches:machine [2020/12/20 12:59] – [アンサンブル学習アルゴリズム] Hideaki IIDUKA | intro:researches:machine [2023/05/29 12:26] – [クリティカルバッチサイズの推定] Naoki SATO | ||
---|---|---|---|
行 1: | 行 1: | ||
- | ====== 機械学習アルゴリズムの研究紹介 | + | ====== 機械学習研究 ====== |
- | ===== Euclid 空間上の機械学習とその既存手法 | + | ===== ニューラルネットワークの訓練 |
- | [[https:// | + | [[https:// |
このように、機械学習と最適化はとても密接な関係があります。 | このように、機械学習と最適化はとても密接な関係があります。 | ||
- | 機械学習に現れる損失最小化問題は、一般に、以下のように表現できます。 | + | 深層ニューラルネットワークに現れる損失最小化問題は、一般に、以下のように表現できます。 |
\begin{align*} | \begin{align*} | ||
- | \text{Minimize } f(x):= \sum_{t\in \mathcal{T}} f_t (x) \text{ subject to } x\in X. | + | \text{Minimize } f(x):= \frac{1}{n} \sum_{i=1}^n f_i (x) \text{ subject to } x\in X. |
\end{align*} | \end{align*} | ||
- | ただし、$f_t \colon \mathbb{R}^d \to \mathbb{R}$ $(t\in \mathcal{T}: | + | ただし、$f_i \colon \mathbb{R}^d \to \mathbb{R}$ $(i\in \{1, |
$X$ $(\subset \mathbb{R}^d)$ は空でない閉凸集合です。 | $X$ $(\subset \mathbb{R}^d)$ は空でない閉凸集合です。 | ||
- | この損失最小化問題手法を解くための機械学習手法として、[[https:// | + | この損失最小化問題手法を解くための深層学習手法(ここではオプティマイザーと呼ぶことにします)として、[[https:// |
- | 例えば、[[https:// | + | 例えば、[[https:// |
- | [[http:// | + | [[http:// |
- | [[https:// | + | [[https:// |
- | + | ||
- | 畳み込み層が20からなる ResNet-20 を用いた[[https:// | + | |
+ | [[https:// | ||
{{ : | {{ : | ||
- | ですが、これらのアルゴリズムを利用する際の最も困難な問題は、機械学習を適切に行うための学習率の調整です。例えば、適応学習率最適化アルゴリズムである [[https:// | + | ==== クリティカルバッチサイズの存在と推定 ==== |
- | \begin{align*} | + | |
- | R(T) = \sum_{t\in \mathcal{T}} f_t (x_t) - \underbrace{\sum_{t\in \mathcal{T}} f_t (x^\star)}_{f^\star} | + | |
- | \end{align*} | + | |
- | で定義されるリグレット(ただし、$(x_t)_{t\in \mathcal{T}}$ は学習アルゴリズムで生成される点列、$x^\star$ は損失最小化問題の解)に対して、 | + | |
- | \begin{align*} | + | |
- | \frac{R(T)}{T} \leq M \sqrt{\frac{1+ \log T}{T}} | + | |
- | \end{align*} | + | |
- | を満たします((十分大きな $T$ に対して、$\sqrt{(1+ \log T)/T} \approx 0$ を満たします。))(ただし、$M$ は定数)が、損失最小化問題を高速に解くための適切な $\alpha$ を事前に設定することは大変難しいです((Adam や AMSGrad といった適応学習率最適化アルゴリズム (adaptive learning rate optimization algorithm) は時刻 $t$ に対して学習率を調整しますが、$\alpha$ は事前に設定する必要があります。))。この問題は、機械学習分野に限らず、一般の[[intro: | + | |
- | 加えて、既存の適応学習率最適化アルゴリズムは($R(T)/ | + | |
- | ===== Euclid 空間上の機械学習アルゴリズム ===== | + | ===== 敵対的生成ネットワークの訓練 ===== |
- | * [[: | + | |
- | 適切な学習率の設定を考慮しつつ、損失最小化問題を解くことを保証する適応学習率最適化アルゴリズムについて提案しています。\\ | + | [[https:// |
- | $0$に収束するような減少学習率 (例えば、$\alpha_t = \alpha/ | + | |
- | $(x_n)_{n\in\mathbb{N}}$は適応学習率最適化アルゴリズムで生成される点列とし、$\alpha, | + | |
- | \begin{align*} | + | |
- | \liminf_{n \to + \infty} \mathbb{E}\left[f (x_n) - f^\star \right] | + | |
- | \leq M_1 \alpha + M_2 \beta. | + | |
- | \end{align*} | + | |
- | $M_i$ ($i=1,2$) はアルゴリズムを実行させる前に計算可能な定数であるため、この不等式の右辺が十分小さくなるように**定数**学習率 $\alpha, \beta$ を適切に設定できます。少し大まかに言うと、小さな定数学習率を有する適応学習率最適化アルゴリズムが損失最小化問題の解を近似できる、となります。\\ | + | |
- | これまでの減少学習率に対する適応学習率最適化アルゴリズムの収束解析では、リグレット最小化のみが保証されており、損失最小化問題を解くことまでは保証されていませんでした。 | + | |
- | この論文では、**減少**学習率を有する適応学習率最適化アルゴリズムで生成される点列の任意の集積点が損失最小化問題の解集合に属することを数学的に証明しています。詳細については、[[https:// | + | |
- | * Y. Kobayashi and [[: | + | |
- | 既存の適応学習率最適化アルゴリズムと比べて高速に深層ニューラルネットワークを訓練可能なアルゴリズム CoBA を提案しています。主なアイデアは、既存の適応学習率最適化アルゴリズム | + | |
- | [[https:// | + | |
- | \begin{align*} | + | |
- | d_t = - g_t + \gamma_t d_{t-1} | + | |
- | \end{align*} | + | |
- | に修正した点です。[[https:// | + | |
- | 本論文では、 CoBA がリグレット最小化に関して、[[https:// | + | |
- | 更に、テキスト分類や画像分類に対する [[https:// | + | |
- | [[http:// | + | |
- | [[https:// | + | |
- | 詳細については、[[https:// | + | |
- | * K. Hishinuma and [[: | + | |
- | [[https:// | + | |
- | 多層ニューラルネットワークなどといった深層学習においては、そのネットワークの規模に応じて扱う問題の次元が大きくなります。 | + | |
- | そのような問題を既存手法で効率的に解くためには、学習する問題やネットワークに対して最適な学習率を事前にアルゴリズムに与える必要があります。 | + | |
- | しかしながら提案手法では、実行時に自動的に適切な学習率を[[https:// | + | |
- | 本論文では、直線探索法を取り入れた増分劣勾配法や並列型劣勾配法が制約付き非平滑凸最適化問題の解へ収束する点列を生成することを数学的に証明するとともに、これらの手法を多層ニューラルネットワークの学習に適用して、深層学習への活用可能性について議論しています。(説明終わり) | + | |
- | ===== 多様体上の機械学習とその既存手法 ===== | ||
- | グラフやテキストなどのデータを双曲空間の [[https:// | ||
- | Poincaré 円板は Riemann 多様体構造を持つため、 以下のような Riemann 多様体上の損失最小化問題を解くことを考えます。 | ||
\begin{align*} | \begin{align*} | ||
- | \text{Minimize } f(x):= \sum_{t\in \mathcal{T}} f_t (x) \text{ subject to } x\in X. | + | \min_G \max_D V(D,G):= \mathbb{E}_\boldsymbol{x} [\log D(\boldsymbol{x})] + \mathbb{E}_\boldsymbol{z} [\log (1-D(G(\boldsymbol{z})))]. |
\end{align*} | \end{align*} | ||
- | ただし、$M_i$ は測地的完備 Riemann 多様体、$M = M_1 \times \cdots \times M_N$、$f_t \colon M \to \mathbb{R}$ $(t\in \mathcal{T}: | ||
- | この損失最小化問題手法を解くための機械学習手法として、Euclid 空間上の[[https:// | ||
- | そこで、 Adam や AMSGrad といった Euclid 空間上の適応学習率最適化アルゴリズムを一般の Riemann 多様体上に拡張することは、Riemann 多様体上の損失最小化問題を高速に解くためには大変自然な発想であると思います。 | ||
- | しかしながら、Euclid 空間上の適応学習率最適化アルゴリズムの多様体上への拡張は、一般の多様体上に共通する座標系が存在しないことが原因となり、容易ではないと考えられます。 | ||
- | そこで、積多様体の成分を Euclid 空間における座標成分のようにみなして [[https:// | ||
- | しかしながら、Euclid 空間上の機械学習アルゴリズム内でも示したように、 **減少**学習率 $\alpha_t = \alpha/ | ||
- | \begin{align*} | ||
- | R(T) = \sum_{t\in \mathcal{T}} f_t (x_t) - f^\star | ||
- | \end{align*} | ||
- | で定義されるリグレット(ただし、$(x_t)_{t\in \mathcal{T}}$ は学習アルゴリズムで生成される点列、$f^\star$ は損失最小化問題の最適値)に対して、 | ||
- | \begin{align*} | ||
- | \frac{R(T)}{T} \leq M \sqrt{\frac{1+ \log T}{T}} | ||
- | \end{align*} | ||
- | を満たします (ただし、$M$ は定数) が、損失最小化問題を解くことが保証されていません。また、適切な学習率設定と実用の観点から、**定数**学習率での収束解析は必要です((減少学習率 $\alpha_t = \alpha/ | ||
- | ===== 多様体上の機械学習アルゴリズム ===== | ||
- | * H. Sakai and [[: | ||
- | 適切な学習率の設定を考慮しつつ、損失最小化問題を解くことを保証する適応学習率最適化アルゴリズムについて提案しています。\\ | ||
- | $0$に収束するような減少学習率 (例えば、$\alpha_t = \alpha/ | ||
- | $(x_n)_{n\in\mathbb{N}}$は適応学習率最適化アルゴリズムで生成される点列とし、$\alpha, | ||
- | \begin{align*} | ||
- | \mathbb{E} \left[\frac{1}{n} \sum_{k=1}^n f(x_k) - f^\star \right] \leq \mathcal{O}\left(\frac{1}{n}\right) + C_1 \alpha + C_2 \beta. | ||
- | \end{align*} | ||
- | $C_i$ ($i=1,2$) はアルゴリズムを実行させる前に計算可能な定数であるため、この不等式の右辺が十分小さくなるように**定数**学習率 $\alpha, \beta$ を適切に設定できます。大まかに言うと、小さな定数学習率を有する適応学習率最適化アルゴリズムが損失最小化問題の解を近似できる、となります。\\ | ||
- | これまでの減少学習率に対する適応学習率最適化アルゴリズムの収束解析では、リグレット最小化のみが保証されており、損失最小化問題を解くことまでは保証されていませんでした。 | ||
- | この論文では、**減少**学習率を有する適応学習率最適化アルゴリズムが損失最小化問題を解くことができます。 | ||
- | WordNet の単語全体 (82, | ||
- | 定数学習率を有する [[https:// | ||
- | 得られた収束解析に基づいて設定した定数学習率を有する提案手法 (CA2, **定数**学習率を有する [[https:// | ||
- | {{ : | + | ただし、$G: |
- | {{ : | + | $D: |
+ | さらに、$\boldsymbol{x} \in \mathbb{R}^d$ は実画像、$\boldsymbol{z} \in \mathbb{R}^l$ はノイズで、 | ||
+ | $G(\boldsymbol{z}) \in \mathbb{R}^d$は生成画像です。 | ||
+ | 実画像の次元$d$は、データセットによって決まっています。例えば、[[https:// | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | 生成器はノイズ、または[[https:// | ||
+ | 識別器は、実画像$\boldsymbol{x} \in \mathbb{R}^d$または生成画像$G(\boldsymbol{z}) \in \mathbb{R}^d$を入力とし、入力された画像が実画像である確率$[0, | ||
+ | |||
+ | 生成器は、識別器に見破られない生成画像を作ることを目指すので、$D(\boldsymbol{x})=0, | ||
+ | 識別器は、実画像と生成画像を完全に識別することを目指すので、$D(\boldsymbol{x})=1, | ||
+ | すなわち、生成器は$L_G=V$を最小にするように行動し、識別器は$L_D=-V$を最小にするように行動します。\\ | ||
+ | 具体的には、生成器と識別器は[[https:// | ||
+ | これを踏まえると、GANの学習は、生成器と識別器をプレイヤーとするナッシュ均衡問題の局所的[[https:// | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | このように、GANは他の深層生成モデルと比べて高品質な画像を生成することができますが、その学習は非常に不安定であることが知られています。\\ | ||
+ | より早く、より安定した学習で、より高品質な画像を生成するために、[[https:// | ||
+ | |||
+ | ==== 収束解析 ==== | ||
+ | |||
+ | 生成器のニューラルネットワークのパラメータを$\boldsymbol{\theta}$、識別器のニューラルネットワークのパラメータを$\boldsymbol{w}$とします。それぞれの目的関数を最小にすることを目指すので、 | ||
+ | \begin{align} | ||
+ | \nabla_\boldsymbol{\theta} L_G(\boldsymbol{\theta}_n, | ||
+ | \end{align} | ||
+ | を満たすような最適解$(\boldsymbol{\theta}^\star, | ||
+ | \begin{align} | ||
+ | \forall \boldsymbol{\theta} \in \mathbb{R}^\Theta, | ||
+ | \langle \boldsymbol{\theta}_n - \boldsymbol{\theta}, | ||
+ | \nabla_{\boldsymbol{\theta}} L_G (\boldsymbol{\theta}_n, | ||
+ | \text{, } | ||
+ | \langle \boldsymbol{w}_n - \boldsymbol{w}, | ||
+ | \end{align} | ||
+ | と等価なので、この不等式を満たすような最適解$(\boldsymbol{\theta}^\star, | ||
+ | 上の不等式の左辺について、それぞれ次の不等式が成り立ちます。 | ||
+ | \begin{align} | ||
+ | & | ||
+ | \mathbb{E} \left[ | ||
+ | \langle \boldsymbol{\theta}_n - \boldsymbol{\theta}, | ||
+ | \nabla_{\boldsymbol{\theta}} L_G (\boldsymbol{\theta}_n, | ||
+ | \leq | ||
+ | \underbrace{\frac{\Theta \mathrm{Dist}(\boldsymbol{\theta}) H^G}{2 \alpha^G \tilde{\beta_1^G}}}_{A_G} | ||
+ | \frac{1}{N} | ||
+ | + | ||
+ | \underbrace{\frac{\sigma_G^2 \alpha^G}{2 \tilde{\beta_1^G} \tilde{\gamma}^{G^2} h_{0, | ||
+ | \frac{1}{b} | ||
+ | + | ||
+ | \underbrace{\frac{M_G^2 \alpha^G}{2 \tilde{\beta_1^G} \tilde{\gamma}^{G^2} h_{0, | ||
+ | + | ||
+ | \frac{\beta_1^G}{\tilde{\beta_1^G}} | ||
+ | \sqrt{\Theta \mathrm{Dist}(\boldsymbol{\theta}) | ||
+ | ( \sigma_G^2 + M_G^2 )}}_{C_G}, \\ | ||
+ | |||
+ | & | ||
+ | \mathbb{E} \left[ | ||
+ | \langle \boldsymbol{w}_n - \boldsymbol{w}, | ||
+ | \nabla_{\boldsymbol{w}} L_G (\boldsymbol{\theta}_n, | ||
+ | \leq | ||
+ | \underbrace{\frac{W \mathrm{Dist}(\boldsymbol{w}) H^D}{2 \alpha^D \tilde{\beta_1^D}}}_{A_D} | ||
+ | \frac{1}{N} | ||
+ | + | ||
+ | \underbrace{\frac{\sigma_G^2 \alpha^D}{2 \tilde{\beta_1^D} \tilde{\gamma}^{D^2} h_{0, | ||
+ | \frac{1}{b} | ||
+ | + | ||
+ | \underbrace{\frac{M_D^2 \alpha^D}{2 \tilde{\beta_1^D} \tilde{\gamma}^{D^2} h_{0, | ||
+ | + | ||
+ | \frac{\beta_1^D}{\tilde{\beta_1^D}} | ||
+ | \sqrt{W \mathrm{Dist}(\boldsymbol{w}) | ||
+ | ( \sigma_D^2 + M_D^2 )}}_{C_D} | ||
+ | \end{align} | ||
+ | ただし、$\alpha^G, | ||
+ | |||
+ | ==== ステップ数$N$とバッチサイズ$b$の関係 ==== | ||
+ | 局所的ナッシュ均衡を近似できる理想的なステップ数$N$、バッチサイズ$b$、学習率$\alpha^G, | ||
+ | \begin{align} | ||
+ | \frac{A_G}{N_G}+\frac{B_G}{b}+C_G=\epsilon_G^2, | ||
+ | \frac{A_D}{N_D}+\frac{B_D}{b}+C_D=\epsilon_D^2 | ||
+ | \end{align} | ||
+ | すなわち、 | ||
+ | \begin{align} | ||
+ | N_G(b)=\frac{A_G b}{(\epsilon_G^2 -C_G)b -B_G}, \text{ | ||
+ | N_D(b)=\frac{A_D b}{(\epsilon_D^2 -C_D)b -B_D} | ||
+ | \end{align} | ||
+ | が成り立ちます。ただし、生成器のステップ数を$N_G$、識別器のステップ数を$N_D$とし、それぞれをバッチサイズ$b$の関数だと捉えています。$N_G(b)$を微分して、その形状について考えてみましょう。 | ||
+ | \begin{align} | ||
+ | \frac{\mathrm{d}N_G(b)}{\mathrm{d}b} | ||
+ | = | ||
+ | \frac{-A_G B_G}{{(\epsilon_G^2 - C_G)b - B_G}^2} | ||
+ | \leq | ||
+ | 0, \text{ | ||
+ | \frac{\mathrm{d}^2 N_G(b)}{\mathrm{d}b^2} | ||
+ | = | ||
+ | \frac{2A_G B_G(\epsilon_G^2 - C_G)}{{(\epsilon_G^2 - C_G)b - B_G}^3} | ||
+ | \geq | ||
+ | 0 | ||
+ | \end{align} | ||
+ | が成り立ちます。1階微分が$0$以下で、2階微分が$0$以上なので、$N_G(b)$は$b$に対して単調減少で、かつ凸関数であることがわかります。$N_D(b)$についても同様です。\\ | ||
+ | このことから、学習が収束するまでに必要なステップ数$N$を最小にするバッチサイズ$b$が存在することが分かります。 | ||
+ | ==== クリティカルバッチサイズの存在 ==== | ||
+ | クリティカルバッチサイズとは、学習の計算量を最小にするバッチサイズのことです。 | ||
+ | ニューラルネットワークの訓練には、クリティカルバッチサイズが存在することが先行研究によって明らかになっています。 | ||
+ | そこで、GANの訓練にもクリティカルバッチサイズが存在するかどうかを考えてみましょう。 | ||
+ | |||
+ | 学習の計算量の指標である確率的勾配計算コスト(SFO計算量:stochastic first-order oracle complexity)は、それぞれ$N_G(b)b, | ||
+ | \begin{align} | ||
+ | N_G(b)b | ||
+ | = | ||
+ | \frac{A_G b^2}{(\epsilon_G^2 - C_G)b - B_G}, \text{ | ||
+ | N_D(b)b | ||
+ | = | ||
+ | \frac{A_D b^2}{(\epsilon_D^2 - C_D)b - B_D} | ||
+ | \end{align} | ||
+ | 先ほどと同様に微分して形状を調べてみましょう。 | ||
+ | \begin{align} | ||
+ | \frac{\mathrm{d}N_G(b)b}{\mathrm{d}b} | ||
+ | = | ||
+ | \frac{A_G b\{(\epsilon_G^2-C_G)b -2B_G\}}{\{(\epsilon_G^2-C_G)b-B_G\}^2} | ||
+ | , \text{ | ||
+ | \frac{\mathrm{d}^2 N_G(b)b}{\mathrm{d}b^2} | ||
+ | = | ||
+ | \frac{2A_G B_G^2}{\{(\epsilon_G^2-C_G)b-B_G\}^3} | ||
+ | \geq | ||
+ | 0 | ||
+ | \end{align} | ||
+ | が成り立ちます。2階微分が常に$0$以上なので、$N_G(b)b$は$b$に対して凸関数であることが分かります。$N_D(b)b$についても同様です。 | ||
+ | また、1階微分から、$N_G(b)b, | ||
+ | \begin{align} | ||
+ | b_G^\star := \frac{2B_G}{\epsilon_G^2-C_G}, | ||
+ | \text{ | ||
+ | b_D^\star := \frac{2B_D}{\epsilon_D^2-C_D} | ||
+ | \end{align} | ||
+ | この$b_G^\star$と$b_D^\star$がクリティカルバッチサイズです。 | ||
+ | ==== クリティカルバッチサイズの推定 ==== | ||
+ | ここまでで、GANの訓練にもクリティカルバッチサイズが存在することがわかりました。このクリティカルバッチサイズを、事前に知ることを目指します。\\ | ||
+ | GANの目標は綺麗な生成画像を得ることです。学習の停止条件にも、生成画像の品質が利用されます。なので、ここでは生成器のクリティカルバッチサイズについて考えてみましょう。 | ||
+ | 生成器$G$のクリティカルバッチサイズは、次のように表すことができました。 | ||
+ | \begin{align} | ||
+ | b_G^\star := \frac{2B_G}{\epsilon_G^2 -C_G} | ||
+ | \end{align} | ||
+ | $B_G$や$C_G$の定義に立ち返って式変形をすると、$b_G^\star$の下界をoptimizerごとに次のように表すことができます。 | ||
+ | * Adam | ||
+ | \begin{align} | ||
+ | b_G^\star \geq | ||
+ | \frac{\sigma_G^2}{\epsilon_G^3}\frac{\alpha^G}{(1-\beta_1^G)^3 \sqrt{\frac{\Theta}{1-\beta_2^G} \frac{1}{|S|^2}}} | ||
+ | \end{align} | ||
+ | * AdaBelief | ||
+ | \begin{align} | ||
+ | b_G^\star \geq | ||
+ | \frac{\sigma_G^2}{\epsilon_G^3}\frac{\alpha^G}{(1-\beta_1^G)^3 \sqrt{\frac{4\Theta}{1-\beta_2^G} \frac{1}{|S|^2}}} | ||
+ | \end{align} | ||
+ | * RMSProp | ||
+ | \begin{align} | ||
+ | b_G^\star \geq | ||
+ | \frac{\sigma_G^2}{\epsilon_G^3}\frac{\alpha^G}{\sqrt{\frac{\Theta}{|S|^2}}} | ||
+ | \end{align} | ||
+ | このとき、$\sigma_G^2 / \epsilon_G^3$のみ未知です。$\alpha^G, | ||
+ | $\Theta$は生成器の次元でした。例えばDCGAN architectureならば、$\Theta=3, | ||
+ | |||
+ | それでは、未知数である$\sigma_G^2 / \epsilon_G^3$について考えてみましょう。これは決して事前には分からないので、クリティカルバッチサイズの測定値と、先ほどの下界の推定式を利用して逆算します。 | ||
+ | DCGANを訓練して、その学習のクリティカルバッチサイズの測定値を求めましょう。使用したデータセットはLSUN-Bedroomです。 | ||
+ | クリティカルバッチサイズは、SFO計算量である$Nb$を最小にする$b$だったので、$Nb$-$b$グラフを用意します。ここで、$N$は学習が収束するまでに必要なステップ数です。 | ||
+ | 一般的に、GANの学習の停止条件にはFID(Freche' | ||
+ | ここまでのことを踏まえて、『学習が収束するまでに必要なステップ数$N$』を、『十分に低いFIDを達成するまでに必要なステップ数$N$』と読み替えます。 | ||
+ | |||
+ | Naoki Sato, Hideaki Iiduka: Existence and Estimation of Critical Batch Size for Training Generative Adversarial Networks with Two Time-Scale Update Rule, Proceedings of The 40th International Conference on Machine Learning, PMLR 202: ??–?? (2023) | ||
+ | |||
+ | ==== GAN を訓練するための共役勾配法 ==== | ||
+ | |||
+ | Hiroki Naganuma, Hideaki Iiduka: Conjugate Gradient Method for Generative Adversarial Networks, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206: 4381–4408 (2023) | ||
- | 詳細については、[[https:// | ||
- | ===== アンサンブル学習 ===== | ||
- | [[https:// | ||
- | ここで考察される損失最小化問題は、以下のように定義されます。 | ||
- | \begin{align*} | ||
- | \text{Minimize } f(x) := \sum_{t\in\mathcal{T}} f_t (x) \text{ subject to } x \in X = \mathbb{R}_+^d \cap \underbrace{\left\{ x \in \mathbb{R}^d \colon \|x\|_1 \leq t_1 \right\}}_{C_{\mathrm{s}}} \cap \underbrace{\left\{ x \in \mathbb{R}^d \colon f_{\mathrm{div}}(x) \geq t_2 \right\}}_{C_{\mathrm{d}}}. | ||
- | \end{align*} | ||
- | ただし、$\mathbb{R}_+^d = \{ (x_i)_{i=1}^d \in \mathbb{R}^d \colon x_i \geq 0 \text{ } (i=1, | ||
- | この損失最小化問題を解くために、[[https:// | ||
- | \begin{align*} | ||
- | x_{n+1} = P_X (x_n - \alpha_n \mathsf{G}(x_n, | ||
- | \end{align*} | ||
- | ただし、$\alpha_n >0$ は学習率、$\mathsf{G}(x, | ||
- | ===== アンサンブル学習アルゴリズム ===== | ||
- | $X = \mathbb{R}_+^d \cap C_{\mathrm{s}} \cap C_{\mathrm{d}}$ という定義から、$P_X$ の計算は容易ではありません。 | ||
- | そのため、残念ながら[[https:// | ||
- | $\mathbb{R}_+^d$ への距離射影を $P_+$、$C_{\mathrm{s}}$ 及び $C_{\mathrm{d}}$ に関する射影((凸関数 $g\colon \mathbb{R}^d \to \mathbb{R}$ に対して、劣勾配射影 $P$ は、以下のように与えられます。$P(x) = x - \frac{g(x)}{\|u\|^2} u$ $\text{ } (g(x) \leq 0)$, $P(x) = x$ $\text{ }(g(x) > 0)$. | ||
- | ただし、$u \in \partial g(x)$ は $g$ の $x$ での任意の劣勾配とします。このとき、$P$ は準非拡大写像となり、$\mathrm{Fix}(P) = \{ x \in \mathbb{R}^d \colon g(x) \leq 0\}$ を満たします。例えば、$g (x) = \|x\|_1 - t_1$ と置くと、劣勾配射影 $P_{\mathrm{s}}$ が定義できます。))をそれぞれ $P_{\mathrm{s}}, | ||
- | \begin{align*} | ||
- | Q = w_1 P_+ + w_2 P_{\mathrm{s}} + w_3 P_{\mathrm{d}} | ||
- | \end{align*} | ||
- | が定義できます。$P_+, | ||
- | $Q$ は準非拡大写像となり、 $\mathrm{Fix}(Q) = X$ を示すことができます。この事実により、$Q$ を取り入れたアルゴリズムで生成される点列は $Q$ の不動点、すなわち、$X$ の点を見つけることが期待できそうです。 | ||
- | * [[: | ||
- | この論文では、以下で定義される**確率的不動点最適化アルゴリズム**を提案しています。 | ||
- | \begin{align*} | ||
- | x_{n+1} = Q(x_n) - \alpha_n \mathsf{G}(Q(x_n), | ||
- | \end{align*} | ||
- | **定数**学習率 $\alpha$ に対しては、ある定数 $K_i$ $(i=1,2)$ が存在して、以下が成り立ちます。 | ||
- | \begin{align*} | ||
- | \liminf_{n\to + \infty} \mathbb{E} \left[\| x_n - Q(x_n) | ||
- | \liminf_{n \to + \infty} \mathbb{E} \left[ f(x_n) - f^\star \right] \leq K_2 \sqrt{\alpha}. | ||
- | \end{align*} | ||
- | これらの不等式は、十分小さい定数学習率を有する確率的不動点最適化アルゴリズムは損失最小化問題の解を近似できることを示しています。 | ||
- | また、**減少**学習率及び**直線探索法**で計算された学習率を有する確率的不動点最適化アルゴリズムは損失最小化問題の解に収束することを数学的に証明しています。 | ||
- | 詳細については、[[https:// | ||
- | * [[: |