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

ヘッセ行列

Introduction


今日は、ヘッセ行列を用いたテイラー展開について書こうと思います。
これは最適化を勉強するにあたって、とても大事になってくるので自分でまとめて残しておくことにしました。とくに、機械学習では最適化を必ず行うため、このブログのタイトルにもマッチした内容だと思います。
.

概要

  • ヘッセ行列の定義
  • ベクトルを用いたテイラー展開
  • 関数の最適性

ヘッセ行列の定義

仮定

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} & \ldots & \frac{\partial^2 f}{\partial x_n^2} \\ \end{array} \right) \]

ベクトルを用いたテイラー展開

テイラー展開を二次の項まで行った式を与えます。
\[f(a+h) = f(a) + \nabla f(a) h + \frac{1}{2} h^T \nabla f(a) h + R_3\]
ただし、 \(H=\nabla ^2 f\) はヘッセ行列です。
大事なのは二次の項までで止めていることです。理由は最適化できるようにです。

関数の最適性

定置性

  • \(n \times n\)行列A が 正定置
    \(\forall x \in\)n次元ベクトル空間、\(z^T A z > 0\)
  • \(n \times n\)行列A が 負定置
    \(\forall x \in\)n次元ベクトル空間、\(z^T A z < 0\)
  • \(n \times n\)行列A が 半正定置
    \(\forall x \in\)n次元ベクトル空間、\(z^T A z => 0\)
  • \(n \times n\)行列A が 半不定値
    \(\forall x \in\)n次元ベクトル空間、\(z^T A z <= 0\)
\(z^T A z\) は二次形式と呼ばれています。

最適性

もちろん上記で書いた二次の項までのテイラー展開の式は二次形式を含みます。
よって関数の最適性は次のように考えられます。
  • H(a)(ヘッセ行列) が正定置\(\implies\)f(a) は極小値.
  • H(a)(ヘッセ行列) が負定置\(\implies\) f(a) は極大値

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:

コメント

コメントを投稿

このブログの人気の投稿

カーネルk-meansの実装

Introduction   English ver 今日はカーネルk-meansの実装をしました。k-menasアルゴリズムはクラスタリングのためのアルゴリズムです。僕がカーネルk-meansを実装しようと思ったのには一つ理由があります。それは僕の友人がk-meansのプレゼンを、僕がカーネルのプレゼンをしていた時に、k-meansにカーネルを適応できないかと思ったからです。そこで、カーネルk-meansについての論文を探しました。 ここのpdf を主に参考にさせていただきました。うまくカーネルk-meansを実装できたと思います。ここでは、普通のk-meansとカーネルを用いた,kernel k-meansについての実装の結果を紹介します。 また、この記事では実装結果のみ書きますが、理論のほうも別の記事で書くつもりです。書き終えたらリンクをこの記事にも貼っておきます。 #  理論編書きました。K-means 理論編 概要 dataset   ちょっとだけ理論の説明  k-means    kernel k-means   Dataset   English ver 今回使うのは二つのデータセットです。一つ目は、普通のk-means用のデータです。二つ目はkernel k-means用のデータセットです。 一つ目のデータは、三つのグループで構成されており、次元は2で、サンプル数は300です。以下のような分布になっています。 二つ目のデータは二つのグループで構成されており、次元は2でサンプル数は300です。   this page にデータセットを作ったコードを載せています。 ちょっとだけ理論の説明 k-meansとは、k-平均法とも呼ばれています。初めに、適当なクラスに分け、各クラスの中で平均となるベクトルを求めます。そして、各データに対して、すべての平均ベクトルとの距離を求めます。そして、最小となる距離になるクラスに改めて、そのデータをクラスタリングします。そして、新たに得られたクラスの中でそれぞれ平均ベクトルを求め、これを繰り返し、平均ベクトルが動かな...
コメントを投稿
続きを読む

ヒープ構造

Introduction English ver 今日はヒープ構造について書きます。ヒープ構造はデータ構造の一種です。ちょうど大学の自主ゼミグループのセミナー合宿に参加させてもらい、そこでグラフ理論を勉強したので、メモをしておこうと思います。   slide  はこんなのを使いました。 Overview データ構造 二分木 ヒープ 実装 ヒープソート データ構造 ヒープ構造の前に、データ構造について、説明します。データ構造とは、データを保存する手法であります。データ構造は、そのデータについてどのような操作を行いたいかによって、最適なものを選ぶことになります。 ヒープ構造はプライオリティキューと呼ばれれるデータ構造を表す方法です。プライオリティキューで行いたい操作は以下の二つです。 データの追加 最小値の抽出 二分木 まず、グラフを定義します。E と V は集合とし、 $e \in E$、つまりEの要素をedge(枝)と呼びます。また、$v \in V$、つまりVの要素をnodeと呼びます。 g:E->V×V をEからV × Vへの写像とします。この時、.(E,V,g)をグラフを言います。 例えば、次のようなものがあります。 丸いのがそれぞれのnodeで、矢印がedgeになります。 各edgeに対して、始点v1と始点v2を対応させるのが写像gの役目です。 根付き木とは次のような木のことです。 これはnode1からnodeが二つずつどんどん派生していっています。 特に、次のような木を 二分木 といいます。 特徴は、ノードが上からなおかつ左から敷き詰められています。一番上のノードを根といいます。また、例えば2を基準にすると、1は2の親、4,5は2の子、3は2の兄弟、8,9,10,11,12は葉と呼ばれます。 ヒープ ヒープ構造はプライオリティキューを二分木で表現したものです。プライオリティキューでやりたいことは次のことでした。 データの追加 最小値の抽出 . では、どのようにこの二つの操作を実現するのでしょうか。 初めにデータの追加について説明します。 1. 二分木の最後に追加す...
コメントを投稿
続きを読む

Entropy

Introduction sorry, this page is Japanese only.   今日はエントロピーについて書こうと思います。これは確率論や統計学で死ぬほど大事なKLダイバージェンスといものを理解するために必要な知識です。 この記事ではエントロピーについてしか書きませんが、今度KLダイバージェンスについても書こうと思います。 KLダイバージェンスの記事はこちら Entropy 直観的な話 ある事象、「例えば明日大学の講義にX分遅刻する」という事象を考えます。 この事象に対する確率がP(X)が与えられているとしましょう。P(1)は一分遅刻する確率です。この時確率分布P(X）が持つ情報量はどれだけのものかとうことを考えたいとします。 明日の講義はテストを受けるとします。そのテストを受けないと単位を落としてしまします。しかし、テスト前日はすごく寝不足としましょう。遅刻する確率が99パーセントとわかった時、ほとんどどうあがいても遅刻するのであれば単位を落とすのはほぼ確実といえます。 よって前日に徹夜で勉強するよりも、睡眠不足を解消するために寝る方がよっぽど効率的であることがわかります。しかし、遅刻をする確率が50パーセントとわかった時、前日にテスト勉強をすればよいのか、せずに睡眠をとればよいのかわかりません。このように、確率が偏っているほど何が起こるか予測しやすく、対策を立てやすいのです。遅刻する確率が99パーセントとわかる時は遅刻する確率が50パーセントとわかった時に比べて圧倒的に多いはずです。 確率P(X)に対してこの情報量のことをP(X)の 自己エントロピー といいます。 そして、自己エントロピーの期待値のことを 平均エントロピー といいます。 立式 性質 ではこの情報量を数式で表していきましょう。まず自己エントロピーには大事な性質が二つあります。それが 互いに独立な確率変数の自己エントロピーはそれぞれの情報量の和で表される。 自己エントロピーは減少関数である。 の二つです。 自己エントロピーの加法性 互いに独立な確率変数の情報慮はそれぞれの情報量の和でなければいけません。例えば「明日の講義がY分早く終わる」という事象を考えます。この確率変数Yはあなたが何分講義に遅刻...
コメントを投稿
続きを読む