勾配法 - 変更履歴

2020年11月25日 (水) 14:26 における Moderator による編集

Moderator — Wed, 25 Nov 2020 14:26:46 GMT

←前の版		2020年11月25日 (水) 14:26時点における版
119 行:		119 行:


-	関数<math>l({\bf x})</math>が解析的な関数なら,	+	これを一般化する.関数<math>l({\bf x})</math>が解析的な関数なら,

	<math>		<math>

2020年11月25日 (水) 10:26 における Moderator による編集

Moderator — Wed, 25 Nov 2020 10:26:59 GMT

←前の版		2020年11月25日 (水) 10:26時点における版
1 行:		1 行:
-
	==一次アルゴリズム==		==一次アルゴリズム==
	<math>		<math>
230 行:		229 行:
	<math>		<math>
	l({\bf x}_n+\epsilon_n {\bf \eta }_n)		l({\bf x}_n+\epsilon_n {\bf \eta }_n)
-	=\min_{~~\epsilon,~~\epsilon>0} l({\bf x}_n+\epsilon {\bf \eta }_n)\\	+	=\min_{\epsilon>0} l({\bf x}_n+\epsilon {\bf \eta }_n)\\
	{\bf x}_{n+1}={\bf x}_n+\epsilon_n {\bf \eta }_n \\		{\bf x}_{n+1}={\bf x}_n+\epsilon_n {\bf \eta }_n \\
	{\bf \eta}_{n+1}:{\bf x}_{n+1}によって決まる何らかの方向ベクトル		{\bf \eta}_{n+1}:{\bf x}_{n+1}によって決まる何らかの方向ベクトル

2020年11月25日 (水) 08:50 における Moderator による編集

Moderator — Wed, 25 Nov 2020 08:50:20 GMT

←前の版		2020年11月25日 (水) 08:50時点における版
273 行:		273 行:

	これは<math>{\bf y}</math>についての２次式である。この式が<math>{\bf y}</math>について,極小になるための		これは<math>{\bf y}</math>についての２次式である。この式が<math>{\bf y}</math>について,極小になるための
-	条件は,極値条件(<math>{\bf y}</math>についての微分が{\bf 0}ベクトル)	+	条件は,極値条件(<math>{\bf y}</math>についての微分が<math>{\bf 0}</math>ベクトル)

	<math>		<math>

2020年11月25日 (水) 08:46 における Moderator による編集

Moderator — Wed, 25 Nov 2020 08:46:39 GMT

←前の版		2020年11月25日 (水) 08:46時点における版
223 行:		223 行:
	<math>		<math>
	l({\bf x}_n-\epsilon_n \frac{d l}{d {\bf x}}({\bf x}_n))		l({\bf x}_n-\epsilon_n \frac{d l}{d {\bf x}}({\bf x}_n))
-	=\min_{~~\epsilon,~~\epsilon>0} l({\bf x}_n-\epsilon \frac{d l}{d {\bf x}}({\bf x}_n))	+	=\min_{\epsilon>0} l({\bf x}_n-\epsilon \frac{d l}{d {\bf x}}({\bf x}_n))
	</math>		</math>

243 行:		243 行:
	を生成し,		を生成し,
	<math>		<math>
-	\lim_{n \to \infty }l({\bf x}_n)　=\min_{{\bf x}} l({\bf x})	+	\lim_{n \to \infty }l({\bf x}_n)= \min_{\bf x} l({\bf x})
	</math>		</math>

281 行:		281 行:

	である。これから,行列		である。これから,行列
-
	<math>		<math>
	\frac{d^2 l}{d {\bf x}^2}({\bf x})		\frac{d^2 l}{d {\bf x}^2}({\bf x})
	</math>		</math>
-
	が正則(逆行列をもつ)とすれば,		が正則(逆行列をもつ)とすれば,

2020年11月25日 (水) 08:42 における Moderator による編集

Moderator — Wed, 25 Nov 2020 08:42:53 GMT

←前の版		2020年11月25日 (水) 08:42時点における版
243 行:		243 行:
	を生成し,		を生成し,
	<math>		<math>
-	\lim_{n \to \infty } 　l({\bf x}_n)　=\min_{{\bf x}} l({\bf x})	+	\lim_{n \to \infty }l({\bf x}_n)　=\min_{{\bf x}} l({\bf x})
	</math>		</math>

2020年11月25日 (水) 08:40 における Moderator による編集

Moderator — Wed, 25 Nov 2020 08:40:20 GMT

←前の版		2020年11月25日 (水) 08:40時点における版
1 行:		1 行:

-	== ~~１次アルゴリズム~~ ==	+	==一次アルゴリズム==
-		+
-	~~関数の勾配~~	+
	<math>		<math>
	l(x,y)=x+y+x^2+y^2		l(x,y)=x+y+x^2+y^2
131 行:		129 行:
	</math>		</math>

-	となる．<math>{\bf o}(\Delta {\bf x})<math>は３次以上の高位の項である。	+	となる．<math>{\bf o}(\Delta {\bf x})</math>は３次以上の高位の項である。

-	== 勾配を使う計算法 ==	+	==勾配を使う計算法==

	<math>l({\bf x})=l(x,y)</math>を最小化するため先ず,		<math>l({\bf x})=l(x,y)</math>を最小化するため先ず,
250 行:		248 行:
	とする計算法は,一次アルゴリズムと呼ばれている．		とする計算法は,一次アルゴリズムと呼ばれている．

-	==~~２次アルゴリズム~~==	+	==2次アルゴリズム==

2020年11月25日 (水) 08:35 における Moderator による編集

Moderator — Wed, 25 Nov 2020 08:35:44 GMT

←前の版		2020年11月25日 (水) 08:35時点における版
191 行:		191 行:
	{\bf z}^T{\bf z}=p^2+q^2		{\bf z}^T{\bf z}=p^2+q^2
	</math>		</math>
-	~~である,~~<math>{\bf z}^T{\bf z} \ge 0	+	であるから<math>{\bf z}^T{\bf z} \ge 0
	</math>である。		</math>である。

208 行:		208 行:

	<math>0 \lt \epsilon</math>が十分小さければ,		<math>0 \lt \epsilon</math>が十分小さければ,
-
	<math>		<math>
	\Delta {\bf x} = -\epsilon \frac{d l}{d {\bf x}}({\bf x}_0)		\Delta {\bf x} = -\epsilon \frac{d l}{d {\bf x}}({\bf x}_0)
	</math>		</math>
-
	として,		として,
-
	<math>l({\bf x}_0 +\Delta {\bf x}) < l({\bf x}_0)</math>		<math>l({\bf x}_0 +\Delta {\bf x}) < l({\bf x}_0)</math>
	となる．		となる．
248 行:		245 行:
	を生成し,		を生成し,
	<math>		<math>
-	\lim_{n \to \infty } l({\bf x}_n)=min_{{\bf x}}l({\bf x})	+	\lim_{n \to \infty } 　l({\bf x}_n)　=\min_{{\bf x}} l({\bf x})
	</math>		</math>

2020年11月25日 (水) 08:28 における Moderator による編集

Moderator — Wed, 25 Nov 2020 08:28:45 GMT

←前の版		2020年11月25日 (水) 08:28時点における版
1 行:		1 行:

-	１次アルゴリズム	+	== １次アルゴリズム ==

	関数の勾配		関数の勾配
6 行:		6 行:
	l(x,y)=x+y+x^2+y^2		l(x,y)=x+y+x^2+y^2
	</math>		</math>
-	~~を例にとって説明します。~~<math>l(x,y)</math>を	+	を例にとる.<math>l(x,y)</math>を列ベクトルと行列
-	~~列ベクトルと行列~~	+

	<math>		<math>
60 行:		59 行:

	から		から
-
	<math>		<math>
	l({\bf x}) ={\bf p}^T {\bf x} + {\bf x}^T {\bf Q}{\bf x}		l({\bf x}) ={\bf p}^T {\bf x} + {\bf x}^T {\bf Q}{\bf x}
	</math>		</math>
-
	と書ける．		と書ける．

90 行:		87 行:
	</math>		</math>

		+	である。

-	~~である。~~
	また,<math>l({\bf x})</math>の２階微分は		また,<math>l({\bf x})</math>の２階微分は

97 行:		94 行:
	\frac{d^2 l}{d {\bf x}^2}({\bf x})= {\bf Q}		\frac{d^2 l}{d {\bf x}^2}({\bf x})= {\bf Q}
	</math>		</math>
-
	である。		である。

109 行:		105 行:
	\right )		\right )
	</math>		</math>
-		+	とすると
-	~~として,~~	+

	<math>		<math>
124 行:		119 行:
	</math>		</math>

-	~~結局,~~	+	である.

-	~~<math>~~
-	~~l({\bf x} +\Delta {\bf x})~~
-	~~=l({\bf x})+\frac{d l}{d {\bf x}}({\bf x})^T\Delta {\bf x}~~
-	~~+\frac{1}{2} \Delta {\bf x}^T \frac{d^2 l}{d {\bf x}^2}({\bf x})~~
-	~~\Delta {\bf x}~~
-	~~</math>~~

-	~~となる．~~	+	関数<math>l({\bf x})</math>が解析的な関数なら,

-	~~無論,一般の関数<math>l({\bf x})<math>,解析的な関数なら,~~
	<math>		<math>
	l({\bf x} +\Delta {\bf x})		l({\bf x} +\Delta {\bf x})
142 行:		130 行:
	\Delta {\bf x} +{\bf o}(\Delta {\bf x})		\Delta {\bf x} +{\bf o}(\Delta {\bf x})
	</math>		</math>
		+
	となる．<math>{\bf o}(\Delta {\bf x})<math>は３次以上の高位の項である。		となる．<math>{\bf o}(\Delta {\bf x})<math>は３次以上の高位の項である。

-	勾配を使う計算法	+	== 勾配を使う計算法 ==

-	<math>l({\bf x})=l(x,y)</math>~~を最小化するため,先ず~~,	+	<math>l({\bf x})=l(x,y)</math>を最小化するため先ず,

-	~~初期点~~	+	初期点
	<math>		<math>
	{\bf x}_0=		{\bf x}_0=
158 行:		147 行:
	\right )		\right )
	</math>		</math>
-
	を与えて,<math>l({\bf x}_0)</math>を求め,次に,		を与えて,<math>l({\bf x}_0)</math>を求め,次に,

189 行:		177 行:

	ここで,任意のベクトル		ここで,任意のベクトル
-
	<math>		<math>
	{\bf z}		{\bf z}
199 行:		186 行:
	\right )		\right )
	</math>		</math>
-
	について		について

205 行:		191 行:
	{\bf z}^T{\bf z}=p^2+q^2		{\bf z}^T{\bf z}=p^2+q^2
	</math>		</math>
-	である,<math>{\bf z}^T{\bf z} \ge 0</math>~~である。同様に~~,	+	である,<math>{\bf z}^T{\bf z} \ge 0
		+	</math>である。
		+
		+	同様に,
		+
	<math>		<math>
	\frac{d l}{d {\bf x}}({\bf x}_0) ^T \frac{d l}{d {\bf x}}({\bf x}_0) \ge 0		\frac{d l}{d {\bf x}}({\bf x}_0) ^T \frac{d l}{d {\bf x}}({\bf x}_0) \ge 0
	</math>		</math>
-

	<math>		<math>
218 行:		207 行:
	である。		である。

-	<math>\epsilon</math>が十分小さければ,	+	<math>0 \lt \epsilon</math>が十分小さければ,

	<math>		<math>
232 行:		221 行:
	{\bf x}_1 ={\bf x}_0 +\Delta {\bf x}		{\bf x}_1 ={\bf x}_0 +\Delta {\bf x}
	</math>		</math>
-	~~を新たな初期点としてこれを繰り返すことができる．このような方法を勾配法と呼ばれる．特に~~,毎回の繰り返しで,	+	を新たな初期点としてこれを繰り返すことができる．このような方法を勾配法と呼ばれる．
		+
		+
		+	特に,毎回の繰り返しで,

	<math>		<math>
260 行:		252 行:

	とする計算法は,一次アルゴリズムと呼ばれている．		とする計算法は,一次アルゴリズムと呼ばれている．
-	２次アルゴリズム	+
		+	==２次アルゴリズム==
		+

	<math>		<math>

2020年11月25日 (水) 08:17 における Moderator による編集

Moderator — Wed, 25 Nov 2020 08:17:42 GMT

差分を表示

Moderator: ページの作成: １次アルゴリズム関数の勾配 $l(x,y)=x+y+x^2+y^2$ を例にとって説明します。 $l(x,y)$ を列ベクトルと行列 ${\bf p} =\…$

Moderator — Wed, 25 Nov 2020 05:33:53 GMT

ページの作成: １次アルゴリズム関数の勾配 <math> l(x,y)=x+y+x^2+y^2 </math> を例にとって説明します。<math>l(x,y)</math>を列ベクトルと行列 <math> {\bf p} =\…

新規ページ

１次アルゴリズム

関数の勾配
<math>
l(x,y)=x+y+x^2+y^2
</math>
を例にとって説明します。<math>l(x,y)</math>を
列ベクトルと行列
<math>
{\bf p}
=\left (
\begin{array}{c}
1\\
1\\
\end{array}
\right ),
{\bf x}
=\left (
\begin{array}{c}
x\\
y\\
\end{array}
\right ),
{\bf Q}=
\left (
\begin{array}{cc}
1&0\\
0&1\\
\end{array}
\right )
</math>
を使って表現すると

<math>
l(x,y)
=(1,1)
\left (
\begin{array}{c}
x\\
y\\
\end{array}
\right )
+ (x,y)
\left (
\begin{array}{cc}
1&0\\
0&1\\
\end{array}
\right )
\left (
\begin{array}{c}
x\\
y\\
\end{array}
\right )
</math>

から
<math>
l({\bf x}) ={\bf p}^T {\bf x} + {\bf x}^T {\bf Q}{\bf x}
</math>
と書ける．

ここで,<math>l(x,y)</math>の<math>x,y</math>についての偏微分係数はそれぞれ,
<math>
\frac{\partial l}{\partial x}(x,y)=1+x \\
\frac{\partial l}{\partial y}(x,y)=1+y
</math>
である。これらを要素にもつ列ベクトルは,
<math>l({\bf x})=l(x,y)</math>の<math>{\bf x}</math>について
の微分であり,
<math>
\frac{d l}{d {\bf x}}({\bf x})
=\left (
\begin{array}{c}
\frac{\partial l}{\partial x}(x,y)\\
\frac{\partial l}{\partial y}(x,y)\\
\end{array}
\right )
={\bf p}+ 2 {\bf Q} {\bf x}
</math>
である。
また,<math>l({\bf x})</math>の２階微分は
<math>
\frac{d^2 l}{d {\bf x}^2}({\bf x})= {\bf Q}
</math>
である。さて,
<math>
\Delta {\bf x}=
\left (
\begin{array}{c}
\Delta x\\
\Delta y\\
\end{array}
\right )
</math>
として,
<math>
l({\bf x} +\Delta {\bf x}) \\
={\bf p}^T ( {\bf x} +\Delta {\bf x})
+ ({\bf x}+\Delta {\bf x})^T {\bf Q}({\bf x}+\Delta {\bf x}) \\
={\bf p}^T {\bf x} +{\bf x}^T {\bf Q} {\bf x}
+{\bf p}^T \Delta {\bf x}) +2{\bf x}^T {\bf Q} \Delta {\bf x}
+\frac{1}{2} \Delta {\bf x}^T {\bf Q} \Delta {\bf x} \\
=l({\bf x})+\frac{d l}{d {\bf x}}({\bf x})^T\Delta {\bf x}
+\frac{1}{2} \Delta {\bf x}^T \frac{d^2 l}{d {\bf x}^2}({\bf x})
\Delta {\bf x}
</math>

結局,

<math>
l({\bf x} +\Delta {\bf x})
=l({\bf x})+\frac{d l}{d {\bf x}}({\bf x})^T\Delta {\bf x}
+\frac{1}{2} \Delta {\bf x}^T \frac{d^2 l}{d {\bf x}^2}({\bf x})
\Delta {\bf x}
</math>

となる．

無論,一般の関数<math>l({\bf x})<math>,解析的な関数なら,
<math>
l({\bf x} +\Delta {\bf x})
=l({\bf x})+\frac{d l}{d {\bf x}}({\bf x})^T\Delta {\bf x}
+\frac{1}{2} \Delta {\bf x}^T \frac{d^2 l}{d {\bf x}^2}({\bf x})
\Delta {\bf x} +{\bf o}(\Delta {\bf x})
</math>
となる．<math>{\bf o}(\Delta {\bf x})<math>は３次以上の高位の項である。

勾配を使う計算法
さて,<math>l({\bf x})=l(x,y)</math>を最小化するため,先ず,
初期点
<math>
{\bf x}_0=
\left (
\begin{array}{c}
x_0\\
y_0\\
\end{array}
\right )
</math>
を与えて,<math>l({\bf x}_0)</math>を求め,次に,

<math>{\bf x}={\bf x}_0</math>での<math>l({\bf x})</math>の微分,
<math>
\frac{d l}{d {\bf x}}({\bf x}_0)
= {\bf p}+ {\bf Q}{\bf x}_0
</math>
を求め,これと微小な正数<math>\epsilon >0</math>を使って,

<math>
\Delta {\bf x} = -\epsilon \frac{d l}{d {\bf x}}({\bf x}_0)
</math>
として,<math>l({\bf x}_0 +\Delta {\bf x})</math>を計算すると,

<math>
l({\bf x}_0 +\Delta {\bf x}) \\
=l({\bf x}_0)+\frac{d l}{d {\bf x}}({\bf x}_0)^T\Delta {\bf x}
+\frac{1}{2} \Delta {\bf x}^T \frac{d^2 l}{d {\bf x}^2}({\bf x}_0)
\Delta {\bf x} \\
=l({\bf x}_0)
-\epsilon \frac{d l}{d {\bf x}}({\bf x}_0) ^T \frac{d l}{d {\bf x}}({\bf x}_0)
+\epsilon^2 \frac{d l}{d {\bf x}}({\bf x}_0)^T
\frac{d^2 l}{d^2 {\bf x}}({\bf x}_0)
\frac{d l}{d {\bf x}}({\bf x}_0)\\
</math>

ここで,任意のベクトル
<math>
{\bf z}
=\left (
\begin{array}{c}
p\\
q\\
\end{array}
\right )
</math>
について
<math>
{\bf z}^T{\bf z}=p^2+q^2
</math>
である,<math>{\bf z}^T{\bf z} \ge 0</math>である。同様に,
<math>
\frac{d l}{d {\bf x}}({\bf x}_0) ^T \frac{d l}{d {\bf x}}({\bf x}_0) \ge 0
</math>
<math>
\frac{d l}{d {\bf x}}({\bf x}_0)^T
{\bf Q} \frac{d l}{d {\bf x}}({\bf x}_0) \ge 0
</math>
である。<math>\epsilon</math>が十分小さければ,
<math>
\Delta {\bf x} = -\epsilon \frac{d l}{d {\bf x}}({\bf x}_0)
</math>
として,

<math>l({\bf x}_0 +\Delta {\bf x}) < l({\bf x}_0)</math>
となる．
<math>
{\bf x}_1 ={\bf x}_0 +\Delta {\bf x}
</math>
を新たな初期点としてこれを繰り返すことができる．このような方法を勾配法と呼ばれる．特に,毎回の繰り返しで,
<math>
l({\bf x}_n-\epsilon_n \frac{d l}{d {\bf x}}({\bf x}_n))
=\min_{\epsilon,\epsilon>0} l({\bf x}_n-\epsilon \frac{d l}{d {\bf x}}({\bf x}_n))
</math>
となるように,<math>\epsilon_n</math>を選ぶ繰り返し計算法を最急降下法と呼ぶ．

<math>
l({\bf x}_n+\epsilon_n {\bf \eta }_n)
=\min_{\epsilon,\epsilon>0} l({\bf x}_n+\epsilon {\bf \eta }_n)\\
{\bf x}_{n+1}={\bf x}_n+\epsilon_n {\bf \eta }_n \\
{\bf \eta}_{n+1}:{\bf x}_{n+1}によって決まる何らかの方向ベクトル
</math>
を繰り返しながら
<math>
\{ {\bf x}_n\},\{{\bf \eta }_n \},\{ \epsilon_n \}
</math>
を生成し,
<math>
\lim_{n \to \infty } l({\bf x}_n)=min_{{\bf x}}l({\bf x})
</math>
とする計算法は,一次アルゴリズムと呼ばれている．
２次アルゴリズム
<math>
l({\bf x} +\Delta {\bf x})
=l({\bf x})+\frac{d l}{d {\bf x}}({\bf x})^T\Delta {\bf x}
+\frac{1}{2} \Delta {\bf x}^T \frac{d^2 l}{d {\bf x}^2}({\bf x})
\Delta {\bf x}
</math>
を使って,高速なアルゴリズムを造る．
<math>
\Delta {\bf x}={\bf y}-{\bf x}
</math>
とおき,上の式の右辺を書き換える．
<math>
l({\bf x})+\frac{d l}{d {\bf x}}({\bf x})^T({\bf y}-{\bf x})
+\frac{1}{2} ({\bf y}-{\bf x})^T \frac{d^2 l}{d {\bf x}^2}({\bf x})
({\bf y}-{\bf x})
</math>
これは<math>{\bf y}</math>についての２次式である。この式が<math>{\bf y}</math>について,極小になるための
条件は,極値条件(<math>{\bf y}</math>についての微分が{\bf 0}ベクトル)
<math>
\frac{d l}{d {\bf x}}({\bf x})+\frac{d^2 l}{d {\bf x}^2}({\bf x})
{\bf y}={\bf 0}
</math>
である。これから,行列
<math>
\frac{d^2 l}{d {\bf x}^2}({\bf x})
</math>
が正則(逆行列をもつ)とすれば,
<math>
{\bf y}=-(\frac{d^2 l}{d {\bf x}^2}({\bf x}))^{-1}\frac{d l}{d {\bf x}}({\bf x})</math>
が得られる．

<math>
{\bf x}_{k+1}=-(\frac{d^2 l}{d {\bf x}^2}({\bf x}_k))^{-1}
\frac{d l}{d {\bf x}}({\bf x}_k)
</math>
を繰り返すアルゴリズムはニュートン法と呼ばれる．