2019-09-09

自己情報量の発見法的導出

はじめに

情報理論の基本的な概念として、自己情報量 $- \ln p$ があります。自己情報量は、機械学習の分類モデルのアルゴリズムで登場する平均情報量の定義の基礎となっていたり、ここそこで現れてきます。ただ、抽象度が高いため初心者泣かせの概念です。

そこで、この記事では、以下の手順で自己情報量を理解していきます。

自己情報量の式の形を知らない前提で出発し、自己情報量が満たすべき性質を考察し、それを要請として表現します。
その上で、その要請を満たす式が自己情報量の式と一致することを見ます。つまり、自己情報量の式を導出します。また、どの要請がどう導出で効いていたかを観察します。
まとめとして、端的に自己情報量がどのような概念か表現します。

情報量が満たすべき性質と、要請

ここでは、情報量という言葉の意味からそれが満たすべき性質を考察し、その性質を要請として表現します。

情報量はびっくり度

まず、情報理論で情報量に関して知っていることを忘れていただきます。一つの解釈として、情報量とは、ある事象を観測する際のびっくり度であると言えます。

これは、以下のような理由です。

起こることが全然分かっていないような、生起確率が小さい事象を観測するとき、得られる情報量（びっくり度）が大きい
逆に、起こることが確実に分かっているような、生起確率が大きい事象を観測するとき、得られる情報量（びっくり度）が小さい

より端的に言い換えると、以下のようになります。

生起確率の小さい事象を観測するとき、情報量（びっくり度）が大きい
生起確率の大きい事象を観測するとき、情報量（びっくり度）が小さい

そこで、これを満たすべき性質として捉え、以下のような要請をしてみます。
びっくり度の要請. $h$ は、確率 $p$ のみに依存し単調減少で、連続である

ただし、連続性の要請は導出のために補助的に追加しました。

情報量の加法性

情報量の「量」という言葉に着目してみます。例えば、水を朝 $1L$ 、昼 $1.5L$ 、夜 $0.5L$ 飲んだとします。この場合、合計で飲んだ水の量は、朝昼夜で飲んだ水の量の和 $(1+1.5+0.5) = 3.0L$ と一致します。この性質は、物理では、相加性という名前で知られています。相加性は、水の体積だけでなく、体積・粒子数・エネルギー・質量などの「量」的な概念が持っています。逆に、温度・圧力・密度・濃度などの「量」的でない概念にはありません。

ここで情報量の話に戻ります。情報「量」というからには、相加性のような性質を持つべきです。つまり、事象が独立な複数の事象からなる場合には、部分ごとの情報量の和が全体の情報量と一致するべきです。そこで、以下のような要請をします。
加法性の要請. 2つの独立な事象 $x, y$ について、 $\begin{equation} h(x, y)= h(x) + h(y) \end{equation}$
※情報理論の分野では、この性質を加法性と呼ぶようなので、この記事でも、相加性ではなく加法性と呼ぶことにします。

要請（自己情報量が満たすべき性質）のまとめ

これまでの議論をまとめると、以下の要請をすることにした、ということです。
びっくり度の要請. 自己情報量の関数 $h$ は、確率 $p$ のみに依存し単調減少で、連続である
加法性の要請. 2つの独立な事象 $x, y$ について、 $\begin{equation} h(x, y)= h(x) + h(y) \end{equation}$

自己情報量の式の導出

ここでは、上記要請を満たす式 $h$ が自己情報量の式と一致することを見ます。つまり、自己情報量の式を導出します。

導出

ある事象 $X=x$ が独立に $n$ 回起こる場合を考えます。 加法性の要請より以下が成り立ちます。
$\begin{equation} h( p^{n}(x) ) \end{equation}$
$\begin{equation} = h(p(x)) + h(p^{n-1}(x)) \end{equation}$
$\begin{equation} = h(p(x)) + h(p(x)) + h(p^{n-2}(x)) \end{equation}$
$\begin{equation} ... \end{equation}$
$\begin{equation} = h(p(x)) + h(p(x)) + \cdots + h(p(x)) \end{equation}$
$\begin{equation} = n \times h(p(x)) \end{equation}$
びっくり度の要請 （ $h$ は $p$ のみの関数）より、この式は特定の事象についてだけではなく一般的に成り立ちます。つまり、以下が言えます。
$\begin{equation} h(p^{n}) = n \times h(p) \end{equation}$

$m$ を自然数とします。 $p \to p^{1/m} ( 0 \lt p^{1/m} \lt 1 )$ で置き換えれば、以下が成り立ちます。
$\begin{equation} h(p^{n/m}) = n \times h(p^{1/m}) = n \times h( p^ {m/m} )/m = n/m \times h(p) \end{equation}$

これより、任意の正の有理数 $x$ で
$\begin{equation} h (p^{x}) = x \times h(p) \end{equation}$
が成り立ちます。これは、びっくり度の要請 (連続性)より、任意の正の実数でも成り立ちます。 $q=p^{x}$ と置き、両辺を $\ln q = \ln p^{x}$ で割れば、
$\begin{equation} h(q)/ \ln q = x \times h(p) / \ln p^{x} = h(p)/ \ln p \end{equation}$
となり、 $0 \lt q \lt 1$ を満たす任意の実数 $q$ について $h(q) / \ln q$ は一定となります。これより、自己情報量は以下のように導出できます。
$h(q) = - C \times \ln q$
ただし、この式は $q=1$ でも自明に成り立ち、 びっくり度の要請 （ $h$ は $p$ の単調減少関数）より、 $C$ は任意の正の定数です。

このように任意性が残ることは、 $\log$ の底の値が $2$ であろうと $e$ であろうと本質的でないことと無矛盾です。

導出のおさらい

導出のポイントは以下です。

加法性の要請とびっくり度の要請 （ $h$ は確率 $p$ のみに依存）によって、任意の事象について $h$ が $\ln p$ に比例することが言える
びっくり度の要請 （ $h$ は、確率 $p$ の単調減少関数）によって、比例定数が負であることが言える
びっくり度の要請 （ $h$ の連続性）によって、 $h$ の定義域を離散から連続に拡張できる（ただし、証明の方法によっては、この要請を使わずに拡張することも可能かもしれません）

まとめ

結局、導出から次のように言えます。

自己情報量 $h(p) = - \ln p$ は、事象の起こりにくさ「びっくり度」のみに依存する「量」である

これが本質的と言えそうです。

おわりに

自己情報量の確率的平均が、平均情報量（エントロピー） $\begin{equation} H(p) \end{equation}$ です。
$\begin{equation} H(p) = - \sum_i p_i \ln p_i \end{equation}$
注意すべき点は、平均情報量が確率分布を引数とすることです。
ここでは触れていませんが、確率変数の値を伝えるときに最短の必要な符号長の平均長さが、平均情報量と一致するという性質があり、より「情報量」と命名される納得感があります。

2019-09-03

「なんでXGBoostでは分類問題の学習に対数損失を使うんですか？」

機械学習勾配ブースティングアルゴリズム決定木 XGBoost LightGBM tamiya.yuji

先日M氏がO御大に質問していたのを聞いて、自分も気になったのでまとめてみました。

そもそも勾配ブースティングで目的関数はどのように使われる？
分類問題の場合
まとめ
参考文献
- T.Hastieほか、統計的学習の基礎 ―データマイニング・推論・予測―
- scikit-learn

そもそも勾配ブースティングで目的関数はどのように使われる？

分類問題の話に入る前に、回帰問題を例にして勾配ブースティングの原理を簡単に解説します。冒頭のM氏の質問ではXGBoostでしたが、ここ数年Kaggleなどでよく使われるLightGBMも含め、基本的なアルゴリズムは全部同じです。

勾配ブースティングの仕組み

$N$ 個のデータ $\boldsymbol{x} = {x _ 1, x _ 2, ..., x _ N}$ と正解データ $\boldsymbol{y}={y _ 1, y _ 2, ..., y _ N}$ が与えられているものとします。

今、勾配ブースティングモデルを $F _ T(x, \Theta)$ と表すことにします。簡単に言うと、勾配ブースティングは、決定木を縦に足し合わせたモデルで、各木を $f _ i(x, \theta _ i)$ として、以下のようにあらわすことができます。

$F _ T(x, \Theta) = \sum _ {i=1}^T f _ i(x, \theta _ i)$

ここで、 $T$ は縦につなげた木の数（scikit-learnのGradientBoostingでいうn _ estimators）を意味します。 $\Theta = {\theta _ 1, \theta _ 2, ..., \theta _ T}$ は各木のパラメータ（木構造、分割の際に用いる特徴量や閾値など）です。

学習プロセス

では、 $T$ 本の木をどう構築していくかですが、一言でいうと予測誤差にフィットさせた木を接ぎ足していきます。

例えば、 $t$ 本目までの木ができていたとして、その時点での暫定モデルを $F _ t(x, \Theta _ t)=\sum _ {i=1}^t f _ i(x, \theta _ i)$ と表すことにします。

この時のモデルと正解値との予測誤差 $y _ i - F _ T(x _ i, \Theta _ t)$ にフィットさせて学習したものを、 $t+1$ 番目の木とします。

このようにすることで、新しい暫定モデル $F _ {t+1}(x, \Theta _ {t+1})=\sum _ {i=1}^t f _ i(x, \theta _ i)$ は、 $t$ 本目までのモデル $F _ t(x, \Theta _ t)$ で間違ったデータを重点的に学習していく形になります。

損失関数を用いた解釈（勾配降下法）

前項では予測誤差 $y _ i - F _ T(x _ i, \Theta _ t)$ を新たな目的変数として新しい木を作っていきましたが、これを、損失関数と勾配降下法という視点でとらえ直してみます。

まず、以下のように損失関数を定義します。

$L(\boldsymbol{y}, \{ F _ t(x _ i, \Theta _ t) \} _ {i=1} ^ N) = \frac{1}{2}\sum _ {i=1} ^ N (y _ i - F _ t(x _ i, \Theta _ t)) ^ 2$

これは単純に誤差の２乗和ですが，モデルの予測値 $\{F _ t(x _ i, \Theta _ t)\} _ {i=1, 2, ..., N}$ を変数とした下に凸な関数としても捉えることができます。

さて，ここからがポイントなのですが，予測誤差 $g _ i = y _ i - F _ T(x _ i, \Theta _ t)$ は，下記のように損失関数の勾配として捉えることができるのです。したがって，「予測誤差に対して新たにフィットした木をモデルに追加する」という操作は、実は、勾配に沿った方向にモデル予測値を修正するということに相当するのです。

イメージ的にはこんな感じです：

$F _ {t+1}(x _ i, \Theta _ {t+1}) = F _ t(x _ i, \Theta _ t) + f _ t(x _ i, \Theta _ {t+1}) \approx F _ t(x _ i, \Theta _ t)-\frac{\partial L(\boldsymbol{y}, \{F _ t(x _ i, \Theta _ t)\} _ {i=1}^N)}{\partial F _ t(x _ i, \Theta _ t)}$

この構図，どこかで見たことありませんか...? そう，勾配降下法になっているのです。

f:id:gri-blog:20190903184012j:plain — gradient descent

分類問題の場合

回帰問題では二乗誤差和を損失関数として勾配方向に沿って木を成長させていきました。この方法は、二乗誤差和以外の損失関数でも適用できます。絶対誤差和や，二乗誤差をある閾値から線形に切り替えたHuber損失が使われることもあります。

同じ要領で、分類問題であっても損失関数さえ決めれば回帰の時と同じFormalismに落とし込むことができます。

問題設定

今までと同様， $N$ 個の説明変数（特徴量） $\boldsymbol{x} = {x _ 1, x _ 2, ..., x _ N}$ と目的変数 $\boldsymbol{y}={y _ 1, y _ 2, ..., y _ N}$ が与えられているものとします。ただし，今回の目的変数は、 $K$ 個のクラスのいずれかとします： $y _ i \in {1, 2, ..., K}$ 。

対数損失関数の導入

分類問題を扱うにあたり，出力値は各クラスへの分類確率 $p^{(t)} _ {k}(x _ n), \, k=1, 2, ..., K$ とします。この分類確率は、理想的には正解クラス $k = y _ n$ のみ1をとり，それ以外は0を取るのが望ましいです。

したがってこの時，損失関数 $L$ は、

全データの正解クラスへの分類確率 $p^{(t)} _ {k=y _ n}(x _ n)$ が1のとき， $L=0$
正解クラスへの分類確率 $p^{(t)} _ {k=y _ n}(x _ n)$ が0に近づくほど $L$ は大きくなる

となるように設計するのが望ましいです。

そこで，今回の出発点であった対数損失（逸脱度）を導入します。まず、各学習データについて、分類確率に対数をとったもの $-\log p^{(t)} _ {k=y _ n}(x _ n)$ を損失として定義します。

この値は、 $p _ {k=y _ n}^{(n)}$ が1の時に最小値0をとり、確率0に近づくにつれ大きくなることが分かります。

これをN個の全学習データ分足し合わせたものが、下記の対数損失です。

$L(\boldsymbol{y}, {\boldsymbol{p}^{(n)}(x _ n)}) = -\sum _ {n=1}^N\log p^{(n)} _ {y _ n}(x _ n)$

この損失関数を使うことで、分類確率 $p^{(t)} _ k(x _ n)$ を直接あてに行く場合と比べ、誤分類時の損失が強調されるので学習しやすくなります。

学習の進め方

前項で定義した対数損失をもとにモデルの学習を進めますが、これには回帰の場合と同様に損失関数の勾配を新たな目的変数として逐次新しい木を構成していきます。

ただし、正解ラベルや確率そのものを当てに行くのは難しいので、いったん回帰モデルを構築してから確率に変換するという方法をとります。

$t$ ステップ目までのモデルを $F _ t^{(k)}(x)$ とします。ここで注意点ですが、多値分類の場合は各クラスごとに異なる木を構築し、別々に学習を行います。このモデル出力値に、二値分類の場合はlogistic関数を、多値分類の場合はsoft max関数を噛ませることで、確率に変換します。

二値分類 $p^{(t)}(x _ n) = \frac{1}{1 + \exp(-F _ t(x _ n))}$

多値分類 $p _ k^{(t)}(x _ n) = \frac{\exp(F _ t^{(k)}(x _ n))}{\sum _ {k=1}^K \exp(F _ t^{(k)}(x _ n))}$

これを用いると、対数損失とその勾配は以下のように書けます。

二値分類

損失関数： $L(\boldsymbol{y}, \{ F _ t (x _ n) \} _ {n=1} ^ N)= \sum _ {n=1} ^ N \left( (1-y _ n)F _ t (x _ n) + \log \{1 + \exp(-F _ t(x _ n))\} \right)$

勾配： $- \frac{\partial L(\boldsymbol{y}, {F _ t(x _ n)} _ {n=1}^N)}{\partial F _ t(x _ n)} = y _ n - p^{(t)}(x _ n)$

多値分類

損失関数：

$L(\boldsymbol{y}, \{ \boldsymbol{F} _ t(x _ n) \} _ {n=1} ^ N)=\sum _ {n=1} ^ N \left(F ^ {(y _ n)} _ t(x _ n) + \log \left\{ \sum _ {k=1} ^ K \exp(F ^ {(k)} _ t(x _ n)) \right\} \right)$

勾配： $- \frac{\partial L(\boldsymbol{y}, {\boldsymbol{F} _ t(x _ n)} _ {n=1}^N)}{\partial F^{(k)} _ t(x _ n)} = \delta _ {k, y _ n} - p^{(t)} _ k (x _ n)$

$\delta _ {j, k}$ はクロネッカーのデルタといって、 $k=j$ の時のみ1, それ以外では0をとります。

この勾配を目的変数とし新しい回帰決定木 $f _ {t+1}^{(k)}(x)$ を構築してそれまでのモデル $F _ t^{(k)}(x)$ に足し合わせることで、新たなモデル $F _ {t+1}^{(k)}(x)$ を作ります。ここからまた新たな対数損失の勾配を求め、モデルを更新し、...というステップを繰り返していきます。

まとめ

所々細かいところは端折りましたが、以上が勾配ブースティングのアルゴリズム概要になります。

冒頭の「なぜ対数損失を使うのか？」という問いに戻ると、以下のような回答が挙げられるかと思います。

勾配ブースティングでは内部的には回帰決定木を用いて予測を行う
分類確率に対数をとった $-\log p _ k(x)$ に着目することで値域が $[0, \infty)$ となり、不正解時の誤差が強調される。

対数をとらずに分類確率をそのまま使って $\frac{1}{2}\sum _ {n=1} ^ N(1-p ^ {(n)} _ {y _ n}) ^ 2$ といった量を損失関数として学習を行うこともできなくはないかもしれません。しかし、 $p _ k(x)$ 自身は $[0,1$ ]区間の値しか取れないので、対数誤差と比べると学習しにくくなるように思います。

ちなみに、対数損失以外に指数損失が使われることもあります。特に二値分類で指数損失を用いる場合は、AdaBoostという別の手法と一致することが知られています。

参考文献

T.Hastieほか、統計的学習の基礎 ―データマイニング・推論・予測―

統計的学習の基礎 ―データマイニング・推論・予測―

作者:Trevor Hastie,Robert Tibshirani,Jerome Friedman
発売日: 2014/06/25
メディア: 単行本

通称カステラ本。標準的な機械学習アルゴリズムが網羅的に書かれた辞書のような本です。分厚いですが、記述は丁寧なので気になるところをつまみ読みするにはもってこいです。

特に勾配ブースティングを含めたツリー系アルゴリズムが数理的にきちんと書かれた書籍はこれ以外知りません。

scikit-learn

Python 機械学習ライブラリの定番です。ドキュメントやGitHubにあがっているコードを読みながら動作を辿ってみると理解が深まります。

2019-09-02

GRIブログの始まり

はてなブログ Jupyter Tableau スライド

はてなブログの使い方

株式会社GRIは「データ分析で社会をより良く」をテーマに掲げるデータサイエンス系の会社です。

分析官たちは日ごろから案件を通して研究開発を進めていますが、その過程で生まれた分析ノウハウなどは現状、様々な場所に散在してしまっています。 GRIではConfluence、Github、Colaboratory、Slackなどのサービスを利用しており、他のメンバーと共有したい情報はその文脈に合わせてサービスを使い分けています。一見、効率的で賢い方法にも思えるのですが、情報が散らばった状態では本当に価値のあるストーリーにまで昇華しないことも多い気がしています。直近の作業を進める上では効率的なコミュニケーションがとれるのですが、知識の積み上げが部分的になり、長期的にみたときの成長曲線にブレーキをかけるのではという危惧があります。

そこで、分析官が気軽に書けるブログサイトを開設することにしました。 WixやWordpressなども試しましたが、

前者はマークダウン記法が使えなくて数式の記述が面倒
後者はTableauやJupyter NotebookのEmbedが面倒

だったりと、分析官が気軽に書ける環境ではなかったので、はてなブログを今は試しています。

はてなブログの書き方

基本は「マークダウン記法」

こちらの記事を参考に、デフォルトの「見たままモード」から「マークダウンモード」に変更しました。 Jupyter NotebookやGithubで書き慣れているというのが最も大きい要因でした。

ソースコードの書き方

はてなブログではシンタックス・ハイライトのソースコードを記述することが可能です。

import pandas as pd
df = pd.DataFrame(range(10), columns=['colA'])

数式の書き方

はてなブログでは以下のように記述することで、Texの数式を表現可能です。

[tex: （TeX記法）]

たとえば、

[tex: x + y = z]

と書くと、

$x + y = z$

のように表示できます。ただし、はてなブログ特有のクセがあるようなので、以下の記事などを参照してください。

7shi.hateblo.jp

Tableauの埋め込み

分析官はデータの可視化にTableauを使うことも良くあります。はてなブログではTableauのEmbedコードを直接貼り付けるだけで、以下のように表示することができます。

Power Pointの埋め込み

分析官のレポートはPowerPointになることが多いので、それを埋め込めると記事を書くハードルが下がる場面もあると思います。以下はこちらの記事を参考にして、Google Slideを埋め込んだ例になります。

Jupyter Notebookの埋め込み

GRIでの分析のプライマリ言語はPythonになっているので、Pythonの話題はとても多いです。 PythonにはJupyter Notebookという対話形式で分析の試行錯誤ができるパッケージがあり、これが分析の過程や結果を共有するのに非常に便利です。はてなブログでは、この記事で紹介されているような方法でNotebookを表示することが可能です。

まとめ

はてなブログでは分析官の良く使うツールの埋め込みや表示がとても簡単にできることが分かりました。知見を蓄積・共有するため、ブログ記事をどんどん書いていこうと思います。