最急降下法

一ヶ月ぶりに会社復帰してみたら、ひょんな手違いから『イントラ八分』されてしまった。

暇で仕方ないので、後輩の教育に勤しんでみた。

最急降下法

最急降下法(wikipedia)
多数のパラメータセットの最適値を探索する手法。
局所解に当たる事も多いが、処理が単純（高速）で収束が非常に早いので重宝するアルゴリズムです。

個人的には、昔リバーシ（３０次元近いパラメータセットを扱う）のAIエンジンをPentium６００MHｚ程度で頑張ってた時期にお世話になってます。

肝は、各パラメータが結果に及ぼす影響を単純に評価（偏微分）するので、多項式時間で解決出来る点です。
全パラメータを同時進行するので乱暴ですが調整次第で大抵は巧くいきます。

課題

方程式： V = x^2 + 2x + 3y^2 - 4y + 2z^2 - 5z
のV最小値を求めよ！

単純な３つの変数の２次方程式の和なので、外乱要素が無く
因数分解すれば一瞬ですが最急降下法でも一瞬で終わります。

どんな言語でも良いから一週間で書けよ！と。。

C++の回答

方程式をx,y,zで偏微分して適当に収束させるだけ。。
判ってれば１０分ですね。
（前に似たような問題を入社試験にも出した気がします）

#include <iostream>
#include <math.h>
using namespace std;
// x^2 + 2x + 3y^2 - 4y + 2z^2 - 5z

static const double D=0.0001;
static const double A=0.001;
static const double E=0.00001;

double formula(double x , double y , double z ){
  return x*x + 2*x + 3*y*y - 4*y + 2*z*z - 5*z;
}
double pd_x(double x , double y , double z ){
  return (formula(x+D,y,z) - formula(x,y,z))/D;
}
double pd_y(double x , double y , double z ){
  return (formula(x,y+D,z) - formula(x,y,z))/D;
}
double pd_z(double x , double y , double z ){
  return (formula(x,y,z+D) - formula(x,y,z))/D;
}

double loop(double x , double y , double z ){
  for(;;){
    double dx = pd_x(x,y,z)*A;
    double dy = pd_y(x,y,z)*A;
    double dz = pd_z(x,y,z)*A;
    cout  << "[" << dx << "," << dy << "," << dz << "]" << "(" << x << "," << y << "," << z << ") = " << formula(x,y,z) << endl;
    if ( fabs(dx) < E &&
         fabs(dx) < E &&
         fabs(dx) < E ){
      return formula(x,y,z);
    }
    x -= dx;
    y -= dy;
    z -= dz;
  }
}

int main ( int argc , char * argv[]  ){
  cout << loop(1,1,1) << endl;
  return 0;
}

その後輩はまがりなりにもビッグデータを扱うインフラに関わっているので
この辺りを含めた統計的手法を何とか理解して貰いたいものです！