Processing math: 100%
スキップしてメイン コンテンツに移動

Hessian Matrix

Introduction

Today, I will talk about Taylor expansion with Hessian matrix.
It is important for optimization to understand Taylor expansion with Hessian matrix. Especially, Machine learning has always situation about thinking optimization. Thus I will write it to save knowledge about Hessian matrix.

Overview

  • Definition of Hessian matrix
  • Expression Taylor expansion with vector
  • Optimality of the function
Definition of Hessian matrix
Assumption
f is a function which meets a condition as follows.
  • f output Real value after getting the n-dimensional vector.
    This vector is expressed as follows.
    x = [x_1,x_2,,,,x_n]
  • \forall x_i , i \in {1,2,,,n}, f have twice partial differential

Definition Hessian matrix

Hessian matrix have \frac{\partial^2}{\partial x_i \partial x_j} f(x) ~in~ ~element~ ~of~ (i,j)
Thus Hessian matrix is expressed following.
H(f) = \left( \begin{array}{cccc} \frac{\partial^ 2}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & &\ldots \frac{\partial^2 f}{\partial x_1 \partial x_n} \\ \frac{\partial^ 2 f}{\partial x_1 \partial x_2} & \frac{\partial^ 2 f}{\partial x_2^ 2} & \ldots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^ 2 f}{\partial x_n \partial x_2} & \frac{\partial^ 2 f}{\partial x_n \partial x_2} & \ldots & \frac{\partial^2 f}{\partial x_n^2} \\ \end{array} \right)

Expression Taylor expansion with vector

I put Taylor expansion until the quadratic terms.
f(a+h) = f(a) + \nabla f(a) h + \frac{1}{2} h^T \nabla f(a) h + R_3
note that H=\nabla ^2 f is Hessian matrix.
Please check out the point that I put Taylor expansion until the quadratic terms
There is the reason. It is that I want to optimize f.

Optimality of the function

Definiteness

  • n \times n ~matrix~ A is positive definite
    \forall x \in ~n-dimentinal~ ~space~, z^T A z > 0
  • n \times n ~matrix~ A is negative definite
    \forall x \in ~n-dimentinal~ ~space~, z^T A z < 0
  • n \times n ~matrix~ A is positive semidefinite
    \forall x \in ~n-dimentinal~ ~space~, z^T A z => 0
  • n \times n ~matrix~ A is negative semidefinite
    \forall x \in ~n-dimentinal~ ~space~, z^T A z <= 0
z^T A z is called Quadratic form

Optimality

Now, of course, f deformed by Taylor expansion until the quadratic form is quadratic form.
Thus, We are able to judge Optimality of f.
  • if H(a)(Hessian matrix) is positive definite, f(a) is the minimum value.
  • if H(a)(Hessian matrix) is negative definite, f(a) is the maximum value.

Reference

https://ja.wikipedia.org/wiki/%E3%83%98%E3%83%83%E3%82%BB%E8%A1%8C%E5%88%97
http://www2.kaiyodai.ac.jp/~takenawa/optimization/resume10-1.pdf
http://www.dais.is.tohoku.ac.jp/~shioura/teaching/mp04/mp04-8.pdf
http://tau.doshisha.ac.jp/lectures/2008.calculus-II/html.dir/node43.html

コメント

このブログの人気の投稿

ヘッセ行列

Introduction English ver 今日は、ヘッセ行列を用いたテイラー展開について書こうと思います。 これは最適化を勉強するにあたって、とても大事になってくるので自分でまとめて残しておくことにしました。とくに、機械学習では最適化を必ず行うため、このブログのタイトルにもマッチした内容だと思います。 . 概要 ヘッセ行列の定義 ベクトルを用いたテイラー展開 関数の最適性 ヘッセ行列の定義 仮定 f は次のような条件を満たす関数です。. f はn次元ベクトルから実数値を出力します。 このベクトルは次のように表せます。 x = [x_1,x_2,,,,x_n] \forall x_i , i \in {1,2,,,n}, f は二回偏微分可能です。 定義 ヘッセ行列は \frac{\partial^2}{\partial x_i \partial x_j}を (i,j)要素に持ちます。 よってヘッセ行列は次のように表せます。 \[ H(f) = \left( \begin{array}{cccc} \frac{\partial^ 2}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & &\ldots \frac{\partial^2 f}{\partial x_1 \partial x_n} \\ \frac{\partial^ 2 f}{\partial x_1 \partial x_2} & \frac{\partial^ 2 f}{\partial x_2^ 2} & \ldots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^ 2 f}{\partial x_n \partial x_2} & \frac{\partial^ 2 f}{\partial x_n \partial x_2} & \ldo...

Implementation of Robbins monro

Robbins monro の実装 sorry, this page is Japanese only.   今回はRobbins monro の実装をしてみました。 Robbins monroは確率勾配降下法の学習率を入りテーション回数の逆数で割っていくものです。 使っているprogram言語はpython 3です。osはwindowsです。(macほしい...) アルゴリズム 確率勾配降下方とは目的関数の最適解を求めるアルゴリズムです。目的関数をf(X)とすると、手順は以下のようになっています。 初期学習率n_0を決めます。訓練データDを用意します。この訓練データは複数の初期値の集まりです。 訓練データから一つ初期値をランダムに取り出し、これをx_0とし、最初の予測値とします。 次の式に現在の予測値x_0を代入し、新たな予測値x_{n+1}を得ます。x_{n+1} = x_{n} - \frac{n_0}{n} grad f(X_n) 収束して入れば4へ、収束していなければ2で得られた値x{n+1}を新たにx_nとしてもう一度2を行う。 訓練データを一周していなければ2へ、一周していれば各初期値から得られた解の中から目的関数を最も小さくするものを選ぶ。   実装例 以下の目的関数を最小化させてみましょう。 f(x,y) = (x-2)^2 + (y-3)^2 コマンドラインでpythonを実行していきます。 予想通り、(2,3)という解を導き出してくれました。目的関数が簡単だったので、初期値をどの値でとってもばっちり正解にたどり着いてくれました。 CODE 以下にRobbins monroの関数だけ置いておきます。 こちら にすべてのコードを載せています。 def Robbins_monro(function,grad,number_variable_gradient): init_learning_rate = 1.5 stepsize = 1000 init_value = np.array([range(-1000,1020,20) for i in range(number_v...

カーネルK-means 理論編

Introduction English ver 今日は、カーネルK-meansの理論について書きます。カーネルK-meansは通常のK-meansの欠点を補うことができます。通常のK-meansの欠点とカーネルK-meansの強みも説明します。もし、まだ御覧になられていなければ、通常の K-means 理論編 の記事を見ていただけるとよいのではないかと思います。 カーネルK-meansの実装編 も併せてご覧ください。 概要 K-meansの弱点 カーネルトリック カーネルK-means アルゴリズム K-meansの弱点 例えば、次のようなデータを用意します。 このデータはK-meansによってうまく分類することはできません。なぜなら通常のK-meansでは、データとプロトタイプのユークリッド距離に依存しているからです。そのため、このような円状に分布しているデータはうまく分類することができません。 プロトタイプとはそれぞれのクラスにあり、そのクラスを代表するようなもののことです。K-meansでは各クラスの平均ベクトルとなります。それゆえ、以下のような分類になってしまいます。 このようなデータではK-meansはうまくいきません。 K-meansで分類できるデータセットは次のように各クラスで固まっている必要があります。 カーネルK-meansはK-meansの弱点を補います。 カーネルトリック 初めに、カーネルトリックを説明します。 線形分離できないようなデータXを例えば次のように線形分離できるように\phi(x)に送る写像\phiを考えます。 カーネルは次のように定義されます。 K(x,y) = \phi(x)^T \phi(y) \phiを具体的に計算することは難しいですが、K(x,y)を計算することなら簡単です。 この手法をカーネルトリックと呼ばれます。 カーネルK means K-meansの目的関数を復習しておきます。 J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2 ここで、 プロトタイプは\mu_i ~\forall k \in Kとしま...