勾配降下アルゴリズムが収束しない

Question

スタンフォード機械学習講義（lecture 2 at around 25:00）で説明した勾配降下アルゴリズムのコードを少し書いてみようとしています。以下は私が最初に使った実装ですが、講義から正しくコピーされていると思いますが、大きな数字（>8）をトレーニングセットに追加すると収束しません。

私は数Xを入力していて、現時点では、私はそれだけがy=ax+bどこa=1=theta\[1\]とb=0=theta\[0\]に収束するために取得しようとしているのでpoint (X,X)は、訓練セットに追加されます。 トレーニングセットは配列xとyです。(x[i],y[i])がポイントです。

void train() 
{ 
    double delta; 
    for (int i = 0; i < x.size(); i++) 
    { 
     delta = y[i]-hypothesis(x[i]); 
     theta[1] += alpha*delta*x[i]; 
     theta[0] += alpha*delta*1; 
    } 
} 

void C_Approx::display() 
{ 
    std::cout<<theta[1]<<"x + "<<theta[0]<<" \t "<<"f(x)="<<hypothesis(1)<<std::endl; 
} 

私は取得していた結果の一部

：

： I入力数は、それがその後、 display()

1 
0.33616x + 0.33616 f(x)=0.67232 
1 
0.482408x + 0.482408  f(x)=0.964816 
1 
0.499381x + 0.499381  f(x)=0.998762 
1 
0.499993x + 0.499993  f(x)=0.999986 
1 
0.5x + 0.5 f(x)=1 

それは8を通過した後、それが発散の例train()数回、実行します

1 
0.33616x + 0.33616 f(x)=0.67232 
2 
0.705508x + 0.509914  f(x)=1.21542 
3 
0.850024x + 0.449928  f(x)=1.29995 
4 
0.936062x + 0.330346  f(x)=1.26641 
5 
0.951346x + 0.231295  f(x)=1.18264 
6 
0.992876x + 0.137739  f(x)=1.13062 
7 
0.932206x + 0.127372  f(x)=1.05958 
8 
1.00077x + 0.000493063 f(x)=1.00126 
9 
-0.689325x + -0.0714712  f(x)=-0.760797 
10 
4.10321e+08x + 4.365e+07  f(x)=4.53971e+08 
11 
1.79968e+22x + 1.61125e+21 f(x)=1.9608e+22 
12 
-3.9452e+41x + -3.26957e+40  f(x)=-4.27216e+41 

解決策を試して、ステップをスケーリングするhereを試み、同様の結果に終わった。 私は何が間違っていますか？

Answer 1

あなたの実装は良いです。一般に、確率的勾配降下は、αが大き過ぎると発散する可能性がある。大規模なデータセットで行うことは、合理的なサイズのランダムサンプルを取って、最良の結果をもたらすαを見つけて、それを残りの部分に使用することです。

Answer 2

あなたが正しく理解している場合、トレーニングセットの線の端にゼロ以外の勾配しかありませんか？あなたがラインで始まらない限り（実際にあなたのトレーニングポイントの1つで始まる）、ラインを見つけることはできません。あなたは常に地元の最小限の人です。

Answer 3

コスト関数が増加または減少すると、通常はalphaの値が大きすぎます。何を使用していますかalpha

alpha = 0.001で始まり、それが収束するかどうかを確認してください。いろいろ試してみると、alphas(0.003, 0.01, 0.03, 0.1, 0.3, 1)となり、すばやく収束するものが見つかります。

ノーマライゼーションとして1つのフィーチャ（theta[1]）しか使用できない場合は、2+フィーチャ（多変量線形回帰）にのみ適用されます。

また、少数のフィーチャでは、正規方程式を使用して正解を得ることができます。

Answer 4

私は学習率が大きすぎるため（Javaでも）同じ問題が発生しました。
つまり、私はα = 0.001を使用していました。実際のコンバージェンスを確認するには、0.000001にプッシュしなければなりませんでした。

もちろん、これらの値はデータセットにリンクされています。

Answer 5

コンバージェンスを保証するバックトラックライン検索を使用します。実装が非常に簡単です。参考までにStephen Boyd、Convex Optimizationを参照してください。バックトラック行の検索には、アルファ、ベータの標準値をいくつか選択することができます（例：0.3と0.8）。