座標降下法のソースを表示

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

== 説明 ==
座標降下法は各反復において一つの（あるいは少数の）変数の最適化問題を解くように、変数の各方向に順番に最小化することで多変数関数 <math>F(\mathbf{x})</math> の最小化を行うアルゴリズムである<ref name="wright">{{Cite journal |last=Wright |first=Stephen J. |title=Coordinate descent algorithms |journal=Mathematical Programming |volume=151 |issue=1 |year=2015 |pages=3–34 |arxiv=1502.04759 |doi=10.1007/s10107-015-0892-3|s2cid=15284973 }}</ref>。最も単純な巡回座標降下の場合では、各反復ごとに順番に座標方向に沿って目的関数を最小化することを考える。始めに、以下の初期点から開始する:

: <math>\mathbf{x}^0 = (x^0_1, \ldots, x^0_n)</math>,

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

:<math>x^{k+1}_i = \underset{y\in\mathbb R}{\operatorname{arg\,min}}\; f(x^{k+1}_1, \dots, x^{k+1}_{i-1}, y, x^k_{i+1}, \dots, x^k_n)</math><ref>{{cite web |url=https://www.cs.cmu.edu/~ggordon/10725-F12/slides/25-coord-desc.pdf|title=Coordinate descent |first1=Geoff |last1=Gordon |first2=Ryan |last2=Tibshirani |publisher=Carnegie Mellon University |work=Optimization 10-725 / 36-725 |date=2012年秋 |accessdate=2025-03-10 }}</ref>

ただし、変数 <math>x_i</math> は <math>\mathbf{x}</math> の 1 から <math>n</math> までの添字 <math>i</math> に対応している。
 
すなわち、関数 <math>F</math> の極値を求めるため初期点 <math>\mathbf{x}^0</math> から開始し、点列 
<math>\mathbf{x}^0, \mathbf{x}^1, \mathbf{x}^2, \dots</math> を求めていく。

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

:<math>F(\mathbf{x}^0)\ge F(\mathbf{x}^1)\ge F(\mathbf{x}^2)\ge \dots.</math>

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

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

[[File:Coordinate descent.svg|center|500px]]

=== 微分可能な場合 ===
[[連続的微分可能]]関数 {{mvar|F}} での座標降下法は以下の手続きを行う{{r|wright}}:

<div style="margin-left: 35px; width: 600px">
{{枠の始まり|青}}
* 初期ベクトル {{math|'''x'''}} を選択する。
* 収束あるいは反復の上限回数に達するまで以下を反復:
** {{math|1}} から {{mvar|n}}での添字 {{mvar|i}} を選択する。
** ステップサイズ {{mvar|α}} を選択する。 
** {{mvar|x<sub>i</sub>}} を {{math|''x<sub>i</sub>'' − {{mvar|α}}{{sfrac|∂''F''|∂''x<sub>i</sub>''}}('''x''')}} に更新する。
{{枠の終わり}}
</div>

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

== 制限 ==
座標降下法は二つの問題を抱えている。一つ目は目的関数が[[滑らかな関数]]でない場合である。下記の図では目的関数の等高線が滑らかでない場合について、座標降下法の各反復において停留点でない点が求まってしまう例を挙げている。最小化問題に対して座標降下法において現在の反復が点 {{math|(−2, −2)}} であるとすると、次の探索方向として赤い矢印の方向に進むことが考えられるが、どちらの方向に進むことを考えても、この場合目的関数は増大してしまう。この場合座標方向に進まず、二つの探索方向を併せた方向に方向に進むことで目的関数は改善される。下記の図では最適解に収束しない例を紹介したが、ある条件の下では収束性を示すことができる<ref>{{cite journal |last=Spall |first=J. C. |year=2012 |title=Cyclic Seesaw Process for Optimization and Identification |journal=Journal of Optimization Theory and Applications |volume=154 |issue=1 |pages=187–208 |doi=10.1007/s10957-012-0001-1 |s2cid=7795605 }}</ref>。

[[File:Nonsmooth coordinate descent.svg|center|500px]]

二つ目の問題点として座標降下法の並列化が困難であることが挙げられる。座標降下法では各座標方向に順番に探索し、目的関数を改善することから、大規模な並列化は難しいとされる。近年の研究で座標降下法は各座標方向への目的関数の変化を緩和することによって大規模な並列化を可能にする手法が提案されている<ref>{{Cite journal|last1=Zheng|first1=J.|last2=Saquib|first2=S. S.|last3=Sauer|first3=K.|last4=Bouman|first4=C. A.|date=2000-10-01|title=Parallelizable Bayesian tomography algorithms with rapid, guaranteed convergence|journal=IEEE Transactions on Image Processing|volume=9|issue=10|pages=1745–1759|doi=10.1109/83.869186|pmid=18262913|issn=1057-7149|bibcode=2000ITIP....9.1745Z|citeseerx=10.1.1.34.4282}}</ref><ref>{{Cite journal|last1=Fessler|first1=J. A.|last2=Ficaro|first2=E. P.|last3=Clinthorne|first3=N. H.|last4=Lange|first4=K.|date=1997-04-01|title=Grouped-coordinate ascent algorithms for penalized-likelihood transmission image reconstruction|journal=IEEE Transactions on Medical Imaging|volume=16|issue=2|pages=166–175|doi=10.1109/42.563662|pmid=9101326|issn=0278-0062|hdl=2027.42/86021|s2cid=1523517|hdl-access=free}}</ref><ref>{{Cite book|last1=Wang|first1=Xiao|last2=Sabne|first2=Amit|last3=Kisner|first3=Sherman|last4=Raghunathan|first4=Anand|last5=Bouman|first5=Charles|last6=Midkiff|first6=Samuel|title=Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming |chapter=High performance model based image reconstruction |date=2016-01-01|series=PPoPP '16|location=New York, NY, USA|publisher=ACM|pages=2:1–2:12|doi=10.1145/2851141.2851163|isbn=9781450340922|s2cid=16569156|url=https://zenodo.org/record/895136}}</ref>。

== 応用 ==
座標降下法は単純な手続きで完結することから実用面においては人気のある解法となっているが、最適化理論に関する研究者の間ではより複雑な解法を注目することが多いことから、ほとんど研究されない解法となっている{{r|wright}}。座標降下法の初期の応用例として、コンピュータ断層撮影の分野が挙げられ<ref>{{cite journal|last1=Sauer|first1=Ken|last2=Bouman|first2=Charles|title=A Local Update Strategy for Iterative Reconstruction from Projections|journal= IEEE Transactions on Signal Processing|date=1993-02|volume=41|issue=2|pages=534–548|doi=10.1109/78.193196|url=https://engineering.purdue.edu/~bouman/publications/orig-pdf/sp2.pdf|bibcode=1993ITSP...41..534S|citeseerx=10.1.1.135.6045}}</ref>、この応用において座標降下法による収束の速さが良いことが判明したことから<ref>{{cite journal|last1=Yu|first1=Zhou|last2=Thibault|first2=Jean-Baptiste|last3=Bouman|first3=Charles|last4=Sauer|first4=Ken|last5=Hsieh|first5=Jiang|title=Fast Model-Based X-ray CT Reconstruction Using Spatially Non-Homogeneous ICD Optimization|journal=IEEE Transactions on Image Processing|date=2011-01|volume=20|issue=1|pages=161–175|doi=10.1109/TIP.2010.2058811|pmid=20643609|url=https://engineering.purdue.edu/~bouman/publications/orig-pdf/tip28.pdf|bibcode=2011ITIP...20..161Y|s2cid=9315957}}</ref>、臨床用のマルチスライスCTのヘリカルスキャン時に使用されるようになった <ref>{{cite journal|last1=Thibault|first1=Jean-Baptiste|last2=Sauer|first2=Ken|last3=Bouman|first3=Charles|last4=Hsieh|first4=Jiang|title=A Three-Dimensional Statistical Approach to Improved Image Quality for Multi-Slice Helical CT|journal=Medical Physics|date=2007-11|volume=34|issue=11|pages=4526–4544|doi=10.1118/1.2789499|pmid=18072519|url=https://engineering.purdue.edu/~bouman/publications/orig-pdf/medphys1.pdf|bibcode=2007MedPh..34.4526T}}</ref>。巡回座標降下法はタンパク質構造予測の面でも使用されるようになった<ref>{{Cite journal|last1=Canutescu|first1=AA|last2=Dunbrack|first2=RL|title=Cyclic coordinate descent: A robotics algorithm for protein loop closure.|periodical=Protein Science|year=2003|volume=12|issue=5|pages=963–72|pmid=12717019|doi=10.1110/ps.0242703|pmc=2323867}}</ref>。加えて、[[機械学習]]における大規模最適化問題に対する応用においても注目されるようになり、特に[[サポートベクターマシン]]の訓練時や{{仮リンク|非負値行列因子分解|en|non-negative matrix factorization}}において座標降下法を適用した際に、他の解法以上の優位性が示されている<ref>{{Cite book |last1=Hsieh |first1=C. J. |last2=Chang |first2=K. W. |last3=Lin |first3=C. J. |last4=Keerthi |first4=S. S. |last5=Sundararajan |first5=S. |doi=10.1145/1390156.1390208 |chapter=A dual coordinate descent method for large-scale linear SVM |title=Proceedings of the 25th international conference on Machine learning - ICML '08 |pages=408 |year=2008 |isbn=9781605582054 |s2cid=7880266 |chapter-url=http://ntu.csie.org/~cjlin/papers/cddual.pdf }}</ref><ref>{{Cite conference |last1=Hsieh |first1=C. J. |last2=Dhillon |first2=I. S. |doi=10.1145/2020408.2020577 |title=Fast coordinate descent methods with variable selection for non-negative matrix factorization |conference=Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '11 |pages=1064|year=2011 |isbn=9781450308137 |url=http://www.cs.utexas.edu/~cjhsieh/nmf_kdd11.pdf }}</ref>。また勾配の計算が難しいような問題に対しても適用されている<ref>{{cite journal |last=Nesterov |first=Yurii |author-link=:en:Yurii Nesterov |title=Efficiency of coordinate descent methods on huge-scale optimization problems |journal=SIAM J. Optim. |volume=22 |issue=2 |year=2012 |pages=341–362 |url=http://www.ulouvain.be/cps/ucl/doc/core/documents/coredp2010_2web.pdf |doi=10.1137/100802001|citeseerx=10.1.1.332.3336 }}</ref>。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==
*{{Citation |last1=Bezdek |first1=J. C. |last2=Hathaway |first2=R. J. |last3=Howard |first3=R. E. |last4=Wilson |first4=C. A. |last5=Windham |first5=M. P. |year=1987 |title=Local convergence analysis of a grouped variable version of coordinate descent |periodical=Journal of Optimization Theory and Applications |volume=54 |issue=3 |pages=471–477 |doi=10.1007/BF00940196 |publisher=Kluwer Academic/Plenum Publishers|s2cid=120052975 }}
* Bertsekas, Dimitri P. (1999). ''Nonlinear Programming, Second Edition'' Athena Scientific, Belmont, Massachusetts. {{ISBN|1-886529-00-0}}.
*{{Citation |last1=Luo |first1=Zhiquan |last2=Tseng |first2=P. |year=1992 |title=On the convergence of the coordinate descent method for convex differentiable minimization |periodical=Journal of Optimization Theory and Applications |volume=72 |issue=1 |pages=7–35 |doi=10.1007/BF00939948 |publisher=Kluwer Academic/Plenum Publishers|hdl=1721.1/3164 |s2cid=121091844 |hdl-access=free }}.
*{{Citation |last1=Wu |first1=TongTong |last2=Lange |first2=Kenneth |year=2008 |title=Coordinate descent algorithms for Lasso penalized regression |periodical=The Annals of Applied Statistics |volume=2 |issue=1 |pages=224–244 |doi=10.1214/07-AOAS147 |publisher=Institute of Mathematical Statistics|arxiv=0803.3876 |s2cid=16350311 }}.
*{{Citation |last1=Richtarik |first1=Peter |last2=Takac |first2=Martin |date=2011-04 |title=Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function |periodical=Mathematical Programming |doi=10.1007/s10107-012-0614-z |publisher=Springer |volume=144 |issue=1–2 |pages=1–38|arxiv=1107.2848 |s2cid=16816638 }}.
*{{Citation |last1=Richtarik |first1=Peter |last2=Takac |first2=Martin |date=2012-12 |title=Parallel coordinate descent methods for big data optimization |periodical=ArXiv:1212.0873|arxiv=1212.0873 }}.

== 関連項目 ==
* {{仮リンク|適応型座標降下法|en|Adaptive coordinate descent}}
* {{annotated link|共役勾配法}}
* {{annotated link|最急降下法}}
* {{annotated link|直線探索}}
* {{annotated link|数理最適化}}
* {{annotated link|最適化におけるニュートン法}}
* {{annotated link|確率的勾配降下法}}

{{最適化アルゴリズム}}

{{DEFAULTSORT:さひようこうかほう}}
[[Category:勾配法]]
[[Category:最適化アルゴリズムとメソッド]]
[[Category:数学に関する記事]]