読者です 読者をやめる 読者になる 読者になる

中年engineerの独り言 - crumbjp

LinuxとApacheの憂鬱

最急降下法

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

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

最急降下法

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

個人的には、昔リバーシ(30次元近いパラメータセットを扱う)のAIエンジンをPentium600MHz程度で頑張ってた時期にお世話になってます。

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

課題

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

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

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

C++の回答

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

#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;
}

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