スキップしてメイン コンテンツに移動

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
Labels:

コメント

コメントを投稿

このブログの人気の投稿

ダイクストラ法

Introduction English ver 今日は、ダイクストラ法について書きます。ダイクストラ法とは最短距離を求めるアルゴリズムです。地図はグラフで表されます。もし、まだ this page を見ていない方は先にこちらをご覧ください。今回はこの記事を前提としています。このページでは、グラフの定義と、ヒープ構造について書いています。ダイクストラ法ではヒープ構造を使って、かなりの計算量を落とします。 この スライド はダイクストラ法を説明したスライドです。 Overview アルゴリズム 実装 アルゴリズム このアルゴリズムは スタート始点のノードを決める。そして、それをAと名付ける。 各ノードに$d=\infty$を割り当てる。ただし、スタート地点はd=0 Aの隣接ノードのリストをadj_listと名付ける。  For adj in adj_list:  If d of adj > d of A + weight to adj -> d = A + weight to adj. グラフnetworkからAを取り除く グラフnetworkの中で最初のdを持っているノードをAとし、4に戻る。 となっています。 このアルゴリズムを図を用いて説明します。  このグラフを使って説明します。  初めに、スタート地点を決めます。そして、各ノードに$d=\infty$を割り当てます。  Aから始まります。Aの隣接ノードであるBのdを更新します。もし、現在のBよりもAのdとA->Bへの重みを足したもののほうが小さいならdをその値に更新します。同じようにCnのdを更新します。 次にAを取り除きます。  次はBから始まります。Aと同じことをやります。 このダイクストラ法では今のような操作をグラフの全てのノードに×がつくまで続きます。 実装 このアルゴリズムでは$O(log(|V|^2))$という計算量を持っています。最小のdを持つノードを探すのに時間がかかります。 しかし、ヒープ構造を使えばO((E+V)log(V))に減らせます。ヒープ構造で現時点での...
コメントを投稿
続きを読む

線形SVMの実装

Introduction English ver 今日は線形SVMの実装をしました。 SVMはDeep learningが主流になる前、人気だったとどこかで拝見しました。 SVMの詳しい理論の説明は別の機会に必ず書きます。 # 第一弾書きました。 SVMの理論 part 1 computerはwindowsでOSはwindows10です。Python3で実装します。 このプログラムには内点法という最適化を使っています。 Dataset 次の二つのdastasetを使います。 一つは、完全に分離できるような分布のデータです・ もう一つは完全に分離できないような分布のデータです。 例えば、data1の分布はこのような形になります。 この分布ならきれいに二つのクラスを分けるような線が引けそうですね。 もう一つのデータは次のようなデータを使います。 このデータはきれいに分けるような線は引けなさそうです。 この二つのデータを用いて、線形SVMを使っていきましょう。 Implementation data1 この線が分離面になります。 きれいにいい感じのところに引けてます。 data2 このデータについては様々なCを用いて計算してみました。 Cの値が小さければ小さいほど、誤分類を認めてしまうことになります。 このデータではCの影響を確認しずらいかもしれませんが、\(C=1\)　の時、よく見ると、赤色のデータが一つ境界面を飛び出しています。 線形でないSVMを使うとCの影響がもっとわかりやすいかもしれません。 非線形なSVMについては、別の記事で書こうと思います。 CODE コードはすべてgithubに乗せています。 My SVM code is here 今回使ったファイルはgit_SVM_check.pyとgit_SVM_def.pyです。 git_SVM_check.py には次のようなコードが入ったメインファイルです。 if __name__ == '__main__': git_SVM_def にはSVMのクラスと、内点法の実装が入っています。 次は非線形のSVMについても書きたいと思います。 もし、そちらの記事も見ていただけたらハッピーです。
コメントを投稿
続きを読む

Discrete Fourier transform

Introduction 日本語 ver I will write about Discrete Fourier transform. Discrete Fourier transform is Abbreviated DFT. I am making pdf about Audio Signal Processing. I publish pdf at  github . However, I write tex in Japanese. I take a lecture about the signal processing. There is lecture at  thie page . I update this pdf.
コメントを投稿
続きを読む