2013-12-06

MLaPP アドベントカレンダー6日目：Ch.6 Frequentist statistics

ML 本

というわけで，昨日はベイズ統計でしたが，本日は頻度論的統計の章です．頻度論から統計学を知った身としては，頻度論の問題点を指摘されているのは自分の黒歴史を見つめているようで悲しい気分になります…．とはいえ，最近は完全に発想がベイジアンになっているのですが．

頻度論統計のベイズ統計の一番の視点の違いは最初にも書かれているように，頻度論はパラメータが固定（真のパラメータがある），データはそこからサンプリングされたに過ぎない（ランダムでありうる）と考えているのに対し，ベイズ統計はデータは固定（だって目の前にデータがあるじゃん！），パラメータはランダム（事前分布などに応じて変わりうる）と考えています．これらの違いを意識すると，どっちの立場の話もすっきりするのではないでしょうか．

Sampling distribution of an estimator

- 頻度統計ではパラメータ推定値 $\hat \theta$ はestimator $\delta$ をデータDに適用することによって計算される
- パラメータが固定で，データがランダムと捉える．これはベイズ統計とまったく逆
- ある真の分布からデータがサンプルされたと考え，データから真の分布のパラメータを推定する
Bootstrap
- ブートストラップはサンプリング分布を近似するモンテカルロ手法
- 推定量が真のパラメータの複雑な関数のときに有用
  - ブートストラップの基本的な考え方
    - 真の分布のパラメータを知っているならば，任意のサイズのfake dataをつくることができる
    - ブートストラップでは各サンプルデータから推定量を計算し，サンプリング分布の推定として経験分布を用いる
    - $\theta$ は未知なので，パラメトリックブートストラップの考えは $\hat \theta(D)$ を代わりに用いてサンプルを生成する
    - ノンパラメトリックブートストラップはオリジナルデータDからxをサンプリングし，分布を計算する

Frequentist decision theory

- 頻度統計では損失関数や尤度はあるが，事前分布がないので，事後分布や事後期待損失がない
- そのため，ベイズ統計のように自動的に最適な推定量を導出する方法はない
- 代わりに頻度的アプローチでは推定量や決定プロセスを自由に選ぶことができる
- 推定量を選ぶとリスクを式(6.9)のように定義できる
Bayes risk
Minimax risk
Admissible estimator
- 頻度論的決定理論の基本的な問題はリスクを評価するために真の分布を知ること
- しかし，ある場合においては推定値は最尤推定量であるにもかかわらず他より悪くなることがある
- 特にすべての $\theta$ において， $R(\theta, \delta_1) \leq R(\theta, \delta_2)$ ならば， $\delta_1$ は $\delta_2$ を支配するという
- 他の推定量によって完全に支配されないならば，その推定量はadmissibleであるという
Stein's paradox
- $N(\theta_i, 0)$ に従うN個のi.i.dな変数 $X_i$ に対して， $\theta_i$ を推定したい
- MLEを使うと $\hat \theta_i = x_i$ である．これは $N \geq 4$ のとき，二次損失のもとでは許容できないパラメータである
- $N \geq 4$ のとき，最尤推定量(sample mean)よりもより小さいリスク(MSE)となるshrinkage estimatorがある
- これはStein's paradoxとして知られている
Admissibility is not enough

Desirable properties of estimators

Consistent estimators
- データが大きくなるにつれて，推定量が収束する
Unbiased estimators
- 真のパラメータとの差の期待値が0であるとき，バイアスがない(unbiased)という
Minimum variance estimators
- unbiasedだけでOKではなくて，varianceも重要
- Craner-Rao lower bound
The bias-variance tradeoff
- MSE = variance + bias^2
- この関係性をbias-variance tradeoff (Geman et al. 1992)と呼ぶ

Empirical risk minimization

- Frequentist decision thoeryは真のデータ分布を知っていることに依存しているので，実際にはリスク関数を計算できないという問題がある
- (逆にベイズの事後期待損失はそうではない)
- この問題を避けるために，真のパラメータと推定量によるロス関数 $L(\theta, \delta (D))$ の代わりに
- 真のレスポンスyとxが与えられたときの予測 $\delta(x)$ によるロス関数 $L(y, \delta(x))$ を考える
- これは式(6.47)
- ただし，真のデータ分布はわからないままなので，経験分布を用いる，これは式(6.49)の経験リスク
Regularized risk minimization
- 経験リスクは自然分布が自然な分布であるならば，ベイズリスクと一致する(Minka, 2001)
Structural risk minimization
Estimationg the risk using cross validation
The one standard error rule
CV for model selection in non-probabilistic unsupervised learning
Upper bounding the risk using statistical learning theory
Surrogate loss function

Pathologies of frequentist statistics

- 頻度統計はpathologyとして知られる，あまり望ましくない振る舞いが知られている
- 以下でいくつかの例を示す
Counter-intuitive behavior of confidence intervals
p-values considered harmful
The likelihood principle
Why isn't everyone a Bayesian?
- 頻度論的統計学者のEfronは"Why isn't everyone a Bayesian?"というタイトルで論文(Efron, 1986)を書いているので以下に引用

このタイトルは少なくとも2つの点で合理的な質問だ．1点目はすべての人は以前はベイジアンだった．ラプラスは推論問題において，心底ベイズの定理を支持していたし，19世紀の科学者は大抵そうだったろう．これはガウスも含む．彼の仕事は頻度論的統計の分野で語られがちであるけれども．
2点目の，より重要な点として，ベイズ論の説得力だ．Savegeやde Finettiに続く現代的な統計学者はベイズ推論のパワフルな理論的論拠を有している．その結果として，頻度論的な見方との不一致がカタログのように多く生まれた．
にもかかわらず，すべての人はベイジアンではない．現代(1986)は統計学が科学の分野で広く使われるようになった初めての世紀であり，実際，20世紀の統計学は主にノンベイジアンであった．しかし，Lindley (1975)は21世紀には変化すると予測している．

- Lindleyが正しいかどうかは時間が経てばわかるだろう．

更新する時間が当初に比べて有意に遅れているように思えますが，気のせいではありません．

2013-12-05

MLaPP アドベントカレンダー5日目：Ch.5 Bayesian statistics

ML 本

5日目になってベイズ統計の章に入ってきました．ベイズの定理を用いたベイズモデリングや，そこまで詳しく触れられませんが古典的ベイズ，階層ベイズ，経験ベイズの違いがわかるといいと思います．また，次の章では頻度論的な話になっているので対比してみると理解が深まるように思います．

Summarizing posterior distributions

- 事後分布 $p(\theta|D)$ は未知量 $\theta$ に関して知っていること全てを要約
MAP estimation
- 未知量に対する点推定は事後分布の平均や中央値などで計算
- このアプローチは計算しやすいが，MAP推定には様々な欠点があることを把握しておくのは重要
- これは後半に続くより徹底的なベイズアプローチのモチベーションになっている
  - No measure of uncertainty
    - MAP推定を含む任意の点推定は不確実性に対する指標がない
  - Plugging in the MAP estimate can result in overfitting
    - MLにおいてはパラメータ解釈よりも予測精度を重視
    - 不確実性をモデル化していないと予測分布はoverfitしている
  - The mode is an untypical point
  - MAP estimation is not invariant to reparameterization
    - MAP推定に関するより本質的な問題
    - 確率分布を分析者がどのようにパラメタライズしたかに依存する
Credible intervals
- 事後分布の幅を与えるのがCredible interval(信用区間)
- $C_{\alpha} (D) = (l,u) : p(l \leq \theta \leq u | D) = 1- \alpha$
- 事後分布がよく知られた関数形ならばその関数を用いて信用区間を計算
- 事後分布がよくわからないならば，モンテカルロでサンプリング
- Bayesian credible intervalとfrequentist confidence interval(信頼区間)は混同しやすい
- 前者は人々が計算したいもの，後者は実際に計算するものという違いがある
Inference for a difference in proportion
- 評判がポジティブ90人，ネガティブ10人の店とポジティブ2人，ネガティブ0人の店のどちらから買うべきか問題
- $\theta_1, \ \theta_2$ は2つの店の未知の信頼性
- それぞれ事前分布 $\theta_i \sim Beta(1,1)$ に従うとする
- 事後分布は $p(\theta_1|D_1) = Beta(91,11), \ p(\theta_2|D_2) = Beta(3,1)$
- $p(\theta_1 > \theta_2|D)$ を計算したいので $\delta = \theta_1 - \theta_2$ として
- $p(\delta>0|D) = \int_0^1 \int_0^1 I(\theta_1 > \theta_2) Beta(\theta_1|y_1 + 1, N_1 - y_1 + 1)$ $Beta(\theta_2|y_2+1,N_2 - y_2 + 1)d \theta_1 d \theta_2$
- $p(\delta>0|D) = 0.710$ なので店1から買った方がよさそう

Bayesian model selection

- モデルを高次元にするとoverfitするし，低次元だとunderfit
- 正則化パラメータも少ないとoverfitするし，多いとunderfit
- 一般に複雑さの異なるモデルの中からどれを選ぶべき？これがmodel selection
- 1つのアプローチはクロスバリデーションで全ての候補モデルの一般化エラーを推定
- もっと効率的なアプローチとしてモデル上で事後分布を計算
- $p(D|m) = \int p(D|\theta) p(\theta|m) d\theta$
- これはmarginal likelihood, integrated likelihood, evidence for model mなどと呼ばれる

Bayesian Occam's razor
- 単純にp(D|m)を使うとパラメータが多いモデルが有利っぽいが，最大値ではなく周辺化なので必ずしも良くなるわけではない
- これをBayesian Occam's razorと呼ぶ
BIC approximation to log marginal likelihood
- 真面目に上式を計算するのは大変なので，一つの単純な近似としてBayesian information criterion (BIC)がある
- $BIC \equiv \log p(D|\hat \theta) - \frac{dof(\hat \theta)}{2} \log N$
- $dof(\hat \theta)$ はモデルの自由度． $\hat \theta$ はモデルのMLE

Bayes factors
- モデルの事前分布を一様分布と仮定すると，モデル選択は最も高い周辺尤度をもつモデルを選択することと等価
- 次の夜にnull hypothesis M_0とalternative hypothesis M_1があるとき，Bayes factorは周辺尤度の比で定義できる
- $BF_{1,0} = \frac{p(D|M_1)}{p(D|M_0)}$
- これは尤度比のようなもの

Priors

- ベイズ統計でもっとも論争を呼ぶ点は事前分布の存在
- すべての推論はある仮定の下でなされているはずなのに，中には事前分布の影響を最小にしたいと考えている人たちもいる
- これについて簡単にまとめる
Uniformative priors
- pseudo countの大きさを減らせば，事前分布の影響は小さくできるので，最も情報のない事前分布として
- Beta(0.0)がある．これはHaldane priorとも呼ばれる
Jeffreys priors
- Jeffreysは情報のない事前分布をつくるために一般的な方法を考えた．それはJeffreys priorとして知られる
- もし $p(\phi)$ が無情報なら，その事前分布のre-parameterizationもまた無情報である．よって変数変換して
- $p_{\theta} (\theta) = p_{\phi} (\phi) |\frac{d \phi}{d \theta}|$
- となる． $I(\phi)$ をフィッシャー情報行列とすると， $p(\phi) \propto (I(\phi))^{1/2}$ であり
- これはMLEの安定性の指標となる．
  - Bernoulli and multinoulliのJeffreys priorとか
  - location and scale parameterのJeffreys priorとか
Robust priors
Mixtures of conjugate priors

Hierarchical Bayes

- 事前分布 $p(\theta|\eta)$ の $\eta$ どうやって特定するのか問題
- そのために階層ベイズとかmulti-level modelとかって呼ばれる方法があり，この本の後半でいっぱい出てくるよ

Empirical Bayes

- 階層ベイズでは潜在変数の事前分布を計算する必要があった
- けど，計算で楽するために，ハイパーパラメータの事後分布を点推定で近似する
- 多くの場合， $\eta$ の次元は $\theta$ の次元より小さいので， $\eta$ の事前分布に一様を仮定して次の $\eta$ を求める
- $\hat \eta = \arg \max p(D|\eta) = \arg \max \left[ \int p(D|\theta) p(\theta|\eta) d \theta \right]$
- これは経験ベイズとかtype-II maximum likelihoodなどと呼ばれる．ML分野ではevidence procedureとも．
- 経験ベイズは事前分布はデータとは無関係に選ばれるという主義をぶちこわす．
- しかし，階層ベイズモデルにおける推論の計算的に楽な近似として見ることができる
- 経験ベイズは良い頻度論的性質ももっているので(see Carlin and Louis 1996; Efron 2010)non-Bayesianにも広く使われている

Bayesian decition theory

Bayes estimators for common loss functions
The false positive vs false negative tradeoff

それはともかく，良い感じの自転車操業です．

2013-12-04

MLaPP アドベントカレンダー4日目：Ch.4 Gaussian models

ML 本

4章長くてつらい．4.3が1番重要と思う．PRML 2章でも正規分布の部分は結構重たかったんだけど，それだけ重要だということだと思う．途中で積ん読になるならこの章だと思うので，序盤の山場と思われ．初日に書いた通り，自分も1, 2, 3章読んで止まってたので4章で本棚にしまったのだろう…．

Introduction

- みんな大好き多変量正規分布(MVN)
- 悲しいことに著者曰くこの章の数学レベルは他の章に比べると高い！とのこと（特に線型代数と行列計算の観点で）
- しかし高次元データを扱う場合は絶対必要だよね，とのこと
Basics
- D次元のMVNの確率密度関数は
- $N(x|\mu,\Sigma) \equiv \frac{1}{(2\pi)^{D/2}|\Sigma|^{1/2}} \exp \left[ - \frac{1}{2} (x-\mu)^T \Sigma^{-1} (x-\mu)\right]$
- expの中はデータベクトル $x$ と平均ベクトル $\mu$ のマハラノビス距離である
- 共分散行列 $\Sigma$ の固有値分解することでより理解しやすい
- $\Sigma = U \Lambda U^T$
- ここでUは $U^T U = I$ を満たす固有値ベクトルの直交行列であり， $\Lambda$ は固有値の対角行列
- このとき
- $\Sigma^{-1} = U^{-T} \Lambda^{-1} U^{-1} = U \Lambda^{-1} U^T = \sum\limits_{i=1}^D \frac{1}{\lambda_i} u_i u_i^T$
- ここで， $u_i$ はi番目の固有値ベクトルを含むUのi番目の列
- そのため，マハラノビス距離は次のように書き換えることができる
- $(x - \mu)^T \Sigma^{-1} (x - \mu) = (x - \mu)^T (\sum\limits_{i=1}^D \frac{1}{\lambda_i} u_i u_i^T) (x - \mu)$
- $= \sum\limits_{i=1}^D \frac{1}{\lambda_i} (x-\mu)^T u_i u_i^T (x-\mu) = \sum\limits_{i=1}^D \frac{y_i^2}{\lambda}$
- ここで， $y_i = u_i^T (x - \mu)$
- ここからわかる解釈として，ある正規分布の等確率密度のコンターは楕円であり，固有ベクトルは楕円の中心を，固有値は長径と短径を表す
Maximum entropy derivation of the Gaussian
- 多変量正規分布はある平均と共分散の下で，エントロピーを最大化する分布である

Gaussian discriminant analysis

- MVNによって生成モデル的な条件付き確率密度を定義することができ，これは(Gaussian) discriminant analysis (GDA)と呼ばれる
- これは各クラスの共分散行列が対角行列であれば，ナイーブベイズと等価
- 各クラスの条件付き確率密度の下でxの確率が計算されたとき，xから各クラスの $\mu$ までのマハラノビス距離を計算でき
- これは最近隣セントロイドへの分類器である
Quadratic discriminant analysis (QDA)
- 生成モデル分類器の式(2.13)にガウス分布を適用すると式(4.33)
- これはxの二次式になっているのでquadratic discriminant analysis (QDA)と呼ばれる
Linear discriminant analysis (LDA)
- 共分散行列がクラス間で共有されている，つまり $\Sigma_c = \Sigma$ のような特殊ケースでは式(4.33)は式(4.35)
- するといろいろキャンセルアウトされて， $p(y=c|x, \theta)$ は式(4.38)のようにsoft-max関数で書ける
- これは統計物理の分野ではBoltzmann分布と呼ばれる
- 式(4.38)は対数をとると，xの線形関数となるので2つのクラス間の決定境界は直線になる．そのためLDAと呼ばれる
- 事後確率をより直接的に導出するのがmulti-class rogistic regression or multinomial rogistic regressionである
- これらの違いはSection 8.2, Section 8.6で詳細に述べる
Regularized LDA
- 共分散行列 $\Sigma_c = \Sigma$ と仮定した上に， $\Sigma$ の事前分布に逆ウィッシャート分布を用いてMAP推定をする
- これは正規化項が入るのでregularized discriminant analysis (RDA)と呼ばれる(Hastie et al., 2009)
Nearest shrunken centroid classifier
- 高次元の問題では精度や解釈しやすさの観点から，特徴量の部分集合にのみ依存する方法が望ましい
- 一つの方法はSection 3.5.4で述べた相互情報量を用いたスクリーニング
- 別の方法として，このnearest shrunken centroid classifier
- 基本的アイデア
  - sparsity-promoting (Laplace) priorを用いたdiagonal LDAのMAP推定
  - クラス固有の特徴量平均 $\mu_{cj}$ をクラス独立特徴量平均 $m_j$ とクラス固有オフセット $\delta_{cj}$ を用いて
  - $\mu_{cj} = m_j + \delta_{cj}$
  - で表す．ここで， $\delta_{cj}$ の項が厳密に0になるような事前分布をおき，MAP推定を行う
  - たとえば，特徴量jにおいて，すべてのcにおいて $\delta_{cj} = 0$ になれば，特徴量jはクラス分類に役立たないことがわかる
  - 詳細は(Hastie et al. 2009)

Inference in jointly Gaussian distribution

Statement of the result
- 式(4.69)がとても重要
Information form
- 一般的には正規分布は $\mu$ と $\Sigma$ によって表す．これはmoment parametersと呼ぶ
- しかし，場合によってはcanonical parameter, natural parameterを用いることも役立つ
- $\Lambda = \Sigma^{-1},\ \xi = \Sigma^{-1} \mu$
- canonical parameterを用いるとMVNはinformation formで書ける（詳しくはSection 9.2 指数型分布族)
- $N_c (x|\xi, \Lambda) = (2 \pi)^{-D/2} |\Lambda|^{1/2} \exp (-\frac{1}{2} (x^T \Lambda x + \xi^T \Lambda^{-1} \xi - 2 x^T \xi))$
- information formでも周辺確率や条件付き確率が書ける
- 特に，周辺確率はmoment formが，条件付き確率はinformation formが簡単
Proof of the result
- シューア補行列を使ったここらへんの式展開は超重要(PRMLにもありましたね…)

Linear Gaussian systems

- xが隠れ変数，yがnoisy observationでAx + bとなるような線形システム

The Wishart distribution

- ウィシャート分布はガンマ分布の正定値行列への一般化
- Press (Press, 2005)は「多変量統計において重要性と有用性の観点で，ウィッシャート分布は正規分布の次のランクだ」と言っている
- ウィシャート分布は式(4.159)
- 正規分布のベイズ推定するときに，共分散行列の事前分布でよく使うのが逆ウィシャート分布

最初にも書いた通り，正規分布は様々な統計モデルで用いられる上に，想像の範囲内の動きをする確率分布なので，いろんなモデルの具体例を考えるときにも有用ですよね．

2013-12-03

MLaPP アドベントカレンダー3日目：Ch.3 Generative models for discrete data

ML 本

というわけでMLaPPアドベントカレンダー3日目．三日坊主の域まで来たので，一つ目の関門は越えた感じです．ここまでで一応100ページ弱．3章の内容はまだまだ導入という感じの章ですね．生成モデルの考え方，ベイズの考え方などが具体例に沿って説明されるのでわかりやすい章だと思います．また，1章から3章の内容はとても読みやすい導入になっていると思うので，これから機械学習を勉強しようという人にはとてもオススメできるパートです．

Bayesian concept learning

number game (Tenenbaum, 1999)が面白い
- あるコンセプトに従って1から100までの間の数が伝えられ，どういうコンセプトかを当てる
- 最初に"16"と言われると，"10台の数字"とか"4の倍数"とか"偶数"などのコンセプトに沿った数字の事後確率が上がる
- 次に"8"と言われると，4の倍数"や"偶数"，"8の倍数"のコンセプトの事後確率がもっと上がる（逆に"10台の数字"は下がる）
- みたいな感じでベイズ的な考え方がうまく説明されている

Beta-binomial model

- コイントスをしたときに，コインの表が出る確率を推論する問題
- また，この問題はBayesのoriginal paperでも分析されている
Likelihood
- $p(D|\theta) = \theta^{N_1} (1-\theta)^{N_0}$
- $\theta \in [0,1]$ はパラメータ
- $N_1 = \sum_{i=1}^{N} I(x_i = 1)$ は表が出た回数, $N_0 = \sum_{i=1}^N I(x_i = 0)$ は裏が出た回数
- これらの2つの数はデータの十分統計量(sufficient statistics)と呼ばれる
Prior
- 簡単のため，事前分布は尤度と同じ形を考える．たとえば以下
- $p(\theta) \propto \theta^{\gamma_1} (1- \theta)^{\gamma_2}$
- $\gamma_1,\ \gamma_2$ は事前パラメータ
- 事前分布と事後分布が同じ形になるような事前分布を共役事前分布(conjugate prior)と呼ぶ
- 共役事前分布は計算が容易い，解釈がしやすいなどの理由で広く使われている
Posterior
- 事後分布は尤度と事前分布の積に比例するので次の形でかける
- $p(\theta|D) \propto p(D|\theta) \cdot p(\theta)$
- 尤度がベルヌーイ分布，事前分布に二項分布を仮定すると，事前分布のハイパーパラメータはpseudo countsとして解釈できる
- 事前分布の強さはeffective sample sizeとして知られ，pseudo countsの合計
- （これはデータサイズ $N=N_1 + N_0$ とのアナロジー）
Overfitting and the black swan paradox
- このblack swan paradoxは面白い
- 最尤推定では3回コイントスをして3回表が出ると，このコインの裏が出る確率は0となる
- でも，これって感覚的におかしいと思う
- このような問題はzero count problemと呼ばれたり，sparse data problemと呼ばれたりする
- カール・ポパーはこのような問題を哲学上はblack swan paradoxと呼んでいる
- この問題のシンプルな解決策の一つがベイズ統計における事前分布の仮定
- add-one smoothingとして知られている0をすべて1にする方法はLaplace's ruleによる事後平均である

The Dirichlet-multinomial model

- 二項分布モデルの多項分布への拡張版
- その場合は事前分布はディリクレ分布が共役事前分布
  - よく知られた例としてBoWを用いたlanguage model

Naive Bayes classifiers

- 離散値を取る特徴量ベクトルにおける生成モデルアプローチによる分類器
- 各クラスの条件付き分布 $p(x|y=c)$ が必要
- 1番簡単な方法は各特徴量が各クラスラベルと条件付き独立であると仮定すること
- これにより，各クラスの条件付き確率密度は各次元の密度の積で表現される
- $p(x|y=c, \theta) = \prod\limits_{j=1}^{D} p(x_j | y=c, \theta_{jc})$
- このモデルはnaive Bayes classifier (NBC)と呼ばれる
ナイーブと呼ばれる理由
- 本当はクラスラベルの条件付きであってもfeatureは独立ではない
- しかし，この仮定が正しくなくても結構この分類器はうまくいく(Domingo and Pazzani, 1997)
- 特徴量が実数の時は正規分布の積で
- 特徴量が2値変数のときはベルヌーイ分布の積でかける．これはmultivariate Bernoulli naive Bayesとよばれる
Model fitting
- 最尤推定とか
- ベイジアンナイーブベイズとか
the log-sum-exp trick
- ナイーブベイズなどの計算をしてるとき，exp()がいっぱいあるので，計算がアンダーフローする
- それはxが高次元の時， $p(x|y=c)$ がたいてい値が小さくなってしまうため
- そこで良く使うのがlog-sum exp trickである
Feature selection using mutual information
- ナイーブベイズはオーバーフィッティングしがちなので，特徴量選択を相互情報量をもちいて行う
- 特徴量選択の1番簡単な方法は各特徴量を別々に比較し，上位K個を用いる方法である
- これはranking, filtering, screeningと呼ばれる
Classifying documents using bag of words
- ナイーブベイズは文書分類に用いられる
- たとえばスパムフィルタ
- ベルヌーイ積モデル (Bernoulli product model or binary independence model)
- McCallum and Nigam (1998)

しかし，これがあと25章，しかも内容がどんどん難しくなっていく上に，自分の日中業務も忙しくなってきているので，不安感しかないですね．．．夜はMLaPP読んで心を静めるしかない！

2013-12-02

MLaPP アドベントカレンダー2日目：Ch.2 Probability

ML 本

他のアドベントカレンダーのエントリタイトルみていたらみんな，ほにゃららAdvent Calendarってなってて，アドベントカレンダーってカタカナで書いてしまって恥ずかしい…．ということで，確率論の概要の章．ここらへんはまだ大丈夫そうです．

Some common discrete distributions

二項分布・ベルヌーイ分布
多項分布
ポアソン分布
経験分布
- 得られたデータの分布

Some common continuous distributions

ガウス分布
Degenerate pdf
- $\sigma \rightarrow 0$ の極限を考えると，正規分布は $\mu$ において無限に高く無限に薄い"spike"となる
- $\delta (x - \mu)$
- ここで $\delta$ はディラックのデルタ関数と呼ばれる
- デルタ関数の有用な性質はshifting propertyであり，sumやintegralの中から1つの項を抜き出せる(式2.50)
ラプラス分布
- heavy tailをもつ分布．double sided exponential distributionとも呼ばれる
- 外れ値に対してロバストであり，正規分布よりも $\mu$ における確率が高い
- これはモデルにおけるsparsityを表現するのに有用(see Section 13.3)
ガンマ分布
- 正の実数における柔軟な分布
- ガンマ分布の特殊形に
  - 指数分布
  - Erlang分布
  - カイ二乗分布
- などがある
ベータ分布
- 区間[0,1]間で定義される
パレート分布
- いわゆるlong tailを表現するための分布
- 最も使われる単語("the")は二番目によく使われる単語("of")の約2倍使われる
- 単語の頻度とランクをプロットするとZipf's lawと呼ばれる，冪乗則に従う

Joint probability distributions

多次元になったバージョン
共分散と相関
- 共分散(covariance): XとYが(線形に)関連している度合い
- 共分散は0から無限大の値をとるので，正規化したのが(Pearsonの)相関係数(correlation)
多変量ガウス分布
- multivariate Gaussian or multivariate normal (MVN)は最も良く使われる多変量分布
- Ch 4で詳しくやる
- 分散共分散行列を $\Sigma$ としたとき，その逆行列は精度行列(precision matrix, concentration matrix)と呼ばれる
多変量スチューデントt分布
- スチューデントのt分布の多変量版
ディリクレ分布
- ベータ分布の多変量版
- この分布はprobability simplex上で定義されるのでいろいろ使いやすい

Transformations of random variables

- $x \sim p()$ という確率変数があったとき， $y=f(x)$ ならば， $y$ の分布はなんなんだろか問題
Linear transformations
- $f()$ が線形関数だったとき，期待値は線形．これはlinearity of expectationと呼ばれる．つまり
- $y = Ax + b$ のとき， $E[y] = E[Ax+b] = A\mu + b$
- 共分散は $cov(y) = cov(Ax + b) = A \Sigma A^T$
General transformations
- いわゆる変数変換
Central limit theorem
- いわゆる中心極限定理

Monte Carlo approximation

- いろんな確率計算するときにモンテカルロ積分使いますよね，という話．

Information theory

- 情報理論はデータ圧縮(data compression)や情報源符号化(source coding)，誤り訂正(error correction)，通信路符号化(channel coding)に関連がある
- この本では詳しく書けないのでCover and Thomas (2006)を読めとのこと
Entropy
- $H(X) = - \sum_{k=1}^K p(X = k) \log_2 p(X = k)$
- K個の状態があるとき，各状態の生成確率が1/Kのときエントロピーは最大になる
- 任意のデルタ関数は不確実性がないのでエントロピーが最小(=0)になる
KL divergence
- 2つの確率分布p, q間の違いを測定する計量がカルバック・ライブラーダイバージェンス（相対エントロピー）である
- 今後も良く出てくる重要な概念
Mutual information
- 相互情報量は一方を知ることで他方をどれだけ知ることができるかを表す．

2章は確率論や確率分布の復習なので，そこらへんがきちんとわかっていれば特に詰まる部分もなく，読み進められると思います．ということでスキップ，スキップ．大切なこともいっぱい書かれているので読みながら戻ってくることもあると思います．

2013-12-01

MLaPP アドベントカレンダー1日目：Ch.1 Introduction

ML 本

12月ですね．そういえば昨年ベイズ統計分析ハンドブックに関するエントリーを書いたところ，ホッテントリに入って大量のアクセスを頂きましたが，誰一人としてアフィリエイトで買う人間はおらず，やはり薦める本を失敗した！と後悔し続けた2013年です．

皆様から注目を頂いたベイズ統計ハンドブックですが，やはり1047ページ，28,000円という物理的にもお財布的にも鈍器のように優しくない本を購入する人間はいないということがわかったので，今年はもっとみんなが興味があり，かつ手に取りやすい本をご紹介したいと思います．そこで，MLaPPです．MLaPPとはMachine Learning: a Probabilistic Perspective（著者ページ）というタイトルで，全28章にわたって，Machine Learningを概説している本であり，PRMLと同じくらい注目されても良い本ではないかと個人的には思っています．

あの（自分のブログ経由ではさっぱり売れなかった）ベイズ統計ハンドブックと異なり，1067ページ，8335円(現時点amazon)と，ページ数はより多く，値段は大変お求めやすくなっています！！！kindle版ならなんと5286円(現時点amazon)です！！！1ページあたりの値段を考えると，ベイズ統計ハンドブックより5倍ほどお得です．

．．．．さて，与太話はこのあたりにしておいて，実物を見たことのある人はご存じかと思いますが，MLを俯瞰的に眺められる本の中では現時点で1位といったも過言ではないと思います．しかし，如何せんこの分厚さにより，なかなか読み進めることができません．私はこの本を5月くらいに買いましたが，完全に積み本です．1, 2, 3章くらい読んで，あとはパラパラめくって，へぇ〜いろいろなトピック網羅しているなぁ〜と思って本棚行きです．読破した人はいるのでしょうか…．

ということで，年の瀬のこのクソ忙しい時期に睡眠時間を削ってMLaPPアドベントカレンダーという無謀なチャレンジに挑戦したいと思います．基本的には1章ごとに読んで簡単なメモを作成するということを目標にしたいと思います．だんだん厳しくなってくると思うので，わかった部分だけのメモや重要だと思った点だけのメモになると思います．

28章あるのでアドベントカレンダーの日数と違うじゃないか，どうするつもりだ！というご質問については，どうせ続かないのでそんな先のことを考えても仕方ないというコメントを予めしておきたいと思います．このチャレンジのためにどこでも持ち歩けるようにkindle版も買いました．Murphyに貢いでばかりです．なんとか読破して取り戻したい！！！

Machine learningとは何か？

データ内のパターンを自動的に発見する方法論の集合として定義
将来データの予測，不確実性下における意思決定に役立つパターン発見
確率論のツールを利用
ゴールは確率モデルや推論を通してフィールドに対する統一的な視点を与えること

Machine learningの分類

Supervised learning (predictive learning)
- 入力データxからラベルyへの写像を学習することがゴール
- $y_i$ がカテゴリカル変数であれば，問題は分類・パターン認識
- $y_i$ が実数であれば，問題は回帰
Unsupervised learning (descriptive learning)
- 入力データのみ与えられる
- "興味深いパターン"を発見することがゴール
- これは知識発見(knowledge discovery)と呼ばれる
- このモデルは教師あり学習と異なりerror metricが明らかではない
Reinforcement learning
- 強化学習はマルチエージェントやロボットの分野でやられているイメージ

Supervised learning

分類
- 入力xから出力yへの写像を学習することがゴール
- この問題を定式化する一つの方法は関数近似
- 訓練集合で予測をすることは簡単なので，新たなデータに対する予測をするのが主な目的
- 実世界での適用
  - 文書分類
  - スパムフィルタリング
  - イメージ分類，手書き認識
  - 顔検知と顔認識
回帰
- 実世界での適用
  - 明日の株価の予測
  - Youtubeのviewer数の予測
  - ロボットアームの三次元位置の予測など

Unsupervised learning

ゴールは"興味深い構造"の発見，knowledge discovery
教師あり学習と異なり，各入力に対する望ましい出力が何なのかわからない
- 一つには $p(x_i|\theta)$ のモデルをつくるために密度推定としてタスクを定式化できる
教師あり学習との違い
- $p(y_i|x_i, \theta)$ の代わりに $p(x_i|\theta)$ をモデル化
- は特徴量ベクトルであり，多変量確率モデルをつくる必要
  - 多くの教師あり学習と同じように，問題を十分に単純化した確率モデルを使うことができる
Unsupervised learningに対するHinton先生のありがたいお言葉

我々がなにかをみて学んでいるとき，誰もその正確な答えは教えてくれない．わたしたちはただ見ているだけだ．時折，お母さんは「あれは犬よ」と教えてくれる．でも，それはとっても小さな情報だ．もし，そこから1秒間に2, 3ビットの情報でさえ得たならばラッキーだろう．しかし，脳の視覚システムは10^14のニューラルコネクションをもっている．そして，あなたは10^9秒程度しか生きないのだ．1秒間に1ビット学ぶことは役に立たない．1秒間に10^5 ビット必要なのだ．あなたは入力そのものから，多くの情報を得ることができている．, Hinton (1996) (意訳)

Discovering clusters
- 1番よくある例はデータをグループにクラスタリングすること
- 一つ目のゴールはクラスター数の分布p(K|D)を推定すること
- 二つ目のゴールは各ポイントが属するクラスターを推定すること

Discovering latent factors
- 高次元データを取り扱うとき，データの"essence"を捉えた低次元部分空間にデータを写像する次元削減が有用
- 次元削減に良く使われるアプローチはprincipal components analysis (PCA)
  - biologyではマイクロアレイデータにPCA
  - NLPではlatent semantic analysis for document retrieval
  - 信号処理ではICA

Discovering graph structure
- あるものと最も関連がある他のデータを発見したい
- スパースグラフ学習には2つの主要なアプリケーションがある
  - 新しい知識の発見
  - 結合確率密度をより良くする
  - 図1.11

Matrix Completion
- 実際の値がわからないような欠損値データを得ることもある
- corresponding design matrixの中には穴があいている
- これらの欠損値はしばしばNaNによって表現される
- データ補完のゴールは欠損した入力値に対してもっともらしい値を推測すること
  - Image inpainting
  - Collaborative filtering
  - Market basket analysis

Some basic concepts in machine learning

パラメトリック vs ノンパラメトリック
- パラメトリックモデル
  - モデルが固定された数のパラメータをもつ
  - 速い
  - データ分布について強い仮定をもつ
- ノンパラメトリックモデル
  - パラメータの数が訓練データ量に合わせて変化する
  - より柔軟
  - 大きなデータセットについて計算的に扱いづらい

A simple non-parametric classifier: K-nearest neighbors (KNN)
- 訓練集合の中のテスト入力xに最も近いK個の点を単に見て，この集合内の各クラスの数を数える
- 式(1.2)
- この方法はmemory-based learning or instance-based learningの例
- 一般的な距離計量はユークリッド距離，他の計量も用いることができる

No free lunch theorem
- どんなときでも最高なものはない

他の章へのリンク（随時追加）

とりあえず1章は大丈夫だと思いますが，何章までいけるのでしょうか…．自分予測では7章くらいで死にそうです．ただ関心があるのが中盤から後半にかけてなんだよなぁ…．風邪を引かないようにがんばりたいです．

2013-11-15

Contrastive Divergenceについてお勉強してみた

論文 ML

今週はMLど素人でありながら初めてIBISに参加し，様々な刺激を受けて大変良い1週間でした．いつもtwitter上でご活躍を拝見している方々とリアルに会ったり，遠目に眺めてみたり，話をしたりできたので良かったです．

刺激を受けたご講演・発表は数多くあったのですが，Salakhutdinov先生（いまだに発音がわからない）の基調講演も面白い内容でした．Deep Learningが実装できるような計算機環境やデータを自分が準備できそうにないので，Deep Learning自体の進展については遠巻きにながめているしかないのですが，Restricted Boltzmann Machines (RBM)周辺の話は面白いなぁと素直に感じた次第です．現在，学生さんと自分の研究でGaussian Markov Random Fieldの欠損値推定をノリで行っているのですが，IBISに参加してRBM周辺のお勉強をしなくては！と思い立ち，Salakhutdinov, Mnih and Hinton (2007)*1を読み始めました．そこで，Contrastive Divergenceが重要な概念だなぁと気付き，結局Hinton (2002) *2を読むことにしました．ということで，自分の理解のために，とりあえずまとめてみます．

PoEモデルと最尤推定

次のようなモデルを考えます．
$p({\bf d|\theta}_1,...,{\bf \theta}_n) = \frac{\prod_m f_m ({\bf d|\theta}_m)}{\sum_c\prod_m f_m ({\bf c|\theta}_m)}$
これはProducts of Experts (PoE)モデルと呼ばれており，高次元空間では非効率になりがちな混合モデルに対して，Expertsと呼ばれる個々の複雑なモデルの積として表現することでパワフルなモデルになっています．このPoEを真面目に最尤推定することを考えると，次のようになります．
$\frac{\partial \log p({\bf d | \theta}_1,...,{\bf \theta}_n)}{\partial {\bf \theta}_m} = \frac{\partial \log f_m ({\bf d|}\theta_m)}{\partial {\bf \theta}_m} -$ $\sum\limits_{\bf c} p({\bf c | \theta}_1,...,{\bf \theta}_n) \frac{\partial \log f_m ({\bf c|\theta}_m)}{\partial {\bf \theta}_m}$ 　　　(a)
ここで，第2項はfantasy dataにおける対数尤度の偏微分の期待値となっており，これに真面目に対応するのは大変です．一つにはGibbs Samplingが考えられますが，計算的に大変なだけでなくfantasy dataの分散が大きいという問題があります．

KL DivergenceとContrastive Divergence

このような得られたデータに対する対数尤度を最大化することはデータ分布 $P^0$ と観測変数の均衡分布 $P_{\theta}^\infty$ の間のKL Divergenceを最小化することと等価であることはよく知られています．そこで，KL Divergenceを考えると，次式で表すことができます．
$P^0||P_{\theta}^\infty = \sum\limits_{{\bf d}} P^0({\bf d}) \log P^0 ({\bf d}) - \sum\limits_{{\bf d}}P^0({\bf d})\log P_{\theta}^\infty ({\bf d})$
　　　　 $= -H(P^0) - \left< \log P_{\theta}^\infty \right>_{P^0}$
ここで，<>はある分布上の期待値を表します．H(P^0)はデータ分布上のエントロピーであり，モデルのパラメータに依存しないので，最適化とは無関係です．最適化のために第2項の偏微分を考えるわけですが，データ分布上で平均化すると，式(a)は次のように書き直すことができます．
$\left< \frac{\partial \log P_{\theta}^{\infty} ({\bf D})}{\partial {\bf \theta}_m}\right>_{P^0} = \left< \frac{\partial \log f_{\theta_m}}{\partial {\bf \theta}_m}\right>_{P^0}$ $- \left< \frac{\partial \log f_{\theta_m}}{\partial {\bf \theta}_m}\right>_{P_{\theta}^\infty}$

ここで $P^1$ は1回のfull stepのGibbs Samplingから生成されるデータベクトルの分布とすると，この式の右辺における $P_\theta^\infty$ 上での扱いづらい期待値は次のようにキャンセルアウトできます．
$- \frac{\partial}{\partial {\bf \theta}_m} (P^0||P_\theta^\infty - P^1_\theta ||P_\theta^\infty) = \left< \frac{\partial \log f_{\theta_m}}{\partial {\bf \theta}_m}\right>_{P^0} -$ $\left< \frac{\partial \log f_{\theta_m}}{\partial {\bf \theta}_m}\right>_{P^1_\theta}$ $+ \frac{\partial P_\theta^1}{\partial {\bf \theta}_m}\frac{\partial (P^1_\theta||P_\theta^\infty)}{\partial P^1_\theta}$ 　　　　(b)
PoEモデルでは各expertは扱いやすいモデルが選ばれているため，式(b)の第1項，第2項は計算することができます．第3項は ${\bf \theta}_m$ の変化によって起こる1 stepの分布の変化が $P^1_\theta||P_\theta^\infty$ に与える影響を表しています．これを計算するのは難しいのですが，これは他の2項の影響と比べると小さいので無視することができます．そのため，expertのパラメータはContrastive Divergenceの近似的な微分値に比例する形で調節できます．
$\Delta {\bf \theta}_m \prop \left< \frac{\partial \log f_{\theta_m}}{\partial {\bf \theta}_m}\right>_{P^0} - \left< \frac{\partial \log f_{\theta_m}}{\partial {\bf \theta}_m} \right>_{P^1_\theta}$ (c)

また，式(c)は学習アルゴリズムにおける新たなjustificationを与えています．高次元データセットにおいても，多くの場合，非常に低次元のなめらかな曲がった多様体上にデータはほとんどペタっとなっていたり，近くに集まっていたりします．なので，多様体上の点から始めることで，実用上うまくいきます（いくそうです）．

Contrastive Divergenceの解釈

この変形のありがたいところは，式(a)の均衡分布からのサンプリングによる煩雑な計算を避け， $P^0||P_\theta^\infty$ を最小化するのではなく， $P^0||P_\theta^\infty$ と $P^1||P_\theta^\infty$ の差を最小化する問題として捉えなおす点です．

直観的には均衡分布へのマルコフ連鎖を実行し，initial derivativeとfinal derivativeを比較することの代わりに，1回のfull step チェインを実行して，最初のステップで初期分布からうろうろするチェインの傾向を小さくするようにパラメータを更新するイメージです．ここらへんは自分もまだなんとなくしか理解していないので，この直観的なイメージがあっているのかわかりませんが…．ただ， $P^1_\theta$ は $P^0$ よりも均衡分布に対して1 step近い分布なので， $P^0||P_\theta^\infty$ は $P^1_{\theta}||P_\theta^\infty$ よりも大きいことが保証されており，このContrastive Divergenceは決して負にならないという性質をもっています．

おわりに

1回のfull step Gibbs Samplingで済むというのがContrastive Divergenceの1番のメリットだと思うので，そのあたりを意識すると，最初に読もうとしていたSalakhutdinov, Mnih and Hinton (2007)も読みやすくなるのでは，と思って次はそっちを読みます．まだ納得するほど理解が進んでいないので，Hinton(2002)に書いてある簡単な例なども手を動かしながら理解したいと思います．

そして，ここまで読んだ人へのご褒美ですが，自分が書いた上よりもわかりやすく書いてある持橋さんの資料を見つけましたので，関心がある人は是非ご覧くださいｗ

*1:Salakhutdinov, Mnih and Hinton, Restricted Boltzmann machines for collaborative filtering, ICML, 2007.

*2:Hinton, Training products of experts by minimizing contrastive divergence, Neural Computation, 14, 1711-1800.