Kullback-Leibler divergence

Introduction

sorry, this page is Japanese only.

今日がダイバージェンスについて書いていきます。
ちなみにエントロピーの知識を使うのでエントロピーの記事も見てあげてください。

エントロピーの記事はこちら

Kullback-Leibler Divergence
二つの確率分布の平均エントロピーの差を表す値をKLダイバージェンスといいます。
式では次のように定義されます。

$KL(P||Q) = \int_{-\infty}^{\infty} P(X) log \frac{P(X)}{Q(X)}$
離散の場合は

$KL(P||Q) = \sum_{i} P(X_i) log \frac{P(X_i)}{Q(X)}$

なぜ二つの分布間の距離をこのように定義できるのでしょうか。

式の解釈
真の分布P(X)が存在するとします。しかし、有限のデータから真の分布P(X)を求めるのは難しいです。そこで、有限のデータから推定して得られた確率分布をQ(X）とします。では真の分布P(X）と推定した分布Q(X)はどれだけ違っているのでしょうか。

ここで登場するのがエントロピーです。エントロピーはその分布の不確実性を示す値でした。
エントロピーが高いほど不確かなことが起こるとゆうことです。

P(X)のエントロピーとは

$-\int_{-\infty}^{\infty} logP(X)$ でした。

では推定した確率分布Q(X）は確率分布P(X)に対してどれだけ不確実性を持っているのでしょうか。エントロピーとは情報量の期待値でした。確率分布Q(X）が持つ情報量は

$-logQ(X)$ です。この情報量を確率P(X)で期待値をとります。
式は以下のようになります。

$-\int_{-\infty}^{\infty} P(X) logQ(X)$
この値と真の分布のエントロピーとの差を二つの分布間の差として定義します。式では以下のようになります。

$-\int_{-\infty}^{\infty} P(X) logQ(X) - (--\int_{-\infty}^{\infty} P(X) logP(X)))$
これを式変形すると

$-\int_{-\infty}^{\infty}(logQ(X)-logP(X)) =\int_{-\infty}^{\infty}(logP(X)-logQ(X)) = \int_{-\infty}^{\infty} log \frac{P(X)}{Q(X)}$
となるわけです。

Referece

https://ja.wikipedia.org/wiki/カルバック・ライブラー情報量

このブログの人気の投稿

カーネル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 今日は、ダイクストラ法について書きます。ダイクストラ法とは最短距離を求めるアルゴリズムです。地図はグラフで表されます。もし、まだ 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))に減らせます。ヒープ構造で現時点での...

ヘッセ行列

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...

journey of Froakie (ケロマツの旅路)

このブログを検索