Javaで線形回帰を実装しようとしています。私の仮説は theta0 + theta1 * x[i] です。コスト関数が最小になるように、theta0 と theta1 の値を把握しようとしています。勾配降下法を使用して値を見つけています-
の中に
while(repeat until convergence)
{
calculate theta0 and theta1 simultaneously.
}
この収束までの繰り返しは何ですか？これが局所的な最小値であることは理解しましたが、while ループに入れる正確なコードは何ですか?
私は機械学習の初心者で、理解を深めるために基本的なアルゴリズムのコーディングを始めたばかりです。どんな助けでも大歓迎です。
勾配降下法は、与えられた関数を最小化するための反復アプローチです。解の初期推定から始め、その時点での関数の勾配を取得します。勾配の負の方向に解を進め、プロセスを繰り返します。アルゴリズムは最終的に、勾配がゼロ (極小値に対応) になる場所に収束します。したがって、あなたの仕事は、損失関数を最小化する theta0 と theta1 の値を見つけることです [たとえば、最小二乗誤差]。「収束」という用語は、局所的な最小値に到達し、それ以上の反復がパラメーターの値に影響を与えないことを意味します。つまり、theta0 と theta1 の値は一定のままです。例を見てみましょう 注: この説明では、最初の象限にあると仮定します。
関数 f(x) [あなたのケースではコスト関数] を最小化する必要があるとしましょう。このためには、f(x) の関数値を最小化する x の値を見つける必要があります。これは、勾配降下法を使用して x の値を見つけるための段階的な手順です。
x = x - [Some positive value]。これにより、x が D [つまり最小値] に近づき、f(x) の関数値が減少します [図から]。反復 1 の後、点 B に到達したとします。x = x - [0]。同じ x [または前の x に非常に近い値] が得られます。この状態は「収束」として知られています。上記の手順は勾配を増加させるためのものですが、勾配を減少させる場合にも同様に有効です。たとえば、点 G の勾配は負の値になります。x ie を更新するとx = x - [ negative value] = x - [ - some positive value] = x + some positive value。これにより x の値が増加し、x が点 F [または最小値に近づく] に近づきます。この勾配降下を解決するには、さまざまなアプローチがあります。@mattnedrichが言ったように、2つの基本的なアプローチは
この擬似コードは次のようになるため、反復回数 N を使用します。
iter = 0
while (iter < N) {
theta0 = theta0 - gradient with respect to theta0
theta1 = theta1 - gradient with respect to theta1
iter++
}
勾配降下法は、線形回帰で関数を最小化するアプローチの 1 つです。直接解もある。バッチ処理 (正規方程式とも呼ばれます) を使用すると、1 つのステップで theta0 と theta1 の値を見つけることができます。X が入力行列、y が出力ベクトル、シータが計算するパラメーターの場合、二乗誤差法では、この行列方程式を使用して 1 つのステップでシータの値を見つけることができます。
theta = inverse(transpose (X)*X)*transpose(X)*y
しかし、これには行列計算が含まれているため、行列 X のサイズが大きい場合、勾配降下法よりも明らかに計算コストが高くなります。これがあなたの質問に答えてくれることを願っています。そうでない場合は、お知らせください。
Gradient Descent は最適化アルゴリズムです (正確には最小化、最大化には勾配上昇もあります)。線形回帰の場合、コスト関数を最小化します。これは勾配ベースの最適化ファミリーに属し、その考え方は、負の勾配でコストを差し引いたときに、コスト面の丘を最適化するというものです。
アルゴリズムでは、収束まで繰り返すとは、コスト面/曲線の最適点に到達することを意味します。これは、いくつかの反復で勾配がゼロに非常に近い場合に決定されます。その場合、アルゴリズムは収束したと言われます (局所最適にある可能性があり、多くの場合、勾配降下法が局所最適に収束することは明らかです)。
アルゴリズムが収束したかどうかを判断するには、次のようにします。
calculate gradient
theta = theta -gradientTheta
while(True):
calculate gradient
newTheta = theta - gradient
if gradient is very close to zero and abs(newTheta-Theta) is very close to zero:
break from loop # (The algorithm has converged)
theta = newTheta
線形回帰と勾配降下法、およびその他の最適化の詳細については、Andrew Ng のノートhttp://cs229.stanford.edu/notes/cs229-notes1.pdfを参照してください。
theta[0]最初にとを任意の値に割り当ててtheta[1]から、仮説 の値を計算(theta[0] +theta[1]*x1)し、勾配降下アルゴリズムによって と を計算theta[0]しtheta[1]ます。アルゴリズムによって:
theta[0](new) = theta[0](old) - alpha*[partialderivative(J(theta[0],theta[1]) w.r.t theta[0])
theta[1](new) = theta[1](old) - alpha*[partialderivative(J(theta[0],theta[1]) w.r.t theta[1])
alpha: 学習率
J(theta[0],theta[1])=cost function
theta[0]との新しい値を取得しますtheta[1]。次に、仮説の新しい値を再度計算する必要があります。との差が 未満になるまで、theta[0]とを計算するこのプロセスを繰り返します。theta[1]theta[i](new)theta[i](old)0.001
詳細については、http: //cs229.stanford.edu/notes/cs229-notes1.pdfを参照してください。
勾配下降についてはよくわかりませんが、いくつかのポイントを使用して線形回帰を計算する別の方法を学びました。
http://en.wikipedia.org/wiki/Simple_linear_regression#Fitting_the_regression_line
ただし、while ループを本当に追加したい場合は、次のことをお勧めします。
最終的に、theta0 と theta1 は特定の値に収束します。これは、式を何度適用しても、常にその値の近くにとどまることを意味します。( http://en.wikipedia.org/wiki/(%CE%B5,_%CE%B4)-definition_of_limit )。
したがって、コードをもう一度適用しても、theta0 と theta1 はあまり変化せず、ごくわずかです。または: theta0(1) と次の theta0(1) の差が一定量より小さい。
これにより、次のコードが得られます。
double little = 1E-10;
do {
$theta0 = theta0;
$theta1 = theta1;
// now calculate the new theta0, theta1 simultaneously.
} while(Math.abs(theta0-$theta0) + Math.abs(theta1-$theta1)>little);
while ループ内で次の操作を行う必要があります。
while (some condition is not met)
// 1) Compute the gradient using theta0 and theta1
// 2) Use the gradient to compute newTheta0 and newTheta1 values
// 3) Set theta0 = newTheta0 and theta1 = newTheta1
勾配降下法検索を終了するために、いくつかの異なる基準を使用できます。たとえば、勾配降下を実行できます
反復するたびに、最適解にどんどん近づいていく必要があります。つまり、反復ごとに誤差 (theta0、theta1 モデルがデータをどれだけうまく予測するか) を計算すると、誤差はどんどん小さくなっていきます。
このコードを実際に記述する方法については、https://www.youtube.com/watch?v=CGHDsi_l8F4&list=PLnnr1O8OWc6ajN_fNcSUz9k5gF_E9huF0 を参照してください
。