座標降下法

座標降下法（ざひょうこうかほう、英: Coordinate descent）とは、関数の極値を逐次座標方向に最小化して求める最適化アルゴリズムの一種。各反復において座標降下法は座標選択規則に従って座標あるいは座標ブロックを決定し、選択されていない座標や座標ブロックを固定したままその座標超平面上で厳密あるいは近似的に最小化する。座標方向に直線探索を行うことで現在の反復点における適切なステップサイズを求めることができる。座標降下法は微分可能・微分不可能な関数両者ともに適用できる解法である。

説明

座標降下法は各反復において一つの（あるいは少数の）変数の最適化問題を解くように、変数の各方向に順番に最小化することで多変数関数 ${\displaystyle F(\mathbf {x} )}$ の最小化を行うアルゴリズムである。最も単純な巡回座標降下の場合では、各反復ごとに順番に座標方向に沿って目的関数を最小化することを考える。始めに、以下の初期点から開始する:

${\displaystyle \mathbf {x} ^{0}=(x_{1}^{0},\ldots ,x_{n}^{0})}$,

${\displaystyle k 1}$ 番目の反復点 ${\displaystyle \mathbf {x} ^{k 1}}$ は点 ${\displaystyle \mathbf {x} ^{k}}$ を用いて以下の最適化問題を解くことで求まる:

${\displaystyle x_{i}^{k 1}={\underset {y\in \mathbb {R} }{\operatorname {arg\,min} }}\;f(x_{1}^{k 1},\dots ,x_{i-1}^{k 1},y,x_{i 1}^{k},\dots ,x_{n}^{k})}$

ただし、変数 ${\displaystyle x_{i}}$ は ${\displaystyle \mathbf {x} }$ の 1 から ${\displaystyle n}$ までの添字 ${\displaystyle i}$ に対応している。

すなわち、関数 ${\displaystyle F}$ の極値を求めるため初期点 ${\displaystyle \mathbf {x} ^{0}}$ から開始し、点列 ${\displaystyle \mathbf {x} ^{0},\mathbf {x} ^{1},\mathbf {x} ^{2},\dots }$ を求めていく。

各反復において直線探索を行うことで以下の性質が導かれる:

${\displaystyle F(\mathbf {x} ^{0})\geq F(\mathbf {x} ^{1})\geq F(\mathbf {x} ^{2})\geq \dots .}$

この点列は最急降下法と同様に極値への収束性を持つことが知られている。直線探索による座標方向への探索が一通り巡回した後でも目的関数の改善がない場合は極値へ収束したとみなせる。

上記の手続きによる各反復は以下のように表される。

微分可能な場合

連続的微分可能関数 F での座標降下法は以下の手続きを行う:

ステップサイズの選択方法はいくつか知られており、厳密に f(x_i) = F(x) の最小化問題を解く（変数 x_i を固定した上で F の最小化）、あるいは古典的な直線探索での選択基準に従った方法が挙げられる。

制限

座標降下法は二つの問題を抱えている。一つ目は目的関数が滑らかな関数でない場合である。下記の図では目的関数の等高線が滑らかでない場合について、座標降下法の各反復において停留点でない点が求まってしまう例を挙げている。最小化問題に対して座標降下法において現在の反復が点 (−2, −2) であるとすると、次の探索方向として赤い矢印の方向に進むことが考えられるが、どちらの方向に進むことを考えても、この場合目的関数は増大してしまう。この場合座標方向に進まず、二つの探索方向を併せた方向に方向に進むことで目的関数は改善される。下記の図では最適解に収束しない例を紹介したが、ある条件の下では収束性を示すことができる。

二つ目の問題点として座標降下法の並列化が困難であることが挙げられる。座標降下法では各座標方向に順番に探索し、目的関数を改善することから、大規模な並列化は難しいとされる。近年の研究で座標降下法は各座標方向への目的関数の変化を緩和することによって大規模な並列化を可能にする手法が提案されている。

応用

座標降下法は単純な手続きで完結することから実用面においては人気のある解法となっているが、最適化理論に関する研究者の間ではより複雑な解法を注目することが多いことから、ほとんど研究されない解法となっている。座標降下法の初期の応用例として、コンピュータ断層撮影の分野が挙げられ、この応用において座標降下法による収束の速さが良いことが判明したことから、臨床用のマルチスライスCTのヘリカルスキャン時に使用されるようになった 。巡回座標降下法はタンパク質構造予測の面でも使用されるようになった。加えて、機械学習における大規模最適化問題に対する応用においても注目されるようになり、特にサポートベクターマシンの訓練時や非負値行列因子分解において座標降下法を適用した際に、他の解法以上の優位性が示されている。また勾配の計算が難しいような問題に対しても適用されている。

脚注

参考文献

• Bezdek, J. C.; Hathaway, R. J.; Howard, R. E.; Wilson, C. A.; Windham, M. P. (1987), “Local convergence analysis of a grouped variable version of coordinate descent”, Journal of Optimization Theory and Applications (Kluwer Academic/Plenum Publishers) 54 (3): pp. 471–477, doi:10.1007/BF00940196 
• Bertsekas, Dimitri P. (1999). Nonlinear Programming, Second Edition Athena Scientific, Belmont, Massachusetts. ISBN 1-886529-00-0.
• Luo, Zhiquan; Tseng, P. (1992), “On the convergence of the coordinate descent method for convex differentiable minimization”, Journal of Optimization Theory and Applications (Kluwer Academic/Plenum Publishers) 72 (1): pp. 7–35, doi:10.1007/BF00939948, hdl:1721.1/3164 .
• Wu, TongTong; Lange, Kenneth (2008), “Coordinate descent algorithms for Lasso penalized regression”, The Annals of Applied Statistics (Institute of Mathematical Statistics) 2 (1): pp. 224–244, arXiv:0803.3876, doi:10.1214/07-AOAS147 .
• Richtarik, Peter; Takac, Martin (2011-04), “Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function”, Mathematical Programming (Springer) 144 (1–2): pp. 1–38, arXiv:1107.2848, doi:10.1007/s10107-012-0614-z .
• Richtarik, Peter; Takac, Martin (2012-12), “Parallel coordinate descent methods for big data optimization”, ArXiv:1212.0873, arXiv:1212.0873 .

関連項目

• 適応型座標降下法
• 共役勾配法
• 最急降下法
• 直線探索
• 数理最適化
• 最適化におけるニュートン法
• 確率的勾配降下法